Skip to content

Instantly share code, notes, and snippets.

@davezarzycki

davezarzycki/crc64_up_to_191_bits.cpp

Last active June 23, 2022 02:02
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save davezarzycki/86be758beb05afcac0b90f28255218e2 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save davezarzycki/86be758beb05afcac0b90f28255218e2 to your computer and use it in GitHub Desktop.
Download ZIP
CRC examples with poly: 0x(1)E691A23E28619DF3
Raw
crc64_up_to_191_bits.cpp
// Copyright (c) 2022 David Zarzycki
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to
// deal in the Software without restriction, including without limitation the
// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
// sell copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
// IN THE SOFTWARE.
#include <assert.h>
#include <stdint.h>
#include <immintrin.h>
// This sample code computes a 64b hash using a specialized CRC that is
// optimized for data less than 192 bits and provides a Hamming distance of 17
// over 255 bits (i.e. including the CRC result itself). What does that mean
// for hashing?
//
// 1) Given a random value <192 bits, any combination of changes <17 bits will
// always result in a different hash value. That's >2^76 potential changes!
// 2) Given a random value <192 bits, all combinations of changes <9 bits will
// always result in a collision-free set. That's >2^45 hash values! In
// contrast, a hash function that aspires to random output will probably
// start having collisions around 2^32 values in the set.
// 3) Smaller changes result in bigger changes in the hash value. For example,
// changing any combination of 7 bits guarantees that 10+ bits change in
// the CRC result.
//
//
// Details to know:
//
// 1) Hashing an empty/zero buffer will result in a hash value of zero.
// 2) You're not implementing hardware so you can arguably ignore the tricks
// used to detect extra bits at the start of data being checksummed.
// 3) That being said, if trailing zeros are semantically meaningful, you might
// want to set a bit right after the last zero in the data.
// 4) You can push this hash to <=192 bits instead of <192 bits, but the
// caveat is that extra bit will only flip the top or bottom bit of the
// CRC result depending on how the CRC is computed.
// 5) Do not nest this hash. I.e. this: crc64z8({ x, crc64z8(buffer) }) because
// this behaves like buffer concatenation, which is incompatible with the
// core design of this CRC. Also avoid this: crc64z8({ crc64z8(buffer), x })
// I haven't studied how this behaves but the behavior is not good.
// 6) CRCs are ideal for hash flood attacks, so you really should not use this
// with untrusted data. (I think creating a random permute pattern at launch
// and then permutting the data before the CRC can solve that problem but I
// haven't tested this idea.)
//
// And for the curious, the higher Hamming distance message lengths (not
// including the CRC itself):
//
// HD 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
// Bits 48 32 32 29 16 16 7 7 7 7 6 5 5 1 1 1
namespace {
inline uint64_t rdrand() {
unsigned long long result;
while (__builtin_ia32_rdrand64_step(&result) == 0) {
__builtin_ia32_pause();
}
return result;
}
void update_rem(uint64_t &rem, uint64_t poly) {
if (int64_t(rem) < 0) {
rem = (rem << 1) ^ poly;
} else {
rem <<= 1;
}
}
const __m128i inv_and_poly = { int64_t(0x9EB373F963A012AAULL), int64_t(0xE691A23E28619DF3ULL) };
const __m128i fold_magic = { 0x15014A680736459ELL, 0x67B9985917234E53LL };
template<unsigned N>
uint64_t crc64z8(const uint64_t (&buffer)[N]) {
__m128i fold = {};
static_assert(N > 0 && N < 4);
switch (N) {
case 3: {
__m128i temp = { int64_t(buffer[2]), 0 };
fold = _mm_clmulepi64_si128(temp, fold_magic, 0x10);
[[fallthrough]];
}
case 2: {
__m128i temp = { int64_t(buffer[0]), int64_t(buffer[1]) };
fold ^= _mm_clmulepi64_si128(temp, fold_magic, 0x01) ^ _mm_slli_si128(temp, 8);
break;
}
default: {
fold = { 0, int64_t(buffer[0]) };
break;
}
}
auto first = _mm_clmulepi64_si128(inv_and_poly, fold, 0x10) ^ fold;
auto result = _mm_clmulepi64_si128(inv_and_poly, first, 0x11);
if (N > 1) {
result ^= fold;
}
return uint64_t(result[0]);
}
};
int main() {
uint64_t buffer[3] = { rdrand(), rdrand(), rdrand() };
const auto poly = uint64_t(inv_and_poly[1]);
// The literal is in Koopman notation which is nice because the notation
// self-documents the CRC size at the cost of implying the +1 coefficient.
assert(poly == ((0xF348D11F1430CEF9ull << 1) | 1));
// First compute the result one bit at a time.
uint64_t rem = poly;
uint64_t crc1 = 0;
for (unsigned i = 0; i < 64*3; i++) {
if (buffer[i / 64] & (1ull << (i % 64))) {
crc1 ^= rem;
}
update_rem(rem, poly);
}
assert(rem == 2);
// Now compute the result one "round" at a time.
uint64_t crc2 = 0;
for (int i = 2; i >= 0; i--) {
crc2 = crc64z8({ crc2 ^ buffer[i] });
}
// Finally compute the result as a buffer via folding tricks.
uint64_t crc3 = crc64z8(buffer);
assert(crc1 == crc2);
assert(crc1 == crc3);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment