问题 用C / C ++计算32位CRC查找表


我想计算一个32位CRC查找表。我试过的一种方法是使用以下代码 这个网站：

#include <iostream>
#include <stdint.h>

void make_crc_table()
{
    unsigned long POLYNOMIAL = 0x04c11db7;
    unsigned long WIDTH = 8 * sizeof(unsigned long);
    unsigned long TOPBIT = 1 << (WIDTH - 1);
    unsigned long crcTable[256];
    unsigned long remainder;
    // Compute the remainder of each possible dividend
    for (int dividend = 0; dividend < 256; ++dividend)
    {
        // Start with the dividend followed by zeros
        remainder = dividend << (WIDTH - 8);

        // Perform modulo-2 division, a bit at a time
        for (unsigned long bit = 8; bit > 0; --bit)
        {
            // Try to divide the current data bit
            if (remainder & TOPBIT)
            {
                remainder = (remainder << 1) ^ POLYNOMIAL;
            }
            else
            {
                remainder = (remainder << 1);
            }
        }
        crcTable[dividend] = remainder;
    }

    // Print the CRC table
    for (int i = 0; i < 256; i++)
    {
        if (i % 4 == 0)
        {
            std::cout <<"\n";
        }
        std::cout << std::hex << crcTable[i];
        std::cout << ", ";
    }
}

int main()
{
    make_crc_table();
    return 0;
}

我尝试的另一种方法是使用我找到的以下代码 这个StackOverflow问题，可以下载代码 从这里在一个名为CRC Calculator.zip的文件中

#include <iostream>
#include <stdint.h>

#define POLYNOMIAL      0x04C11DB7
uint32_t A_crcLookupTable[256] = {0};
#define WIDTH    (8 * sizeof(uint32_t))
#define TOPBIT   (((uint32_t)1) << (WIDTH - 1))

#define FP_reflect_DATA(_DATO)                      (_DATO)
#define FP_reflect_CRCTableValue(_CRCTableValue)    (_CRCTableValue)

uint32_t F_CRC_ObtenValorDeTabla(uint8_t VP_Pos_Tabla)
{
    uint32_t VP_CRCTableValue = 0;
    uint8_t VP_Pos_bit = 0;

    VP_CRCTableValue = ((uint32_t) FP_reflect_DATA(VP_Pos_Tabla)) << (WIDTH - 8);

    for (VP_Pos_bit = 0; VP_Pos_bit < 8; VP_Pos_bit++)
    {
        if (VP_CRCTableValue & TOPBIT)
        {
            VP_CRCTableValue = (VP_CRCTableValue << 1) ^ POLYNOMIAL;
        }
        else
        {
            VP_CRCTableValue = (VP_CRCTableValue << 1);
        }
    }
    return (FP_reflect_CRCTableValue(VP_CRCTableValue));
}

void F_CRC_InicializaTabla(void)
{
    uint16_t VP_Pos_Array = 0;

    for (VP_Pos_Array = 0; VP_Pos_Array < 256; VP_Pos_Array++)
    {
        A_crcLookupTable[VP_Pos_Array] = F_CRC_ObtenValorDeTabla((uint8_t)(VP_Pos_Array &0xFF));

    }

}


void make_crc_table()
{
    F_CRC_InicializaTabla();

    // Print the CRC table
    for (int i = 0; i < 256; i++)
    {
        if (i % 4 == 0)
        {
            std::cout <<"\n";
        }
        std::cout << std::hex << A_crcLookupTable[i];
        std::cout << ", ";
    }
}

int main()
{
    make_crc_table();
    return 0;
}

这是什么的 正确 决赛桌应该是基于的 这个链接：

// The constants here are for the CRC-32 generator 
// polynomial, as defined in the Microsoft 
// Systems Journal, March 1995, pp. 107-108
CONST
  table: ARRAY[0..255] OF DWORD =
 ($00000000, $77073096, $EE0E612C, $990951BA,
  $076DC419, $706AF48F, $E963A535, $9E6495A3,
  $0EDB8832, $79DCB8A4, $E0D5E91E, $97D2D988,
  $09B64C2B, $7EB17CBD, $E7B82D07, $90BF1D91,
  $1DB71064, $6AB020F2, $F3B97148, $84BE41DE,
  $1ADAD47D, $6DDDE4EB, $F4D4B551, $83D385C7,
  $136C9856, $646BA8C0, $FD62F97A, $8A65C9EC,
  $14015C4F, $63066CD9, $FA0F3D63, $8D080DF5,
  $3B6E20C8, $4C69105E, $D56041E4, $A2677172,
  $3C03E4D1, $4B04D447, $D20D85FD, $A50AB56B,
  $35B5A8FA, $42B2986C, $DBBBC9D6, $ACBCF940,
  $32D86CE3, $45DF5C75, $DCD60DCF, $ABD13D59,
  $26D930AC, $51DE003A, $C8D75180, $BFD06116,
  $21B4F4B5, $56B3C423, $CFBA9599, $B8BDA50F,
  $2802B89E, $5F058808, $C60CD9B2, $B10BE924,
  $2F6F7C87, $58684C11, $C1611DAB, $B6662D3D,

  $76DC4190, $01DB7106, $98D220BC, $EFD5102A,
  $71B18589, $06B6B51F, $9FBFE4A5, $E8B8D433,
  $7807C9A2, $0F00F934, $9609A88E, $E10E9818,
  $7F6A0DBB, $086D3D2D, $91646C97, $E6635C01,
  $6B6B51F4, $1C6C6162, $856530D8, $F262004E,
  $6C0695ED, $1B01A57B, $8208F4C1, $F50FC457,
  $65B0D9C6, $12B7E950, $8BBEB8EA, $FCB9887C,
  $62DD1DDF, $15DA2D49, $8CD37CF3, $FBD44C65,
  $4DB26158, $3AB551CE, $A3BC0074, $D4BB30E2,
  $4ADFA541, $3DD895D7, $A4D1C46D, $D3D6F4FB,
  $4369E96A, $346ED9FC, $AD678846, $DA60B8D0,
  $44042D73, $33031DE5, $AA0A4C5F, $DD0D7CC9,
  $5005713C, $270241AA, $BE0B1010, $C90C2086,
  $5768B525, $206F85B3, $B966D409, $CE61E49F,
  $5EDEF90E, $29D9C998, $B0D09822, $C7D7A8B4,
  $59B33D17, $2EB40D81, $B7BD5C3B, $C0BA6CAD,

  $EDB88320, $9ABFB3B6, $03B6E20C, $74B1D29A,
  $EAD54739, $9DD277AF, $04DB2615, $73DC1683,
  $E3630B12, $94643B84, $0D6D6A3E, $7A6A5AA8,
  $E40ECF0B, $9309FF9D, $0A00AE27, $7D079EB1,
  $F00F9344, $8708A3D2, $1E01F268, $6906C2FE,
  $F762575D, $806567CB, $196C3671, $6E6B06E7,
  $FED41B76, $89D32BE0, $10DA7A5A, $67DD4ACC,
  $F9B9DF6F, $8EBEEFF9, $17B7BE43, $60B08ED5,
  $D6D6A3E8, $A1D1937E, $38D8C2C4, $4FDFF252,
  $D1BB67F1, $A6BC5767, $3FB506DD, $48B2364B,
  $D80D2BDA, $AF0A1B4C, $36034AF6, $41047A60,
  $DF60EFC3, $A867DF55, $316E8EEF, $4669BE79,
  $CB61B38C, $BC66831A, $256FD2A0, $5268E236,
  $CC0C7795, $BB0B4703, $220216B9, $5505262F,
  $C5BA3BBE, $B2BD0B28, $2BB45A92, $5CB36A04,
  $C2D7FFA7, $B5D0CF31, $2CD99E8B, $5BDEAE1D,

  $9B64C2B0, $EC63F226, $756AA39C, $026D930A,
  $9C0906A9, $EB0E363F, $72076785, $05005713,
  $95BF4A82, $E2B87A14, $7BB12BAE, $0CB61B38,
  $92D28E9B, $E5D5BE0D, $7CDCEFB7, $0BDBDF21,
  $86D3D2D4, $F1D4E242, $68DDB3F8, $1FDA836E,
  $81BE16CD, $F6B9265B, $6FB077E1, $18B74777,
  $88085AE6, $FF0F6A70, $66063BCA, $11010B5C,
  $8F659EFF, $F862AE69, $616BFFD3, $166CCF45,
  $A00AE278, $D70DD2EE, $4E048354, $3903B3C2,
  $A7672661, $D06016F7, $4969474D, $3E6E77DB,
  $AED16A4A, $D9D65ADC, $40DF0B66, $37D83BF0,
  $A9BCAE53, $DEBB9EC5, $47B2CF7F, $30B5FFE9,
  $BDBDF21C, $CABAC28A, $53B39330, $24B4A3A6,
  $BAD03605, $CDD70693, $54DE5729, $23D967BF,
  $B3667A2E, $C4614AB8, $5D681B02, $2A6F2B94,
  $B40BBE37, $C30C8EA1, $5A05DF1B, $2D02EF8D);

然而，这是我的输出来自两个程序（我对输出进行了分析，并且两者都相同），并且它是 不正确：

0, 4c11db7, 9823b6e, d4326d9, 
130476dc, 17c56b6b, 1a864db2, 1e475005, 
2608edb8, 22c9f00f, 2f8ad6d6, 2b4bcb61, 
350c9b64, 31cd86d3, 3c8ea00a, 384fbdbd, 
4c11db70, 48d0c6c7, 4593e01e, 4152fda9, 
5f15adac, 5bd4b01b, 569796c2, 52568b75, 
6a1936c8, 6ed82b7f, 639b0da6, 675a1011, 
791d4014, 7ddc5da3, 709f7b7a, 745e66cd, 
9823b6e0, 9ce2ab57, 91a18d8e, 95609039, 
8b27c03c, 8fe6dd8b, 82a5fb52, 8664e6e5, 
be2b5b58, baea46ef, b7a96036, b3687d81, 
ad2f2d84, a9ee3033, a4ad16ea, a06c0b5d, 
d4326d90, d0f37027, ddb056fe, d9714b49, 
c7361b4c, c3f706fb, ceb42022, ca753d95, 
f23a8028, f6fb9d9f, fbb8bb46, ff79a6f1, 
e13ef6f4, e5ffeb43, e8bccd9a, ec7dd02d, 
34867077, 30476dc0, 3d044b19, 39c556ae, 
278206ab, 23431b1c, 2e003dc5, 2ac12072, 
128e9dcf, 164f8078, 1b0ca6a1, 1fcdbb16, 
18aeb13, 54bf6a4, 808d07d, cc9cdca, 
7897ab07, 7c56b6b0, 71159069, 75d48dde, 
6b93dddb, 6f52c06c, 6211e6b5, 66d0fb02, 
5e9f46bf, 5a5e5b08, 571d7dd1, 53dc6066, 
4d9b3063, 495a2dd4, 44190b0d, 40d816ba, 
aca5c697, a864db20, a527fdf9, a1e6e04e, 
bfa1b04b, bb60adfc, b6238b25, b2e29692, 
8aad2b2f, 8e6c3698, 832f1041, 87ee0df6, 
99a95df3, 9d684044, 902b669d, 94ea7b2a, 
e0b41de7, e4750050, e9362689, edf73b3e, 
f3b06b3b, f771768c, fa325055, fef34de2, 
c6bcf05f, c27dede8, cf3ecb31, cbffd686, 
d5b88683, d1799b34, dc3abded, d8fba05a, 
690ce0ee, 6dcdfd59, 608edb80, 644fc637, 
7a089632, 7ec98b85, 738aad5c, 774bb0eb, 
4f040d56, 4bc510e1, 46863638, 42472b8f, 
5c007b8a, 58c1663d, 558240e4, 51435d53, 
251d3b9e, 21dc2629, 2c9f00f0, 285e1d47, 
36194d42, 32d850f5, 3f9b762c, 3b5a6b9b, 
315d626, 7d4cb91, a97ed48, e56f0ff, 
1011a0fa, 14d0bd4d, 19939b94, 1d528623, 
f12f560e, f5ee4bb9, f8ad6d60, fc6c70d7, 
e22b20d2, e6ea3d65, eba91bbc, ef68060b, 
d727bbb6, d3e6a601, dea580d8, da649d6f, 
c423cd6a, c0e2d0dd, cda1f604, c960ebb3, 
bd3e8d7e, b9ff90c9, b4bcb610, b07daba7, 
ae3afba2, aafbe615, a7b8c0cc, a379dd7b, 
9b3660c6, 9ff77d71, 92b45ba8, 9675461f, 
8832161a, 8cf30bad, 81b02d74, 857130c3, 
5d8a9099, 594b8d2e, 5408abf7, 50c9b640, 
4e8ee645, 4a4ffbf2, 470cdd2b, 43cdc09c, 
7b827d21, 7f436096, 7200464f, 76c15bf8, 
68860bfd, 6c47164a, 61043093, 65c52d24, 
119b4be9, 155a565e, 18197087, 1cd86d30, 
29f3d35, 65e2082, b1d065b, fdc1bec, 
3793a651, 3352bbe6, 3e119d3f, 3ad08088, 
2497d08d, 2056cd3a, 2d15ebe3, 29d4f654, 
c5a92679, c1683bce, cc2b1d17, c8ea00a0, 
d6ad50a5, d26c4d12, df2f6bcb, dbee767c, 
e3a1cbc1, e760d676, ea23f0af, eee2ed18, 
f0a5bd1d, f464a0aa, f9278673, fde69bc4, 
89b8fd09, 8d79e0be, 803ac667, 84fbdbd0, 
9abc8bd5, 9e7d9662, 933eb0bb, 97ffad0c, 
afb010b1, ab710d06, a6322bdf, a2f33668, 
bcb4666d, b8757bda, b5365d03, b1f740b4,

4260
2017-09-25 22:25


起源
您使用与您检查桌子的人相同的生成多项式吗？ - genisage
@genisage是的，我是。我正在使用用于以太网的CRC-32多项式。在这里，从我得到输出的网站列出：x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x1 + 1 - Programmer_D
打印五列输出就可以了 真的很难 找到有趣的系数。请使用2的幂。 - Ben Voigt
它们是否有可能以最高功率表示它作为最重要的位并且您以最高功率作为最低有效位来实现它？ - genisage
@genisage：我认为这是CRC值的位顺序和数组索引的位顺序的区别。但是，不能从另一个表构造一个表，因为位移也有效地在错误的方向上执行。 - Ben Voigt

答案:

这些位是相反的。注意表项为 array[0x80] （0x80反转为0x01） = 0xEDB88320，是的 0x04C11DB7 逆转。

示例代码：

#include <iostream>
#include <iomanip>

void make_crc_table(unsigned long crcTable[]) {
    unsigned long POLYNOMIAL = 0xEDB88320;
    unsigned long remainder;
    unsigned char b = 0;
    do {
        // Start with the data byte
        remainder = b;
        for (unsigned long bit = 8; bit > 0; --bit) {
            if (remainder & 1)
                remainder = (remainder >> 1) ^ POLYNOMIAL;
            else
                remainder = (remainder >> 1);
        }
        crcTable[(size_t)b] = remainder;
    } while(0 != ++b);
}

unsigned long gen_crc(unsigned char *p, size_t n, unsigned long crcTable[]) {
    unsigned long crc = 0xfffffffful;
    size_t i;
    for(i = 0; i < n; i++)
        crc = crcTable[*p++ ^ (crc&0xff)] ^ (crc>>8);
    return(~crc);
}

int main() {
    unsigned long crcTable[256];
    make_crc_table(crcTable);
    // Print the CRC table
    for (size_t i = 0; i < 256; i++) {
        std::cout << std::setfill('0') << std::setw(8) << std::hex << crcTable[i];
        if (i % 4 == 3)
            std::cout << std::endl;
        else
            std::cout << ", ";
    }
    return 0;
}

14
2017-09-26 02:35


我在“正确”表中看到了这个值，但我不确定如何更正算法。反转多项式并使用0xEDB88320似乎不起作用。我应该扭转哪些位？ - Programmer_D
@Programmer_D - 我用示例代码更新了答案。 - rcgldr
@Programmer_D - 请注意，在生成crc结束时使用的一个补码（~crc）不是传统的crc。如果crc没有补充，并附加到要编码的数据的末尾，则可以使用数据+ 4字节crc（称为重新编码）调用另一个生成crc，如果有，则返回值为零数据+ crc中没有可检测到的错误。 - rcgldr
@Programmer_D - 跟进，用crc（〜crc）的补码，然后如果你将crc附加到数据上，（小端，所以在X86上，*（unsigned long *）（array + n）= crc），然后，如果你使用gen_crc（array，n + 4，crcTable）重新编码，如果数据中没有错误，crc将为0x2144df1c。重新编码后，可以使用crc ^ = 0x2144df1c;删除gen_crc中使用的~crc的效果。 - rcgldr
@TypeKazt - 在这种情况下，操作的顺序无关紧要，因为p是指向字节的指针（unsigned char）。在任何一种情况下，（（CRC ^ byte）＆0xff）或（byte ^（CRC＆0xff）），结果是相同的，8位索引被提升为具有前导零位的32位索引，因为它被用作索引到表（xor操作也提升到32位索引，在第二种情况下具有前导零位） - rcgldr

如果没有足够的Flash和RAM（嵌入式软件），您可以使用此功能：

uint32_t CRC32_function(uint8_t *buf, uint32_t len){

    uint32_t val, crc;
    uint8_t i;

    crc = 0xFFFFFFFF;
    while(len--){
        val=(crc^*buf++)&0xFF;
        for(i=0; i<8; i++){
            val = val & 1 ? (val>>1)^0xEDB88320 : val>>1;
        }
        crc = val^crc>>8;
    }
    return crc^0xFFFFFFFF;
}

但CRC计算需要更多时间。


1
2018-02-06 07:57



热门问题

不使用eval / new函数的JavaScript模板库 当涉及内部类时，Java继承如何工作 .NET Windows服务的奇怪问题 在.ipa或.app下查找App ID 快速入门XSLT参考[关闭] 如何找出Android应用程序中未使用的资源 Ruby中并发的同步方法[重复] 将std :: chrono :: system_clock :: time_point转换为struct timeval并返回 Google Drive API V3（javascript）更新文件内容 Bootstrap 3.0 - 将元素推到底部 受密码保护的.NET ClickOnce部署？ 如何用postgresql安装wordpress coq Set或Type如何成为命题 硒滚动元素进入（中心）视图 在Spring Transaction JUnit测试中自动装配Hibernate会话的正确方法 Git的Dockerfile策略 如何在FOS_PICKFOLDER中使用IFileDialog，同时仍在对话框中显示文件名 在Firefox扩展中复制Google Chrome浏览器操作弹出效果 CakePHP找到MAX 芹菜 - 完成任务的召唤功能 从使用fmemopen创建的流中读取宽字符 .NET是否为每个程序集创建一个字符串实习池？ DefaultModelBinder不绑定嵌套模型 Navigator.MediaDevices.getUserMedia（）使用了哪些相机通信标准？ 选择命名空间名称时应该知道什么？ cout Swagger Codegen CLI Java客户端 - 如何正确使用它 一个很好的哈希函数用于采访整数，字符串？ Maven 3 ciManagement配置的目的是什么？ 如何通过语言文化获取代码页？
licensed under cc by-sa 3.0 with attribution.
隐私政策 往来