这是哪种 CRC 算法（BBC 微型磁带归档系统使用的算法）？

Question

这个 CRC 实现有一个众所周知的名字吗？此代码是用 C 语言编写的，但我认为这与 BBC micro 的磁带归档系统所使用的 CRC 计算相同。但是 BBC 微文档没有指定 CRC 的名称。我也无法在 http://reveng.sourceforge.net/crc-catalogue/16.htm or in 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

Answer 1

多项式为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 吗？）。

Answer 2

题中的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 却没有。）

这是哪种 CRC 算法（BBC 微型磁带归档系统使用的算法）？

Which CRC algorithm is this (used by BBC micro tape filing system)?

crc

crc16

bbc-micro