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

Christian Vogel vogelchr at vogel.cx
Sun Jan 23 20:03:06 UTC 2011


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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-Table-based-msb-first-crc16-functions.patch
Type: application/octet-stream
Size: 5381 bytes
Desc: not available
URL: <http://lists.osmocom.org/pipermail/tetra/attachments/20110123/a41987cc/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0002-Test-for-osmo_crc16-routines-based-on-Harald-s-crc_t.patch
Type: application/octet-stream
Size: 4473 bytes
Desc: not available
URL: <http://lists.osmocom.org/pipermail/tetra/attachments/20110123/a41987cc/attachment-0001.obj>


More information about the tetra mailing list