Skip to contentSkip to conversation

lib: add crc16_le helper

PATCH In review Florian Fainelli 4 participants 7 messages Aug 18, 2010 – Aug 20, 2010

Subsystems (3)
Library code Memory technology devices (MTD) CRC library
lore
Share & tools
lore

Florian Fainelli

author
#0 lore raw

PATCH v2 3/4 lib: add crc16_le helper

This patch adds a crc16_le helper function to lib/crc16.c

Signed-off-by Matthieu CASTET <[email protected]>
Signed-off-by Florian Fainelli <[email protected]>

--

include/linux/crc16.h +2 -0
index 9443c08..6c1c61f 100644
@@ -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 */
lib/crc16.c +12 -0
index 8737b08..ec4a95c 100644
@@ -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");
#1 lore raw
Quoted 30 lines

This patch adds a crc16_le helper function to lib/crc16.c

Signed-off-by Matthieu CASTET <[email protected]>
Signed-off-by Florian Fainelli <[email protected]>

--

include/linux/crc16.h +2 -0
index 9443c08..6c1c61f 100644
@@ -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 */
lib/crc16.c +4 -0
index 8737b08..ec4a95c 100644
@@ -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--) {

lib/crc16.c u16 crc16(u16 crc, u8 const *buffer, size_t len) · line 78

Quoted 10 lines
lib/crc16.c +8 -0
+      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

#2 lore raw

Hi,

thanks for the review.

Quoted 34 lines · Joakim Tjernlund
Quoted 34 lines

This patch adds a crc16_le helper function to lib/crc16.c

Signed-off-by Matthieu CASTET <[email protected]>
Signed-off-by Florian Fainelli <[email protected]>

--

include/linux/crc16.h +2 -0
index 9443c08..6c1c61f 100644
@@ -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 */
lib/crc16.c +9 -0
index 8737b08..ec4a95c 100644
@@ -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;
Quoted 8 lines

lib/crc16.c u16 crc16(u16 crc, u8 const *buffer, size_t len) · line 78

Quoted 5 lines
lib/crc16.c +3 -0
+}
+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.

Quoted 2 lines

if so, 0x8005 looks
wrong too. see CRCPOLY_LE resp. CRCPOLY_BE for an idea.

Why ?

Quoted 1 line

What is this crc sum used for?

Onfi flash parsing in mtd.

Matthieu

#3 lore raw

Matthieu CASTET <[email protected]> wrote on 2010/08/18 18:10:11:

Quoted 48 lines

Hi,

thanks for the review.

Quoted 34 lines · Joakim Tjernlund
Quoted 34 lines

This patch adds a crc16_le helper function to lib/crc16.c

Signed-off-by Matthieu CASTET <[email protected]>
Signed-off-by Florian Fainelli <[email protected]>

--

include/linux/crc16.h +2 -0
index 9443c08..6c1c61f 100644
@@ -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 */
lib/crc16.c +9 -0
index 8737b08..ec4a95c 100644
@@ -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;
Quoted 8 lines

lib/crc16.c u16 crc16(u16 crc, u8 const *buffer, size_t len) · line 78

Quoted 5 lines
lib/crc16.c +3 -0
+}
+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.

Quoted 7 lines

yes it is a be crc while crc16 is a le one. So we should rename it to crc16_be.

Quoted 2 lines

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

Quoted 3 lines
Quoted 2 lines

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?

#4 lore raw

Hi,

Quoted 11 lines · Joakim Tjernlund

Matthieu CASTET <[email protected]> wrote on 2010/08/18 18:10:11:

Quoted 3 lines
Quoted 2 lines

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.

Quoted 6 lines
Quoted 3 lines
Quoted 2 lines

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.

Quoted 2 lines

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;
}

#5 lore raw

Matthieu CASTET <[email protected]> wrote on 2010/08/19 09:42:49:

Quoted 20 lines

Hi,

Quoted 11 lines · Joakim Tjernlund

Matthieu CASTET <[email protected]> wrote on 2010/08/18 18:10:11:

Quoted 3 lines
Quoted 2 lines

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.

Quoted 1 line
Quoted 7 lines
Quoted 5 lines
Quoted 2 lines
Quoted 1 line

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.

Quoted 5 lines
Quoted 3 lines

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]

#6 lore raw

Hi Joakim,

Quoted 5 lines · On Thursday 19 August 2010 11:41:13 Joakim Tjernlund wrote:

Matthieu CASTET <[email protected]> wrote on 2010/08/19 09:42:49:

Quoted 4 lines

Hi,

Quoted 1 line · Joakim Tjernlund

Matthieu CASTET <[email protected]> wrote on 2010/08/18

18:10:11:

Quoted 31 lines
Quoted 19 lines
Quoted 5 lines
Quoted 4 lines
Quoted 2 lines

if so, 0x8005 looks
wrong too. see CRCPOLY_LE resp. CRCPOLY_BE for an idea.

Why ?

Quoted 8 lines

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.

Quoted 2 lines
Quoted 2 lines
Quoted 1 line

What is this crc sum used for?

Quoted 7 lines
Quoted 4 lines
Quoted 1 line

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.

Quoted 2 lines
Quoted 1 line

Why can't you use the crc16 LE version?

Quoted 7 lines
Quoted 2 lines

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.

Quoted 15 lines

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;
}
Quoted 4 lines

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