From c4d8838a2b54cb364ee3f05d86c8f980ac59bbc1 Mon Sep 17 00:00:00 2001 From: Peter Dillinger Date: Thu, 3 Sep 2020 09:31:28 -0700 Subject: New bit manipulation functions and 128-bit value library (#7338) Summary: These new functions and 128-bit value bit operations are expected to be used in a forthcoming Bloom filter alternative. No functional changes to production code, just new code only called by unit tests, cosmetic changes to existing headers, and fix an existing function for a yet-unused template instantiation (BitsSetToOne on something signed and smaller than 32 bits). Pull Request resolved: https://github.com/facebook/rocksdb/pull/7338 Test Plan: Unit tests included. Works with and without TEST_UINT128_COMPAT=1 to check compatibility with and without __uint128_t. Also added that parameter to the CircleCI build build-linux-shared_lib-alt_namespace-status_checked. Reviewed By: jay-zhuang Differential Revision: D23494945 Pulled By: pdillinger fbshipit-source-id: 5c0dc419100d9df5d4d9abb153b2855d5aea39e8 --- util/hash_test.cc | 157 +++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 156 insertions(+), 1 deletion(-) (limited to 'util/hash_test.cc') diff --git a/util/hash_test.cc b/util/hash_test.cc index 9c3c6efe9..802fb27f3 100644 --- a/util/hash_test.cc +++ b/util/hash_test.cc @@ -7,12 +7,14 @@ // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. See the AUTHORS file for names of contributors. +#include "util/hash.h" + #include #include #include "test_util/testharness.h" #include "util/coding.h" -#include "util/hash.h" +#include "util/math128.h" using ROCKSDB_NAMESPACE::EncodeFixed32; using ROCKSDB_NAMESPACE::GetSliceHash64; @@ -370,6 +372,159 @@ size_t fastrange64(uint64_t hash, size_t range) { return ROCKSDB_NAMESPACE::fastrange64(hash, range); } +// Tests for math.h / math128.h (not worth a separate test binary) +using ROCKSDB_NAMESPACE::BitParity; +using ROCKSDB_NAMESPACE::BitsSetToOne; +using ROCKSDB_NAMESPACE::CountTrailingZeroBits; +using ROCKSDB_NAMESPACE::DecodeFixed128; +using ROCKSDB_NAMESPACE::EncodeFixed128; +using ROCKSDB_NAMESPACE::FloorLog2; +using ROCKSDB_NAMESPACE::Lower64of128; +using ROCKSDB_NAMESPACE::Multiply64to128; +using ROCKSDB_NAMESPACE::Unsigned128; +using ROCKSDB_NAMESPACE::Upper64of128; + +template +static void test_BitOps() { + // This complex code is to generalize to 128-bit values. Otherwise + // we could just use = static_cast(0x5555555555555555ULL); + T everyOtherBit = 0; + for (unsigned i = 0; i < sizeof(T); ++i) { + everyOtherBit = (everyOtherBit << 8) | T{0x55}; + } + + // This one built using bit operations, as our 128-bit layer + // might not implement arithmetic such as subtraction. + T vm1 = 0; // "v minus one" + + for (int i = 0; i < int{8 * sizeof(T)}; ++i) { + T v = T{1} << i; + // If we could directly use arithmetic: + // T vm1 = static_cast(v - 1); + + // FloorLog2 + if (v > 0) { + EXPECT_EQ(FloorLog2(v), i); + } + if (vm1 > 0) { + EXPECT_EQ(FloorLog2(vm1), i - 1); + EXPECT_EQ(FloorLog2(everyOtherBit & vm1), (i - 1) & ~1); + } + + // CountTrailingZeroBits + if (v != 0) { + EXPECT_EQ(CountTrailingZeroBits(v), i); + } + if (vm1 != 0) { + EXPECT_EQ(CountTrailingZeroBits(vm1), 0); + } + if (i < int{8 * sizeof(T)} - 1) { + EXPECT_EQ(CountTrailingZeroBits(~vm1 & everyOtherBit), (i + 1) & ~1); + } + + // BitsSetToOne + EXPECT_EQ(BitsSetToOne(v), 1); + EXPECT_EQ(BitsSetToOne(vm1), i); + EXPECT_EQ(BitsSetToOne(vm1 & everyOtherBit), (i + 1) / 2); + + // BitParity + EXPECT_EQ(BitParity(v), 1); + EXPECT_EQ(BitParity(vm1), i & 1); + EXPECT_EQ(BitParity(vm1 & everyOtherBit), ((i + 1) / 2) & 1); + + vm1 = (vm1 << 1) | 1; + } +} + +TEST(MathTest, BitOps) { + test_BitOps(); + test_BitOps(); + test_BitOps(); + test_BitOps(); + test_BitOps(); + test_BitOps(); + test_BitOps(); + test_BitOps(); + test_BitOps(); + test_BitOps(); + test_BitOps(); + test_BitOps(); + test_BitOps(); + test_BitOps(); + test_BitOps(); + test_BitOps(); + test_BitOps(); + test_BitOps(); + test_BitOps(); + test_BitOps(); + test_BitOps(); +} + +TEST(MathTest, BitOps128) { test_BitOps(); } + +TEST(MathTest, Math128) { + const Unsigned128 sixteenHexOnes = 0x1111111111111111U; + const Unsigned128 thirtyHexOnes = (sixteenHexOnes << 56) | sixteenHexOnes; + const Unsigned128 sixteenHexTwos = 0x2222222222222222U; + const Unsigned128 thirtyHexTwos = (sixteenHexTwos << 56) | sixteenHexTwos; + + // v will slide from all hex ones to all hex twos + Unsigned128 v = thirtyHexOnes; + for (int i = 0; i <= 30; ++i) { + // Test bitwise operations + EXPECT_EQ(BitsSetToOne(v), 30); + EXPECT_EQ(BitsSetToOne(~v), 128 - 30); + EXPECT_EQ(BitsSetToOne(v & thirtyHexOnes), 30 - i); + EXPECT_EQ(BitsSetToOne(v | thirtyHexOnes), 30 + i); + EXPECT_EQ(BitsSetToOne(v ^ thirtyHexOnes), 2 * i); + EXPECT_EQ(BitsSetToOne(v & thirtyHexTwos), i); + EXPECT_EQ(BitsSetToOne(v | thirtyHexTwos), 60 - i); + EXPECT_EQ(BitsSetToOne(v ^ thirtyHexTwos), 60 - 2 * i); + + // Test comparisons + EXPECT_EQ(v == thirtyHexOnes, i == 0); + EXPECT_EQ(v == thirtyHexTwos, i == 30); + EXPECT_EQ(v > thirtyHexOnes, i > 0); + EXPECT_EQ(v > thirtyHexTwos, false); + EXPECT_EQ(v >= thirtyHexOnes, true); + EXPECT_EQ(v >= thirtyHexTwos, i == 30); + EXPECT_EQ(v < thirtyHexOnes, false); + EXPECT_EQ(v < thirtyHexTwos, i < 30); + EXPECT_EQ(v <= thirtyHexOnes, i == 0); + EXPECT_EQ(v <= thirtyHexTwos, true); + + // Update v, clearing upper-most byte + v = ((v << 12) >> 8) | 0x2; + } + + for (int i = 0; i < 128; ++i) { + // Test shifts + Unsigned128 sl = thirtyHexOnes << i; + Unsigned128 sr = thirtyHexOnes >> i; + EXPECT_EQ(BitsSetToOne(sl), std::min(30, 32 - i / 4)); + EXPECT_EQ(BitsSetToOne(sr), std::max(0, 30 - (i + 3) / 4)); + EXPECT_EQ(BitsSetToOne(sl & sr), i % 2 ? 0 : std::max(0, 30 - i / 2)); + } + + // Test 64x64->128 multiply + Unsigned128 product = + Multiply64to128(0x1111111111111111U, 0x2222222222222222U); + EXPECT_EQ(Lower64of128(product), 2295594818061633090U); + EXPECT_EQ(Upper64of128(product), 163971058432973792U); +} + +TEST(MathTest, Coding128) { + const char *in = "_1234567890123456"; + Unsigned128 decoded = DecodeFixed128(in + 1); + EXPECT_EQ(Lower64of128(decoded), 4050765991979987505U); + EXPECT_EQ(Upper64of128(decoded), 3906085646303834169U); + char out[18]; + out[0] = '_'; + EncodeFixed128(out + 1, decoded); + out[17] = '\0'; + EXPECT_EQ(std::string(in), std::string(out)); +} + int main(int argc, char** argv) { ::testing::InitGoogleTest(&argc, argv); -- cgit v1.2.3-70-g09d2