CRC-16码由两个字节构成，在开始时CRC寄存器的每一位都预置为1，然后把CRC寄存器与8-bit的数据进行异或(异或：二进制运算 相同为0，不同为1；0^0=00^1=11^0=11^1=0)， 之后对CRC寄存器从高到低进行移位，在最高位（MSB）的位置补零，而最低位（LSB，移位后已经被移出CRC寄存器）如果为1，则把寄存器与预定义的多项式码进行异或，否则如果LSB为零，则无需进行异或。重复上述的由高至低的移位8次，第一个8-bit数据处睁余理完毕，用此时CRC寄存器的值纳早扮与下一个8-bit数据异或并进行如前一个数据似的8次移位。所有的字符处理完成后CRC寄存器内的值即为最终的CRC值。
1．设置CRC寄存器，并给其赋值FFFF(hex)。
2．将数据的第一个8-bit字符与16位CRC寄存器的低8位进行异或，并把结果存入CRC寄存器。 3．CRC寄存器向右移一位，MSB补零，移出并检查LSB。
4．如果LSB为0，重复第三步；若LSB为1，CRC寄存器与多项式码相异或。
5．重复第3与第4步直到8次移位全部完成。洞灶此时一个8-bit数据处理完毕。
6．重复第2至第5步直到所有数据全部处理完成。
7．最终CRC寄存器的内容即为CRC值。
CRC(16位)多项式为 X16+X15+X2+1，其对应校验二进制位列为1 1000 0000 0000 0101。
#include <stdio.h>typedef unsigned short ushort
typedef unsigned char uchar
typedef union _CRC
{
ushort crc16
uchar by[2]
} CRC
//输入不带CRC码的数据时，返回值是CRC码
//输入带CRC码的数据时，则可以进行校验，返回0时CRC校验成功，否则CRC校验失败
ushort CRC16(uchar *ba, int size)
{
CRC crc
crc.crc16 = 0xffff
int i, l
for (i=0i<sizei++)
{
uchar ch = ba[i]
crc.by[0] = crc.by[0] ^ ch
for (l=0l<8l++)
{
if (crc.by[0] &0x01)
{
crc.crc16 = crc.crc16 >>1
crc.crc16 = crc.crc16 ^ 0xa001
}
else
{
crc.crc16 = crc.crc16 >>1
}
}
}
uchar swap = crc.by[0]
crc.by[0] = crc.by[1]
crc.by[1] = swap
return crc.crc16
}
void main()
{
uchar ba[8] = {0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08}
CRC crc
//计算CRC码
crc.crc16 = CRC16(ba, 8)
printf("高字节:0x%x, 低字节:0x%x\n", crc.by[1], crc.by[0])
//CRC校验
uchar bb[10] = {0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0xb0, 0xcf}
if (0 == CRC16(bb, 10))
{
printf("bb 校验成功！")
}
else
{
printf("bb 校做亏验失败！饥行"烂胡哗)
}
}
TCP校验和是一个端到端的校验和，由发送端计算，然后由接收端验证。其目的是为了发现TCP首部和数据在发送端到
接收端之间发生的任何改动。如果接收方检测到校验和有差错，则TCP段会被直接丢弃。
TCP校验和覆盖TCP首部和TCP数据，而IP首部中的校验和只覆盖IP的首部，不覆盖IP数据报中的任何数据。
TCP的校验和是必需的，而UDP的校验和是可选的铅枯。
TCP和UDP计算校验和时，都要加上一个12字节的伪首部。
伪首部共有12字节，包含如下信息：源IP地址、目的IP地址、保留字节(置0)、传输层协议号(TCP是6)、TCP报文长度(报头+数据)。
伪首部是为了增加TCP校验和的检错能力：如检查TCP报文是否收错了(目的IP地址)、传输层协议是否选对了(传输层协议号)等。
首先，把伪首部、TCP报头、TCP数据分为16位的字，如果总长度为奇数个字节，则在最后增添一个位都为0的字节。
把TCP报头中的校验和字段置为0（否则就陷入鸡生蛋还是蛋生鸡的问题）。
其次，用反码相加法累加所有的16位字（进位也要累加）。
最后，对计算结果取反，作为TCP的校验和。
实现
基于2.6.18、x86_64。
csum_tcpudp_nofold()按4字节累加伪首部到sum中。
[java] view plaincopy
static inline unsigned long csum_tcpudp_nofold (unsigned long saddr, unsigned long daddr,
unsigned short len, unsigned short proto,
unsigned int sum)
{
asm("addl %1, %0\n" /* 累加daddr */
"adcl %2, %0\n" /* 累加saddr */
"adcl %3, %0\n" /* 累加len(2字节), proto, 0*/
"adcl $0, %0\n" /*加上进位 */
: "=r" (sum)
: "g" (daddr), "g" (saddr), "g" ((ntohs(len) << 16) + proto*256), "0" (sum))
return sum
}
csum_tcpudp_magic()产生最终的校验和。
首先，按4字节累加伪首部到sum中。
其次，累加sum的低16位、sum的高16位，并且对累加的结果取反。
最后，截取sum的高16位，作为校验和。
[java] view plaincopy
static inline unsigned short int csum_tcpudp_magic(unsigned long saddr, unsigned long daddr,
unsigned short len, unsigned short proto,
unsigned int sum)
{
return csum_fold(csum_tcpudp_nofold(saddr, daddr, len, proto, sum))
}
static inline unsigned int csum_fold(unsigned int sum)
{
__asm__(
"addl %1, %0\n"
"adcl 0xffff, %0"
: "=r" (sum)
: "r" (sum << 16), "0" (sum & 0xffff0000)
/* 将sum的低16位，作为寄存器1的高16位，寄存器1的低16位补0。搭旁
* 将sum的高16位，作为寄存器0的高16位，寄存器0的低16位补0。
* 这样，addl %1, %0就累加了sum的高16位和低16位。
*
* 还要考虑进位。如果有进位，adcl 0xfff, %0为：0x1 + 0xffff + %0，寄存器0的高16位加1。
* 如果没有进位，adcl 0xffff, %0为：0xffff + %0，对寄存器0的高16位槐枝洞无影响。
*/
)
return (~sum) >> 16 /* 对sum取反，返回它的高16位，作为最终的校验和 */
}
发送校验
[java] view plaincopy
#define CHECKSUM_NONE 0 /* 需要由传输层自己计算校验和 */
#define CHECKSUM_HW 1 /* 由硬件计算报头和首部的校验和 */
#define CHECKSUM_UNNECESSARY 2 /* 表示不需要校验，或者已经成功校验了 */
#define CHECKSUM_PARTIAL CHECKSUM_HW
#define CHECKSUM_COMPLETE CHECKSUM_HW
@tcp_transmit_skb()
icsk->icsk_af_ops->send_check(sk, skb->len, skb)/* 计算校验和 */
[java] view plaincopy
void tcp_v4_send_check(struct sock *sk, int len, struct sk_buff *skb)
{
struct inet_sock *inet = inet_sk(sk)
struct tcphdr *th = skb->h.th
if (skb->ip_summed == CHECKSUM_HW) {
/* 只计算伪首部，TCP报头和TCP数据的累加由硬件完成 */
th->check = ~tcp_v4_check(th, len, inet->saddr, inet->daddr, 0)
skb->csum = offsetof(struct tcphdr, check) /* 校验和值在TCP首部的偏移 */
} else {
/* tcp_v4_check累加伪首部，获取最终的校验和。
* csum_partial累加TCP报头。
* 那么skb->csum应该是TCP数据部分的累加，这是在从用户空间复制时顺便累加的。
*/
th->check = tcp_v4_check(th, len, inet->saddr, inet->daddr,
csum_partial((char *)th, th->doff << 2, skb->csum))
}
}
[java] view plaincopy
unsigned csum_partial(const unsigned char *buff, unsigned len, unsigned sum)
{
return add32_with_carry(do_csum(buff, len), sum)
}
static inline unsigned add32_with_carry(unsigned a, unsigned b)
{
asm("addl %2, %0\n\t"
"adcl $0, %0"
: "=r" (a)
: "0" (a), "r" (b))
return a
}
do_csum()用于计算一段内存的校验和，这里用于累加TCP报头。
具体计算时用到一些技巧：
1. 反码累加时，按16位、32位、64位来累加的效果是一样的。
2. 使用内存对齐，减少内存 *** 作的次数。
[java] view plaincopy
static __force_inline unsigned do_csum(const unsigned char *buff, unsigned len)
{
unsigned odd, count
unsigned long result = 0
if (unlikely(len == 0))
return result
/* 使起始地址为XXX0，接下来可按2字节对齐 */
odd = 1 & (unsigned long) buff
if (unlikely(odd)) {
result = *buff << 8 /* 因为机器是小端的 */
len--
buff++
}
count = len >> 1 /* nr of 16-bit words，这里可能余下1字节未算，最后会处理*/
if (count) {
/* 使起始地址为XX00，接下来可按4字节对齐 */
if (2 & (unsigned long) buff) {
result += *(unsigned short *)buff
count--
len -= 2
buff += 2
}
count >>= 1 /* nr of 32-bit words，这里可能余下2字节未算，最后会处理 */
if (count) {
unsigned long zero
unsigned count64
/* 使起始地址为X000，接下来可按8字节对齐 */
if (4 & (unsigned long)buff) {
result += *(unsigned int *)buff
count--
len -= 4
buff += 4
}
count >>= 1 /* nr of 64-bit words，这里可能余下4字节未算，最后会处理*/
/* main loop using 64byte blocks */
zero = 0
count64 = count >> 3 /* 64字节的块数，这里可能余下56字节未算，最后会处理 */
while (count64) { /* 反码累加所有的64字节块 */
asm ("addq 0*8(%[src]), %[res]\n\t" /* b、w、l、q分别对应8、16、32、64位 *** 作 */
"addq 1*8(%[src]), %[res]\n\t" /* [src]为指定寄存器的别名，效果应该等同于0、1等 */
"adcq 2*8(%[src]), %[res]\n\t"
"adcq 3*8(%[src]), %[res]\n\t"
"adcq 4*8(%[src]), %[res]\n\t"
"adcq 5*8(%[src]), %[res]\n\t"
"adcq 6*8(%[src]), %[res]\n\t"
"adcq 7*8(%[src]), %[res]\n\t"
"adcq %[zero], %[res]"
: [res] "=r" (result)
: [src] "r" (buff), [zero] "r" (zero), "[res]" (result))
buff += 64
count64--
}
/* 从这里开始，反序处理之前可能漏算的字节 */
/* last upto 7 8byte blocks，前面按8个8字节做计算单位，所以最多可能剩下7个8字节 */
count %= 8
while (count) {
asm ("addq %1, %0\n\t"
"adcq %2, %0\n"
: "=r" (result)
: "m" (*(unsigned long *)buff), "r" (zero), "0" (result))
--count
buff += 8
}
/* 带进位累加result的高32位和低32位 */
result = add32_with_carry(result>>32, result&0xffffffff)
/* 之前始按8字节对齐，可能有4字节剩下 */
if (len & 4) {
result += *(unsigned int *) buff
buff += 4
}
}
/* 更早前按4字节对齐，可能有2字节剩下 */
if (len & 2) {
result += *(unsigned short *) buff
buff += 2
}
}
/* 最早之前按2字节对齐，可能有1字节剩下 */
if (len & 1)
result += *buff
/* 再次带进位累加result的高32位和低32位 */
result = add32_with_carry(result>>32, result & 0xffffffff)
/* 这里涉及到一个技巧，用于处理初始地址为奇数的情况 */
if (unlikely(odd)) {
result = from32to16(result) /* 累加到result的低16位 */
/* result为：0 0 a b
* 然后交换a和b，result变为：0 0 b a
*/
result = ((result >> 8) & 0xff) | ((result & oxff) << 8)
}
return result /* 返回result的低32位 */
}
[java] view plaincopy
static inline unsigned short from32to16(unsigned a)
{
unsigned short b = a >> 16
asm ("addw %w2, %w0\n\t"
"adcw $0, %w0\n"
: "=r" (b)
: "0" (b), "r" (a))
return b
}
csum_partial_copy_from_user()用于拷贝用户空间数据到内核空间，同时计算用户数据的校验和，
结果保存到skb->csum中（X86_64）。
[java] view plaincopy
/**
* csum_partial_copy_from_user - Copy and checksum from user space.
* @src: source address (user space)
* @dst: destination address
* @len: number of bytes to be copied.
* @isum: initial sum that is added into the result (32bit unfolded)
* @errp: set to -EFAULT for an bad source address.
*
* Returns an 32bit unfolded checksum of the buffer.
* src and dst are best aligned to 64bits.
*/
unsigned int csum_partial_copy_from_user(const unsigned char __user *src,
unsigned char *dst, int len, unsigned int isum, int *errp)
{
might_sleep()
*errp = 0
if (likely(access_ok(VERIFY_READ, src, len))) {
/* Why 6, not 7? To handle odd addresses aligned we would need to do considerable
* complications to fix the checksum which is defined as an 16bit accumulator. The fix
* alignment code is primarily for performance compatibility with 32bit and that will handle
* odd addresses slowly too.
* 处理X010、X100、X110的起始地址。不处理X001，因为这会使复杂度大增加。
*/
if (unlikely((unsigned long)src & 6)) {
while (((unsigned long)src & 6) && len >= 2) {
__u16 val16
*errp = __get_user(val16, (__u16 __user *)src)
if (*errp)
return isum
*(__u16 *)dst = val16
isum = add32_with_carry(isum, val16)
src += 2
dst += 2
len -= 2
}
}
/* 计算函数是用纯汇编实现的，应该是因为效率吧 */
isum = csum_parial_copy_generic((__force void *)src, dst, len, isum, errp, NULL)
if (likely(*errp == 0))
return isum /* 成功 */
}
*errp = -EFAULT
memset(dst, 0, len)
return isum
}
上述的实现比较复杂，来看下最简单的csum_partial_copy_from_user()实现（um）。
[java] view plaincopy
unsigned int csum_partial_copy_from_user(const unsigned char *src,
unsigned char *dst, int len, int sum,
int *err_ptr)
{
if (copy_from_user(dst, src, len)) { /* 拷贝用户空间数据到内核空间 */
*err_ptr = -EFAULT /* bad address */
return (-1)
}
return csum_partial(dst, len, sum) /* 计算用户数据的校验和，会存到skb->csum中 */
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）