1 /*********************************************************************** 2 * * 3 * This software is part of the ast package * 4 * Copyright (c) 1996-2009 AT&T Intellectual Property * 5 * and is licensed under the * 6 * Common Public License, Version 1.0 * 7 * by AT&T Intellectual Property * 8 * * 9 * A copy of the License is available at * 10 * http://www.opensource.org/licenses/cpl1.0.txt * 11 * (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9) * 12 * * 13 * Information and Software Systems Research * 14 * AT&T Research * 15 * Florham Park NJ * 16 * * 17 * Glenn Fowler <gsf@research.att.com> * 18 * * 19 ***********************************************************************/ 20 #pragma prototyped 21 22 /* 23 * crc 24 */ 25 26 #define crc_description \ 27 "32 bit CRC (cyclic redundancy check)." 28 #define crc_options "\ 29 [+polynomial?The 32 bit crc polynomial bitmask with implicit bit 32.]:[mask:=0xedb88320]\ 30 [+done?XOR the final crc value with \anumber\a. 0xffffffff is used if \anumber\a is omitted.]:?[number:=0]\ 31 [+init?The initial crc value. 0xffffffff is used if \anumber\a is omitted.]:?[number:=0]\ 32 [+rotate?XOR each input character with the high order crc byte (instead of the low order).]\ 33 [+size?Include the total number of bytes in the crc. \anumber\a, if specified, is first XOR'd into the size.]:?[number:=0]\ 34 " 35 #define crc_match "crc" 36 #define crc_open crc_open 37 #define crc_print long_print 38 #define crc_data long_data 39 #define crc_scale 0 40 41 typedef uint32_t Crcnum_t; 42 43 typedef struct Crc_s 44 { 45 _SUM_PUBLIC_ 46 _SUM_PRIVATE_ 47 _INTEGRAL_PRIVATE_ 48 Crcnum_t init; 49 Crcnum_t done; 50 Crcnum_t xorsize; 51 const Crcnum_t *tab; /* use |const| to give the compiler a hint that the data won't change */ 52 Crcnum_t tabdata[256]; 53 unsigned int addsize; 54 unsigned int rotate; 55 } Crc_t; 56 57 #define CRC(p,s,c) (s = (s >> 8) ^ (p)->tab[(s ^ (c)) & 0xff]) 58 #define CRCROTATE(p,s,c) (s = (s << 8) ^ (p)->tab[((s >> 24) ^ (c)) & 0xff]) 59 60 static const 61 Crcnum_t posix_cksum_tab[256] = { 62 0x00000000U, 63 0x04c11db7U, 0x09823b6eU, 0x0d4326d9U, 0x130476dcU, 0x17c56b6bU, 64 0x1a864db2U, 0x1e475005U, 0x2608edb8U, 0x22c9f00fU, 0x2f8ad6d6U, 65 0x2b4bcb61U, 0x350c9b64U, 0x31cd86d3U, 0x3c8ea00aU, 0x384fbdbdU, 66 0x4c11db70U, 0x48d0c6c7U, 0x4593e01eU, 0x4152fda9U, 0x5f15adacU, 67 0x5bd4b01bU, 0x569796c2U, 0x52568b75U, 0x6a1936c8U, 0x6ed82b7fU, 68 0x639b0da6U, 0x675a1011U, 0x791d4014U, 0x7ddc5da3U, 0x709f7b7aU, 69 0x745e66cdU, 0x9823b6e0U, 0x9ce2ab57U, 0x91a18d8eU, 0x95609039U, 70 0x8b27c03cU, 0x8fe6dd8bU, 0x82a5fb52U, 0x8664e6e5U, 0xbe2b5b58U, 71 0xbaea46efU, 0xb7a96036U, 0xb3687d81U, 0xad2f2d84U, 0xa9ee3033U, 72 0xa4ad16eaU, 0xa06c0b5dU, 0xd4326d90U, 0xd0f37027U, 0xddb056feU, 73 0xd9714b49U, 0xc7361b4cU, 0xc3f706fbU, 0xceb42022U, 0xca753d95U, 74 0xf23a8028U, 0xf6fb9d9fU, 0xfbb8bb46U, 0xff79a6f1U, 0xe13ef6f4U, 75 0xe5ffeb43U, 0xe8bccd9aU, 0xec7dd02dU, 0x34867077U, 0x30476dc0U, 76 0x3d044b19U, 0x39c556aeU, 0x278206abU, 0x23431b1cU, 0x2e003dc5U, 77 0x2ac12072U, 0x128e9dcfU, 0x164f8078U, 0x1b0ca6a1U, 0x1fcdbb16U, 78 0x018aeb13U, 0x054bf6a4U, 0x0808d07dU, 0x0cc9cdcaU, 0x7897ab07U, 79 0x7c56b6b0U, 0x71159069U, 0x75d48ddeU, 0x6b93dddbU, 0x6f52c06cU, 80 0x6211e6b5U, 0x66d0fb02U, 0x5e9f46bfU, 0x5a5e5b08U, 0x571d7dd1U, 81 0x53dc6066U, 0x4d9b3063U, 0x495a2dd4U, 0x44190b0dU, 0x40d816baU, 82 0xaca5c697U, 0xa864db20U, 0xa527fdf9U, 0xa1e6e04eU, 0xbfa1b04bU, 83 0xbb60adfcU, 0xb6238b25U, 0xb2e29692U, 0x8aad2b2fU, 0x8e6c3698U, 84 0x832f1041U, 0x87ee0df6U, 0x99a95df3U, 0x9d684044U, 0x902b669dU, 85 0x94ea7b2aU, 0xe0b41de7U, 0xe4750050U, 0xe9362689U, 0xedf73b3eU, 86 0xf3b06b3bU, 0xf771768cU, 0xfa325055U, 0xfef34de2U, 0xc6bcf05fU, 87 0xc27dede8U, 0xcf3ecb31U, 0xcbffd686U, 0xd5b88683U, 0xd1799b34U, 88 0xdc3abdedU, 0xd8fba05aU, 0x690ce0eeU, 0x6dcdfd59U, 0x608edb80U, 89 0x644fc637U, 0x7a089632U, 0x7ec98b85U, 0x738aad5cU, 0x774bb0ebU, 90 0x4f040d56U, 0x4bc510e1U, 0x46863638U, 0x42472b8fU, 0x5c007b8aU, 91 0x58c1663dU, 0x558240e4U, 0x51435d53U, 0x251d3b9eU, 0x21dc2629U, 92 0x2c9f00f0U, 0x285e1d47U, 0x36194d42U, 0x32d850f5U, 0x3f9b762cU, 93 0x3b5a6b9bU, 0x0315d626U, 0x07d4cb91U, 0x0a97ed48U, 0x0e56f0ffU, 94 0x1011a0faU, 0x14d0bd4dU, 0x19939b94U, 0x1d528623U, 0xf12f560eU, 95 0xf5ee4bb9U, 0xf8ad6d60U, 0xfc6c70d7U, 0xe22b20d2U, 0xe6ea3d65U, 96 0xeba91bbcU, 0xef68060bU, 0xd727bbb6U, 0xd3e6a601U, 0xdea580d8U, 97 0xda649d6fU, 0xc423cd6aU, 0xc0e2d0ddU, 0xcda1f604U, 0xc960ebb3U, 98 0xbd3e8d7eU, 0xb9ff90c9U, 0xb4bcb610U, 0xb07daba7U, 0xae3afba2U, 99 0xaafbe615U, 0xa7b8c0ccU, 0xa379dd7bU, 0x9b3660c6U, 0x9ff77d71U, 100 0x92b45ba8U, 0x9675461fU, 0x8832161aU, 0x8cf30badU, 0x81b02d74U, 101 0x857130c3U, 0x5d8a9099U, 0x594b8d2eU, 0x5408abf7U, 0x50c9b640U, 102 0x4e8ee645U, 0x4a4ffbf2U, 0x470cdd2bU, 0x43cdc09cU, 0x7b827d21U, 103 0x7f436096U, 0x7200464fU, 0x76c15bf8U, 0x68860bfdU, 0x6c47164aU, 104 0x61043093U, 0x65c52d24U, 0x119b4be9U, 0x155a565eU, 0x18197087U, 105 0x1cd86d30U, 0x029f3d35U, 0x065e2082U, 0x0b1d065bU, 0x0fdc1becU, 106 0x3793a651U, 0x3352bbe6U, 0x3e119d3fU, 0x3ad08088U, 0x2497d08dU, 107 0x2056cd3aU, 0x2d15ebe3U, 0x29d4f654U, 0xc5a92679U, 0xc1683bceU, 108 0xcc2b1d17U, 0xc8ea00a0U, 0xd6ad50a5U, 0xd26c4d12U, 0xdf2f6bcbU, 109 0xdbee767cU, 0xe3a1cbc1U, 0xe760d676U, 0xea23f0afU, 0xeee2ed18U, 110 0xf0a5bd1dU, 0xf464a0aaU, 0xf9278673U, 0xfde69bc4U, 0x89b8fd09U, 111 0x8d79e0beU, 0x803ac667U, 0x84fbdbd0U, 0x9abc8bd5U, 0x9e7d9662U, 112 0x933eb0bbU, 0x97ffad0cU, 0xafb010b1U, 0xab710d06U, 0xa6322bdfU, 113 0xa2f33668U, 0xbcb4666dU, 0xb8757bdaU, 0xb5365d03U, 0xb1f740b4U 114 }; 115 116 static Sum_t* 117 crc_open(const Method_t* method, const char* name) 118 { 119 register Crc_t* sum; 120 register const char* s; 121 register const char* t; 122 register const char* v; 123 register int i; 124 register int j; 125 Crcnum_t polynomial; 126 Crcnum_t x; 127 128 if (sum = newof(0, Crc_t, 1, 0)) 129 { 130 sum->method = (Method_t*)method; 131 sum->name = name; 132 } 133 134 if(!strcmp(name, "crc-0x04c11db7-rotate-done-size")) 135 { 136 sum->init=0; 137 sum->done=0xffffffff; 138 sum->xorsize=0x0; 139 sum->addsize=0x1; 140 sum->rotate=1; 141 142 /* Optimized codepath for POSIX cksum to save startup time */ 143 sum->tab=posix_cksum_tab; 144 } 145 else 146 { 147 polynomial = 0xedb88320; 148 s = name; 149 while (*(t = s)) 150 { 151 for (t = s, v = 0; *s && *s != '-'; s++) 152 if (*s == '=' && !v) 153 v = s; 154 i = (v ? v : s) - t; 155 if (isdigit(*t) || v && i >= 4 && strneq(t, "poly", 4) && (t = v + 1)) 156 polynomial = strtoul(t, NiL, 0); 157 else if (strneq(t, "done", i)) 158 sum->done = v ? strtoul(v + 1, NiL, 0) : ~sum->done; 159 else if (strneq(t, "init", i)) 160 sum->init = v ? strtoul(v + 1, NiL, 0) : ~sum->init; 161 else if (strneq(t, "rotate", i)) 162 sum->rotate = 1; 163 else if (strneq(t, "size", i)) 164 { 165 sum->addsize = 1; 166 if (v) 167 sum->xorsize = strtoul(v + 1, NiL, 0); 168 } 169 if (*s == '-') 170 s++; 171 } 172 if (sum->rotate) 173 { 174 Crcnum_t t; 175 Crcnum_t p[8]; 176 177 p[0] = polynomial; 178 for (i = 1; i < 8; i++) 179 p[i] = (p[i-1] << 1) ^ ((p[i-1] & 0x80000000) ? polynomial : 0); 180 for (i = 0; i < elementsof(sum->tabdata); i++) 181 { 182 t = 0; 183 x = i; 184 for (j = 0; j < 8; j++) 185 { 186 if (x & 1) 187 t ^= p[j]; 188 x >>= 1; 189 } 190 sum->tabdata[i] = t; 191 } 192 } 193 else 194 { 195 for (i = 0; i < elementsof(sum->tabdata); i++) 196 { 197 x = i; 198 for (j = 0; j < 8; j++) 199 x = (x>>1) ^ ((x & 1) ? polynomial : 0); 200 sum->tabdata[i] = x; 201 } 202 } 203 204 sum->tab=sum->tabdata; 205 } 206 207 return (Sum_t*)sum; 208 } 209 210 static int 211 crc_init(Sum_t* p) 212 { 213 Crc_t* sum = (Crc_t*)p; 214 215 sum->sum = sum->init; 216 return 0; 217 } 218 219 #if defined(__SUNPRO_C) || defined(__GNUC__) 220 221 #if defined(__SUNPRO_C) 222 # include <sun_prefetch.h> 223 # define sum_prefetch(addr) sun_prefetch_read_many((void *)(addr)) 224 #elif defined(__GNUC__) 225 # define sum_prefetch(addr) __builtin_prefetch((addr), 0, 3) 226 #else 227 # error Unknown compiler 228 #endif 229 230 #define CBLOCK_SIZE (64) 231 #pragma unroll(16) 232 233 static int 234 crc_block(Sum_t* p, const void* s, size_t n) 235 { 236 Crc_t* sum = (Crc_t*)p; 237 register Crcnum_t c = sum->sum; 238 register const unsigned char* b = (const unsigned char*)s; 239 register const unsigned char* e = b + n; 240 unsigned short i; 241 242 sum_prefetch(b); 243 244 if (sum->rotate) 245 { 246 while (n > CBLOCK_SIZE) 247 { 248 sum_prefetch(b+CBLOCK_SIZE); 249 for(i=0 ; i < CBLOCK_SIZE ; i++) 250 { 251 CRCROTATE(sum, c, *b++); 252 } 253 254 n-=CBLOCK_SIZE; 255 } 256 257 while (b < e) 258 { 259 CRCROTATE(sum, c, *b++); 260 } 261 } 262 else 263 { 264 while (n > CBLOCK_SIZE) 265 { 266 sum_prefetch(b+CBLOCK_SIZE); 267 for(i=0 ; i < CBLOCK_SIZE ; i++) 268 { 269 CRC(sum, c, *b++); 270 } 271 272 n-=CBLOCK_SIZE; 273 } 274 275 while (b < e) 276 { 277 CRC(sum, c, *b++); 278 } 279 } 280 281 sum->sum = c; 282 return 0; 283 } 284 #else 285 static int 286 crc_block(Sum_t* p, const void* s, size_t n) 287 { 288 Crc_t* sum = (Crc_t*)p; 289 register Crcnum_t c = sum->sum; 290 register unsigned char* b = (unsigned char*)s; 291 register unsigned char* e = b + n; 292 293 if (sum->rotate) 294 while (b < e) 295 CRCROTATE(sum, c, *b++); 296 else 297 while (b < e) 298 CRC(sum, c, *b++); 299 sum->sum = c; 300 return 0; 301 } 302 #endif /* defined(__SUNPRO_C) || defined(__GNUC__) */ 303 304 static int 305 crc_done(Sum_t* p) 306 { 307 register Crc_t* sum = (Crc_t*)p; 308 register Crcnum_t c; 309 register uintmax_t n; 310 int i; 311 int j; 312 313 c = sum->sum; 314 if (sum->addsize) 315 { 316 n = sum->size ^ sum->xorsize; 317 if (sum->rotate) 318 while (n) 319 { 320 CRCROTATE(sum, c, n); 321 n >>= 8; 322 } 323 else 324 for (i = 0, j = 32; i < 4; i++) 325 { 326 j -= 8; 327 CRC(sum, c, n >> j); 328 } 329 } 330 sum->sum = c ^ sum->done; 331 sum->total_sum ^= (sum->sum &= 0xffffffff); 332 return 0; 333 } 334