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 static const uint32_t crc32_ieee_tab[] = {
  32         0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f,
  33         0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
  34         0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2,
  35         0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
  36         0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9,
  37         0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
  38         0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c,
  39         0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
  40         0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423,
  41         0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
  42         0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106,
  43         0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
  44         0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d,
  45         0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
  46         0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
  47         0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
  48         0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7,
  49         0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
  50         0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa,
  51         0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
  52         0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81,
  53         0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
  54         0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84,
  55         0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
  56         0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
  57         0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
  58         0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e,
  59         0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
  60         0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55,
  61         0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
  62         0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28,
  63         0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
  64         0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f,
  65         0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
  66         0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
  67         0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
  68         0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69,
  69         0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
  70         0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc,
  71         0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
  72         0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693,
  73         0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
  74         0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
  75 };
  76
  77 uint32_t crc32_ieee(uint32_t crc, const void *buf, size_t size)
  78 {
  79         const uint8_t *p;
  80
  81         p = buf;
  82         crc ^= ~0U;
  83
  84         while (size--)
  85                 crc = crc32_ieee_tab[(crc ^ *p++) & 0xFF] ^ (crc >> 8);
  86
  87         return crc ^ ~0U;
  88 }
  89
  90 const uint32_t *crc32_ieee_table(void)
  91 {
  92         return crc32_ieee_tab;
  93 }
  94
  95 /* We only keep the upper 16 bits of the table: the lower 48 are always 0 */
  96 static uint16_t crc64_tab[] = {
  97     0x0000, 0x01b0, 0x0360,
  98     0x02d0, 0x06c0, 0x0770,
  99     0x05a0, 0x0410, 0x0d80,
 100     0x0c30, 0x0ee0, 0x0f50,
 101     0x0b40, 0x0af0, 0x0820,
 102     0x0990, 0x1b00, 0x1ab0,
 103     0x1860, 0x19d0, 0x1dc0,
 104     0x1c70, 0x1ea0, 0x1f10,
 105     0x1680, 0x1730, 0x15e0,
 106     0x1450, 0x1040, 0x11f0,
 107     0x1320, 0x1290, 0x3600,
 108     0x37b0, 0x3560, 0x34d0,
 109     0x30c0, 0x3170, 0x33a0,
 110     0x3210, 0x3b80, 0x3a30,
 111     0x38e0, 0x3950, 0x3d40,
 112     0x3cf0, 0x3e20, 0x3f90,
 113     0x2d00, 0x2cb0, 0x2e60,
 114     0x2fd0, 0x2bc0, 0x2a70,
 115     0x28a0, 0x2910, 0x2080,
 116     0x2130, 0x23e0, 0x2250,
 117     0x2640, 0x27f0, 0x2520,
 118     0x2490, 0x6c00, 0x6db0,
 119     0x6f60, 0x6ed0, 0x6ac0,
 120     0x6b70, 0x69a0, 0x6810,
 121     0x6180, 0x6030, 0x62e0,
 122     0x6350, 0x6740, 0x66f0,
 123     0x6420, 0x6590, 0x7700,
 124     0x76b0, 0x7460, 0x75d0,
 125     0x71c0, 0x7070, 0x72a0,
 126     0x7310, 0x7a80, 0x7b30,
 127     0x79e0, 0x7850, 0x7c40,
 128     0x7df0, 0x7f20, 0x7e90,
 129     0x5a00, 0x5bb0, 0x5960,
 130     0x58d0, 0x5cc0, 0x5d70,
 131     0x5fa0, 0x5e10, 0x5780,
 132     0x5630, 0x54e0, 0x5550,
 133     0x5140, 0x50f0, 0x5220,
 134     0x5390, 0x4100, 0x40b0,
 135     0x4260, 0x43d0, 0x47c0,
 136     0x4670, 0x44a0, 0x4510,
 137     0x4c80, 0x4d30, 0x4fe0,
 138     0x4e50, 0x4a40, 0x4bf0,
 139     0x4920, 0x4890, 0xd800,
 140     0xd9b0, 0xdb60, 0xdad0,
 141     0xdec0, 0xdf70, 0xdda0,
 142     0xdc10, 0xd580, 0xd430,
 143     0xd6e0, 0xd750, 0xd340,
 144     0xd2f0, 0xd020, 0xd190,
 145     0xc300, 0xc2b0, 0xc060,
 146     0xc1d0, 0xc5c0, 0xc470,
 147     0xc6a0, 0xc710, 0xce80,
 148     0xcf30, 0xcde0, 0xcc50,
 149     0xc840, 0xc9f0, 0xcb20,
 150     0xca90, 0xee00, 0xefb0,
 151     0xed60, 0xecd0, 0xe8c0,
 152     0xe970, 0xeba0, 0xea10,
 153     0xe380, 0xe230, 0xe0e0,
 154     0xe150, 0xe540, 0xe4f0,
 155     0xe620, 0xe790, 0xf500,
 156     0xf4b0, 0xf660, 0xf7d0,
 157     0xf3c0, 0xf270, 0xf0a0,
 158     0xf110, 0xf880, 0xf930,
 159     0xfbe0, 0xfa50, 0xfe40,
 160     0xfff0, 0xfd20, 0xfc90,
 161     0xb400, 0xb5b0, 0xb760,
 162     0xb6d0, 0xb2c0, 0xb370,
 163     0xb1a0, 0xb010, 0xb980,
 164     0xb830, 0xbae0, 0xbb50,
 165     0xbf40, 0xbef0, 0xbc20,
 166     0xbd90, 0xaf00, 0xaeb0,
 167     0xac60, 0xadd0, 0xa9c0,
 168     0xa870, 0xaaa0, 0xab10,
 169     0xa280, 0xa330, 0xa1e0,
 170     0xa050, 0xa440, 0xa5f0,
 171     0xa720, 0xa690, 0x8200,
 172     0x83b0, 0x8160, 0x80d0,
 173     0x84c0, 0x8570, 0x87a0,
 174     0x8610, 0x8f80, 0x8e30,
 175     0x8ce0, 0x8d50, 0x8940,
 176     0x88f0, 0x8a20, 0x8b90,
 177     0x9900, 0x98b0, 0x9a60,
 178     0x9bd0, 0x9fc0, 0x9e70,
 179     0x9ca0, 0x9d10, 0x9480,
 180     0x9530, 0x97e0, 0x9650,
 181     0x9240, 0x93f0, 0x9120,
 182     0x9090
 183 };
 184
 185 uint64_t crc64_iso(uint64_t crc, const void *buf, size_t size)
 186 {
 187         const uint8_t *p = buf;
 188
 189         while (size--) {
 190                 uint64_t tabval = crc64_tab[(crc ^ *p++) & 0xFFL];
 191                 tabval <<= 48;
 192                 crc = tabval ^ (crc >> 8);
 193         }
 194         return crc;
 195 }
 196
 197 const uint64_t *crc64_iso_table(void)
 198 {
 199         static uint64_t *fulltab = NULL;
 200         unsigned int i;
 201
 202         if (fulltab)
 203                 return fulltab;
 204
 205         fulltab = malloc(sizeof(uint64_t)*ARRAY_SIZE(crc64_tab));
 206         if (!fulltab)
 207                 return NULL;
 208
 209         for (i = 0; i < ARRAY_SIZE(crc64_tab); i++)
 210                 fulltab[i] = (uint64_t)crc64_tab[i] << 48;
 211
 212         return fulltab;
 213 }