CRC32 计算 CRC 消息开头的 CRC 散列
CRC32 calculation with CRC hash at the beginning of the message in C
我需要计算消息的 CRC 并将其 放在这条消息的开头 ，以便 'prepended' 补丁字节的消息的最终 CRC 等于0. 在几篇文章的帮助下，我能够很容易地做到这一点，但不是我的特定参数。问题是我必须使用给定的 CRC32 算法来计算内存块的 CRC，但我没有计算那 4 个补丁字节/'kind of CRC' 的 'reverse' 算法。给定的 CRC32 算法的参数是：
- 多项式：0x04C11DB7
- 字节顺序：大端
- 初始值：0xFFFFFFFF
- 反映：错误
- 异或输出：0L
- 测试流：0x0123、0x4567、0x89AB、0xCDEF 结果为 CRC = 0x612793C3
计算CRC的代码（半字节，table驱动，希望数据类型定义不言自明）：
uint32 crc32tab(uint16* data, uint32 len, uint32 crc)
{
uint8 nibble;
int i;
while(len--)
{
for(i = 3; i >= 0; i--)
{
nibble = (*data >> i*4) & 0x0F;
crc = ((crc << 4) | nibble) ^ tab[crc >> 28];
}
data++;
}
return crc;
}
所需的 table 是（我认为短 [16] table 应该包含大 [256] table 中的每第 16 个元素，但是这个 table实际上包含 first 16 个元素，但这就是它提供给我的方式）：
static const uint32 tab[16]=
{
0x00000000, 0x04C11DB7, 0x09823B6E, 0x0D4326D9,
0x130476DC, 0x17C56B6B, 0x1A864DB2, 0x1E475005,
0x2608EDB8, 0x22C9F00F, 0x2F8AD6D6, 0x2B4BCB61,
0x350C9B64, 0x31CD86D3, 0x3C8EA00A, 0x384FBDBD
};
我修改了代码，使其不那么长，但功能保持不变。问题是这个正向 CRC 计算看起来更像 backward/reverse CRC 计算。
我花了将近一周的时间试图找出正确的 polynomial/algorithm/table 组合，但没有成功。如果有帮助，我提出了对应于上面 table 驱动代码的按位算法，尽管这毕竟不是那么难：
uint32 crc32(uint16* data, uint32 len, uint32 crc)
{
uint32 i;
while(len--)
{
for(i = 0; i < 16; i++)
{
// #define POLY 0x04C11DB7
crc = (crc << 1) ^ (((crc ^ *data) & 0x80000000) ? POLY : 0);
}
crc ^= *data++;
}
return crc;
}
这是预期的结果 - 前 2 个 16 位字构成所需的未知 CRC，其余是已知数据本身（通过将这些示例提供给提供的算法，结果为 0）。
{0x3288, 0xD244, 0xCDEF, 0x89AB, 0x4567, 0x0123}
{0xC704, 0xDD7B, 0x0000} - append as many zeros as you like, the result is the same
{0xCEBD, 0x1ADD, 0xFFFF}
{0x81AB, 0xB932, 0xFFFF, 0xFFFF}
{0x0857, 0x0465, 0x0000, 0x0123}
{0x1583, 0xD959, 0x0123}
^ ^
| |
unknown bytes that I need to calculate
我认为在 0xFFFF 或 0x0000 字上测试这个很方便，因为计算的方向和字节顺序并不重要（我希望 :D）。所以要小心使用其他测试字节，因为计算的方向很曲折：D。您还可以看到，通过仅向算法（向前和向后）提供零，结果是所谓的残差 (0xC704DD7B)，这可能会有所帮助。
所以...我写了至少 10 个不同的函数（逐位、tables、多项式组合等）试图解决这个问题，但没有成功。我在这里给你我寄予希望的功能。它是上面 table 驱动算法的 'reversed' 算法，当然 table 不同。问题是我从中得到的唯一正确的 CRC 是全 0 消息，这并不意外。我还编写了按位算法的反向实现（反向移位等），但是那个 returns 只有第一个字节正确。
这是 table 驱动的，指向 data 的指针应该指向消息的最后一个元素，crc 输入应该是请求的 crc（整个消息为 0，或者您可以采用另一种方法 - 消息的最后 4 个字节是您要查找的 CRC：）：
uint32 crc32tabrev(uint16* data, uint32 len, uint32 crc)
{
uint8 nibble;
int i;
while(len--)
{
for(i = 0; i < 4; i++)
{
nibble = (*data >> i*4) & 0x0F;
crc = (crc >> 4) ^ revtab[((crc ^ nibble) & 0x0F)];
}
data--;
}
return reverse(crc); //reverse() flips all bits around center (MSB <-> LSB ...)
}
table，希望是'the chosen one':
static const uint32 revtab[16]=
{
0x00000000, 0x1DB71064, 0x3B6E20C8, 0x26D930AC,
0x76DC4190, 0x6B6B51F4, 0x4DB26158, 0x5005713C,
0xEDB88320, 0xF00F9344, 0xD6D6A3E8, 0xCB61B38C,
0x9B64C2B0, 0x86D3D2D4, 0xA00AE278, 0xBDBDF21C
};
如您所见，该算法有一些优点让我 运行 陷入困境，我认为我可能走在正确的轨道上，但我遗漏了一些东西。我希望多一双眼睛能看到我看不到的东西。很抱歉这么长 post（没有土豆 :D），但我认为所有这些解释都是必要的。预先感谢您的见解或建议。
我会回答你的 CRC 规范，CRC-32/MPEG-2。我将不得不忽略您计算 CRC 的尝试，因为它们不正确。
不管怎样，为了回答你的问题，我正好写了一个解决这个问题的程序。它被称为spoof.c。它可以非常快速地计算出要更改消息中的哪些位以获得所需的 CRC。它按照 log(n) 时间的顺序执行此操作，其中 n 是消息的长度。这是一个例子：
让我们来看一下九字节的消息 123456789（那些以 ASCII 表示的数字）。我们将在它前面加上四个零字节，我们将对其进行更改以在最后获得所需的 CRC。十六进制的消息是：00 00 00 00 31 32 33 34 35 36 37 38 39。现在我们计算该消息的 CRC-32/MPEG-2。我们得到 373c5870.
现在我们运行spoof有了这个输入，它是以位为单位的CRC长度，它没有反映出来的事实，多项式，我们刚刚计算的CRC，长度以字节为单位的消息，以及前四个字节中的所有 32 位位置（这是我们允许 spoof 更改的内容）：
32 0 04C11DB7
373c5870 13
0 0 1 2 3 4 5 6 7
1 0 1 2 3 4 5 6 7
2 0 1 2 3 4 5 6 7
3 0 1 2 3 4 5 6 7
它为这个输出提供了前四个字节中要设置的位：
invert these bits in the sequence:
offset bit
0 1
0 2
0 4
0 5
0 6
1 0
1 2
1 5
1 7
2 0
2 2
2 5
2 6
2 7
3 0
3 1
3 2
3 4
3 5
3 7
然后我们将前四个字节设置为：76 a5 e5 b7。然后我们通过计算消息 76 a5 e5 b7 31 32 33 34 35 36 37 38 39 的 CRC-32/MPEG-2 进行测试，我们得到 00000000，我们想要的结果。
您可以根据您的应用程序调整 spoof.c。
下面是一个使用按位算法正确计算字节流 CRC-32/MPEG-2 的示例：
uint32_t crc32m(uint32_t crc, const unsigned char *buf, size_t len)
{
int k;
while (len--) {
crc ^= (uint32_t)(*buf++) << 24;
for (k = 0; k < 8; k++)
crc = crc & 0x80000000 ? (crc << 1) ^ 0x04c11db7 : crc << 1;
}
return crc;
}
并使用问题中的 table 的 nybble-wise 算法（这是正确的）：
uint32_t crc_table[] = {
0x00000000, 0x04C11DB7, 0x09823B6E, 0x0D4326D9,
0x130476DC, 0x17C56B6B, 0x1A864DB2, 0x1E475005,
0x2608EDB8, 0x22C9F00F, 0x2F8AD6D6, 0x2B4BCB61,
0x350C9B64, 0x31CD86D3, 0x3C8EA00A, 0x384FBDBD
};
uint32_t crc32m_nyb(uint32_t crc, const unsigned char *buf, size_t len)
{
while (len--) {
crc ^= (uint32_t)(*buf++) << 24;
crc = (crc << 4) ^ crc_table[crc >> 28];
crc = (crc << 4) ^ crc_table[crc >> 28];
}
return crc;
}
在这两种情况下，初始 CRC 必须是 0xffffffff。
好吧，在我提出问题后几个小时，我不记得名字的人 post 回答了我的问题，结果证明是正确的。不知何故，这个答案被完全删除了，我不知道为什么或是谁做的，但我要感谢这个人，如果你会看到这个，请再次 post 你的答案，我会删除这个。但对于其他用户，这是他对我有用的答案，再次感谢你，神秘的（不幸的是，我不能很好地复制他的笔记和建议，只能复制代码本身）：
编辑：最初的答案来自用户 samgak，所以在他 post 回答之前，它会一直保留在这里。
反向CRC算法：
uint32 revcrc32(uint16* data, uint32 len, uint32 crc)
{
uint32 i;
data += len - 1;
while(len--)
{
crc ^= *data--;
for(i = 0; i < 16; i++)
{
uint32 crc1 = ((crc ^ POLY) >> 1) | 0x80000000;
uint32 crc2 = crc >> 1;
if(((crc1 << 1) ^ (((crc1 ^ *data) & 0x80000000) ? POLY : 0)) == crc)
crc = crc1;
else if(((crc2 << 1) ^ (((crc2 ^ *data) & 0x80000000) ? POLY : 0)) == crc)
crc = crc2;
}
}
return crc;
}
查找补丁字节：
#define CRC_OF_ZERO 0xb7647d
void bruteforcecrc32(uint32 targetcrc)
{
// compute prefixes:
uint16 j;
for(j = 0; j <= 0xffff; j++)
{
uint32 crc = revcrc32(&j, 1, targetcrc);
if((crc >> 16) == (CRC_OF_ZERO >> 16))
{
printf("prefixes: %04lX %04lX\n", (crc ^ CRC_OF_ZERO) & 0xffff, (uint32)j);
return;
}
}
}
用法：
uint16 test[] = {0x0123, 0x4567, 0x89AB, 0xCDEF}; // prefix should be 0x0CD8236A
bruteforcecrc32(revcrc32(test, 4, 0L));
替代方法。假设xorout = 0，如果不是，则计算正常的crc后，再用crc ^= xorout将其去掉。这里的方法将普通的 crc 乘以 (1/2)%(crc polynomial) 提高到 (message size in bits) power % (crc polynomial) 等同于向后循环它。如果消息大小固定，则映射固定，时间复杂度为 O(1)。否则，它是 O(log(n)).
此示例代码使用 Visual Studio 和一个用于无进位乘法 (PCLMULQDQ) 的内在函数，它使用 XMM（128 位）寄存器。 Visual Studio 使用 __m128i 类型来表示整数 XMM 值。
#include <stdio.h>
#include <stdlib.h>
#include <intrin.h>
typedef unsigned char uint8_t;
typedef unsigned int uint32_t;
typedef unsigned long long uint64_t;
#define POLY (0x104c11db7ull)
#define POLYM ( 0x04c11db7u)
static uint32_t crctbl[256];
static __m128i poly; /* poly */
static __m128i invpoly; /* 2^64 / POLY */
void GenMPoly(void) /* generate __m128i poly info */
{
uint64_t N = 0x100000000ull;
uint64_t Q = 0;
for(size_t i = 0; i < 33; i++){
Q <<= 1;
if(N&0x100000000ull){
Q |= 1;
N ^= POLY;
}
N <<= 1;
}
poly.m128i_u64[0] = POLY;
invpoly.m128i_u64[0] = Q;
}
void GenTbl(void) /* generate crc table */
{
uint32_t crc;
uint32_t c;
uint32_t i;
for(c = 0; c < 0x100; c++){
crc = c<<24;
for(i = 0; i < 8; i++)
/* assumes twos complement */
crc = (crc<<1)^((0-(crc>>31))&POLYM);
crctbl[c] = crc;
}
}
uint32_t GenCrc(uint8_t * bfr, size_t size) /* generate crc */
{
uint32_t crc = 0xffffffffu;
while(size--)
crc = (crc<<8)^crctbl[(crc>>24)^*bfr++];
return(crc);
}
/* carryless multiply modulo poly */
uint32_t MpyModPoly(uint32_t a, uint32_t b) /* (a*b)%poly */
{
__m128i ma, mb, mp, mt;
ma.m128i_u64[0] = a;
mb.m128i_u64[0] = b;
mp = _mm_clmulepi64_si128(ma, mb, 0x00); /* p[0] = a*b */
mt = _mm_clmulepi64_si128(mp, invpoly, 0x00); /* t[1] = (p[0]*((2^64)/POLY))>>64 */
mt = _mm_clmulepi64_si128(mt, poly, 0x01); /* t[0] = t[1]*POLY */
return mp.m128i_u32[0] ^ mt.m128i_u32[0]; /* ret = p[0] ^ t[0] */
}
/* exponentiate by repeated squaring modulo poly */
uint32_t PowModPoly(uint32_t a, uint32_t b) /* pow(a,b)%poly */
{
uint32_t prd = 0x1u; /* current product */
uint32_t sqr = a; /* current square */
while(b){
if(b&1)
prd = MpyModPoly(prd, sqr);
sqr = MpyModPoly(sqr, sqr);
b >>= 1;
}
return prd;
}
int main()
{
uint32_t inv; /* 1/2 % poly, constant */
uint32_t fix; /* fix value, constant if msg size fixed */
uint32_t crc; /* crc at end of msg */
uint32_t pre; /* prefix for msg */
uint8_t msg[13] = {0x00,0x00,0x00,0x00,0x31,0x32,0x33,0x34,0x35,0x36,0x37,0x38,0x39};
GenMPoly(); /* generate __m128i polys */
GenTbl(); /* generate crc table */
inv = PowModPoly(2, 0xfffffffeu); /* inv = 2^(2^32-2) % Poly = 1/2 % poly */
fix = PowModPoly(inv, 8*sizeof(msg)); /* fix value */
crc = GenCrc(msg, sizeof(msg)); /* calculate normal crc */
pre = MpyModPoly(fix, crc); /* convert to prefix */
printf("crc = %08x pre = %08x ", crc, pre);
msg[0] = (uint8_t)(pre>>24); /* store prefix in msg */
msg[1] = (uint8_t)(pre>>16);
msg[2] = (uint8_t)(pre>> 8);
msg[3] = (uint8_t)(pre>> 0);
crc = GenCrc(msg, sizeof(msg)); /* check result */
if(crc == 0)
printf("passed\n");
else
printf("failed\n");
return 0;
}
我需要计算消息的 CRC 并将其 放在这条消息的开头 ，以便 'prepended' 补丁字节的消息的最终 CRC 等于0. 在几篇文章的帮助下，我能够很容易地做到这一点，但不是我的特定参数。问题是我必须使用给定的 CRC32 算法来计算内存块的 CRC，但我没有计算那 4 个补丁字节/'kind of CRC' 的 'reverse' 算法。给定的 CRC32 算法的参数是：
- 多项式：0x04C11DB7
- 字节顺序：大端
- 初始值：0xFFFFFFFF
- 反映：错误
- 异或输出：0L
- 测试流：0x0123、0x4567、0x89AB、0xCDEF 结果为 CRC = 0x612793C3
计算CRC的代码（半字节，table驱动，希望数据类型定义不言自明）：
uint32 crc32tab(uint16* data, uint32 len, uint32 crc)
{
uint8 nibble;
int i;
while(len--)
{
for(i = 3; i >= 0; i--)
{
nibble = (*data >> i*4) & 0x0F;
crc = ((crc << 4) | nibble) ^ tab[crc >> 28];
}
data++;
}
return crc;
}
所需的 table 是（我认为短 [16] table 应该包含大 [256] table 中的每第 16 个元素，但是这个 table实际上包含 first 16 个元素，但这就是它提供给我的方式）：
static const uint32 tab[16]=
{
0x00000000, 0x04C11DB7, 0x09823B6E, 0x0D4326D9,
0x130476DC, 0x17C56B6B, 0x1A864DB2, 0x1E475005,
0x2608EDB8, 0x22C9F00F, 0x2F8AD6D6, 0x2B4BCB61,
0x350C9B64, 0x31CD86D3, 0x3C8EA00A, 0x384FBDBD
};
我修改了代码，使其不那么长，但功能保持不变。问题是这个正向 CRC 计算看起来更像 backward/reverse CRC 计算。
我花了将近一周的时间试图找出正确的 polynomial/algorithm/table 组合，但没有成功。如果有帮助，我提出了对应于上面 table 驱动代码的按位算法，尽管这毕竟不是那么难：
uint32 crc32(uint16* data, uint32 len, uint32 crc)
{
uint32 i;
while(len--)
{
for(i = 0; i < 16; i++)
{
// #define POLY 0x04C11DB7
crc = (crc << 1) ^ (((crc ^ *data) & 0x80000000) ? POLY : 0);
}
crc ^= *data++;
}
return crc;
}
这是预期的结果 - 前 2 个 16 位字构成所需的未知 CRC，其余是已知数据本身（通过将这些示例提供给提供的算法，结果为 0）。
{0x3288, 0xD244, 0xCDEF, 0x89AB, 0x4567, 0x0123}
{0xC704, 0xDD7B, 0x0000} - append as many zeros as you like, the result is the same
{0xCEBD, 0x1ADD, 0xFFFF}
{0x81AB, 0xB932, 0xFFFF, 0xFFFF}
{0x0857, 0x0465, 0x0000, 0x0123}
{0x1583, 0xD959, 0x0123}
^ ^
| |
unknown bytes that I need to calculate
我认为在 0xFFFF 或 0x0000 字上测试这个很方便，因为计算的方向和字节顺序并不重要（我希望 :D）。所以要小心使用其他测试字节，因为计算的方向很曲折：D。您还可以看到，通过仅向算法（向前和向后）提供零，结果是所谓的残差 (0xC704DD7B)，这可能会有所帮助。
所以...我写了至少 10 个不同的函数（逐位、tables、多项式组合等）试图解决这个问题，但没有成功。我在这里给你我寄予希望的功能。它是上面 table 驱动算法的 'reversed' 算法，当然 table 不同。问题是我从中得到的唯一正确的 CRC 是全 0 消息，这并不意外。我还编写了按位算法的反向实现（反向移位等），但是那个 returns 只有第一个字节正确。
这是 table 驱动的，指向 data 的指针应该指向消息的最后一个元素，crc 输入应该是请求的 crc（整个消息为 0，或者您可以采用另一种方法 - 消息的最后 4 个字节是您要查找的 CRC：
uint32 crc32tabrev(uint16* data, uint32 len, uint32 crc)
{
uint8 nibble;
int i;
while(len--)
{
for(i = 0; i < 4; i++)
{
nibble = (*data >> i*4) & 0x0F;
crc = (crc >> 4) ^ revtab[((crc ^ nibble) & 0x0F)];
}
data--;
}
return reverse(crc); //reverse() flips all bits around center (MSB <-> LSB ...)
}
table，希望是'the chosen one':
static const uint32 revtab[16]=
{
0x00000000, 0x1DB71064, 0x3B6E20C8, 0x26D930AC,
0x76DC4190, 0x6B6B51F4, 0x4DB26158, 0x5005713C,
0xEDB88320, 0xF00F9344, 0xD6D6A3E8, 0xCB61B38C,
0x9B64C2B0, 0x86D3D2D4, 0xA00AE278, 0xBDBDF21C
};
如您所见，该算法有一些优点让我 运行 陷入困境，我认为我可能走在正确的轨道上，但我遗漏了一些东西。我希望多一双眼睛能看到我看不到的东西。很抱歉这么长 post（没有土豆 :D），但我认为所有这些解释都是必要的。预先感谢您的见解或建议。
我会回答你的 CRC 规范，CRC-32/MPEG-2。我将不得不忽略您计算 CRC 的尝试，因为它们不正确。
不管怎样，为了回答你的问题，我正好写了一个解决这个问题的程序。它被称为spoof.c。它可以非常快速地计算出要更改消息中的哪些位以获得所需的 CRC。它按照 log(n) 时间的顺序执行此操作，其中 n 是消息的长度。这是一个例子：
让我们来看一下九字节的消息 123456789（那些以 ASCII 表示的数字）。我们将在它前面加上四个零字节，我们将对其进行更改以在最后获得所需的 CRC。十六进制的消息是：00 00 00 00 31 32 33 34 35 36 37 38 39。现在我们计算该消息的 CRC-32/MPEG-2。我们得到 373c5870.
现在我们运行spoof有了这个输入，它是以位为单位的CRC长度，它没有反映出来的事实，多项式，我们刚刚计算的CRC，长度以字节为单位的消息，以及前四个字节中的所有 32 位位置（这是我们允许 spoof 更改的内容）：
32 0 04C11DB7
373c5870 13
0 0 1 2 3 4 5 6 7
1 0 1 2 3 4 5 6 7
2 0 1 2 3 4 5 6 7
3 0 1 2 3 4 5 6 7
它为这个输出提供了前四个字节中要设置的位：
invert these bits in the sequence:
offset bit
0 1
0 2
0 4
0 5
0 6
1 0
1 2
1 5
1 7
2 0
2 2
2 5
2 6
2 7
3 0
3 1
3 2
3 4
3 5
3 7
然后我们将前四个字节设置为：76 a5 e5 b7。然后我们通过计算消息 76 a5 e5 b7 31 32 33 34 35 36 37 38 39 的 CRC-32/MPEG-2 进行测试，我们得到 00000000，我们想要的结果。
您可以根据您的应用程序调整 spoof.c。
下面是一个使用按位算法正确计算字节流 CRC-32/MPEG-2 的示例：
uint32_t crc32m(uint32_t crc, const unsigned char *buf, size_t len)
{
int k;
while (len--) {
crc ^= (uint32_t)(*buf++) << 24;
for (k = 0; k < 8; k++)
crc = crc & 0x80000000 ? (crc << 1) ^ 0x04c11db7 : crc << 1;
}
return crc;
}
并使用问题中的 table 的 nybble-wise 算法（这是正确的）：
uint32_t crc_table[] = {
0x00000000, 0x04C11DB7, 0x09823B6E, 0x0D4326D9,
0x130476DC, 0x17C56B6B, 0x1A864DB2, 0x1E475005,
0x2608EDB8, 0x22C9F00F, 0x2F8AD6D6, 0x2B4BCB61,
0x350C9B64, 0x31CD86D3, 0x3C8EA00A, 0x384FBDBD
};
uint32_t crc32m_nyb(uint32_t crc, const unsigned char *buf, size_t len)
{
while (len--) {
crc ^= (uint32_t)(*buf++) << 24;
crc = (crc << 4) ^ crc_table[crc >> 28];
crc = (crc << 4) ^ crc_table[crc >> 28];
}
return crc;
}
在这两种情况下，初始 CRC 必须是 0xffffffff。
好吧，在我提出问题后几个小时，我不记得名字的人 post 回答了我的问题，结果证明是正确的。不知何故，这个答案被完全删除了，我不知道为什么或是谁做的，但我要感谢这个人，如果你会看到这个，请再次 post 你的答案，我会删除这个。但对于其他用户，这是他对我有用的答案，再次感谢你，神秘的（不幸的是，我不能很好地复制他的笔记和建议，只能复制代码本身）：
编辑：最初的答案来自用户 samgak，所以在他 post 回答之前，它会一直保留在这里。
反向CRC算法：
uint32 revcrc32(uint16* data, uint32 len, uint32 crc)
{
uint32 i;
data += len - 1;
while(len--)
{
crc ^= *data--;
for(i = 0; i < 16; i++)
{
uint32 crc1 = ((crc ^ POLY) >> 1) | 0x80000000;
uint32 crc2 = crc >> 1;
if(((crc1 << 1) ^ (((crc1 ^ *data) & 0x80000000) ? POLY : 0)) == crc)
crc = crc1;
else if(((crc2 << 1) ^ (((crc2 ^ *data) & 0x80000000) ? POLY : 0)) == crc)
crc = crc2;
}
}
return crc;
}
查找补丁字节：
#define CRC_OF_ZERO 0xb7647d
void bruteforcecrc32(uint32 targetcrc)
{
// compute prefixes:
uint16 j;
for(j = 0; j <= 0xffff; j++)
{
uint32 crc = revcrc32(&j, 1, targetcrc);
if((crc >> 16) == (CRC_OF_ZERO >> 16))
{
printf("prefixes: %04lX %04lX\n", (crc ^ CRC_OF_ZERO) & 0xffff, (uint32)j);
return;
}
}
}
用法：
uint16 test[] = {0x0123, 0x4567, 0x89AB, 0xCDEF}; // prefix should be 0x0CD8236A
bruteforcecrc32(revcrc32(test, 4, 0L));
替代方法。假设xorout = 0，如果不是，则计算正常的crc后，再用crc ^= xorout将其去掉。这里的方法将普通的 crc 乘以 (1/2)%(crc polynomial) 提高到 (message size in bits) power % (crc polynomial) 等同于向后循环它。如果消息大小固定，则映射固定，时间复杂度为 O(1)。否则，它是 O(log(n)).
此示例代码使用 Visual Studio 和一个用于无进位乘法 (PCLMULQDQ) 的内在函数，它使用 XMM（128 位）寄存器。 Visual Studio 使用 __m128i 类型来表示整数 XMM 值。
#include <stdio.h>
#include <stdlib.h>
#include <intrin.h>
typedef unsigned char uint8_t;
typedef unsigned int uint32_t;
typedef unsigned long long uint64_t;
#define POLY (0x104c11db7ull)
#define POLYM ( 0x04c11db7u)
static uint32_t crctbl[256];
static __m128i poly; /* poly */
static __m128i invpoly; /* 2^64 / POLY */
void GenMPoly(void) /* generate __m128i poly info */
{
uint64_t N = 0x100000000ull;
uint64_t Q = 0;
for(size_t i = 0; i < 33; i++){
Q <<= 1;
if(N&0x100000000ull){
Q |= 1;
N ^= POLY;
}
N <<= 1;
}
poly.m128i_u64[0] = POLY;
invpoly.m128i_u64[0] = Q;
}
void GenTbl(void) /* generate crc table */
{
uint32_t crc;
uint32_t c;
uint32_t i;
for(c = 0; c < 0x100; c++){
crc = c<<24;
for(i = 0; i < 8; i++)
/* assumes twos complement */
crc = (crc<<1)^((0-(crc>>31))&POLYM);
crctbl[c] = crc;
}
}
uint32_t GenCrc(uint8_t * bfr, size_t size) /* generate crc */
{
uint32_t crc = 0xffffffffu;
while(size--)
crc = (crc<<8)^crctbl[(crc>>24)^*bfr++];
return(crc);
}
/* carryless multiply modulo poly */
uint32_t MpyModPoly(uint32_t a, uint32_t b) /* (a*b)%poly */
{
__m128i ma, mb, mp, mt;
ma.m128i_u64[0] = a;
mb.m128i_u64[0] = b;
mp = _mm_clmulepi64_si128(ma, mb, 0x00); /* p[0] = a*b */
mt = _mm_clmulepi64_si128(mp, invpoly, 0x00); /* t[1] = (p[0]*((2^64)/POLY))>>64 */
mt = _mm_clmulepi64_si128(mt, poly, 0x01); /* t[0] = t[1]*POLY */
return mp.m128i_u32[0] ^ mt.m128i_u32[0]; /* ret = p[0] ^ t[0] */
}
/* exponentiate by repeated squaring modulo poly */
uint32_t PowModPoly(uint32_t a, uint32_t b) /* pow(a,b)%poly */
{
uint32_t prd = 0x1u; /* current product */
uint32_t sqr = a; /* current square */
while(b){
if(b&1)
prd = MpyModPoly(prd, sqr);
sqr = MpyModPoly(sqr, sqr);
b >>= 1;
}
return prd;
}
int main()
{
uint32_t inv; /* 1/2 % poly, constant */
uint32_t fix; /* fix value, constant if msg size fixed */
uint32_t crc; /* crc at end of msg */
uint32_t pre; /* prefix for msg */
uint8_t msg[13] = {0x00,0x00,0x00,0x00,0x31,0x32,0x33,0x34,0x35,0x36,0x37,0x38,0x39};
GenMPoly(); /* generate __m128i polys */
GenTbl(); /* generate crc table */
inv = PowModPoly(2, 0xfffffffeu); /* inv = 2^(2^32-2) % Poly = 1/2 % poly */
fix = PowModPoly(inv, 8*sizeof(msg)); /* fix value */
crc = GenCrc(msg, sizeof(msg)); /* calculate normal crc */
pre = MpyModPoly(fix, crc); /* convert to prefix */
printf("crc = %08x pre = %08x ", crc, pre);
msg[0] = (uint8_t)(pre>>24); /* store prefix in msg */
msg[1] = (uint8_t)(pre>>16);
msg[2] = (uint8_t)(pre>> 8);
msg[3] = (uint8_t)(pre>> 0);
crc = GenCrc(msg, sizeof(msg)); /* check result */
if(crc == 0)
printf("passed\n");
else
printf("failed\n");
return 0;
}