64-bit CRC code.
[ccan] / 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 <stdbool.h>
28 #include <stdlib.h>
29
30 /*
31  * This is the CRC-32C table
32  * Generated with:
33  * width = 32 bits
34  * poly = 0x1EDC6F41
35  * reflect input bytes = true
36  * reflect output bytes = true
37  */
38 static const uint32_t crc32c_tab[] = {
39         0x00000000, 0xF26B8303, 0xE13B70F7, 0x1350F3F4,
40         0xC79A971F, 0x35F1141C, 0x26A1E7E8, 0xD4CA64EB,
41         0x8AD958CF, 0x78B2DBCC, 0x6BE22838, 0x9989AB3B,
42         0x4D43CFD0, 0xBF284CD3, 0xAC78BF27, 0x5E133C24,
43         0x105EC76F, 0xE235446C, 0xF165B798, 0x030E349B,
44         0xD7C45070, 0x25AFD373, 0x36FF2087, 0xC494A384,
45         0x9A879FA0, 0x68EC1CA3, 0x7BBCEF57, 0x89D76C54,
46         0x5D1D08BF, 0xAF768BBC, 0xBC267848, 0x4E4DFB4B,
47         0x20BD8EDE, 0xD2D60DDD, 0xC186FE29, 0x33ED7D2A,
48         0xE72719C1, 0x154C9AC2, 0x061C6936, 0xF477EA35,
49         0xAA64D611, 0x580F5512, 0x4B5FA6E6, 0xB93425E5,
50         0x6DFE410E, 0x9F95C20D, 0x8CC531F9, 0x7EAEB2FA,
51         0x30E349B1, 0xC288CAB2, 0xD1D83946, 0x23B3BA45,
52         0xF779DEAE, 0x05125DAD, 0x1642AE59, 0xE4292D5A,
53         0xBA3A117E, 0x4851927D, 0x5B016189, 0xA96AE28A,
54         0x7DA08661, 0x8FCB0562, 0x9C9BF696, 0x6EF07595,
55         0x417B1DBC, 0xB3109EBF, 0xA0406D4B, 0x522BEE48,
56         0x86E18AA3, 0x748A09A0, 0x67DAFA54, 0x95B17957,
57         0xCBA24573, 0x39C9C670, 0x2A993584, 0xD8F2B687,
58         0x0C38D26C, 0xFE53516F, 0xED03A29B, 0x1F682198,
59         0x5125DAD3, 0xA34E59D0, 0xB01EAA24, 0x42752927,
60         0x96BF4DCC, 0x64D4CECF, 0x77843D3B, 0x85EFBE38,
61         0xDBFC821C, 0x2997011F, 0x3AC7F2EB, 0xC8AC71E8,
62         0x1C661503, 0xEE0D9600, 0xFD5D65F4, 0x0F36E6F7,
63         0x61C69362, 0x93AD1061, 0x80FDE395, 0x72966096,
64         0xA65C047D, 0x5437877E, 0x4767748A, 0xB50CF789,
65         0xEB1FCBAD, 0x197448AE, 0x0A24BB5A, 0xF84F3859,
66         0x2C855CB2, 0xDEEEDFB1, 0xCDBE2C45, 0x3FD5AF46,
67         0x7198540D, 0x83F3D70E, 0x90A324FA, 0x62C8A7F9,
68         0xB602C312, 0x44694011, 0x5739B3E5, 0xA55230E6,
69         0xFB410CC2, 0x092A8FC1, 0x1A7A7C35, 0xE811FF36,
70         0x3CDB9BDD, 0xCEB018DE, 0xDDE0EB2A, 0x2F8B6829,
71         0x82F63B78, 0x709DB87B, 0x63CD4B8F, 0x91A6C88C,
72         0x456CAC67, 0xB7072F64, 0xA457DC90, 0x563C5F93,
73         0x082F63B7, 0xFA44E0B4, 0xE9141340, 0x1B7F9043,
74         0xCFB5F4A8, 0x3DDE77AB, 0x2E8E845F, 0xDCE5075C,
75         0x92A8FC17, 0x60C37F14, 0x73938CE0, 0x81F80FE3,
76         0x55326B08, 0xA759E80B, 0xB4091BFF, 0x466298FC,
77         0x1871A4D8, 0xEA1A27DB, 0xF94AD42F, 0x0B21572C,
78         0xDFEB33C7, 0x2D80B0C4, 0x3ED04330, 0xCCBBC033,
79         0xA24BB5A6, 0x502036A5, 0x4370C551, 0xB11B4652,
80         0x65D122B9, 0x97BAA1BA, 0x84EA524E, 0x7681D14D,
81         0x2892ED69, 0xDAF96E6A, 0xC9A99D9E, 0x3BC21E9D,
82         0xEF087A76, 0x1D63F975, 0x0E330A81, 0xFC588982,
83         0xB21572C9, 0x407EF1CA, 0x532E023E, 0xA145813D,
84         0x758FE5D6, 0x87E466D5, 0x94B49521, 0x66DF1622,
85         0x38CC2A06, 0xCAA7A905, 0xD9F75AF1, 0x2B9CD9F2,
86         0xFF56BD19, 0x0D3D3E1A, 0x1E6DCDEE, 0xEC064EED,
87         0xC38D26C4, 0x31E6A5C7, 0x22B65633, 0xD0DDD530,
88         0x0417B1DB, 0xF67C32D8, 0xE52CC12C, 0x1747422F,
89         0x49547E0B, 0xBB3FFD08, 0xA86F0EFC, 0x5A048DFF,
90         0x8ECEE914, 0x7CA56A17, 0x6FF599E3, 0x9D9E1AE0,
91         0xD3D3E1AB, 0x21B862A8, 0x32E8915C, 0xC083125F,
92         0x144976B4, 0xE622F5B7, 0xF5720643, 0x07198540,
93         0x590AB964, 0xAB613A67, 0xB831C993, 0x4A5A4A90,
94         0x9E902E7B, 0x6CFBAD78, 0x7FAB5E8C, 0x8DC0DD8F,
95         0xE330A81A, 0x115B2B19, 0x020BD8ED, 0xF0605BEE,
96         0x24AA3F05, 0xD6C1BC06, 0xC5914FF2, 0x37FACCF1,
97         0x69E9F0D5, 0x9B8273D6, 0x88D28022, 0x7AB90321,
98         0xAE7367CA, 0x5C18E4C9, 0x4F48173D, 0xBD23943E,
99         0xF36E6F75, 0x0105EC76, 0x12551F82, 0xE03E9C81,
100         0x34F4F86A, 0xC69F7B69, 0xD5CF889D, 0x27A40B9E,
101         0x79B737BA, 0x8BDCB4B9, 0x988C474D, 0x6AE7C44E,
102         0xBE2DA0A5, 0x4C4623A6, 0x5F16D052, 0xAD7D5351
103 };
104
105 /*
106  * Steps through buffer one byte at at time, calculates reflected
107  * crc using table.
108  */
109 uint32_t crc32c(uint32_t crc, const void *buf, size_t size)
110 {
111         const uint8_t *p = buf;
112
113         while (size--)
114                 crc = crc32c_tab[(crc ^ *p++) & 0xFFL] ^ (crc >> 8);
115
116         return crc;
117 }
118
119 const uint32_t *crc32c_table(void)
120 {
121         return crc32c_tab;
122 }
123
124 static const uint32_t crc32_ieee_tab[] = {
125         0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f,
126         0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
127         0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2,
128         0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
129         0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9,
130         0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
131         0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c,
132         0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
133         0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423,
134         0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
135         0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106,
136         0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
137         0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d,
138         0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
139         0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
140         0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
141         0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7,
142         0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
143         0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa,
144         0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
145         0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81,
146         0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
147         0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84,
148         0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
149         0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
150         0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
151         0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e,
152         0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
153         0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55,
154         0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
155         0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28,
156         0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
157         0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f,
158         0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
159         0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
160         0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
161         0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69,
162         0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
163         0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc,
164         0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
165         0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693,
166         0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
167         0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
168 };
169
170 uint32_t crc32_ieee(uint32_t crc, const void *buf, size_t size)
171 {
172         const uint8_t *p;
173
174         p = buf;
175         crc ^= ~0U;
176
177         while (size--)
178                 crc = crc32_ieee_tab[(crc ^ *p++) & 0xFF] ^ (crc >> 8);
179
180         return crc ^ ~0U;
181 }
182
183 const uint32_t *crc32_ieee_table(void)
184 {
185         return crc32_ieee_tab;
186 }
187
188 static uint64_t crc64_tab[] = {
189     0x0000000000000000ULL, 0x01b0000000000000ULL, 0x0360000000000000ULL,
190     0x02d0000000000000ULL, 0x06c0000000000000ULL, 0x0770000000000000ULL,
191     0x05a0000000000000ULL, 0x0410000000000000ULL, 0x0d80000000000000ULL,
192     0x0c30000000000000ULL, 0x0ee0000000000000ULL, 0x0f50000000000000ULL,
193     0x0b40000000000000ULL, 0x0af0000000000000ULL, 0x0820000000000000ULL,
194     0x0990000000000000ULL, 0x1b00000000000000ULL, 0x1ab0000000000000ULL,
195     0x1860000000000000ULL, 0x19d0000000000000ULL, 0x1dc0000000000000ULL,
196     0x1c70000000000000ULL, 0x1ea0000000000000ULL, 0x1f10000000000000ULL,
197     0x1680000000000000ULL, 0x1730000000000000ULL, 0x15e0000000000000ULL,
198     0x1450000000000000ULL, 0x1040000000000000ULL, 0x11f0000000000000ULL,
199     0x1320000000000000ULL, 0x1290000000000000ULL, 0x3600000000000000ULL,
200     0x37b0000000000000ULL, 0x3560000000000000ULL, 0x34d0000000000000ULL,
201     0x30c0000000000000ULL, 0x3170000000000000ULL, 0x33a0000000000000ULL,
202     0x3210000000000000ULL, 0x3b80000000000000ULL, 0x3a30000000000000ULL,
203     0x38e0000000000000ULL, 0x3950000000000000ULL, 0x3d40000000000000ULL,
204     0x3cf0000000000000ULL, 0x3e20000000000000ULL, 0x3f90000000000000ULL,
205     0x2d00000000000000ULL, 0x2cb0000000000000ULL, 0x2e60000000000000ULL,
206     0x2fd0000000000000ULL, 0x2bc0000000000000ULL, 0x2a70000000000000ULL,
207     0x28a0000000000000ULL, 0x2910000000000000ULL, 0x2080000000000000ULL,
208     0x2130000000000000ULL, 0x23e0000000000000ULL, 0x2250000000000000ULL,
209     0x2640000000000000ULL, 0x27f0000000000000ULL, 0x2520000000000000ULL,
210     0x2490000000000000ULL, 0x6c00000000000000ULL, 0x6db0000000000000ULL,
211     0x6f60000000000000ULL, 0x6ed0000000000000ULL, 0x6ac0000000000000ULL,
212     0x6b70000000000000ULL, 0x69a0000000000000ULL, 0x6810000000000000ULL,
213     0x6180000000000000ULL, 0x6030000000000000ULL, 0x62e0000000000000ULL,
214     0x6350000000000000ULL, 0x6740000000000000ULL, 0x66f0000000000000ULL,
215     0x6420000000000000ULL, 0x6590000000000000ULL, 0x7700000000000000ULL,
216     0x76b0000000000000ULL, 0x7460000000000000ULL, 0x75d0000000000000ULL,
217     0x71c0000000000000ULL, 0x7070000000000000ULL, 0x72a0000000000000ULL,
218     0x7310000000000000ULL, 0x7a80000000000000ULL, 0x7b30000000000000ULL,
219     0x79e0000000000000ULL, 0x7850000000000000ULL, 0x7c40000000000000ULL,
220     0x7df0000000000000ULL, 0x7f20000000000000ULL, 0x7e90000000000000ULL,
221     0x5a00000000000000ULL, 0x5bb0000000000000ULL, 0x5960000000000000ULL,
222     0x58d0000000000000ULL, 0x5cc0000000000000ULL, 0x5d70000000000000ULL,
223     0x5fa0000000000000ULL, 0x5e10000000000000ULL, 0x5780000000000000ULL,
224     0x5630000000000000ULL, 0x54e0000000000000ULL, 0x5550000000000000ULL,
225     0x5140000000000000ULL, 0x50f0000000000000ULL, 0x5220000000000000ULL,
226     0x5390000000000000ULL, 0x4100000000000000ULL, 0x40b0000000000000ULL,
227     0x4260000000000000ULL, 0x43d0000000000000ULL, 0x47c0000000000000ULL,
228     0x4670000000000000ULL, 0x44a0000000000000ULL, 0x4510000000000000ULL,
229     0x4c80000000000000ULL, 0x4d30000000000000ULL, 0x4fe0000000000000ULL,
230     0x4e50000000000000ULL, 0x4a40000000000000ULL, 0x4bf0000000000000ULL,
231     0x4920000000000000ULL, 0x4890000000000000ULL, 0xd800000000000000ULL,
232     0xd9b0000000000000ULL, 0xdb60000000000000ULL, 0xdad0000000000000ULL,
233     0xdec0000000000000ULL, 0xdf70000000000000ULL, 0xdda0000000000000ULL,
234     0xdc10000000000000ULL, 0xd580000000000000ULL, 0xd430000000000000ULL,
235     0xd6e0000000000000ULL, 0xd750000000000000ULL, 0xd340000000000000ULL,
236     0xd2f0000000000000ULL, 0xd020000000000000ULL, 0xd190000000000000ULL,
237     0xc300000000000000ULL, 0xc2b0000000000000ULL, 0xc060000000000000ULL,
238     0xc1d0000000000000ULL, 0xc5c0000000000000ULL, 0xc470000000000000ULL,
239     0xc6a0000000000000ULL, 0xc710000000000000ULL, 0xce80000000000000ULL,
240     0xcf30000000000000ULL, 0xcde0000000000000ULL, 0xcc50000000000000ULL,
241     0xc840000000000000ULL, 0xc9f0000000000000ULL, 0xcb20000000000000ULL,
242     0xca90000000000000ULL, 0xee00000000000000ULL, 0xefb0000000000000ULL,
243     0xed60000000000000ULL, 0xecd0000000000000ULL, 0xe8c0000000000000ULL,
244     0xe970000000000000ULL, 0xeba0000000000000ULL, 0xea10000000000000ULL,
245     0xe380000000000000ULL, 0xe230000000000000ULL, 0xe0e0000000000000ULL,
246     0xe150000000000000ULL, 0xe540000000000000ULL, 0xe4f0000000000000ULL,
247     0xe620000000000000ULL, 0xe790000000000000ULL, 0xf500000000000000ULL,
248     0xf4b0000000000000ULL, 0xf660000000000000ULL, 0xf7d0000000000000ULL,
249     0xf3c0000000000000ULL, 0xf270000000000000ULL, 0xf0a0000000000000ULL,
250     0xf110000000000000ULL, 0xf880000000000000ULL, 0xf930000000000000ULL,
251     0xfbe0000000000000ULL, 0xfa50000000000000ULL, 0xfe40000000000000ULL,
252     0xfff0000000000000ULL, 0xfd20000000000000ULL, 0xfc90000000000000ULL,
253     0xb400000000000000ULL, 0xb5b0000000000000ULL, 0xb760000000000000ULL,
254     0xb6d0000000000000ULL, 0xb2c0000000000000ULL, 0xb370000000000000ULL,
255     0xb1a0000000000000ULL, 0xb010000000000000ULL, 0xb980000000000000ULL,
256     0xb830000000000000ULL, 0xbae0000000000000ULL, 0xbb50000000000000ULL,
257     0xbf40000000000000ULL, 0xbef0000000000000ULL, 0xbc20000000000000ULL,
258     0xbd90000000000000ULL, 0xaf00000000000000ULL, 0xaeb0000000000000ULL,
259     0xac60000000000000ULL, 0xadd0000000000000ULL, 0xa9c0000000000000ULL,
260     0xa870000000000000ULL, 0xaaa0000000000000ULL, 0xab10000000000000ULL,
261     0xa280000000000000ULL, 0xa330000000000000ULL, 0xa1e0000000000000ULL,
262     0xa050000000000000ULL, 0xa440000000000000ULL, 0xa5f0000000000000ULL,
263     0xa720000000000000ULL, 0xa690000000000000ULL, 0x8200000000000000ULL,
264     0x83b0000000000000ULL, 0x8160000000000000ULL, 0x80d0000000000000ULL,
265     0x84c0000000000000ULL, 0x8570000000000000ULL, 0x87a0000000000000ULL,
266     0x8610000000000000ULL, 0x8f80000000000000ULL, 0x8e30000000000000ULL,
267     0x8ce0000000000000ULL, 0x8d50000000000000ULL, 0x8940000000000000ULL,
268     0x88f0000000000000ULL, 0x8a20000000000000ULL, 0x8b90000000000000ULL,
269     0x9900000000000000ULL, 0x98b0000000000000ULL, 0x9a60000000000000ULL,
270     0x9bd0000000000000ULL, 0x9fc0000000000000ULL, 0x9e70000000000000ULL,
271     0x9ca0000000000000ULL, 0x9d10000000000000ULL, 0x9480000000000000ULL,
272     0x9530000000000000ULL, 0x97e0000000000000ULL, 0x9650000000000000ULL,
273     0x9240000000000000ULL, 0x93f0000000000000ULL, 0x9120000000000000ULL,
274     0x9090000000000000ULL
275 };
276
277 uint64_t crc64_iso(uint64_t crc, const void *buf, size_t size)
278 {
279         const uint8_t *p = buf;
280
281         while (size--)
282                 crc = crc64_tab[(crc ^ *p++) & 0xFFL] ^ (crc >> 8);
283
284         return crc;
285 }
286
287 const uint64_t *crc64_iso_table(void)
288 {
289         return crc64_tab;
290 }