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
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?).