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

Question

Is there a well-known name for this CRC implementation? This code is in C, but this is the same CRC computation that's used for the tape filing system of the BBC micro, I think. But the BBC micro documentation doesn't specify the name of the CRC. I also wasn't able to find any obvious match in 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);
}

This checksum is also described on page 348 of the BBC Microcmputer Advanced User Guide but there also, it is not given a name. The code on that page is 6502 assembly:

      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

The polynomial is 0x10000 + (0x810<<1) + 1 = 0x11021, known as CRC16-CCITT.

However, based on what I recall from the 1980's and from the Wiki article, CRC16-CCITT is a name given to any CRC using polynomial 0x11021. In addition to the polynomial, the CRC may be left shifting (not reflected), right shifting (reflected), have an initial value, and the result may be complemented. The online calculators have corresponding check boxes: input reflected, output reflected, initial value, final xor value. (It is rare for the reflection of input and output not be the same).

The code implements a left shifting CRC, with initial value 0 and no final exclusive-or, assuming that there isn't another function like crc_update that doesn't take an input parameter and initializes the CRC to some specific value.

Mark Adler pointed out bugs in the code, like incrementing p twice in the loop. I also don't see the point of assert(crc & ~0xffff == 0) (isn't ~0xffff == 0x...0000?).

Answer 2

The C source code in the question is in error. The pointer to the data is inadvertently incremented twice, computing the CRC only on every other byte! This:

crc ^= *p++ << 8;

should be this:

crc ^= *p << 8;

The assembler code had a character rendered incorrectly in the manual, where EOR #&l0 should have been EOR #&10.

Once corrected, both codes compute CRC-16/XMODEM.

(The other answer here refers to "CRC16-CCITT" as a family of CRCs with that polynomial, but the CRC-16/CCITT in the reveng catalog does not produce the same output as the code in the question. While they use the same polynomial, CRC-16/CCITT is reflected, whereas the CRC in the code is not.)