1 /*********************************************************************** 2 * * 3 * This software is part of the ast package * 4 * Copyright (c) 1996-2008 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 Crcnum_t tab[256]; 52 unsigned int addsize; 53 unsigned int rotate; 54 } Crc_t; 55 56 #define CRC(p,s,c) (s = (s >> 8) ^ (p)->tab[(s ^ (c)) & 0xff]) 57 #define CRCROTATE(p,s,c) (s = (s << 8) ^ (p)->tab[((s >> 24) ^ (c)) & 0xff]) 58 59 static Sum_t* 60 crc_open(const Method_t* method, const char* name) 61 { 62 register Crc_t* sum; 63 register const char* s; 64 register const char* t; 65 register const char* v; 66 register int i; 67 register int j; 68 Crcnum_t polynomial; 69 Crcnum_t x; 70 71 if (sum = newof(0, Crc_t, 1, 0)) 72 { 73 sum->method = (Method_t*)method; 74 sum->name = name; 75 } 76 polynomial = 0xedb88320; 77 s = name; 78 while (*(t = s)) 79 { 80 for (t = s, v = 0; *s && *s != '-'; s++) 81 if (*s == '=' && !v) 82 v = s; 83 i = (v ? v : s) - t; 84 if (isdigit(*t) || v && i >= 4 && strneq(t, "poly", 4) && (t = v + 1)) 85 polynomial = strtoul(t, NiL, 0); 86 else if (strneq(t, "done", i)) 87 sum->done = v ? strtoul(v + 1, NiL, 0) : ~sum->done; 88 else if (strneq(t, "init", i)) 89 sum->init = v ? strtoul(v + 1, NiL, 0) : ~sum->init; 90 else if (strneq(t, "rotate", i)) 91 sum->rotate = 1; 92 else if (strneq(t, "size", i)) 93 { 94 sum->addsize = 1; 95 if (v) 96 sum->xorsize = strtoul(v + 1, NiL, 0); 97 } 98 if (*s == '-') 99 s++; 100 } 101 if (sum->rotate) 102 { 103 Crcnum_t t; 104 Crcnum_t p[8]; 105 106 p[0] = polynomial; 107 for (i = 1; i < 8; i++) 108 p[i] = (p[i-1] << 1) ^ ((p[i-1] & 0x80000000) ? polynomial : 0); 109 for (i = 0; i < elementsof(sum->tab); i++) 110 { 111 t = 0; 112 x = i; 113 for (j = 0; j < 8; j++) 114 { 115 if (x & 1) 116 t ^= p[j]; 117 x >>= 1; 118 } 119 sum->tab[i] = t; 120 } 121 } 122 else 123 { 124 for (i = 0; i < elementsof(sum->tab); i++) 125 { 126 x = i; 127 for (j = 0; j < 8; j++) 128 x = (x>>1) ^ ((x & 1) ? polynomial : 0); 129 sum->tab[i] = x; 130 } 131 } 132 return (Sum_t*)sum; 133 } 134 135 static int 136 crc_init(Sum_t* p) 137 { 138 Crc_t* sum = (Crc_t*)p; 139 140 sum->sum = sum->init; 141 return 0; 142 } 143 144 static int 145 crc_block(Sum_t* p, const void* s, size_t n) 146 { 147 Crc_t* sum = (Crc_t*)p; 148 register Crcnum_t c = sum->sum; 149 register unsigned char* b = (unsigned char*)s; 150 register unsigned char* e = b + n; 151 152 if (sum->rotate) 153 while (b < e) 154 CRCROTATE(sum, c, *b++); 155 else 156 while (b < e) 157 CRC(sum, c, *b++); 158 sum->sum = c; 159 return 0; 160 } 161 162 static int 163 crc_done(Sum_t* p) 164 { 165 register Crc_t* sum = (Crc_t*)p; 166 register Crcnum_t c; 167 register uintmax_t n; 168 int i; 169 int j; 170 171 c = sum->sum; 172 if (sum->addsize) 173 { 174 n = sum->size ^ sum->xorsize; 175 if (sum->rotate) 176 while (n) 177 { 178 CRCROTATE(sum, c, n); 179 n >>= 8; 180 } 181 else 182 for (i = 0, j = 32; i < 4; i++) 183 { 184 j -= 8; 185 CRC(sum, c, n >> j); 186 } 187 } 188 sum->sum = c ^ sum->done; 189 sum->total_sum ^= (sum->sum &= 0xffffffff); 190 return 0; 191 } 192