CRC16 in rt2x00
Subsystems (2)
Hi,
I have a small question about the CRC16 usage in rt2x00 and what the netdev preferred method is for this.
At the moment the rt2x00 drivers in wireless-dev use its own CRC16 table and calculation inside the driver. There already is a CRC16 library in the kernel which uses the 0x8005 table, while rt2x00 uses the 0x1021 polynomial table.
Is keeping this version of CRC16 inside rt2x00 the most sensible thing to do? Or should it be moved to the lib folder of the kernel so other drivers could make use of it as well? (So far I have not found a driver which makes use
of the same CRC16 table)
Thanks.
Ivo
Quoted 9 lines · On Sat, 27 May 2006 13:27:15 +0200 Ivo van Doorn wrote:
I have a small question about the CRC16 usage in rt2x00 and what the netdev preferred method is for this.
At the moment the rt2x00 drivers in wireless-dev use its own CRC16 table and calculation inside the driver. There already is a CRC16 library in the kernel which uses the
0x8005table, while rt2x00 uses the0x1021polynomial table.
Quoted 5 lines
Is keeping this version of CRC16 inside rt2x00 the most sensible thing to do? Or should it be moved to the lib folder of the kernel so other drivers could make use of it as well? (So far I have not found a driver which makes use
of the same CRC16 table)
However, fs/udf/crc.c has exactly the same CRC table as rt2x00:
static uint16_t crc_table[256] = {
0x0000U, 0x1021U, 0x2042U, 0x3063U, 0x4084U, 0x50a5U, 0x60c6U, 0x70e7U,
...
0x6e17U, 0x7e36U, 0x4e55U, 0x5e74U, 0x2e93U, 0x3eb2U, 0x0ed1U, 0x1ef0U
};/*
* udf_crc
*
* PURPOSE
* Calculate a 16-bit CRC checksum using ITU-T V.41 polynomial.
*
* DESCRIPTION
* The OSTA-UDF(tm) 1.50 standard states that using CRCs is mandatory.
* The polynomial used is: x^16 + x^12 + x^15 + 1
*
* PRE-CONDITIONS
* data Pointer to the data block. * size Size of the data block.
*
* POST-CONDITIONS
* <return> CRC of the data block.
*
* HISTORY
* July 21, 1997 - Andrew E. Mileski
* Adapted from OSTA-UDF(tm) 1.50 standard.
*/
This is a bit-reversed form of CRC-CCITT supported by lib/crc-ccitt.c. Unfortunately, this does not help much, because converting one form to the other is too expensive (you would need to reverse bits in all data bytes, and then reverse bits in the 16-bit result).
BTW, there is more CRC code duplication in drivers/bluetooth/hci_bcsp.c (bcsp_crc_update() seems to give the same result as crc_ccitt_byte()).
In drivers/media/dvb/frontends/nxt200x.c, nxt200x_crc() seems to give the same result as rt2x00crc_byte() (but without using a table).
drivers/net/wan/cycx_drv.c:checksum() is also some mutated version of CRC-CCITT (adding two additional zero bytes at the end of data makes it return the same result as rt2x00crc()).
Quoted 55 lines · Sergey Vlasov
Quoted 9 lines · On Sat, 27 May 2006 13:27:15 +0200 Ivo van Doorn wrote:
I have a small question about the CRC16 usage in rt2x00 and what the netdev preferred method is for this.
At the moment the rt2x00 drivers in wireless-dev use its own CRC16 table and calculation inside the driver. There already is a CRC16 library in the kernel which uses the
0x8005table, while rt2x00 uses the0x1021polynomial table.Quoted 5 lines
Is keeping this version of CRC16 inside rt2x00 the most sensible thing to do? Or should it be moved to the lib folder of the kernel so other drivers could make use of it as well? (So far I have not found a driver which makes use
of the same CRC16 table)However,
fs/udf/crc.chas exactly the same CRC table as rt2x00:static uint16_t crc_table[256] = { 0x0000U, 0x1021U, 0x2042U, 0x3063U, 0x4084U, 0x50a5U, 0x60c6U, 0x70e7U, ... 0x6e17U, 0x7e36U, 0x4e55U, 0x5e74U, 0x2e93U, 0x3eb2U, 0x0ed1U, 0x1ef0U };/*
*udf_crc
*
* PURPOSE
* Calculate a 16-bit CRC checksum using ITU-T V.41 polynomial.
*
* DESCRIPTION
* The OSTA-UDF(tm) 1.50 standard states that using CRCs is mandatory.
* The polynomial used is: x^16 + x^12 + x^15 + 1
*
* PRE-CONDITIONS* data Pointer to the data block. * size Size of the data block.*
* POST-CONDITIONS
* <return> CRC of the data block.
*
* HISTORY
* July 21, 1997 - Andrew E. Mileski
* Adapted from OSTA-UDF(tm) 1.50 standard.
*/This is a bit-reversed form of CRC-CCITT supported by
lib/crc-ccitt.c. Unfortunately, this does not help much, because converting one form to the other is too expensive (you would need to reverse bits in all data bytes, and then reverse bits in the 16-bit result).BTW, there is more CRC code duplication in
drivers/bluetooth/hci_bcsp.c(bcsp_crc_update()seems to give the same result ascrc_ccitt_byte()).
Quoted 6 lines
In
drivers/media/dvb/frontends/nxt200x.c,nxt200x_crc()seems to give the same result asrt2x00crc_byte()(but without using a table).drivers/net/wan/cycx_drv.c:checksum() is also some mutated version of CRC-CCITT (adding two additional zero bytes at the end of data makes it return the same result as
rt2x00crc()).
Interesting, so it would actually be usefull to move the nxt200x crc16 implemetation into the crc16 library (Is not using a table preferred over using a table?) And make rt2x00 and fs/udf/crc.c make use of this library?
And perhaps hci_bcsp could be updated to use crc_ccitt_byte() instead?
Regards,
ivo
Quoted 1 line · Ivo van Doorn
On Saturday 27 May 2006 15:55, Sergey Vlasov wrote:
[skip]
Quoted 1 line
Quoted 1 line
However,
fs/udf/crc.chas exactly the same CRC table as rt2x00:
[skip]
Quoted 8 lines
Quoted 8 lines
This is a bit-reversed form of CRC-CCITT supported by
lib/crc-ccitt.c. Unfortunately, this does not help much, because converting one form to the other is too expensive (you would need to reverse bits in all data bytes, and then reverse bits in the 16-bit result).BTW, there is more CRC code duplication in
drivers/bluetooth/hci_bcsp.c(bcsp_crc_update()seems to give the same result ascrc_ccitt_byte()).
Quoted 6 lines
Quoted 6 lines
In
drivers/media/dvb/frontends/nxt200x.c,nxt200x_crc()seems to give the same result asrt2x00crc_byte()(but without using a table).drivers/net/wan/cycx_drv.c:checksum() is also some mutated version of CRC-CCITT (adding two additional zero bytes at the end of data makes it return the same result as
rt2x00crc()).
More stealth CRC implementations:
- drivers/ieee1394/csr.c:csr_crc16() - the same as rt2x00crc();
- drivers/ieee1394/csr1212.c:csr1212_crc16() - again the same as rt2x00crc(), except the final byteswap;
- drivers/net/wireless/wavelan.c:psa_crc() is plain crc16(); it is duplicated in drivers/net/wireless/wavelan_cs.c;
- drivers/scsi/FlashPoint.c:FPT_CalcCrc16() is also crc16();
Quoted 3 lines
Interesting, so it would actually be usefull to move the nxt200x crc16 implemetation into the crc16 library (Is not using a table preferred over using a table?)
Using a table is probably faster, but consumes more memory.
Quoted 3 lines
And make rt2x00 and
fs/udf/crc.cmake use of this library?And perhaps
hci_bcspcould be updated to usecrc_ccitt_byte()instead?
Quoted 30 lines · Sergey Vlasov
Quoted 1 line · Ivo van Doorn
On Saturday 27 May 2006 15:55, Sergey Vlasov wrote:
[skip]
Quoted 1 line
Quoted 1 line
However,
fs/udf/crc.chas exactly the same CRC table as rt2x00:[skip]
Quoted 8 lines
Quoted 8 lines
This is a bit-reversed form of CRC-CCITT supported by
lib/crc-ccitt.c. Unfortunately, this does not help much, because converting one form to the other is too expensive (you would need to reverse bits in all data bytes, and then reverse bits in the 16-bit result).BTW, there is more CRC code duplication in
drivers/bluetooth/hci_bcsp.c(bcsp_crc_update()seems to give the same result ascrc_ccitt_byte()).Quoted 6 lines
Quoted 6 lines
In
drivers/media/dvb/frontends/nxt200x.c,nxt200x_crc()seems to give the same result asrt2x00crc_byte()(but without using a table).drivers/net/wan/cycx_drv.c:checksum() is also some mutated version of CRC-CCITT (adding two additional zero bytes at the end of data makes it return the same result as
rt2x00crc()).More stealth CRC implementations:
- drivers/ieee1394/csr.c:csr_crc16() - the same as
rt2x00crc();- drivers/ieee1394/csr1212.c:csr1212_crc16() - again the same as
rt2x00crc(), except the final byteswap;- drivers/net/wireless/wavelan.c:psa_crc() is plain
crc16(); it is duplicated indrivers/net/wireless/wavelan_cs.c;
Quoted 11 lines
- drivers/scsi/FlashPoint.c:FPT_CalcCrc16() is also
crc16();Quoted 3 lines
Interesting, so it would actually be usefull to move the nxt200x crc16 implemetation into the crc16 library (Is not using a table preferred over using a table?)
Using a table is probably faster, but consumes more memory.
Quoted 3 lines
And make rt2x00 and
fs/udf/crc.cmake use of this library?And perhaps
hci_bcspcould be updated to usecrc_ccitt_byte()instead?
Thanks,
I will take another look at the drivers as well and see which drivers could best be udpated to use the kernel library instead of using its own implementation.
This will take a couple of days, but then I should have a couple of patches ready to add some crc libs and update the drivers to make use of these labs.
Ivo