在学习TCP/IP 详解的过程中遇到了不止一次的关于检验和的概念，在吸取了他人理解的前提下，我决定用Wireshare 进行抓包分析。
首先我们得知道IP数据包格式
首先把检验和字段置为 0 。然后，对首部中每个 16 bit 进行二进制反码求和（整个首部看成是由一串 16 bit的字组成），结果存在检验和字段中。当收到一份I P数据报后，同样对首部中每个 16 bit进行二进制反码的求和。由于接收方在计算过程中包含了发送方存在首部中的检验和，因此，如果首部在传输过程中没有发生任何差错，那么接收方计算的结果应该为全 1。如果结果不是全1 （即检验和错误），那么I P就丢弃收到的数据报。但是不生成差错报文，由上层去发现丢失的数据报并进行重传。
再来看看Wireshare抓取结果
观察此图，我们可以看到这是一个源地址为123.151.152.231 目的地址为10.22.66.206即为本机地址的IP数字报传送。
注意图中标深蓝颜色的数字，每当我们点击分类信息时，下方的数字就会跟随着发生变化，因此我们就可以得到IP数据报的内容。、
解释如下：（本内容部分取自博客园）
版本号4，占了4位，表示ipv4.
接下来是包头长度，又占了4位，指明ipv4协议包头长度的字节数包含多少个32位。由于IPv4
的包头可能包含可变数量的可选 项，所以这个字段可以用来确定IPv4数据报中数据部分的偏
移位置。IPv4包头的最小长度是20个字节，因此IHL这个字段的最小值用十六进制表示就是5
(5x4（4个字节32位） = 20字节)。就是说，它表示的是包头的总字节数是4字节的倍数。
图中即为header length为20表示是20个字节，所以经过计算此处用十六进制表示为5，二进制
表示为1001。
再往下是服务类型为0x00。
服务类型此处一共占了8位，涵义如下：
过程字段：3位，设置了数据包的重要性，取值越大数据越重要，取值范围为：0（正常）~ 7（网络控制）
延迟字段：1位，取值：0（正常）、1（期特低的延迟）
流量字段：1位，取值：0（正常）、1（期特高的流量）
可靠性字段：1位，取值：0（正常）、1（期特高的可靠性）
成本字段：1位，取值：0（正常）、1（期特最小成本）
未使用：1位
接着是总长度total length：十六进制是0x0028
标识字段：占16位。IP软件在存储器中维持一个计数器，每产生一个数据报，计数器就加1，并将此值赋给标识字段。
但这个“标识”不是序号，因为IP是无连接服务，数据报不存在按序接收的问题。当数据报由于长度超过网络的MTU而必须分片时，
这个标识字段的值就被复制到所有的数据报片的标识字段中。相同的标识字段的值使分片后的各数据报片最后能正确地重装成为原来的数据报
此处值为0xcf59
标志（flag）：占3位，但目前只有两位有意义。
标志字段中的最低位为MF（More Fragment）。MF=1即表示后面“还有分片”的数据报。MF=0表示这已是若干数据报片中的最后一个。
标志字段中间的一位记为DF（Don't Fragment），意思是“不能分片”。只有当DF=0时才允许分片。
此处值为0x02即010表示不能分片，即don't Fragment
13位片偏移：当数据分组时，它和更多段位（MF, More fragments）进行连接，帮助目的主机将分段的包组合
此处值为0x000
8位生存时间即ttl，表示数据包在网络上生存多久，每通过一个路由器该值减一，为0时将被路由器丢弃。此处为0x33 十进制为51
8位协议：8位，这个字段定义了IP数据报的数据部分使用的协议类型。常用的协议及其十进制数值包括ICMP(1)、TCP(6)、UDP(17)。此处为tcp。
源端ip：123.151.152.231 0x7b97 0x98e7
目标ip：10.22.66.206 0x0a16 0x42ce
注意上面的0x1714就是我们的检验和，这个就是我们发送端的检验和。
到此，首部的数据基本确定清楚。
接下来我们讲一下检验和算法：
0和0相加是0，0和1相加是1，1和1相加是0但要产生一个进位1，加到下一列．若最高位相加后产生进位，则最后得到的结果要加1．
在发送数据时，为了计算IP数据包的校验和。应该按如下步骤：
（1）把IP数据包的校验和字段置为0；
（2）把首部看成以16位为单位的数字组成，依次进行二进制反码求和；
（3）把得到的结果存入校验和字段中。
在接收数据时，计算数据包的校验和相对简单，按如下步骤：
（1）把首部看成以16位为单位的数字组成，依次进行二进制反码求和，包括校验和字段；
（2）检查计算出的校验和的结果是否等于零（反码应为16个0）；
（3）如果等于零，说明被整除，校验和正确。否则，校验和就是错误的，协议栈要抛弃这个数据包。
网上找了一个简单点的例子先来看一下
原始数据为 1100 ， 1010 ， 0000（校验位）
那么把他们按照4bit一组进行按位取反相加。 1100取反0011 ， 1010取反是0101，0011加上0101 是1000，填入到校验位后
1100 ， 1010 ， 1000
那么这个就是要发送的数据。收到数据后同样进行按位取反相加。0011+0101+0111 =1111；全为1表示正确
第二种方法就是先直接相加再取反。
我们使用第二种：
先计算发送端的检验和，我们先令检验和为0x0000，然后进行运算4500+0028+cf59+4000+3306+0000+7b97+98e7+0a16+42ce然后将运算结果取反，最终得到数值0x1714，将其存入检验和字段中。
接收端收到一个IP数字报时，将进行4500+0028+cf59+4000+3306+1714+7b97+98e7+0a16+42ce运算，如果最终结果全为1，代表检验和无错误，否则丢弃收到的数据包。
本文链接：http://www.cnblogs.com/tracylining/p/3354726.html，转载请注明。
为了完成二维数据快速分类，最先使用的是hash分类。
前几天我突然想，既然基数排序的时间复杂度也不高，而且可能比hash分类更稳定，所以不妨试一下。
在实现上我依次实现：
1、一维数组基数排序
基本解决主要问题，涵盖排序，包含改进的存储分配策略。
如果用链表来实现，大量的函数调用将耗费太多时间。
2、二位数组基数排序
主要是实现和原有程序的集成。
一、数据结构
下面是存储节点的主数据结构。
int * PagePtr;
struct tagPageList * next;
}PageList;
typedef struct tagBucket{
int * currentPagePtr;
int offset;
PageList pl;
PageList * currentPageListItem;
}Bucket;
链表内是存储的一个4KB页面的指针。
每4KB页面可以存储最多1024个记录序号，如果是一维数组排序，那就直接存储数组元素了。
二、算法
基数排序可以分为MSD或者LSD。这里用的是LSD。
伪代码如下：
for each sorted-num{
cell = sorted-num
bucketIdx = (cell>>8*i)&0xff
bucket = cell
}
combine linked list nodes to overwrite original array
}
C代码实现：
HANDLE heap = NULL;
Bucket bucket;
PageList * pageListPool;
int plpAvailable = 0;
int * pages = NULL;
int * pagesAvailable = NULL;
int * objIdx;
unsigned short * s;
time_t timeBegin;
time_t timeEnd;
heap = HeapCreate(HEAP_NO_SERIALIZE|HEAP_GENERATE_EXCEPTIONS, 1024*1024, 0);
if (heap != NULL){
pages = (int * )HeapAlloc(heap, 0, (TFSI/PAGEGRANULAR + BUCKETSLOTCOUNT + 8) * 4096);
pageListPool = (PageList *)HeapAlloc(heap, 0, (TFSI/PAGEGRANULAR + 8) * sizeof(PageList));
s = (unsigned short *)HeapAlloc(heap, 0, TFSI*sizeof(unsigned short));
objIdx = (int *)HeapAlloc(heap, 0, TFSI * sizeof(int));
}
MakeSure(pages != NULL && pageListPool != NULL && objIdx != NULL);
for(int i=0; i<TFSI; i++) objIdx=i;
timeBegin = clock();
for (int i=0; i<TFSI; i++) s = rand();
timeEnd = clock();
printf("\n%f(s) consumed in generating numbers", (double)(timeEnd-timeBegin)/CLOCKS_PER_SEC);
timeBegin = clock();
for (int t=0; t<sizeof(short); t++){
FillMemory(pages, (TFSI/PAGEGRANULAR + BUCKETSLOTCOUNT + 8) * 4096, 0xff);
SecureZeroMemory(pageListPool, (TFSI/PAGEGRANULAR + 8) * sizeof(PageList));
pagesAvailable = pages;
plpAvailable = 0;
for(int i=0; i<256; i++){
bucket.currentPagePtr = pagesAvailable;
bucket.offset = 0;
bucket.pl.PagePtr = pagesAvailable;
bucket.pl.next = NULL;
pagesAvailable += PAGEGRANULAR;
bucket.currentPageListItem = &(bucket.pl);
}
int bucketIdx;
for (int i=0; i<TFSI; i++){
bucketIdx = (s[objIdx[i]]>>t*8)&0xff;
MakeSure(bucketIdx < 256);
//save(bucketIdx, objIdx);
bucket.currentPagePtr[ bucket[bucketIdx].offset ] = objIdx;
bucket.offset++;
if (bucket.offset == PAGEGRANULAR){
bucket.currentPageListItem->next = &pageListPool[plpAvailable];
plpAvailable++;
MakeSure(plpAvailable < TFSI/PAGEGRANULAR + 8);
bucket.currentPageListItem->next->PagePtr = pagesAvailable;
bucket.currentPageListItem->next->next = NULL;
bucket.currentPagePtr = pagesAvailable;
bucket.offset = 0;
pagesAvailable += PAGEGRANULAR;
MakeSure(pagesAvailable < pages+(TFSI/PAGEGRANULAR + BUCKETSLOTCOUNT + 8) * 1024);
bucket.currentPageListItem = bucket.currentPageListItem->next;
}
}
//update objIdx index
int start = 0;
for (int阅读更多内容
没有评论:
发表评论