git.ozlabs.org Git - ccan/blob - ccan/crc/crc.c

   1 /* crc32_ieee code:
   2  *  COPYRIGHT (C) 1986 Gary S. Brown.  You may use this program, or
   3  *  code or tables extracted from it, as desired without restriction.
   4  */
   5
   6 /* crc32c code taken from 2.6.29 Linux kernel crypto/crc32c.c:
   7  * Copyright (c) 2004 Cisco Systems, Inc.
   8  * Copyright (c) 2008 Herbert Xu <herbert@gondor.apana.org.au>
   9  *
  10  * This program is free software; you can redistribute it and/or modify it
  11  * under the terms of the GNU General Public License as published by the Free
  12  * Software Foundation; either version 2 of the License, or (at your option)
  13  * any later version. */
  14
  15 /* crc64 code taken from Jacksum version 1.7.0 - checksum utility in Java
  16  * E-mail: jonelo@jonelo.de
  17  * Copyright (C) 2001-2006 Dipl.-Inf. (FH) Johann Nepomuk Loefflmann,
  18  * All Rights Reserved, http://www.jonelo.de
  19  *
  20  * This program is free software; you can redistribute it and/or
  21  * modify it under the terms of the GNU General Public License
  22  * as published by the Free Software Foundation; either version 2
  23  * of the License, or (at your option) any later version.
  24  */
  25
  26 #include "crc.h"
  27 #include <ccan/array_size/array_size.h>
  28 #include <stdbool.h>
  29 #include <stdlib.h>
  30
  31 /*
  32  * This is the CRC-32C table
  33  * Generated with:
  34  * width = 32 bits
  35  * poly = 0x1EDC6F41
  36  * reflect input bytes = true
  37  * reflect output bytes = true
  38  */
  39 static const uint32_t crc32c_tab[] = {
  40         0x00000000, 0xF26B8303, 0xE13B70F7, 0x1350F3F4,
  41         0xC79A971F, 0x35F1141C, 0x26A1E7E8, 0xD4CA64EB,
  42         0x8AD958CF, 0x78B2DBCC, 0x6BE22838, 0x9989AB3B,
  43         0x4D43CFD0, 0xBF284CD3, 0xAC78BF27, 0x5E133C24,
  44         0x105EC76F, 0xE235446C, 0xF165B798, 0x030E349B,
  45         0xD7C45070, 0x25AFD373, 0x36FF2087, 0xC494A384,
  46         0x9A879FA0, 0x68EC1CA3, 0x7BBCEF57, 0x89D76C54,
  47         0x5D1D08BF, 0xAF768BBC, 0xBC267848, 0x4E4DFB4B,
  48         0x20BD8EDE, 0xD2D60DDD, 0xC186FE29, 0x33ED7D2A,
  49         0xE72719C1, 0x154C9AC2, 0x061C6936, 0xF477EA35,
  50         0xAA64D611, 0x580F5512, 0x4B5FA6E6, 0xB93425E5,
  51         0x6DFE410E, 0x9F95C20D, 0x8CC531F9, 0x7EAEB2FA,
  52         0x30E349B1, 0xC288CAB2, 0xD1D83946, 0x23B3BA45,
  53         0xF779DEAE, 0x05125DAD, 0x1642AE59, 0xE4292D5A,
  54         0xBA3A117E, 0x4851927D, 0x5B016189, 0xA96AE28A,
  55         0x7DA08661, 0x8FCB0562, 0x9C9BF696, 0x6EF07595,
  56         0x417B1DBC, 0xB3109EBF, 0xA0406D4B, 0x522BEE48,
  57         0x86E18AA3, 0x748A09A0, 0x67DAFA54, 0x95B17957,
  58         0xCBA24573, 0x39C9C670, 0x2A993584, 0xD8F2B687,
  59         0x0C38D26C, 0xFE53516F, 0xED03A29B, 0x1F682198,
  60         0x5125DAD3, 0xA34E59D0, 0xB01EAA24, 0x42752927,
  61         0x96BF4DCC, 0x64D4CECF, 0x77843D3B, 0x85EFBE38,
  62         0xDBFC821C, 0x2997011F, 0x3AC7F2EB, 0xC8AC71E8,
  63         0x1C661503, 0xEE0D9600, 0xFD5D65F4, 0x0F36E6F7,
  64         0x61C69362, 0x93AD1061, 0x80FDE395, 0x72966096,
  65         0xA65C047D, 0x5437877E, 0x4767748A, 0xB50CF789,
  66         0xEB1FCBAD, 0x197448AE, 0x0A24BB5A, 0xF84F3859,
  67         0x2C855CB2, 0xDEEEDFB1, 0xCDBE2C45, 0x3FD5AF46,
  68         0x7198540D, 0x83F3D70E, 0x90A324FA, 0x62C8A7F9,
  69         0xB602C312, 0x44694011, 0x5739B3E5, 0xA55230E6,
  70         0xFB410CC2, 0x092A8FC1, 0x1A7A7C35, 0xE811FF36,
  71         0x3CDB9BDD, 0xCEB018DE, 0xDDE0EB2A, 0x2F8B6829,
  72         0x82F63B78, 0x709DB87B, 0x63CD4B8F, 0x91A6C88C,
  73         0x456CAC67, 0xB7072F64, 0xA457DC90, 0x563C5F93,
  74         0x082F63B7, 0xFA44E0B4, 0xE9141340, 0x1B7F9043,
  75         0xCFB5F4A8, 0x3DDE77AB, 0x2E8E845F, 0xDCE5075C,
  76         0x92A8FC17, 0x60C37F14, 0x73938CE0, 0x81F80FE3,
  77         0x55326B08, 0xA759E80B, 0xB4091BFF, 0x466298FC,
  78         0x1871A4D8, 0xEA1A27DB, 0xF94AD42F, 0x0B21572C,
  79         0xDFEB33C7, 0x2D80B0C4, 0x3ED04330, 0xCCBBC033,
  80         0xA24BB5A6, 0x502036A5, 0x4370C551, 0xB11B4652,
  81         0x65D122B9, 0x97BAA1BA, 0x84EA524E, 0x7681D14D,
  82         0x2892ED69, 0xDAF96E6A, 0xC9A99D9E, 0x3BC21E9D,
  83         0xEF087A76, 0x1D63F975, 0x0E330A81, 0xFC588982,
  84         0xB21572C9, 0x407EF1CA, 0x532E023E, 0xA145813D,
  85         0x758FE5D6, 0x87E466D5, 0x94B49521, 0x66DF1622,
  86         0x38CC2A06, 0xCAA7A905, 0xD9F75AF1, 0x2B9CD9F2,
  87         0xFF56BD19, 0x0D3D3E1A, 0x1E6DCDEE, 0xEC064EED,
  88         0xC38D26C4, 0x31E6A5C7, 0x22B65633, 0xD0DDD530,
  89         0x0417B1DB, 0xF67C32D8, 0xE52CC12C, 0x1747422F,
  90         0x49547E0B, 0xBB3FFD08, 0xA86F0EFC, 0x5A048DFF,
  91         0x8ECEE914, 0x7CA56A17, 0x6FF599E3, 0x9D9E1AE0,
  92         0xD3D3E1AB, 0x21B862A8, 0x32E8915C, 0xC083125F,
  93         0x144976B4, 0xE622F5B7, 0xF5720643, 0x07198540,
  94         0x590AB964, 0xAB613A67, 0xB831C993, 0x4A5A4A90,
  95         0x9E902E7B, 0x6CFBAD78, 0x7FAB5E8C, 0x8DC0DD8F,
  96         0xE330A81A, 0x115B2B19, 0x020BD8ED, 0xF0605BEE,
  97         0x24AA3F05, 0xD6C1BC06, 0xC5914FF2, 0x37FACCF1,
  98         0x69E9F0D5, 0x9B8273D6, 0x88D28022, 0x7AB90321,
  99         0xAE7367CA, 0x5C18E4C9, 0x4F48173D, 0xBD23943E,
 100         0xF36E6F75, 0x0105EC76, 0x12551F82, 0xE03E9C81,
 101         0x34F4F86A, 0xC69F7B69, 0xD5CF889D, 0x27A40B9E,
 102         0x79B737BA, 0x8BDCB4B9, 0x988C474D, 0x6AE7C44E,
 103         0xBE2DA0A5, 0x4C4623A6, 0x5F16D052, 0xAD7D5351
 104 };
 105
 106 /*
 107  * Steps through buffer one byte at at time, calculates reflected
 108  * crc using table.
 109  */
 110 uint32_t crc32c(uint32_t crc, const void *buf, size_t size)
 111 {
 112         const uint8_t *p = buf;
 113
 114         while (size--)
 115                 crc = crc32c_tab[(crc ^ *p++) & 0xFFL] ^ (crc >> 8);
 116
 117         return crc;
 118 }
 119
 120 const uint32_t *crc32c_table(void)
 121 {
 122         return crc32c_tab;
 123 }
 124
 125 static const uint32_t crc32_ieee_tab[] = {
 126         0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f,
 127         0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
 128         0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2,
 129         0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
 130         0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9,
 131         0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
 132         0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c,
 133         0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
 134         0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423,
 135         0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
 136         0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106,
 137         0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
 138         0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d,
 139         0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
 140         0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
 141         0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
 142         0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7,
 143         0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
 144         0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa,
 145         0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
 146         0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81,
 147         0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
 148         0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84,
 149         0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
 150         0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
 151         0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
 152         0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e,
 153         0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
 154         0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55,
 155         0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
 156         0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28,
 157         0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
 158         0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f,
 159         0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
 160         0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
 161         0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
 162         0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69,
 163         0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
 164         0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc,
 165         0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
 166         0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693,
 167         0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
 168         0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
 169 };
 170
 171 uint32_t crc32_ieee(uint32_t crc, const void *buf, size_t size)
 172 {
 173         const uint8_t *p;
 174
 175         p = buf;
 176         crc ^= ~0U;
 177
 178         while (size--)
 179                 crc = crc32_ieee_tab[(crc ^ *p++) & 0xFF] ^ (crc >> 8);
 180
 181         return crc ^ ~0U;
 182 }
 183
 184 const uint32_t *crc32_ieee_table(void)
 185 {
 186         return crc32_ieee_tab;
 187 }
 188
 189 /* We only keep the upper 16 bits of the table: the lower 48 are always 0 */
 190 static uint16_t crc64_tab[] = {
 191     0x0000, 0x01b0, 0x0360,
 192     0x02d0, 0x06c0, 0x0770,
 193     0x05a0, 0x0410, 0x0d80,
 194     0x0c30, 0x0ee0, 0x0f50,
 195     0x0b40, 0x0af0, 0x0820,
 196     0x0990, 0x1b00, 0x1ab0,
 197     0x1860, 0x19d0, 0x1dc0,
 198     0x1c70, 0x1ea0, 0x1f10,
 199     0x1680, 0x1730, 0x15e0,
 200     0x1450, 0x1040, 0x11f0,
 201     0x1320, 0x1290, 0x3600,
 202     0x37b0, 0x3560, 0x34d0,
 203     0x30c0, 0x3170, 0x33a0,
 204     0x3210, 0x3b80, 0x3a30,
 205     0x38e0, 0x3950, 0x3d40,
 206     0x3cf0, 0x3e20, 0x3f90,
 207     0x2d00, 0x2cb0, 0x2e60,
 208     0x2fd0, 0x2bc0, 0x2a70,
 209     0x28a0, 0x2910, 0x2080,
 210     0x2130, 0x23e0, 0x2250,
 211     0x2640, 0x27f0, 0x2520,
 212     0x2490, 0x6c00, 0x6db0,
 213     0x6f60, 0x6ed0, 0x6ac0,
 214     0x6b70, 0x69a0, 0x6810,
 215     0x6180, 0x6030, 0x62e0,
 216     0x6350, 0x6740, 0x66f0,
 217     0x6420, 0x6590, 0x7700,
 218     0x76b0, 0x7460, 0x75d0,
 219     0x71c0, 0x7070, 0x72a0,
 220     0x7310, 0x7a80, 0x7b30,
 221     0x79e0, 0x7850, 0x7c40,
 222     0x7df0, 0x7f20, 0x7e90,
 223     0x5a00, 0x5bb0, 0x5960,
 224     0x58d0, 0x5cc0, 0x5d70,
 225     0x5fa0, 0x5e10, 0x5780,
 226     0x5630, 0x54e0, 0x5550,
 227     0x5140, 0x50f0, 0x5220,
 228     0x5390, 0x4100, 0x40b0,
 229     0x4260, 0x43d0, 0x47c0,
 230     0x4670, 0x44a0, 0x4510,
 231     0x4c80, 0x4d30, 0x4fe0,
 232     0x4e50, 0x4a40, 0x4bf0,
 233     0x4920, 0x4890, 0xd800,
 234     0xd9b0, 0xdb60, 0xdad0,
 235     0xdec0, 0xdf70, 0xdda0,
 236     0xdc10, 0xd580, 0xd430,
 237     0xd6e0, 0xd750, 0xd340,
 238     0xd2f0, 0xd020, 0xd190,
 239     0xc300, 0xc2b0, 0xc060,
 240     0xc1d0, 0xc5c0, 0xc470,
 241     0xc6a0, 0xc710, 0xce80,
 242     0xcf30, 0xcde0, 0xcc50,
 243     0xc840, 0xc9f0, 0xcb20,
 244     0xca90, 0xee00, 0xefb0,
 245     0xed60, 0xecd0, 0xe8c0,
 246     0xe970, 0xeba0, 0xea10,
 247     0xe380, 0xe230, 0xe0e0,
 248     0xe150, 0xe540, 0xe4f0,
 249     0xe620, 0xe790, 0xf500,
 250     0xf4b0, 0xf660, 0xf7d0,
 251     0xf3c0, 0xf270, 0xf0a0,
 252     0xf110, 0xf880, 0xf930,
 253     0xfbe0, 0xfa50, 0xfe40,
 254     0xfff0, 0xfd20, 0xfc90,
 255     0xb400, 0xb5b0, 0xb760,
 256     0xb6d0, 0xb2c0, 0xb370,
 257     0xb1a0, 0xb010, 0xb980,
 258     0xb830, 0xbae0, 0xbb50,
 259     0xbf40, 0xbef0, 0xbc20,
 260     0xbd90, 0xaf00, 0xaeb0,
 261     0xac60, 0xadd0, 0xa9c0,
 262     0xa870, 0xaaa0, 0xab10,
 263     0xa280, 0xa330, 0xa1e0,
 264     0xa050, 0xa440, 0xa5f0,
 265     0xa720, 0xa690, 0x8200,
 266     0x83b0, 0x8160, 0x80d0,
 267     0x84c0, 0x8570, 0x87a0,
 268     0x8610, 0x8f80, 0x8e30,
 269     0x8ce0, 0x8d50, 0x8940,
 270     0x88f0, 0x8a20, 0x8b90,
 271     0x9900, 0x98b0, 0x9a60,
 272     0x9bd0, 0x9fc0, 0x9e70,
 273     0x9ca0, 0x9d10, 0x9480,
 274     0x9530, 0x97e0, 0x9650,
 275     0x9240, 0x93f0, 0x9120,
 276     0x9090
 277 };
 278
 279 uint64_t crc64_iso(uint64_t crc, const void *buf, size_t size)
 280 {
 281         const uint8_t *p = buf;
 282
 283         while (size--) {
 284                 uint64_t tabval = crc64_tab[(crc ^ *p++) & 0xFFL];
 285                 tabval <<= 48;
 286                 crc = tabval ^ (crc >> 8);
 287         }
 288         return crc;
 289 }
 290
 291 const uint64_t *crc64_iso_table(void)
 292 {
 293         static uint64_t *fulltab = NULL;
 294         unsigned int i;
 295
 296         if (fulltab)
 297                 return fulltab;
 298
 299         fulltab = malloc(sizeof(uint64_t)*ARRAY_SIZE(crc64_tab));
 300         if (!fulltab)
 301                 return NULL;
 302
 303         for (i = 0; i < ARRAY_SIZE(crc64_tab); i++)
 304                 fulltab[i] = (uint64_t)crc64_tab[i] << 48;
 305
 306         return fulltab;
 307 }