CRC16 in rt2x00

CRC16 in rt2x00

[Ivo van Doorn]

[-- Attachment #1: Type: text/plain, Size: 612 bytes --]

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

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: CRC16 in rt2x00

[Sergey Vlasov]

[-- Attachment #1: Type: text/plain, Size: 2298 bytes --]

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 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)

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()).

[-- Attachment #2: Type: application/pgp-signature, Size: 190 bytes --]

Re: CRC16 in rt2x00

[Ivo van Doorn]

[-- Attachment #1: Type: text/plain, Size: 2791 bytes --]

On Saturday 27 May 2006 15:55, Sergey Vlasov wrote:
> 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 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)
> 
> 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()).

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

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: CRC16 in rt2x00

[Sergey Vlasov]

[-- Attachment #1: Type: text/plain, Size: 1780 bytes --]

On Sat, May 27, 2006 at 04:24:07PM +0200, Ivo van Doorn wrote:
> On Saturday 27 May 2006 15:55, Sergey Vlasov wrote:
[skip]
> > However, fs/udf/crc.c has exactly the same CRC table as rt2x00:
[skip]
> > 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()).

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();

> 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.

> 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?

[-- Attachment #2: Type: application/pgp-signature, Size: 191 bytes --]

Re: CRC16 in rt2x00

[Ivo van Doorn]

[-- Attachment #1: Type: text/plain, Size: 2251 bytes --]

On Saturday 27 May 2006 18:30, Sergey Vlasov wrote:
> On Sat, May 27, 2006 at 04:24:07PM +0200, Ivo van Doorn wrote:
> > On Saturday 27 May 2006 15:55, Sergey Vlasov wrote:
> [skip]
> > > However, fs/udf/crc.c has exactly the same CRC table as rt2x00:
> [skip]
> > > 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()).
> 
> 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();
> 
> > 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.
> 
> > 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?

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

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]