2

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
James Youngman
  • 3,623
  • 2
  • 19
  • 21

2 Answers2

3

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

Mark Adler
  • 101,978
  • 13
  • 118
  • 158
rcgldr
  • 27,407
  • 3
  • 36
  • 61
  • Yes on the polynomial, no on the CRC. – Mark Adler Jul 17 '20 at 05:27
  • @MarkAdler - scroll down to about the middle of the [wiki article](https://en.wikipedia.org/wiki/Cyclic_redundancy_check#Polynomial_representations_of_cyclic_redundancy_checks) for CRC16-CCITT.== 0x1021 – rcgldr Jul 17 '20 at 06:40
  • The question is specifically asking for what entry in the reveng catalog matches the output of the provided code. It is _not_ the one called CRC-16/CCITT in that catalog. – Mark Adler Jul 17 '20 at 15:41
  • The code above returns `0x31c3` on the sequence of nine bytes "123456789". CRC-16/CCITT instead gives `0x2189`. – Mark Adler Jul 17 '20 at 15:47
  • The code in the question does in fact show an initial value of zero: `return crc_update(0, start, end);`. – Mark Adler Jul 17 '20 at 16:51
  • Non-reflected CRC implementations usually permit extraneous one bits to be shifted up into a register that is larger than the CRC. Then an `&` operation is done at the end to clear those out. That `assert()` verifies that this implementation doesn't need that, checking that there no extraneous high one bits. The C implementation in the question has a `& 32767` operation specifically to clear out the high bit when it is 1, before it could get shifted into the bits above the CRC length. – Mark Adler Jul 17 '20 at 23:36
  • That and the `assert` are both a waste of time (in inner loops!), since you could instead just do an `& 0xffff` on the result once, right before returning it. – Mark Adler Jul 17 '20 at 23:36
1

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

Mark Adler
  • 101,978
  • 13
  • 118
  • 158
  • CRC16-XMODEM is one of many CRCs of the CRC class CRC16-CCITT (essentially a reference to the polynomial, regardless if it's reflected or not, initial value, or final xor), as mentioned in the [wiki article](https://en.wikipedia.org/wiki/Cyclic_redundancy_check#Polynomial_representations_of_cyclic_redundancy_checks) . A reference for a non-reflected implementation of [CRC CCITT](http://srecord.sourceforge.net/crc16-ccitt.html). – rcgldr Jul 17 '20 at 06:54
  • If you would like to unilaterally declare that "CRC-16/CCITT" refers to _all_ CRCs with that polynomial, then fine.Then that term is rendered both useless and misleading, since it is no longer a specific CRC. It then cannot be a sufficient answer to a question asking "what CRC does this code implement?" – Mark Adler Jul 17 '20 at 15:46
  • I'm going by the wiki article. I seem to recall back in the 1980's (related to my job back then) some CRC standards (printed copies from one of the related companies back then) that gave names to all of the polynomials that would correspond to the names used in the Wiki article, but I haven't found a web site based reference for this. Some of the articles describing CRC's by name are in conflict (as in that non-reflected CRC_CCITT link in my prior comments, so I tend to go with wiki on this stuff. I've updated my answer. – rcgldr Jul 17 '20 at 17:01
  • As noted in the Wikipedia article: "The table below lists only the polynomials of the various algorithms in use." The [reveng catalog](http://reveng.sourceforge.net/crc-catalogue/all.htm) is the only decent reference, fully sourced, of _complete_ CRC definitions that I have found. – Mark Adler Jul 18 '20 at 04:12
  • I think the wiki article is making a distinction between CRC-16-CCITT (the polynomial) versus CRC-CCITT (a specific implementation). Back in the 1980's, it was Western Digital that was publishing hard copy specs in my area at that time. It was a pretty impressive setup that could print out the pages and covers, and could glue bind, comb bind, 3 hole punch bind, ... . I seem to recall IBM-3740 (IBM floppy disk) as a specific implementation of CRC-16-CCITT. The company I worked for made backup tape drives that used a PC floppy disk controller as the interface, which used IBM-3740 CRC. – rcgldr Jul 18 '20 at 14:04