PATCH: bitwise msb-first table-based 16bit CRC calculation

This is merely a historical archive of years 2008-2021, before the migration to mailman3.

A maintained and still updated list archive can be found at https://lists.osmocom.org/hyperkitty/list/tetra@lists.osmocom.org/.

Sylvain Munaut 246tnt at gmail.com
Sun Jan 23 22:28:55 UTC 2011


Hi,

> I would have no problem to put it into libosmocore,

As I said in IRC, I would put it as 'template' in libosmocore,
replacing the 16 with like @N@
Then in the make file, use a couple of sed to generate the .c / .h for
the 8,16,32,64 bits versions.

This way it could be used for GSM as wel where a wide variety of CRC
polynoms are used (from 4 bits up to 40 bits ...)


> just make sure it has a
> compile option to be compiled out (in case we need that for osmocomBB).

I think it should compile just fine for the target, nothing special
there and if we don't use it it won't be included.
It's mostly code than uses libc io stuff that's tricky.


> I have two nitpicks/questions though:
>        - Why not keep the generated tables around in the code? This avoids
>          the runtime init, if multiple processes use this table it will also
>          be shared between these, if it is not used at all it will not be
>          mapped.

Standard tables could indeed be included in the code by default for
well known CRC, but the ability
to compute/use tables dynamically should stay.

A small utility to generate the .c code for such tables should be added then.

So you could have stuff like:

crc_tbl_ccit.c: crc_tbl_gen
    crc_tbl_gen 0x????? > crc_tbl_ccit.c


Other comments:

 - name it crc16.c  (the function name osmo_xxx is fine, but for the
file name, none of the others have osmo_ prefix ... we're in osmocore)
 - Oh, I just noticed there is a crc16.c already ... that's just
confusing, need better naming than that.
 - If we indeed do a lot of crc (8/16/32/64) with some prebuilt table,
maybe a directory/separate lib ? (like the vty/codec stuff) just a
tought. That would also split the crc used for pbit/ubits from the
'traditional' crc16.
 - Unaligned bit start in pbits.
 - For the ubits case, the function makes it look like you need the
whole table ... when in fact you just need the poly.
   Maybe take the poly as argument and add a macro crc_tbl2poly that
takes the element[1] ? This way, if you only use ubits, you can just
have the poly without tables at all ...


Cheers,

    Sylvain




More information about the tetra mailing list