Redis源码分析（二十三）--- CRC循环冗余算法和RAND随机数算法

rwewqe

     今天开始研究Redis源码中的一些工具类的代码实现，工具类在任何语言中，实现的算法原理应该都是一样的，所以可以借此机会学习一下一些比较经典的算法。比如说我今天看的Crc循环冗余校验算法和rand随机数产生算法。

            CRC算法全称循环冗余校验算法。CRC校验的基本思想是利用线性编码理论,在发送端根据要传送的k位二进制码序列,以一定的规则产生一个校验用的监督码（既CRC码）r位,并附在信息后边,构成一个新的二进制码序列数共(k+r)位,最后发送出去。在接收端, 则根据信息码和CRC码之间所遵循的规则进行检验,以确定传送中是否出错。16位的CRC码产生的规则是先将要发送的二进制序列数左移16位（既乘以 ）后,再除以一个多项式,最后 所得到的余数既是CRC码。在Redis中实现的冗余校验算法为字节型算法；

字节型算法的一般描述为：本字节的CRC码，等于上一字节CRC码的低8位左移8位，与上一字节CRC右移8位同本字节异或后所得的CRC码异或。   
字节型算法如下：
1)CRC寄存器组初始化为全"0"(0x0000)。（注意：CRC寄存器组初始化全为1时，最后CRC应取反。）
2)CRC寄存器组向左移8位,并保存到CRC寄存器组。
3)原CRC寄存器组高8位（右移8位）与数据字节进行异或运算，得出一个指向值表的索引。
4)索引所指的表值与CRC寄存器组做异或运算。
5)数据指针加1，如果数据没有全部处理完，则重复步骤2)。
6)得出CRC。

我们来对应一下在Redis中的代码，完全符合；



    /* Crc64循环冗余运算算法，crc:基础值0，s：传入的内容，l:内容长度 */  
    uint64_t crc64(uint64_t crc, const unsigned char *s, uint64_t l) {  
        uint64_t j;  
      
        for (j = 0; j < l; j++) {  
            uint8_t byte = s[j];  
            crc = crc64_tab[(uint8_t)crc ^ byte] ^ (crc >> 8);  
        }  
        return crc;  
    }  

Redis内置的例子，


    /* Test main */  
    /* 测试的代码 */  
    #ifdef TEST_MAIN  
    #include <stdio.h>  
    int main(void) {  
        printf("e9c6d914c4b8d9ca == %016llx\n",  
            (unsigned long long) crc64(0,(unsigned char*)"123456789",9));  
        return 0;  
    }  

对字符串1到9做冗余运算。

      下面说说Redis中的随机算法实现的原理，一开始以为是调用的是math.Rand()方法，后来发现，我真的是错了。作者给出的理由是:



    /* Pseudo random number generation functions derived from the drand48()  
     * function obtained from pysam source code.  
     *  
     * This functions are used in order to replace the default math.random()  
     * Lua implementation with something having exactly the same behavior  
     * across different systems (by default Lua uses libc's rand() that is not  
     * required to implement a specific PRNG generating the same sequence  
     * in different systems if seeded with the same integer).  
     *  
     * The original code appears to be under the public domain.  
     * I modified it removing the non needed functions and all the  
     * 1960-style C coding stuff...  
     *   
     * 随机函数在不同的系统可能会表现出不同的行为，作者就没有采用系统自带的math.random,  
     * ,而是基于drand48()随机算法，重写了随机函数行为,作者在重写随机代码的时候取出了不需要的方法  
     * ----------------------------------------------------------------------------  


             也就是说作者是重写了随机算法。基于的算法实现是drand48()算法。因为此算法用到了48位的数字所以用此名。srand48和drand48是Unix库函数，drand48的作用是产生[0,1]之间均匀分布的随机数，采用了线性同余法和48位整数运算来产生伪随机序列函数用上面的算法产生一个48位的伪随机整数，然后再取出此整数的高32位作为随机数，然后将这个32位的伪随机数规划到[0,1]之间，用函数srand48来初始化drand48（),其只对于48位整数的高32位进行初始化，而其低16位被设定为随机值。这是一种统计特性比较好的伪随机发生器。这2个函数原版的C语言实现:



    #ifndef DRAND48_H  
    #define DRAND48_H  
      
    #include <stdlib.h>  
      
    #define m 0x100000000LL  
    #define c 0xB16  
    #define a 0x5DEECE66DLL  
      
    static unsigned long long seed = 1;  
      
    double drand48(void)  
    {  
        seed = (a * seed + c) & 0xFFFFFFFFFFFFLL;  
        unsigned int x = seed >> 16;  
        return  ((double)x / (double)m);  
         
    }  
      
    void srand48(unsigned int i)  
    {  
        seed  = (((long long int)i) << 16) | rand();  
    }  
      
    #endif  


因为这里还是用到了系统的rand()函数，z作者完全没有用系统自带的，所以在Redis中这里的实现就略有不同了:



    int32_t redisLrand48() {  
        next();  
        return (((int32_t)x[2] << (N - 1)) + (x[1] >> 1));  
    }  
      
    /* 设置种子 */  
    void redisSrand48(int32_t seedval) {  
        SEED(X0, LOW(seedval), HIGH(seedval));  
    }  
      
    static void next(void) {  
        uint32_t p[2], q[2], r[2], carry0, carry1;  
      
        MUL(a[0], x[0], p);  
        ADDEQU(p[0], c, carry0);  
        ADDEQU(p[1], carry0, carry1);  
        MUL(a[0], x[1], q);  
        ADDEQU(p[1], q[0], carry0);  
        MUL(a[1], x[0], r);  
        x[2] = LOW(carry0 + carry1 + CARRY(p[1], r[0]) + q[1] + r[1] +  
                a[0] * x[2] + a[1] * x[1] + a[2] * x[0]);  
        x[1] = LOW(p[1] + r[0]);  
        x[0] = LOW(p[0]);  
    }  

具体的next的实现，参照源代码，各种4则运算的并操作。