1/* crc32.c
2   Copyright (C) 2009, 2011 Free Software Foundation, Inc.
3
4   This file is part of the libiberty library.
5
6   This file is free software; you can redistribute it and/or modify
7   it under the terms of the GNU General Public License as published by
8   the Free Software Foundation; either version 2 of the License, or
9   (at your option) any later version.
10
11   In addition to the permissions in the GNU General Public License, the
12   Free Software Foundation gives you unlimited permission to link the
13   compiled version of this file into combinations with other programs,
14   and to distribute those combinations without any restriction coming
15   from the use of this file.  (The General Public License restrictions
16   do apply in other respects; for example, they cover modification of
17   the file, and distribution when not linked into a combined
18   executable.)
19
20   This program is distributed in the hope that it will be useful,
21   but WITHOUT ANY WARRANTY; without even the implied warranty of
22   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
23   GNU General Public License for more details.
24
25   You should have received a copy of the GNU General Public License
26   along with this program; if not, write to the Free Software
27   Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA 02110-1301, USA.
28*/
29
30#ifdef HAVE_CONFIG_H
31#include "config.h"
32#endif
33
34#include "libiberty.h"
35
36/* This table was generated by the following program.
37
38   #include <stdio.h>
39
40   int
41   main ()
42   {
43     unsigned int i, j;
44     unsigned int c;
45     int table[256];
46
47     for (i = 0; i < 256; i++)
48       {
49	 for (c = i << 24, j = 8; j > 0; --j)
50	   c = c & 0x80000000 ? (c << 1) ^ 0x04c11db7 : (c << 1);
51	 table[i] = c;
52       }
53
54     printf ("static const unsigned int crc32_table[] =\n{\n");
55     for (i = 0; i < 256; i += 4)
56       {
57	 printf ("  0x%08x, 0x%08x, 0x%08x, 0x%08x",
58		 table[i + 0], table[i + 1], table[i + 2], table[i + 3]);
59	 if (i + 4 < 256)
60	   putchar (',');
61	 putchar ('\n');
62       }
63     printf ("};\n");
64     return 0;
65   }
66
67   For more information on CRC, see, e.g.,
68   http://www.ross.net/crc/download/crc_v3.txt.  */
69
70static const unsigned int crc32_table[] =
71{
72  0x00000000, 0x04c11db7, 0x09823b6e, 0x0d4326d9,
73  0x130476dc, 0x17c56b6b, 0x1a864db2, 0x1e475005,
74  0x2608edb8, 0x22c9f00f, 0x2f8ad6d6, 0x2b4bcb61,
75  0x350c9b64, 0x31cd86d3, 0x3c8ea00a, 0x384fbdbd,
76  0x4c11db70, 0x48d0c6c7, 0x4593e01e, 0x4152fda9,
77  0x5f15adac, 0x5bd4b01b, 0x569796c2, 0x52568b75,
78  0x6a1936c8, 0x6ed82b7f, 0x639b0da6, 0x675a1011,
79  0x791d4014, 0x7ddc5da3, 0x709f7b7a, 0x745e66cd,
80  0x9823b6e0, 0x9ce2ab57, 0x91a18d8e, 0x95609039,
81  0x8b27c03c, 0x8fe6dd8b, 0x82a5fb52, 0x8664e6e5,
82  0xbe2b5b58, 0xbaea46ef, 0xb7a96036, 0xb3687d81,
83  0xad2f2d84, 0xa9ee3033, 0xa4ad16ea, 0xa06c0b5d,
84  0xd4326d90, 0xd0f37027, 0xddb056fe, 0xd9714b49,
85  0xc7361b4c, 0xc3f706fb, 0xceb42022, 0xca753d95,
86  0xf23a8028, 0xf6fb9d9f, 0xfbb8bb46, 0xff79a6f1,
87  0xe13ef6f4, 0xe5ffeb43, 0xe8bccd9a, 0xec7dd02d,
88  0x34867077, 0x30476dc0, 0x3d044b19, 0x39c556ae,
89  0x278206ab, 0x23431b1c, 0x2e003dc5, 0x2ac12072,
90  0x128e9dcf, 0x164f8078, 0x1b0ca6a1, 0x1fcdbb16,
91  0x018aeb13, 0x054bf6a4, 0x0808d07d, 0x0cc9cdca,
92  0x7897ab07, 0x7c56b6b0, 0x71159069, 0x75d48dde,
93  0x6b93dddb, 0x6f52c06c, 0x6211e6b5, 0x66d0fb02,
94  0x5e9f46bf, 0x5a5e5b08, 0x571d7dd1, 0x53dc6066,
95  0x4d9b3063, 0x495a2dd4, 0x44190b0d, 0x40d816ba,
96  0xaca5c697, 0xa864db20, 0xa527fdf9, 0xa1e6e04e,
97  0xbfa1b04b, 0xbb60adfc, 0xb6238b25, 0xb2e29692,
98  0x8aad2b2f, 0x8e6c3698, 0x832f1041, 0x87ee0df6,
99  0x99a95df3, 0x9d684044, 0x902b669d, 0x94ea7b2a,
100  0xe0b41de7, 0xe4750050, 0xe9362689, 0xedf73b3e,
101  0xf3b06b3b, 0xf771768c, 0xfa325055, 0xfef34de2,
102  0xc6bcf05f, 0xc27dede8, 0xcf3ecb31, 0xcbffd686,
103  0xd5b88683, 0xd1799b34, 0xdc3abded, 0xd8fba05a,
104  0x690ce0ee, 0x6dcdfd59, 0x608edb80, 0x644fc637,
105  0x7a089632, 0x7ec98b85, 0x738aad5c, 0x774bb0eb,
106  0x4f040d56, 0x4bc510e1, 0x46863638, 0x42472b8f,
107  0x5c007b8a, 0x58c1663d, 0x558240e4, 0x51435d53,
108  0x251d3b9e, 0x21dc2629, 0x2c9f00f0, 0x285e1d47,
109  0x36194d42, 0x32d850f5, 0x3f9b762c, 0x3b5a6b9b,
110  0x0315d626, 0x07d4cb91, 0x0a97ed48, 0x0e56f0ff,
111  0x1011a0fa, 0x14d0bd4d, 0x19939b94, 0x1d528623,
112  0xf12f560e, 0xf5ee4bb9, 0xf8ad6d60, 0xfc6c70d7,
113  0xe22b20d2, 0xe6ea3d65, 0xeba91bbc, 0xef68060b,
114  0xd727bbb6, 0xd3e6a601, 0xdea580d8, 0xda649d6f,
115  0xc423cd6a, 0xc0e2d0dd, 0xcda1f604, 0xc960ebb3,
116  0xbd3e8d7e, 0xb9ff90c9, 0xb4bcb610, 0xb07daba7,
117  0xae3afba2, 0xaafbe615, 0xa7b8c0cc, 0xa379dd7b,
118  0x9b3660c6, 0x9ff77d71, 0x92b45ba8, 0x9675461f,
119  0x8832161a, 0x8cf30bad, 0x81b02d74, 0x857130c3,
120  0x5d8a9099, 0x594b8d2e, 0x5408abf7, 0x50c9b640,
121  0x4e8ee645, 0x4a4ffbf2, 0x470cdd2b, 0x43cdc09c,
122  0x7b827d21, 0x7f436096, 0x7200464f, 0x76c15bf8,
123  0x68860bfd, 0x6c47164a, 0x61043093, 0x65c52d24,
124  0x119b4be9, 0x155a565e, 0x18197087, 0x1cd86d30,
125  0x029f3d35, 0x065e2082, 0x0b1d065b, 0x0fdc1bec,
126  0x3793a651, 0x3352bbe6, 0x3e119d3f, 0x3ad08088,
127  0x2497d08d, 0x2056cd3a, 0x2d15ebe3, 0x29d4f654,
128  0xc5a92679, 0xc1683bce, 0xcc2b1d17, 0xc8ea00a0,
129  0xd6ad50a5, 0xd26c4d12, 0xdf2f6bcb, 0xdbee767c,
130  0xe3a1cbc1, 0xe760d676, 0xea23f0af, 0xeee2ed18,
131  0xf0a5bd1d, 0xf464a0aa, 0xf9278673, 0xfde69bc4,
132  0x89b8fd09, 0x8d79e0be, 0x803ac667, 0x84fbdbd0,
133  0x9abc8bd5, 0x9e7d9662, 0x933eb0bb, 0x97ffad0c,
134  0xafb010b1, 0xab710d06, 0xa6322bdf, 0xa2f33668,
135  0xbcb4666d, 0xb8757bda, 0xb5365d03, 0xb1f740b4
136};
137
138/*
139
140@deftypefn Extension {unsigned int} crc32 (const unsigned char *@var{buf}, @
141  int @var{len}, unsigned int @var{init})
142
143Compute the 32-bit CRC of @var{buf} which has length @var{len}.  The
144starting value is @var{init}; this may be used to compute the CRC of
145data split across multiple buffers by passing the return value of each
146call as the @var{init} parameter of the next.
147
148This is used by the @command{gdb} remote protocol for the @samp{qCRC}
149command.  In order to get the same results as gdb for a block of data,
150you must pass the first CRC parameter as @code{0xffffffff}.
151
152This CRC can be specified as:
153
154  Width  : 32
155  Poly   : 0x04c11db7
156  Init   : parameter, typically 0xffffffff
157  RefIn  : false
158  RefOut : false
159  XorOut : 0
160
161This differs from the "standard" CRC-32 algorithm in that the values
162are not reflected, and there is no final XOR value.  These differences
163make it easy to compose the values of multiple blocks.
164
165@end deftypefn
166
167*/
168
169unsigned int
170xcrc32 (const unsigned char *buf, int len, unsigned int init)
171{
172  unsigned int crc = init;
173  while (len--)
174    {
175      crc = (crc << 8) ^ crc32_table[((crc >> 24) ^ *buf) & 255];
176      buf++;
177    }
178  return crc;
179}
180