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   // Special case
  38   if (len < 4)
  39     goto small;
  40
  41   // Align start address to a multiple of 4 bytes
  42   init_bytes = ((uintptr_t) buf) & 3;
  43   if (init_bytes)
  44     {
  45       init_bytes = 4 - init_bytes;
  46       len -= init_bytes;
  47       while (init_bytes--)
  48         crc = crc_tableil8_o32[(crc ^ *buf++) & 0x000000FF] ^ (crc >> 8);
  49     }
  50
  51   // Process 4 bytes at a time
  52   words = len/4;
  53   len -= 4*words;
  54   buf32 = (u32 *) buf;
  55   while (words--)
  56     {
  57       crc ^= *buf32++;
  58       term1 = crc_tableil8_o56[crc & 0x000000FF] ^ crc_tableil8_o48[(crc >> 8) & 0x000000FF];
  59       term2 = crc >> 16;
  60       crc = term1 ^
  61             crc_tableil8_o40[term2 & 0x000000FF] ^
  62             crc_tableil8_o32[(term2 >> 8) & 0x000000FF];
  63     }
  64
  65   // Process remaining up to 7 bytes
  66   buf = (byte *) buf32;
  67 small:
  68   while (len--)
  69     crc = crc_tableil8_o32[(crc ^ *buf++) & 0x000000FF] ^ (crc >> 8);
  70
  71   ctx->state = crc;
  72 }
  73
  74 static void crc32_update_by8(crc32_context *ctx, const byte *buf, uint len)
  75 {
  76   uint init_bytes, quads;
  77   u32 crc = ctx->state;
  78   u32 term1, term2, *buf32;
  79
  80   // Special case
  81   if (len < 8)
  82     goto small;
  83
  84   // Align start address to a multiple of 8 bytes
  85   init_bytes = ((uintptr_t) buf) & 7;
  86   if (init_bytes)
  87     {
  88       init_bytes = 8 - init_bytes;
  89       len -= init_bytes;
  90       while (init_bytes--)
  91         crc = crc_tableil8_o32[(crc ^ *buf++) & 0x000000FF] ^ (crc >> 8);
  92     }
  93
  94   // Process 8 bytes at a time
  95   quads = len/8;
  96   len -= 8*quads;
  97   buf32 = (u32 *) buf;
  98   while (quads--)
  99     {
 100       crc ^= *buf32++;
 101       term1 = crc_tableil8_o88[crc & 0x000000FF] ^
 102               crc_tableil8_o80[(crc >> 8) & 0x000000FF];
 103       term2 = crc >> 16;
 104       crc = term1 ^
 105               crc_tableil8_o72[term2 & 0x000000FF] ^
 106               crc_tableil8_o64[(term2 >> 8) & 0x000000FF];
 107       term1 = crc_tableil8_o56[*buf32 & 0x000000FF] ^
 108               crc_tableil8_o48[(*buf32 >> 8) & 0x000000FF];
 109
 110       term2 = *buf32 >> 16;
 111       crc =     crc ^
 112               term1 ^
 113               crc_tableil8_o40[term2  & 0x000000FF] ^
 114               crc_tableil8_o32[(term2 >> 8) & 0x000000FF];
 115       buf32++;
 116     }
 117
 118   // Process remaining up to 7 bytes
 119   buf = (byte *) buf32;
 120 small:
 121   while (len--)
 122     crc = crc_tableil8_o32[(crc ^ *buf++) & 0x000000FF] ^ (crc >> 8);
 123
 124   ctx->state = crc;
 125 }
 126
 127 void
 128 crc32_init(crc32_context *ctx, uint crc_mode)
 129 {
 130   ctx->state = 0xffffffff;
 131   switch (crc_mode)
 132     {
 133     case CRC_MODE_DEFAULT:
 134       ctx->update_func = crc32_update_by4;
 135       break;
 136     case CRC_MODE_SMALL:
 137       ctx->update_func = crc32_update_by1;
 138       break;
 139     case CRC_MODE_BIG:
 140       ctx->update_func = crc32_update_by8;
 141       break;
 142     default:
 143       ASSERT(0);
 144     }
 145 }
 146
 147 u32
 148 crc32_hash_buffer(const byte *buf, uint len)
 149 {
 150   crc32_context ctx;
 151   crc32_init(&ctx, CRC_MODE_DEFAULT);
 152   crc32_update(&ctx, buf, len);
 153   return crc32_final(&ctx);
 154 }
 155
 156 #ifdef TEST
 157
 158 #include <stdio.h>
 159 #include <stdlib.h>
 160
 161 int main(int argc, char **argv)
 162 {
 163   if (argc != 5)
 164     die("Usage: crc-t <alg> <len> <block> <iters>");
 165   uint alg = atoi(argv[1]);
 166   uint len = atoi(argv[2]);
 167   uint block = atoi(argv[3]);
 168   uint iters = atoi(argv[4]);
 169
 170   byte *buf = xmalloc(len);
 171   for (uint i=0; i<len; i++)
 172     buf[i] = i ^ (i >> 5) ^ (i >> 11);
 173
 174   for (uint i=0; i<iters; i++)
 175     {
 176       crc32_context ctx;
 177       uint modes[] = { CRC_MODE_DEFAULT, CRC_MODE_SMALL, CRC_MODE_BIG };
 178       ASSERT(alg < ARRAY_SIZE(modes));
 179       crc32_init(&ctx, modes[alg]);
 180       for (uint p=0; p<len;)
 181         {
 182           uint l = MIN(len-p, block);
 183           crc32_update(&ctx, buf+p, l);
 184           p += l;
 185         }
 186       uint crc = crc32_final(&ctx);
 187       if (!i)
 188         printf("%08x\n", crc);
 189     }
 190
 191   return 0;
 192 }
 193
 194 #endif