程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Redis源碼分析(二十三)--- CRC循環冗余算法和RAND隨機數算法

Redis源碼分析(二十三)--- CRC循環冗余算法和RAND隨機數算法

編輯:C++入門知識

Redis源碼分析(二十三)--- CRC循環冗余算法和RAND隨機數算法


今天開始研究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 
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 

#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則運算的並操作。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved