1 /* crc32.c 2 Copyright (C) 2009-2018 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 70 static 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 143 Compute the 32-bit CRC of @var{buf} which has length @var{len}. The 144 starting value is @var{init}; this may be used to compute the CRC of 145 data split across multiple buffers by passing the return value of each 146 call as the @var{init} parameter of the next. 147 148 This is used by the @command{gdb} remote protocol for the @samp{qCRC} 149 command. In order to get the same results as gdb for a block of data, 150 you must pass the first CRC parameter as @code{0xffffffff}. 151 152 This 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 161 This differs from the "standard" CRC-32 algorithm in that the values 162 are not reflected, and there is no final XOR value. These differences 163 make it easy to compose the values of multiple blocks. 164 165 @end deftypefn 166 167 */ 168 169 unsigned int 170 xcrc32 (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