checksum algorithm adler32

约定不等于承诺〃 2021-11-09 01:01 318阅读 0赞

在 wiki 上有比较详细的解释 以下大部分解释来自 wiki 上的说明

*  一个 adler-32 checksum 是由两个 16bit checksum A 与 B 组合而成的 32bit 的数
 *  A 初始化为 1 B 初始化为 0
 *  A是需要计算的字符串中每一个字符相加的值 并且对 65521 取模
 *  B是每一步中A的值相加 并且对 65521 取模
 *  65521 是 2^16 内的最大质数
 *  用途
    
     *  adler32 checksum 在 zlib 库中被广泛的使用
     *  在rsync utility 中也有使用 rolling checksum

--------------------

具体的伪代码如下 D 是需要进行adler32计算的字符串(string of bytes) n 是 D 的长度

A = 1 + D1 + D2 + D3 + ... + Dn (mod 65521)
    B = (1 + D1) + (1 + D1 + D2) + ... + (1 + D1 + D2 + ... + Dn) (mod 65521)
                                ↓↓↓  等价于下面
    B = n * D1 + (n - 1) * D2 + (n - 2) * D3 + ... + Dn + n (mod 65521)
    Adler-32(D) = B * 65535 + A

wiki上给出的C实现实例如下adler32函数所示 基本和伪代码一致

#include <iostream>
    using namespace std;
    
    const uint32_t MOD_ADLER = 65521;
    
    uint32_t adler32(unsigned char *data, size_t len)
    { 
        uint32_t a = 1, b = 0;
        size_t index;
        for (index = 0; index < len; ++index)
        { 
            a = (a + data[index]) % MOD_ADLER;
            b = (b + a) % MOD_ADLER;
        }
        return (b << 16) | a;
    }
    
    int main(int argc, char *argv[])
    { 
        unsigned char *data;
        data = (unsigned char *)("Wikipedia");
        adler32(data, 9);
        return 1;
    }

--------------------

在 rsync 中的checksum方法如下

/* a simple 32 bit checksum that can be upadted from either end (inspired by Mark Adler's Adler-32 checksum) */
    uint32 get_checksum1(char *buf1, int32 len)
    { 
        int32 i;
        uint32 s1, s2;
        schar *buf = (schar *)buf1;
    
        s1 = s2 = 0;
        for (i = 0; i < (len-4); i+=4) { 
    	s2 += 4*(s1 + buf[i]) + 3*buf[i+1] + 2*buf[i+2] + buf[i+3] +
    	  10*CHAR_OFFSET;
    	s1 += (buf[i+0] + buf[i+1] + buf[i+2] + buf[i+3] + 4*CHAR_OFFSET);
        }
        for (; i < len; i++) { 
    	s1 += (buf[i]+CHAR_OFFSET); s2 += s1;
        }
        return (s1 & 0xffff) + (s2 << 16);
    }
    
    // 其中 schar 和 CHAR_OFFSET 的定义在 rsync.h 中如下 
    
    #ifdef SIGNED_CHAR_OK
    #define schar signed char
    #else
    #define schar char
    #endif
    
    /* a non-zero CHAR_OFFSET makes the rolling sum stronger, but is incompatible with older versions :-( */
    #define CHAR_OFFSET 0

阅读代码发现 只有 A 的初始值从 1 变成了 0 不一样  
根据定义稍微简化一下如下 并加以测试

uint32_t get_checksum(const char *buf, uint32_t len)
    { 
        uint32_t i;
        uint32_t s1, s2;
        s1 = s2 = 0;
        for (i = 0; i < (len - 4); i += 4)
        { 
            s2 += 4 * (s1 + buf[i]) + 3 * buf[i + 1] + 2 * buf[i + 2] + buf[i + 3];
            s1 += (buf[i + 0] + buf[i + 1] + buf[i + 2] + buf[i + 3]);
        }
        for (; i < len; i++)
        { 
            s1 += buf[i];
            s2 += s1;
        }
        return (s1 & 0xffff) + (s2 << 16);
    }
    
    int main(int argc, char *argv[])
    { 
        unsigned char *data;
        data = (unsigned char *)("Wikipedia");
        adler32(data, 9);
        get_checksum("Wikipedia", 9);
        return 1;
    }

由于初始化是 A 初始化为 0 所以计算出来的 A B 两个值有差异 以上面的测试来说 A 相差 1 B 相差 9  
如果初始化为 s1=1，s2=0 那么结果将完全一致