libiberty/crc32.c

   1 /* crc32.c
   2    Copyright (C) 2009, 2011 Free Software Foundation, Inc.
   3
   4    This file is part of the libiberty library.
   5
   6    This file is free software; you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 2 of the License, or
   9    (at your option) any later version.
  10
  11    In addition to the permissions in the GNU General Public License, the
  12    Free Software Foundation gives you unlimited permission to link the
  13    compiled version of this file into combinations with other programs,
  14    and to distribute those combinations without any restriction coming
  15    from the use of this file.  (The General Public License restrictions
  16    do apply in other respects; for example, they cover modification of
  17    the file, and distribution when not linked into a combined
  18    executable.)
  19
  20    This program is distributed in the hope that it will be useful,
  21    but WITHOUT ANY WARRANTY; without even the implied warranty of
  22    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  23    GNU General Public License for more details.
  24
  25    You should have received a copy of the GNU General Public License
  26    along with this program; if not, write to the Free Software
  27    Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA 02110-1301, USA.
  28 */
  29
  30 #ifdef HAVE_CONFIG_H
  31 #include "config.h"
  32 #endif
  33
  34 #include "libiberty.h"
  35
  36 /* This table was generated by the following program.
  37
  38    #include <stdio.h>
  39
  40    int
  41    main ()
  42    {
  43      unsigned int i, j;
  44      unsigned int c;
  45      int table[256];
  46
  47      for (i = 0; i < 256; i++)
  48        {
  49          for (c = i << 24, j = 8; j > 0; --j)
  50            c = c & 0x80000000 ? (c << 1) ^ 0x04c11db7 : (c << 1);
  51          table[i] = c;
  52        }
  53
  54      printf ("static const unsigned int crc32_table[] =\n{\n");
  55      for (i = 0; i < 256; i += 4)
  56        {
  57          printf ("  0x%08x, 0x%08x, 0x%08x, 0x%08x",
  58                  table[i + 0], table[i + 1], table[i + 2], table[i + 3]);
  59          if (i + 4 < 256)
  60            putchar (',');
  61          putchar ('\n');
  62        }
  63      printf ("};\n");
  64      return 0;
  65    }
  66
  67    For more information on CRC, see, e.g.,
  68    http://www.ross.net/crc/download/crc_v3.txt.  */
  69
  70 static const unsigned int crc32_table[] =
  71 {
  72   0x00000000, 0x04c11db7, 0x09823b6e, 0x0d4326d9,
  73   0x130476dc, 0x17c56b6b, 0x1a864db2, 0x1e475005,
  74   0x2608edb8, 0x22c9f00f, 0x2f8ad6d6, 0x2b4bcb61,
  75   0x350c9b64, 0x31cd86d3, 0x3c8ea00a, 0x384fbdbd,
  76   0x4c11db70, 0x48d0c6c7, 0x4593e01e, 0x4152fda9,
  77   0x5f15adac, 0x5bd4b01b, 0x569796c2, 0x52568b75,
  78   0x6a1936c8, 0x6ed82b7f, 0x639b0da6, 0x675a1011,
  79   0x791d4014, 0x7ddc5da3, 0x709f7b7a, 0x745e66cd,
  80   0x9823b6e0, 0x9ce2ab57, 0x91a18d8e, 0x95609039,
  81   0x8b27c03c, 0x8fe6dd8b, 0x82a5fb52, 0x8664e6e5,
  82   0xbe2b5b58, 0xbaea46ef, 0xb7a96036, 0xb3687d81,
  83   0xad2f2d84, 0xa9ee3033, 0xa4ad16ea, 0xa06c0b5d,
  84   0xd4326d90, 0xd0f37027, 0xddb056fe, 0xd9714b49,
  85   0xc7361b4c, 0xc3f706fb, 0xceb42022, 0xca753d95,
  86   0xf23a8028, 0xf6fb9d9f, 0xfbb8bb46, 0xff79a6f1,
  87   0xe13ef6f4, 0xe5ffeb43, 0xe8bccd9a, 0xec7dd02d,
  88   0x34867077, 0x30476dc0, 0x3d044b19, 0x39c556ae,
  89   0x278206ab, 0x23431b1c, 0x2e003dc5, 0x2ac12072,
  90   0x128e9dcf, 0x164f8078, 0x1b0ca6a1, 0x1fcdbb16,
  91   0x018aeb13, 0x054bf6a4, 0x0808d07d, 0x0cc9cdca,
  92   0x7897ab07, 0x7c56b6b0, 0x71159069, 0x75d48dde,
  93   0x6b93dddb, 0x6f52c06c, 0x6211e6b5, 0x66d0fb02,
  94   0x5e9f46bf, 0x5a5e5b08, 0x571d7dd1, 0x53dc6066,
  95   0x4d9b3063, 0x495a2dd4, 0x44190b0d, 0x40d816ba,
  96   0xaca5c697, 0xa864db20, 0xa527fdf9, 0xa1e6e04e,
  97   0xbfa1b04b, 0xbb60adfc, 0xb6238b25, 0xb2e29692,
  98   0x8aad2b2f, 0x8e6c3698, 0x832f1041, 0x87ee0df6,
  99   0x99a95df3, 0x9d684044, 0x902b669d, 0x94ea7b2a,
 100   0xe0b41de7, 0xe4750050, 0xe9362689, 0xedf73b3e,
 101   0xf3b06b3b, 0xf771768c, 0xfa325055, 0xfef34de2,
 102   0xc6bcf05f, 0xc27dede8, 0xcf3ecb31, 0xcbffd686,
 103   0xd5b88683, 0xd1799b34, 0xdc3abded, 0xd8fba05a,
 104   0x690ce0ee, 0x6dcdfd59, 0x608edb80, 0x644fc637,
 105   0x7a089632, 0x7ec98b85, 0x738aad5c, 0x774bb0eb,
 106   0x4f040d56, 0x4bc510e1, 0x46863638, 0x42472b8f,
 107   0x5c007b8a, 0x58c1663d, 0x558240e4, 0x51435d53,
 108   0x251d3b9e, 0x21dc2629, 0x2c9f00f0, 0x285e1d47,
 109   0x36194d42, 0x32d850f5, 0x3f9b762c, 0x3b5a6b9b,
 110   0x0315d626, 0x07d4cb91, 0x0a97ed48, 0x0e56f0ff,
 111   0x1011a0fa, 0x14d0bd4d, 0x19939b94, 0x1d528623,
 112   0xf12f560e, 0xf5ee4bb9, 0xf8ad6d60, 0xfc6c70d7,
 113   0xe22b20d2, 0xe6ea3d65, 0xeba91bbc, 0xef68060b,
 114   0xd727bbb6, 0xd3e6a601, 0xdea580d8, 0xda649d6f,
 115   0xc423cd6a, 0xc0e2d0dd, 0xcda1f604, 0xc960ebb3,
 116   0xbd3e8d7e, 0xb9ff90c9, 0xb4bcb610, 0xb07daba7,
 117   0xae3afba2, 0xaafbe615, 0xa7b8c0cc, 0xa379dd7b,
 118   0x9b3660c6, 0x9ff77d71, 0x92b45ba8, 0x9675461f,
 119   0x8832161a, 0x8cf30bad, 0x81b02d74, 0x857130c3,
 120   0x5d8a9099, 0x594b8d2e, 0x5408abf7, 0x50c9b640,
 121   0x4e8ee645, 0x4a4ffbf2, 0x470cdd2b, 0x43cdc09c,
 122   0x7b827d21, 0x7f436096, 0x7200464f, 0x76c15bf8,
 123   0x68860bfd, 0x6c47164a, 0x61043093, 0x65c52d24,
 124   0x119b4be9, 0x155a565e, 0x18197087, 0x1cd86d30,
 125   0x029f3d35, 0x065e2082, 0x0b1d065b, 0x0fdc1bec,
 126   0x3793a651, 0x3352bbe6, 0x3e119d3f, 0x3ad08088,
 127   0x2497d08d, 0x2056cd3a, 0x2d15ebe3, 0x29d4f654,
 128   0xc5a92679, 0xc1683bce, 0xcc2b1d17, 0xc8ea00a0,
 129   0xd6ad50a5, 0xd26c4d12, 0xdf2f6bcb, 0xdbee767c,
 130   0xe3a1cbc1, 0xe760d676, 0xea23f0af, 0xeee2ed18,
 131   0xf0a5bd1d, 0xf464a0aa, 0xf9278673, 0xfde69bc4,
 132   0x89b8fd09, 0x8d79e0be, 0x803ac667, 0x84fbdbd0,
 133   0x9abc8bd5, 0x9e7d9662, 0x933eb0bb, 0x97ffad0c,
 134   0xafb010b1, 0xab710d06, 0xa6322bdf, 0xa2f33668,
 135   0xbcb4666d, 0xb8757bda, 0xb5365d03, 0xb1f740b4
 136 };
 137
 138 /*
 139
 140 @deftypefn Extension {unsigned int} crc32 (const unsigned char *@var{buf}, @
 141   int @var{len}, unsigned int @var{init})
 142
 143 Compute the 32-bit CRC of @var{buf} which has length @var{len}.  The
 144 starting value is @var{init}; this may be used to compute the CRC of
 145 data split across multiple buffers by passing the return value of each
 146 call as the @var{init} parameter of the next.
 147
 148 This is used by the @command{gdb} remote protocol for the @samp{qCRC}
 149 command.  In order to get the same results as gdb for a block of data,
 150 you must pass the first CRC parameter as @code{0xffffffff}.
 151
 152 This CRC can be specified as:
 153
 154   Width  : 32
 155   Poly   : 0x04c11db7
 156   Init   : parameter, typically 0xffffffff
 157   RefIn  : false
 158   RefOut : false
 159   XorOut : 0
 160
 161 This differs from the "standard" CRC-32 algorithm in that the values
 162 are not reflected, and there is no final XOR value.  These differences
 163 make it easy to compose the values of multiple blocks.
 164
 165 @end deftypefn
 166
 167 */
 168
 169 unsigned int
 170 xcrc32 (const unsigned char *buf, int len, unsigned int init)
 171 {
 172   unsigned int crc = init;
 173   while (len--)
 174     {
 175       crc = (crc << 8) ^ crc32_table[((crc >> 24) ^ *buf) & 255];
 176       buf++;
 177     }
 178   return crc;
 179 }