CRC16 table Vs polynomial

Question

I've got 2 crc calculators that I think should produce the same checksum. The lookup calculator

table=[0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50A5, 0x60C6, 0x70E7, 0x8108, 0x9129, 0xA14A, 0xB16B, 0xC18C, 0xD1AD, 0xE1CE, 0xF1EF,
       0x1231, 0x0210, 0x3273, 0x2252, 0x52B5, 0x4294, 0x72F7, 0x62D6, 0x9339, 0x8318, 0xB37B, 0xA35A, 0xD3BD, 0xC39C, 0xF3FF, 0xE3DE,
       0x2462, 0x3443, 0x0420, 0x1401, 0x64E6, 0x74C7, 0x44A4, 0x5485, 0xA56A, 0xB54B, 0x8528, 0x9509, 0xE5EE, 0xF5CF, 0xC5AC, 0xD58D,
       0x3653, 0x2672, 0x1611, 0x0630, 0x76D7, 0x66F6, 0x5695, 0x46B4, 0xB75B, 0xA77A, 0x9719, 0x8738, 0xF7DF, 0xE7FE, 0xD79D, 0xC7BC,
       0x48C4, 0x58E5, 0x6886, 0x78A7, 0x0840, 0x1861, 0x2802, 0x3823, 0xC9CC, 0xD9ED, 0xE98E, 0xF9AF, 0x8948, 0x9969, 0xA90A, 0xB92B,
       0x5AF5, 0x4AD4, 0x7AB7, 0x6A96, 0x1A71, 0x0A50, 0x3A33, 0x2A12, 0xDBFD, 0xCBDC, 0xFBBF, 0xEB9E, 0x9B79, 0x8B58, 0xBB3B, 0xAB1A,
       0x6CA6, 0x7C87, 0x4CE4, 0x5CC5, 0x2C22, 0x3C03, 0x0C60, 0x1C41, 0xEDAE, 0xFD8F, 0xCDEC, 0xDDCD, 0xAD2A, 0xBD0B, 0x8D68, 0x9D49,
       0x7E97, 0x6EB6, 0x5ED5, 0x4EF4, 0x3E13, 0x2E32, 0x1E51, 0x0E70, 0xFF9F, 0xEFBE, 0xDFDD, 0xCFFC, 0xBF1B, 0xAF3A, 0x9F59, 0x8F78,
       0x9188, 0x81A9, 0xB1CA, 0xA1EB, 0xD10C, 0xC12D, 0xF14E, 0xE16F, 0x1080, 0x00A1, 0x30C2, 0x20E3, 0x5004, 0x4025, 0x7046, 0x6067,
       0x83B9, 0x9398, 0xA3FB, 0xB3DA, 0xC33D, 0xD31C, 0xE37F, 0xF35E, 0x02B1, 0x1290, 0x22F3, 0x32D2, 0x4235, 0x5214, 0x6277, 0x7256,
       0xB5EA, 0xA5CB, 0x95A8, 0x8589, 0xF56E, 0xE54F, 0xD52C, 0xC50D, 0x34E2, 0x24C3, 0x14A0, 0x0481, 0x7466, 0x6447, 0x5424, 0x4405,
       0xA7DB, 0xB7FA, 0x8799, 0x97B8, 0xE75F, 0xF77E, 0xC71D, 0xD73C, 0x26D3, 0x36F2, 0x0691, 0x16B0, 0x6657, 0x7676, 0x4615, 0x5634,
       0xD94C, 0xC96D, 0xF90E, 0xE92F, 0x99C8, 0x89E9, 0xB98A, 0xA9AB, 0x5844, 0x4865, 0x7806, 0x6827, 0x18C0, 0x08E1, 0x3882, 0x28A3,
       0xCB7D, 0xDB5C, 0xEB3F, 0xFB1E, 0x8BF9, 0x9BD8, 0xABBB, 0xBB9A, 0x4A75, 0x5A54, 0x6A37, 0x7A16, 0x0AF1, 0x1AD0, 0x2AB3, 0x3A92,
       0xFD2E, 0xED0F, 0xDD6C, 0xCD4D, 0xBDAA, 0xAD8B, 0x9DE8, 0x8DC9, 0x7C26, 0x6C07, 0x5C64, 0x4C45, 0x3CA2, 0x2C83, 0x1CE0, 0x0CC1,
       0xEF1F, 0xFF3E, 0xCF5D, 0xDF7C, 0xAF9B, 0xBFBA, 0x8FD9, 0x9FF8, 0x6E17, 0x7E36, 0x4E55, 0x5E74, 0x2E93, 0x3EB2, 0x0ED1, 0x1EF0]
crc=0xFFFF
for byte in b'123456789': crc=(crc<<8)^table[(crc>>8)^byte]; crc &= 0xFFFF
print('%.04X'%crc)

prints 29B1 whereas the poly calculator

PRESET = 0xffff; POLYNOMIAL = 0x8408 # bit reverse of 0x1021
crc = PRESET
for c in b'123456789':
  crc = crc ^ c
  for j in range(8):
    if crc & 0x01: crc = (crc >> 1) ^ POLYNOMIAL
    else: crc = crc >> 1
print('%.04X'%crc)

prints 6F91. I don't understand why they are different?

Answer 1

The traditional non-table driven computation of this CRC species (CRC-16/CCITT-FALSE) is along the lines of:

PRESET = 0xFFFF; POLYNOMIAL = 0x1021 
crc = PRESET
for c in b'123456789':
  crc = crc ^ (c << 8)
  for j in range(8):
    if crc & 0x8000: crc = (crc << 1) ^ POLYNOMIAL
    else: crc = crc << 1
crc = crc & 0xFFFF
print('%.04X'%crc)  # outputs 0x29B1 as expected

So, it xors each byte with the upper byte of the crc and processes the bits high end to low end (well, middle end).

Your method, on the other hand, xors each byte with the lower byte of the crc and processes the bits low end to middle end. That isn't equivalent – but, interestingly, if you feed it the input with each byte bit-reversed, then the resulting CRC will be bit-reversed. Kind of a mirror-image CRC, we could call it ... um, "CRC" I guess:

mirror_input = bytes([(int(bin(ord(b))[2:].zfill(8)[::-1], 2)) for b in "123456789"])
# b'\x8cL\xcc,\xacl\xec\x1c\x9c'

mirror_crc = kris_mclean_crc(mirror_input)
# 0x8D94 == 0b1000110110010100
# 0x29B1 == 0b0010100110110001

So, no slightly neater implementation today I'm afraid.