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