有谁有 C++ 中的 CRC128 和 CRC256 代码吗？和C#？

Question

我正在学习，试图了解 CRC 背后的想法。我在任何地方都找不到 CRC128 和 CRC256 代码。如果你们中有人有 C++ 或 C# 代码，请与我分享。还提供网站的在线链接。我是一个新手，根本不会自己编码，也不能将理论和数学转化为编码。所以我请求你的帮助。如果您为我提供正确且简单的代码，那就太好了。如果有人向我提供这些代码，请同时提供 CRC 表生成器函数。谢谢。

Answer 1

尽管定义了 CRC-128 和 CRC-256，但我不知道有谁真正使用它们。

大多数时候，认为自己需要 CRC 的开发人员实际上应该使用加密哈希函数 ，它已经在许多应用中成功地实现了 CRC。在极少数情况下，CRC-128 或 CRC-256 甚至比损坏的 MD5 更优越，更不用说 SHA-2 系列了。

Answer 2

我同意你的观点，只是对于 32 位和 64 位 CRC，意外冲突率分别高于 2^32 分之一或 2^64 分之一。

我编写了一个应用程序，通过 CRC 值来跟踪事物，以跟踪项目。我们需要跟踪潜在的数百万个项目，我们从 CRC32 开始，在现实世界的实践中，其冲突率约为 2^16 中的 1，这是一个令人不快的意外。然后我们重新编码以使用 CRC64，其实际冲突率约为 2^23 中的 1。我们在对 32 位版本感到不愉快之后对此进行了测试，并接受了 64 位版本的较小错误率。

我无法真正解释预期冲突率背后的统计数据，但有道理的是，您会比位宽度更快地经历碰撞。就像哈希表一样...一些哈希桶是空的，而另一些哈希桶有多个条目...

即使对于 256 位 CRC，前 2 个 CRC 也可能是相同的...这几乎令人难以置信，但却是可能的。

Answer 3

这是我最近编写的一个用于处理 CRC 的 Java 类。请注意，更改位顺序仅适用于按位计算。

/**
 * A CRC algorithm for computing check values.
 */
public class Crc
{
public static final Crc CRC_16_CCITT =
    new Crc(16, 0x1021, 0xffff, 0xffff, true);
public static final Crc CRC_32 =
    new Crc(32, 0x04c11db7, 0xffffffffL, 0xffffffffL, true);


private final int _width;
private final long _polynomial;
private final long _mask;
private final long _highBitMask;
private final long _preset;
private final long _postComplementMask;
private final boolean _msbFirstBitOrder;
private final int _shift;

private final long[] _crcs;



/**
 * Constructs a CRC specification.
 *
 * @param width
 * @param polynomial
 * @param msbFirstBitOrder
 */
public Crc(
    int width,
    long polynomial)
{
    this(width, polynomial, 0, 0, true);
}


/**
 * Constructs a CRC specification.
 *
 * @param width
 * @param polynomial
 * @param msbFirstBitOrder
 */
public Crc(
    int width,
    long polynomial,
    long preset,
    long postComplementMask,
    boolean msbFirstBitOrder)
{
    super();
    _width = width;
    _polynomial = polynomial;
    _mask = (1L << width) - 1;
    _highBitMask = (1L << (width - 1));
    _preset = preset;
    _postComplementMask = postComplementMask;
    _msbFirstBitOrder = msbFirstBitOrder;
    _shift = _width - 8;

    _crcs = new long[256];
    for (int i = 0; i < 256; i++)
    {
        _crcs[i] = crcForByte(i);
    }
}


/**
 * Gets the width.
 *
 * @return  The width.
 */
public int getWidth()
{
    return _width;
}


/**
 * Gets the polynomial.
 *
 * @return  The polynomial.
 */
public long getPolynomial()
{
    return _polynomial;
}


/**
 * Gets the mask.
 *
 * @return  The mask.
 */
public long getMask()
{
    return _mask;
}


/**
 * Gets the preset.
 *
 * @return  The preset.
 */
public long getPreset()
{
    return _preset;
}


/**
 * Gets the post-complement mask.
 *
 * @return  The post-complement mask.
 */
public long getPostComplementMask()
{
    return _postComplementMask;
}


/**
 * @return  True if this CRC uses MSB first bit order.
 */
public boolean isMsbFirstBitOrder()
{
    return _msbFirstBitOrder;
}


public long computeBitwise(byte[] message)
{
    long result = _preset;

    for (int i = 0; i < message.length; i++)
    {
        for (int j = 0; j < 8; j++)
        {
            final int bitIndex = _msbFirstBitOrder ? 7 - j : j;
            final boolean messageBit = (message[i] & (1 << bitIndex)) != 0;
            final boolean crcBit = (result & _highBitMask) != 0;

            result <<= 1;
            if (messageBit ^ crcBit)
            {
                result ^= _polynomial;
            }
            result &= _mask;
        }
    }

    return result ^ _postComplementMask;
}


public long compute(byte[] message)
{
    long result = _preset;

    for (int i = 0; i < message.length; i++)
    {
        final int b = (int) (message[i] ^ (result >>> _shift)) & 0xff;

        result = ((result << 8) ^ _crcs[b]) & _mask;
    }
    return result ^ _postComplementMask;
}


private long crcForByte(int b)
{
    long result1 = (b & 0xff) << _shift;
    for (int j = 0; j < 8; j++)
    {
        final boolean crcBit = (result1 & (1L << (_width - 1))) != 0;

        result1 <<= 1;
        if (crcBit)
        {
            result1 ^= _polynomial;
        }
        result1 &= _mask;
    }
    return result1;
}


public String crcTable()
{
    final int digits = (_width + 3) / 4;
    final int itemsPerLine = (digits + 4) * 8 < 72 ? 8 : 4;

    final String format = "0x%0" + digits + "x, ";

    final StringBuilder builder = new StringBuilder();
    builder.append("{\n");
    for (int i = 0; i < _crcs.length; i += itemsPerLine)
    {
        builder.append("    ");
        for (int j = i; j < i + itemsPerLine; j++)
        {
            builder.append(String.format(format, _crcs[j]));
        }
        builder.append("\n");
    }
    builder.append("}\n");
    return builder.toString();
}
}

Answer 4

仅当以下三点为真时，CRC-128 和 CRC-256 才有意义：

1. 您的 CPU 受限于加密哈希会显着降低速度的程度
2. 统计上绝不能发生意外冲突，2^64 中的 1 仍然太高
3. OTOH 故意冲突不是问题

2 和 3 可以同时成立的典型情况是，如果意外冲突会造成数据丢失，则只会影响数据发送者，而不影响平台。