the startup process and real mode & protect mode

Linux内核设计的艺术_图解Linux操作系统架构设计与实现原理

从开机加电到执行main函数之前的过程

clip_image002

       从开机到main函数的执行分为三步,目的是实现从启动盘加载操作系统程序,完成执行main函数所需要的准备工作。

clip_image003clip_image003[1]clip_image005

 

1)       启动BIOS,准备实模式下的中断向量表和中断服务程序;

2)       从启动盘加载操作系统到内存;

3)       为执行32main函数做过渡工作

关于实模式和保护模式

clip_image007

实模式:(即实地址访问模式)它是Intel公司80286及以后的x86(80386,8048680586)兼容处理器(CPU)的一种操作模式。实模式被特殊定义为20位地址内存可访问空间上,这就意味着它的容量是220次幂(1M)的可访问内存空间(物理内存和BIOS-ROM),软件可通过这些地址直接访问BIOS程序和外围硬件。实模式下处理器没有硬件级的内存保护概念和多道任务的工作模式。但是为了向下兼容,所以80286及以后的x86系列兼容处理器仍然是开机启动时工作在实模式下。80186和早期的处理器仅有一种操作模式,就是后来我们所定义的实模式。实模式虽然能访问到1M的地址空间,但是由于BIOS的映射作用(即BIOS占用了部分空间地址资源),所以真正能使用的物理内存空间(内存条),也就是在640k924k之间。1M地址空间组成是由16位的段地址和16位的段内偏移地址组成的。用公式表示为:物理地址=左移4位的段地址+偏移地址。

286处理器体系结构引入了地址保护模式的概念,处理器能够对内存及一些其他外围设备做硬件级的保护设置(保护设置实质上就是屏蔽一些地址的访问)。使用这些新的特性,然而必不可少一些额外的在80186及以前处理器没有的操作规程。自从最初的x86微处理器规格以后,它对程序开发完全向下兼容,80286芯片被制作成启动时继承了以前版本芯片的特性,工作在实模式下,在这种模式下实际上是关闭了新的保护功能特性,因此能使以往的软件继续工作在新的芯片下。直到今天,甚至最新的x86处理器都是在计算机加电启动时都是工作在实模式下,它能运行为以前处理器芯片写的程序.

DOS操作系统(例如MS-DOS,DR-DOS)工作在实模式下,微软Windows早期的版本(它本质上是运行在DOS上的图形用户界面应用程序,实际上本身并不是一个操作系统)也是运行在实模式下,直到Windows3.0,它运行期间既有实模式又有保护模式,所以说它是一种混合模式工作。它的保护模式运行有两种不同意义(因为80286并没有完全地实现80386及以后的保护模式功能)

1标准保护模式:这就是程序运行在保护模式下;

2虚拟保护模式(实质上还是实模式,是实模式上模拟的保护模式):它也使用32位地址寻址方式。Windows3.1彻底删除了对实模式的支持。在80286处理器芯片以后,Windows3.1成为主流操作系统(Windows/80286不是主流产品)。目前差不多所有的X86系列处理器操作系统(LinuxWindows95 and laterOS/2等)都是在启动时进行处理器设置而进入保护模式的。

实模式工作机理:

1> 对于8086/8088来说计算实际地址是用绝对地址对1M求模。8086的地址线的物理结构:20根,也就是它可以物理寻址的内存范围为2^20个字节,即1 M空间,但由于8086/8088所使用的寄存器都是16位,能够表示的地址范围只有0-64K,这和1M地址空间来比较也太小了,所以为了在8086/8088下能够访问1M内存,Intel采取了分段寻址的模式:16位段基地址:16位偏移EA。其绝对地址计算方法为:16位基地址左移4+16位偏移=20位地址。  比如:DS=1000H EA=FFFFH 那么绝对地址就为:10000H + 0FFFFH = 1FFFFH 地址单元。通过这种方法来实现使用16位寄存器访问1M的地址空间,这种技术是处理器内部实现的,通过上述分段技术模式,能够表示的最大内存为:FFFFh: FFFFh=FFFF0h+FFFFh=10FFEFh=1M+64K-16Bytes1M多余出来的部分被称做高端内存区HMA)。但8086/8088只有20位地址线,只能够访问1M地址范围的数据,所以如果访问100000h~10FFEFh之间的内存(大于1M空间),则必须有第21根地址线来参与寻址(8086/8088没有)。因此,当程序员给出超过1M100000H-10FFEFH)的地址时,因为逻辑上正常,系统并不认为其访问越界而产生异常,而是自动从0开始计算,也就是说系统计算实际地址的时候是按照对1M求模的方式进行的,这种技术被称为wrap-around

2> 对于80286或以上的CPU通过A20 GATE来控制A20地址线。 技术发展到了80286,虽然系统的地址总线由原来的20根发展为24根,这样能够访问的内存可以达到2^24=16M,但是Intel在设计80286时提出的目标是向下兼容,所以在实模式下,系统所表现的行为应该和8086/8088所表现的完全一样,也就是说,在实模式下,80386以及后续系列应该和8086/8088完全兼容仍然使用A20地址线。所以说80286芯片存在一个BUG:它开设A20地址线。如果程序员访问100000H-10FFEFH之间的内存,系统将实际访问这块内存(没有wrap-around技术),而不是象8086/8088一样从0开始。我们来看一副图:

 clip_image008

      为了解决上述兼容性问题,IBM使用键盘控制器上剩余的一些输出线来管理第21根地址线(从0开始数是第20根) 的有效性,被称为A20 Gate

      1> 如果A20 Gate被打开,则当程序员给出100000H-10FFEFH之间的地址的时候,系统将真正访问这块内存区域;

      2 如果A20 Gate被禁止,则当程序员给出100000H-10FFEFH之间的地址的时候,系统仍然使用8086/8088的方式即取模方式(8086仿真)。绝大多数IBM PC兼容机默认的A20 Gate是被禁止的。现在许多新型PC上存在直接通过BIOS功能调用来控制A20 Gate的功能。

      上面所述的内存访问模式都是实模式,在80286以及更高系列的PC中,即使A20 Gate被打开,在实模式下所能够访问的内存最大也只能为10FFEFH,尽管它们的地址总线所能够访问的能力都大大超过这个限制。为了能够访问10FFEFH以上的内存,则必须进入保护模式。

保护模式:经常缩写为p-mode,Intel iAPX 286程序员参考手册中(iAPX 286Intel 80286的另一种叫法)它又被称作为虚拟地址保护模式。经管在Intel 80286手册中已经提出了虚地址保护模式,但实际上它只是一个指引,真正的32位地址出现在Intel 80386上。保护模式本身是80286及以后兼容处理器序列之后产成的一种操作模式,它具有许多特性设计为提高系统的多道任务和系统的稳定性。例如内存的保护,分页机制和硬件虚拟存储的支持。现代多数的x86处理器操作系统都运行在保护模式下,包括Linux, Free BSD, Windows 3.0(它也运行在实模式下,为了和Windows 2.x应用程序兼容)及以后的版本。

80286及以后的处理器另一种工作模式是实模式(仅当系统启动的一瞬间),本着向下兼容的原则屏蔽保护模式特性,从而容许老的软件能够运行在新的芯片上。作为一个设计规范,所有的x86系列处理器,除嵌入式Intel80387之外,都是系统启动工作在实模式下,确保遗留下的操作系统向下兼容。它们都必须被启动程序(操作系统程序最初运行代码)重新设置而相应进入保护模式的,在这之前任何的保护模式特性都是无效的。在现代计算机中,这种匹配进入保护模式是操作系统启动时最前沿的动作之一。

在被调停的多道任务程序中,它可以从新工作在实模式下是相当可能的。保护模式的特性是阻止被其他任务或系统内核破坏已经不健全的程序的运行,保护模式也有对硬件的支持,例如中断运行程序,移动运行进程文档到另一个进程和置空多任务的保护功能。

386及以后系列处理器不仅具有保护模式又具有32位寄存器,结果导致了处理功能的混乱,因为80286虽然支持保护模式,但是它的寄存器都是16位的,它是通过自身程序设定而模拟出的32位,并非32位寄存器处理。归咎于这种混乱现象,它促使Windows/386及以后的版本彻底抛弃80286的虚拟保护模式,以后保护模式的操作系统都是运行在80386以上,不再运行在80286(尽管80286模式支持保护模式),所以说80286是一个过渡芯片,它是一个过渡产品。

尽管286386处理器能够实现保护模式和兼容以前的版本,但是内存的1M以上空间还是不易存取,由于内存地址的回绕,IBM PC XT (现以废弃)设计一种模拟系统,它能过欺骗手段访问到1M以上的地址空间,就是开通了A20地址线。在保护模式里,前32个中断为处理器异常预留,例如,中断0D(十进制13)常规保护故障和中断00是除数为零异常。

如果要访问更多的内存,则必须进入保护模式,那么,在保护模式下,A20 Gate对于内存访问有什么影响呢?

      为了搞清楚这一点,我们先来看一看A20的工作原理。A20,从它的名字就可以看出来,其实它就是对于A20(从0开始数)的特殊处理(也就是对第21根地址线的处理)。如果A20 Gate被禁止,对于80286来说,其地址为24根地址线,其地址表示为EFFFFF;对于80386极其随后的32根地址线芯片来说,其地址表示为FFEFFFFF。这种表示的意思是:

clip_image009

    1> 如果A20 Gate被禁止。则其第A20CPU做地址访问的时候是无效的,永远只能被作为0。所以,在保护模式下,如果A20 Gate被禁止,则可以访问的内存只能是奇数1M段,即1M,3M,5M…,也就是00000-FFFFF, 200000-2FFFFF,300000-3FFFFF…

      2如果A20 Gate被打开。则其第20-bit是有效的,其值既可以是0,又可以是1。那么就可以使A20线传递实际的地址信号。如果A20 Gate被打开,则可以访问的内存则是连续的。

实模式和保护模式的区别:从表面上看,保护模式和实模式并没有太大的区别,二者都使用了内存段、中断和设备驱动来处理硬件,但二者有很多不同之处。我们知道,在实模式中内存被划分成段,每个段的大小为64KB,而这样的段地址可以用16位来表示。内存段的处理是通过和段寄存器相关联的内部机制来处理的,这些段寄存器(CSDS SSES)的内容形成了物理地址的一部分。具体来说,最终的物理地址是由16位的段地址和16位的段内偏移地址组成的。用公式表示为:物理地址=左移4位的段地址+偏移地址。

在保护模式下,段是通过一系列被称之为描述符表的表所定义的。段寄存器存储的是指向这些表的指针。用于定义内存段的表有两种:全局描述符表(GDT) 和局部描述符表(LDT)GDT是一个段描述符数组,其中包含所有应用程序都可以使用的基本描述符。在实模式中,段长是固定的(64KB),而在保护模式中,段长是可变的,其最大可达4GBLDT也是段描述符的一个数组。与GDT不同,LDT是一个段,其中存放的是局部的、不需要全局共享的段描述符。每一个操作系统都必须定义一个GDT,而每一个正在运行的任务都会有一个相应的LDT。每一个描述符的长度是8个字节,格式如图3所示。当段寄存器被加载的时候,段基地址就会从相应的表入口获得。描述符的内容会被存储在一个程序员不可见的影像寄存器(shadow register)之中,以便下一次同一个段可以使用该信息而不用每次都到表中提取。物理地址由16位或者32位的偏移加上影像寄存器中的基址组成。实模式和保护模式的不同可以从下图很清楚地看出来。

clip_image010

                  实模式下寻址方式

 

 

   clip_image011

                     保护模式下寻址方式

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

the start sequence of Linux

2013-08-21Linux 的启动流程

Refer from :

http://www.ruanyifeng.com/blog/2013/08/linux_boot_process.html

作者: 阮一峰

日期: 2013817

半年前,我写了《计算机是如何启动的?》,探讨BIOS和主引导记录的作用。

那篇文章不涉及操作系统,只与主板的板载程序有关。今天,我想接着往下写,探讨操作系统接管硬件以后发生的事情,也就是操作系统的启动流程。

clip_image001

这个部分比较有意思。因为在BIOS阶段,计算机的行为基本上被写死了,程序员可以做的事情并不多;但是,一旦进入操作系统,程序员几乎可以定制所有方面。所以,这个部分与程序员的关系更密切。

我主要关心的是Linux操作系统,它是目前服务器端的主流操作系统。下面的内容针对的是Debian发行版,因为我对其他发行版不够熟悉。

第一步、加载内核

操作系统接管硬件以后,首先读入 /boot 目录下的内核文件。

clip_image002

以我的电脑为例,/boot 目录下面大概是这样一些文件:

 

  $ ls /boot

  

  config-3.2.03amd64

  config-3.2.04amd64

  grub

  initrd.img-3.2.03amd64

  initrd.img-3.2.04amd64

  System.map-3.2.03amd64

  System.map-3.2.04amd64

  vmlinuz-3.2.03amd64

  vmlinuz-3.2.04amd64

  

第二步、启动初始化进程

内核文件加载以后,就开始运行第一个程序 /sbin/init,它的作用是初始化系统环境。

clip_image003

由于init是第一个运行的程序,它的进程编号(pid)就是1。其他所有进程都从它衍生,都是它的子进程。

第三步、确定运行级别

许多程序需要开机启动。它们在Windows叫做服务service),在Linux就叫做守护进程daemon)。

init进程的一大任务,就是去运行这些开机启动的程序。但是,不同的场合需要启动不同的程序,比如用作服务器时,需要启动Apache,用作桌面就不需要。Linux允许为不同的场合,分配不同的开机启动程序,这就叫做运行级别runlevel)。也就是说,启动时根据运行级别,确定要运行哪些程序。

clip_image004

Linux预置七种运行级别(0-6)。一般来说,0是关机,1是单用户模式(也就是维护模式),6是重启。运行级别2-5,各个发行版不太一样,对于Debian来说,都是同样的多用户模式(也就是正常模式)。

init进程首先读取文件 /etc/inittab,它是运行级别的设置文件。如果你打开它,可以看到第一行是这样的:

 

  id:2:initdefault:

  

initdefault的值是2,表明系统启动时的运行级别为2。如果需要指定其他级别,可以手动修改这个值。

那么,运行级别2有些什么程序呢,系统怎么知道每个级别应该加载哪些程序呢?……回答是每个运行级别在/etc目录下面,都有一个对应的子目录,指定要加载的程序。

 

  /etc/rc0.d

  /etc/rc1.d

  /etc/rc2.d

  /etc/rc3.d

  /etc/rc4.d

  /etc/rc5.d

  /etc/rc6.d

  

上面目录名中的“rc”,表示run command(运行程序),最后的d表示directory(目录)。下面让我们看看 /etc/rc2.d 目录中到底指定了哪些程序。

 

  $ ls  /etc/rc2.d

  

  README

  S01motd

  S13rpcbind

  S14nfscommon

  S16binfmtsupport

  S16rsyslog

  S16sudo

  S17apache2

  S18acpid

  

  

可以看到,除了第一个文件README以外,其他文件名都是字母S+两位数字+程序名的形式。字母S表示Start,也就是启动的意思(启动脚本的运行参数为start),如果这个位置是字母K,就代表Kill(关闭),即如果从其他运行级别切换过来,需要关闭的程序(启动脚本的运行参数为stop)。后面的两位数字表示处理顺序,数字越小越早处理,所以第一个启动的程序是motd,然后是rpcbingnfs……数字相同时,则按照程序名的字母顺序启动,所以rsyslog会先于sudo启动。

这个目录里的所有文件(除了README),就是启动时要加载的程序。如果想增加或删除某些程序,不建议手动修改 /etc/rcN.d 目录,最好是用一些专门命令进行管理(参考这里这里)。

第四步、加载开机启动程序

前面提到,七种预设的运行级别各自有一个目录,存放需要开机启动的程序。不难想到,如果多个运行级别需要启动同一个程序,那么这个程序的启动脚本,就会在每一个目录里都有一个拷贝。这样会造成管理上的困扰:如果要修改启动脚本,岂不是每个目录都要改一遍?

Linux的解决办法,就是七个 /etc/rcN.d 目录里列出的程序,都设为链接文件,指向另外一个目录 /etc/init.d ,真正的启动脚本都统一放在这个目录中。init进程逐一加载开机启动程序,其实就是运行这个目录里的启动脚本。

clip_image005

下面就是链接文件真正的指向。

 

  $ ls l /etc/rc2.d

  

  README

  S01motd -> ../init.d/motd

  S13rpcbind -> ../init.d/rpcbind

  S14nfscommon -> ../init.d/nfscommon

  S16binfmtsupport -> ../init.d/binfmtsupport

  S16rsyslog -> ../init.d/rsyslog

  S16sudo -> ../init.d/sudo

  S17apache2 -> ../init.d/apache2

  S18acpid -> ../init.d/acpid

  

  

这样做的另一个好处,就是如果你要手动关闭或重启某个进程,直接到目录 /etc/init.d 中寻找启动脚本即可。比如,我要重启Apache服务器,就运行下面的命令:

 

  $ sudo /etc/init.d/apache2 restart

  

/etc/init.d 这个目录名最后一个字母d,是directory的意思,表示这是一个目录,用来与程序 /etc/init 区分。

第五步、用户登录

开机启动程序加载完毕以后,就要让用户登录了。

clip_image006

一般来说,用户的登录方式有三种:

  (1)命令行登录

  (2ssh登录

  (3)图形界面登录

这三种情况,都有自己的方式对用户进行认证。

1)命令行登录:init进程调用getty程序(意为get teletype),让用户输入用户名和密码。输入完成后,再调用login程序,核对密码(Debian还会再多运行一个身份核对程序/etc/pam.d/login)。如果密码正确,就从文件 /etc/passwd 读取该用户指定的shell,然后启动这个shell

2ssh登录:这时系统调用sshd程序(Debian还会再运行/etc/pam.d/ssh ),取代gettylogin,然后启动shell

3)图形界面登录:init进程调用显示管理器,Gnome图形界面对应的显示管理器为gdmGNOME Display Manager),然后用户输入用户名和密码。如果密码正确,就读取/etc/gdm3/Xsession,启动用户的会话。

第六步、进入 login shell

所谓shell,简单说就是命令行界面,让用户可以直接与操作系统对话。用户登录时打开的shell,就叫做login shell

clip_image007

Debian默认的shellBash,它会读入一系列的配置文件。上一步的三种情况,在这一步的处理,也存在差异。

1)命令行登录:首先读入 /etc/profile,这是对所有用户都有效的配置;然后依次寻找下面三个文件,这是针对当前用户的配置。

 

  ~/.bash_profile

  ~/.bash_login

  ~/.profile

  

需要注意的是,这三个文件只要有一个存在,就不再读入后面的文件了。比如,要是 ~/.bash_profile 存在,就不会再读入后面两个文件了。

2ssh登录:与第一种情况完全相同。

3)图形界面登录:只加载 /etc/profile ~/.profile。也就是说,~/.bash_profile 不管有没有,都不会运行。

第七步,打开 non-login shell

老实说,上一步完成以后,Linux的启动过程就算结束了,用户已经可以看到命令行提示符或者图形界面了。但是,为了内容的完整,必须再介绍一下这一步。

用户进入操作系统以后,常常会再手动开启一个shell。这个shell就叫做 non-login shell,意思是它不同于登录时出现的那个shell,不读取/etc/profile.profile等配置文件。

clip_image008

non-login shell的重要性,不仅在于它是用户最常接触的那个shell,还在于它会读入用户自己的bash配置文件 ~/.bashrc。大多数时候,我们对于bash的定制,都是写在这个文件里面的。

你也许会问,要是不进入 non-login shell,岂不是.bashrc就不会运行了,因此bash 也就不能完成定制了?事实上,Debian已经考虑到这个问题了,请打开文件 ~/.profile,可以看到下面的代码:

 

  if [ n $BASH_VERSION ]; then

    if [ f $HOME/.bashrc” ]; then

      . $HOME/.bashrc”

    fi

  fi

  

上面代码先判断变量 $BASH_VERSION 是否有值,然后判断主目录下是否存在 .bashrc 文件,如果存在就运行该文件。第三行开头的那个点,是source命令的简写形式,表示运行某个文件,写成“source ~/.bashrc”也是可以的。

因此,只要运行~/.profile文件,~/.bashrc文件就会连带运行。但是上一节的第一种情况提到过,如果存在~/.bash_profile文件,那么有可能不会运行~/.profile文件。解决这个问题很简单,把下面代码写入.bash_profile就行了。

 

  if [ f ~/.profile ]; then

    . ~/.profile

  fi

  

这样一来,不管是哪种情况,.bashrc都会执行,用户的设置可以放心地都写入这个文件了。

Bash的设置之所以如此繁琐,是由于历史原因造成的。早期的时候,计算机运行速度很慢,载入配置文件需要很长时间,Bash的作者只好把配置文件分成了几个部分,阶段性载入。系统的通用设置放在 /etc/profile,用户个人的、需要被所有子进程继承的设置放在.profile,不需要被继承的设置放在.bashrc

顺便提一下,除了Linux以外, Mac OS X 使用的shell也是Bash。但是,它只加载.bash_profile,然后在.bash_profile里面调用.bashrc。而且,不管是ssh登录,还是在图形界面里启动shell窗口,都是如此。

参考链接

[1] Debian Wiki, Environment Variables

[2] Debian Wiki, Dot Files

[3] Debian Administration, An introduction to run-levels

[4] Debian AdminDebian and Ubuntu Linux Run Levels

[5] Linux Information Project (LINFO), Runlevel Definition

[6] LinuxQuestions.org, What are run levels?

[7] Dalton Hubble, Bash Configurations Demystified

(完)

 

non–standard alias for PG-function

非标准的一些函数

l  PGADVANCE — non-standard alias for PGPAGE

l  PGBEGIN — non-standard alias for PGBEG

l  PGCURSE — non-standard alias for PGCURS

l  PGLABEL — non-standard alias for PGLAB

l  PGMTEXT — non-standard alias for PGMTXT

l  PGNCURSE — non-standard alias for PGNCUR

l  PGPAPER — non-standard alias for PGPAP

l  PGPOINT — non-standard alias for PGPT

l  PGPTEXT — non-standard alias for PGPTXT

l  PGVPORT — non-standard alias for PGSVP

l  PGVSIZE — non-standard alias for PGVSIZ

l  PGVSTAND — non-standard alias for PGVSTD

l  PGWINDOW — non-standard alias for PGSWIN

PGADVANCE非标准的PGPAGE

PGBEGIN非标准的PGBEG

PGCURSE非标准的PGCURS

PGLABEL非标准的PGLAB

PGMTEXT非标准的PGMTXT

PGNCURSE非标准的PGNCUR

PGPAPER非标准的PGPAP

PGPOINT非标准的PGPT

PGPTEXT非标准的PGPTXT

PGVPORT非标准的PGSVP

PGVSIZE非标准的PGVSIZ

PGVSTAND非标准的PGVSTD

PGWINDOW非标准的PGSWIN

vnc problem vncviewer

VNC 登录问题

对于从windows登录到linux的众多软件中,vnc在图形化做的偶觉得还是很好的。
但是今天碰到了这个问题:


Oh no! Something has gone wrong. A problem has ocurred and the system can’t recover.”

以前从来没有遇到过,解决方法重启一下就ok了。
比如开的是N端口,而ip192.168.1.111,那么使用vncviewer登录的时候就是


192.168.1.111N

此时只需要ssh192.168.1.111机器,使用
vncserver -kill :N
vncserver N
即可。

clip_image001

 

Cyclic Redundancy Check

CRC校验码

校验原理

1、循环校验码(CRC码):是数据通信领域中最常用的一种差错校验码,其特征是信息字段和校验字段的长度可以任意选定。

2、生成CRC码的基本原理:任意一个由二进制位串组成的代码都可以和一个系数仅为‘0’‘1’取值的多项式一一对应。例如:代码1010111对应的多项式为x6+x4+x2+x+1,而多项式为x5+x3+x2+x+1对应的代码101111

3CRC码集选择的原则:若设码字长度为N,信息字段为K位,校验字段为R(N=K+R),则对于CRC码集中的任一码字,存在且仅存在一个R次多项式g(x),使得

V(x)=A(x)g(x)=xRm(x)+r(x);

其中:    m(x)K次信息多项式, r(x)R-1次校验多项式,

         g(x)称为生成多项式:

g(x)=g0+g1x+ g2x2+…+g(R-1)x(R-1)+gRxR

发送方通过指定的g(x)产生CRC码字,接收方则通过该g(x)来验证收到的CRC码字。

4CRC校验码软件生成方法:

    借助于多项式除法,其余数为校验字段。

例如:信息字段代码为: 1011001;对应m(x)=x6+x4+x3+1

      假设生成多项式为:g(x)=x4+x3+1;则对应g(x)的代码为: 11001

      x4m(x)=x10+x8+x7+x4 对应的代码记为:10110010000

采用多项式除法得余数为: 1010     (即校验字段为:1010

发送方:发出的传输字段为1 0 1 1 0 0 1 1 0 10

                          信息字段       校验字段

接收方:使用相同的生成码进行校验:接收到的字段/生成码(二进制除法)

                  如果能够除尽,则正确,

 

 

 

CRC校验原理看起来比较复杂,好难懂,因为大多数书上基本上是以二进制的多项式形式来说明的。其实很简单的问题,其根本思想就是先在要发送的帧后面附加一个数(这个就是用来校验的校验码,但要注意,这里的数也是二进制序列的,下同),生成一个新帧发送给接收端。当然,这个附加的数不是随意的,它要使所生成的新帧能与发送端和接收端共同选定的某个特定数整除(注意,这里不是直接采用二进制除法,而是采用一种称之为2除法)。到达接收端后,再把接收到的新帧除以(同样采用2除法)这个选定的除数。因为在发送端发送数据帧之前就已通过附加一个数,做了去余处理(也就已经能整除了),所以结果应该是没有余数。如果有余数,则表明该帧在传输过程中出现了差错。

 

 

CRC 根据”(即多项表达式)的不同而相应的源代码也有稍许不同。以下是各种常用的权。

l  CRC8=X8+X5+X4+1

l  CRC-CCITT=X16+X12+X5+1

l  CRC16=X16+X15+X5+1

l  CRC12=X12+X11+X3+X2+1

l  CRC32=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1+1    

 

以下的源程序全部以 CCITT 为例。其实本质都是一样,搞明白一种,其他的都是小菜。

 

typedef    unsigned char     uchar;
typedef    unsigned int      uint;
 
code uchar crcbuff [] = { 0x00,0x00,0x00,0x00,0x06,0x0d,0xd2,0xe3};
uint crc;                  // CRC

void main(void)
{
  uchar *ptr;
  crc = 0;                // CRC 
初值

  ptr = crcbuff;              // 
指向第一个 Byte 数据

  crc = crc16l(ptr,8);           
  while(1);
}
 
uint crc16l(uchar *ptr,uchar len)        // ptr
为数据指针,len 为数据长度

{
  uchar i;
  while(len–)
  {
      for(i=0x80; i!=0; i>>=1)
    {
        if((crc&0x8000)!=0) {crc<<=1; crc^=0x1021;}        1-1  
          else crc<<=1;                     1-2
      if((*ptr&i)!=0) crc^=0x1021;                       1-3  
    }
    ptr++;
  }
  return(crc);
}
 

执行结果
crc = 0xdbc0;
程序 1-1,1-2,1-3 可以理解成移位前 crc  Bit15 与数据对应的 Bit(*ptr&i) XOR运算,根据此结果来决定是否执行 crc^=0x1021。只要明白两次异或运算与原值相同,就不难理解这个程序。

 

很多资料上都写了查表法来计算,当时是怎么也没想通。其实蛮简单的。假设通过移位处理了 8 bit 的数据,相当于把之前的 CRC 码的高字节(8bit)全部移出,与一个 byte 的数据做XOR 运算,根据运算结果来选择一个值(称为余式),与原来的 CRC 码再做一次 XOR 运算,就可以得到新的 CRC 码。

 

 
本质上 CRC 计算的就是移位和异或。所以一次处理移动几位都没有关系,只要做相应的处理就好了。
下面给出半字节查表的处理程序。其实和全字节是一回事。

 

循环冗余校验码

  CRCCyclic Redundancy Check)循环冗余校验码是常用的校验码,在早期的通信中运用广泛,因为早期的通信技术不够可靠(不可靠性的来源是通信技术决定的,比如电磁波通信时受雷电等因素的影响),不可靠的通信就会带来确认信息的困惑,书上提到红军和蓝军通信联合进攻山下的敌军的例子,第一天红军发了条信息要蓝军第二天一起进攻,蓝军收到之后,发一条确认信息,但是蓝军担心的是确认信息如果也不可靠而没有成功到达红军那里,那自己不是很危险?于是红军再发一条对确认的确认信息,但同样的问题还是不能解决,红军仍然不敢贸然行动。

  对通信的可靠性检查就需要校验,校验是从数据本身进行检查,它依靠某种数学上约定的形式进行检查,校验的结果是可靠或不可靠,如果可靠就对数据进行处理,如果不可靠,就丢弃重发或者进行修复。

  CRC码是由两部分组成,前部分是信息码,就是需要校验的信息,后部分是校验码,如果CRC码共长nbit,信息码长kbit,就称为(n,k)码。 它的编码规则是:

  1、首先将原信息码(kbit)左移r(k+r=n)

  2、运用一个生成多项式g(x)(也可看成二进制数)用模2除上面的式子,得到的余数就是校验码。

  非常简单,要说明的:模2除就是在除的过程中用模2加,模2加实际上就是我们熟悉的异或运算,就是加法不考虑进位,公式是:

  0+0=1+1=0,1+0=0+1=1

  即则真,非异则假。

  由此得到定理:a+b+b=a 也就是22直值表完全相同。

  有了加减法就可以用来定义模2除法,于是就可以用生成多项式g(x)生成CRC校验码。

  例如: g(x)=x4+x3+x2+1,(7,3),信息码110产生的CRC码就是:

  对于g(x)=x4+x3+x2+1的解释:(都是从右往左数)x4就是第五位是1,因为没有x1所以第2位就是0

  11101 | 110,0000(设a=11101 b=1100000

  取b的前511000a异或得到101

  101加上b没有取到的00得到10100

  然后跟a异或得到01001

  也就是余数1001

  余数是1001,所以CRC码是110,1001

  标准的CRC码是,CRC-CCITTCRC-16,它们的生成多项式是:

  CRC-CCITT=x^16+x^12+x^5+1

  CRC-16=x^16+x^15+x^2+1

 

 

2 CRC校验的C语言实现
下面我们以CRC-16为例来说明任意长度数据流的CRC校验码生成过程。我们采用将数据流分成若干个8bit字符,并由低字节到高字节传送的并行方法来求CRC校验码。具体计算过程为:用一个16bit的寄存器来存放CRC校验值,且设定其初值为0x0000;将数据流的第一个8bit16bitCRC寄存器的高字节相异或,并将结果存入CRC寄存器高字节;CRC寄存器左移一位,最低1bit补零,同时检查移出的最高1bit,若移出的最高1bit0,则继续按上述过程左移,若最高1bit1,则将CRC寄存器中的值与生成多项式码相异或,结果存入CRC寄存器值;继续左移并重复上述处理方法,直到将8bit数据处理完为止,则此时CRC寄存器中的值就是第一个8bit数据对应的CRC校验码;然后将此时CRC寄存器的值作为初值,用同样的处理方法重复上述步骤来处理下一个8bit数据流,直到将所有的8bit字符都处理完后,此刻CRC寄存器中的值即为整个数据流对应的CRC校验码。

下面示出了其计算过程的流程图:

在用C语言编写CRC校验码的实现程序时我们应该注意,生成多项式 对应的十六进制数为0x18005,由于CRC寄存器左移过程中,移出的最高位为1时与 相异或,所以与16bitCRC寄存器对应的生成多项式的十六进制数可用0x8005表示。下面给出并行处理8bit数据流的C源程序:
unsigned short crc_dsp(unsigned short reg, unsigned char data_crc)
//reg
crc寄存器, data_crc为将要处理的8bit数据流

{
unsigned short msb; //crc
寄存器将移出的最高
1bit
unsigned short data;
unsigned short gx = 0x8005, i = 0; //i
为左移次数, gx为生成多项式

data = (unsigned short)data_crc;
data = data << 8;
reg = reg ^ data;
do
{
msb = reg & 0x8000;
reg = reg << 1;
if(msb == 0x8000)
{
reg = reg ^ gx;
}
i++;
}
while(i < 8);
return (reg);
}

以上为处理每一个8bit数据流的子程序,在计算整个数据流的CRC校验码时,我们只需将CRC_reg的初值置为0x0000,求第一个8bitCRC值,之后,即可将上次求得的CRC值和本次将要处理的8bit数据作为函数实参传递给上述子程序的形参进行处理即可,最终返回的reg值便是我们所想得到的整个数据流的CRC校验值。


 

 

其实CRC可以用查表的方法。
/*
CRC
校验算法实现 C语言代码实现

文件
CRC16.h
*/
#ifndef _CRC16_h
#define _CRC16_h
static unsigned char auchCRCHi[] = {
0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0,
0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41,
0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0,
0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40,
0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1,
0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41,
0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1,
0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41,
0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0,
0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40,
0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1,
0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40,
0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0,
0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40,
0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0,
0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40,
0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0,
0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41,
0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0,
0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41,
0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0,
0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40,
0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1,
0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41,
0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0,
0x80, 0x41, 0x00, 0xC1, 0x81, 0x40
};
/* CRC
低位字节值表
*/
static char auchCRCLo[] = {
0x00, 0xC0, 0xC1, 0x01, 0xC3, 0x03, 0x02, 0xC2, 0xC6, 0x06,
0x07, 0xC7, 0x05, 0xC5, 0xC4, 0x04, 0xCC, 0x0C, 0x0D, 0xCD,
0x0F, 0xCF, 0xCE, 0x0E, 0x0A, 0xCA, 0xCB, 0x0B, 0xC9, 0x09,
0x08, 0xC8, 0xD8, 0x18, 0x19, 0xD9, 0x1B, 0xDB, 0xDA, 0x1A,
0x1E, 0xDE, 0xDF, 0x1F, 0xDD, 0x1D, 0x1C, 0xDC, 0x14, 0xD4,
0xD5, 0x15, 0xD7, 0x17, 0x16, 0xD6, 0xD2, 0x12, 0x13, 0xD3,
0x11, 0xD1, 0xD0, 0x10, 0xF0, 0x30, 0x31, 0xF1, 0x33, 0xF3,
0xF2, 0x32, 0x36, 0xF6, 0xF7, 0x37, 0xF5, 0x35, 0x34, 0xF4,
0x3C, 0xFC, 0xFD, 0x3D, 0xFF, 0x3F, 0x3E, 0xFE, 0xFA, 0x3A,
0x3B, 0xFB, 0x39, 0xF9, 0xF8, 0x38, 0x28, 0xE8, 0xE9, 0x29,
0xEB, 0x2B, 0x2A, 0xEA, 0xEE, 0x2E, 0x2F, 0xEF, 0x2D, 0xED,
0xEC, 0x2C, 0xE4, 0x24, 0x25, 0xE5, 0x27, 0xE7, 0xE6, 0x26,
0x22, 0xE2, 0xE3, 0x23, 0xE1, 0x21, 0x20, 0xE0, 0xA0, 0x60,
0x61, 0xA1, 0x63, 0xA3, 0xA2, 0x62, 0x66, 0xA6, 0xA7, 0x67,
0xA5, 0x65, 0x64, 0xA4, 0x6C, 0xAC, 0xAD, 0x6D, 0xAF, 0x6F,
0x6E, 0xAE, 0xAA, 0x6A, 0x6B, 0xAB, 0x69, 0xA9, 0xA8, 0x68,
0x78, 0xB8, 0xB9, 0x79, 0xBB, 0x7B, 0x7A, 0xBA, 0xBE, 0x7E,
0x7F, 0xBF, 0x7D, 0xBD, 0xBC, 0x7C, 0xB4, 0x74, 0x75, 0xB5,
0x77, 0xB7, 0xB6, 0x76, 0x72, 0xB2, 0xB3, 0x73, 0xB1, 0x71,
0x70, 0xB0, 0x50, 0x90, 0x91, 0x51, 0x93, 0x53, 0x52, 0x92,
0x96, 0x56, 0x57, 0x97, 0x55, 0x95, 0x94, 0x54, 0x9C, 0x5C,
0x5D, 0x9D, 0x5F, 0x9F, 0x9E, 0x5E, 0x5A, 0x9A, 0x9B, 0x5B,
0x99, 0x59, 0x58, 0x98, 0x88, 0x48, 0x49, 0x89, 0x4B, 0x8B,
0x8A, 0x4A, 0x4E, 0x8E, 0x8F, 0x4F, 0x8D, 0x4D, 0x4C, 0x8C,
0x44, 0x84, 0x85, 0x45, 0x87, 0x47, 0x46, 0x86, 0x82, 0x42,
0x43, 0x83, 0x41, 0x81, 0x80, 0x40
};
/*
要进行CRC校验的消息 */ /* 消息中字节数
*/
unsigned short CRC16(unsigned char *puchMsg,unsigned short usDataLen )
{
unsigned char uchCRCHi = 0xFF ; /*
CRC字节初始化
*/
unsigned char uchCRCLo = 0xFF ; /*
CRC 字节初始化
*/
unsigned uIndex ; /* CRC
循环中的索引
*/
while (usDataLen–) /*
传输消息缓冲区
*/
{
uIndex = uchCRCHi ^ *puchMsg++ ; /*
计算
CRC */
uchCRCHi = uchCRCLo ^ auchCRCHi[uIndex];
uchCRCLo = auchCRCLo[uIndex] ;
}
return (uchCRCHi < < 8 | uchCRCLo) ;
}
#endif //_CRC16_h

/*
CRC16.cpp

生成 CRC码实现

*/
#include <stdio.h>
#include “CRC16.h”
void main()
{
unsigned char ppp[13] = {0x12,0x34};
    unsigned short result; 
    //
计算
CRC
    result = CRC16(ppp, 2);
printf(“%x\n”,result);
}