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.  This matches
  37    what gdb does.
  38
  39    #include <stdio.h>
  40
  41    int
  42    main ()
  43    {
  44      int i, j;
  45      unsigned int c;
  46      int table[256];
  47
  48      for (i = 0; i < 256; i++)
  49        {
  50          for (c = i << 24, j = 8; j > 0; --j)
  51            c = c & 0x80000000 ? (c << 1) ^ 0x04c11db7 : (c << 1);
  52          table[i] = c;
  53        }
  54
  55      printf ("static const unsigned int crc32_table[] =\n{\n");
  56      for (i = 0; i < 256; i += 4)
  57        {
  58          printf ("  0x%08x, 0x%08x, 0x%08x, 0x%08x",
  59                  table[i + 0], table[i + 1], table[i + 2], table[i + 3]);
  60          if (i + 4 < 256)
  61            putchar (',');
  62          putchar ('\n');
  63        }
  64      printf ("};\n");
  65      return 0;
  66    }
  67
  68    For more information on CRC, see, e.g.,
  69    http://www.ross.net/crc/download/crc_v3.txt.  */
  70
  71 static const unsigned int crc32_table[] =
  72 {
  73   0x00000000, 0x04c11db7, 0x09823b6e, 0x0d4326d9,
  74   0x130476dc, 0x17c56b6b, 0x1a864db2, 0x1e475005,
  75   0x2608edb8, 0x22c9f00f, 0x2f8ad6d6, 0x2b4bcb61,
  76   0x350c9b64, 0x31cd86d3, 0x3c8ea00a, 0x384fbdbd,
  77   0x4c11db70, 0x48d0c6c7, 0x4593e01e, 0x4152fda9,
  78   0x5f15adac, 0x5bd4b01b, 0x569796c2, 0x52568b75,
  79   0x6a1936c8, 0x6ed82b7f, 0x639b0da6, 0x675a1011,
  80   0x791d4014, 0x7ddc5da3, 0x709f7b7a, 0x745e66cd,
  81   0x9823b6e0, 0x9ce2ab57, 0x91a18d8e, 0x95609039,
  82   0x8b27c03c, 0x8fe6dd8b, 0x82a5fb52, 0x8664e6e5,
  83   0xbe2b5b58, 0xbaea46ef, 0xb7a96036, 0xb3687d81,
  84   0xad2f2d84, 0xa9ee3033, 0xa4ad16ea, 0xa06c0b5d,
  85   0xd4326d90, 0xd0f37027, 0xddb056fe, 0xd9714b49,
  86   0xc7361b4c, 0xc3f706fb, 0xceb42022, 0xca753d95,
  87   0xf23a8028, 0xf6fb9d9f, 0xfbb8bb46, 0xff79a6f1,
  88   0xe13ef6f4, 0xe5ffeb43, 0xe8bccd9a, 0xec7dd02d,
  89   0x34867077, 0x30476dc0, 0x3d044b19, 0x39c556ae,
  90   0x278206ab, 0x23431b1c, 0x2e003dc5, 0x2ac12072,
  91   0x128e9dcf, 0x164f8078, 0x1b0ca6a1, 0x1fcdbb16,
  92   0x018aeb13, 0x054bf6a4, 0x0808d07d, 0x0cc9cdca,
  93   0x7897ab07, 0x7c56b6b0, 0x71159069, 0x75d48dde,
  94   0x6b93dddb, 0x6f52c06c, 0x6211e6b5, 0x66d0fb02,
  95   0x5e9f46bf, 0x5a5e5b08, 0x571d7dd1, 0x53dc6066,
  96   0x4d9b3063, 0x495a2dd4, 0x44190b0d, 0x40d816ba,
  97   0xaca5c697, 0xa864db20, 0xa527fdf9, 0xa1e6e04e,
  98   0xbfa1b04b, 0xbb60adfc, 0xb6238b25, 0xb2e29692,
  99   0x8aad2b2f, 0x8e6c3698, 0x832f1041, 0x87ee0df6,
 100   0x99a95df3, 0x9d684044, 0x902b669d, 0x94ea7b2a,
 101   0xe0b41de7, 0xe4750050, 0xe9362689, 0xedf73b3e,
 102   0xf3b06b3b, 0xf771768c, 0xfa325055, 0xfef34de2,
 103   0xc6bcf05f, 0xc27dede8, 0xcf3ecb31, 0xcbffd686,
 104   0xd5b88683, 0xd1799b34, 0xdc3abded, 0xd8fba05a,
 105   0x690ce0ee, 0x6dcdfd59, 0x608edb80, 0x644fc637,
 106   0x7a089632, 0x7ec98b85, 0x738aad5c, 0x774bb0eb,
 107   0x4f040d56, 0x4bc510e1, 0x46863638, 0x42472b8f,
 108   0x5c007b8a, 0x58c1663d, 0x558240e4, 0x51435d53,
 109   0x251d3b9e, 0x21dc2629, 0x2c9f00f0, 0x285e1d47,
 110   0x36194d42, 0x32d850f5, 0x3f9b762c, 0x3b5a6b9b,
 111   0x0315d626, 0x07d4cb91, 0x0a97ed48, 0x0e56f0ff,
 112   0x1011a0fa, 0x14d0bd4d, 0x19939b94, 0x1d528623,
 113   0xf12f560e, 0xf5ee4bb9, 0xf8ad6d60, 0xfc6c70d7,
 114   0xe22b20d2, 0xe6ea3d65, 0xeba91bbc, 0xef68060b,
 115   0xd727bbb6, 0xd3e6a601, 0xdea580d8, 0xda649d6f,
 116   0xc423cd6a, 0xc0e2d0dd, 0xcda1f604, 0xc960ebb3,
 117   0xbd3e8d7e, 0xb9ff90c9, 0xb4bcb610, 0xb07daba7,
 118   0xae3afba2, 0xaafbe615, 0xa7b8c0cc, 0xa379dd7b,
 119   0x9b3660c6, 0x9ff77d71, 0x92b45ba8, 0x9675461f,
 120   0x8832161a, 0x8cf30bad, 0x81b02d74, 0x857130c3,
 121   0x5d8a9099, 0x594b8d2e, 0x5408abf7, 0x50c9b640,
 122   0x4e8ee645, 0x4a4ffbf2, 0x470cdd2b, 0x43cdc09c,
 123   0x7b827d21, 0x7f436096, 0x7200464f, 0x76c15bf8,
 124   0x68860bfd, 0x6c47164a, 0x61043093, 0x65c52d24,
 125   0x119b4be9, 0x155a565e, 0x18197087, 0x1cd86d30,
 126   0x029f3d35, 0x065e2082, 0x0b1d065b, 0x0fdc1bec,
 127   0x3793a651, 0x3352bbe6, 0x3e119d3f, 0x3ad08088,
 128   0x2497d08d, 0x2056cd3a, 0x2d15ebe3, 0x29d4f654,
 129   0xc5a92679, 0xc1683bce, 0xcc2b1d17, 0xc8ea00a0,
 130   0xd6ad50a5, 0xd26c4d12, 0xdf2f6bcb, 0xdbee767c,
 131   0xe3a1cbc1, 0xe760d676, 0xea23f0af, 0xeee2ed18,
 132   0xf0a5bd1d, 0xf464a0aa, 0xf9278673, 0xfde69bc4,
 133   0x89b8fd09, 0x8d79e0be, 0x803ac667, 0x84fbdbd0,
 134   0x9abc8bd5, 0x9e7d9662, 0x933eb0bb, 0x97ffad0c,
 135   0xafb010b1, 0xab710d06, 0xa6322bdf, 0xa2f33668,
 136   0xbcb4666d, 0xb8757bda, 0xb5365d03, 0xb1f740b4
 137 };
 138
 139 /*
 140
 141 @deftypefn Extension {unsigned int} crc32 (const unsigned char *@var{buf}, @
 142   int @var{len}, unsigned int @var{init})
 143
 144 Compute the 32-bit CRC of @var{buf} which has length @var{len}.  The
 145 starting value is @var{init}; this may be used to compute the CRC of
 146 data split across multiple buffers by passing the return value of each
 147 call as the @var{init} parameter of the next.
 148
 149 This is intended to match the CRC used by the @command{gdb} remote
 150 protocol for the @samp{qCRC} command.  In order to get the same
 151 results as gdb for a block of data, you must pass the first CRC
 152 parameter as @code{0xffffffff}.
 153
 154 This CRC can be specified as:
 155
 156   Width  : 32
 157   Poly   : 0x04c11db7
 158   Init   : parameter, typically 0xffffffff
 159   RefIn  : false
 160   RefOut : false
 161   XorOut : 0
 162
 163 This differs from the "standard" CRC-32 algorithm in that the values
 164 are not reflected, and there is no final XOR value.  These differences
 165 make it easy to compose the values of multiple blocks.
 166
 167 @end deftypefn
 168
 169 */
 170
 171 unsigned int
 172 xcrc32 (const unsigned char *buf, int len, unsigned int init)
 173 {
 174   unsigned int crc = init;
 175   while (len--)
 176     {
 177       crc = (crc << 8) ^ crc32_table[((crc >> 24) ^ *buf) & 255];
 178       buf++;
 179     }
 180   return crc;
 181 }