usr/src/lib/libsum/common/sum-crc.c

   1 /***********************************************************************
   2 *                                                                      *
   3 *               This software is part of the ast package               *
   4 *          Copyright (c) 1996-2010 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 }