bits_unittest.cc 10 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277
  1. // Copyright (c) 2009 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. // This file contains the unit tests for the bit utilities.
  5. #include "base/bits.h"
  6. #include "build/build_config.h"
  7. #include <stddef.h>
  8. #include <limits>
  9. #include "testing/gtest/include/gtest/gtest.h"
  10. namespace base {
  11. namespace bits {
  12. TEST(BitsTest, Log2Floor) {
  13. EXPECT_EQ(-1, Log2Floor(0));
  14. EXPECT_EQ(0, Log2Floor(1));
  15. EXPECT_EQ(1, Log2Floor(2));
  16. EXPECT_EQ(1, Log2Floor(3));
  17. EXPECT_EQ(2, Log2Floor(4));
  18. for (int i = 3; i < 31; ++i) {
  19. unsigned int value = 1U << i;
  20. EXPECT_EQ(i, Log2Floor(value));
  21. EXPECT_EQ(i, Log2Floor(value + 1));
  22. EXPECT_EQ(i, Log2Floor(value + 2));
  23. EXPECT_EQ(i - 1, Log2Floor(value - 1));
  24. EXPECT_EQ(i - 1, Log2Floor(value - 2));
  25. }
  26. EXPECT_EQ(31, Log2Floor(0xffffffffU));
  27. }
  28. TEST(BitsTest, Log2Ceiling) {
  29. EXPECT_EQ(-1, Log2Ceiling(0));
  30. EXPECT_EQ(0, Log2Ceiling(1));
  31. EXPECT_EQ(1, Log2Ceiling(2));
  32. EXPECT_EQ(2, Log2Ceiling(3));
  33. EXPECT_EQ(2, Log2Ceiling(4));
  34. for (int i = 3; i < 31; ++i) {
  35. unsigned int value = 1U << i;
  36. EXPECT_EQ(i, Log2Ceiling(value));
  37. EXPECT_EQ(i + 1, Log2Ceiling(value + 1));
  38. EXPECT_EQ(i + 1, Log2Ceiling(value + 2));
  39. EXPECT_EQ(i, Log2Ceiling(value - 1));
  40. EXPECT_EQ(i, Log2Ceiling(value - 2));
  41. }
  42. EXPECT_EQ(32, Log2Ceiling(0xffffffffU));
  43. }
  44. TEST(BitsTest, AlignUp) {
  45. static constexpr size_t kSizeTMax = std::numeric_limits<size_t>::max();
  46. EXPECT_EQ(0, AlignUp(0, 4));
  47. EXPECT_EQ(4, AlignUp(1, 4));
  48. EXPECT_EQ(4096, AlignUp(1, 4096));
  49. EXPECT_EQ(4096, AlignUp(4096, 4096));
  50. EXPECT_EQ(4096, AlignUp(4095, 4096));
  51. EXPECT_EQ(8192, AlignUp(4097, 4096));
  52. EXPECT_EQ(kSizeTMax - 31, AlignUp(kSizeTMax - 62, size_t{32}));
  53. EXPECT_EQ(kSizeTMax / 2 + 1, AlignUp(size_t{1}, kSizeTMax / 2 + 1));
  54. }
  55. TEST(BitsTest, AlignUpPointer) {
  56. static constexpr uintptr_t kUintPtrTMax =
  57. std::numeric_limits<uintptr_t>::max();
  58. EXPECT_EQ(reinterpret_cast<uint8_t*>(0),
  59. AlignUp(reinterpret_cast<uint8_t*>(0), 4));
  60. EXPECT_EQ(reinterpret_cast<uint8_t*>(4),
  61. AlignUp(reinterpret_cast<uint8_t*>(1), 4));
  62. EXPECT_EQ(reinterpret_cast<uint8_t*>(4096),
  63. AlignUp(reinterpret_cast<uint8_t*>(1), 4096));
  64. EXPECT_EQ(reinterpret_cast<uint8_t*>(4096),
  65. AlignUp(reinterpret_cast<uint8_t*>(4096), 4096));
  66. EXPECT_EQ(reinterpret_cast<uint8_t*>(4096),
  67. AlignUp(reinterpret_cast<uint8_t*>(4095), 4096));
  68. EXPECT_EQ(reinterpret_cast<uint8_t*>(8192),
  69. AlignUp(reinterpret_cast<uint8_t*>(4097), 4096));
  70. EXPECT_EQ(reinterpret_cast<uint8_t*>(kUintPtrTMax - 31),
  71. AlignUp(reinterpret_cast<uint8_t*>(kUintPtrTMax - 62), 32));
  72. EXPECT_EQ(reinterpret_cast<uint8_t*>(kUintPtrTMax / 2 + 1),
  73. AlignUp(reinterpret_cast<uint8_t*>(1), kUintPtrTMax / 2 + 1));
  74. }
  75. TEST(BitsTest, AlignDown) {
  76. static constexpr size_t kSizeTMax = std::numeric_limits<size_t>::max();
  77. EXPECT_EQ(0, AlignDown(0, 4));
  78. EXPECT_EQ(0, AlignDown(1, 4));
  79. EXPECT_EQ(0, AlignDown(1, 4096));
  80. EXPECT_EQ(4096, AlignDown(4096, 4096));
  81. EXPECT_EQ(0, AlignDown(4095, 4096));
  82. EXPECT_EQ(4096, AlignDown(4097, 4096));
  83. EXPECT_EQ(kSizeTMax - 63, AlignDown(kSizeTMax - 62, size_t{32}));
  84. EXPECT_EQ(kSizeTMax - 31, AlignDown(kSizeTMax, size_t{32}));
  85. EXPECT_EQ(0ul, AlignDown(size_t{1}, kSizeTMax / 2 + 1));
  86. }
  87. TEST(BitsTest, AlignDownPointer) {
  88. static constexpr uintptr_t kUintPtrTMax =
  89. std::numeric_limits<uintptr_t>::max();
  90. EXPECT_EQ(reinterpret_cast<uint8_t*>(0),
  91. AlignDown(reinterpret_cast<uint8_t*>(0), 4));
  92. EXPECT_EQ(reinterpret_cast<uint8_t*>(0),
  93. AlignDown(reinterpret_cast<uint8_t*>(1), 4));
  94. EXPECT_EQ(reinterpret_cast<uint8_t*>(0),
  95. AlignDown(reinterpret_cast<uint8_t*>(1), 4096));
  96. EXPECT_EQ(reinterpret_cast<uint8_t*>(4096),
  97. AlignDown(reinterpret_cast<uint8_t*>(4096), 4096));
  98. EXPECT_EQ(reinterpret_cast<uint8_t*>(0),
  99. AlignDown(reinterpret_cast<uint8_t*>(4095), 4096));
  100. EXPECT_EQ(reinterpret_cast<uint8_t*>(4096),
  101. AlignDown(reinterpret_cast<uint8_t*>(4097), 4096));
  102. EXPECT_EQ(reinterpret_cast<uint8_t*>(kUintPtrTMax - 63),
  103. AlignDown(reinterpret_cast<uint8_t*>(kUintPtrTMax - 62), 32));
  104. EXPECT_EQ(reinterpret_cast<uint8_t*>(kUintPtrTMax - 31),
  105. AlignDown(reinterpret_cast<uint8_t*>(kUintPtrTMax), 32));
  106. EXPECT_EQ(reinterpret_cast<uint8_t*>(0),
  107. AlignDown(reinterpret_cast<uint8_t*>(1), kUintPtrTMax / 2 + 1));
  108. }
  109. TEST(BitsTest, CountLeadingZeroBits8) {
  110. EXPECT_EQ(8, CountLeadingZeroBits(uint8_t{0}));
  111. EXPECT_EQ(7, CountLeadingZeroBits(uint8_t{1}));
  112. for (int shift = 0; shift <= 7; ++shift) {
  113. EXPECT_EQ(7 - shift,
  114. CountLeadingZeroBits(static_cast<uint8_t>(1 << shift)));
  115. }
  116. EXPECT_EQ(4, CountLeadingZeroBits(uint8_t{0x0f}));
  117. }
  118. TEST(BitsTest, CountLeadingZeroBits16) {
  119. EXPECT_EQ(16, CountLeadingZeroBits(uint16_t{0}));
  120. EXPECT_EQ(15, CountLeadingZeroBits(uint16_t{1}));
  121. for (int shift = 0; shift <= 15; ++shift) {
  122. EXPECT_EQ(15 - shift,
  123. CountLeadingZeroBits(static_cast<uint16_t>(1 << shift)));
  124. }
  125. EXPECT_EQ(4, CountLeadingZeroBits(uint16_t{0x0f0f}));
  126. }
  127. TEST(BitsTest, CountLeadingZeroBits32) {
  128. EXPECT_EQ(32, CountLeadingZeroBits(uint32_t{0}));
  129. EXPECT_EQ(31, CountLeadingZeroBits(uint32_t{1}));
  130. for (int shift = 0; shift <= 31; ++shift) {
  131. EXPECT_EQ(31 - shift, CountLeadingZeroBits(uint32_t{1} << shift));
  132. }
  133. EXPECT_EQ(4, CountLeadingZeroBits(uint32_t{0x0f0f0f0f}));
  134. }
  135. TEST(BitsTest, CountTrailingZeroBits8) {
  136. EXPECT_EQ(8, CountTrailingZeroBits(uint8_t{0}));
  137. EXPECT_EQ(7, CountTrailingZeroBits(uint8_t{128}));
  138. for (int shift = 0; shift <= 7; ++shift) {
  139. EXPECT_EQ(shift, CountTrailingZeroBits(static_cast<uint8_t>(1 << shift)));
  140. }
  141. EXPECT_EQ(4, CountTrailingZeroBits(uint8_t{0xf0}));
  142. }
  143. TEST(BitsTest, CountTrailingZeroBits16) {
  144. EXPECT_EQ(16, CountTrailingZeroBits(uint16_t{0}));
  145. EXPECT_EQ(15, CountTrailingZeroBits(uint16_t{32768}));
  146. for (int shift = 0; shift <= 15; ++shift) {
  147. EXPECT_EQ(shift, CountTrailingZeroBits(static_cast<uint16_t>(1 << shift)));
  148. }
  149. EXPECT_EQ(4, CountTrailingZeroBits(uint16_t{0xf0f0}));
  150. }
  151. TEST(BitsTest, CountTrailingZeroBits32) {
  152. EXPECT_EQ(32, CountTrailingZeroBits(uint32_t{0}));
  153. EXPECT_EQ(31, CountTrailingZeroBits(uint32_t{1} << 31));
  154. for (int shift = 0; shift <= 31; ++shift) {
  155. EXPECT_EQ(shift, CountTrailingZeroBits(uint32_t{1} << shift));
  156. }
  157. EXPECT_EQ(4, CountTrailingZeroBits(uint32_t{0xf0f0f0f0}));
  158. }
  159. TEST(BitsTest, CountLeadingZeroBits64) {
  160. EXPECT_EQ(64, CountLeadingZeroBits(uint64_t{0}));
  161. EXPECT_EQ(63, CountLeadingZeroBits(uint64_t{1}));
  162. for (int shift = 0; shift <= 63; ++shift) {
  163. EXPECT_EQ(63 - shift, CountLeadingZeroBits(uint64_t{1} << shift));
  164. }
  165. EXPECT_EQ(4, CountLeadingZeroBits(uint64_t{0x0f0f0f0f0f0f0f0f}));
  166. }
  167. TEST(BitsTest, CountTrailingZeroBits64) {
  168. EXPECT_EQ(64, CountTrailingZeroBits(uint64_t{0}));
  169. EXPECT_EQ(63, CountTrailingZeroBits(uint64_t{1} << 63));
  170. for (int shift = 0; shift <= 31; ++shift) {
  171. EXPECT_EQ(shift, CountTrailingZeroBits(uint64_t{1} << shift));
  172. }
  173. EXPECT_EQ(4, CountTrailingZeroBits(uint64_t{0xf0f0f0f0f0f0f0f0}));
  174. }
  175. TEST(BitsTest, CountLeadingZeroBitsSizeT) {
  176. #if defined(ARCH_CPU_64_BITS)
  177. EXPECT_EQ(64, CountLeadingZeroBits(size_t{0}));
  178. EXPECT_EQ(63, CountLeadingZeroBits(size_t{1}));
  179. EXPECT_EQ(32, CountLeadingZeroBits(size_t{1} << 31));
  180. EXPECT_EQ(1, CountLeadingZeroBits(size_t{1} << 62));
  181. EXPECT_EQ(0, CountLeadingZeroBits(size_t{1} << 63));
  182. #else
  183. EXPECT_EQ(32, CountLeadingZeroBits(size_t{0}));
  184. EXPECT_EQ(31, CountLeadingZeroBits(size_t{1}));
  185. EXPECT_EQ(1, CountLeadingZeroBits(size_t{1} << 30));
  186. EXPECT_EQ(0, CountLeadingZeroBits(size_t{1} << 31));
  187. #endif // ARCH_CPU_64_BITS
  188. }
  189. TEST(BitsTest, CountTrailingZeroBitsSizeT) {
  190. #if defined(ARCH_CPU_64_BITS)
  191. EXPECT_EQ(64, CountTrailingZeroBits(size_t{0}));
  192. EXPECT_EQ(63, CountTrailingZeroBits(size_t{1} << 63));
  193. EXPECT_EQ(31, CountTrailingZeroBits(size_t{1} << 31));
  194. EXPECT_EQ(1, CountTrailingZeroBits(size_t{2}));
  195. EXPECT_EQ(0, CountTrailingZeroBits(size_t{1}));
  196. #else
  197. EXPECT_EQ(32, CountTrailingZeroBits(size_t{0}));
  198. EXPECT_EQ(31, CountTrailingZeroBits(size_t{1} << 31));
  199. EXPECT_EQ(1, CountTrailingZeroBits(size_t{2}));
  200. EXPECT_EQ(0, CountTrailingZeroBits(size_t{1}));
  201. #endif // ARCH_CPU_64_BITS
  202. }
  203. TEST(BitsTest, PowerOfTwo) {
  204. EXPECT_FALSE(IsPowerOfTwo(-1));
  205. EXPECT_FALSE(IsPowerOfTwo(0));
  206. EXPECT_TRUE(IsPowerOfTwo(1));
  207. EXPECT_TRUE(IsPowerOfTwo(2));
  208. // Unsigned 64 bit cases.
  209. for (uint32_t i = 2; i < 64; i++) {
  210. const uint64_t val = uint64_t{1} << i;
  211. EXPECT_FALSE(IsPowerOfTwo(val - 1));
  212. EXPECT_TRUE(IsPowerOfTwo(val));
  213. EXPECT_FALSE(IsPowerOfTwo(val + 1));
  214. }
  215. // Signed 64 bit cases.
  216. for (uint32_t i = 2; i < 63; i++) {
  217. const int64_t val = int64_t{1} << i;
  218. EXPECT_FALSE(IsPowerOfTwo(val - 1));
  219. EXPECT_TRUE(IsPowerOfTwo(val));
  220. EXPECT_FALSE(IsPowerOfTwo(val + 1));
  221. }
  222. // Signed integers with only the last bit set are negative, not powers of two.
  223. EXPECT_FALSE(IsPowerOfTwo(int64_t{1} << 63));
  224. }
  225. TEST(BitsTest, LeftMostBit) {
  226. // Construction of a signed type from an unsigned one of the same width
  227. // preserves all bits. Explicitily confirming this behavior here to illustrate
  228. // correctness of reusing unsigned literals to test behavior of signed types.
  229. // Using signed literals does not work with EXPECT_EQ.
  230. static_assert(int64_t(0xFFFFFFFFFFFFFFFFu) == 0xFFFFFFFFFFFFFFFFl,
  231. "Comparing signed with unsigned literals compares bits.");
  232. static_assert((0xFFFFFFFFFFFFFFFFu ^ 0xFFFFFFFFFFFFFFFFl) == 0,
  233. "Signed and unsigned literals have the same bits set");
  234. uint64_t unsigned_long_long_value = 0x8000000000000000u;
  235. EXPECT_EQ(LeftmostBit<uint64_t>(), unsigned_long_long_value);
  236. EXPECT_EQ(LeftmostBit<int64_t>(), int64_t(unsigned_long_long_value));
  237. uint32_t unsigned_long_value = 0x80000000u;
  238. EXPECT_EQ(LeftmostBit<uint32_t>(), unsigned_long_value);
  239. EXPECT_EQ(LeftmostBit<int32_t>(), int32_t(unsigned_long_value));
  240. uint16_t unsigned_short_value = 0x8000u;
  241. EXPECT_EQ(LeftmostBit<uint16_t>(), unsigned_short_value);
  242. EXPECT_EQ(LeftmostBit<int16_t>(), int16_t(unsigned_short_value));
  243. uint8_t unsigned_byte_value = 0x80u;
  244. EXPECT_EQ(LeftmostBit<uint8_t>(), unsigned_byte_value);
  245. EXPECT_EQ(LeftmostBit<int8_t>(), int8_t(unsigned_byte_value));
  246. }
  247. } // namespace bits
  248. } // namespace base