[PATCH 3/4 v2] lib: add crc16_le helper

[PATCH 3/4 v2] lib: add crc16_le helper

[Florian Fainelli]

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

Re: [PATCH 3/4 v2] lib: add crc16_le helper

[Joakim Tjernlund]

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

Re: [PATCH 3/4 v2] lib: add crc16_le helper

[Matthieu CASTET]

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

Re: [PATCH 3/4 v2] lib: add crc16_le helper

[Joakim Tjernlund]

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?

Re: [PATCH 3/4 v2] lib: add crc16_le helper

[Matthieu CASTET]

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

Re: [PATCH 3/4 v2] lib: add crc16_le helper

[Joakim Tjernlund]

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]

Re: [PATCH 3/4 v2] lib: add crc16_le helper

[Florian Fainelli]

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