修改 CRC64 的散列 table 以生成 65536 而不是 256 个值

Question

简单地将循环中的 256 修改为 65536 只是一遍又一遍地重复相同的 256 值。如何生成65536个不同的值？

#define CRC64_ECMA182_POLY 0x42F0E1EBA9EA3693ULL

static uint64_t crc64_table[256] = {0};

static void generate_crc64_table(void)
{
    uint64_t i, j, c, crc;

    for (i = 0; i < 256; i++) {
        crc = 0;
        c = i << 56;

        for (j = 0; j < 8; j++) {
            if ((crc ^ c) & 0x8000000000000000ULL)
                crc = (crc << 1) ^ CRC64_ECMA182_POLY;
            else
                crc <<= 1;
            c <<= 1;
        }

        crc64_table[i] = crc;
    }
}

Answer 1

如果你想要 65536 个值，大概你想要一个 16 位 table，所以将位循环也升级到 16。

static void generate_crc64_table(void)
{
    uint64_t i, j, c, crc;

    for (i = 0; i < 65536 ; i++) { // 65536 was 256  
        crc = 0;
        c = i << 32; // 32 was 56

        for (j = 0; j < 16; j++) { // 16 was 8
            if ((crc ^ c) & 0x8000000000000000ULL)
                crc = (crc << 1) ^ CRC64_ECMA182_POLY;
            else
                crc <<= 1;
            c <<= 1;
        }

        crc64_table[i] = crc;
    }
}

不保证这会产生有用的 table，但值应该都不同 at-least。

Answer 2

如果生成的 CRC 应该与小端处理器（例如 X86）上面向位或字节的 CRC 匹配，则需要交换每个 2 字节 == 16 位对的 upper/lower 字节。示例代码，不确定是否可以清理。注意生成函数中的len是#shorts == #2 byte elements == #16 bit elements.

#define CRC64_ECMA182_POLY 0x42F0E1EBA9EA3693ULL

static uint64_t crc64_table[65536] = {0};

static void generate_crc64_table(void)
{
    uint64_t i, j, crc;
    for (i = 0; i < 65536; i++) {
        crc = i << 48;
        for (j = 0; j < 16; j++) 
            // assumes two's complement math
            crc = (crc << 1) ^ ((0ull-(crc>>63))&CRC64_ECMA182_POLY);
        // swap byte pairs on index and values for table lookup
        crc64_table[((i & 0xff00) >> 8) | ((i & 0x00ff) << 8)] = 
            ((crc & 0xff00ff00ff00ff00ull) >> 8) | ((crc & 0x00ff00ff00ff00ffull) << 8);
    }
}

static uint64_t generate_crc64(uint16_t *bfr, int len)
{
    uint64_t crc = 0;
    int i;
    for (i = 0; i < len; i++)
        // generates crc with byte pairs swapped
        crc = crc64_table[(crc>>48) ^ *bfr++] ^ (crc << 16);
        // unswap byte pairs for return
    return ((crc & 0xff00ff00ff00ff00) >> 8) | ((crc & 0x00ff00ff00ff00ff) << 8);
}

修改 CRC64 的散列 table 以生成 65536 而不是 256 个值

Modify CRC64's hash table to generate 65536 instead of 256 values

c

hash

cryptography

crc