您现在的位置：首页 --> 算法 --> 关于libmemcached中的crc的实现

关于libmemcached中的crc的实现

浏览:875次出处信息

缘起

libmemcached备受青睐，号称错误信息是很详细的，比所谓的memcache模块强多了；但是，就是因为他的名气大，还是被坑了；所谓的错误信息详细在get操作时完全不存在了，不管是连接失败还是各种超时，得到的错误信息都是NOTFOUND；于是乎，我想自己用PHP写一个memcached的client，起初，我可以之实现我需要的几个方法，鉴于memcache的协议很简单，应该是比较容易完成的。

问题

其实，我1天时间已经完成了memcache的几个简单的协议，出于一些不想说的考虑，当add多个server时，我需要把根据key的hash结果和libmemcached中的完全一样；看了libmemcached中几种hash和distribute的策略，我只想选择一种最简单的hash和distribute策略来实现，我选择了 crc32 + modular；简而言之，算法就是： crc32(key) % count(server) 就Ok了；但是，问题是PHP的crc32结果和libmemcached中的crc32结果是不同的，鉴于我的C语言水平有限，不想看和看不懂使得我咨询了一下牛人，没有结果，于是还是硬着头皮看吧。

分析

后面分别贴一下libmemcached和php中crc的实现，这里先说结论了：

二者差别不大，主要差别在于：

PHP中的crc32返回的是一个32位的有符号数，而libmemecached中返回的是前者32位有符号数种的高16位，并且忽略了符号位；

如果用PHP实现一个和libmemcached相同的crc32将是：

1
2
<?php
echo(crc32('test')>>16)&0x7fff;

或者如下实现：

本来只需要简单的位移操作、异或操作就可以处理的事情，用PHP来实现却需要大量的pack、unpack，对‘test’进行crc32大约需要0.1ms(很慢的)，如果用上面实现，大约比该实现快100倍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
<?php
 
function_crc32($str){
        $arr=array(
            0x00000000,0x77073096,0xee0e612c,0x990951ba,
            0x076dc419,0x706af48f,0xe963a535,0x9e6495a3,
            0x0edb8832,0x79dcb8a4,0xe0d5e91e,0x97d2d988,
            0x09b64c2b,0x7eb17cbd,0xe7b82d07,0x90bf1d91,
            0x1db71064,0x6ab020f2,0xf3b97148,0x84be41de,
            0x1adad47d,0x6ddde4eb,0xf4d4b551,0x83d385c7,
            0x136c9856,0x646ba8c0,0xfd62f97a,0x8a65c9ec,
            0x14015c4f,0x63066cd9,0xfa0f3d63,0x8d080df5,
            0x3b6e20c8,0x4c69105e,0xd56041e4,0xa2677172,
            0x3c03e4d1,0x4b04d447,0xd20d85fd,0xa50ab56b,
            0x35b5a8fa,0x42b2986c,0xdbbbc9d6,0xacbcf940,
            0x32d86ce3,0x45df5c75,0xdcd60dcf,0xabd13d59,
            0x26d930ac,0x51de003a,0xc8d75180,0xbfd06116,
            0x21b4f4b5,0x56b3c423,0xcfba9599,0xb8bda50f,
            0x2802b89e,0x5f058808,0xc60cd9b2,0xb10be924,
            0x2f6f7c87,0x58684c11,0xc1611dab,0xb6662d3d,
            0x76dc4190,0x01db7106,0x98d220bc,0xefd5102a,
            0x71b18589,0x06b6b51f,0x9fbfe4a5,0xe8b8d433,
            0x7807c9a2,0x0f00f934,0x9609a88e,0xe10e9818,
            0x7f6a0dbb,0x086d3d2d,0x91646c97,0xe6635c01,
            0x6b6b51f4,0x1c6c6162,0x856530d8,0xf262004e,
            0x6c0695ed,0x1b01a57b,0x8208f4c1,0xf50fc457,
            0x65b0d9c6,0x12b7e950,0x8bbeb8ea,0xfcb9887c,
            0x62dd1ddf,0x15da2d49,0x8cd37cf3,0xfbd44c65,
            0x4db26158,0x3ab551ce,0xa3bc0074,0xd4bb30e2,
            0x4adfa541,0x3dd895d7,0xa4d1c46d,0xd3d6f4fb,
            0x4369e96a,0x346ed9fc,0xad678846,0xda60b8d0,
            0x44042d73,0x33031de5,0xaa0a4c5f,0xdd0d7cc9,
            0x5005713c,0x270241aa,0xbe0b1010,0xc90c2086,
            0x5768b525,0x206f85b3,0xb966d409,0xce61e49f,
            0x5edef90e,0x29d9c998,0xb0d09822,0xc7d7a8b4,
            0x59b33d17,0x2eb40d81,0xb7bd5c3b,0xc0ba6cad,
            0xedb88320,0x9abfb3b6,0x03b6e20c,0x74b1d29a,
            0xead54739,0x9dd277af,0x04db2615,0x73dc1683,
            0xe3630b12,0x94643b84,0x0d6d6a3e,0x7a6a5aa8,
            0xe40ecf0b,0x9309ff9d,0x0a00ae27,0x7d079eb1,
            0xf00f9344,0x8708a3d2,0x1e01f268,0x6906c2fe,
            0xf762575d,0x806567cb,0x196c3671,0x6e6b06e7,
            0xfed41b76,0x89d32be0,0x10da7a5a,0x67dd4acc,
            0xf9b9df6f,0x8ebeeff9,0x17b7be43,0x60b08ed5,
            0xd6d6a3e8,0xa1d1937e,0x38d8c2c4,0x4fdff252,
            0xd1bb67f1,0xa6bc5767,0x3fb506dd,0x48b2364b,
            0xd80d2bda,0xaf0a1b4c,0x36034af6,0x41047a60,
            0xdf60efc3,0xa867df55,0x316e8eef,0x4669be79,
            0xcb61b38c,0xbc66831a,0x256fd2a0,0x5268e236,
            0xcc0c7795,0xbb0b4703,0x220216b9,0x5505262f,
            0xc5ba3bbe,0xb2bd0b28,0x2bb45a92,0x5cb36a04,
            0xc2d7ffa7,0xb5d0cf31,0x2cd99e8b,0x5bdeae1d,
            0x9b64c2b0,0xec63f226,0x756aa39c,0x026d930a,
            0x9c0906a9,0xeb0e363f,0x72076785,0x05005713,
            0x95bf4a82,0xe2b87a14,0x7bb12bae,0x0cb61b38,
            0x92d28e9b,0xe5d5be0d,0x7cdcefb7,0x0bdbdf21,
            0x86d3d2d4,0xf1d4e242,0x68ddb3f8,0x1fda836e,
            0x81be16cd,0xf6b9265b,0x6fb077e1,0x18b74777,
            0x88085ae6,0xff0f6a70,0x66063bca,0x11010b5c,
            0x8f659eff,0xf862ae69,0x616bffd3,0x166ccf45,
            0xa00ae278,0xd70dd2ee,0x4e048354,0x3903b3c2,
            0xa7672661,0xd06016f7,0x4969474d,0x3e6e77db,
            0xaed16a4a,0xd9d65adc,0x40df0b66,0x37d83bf0,
            0xa9bcae53,0xdebb9ec5,0x47b2cf7f,0x30b5ffe9,
            0xbdbdf21c,0xcabac28a,0x53b39330,0x24b4a3a6,
            0xbad03605,0xcdd70693,0x54de5729,0x23d967bf,
            0xb3667a2e,0xc4614ab8,0x5d681b02,0x2a6f2b94,
            0xb40bbe37,0xc30c8ea1,0x5a05df1b,0x2d02ef8d,
        );
        $table='';
        foreach($arras$int){
                $table.=pack('N',$int);
        }
 
        $crc=pack('N',4294967295);
        for($i=0;$i<strlen($str);$i++){
                $m=$crc^(chr(0).chr(0).chr(0).$str{$i});
                $n=$m&(chr(0).chr(0).chr(0).chr(0xff));
                $arr=unpack('N',$n);
                $n=$arr[1];
                $arr=unpack('N',$crc);
                $crc=(pack('N',$arr[1]>>8))^substr($table,$n*4,4);
        }
        $arr=unpack('N',~$crc);
        $res=(pack('N',$arr[1]>>16))&(chr(0).chr(0).chr(0x7f).chr(0xff));
        $arr=unpack('N',$res);
        return$arr[1];
}

libmemcached：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
staticconstuint32_t crc32tab[256]={
    0x00000000,0x77073096,0xee0e612c,0x990951ba,
    0x076dc419,0x706af48f,0xe963a535,0x9e6495a3,
    0x0edb8832,0x79dcb8a4,0xe0d5e91e,0x97d2d988,
    0x09b64c2b,0x7eb17cbd,0xe7b82d07,0x90bf1d91,
    0x1db71064,0x6ab020f2,0xf3b97148,0x84be41de,
    0x1adad47d,0x6ddde4eb,0xf4d4b551,0x83d385c7,
    0x136c9856,0x646ba8c0,0xfd62f97a,0x8a65c9ec,
    0x14015c4f,0x63066cd9,0xfa0f3d63,0x8d080df5,
    0x3b6e20c8,0x4c69105e,0xd56041e4,0xa2677172,
    0x3c03e4d1,0x4b04d447,0xd20d85fd,0xa50ab56b,
    0x35b5a8fa,0x42b2986c,0xdbbbc9d6,0xacbcf940,
    0x32d86ce3,0x45df5c75,0xdcd60dcf,0xabd13d59,
    0x26d930ac,0x51de003a,0xc8d75180,0xbfd06116,
    0x21b4f4b5,0x56b3c423,0xcfba9599,0xb8bda50f,
    0x2802b89e,0x5f058808,0xc60cd9b2,0xb10be924,
    0x2f6f7c87,0x58684c11,0xc1611dab,0xb6662d3d,
    0x76dc4190,0x01db7106,0x98d220bc,0xefd5102a,
    0x71b18589,0x06b6b51f,0x9fbfe4a5,0xe8b8d433,
    0x7807c9a2,0x0f00f934,0x9609a88e,0xe10e9818,
    0x7f6a0dbb,0x086d3d2d,0x91646c97,0xe6635c01,
    0x6b6b51f4,0x1c6c6162,0x856530d8,0xf262004e,
    0x6c0695ed,0x1b01a57b,0x8208f4c1,0xf50fc457,
    0x65b0d9c6,0x12b7e950,0x8bbeb8ea,0xfcb9887c,
    0x62dd1ddf,0x15da2d49,0x8cd37cf3,0xfbd44c65,
    0x4db26158,0x3ab551ce,0xa3bc0074,0xd4bb30e2,
    0x4adfa541,0x3dd895d7,0xa4d1c46d,0xd3d6f4fb,
    0x4369e96a,0x346ed9fc,0xad678846,0xda60b8d0,
    0x44042d73,0x33031de5,0xaa0a4c5f,0xdd0d7cc9,
    0x5005713c,0x270241aa,0xbe0b1010,0xc90c2086,
    0x5768b525,0x206f85b3,0xb966d409,0xce61e49f,
    0x5edef90e,0x29d9c998,0xb0d09822,0xc7d7a8b4,
    0x59b33d17,0x2eb40d81,0xb7bd5c3b,0xc0ba6cad,
    0xedb88320,0x9abfb3b6,0x03b6e20c,0x74b1d29a,
    0xead54739,0x9dd277af,0x04db2615,0x73dc1683,
    0xe3630b12,0x94643b84,0x0d6d6a3e,0x7a6a5aa8,
    0xe40ecf0b,0x9309ff9d,0x0a00ae27,0x7d079eb1,
    0xf00f9344,0x8708a3d2,0x1e01f268,0x6906c2fe,
    0xf762575d,0x806567cb,0x196c3671,0x6e6b06e7,
    0xfed41b76,0x89d32be0,0x10da7a5a,0x67dd4acc,
    0xf9b9df6f,0x8ebeeff9,0x17b7be43,0x60b08ed5,
    0xd6d6a3e8,0xa1d1937e,0x38d8c2c4,0x4fdff252,
    0xd1bb67f1,0xa6bc5767,0x3fb506dd,0x48b2364b,
    0xd80d2bda,0xaf0a1b4c,0x36034af6,0x41047a60,
    0xdf60efc3,0xa867df55,0x316e8eef,0x4669be79,
    0xcb61b38c,0xbc66831a,0x256fd2a0,0x5268e236,
    0xcc0c7795,0xbb0b4703,0x220216b9,0x5505262f,
    0xc5ba3bbe,0xb2bd0b28,0x2bb45a92,0x5cb36a04,
    0xc2d7ffa7,0xb5d0cf31,0x2cd99e8b,0x5bdeae1d,
    0x9b64c2b0,0xec63f226,0x756aa39c,0x026d930a,
    0x9c0906a9,0xeb0e363f,0x72076785,0x05005713,
    0x95bf4a82,0xe2b87a14,0x7bb12bae,0x0cb61b38,
    0x92d28e9b,0xe5d5be0d,0x7cdcefb7,0x0bdbdf21,
    0x86d3d2d4,0xf1d4e242,0x68ddb3f8,0x1fda836e,
    0x81be16cd,0xf6b9265b,0x6fb077e1,0x18b74777,
    0x88085ae6,0xff0f6a70,0x66063bca,0x11010b5c,
    0x8f659eff,0xf862ae69,0x616bffd3,0x166ccf45,
    0xa00ae278,0xd70dd2ee,0x4e048354,0x3903b3c2,
    0xa7672661,0xd06016f7,0x4969474d,0x3e6e77db,
    0xaed16a4a,0xd9d65adc,0x40df0b66,0x37d83bf0,
    0xa9bcae53,0xdebb9ec5,0x47b2cf7f,0x30b5ffe9,
    0xbdbdf21c,0xcabac28a,0x53b39330,0x24b4a3a6,
    0xbad03605,0xcdd70693,0x54de5729,0x23d967bf,
    0xb3667a2e,0xc4614ab8,0x5d681b02,0x2a6f2b94,
    0xb40bbe37,0xc30c8ea1,0x5a05df1b,0x2d02ef8d,
};
 
uint32_t
hash_crc32(constchar*key,size_t key_length)
{
    uint64_tx;
    uint32_t crc=UINT32_MAX;
 
    for(x=0;x<key_length;x++){
        crc=(crc>>8)^crc32tab[(crc^(uint64_t)key[x])&0xff];
    }
 
    return((~crc)>>16)&0x7fff;
}

php中的实现(说明一下：这里的crc32tab和上面的是一样的)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/* {{{ proto string crc32(string str)
   Calculate the crc32 polynomial of a string */
PHP_NAMED_FUNCTION(php_if_crc32)
{
    char*p;
    intlen,nr;
    php_uint32 crcinit=0;
    registerphp_uint32 crc;
 
    if(zend_parse_parameters(ZEND_NUM_ARGS()TSRMLS_CC,"s",&p,&nr)==FAILURE){
        return;
    }
    crc=crcinit^0xFFFFFFFF;
 
    for(len=+nr;nr--;++p){
        crc=((crc>>8)&0x00FFFFFF)^crc32tab[(crc^(*p))&0xFF];
    }
    RETVAL_LONG(crc^0xFFFFFFFF);
}
/* }}} */

关于crc32_table 的由来，crc32_table是出于提高效率的目的而诞生的，来源于一个神奇的数字 0x04c11db7：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <stdio.h> 
unsignedlongintcrc32_table[256];
unsignedlongintulPolynomial=0x04c11db7;
unsignedlongintReflect(unsignedlongintref,charch){
        unsignedlongintvalue=0;
        // 交换bit0 和bit7，bit1 和bit6，类推 
        inti;
        for(i=1;i<(ch+1);i++){
                if(ref&1)
                        value|=1<<(ch-i);
                ref>>=1;
        }
        returnvalue;
}
voidinit_crc32_table(){
        unsignedlongintcrc,temp;
        // 256 个值 
        inti,j;
        for(i=0;i<=0xFF;i++){
                temp=Reflect(i,8);
                crc32_table[i]=temp<<24;
                for(j=0;j<8;j++){
                        unsignedlongintt1,t2;
                        unsignedlongintflag=crc32_table[i]&0x80000000;
                        t1=(crc32_table[i]<<1);
                        if(flag==0)
                                t2=0;
                        else
                                t2=ulPolynomial;
                        crc32_table[i]=t1^t2;}
                        crc=crc32_table[i];
                        crc32_table[i]=Reflect(crc32_table[i],32);
        }
}
intmain(intac,char**av){
        init_crc32_table();
        inti;
        for(i=0;i<256;i++){
                printf("0x%08x	",crc32_table[i]);
                if(i%4==3)printf("
");
        }
 
        return0;
}

参考资料：

http://baike.baidu.com/view/410181.htm?fr=aladdin

http://hi.baidu.com/qyiyunso/item/c06719c5872ed5d5964452ac

http://zh.wikipedia.org/wiki/CRC32

建议继续学习：

libmemcached的MEMCACHED_MAX_BUFFER问题 (阅读：926)

QQ技术交流群：445447336，欢迎加入！
扫一扫订阅我的微信号：IT技术博客大学习

<< 前一篇：如何编程实现 2 + 2 = 5？

后一篇：用牛顿迭代法求整数的平方根 >>

文章信息

作者：phpor 来源： PHPor 的Blog
标签： crc libmemcached
发布时间：2014-11-24 23:32:25

建议继续学习

libmemcached的MEMCACHED_MAX_BUFFER问题

近3天十大热文