PATCH: bitwise msb-first table-based 16bit CRC calculation
Hi, after a remark by Harald about bitwise CRC calculation and seeing the crc_simple code in lower_mac, I've thought about how to implement "optimized" routines using a table-based approach operating on our pbit_t/ubit_t arrays in libosmocore/master. People on IRC consider it more tetra-specific though, so I'm posting this here for advice on where to put it. The usage is to first create the table via osmo_crc16_table_init(*table,polynomial) and then to encode bits using osmo_crc16() - default, operates on pbit_t[] osmo_crc16_ubits() - operate on ubit_t[] osmo_crc16_ubit() - one single bit, takes polynomial as first arg! osmo_crc16_pbit() - operate on 1-7 bits in a pbit_t It passes the crc_test ported to the new routines. $ ./crc_test # osmo-tetra The CRC is now: 4129/0x1021 The CRC is now: 4129/0x1021 The CRC is now: 61905/0xf1d1 The CRC is now: 65534/0xfffe The CRC is now: 57073/0xdef1 The CRC is now: 7439/0x1d0f Decoded successfully. $ tests/crc/crc_test # this patch, in libosmocore First elements of table for CRC with poly 0x1021: 0000 1021 2042 3063 4084 50a5 60c6 70e7 8108 9129 a14a b16b c18c d1ad e1ce f1ef The CRC is now: 4129/0x1021 The CRC is now: 4129/0x1021 The CRC is now: 61905/0xf1d1 The CRC is now: 65534/0xfffe packed bits: 10 b0 be 00 83 07 d3 3d ef 10 The CRC is now: 57073/0xdef1 ...packed: 57073/0xdef1 packed bits: 10 b0 be 00 83 07 d3 3d ef 10 The CRC is now: 7439/0x1d0f Decoded successfully. Chris
On 01/23/2011 09:03 PM, Christian Vogel wrote:
Hi,
after a remark by Harald about bitwise CRC calculation and seeing the crc_simple code in lower_mac, I've thought about how to implement "optimized" routines using a table-based approach operating on our pbit_t/ubit_t arrays in libosmocore/master.
People on IRC consider it more tetra-specific though, so I'm posting this here for advice on where to put it.
Hi Christian, I would have no problem to put it into libosmocore, just make sure it has a compile option to be compiled out (in case we need that for osmocomBB). 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. - The coding style would also need update. regards holger
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
participants (3)
-
Christian Vogel -
Holger Hans Peter Freyther -
Sylvain Munaut