| 1 |
//===- unittest/Support/BranchProbabilityTest.cpp - BranchProbability tests -=// |
| 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-exception |
| 6 |
// |
| 7 |
//===----------------------------------------------------------------------===// |
| 8 |
|
| 9 |
#include "llvm/Support/BranchProbability.h" |
| 10 |
#include "llvm/Support/raw_ostream.h" |
| 11 |
#include "gtest/gtest.h" |
| 12 |
|
| 13 |
using namespace llvm; |
| 14 |
|
| 15 |
namespace llvm { |
| 16 |
void PrintTo(BranchProbability P, ::std::ostream *os) { |
| 17 |
*os << P.getNumerator() << "/" << P.getDenominator(); |
| 18 |
} |
| 19 |
} |
| 20 |
namespace { |
| 21 |
|
| 22 |
typedef BranchProbability BP; |
| 23 |
TEST(BranchProbabilityTest, Accessors) { |
| 24 |
EXPECT_EQ(306783378u, BP(1, 7).getNumerator()); |
| 25 |
EXPECT_EQ(1u << 31, BP(1, 7).getDenominator()); |
| 26 |
EXPECT_EQ(0u, BP::getZero().getNumerator()); |
| 27 |
EXPECT_EQ(1u << 31, BP::getZero().getDenominator()); |
| 28 |
EXPECT_EQ(1u << 31, BP::getOne().getNumerator()); |
| 29 |
EXPECT_EQ(1u << 31, BP::getOne().getDenominator()); |
| 30 |
} |
| 31 |
|
| 32 |
TEST(BranchProbabilityTest, Operators) { |
| 33 |
EXPECT_TRUE(BP(1, 7) < BP(2, 7)); |
| 34 |
EXPECT_TRUE(BP(1, 7) < BP(1, 4)); |
| 35 |
EXPECT_TRUE(BP(5, 7) < BP(3, 4)); |
| 36 |
EXPECT_FALSE(BP(1, 7) < BP(1, 7)); |
| 37 |
EXPECT_FALSE(BP(1, 7) < BP(2, 14)); |
| 38 |
EXPECT_FALSE(BP(4, 7) < BP(1, 2)); |
| 39 |
EXPECT_FALSE(BP(4, 7) < BP(3, 7)); |
| 40 |
|
| 41 |
EXPECT_FALSE(BP(1, 7) > BP(2, 7)); |
| 42 |
EXPECT_FALSE(BP(1, 7) > BP(1, 4)); |
| 43 |
EXPECT_FALSE(BP(5, 7) > BP(3, 4)); |
| 44 |
EXPECT_FALSE(BP(1, 7) > BP(1, 7)); |
| 45 |
EXPECT_FALSE(BP(1, 7) > BP(2, 14)); |
| 46 |
EXPECT_TRUE(BP(4, 7) > BP(1, 2)); |
| 47 |
EXPECT_TRUE(BP(4, 7) > BP(3, 7)); |
| 48 |
|
| 49 |
EXPECT_TRUE(BP(1, 7) <= BP(2, 7)); |
| 50 |
EXPECT_TRUE(BP(1, 7) <= BP(1, 4)); |
| 51 |
EXPECT_TRUE(BP(5, 7) <= BP(3, 4)); |
| 52 |
EXPECT_TRUE(BP(1, 7) <= BP(1, 7)); |
| 53 |
EXPECT_TRUE(BP(1, 7) <= BP(2, 14)); |
| 54 |
EXPECT_FALSE(BP(4, 7) <= BP(1, 2)); |
| 55 |
EXPECT_FALSE(BP(4, 7) <= BP(3, 7)); |
| 56 |
|
| 57 |
EXPECT_FALSE(BP(1, 7) >= BP(2, 7)); |
| 58 |
EXPECT_FALSE(BP(1, 7) >= BP(1, 4)); |
| 59 |
EXPECT_FALSE(BP(5, 7) >= BP(3, 4)); |
| 60 |
EXPECT_TRUE(BP(1, 7) >= BP(1, 7)); |
| 61 |
EXPECT_TRUE(BP(1, 7) >= BP(2, 14)); |
| 62 |
EXPECT_TRUE(BP(4, 7) >= BP(1, 2)); |
| 63 |
EXPECT_TRUE(BP(4, 7) >= BP(3, 7)); |
| 64 |
|
| 65 |
EXPECT_FALSE(BP(1, 7) == BP(2, 7)); |
| 66 |
EXPECT_FALSE(BP(1, 7) == BP(1, 4)); |
| 67 |
EXPECT_FALSE(BP(5, 7) == BP(3, 4)); |
| 68 |
EXPECT_TRUE(BP(1, 7) == BP(1, 7)); |
| 69 |
EXPECT_TRUE(BP(1, 7) == BP(2, 14)); |
| 70 |
EXPECT_FALSE(BP(4, 7) == BP(1, 2)); |
| 71 |
EXPECT_FALSE(BP(4, 7) == BP(3, 7)); |
| 72 |
|
| 73 |
EXPECT_TRUE(BP(1, 7) != BP(2, 7)); |
| 74 |
EXPECT_TRUE(BP(1, 7) != BP(1, 4)); |
| 75 |
EXPECT_TRUE(BP(5, 7) != BP(3, 4)); |
| 76 |
EXPECT_FALSE(BP(1, 7) != BP(1, 7)); |
| 77 |
EXPECT_FALSE(BP(1, 7) != BP(2, 14)); |
| 78 |
EXPECT_TRUE(BP(4, 7) != BP(1, 2)); |
| 79 |
EXPECT_TRUE(BP(4, 7) != BP(3, 7)); |
| 80 |
|
| 81 |
EXPECT_TRUE(BP(1, 7) == BP(2, 14)); |
| 82 |
EXPECT_TRUE(BP(1, 7) == BP(3, 21)); |
| 83 |
EXPECT_TRUE(BP(5, 7) == BP(25, 35)); |
| 84 |
EXPECT_TRUE(BP(99999998, 100000000) < BP(99999999, 100000000)); |
| 85 |
EXPECT_TRUE(BP(4, 8) == BP(400000000, 800000000)); |
| 86 |
} |
| 87 |
|
| 88 |
TEST(BranchProbabilityTest, MoreOperators) { |
| 89 |
BP A(4, 5); |
| 90 |
BP B(4U << 29, 5U << 29); |
| 91 |
BP C(3, 4); |
| 92 |
|
| 93 |
EXPECT_TRUE(A == B); |
| 94 |
EXPECT_FALSE(A != B); |
| 95 |
EXPECT_FALSE(A < B); |
| 96 |
EXPECT_FALSE(A > B); |
| 97 |
EXPECT_TRUE(A <= B); |
| 98 |
EXPECT_TRUE(A >= B); |
| 99 |
|
| 100 |
EXPECT_FALSE(B == C); |
| 101 |
EXPECT_TRUE(B != C); |
| 102 |
EXPECT_FALSE(B < C); |
| 103 |
EXPECT_TRUE(B > C); |
| 104 |
EXPECT_FALSE(B <= C); |
| 105 |
EXPECT_TRUE(B >= C); |
| 106 |
|
| 107 |
BP BigZero(0, UINT32_MAX); |
| 108 |
BP BigOne(UINT32_MAX, UINT32_MAX); |
| 109 |
EXPECT_FALSE(BigZero == BigOne); |
| 110 |
EXPECT_TRUE(BigZero != BigOne); |
| 111 |
EXPECT_TRUE(BigZero < BigOne); |
| 112 |
EXPECT_FALSE(BigZero > BigOne); |
| 113 |
EXPECT_TRUE(BigZero <= BigOne); |
| 114 |
EXPECT_FALSE(BigZero >= BigOne); |
| 115 |
} |
| 116 |
|
| 117 |
TEST(BranchProbabilityTest, ArithmeticOperators) { |
| 118 |
BP Z(0, 1); |
| 119 |
BP O(1, 1); |
| 120 |
BP H(1, 2); |
| 121 |
BP Q(1, 4); |
| 122 |
BP Q3(3, 4); |
| 123 |
|
| 124 |
EXPECT_EQ(Z + O, O); |
| 125 |
EXPECT_EQ(H + Z, H); |
| 126 |
EXPECT_EQ(H + H, O); |
| 127 |
EXPECT_EQ(Q + H, Q3); |
| 128 |
EXPECT_EQ(Q + Q3, O); |
| 129 |
EXPECT_EQ(H + Q3, O); |
| 130 |
EXPECT_EQ(Q3 + Q3, O); |
| 131 |
|
| 132 |
EXPECT_EQ(Z - O, Z); |
| 133 |
EXPECT_EQ(O - Z, O); |
| 134 |
EXPECT_EQ(O - H, H); |
| 135 |
EXPECT_EQ(O - Q, Q3); |
| 136 |
EXPECT_EQ(Q3 - H, Q); |
| 137 |
EXPECT_EQ(Q - H, Z); |
| 138 |
EXPECT_EQ(Q - Q3, Z); |
| 139 |
|
| 140 |
EXPECT_EQ(Z * O, Z); |
| 141 |
EXPECT_EQ(H * H, Q); |
| 142 |
EXPECT_EQ(Q * O, Q); |
| 143 |
EXPECT_EQ(O * O, O); |
| 144 |
EXPECT_EQ(Z * Z, Z); |
| 145 |
|
| 146 |
EXPECT_EQ(Z * 3, Z); |
| 147 |
EXPECT_EQ(Q * 3, Q3); |
| 148 |
EXPECT_EQ(H * 3, O); |
| 149 |
EXPECT_EQ(Q3 * 2, O); |
| 150 |
EXPECT_EQ(O * UINT32_MAX, O); |
| 151 |
|
| 152 |
EXPECT_EQ(Z / 4, Z); |
| 153 |
EXPECT_EQ(O / 4, Q); |
| 154 |
EXPECT_EQ(Q3 / 3, Q); |
| 155 |
EXPECT_EQ(H / 2, Q); |
| 156 |
EXPECT_EQ(O / 2, H); |
| 157 |
EXPECT_EQ(H / UINT32_MAX, Z); |
| 158 |
|
| 159 |
BP Min(1, 1u << 31); |
| 160 |
|
| 161 |
EXPECT_EQ(O / UINT32_MAX, Z); |
| 162 |
EXPECT_EQ(Min * UINT32_MAX, O); |
| 163 |
} |
| 164 |
|
| 165 |
TEST(BranchProbabilityTest, getCompl) { |
| 166 |
EXPECT_EQ(BP(5, 7), BP(2, 7).getCompl()); |
| 167 |
EXPECT_EQ(BP(2, 7), BP(5, 7).getCompl()); |
| 168 |
EXPECT_EQ(BP::getZero(), BP(7, 7).getCompl()); |
| 169 |
EXPECT_EQ(BP::getOne(), BP(0, 7).getCompl()); |
| 170 |
} |
| 171 |
|
| 172 |
TEST(BranchProbabilityTest, scale) { |
| 173 |
// Multiply by 1.0. |
| 174 |
EXPECT_EQ(UINT64_MAX, BP(1, 1).scale(UINT64_MAX)); |
| 175 |
EXPECT_EQ(UINT64_MAX, BP(7, 7).scale(UINT64_MAX)); |
| 176 |
EXPECT_EQ(UINT32_MAX, BP(1, 1).scale(UINT32_MAX)); |
| 177 |
EXPECT_EQ(UINT32_MAX, BP(7, 7).scale(UINT32_MAX)); |
| 178 |
EXPECT_EQ(0u, BP(1, 1).scale(0)); |
| 179 |
EXPECT_EQ(0u, BP(7, 7).scale(0)); |
| 180 |
|
| 181 |
// Multiply by 0.0. |
| 182 |
EXPECT_EQ(0u, BP(0, 1).scale(UINT64_MAX)); |
| 183 |
EXPECT_EQ(0u, BP(0, 1).scale(UINT64_MAX)); |
| 184 |
EXPECT_EQ(0u, BP(0, 1).scale(0)); |
| 185 |
|
| 186 |
auto Two63 = UINT64_C(1) << 63; |
| 187 |
auto Two31 = UINT64_C(1) << 31; |
| 188 |
|
| 189 |
// Multiply by 0.5. |
| 190 |
EXPECT_EQ(Two63 - 1, BP(1, 2).scale(UINT64_MAX)); |
| 191 |
|
| 192 |
// Big fractions. |
| 193 |
EXPECT_EQ(1u, BP(Two31, UINT32_MAX).scale(2)); |
| 194 |
EXPECT_EQ(Two31, BP(Two31, UINT32_MAX).scale(Two31 * 2)); |
| 195 |
EXPECT_EQ(9223372036854775807ULL, BP(Two31, UINT32_MAX).scale(UINT64_MAX)); |
| 196 |
|
| 197 |
// High precision. |
| 198 |
EXPECT_EQ(UINT64_C(9223372045444710399), |
| 199 |
BP(Two31 + 1, UINT32_MAX - 2).scale(UINT64_MAX)); |
| 200 |
} |
| 201 |
|
| 202 |
TEST(BranchProbabilityTest, scaleByInverse) { |
| 203 |
// Divide by 1.0. |
| 204 |
EXPECT_EQ(UINT64_MAX, BP(1, 1).scaleByInverse(UINT64_MAX)); |
| 205 |
EXPECT_EQ(UINT64_MAX, BP(7, 7).scaleByInverse(UINT64_MAX)); |
| 206 |
EXPECT_EQ(UINT32_MAX, BP(1, 1).scaleByInverse(UINT32_MAX)); |
| 207 |
EXPECT_EQ(UINT32_MAX, BP(7, 7).scaleByInverse(UINT32_MAX)); |
| 208 |
EXPECT_EQ(0u, BP(1, 1).scaleByInverse(0)); |
| 209 |
EXPECT_EQ(0u, BP(7, 7).scaleByInverse(0)); |
| 210 |
|
| 211 |
auto MAX_DENOMINATOR = BP::getDenominator(); |
| 212 |
|
| 213 |
// Divide by something very small. |
| 214 |
EXPECT_EQ(UINT64_MAX, BP(1, UINT32_MAX).scaleByInverse(UINT64_MAX)); |
| 215 |
EXPECT_EQ(uint64_t(UINT32_MAX) * MAX_DENOMINATOR, |
| 216 |
BP(1, MAX_DENOMINATOR).scaleByInverse(UINT32_MAX)); |
| 217 |
EXPECT_EQ(MAX_DENOMINATOR, BP(1, MAX_DENOMINATOR).scaleByInverse(1)); |
| 218 |
|
| 219 |
auto Two63 = UINT64_C(1) << 63; |
| 220 |
auto Two31 = UINT64_C(1) << 31; |
| 221 |
|
| 222 |
// Divide by 0.5. |
| 223 |
EXPECT_EQ(UINT64_MAX - 1, BP(1, 2).scaleByInverse(Two63 - 1)); |
| 224 |
EXPECT_EQ(UINT64_MAX, BP(1, 2).scaleByInverse(Two63)); |
| 225 |
|
| 226 |
// Big fractions. |
| 227 |
EXPECT_EQ(2u, BP(Two31, UINT32_MAX).scaleByInverse(1)); |
| 228 |
EXPECT_EQ(2u, BP(Two31 - 1, UINT32_MAX).scaleByInverse(1)); |
| 229 |
EXPECT_EQ(Two31 * 2, BP(Two31, UINT32_MAX).scaleByInverse(Two31)); |
| 230 |
EXPECT_EQ(Two31 * 2, BP(Two31 - 1, UINT32_MAX).scaleByInverse(Two31)); |
| 231 |
EXPECT_EQ(UINT64_MAX, BP(Two31, UINT32_MAX).scaleByInverse(Two63 + Two31)); |
| 232 |
|
| 233 |
// High precision. The exact answers to these are close to the successors of |
| 234 |
// the floor. If we were rounding, these would round up. |
| 235 |
EXPECT_EQ(UINT64_C(18446744060824649767), |
| 236 |
BP(Two31 + 2, UINT32_MAX - 2) |
| 237 |
.scaleByInverse(UINT64_C(9223372047592194056))); |
| 238 |
EXPECT_EQ(UINT64_C(18446744060824649739), |
| 239 |
BP(Two31 + 1, UINT32_MAX).scaleByInverse(Two63 + Two31)); |
| 240 |
} |
| 241 |
|
| 242 |
TEST(BranchProbabilityTest, scaleBruteForce) { |
| 243 |
struct { |
| 244 |
uint64_t Num; |
| 245 |
uint32_t Prob[2]; |
| 246 |
uint64_t Result; |
| 247 |
} Tests[] = { |
| 248 |
// Data for scaling that results in <= 64 bit division. |
| 249 |
{ 0x1423e2a50ULL, { 0x64819521, 0x7765dd13 }, 0x10f418888ULL }, |
| 250 |
{ 0x35ef14ceULL, { 0x28ade3c7, 0x304532ae }, 0x2d73c33bULL }, |
| 251 |
{ 0xd03dbfbe24ULL, { 0x790079, 0xe419f3 }, 0x6e776fc2c4ULL }, |
| 252 |
{ 0x21d67410bULL, { 0x302a9dc2, 0x3ddb4442 }, 0x1a5948fd4ULL }, |
| 253 |
{ 0x8664aeadULL, { 0x3d523513, 0x403523b1 }, 0x805a04cfULL }, |
| 254 |
{ 0x201db0cf4ULL, { 0x35112a7b, 0x79fc0c74 }, 0xdf8b07f8ULL }, |
| 255 |
{ 0x13f1e4430aULL, { 0x21c92bf, 0x21e63aae }, 0x13e0cba26ULL }, |
| 256 |
{ 0x16c83229ULL, { 0x3793f66f, 0x53180dea }, 0xf3ce7b6ULL }, |
| 257 |
{ 0xc62415be8ULL, { 0x9cc4a63, 0x4327ae9b }, 0x1ce8b71c1ULL }, |
| 258 |
{ 0x6fac5e434ULL, { 0xe5f9170, 0x1115e10b }, 0x5df23dd4cULL }, |
| 259 |
{ 0x1929375f2ULL, { 0x3a851375, 0x76c08456 }, 0xc662b083ULL }, |
| 260 |
{ 0x243c89db6ULL, { 0x354ebfc0, 0x450ef197 }, 0x1bf8c1663ULL }, |
| 261 |
{ 0x310e9b31aULL, { 0x1b1b8acf, 0x2d3629f0 }, 0x1d69c93f9ULL }, |
| 262 |
{ 0xa1fae921dULL, { 0xa7a098c, 0x10469f44 }, 0x684413d6eULL }, |
| 263 |
{ 0xc1582d957ULL, { 0x498e061, 0x59856bc }, 0x9edc5f4ecULL }, |
| 264 |
{ 0x57cfee75ULL, { 0x1d061dc3, 0x7c8bfc17 }, 0x1476a220ULL }, |
| 265 |
{ 0x139220080ULL, { 0x294a6c71, 0x2a2b07c9 }, 0x1329e1c75ULL }, |
| 266 |
{ 0x1665d353cULL, { 0x7080db5, 0xde0d75c }, 0xb590d9faULL }, |
| 267 |
{ 0xe8f14541ULL, { 0x5188e8b2, 0x736527ef }, 0xa4971be5ULL }, |
| 268 |
{ 0x2f4775f29ULL, { 0x254ef0fe, 0x435fcf50 }, 0x1a2e449c1ULL }, |
| 269 |
{ 0x27b85d8d7ULL, { 0x304c8220, 0x5de678f2 }, 0x146e3befbULL }, |
| 270 |
{ 0x1d362e36bULL, { 0x36c85b12, 0x37a66f55 }, 0x1cc19b8e7ULL }, |
| 271 |
{ 0x155fd48c7ULL, { 0xf5894d, 0x1256108 }, 0x11e383604ULL }, |
| 272 |
{ 0xb5db2d15ULL, { 0x39bb26c5, 0x5bdcda3e }, 0x72499259ULL }, |
| 273 |
{ 0x153990298ULL, { 0x48921c09, 0x706eb817 }, 0xdb3268e7ULL }, |
| 274 |
{ 0x28a7c3ed7ULL, { 0x1f776fd7, 0x349f7a70 }, 0x184f73ae2ULL }, |
| 275 |
{ 0x724dbeabULL, { 0x1bd149f5, 0x253a085e }, 0x5569c0b3ULL }, |
| 276 |
{ 0xd8f0c513ULL, { 0x18c8cc4c, 0x1b72bad0 }, 0xc3e30642ULL }, |
| 277 |
{ 0x17ce3dcbULL, { 0x1e4c6260, 0x233b359e }, 0x1478f4afULL }, |
| 278 |
{ 0x1ce036ce0ULL, { 0x29e3c8af, 0x5318dd4a }, 0xe8e76195ULL }, |
| 279 |
{ 0x1473ae2aULL, { 0x29b897ba, 0x2be29378 }, 0x13718185ULL }, |
| 280 |
{ 0x1dd41aa68ULL, { 0x3d0a4441, 0x5a0e8f12 }, 0x1437b6bbfULL }, |
| 281 |
{ 0x1b49e4a53ULL, { 0x3430c1fe, 0x5a204aed }, 0xfcd6852fULL }, |
| 282 |
{ 0x217941b19ULL, { 0x12ced2bd, 0x21b68310 }, 0x12aca65b1ULL }, |
| 283 |
{ 0xac6a4dc8ULL, { 0x3ed68da8, 0x6fdca34c }, 0x60da926dULL }, |
| 284 |
{ 0x1c503a4e7ULL, { 0xfcbbd32, 0x11e48d17 }, 0x18fec7d37ULL }, |
| 285 |
{ 0x1c885855ULL, { 0x213e919d, 0x25941897 }, 0x193de742ULL }, |
| 286 |
{ 0x29b9c168eULL, { 0x2b644aea, 0x45725ee7 }, 0x1a122e5d4ULL }, |
| 287 |
{ 0x806a33f2ULL, { 0x30a80a23, 0x5063733a }, 0x4db9a264ULL }, |
| 288 |
{ 0x282afc96bULL, { 0x143ae554, 0x1a9863ff }, 0x1e8de5204ULL }, |
| 289 |
// Data for scaling that results in > 64 bit division. |
| 290 |
{ 0x23ca5f2f672ca41cULL, { 0xecbc641, 0x111373f7 }, 0x1f0301e5c76869c6ULL }, |
| 291 |
{ 0x5e4f2468142265e3ULL, { 0x1ddf5837, 0x32189233 }, 0x383ca7bad6053ac9ULL }, |
| 292 |
{ 0x277a1a6f6b266bf6ULL, { 0x415d81a8, 0x61eb5e1e }, 0x1a5a3e1d1c9e8540ULL }, |
| 293 |
{ 0x1bdbb49a237035cbULL, { 0xea5bf17, 0x1d25ffb3 }, 0xdffc51c5cb51cf1ULL }, |
| 294 |
{ 0x2bce6d29b64fb8ULL, { 0x3bfd5631, 0x7525c9bb }, 0x166ebedd9581fdULL }, |
| 295 |
{ 0x3a02116103df5013ULL, { 0x2ee18a83, 0x3299aea8 }, 0x35be89227276f105ULL }, |
| 296 |
{ 0x7b5762390799b18cULL, { 0x12f8e5b9, 0x2563bcd4 }, 0x3e960077695655a3ULL }, |
| 297 |
{ 0x69cfd72537021579ULL, { 0x4c35f468, 0x6a40feee }, 0x4be4cb38695a4f30ULL }, |
| 298 |
{ 0x49dfdf835120f1c1ULL, { 0x8cb3759, 0x559eb891 }, 0x79663f6e3c8d8f6ULL }, |
| 299 |
{ 0x74b5be5c27676381ULL, { 0x47e4c5e0, 0x7c7b19ff }, 0x4367d2dfb22b3265ULL }, |
| 300 |
{ 0x4f50f97075e7f431ULL, { 0x9a50a17, 0x11cd1185 }, 0x2af952b30374f382ULL }, |
| 301 |
{ 0x2f8b0d712e393be4ULL, { 0x1487e386, 0x15aa356e }, 0x2d0df3649b2b19fcULL }, |
| 302 |
{ 0x224c1c75999d3deULL, { 0x3b2df0ea, 0x4523b100 }, 0x1d5b481d160dd8bULL }, |
| 303 |
{ 0x2bcbcea22a399a76ULL, { 0x28b58212, 0x48dd013e }, 0x187814d0610c8a56ULL }, |
| 304 |
{ 0x1dbfca91257cb2d1ULL, { 0x1a8c04d9, 0x5e92502c }, 0x859cf7d19e83ad0ULL }, |
| 305 |
{ 0x7f20039b57cda935ULL, { 0xeccf651, 0x323f476e }, 0x25720cd9054634bdULL }, |
| 306 |
{ 0x40512c6a586aa087ULL, { 0x113b0423, 0x398c9eab }, 0x1341c03dbb662054ULL }, |
| 307 |
{ 0x63d802693f050a11ULL, { 0xf50cdd6, 0xfce2a44 }, 0x60c0177b667a4feaULL }, |
| 308 |
{ 0x2d956b422838de77ULL, { 0xb2d345b, 0x1321e557 }, 0x1aa0ed16b094575cULL }, |
| 309 |
{ 0x5a1cdf0c1657bc91ULL, { 0x1d77bb0c, 0x1f991ff1 }, 0x54097ee9907290eaULL }, |
| 310 |
{ 0x3801b26d7e00176bULL, { 0xeed25da, 0x1a819d8b }, 0x1f89e96a616b9abeULL }, |
| 311 |
{ 0x37655e74338e1e45ULL, { 0x300e170a, 0x5a1595fe }, 0x1d8cfb55ff6a6dbcULL }, |
| 312 |
{ 0x7b38703f2a84e6ULL, { 0x66d9053, 0xc79b6b9 }, 0x3f7d4c91b9afb9ULL }, |
| 313 |
{ 0x2245063c0acb3215ULL, { 0x30ce2f5b, 0x610e7271 }, 0x113b916455fe2560ULL }, |
| 314 |
{ 0x6bc195877b7b8a7eULL, { 0x392004aa, 0x4a24e60c }, 0x530594fabfc81cc3ULL }, |
| 315 |
{ 0x40a3fde23c7b43dbULL, { 0x4e712195, 0x6553e56e }, 0x320a799bc205c78dULL }, |
| 316 |
{ 0x1d3dfc2866fbccbaULL, { 0x5075b517, 0x5fc42245 }, 0x18917f00745cb781ULL }, |
| 317 |
{ 0x19aeb14045a61121ULL, { 0x1bf6edec, 0x707e2f4b }, 0x6626672aa2ba10aULL }, |
| 318 |
{ 0x44ff90486c531e9fULL, { 0x66598a, 0x8a90dc }, 0x32f6f2b097001598ULL }, |
| 319 |
{ 0x3f3e7121092c5bcbULL, { 0x1c754df7, 0x5951a1b9 }, 0x14267f50d4971583ULL }, |
| 320 |
{ 0x60e2dafb7e50a67eULL, { 0x4d96c66e, 0x65bd878d }, 0x49e317155d75e883ULL }, |
| 321 |
{ 0x656286667e0e6e29ULL, { 0x9d971a2, 0xacda23b }, 0x5c6ee3159e1deac3ULL }, |
| 322 |
{ 0x1114e0974255d507ULL, { 0x1c693, 0x2d6ff }, 0xaae42e4be5f9f8dULL }, |
| 323 |
{ 0x508c8baf3a70ff5aULL, { 0x3b26b779, 0x6ad78745 }, 0x2c983876178ed5b1ULL }, |
| 324 |
{ 0x5b47bc666bf1f9cfULL, { 0x10a87ed6, 0x187d358a }, 0x3e1767153bea720aULL }, |
| 325 |
{ 0x50954e3744460395ULL, { 0x7a42263, 0xcdaa048 }, 0x2fe739f0944a023cULL }, |
| 326 |
{ 0x20020b406550dd8fULL, { 0x3318539, 0x42eead0 }, 0x186f326307c0d985ULL }, |
| 327 |
{ 0x5bcb0b872439ffd5ULL, { 0x6f61fb2, 0x9af7344 }, 0x41fa1e3c47f0f80dULL }, |
| 328 |
{ 0x7a670f365db87a53ULL, { 0x417e102, 0x3bb54c67 }, 0x8642a551d0f41b0ULL }, |
| 329 |
{ 0x1ef0db1e7bab1cd0ULL, { 0x2b60cf38, 0x4188f78f }, 0x147ae0d63fc0575aULL } |
| 330 |
}; |
| 331 |
|
| 332 |
for (const auto &T : Tests) { |
| 333 |
EXPECT_EQ(T.Result, BP(T.Prob[0], T.Prob[1]).scale(T.Num)); |
| 334 |
} |
| 335 |
} |
| 336 |
|
| 337 |
TEST(BranchProbabilityTest, NormalizeProbabilities) { |
| 338 |
const auto UnknownProb = BranchProbability::getUnknown(); |
| 339 |
{ |
| 340 |
SmallVector<BranchProbability, 2> Probs{{0, 1}, {0, 1}}; |
| 341 |
BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end()); |
| 342 |
EXPECT_EQ(BranchProbability::getDenominator() / 2, Probs[0].getNumerator()); |
| 343 |
EXPECT_EQ(BranchProbability::getDenominator() / 2, Probs[1].getNumerator()); |
| 344 |
} |
| 345 |
{ |
| 346 |
SmallVector<BranchProbability, 2> Probs{{0, 1}, {1, 1}}; |
| 347 |
BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end()); |
| 348 |
EXPECT_EQ(0u, Probs[0].getNumerator()); |
| 349 |
EXPECT_EQ(BranchProbability::getDenominator(), Probs[1].getNumerator()); |
| 350 |
} |
| 351 |
{ |
| 352 |
SmallVector<BranchProbability, 2> Probs{{1, 100}, {1, 100}}; |
| 353 |
BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end()); |
| 354 |
EXPECT_EQ(BranchProbability::getDenominator() / 2, Probs[0].getNumerator()); |
| 355 |
EXPECT_EQ(BranchProbability::getDenominator() / 2, Probs[1].getNumerator()); |
| 356 |
} |
| 357 |
{ |
| 358 |
SmallVector<BranchProbability, 2> Probs{{1, 1}, {1, 1}}; |
| 359 |
BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end()); |
| 360 |
EXPECT_EQ(BranchProbability::getDenominator() / 2, Probs[0].getNumerator()); |
| 361 |
EXPECT_EQ(BranchProbability::getDenominator() / 2, Probs[1].getNumerator()); |
| 362 |
} |
| 363 |
{ |
| 364 |
SmallVector<BranchProbability, 3> Probs{{1, 1}, {1, 1}, {1, 1}}; |
| 365 |
BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end()); |
| 366 |
EXPECT_EQ(BranchProbability::getDenominator() / 3 + 1, |
| 367 |
Probs[0].getNumerator()); |
| 368 |
EXPECT_EQ(BranchProbability::getDenominator() / 3 + 1, |
| 369 |
Probs[1].getNumerator()); |
| 370 |
EXPECT_EQ(BranchProbability::getDenominator() / 3 + 1, |
| 371 |
Probs[2].getNumerator()); |
| 372 |
} |
| 373 |
{ |
| 374 |
SmallVector<BranchProbability, 2> Probs{{0, 1}, UnknownProb}; |
| 375 |
BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end()); |
| 376 |
EXPECT_EQ(0U, Probs[0].getNumerator()); |
| 377 |
EXPECT_EQ(BranchProbability::getDenominator(), Probs[1].getNumerator()); |
| 378 |
} |
| 379 |
{ |
| 380 |
SmallVector<BranchProbability, 2> Probs{{1, 1}, UnknownProb}; |
| 381 |
BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end()); |
| 382 |
EXPECT_EQ(BranchProbability::getDenominator(), Probs[0].getNumerator()); |
| 383 |
EXPECT_EQ(0U, Probs[1].getNumerator()); |
| 384 |
} |
| 385 |
{ |
| 386 |
SmallVector<BranchProbability, 2> Probs{{1, 2}, UnknownProb}; |
| 387 |
BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end()); |
| 388 |
EXPECT_EQ(BranchProbability::getDenominator() / 2, Probs[0].getNumerator()); |
| 389 |
EXPECT_EQ(BranchProbability::getDenominator() / 2, Probs[1].getNumerator()); |
| 390 |
} |
| 391 |
{ |
| 392 |
SmallVector<BranchProbability, 4> Probs{ |
| 393 |
{1, 2}, {1, 2}, {1, 2}, UnknownProb}; |
| 394 |
BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end()); |
| 395 |
EXPECT_EQ(BranchProbability::getDenominator() / 3 + 1, |
| 396 |
Probs[0].getNumerator()); |
| 397 |
EXPECT_EQ(BranchProbability::getDenominator() / 3 + 1, |
| 398 |
Probs[1].getNumerator()); |
| 399 |
EXPECT_EQ(BranchProbability::getDenominator() / 3 + 1, |
| 400 |
Probs[2].getNumerator()); |
| 401 |
EXPECT_EQ(0U, Probs[3].getNumerator()); |
| 402 |
} |
| 403 |
} |
| 404 |
|
| 405 |
} |