2

这个 CRC 实现有一个众所周知的名字吗？这段代码是用 C 语言编写的，但我认为这与用于 BBC micro 的磁带归档系统的 CRC 计算相同。但是 BBC 微文档没有指定 CRC 的名称。我也无法在http://reveng.sourceforge.net/crc-catalogue/16.htm或https://en.wikipedia.org/wiki/Cyclic_redundancy_check中找到任何明显的匹配项

inline unsigned long crc_cycle(unsigned long crc)
{
  if (crc & 32768)
    return  (((crc ^ 0x0810) & 32767) << 1) + 1;
  else
    return crc << 1;
}

unsigned long crc_update(unsigned long crc, const byte *start, const byte *end)
{
    for (const byte* p = start; p < end; ++p)
    {
        crc ^= *p++ << 8;
        for(int k = 0; k < 8; k++)
          crc = crc_cycle(crc);
        assert((crc & ~0xFFFF) == 0);
    }
    return crc;
}

unsigned long crc(const byte *start, const byte* end)
{
  return crc_update(0, start, end);
}

BBC Microcmputer Advanced User Guide的第 348 页也描述了此校验和，但也没有给出名称。该页面上的代码是 6502 程序集：

      LDA #0
      STA H \ Initialise the CRC to zero
      STA L
      TAY \ Initialise the data pointer
.nbyt LDA H \ Work data into CRC
      EOR data,Y
      STA H
      LDX #8 \ Perform polynomial recycling
.loop LDA H \ Loop is performed 8 times, once for bit
      ROL A Test if a bit is being cycled out
      BCC b7z
      LDA H \ Yes, add it back in *~8~5
      EOR #8
      STA H
      LDA L
      EOR #&l0
      STA L
.b7z  ROL L \ Always, rotate whole CRC left one bit
      ROL H
      DEX
      BNE loop \Do once for each bit
      INY \Point to next data byte
      CPY #lblk \All done yet?
      BNE nbyt
      RTS \All done- H=CRC Hi, L=CRC
4

2 回答 2

3

多项式为0x10000 + (0x810<<1) + 1 = 0x11021，称为CRC16-CCITT。

但是，根据我从 1980 年代和 Wiki 文章中回忆的内容，CRC16-CCITT 是使用多项式 0x11021 赋予任何 CRC 的名称。除了多项式之外，CRC可能是左移（不反映），右移（反映），具有初始值，并且结果可以被补码。在线计算器有相应的复选框：输入反射、输出反射、初始值、最终异或值。（很少有输入输出反映不一样的情况）。

该代码实现了一个左移 CRC，初始值为 0，没有最终的异或，假设没有像 crc_update 这样不接受输入参数并将 CRC 初始化为某个特定值的函数。

Mark Adler 指出了代码中的错误，例如在循环中将 p 递增两次。我也没有看到 assert(crc & ~0xffff == 0) 的意义（不是 ~0xffff == 0x...0000？）。

于 2020-07-16T07:09:12.840 回答
1

问题中的 C 源代码有误。指向数据的指针无意中增加了两次，仅在每隔一个字节上计算 CRC！这：

crc ^= *p++ << 8;

应该是这样的：

crc ^= *p << 8;

汇编代码有一个字符在手册中呈现不正确，EOR #&l0应该是EOR #&10.

一旦更正，两个代码都会计算CRC-16/XMODEM。

（此处的另一个答案将“CRC16-CCITT”称为具有该多项式的 CRC 族，但 reveng 目录中的 CRC-16/CCITT 不会产生与问题中的代码相同的输出。虽然他们使用相同多项式，CRC-16/CCITT被反映，而代码中的 CRC 没有。）

于 2020-07-16T20:32:59.657 回答