lib/crc.c

   1 /* crc.c -- cyclic redundancy checks
   2    Copyright (C) 2005-2006, 2009-2024 Free Software Foundation, Inc.
   3
   4    This file is free software: you can redistribute it and/or modify
   5    it under the terms of the GNU Lesser General Public License as
   6    published by the Free Software Foundation, either version 3 of the
   7    License, or (at your option) any later version.
   8
   9    This file is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU Lesser General Public License for more details.
  13
  14    You should have received a copy of the GNU Lesser General Public License
  15    along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
  16
  17 /* Written by Simon Josefsson.  */
  18
  19 #include <config.h>
  20
  21 #include "crc.h"
  22 #include "endian.h"
  23
  24 #include <string.h>
  25
  26 #ifdef GL_CRC_SLICE_BY_8
  27 #include "crc-sliceby8.h"
  28
  29 /*
  30  * When we calculate the CRC32 byte-by-byte we take the checksum
  31  * up to the previous byte, XOR it with our new byte, run CRC32
  32  * and then XOR against the remaining bytes from the prior checksum:
  33  *
  34  * c0 = prior checksum
  35  * d0,d1 = bytes 0 and 1 of our data
  36  * c1 = (c0 >> 8)
  37  * c2 = CRC32(c0 ^ d0) ^ c1
  38  * c3 = (c2 >> 8)
  39  * c4 = CRC32(c2 ^ d1) ^ c3
  40  *
  41  * The CRC32 function is "affine" which means that
  42  * CRC32(a ^ b) = CRC32(a) ^ CRC32(b)
  43  *
  44  * and therefore we can move some of the terms around, e.g.
  45  *
  46  * c4 = CRC32(CRC32(c0 ^ d0) ^ c1 ^ d1) ^ c3
  47  * c4 = CRC32(CRC32(c0 ^ d0)) ^ CRC32(c1 ^ d1) ^ c3
  48  *
  49  * Another way to look at this is
  50  *
  51  * CRC32(0x1200) ^ CRC32(0x34) = CRC32(0x1234)
  52  *
  53  * With the slice-by-8 method, we extend the table-lookup technique
  54  * from a single table of 0x00 to 0xFF, but also every 0x100 from
  55  * 0x0000 to 0xFF00, and for 0x000000 to 0xFF0000 etc.
  56  *
  57  * We can then calculate by taking 8 bytes of plaintext and then
  58  * looking up each one individually and XORing them together
  59  * at the end.
  60  *
  61  * This approach has been mentioned by multiple sources but one of
  62  * the common references is 10.1109/TC.2008.85 by Kounavis
  63  * and Berry
  64  */
  65
  66 static uint32_t
  67 crc32_update_no_xor_slice_by_8 (uint32_t crc, const char *buf)
  68 {
  69   uint64_t local_buf;
  70   memcpy (&local_buf, buf, 8);
  71   local_buf = le64toh (local_buf) ^ crc;
  72   crc = crc32_sliceby8_table[0][(local_buf >> 56) & 0xFF]
  73         ^ crc32_sliceby8_table[1][(local_buf >> 48) & 0xFF]
  74         ^ crc32_sliceby8_table[2][(local_buf >> 40) & 0xFF]
  75         ^ crc32_sliceby8_table[3][(local_buf >> 32) & 0xFF]
  76         ^ crc32_sliceby8_table[4][(local_buf >> 24) & 0xFF]
  77         ^ crc32_sliceby8_table[5][(local_buf >> 16) & 0xFF]
  78         ^ crc32_sliceby8_table[6][(local_buf >> 8) & 0xFF]
  79         ^ crc32_sliceby8_table[7][local_buf & 0xFF];
  80
  81   return crc;
  82 }
  83
  84 static uint32_t
  85 crc32_update_no_xor_slice_by_n (uint32_t crc, const char *buf,
  86                                 size_t num_bytes)
  87 {
  88   uint64_t local_buf;
  89   size_t i, shift_amount;
  90
  91   memcpy (&local_buf, buf, num_bytes);
  92   local_buf = le64toh (local_buf) ^ crc;
  93
  94   if (num_bytes >= 4)
  95     crc = 0;
  96   else
  97     crc = crc >> (num_bytes * 8);
  98
  99   for (i = 0; i < num_bytes; i++)
 100     {
 101       shift_amount = ((num_bytes - i - 1) * 8);
 102       crc = crc ^ crc32_sliceby8_table[i][(local_buf >> shift_amount) & 0xFF];
 103     }
 104
 105   return crc;
 106 }
 107
 108 uint32_t
 109 crc32_update_no_xor (uint32_t crc, const char *buf, size_t len)
 110 {
 111   size_t n, slice_alignment;
 112
 113   slice_alignment = (len & (-8));
 114
 115   for (n = 0; n < slice_alignment; n += 8)
 116     crc = crc32_update_no_xor_slice_by_8 (crc, buf + n);
 117
 118   if (len > n)
 119     crc = crc32_update_no_xor_slice_by_n (crc, buf + n, len - n);
 120
 121   return crc;
 122 }
 123 #else
 124
 125 /* Table of CRCs of all 8-bit messages.  Generated by running code
 126    from RFC 1952 modified to print out the table. */
 127 static const uint32_t crc32_table[256] = {
 128   0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f,
 129   0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
 130   0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2,
 131   0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
 132   0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9,
 133   0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
 134   0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c,
 135   0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
 136   0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423,
 137   0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
 138   0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106,
 139   0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
 140   0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d,
 141   0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
 142   0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
 143   0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
 144   0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7,
 145   0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
 146   0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa,
 147   0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
 148   0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81,
 149   0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
 150   0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84,
 151   0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
 152   0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
 153   0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
 154   0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e,
 155   0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
 156   0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55,
 157   0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
 158   0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28,
 159   0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
 160   0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f,
 161   0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
 162   0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
 163   0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
 164   0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69,
 165   0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
 166   0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc,
 167   0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
 168   0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693,
 169   0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
 170   0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
 171 };
 172
 173 /*
 174  * The following function was extracted from RFC 1952 by Simon
 175  * Josefsson.  It was modified to avoid initial and final XOR, to use
 176  * size_t for the buffer length, and to use the const keyword.
 177  */
 178 uint32_t
 179 crc32_update_no_xor (uint32_t crc, const char *buf, size_t len)
 180 {
 181   size_t n;
 182
 183   for (n = 0; n < len; n++)
 184     crc = crc32_table[(crc ^ buf[n]) & 0xff] ^ (crc >> 8);
 185
 186   return crc;
 187 }
 188
 189 #endif
 190
 191 uint32_t
 192 crc32_no_xor (const char *buf, size_t len)
 193 {
 194   return crc32_update_no_xor (0L, buf, len);
 195 }
 196
 197 uint32_t
 198 crc32_update (uint32_t crc, const char *buf, size_t len)
 199 {
 200   return crc32_update_no_xor (crc ^ 0xffffffff, buf, len) ^ 0xffffffff;
 201 }
 202
 203 uint32_t
 204 crc32 (const char *buf, size_t len)
 205 {
 206   return crc32_update (0L, buf, len);
 207 }