python - python字符串的CRC32散列

Question

使用现有的 C 示例算法，我想为 python 中的字符串生成正确的 CRC32 哈希。但是，我收到的结果不正确。我屏蔽了每个操作的结果并尝试复制原始算法的逻辑。 C 代码是由同一网站提供的，该网站具有网页字符串哈希检查工具，因此很可能是正确的。

下面是一个完整的 Python 文件，在其试图模仿的注释中包含 C 代码。所有相关信息都在文件中。

P_32 = 0xEDB88320
init = 0xffffffff
_ran = True
tab32 = []

def mask32(n):
    return n & 0xffffffff

def mask8(n):
    return n & 0x000000ff

def mask1(n):
    return n & 0x00000001

def init32():
    for i in range(256):
        crc = mask32(i)
        for j in range(8):
            if (mask1(crc) == 1):
                crc = mask32(mask32(crc >> 1) ^ P_32)
            else:
                crc = mask32(crc >> 1)
        tab32.append(crc)
    global _ran
    _ran = False

def update32(crc, char):
    char = mask8(char)
    t = crc ^ char
    crc = mask32(mask32(crc >> 8) ^ tab32[mask8(t)])
    return crc

def run(string):
    if _ran:
        init32()
    crc = init
    for c in string:
        crc = update32(crc, ord(c))
    print(hex(crc)[2:].upper())

check0 = "The CRC32 of this string is 4A1C449B"
check1 = "123456789" # CBF43926
run(check0) # Produces B5E3BB64
run(check1) # Produces 340BC6D9

# Check CRC-32 on http://www.lammertbies.nl/comm/info/crc-calculation.html#intr

"""
/* http://www.lammertbies.nl/download/lib_crc.zip */

#define                 P_32        0xEDB88320L
static int              crc_tab32_init          = FALSE;
static unsigned long    crc_tab32[256];

    /*******************************************************************\
    *                                                                   *
    *   unsigned long update_crc_32( unsigned long crc, char c );       *
    *                                                                   *
    *   The function update_crc_32 calculates a  new  CRC-32  value     *
    *   based  on  the  previous value of the CRC and the next byte     *
    *   of the data to be checked.                                      *
    *                                                                   *
    \*******************************************************************/

unsigned long update_crc_32( unsigned long crc, char c ) {

    unsigned long tmp, long_c;

    long_c = 0x000000ffL & (unsigned long) c;

    if ( ! crc_tab32_init ) init_crc32_tab();

    tmp = crc ^ long_c;
    crc = (crc >> 8) ^ crc_tab32[ tmp & 0xff ];

    return crc;

}  /* update_crc_32 */

    /*******************************************************************\
    *                                                                   *
    *   static void init_crc32_tab( void );                             *
    *                                                                   *
    *   The function init_crc32_tab() is used  to  fill  the  array     *
    *   for calculation of the CRC-32 with values.                      *
    *                                                                   *
    \*******************************************************************/

static void init_crc32_tab( void ) {

    int i, j;
    unsigned long crc;

    for (i=0; i<256; i++) {

        crc = (unsigned long) i;

        for (j=0; j<8; j++) {

            if ( crc & 0x00000001L ) crc = ( crc >> 1 ) ^ P_32;
            else                     crc =   crc >> 1;
        }

        crc_tab32[i] = crc;
    }

    crc_tab32_init = TRUE;

}  /* init_crc32_tab */
"""

Answer 1

当前的实现只有一件事是错误的，修复实际上只是运行函数末尾的一行代码，即:

crc = crc ^ init

如果将其添加到您的运行函数中，则如下所示:

def run(string):
    if _ran:
        init32()
    crc = init
    for c in string:
        crc = update32(crc, ord(c))
    crc = crc ^ init    
    print(hex(crc)[2:].upper())

这将为您提供您期望的正确结果。这是必要的原因是在您完成更新 CRC32 之后，它的最终确定是将它与 0xFFFFFFFF 进行异或运算。由于您只有 init 表和更新函数，而没有 finalize，因此您离实际的 crc 差了一步。

另一个更直接的 C 实现是 this one，它更容易看到整个过程。唯一有点模糊的是 init poly ~0x0 是相同的 (0xFFFFFFFF)。