1 /* Crc64.cc -- compute CRC-64
2 * Copyright (C) 2013 Mark Adler
3 * Version 1.4 16 Dec 2013 Mark Adler
4 */
5
6 /*
7 This software is provided 'as-is', without any express or implied
8 warranty. In no event will the author be held liable for any damages
9 arising from the use of this software.
10
11 Permission is granted to anyone to use this software for any purpose,
12 including commercial applications, and to alter it and redistribute it
13 freely, subject to the following restrictions:
14
15 1. The origin of this software must not be misrepresented; you must not
16 claim that you wrote the original software. If you use this software
17 in a product, an acknowledgment in the product documentation would be
18 appreciated but is not required.
19 2. Altered source versions must be plainly marked as such, and must not be
20 misrepresented as being the original software.
21 3. This notice may not be removed or altered from any source distribution.
22
23 Mark Adler
24 madler@alumni.caltech.edu
25 */
26
27 /* Compute CRC-64 in the manner of xz, using the ECMA-182 polynomial,
28 bit-reversed, with one's complement pre and post processing. Provide a
29 means to combine separately computed CRC-64's. */
30
31 /* Version history:
32 1.0 13 Dec 2013 First version
33 1.1 13 Dec 2013 Fix comments in test code
34 1.2 14 Dec 2013 Determine endianess at run time
35 1.3 15 Dec 2013 Add eight-byte processing for big endian as well
36 Make use of the pthread library optional
37 1.4 16 Dec 2013 Make once variable volatile for limited thread protection
38 */
39
40 #include "Crc64.h"
41 namespace AlibabaCloud
42 {
43 namespace OSS
44 {
45 /* 64-bit CRC polynomial with these coefficients, but reversed:
46 64, 62, 57, 55, 54, 53, 52, 47, 46, 45, 40, 39, 38, 37, 35, 33, 32,
47 31, 29, 27, 24, 23, 22, 21, 19, 17, 13, 12, 10, 9, 7, 4, 1, 0 */
48 #define POLY UINT64_C(0xc96c5795d7870f42)
49
50 /* Tables for CRC calculation -- filled in by initialization functions that are
51 called once. These could be replaced by constant tables generated in the
52 same way. There are two tables, one for each endianess. Since these are
53 static, i.e. local, one should be compiled out of existence if the compiler
54 can evaluate the endianess check in crc64() at compile time. */
55 static uint64_t crc64_table[8][256];
56
57 /* Fill in the CRC-64 constants table. */
crc64_init(uint64_t table[][256])58 static void crc64_init(uint64_t table[][256])
59 {
60 unsigned n, k;
61 uint64_t crc;
62
63 /* generate CRC-64's for all single byte sequences */
64 for (n = 0; n < 256; n++) {
65 crc = n;
66 for (k = 0; k < 8; k++)
67 crc = crc & 1 ? POLY ^ (crc >> 1) : crc >> 1;
68 table[0][n] = crc;
69 }
70
71 /* generate CRC-64's for those followed by 1 to 7 zeros */
72 for (n = 0; n < 256; n++) {
73 crc = table[0][n];
74 for (k = 1; k < 8; k++) {
75 crc = table[0][crc & 0xff] ^ (crc >> 8);
76 table[k][n] = crc;
77 }
78 }
79 }
80
81 /* This function is called once to initialize the CRC-64 table for use on a
82 little-endian architecture. */
crc64_little_init(void)83 static void crc64_little_init(void)
84 {
85 crc64_init(crc64_table);
86 }
87
88 /* Reverse the bytes in a 64-bit word. */
rev8(uint64_t a)89 static uint64_t rev8(uint64_t a)
90 {
91 uint64_t m;
92
93 m = UINT64_C(0xff00ff00ff00ff);
94 a = ((a >> 8) & m) | (a & m) << 8;
95 m = UINT64_C(0xffff0000ffff);
96 a = ((a >> 16) & m) | (a & m) << 16;
97 return a >> 32 | a << 32;
98 }
99
100 /* This function is called once to initialize the CRC-64 table for use on a
101 big-endian architecture. */
crc64_big_init(void)102 static void crc64_big_init(void)
103 {
104 unsigned k, n;
105
106 crc64_init(crc64_table);
107 for (k = 0; k < 8; k++)
108 for (n = 0; n < 256; n++)
109 crc64_table[k][n] = rev8(crc64_table[k][n]);
110 }
111
112 /* Calculate a CRC-64 eight bytes at a time on a little-endian architecture. */
crc64_little(uint64_t crc,void * buf,size_t len)113 static uint64_t crc64_little(uint64_t crc, void *buf, size_t len)
114 {
115 unsigned char *next = (unsigned char *)buf;
116
117 crc = ~crc;
118 while (len && ((uintptr_t)next & 7) != 0) {
119 crc = crc64_table[0][(crc ^ *next++) & 0xff] ^ (crc >> 8);
120 len--;
121 }
122 while (len >= 8) {
123 crc ^= *(uint64_t *)next;
124 crc = crc64_table[7][crc & 0xff] ^
125 crc64_table[6][(crc >> 8) & 0xff] ^
126 crc64_table[5][(crc >> 16) & 0xff] ^
127 crc64_table[4][(crc >> 24) & 0xff] ^
128 crc64_table[3][(crc >> 32) & 0xff] ^
129 crc64_table[2][(crc >> 40) & 0xff] ^
130 crc64_table[1][(crc >> 48) & 0xff] ^
131 crc64_table[0][crc >> 56];
132 next += 8;
133 len -= 8;
134 }
135 while (len) {
136 crc = crc64_table[0][(crc ^ *next++) & 0xff] ^ (crc >> 8);
137 len--;
138 }
139 return ~crc;
140 }
141
142 /* Calculate a CRC-64 eight bytes at a time on a big-endian architecture. */
crc64_big(uint64_t crc,void * buf,size_t len)143 static uint64_t crc64_big(uint64_t crc, void *buf, size_t len)
144 {
145 unsigned char *next = (unsigned char *)buf;
146
147 crc = ~rev8(crc);
148 while (len && ((uintptr_t)next & 7) != 0) {
149 crc = crc64_table[0][(crc >> 56) ^ *next++] ^ (crc << 8);
150 len--;
151 }
152 while (len >= 8) {
153 crc ^= *(uint64_t *)next;
154 crc = crc64_table[0][crc & 0xff] ^
155 crc64_table[1][(crc >> 8) & 0xff] ^
156 crc64_table[2][(crc >> 16) & 0xff] ^
157 crc64_table[3][(crc >> 24) & 0xff] ^
158 crc64_table[4][(crc >> 32) & 0xff] ^
159 crc64_table[5][(crc >> 40) & 0xff] ^
160 crc64_table[6][(crc >> 48) & 0xff] ^
161 crc64_table[7][crc >> 56];
162 next += 8;
163 len -= 8;
164 }
165 while (len) {
166 crc = crc64_table[0][(crc >> 56) ^ *next++] ^ (crc << 8);
167 len--;
168 }
169 return ~rev8(crc);
170 }
171
172 /* Return the CRC-64 of buf[0..len-1] with initial crc, processing eight bytes
173 at a time. This selects one of two routines depending on the endianess of
174 the architecture. A good optimizing compiler will determine the endianess
175 at compile time if it can, and get rid of the unused code and table. If the
176 endianess can be changed at run time, then this code will handle that as
177 well, initializing and using two tables, if called upon to do so. */
178
179
180 #define GF2_DIM 64 /* dimension of GF(2) vectors (length of CRC) */
181
gf2_matrix_times(uint64_t * mat,uint64_t vec)182 static uint64_t gf2_matrix_times(uint64_t *mat, uint64_t vec)
183 {
184 uint64_t sum;
185
186 sum = 0;
187 while (vec) {
188 if (vec & 1)
189 sum ^= *mat;
190 vec >>= 1;
191 mat++;
192 }
193 return sum;
194 }
195
gf2_matrix_square(uint64_t * square,uint64_t * mat)196 static void gf2_matrix_square(uint64_t *square, uint64_t *mat)
197 {
198 unsigned n;
199
200 for (n = 0; n < GF2_DIM; n++)
201 square[n] = gf2_matrix_times(mat, mat[n]);
202 }
203
204 /* Return the CRC-64 of two sequential blocks, where crc1 is the CRC-64 of the
205 first block, crc2 is the CRC-64 of the second block, and len2 is the length
206 of the second block. */
crc64_combine(uint64_t crc1,uint64_t crc2,uintmax_t len2)207 static uint64_t crc64_combine(uint64_t crc1, uint64_t crc2, uintmax_t len2)
208 {
209 unsigned n;
210 uint64_t row;
211 uint64_t even[GF2_DIM]; /* even-power-of-two zeros operator */
212 uint64_t odd[GF2_DIM]; /* odd-power-of-two zeros operator */
213
214 /* degenerate case */
215 if (len2 == 0)
216 return crc1;
217
218 /* put operator for one zero bit in odd */
219 odd[0] = POLY; /* CRC-64 polynomial */
220 row = 1;
221 for (n = 1; n < GF2_DIM; n++) {
222 odd[n] = row;
223 row <<= 1;
224 }
225
226 /* put operator for two zero bits in even */
227 gf2_matrix_square(even, odd);
228
229 /* put operator for four zero bits in odd */
230 gf2_matrix_square(odd, even);
231
232 /* apply len2 zeros to crc1 (first square will put the operator for one
233 zero byte, eight zero bits, in even) */
234 do {
235 /* apply zeros operator for this bit of len2 */
236 gf2_matrix_square(even, odd);
237 if (len2 & 1)
238 crc1 = gf2_matrix_times(even, crc1);
239 len2 >>= 1;
240
241 /* if no more bits set, then done */
242 if (len2 == 0)
243 break;
244
245 /* another iteration of the loop with odd and even swapped */
246 gf2_matrix_square(odd, even);
247 if (len2 & 1)
248 crc1 = gf2_matrix_times(odd, crc1);
249 len2 >>= 1;
250
251 /* if no more bits set, then done */
252 } while (len2 != 0);
253
254 /* return combined crc */
255 crc1 ^= crc2;
256 return crc1;
257 }
258
259 class CRC64_GUARD
260 {
261 public:
CRC64_GUARD()262 CRC64_GUARD()
263 {
264 uint64_t n = 1;
265 if (*(char *)&n) {
266 crc64_little_init();
267 }
268 else {
269 crc64_big_init();
270 }
271 }
272 ~CRC64_GUARD() = default;
273 };
274
275 static CRC64_GUARD crc64Guard;
276
CalcCRC(uint64_t crc,void * buf,size_t len)277 uint64_t CRC64::CalcCRC(uint64_t crc, void *buf, size_t len)
278 {
279 uint64_t n = 1;
280 return *(char *)&n ? crc64_little(crc, buf, len) : crc64_big(crc, buf, len);
281 }
282
CalcCRC(uint64_t crc,void * buf,size_t len,bool little)283 uint64_t CRC64::CalcCRC(uint64_t crc, void *buf, size_t len, bool little)
284 {
285 return little ? crc64_little(crc, buf, len) : crc64_big(crc, buf, len);
286 }
287
CombineCRC(uint64_t crc1,uint64_t crc2,uintmax_t len2)288 uint64_t CRC64::CombineCRC(uint64_t crc1, uint64_t crc2, uintmax_t len2)
289 {
290 return crc64_combine(crc1, crc2, len2);
291 }
292
293
294 }
295 }
296
297
298