]> git.proxmox.com Git - ceph.git/blame - ceph/src/rocksdb/util/crc32c.cc
projects / ceph.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
bump version to 18.2.2-pve1
[ceph.git] / ceph / src / rocksdb / util / crc32c.cc
CommitLineData
7c673cae 1// Copyright (c) 2011-present, Facebook, Inc. All rights reserved.
11fdf7f2
TL		 2// This source code is licensed under both the GPLv2 (found in the
3// COPYING file in the root directory) and Apache 2.0 License
4// (found in the LICENSE.Apache file in the root directory).
7c673cae
FG		 5//
6// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
7// Use of this source code is governed by a BSD-style license that can be
8// found in the LICENSE file. See the AUTHORS file for names of contributors.
9//
10// A portable implementation of crc32c, optimized to handle
11// four bytes at a time.
7c673cae 12#include "util/crc32c.h"
1e59de90 13
7c673cae 14#include <stdint.h>
1e59de90
TL		 15
16#include <array>
17#include <utility>
11fdf7f2 18#ifdef HAVE_SSE42
7c673cae 19#include <nmmintrin.h>
11fdf7f2 20#include <wmmintrin.h>
7c673cae 21#endif
1e59de90 22
20effc67 23#include "port/lang.h"
11fdf7f2 24#include "util/coding.h"
f67539c2 25#include "util/crc32c_arm64.h"
1e59de90 26#include "util/math.h"
f67539c2 27
11fdf7f2
TL		 28#ifdef __powerpc64__
29#include "util/crc32c_ppc.h"
30#include "util/crc32c_ppc_constants.h"
31
32#if __linux__
b3b6e05e 33#ifdef ROCKSDB_AUXV_GETAUXVAL_PRESENT
11fdf7f2 34#include <sys/auxv.h>
b3b6e05e 35#endif
11fdf7f2
TL		 36
37#ifndef PPC_FEATURE2_VEC_CRYPTO
38#define PPC_FEATURE2_VEC_CRYPTO 0x02000000
7c673cae 39#endif
11fdf7f2
TL		 40
41#ifndef AT_HWCAP2
42#define AT_HWCAP2 26
43#endif
44
1e59de90
TL		 45#elif __FreeBSD__
46#include <machine/cpu.h>
47#include <sys/auxv.h>
48#include <sys/elf_common.h>
11fdf7f2
TL		 49#endif /* __linux__ */
50
7c673cae 51#endif
7c673cae 52
1e59de90 53#if defined(HAVE_ARM64_CRC)
b3b6e05e
TL		 54bool pmull_runtime_flag = false;
55#endif
56
f67539c2 57namespace ROCKSDB_NAMESPACE {
7c673cae
FG		 58namespace crc32c {
59
11fdf7f2
TL		 60#if defined(HAVE_POWER8) && defined(HAS_ALTIVEC)
61#ifdef __powerpc64__
62static int arch_ppc_crc32 = 0;
63#endif /* __powerpc64__ */
64#endif
65
7c673cae 66static const uint32_t table0_[256] = {
1e59de90
TL		 67 0x00000000, 0xf26b8303, 0xe13b70f7, 0x1350f3f4, 0xc79a971f, 0x35f1141c,
68 0x26a1e7e8, 0xd4ca64eb, 0x8ad958cf, 0x78b2dbcc, 0x6be22838, 0x9989ab3b,
69 0x4d43cfd0, 0xbf284cd3, 0xac78bf27, 0x5e133c24, 0x105ec76f, 0xe235446c,
70 0xf165b798, 0x030e349b, 0xd7c45070, 0x25afd373, 0x36ff2087, 0xc494a384,
71 0x9a879fa0, 0x68ec1ca3, 0x7bbcef57, 0x89d76c54, 0x5d1d08bf, 0xaf768bbc,
72 0xbc267848, 0x4e4dfb4b, 0x20bd8ede, 0xd2d60ddd, 0xc186fe29, 0x33ed7d2a,
73 0xe72719c1, 0x154c9ac2, 0x061c6936, 0xf477ea35, 0xaa64d611, 0x580f5512,
74 0x4b5fa6e6, 0xb93425e5, 0x6dfe410e, 0x9f95c20d, 0x8cc531f9, 0x7eaeb2fa,
75 0x30e349b1, 0xc288cab2, 0xd1d83946, 0x23b3ba45, 0xf779deae, 0x05125dad,
76 0x1642ae59, 0xe4292d5a, 0xba3a117e, 0x4851927d, 0x5b016189, 0xa96ae28a,
77 0x7da08661, 0x8fcb0562, 0x9c9bf696, 0x6ef07595, 0x417b1dbc, 0xb3109ebf,
78 0xa0406d4b, 0x522bee48, 0x86e18aa3, 0x748a09a0, 0x67dafa54, 0x95b17957,
79 0xcba24573, 0x39c9c670, 0x2a993584, 0xd8f2b687, 0x0c38d26c, 0xfe53516f,
80 0xed03a29b, 0x1f682198, 0x5125dad3, 0xa34e59d0, 0xb01eaa24, 0x42752927,
81 0x96bf4dcc, 0x64d4cecf, 0x77843d3b, 0x85efbe38, 0xdbfc821c, 0x2997011f,
82 0x3ac7f2eb, 0xc8ac71e8, 0x1c661503, 0xee0d9600, 0xfd5d65f4, 0x0f36e6f7,
83 0x61c69362, 0x93ad1061, 0x80fde395, 0x72966096, 0xa65c047d, 0x5437877e,
84 0x4767748a, 0xb50cf789, 0xeb1fcbad, 0x197448ae, 0x0a24bb5a, 0xf84f3859,
85 0x2c855cb2, 0xdeeedfb1, 0xcdbe2c45, 0x3fd5af46, 0x7198540d, 0x83f3d70e,
86 0x90a324fa, 0x62c8a7f9, 0xb602c312, 0x44694011, 0x5739b3e5, 0xa55230e6,
87 0xfb410cc2, 0x092a8fc1, 0x1a7a7c35, 0xe811ff36, 0x3cdb9bdd, 0xceb018de,
88 0xdde0eb2a, 0x2f8b6829, 0x82f63b78, 0x709db87b, 0x63cd4b8f, 0x91a6c88c,
89 0x456cac67, 0xb7072f64, 0xa457dc90, 0x563c5f93, 0x082f63b7, 0xfa44e0b4,
90 0xe9141340, 0x1b7f9043, 0xcfb5f4a8, 0x3dde77ab, 0x2e8e845f, 0xdce5075c,
91 0x92a8fc17, 0x60c37f14, 0x73938ce0, 0x81f80fe3, 0x55326b08, 0xa759e80b,
92 0xb4091bff, 0x466298fc, 0x1871a4d8, 0xea1a27db, 0xf94ad42f, 0x0b21572c,
93 0xdfeb33c7, 0x2d80b0c4, 0x3ed04330, 0xccbbc033, 0xa24bb5a6, 0x502036a5,
94 0x4370c551, 0xb11b4652, 0x65d122b9, 0x97baa1ba, 0x84ea524e, 0x7681d14d,
95 0x2892ed69, 0xdaf96e6a, 0xc9a99d9e, 0x3bc21e9d, 0xef087a76, 0x1d63f975,
96 0x0e330a81, 0xfc588982, 0xb21572c9, 0x407ef1ca, 0x532e023e, 0xa145813d,
97 0x758fe5d6, 0x87e466d5, 0x94b49521, 0x66df1622, 0x38cc2a06, 0xcaa7a905,
98 0xd9f75af1, 0x2b9cd9f2, 0xff56bd19, 0x0d3d3e1a, 0x1e6dcdee, 0xec064eed,
99 0xc38d26c4, 0x31e6a5c7, 0x22b65633, 0xd0ddd530, 0x0417b1db, 0xf67c32d8,
100 0xe52cc12c, 0x1747422f, 0x49547e0b, 0xbb3ffd08, 0xa86f0efc, 0x5a048dff,
101 0x8ecee914, 0x7ca56a17, 0x6ff599e3, 0x9d9e1ae0, 0xd3d3e1ab, 0x21b862a8,
102 0x32e8915c, 0xc083125f, 0x144976b4, 0xe622f5b7, 0xf5720643, 0x07198540,
103 0x590ab964, 0xab613a67, 0xb831c993, 0x4a5a4a90, 0x9e902e7b, 0x6cfbad78,
104 0x7fab5e8c, 0x8dc0dd8f, 0xe330a81a, 0x115b2b19, 0x020bd8ed, 0xf0605bee,
105 0x24aa3f05, 0xd6c1bc06, 0xc5914ff2, 0x37faccf1, 0x69e9f0d5, 0x9b8273d6,
106 0x88d28022, 0x7ab90321, 0xae7367ca, 0x5c18e4c9, 0x4f48173d, 0xbd23943e,
107 0xf36e6f75, 0x0105ec76, 0x12551f82, 0xe03e9c81, 0x34f4f86a, 0xc69f7b69,
108 0xd5cf889d, 0x27a40b9e, 0x79b737ba, 0x8bdcb4b9, 0x988c474d, 0x6ae7c44e,
109 0xbe2da0a5, 0x4c4623a6, 0x5f16d052, 0xad7d5351};
7c673cae 110static const uint32_t table1_[256] = {
1e59de90
TL		 111 0x00000000, 0x13a29877, 0x274530ee, 0x34e7a899, 0x4e8a61dc, 0x5d28f9ab,
112 0x69cf5132, 0x7a6dc945, 0x9d14c3b8, 0x8eb65bcf, 0xba51f356, 0xa9f36b21,
113 0xd39ea264, 0xc03c3a13, 0xf4db928a, 0xe7790afd, 0x3fc5f181, 0x2c6769f6,
114 0x1880c16f, 0x0b225918, 0x714f905d, 0x62ed082a, 0x560aa0b3, 0x45a838c4,
115 0xa2d13239, 0xb173aa4e, 0x859402d7, 0x96369aa0, 0xec5b53e5, 0xfff9cb92,
116 0xcb1e630b, 0xd8bcfb7c, 0x7f8be302, 0x6c297b75, 0x58ced3ec, 0x4b6c4b9b,
117 0x310182de, 0x22a31aa9, 0x1644b230, 0x05e62a47, 0xe29f20ba, 0xf13db8cd,
118 0xc5da1054, 0xd6788823, 0xac154166, 0xbfb7d911, 0x8b507188, 0x98f2e9ff,
119 0x404e1283, 0x53ec8af4, 0x670b226d, 0x74a9ba1a, 0x0ec4735f, 0x1d66eb28,
120 0x298143b1, 0x3a23dbc6, 0xdd5ad13b, 0xcef8494c, 0xfa1fe1d5, 0xe9bd79a2,
121 0x93d0b0e7, 0x80722890, 0xb4958009, 0xa737187e, 0xff17c604, 0xecb55e73,
122 0xd852f6ea, 0xcbf06e9d, 0xb19da7d8, 0xa23f3faf, 0x96d89736, 0x857a0f41,
123 0x620305bc, 0x71a19dcb, 0x45463552, 0x56e4ad25, 0x2c896460, 0x3f2bfc17,
124 0x0bcc548e, 0x186eccf9, 0xc0d23785, 0xd370aff2, 0xe797076b, 0xf4359f1c,
125 0x8e585659, 0x9dface2e, 0xa91d66b7, 0xbabffec0, 0x5dc6f43d, 0x4e646c4a,
126 0x7a83c4d3, 0x69215ca4, 0x134c95e1, 0x00ee0d96, 0x3409a50f, 0x27ab3d78,
127 0x809c2506, 0x933ebd71, 0xa7d915e8, 0xb47b8d9f, 0xce1644da, 0xddb4dcad,
128 0xe9537434, 0xfaf1ec43, 0x1d88e6be, 0x0e2a7ec9, 0x3acdd650, 0x296f4e27,
129 0x53028762, 0x40a01f15, 0x7447b78c, 0x67e52ffb, 0xbf59d487, 0xacfb4cf0,
130 0x981ce469, 0x8bbe7c1e, 0xf1d3b55b, 0xe2712d2c, 0xd69685b5, 0xc5341dc2,
131 0x224d173f, 0x31ef8f48, 0x050827d1, 0x16aabfa6, 0x6cc776e3, 0x7f65ee94,
132 0x4b82460d, 0x5820de7a, 0xfbc3faf9, 0xe861628e, 0xdc86ca17, 0xcf245260,
133 0xb5499b25, 0xa6eb0352, 0x920cabcb, 0x81ae33bc, 0x66d73941, 0x7575a136,
134 0x419209af, 0x523091d8, 0x285d589d, 0x3bffc0ea, 0x0f186873, 0x1cbaf004,
135 0xc4060b78, 0xd7a4930f, 0xe3433b96, 0xf0e1a3e1, 0x8a8c6aa4, 0x992ef2d3,
136 0xadc95a4a, 0xbe6bc23d, 0x5912c8c0, 0x4ab050b7, 0x7e57f82e, 0x6df56059,
137 0x1798a91c, 0x043a316b, 0x30dd99f2, 0x237f0185, 0x844819fb, 0x97ea818c,
138 0xa30d2915, 0xb0afb162, 0xcac27827, 0xd960e050, 0xed8748c9, 0xfe25d0be,
139 0x195cda43, 0x0afe4234, 0x3e19eaad, 0x2dbb72da, 0x57d6bb9f, 0x447423e8,
140 0x70938b71, 0x63311306, 0xbb8de87a, 0xa82f700d, 0x9cc8d894, 0x8f6a40e3,
141 0xf50789a6, 0xe6a511d1, 0xd242b948, 0xc1e0213f, 0x26992bc2, 0x353bb3b5,
142 0x01dc1b2c, 0x127e835b, 0x68134a1e, 0x7bb1d269, 0x4f567af0, 0x5cf4e287,
143 0x04d43cfd, 0x1776a48a, 0x23910c13, 0x30339464, 0x4a5e5d21, 0x59fcc556,
144 0x6d1b6dcf, 0x7eb9f5b8, 0x99c0ff45, 0x8a626732, 0xbe85cfab, 0xad2757dc,
145 0xd74a9e99, 0xc4e806ee, 0xf00fae77, 0xe3ad3600, 0x3b11cd7c, 0x28b3550b,
146 0x1c54fd92, 0x0ff665e5, 0x759baca0, 0x663934d7, 0x52de9c4e, 0x417c0439,
147 0xa6050ec4, 0xb5a796b3, 0x81403e2a, 0x92e2a65d, 0xe88f6f18, 0xfb2df76f,
148 0xcfca5ff6, 0xdc68c781, 0x7b5fdfff, 0x68fd4788, 0x5c1aef11, 0x4fb87766,
149 0x35d5be23, 0x26772654, 0x12908ecd, 0x013216ba, 0xe64b1c47, 0xf5e98430,
150 0xc10e2ca9, 0xd2acb4de, 0xa8c17d9b, 0xbb63e5ec, 0x8f844d75, 0x9c26d502,
151 0x449a2e7e, 0x5738b609, 0x63df1e90, 0x707d86e7, 0x0a104fa2, 0x19b2d7d5,
152 0x2d557f4c, 0x3ef7e73b, 0xd98eedc6, 0xca2c75b1, 0xfecbdd28, 0xed69455f,
153 0x97048c1a, 0x84a6146d, 0xb041bcf4, 0xa3e32483};
7c673cae 154static const uint32_t table2_[256] = {
1e59de90
TL		 155 0x00000000, 0xa541927e, 0x4f6f520d, 0xea2ec073, 0x9edea41a, 0x3b9f3664,
156 0xd1b1f617, 0x74f06469, 0x38513ec5, 0x9d10acbb, 0x773e6cc8, 0xd27ffeb6,
157 0xa68f9adf, 0x03ce08a1, 0xe9e0c8d2, 0x4ca15aac, 0x70a27d8a, 0xd5e3eff4,
158 0x3fcd2f87, 0x9a8cbdf9, 0xee7cd990, 0x4b3d4bee, 0xa1138b9d, 0x045219e3,
159 0x48f3434f, 0xedb2d131, 0x079c1142, 0xa2dd833c, 0xd62de755, 0x736c752b,
160 0x9942b558, 0x3c032726, 0xe144fb14, 0x4405696a, 0xae2ba919, 0x0b6a3b67,
161 0x7f9a5f0e, 0xdadbcd70, 0x30f50d03, 0x95b49f7d, 0xd915c5d1, 0x7c5457af,
162 0x967a97dc, 0x333b05a2, 0x47cb61cb, 0xe28af3b5, 0x08a433c6, 0xade5a1b8,
163 0x91e6869e, 0x34a714e0, 0xde89d493, 0x7bc846ed, 0x0f382284, 0xaa79b0fa,
164 0x40577089, 0xe516e2f7, 0xa9b7b85b, 0x0cf62a25, 0xe6d8ea56, 0x43997828,
165 0x37691c41, 0x92288e3f, 0x78064e4c, 0xdd47dc32, 0xc76580d9, 0x622412a7,
166 0x880ad2d4, 0x2d4b40aa, 0x59bb24c3, 0xfcfab6bd, 0x16d476ce, 0xb395e4b0,
167 0xff34be1c, 0x5a752c62, 0xb05bec11, 0x151a7e6f, 0x61ea1a06, 0xc4ab8878,
168 0x2e85480b, 0x8bc4da75, 0xb7c7fd53, 0x12866f2d, 0xf8a8af5e, 0x5de93d20,
169 0x29195949, 0x8c58cb37, 0x66760b44, 0xc337993a, 0x8f96c396, 0x2ad751e8,
170 0xc0f9919b, 0x65b803e5, 0x1148678c, 0xb409f5f2, 0x5e273581, 0xfb66a7ff,
171 0x26217bcd, 0x8360e9b3, 0x694e29c0, 0xcc0fbbbe, 0xb8ffdfd7, 0x1dbe4da9,
172 0xf7908dda, 0x52d11fa4, 0x1e704508, 0xbb31d776, 0x511f1705, 0xf45e857b,
173 0x80aee112, 0x25ef736c, 0xcfc1b31f, 0x6a802161, 0x56830647, 0xf3c29439,
174 0x19ec544a, 0xbcadc634, 0xc85da25d, 0x6d1c3023, 0x8732f050, 0x2273622e,
175 0x6ed23882, 0xcb93aafc, 0x21bd6a8f, 0x84fcf8f1, 0xf00c9c98, 0x554d0ee6,
176 0xbf63ce95, 0x1a225ceb, 0x8b277743, 0x2e66e53d, 0xc448254e, 0x6109b730,
177 0x15f9d359, 0xb0b84127, 0x5a968154, 0xffd7132a, 0xb3764986, 0x1637dbf8,
178 0xfc191b8b, 0x595889f5, 0x2da8ed9c, 0x88e97fe2, 0x62c7bf91, 0xc7862def,
179 0xfb850ac9, 0x5ec498b7, 0xb4ea58c4, 0x11abcaba, 0x655baed3, 0xc01a3cad,
180 0x2a34fcde, 0x8f756ea0, 0xc3d4340c, 0x6695a672, 0x8cbb6601, 0x29faf47f,
181 0x5d0a9016, 0xf84b0268, 0x1265c21b, 0xb7245065, 0x6a638c57, 0xcf221e29,
182 0x250cde5a, 0x804d4c24, 0xf4bd284d, 0x51fcba33, 0xbbd27a40, 0x1e93e83e,
183 0x5232b292, 0xf77320ec, 0x1d5de09f, 0xb81c72e1, 0xccec1688, 0x69ad84f6,
184 0x83834485, 0x26c2d6fb, 0x1ac1f1dd, 0xbf8063a3, 0x55aea3d0, 0xf0ef31ae,
185 0x841f55c7, 0x215ec7b9, 0xcb7007ca, 0x6e3195b4, 0x2290cf18, 0x87d15d66,
186 0x6dff9d15, 0xc8be0f6b, 0xbc4e6b02, 0x190ff97c, 0xf321390f, 0x5660ab71,
187 0x4c42f79a, 0xe90365e4, 0x032da597, 0xa66c37e9, 0xd29c5380, 0x77ddc1fe,
188 0x9df3018d, 0x38b293f3, 0x7413c95f, 0xd1525b21, 0x3b7c9b52, 0x9e3d092c,
189 0xeacd6d45, 0x4f8cff3b, 0xa5a23f48, 0x00e3ad36, 0x3ce08a10, 0x99a1186e,
190 0x738fd81d, 0xd6ce4a63, 0xa23e2e0a, 0x077fbc74, 0xed517c07, 0x4810ee79,
191 0x04b1b4d5, 0xa1f026ab, 0x4bdee6d8, 0xee9f74a6, 0x9a6f10cf, 0x3f2e82b1,
192 0xd50042c2, 0x7041d0bc, 0xad060c8e, 0x08479ef0, 0xe2695e83, 0x4728ccfd,
193 0x33d8a894, 0x96993aea, 0x7cb7fa99, 0xd9f668e7, 0x9557324b, 0x3016a035,
194 0xda386046, 0x7f79f238, 0x0b899651, 0xaec8042f, 0x44e6c45c, 0xe1a75622,
195 0xdda47104, 0x78e5e37a, 0x92cb2309, 0x378ab177, 0x437ad51e, 0xe63b4760,
196 0x0c158713, 0xa954156d, 0xe5f54fc1, 0x40b4ddbf, 0xaa9a1dcc, 0x0fdb8fb2,
197 0x7b2bebdb, 0xde6a79a5, 0x3444b9d6, 0x91052ba8};
7c673cae 198static const uint32_t table3_[256] = {
1e59de90
TL		 199 0x00000000, 0xdd45aab8, 0xbf672381, 0x62228939, 0x7b2231f3, 0xa6679b4b,
200 0xc4451272, 0x1900b8ca, 0xf64463e6, 0x2b01c95e, 0x49234067, 0x9466eadf,
201 0x8d665215, 0x5023f8ad, 0x32017194, 0xef44db2c, 0xe964b13d, 0x34211b85,
202 0x560392bc, 0x8b463804, 0x924680ce, 0x4f032a76, 0x2d21a34f, 0xf06409f7,
203 0x1f20d2db, 0xc2657863, 0xa047f15a, 0x7d025be2, 0x6402e328, 0xb9474990,
204 0xdb65c0a9, 0x06206a11, 0xd725148b, 0x0a60be33, 0x6842370a, 0xb5079db2,
205 0xac072578, 0x71428fc0, 0x136006f9, 0xce25ac41, 0x2161776d, 0xfc24ddd5,
206 0x9e0654ec, 0x4343fe54, 0x5a43469e, 0x8706ec26, 0xe524651f, 0x3861cfa7,
207 0x3e41a5b6, 0xe3040f0e, 0x81268637, 0x5c632c8f, 0x45639445, 0x98263efd,
208 0xfa04b7c4, 0x27411d7c, 0xc805c650, 0x15406ce8, 0x7762e5d1, 0xaa274f69,
209 0xb327f7a3, 0x6e625d1b, 0x0c40d422, 0xd1057e9a, 0xaba65fe7, 0x76e3f55f,
210 0x14c17c66, 0xc984d6de, 0xd0846e14, 0x0dc1c4ac, 0x6fe34d95, 0xb2a6e72d,
211 0x5de23c01, 0x80a796b9, 0xe2851f80, 0x3fc0b538, 0x26c00df2, 0xfb85a74a,
212 0x99a72e73, 0x44e284cb, 0x42c2eeda, 0x9f874462, 0xfda5cd5b, 0x20e067e3,
213 0x39e0df29, 0xe4a57591, 0x8687fca8, 0x5bc25610, 0xb4868d3c, 0x69c32784,
214 0x0be1aebd, 0xd6a40405, 0xcfa4bccf, 0x12e11677, 0x70c39f4e, 0xad8635f6,
215 0x7c834b6c, 0xa1c6e1d4, 0xc3e468ed, 0x1ea1c255, 0x07a17a9f, 0xdae4d027,
216 0xb8c6591e, 0x6583f3a6, 0x8ac7288a, 0x57828232, 0x35a00b0b, 0xe8e5a1b3,
217 0xf1e51979, 0x2ca0b3c1, 0x4e823af8, 0x93c79040, 0x95e7fa51, 0x48a250e9,
218 0x2a80d9d0, 0xf7c57368, 0xeec5cba2, 0x3380611a, 0x51a2e823, 0x8ce7429b,
219 0x63a399b7, 0xbee6330f, 0xdcc4ba36, 0x0181108e, 0x1881a844, 0xc5c402fc,
220 0xa7e68bc5, 0x7aa3217d, 0x52a0c93f, 0x8fe56387, 0xedc7eabe, 0x30824006,
221 0x2982f8cc, 0xf4c75274, 0x96e5db4d, 0x4ba071f5, 0xa4e4aad9, 0x79a10061,
222 0x1b838958, 0xc6c623e0, 0xdfc69b2a, 0x02833192, 0x60a1b8ab, 0xbde41213,
223 0xbbc47802, 0x6681d2ba, 0x04a35b83, 0xd9e6f13b, 0xc0e649f1, 0x1da3e349,
224 0x7f816a70, 0xa2c4c0c8, 0x4d801be4, 0x90c5b15c, 0xf2e73865, 0x2fa292dd,
225 0x36a22a17, 0xebe780af, 0x89c50996, 0x5480a32e, 0x8585ddb4, 0x58c0770c,
226 0x3ae2fe35, 0xe7a7548d, 0xfea7ec47, 0x23e246ff, 0x41c0cfc6, 0x9c85657e,
227 0x73c1be52, 0xae8414ea, 0xcca69dd3, 0x11e3376b, 0x08e38fa1, 0xd5a62519,
228 0xb784ac20, 0x6ac10698, 0x6ce16c89, 0xb1a4c631, 0xd3864f08, 0x0ec3e5b0,
229 0x17c35d7a, 0xca86f7c2, 0xa8a47efb, 0x75e1d443, 0x9aa50f6f, 0x47e0a5d7,
230 0x25c22cee, 0xf8878656, 0xe1873e9c, 0x3cc29424, 0x5ee01d1d, 0x83a5b7a5,
231 0xf90696d8, 0x24433c60, 0x4661b559, 0x9b241fe1, 0x8224a72b, 0x5f610d93,
232 0x3d4384aa, 0xe0062e12, 0x0f42f53e, 0xd2075f86, 0xb025d6bf, 0x6d607c07,
233 0x7460c4cd, 0xa9256e75, 0xcb07e74c, 0x16424df4, 0x106227e5, 0xcd278d5d,
234 0xaf050464, 0x7240aedc, 0x6b401616, 0xb605bcae, 0xd4273597, 0x09629f2f,
235 0xe6264403, 0x3b63eebb, 0x59416782, 0x8404cd3a, 0x9d0475f0, 0x4041df48,
236 0x22635671, 0xff26fcc9, 0x2e238253, 0xf36628eb, 0x9144a1d2, 0x4c010b6a,
237 0x5501b3a0, 0x88441918, 0xea669021, 0x37233a99, 0xd867e1b5, 0x05224b0d,
238 0x6700c234, 0xba45688c, 0xa345d046, 0x7e007afe, 0x1c22f3c7, 0xc167597f,
239 0xc747336e, 0x1a0299d6, 0x782010ef, 0xa565ba57, 0xbc65029d, 0x6120a825,
240 0x0302211c, 0xde478ba4, 0x31035088, 0xec46fa30, 0x8e647309, 0x5321d9b1,
241 0x4a21617b, 0x9764cbc3, 0xf54642fa, 0x2803e842};
7c673cae
FG		 242
243// Used to fetch a naturally-aligned 32-bit word in little endian byte-order
1e59de90 244static inline uint32_t LE_LOAD32(const uint8_t* p) {
7c673cae
FG		 245 return DecodeFixed32(reinterpret_cast<const char*>(p));
246}
247
11fdf7f2 248#if defined(HAVE_SSE42) && (defined(__LP64__) || defined(_WIN64))
1e59de90 249static inline uint64_t LE_LOAD64(const uint8_t* p) {
7c673cae
FG		 250 return DecodeFixed64(reinterpret_cast<const char*>(p));
251}
252#endif
7c673cae 253
1e59de90 254static inline void Slow_CRC32(uint64_t* l, uint8_t const** p) {
7c673cae
FG		 255 uint32_t c = static_cast<uint32_t>(*l ^ LE_LOAD32(*p));
256 *p += 4;
1e59de90
TL		 257 *l = table3_[c & 0xff] ^ table2_[(c >> 8) & 0xff] ^
258 table1_[(c >> 16) & 0xff] ^ table0_[c >> 24];
7c673cae
FG		 259 // DO it twice.
260 c = static_cast<uint32_t>(*l ^ LE_LOAD32(*p));
261 *p += 4;
1e59de90
TL		 262 *l = table3_[c & 0xff] ^ table2_[(c >> 8) & 0xff] ^
263 table1_[(c >> 16) & 0xff] ^ table0_[c >> 24];
7c673cae
FG		 264}
265
1e59de90
TL		 266#if (!(defined(HAVE_POWER8) && defined(HAS_ALTIVEC))) && \
267 (!defined(HAVE_ARM64_CRC)) || \
268 defined(NO_THREEWAY_CRC32C)
269static inline void Fast_CRC32(uint64_t* l, uint8_t const** p) {
11fdf7f2
TL		 270#ifndef HAVE_SSE42
271 Slow_CRC32(l, p);
272#elif defined(__LP64__) || defined(_WIN64)
7c673cae
FG		 273 *l = _mm_crc32_u64(*l, LE_LOAD64(*p));
274 *p += 8;
275#else
276 *l = _mm_crc32_u32(static_cast<unsigned int>(*l), LE_LOAD32(*p));
277 *p += 4;
278 *l = _mm_crc32_u32(static_cast<unsigned int>(*l), LE_LOAD32(*p));
279 *p += 4;
280#endif
7c673cae 281}
1e59de90 282#endif
7c673cae 283
1e59de90 284template <void (*CRC32)(uint64_t*, uint8_t const**)>
7c673cae 285uint32_t ExtendImpl(uint32_t crc, const char* buf, size_t size) {
1e59de90
TL		 286 const uint8_t* p = reinterpret_cast<const uint8_t*>(buf);
287 const uint8_t* e = p + size;
7c673cae
FG		 288 uint64_t l = crc ^ 0xffffffffu;
289
290// Align n to (1 << m) byte boundary
1e59de90 291#define ALIGN(n, m) ((n + ((1 << m) - 1)) & ~((1 << m) - 1))
7c673cae 292
1e59de90
TL		 293#define STEP1 \
294 do { \
295 int c = (l & 0xff) ^ *p++; \
296 l = table0_[c] ^ (l >> 8); \
297 } while (0)
7c673cae
FG		 298
299 // Point x at first 16-byte aligned byte in string. This might be
300 // just past the end of the string.
301 const uintptr_t pval = reinterpret_cast<uintptr_t>(p);
302 const uint8_t* x = reinterpret_cast<const uint8_t*>(ALIGN(pval, 4));
303 if (x <= e) {
304 // Process bytes until finished or p is 16-byte aligned
305 while (p != x) {
306 STEP1;
307 }
308 }
309 // Process bytes 16 at a time
1e59de90 310 while ((e - p) >= 16) {
7c673cae
FG		 311 CRC32(&l, &p);
312 CRC32(&l, &p);
313 }
314 // Process bytes 8 at a time
1e59de90 315 while ((e - p) >= 8) {
7c673cae
FG		 316 CRC32(&l, &p);
317 }
318 // Process the last few bytes
319 while (p != e) {
320 STEP1;
321 }
322#undef STEP1
323#undef ALIGN
324 return static_cast<uint32_t>(l ^ 0xffffffffu);
325}
326
f67539c2
TL		 327// Detect if ARM64 CRC or not.
328#ifndef HAVE_ARM64_CRC
7c673cae 329// Detect if SS42 or not.
11fdf7f2
TL		 330#ifndef HAVE_POWER8
331
7c673cae 332static bool isSSE42() {
11fdf7f2
TL		 333#ifndef HAVE_SSE42
334 return false;
335#elif defined(__GNUC__) && defined(__x86_64__) && !defined(IOS_CROSS_COMPILE)
7c673cae 336 uint32_t c_;
181888fb 337 __asm__("cpuid" : "=c"(c_) : "a"(1) : "ebx", "edx");
11fdf7f2 338 return c_ & (1U << 20); // copied from CpuId.h in Folly. Test SSE42
7c673cae
FG		 339#elif defined(_WIN64)
340 int info[4];
341 __cpuidex(info, 0x00000001, 0);
342 return (info[2] & ((int)1 << 20)) != 0;
343#else
344 return false;
345#endif
346}
347
11fdf7f2
TL		 348static bool isPCLMULQDQ() {
349#ifndef HAVE_SSE42
1e59de90
TL		 350 // in build_detect_platform we set this macro when both SSE42 and PCLMULQDQ
351 // are supported by compiler
11fdf7f2
TL		 352 return false;
353#elif defined(__GNUC__) && defined(__x86_64__) && !defined(IOS_CROSS_COMPILE)
354 uint32_t c_;
355 __asm__("cpuid" : "=c"(c_) : "a"(1) : "ebx", "edx");
356 return c_ & (1U << 1); // PCLMULQDQ is in bit 1 (not bit 0)
357#elif defined(_WIN64)
358 int info[4];
359 __cpuidex(info, 0x00000001, 0);
360 return (info[2] & ((int)1 << 1)) != 0;
361#else
362 return false;
363#endif
364}
365
366#endif // HAVE_POWER8
f67539c2 367#endif // HAVE_ARM64_CRC
11fdf7f2 368
1e59de90 369using Function = uint32_t (*)(uint32_t, const char*, size_t);
7c673cae 370
11fdf7f2 371#if defined(HAVE_POWER8) && defined(HAS_ALTIVEC)
1e59de90
TL		 372uint32_t ExtendPPCImpl(uint32_t crc, const char* buf, size_t size) {
373 return crc32c_ppc(crc, (const unsigned char*)buf, size);
7c673cae
FG		 374}
375
11fdf7f2
TL		 376#if __linux__
377static int arch_ppc_probe(void) {
378 arch_ppc_crc32 = 0;
379
b3b6e05e 380#if defined(__powerpc64__) && defined(ROCKSDB_AUXV_GETAUXVAL_PRESENT)
11fdf7f2
TL		 381 if (getauxval(AT_HWCAP2) & PPC_FEATURE2_VEC_CRYPTO) arch_ppc_crc32 = 1;
382#endif /* __powerpc64__ */
383
384 return arch_ppc_crc32;
385}
1e59de90
TL		 386#elif __FreeBSD__
387static int arch_ppc_probe(void) {
388 unsigned long cpufeatures;
389 arch_ppc_crc32 = 0;
390
391#if defined(__powerpc64__)
392 elf_aux_info(AT_HWCAP2, &cpufeatures, sizeof(cpufeatures));
393 if (cpufeatures & PPC_FEATURE2_HAS_VEC_CRYPTO) arch_ppc_crc32 = 1;
394#endif /* __powerpc64__ */
395
396 return arch_ppc_crc32;
397}
11fdf7f2
TL		 398#endif // __linux__
399
400static bool isAltiVec() {
401 if (arch_ppc_probe()) {
402 return true;
403 } else {
404 return false;
405 }
406}
407#endif
408
1e59de90
TL		 409#if defined(HAVE_ARM64_CRC)
410uint32_t ExtendARMImpl(uint32_t crc, const char* buf, size_t size) {
411 return crc32c_arm64(crc, (const unsigned char*)buf, size);
f67539c2
TL		 412}
413#endif
11fdf7f2
TL		 414
415std::string IsFastCrc32Supported() {
416 bool has_fast_crc = false;
417 std::string fast_zero_msg;
418 std::string arch;
419#ifdef HAVE_POWER8
420#ifdef HAS_ALTIVEC
421 if (arch_ppc_probe()) {
422 has_fast_crc = true;
423 arch = "PPC";
424 }
7c673cae 425#else
11fdf7f2
TL		 426 has_fast_crc = false;
427 arch = "PPC";
428#endif
1e59de90 429#elif defined(HAVE_ARM64_CRC)
f67539c2
TL		 430 if (crc32c_runtime_check()) {
431 has_fast_crc = true;
432 arch = "Arm64";
b3b6e05e 433 pmull_runtime_flag = crc32c_pmull_runtime_check();
f67539c2
TL		 434 } else {
435 has_fast_crc = false;
436 arch = "Arm64";
437 }
11fdf7f2
TL		 438#else
439 has_fast_crc = isSSE42();
440 arch = "x86";
7c673cae 441#endif
11fdf7f2
TL		 442 if (has_fast_crc) {
443 fast_zero_msg.append("Supported on " + arch);
1e59de90 444 } else {
11fdf7f2
TL		 445 fast_zero_msg.append("Not supported on " + arch);
446 }
447 return fast_zero_msg;
7c673cae
FG		 448}
449
11fdf7f2
TL		 450/*
451 * Copyright 2016 Ferry Toth, Exalon Delft BV, The Netherlands
452 * This software is provided 'as-is', without any express or implied
453 * warranty. In no event will the author be held liable for any damages
454 * arising from the use of this software.
455 * Permission is granted to anyone to use this software for any purpose,
456 * including commercial applications, and to alter it and redistribute it
457 * freely, subject to the following restrictions:
458 * 1. The origin of this software must not be misrepresented; you must not
459 * claim that you wrote the original software. If you use this software
460 * in a product, an acknowledgment in the product documentation would be
461 * appreciated but is not required.
462 * 2. Altered source versions must be plainly marked as such, and must not be
463 * misrepresented as being the original software.
464 * 3. This notice may not be removed or altered from any source distribution.
465 * Ferry Toth
466 * ftoth@exalondelft.nl
467 *
468 * https://github.com/htot/crc32c
469 *
470 * Modified by Facebook
471 *
472 * Original intel whitepaper:
473 * "Fast CRC Computation for iSCSI Polynomial Using CRC32 Instruction"
474 * https://www.intel.com/content/dam/www/public/us/en/documents/white-papers/crc-iscsi-polynomial-crc32-instruction-paper.pdf
475 *
1e59de90
TL		 476 * This version is from the folly library, created by Dave Watson
477 * <davejwatson@fb.com>
11fdf7f2 478 *
1e59de90 479 */
11fdf7f2
TL		 480#if defined HAVE_SSE42 && defined HAVE_PCLMUL
481
482#define CRCtriplet(crc, buf, offset) \
483 crc##0 = _mm_crc32_u64(crc##0, *(buf##0 + offset)); \
484 crc##1 = _mm_crc32_u64(crc##1, *(buf##1 + offset)); \
485 crc##2 = _mm_crc32_u64(crc##2, *(buf##2 + offset));
486
487#define CRCduplet(crc, buf, offset) \
488 crc##0 = _mm_crc32_u64(crc##0, *(buf##0 + offset)); \
489 crc##1 = _mm_crc32_u64(crc##1, *(buf##1 + offset));
490
1e59de90 491#define CRCsinglet(crc, buf, offset) \
11fdf7f2
TL		 492 crc = _mm_crc32_u64(crc, *(uint64_t*)(buf + offset));
493
11fdf7f2
TL		 494// Numbers taken directly from intel whitepaper.
495// clang-format off
496const uint64_t clmul_constants[] = {
497 0x14cd00bd6, 0x105ec76f0, 0x0ba4fc28e, 0x14cd00bd6,
498 0x1d82c63da, 0x0f20c0dfe, 0x09e4addf8, 0x0ba4fc28e,
499 0x039d3b296, 0x1384aa63a, 0x102f9b8a2, 0x1d82c63da,
500 0x14237f5e6, 0x01c291d04, 0x00d3b6092, 0x09e4addf8,
501 0x0c96cfdc0, 0x0740eef02, 0x18266e456, 0x039d3b296,
502 0x0daece73e, 0x0083a6eec, 0x0ab7aff2a, 0x102f9b8a2,
503 0x1248ea574, 0x1c1733996, 0x083348832, 0x14237f5e6,
504 0x12c743124, 0x02ad91c30, 0x0b9e02b86, 0x00d3b6092,
505 0x018b33a4e, 0x06992cea2, 0x1b331e26a, 0x0c96cfdc0,
506 0x17d35ba46, 0x07e908048, 0x1bf2e8b8a, 0x18266e456,
507 0x1a3e0968a, 0x11ed1f9d8, 0x0ce7f39f4, 0x0daece73e,
508 0x061d82e56, 0x0f1d0f55e, 0x0d270f1a2, 0x0ab7aff2a,
509 0x1c3f5f66c, 0x0a87ab8a8, 0x12ed0daac, 0x1248ea574,
510 0x065863b64, 0x08462d800, 0x11eef4f8e, 0x083348832,
511 0x1ee54f54c, 0x071d111a8, 0x0b3e32c28, 0x12c743124,
512 0x0064f7f26, 0x0ffd852c6, 0x0dd7e3b0c, 0x0b9e02b86,
513 0x0f285651c, 0x0dcb17aa4, 0x010746f3c, 0x018b33a4e,
514 0x1c24afea4, 0x0f37c5aee, 0x0271d9844, 0x1b331e26a,
515 0x08e766a0c, 0x06051d5a2, 0x093a5f730, 0x17d35ba46,
516 0x06cb08e5c, 0x11d5ca20e, 0x06b749fb2, 0x1bf2e8b8a,
517 0x1167f94f2, 0x021f3d99c, 0x0cec3662e, 0x1a3e0968a,
518 0x19329634a, 0x08f158014, 0x0e6fc4e6a, 0x0ce7f39f4,
519 0x08227bb8a, 0x1a5e82106, 0x0b0cd4768, 0x061d82e56,
520 0x13c2b89c4, 0x188815ab2, 0x0d7a4825c, 0x0d270f1a2,
521 0x10f5ff2ba, 0x105405f3e, 0x00167d312, 0x1c3f5f66c,
522 0x0f6076544, 0x0e9adf796, 0x026f6a60a, 0x12ed0daac,
523 0x1a2adb74e, 0x096638b34, 0x19d34af3a, 0x065863b64,
524 0x049c3cc9c, 0x1e50585a0, 0x068bce87a, 0x11eef4f8e,
525 0x1524fa6c6, 0x19f1c69dc, 0x16cba8aca, 0x1ee54f54c,
526 0x042d98888, 0x12913343e, 0x1329d9f7e, 0x0b3e32c28,
527 0x1b1c69528, 0x088f25a3a, 0x02178513a, 0x0064f7f26,
528 0x0e0ac139e, 0x04e36f0b0, 0x0170076fa, 0x0dd7e3b0c,
529 0x141a1a2e2, 0x0bd6f81f8, 0x16ad828b4, 0x0f285651c,
530 0x041d17b64, 0x19425cbba, 0x1fae1cc66, 0x010746f3c,
531 0x1a75b4b00, 0x18db37e8a, 0x0f872e54c, 0x1c24afea4,
532 0x01e41e9fc, 0x04c144932, 0x086d8e4d2, 0x0271d9844,
533 0x160f7af7a, 0x052148f02, 0x05bb8f1bc, 0x08e766a0c,
534 0x0a90fd27a, 0x0a3c6f37a, 0x0b3af077a, 0x093a5f730,
535 0x04984d782, 0x1d22c238e, 0x0ca6ef3ac, 0x06cb08e5c,
536 0x0234e0b26, 0x063ded06a, 0x1d88abd4a, 0x06b749fb2,
537 0x04597456a, 0x04d56973c, 0x0e9e28eb4, 0x1167f94f2,
538 0x07b3ff57a, 0x19385bf2e, 0x0c9c8b782, 0x0cec3662e,
539 0x13a9cba9e, 0x0e417f38a, 0x093e106a4, 0x19329634a,
540 0x167001a9c, 0x14e727980, 0x1ddffc5d4, 0x0e6fc4e6a,
541 0x00df04680, 0x0d104b8fc, 0x02342001e, 0x08227bb8a,
542 0x00a2a8d7e, 0x05b397730, 0x168763fa6, 0x0b0cd4768,
543 0x1ed5a407a, 0x0e78eb416, 0x0d2c3ed1a, 0x13c2b89c4,
544 0x0995a5724, 0x1641378f0, 0x19b1afbc4, 0x0d7a4825c,
545 0x109ffedc0, 0x08d96551c, 0x0f2271e60, 0x10f5ff2ba,
546 0x00b0bf8ca, 0x00bf80dd2, 0x123888b7a, 0x00167d312,
547 0x1e888f7dc, 0x18dcddd1c, 0x002ee03b2, 0x0f6076544,
548 0x183e8d8fe, 0x06a45d2b2, 0x133d7a042, 0x026f6a60a,
549 0x116b0f50c, 0x1dd3e10e8, 0x05fabe670, 0x1a2adb74e,
550 0x130004488, 0x0de87806c, 0x000bcf5f6, 0x19d34af3a,
551 0x18f0c7078, 0x014338754, 0x017f27698, 0x049c3cc9c,
552 0x058ca5f00, 0x15e3e77ee, 0x1af900c24, 0x068bce87a,
553 0x0b5cfca28, 0x0dd07448e, 0x0ded288f8, 0x1524fa6c6,
554 0x059f229bc, 0x1d8048348, 0x06d390dec, 0x16cba8aca,
555 0x037170390, 0x0a3e3e02c, 0x06353c1cc, 0x042d98888,
556 0x0c4584f5c, 0x0d73c7bea, 0x1f16a3418, 0x1329d9f7e,
557 0x0531377e2, 0x185137662, 0x1d8d9ca7c, 0x1b1c69528,
558 0x0b25b29f2, 0x18a08b5bc, 0x19fb2a8b0, 0x02178513a,
559 0x1a08fe6ac, 0x1da758ae0, 0x045cddf4e, 0x0e0ac139e,
560 0x1a91647f2, 0x169cf9eb0, 0x1a0f717c4, 0x0170076fa,
561};
562
563// Compute the crc32c value for buffer smaller than 8
564#ifdef ROCKSDB_UBSAN_RUN
565#if defined(__clang__)
566__attribute__((__no_sanitize__("alignment")))
567#elif defined(__GNUC__)
568__attribute__((__no_sanitize_undefined__))
569#endif
570#endif
571inline void align_to_8(
572 size_t len,
573 uint64_t& crc0, // crc so far, updated on return
574 const unsigned char*& next) { // next data pointer, updated on return
575 uint32_t crc32bit = static_cast<uint32_t>(crc0);
576 if (len & 0x04) {
577 crc32bit = _mm_crc32_u32(crc32bit, *(uint32_t*)next);
578 next += sizeof(uint32_t);
579 }
580 if (len & 0x02) {
581 crc32bit = _mm_crc32_u16(crc32bit, *(uint16_t*)next);
582 next += sizeof(uint16_t);
583 }
584 if (len & 0x01) {
585 crc32bit = _mm_crc32_u8(crc32bit, *(next));
586 next++;
587 }
588 crc0 = crc32bit;
589}
590
591//
592// CombineCRC performs pclmulqdq multiplication of 2 partial CRC's and a well
593// chosen constant and xor's these with the remaining CRC.
594//
595inline uint64_t CombineCRC(
596 size_t block_size,
597 uint64_t crc0,
598 uint64_t crc1,
599 uint64_t crc2,
600 const uint64_t* next2) {
601 const auto multiplier =
602 *(reinterpret_cast<const __m128i*>(clmul_constants) + block_size - 1);
603 const auto crc0_xmm = _mm_set_epi64x(0, crc0);
604 const auto res0 = _mm_clmulepi64_si128(crc0_xmm, multiplier, 0x00);
605 const auto crc1_xmm = _mm_set_epi64x(0, crc1);
606 const auto res1 = _mm_clmulepi64_si128(crc1_xmm, multiplier, 0x10);
607 const auto res = _mm_xor_si128(res0, res1);
608 crc0 = _mm_cvtsi128_si64(res);
609 crc0 = crc0 ^ *((uint64_t*)next2 - 1);
610 crc2 = _mm_crc32_u64(crc2, crc0);
611 return crc2;
612}
613
614// Compute CRC-32C using the Intel hardware instruction.
615#ifdef ROCKSDB_UBSAN_RUN
616#if defined(__clang__)
617__attribute__((__no_sanitize__("alignment")))
618#elif defined(__GNUC__)
619__attribute__((__no_sanitize_undefined__))
620#endif
621#endif
622uint32_t crc32c_3way(uint32_t crc, const char* buf, size_t len) {
623 const unsigned char* next = (const unsigned char*)buf;
624 uint64_t count;
625 uint64_t crc0, crc1, crc2;
626 crc0 = crc ^ 0xffffffffu;
627
628
629 if (len >= 8) {
630 // if len > 216 then align and use triplets
631 if (len > 216) {
632 {
633 // Work on the bytes (< 8) before the first 8-byte alignment addr starts
634 uint64_t align_bytes = (8 - (uintptr_t)next) & 7;
635 len -= align_bytes;
636 align_to_8(align_bytes, crc0, next);
637 }
638
639 // Now work on the remaining blocks
640 count = len / 24; // number of triplets
641 len %= 24; // bytes remaining
642 uint64_t n = count >> 7; // #blocks = first block + full blocks
643 uint64_t block_size = count & 127;
644 if (block_size == 0) {
645 block_size = 128;
646 } else {
647 n++;
648 }
649 // points to the first byte of the next block
650 const uint64_t* next0 = (uint64_t*)next + block_size;
651 const uint64_t* next1 = next0 + block_size;
652 const uint64_t* next2 = next1 + block_size;
653
654 crc1 = crc2 = 0;
655 // Use Duff's device, a for() loop inside a switch()
656 // statement. This needs to execute at least once, round len
657 // down to nearest triplet multiple
658 switch (block_size) {
659 case 128:
660 do {
661 // jumps here for a full block of len 128
662 CRCtriplet(crc, next, -128);
20effc67 663 FALLTHROUGH_INTENDED;
11fdf7f2
TL		 664 case 127:
665 // jumps here or below for the first block smaller
666 CRCtriplet(crc, next, -127);
20effc67 667 FALLTHROUGH_INTENDED;
11fdf7f2
TL		 668 case 126:
669 CRCtriplet(crc, next, -126); // than 128
20effc67 670 FALLTHROUGH_INTENDED;
11fdf7f2
TL		 671 case 125:
672 CRCtriplet(crc, next, -125);
20effc67 673 FALLTHROUGH_INTENDED;
11fdf7f2
TL		 674 case 124:
675 CRCtriplet(crc, next, -124);
20effc67 676 FALLTHROUGH_INTENDED;
11fdf7f2
TL		 677 case 123:
678 CRCtriplet(crc, next, -123);
20effc67 679 FALLTHROUGH_INTENDED;
11fdf7f2
TL		 680 case 122:
681 CRCtriplet(crc, next, -122);
20effc67 682 FALLTHROUGH_INTENDED;
11fdf7f2
TL		 683 case 121:
684 CRCtriplet(crc, next, -121);
20effc67 685 FALLTHROUGH_INTENDED;
11fdf7f2
TL		 686 case 120:
687 CRCtriplet(crc, next, -120);
688 FALLTHROUGH_INTENDED;
689 case 119:
690 CRCtriplet(crc, next, -119);
691 FALLTHROUGH_INTENDED;
692 case 118:
693 CRCtriplet(crc, next, -118);
694 FALLTHROUGH_INTENDED;
695 case 117:
696 CRCtriplet(crc, next, -117);
697 FALLTHROUGH_INTENDED;
698 case 116:
699 CRCtriplet(crc, next, -116);
700 FALLTHROUGH_INTENDED;
701 case 115:
702 CRCtriplet(crc, next, -115);
703 FALLTHROUGH_INTENDED;
704 case 114:
705 CRCtriplet(crc, next, -114);
706 FALLTHROUGH_INTENDED;
707 case 113:
708 CRCtriplet(crc, next, -113);
709 FALLTHROUGH_INTENDED;
710 case 112:
711 CRCtriplet(crc, next, -112);
712 FALLTHROUGH_INTENDED;
713 case 111:
714 CRCtriplet(crc, next, -111);
715 FALLTHROUGH_INTENDED;
716 case 110:
717 CRCtriplet(crc, next, -110);
718 FALLTHROUGH_INTENDED;
719 case 109:
720 CRCtriplet(crc, next, -109);
721 FALLTHROUGH_INTENDED;
722 case 108:
723 CRCtriplet(crc, next, -108);
724 FALLTHROUGH_INTENDED;
725 case 107:
726 CRCtriplet(crc, next, -107);
727 FALLTHROUGH_INTENDED;
728 case 106:
729 CRCtriplet(crc, next, -106);
730 FALLTHROUGH_INTENDED;
731 case 105:
732 CRCtriplet(crc, next, -105);
733 FALLTHROUGH_INTENDED;
734 case 104:
735 CRCtriplet(crc, next, -104);
736 FALLTHROUGH_INTENDED;
737 case 103:
738 CRCtriplet(crc, next, -103);
739 FALLTHROUGH_INTENDED;
740 case 102:
741 CRCtriplet(crc, next, -102);
742 FALLTHROUGH_INTENDED;
743 case 101:
744 CRCtriplet(crc, next, -101);
745 FALLTHROUGH_INTENDED;
746 case 100:
747 CRCtriplet(crc, next, -100);
748 FALLTHROUGH_INTENDED;
749 case 99:
750 CRCtriplet(crc, next, -99);
751 FALLTHROUGH_INTENDED;
752 case 98:
753 CRCtriplet(crc, next, -98);
754 FALLTHROUGH_INTENDED;
755 case 97:
756 CRCtriplet(crc, next, -97);
757 FALLTHROUGH_INTENDED;
758 case 96:
759 CRCtriplet(crc, next, -96);
760 FALLTHROUGH_INTENDED;
761 case 95:
762 CRCtriplet(crc, next, -95);
763 FALLTHROUGH_INTENDED;
764 case 94:
765 CRCtriplet(crc, next, -94);
766 FALLTHROUGH_INTENDED;
767 case 93:
768 CRCtriplet(crc, next, -93);
769 FALLTHROUGH_INTENDED;
770 case 92:
771 CRCtriplet(crc, next, -92);
772 FALLTHROUGH_INTENDED;
773 case 91:
774 CRCtriplet(crc, next, -91);
775 FALLTHROUGH_INTENDED;
776 case 90:
777 CRCtriplet(crc, next, -90);
778 FALLTHROUGH_INTENDED;
779 case 89:
780 CRCtriplet(crc, next, -89);
781 FALLTHROUGH_INTENDED;
782 case 88:
783 CRCtriplet(crc, next, -88);
784 FALLTHROUGH_INTENDED;
785 case 87:
786 CRCtriplet(crc, next, -87);
787 FALLTHROUGH_INTENDED;
788 case 86:
789 CRCtriplet(crc, next, -86);
790 FALLTHROUGH_INTENDED;
791 case 85:
792 CRCtriplet(crc, next, -85);
793 FALLTHROUGH_INTENDED;
794 case 84:
795 CRCtriplet(crc, next, -84);
796 FALLTHROUGH_INTENDED;
797 case 83:
798 CRCtriplet(crc, next, -83);
799 FALLTHROUGH_INTENDED;
800 case 82:
801 CRCtriplet(crc, next, -82);
802 FALLTHROUGH_INTENDED;
803 case 81:
804 CRCtriplet(crc, next, -81);
805 FALLTHROUGH_INTENDED;
806 case 80:
807 CRCtriplet(crc, next, -80);
808 FALLTHROUGH_INTENDED;
809 case 79:
810 CRCtriplet(crc, next, -79);
811 FALLTHROUGH_INTENDED;
812 case 78:
813 CRCtriplet(crc, next, -78);
814 FALLTHROUGH_INTENDED;
815 case 77:
816 CRCtriplet(crc, next, -77);
817 FALLTHROUGH_INTENDED;
818 case 76:
819 CRCtriplet(crc, next, -76);
820 FALLTHROUGH_INTENDED;
821 case 75:
822 CRCtriplet(crc, next, -75);
823 FALLTHROUGH_INTENDED;
824 case 74:
825 CRCtriplet(crc, next, -74);
826 FALLTHROUGH_INTENDED;
827 case 73:
828 CRCtriplet(crc, next, -73);
829 FALLTHROUGH_INTENDED;
830 case 72:
831 CRCtriplet(crc, next, -72);
832 FALLTHROUGH_INTENDED;
833 case 71:
834 CRCtriplet(crc, next, -71);
835 FALLTHROUGH_INTENDED;
836 case 70:
837 CRCtriplet(crc, next, -70);
838 FALLTHROUGH_INTENDED;
839 case 69:
840 CRCtriplet(crc, next, -69);
841 FALLTHROUGH_INTENDED;
842 case 68:
843 CRCtriplet(crc, next, -68);
844 FALLTHROUGH_INTENDED;
845 case 67:
846 CRCtriplet(crc, next, -67);
847 FALLTHROUGH_INTENDED;
848 case 66:
849 CRCtriplet(crc, next, -66);
850 FALLTHROUGH_INTENDED;
851 case 65:
852 CRCtriplet(crc, next, -65);
853 FALLTHROUGH_INTENDED;
854 case 64:
855 CRCtriplet(crc, next, -64);
856 FALLTHROUGH_INTENDED;
857 case 63:
858 CRCtriplet(crc, next, -63);
859 FALLTHROUGH_INTENDED;
860 case 62:
861 CRCtriplet(crc, next, -62);
862 FALLTHROUGH_INTENDED;
863 case 61:
864 CRCtriplet(crc, next, -61);
865 FALLTHROUGH_INTENDED;
866 case 60:
867 CRCtriplet(crc, next, -60);
868 FALLTHROUGH_INTENDED;
869 case 59:
870 CRCtriplet(crc, next, -59);
871 FALLTHROUGH_INTENDED;
872 case 58:
873 CRCtriplet(crc, next, -58);
874 FALLTHROUGH_INTENDED;
875 case 57:
876 CRCtriplet(crc, next, -57);
877 FALLTHROUGH_INTENDED;
878 case 56:
879 CRCtriplet(crc, next, -56);
880 FALLTHROUGH_INTENDED;
881 case 55:
882 CRCtriplet(crc, next, -55);
883 FALLTHROUGH_INTENDED;
884 case 54:
885 CRCtriplet(crc, next, -54);
886 FALLTHROUGH_INTENDED;
887 case 53:
888 CRCtriplet(crc, next, -53);
889 FALLTHROUGH_INTENDED;
890 case 52:
891 CRCtriplet(crc, next, -52);
892 FALLTHROUGH_INTENDED;
893 case 51:
894 CRCtriplet(crc, next, -51);
895 FALLTHROUGH_INTENDED;
896 case 50:
897 CRCtriplet(crc, next, -50);
898 FALLTHROUGH_INTENDED;
899 case 49:
900 CRCtriplet(crc, next, -49);
901 FALLTHROUGH_INTENDED;
902 case 48:
903 CRCtriplet(crc, next, -48);
904 FALLTHROUGH_INTENDED;
905 case 47:
906 CRCtriplet(crc, next, -47);
907 FALLTHROUGH_INTENDED;
908 case 46:
909 CRCtriplet(crc, next, -46);
910 FALLTHROUGH_INTENDED;
911 case 45:
912 CRCtriplet(crc, next, -45);
913 FALLTHROUGH_INTENDED;
914 case 44:
915 CRCtriplet(crc, next, -44);
916 FALLTHROUGH_INTENDED;
917 case 43:
918 CRCtriplet(crc, next, -43);
919 FALLTHROUGH_INTENDED;
920 case 42:
921 CRCtriplet(crc, next, -42);
922 FALLTHROUGH_INTENDED;
923 case 41:
924 CRCtriplet(crc, next, -41);
925 FALLTHROUGH_INTENDED;
926 case 40:
927 CRCtriplet(crc, next, -40);
928 FALLTHROUGH_INTENDED;
929 case 39:
930 CRCtriplet(crc, next, -39);
931 FALLTHROUGH_INTENDED;
932 case 38:
933 CRCtriplet(crc, next, -38);
934 FALLTHROUGH_INTENDED;
935 case 37:
936 CRCtriplet(crc, next, -37);
937 FALLTHROUGH_INTENDED;
938 case 36:
939 CRCtriplet(crc, next, -36);
940 FALLTHROUGH_INTENDED;
941 case 35:
942 CRCtriplet(crc, next, -35);
943 FALLTHROUGH_INTENDED;
944 case 34:
945 CRCtriplet(crc, next, -34);
946 FALLTHROUGH_INTENDED;
947 case 33:
948 CRCtriplet(crc, next, -33);
949 FALLTHROUGH_INTENDED;
950 case 32:
951 CRCtriplet(crc, next, -32);
952 FALLTHROUGH_INTENDED;
953 case 31:
954 CRCtriplet(crc, next, -31);
955 FALLTHROUGH_INTENDED;
956 case 30:
957 CRCtriplet(crc, next, -30);
958 FALLTHROUGH_INTENDED;
959 case 29:
960 CRCtriplet(crc, next, -29);
961 FALLTHROUGH_INTENDED;
962 case 28:
963 CRCtriplet(crc, next, -28);
964 FALLTHROUGH_INTENDED;
965 case 27:
966 CRCtriplet(crc, next, -27);
967 FALLTHROUGH_INTENDED;
968 case 26:
969 CRCtriplet(crc, next, -26);
970 FALLTHROUGH_INTENDED;
971 case 25:
972 CRCtriplet(crc, next, -25);
973 FALLTHROUGH_INTENDED;
974 case 24:
975 CRCtriplet(crc, next, -24);
976 FALLTHROUGH_INTENDED;
977 case 23:
978 CRCtriplet(crc, next, -23);
979 FALLTHROUGH_INTENDED;
980 case 22:
981 CRCtriplet(crc, next, -22);
982 FALLTHROUGH_INTENDED;
983 case 21:
984 CRCtriplet(crc, next, -21);
985 FALLTHROUGH_INTENDED;
986 case 20:
987 CRCtriplet(crc, next, -20);
988 FALLTHROUGH_INTENDED;
989 case 19:
990 CRCtriplet(crc, next, -19);
991 FALLTHROUGH_INTENDED;
992 case 18:
993 CRCtriplet(crc, next, -18);
994 FALLTHROUGH_INTENDED;
995 case 17:
996 CRCtriplet(crc, next, -17);
997 FALLTHROUGH_INTENDED;
998 case 16:
999 CRCtriplet(crc, next, -16);
1000 FALLTHROUGH_INTENDED;
1001 case 15:
1002 CRCtriplet(crc, next, -15);
1003 FALLTHROUGH_INTENDED;
1004 case 14:
1005 CRCtriplet(crc, next, -14);
1006 FALLTHROUGH_INTENDED;
1007 case 13:
1008 CRCtriplet(crc, next, -13);
1009 FALLTHROUGH_INTENDED;
1010 case 12:
1011 CRCtriplet(crc, next, -12);
1012 FALLTHROUGH_INTENDED;
1013 case 11:
1014 CRCtriplet(crc, next, -11);
1015 FALLTHROUGH_INTENDED;
1016 case 10:
1017 CRCtriplet(crc, next, -10);
1018 FALLTHROUGH_INTENDED;
1019 case 9:
1020 CRCtriplet(crc, next, -9);
1021 FALLTHROUGH_INTENDED;
1022 case 8:
1023 CRCtriplet(crc, next, -8);
1024 FALLTHROUGH_INTENDED;
1025 case 7:
1026 CRCtriplet(crc, next, -7);
1027 FALLTHROUGH_INTENDED;
1028 case 6:
1029 CRCtriplet(crc, next, -6);
1030 FALLTHROUGH_INTENDED;
1031 case 5:
1032 CRCtriplet(crc, next, -5);
1033 FALLTHROUGH_INTENDED;
1034 case 4:
1035 CRCtriplet(crc, next, -4);
1036 FALLTHROUGH_INTENDED;
1037 case 3:
1038 CRCtriplet(crc, next, -3);
1039 FALLTHROUGH_INTENDED;
1040 case 2:
1041 CRCtriplet(crc, next, -2);
1042 FALLTHROUGH_INTENDED;
1043 case 1:
1044 CRCduplet(crc, next, -1); // the final triplet is actually only 2
1045 //{ CombineCRC(); }
1046 crc0 = CombineCRC(block_size, crc0, crc1, crc2, next2);
1047 if (--n > 0) {
1048 crc1 = crc2 = 0;
1049 block_size = 128;
1050 // points to the first byte of the next block
1051 next0 = next2 + 128;
1052 next1 = next0 + 128; // from here on all blocks are 128 long
1053 next2 = next1 + 128;
1054 }
1055 FALLTHROUGH_INTENDED;
1056 case 0:;
1057 } while (n > 0);
1058 }
1059 next = (const unsigned char*)next2;
1060 }
1061 uint64_t count2 = len >> 3; // 216 of less bytes is 27 or less singlets
1062 len = len & 7;
1063 next += (count2 * 8);
1064 switch (count2) {
1065 case 27:
1066 CRCsinglet(crc0, next, -27 * 8);
1067 FALLTHROUGH_INTENDED;
1068 case 26:
1069 CRCsinglet(crc0, next, -26 * 8);
1070 FALLTHROUGH_INTENDED;
1071 case 25:
1072 CRCsinglet(crc0, next, -25 * 8);
1073 FALLTHROUGH_INTENDED;
1074 case 24:
1075 CRCsinglet(crc0, next, -24 * 8);
1076 FALLTHROUGH_INTENDED;
1077 case 23:
1078 CRCsinglet(crc0, next, -23 * 8);
1079 FALLTHROUGH_INTENDED;
1080 case 22:
1081 CRCsinglet(crc0, next, -22 * 8);
1082 FALLTHROUGH_INTENDED;
1083 case 21:
1084 CRCsinglet(crc0, next, -21 * 8);
1085 FALLTHROUGH_INTENDED;
1086 case 20:
1087 CRCsinglet(crc0, next, -20 * 8);
1088 FALLTHROUGH_INTENDED;
1089 case 19:
1090 CRCsinglet(crc0, next, -19 * 8);
1091 FALLTHROUGH_INTENDED;
1092 case 18:
1093 CRCsinglet(crc0, next, -18 * 8);
1094 FALLTHROUGH_INTENDED;
1095 case 17:
1096 CRCsinglet(crc0, next, -17 * 8);
1097 FALLTHROUGH_INTENDED;
1098 case 16:
1099 CRCsinglet(crc0, next, -16 * 8);
1100 FALLTHROUGH_INTENDED;
1101 case 15:
1102 CRCsinglet(crc0, next, -15 * 8);
1103 FALLTHROUGH_INTENDED;
1104 case 14:
1105 CRCsinglet(crc0, next, -14 * 8);
1106 FALLTHROUGH_INTENDED;
1107 case 13:
1108 CRCsinglet(crc0, next, -13 * 8);
1109 FALLTHROUGH_INTENDED;
1110 case 12:
1111 CRCsinglet(crc0, next, -12 * 8);
1112 FALLTHROUGH_INTENDED;
1113 case 11:
1114 CRCsinglet(crc0, next, -11 * 8);
1115 FALLTHROUGH_INTENDED;
1116 case 10:
1117 CRCsinglet(crc0, next, -10 * 8);
1118 FALLTHROUGH_INTENDED;
1119 case 9:
1120 CRCsinglet(crc0, next, -9 * 8);
1121 FALLTHROUGH_INTENDED;
1122 case 8:
1123 CRCsinglet(crc0, next, -8 * 8);
1124 FALLTHROUGH_INTENDED;
1125 case 7:
1126 CRCsinglet(crc0, next, -7 * 8);
1127 FALLTHROUGH_INTENDED;
1128 case 6:
1129 CRCsinglet(crc0, next, -6 * 8);
1130 FALLTHROUGH_INTENDED;
1131 case 5:
1132 CRCsinglet(crc0, next, -5 * 8);
1133 FALLTHROUGH_INTENDED;
1134 case 4:
1135 CRCsinglet(crc0, next, -4 * 8);
1136 FALLTHROUGH_INTENDED;
1137 case 3:
1138 CRCsinglet(crc0, next, -3 * 8);
1139 FALLTHROUGH_INTENDED;
1140 case 2:
1141 CRCsinglet(crc0, next, -2 * 8);
1142 FALLTHROUGH_INTENDED;
1143 case 1:
1144 CRCsinglet(crc0, next, -1 * 8);
1145 FALLTHROUGH_INTENDED;
1146 case 0:;
1147 }
1148 }
1149 {
1150 align_to_8(len, crc0, next);
1151 return (uint32_t)crc0 ^ 0xffffffffu;
1152 }
1153}
1154
1155#endif //HAVE_SSE42 && HAVE_PCLMUL
1156
1157static inline Function Choose_Extend() {
f67539c2
TL		 1158#ifdef HAVE_POWER8
1159 return isAltiVec() ? ExtendPPCImpl : ExtendImpl<Slow_CRC32>;
1e59de90 1160#elif defined(HAVE_ARM64_CRC)
f67539c2 1161 if(crc32c_runtime_check()) {
b3b6e05e 1162 pmull_runtime_flag = crc32c_pmull_runtime_check();
f67539c2
TL		 1163 return ExtendARMImpl;
1164 } else {
1165 return ExtendImpl<Slow_CRC32>;
1166 }
1167#else
11fdf7f2
TL		 1168 if (isSSE42()) {
1169 if (isPCLMULQDQ()) {
1e59de90 1170#if (defined HAVE_SSE42 && defined HAVE_PCLMUL) && !defined NO_THREEWAY_CRC32C
11fdf7f2
TL		 1171 return crc32c_3way;
1172#else
1173 return ExtendImpl<Fast_CRC32>; // Fast_CRC32 will check HAVE_SSE42 itself
1174#endif
1175 }
1176 else { // no runtime PCLMULQDQ support but has SSE42 support
1177 return ExtendImpl<Fast_CRC32>;
1178 }
1179 } // end of isSSE42()
1180 else {
1181 return ExtendImpl<Slow_CRC32>;
1182 }
11fdf7f2
TL		 1183#endif
1184}
1185
1186static Function ChosenExtend = Choose_Extend();
7c673cae
FG		 1187uint32_t Extend(uint32_t crc, const char* buf, size_t size) {
1188 return ChosenExtend(crc, buf, size);
1189}
1190
1e59de90
TL		 1191// The code for crc32c combine, copied with permission from folly
1192
1193// Standard galois-field multiply. The only modification is that a,
1194// b, m, and p are all bit-reflected.
1195//
1196// https://en.wikipedia.org/wiki/Finite_field_arithmetic
1197static constexpr uint32_t gf_multiply_sw_1(
1198 size_t i, uint32_t p, uint32_t a, uint32_t b, uint32_t m) {
1199 // clang-format off
1200 return i == 32 ? p : gf_multiply_sw_1(
1201 /* i = */ i + 1,
1202 /* p = */ p ^ ((0u-((b >> 31) & 1)) & a),
1203 /* a = */ (a >> 1) ^ ((0u-(a & 1)) & m),
1204 /* b = */ b << 1,
1205 /* m = */ m);
1206 // clang-format on
1207}
1208static constexpr uint32_t gf_multiply_sw(uint32_t a, uint32_t b, uint32_t m) {
1209 return gf_multiply_sw_1(/* i = */ 0, /* p = */ 0, a, b, m);
1210}
1211
1212static constexpr uint32_t gf_square_sw(uint32_t a, uint32_t m) {
1213 return gf_multiply_sw(a, a, m);
1214}
1215
1216template <size_t i, uint32_t m>
1217struct gf_powers_memo {
1218 static constexpr uint32_t value =
1219 gf_square_sw(gf_powers_memo<i - 1, m>::value, m);
1220};
1221template <uint32_t m>
1222struct gf_powers_memo<0, m> {
1223 static constexpr uint32_t value = m;
1224};
1225
1226template <typename T, T... Ints>
1227struct integer_sequence {
1228 using value_type = T;
1229 static constexpr size_t size() { return sizeof...(Ints); }
1230};
1231
1232template <typename T, std::size_t N, T... Is>
1233struct make_integer_sequence : make_integer_sequence<T, N - 1, N - 1, Is...> {};
1234
1235template <typename T, T... Is>
1236struct make_integer_sequence<T, 0, Is...> : integer_sequence<T, Is...> {};
1237
1238template <std::size_t N>
1239using make_index_sequence = make_integer_sequence<std::size_t, N>;
1240
1241template <uint32_t m>
1242struct gf_powers_make {
1243 template <size_t... i>
1244 using index_sequence = integer_sequence<size_t, i...>;
1245 template <size_t... i>
1246 constexpr std::array<uint32_t, sizeof...(i)> operator()(
1247 index_sequence<i...>) const {
1248 return std::array<uint32_t, sizeof...(i)>{{gf_powers_memo<i, m>::value...}};
1249 }
1250};
1251
1252static constexpr uint32_t crc32c_m = 0x82f63b78;
1253
1254static constexpr std::array<uint32_t, 62> const crc32c_powers =
1255 gf_powers_make<crc32c_m>{}(make_index_sequence<62>{});
1256
1257// Expects a "pure" crc (see Crc32cCombine)
1258static uint32_t Crc32AppendZeroes(
1259 uint32_t crc, size_t len_over_4, uint32_t polynomial,
1260 std::array<uint32_t, 62> const& powers_array) {
1261 auto powers = powers_array.data();
1262 // Append by multiplying by consecutive powers of two of the zeroes
1263 // array
1264 size_t len_bits = len_over_4;
1265
1266 while (len_bits) {
1267 // Advance directly to next bit set.
1268 auto r = CountTrailingZeroBits(len_bits);
1269 len_bits >>= r;
1270 powers += r;
1271
1272 crc = gf_multiply_sw(crc, *powers, polynomial);
1273
1274 len_bits >>= 1;
1275 powers++;
1276 }
1277
1278 return crc;
1279}
1280
1281static inline uint32_t InvertedToPure(uint32_t crc) { return ~crc; }
1282
1283static inline uint32_t PureToInverted(uint32_t crc) { return ~crc; }
1284
1285static inline uint32_t PureExtend(uint32_t crc, const char* buf, size_t size) {
1286 return InvertedToPure(Extend(PureToInverted(crc), buf, size));
1287}
1288
1289// Background:
1290// RocksDB uses two kinds of crc32c values: masked and unmasked. Neither is
1291// a "pure" CRC because a pure CRC satisfies (^ for xor)
1292// crc(a ^ b) = crc(a) ^ crc(b)
1293// The unmasked is closest, and this function takes unmasked crc32c values.
1294// The unmasked values are impure in two ways:
1295// * The initial setting at the start of CRC computation is all 1 bits
1296// (like -1) instead of zero.
1297// * The result has all bits invered.
1298// Note that together, these result in the empty string having a crc32c of
1299// zero. See
1300// https://en.wikipedia.org/wiki/Computation_of_cyclic_redundancy_checks#CRC_variants
1301//
1302// Simplified version of strategy, using xor through pure CRCs (+ for concat):
1303//
1304// pure_crc(str1 + str2) = pure_crc(str1 + zeros(len(str2))) ^
1305// pure_crc(zeros(len(str1)) + str2)
1306//
1307// because the xor of these two zero-padded strings is str1 + str2. For pure
1308// CRC, leading zeros don't affect the result, so we only need
1309//
1310// pure_crc(str1 + str2) = pure_crc(str1 + zeros(len(str2))) ^
1311// pure_crc(str2)
1312//
1313// Considering we aren't working with pure CRCs, what is actually in the input?
1314//
1315// crc1 = PureToInverted(PureExtendCrc32c(-1, zeros, crc1len) ^
1316// PureCrc32c(str1, crc1len))
1317// crc2 = PureToInverted(PureExtendCrc32c(-1, zeros, crc2len) ^
1318// PureCrc32c(str2, crc2len))
1319//
1320// The result we want to compute is
1321// combined = PureToInverted(PureExtendCrc32c(PureExtendCrc32c(-1, zeros,
1322// crc1len) ^
1323// PureCrc32c(str1, crc1len),
1324// zeros, crc2len) ^
1325// PureCrc32c(str2, crc2len))
1326//
1327// Thus, in addition to extending crc1 over the length of str2 in (virtual)
1328// zeros, we need to cancel out the -1 initializer that was used in computing
1329// crc2. To cancel it out, we also need to extend it over crc2len in zeros.
1330// To simplify, since the end of str1 and that -1 initializer for crc2 are at
1331// the same logical position, we can combine them before we extend over the
1332// zeros.
1333uint32_t Crc32cCombine(uint32_t crc1, uint32_t crc2, size_t crc2len) {
1334 uint32_t pure_crc1_with_init = InvertedToPure(crc1);
1335 uint32_t pure_crc2_with_init = InvertedToPure(crc2);
1336 uint32_t pure_crc2_init = static_cast<uint32_t>(-1);
1337
1338 // Append up to 32 bits of zeroes in the normal way
1339 char zeros[4] = {0, 0, 0, 0};
1340 auto len = crc2len & 3;
1341 uint32_t tmp = pure_crc1_with_init ^ pure_crc2_init;
1342 if (len) {
1343 tmp = PureExtend(tmp, zeros, len);
1344 }
1345 return PureToInverted(
1346 Crc32AppendZeroes(tmp, crc2len / 4, crc32c_m, crc32c_powers) ^
1347 pure_crc2_with_init);
1348}
11fdf7f2 1349
7c673cae 1350} // namespace crc32c
f67539c2 1351} // namespace ROCKSDB_NAMESPACE
Ceph