From 856c7dc51dcccc0c6f31a48e42a7a29475351828 Mon Sep 17 00:00:00 2001 From: Elliot Gorokhovsky Date: Wed, 16 Feb 2022 11:16:55 -0500 Subject: [PATCH] Fix fuzzer.c nits and replace CLZ fallback --- lib/common/bits.h | 16 ++++++++++------ tests/fuzzer.c | 24 ++++++++++++++++++------ 2 files changed, 28 insertions(+), 12 deletions(-) diff --git a/lib/common/bits.h b/lib/common/bits.h index 191e68a78..2c4ade865 100644 --- a/lib/common/bits.h +++ b/lib/common/bits.h @@ -51,12 +51,16 @@ MEM_STATIC unsigned ZSTD_countTrailingZeros32(U32 val) MEM_STATIC unsigned ZSTD_countLeadingZeros32_fallback(U32 val) { assert(val != 0); { - unsigned result = 0; - while ((val & 0x80000000) == 0) { - result++; - val <<= 1; - } - return result; + static const U32 DeBruijnClz[32] = {0, 9, 1, 10, 13, 21, 2, 29, + 11, 14, 16, 18, 22, 25, 3, 30, + 8, 12, 20, 28, 15, 17, 24, 7, + 19, 27, 23, 6, 26, 5, 4, 31}; + val |= val >> 1; + val |= val >> 2; + val |= val >> 4; + val |= val >> 8; + val |= val >> 16; + return DeBruijnClz[(val * 0x07C4ACDDU) >> 27] ^ 31; } } diff --git a/tests/fuzzer.c b/tests/fuzzer.c index 9b31469e3..047afc1c8 100644 --- a/tests/fuzzer.c +++ b/tests/fuzzer.c @@ -3377,22 +3377,26 @@ static int basicUnitTests(U32 const seed, double compressibility) DISPLAYLEVEL(3, "test%3i : testing bitwise instrinsics PR#3045: ", testNb++); { - U32 seed_32 = seed == 0 ? seed + 1 : seed; // these intrinsics are undefined on 0 - U64 seed_64 = (U64)seed * 0x87654321; // decent 64-bit distribution + U32 seed_copy = seed; // need non-const seed to avoid compiler warning for FUZ_rand(&seed) + U32 rand32 = FUZ_rand(&seed_copy); + U64 rand64 = ((U64)FUZ_rand(&seed_copy) << 32) | FUZ_rand(&seed_copy); U32 lowbit_only_32 = 1; U64 lowbit_only_64 = 1; U32 highbit_only_32 = (U32)1 << 31; U64 highbit_only_64 = (U64)1 << 63; + U32 i; + if (rand32 == 0) rand32 = 1; // CLZ and CTZ are undefined on 0 + if (rand64 == 0) rand64 = 1; // CLZ and CTZ are undefined on 0 /* Test ZSTD_countTrailingZeros32 */ CHECK_EQ(ZSTD_countTrailingZeros32(lowbit_only_32), 0u); CHECK_EQ(ZSTD_countTrailingZeros32(highbit_only_32), 31u); - CHECK_EQ(ZSTD_countTrailingZeros32(seed_32), ZSTD_countTrailingZeros32_fallback(seed_32)); + CHECK_EQ(ZSTD_countTrailingZeros32(rand32), ZSTD_countTrailingZeros32_fallback(rand32)); /* Test ZSTD_countLeadingZeros32 */ CHECK_EQ(ZSTD_countLeadingZeros32(lowbit_only_32), 31u); CHECK_EQ(ZSTD_countLeadingZeros32(highbit_only_32), 0u); - CHECK_EQ(ZSTD_countLeadingZeros32(seed_32), ZSTD_countLeadingZeros32_fallback(seed_32)); + CHECK_EQ(ZSTD_countLeadingZeros32(rand32), ZSTD_countLeadingZeros32_fallback(rand32)); /* Test ZSTD_countTrailingZeros64 */ CHECK_EQ(ZSTD_countTrailingZeros64(lowbit_only_64), 0u); @@ -3426,8 +3430,16 @@ static int basicUnitTests(U32 const seed, double compressibility) } /* Test MEM_ intrinsics */ - CHECK_EQ(MEM_swap32(seed_32), MEM_swap32_fallback(seed_32)); - CHECK_EQ(MEM_swap64(seed_64), MEM_swap64_fallback(seed_64)); + CHECK_EQ(MEM_swap32(rand32), MEM_swap32_fallback(rand32)); + CHECK_EQ(MEM_swap64(rand64), MEM_swap64_fallback(rand64)); + + /* Test fallbacks vs intrinsics on a range of small integers */ + for (i=1; i <= 1000; i++) { + CHECK_EQ(MEM_swap32(i), MEM_swap32_fallback(i)); + CHECK_EQ(MEM_swap64((U64)i), MEM_swap64_fallback((U64)i)); + CHECK_EQ(ZSTD_countTrailingZeros32(i), ZSTD_countTrailingZeros32_fallback(i)); + CHECK_EQ(ZSTD_countLeadingZeros32(i), ZSTD_countLeadingZeros32_fallback(i)); + } } DISPLAYLEVEL(3, "OK \n"); -- 2.47.3