这个问题的旧标题: CRC16 组合实现与 CRC32 组合实现之间的区别
我正在尝试实现类似于 CRC32 组合实现的 CRC16 组合实现。我正在使用 CRC-CCITT(初始值:0xFFFF，Poly:0x1021)，如 here 所述。
我阅读并试图理解此 answer 中描述的 CRC32_Combine 实现，但我还没有完全理解它。我已经为 CRC16 组合做了一个 C# 实现，只是将 32x32 矩阵修改为 16x16，我不确定更多。我应该得到以下值，但我没有得到:
Msg1 : "123" CRC-16-CCITT : 0x5bce
Msg2 : "456789" CRC-16-CCITT : 0x6887
Combined Msg1 + Msg2 : "123456789" CRC-16-CCITT should be "0x29B1".
But what I got with my code below is "0x64d8".
ZLib 的 C# 代码:
const UInt16 poly16Reverse = 0x8408;
const Int16 GF2_DIM = 16;
private static UInt16 gf2_matrix_times(UInt16[] mat, UInt16 vec)
{
UInt16 sum = 0;
int matIndex = 0;
while (vec > 0)
{
if ((vec & 1) > 0)
{
sum ^= mat[matIndex];
}
vec >>= 1;
matIndex++;
}
return sum;
}
private static void gf2_matrix_square(UInt16[] square, UInt16[] mat)
{
for (int n = 0; n < GF2_DIM; n++)
{
square[n] = gf2_matrix_times(mat, mat[n]);
}
}
public static UInt16 crc16_combine(UInt16 crc1, UInt16 crc2, UInt16 lenOfCrc2)
{
UInt16[] even = new UInt16[GF2_DIM];
UInt16[] odd = new UInt16[GF2_DIM];
if (lenOfCrc2 <= 0)
{
return crc1;
}
// put operator for one zero bit in odd
odd[0] = poly16Reverse;
UInt16 row = 1;
for (int i = 1; i < GF2_DIM; i++)
{
odd[i] = row;
row <<= 1;
}
// put operator for two zero bits in even
gf2_matrix_square(even, odd);
// put operator for four zero bits in odd
gf2_matrix_square(odd, even);
// apply len2 zeros to crc1 (first square will put the operator for one
// zero byte, eight zero bits, in even)
do
{
// apply zeros operator for this bit of lenOfCrc2
gf2_matrix_square(even, odd);
if ((lenOfCrc2 & 1) > 0)
{
crc1 = gf2_matrix_times(even, crc1);
}
lenOfCrc2 >>= 1;
// if no more bits set, then done
if (lenOfCrc2 == 0)
{
break;
}
// another iteration of the loop with odd and even swapped
gf2_matrix_square(odd, even);
if ((lenOfCrc2 & 1) > 0)
{
crc1 = gf2_matrix_times(odd, crc1);
}
lenOfCrc2 >>= 1;
// if no more bits set then done
} while (lenOfCrc2 != 0);
// return combined CRC
crc1 ^= crc2;
return crc1;
}
任何人以前有任何 CRC16 组合的实现，都会有很大的帮助!
最佳答案
结果 0x29b1 是针对“假”CCITT CRC-16 的。该 CRC 使用未反射(reflect)的多项式，因此您可以改用 0x1021。见 this list of CRC definitions 。您还需要更改零运算符的初始化，并考虑 CRC 的初始化。
下面是概括各种 CRC 组合的代码(C 语言):
/* crccomb.c -- generalized combination of CRCs
* Copyright (C) 2015 Mark Adler
* Version 1.1 29 Apr 2015 Mark Adler
*/
/*
This software is provided 'as-is', without any express or implied
warranty. In no event will the author be held liable for any damages
arising from the use of this software.
Permission is granted to anyone to use this software for any purpose,
including commercial applications, and to alter it and redistribute it
freely, subject to the following restrictions:
1. The origin of this software must not be misrepresented; you must not
claim that you wrote the original software. If you use this software
in a product, an acknowledgment in the product documentation would be
appreciated but is not required.
2. Altered source versions must be plainly marked as such, and must not be
misrepresented as being the original software.
3. This notice may not be removed or altered from any source distribution.
Mark Adler
madler@alumni.caltech.edu
*/
/*
zlib provides a fast operation to combine the CRCs of two sequences of bytes
into a single CRC, which is the CRC of the two sequences concatenated. That
operation requires only the two CRC's and the length of the second sequence.
The routine in zlib only works on the particular CRC-32 used by zlib. The
code provided here generalizes that operation to apply to a wide range of
CRCs. The CRC is specified in a series of #defines, based on the
parameterization found in Ross William's excellent CRC tutorial here:
http://www.ross.net/crc/download/crc_v3.txt
A comprehensive catalogue of known CRCs, their parameters, check values, and
references can be found here:
http://reveng.sourceforge.net/crc-catalogue/all.htm
*/
#include <stddef.h>
#include <stdint.h>
#define local static
/*
CRC definition: WIDTH is the degree of the CRC polynomial, and so is the
number of bits in the CRC. crc_t is an unsigned integer type of at least
WIDTH bits. FMT is used to printf() a CRC value. #define REFLECT if the
CRC is reflected (i.e. both refin and refout are true). Otherwise the CRC
is considered to be normally ordered (refin and refout are both false).
POLY is the CRC polynomial, bit-reversed if REFLECT is #defined. INIT is
the initial register value. The final register value is exclusive-ored with
XOROUT. CHECK is the CRC of the nine bytes "123456789" (in ASCII).
crc_general_combine() supports CRCs for which refin and refout are the same.
That is the case for the vast majority of CRCs. There is only one CRC in
the catalogue linked above for which that is not the case (CRC-12/3GPP).
*/
/* Examples of a few CRCs are shown here for illustration and testing. To
compile this code, activate one of the definitions below with a #define. */
#define CRC16FALSE
/* CRC-6 CDMA2000-A */
#ifdef CRC6CDMA
# define WIDTH 6
typedef unsigned crc_t;
# define FMT "0x%02x"
# define POLY 0x27
# define INIT 0x3f
# define XOROUT 0
# define CHECK 0x0d
#endif
/* CRC-8 ITU */
#ifdef CRC8ITU
# define WIDTH 8
typedef unsigned crc_t;
# define FMT "0x%02x"
# define POLY 7
# define INIT 0
# define XOROUT 0x55
# define CHECK 0xa1
#endif
/* CRC-16 CCITT-False */
#ifdef CRC16FALSE
# define WIDTH 16
typedef unsigned crc_t;
# define FMT "0x%04x"
# define POLY 0x1021
# define INIT 0xffff
# define XOROUT 0
# define CHECK 0x29b1
#endif
/* CRC-16 CCITT (also known as KERMIT) */
#ifdef CRC16TRUE
# define WIDTH 16
typedef unsigned crc_t;
# define FMT "0x%04x"
# define POLY 0x8408
# define INIT 0
# define REFLECT
# define XOROUT 0
# define CHECK 0x2189
#endif
/* CRC-32 (standard CRC used by zip, gzip, others) */
#ifdef CRC32
# define WIDTH 32
typedef unsigned long crc_t;
# define FMT "0x%08lx"
# define POLY 0xedb88320
# define INIT 0xffffffff
# define REFLECT
# define XOROUT 0xffffffff
# define CHECK 0xcbf43926
#endif
/* CRC-64 XZ (used by the xz compression utility) */
#ifdef CRC64XZ
# define WIDTH 64
typedef unsigned long long crc_t;
# define FMT "0x%016llx"
# define POLY 0xc96c5795d7870f42
# define INIT 0xffffffffffffffff
# define REFLECT
# define XOROUT 0xffffffffffffffff
# define CHECK 0x995dc9bbdf1939fa
#endif
/* Multiply the GF(2) vector vec by the GF(2) matrix mat, returning the
resulting vector. The vector is stored as bits in a crc_t. The matrix is
similarly stored with each column as a crc_t, where the number of columns is
at least enough to cover the position of the most significant 1 bit in the
vector (so a dimension parameter is not needed). */
local inline crc_t gf2_matrix_times(const crc_t *mat, crc_t vec)
{
crc_t sum;
sum = 0;
while (vec) {
if (vec & 1)
sum ^= *mat;
vec >>= 1;
mat++;
}
return sum;
}
/* Multiply the matrix mat by itself, returning the result in square. WIDTH is
the dimension of the matrices, i.e., the number of bits in each crc_t
(rows), and the number of crc_t's (columns). */
local void gf2_matrix_square(crc_t *square, const crc_t *mat)
{
int n;
for (n = 0; n < WIDTH; n++)
square[n] = gf2_matrix_times(mat, mat[n]);
}
/* Combine the CRCs of two successive sequences, where crc1 is the CRC of the
first sequence of bytes, crc2 is the CRC of the immediately following
sequence of bytes, and len2 is the length of the second sequence. The CRC
of the combined sequence is returned. */
local crc_t crc_general_combine(crc_t crc1, crc_t crc2, uintmax_t len2)
{
int n;
crc_t col;
crc_t even[WIDTH]; /* even-power-of-two zeros operator */
crc_t odd[WIDTH]; /* odd-power-of-two zeros operator */
/* degenerate case (also disallow negative lengths if type changed) */
if (len2 <= 0)
return crc1;
/* exclusive-or the result with len2 zeros applied to the CRC of an empty
sequence */
crc1 ^= INIT ^ XOROUT;
/* construct the operator for one zero bit and put in odd[] */
#ifdef REFLECT
odd[0] = POLY; /* polynomial */
col = 1;
for (n = 1; n < WIDTH; n++) {
odd[n] = col;
col <<= 1;
}
#else
col = 2;
for (n = 0; n < WIDTH - 1; n++) {
odd[n] = col;
col <<= 1;
}
odd[n] = POLY; /* polynomial */
#endif
/* put operator for two zero bits in even[] */
gf2_matrix_square(even, odd);
/* put operator for four zero bits in odd[] */
gf2_matrix_square(odd, even);
/* apply len2 zeros to crc1 (first square will put the operator for eight
zero bits == one zero byte, in even[]) */
do {
/* apply zeros operator for this bit of len2 */
gf2_matrix_square(even, odd);
if (len2 & 1)
crc1 = gf2_matrix_times(even, crc1);
len2 >>= 1;
/* if no more bits set, then done */
if (len2 == 0)
break;
/* another iteration of the loop with odd[] and even[] swapped */
gf2_matrix_square(odd, even);
if (len2 & 1)
crc1 = gf2_matrix_times(odd, crc1);
len2 >>= 1;
/* if no more bits set, then done */
} while (len2 != 0);
/* return combined crc */
crc1 ^= crc2;
return crc1;
}
#ifdef TEST
/* Test crc_general_combine() for the defined CRC. The last two CRC values
printed should be equal. */
/* Update a general, parameterized CRC. (See the parameter definitions above.)
crc_general() updates crc with the sequence buf[0..len-1], and returns the
updated crc. If buf is NULL, crc_general() returns the initial value to use
for crc. A CRC calculation of a long sequence can be broken into pieces:
crc = crc_general(0, NULL, 0); // initial value
crc = crc_general(crc, buf_1, len_1);
...
crc = crc_general(crc, buf_n, len_n);
The final value of crc is then the CRC of the sequence buf_1, ..., buf_n.
crc_general() is a simple, bit-wise implementation for testing purposes. A
CRC routine for production use would instead use table-driven approaches to
compute the CRC using byte-wise or word-wise algorithms, for speed. */
crc_t crc_general(crc_t crc, unsigned char *buf, size_t len)
{
int k;
if (buf == NULL)
return INIT ^ XOROUT;
crc ^= XOROUT;
#ifdef REFLECT
while (len--) {
crc ^= *buf++;
for (k = 0; k < 8; k++)
crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
}
#elif WIDTH >= 8
# define TOP ((crc_t)1 << (WIDTH - 1))
# define MASK ((TOP << 1) - 1)
while (len--) {
crc ^= *buf++ << (WIDTH - 8);
for (k = 0; k < 8; k++)
crc = crc & TOP ? (crc << 1) ^ POLY : crc << 1;
}
crc &= MASK;
#else
# define POLY8 (POLY << (8 - WIDTH))
crc <<= 8 - WIDTH;
while (len--) {
crc ^= *buf++;
for (k = 0; k < 8; k++)
crc = crc & 0x80 ? (crc << 1) ^ POLY8 : crc << 1;
}
crc &= 0xff;
crc >>= 8 - WIDTH;
#endif
return crc ^ XOROUT;
}
#include <stdio.h>
int main(void)
{
crc_t init, crc1, crc2, crc3, crc4;
init = crc_general(0, NULL, 0);
crc1 = crc_general(init, (unsigned char *)"123", 3);
crc2 = crc_general(init, (unsigned char *)"456789", 6);
crc3 = crc_general(init, (unsigned char *)"123456789", 9);
crc4 = crc_general_combine(crc1, crc2, 6);
printf(FMT ", " FMT ", " FMT ", " FMT ", " FMT "\n",
crc1, crc2, crc3, crc4, (crc_t)CHECK);
if (crc3 != (crc_t)CHECK || crc4 != crc3)
puts("mismatch!");
return 0;
}
#endif
几年后更新...
crcany 将为任何给定的 CRC 定义生成 CRC 代码和 CRC 组合代码。
关于c# - 通用 CRC (8/16/32/64) 组合实现，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29915764/