crc mess

[iceman1001]

I was going to start fixing up the new FeliCa implementation to be nicer, when I stumbled into the crc mess. Once poking around, I realise there is multitude of different crc16 algo's everywhere on device.. there is table versions, there is looped byte versions,. all of which takes a lot of space. Not to mention the naive implementations of reflecting uint8, uint16.

The following implementations I have found and within [] is their equvialent entry in the catalogue of parametrised crc algorithms. (http://reveng.sourceforge.net/crc-catalogue/16.htm)

• ISO14443 CRC A [crc-a]
• ISO14443 CRC B [x-25]
• ISO15693 [x-25]
• ISO15693 iClass []
• FeliCA [xmodem]
• LEGIC

After looking at it and some thinking, we need speed (since used in reader/tag comms) and space. Normally we would have one crc to play with but since proxmark3 is able to use many protocols we also have to have many crc-implementations.

The bit-versions inside crc.c, is too slow. Neither can we have many table versions. Normally a LUT implementations uses u16[256] array, which is 512bytes. We have several of them. Thats waste of precious space. So what is possible?

solution The idea is to make a LUT implementation, since we only use one protocol at a time, we only need one LUT table to be filled with pre-calculated data. This will save space and we can recalculate the values when we swap to different protocol. Another slow part of current implementation was reflection of values. Ie (reversing the bit order) 0x0001 -> 0x8000 The new ones uses bitfiddling.

pros

• Unified way of looking at CRC-16, in sync with RevEng and the catalogue of parametrised crc algorithms.
• fast implementation of crc16 (table based)
• one table for all crc16
• faster reflection of values

cons yeah, what could be bad? Finding out the standard parameters for each algos. Currently missing LEGIC 16..

[iceman1001]

crc table version ready. Great performance compared with current implementations.

crc_a table ticks       646
crc_a current ticks     695
crc_a loop ticks        3055
iso15 crc current ticks 1559

table version is fastest. Current 14a uses also a byte based solution which is faster than bit-looped. loop crc_a is the naive implementation with bit looping, which is far slower. current iso15 doesn't take in consideration for refin/refout. Its better than the naive but still slower than table lookup.

The time cost is for generating the table, when switching, but its keeped static so when running same protocol commands there is no extra cost.

[iceman1001]

And there it is, I most likely broke somethings but the crc16 is now used in a unified way.

Do tell if something doesn't work because of this.