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"
31static 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 *****************************************************************************/
69static 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 ******************************************************************************/
88uint64_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. */
116void crc64_init(void) {
117 crcspeed64native_init(_crc64, crc64_table);
118}
119
120/* Compute crc64 */
121uint64_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)
130int 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
157int main(int argc, char *argv[]) {
158 return crc64Test(argc, argv);
159}
160
161#endif
162