1 | /* Copyright (c) 2014, Matt Stancliff <[email protected]> |
2 | * Copyright (c) 2020, Amazon Web Services |
3 | * All rights reserved. |
4 | * |
5 | * Redistribution and use in source and binary forms, with or without |
6 | * modification, are permitted provided that the following conditions are met: |
7 | * |
8 | * * Redistributions of source code must retain the above copyright notice, |
9 | * this list of conditions and the following disclaimer. |
10 | * * Redistributions in binary form must reproduce the above copyright |
11 | * notice, this list of conditions and the following disclaimer in the |
12 | * documentation and/or other materials provided with the distribution. |
13 | * * Neither the name of Redis nor the names of its contributors may be used |
14 | * to endorse or promote products derived from this software without |
15 | * specific prior written permission. |
16 | * |
17 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
18 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
19 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
20 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE |
21 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
22 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
23 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
24 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
25 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
26 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
27 | * POSSIBILITY OF SUCH DAMAGE. */ |
28 | |
29 | #include "crc64.h" |
30 | #include "crcspeed.h" |
31 | static uint64_t crc64_table[8][256] = {{0}}; |
32 | |
33 | #define POLY UINT64_C(0xad93d23594c935a9) |
34 | /******************** BEGIN GENERATED PYCRC FUNCTIONS ********************/ |
35 | /** |
36 | * Generated on Sun Dec 21 14:14:07 2014, |
37 | * by pycrc v0.8.2, https://www.tty1.net/pycrc/ |
38 | * |
39 | * LICENSE ON GENERATED CODE: |
40 | * ========================== |
41 | * As of version 0.6, pycrc is released under the terms of the MIT licence. |
42 | * The code generated by pycrc is not considered a substantial portion of the |
43 | * software, therefore the author of pycrc will not claim any copyright on |
44 | * the generated code. |
45 | * ========================== |
46 | * |
47 | * CRC configuration: |
48 | * Width = 64 |
49 | * Poly = 0xad93d23594c935a9 |
50 | * XorIn = 0xffffffffffffffff |
51 | * ReflectIn = True |
52 | * XorOut = 0x0000000000000000 |
53 | * ReflectOut = True |
54 | * Algorithm = bit-by-bit-fast |
55 | * |
56 | * Modifications after generation (by matt): |
57 | * - included finalize step in-line with update for single-call generation |
58 | * - re-worked some inner variable architectures |
59 | * - adjusted function parameters to match expected prototypes. |
60 | *****************************************************************************/ |
61 | |
62 | /** |
63 | * Reflect all bits of a \a data word of \a data_len bytes. |
64 | * |
65 | * \param data The data word to be reflected. |
66 | * \param data_len The width of \a data expressed in number of bits. |
67 | * \return The reflected data. |
68 | *****************************************************************************/ |
69 | static inline uint_fast64_t crc_reflect(uint_fast64_t data, size_t data_len) { |
70 | uint_fast64_t ret = data & 0x01; |
71 | |
72 | for (size_t i = 1; i < data_len; i++) { |
73 | data >>= 1; |
74 | ret = (ret << 1) | (data & 0x01); |
75 | } |
76 | |
77 | return ret; |
78 | } |
79 | |
80 | /** |
81 | * Update the crc value with new data. |
82 | * |
83 | * \param crc The current crc value. |
84 | * \param data Pointer to a buffer of \a data_len bytes. |
85 | * \param data_len Number of bytes in the \a data buffer. |
86 | * \return The updated crc value. |
87 | ******************************************************************************/ |
88 | uint64_t _crc64(uint_fast64_t crc, const void *in_data, const uint64_t len) { |
89 | const uint8_t *data = in_data; |
90 | unsigned long long bit; |
91 | |
92 | for (uint64_t offset = 0; offset < len; offset++) { |
93 | uint8_t c = data[offset]; |
94 | for (uint_fast8_t i = 0x01; i & 0xff; i <<= 1) { |
95 | bit = crc & 0x8000000000000000; |
96 | if (c & i) { |
97 | bit = !bit; |
98 | } |
99 | |
100 | crc <<= 1; |
101 | if (bit) { |
102 | crc ^= POLY; |
103 | } |
104 | } |
105 | |
106 | crc &= 0xffffffffffffffff; |
107 | } |
108 | |
109 | crc = crc & 0xffffffffffffffff; |
110 | return crc_reflect(crc, 64) ^ 0x0000000000000000; |
111 | } |
112 | |
113 | /******************** END GENERATED PYCRC FUNCTIONS ********************/ |
114 | |
115 | /* Initializes the 16KB lookup tables. */ |
116 | void crc64_init(void) { |
117 | crcspeed64native_init(_crc64, crc64_table); |
118 | } |
119 | |
120 | /* Compute crc64 */ |
121 | uint64_t crc64(uint64_t crc, const unsigned char *s, uint64_t l) { |
122 | return crcspeed64native(crc64_table, crc, (void *) s, l); |
123 | } |
124 | |
125 | /* Test main */ |
126 | #ifdef REDIS_TEST |
127 | #include <stdio.h> |
128 | |
129 | #define UNUSED(x) (void)(x) |
130 | int crc64Test(int argc, char *argv[], int flags) { |
131 | UNUSED(argc); |
132 | UNUSED(argv); |
133 | UNUSED(flags); |
134 | crc64_init(); |
135 | printf("[calcula]: e9c6d914c4b8d9ca == %016" PRIx64 "\n" , |
136 | (uint64_t)_crc64(0, "123456789" , 9)); |
137 | printf("[64speed]: e9c6d914c4b8d9ca == %016" PRIx64 "\n" , |
138 | (uint64_t)crc64(0, (unsigned char*)"123456789" , 9)); |
139 | char li[] = "Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed " |
140 | "do eiusmod tempor incididunt ut labore et dolore magna " |
141 | "aliqua. Ut enim ad minim veniam, quis nostrud exercitation " |
142 | "ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis " |
143 | "aute irure dolor in reprehenderit in voluptate velit esse " |
144 | "cillum dolore eu fugiat nulla pariatur. Excepteur sint " |
145 | "occaecat cupidatat non proident, sunt in culpa qui officia " |
146 | "deserunt mollit anim id est laborum." ; |
147 | printf("[calcula]: c7794709e69683b3 == %016" PRIx64 "\n" , |
148 | (uint64_t)_crc64(0, li, sizeof(li))); |
149 | printf("[64speed]: c7794709e69683b3 == %016" PRIx64 "\n" , |
150 | (uint64_t)crc64(0, (unsigned char*)li, sizeof(li))); |
151 | return 0; |
152 | } |
153 | |
154 | #endif |
155 | |
156 | #ifdef REDIS_TEST_MAIN |
157 | int main(int argc, char *argv[]) { |
158 | return crc64Test(argc, argv); |
159 | } |
160 | |
161 | #endif |
162 | |