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 #include "crc.h"
  16 #include <stdbool.h>
  17 #include <stdlib.h>
  18
  19 /*
  20  * This is the CRC-32C table
  21  * Generated with:
  22  * width = 32 bits
  23  * poly = 0x1EDC6F41
  24  * reflect input bytes = true
  25  * reflect output bytes = true
  26  */
  27 static const uint32_t crc32c_tab[] = {
  28         0x00000000, 0xF26B8303, 0xE13B70F7, 0x1350F3F4,
  29         0xC79A971F, 0x35F1141C, 0x26A1E7E8, 0xD4CA64EB,
  30         0x8AD958CF, 0x78B2DBCC, 0x6BE22838, 0x9989AB3B,
  31         0x4D43CFD0, 0xBF284CD3, 0xAC78BF27, 0x5E133C24,
  32         0x105EC76F, 0xE235446C, 0xF165B798, 0x030E349B,
  33         0xD7C45070, 0x25AFD373, 0x36FF2087, 0xC494A384,
  34         0x9A879FA0, 0x68EC1CA3, 0x7BBCEF57, 0x89D76C54,
  35         0x5D1D08BF, 0xAF768BBC, 0xBC267848, 0x4E4DFB4B,
  36         0x20BD8EDE, 0xD2D60DDD, 0xC186FE29, 0x33ED7D2A,
  37         0xE72719C1, 0x154C9AC2, 0x061C6936, 0xF477EA35,
  38         0xAA64D611, 0x580F5512, 0x4B5FA6E6, 0xB93425E5,
  39         0x6DFE410E, 0x9F95C20D, 0x8CC531F9, 0x7EAEB2FA,
  40         0x30E349B1, 0xC288CAB2, 0xD1D83946, 0x23B3BA45,
  41         0xF779DEAE, 0x05125DAD, 0x1642AE59, 0xE4292D5A,
  42         0xBA3A117E, 0x4851927D, 0x5B016189, 0xA96AE28A,
  43         0x7DA08661, 0x8FCB0562, 0x9C9BF696, 0x6EF07595,
  44         0x417B1DBC, 0xB3109EBF, 0xA0406D4B, 0x522BEE48,
  45         0x86E18AA3, 0x748A09A0, 0x67DAFA54, 0x95B17957,
  46         0xCBA24573, 0x39C9C670, 0x2A993584, 0xD8F2B687,
  47         0x0C38D26C, 0xFE53516F, 0xED03A29B, 0x1F682198,
  48         0x5125DAD3, 0xA34E59D0, 0xB01EAA24, 0x42752927,
  49         0x96BF4DCC, 0x64D4CECF, 0x77843D3B, 0x85EFBE38,
  50         0xDBFC821C, 0x2997011F, 0x3AC7F2EB, 0xC8AC71E8,
  51         0x1C661503, 0xEE0D9600, 0xFD5D65F4, 0x0F36E6F7,
  52         0x61C69362, 0x93AD1061, 0x80FDE395, 0x72966096,
  53         0xA65C047D, 0x5437877E, 0x4767748A, 0xB50CF789,
  54         0xEB1FCBAD, 0x197448AE, 0x0A24BB5A, 0xF84F3859,
  55         0x2C855CB2, 0xDEEEDFB1, 0xCDBE2C45, 0x3FD5AF46,
  56         0x7198540D, 0x83F3D70E, 0x90A324FA, 0x62C8A7F9,
  57         0xB602C312, 0x44694011, 0x5739B3E5, 0xA55230E6,
  58         0xFB410CC2, 0x092A8FC1, 0x1A7A7C35, 0xE811FF36,
  59         0x3CDB9BDD, 0xCEB018DE, 0xDDE0EB2A, 0x2F8B6829,
  60         0x82F63B78, 0x709DB87B, 0x63CD4B8F, 0x91A6C88C,
  61         0x456CAC67, 0xB7072F64, 0xA457DC90, 0x563C5F93,
  62         0x082F63B7, 0xFA44E0B4, 0xE9141340, 0x1B7F9043,
  63         0xCFB5F4A8, 0x3DDE77AB, 0x2E8E845F, 0xDCE5075C,
  64         0x92A8FC17, 0x60C37F14, 0x73938CE0, 0x81F80FE3,
  65         0x55326B08, 0xA759E80B, 0xB4091BFF, 0x466298FC,
  66         0x1871A4D8, 0xEA1A27DB, 0xF94AD42F, 0x0B21572C,
  67         0xDFEB33C7, 0x2D80B0C4, 0x3ED04330, 0xCCBBC033,
  68         0xA24BB5A6, 0x502036A5, 0x4370C551, 0xB11B4652,
  69         0x65D122B9, 0x97BAA1BA, 0x84EA524E, 0x7681D14D,
  70         0x2892ED69, 0xDAF96E6A, 0xC9A99D9E, 0x3BC21E9D,
  71         0xEF087A76, 0x1D63F975, 0x0E330A81, 0xFC588982,
  72         0xB21572C9, 0x407EF1CA, 0x532E023E, 0xA145813D,
  73         0x758FE5D6, 0x87E466D5, 0x94B49521, 0x66DF1622,
  74         0x38CC2A06, 0xCAA7A905, 0xD9F75AF1, 0x2B9CD9F2,
  75         0xFF56BD19, 0x0D3D3E1A, 0x1E6DCDEE, 0xEC064EED,
  76         0xC38D26C4, 0x31E6A5C7, 0x22B65633, 0xD0DDD530,
  77         0x0417B1DB, 0xF67C32D8, 0xE52CC12C, 0x1747422F,
  78         0x49547E0B, 0xBB3FFD08, 0xA86F0EFC, 0x5A048DFF,
  79         0x8ECEE914, 0x7CA56A17, 0x6FF599E3, 0x9D9E1AE0,
  80         0xD3D3E1AB, 0x21B862A8, 0x32E8915C, 0xC083125F,
  81         0x144976B4, 0xE622F5B7, 0xF5720643, 0x07198540,
  82         0x590AB964, 0xAB613A67, 0xB831C993, 0x4A5A4A90,
  83         0x9E902E7B, 0x6CFBAD78, 0x7FAB5E8C, 0x8DC0DD8F,
  84         0xE330A81A, 0x115B2B19, 0x020BD8ED, 0xF0605BEE,
  85         0x24AA3F05, 0xD6C1BC06, 0xC5914FF2, 0x37FACCF1,
  86         0x69E9F0D5, 0x9B8273D6, 0x88D28022, 0x7AB90321,
  87         0xAE7367CA, 0x5C18E4C9, 0x4F48173D, 0xBD23943E,
  88         0xF36E6F75, 0x0105EC76, 0x12551F82, 0xE03E9C81,
  89         0x34F4F86A, 0xC69F7B69, 0xD5CF889D, 0x27A40B9E,
  90         0x79B737BA, 0x8BDCB4B9, 0x988C474D, 0x6AE7C44E,
  91         0xBE2DA0A5, 0x4C4623A6, 0x5F16D052, 0xAD7D5351
  92 };
  93
  94 /*
  95  * Steps through buffer one byte at at time, calculates reflected
  96  * crc using table.
  97  */
  98 uint32_t crc32c(uint32_t crc, const void *buf, size_t size)
  99 {
 100         const uint8_t *p = buf;
 101
 102         while (size--)
 103                 crc = crc32c_tab[(crc ^ *p++) & 0xFFL] ^ (crc >> 8);
 104
 105         return crc;
 106 }
 107
 108 const uint32_t *crc32c_table(void)
 109 {
 110         return crc32c_tab;
 111 }
 112
 113 static const uint32_t crc32_ieee_tab[] = {
 114         0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f,
 115         0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
 116         0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2,
 117         0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
 118         0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9,
 119         0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
 120         0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c,
 121         0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
 122         0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423,
 123         0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
 124         0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106,
 125         0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
 126         0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d,
 127         0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
 128         0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
 129         0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
 130         0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7,
 131         0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
 132         0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa,
 133         0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
 134         0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81,
 135         0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
 136         0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84,
 137         0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
 138         0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
 139         0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
 140         0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e,
 141         0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
 142         0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55,
 143         0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
 144         0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28,
 145         0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
 146         0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f,
 147         0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
 148         0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
 149         0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
 150         0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69,
 151         0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
 152         0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc,
 153         0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
 154         0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693,
 155         0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
 156         0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
 157 };
 158
 159 uint32_t crc32_ieee(uint32_t crc, const void *buf, size_t size)
 160 {
 161         const uint8_t *p;
 162
 163         p = buf;
 164         crc ^= ~0U;
 165
 166         while (size--)
 167                 crc = crc32_ieee_tab[(crc ^ *p++) & 0xFF] ^ (crc >> 8);
 168
 169         return crc ^ ~0U;
 170 }
 171
 172 const uint32_t *crc32_ieee_table(void)
 173 {
 174         return crc32_ieee_tab;
 175 }