src/v8/src/base/division-by-constant-unittest.cc

   1 // Copyright 2014 the V8 project 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
   5 // Check all examples from table 10-1 of "Hacker's Delight".
   6
   7 #include "src/base/division-by-constant.h"
   8
   9 #include <ostream>  // NOLINT
  10
  11 #include "testing/gtest-support.h"
  12
  13 namespace v8 {
  14 namespace base {
  15
  16 template <class T>
  17 std::ostream& operator<<(std::ostream& os,
  18                          const MagicNumbersForDivision<T>& mag) {
  19   return os << "{ multiplier: " << mag.multiplier << ", shift: " << mag.shift
  20             << ", add: " << mag.add << " }";
  21 }
  22
  23
  24 // Some abbreviations...
  25
  26 typedef MagicNumbersForDivision<uint32_t> M32;
  27 typedef MagicNumbersForDivision<uint64_t> M64;
  28
  29
  30 static M32 s32(int32_t d) {
  31   return SignedDivisionByConstant<uint32_t>(static_cast<uint32_t>(d));
  32 }
  33
  34
  35 static M64 s64(int64_t d) {
  36   return SignedDivisionByConstant<uint64_t>(static_cast<uint64_t>(d));
  37 }
  38
  39
  40 static M32 u32(uint32_t d) { return UnsignedDivisionByConstant<uint32_t>(d); }
  41 static M64 u64(uint64_t d) { return UnsignedDivisionByConstant<uint64_t>(d); }
  42
  43
  44 TEST(DivisionByConstant, Signed32) {
  45   EXPECT_EQ(M32(0x99999999U, 1, false), s32(-5));
  46   EXPECT_EQ(M32(0x55555555U, 1, false), s32(-3));
  47   int32_t d = -1;
  48   for (unsigned k = 1; k <= 32 - 1; ++k) {
  49     d *= 2;
  50     EXPECT_EQ(M32(0x7FFFFFFFU, k - 1, false), s32(d));
  51   }
  52   for (unsigned k = 1; k <= 32 - 2; ++k) {
  53     EXPECT_EQ(M32(0x80000001U, k - 1, false), s32(1 << k));
  54   }
  55   EXPECT_EQ(M32(0x55555556U, 0, false), s32(3));
  56   EXPECT_EQ(M32(0x66666667U, 1, false), s32(5));
  57   EXPECT_EQ(M32(0x2AAAAAABU, 0, false), s32(6));
  58   EXPECT_EQ(M32(0x92492493U, 2, false), s32(7));
  59   EXPECT_EQ(M32(0x38E38E39U, 1, false), s32(9));
  60   EXPECT_EQ(M32(0x66666667U, 2, false), s32(10));
  61   EXPECT_EQ(M32(0x2E8BA2E9U, 1, false), s32(11));
  62   EXPECT_EQ(M32(0x2AAAAAABU, 1, false), s32(12));
  63   EXPECT_EQ(M32(0x51EB851FU, 3, false), s32(25));
  64   EXPECT_EQ(M32(0x10624DD3U, 3, false), s32(125));
  65   EXPECT_EQ(M32(0x68DB8BADU, 8, false), s32(625));
  66 }
  67
  68
  69 TEST(DivisionByConstant, Unsigned32) {
  70   EXPECT_EQ(M32(0x00000000U, 0, true), u32(1));
  71   for (unsigned k = 1; k <= 30; ++k) {
  72     EXPECT_EQ(M32(1U << (32 - k), 0, false), u32(1U << k));
  73   }
  74   EXPECT_EQ(M32(0xAAAAAAABU, 1, false), u32(3));
  75   EXPECT_EQ(M32(0xCCCCCCCDU, 2, false), u32(5));
  76   EXPECT_EQ(M32(0xAAAAAAABU, 2, false), u32(6));
  77   EXPECT_EQ(M32(0x24924925U, 3, true), u32(7));
  78   EXPECT_EQ(M32(0x38E38E39U, 1, false), u32(9));
  79   EXPECT_EQ(M32(0xCCCCCCCDU, 3, false), u32(10));
  80   EXPECT_EQ(M32(0xBA2E8BA3U, 3, false), u32(11));
  81   EXPECT_EQ(M32(0xAAAAAAABU, 3, false), u32(12));
  82   EXPECT_EQ(M32(0x51EB851FU, 3, false), u32(25));
  83   EXPECT_EQ(M32(0x10624DD3U, 3, false), u32(125));
  84   EXPECT_EQ(M32(0xD1B71759U, 9, false), u32(625));
  85 }
  86
  87
  88 TEST(DivisionByConstant, Signed64) {
  89   EXPECT_EQ(M64(0x9999999999999999ULL, 1, false), s64(-5));
  90   EXPECT_EQ(M64(0x5555555555555555ULL, 1, false), s64(-3));
  91   int64_t d = -1;
  92   for (unsigned k = 1; k <= 64 - 1; ++k) {
  93     d *= 2;
  94     EXPECT_EQ(M64(0x7FFFFFFFFFFFFFFFULL, k - 1, false), s64(d));
  95   }
  96   for (unsigned k = 1; k <= 64 - 2; ++k) {
  97     EXPECT_EQ(M64(0x8000000000000001ULL, k - 1, false), s64(1LL << k));
  98   }
  99   EXPECT_EQ(M64(0x5555555555555556ULL, 0, false), s64(3));
 100   EXPECT_EQ(M64(0x6666666666666667ULL, 1, false), s64(5));
 101   EXPECT_EQ(M64(0x2AAAAAAAAAAAAAABULL, 0, false), s64(6));
 102   EXPECT_EQ(M64(0x4924924924924925ULL, 1, false), s64(7));
 103   EXPECT_EQ(M64(0x1C71C71C71C71C72ULL, 0, false), s64(9));
 104   EXPECT_EQ(M64(0x6666666666666667ULL, 2, false), s64(10));
 105   EXPECT_EQ(M64(0x2E8BA2E8BA2E8BA3ULL, 1, false), s64(11));
 106   EXPECT_EQ(M64(0x2AAAAAAAAAAAAAABULL, 1, false), s64(12));
 107   EXPECT_EQ(M64(0xA3D70A3D70A3D70BULL, 4, false), s64(25));
 108   EXPECT_EQ(M64(0x20C49BA5E353F7CFULL, 4, false), s64(125));
 109   EXPECT_EQ(M64(0x346DC5D63886594BULL, 7, false), s64(625));
 110 }
 111
 112
 113 TEST(DivisionByConstant, Unsigned64) {
 114   EXPECT_EQ(M64(0x0000000000000000ULL, 0, true), u64(1));
 115   for (unsigned k = 1; k <= 64 - 2; ++k) {
 116     EXPECT_EQ(M64(1ULL << (64 - k), 0, false), u64(1ULL << k));
 117   }
 118   EXPECT_EQ(M64(0xAAAAAAAAAAAAAAABULL, 1, false), u64(3));
 119   EXPECT_EQ(M64(0xCCCCCCCCCCCCCCCDULL, 2, false), u64(5));
 120   EXPECT_EQ(M64(0xAAAAAAAAAAAAAAABULL, 2, false), u64(6));
 121   EXPECT_EQ(M64(0x2492492492492493ULL, 3, true), u64(7));
 122   EXPECT_EQ(M64(0xE38E38E38E38E38FULL, 3, false), u64(9));
 123   EXPECT_EQ(M64(0xCCCCCCCCCCCCCCCDULL, 3, false), u64(10));
 124   EXPECT_EQ(M64(0x2E8BA2E8BA2E8BA3ULL, 1, false), u64(11));
 125   EXPECT_EQ(M64(0xAAAAAAAAAAAAAAABULL, 3, false), u64(12));
 126   EXPECT_EQ(M64(0x47AE147AE147AE15ULL, 5, true), u64(25));
 127   EXPECT_EQ(M64(0x0624DD2F1A9FBE77ULL, 7, true), u64(125));
 128   EXPECT_EQ(M64(0x346DC5D63886594BULL, 7, false), u64(625));
 129 }
 130
 131 }  // namespace base
 132 }  // namespace v8