| Message ID | 201008181401.15328.florian@openwrt.org |
|---|---|
| State | New, archived |
| Headers | show |
> > This patch adds a crc16_le helper function to lib/crc16.c > > Signed-off-by: Matthieu CASTET <matthieu.castet@parrot.com> > Signed-off-by: Florian Fainelli <ffainelli@freebox.fr> > -- > diff --git a/include/linux/crc16.h b/include/linux/crc16.h > index 9443c08..6c1c61f 100644 > --- a/include/linux/crc16.h > +++ b/include/linux/crc16.h > @@ -26,5 +26,7 @@ static inline u16 crc16_byte(u16 crc, const u8 data) > return (crc >> 8) ^ crc16_table[(crc ^ data) & 0xff]; > } > > +extern u16 crc16_le(u16 crc, const u8 *buffer, size_t len); > + > #endif /* __CRC16_H */ > > diff --git a/lib/crc16.c b/lib/crc16.c > index 8737b08..ec4a95c 100644 > --- a/lib/crc16.c > +++ b/lib/crc16.c > @@ -62,6 +62,18 @@ u16 crc16(u16 crc, u8 const *buffer, size_t len) > } > EXPORT_SYMBOL(crc16); > > +u16 crc16_le(u16 crc, u8 const *p, size_t len) > +{ > + int i; > + while (len--) { > + crc ^= *p++ << 8; > + for (i = 0; i < 8; i++) > + crc = (crc << 1) ^ ((crc & 0x8000) ? 0x8005 : 0); > + } > + return crc; > +} > +EXPORT_SYMBOL(crc16_le); > + > MODULE_DESCRIPTION("CRC16 calculations"); > MODULE_LICENSE("GPL"); Don't recall much of my earlier crc32 work but the above looks wrong. crc & 0x8000 suggests this is a big endian crc. if so, 0x8005 looks wrong too. see CRCPOLY_LE resp. CRCPOLY_BE for an idea. What is this crc sum used for? Jocke
Hi, thanks for the review. Joakim Tjernlund a écrit : >> This patch adds a crc16_le helper function to lib/crc16.c >> >> Signed-off-by: Matthieu CASTET <matthieu.castet@parrot.com> >> Signed-off-by: Florian Fainelli <ffainelli@freebox.fr> >> -- >> diff --git a/include/linux/crc16.h b/include/linux/crc16.h >> index 9443c08..6c1c61f 100644 >> --- a/include/linux/crc16.h >> +++ b/include/linux/crc16.h >> @@ -26,5 +26,7 @@ static inline u16 crc16_byte(u16 crc, const u8 data) >> return (crc >> 8) ^ crc16_table[(crc ^ data) & 0xff]; >> } >> >> +extern u16 crc16_le(u16 crc, const u8 *buffer, size_t len); >> + >> #endif /* __CRC16_H */ >> >> diff --git a/lib/crc16.c b/lib/crc16.c >> index 8737b08..ec4a95c 100644 >> --- a/lib/crc16.c >> +++ b/lib/crc16.c >> @@ -62,6 +62,18 @@ u16 crc16(u16 crc, u8 const *buffer, size_t len) >> } >> EXPORT_SYMBOL(crc16); >> >> +u16 crc16_le(u16 crc, u8 const *p, size_t len) >> +{ >> + int i; >> + while (len--) { >> + crc ^= *p++ << 8; >> + for (i = 0; i < 8; i++) >> + crc = (crc << 1) ^ ((crc & 0x8000) ? 0x8005 : 0); >> + } >> + return crc; >> +} >> +EXPORT_SYMBOL(crc16_le); >> + >> MODULE_DESCRIPTION("CRC16 calculations"); >> MODULE_LICENSE("GPL"); > > Don't recall much of my earlier crc32 work but the above looks wrong. > crc & 0x8000 suggests this is a big endian crc. yes it is a be crc while crc16 is a le one. So we should rename it to crc16_be. >if so, 0x8005 looks > wrong too. see CRCPOLY_LE resp. CRCPOLY_BE for an idea. Why ? > What is this crc sum used for? Onfi flash parsing in mtd. Matthieu
Matthieu CASTET <matthieu.castet@parrot.com> wrote on 2010/08/18 18:10:11: > > Hi, > > thanks for the review. > > Joakim Tjernlund a écrit : > >> This patch adds a crc16_le helper function to lib/crc16.c > >> > >> Signed-off-by: Matthieu CASTET <matthieu.castet@parrot.com> > >> Signed-off-by: Florian Fainelli <ffainelli@freebox.fr> > >> -- > >> diff --git a/include/linux/crc16.h b/include/linux/crc16.h > >> index 9443c08..6c1c61f 100644 > >> --- a/include/linux/crc16.h > >> +++ b/include/linux/crc16.h > >> @@ -26,5 +26,7 @@ static inline u16 crc16_byte(u16 crc, const u8 data) > >> return (crc >> 8) ^ crc16_table[(crc ^ data) & 0xff]; > >> } > >> > >> +extern u16 crc16_le(u16 crc, const u8 *buffer, size_t len); > >> + > >> #endif /* __CRC16_H */ > >> > >> diff --git a/lib/crc16.c b/lib/crc16.c > >> index 8737b08..ec4a95c 100644 > >> --- a/lib/crc16.c > >> +++ b/lib/crc16.c > >> @@ -62,6 +62,18 @@ u16 crc16(u16 crc, u8 const *buffer, size_t len) > >> } > >> EXPORT_SYMBOL(crc16); > >> > >> +u16 crc16_le(u16 crc, u8 const *p, size_t len) > >> +{ > >> + int i; > >> + while (len--) { > >> + crc ^= *p++ << 8; > >> + for (i = 0; i < 8; i++) > >> + crc = (crc << 1) ^ ((crc & 0x8000) ? 0x8005 : 0); > >> + } > >> + return crc; > >> +} > >> +EXPORT_SYMBOL(crc16_le); > >> + > >> MODULE_DESCRIPTION("CRC16 calculations"); > >> MODULE_LICENSE("GPL"); > > > > Don't recall much of my earlier crc32 work but the above looks wrong. > > crc & 0x8000 suggests this is a big endian crc. > yes it is a be crc while crc16 is a le one. So we should rename it to > crc16_be. > > > >if so, 0x8005 looks > > wrong too. see CRCPOLY_LE resp. CRCPOLY_BE for an idea. > Why ? Because changing endian of crc also require the POLY to be bit reversed as well. See: #define CRCPOLY_LE 0xedb88320 #define CRCPOLY_BE 0x04c11db7 So I assume you need to do that as well for crc16_be, otherwise it won't be a BE version of the standard crc16 LE > > > What is this crc sum used for? > Onfi flash parsing in mtd. And this is a one time operation of fairly small amount of data? I ask because you impl. is really slow. Why can't you use the crc16 LE version?
Hi, Joakim Tjernlund a écrit : > Matthieu CASTET <matthieu.castet@parrot.com> wrote on 2010/08/18 18:10:11: >>> if so, 0x8005 looks >>> wrong too. see CRCPOLY_LE resp. CRCPOLY_BE for an idea. >> Why ? > > Because changing endian of crc also require the POLY > to be bit reversed as well. See: > #define CRCPOLY_LE 0xedb88320 > #define CRCPOLY_BE 0x04c11db7 > So I assume you need to do that as well for crc16_be, otherwise it > won't be a BE version of the standard crc16 LE Well it match the crc provided in onfi nand [1]. But it may be not a real BE version. > >>> What is this crc sum used for? >> Onfi flash parsing in mtd. > > And this is a one time operation of fairly small amount of > data? I ask because you impl. is really slow. Yes it checks only 253 bytes at startup time (one time only). So it is not speed critical. > Why can't you use the crc16 LE version? > Because it doesn't compute the crc provided by onfi spec. Or is there some magic maths to convert LE version to our version ? Matthieu [1] 5.4.1.36. Byte 254-255: Integrity CRC The Integrity CRC (Cyclic Redundancy Check) field is used to verify that the contents of the parameters page were transferred correctly to the host. The CRC of the parameter page is a word (16-bit) field. The CRC calculation covers all of data between byte 0 and byte 253 of the parameter page inclusive. The CRC shall be calculated on word (16-bit) quantities starting with bytes 1:0 in the parameter page. The bits in the 16-bit quantity are processed from the most significant bit (bit 15) to the least significant bit (bit 0). Even bytes of the parameter page (i.e. 0, 2, 4, etc) shall be used in the lower byte of the CRC calculation (bits 7:0). Odd bytes of the parameter page (i.e. 1, 3, 5, etc) shall be used in the upper byte of the CRC calculation (bits 15:8). The CRC shall be calculated using the following 16-bit generator polynomial: G(X) = X16 + X15 + X2 + 1 This polynomial in hex may be represented as 8005h. The CRC value shall be initialized with a value of 4F4Eh before the calculation begins. There is no XOR applied to the final CRC value after it is calculated. There is no reversal of the data bytes or the CRC calculated value. [...] A. SAMPLE CODE FOR CRC-16 (INFORMATIVE) This section provides an informative implementation of the CRC-16 polynomial. The example is intended as an aid in verifying an implementation of the algorithm. int main(int argc, char* argv[]) { // Bit by bit algorithm without augmented zero bytes const unsigned long crcinit = 0x4F4E; // Initial CRC value in the shift register const int order = 16; // Order of the CRC-16 const unsigned long polynom = 0x8005; // Polynomial unsigned long i, j, c, bit; unsigned long crc = crcinit; // Initialize the shift register with 0x4F4E unsigned long data_in; int dataByteCount = 0; crcmask = ((((unsigned long)1<<(order-1))-1)<<1)|1; crchighbit = (unsigned long)1<<(order-1); // Input byte stream, one byte at a time, bits processed from MSB to LSB printf("Input byte value in hex(eg. 0x30):"); printf("\n"); while(scanf("%x", &data_in) == 1) { c = (unsigned long)data_in; dataByteCount++; for (j=0x80; j; j>>=1) { bit = crc & crchighbit; crc<<= 1; if (c & j) bit^= crchighbit; if (bit) crc^= polynom; } crc&= crcmask; printf("CRC-16 value: 0x%x\n", crc); } printf("Final CRC-16 value: 0x%x, total data bytes: %d\n", crc, dataByteCount); return 0; }
Matthieu CASTET <matthieu.castet@parrot.com> wrote on 2010/08/19 09:42:49: > > Hi, > > Joakim Tjernlund a écrit : > > Matthieu CASTET <matthieu.castet@parrot.com> wrote on 2010/08/18 18:10:11: > >>> if so, 0x8005 looks > >>> wrong too. see CRCPOLY_LE resp. CRCPOLY_BE for an idea. > >> Why ? > > > > Because changing endian of crc also require the POLY > > to be bit reversed as well. See: > > #define CRCPOLY_LE 0xedb88320 > > #define CRCPOLY_BE 0x04c11db7 > > So I assume you need to do that as well for crc16_be, otherwise it > > won't be a BE version of the standard crc16 LE > Well it match the crc provided in onfi nand [1]. But it may be not a > real BE version. > > > > > >>> What is this crc sum used for? > >> Onfi flash parsing in mtd. > > > > And this is a one time operation of fairly small amount of > > data? I ask because you impl. is really slow. > Yes it checks only 253 bytes at startup time (one time only). So it is > not speed critical. OK. > > > Why can't you use the crc16 LE version? > > > Because it doesn't compute the crc provided by onfi spec. Or is there > some magic maths to convert LE version to our version ? I suspect the onfi spec got it wrong and isn't computing a real crc16_be. I suggest you rename this to onfi_crc16_be and move it inside the onfi subsystem. I supposed you are stuck with the onfi version? Just for the record, I think the crc16_be should be like this: u16 crc16_le(u16 crc, u8 const *p, size_t len) { int i; while (len--) { crc ^= *p++ << 8; i = 8; do { crc = (crc << 1) ^ ((crc & 0x8000) ? 0xa001 : 0); } while(--i); } return crc; } Don't know of an easy way to go between LE and BE versions but have a look at lib/crc32.c, there is a unit test in there that suggests that on can byte reverse the data to go between LE and BE. [Deleted ugly code]
Hi Joakim, On Thursday 19 August 2010 11:41:13 Joakim Tjernlund wrote: > Matthieu CASTET <matthieu.castet@parrot.com> wrote on 2010/08/19 09:42:49: > > Hi, > > > > Joakim Tjernlund a écrit : > > > Matthieu CASTET <matthieu.castet@parrot.com> wrote on 2010/08/18 18:10:11: > > >>> if so, 0x8005 looks > > >>> wrong too. see CRCPOLY_LE resp. CRCPOLY_BE for an idea. > > >> > > >> Why ? > > > > > > Because changing endian of crc also require the POLY > > > > > > to be bit reversed as well. See: > > > #define CRCPOLY_LE 0xedb88320 > > > #define CRCPOLY_BE 0x04c11db7 > > > > > > So I assume you need to do that as well for crc16_be, otherwise it > > > won't be a BE version of the standard crc16 LE > > > > Well it match the crc provided in onfi nand [1]. But it may be not a > > real BE version. > > > > >>> What is this crc sum used for? > > >> > > >> Onfi flash parsing in mtd. > > > > > > And this is a one time operation of fairly small amount of > > > data? I ask because you impl. is really slow. > > > > Yes it checks only 253 bytes at startup time (one time only). So it is > > not speed critical. > > OK. > > > > Why can't you use the crc16 LE version? > > > > Because it doesn't compute the crc provided by onfi spec. Or is there > > some magic maths to convert LE version to our version ? > > I suspect the onfi spec got it wrong and isn't computing a real > crc16_be. I suggest you rename this to onfi_crc16_be and move it > inside the onfi subsystem. I supposed you are stuck with > the onfi version? I thought we could somehow genericize this version of the crc16, but you are right, we cannot, so let's put it back to the mtd subsystem where it is used. Thanks for your comments. > Just for the record, I think the crc16_be should be like this: > > u16 crc16_le(u16 crc, u8 const *p, size_t len) > { > int i; > while (len--) { > crc ^= *p++ << 8; > i = 8; > do { > crc = (crc << 1) ^ ((crc & 0x8000) ? 0xa001 : 0); > } while(--i); > } > return crc; > } > > Don't know of an easy way to go between LE and BE versions but > have a look at lib/crc32.c, there is a unit test in there > that suggests that on can byte reverse the data to go between > LE and BE. Ok, I will give it a try. -- Florian
diff --git a/include/linux/crc16.h b/include/linux/crc16.h index 9443c08..6c1c61f 100644 --- a/include/linux/crc16.h +++ b/include/linux/crc16.h @@ -26,5 +26,7 @@ static inline u16 crc16_byte(u16 crc, const u8 data) return (crc >> 8) ^ crc16_table[(crc ^ data) & 0xff]; } +extern u16 crc16_le(u16 crc, const u8 *buffer, size_t len); + #endif /* __CRC16_H */ diff --git a/lib/crc16.c b/lib/crc16.c index 8737b08..ec4a95c 100644 --- a/lib/crc16.c +++ b/lib/crc16.c @@ -62,6 +62,18 @@ u16 crc16(u16 crc, u8 const *buffer, size_t len) } EXPORT_SYMBOL(crc16); +u16 crc16_le(u16 crc, u8 const *p, size_t len) +{ + int i; + while (len--) { + crc ^= *p++ << 8; + for (i = 0; i < 8; i++) + crc = (crc << 1) ^ ((crc & 0x8000) ? 0x8005 : 0); + } + return crc; +} +EXPORT_SYMBOL(crc16_le); + MODULE_DESCRIPTION("CRC16 calculations"); MODULE_LICENSE("GPL");