优秀课设——计算校验和

四 川 理 工 学 院课 程 设 计 书学院 计 算 机 学 院 专业 计 算 机 科 学 与 技 术 班级 零 八 级 六 班 题目 SNMP 的 简 单 实 现 教师 鲜乾坤 陈 超 学生 杨忠书 王琼伍 鲁阳琼 摘要IP协议为提高数据传输效率，简化了协议，舍弃了许多为提供可靠性所需要的工作（如建立连接、维护连接、拆除连接、确认应答、时间片处理等）。其唯一的正确性检验即依靠头部校验和，以保证头部数据的完整性。为了研究IP 首部校验算法，查看了相关的RFC文档并利用wireshark工具进行了抓包，并对抓包取得的数据进行了计算验证。研究发现了一些算法存在一定的问题并对它的改进算法进行了研究。关键字： 计算校验和 并行计算 字节顺序 延迟 进位前言 本课程设计的主要意图是，通过计算机网络中的计算校验和来了解计算机是怎么样判断接收数据的正确与错误。同时也让我们更进一步的了解计算机的一般思想，从而了解计算校验和的目的与作用。最后我们要学会计算校验和，了解和扩展计算机网络的知识面。校验和的作用就是保证数据传送的正确性。本次课程设计的主要内容包括以下几个方面：课程设计目的，通过这一点我们可以了解我们为什么要计算校验和，它的作用和目的是什么，从而学会计算校验和。课程设计的要求，根据下面课程设计中的计算方法编制程序为给定数据计算检验和。计算校验和的相关知识，如交换性与结合性，字节顺序的自主性，并行计算以及实例，以及给出一些编码技术可以提高校验和的速度。课程设计分析，主要是从数据的输入方式，校验和的计算流程图。对知识进行了一些扩展。给出了自己做课程设计的心得体会，和一些参考资料。本次课程设计的适用范围是，所有在校大学生和一些对计算机网络感兴趣的人都可以指导和参观。课程设计分工：杨忠书负责设计设计目的、设计要求、以及相关知识的收索。王琼伍主要负责本课程设计的课程设计的分析、程序流程图设计、和一些相关知识的扩展。鲁阳主要负责本课程设计的相关文献的查找、序言和目录的设定、文档排版及整个课程设计报告的整理。审校人：鲜乾坤、陈超相关的说明：本课程设计由于设计人的经验不足其中的一些内容可能有许多不完整的地方。希望读者在阅读的时候能结合我们提供的文献一起参考。目 录第1章 概述.1 1.1设计综述.1 1.1.1设计目的.1 1.1.2设计要求.1 1.1.3设计原理.2 1.2计算校验和.3 1.2.1交换性和结合性.3 1.2.2字节顺序的自主性.4 1.2.3并进行计算.4 1.3示例.5 1.4一些编码技术可以提高校验和的计算速度.7 1.4.1延迟进位法.7 1.4.2反向循环法.7 1.4.3合并数据拷贝法.7第2章 设计分析.9 2.1数据的输入方式.9 2.2校验和的计算.10 2.3程序流程图.11第3章 相关扩展.12 3.1主要实现过程.12 3.2程序流程图.13第4章 编程实现.14 4.1 程序源代码.14 4.2程序运行截图.17设计总结.18参考文献.20 第一章 概述1.1设计综述1.1.1设计目的将正常文件的内容，计算其校验和，将该校验和写入文件中或写入别的文件中保存。在文件使用过程中，定期地或每次使用文件前，检查文件现在内容算出的校验和与原来保存的校验和是否一致，因而可以发现文件是否感染，这种方法叫校验和法，它既可发现已知病毒又可发现未和病毒。 这种方法既能发现已知病毒，也能发现未和病毒，但是，它不能识别病毒种类，不能报出病毒名称。由于病毒感染并非文件内容改变的唯一的排他性原因，文件内容的改变有可能是正常程序引起的，所以校验和法常常误报警，而且此法也会影响文件的运行速度。 病毒感染的确会引起文件内容变化，但是校验和法对文件内容的变化太敏感，又不能区分正常程序引起的变动，而频繁报警。用监视文件的校验和来检测病毒，不是最好的方法。这种方法当遇到软件版本更新、变更口令以及修改运行参数时都会误报警。 校验和法对隐蔽性病毒无效。隐蔽性病毒进驻内存后，会自动剥去染毒程序中的病毒代码，使校验和法受骗，对一个有毒文件算出正常校验和。 校验和法的优点是：方法简单、能发现未知病毒、被查文件的细微变化也能发现。其缺点是：必须预先记录正常态的校验和、会误报警、不能识别病毒名称、不能对付隐蔽性病毒。 （2）流程图。1.1.3设计原理将正常文件的内容，计算其校验和，将该校验和写入文件中或写入别的文件中保存。在文件使用过程中，定期地或每次使用文件前，检查文件现在内容算出的校验和与原来保存的校验和是否一致，因而可以发现文件是否感染，这种方法叫校验和法，它既可发现已知病毒又可发现未和病毒。 这种方法既能发现已知病毒，也能发现未和病毒，但是，它不能识别病毒种类，不能报出病毒名称。由于病毒感染并非文件内容改变的唯一的排他性原因，文件内容的改变有可能是正常程序引起的，所以校验和法常常误报警，而且此法也会影响文件的运行速度。 病毒感染的确会引起文件内容变化，但是校验和法对文件内容的变化太敏感，又不能区分正常程序引起的变动，而频繁报警。用监视文件的校验和来检测病毒，不是最好的方法。这种方法当遇到软件版本更新、变更口令以及修改运行参数时都会误报警。 校验和法对隐蔽性病毒无效。隐蔽性病毒进驻内存后，会自动剥去染毒程序中的病毒代码，使校验和法受骗，对一个有毒文件算出正常校验和。1.2计算校验和 有很多数学方法可以用来提高校验和的计算速度，下面我们将就此展开讨论。1.2.1 交换性与结合性因为校验和主要考虑被校验数据中所包含字节数量的是奇数还是偶数，所以校验和的计算可以以任意顺序进行，甚至可以把数据进行分组后再计算。例如，用A、B、C、D，Y，Z分别表示一系列八位组，用a,b这样形式的字节来表示a*256+b的整数，那么16位校验和就可以通过以下形式给出：A,B+C,D+Y,Z 1A,B+C,D+Z,0 2在这里，+代表1补数加法，即将前面的16位校验和按位取反。1可以以（A,B+C,D+J,0+(0,K+Y,Z) 3的形式进行计算。1.2.2 字节顺序的自主性CRC的工作原理是，CRC在发送端编码和接受端校验时，都可以利用事先约定的生成多项式G(x)来得到，K位要发送的信息位可对应于一个(K-1)次多项式K(x)，r为冗余位则对应于一个(r-1)次多项式R(x)，有r位冗余位组成的n=k+r位码字则对应与一个(n-1)次多项式T(x)= Xr*K(x)+R(x)。(4)循环冗余校验码的特点CRC校验码的检测能力很强，不仅能检查出离散错误，还能检查出突发错误。CRC校验码具有以下检错能力：第5章 CRC检验码可检测出所有单个错误。第6章 CRC检验码可检测出所有奇数位错误。第7章 CRC检验码可检测出所有双位的错误。第8章 CRC检验码可检测出所有小于、等于校验位长度的突发错误。位的机器上，我们可以一次增加4个字节，即A,B,C,D+。计算结束后再把累加和“折叠”起来，把一个32位的数值变为16位，这样产生的新的进位也要循环累积起来。此外，在此仍不考虑字节顺序的问题，我们可以用D,C,B,A+或B,A,D,C+;这样的顺序来计算校验和，最终再通过交换16位校验和中的字节序来得到正确的值。这些改变顺序的方法都是为了让所有的偶数字节进入一个校验和字节，所有的奇数字节进入一个校验和字节。1.3 示例下面将通过一个简单的例子来演示通过上述的几种方法所得到的校验和的情况16位按字节累加“正常”顺序交换顺序字节0/1：00 0100010100字节2/3：f2 03F20303f2字节4/5：f4 f5f4f5f5f4字节6/7：f6 f7f6f7f7f6- -合计1：2dc 1f02ddf01f2dcdc f0ddf0f2dc进位：1 221- -合计2：dd f2ddf2f2dd最终结果：dd f2ddf2dd f232位按字节累加“正常”顺序交换顺序字节0/1/2/3：0001f203010003f203f20100字节4/5/6/7：f4f5f6f7f5f4f7f6f7 f6 f5f4-合计1：0f4f7e8fa0f6f4fbe80fbe8f6f4进位：000前半段：f4f7f6f4fbe8后半段：e8fafbe8f6f4-合计2：1ddf11f2dc1f2dcddf1f2dcf2dc进位：111-合计3：ddf2f2ddf2dd最终结果：ddf2ddf2ddf2还有一个例子是把计算工作分为两组，第二组是以奇数边界起始的。按字节累加“正常”顺序字节0/1：00 010001字节2/：f2 (00)f200- -合计：f2 01f201字节4/5：03 f403f4字节6/7：f5 f6f5f6字节8/：f7 (00)f700- -合计2：1f0ea合计2：f0ea进位：1-合计3：f0eb合计1：f201合计3（交换字节序）：ebf0-合计41ddf1合计4ddf1进位：1-合计5：ddf21.4一些编码技术可以提高校验和的计算速度源码及注释#include #include #include #include #include #include #include #include#include#define ERROR_SHMGET -1#define ERROR_SHMAT -2#define ERROR_WAIT -3#define ERROR_FORK -4#define SLOT_TIME 0.005/*截止二进制指数退避算法的实现该算法可以表示为：t=2*r为结点重新发送需要的后退延迟时间;2*为冲突窗口值;r为随机数,r的取值范围为0,2k-1,k=Min重传次数,10;当重传16次仍不成功时,则丢弃该帧.*/static unsigned long get_backoff(const int n)/计算重传推迟时间int k=n;k=16-k;if(k10)/如果重传次数大于10时,重传次数置为10k=10;return (random()%(1k)*SLOT_TIME;/返回重传推迟时间/*发送数据流程*/static void send_msg(const void *addr, const pid_t pid,char ch)pid_t *bus=(pid_t *)addr;int collision; /冲突计数器int k=0;/发送成功的次数for(int i=0;i0)printf(%d send collision.n, pid);usleep(get_backoff(collision); /随机延时elseprintf(%d send failure.n, pid); /发送失败break;else*bus=0;break;while(1);if(collision0)k+;printf(%d send success.n, pid);printf(%c send success=%d.n,ch,k);usleep(random()%1024); /*主函数*/int main()pid_t pid=0;int bus=0; /*共享内存的ID,用来模拟总线*/void *addr=0; /*指向模拟总线的首地址*/bus=shmget(IPC_PRIVATE, sizeof(pid_t), SHM_R|SHM_W);/获取共享内存if(bus=-1) /*如果申请内存失败*/perror(shmget error.);return ERROR_SHMGET;if(pid=fork()0)if(pid=fork()0)if(wait(NULL)=-1)perror(wait error.);return ERROR_WAIT;elsereturn 0;return 0;开始 命令行输入正确？ 创建输入文件流，打开指定输入文件， 32位累加器sum置0 文件结束？ 读入下一个字节数据作为高8位 后面还有数据？ 读入下一个字节数据作为低8位 将组合好的16位数据加到sum中欧 输出格式提示 退出 关闭文件 取sum的低16位sum&oxffff Sum高16位为0？ 将sum高16位数据sum16加到低16位上 对所得数据取反，即为check_sum 输出check_sum 结束 Y 低8位置0N N N Y Y N 3.2 程序流程图第四章 编程实现4.1 程序源代码 #include#includevoid main(int argc, char *argv)/指针数组作为主函数参数，用于函数带参数入/定义并初始化变量FILE *fp;char ch;unsigned char chrl,chrh;unsigned int count=0,checksum=0,chr=0;unsigned long int sum=0;/打开文件argv1if(fp=fopen(d:jiaoyan.txt,r)=NULL)printf(nn File cant be opened);exit(1);printf(nnthe type of output:data-sumnn);/从txt文件读取字符，并进行数据处理while(1)if(ch=fgetc(fp)!=EOF)count+;if(ch!= )if(count%12=0)printf(n); /将字符转换成相应的整形变量if(ch=0&ch=a&ch=A&ch=F)ch=ch-A+10; /计算8字节数的累加值，将奇数位累加到长整形sum的158位，偶数位累加到低80位/这样就避免了数据个数为奇偶的处理操作if(count%2=1)chrh=ch4;elsechrl=ch&0x0f;chr=chrh|chrl;if(count%4=2)sum+=chr16)checksum=(long(sum16)+long(sum&0x0000ffff);checksum=checksum&0x0000ffff;/结果输出printf(nnsum:%lx-checksum:%x,sum,checksum);printf(nnsource:argc=%d,targv=%sn,argc,argv1); fclose(fp); 4.2 程序运行截图打开运行窗口，输入“cmd”命令，调用本程序并输入命令，可看到该程序能对指定文件进行校验和的计算设计总结这次课程设计主要是完成校验和的计算，由于之前对这方面的知识了解不是很多，所以在课设刚开始的几天我去图书馆查阅了大量的相关知识，随后我又结合老师发给我们的资料对校验和做了进一步的了解，才对校验和的知识有了一定的掌握，并且知道了设置校验和的作用。计算校验和的算法其实就是把被校验的数据按16位进行累加