238 lines · cpp
1//===-- Unittests for Bit -------------------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#include "hdr/stdint_proxy.h"10#include "src/__support/CPP/bit.h"11#include "src/__support/big_int.h"12#include "src/__support/macros/config.h"13#include "src/__support/macros/properties/types.h" // LIBC_TYPES_HAS_INT12814#include "test/UnitTest/Test.h"15 16namespace LIBC_NAMESPACE_DECL {17namespace cpp {18 19using UnsignedTypes = testing::TypeList<20#if defined(LIBC_TYPES_HAS_INT128)21 __uint128_t,22#endif // LIBC_TYPES_HAS_INT12823 unsigned char, unsigned short, unsigned int, unsigned long,24 unsigned long long, UInt<128>>;25 26#ifdef FAKE_MACRO_DISABLE27TYPED_TEST(LlvmLibcBitTest, HasSingleBit, UnsignedTypes) {28 constexpr auto ZERO = T(0);29 constexpr auto ALL_ONES = T(~ZERO);30 EXPECT_FALSE(has_single_bit<T>(ZERO));31 EXPECT_FALSE(has_single_bit<T>(ALL_ONES));32 33 for (T value = 1; value; value <<= 1)34 EXPECT_TRUE(has_single_bit<T>(value));35 36 // We test that if two bits are set has_single_bit returns false.37 // We do this by setting the highest or lowest bit depending or where the38 // current bit is. This is a bit convoluted but it helps catch a bug on BigInt39 // where we have to work on an element-by-element basis.40 constexpr auto MIDPOINT = T(ALL_ONES / 2);41 constexpr auto LSB = T(1);42 constexpr auto MSB = T(~(ALL_ONES >> 1));43 for (T value = 1; value; value <<= 1) {44 T two_bits_value =45 static_cast<T>(value | ((value <= MIDPOINT) ? MSB : LSB));46 EXPECT_FALSE(has_single_bit<T>(two_bits_value));47 }48}49#endif50 51TYPED_TEST(LlvmLibcBitTest, CountLZero, UnsignedTypes) {52 EXPECT_EQ(countl_zero<T>(T(0)), cpp::numeric_limits<T>::digits);53 int expected = 0;54 for (T value = T(~0); value; value >>= 1, ++expected)55 EXPECT_EQ(countl_zero<T>(value), expected);56}57 58TYPED_TEST(LlvmLibcBitTest, CountRZero, UnsignedTypes) {59 EXPECT_EQ(countr_zero<T>(T(0)), cpp::numeric_limits<T>::digits);60 int expected = 0;61 for (T value = T(~0); value; value <<= 1, ++expected)62 EXPECT_EQ(countr_zero<T>(value), expected);63}64 65TYPED_TEST(LlvmLibcBitTest, CountLOne, UnsignedTypes) {66 EXPECT_EQ(countl_one<T>(T(0)), 0);67 int expected = cpp::numeric_limits<T>::digits;68 for (T value = T(~0); value; value <<= 1, --expected)69 EXPECT_EQ(countl_one<T>(value), expected);70}71 72TYPED_TEST(LlvmLibcBitTest, CountROne, UnsignedTypes) {73 EXPECT_EQ(countr_one<T>(T(0)), 0);74 int expected = cpp::numeric_limits<T>::digits;75 for (T value = T(~0); value; value >>= 1, --expected)76 EXPECT_EQ(countr_one<T>(value), expected);77}78 79TYPED_TEST(LlvmLibcBitTest, BitWidth, UnsignedTypes) {80 EXPECT_EQ(bit_width<T>(T(0)), 0);81 int one_index = 0;82 for (T value = 1; value; value <<= 1, ++one_index)83 EXPECT_EQ(bit_width<T>(value), one_index + 1);84}85 86TEST(LlvmLibcBitTest, BitCeil) {87 EXPECT_EQ(uint8_t(1), bit_ceil(uint8_t(0)));88 EXPECT_EQ(uint16_t(1), bit_ceil(uint16_t(0)));89 EXPECT_EQ(uint32_t(1), bit_ceil(uint32_t(0)));90 EXPECT_EQ(uint64_t(1), bit_ceil(uint64_t(0)));91 92 EXPECT_EQ(uint8_t(1), bit_ceil(uint8_t(1)));93 EXPECT_EQ(uint16_t(1), bit_ceil(uint16_t(1)));94 EXPECT_EQ(uint32_t(1), bit_ceil(uint32_t(1)));95 EXPECT_EQ(uint64_t(1), bit_ceil(uint64_t(1)));96 97 EXPECT_EQ(uint8_t(2), bit_ceil(uint8_t(2)));98 EXPECT_EQ(uint16_t(2), bit_ceil(uint16_t(2)));99 EXPECT_EQ(uint32_t(2), bit_ceil(uint32_t(2)));100 EXPECT_EQ(uint64_t(2), bit_ceil(uint64_t(2)));101 102 EXPECT_EQ(uint8_t(4), bit_ceil(uint8_t(3)));103 EXPECT_EQ(uint16_t(4), bit_ceil(uint16_t(3)));104 EXPECT_EQ(uint32_t(4), bit_ceil(uint32_t(3)));105 EXPECT_EQ(uint64_t(4), bit_ceil(uint64_t(3)));106 107 EXPECT_EQ(uint8_t(4), bit_ceil(uint8_t(4)));108 EXPECT_EQ(uint16_t(4), bit_ceil(uint16_t(4)));109 EXPECT_EQ(uint32_t(4), bit_ceil(uint32_t(4)));110 EXPECT_EQ(uint64_t(4), bit_ceil(uint64_t(4)));111 112 // The result is the representable power of 2 for each type.113 EXPECT_EQ(uint8_t(0x80), bit_ceil(uint8_t(0x7f)));114 EXPECT_EQ(uint16_t(0x8000), bit_ceil(uint16_t(0x7fff)));115 EXPECT_EQ(uint32_t(0x80000000), bit_ceil(uint32_t(0x7fffffff)));116 EXPECT_EQ(uint64_t(0x8000000000000000),117 bit_ceil(uint64_t(0x7fffffffffffffff)));118}119 120TEST(LlvmLibcBitTest, BitFloor) {121 EXPECT_EQ(uint8_t(0), bit_floor(uint8_t(0)));122 EXPECT_EQ(uint16_t(0), bit_floor(uint16_t(0)));123 EXPECT_EQ(uint32_t(0), bit_floor(uint32_t(0)));124 EXPECT_EQ(uint64_t(0), bit_floor(uint64_t(0)));125 126 EXPECT_EQ(uint8_t(1), bit_floor(uint8_t(1)));127 EXPECT_EQ(uint16_t(1), bit_floor(uint16_t(1)));128 EXPECT_EQ(uint32_t(1), bit_floor(uint32_t(1)));129 EXPECT_EQ(uint64_t(1), bit_floor(uint64_t(1)));130 131 EXPECT_EQ(uint8_t(2), bit_floor(uint8_t(2)));132 EXPECT_EQ(uint16_t(2), bit_floor(uint16_t(2)));133 EXPECT_EQ(uint32_t(2), bit_floor(uint32_t(2)));134 EXPECT_EQ(uint64_t(2), bit_floor(uint64_t(2)));135 136 EXPECT_EQ(uint8_t(2), bit_floor(uint8_t(3)));137 EXPECT_EQ(uint16_t(2), bit_floor(uint16_t(3)));138 EXPECT_EQ(uint32_t(2), bit_floor(uint32_t(3)));139 EXPECT_EQ(uint64_t(2), bit_floor(uint64_t(3)));140 141 EXPECT_EQ(uint8_t(4), bit_floor(uint8_t(4)));142 EXPECT_EQ(uint16_t(4), bit_floor(uint16_t(4)));143 EXPECT_EQ(uint32_t(4), bit_floor(uint32_t(4)));144 EXPECT_EQ(uint64_t(4), bit_floor(uint64_t(4)));145 146 EXPECT_EQ(uint8_t(0x40), bit_floor(uint8_t(0x7f)));147 EXPECT_EQ(uint16_t(0x4000), bit_floor(uint16_t(0x7fff)));148 EXPECT_EQ(uint32_t(0x40000000), bit_floor(uint32_t(0x7fffffff)));149 EXPECT_EQ(uint64_t(0x4000000000000000),150 bit_floor(uint64_t(0x7fffffffffffffffull)));151 152 EXPECT_EQ(uint8_t(0x80), bit_floor(uint8_t(0x80)));153 EXPECT_EQ(uint16_t(0x8000), bit_floor(uint16_t(0x8000)));154 EXPECT_EQ(uint32_t(0x80000000), bit_floor(uint32_t(0x80000000)));155 EXPECT_EQ(uint64_t(0x8000000000000000),156 bit_floor(uint64_t(0x8000000000000000)));157 158 EXPECT_EQ(uint8_t(0x80), bit_floor(uint8_t(0xff)));159 EXPECT_EQ(uint16_t(0x8000), bit_floor(uint16_t(0xffff)));160 EXPECT_EQ(uint32_t(0x80000000), bit_floor(uint32_t(0xffffffff)));161 EXPECT_EQ(uint64_t(0x8000000000000000),162 bit_floor(uint64_t(0xffffffffffffffff)));163}164 165TYPED_TEST(LlvmLibcBitTest, RotateIsInvariantForZeroAndOne, UnsignedTypes) {166 constexpr T all_zeros = T(0);167 constexpr T all_ones = T(~0);168 for (int i = 0; i < cpp::numeric_limits<T>::digits; ++i) {169 EXPECT_EQ(rotl<T>(all_zeros, i), all_zeros);170 EXPECT_EQ(rotl<T>(all_ones, i), all_ones);171 EXPECT_EQ(rotr<T>(all_zeros, i), all_zeros);172 EXPECT_EQ(rotr<T>(all_ones, i), all_ones);173 }174}175 176TEST(LlvmLibcBitTest, Rotl) {177 EXPECT_EQ(uint8_t(0x53U), rotl<uint8_t>(0x53, 0));178 EXPECT_EQ(uint8_t(0x4dU), rotl<uint8_t>(0x53, 2));179 EXPECT_EQ(uint8_t(0xa6U), rotl<uint8_t>(0x53, 9));180 EXPECT_EQ(uint8_t(0x9aU), rotl<uint8_t>(0x53, -5));181 182 EXPECT_EQ(uint16_t(0xabcdU), rotl<uint16_t>(0xabcd, 0));183 EXPECT_EQ(uint16_t(0xf36aU), rotl<uint16_t>(0xabcd, 6));184 EXPECT_EQ(uint16_t(0xaf36U), rotl<uint16_t>(0xabcd, 18));185 EXPECT_EQ(uint16_t(0xf36aU), rotl<uint16_t>(0xabcd, -10));186 187 EXPECT_EQ(uint32_t(0xdeadbeefU), rotl<uint32_t>(0xdeadbeef, 0));188 EXPECT_EQ(uint32_t(0x7ddfbd5bU), rotl<uint32_t>(0xdeadbeef, 17));189 EXPECT_EQ(uint32_t(0x5b7ddfbdU), rotl<uint32_t>(0xdeadbeef, 41));190 EXPECT_EQ(uint32_t(0xb6fbbf7aU), rotl<uint32_t>(0xdeadbeef, -22));191 192 EXPECT_EQ(uint64_t(0x12345678deadbeefULL),193 rotl<uint64_t>(0x12345678deadbeefULL, 0));194 EXPECT_EQ(uint64_t(0xf56df77891a2b3c6ULL),195 rotl<uint64_t>(0x12345678deadbeefULL, 35));196 EXPECT_EQ(uint64_t(0x8d159e37ab6fbbc4ULL),197 rotl<uint64_t>(0x12345678deadbeefULL, 70));198 EXPECT_EQ(uint64_t(0xb7dde2468acf1bd5ULL),199 rotl<uint64_t>(0x12345678deadbeefULL, -19));200}201 202TEST(LlvmLibcBitTest, Rotr) {203 EXPECT_EQ(uint8_t(0x53U), rotr<uint8_t>(0x53, 0));204 EXPECT_EQ(uint8_t(0xd4U), rotr<uint8_t>(0x53, 2));205 EXPECT_EQ(uint8_t(0xa9U), rotr<uint8_t>(0x53, 9));206 EXPECT_EQ(uint8_t(0x6aU), rotr<uint8_t>(0x53, -5));207 208 EXPECT_EQ(uint16_t(0xabcdU), rotr<uint16_t>(0xabcd, 0));209 EXPECT_EQ(uint16_t(0x36afU), rotr<uint16_t>(0xabcd, 6));210 EXPECT_EQ(uint16_t(0x6af3U), rotr<uint16_t>(0xabcd, 18));211 EXPECT_EQ(uint16_t(0x36afU), rotr<uint16_t>(0xabcd, -10));212 213 EXPECT_EQ(uint32_t(0xdeadbeefU), rotr<uint32_t>(0xdeadbeef, 0));214 EXPECT_EQ(uint32_t(0xdf77ef56U), rotr<uint32_t>(0xdeadbeef, 17));215 EXPECT_EQ(uint32_t(0x77ef56dfU), rotr<uint32_t>(0xdeadbeef, 41));216 EXPECT_EQ(uint32_t(0xbbf7ab6fU), rotr<uint32_t>(0xdeadbeef, -22));217 218 EXPECT_EQ(uint64_t(0x12345678deadbeefULL),219 rotr<uint64_t>(0x12345678deadbeefULL, 0));220 EXPECT_EQ(uint64_t(0x1bd5b7dde2468acfULL),221 rotr<uint64_t>(0x12345678deadbeefULL, 35));222 EXPECT_EQ(uint64_t(0xbc48d159e37ab6fbULL),223 rotr<uint64_t>(0x12345678deadbeefULL, 70));224 EXPECT_EQ(uint64_t(0xb3c6f56df77891a2ULL),225 rotr<uint64_t>(0x12345678deadbeefULL, -19));226}227 228TYPED_TEST(LlvmLibcBitTest, CountOnes, UnsignedTypes) {229 EXPECT_EQ(popcount(T(0)), 0);230 for (int i = 0; i != cpp::numeric_limits<T>::digits; ++i)231 EXPECT_EQ(232 popcount<T>(cpp::numeric_limits<T>::max() >> static_cast<size_t>(i)),233 cpp::numeric_limits<T>::digits - i);234}235 236} // namespace cpp237} // namespace LIBC_NAMESPACE_DECL238