ucw/crc.c

   1 /*
   2  *      CRC32 (Castagnoli 1993)
   3  *
   4  *      Based on Michael E. Kounavis and Frank L. Berry: A Systematic Approach
   5  *      to Building High Performance Software-based CRC Generators
   6  *      (Proceedings of the 10th IEEE Symposium on Computers and Communications 2005)
   7  *
   8  *      Includes code from http://sourceforge.net/projects/slicing-by-8/,
   9  *      which carried the following copyright notice:
  10  *
  11  *      Copyright (c) 2004-2006 Intel Corporation - All Rights Reserved
  12  *
  13  *      This software program is licensed subject to the BSD License,
  14  *      available at http://www.opensource.org/licenses/bsd-license.html
  15  *
  16  *      Adapted for LibUCW by Martin Mares <mj@ucw.cz> in 2012.
  17  */
  18
  19 #include <ucw/lib.h>
  20 #include <ucw/crc.h>
  21 #include <ucw/crc-tables.h>
  22
  23 static void crc32_update_by1(crc32_context *ctx, const byte *buf, uint len)
  24 {
  25   u32 crc = ctx->state;
  26   while (len--)
  27     crc = crc_tableil8_o32[(crc ^ *buf++) & 0x000000FF] ^ (crc >> 8);
  28   ctx->state = crc;
  29 }
  30
  31 static void crc32_update_by4(crc32_context *ctx, const byte *buf, uint len)
  32 {
  33   uint init_bytes, words;
  34   u32 crc = ctx->state;
  35   u32 term1, term2, *buf32;
  36
  37   // Align start address to a multiple of 4 bytes
  38   init_bytes = ((uintptr_t) buf) & 3;
  39   if (init_bytes)
  40     {
  41       init_bytes = 4 - init_bytes;
  42       len -= init_bytes;
  43       while (init_bytes--)
  44         crc = crc_tableil8_o32[(crc ^ *buf++) & 0x000000FF] ^ (crc >> 8);
  45     }
  46
  47   // Process 4 bytes at a time
  48   words = len/4;
  49   len -= 4*words;
  50   buf32 = (u32 *) buf;
  51   while (words--)
  52     {
  53       crc ^= *buf32++;
  54       term1 = crc_tableil8_o56[crc & 0x000000FF] ^ crc_tableil8_o48[(crc >> 8) & 0x000000FF];
  55       term2 = crc >> 16;
  56       crc = term1 ^
  57             crc_tableil8_o40[term2 & 0x000000FF] ^
  58             crc_tableil8_o32[(term2 >> 8) & 0x000000FF];
  59     }
  60
  61   // Process remaining up to 7 bytes
  62   buf = (byte *) buf32;
  63   while (len--)
  64     crc = crc_tableil8_o32[(crc ^ *buf++) & 0x000000FF] ^ (crc >> 8);
  65
  66   ctx->state = crc;
  67 }
  68
  69 static void crc32_update_by8(crc32_context *ctx, const byte *buf, uint len)
  70 {
  71   uint init_bytes, quads;
  72   u32 crc = ctx->state;
  73   u32 term1, term2, *buf32;
  74
  75   // Align start address to a multiple of 8 bytes
  76   init_bytes = ((uintptr_t) buf) & 7;
  77   if (init_bytes)
  78     {
  79       init_bytes = 8 - init_bytes;
  80       len -= init_bytes;
  81       while (init_bytes--)
  82         crc = crc_tableil8_o32[(crc ^ *buf++) & 0x000000FF] ^ (crc >> 8);
  83     }
  84
  85   // Process 8 bytes at a time
  86   quads = len/8;
  87   len -= 8*quads;
  88   buf32 = (u32 *) buf;
  89   while (quads--)
  90     {
  91       crc ^= *buf32++;
  92       term1 = crc_tableil8_o88[crc & 0x000000FF] ^
  93               crc_tableil8_o80[(crc >> 8) & 0x000000FF];
  94       term2 = crc >> 16;
  95       crc = term1 ^
  96               crc_tableil8_o72[term2 & 0x000000FF] ^
  97               crc_tableil8_o64[(term2 >> 8) & 0x000000FF];
  98       term1 = crc_tableil8_o56[*buf32 & 0x000000FF] ^
  99               crc_tableil8_o48[(*buf32 >> 8) & 0x000000FF];
 100
 101       term2 = *buf32 >> 16;
 102       crc =     crc ^
 103               term1 ^
 104               crc_tableil8_o40[term2  & 0x000000FF] ^
 105               crc_tableil8_o32[(term2 >> 8) & 0x000000FF];
 106       buf32++;
 107     }
 108
 109   // Process remaining up to 7 bytes
 110   buf = (byte *) buf32;
 111   while (len--)
 112     crc = crc_tableil8_o32[(crc ^ *buf++) & 0x000000FF] ^ (crc >> 8);
 113
 114   ctx->state = crc;
 115 }
 116
 117 void
 118 crc32_init(crc32_context *ctx, uint crc_mode)
 119 {
 120   ctx->state = 0xffffffff;
 121   switch (crc_mode)
 122     {
 123     case CRC_MODE_DEFAULT:
 124       ctx->update_func = crc32_update_by4;
 125       break;
 126     case CRC_MODE_SMALL:
 127       ctx->update_func = crc32_update_by1;
 128       break;
 129     case CRC_MODE_BIG:
 130       ctx->update_func = crc32_update_by8;
 131       break;
 132     default:
 133       ASSERT(0);
 134     }
 135 }
 136
 137 u32
 138 crc32_hash_buffer(const byte *buf, uint len)
 139 {
 140   crc32_context ctx;
 141   crc32_init(&ctx, CRC_MODE_DEFAULT);
 142   crc32_update(&ctx, buf, len);
 143   return crc32_final(&ctx);
 144 }
 145
 146 #ifdef TEST
 147
 148 #include <stdio.h>
 149 #include <stdlib.h>
 150
 151 int main(int argc, char **argv)
 152 {
 153   if (argc != 5)
 154     die("Usage: crc-t <alg> <len> <block> <iters>");
 155   uint alg = atoi(argv[1]);
 156   uint len = atoi(argv[2]);
 157   uint block = atoi(argv[3]);
 158   uint iters = atoi(argv[4]);
 159
 160   byte *buf = xmalloc(len);
 161   for (uint i=0; i<len; i++)
 162     buf[i] = i ^ (i >> 5) ^ (i >> 11);
 163
 164   for (uint i=0; i<iters; i++)
 165     {
 166       crc32_context ctx;
 167       uint modes[] = { CRC_MODE_DEFAULT, CRC_MODE_SMALL, CRC_MODE_BIG };
 168       ASSERT(alg < ARRAY_SIZE(modes));
 169       crc32_init(&ctx, modes[alg]);
 170       for (uint p=0; p<len;)
 171         {
 172           uint l = MIN(len-p, block);
 173           crc32_update(&ctx, buf+p, l);
 174           p += l;
 175         }
 176       uint crc = crc32_final(&ctx);
 177       if (!i)
 178         printf("%08x\n", crc);
 179     }
 180
 181   return 0;
 182 }
 183
 184 #endif