1/*******************************************************************************
2 * $Id: crc.c,v 1.1.1.1 2008/10/15 03:31:34 james26_jang Exp $
3 * Copyright 2006, Broadcom Corporation
4 * All Rights Reserved.
5 *
6 * THIS SOFTWARE IS OFFERED "AS IS", AND BROADCOM GRANTS NO WARRANTIES OF ANY
7 * KIND, EXPRESS OR IMPLIED, BY STATUTE, COMMUNICATION OR OTHERWISE. BROADCOM
8 * SPECIFICALLY DISCLAIMS ANY IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS
9 * FOR A SPECIFIC PURPOSE OR NONINFRINGEMENT CONCERNING THIS SOFTWARE.
10 * crc.c: utility function to compute various CRCs
11 ******************************************************************************/
12
13#include "typedefs.h"
14#include "rts/crc.h"
15
16/*******************************************************************************
17 * hcs
18 *
19 * Computes and inserts a header check sum based on crc8 polynomial
20 * below.  Unlike a typical crc, the header check sum is inserted 13
21 * bytes from the end of the byte stream (rather than appended to the
22 * end of the byte stream) such that at the receiver a normal checksum
23 * computation over all of the bytes results in a known good value.
24 * Given a constant 12 bytes after the header checksum to the end of
25 * the header, a lookup table can be used to provide the actual value
26 * inserted.
27 ******************************************************************************/
28
29static uint8 hcs_table[8] = { 0x16, 0x2c, 0x58, 0xb0, 0x37, 0x6e, 0xdc, 0xef};
30
31void
32hcs(
33    uint8 *pheader, /* pointer to array of data to process */
34    uint nbytes   /* number of input data bytes to process */
35)
36{
37    uint8 hcs0, hcs1;
38    int i;
39
40    /* run once with zeros in hcs position, 13th byte from the end */
41    pheader[nbytes - 12 - 1] = 0;
42    hcs0 = crc8(pheader, nbytes, CRC8_INIT_VALUE);
43
44    /* now compute real hcs to insert in place of zeros */
45    hcs1 = 0;
46    for (i = 0; i < 8; i++) {
47        hcs1 ^= ((hcs0 & (1 << i)) != 0 ? hcs_table[i] : 0);
48    }
49    pheader[nbytes - 12 - 1] = hcs1 ^ 0xff;
50    return;
51}
52
53/*******************************************************************************
54 * crc8
55 *
56 * Computes a crc8 over the input data using the polynomial:
57 *
58 *       x^8 + x^7 +x^6 + x^4 + x^2 + 1
59 *
60 * The caller provides the initial value (either CRC8_INIT_VALUE
61 * or the previous returned value) to allow for processing of
62 * discontiguous blocks of data.  When generating the CRC the
63 * caller is responsible for complementing the final return value
64 * and inserting it into the byte stream.  When checking, a final
65 * return value of CRC8_GOOD_VALUE indicates a valid CRC.
66 *
67 * Reference: Dallas Semiconductor Application Note 27
68 *   Williams, Ross N., "A Painless Guide to CRC Error Detection Algorithms",
69 *     ver 3, Aug 1993, ross@guest.adelaide.edu.au, Rocksoft Pty Ltd.,
70 *     ftp://ftp.rocksoft.com/clients/rocksoft/papers/crc_v3.txt
71 *
72 ******************************************************************************/
73
74static uint8 crc8_table[256] = {
75    0x00, 0xF7, 0xB9, 0x4E, 0x25, 0xD2, 0x9C, 0x6B,
76    0x4A, 0xBD, 0xF3, 0x04, 0x6F, 0x98, 0xD6, 0x21,
77    0x94, 0x63, 0x2D, 0xDA, 0xB1, 0x46, 0x08, 0xFF,
78    0xDE, 0x29, 0x67, 0x90, 0xFB, 0x0C, 0x42, 0xB5,
79    0x7F, 0x88, 0xC6, 0x31, 0x5A, 0xAD, 0xE3, 0x14,
80    0x35, 0xC2, 0x8C, 0x7B, 0x10, 0xE7, 0xA9, 0x5E,
81    0xEB, 0x1C, 0x52, 0xA5, 0xCE, 0x39, 0x77, 0x80,
82    0xA1, 0x56, 0x18, 0xEF, 0x84, 0x73, 0x3D, 0xCA,
83    0xFE, 0x09, 0x47, 0xB0, 0xDB, 0x2C, 0x62, 0x95,
84    0xB4, 0x43, 0x0D, 0xFA, 0x91, 0x66, 0x28, 0xDF,
85    0x6A, 0x9D, 0xD3, 0x24, 0x4F, 0xB8, 0xF6, 0x01,
86    0x20, 0xD7, 0x99, 0x6E, 0x05, 0xF2, 0xBC, 0x4B,
87    0x81, 0x76, 0x38, 0xCF, 0xA4, 0x53, 0x1D, 0xEA,
88    0xCB, 0x3C, 0x72, 0x85, 0xEE, 0x19, 0x57, 0xA0,
89    0x15, 0xE2, 0xAC, 0x5B, 0x30, 0xC7, 0x89, 0x7E,
90    0x5F, 0xA8, 0xE6, 0x11, 0x7A, 0x8D, 0xC3, 0x34,
91    0xAB, 0x5C, 0x12, 0xE5, 0x8E, 0x79, 0x37, 0xC0,
92    0xE1, 0x16, 0x58, 0xAF, 0xC4, 0x33, 0x7D, 0x8A,
93    0x3F, 0xC8, 0x86, 0x71, 0x1A, 0xED, 0xA3, 0x54,
94    0x75, 0x82, 0xCC, 0x3B, 0x50, 0xA7, 0xE9, 0x1E,
95    0xD4, 0x23, 0x6D, 0x9A, 0xF1, 0x06, 0x48, 0xBF,
96    0x9E, 0x69, 0x27, 0xD0, 0xBB, 0x4C, 0x02, 0xF5,
97    0x40, 0xB7, 0xF9, 0x0E, 0x65, 0x92, 0xDC, 0x2B,
98    0x0A, 0xFD, 0xB3, 0x44, 0x2F, 0xD8, 0x96, 0x61,
99    0x55, 0xA2, 0xEC, 0x1B, 0x70, 0x87, 0xC9, 0x3E,
100    0x1F, 0xE8, 0xA6, 0x51, 0x3A, 0xCD, 0x83, 0x74,
101    0xC1, 0x36, 0x78, 0x8F, 0xE4, 0x13, 0x5D, 0xAA,
102    0x8B, 0x7C, 0x32, 0xC5, 0xAE, 0x59, 0x17, 0xE0,
103    0x2A, 0xDD, 0x93, 0x64, 0x0F, 0xF8, 0xB6, 0x41,
104    0x60, 0x97, 0xD9, 0x2E, 0x45, 0xB2, 0xFC, 0x0B,
105    0xBE, 0x49, 0x07, 0xF0, 0x9B, 0x6C, 0x22, 0xD5,
106    0xF4, 0x03, 0x4D, 0xBA, 0xD1, 0x26, 0x68, 0x9F
107};
108
109#define CRC_INNER_LOOP(n, c, x) \
110    (c) = ((c) >> 8) ^ crc##n##_table[((c) ^ (x)) & 0xff]
111
112uint8
113crc8(
114    uint8 *pdata,  /* pointer to array of data to process */
115    uint nbytes, /* number of input data bytes to process */
116    uint8 crc      /* either CRC8_INIT_VALUE or previous return value */
117)
118{
119    while (nbytes-- > 0)
120        CRC_INNER_LOOP(8, crc, *pdata++);
121    return crc;
122}
123
124/*******************************************************************************
125 * crc16
126 *
127 * Computes a crc16 over the input data using the polynomial:
128 *
129 *       x^16 + x^12 +x^5 + 1
130 *
131 * The caller provides the initial value (either CRC16_INIT_VALUE
132 * or the previous returned value) to allow for processing of
133 * discontiguous blocks of data.  When generating the CRC the
134 * caller is responsible for complementing the final return value
135 * and inserting it into the byte stream.  When checking, a final
136 * return value of CRC16_GOOD_VALUE indicates a valid CRC.
137 *
138 * Reference: Dallas Semiconductor Application Note 27
139 *   Williams, Ross N., "A Painless Guide to CRC Error Detection Algorithms",
140 *     ver 3, Aug 1993, ross@guest.adelaide.edu.au, Rocksoft Pty Ltd.,
141 *     ftp://ftp.rocksoft.com/clients/rocksoft/papers/crc_v3.txt
142 *
143 ******************************************************************************/
144
145static uint16 crc16_table[256] = {
146    0x0000, 0x1189, 0x2312, 0x329B, 0x4624, 0x57AD, 0x6536, 0x74BF,
147    0x8C48, 0x9DC1, 0xAF5A, 0xBED3, 0xCA6C, 0xDBE5, 0xE97E, 0xF8F7,
148    0x1081, 0x0108, 0x3393, 0x221A, 0x56A5, 0x472C, 0x75B7, 0x643E,
149    0x9CC9, 0x8D40, 0xBFDB, 0xAE52, 0xDAED, 0xCB64, 0xF9FF, 0xE876,
150    0x2102, 0x308B, 0x0210, 0x1399, 0x6726, 0x76AF, 0x4434, 0x55BD,
151    0xAD4A, 0xBCC3, 0x8E58, 0x9FD1, 0xEB6E, 0xFAE7, 0xC87C, 0xD9F5,
152    0x3183, 0x200A, 0x1291, 0x0318, 0x77A7, 0x662E, 0x54B5, 0x453C,
153    0xBDCB, 0xAC42, 0x9ED9, 0x8F50, 0xFBEF, 0xEA66, 0xD8FD, 0xC974,
154    0x4204, 0x538D, 0x6116, 0x709F, 0x0420, 0x15A9, 0x2732, 0x36BB,
155    0xCE4C, 0xDFC5, 0xED5E, 0xFCD7, 0x8868, 0x99E1, 0xAB7A, 0xBAF3,
156    0x5285, 0x430C, 0x7197, 0x601E, 0x14A1, 0x0528, 0x37B3, 0x263A,
157    0xDECD, 0xCF44, 0xFDDF, 0xEC56, 0x98E9, 0x8960, 0xBBFB, 0xAA72,
158    0x6306, 0x728F, 0x4014, 0x519D, 0x2522, 0x34AB, 0x0630, 0x17B9,
159    0xEF4E, 0xFEC7, 0xCC5C, 0xDDD5, 0xA96A, 0xB8E3, 0x8A78, 0x9BF1,
160    0x7387, 0x620E, 0x5095, 0x411C, 0x35A3, 0x242A, 0x16B1, 0x0738,
161    0xFFCF, 0xEE46, 0xDCDD, 0xCD54, 0xB9EB, 0xA862, 0x9AF9, 0x8B70,
162    0x8408, 0x9581, 0xA71A, 0xB693, 0xC22C, 0xD3A5, 0xE13E, 0xF0B7,
163    0x0840, 0x19C9, 0x2B52, 0x3ADB, 0x4E64, 0x5FED, 0x6D76, 0x7CFF,
164    0x9489, 0x8500, 0xB79B, 0xA612, 0xD2AD, 0xC324, 0xF1BF, 0xE036,
165    0x18C1, 0x0948, 0x3BD3, 0x2A5A, 0x5EE5, 0x4F6C, 0x7DF7, 0x6C7E,
166    0xA50A, 0xB483, 0x8618, 0x9791, 0xE32E, 0xF2A7, 0xC03C, 0xD1B5,
167    0x2942, 0x38CB, 0x0A50, 0x1BD9, 0x6F66, 0x7EEF, 0x4C74, 0x5DFD,
168    0xB58B, 0xA402, 0x9699, 0x8710, 0xF3AF, 0xE226, 0xD0BD, 0xC134,
169    0x39C3, 0x284A, 0x1AD1, 0x0B58, 0x7FE7, 0x6E6E, 0x5CF5, 0x4D7C,
170    0xC60C, 0xD785, 0xE51E, 0xF497, 0x8028, 0x91A1, 0xA33A, 0xB2B3,
171    0x4A44, 0x5BCD, 0x6956, 0x78DF, 0x0C60, 0x1DE9, 0x2F72, 0x3EFB,
172    0xD68D, 0xC704, 0xF59F, 0xE416, 0x90A9, 0x8120, 0xB3BB, 0xA232,
173    0x5AC5, 0x4B4C, 0x79D7, 0x685E, 0x1CE1, 0x0D68, 0x3FF3, 0x2E7A,
174    0xE70E, 0xF687, 0xC41C, 0xD595, 0xA12A, 0xB0A3, 0x8238, 0x93B1,
175    0x6B46, 0x7ACF, 0x4854, 0x59DD, 0x2D62, 0x3CEB, 0x0E70, 0x1FF9,
176    0xF78F, 0xE606, 0xD49D, 0xC514, 0xB1AB, 0xA022, 0x92B9, 0x8330,
177    0x7BC7, 0x6A4E, 0x58D5, 0x495C, 0x3DE3, 0x2C6A, 0x1EF1, 0x0F78
178};
179
180uint16
181crc16(
182    uint8 *pdata,  /* pointer to array of data to process */
183    uint nbytes, /* number of input data bytes to process */
184    uint16 crc     /* either CRC16_INIT_VALUE or previous return value */
185)
186{
187    while (nbytes-- > 0)
188        CRC_INNER_LOOP(16, crc, *pdata++);
189    return crc;
190}
191
192/*******************************************************************************
193 * crc32
194 *
195 * Computes a crc32 over the input data using the polynomial:
196 *
197 *       x^32+x^26+x^23+x^22+x^16+x^12+x^11+X^10+x^8+x^7+x^5+x^4+x^2+x+1
198 *
199 * The caller provides the initial value (either CRC32_INIT_VALUE
200 * or the previous returned value) to allow for processing of
201 * discontiguous blocks of data.  When generating the CRC the
202 * caller is responsible for complementing the final return value
203 * and inserting it into the byte stream.  When checking, a final
204 * return value of CRC32_GOOD_VALUE indicates a valid CRC.
205 *
206 * Reference: Dallas Semiconductor Application Note 27
207 *   Williams, Ross N., "A Painless Guide to CRC Error Detection Algorithms",
208 *     ver 3, Aug 1993, ross@guest.adelaide.edu.au, Rocksoft Pty Ltd.,
209 *     ftp://ftp.rocksoft.com/clients/rocksoft/papers/crc_v3.txt
210 *
211 ******************************************************************************/
212
213static uint32 crc32_table[256] = {
214    0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA,
215    0x076DC419, 0x706AF48F, 0xE963A535, 0x9E6495A3,
216    0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988,
217    0x09B64C2B, 0x7EB17CBD, 0xE7B82D07, 0x90BF1D91,
218    0x1DB71064, 0x6AB020F2, 0xF3B97148, 0x84BE41DE,
219    0x1ADAD47D, 0x6DDDE4EB, 0xF4D4B551, 0x83D385C7,
220    0x136C9856, 0x646BA8C0, 0xFD62F97A, 0x8A65C9EC,
221    0x14015C4F, 0x63066CD9, 0xFA0F3D63, 0x8D080DF5,
222    0x3B6E20C8, 0x4C69105E, 0xD56041E4, 0xA2677172,
223    0x3C03E4D1, 0x4B04D447, 0xD20D85FD, 0xA50AB56B,
224    0x35B5A8FA, 0x42B2986C, 0xDBBBC9D6, 0xACBCF940,
225    0x32D86CE3, 0x45DF5C75, 0xDCD60DCF, 0xABD13D59,
226    0x26D930AC, 0x51DE003A, 0xC8D75180, 0xBFD06116,
227    0x21B4F4B5, 0x56B3C423, 0xCFBA9599, 0xB8BDA50F,
228    0x2802B89E, 0x5F058808, 0xC60CD9B2, 0xB10BE924,
229    0x2F6F7C87, 0x58684C11, 0xC1611DAB, 0xB6662D3D,
230    0x76DC4190, 0x01DB7106, 0x98D220BC, 0xEFD5102A,
231    0x71B18589, 0x06B6B51F, 0x9FBFE4A5, 0xE8B8D433,
232    0x7807C9A2, 0x0F00F934, 0x9609A88E, 0xE10E9818,
233    0x7F6A0DBB, 0x086D3D2D, 0x91646C97, 0xE6635C01,
234    0x6B6B51F4, 0x1C6C6162, 0x856530D8, 0xF262004E,
235    0x6C0695ED, 0x1B01A57B, 0x8208F4C1, 0xF50FC457,
236    0x65B0D9C6, 0x12B7E950, 0x8BBEB8EA, 0xFCB9887C,
237    0x62DD1DDF, 0x15DA2D49, 0x8CD37CF3, 0xFBD44C65,
238    0x4DB26158, 0x3AB551CE, 0xA3BC0074, 0xD4BB30E2,
239    0x4ADFA541, 0x3DD895D7, 0xA4D1C46D, 0xD3D6F4FB,
240    0x4369E96A, 0x346ED9FC, 0xAD678846, 0xDA60B8D0,
241    0x44042D73, 0x33031DE5, 0xAA0A4C5F, 0xDD0D7CC9,
242    0x5005713C, 0x270241AA, 0xBE0B1010, 0xC90C2086,
243    0x5768B525, 0x206F85B3, 0xB966D409, 0xCE61E49F,
244    0x5EDEF90E, 0x29D9C998, 0xB0D09822, 0xC7D7A8B4,
245    0x59B33D17, 0x2EB40D81, 0xB7BD5C3B, 0xC0BA6CAD,
246    0xEDB88320, 0x9ABFB3B6, 0x03B6E20C, 0x74B1D29A,
247    0xEAD54739, 0x9DD277AF, 0x04DB2615, 0x73DC1683,
248    0xE3630B12, 0x94643B84, 0x0D6D6A3E, 0x7A6A5AA8,
249    0xE40ECF0B, 0x9309FF9D, 0x0A00AE27, 0x7D079EB1,
250    0xF00F9344, 0x8708A3D2, 0x1E01F268, 0x6906C2FE,
251    0xF762575D, 0x806567CB, 0x196C3671, 0x6E6B06E7,
252    0xFED41B76, 0x89D32BE0, 0x10DA7A5A, 0x67DD4ACC,
253    0xF9B9DF6F, 0x8EBEEFF9, 0x17B7BE43, 0x60B08ED5,
254    0xD6D6A3E8, 0xA1D1937E, 0x38D8C2C4, 0x4FDFF252,
255    0xD1BB67F1, 0xA6BC5767, 0x3FB506DD, 0x48B2364B,
256    0xD80D2BDA, 0xAF0A1B4C, 0x36034AF6, 0x41047A60,
257    0xDF60EFC3, 0xA867DF55, 0x316E8EEF, 0x4669BE79,
258    0xCB61B38C, 0xBC66831A, 0x256FD2A0, 0x5268E236,
259    0xCC0C7795, 0xBB0B4703, 0x220216B9, 0x5505262F,
260    0xC5BA3BBE, 0xB2BD0B28, 0x2BB45A92, 0x5CB36A04,
261    0xC2D7FFA7, 0xB5D0CF31, 0x2CD99E8B, 0x5BDEAE1D,
262    0x9B64C2B0, 0xEC63F226, 0x756AA39C, 0x026D930A,
263    0x9C0906A9, 0xEB0E363F, 0x72076785, 0x05005713,
264    0x95BF4A82, 0xE2B87A14, 0x7BB12BAE, 0x0CB61B38,
265    0x92D28E9B, 0xE5D5BE0D, 0x7CDCEFB7, 0x0BDBDF21,
266    0x86D3D2D4, 0xF1D4E242, 0x68DDB3F8, 0x1FDA836E,
267    0x81BE16CD, 0xF6B9265B, 0x6FB077E1, 0x18B74777,
268    0x88085AE6, 0xFF0F6A70, 0x66063BCA, 0x11010B5C,
269    0x8F659EFF, 0xF862AE69, 0x616BFFD3, 0x166CCF45,
270    0xA00AE278, 0xD70DD2EE, 0x4E048354, 0x3903B3C2,
271    0xA7672661, 0xD06016F7, 0x4969474D, 0x3E6E77DB,
272    0xAED16A4A, 0xD9D65ADC, 0x40DF0B66, 0x37D83BF0,
273    0xA9BCAE53, 0xDEBB9EC5, 0x47B2CF7F, 0x30B5FFE9,
274    0xBDBDF21C, 0xCABAC28A, 0x53B39330, 0x24B4A3A6,
275    0xBAD03605, 0xCDD70693, 0x54DE5729, 0x23D967BF,
276    0xB3667A2E, 0xC4614AB8, 0x5D681B02, 0x2A6F2B94,
277    0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D
278};
279
280uint32
281crc32(
282    uint8 *pdata,  /* pointer to array of data to process */
283    uint nbytes, /* number of input data bytes to process */
284    uint32 crc     /* either CRC32_INIT_VALUE or previous return value */
285)
286{
287    while (nbytes-- > 0)
288        CRC_INNER_LOOP(32, crc, *pdata++);
289    return crc;
290}
291