[RFC] lib: crc8: add new library module providing crc8 algorithm

[RFC] lib: crc8: add new library module providing crc8 algorithm

[Arend van Spriel]

The brcm80211 driver in staging tree uses a crc8 function. Based on
feedback from John Linville to move this to lib directory, the linux
source has been searched. Although there is currently only one other
kernel driver using this algorithm (ie. drivers/ssb) we are providing
this as a library function for others to use.

V1:
- functionality taken from brcm80211 utility function as is.
- documented the crc8 header file using kernel-doc syntax.
- compilation verified in-kernel and as module for x86, x86_64, arm, and mips.

Cc: linux-kernel@vger.kernel.org
Cc: linux-wireless@vger.kernel.org
Cc: "John W. Linville" <linville@tuxdriver.com>
Cc: Dan Carpenter <error27@gmail.com>
Reviewed-by: Henry Ptasinski <henryp@broadcom.com>
Reviewed-by: Roland Vossen <rvossen@broadcom.com>
Reviewed-by: "Franky (Zhenhui) Lin" <frankyl@broadcom.com>
Signed-off-by: Arend van Spriel <arend@broadcom.com>
---
 include/linux/crc8.h |   61 +++++++++++++++++++++++++++++++++++++++
 lib/Kconfig          |    7 ++++
 lib/Makefile         |    1 +
 lib/crc8.c           |   77 ++++++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 146 insertions(+), 0 deletions(-)
 create mode 100644 include/linux/crc8.h
 create mode 100644 lib/crc8.c

diff --git a/include/linux/crc8.h b/include/linux/crc8.h
new file mode 100644
index 0000000..4048a34
--- /dev/null
+++ b/include/linux/crc8.h
@@ -0,0 +1,61 @@
+/*
+ * Copyright (c) 2011 Broadcom Corporation
+ *
+ * Permission to use, copy, modify, and/or distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
+ * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
+ * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
+ * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+#ifndef __CRC8_H_
+#define __CRC8_H_
+
+#include <linux/types.h>
+
+/**
+ * enum - CRC8 constants
+ *
+ * @CRC8_INIT_VALUE: Initial CRC8 checksum value
+ * @CRC8_GOOD_VALUE: Good final CRC8 checksum value
+ *
+ * Constants for the crc8() function. Refer to its
+ * documentation how to use these values.
+ */
+enum CRC8 {
+	CRC8_INIT_VALUE	= 0xff,
+	CRC8_GOOD_VALUE	= 0x9f
+};
+
+/**
+ * crc8() - calculate a crc8 over the given input data
+ *
+ * @pdata:	pointer to data buffer.
+ * @nbytes:	number of bytes in data buffer.
+ * @crc:	previous returned crc8 value.
+ *
+ * The CRC8 is calculated using the polynomial given below.
+ *
+ * x^8 + x^7 +x^6 + x^4 + x^2 + 1
+ *
+ * The caller provides the initial value (either %CRC8_INIT_VALUE
+ * or the previous returned value) to allow for processing of
+ * discontiguous blocks of data.  When generating the CRC the
+ * caller is responsible for complementing the final return value
+ * and inserting it into the byte stream.  When validating a byte
+ * stream (including CRC8), a final return value of %CRC8_GOOD_VALUE
+ * indicates the byte stream data can be considered valid.
+ *
+ * Reference:
+ * "A Painless Guide to CRC Error Detection Algorithms", ver 3, Aug 1993
+ * Williams, Ross N., ross<at>ross.net
+ * (see URL http://www.ross.net/crc/download/crc_v3.txt).
+ */
+u8 crc8(u8 *pdata, uint nbytes, u8 crc);
+
+#endif /* __CRC8_H_ */
diff --git a/lib/Kconfig b/lib/Kconfig
index 9c10e38..ff9e5a3 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -89,6 +89,13 @@ config LIBCRC32C
 	  require M here.  See Castagnoli93.
 	  Module will be libcrc32c.
 
+config CRC8
+	tristate "CRC8 function"
+	help
+	  This option provides CRC8 function. Drivers may select this
+	  when they need to do cyclic redundancy check according CRC8
+	  algorithm. Module will be called crc8.
+
 config AUDIT_GENERIC
 	bool
 	depends on AUDIT && !AUDIT_ARCH
diff --git a/lib/Makefile b/lib/Makefile
index 4b49a24..704959d 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -65,6 +65,7 @@ obj-$(CONFIG_CRC_ITU_T)	+= crc-itu-t.o
 obj-$(CONFIG_CRC32)	+= crc32.o
 obj-$(CONFIG_CRC7)	+= crc7.o
 obj-$(CONFIG_LIBCRC32C)	+= libcrc32c.o
+obj-$(CONFIG_CRC8)	+= crc8.o
 obj-$(CONFIG_GENERIC_ALLOCATOR) += genalloc.o
 
 obj-$(CONFIG_ZLIB_INFLATE) += zlib_inflate/
diff --git a/lib/crc8.c b/lib/crc8.c
new file mode 100644
index 0000000..a4f0923
--- /dev/null
+++ b/lib/crc8.c
@@ -0,0 +1,77 @@
+/*
+ * Copyright (c) 2011 Broadcom Corporation
+ *
+ * Permission to use, copy, modify, and/or distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
+ * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
+ * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
+ * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+#include <linux/module.h>
+#include <linux/crc8.h>
+
+/*
+ * table for crc8 calculation based on following polynomial:
+ * 	x^8 + x^7 +x^6 + x^4 + x^2 + 1
+ */
+static const u8 crc8_table[256] = {
+	0x00, 0xF7, 0xB9, 0x4E, 0x25, 0xD2, 0x9C, 0x6B,
+	0x4A, 0xBD, 0xF3, 0x04, 0x6F, 0x98, 0xD6, 0x21,
+	0x94, 0x63, 0x2D, 0xDA, 0xB1, 0x46, 0x08, 0xFF,
+	0xDE, 0x29, 0x67, 0x90, 0xFB, 0x0C, 0x42, 0xB5,
+	0x7F, 0x88, 0xC6, 0x31, 0x5A, 0xAD, 0xE3, 0x14,
+	0x35, 0xC2, 0x8C, 0x7B, 0x10, 0xE7, 0xA9, 0x5E,
+	0xEB, 0x1C, 0x52, 0xA5, 0xCE, 0x39, 0x77, 0x80,
+	0xA1, 0x56, 0x18, 0xEF, 0x84, 0x73, 0x3D, 0xCA,
+	0xFE, 0x09, 0x47, 0xB0, 0xDB, 0x2C, 0x62, 0x95,
+	0xB4, 0x43, 0x0D, 0xFA, 0x91, 0x66, 0x28, 0xDF,
+	0x6A, 0x9D, 0xD3, 0x24, 0x4F, 0xB8, 0xF6, 0x01,
+	0x20, 0xD7, 0x99, 0x6E, 0x05, 0xF2, 0xBC, 0x4B,
+	0x81, 0x76, 0x38, 0xCF, 0xA4, 0x53, 0x1D, 0xEA,
+	0xCB, 0x3C, 0x72, 0x85, 0xEE, 0x19, 0x57, 0xA0,
+	0x15, 0xE2, 0xAC, 0x5B, 0x30, 0xC7, 0x89, 0x7E,
+	0x5F, 0xA8, 0xE6, 0x11, 0x7A, 0x8D, 0xC3, 0x34,
+	0xAB, 0x5C, 0x12, 0xE5, 0x8E, 0x79, 0x37, 0xC0,
+	0xE1, 0x16, 0x58, 0xAF, 0xC4, 0x33, 0x7D, 0x8A,
+	0x3F, 0xC8, 0x86, 0x71, 0x1A, 0xED, 0xA3, 0x54,
+	0x75, 0x82, 0xCC, 0x3B, 0x50, 0xA7, 0xE9, 0x1E,
+	0xD4, 0x23, 0x6D, 0x9A, 0xF1, 0x06, 0x48, 0xBF,
+	0x9E, 0x69, 0x27, 0xD0, 0xBB, 0x4C, 0x02, 0xF5,
+	0x40, 0xB7, 0xF9, 0x0E, 0x65, 0x92, 0xDC, 0x2B,
+	0x0A, 0xFD, 0xB3, 0x44, 0x2F, 0xD8, 0x96, 0x61,
+	0x55, 0xA2, 0xEC, 0x1B, 0x70, 0x87, 0xC9, 0x3E,
+	0x1F, 0xE8, 0xA6, 0x51, 0x3A, 0xCD, 0x83, 0x74,
+	0xC1, 0x36, 0x78, 0x8F, 0xE4, 0x13, 0x5D, 0xAA,
+	0x8B, 0x7C, 0x32, 0xC5, 0xAE, 0x59, 0x17, 0xE0,
+	0x2A, 0xDD, 0x93, 0x64, 0x0F, 0xF8, 0xB6, 0x41,
+	0x60, 0x97, 0xD9, 0x2E, 0x45, 0xB2, 0xFC, 0x0B,
+	0xBE, 0x49, 0x07, 0xF0, 0x9B, 0x6C, 0x22, 0xD5,
+	0xF4, 0x03, 0x4D, 0xBA, 0xD1, 0x26, 0x68, 0x9F
+};
+
+/*
+ * crc8 - calculate a crc8 over the given input data
+ *
+ * pdata:	pointer to data buffer.
+ * nbytes:	number of bytes in data buffer.
+ * crc:	previous returned crc8 value.
+ */
+u8 crc8(u8 *pdata, uint nbytes, u8 crc)
+{
+	/* loop over the buffer data */
+	while (nbytes-- > 0)
+		crc = crc8_table[(crc ^ *pdata++) & 0xff];
+
+	return crc;
+}
+EXPORT_SYMBOL(crc8);
+
+MODULE_DESCRIPTION("CRC8 (by Williams, Ross N.) function");
+MODULE_AUTHOR("Broadcom Corporation");
+MODULE_LICENSE("Dual BSD/GPL");
-- 
1.7.4.1

Re: [RFC] lib: crc8: add new library module providing crc8 algorithm

[Johannes Berg]

On Sat, 2011-05-21 at 22:49 +0200, Arend van Spriel wrote:

> +/**
> + * enum - CRC8 constants
> + *
> + * @CRC8_INIT_VALUE: Initial CRC8 checksum value
> + * @CRC8_GOOD_VALUE: Good final CRC8 checksum value
> + *
> + * Constants for the crc8() function. Refer to its
> + * documentation how to use these values.
> + */
> +enum CRC8 {
> +	CRC8_INIT_VALUE	= 0xff,
> +	CRC8_GOOD_VALUE	= 0x9f
> +};

These seem a little out of place, wouldn't that be specific to how the
algorithm is used?

johannes

Re: [RFC] lib: crc8: add new library module providing crc8 algorithm

[Arend van Spriel]

On 05/22/2011 12:37 AM, Johannes Berg wrote:
> On Sat, 2011-05-21 at 22:49 +0200, Arend van Spriel wrote:
>
>> +/**
>> + * enum - CRC8 constants
>> + *
>> + * @CRC8_INIT_VALUE: Initial CRC8 checksum value
>> + * @CRC8_GOOD_VALUE: Good final CRC8 checksum value
>> + *
>> + * Constants for the crc8() function. Refer to its
>> + * documentation how to use these values.
>> + */
>> +enum CRC8 {
>> +	CRC8_INIT_VALUE	= 0xff,
>> +	CRC8_GOOD_VALUE	= 0x9f
>> +};
> These seem a little out of place, wouldn't that be specific to how the
> algorithm is used?

True, a different init value likely results in a different good value. 
However, the documentation of the crc8() function provides one possible 
use which makes use of these values. So it is provided as a convenience. 
Removal is easy of course, but I tend to keep it for those who are 
content with the proposed usage (not necessarily Broadcom :-D ).

Gr. AvS

-- 
Almost nobody dances sober, unless they happen to be insane.
-- H.P. Lovecraft --

Re: [RFC] lib: crc8: add new library module providing crc8 algorithm

[Alan Cox]

On Sat, 21 May 2011 22:49:33 +0200
"Arend van Spriel" <arend@broadcom.com> wrote:

> The brcm80211 driver in staging tree uses a crc8 function. Based on
> feedback from John Linville to move this to lib directory, the linux
> source has been searched. Although there is currently only one other
> kernel driver using this algorithm (ie. drivers/ssb) we are providing
> this as a library function for others to use.

Can we find a better name for it - there seem to be lots of CRC8 variants
that are different - eg bit direction and it's going to be confusing to
just call it 'crc8'

Re: [RFC] lib: crc8: add new library module providing crc8 algorithm

[Arend van Spriel]

On 05/22/2011 01:23 PM, Alan Cox wrote:
> On Sat, 21 May 2011 22:49:33 +0200
> "Arend van Spriel"<arend@broadcom.com>  wrote:
>
>> The brcm80211 driver in staging tree uses a crc8 function. Based on
>> feedback from John Linville to move this to lib directory, the linux
>> source has been searched. Although there is currently only one other
>> kernel driver using this algorithm (ie. drivers/ssb) we are providing
>> this as a library function for others to use.
> Can we find a better name for it - there seem to be lots of CRC8 variants
> that are different - eg bit direction and it's going to be confusing to
> just call it 'crc8'

No problem. I just had a look at the lib directory and noticed the crc7 
function and module is called crc7. I can imagine there are enough 
variants of that as well. Another variation is probably the polynomial 
used. Not sure how to factor in bit direction and polynomial into the name.

suggestions from my thumb:
- rnw_crc8: refers to Ross N. Williams who wrote the paper used for 
implementing this function.
- painless_crc8: refers to title of the paper "A Painless Guide to CRC 
Error Detection Algorithms".
- brcm_crc8: indicates where the function came from.

Other suggestions are welcome.

Gr. AvS

-- 
Almost nobody dances sober, unless they happen to be insane.
-- H.P. Lovecraft --

Re: [RFC] lib: crc8: add new library module providing crc8 algorithm

[Alan Cox]

Is it just used for wireless in this form ?

See the n_gsm and bluetooth code for what I think is the same crc
algorithm but in reverse bit order .

Re: [RFC] lib: crc8: add new library module providing crc8 algorithm

[Arend van Spriel]

On 05/22/2011 04:19 PM, Alan Cox wrote:
> Is it just used for wireless in this form ?
>
> See the n_gsm and bluetooth code for what I think is the same crc
> algorithm but in reverse bit order .
>
I only searched for term 'crc8' in the tree so you may be right. I will 
take a look. It may be worth to support both bit directions in some fashion.

Gr. AvS

-- 
Almost nobody dances sober, unless they happen to be insane.
-- H.P. Lovecraft --

Re: [RFC] lib: crc8: add new library module providing crc8 algorithm

[Arend van Spriel]

On 05/22/2011 04:19 PM, Alan Cox wrote:
> Is it just used for wireless in this form ?
>
> See the n_gsm and bluetooth code for what I think is the same crc
> algorithm but in reverse bit order .

Hi Alan,

Look into the code in n_gsm and bluetooth code. The algorithm is the 
same, but except for the bit order it also is using a different 
polynomial. My current implementation has a fixed table. I could do the 
table generation runtime with the polynomial and the bit order as 
parameters. That would make it more general purpose.

Gr. AvS

-- 
Almost nobody dances sober, unless they happen to be insane.
-- H.P. Lovecraft --

Re: [RFC] lib: crc8: add new library module providing crc8 algorithm

[Arend van Spriel]

On 05/24/2011 09:45 AM, Arend van Spriel wrote:
> On 05/22/2011 04:19 PM, Alan Cox wrote:
>> Is it just used for wireless in this form ?
>>
>> See the n_gsm and bluetooth code for what I think is the same crc
>> algorithm but in reverse bit order .
> Hi Alan,
>
> Look into the code in n_gsm and bluetooth code. The algorithm is the
Meant to say 'I looked into the code...'

Gr. AvS

-- 
Almost nobody dances sober, unless they happen to be insane.
-- H.P. Lovecraft --

Re: [RFC] lib: crc8: add new library module providing crc8 algorithm

[Alan Cox]

On Tue, 24 May 2011 09:45:47 +0200
"Arend van Spriel" <arend@broadcom.com> wrote:

> On 05/22/2011 04:19 PM, Alan Cox wrote:
> > Is it just used for wireless in this form ?
> >
> > See the n_gsm and bluetooth code for what I think is the same crc
> > algorithm but in reverse bit order .
> 
> Hi Alan,
> 
> Look into the code in n_gsm and bluetooth code. The algorithm is the 
> same, but except for the bit order it also is using a different 
> polynomial. My current implementation has a fixed table. I could do the 
> table generation runtime with the polynomial and the bit order as 
> parameters. That would make it more general purpose.

Probably not worth it - its so tiny a piece of code anyway (< 500 bytes
or so) that it's going to be bigger not smaller if you do that !

Re: [RFC] lib: crc8: add new library module providing crc8 algorithm

[Arend van Spriel]

On 05/24/2011 11:44 AM, Alan Cox wrote:
> On Tue, 24 May 2011 09:45:47 +0200
> "Arend van Spriel"<arend@broadcom.com>  wrote:
>
>> On 05/22/2011 04:19 PM, Alan Cox wrote:
>>> Is it just used for wireless in this form ?
>>>
>>> See the n_gsm and bluetooth code for what I think is the same crc
>>> algorithm but in reverse bit order .
>> Hi Alan,
>>
>> Look into the code in n_gsm and bluetooth code. The algorithm is the
>> same, but except for the bit order it also is using a different
>> polynomial. My current implementation has a fixed table. I could do the
>> table generation runtime with the polynomial and the bit order as
>> parameters. That would make it more general purpose.
> Probably not worth it - its so tiny a piece of code anyway (<  500 bytes
> or so) that it's going to be bigger not smaller if you do that !

Hi Alan,

Not sure whether you mean the source code or the object code. I build 
kernel with debug symbols so the sizes are bit higher.

fixed table:        -rw-r--r-- 1 arend arend 1859 2011-05-24 11:53 crc8.o
custom table:    -rw-r--r-- 1 arend arend 2215 2011-05-24 11:58 crc8.o

The size increase is not that big.

Gr. AvS

-- 
Almost nobody dances sober, unless they happen to be insane.
-- H.P. Lovecraft --

Re: [RFC] lib: crc8: add new library module providing crc8 algorithm

[Rafał Miłecki]

I'm out of topic, but you can take a look at drivers/ssb/pci.c

We implement crc checksum here as well. The same will be soon needed
for bcma (i've already done this locally).

-- 
Rafał

Re: [RFC] lib: crc8: add new library module providing crc8 algorithm

[Alan Cox]

> Not sure whether you mean the source code or the object code. I build 
> kernel with debug symbols so the sizes are bit higher.

nm will tell you the actual sizes. I think the n_gsm code is about 500
bytes or so and chunks of it inline.

Re: [RFC] lib: crc8: add new library module providing crc8 algorithm

[Arend van Spriel]

On 05/24/2011 12:27 PM, Alan Cox wrote:
>> Not sure whether you mean the source code or the object code. I build
>> kernel with debug symbols so the sizes are bit higher.
> nm will tell you the actual sizes. I think the n_gsm code is about 500
> bytes or so and chunks of it inline.

Not counting the crc table I assume.

Gr. AvS

-- 
Almost nobody dances sober, unless they happen to be insane.
-- H.P. Lovecraft --

Re: [RFC] lib: crc8: add new library module providing crc8 algorithm

[Arend van Spriel]

On 05/24/2011 12:25 PM, Rafał Miłecki wrote:
> I'm out of topic, but you can take a look at drivers/ssb/pci.c
>
> We implement crc checksum here as well. The same will be soon needed
> for bcma (i've already done this locally).
>

Hi Rafał,

Couple of days ago I posted a patch for comments. In the commit message 
I referred to ssb having the same algorithm (identical crc table) as 
brcm80211. One of the reason for moving it to lib directory in the 
kernel tree. brcm80211, ssb, and bcma could use it.

Gr. AvS

-- 
Almost nobody dances sober, unless they happen to be insane.
-- H.P. Lovecraft --

Re: [RFC] lib: crc8: add new library module providing crc8 algorithm

[Alan Cox]

On Tue, 24 May 2011 12:38:45 +0200
"Arend van Spriel" <arend@broadcom.com> wrote:

> On 05/24/2011 12:27 PM, Alan Cox wrote:
> >> Not sure whether you mean the source code or the object code. I build
> >> kernel with debug symbols so the sizes are bit higher.
> > nm will tell you the actual sizes. I think the n_gsm code is about 500
> > bytes or so and chunks of it inline.
> 
> Not counting the crc table I assume.

I forget but I think including - its a tiny tiny bit of code once inlined.

Re: [RFC] lib: crc8: add new library module providing crc8 algorithm

[Arend van Spriel]

On 05/24/2011 02:57 PM, Alan Cox wrote:
> On Tue, 24 May 2011 12:38:45 +0200
> "Arend van Spriel"<arend@broadcom.com>  wrote:
>
>> On 05/24/2011 12:27 PM, Alan Cox wrote:
>>>> Not sure whether you mean the source code or the object code. I build
>>>> kernel with debug symbols so the sizes are bit higher.
>>> nm will tell you the actual sizes. I think the n_gsm code is about 500
>>> bytes or so and chunks of it inline.
>> Not counting the crc table I assume.
> I forget but I think including - its a tiny tiny bit of code once inlined.

I used nm on both flavours.

dynamic crc table based on polynomial and bit order
---------------------------------------------------
00000000 00000026 T crc8
00000030 000000dc T crc8_create

fixed crc table with table selection based on bit order
-------------------------------------------------------
00000000 00000026 T crc8
00000030 0000002b T crc8_create
00000100 00000100 r crc8_table_lsb
00000000 00000100 r crc8_table_msb

The first requires the user to provide buffer to hold the table. The 
difference is in the crc_create() function (maybe better named 
crc_populate_table() in first, and crc_select_table() in second). It is 
177 bytes larger. The crc calculating function is 38 bytes. Still pretty 
small I would think.

Gr. AvS

-- 
Almost nobody dances sober, unless they happen to be insane.
-- H.P. Lovecraft --

Re: [RFC] lib: crc8: add new library module providing crc8 algorithm

[Arend van Spriel]

On 05/25/2011 07:46 AM, George Spelvin wrote:
> Since you are obviously being ironic in your phrasing, I hope I did not
> give serious offense.  What I wrote is a fairly accurate description of
> my reflex reaction, but I could have phrased it more diplomatically.

No offense. I am not keen on politics anyway so blunt in fine with me ;-)

>> If callers use the specific function they can not specify a bit order so
>> no compile-time error.
> What I meant was, the bit order is specified by the function name.
> An invalid bit order translates to an invalid function name, which the
> linker will complain about.

Than we mean the same thing.

> If you feel ambitious, you can fold the crc7 code into yours.  Its an
> msbit-first CRC.  The resultant table will be left-justified rather
> than the current right-justified, but if you look at all the call sites,
> you'll notice that they all shift the result left 1 bit!

We are ambitious, but the focus is on getting our wireless driver in 
shape. The crc8 library function is related to that. So folding the crc7 
will get a low priority for now.

I noticed the whole table changed in the patch you posted in the bug 
report. So that is because of the shift, right?

Gr. AvS

-- 
Almost nobody dances sober, unless they happen to be insane.
-- H.P. Lovecraft --

Re: [RFC] lib: crc8: add new library module providing crc8 algorithm

[George Spelvin]

> On 05/25/2011 12:52 AM, George Spelvin wrote:
>> May I suggest that crc8_create is A Stupid Idea.  Since the bit order
>> (and polynomial) will always be compile-time constants, just let the
>> call sites call crc8_create_[lm]sb_first() directly.

> Thanks for be subtle in your suggestion.

Since you are obviously being ironic in your phrasing, I hope I did not
give serious offense.  What I wrote is a fairly accurate description of
my reflex reaction, but I could have phrased it more diplomatically.

> If callers use the specific function they can not specify a bit order so 
> no compile-time error.

What I meant was, the bit order is specified by the function name.
An invalid bit order translates to an invalid function name, which the
linker will complain about.


If you feel ambitious, you can fold the crc7 code into yours.  Its an
msbit-first CRC.  The resultant table will be left-justified rather
than the current right-justified, but if you look at all the call sites,
you'll notice that they all shift the result left 1 bit!

I have a pending bug report about some of the calling code which I
noticed when trying to update it myself, but it doesn't actally
prevent updating the crc7() call sites:
http://marc.info/?l=linux-wireless&m=130616050311698

Re: [RFC] lib: crc8: add new library module providing crc8 algorithm

[Arend van Spriel]

On 05/25/2011 12:52 AM, George Spelvin wrote:
>> V3:
>> - added function crc8_create().
>> - crc8_create() takes polynomial and bit direction as parameters.
> May I suggest that crc8_create is A Stupid Idea.  Since the bit order
> (and polynomial) will always be compile-time constants, just let the
> call sites call crc8_create_[lm]sb_first() directly.

Thanks for be subtle in your suggestion. The crc8 module can have 
multiple callers, which have their own bit order and polynomial. From 
caller perspective they are likely compile-time constants. You are right 
that the extra layer crc8_create is not adding much and callers should 
the bit order specific create functions directly.
> That way there's no need for the enum, and specifying something
> other than lsb_first and msb_first is a compile-time error rather than
> a run-time one

If callers use the specific function they can not specify a bit order so 
no compile-time error.

> It might be nice to add some const declarations, and use size_t
> for the buffer length:
> u8 crc8(u8 const *table, u8 const *pdata, size_t nbytes, u8 crc)
> or
> u8 crc8(u8 const table[256], u8 const *pdata, size_t nbytes, u8 crc)
>
>
> Style points you might consider, but I do not consider essential:
>
> Personally, when a function parameter is a pointer to
> a fixed-size array, I prefer to declare it as
> 	void crc8_create_lsb_first(u8 table[256], u8 poly)
> for better documentation, but that's your choice.
>
> The CRC8_GOOD_VALUE could be explained if you like.  "If a CRC is inverted
> before transmission, the CRC computed over the while (message+crc)
> is _table[x], when x is the bit pattern of the modification (almost
> always 0xff)."

Great remarks. Will update the code.

> Thanks!

Thanks.

Gr. AvS

-- 
Almost nobody dances sober, unless they happen to be insane.
-- H.P. Lovecraft --

Re: [RFC] lib: crc8: add new library module providing crc8 algorithm

[George Spelvin]

> V3:
> - added function crc8_create().
> - crc8_create() takes polynomial and bit direction as parameters.

May I suggest that crc8_create is A Stupid Idea.  Since the bit order
(and polynomial) will always be compile-time constants, just let the
call sites call crc8_create_[lm]sb_first() directly.

That way there's no need for the enum, and specifying something
other than lsb_first and msb_first is a compile-time error rather than
a run-time one.

It might be nice to add some const declarations, and use size_t
for the buffer length:
u8 crc8(u8 const *table, u8 const *pdata, size_t nbytes, u8 crc)
or
u8 crc8(u8 const table[256], u8 const *pdata, size_t nbytes, u8 crc)


Style points you might consider, but I do not consider essential:

Personally, when a function parameter is a pointer to
a fixed-size array, I prefer to declare it as
	void crc8_create_lsb_first(u8 table[256], u8 poly)
for better documentation, but that's your choice.

The CRC8_GOOD_VALUE could be explained if you like.  "If a CRC is inverted
before transmission, the CRC computed over the while (message+crc)
is _table[x], when x is the bit pattern of the modification (almost
always 0xff)."

Thanks!

[RFC] lib: crc8: add new library module providing crc8 algorithm

[Arend van Spriel]

The brcm80211 driver in staging tree uses a crc8 function. Based on
feedback from John Linville to move this to lib directory, the linux
source has been searched. Although there is currently only one other
kernel driver using this algorithm (ie. drivers/ssb) we are providing
this as a library function for others to use.

V1:
- functionality taken from brcm80211 utility function as is.
- documented the crc8 header file using kernel-doc syntax.
- compilation verified in-kernel and as module for x86, x86_64, arm, and mips.

V2:
- ran checkpatch after sending V1 (sorry for that mortal sin) so fixed that.

V3:
- added function crc8_create().
- crc8_create() takes polynomial and bit direction as parameters.

Cc: linux-kernel@vger.kernel.org
Cc: linux-wireless@vger.kernel.org
Cc: "John W. Linville" <linville@tuxdriver.com>
Cc: Dan Carpenter <error27@gmail.com>
Cc: George Spelvin <linux@horizon.com>
Reviewed-by: Henry Ptasinski <henryp@broadcom.com>
Reviewed-by: Roland Vossen <rvossen@broadcom.com>
Reviewed-by: "Franky (Zhenhui) Lin" <frankyl@broadcom.com>
Signed-off-by: Arend van Spriel <arend@broadcom.com>
---
 include/linux/crc8.h |   92 +++++++++++++++++++++++++++++++++++++++++++
 lib/Kconfig          |    7 +++
 lib/Makefile         |    1 +
 lib/crc8.c           |  105 ++++++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 205 insertions(+), 0 deletions(-)
 create mode 100644 include/linux/crc8.h
 create mode 100644 lib/crc8.c

diff --git a/include/linux/crc8.h b/include/linux/crc8.h
new file mode 100644
index 0000000..2525ca0
--- /dev/null
+++ b/include/linux/crc8.h
@@ -0,0 +1,92 @@
+/*
+ * Copyright (c) 2011 Broadcom Corporation
+ *
+ * Permission to use, copy, modify, and/or distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
+ * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
+ * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
+ * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+#ifndef __CRC8_H_
+#define __CRC8_H_
+
+#include <linux/types.h>
+
+/* see usage of this value in crc8() description */
+#define CRC8_INIT_VALUE		0xFF
+
+/* this return value of crc8() upon validating data indicates success */
+#define CRC8_GOOD_VALUE(_table)	(_table[0xFF])
+
+/* required table size for crc8 algorithm */
+#define CRC8_TABLE_SIZE			256
+
+/* helper macro assuring right table size is used */
+#define DECLARE_CRC8_TABLE(_table) \
+	static u8 _table[CRC8_TABLE_SIZE]
+
+/**
+ * enum - determine bit direction of the crc algorithm.
+ *
+ * @crc8_dir_msb_first: direction is in reverse order.
+ * @crc8_dir_lsb_first: direction is in regular order.
+ */
+enum crc8_direction {
+	crc8_dir_msb_first,
+	crc8_dir_lsb_first
+};
+
+/**
+ * crc8_create - fill crc table for given polynomial and bit direction.
+ *
+ * @table:	table to be filled.
+ * @polynomial:	polynomial for which table is to be filled.
+ * @direction:	bit order for which the table is to be filled.
+ *
+ * This function fills the provided table according the polynomial and
+ * the direction provided. Polynomials in CRC algorithms are typically
+ * represented as shown below.
+ *
+ *	poly = x^8 + x^7 + x^6 + x^4 + x^2 + 1
+ *
+ * For lsb_first direction x^7 maps to the lsb and for msb_first
+ * direction x^7 maps to the msb. So the polynomials are as below.
+ *
+ * - lsb first: poly = 10101011(1) = 0xAB
+ *
+ * - msb first: poly = (1)11010101 = 0xD5
+ *
+ * Reference:
+ * "A Painless Guide to CRC Error Detection Algorithms", ver 3, Aug 1993
+ * Williams, Ross N., ross<at>ross.net
+ * (see URL http://www.ross.net/crc/download/crc_v3.txt).
+ */
+void crc8_create(u8 *table, u8 polynomial, enum crc8_direction direction);
+
+/**
+ * crc8() - calculate a crc8 over the given input data.
+ *
+ * @table:	crc table used for calculation.
+ * @pdata:	pointer to data buffer.
+ * @nbytes:	number of bytes in data buffer.
+ * @crc:	previous returned crc8 value.
+ *
+ * The CRC8 is calculated using the polynomial given in crc8_create().
+ *
+ * The caller provides the initial value (either %CRC8_INIT_VALUE
+ * or the previous returned value) to allow for processing of
+ * discontiguous blocks of data.  When generating the CRC the
+ * caller is responsible for complementing the final return value
+ * and inserting it into the byte stream.  When validating a byte
+ * stream (including CRC8), a final return value of %CRC8_GOOD_VALUE
+ * indicates the byte stream data can be considered valid.
+ */
+u8 crc8(u8 *table, u8 *pdata, uint nbytes, u8 crc);
+
+#endif /* __CRC8_H_ */
diff --git a/lib/Kconfig b/lib/Kconfig
index 9c10e38..ff9e5a3 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -89,6 +89,13 @@ config LIBCRC32C
 	  require M here.  See Castagnoli93.
 	  Module will be libcrc32c.
 
+config CRC8
+	tristate "CRC8 function"
+	help
+	  This option provides CRC8 function. Drivers may select this
+	  when they need to do cyclic redundancy check according CRC8
+	  algorithm. Module will be called crc8.
+
 config AUDIT_GENERIC
 	bool
 	depends on AUDIT && !AUDIT_ARCH
diff --git a/lib/Makefile b/lib/Makefile
index 4b49a24..704959d 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -65,6 +65,7 @@ obj-$(CONFIG_CRC_ITU_T)	+= crc-itu-t.o
 obj-$(CONFIG_CRC32)	+= crc32.o
 obj-$(CONFIG_CRC7)	+= crc7.o
 obj-$(CONFIG_LIBCRC32C)	+= libcrc32c.o
+obj-$(CONFIG_CRC8)	+= crc8.o
 obj-$(CONFIG_GENERIC_ALLOCATOR) += genalloc.o
 
 obj-$(CONFIG_ZLIB_INFLATE) += zlib_inflate/
diff --git a/lib/crc8.c b/lib/crc8.c
new file mode 100644
index 0000000..b17b487
--- /dev/null
+++ b/lib/crc8.c
@@ -0,0 +1,105 @@
+/*
+ * Copyright (c) 2011 Broadcom Corporation
+ *
+ * Permission to use, copy, modify, and/or distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
+ * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
+ * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
+ * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+#define pr_fmt(fmt)		KBUILD_MODNAME ": " fmt
+#include <linux/module.h>
+#include <linux/crc8.h>
+#include <linux/printk.h>
+
+/*
+ * crc8_create_msb_first - creates crc table for reverse (msb first) bit order.
+ *
+ * table: table to be filled.
+ * polynomial: polynomial for which table is to be filled.
+ */
+static void crc8_create_msb_first(u8 *table, u8 polynomial)
+{
+	int i, j;
+	const u8 msbit = 0x80;
+	u8 t = msbit;
+
+	table[0] = 0;
+
+	for (i = 1; i < CRC8_TABLE_SIZE; i *= 2) {
+		t = (t << 1) ^ (t & msbit ? polynomial : 0);
+		for (j = 0; j < i; j++)
+			table[i+j] = table[j] ^ t;
+	}
+}
+
+/*
+ * crc8_create_msb_first - creates crc table for regular (lsb first) bit order.
+ *
+ * table: table to be filled.
+ * polynomial: polynomial for which table is to be filled.
+ */
+static void crc8_create_lsb_first(u8 *table, u8 polynomial)
+{
+	int i, j;
+	u8 t = 1;
+
+	table[0] = 0;
+
+	for (i = (CRC8_TABLE_SIZE >> 1); i; i >>= 1) {
+		t = (t >> 1) ^ (t & 1 ? polynomial : 0);
+		for (j = 0; j < CRC8_TABLE_SIZE; j += 2*i)
+			table[i+j] = table[j] ^ t;
+	}
+}
+
+/*
+ * crc8_create - fill crc table for given polynomial and bit direction.
+ *
+ * table: table to be filled.
+ * polynomial: polynomial for which table is to be filled.
+ * direction: bit order for which the table is to be filled.
+ */
+void crc8_create(u8 *table, u8 polynomial, enum crc8_direction direction)
+{
+	switch (direction) {
+	case crc8_dir_msb_first:
+		crc8_create_msb_first(table, polynomial);
+		break;
+	case crc8_dir_lsb_first:
+		crc8_create_lsb_first(table, polynomial);
+		break;
+	default:
+		pr_err("invalid direction provided\n");
+		return;
+	}
+}
+EXPORT_SYMBOL(crc8_create);
+
+/*
+ * crc8 - calculate a crc8 over the given input data.
+ *
+ * table: crc table used for calculation.
+ * pdata: pointer to data buffer.
+ * nbytes: number of bytes in data buffer.
+ * crc:	previous returned crc8 value.
+ */
+u8 crc8(u8 *table, u8 *pdata, uint nbytes, u8 crc)
+{
+	/* loop over the buffer data */
+	while (nbytes-- > 0)
+		crc = table[(crc ^ *pdata++) & 0xff];
+
+	return crc;
+}
+EXPORT_SYMBOL(crc8);
+
+MODULE_DESCRIPTION("CRC8 (by Williams, Ross N.) function");
+MODULE_AUTHOR("Broadcom Corporation");
+MODULE_LICENSE("Dual BSD/GPL");
-- 
1.7.4.1

Re: [RFC] lib: crc8: add new library module providing crc8 algorithm

[Arend van Spriel]

On 05/22/2011 10:59 AM, Nicolas Kaiser wrote:
> * "Arend van Spriel"<arend@broadcom.com>:
>> +/**
>> + * crc8() - calculate a crc8 over the given input data
>> + *
>> + * @pdata:	pointer to data buffer.
>> + * @nbytes:	number of bytes in data buffer.
>> + * @crc:	previous returned crc8 value.
>> + *
>> + * The CRC8 is calculated using the polynomial given below.
>> + *
>> + * x^8 + x^7 +x^6 + x^4 + x^2 + 1
>                   ^
> Could you possibly add a space here ...
>
>> +/*
>> + * table for crc8 calculation based on following polynomial:
>> + *	x^8 + x^7 +x^6 + x^4 + x^2 + 1
>                     ^
>             ... and here?
>
> Best regards,
> Nicolas Kaiser
>

Done. Will wait for some more feedback before posting a new version.

Gr. AvS

-- 
Almost nobody dances sober, unless they happen to be insane.
-- H.P. Lovecraft --

Re: [RFC] lib: crc8: add new library module providing crc8 algorithm

[Nicolas Kaiser]

* "Arend van Spriel" <arend@broadcom.com>:
> +/**
> + * crc8() - calculate a crc8 over the given input data
> + *
> + * @pdata:	pointer to data buffer.
> + * @nbytes:	number of bytes in data buffer.
> + * @crc:	previous returned crc8 value.
> + *
> + * The CRC8 is calculated using the polynomial given below.
> + *
> + * x^8 + x^7 +x^6 + x^4 + x^2 + 1
                 ^
Could you possibly add a space here ...

> +/*
> + * table for crc8 calculation based on following polynomial:
> + *	x^8 + x^7 +x^6 + x^4 + x^2 + 1
                   ^
           ... and here?

Best regards,
Nicolas Kaiser

[RFC] lib: crc8: add new library module providing crc8 algorithm

[Arend van Spriel]

The brcm80211 driver in staging tree uses a crc8 function. Based on
feedback from John Linville to move this to lib directory, the linux
source has been searched. Although there is currently only one other
kernel driver using this algorithm (ie. drivers/ssb) we are providing
this as a library function for others to use.

V1:
- functionality taken from brcm80211 utility function as is.
- documented the crc8 header file using kernel-doc syntax.
- compilation verified in-kernel and as module for x86, x86_64, arm, and mips.

V2:
- ran checkpatch after sending V1 (sorry for that mortal sin) so fixed that.

Cc: linux-kernel@vger.kernel.org
Cc: linux-wireless@vger.kernel.org
Cc: "John W. Linville" <linville@tuxdriver.com>
Cc: Dan Carpenter <error27@gmail.com>
Reviewed-by: Henry Ptasinski <henryp@broadcom.com>
Reviewed-by: Roland Vossen <rvossen@broadcom.com>
Reviewed-by: "Franky (Zhenhui) Lin" <frankyl@broadcom.com>
Signed-off-by: Arend van Spriel <arend@broadcom.com>
---
 include/linux/crc8.h |   61 +++++++++++++++++++++++++++++++++++++++
 lib/Kconfig          |    7 ++++
 lib/Makefile         |    1 +
 lib/crc8.c           |   77 ++++++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 146 insertions(+), 0 deletions(-)
 create mode 100644 include/linux/crc8.h
 create mode 100644 lib/crc8.c

diff --git a/include/linux/crc8.h b/include/linux/crc8.h
new file mode 100644
index 0000000..4048a34
--- /dev/null
+++ b/include/linux/crc8.h
@@ -0,0 +1,61 @@
+/*
+ * Copyright (c) 2011 Broadcom Corporation
+ *
+ * Permission to use, copy, modify, and/or distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
+ * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
+ * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
+ * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+#ifndef __CRC8_H_
+#define __CRC8_H_
+
+#include <linux/types.h>
+
+/**
+ * enum - CRC8 constants
+ *
+ * @CRC8_INIT_VALUE: Initial CRC8 checksum value
+ * @CRC8_GOOD_VALUE: Good final CRC8 checksum value
+ *
+ * Constants for the crc8() function. Refer to its
+ * documentation how to use these values.
+ */
+enum CRC8 {
+	CRC8_INIT_VALUE	= 0xff,
+	CRC8_GOOD_VALUE	= 0x9f
+};
+
+/**
+ * crc8() - calculate a crc8 over the given input data
+ *
+ * @pdata:	pointer to data buffer.
+ * @nbytes:	number of bytes in data buffer.
+ * @crc:	previous returned crc8 value.
+ *
+ * The CRC8 is calculated using the polynomial given below.
+ *
+ * x^8 + x^7 +x^6 + x^4 + x^2 + 1
+ *
+ * The caller provides the initial value (either %CRC8_INIT_VALUE
+ * or the previous returned value) to allow for processing of
+ * discontiguous blocks of data.  When generating the CRC the
+ * caller is responsible for complementing the final return value
+ * and inserting it into the byte stream.  When validating a byte
+ * stream (including CRC8), a final return value of %CRC8_GOOD_VALUE
+ * indicates the byte stream data can be considered valid.
+ *
+ * Reference:
+ * "A Painless Guide to CRC Error Detection Algorithms", ver 3, Aug 1993
+ * Williams, Ross N., ross<at>ross.net
+ * (see URL http://www.ross.net/crc/download/crc_v3.txt).
+ */
+u8 crc8(u8 *pdata, uint nbytes, u8 crc);
+
+#endif /* __CRC8_H_ */
diff --git a/lib/Kconfig b/lib/Kconfig
index 9c10e38..ff9e5a3 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -89,6 +89,13 @@ config LIBCRC32C
 	  require M here.  See Castagnoli93.
 	  Module will be libcrc32c.
 
+config CRC8
+	tristate "CRC8 function"
+	help
+	  This option provides CRC8 function. Drivers may select this
+	  when they need to do cyclic redundancy check according CRC8
+	  algorithm. Module will be called crc8.
+
 config AUDIT_GENERIC
 	bool
 	depends on AUDIT && !AUDIT_ARCH
diff --git a/lib/Makefile b/lib/Makefile
index 4b49a24..704959d 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -65,6 +65,7 @@ obj-$(CONFIG_CRC_ITU_T)	+= crc-itu-t.o
 obj-$(CONFIG_CRC32)	+= crc32.o
 obj-$(CONFIG_CRC7)	+= crc7.o
 obj-$(CONFIG_LIBCRC32C)	+= libcrc32c.o
+obj-$(CONFIG_CRC8)	+= crc8.o
 obj-$(CONFIG_GENERIC_ALLOCATOR) += genalloc.o
 
 obj-$(CONFIG_ZLIB_INFLATE) += zlib_inflate/
diff --git a/lib/crc8.c b/lib/crc8.c
new file mode 100644
index 0000000..342aeec
--- /dev/null
+++ b/lib/crc8.c
@@ -0,0 +1,77 @@
+/*
+ * Copyright (c) 2011 Broadcom Corporation
+ *
+ * Permission to use, copy, modify, and/or distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
+ * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
+ * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
+ * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+#include <linux/module.h>
+#include <linux/crc8.h>
+
+/*
+ * table for crc8 calculation based on following polynomial:
+ *	x^8 + x^7 +x^6 + x^4 + x^2 + 1
+ */
+static const u8 crc8_table[256] = {
+	0x00, 0xF7, 0xB9, 0x4E, 0x25, 0xD2, 0x9C, 0x6B,
+	0x4A, 0xBD, 0xF3, 0x04, 0x6F, 0x98, 0xD6, 0x21,
+	0x94, 0x63, 0x2D, 0xDA, 0xB1, 0x46, 0x08, 0xFF,
+	0xDE, 0x29, 0x67, 0x90, 0xFB, 0x0C, 0x42, 0xB5,
+	0x7F, 0x88, 0xC6, 0x31, 0x5A, 0xAD, 0xE3, 0x14,
+	0x35, 0xC2, 0x8C, 0x7B, 0x10, 0xE7, 0xA9, 0x5E,
+	0xEB, 0x1C, 0x52, 0xA5, 0xCE, 0x39, 0x77, 0x80,
+	0xA1, 0x56, 0x18, 0xEF, 0x84, 0x73, 0x3D, 0xCA,
+	0xFE, 0x09, 0x47, 0xB0, 0xDB, 0x2C, 0x62, 0x95,
+	0xB4, 0x43, 0x0D, 0xFA, 0x91, 0x66, 0x28, 0xDF,
+	0x6A, 0x9D, 0xD3, 0x24, 0x4F, 0xB8, 0xF6, 0x01,
+	0x20, 0xD7, 0x99, 0x6E, 0x05, 0xF2, 0xBC, 0x4B,
+	0x81, 0x76, 0x38, 0xCF, 0xA4, 0x53, 0x1D, 0xEA,
+	0xCB, 0x3C, 0x72, 0x85, 0xEE, 0x19, 0x57, 0xA0,
+	0x15, 0xE2, 0xAC, 0x5B, 0x30, 0xC7, 0x89, 0x7E,
+	0x5F, 0xA8, 0xE6, 0x11, 0x7A, 0x8D, 0xC3, 0x34,
+	0xAB, 0x5C, 0x12, 0xE5, 0x8E, 0x79, 0x37, 0xC0,
+	0xE1, 0x16, 0x58, 0xAF, 0xC4, 0x33, 0x7D, 0x8A,
+	0x3F, 0xC8, 0x86, 0x71, 0x1A, 0xED, 0xA3, 0x54,
+	0x75, 0x82, 0xCC, 0x3B, 0x50, 0xA7, 0xE9, 0x1E,
+	0xD4, 0x23, 0x6D, 0x9A, 0xF1, 0x06, 0x48, 0xBF,
+	0x9E, 0x69, 0x27, 0xD0, 0xBB, 0x4C, 0x02, 0xF5,
+	0x40, 0xB7, 0xF9, 0x0E, 0x65, 0x92, 0xDC, 0x2B,
+	0x0A, 0xFD, 0xB3, 0x44, 0x2F, 0xD8, 0x96, 0x61,
+	0x55, 0xA2, 0xEC, 0x1B, 0x70, 0x87, 0xC9, 0x3E,
+	0x1F, 0xE8, 0xA6, 0x51, 0x3A, 0xCD, 0x83, 0x74,
+	0xC1, 0x36, 0x78, 0x8F, 0xE4, 0x13, 0x5D, 0xAA,
+	0x8B, 0x7C, 0x32, 0xC5, 0xAE, 0x59, 0x17, 0xE0,
+	0x2A, 0xDD, 0x93, 0x64, 0x0F, 0xF8, 0xB6, 0x41,
+	0x60, 0x97, 0xD9, 0x2E, 0x45, 0xB2, 0xFC, 0x0B,
+	0xBE, 0x49, 0x07, 0xF0, 0x9B, 0x6C, 0x22, 0xD5,
+	0xF4, 0x03, 0x4D, 0xBA, 0xD1, 0x26, 0x68, 0x9F
+};
+
+/*
+ * crc8 - calculate a crc8 over the given input data
+ *
+ * pdata:	pointer to data buffer.
+ * nbytes:	number of bytes in data buffer.
+ * crc:	previous returned crc8 value.
+ */
+u8 crc8(u8 *pdata, uint nbytes, u8 crc)
+{
+	/* loop over the buffer data */
+	while (nbytes-- > 0)
+		crc = crc8_table[(crc ^ *pdata++) & 0xff];
+
+	return crc;
+}
+EXPORT_SYMBOL(crc8);
+
+MODULE_DESCRIPTION("CRC8 (by Williams, Ross N.) function");
+MODULE_AUTHOR("Broadcom Corporation");
+MODULE_LICENSE("Dual BSD/GPL");
-- 
1.7.4.1