1 // Copyright 2011 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 #include "src/base/numbers/cached-powers.h"
6
7 #include <limits.h>
8 #include <stdarg.h>
9 #include <stdint.h>
10
11 #include <cmath>
12
13 #include "src/base/logging.h"
14
15 namespace v8 {
16 namespace base {
17
18 struct CachedPower {
19 uint64_t significand;
20 int16_t binary_exponent;
21 int16_t decimal_exponent;
22 };
23
24 static const CachedPower kCachedPowers[] = {
25 {0xFA8F'D5A0'081C'0288, -1220, -348}, {0xBAAE'E17F'A23E'BF76, -1193, -340},
26 {0x8B16'FB20'3055'AC76, -1166, -332}, {0xCF42'894A'5DCE'35EA, -1140, -324},
27 {0x9A6B'B0AA'5565'3B2D, -1113, -316}, {0xE61A'CF03'3D1A'45DF, -1087, -308},
28 {0xAB70'FE17'C79A'C6CA, -1060, -300}, {0xFF77'B1FC'BEBC'DC4F, -1034, -292},
29 {0xBE56'91EF'416B'D60C, -1007, -284}, {0x8DD0'1FAD'907F'FC3C, -980, -276},
30 {0xD351'5C28'3155'9A83, -954, -268}, {0x9D71'AC8F'ADA6'C9B5, -927, -260},
31 {0xEA9C'2277'23EE'8BCB, -901, -252}, {0xAECC'4991'4078'536D, -874, -244},
32 {0x823C'1279'5DB6'CE57, -847, -236}, {0xC210'9436'4DFB'5637, -821, -228},
33 {0x9096'EA6F'3848'984F, -794, -220}, {0xD774'85CB'2582'3AC7, -768, -212},
34 {0xA086'CFCD'97BF'97F4, -741, -204}, {0xEF34'0A98'172A'ACE5, -715, -196},
35 {0xB238'67FB'2A35'B28E, -688, -188}, {0x84C8'D4DF'D2C6'3F3B, -661, -180},
36 {0xC5DD'4427'1AD3'CDBA, -635, -172}, {0x936B'9FCE'BB25'C996, -608, -164},
37 {0xDBAC'6C24'7D62'A584, -582, -156}, {0xA3AB'6658'0D5F'DAF6, -555, -148},
38 {0xF3E2'F893'DEC3'F126, -529, -140}, {0xB5B5'ADA8'AAFF'80B8, -502, -132},
39 {0x8762'5F05'6C7C'4A8B, -475, -124}, {0xC9BC'FF60'34C1'3053, -449, -116},
40 {0x964E'858C'91BA'2655, -422, -108}, {0xDFF9'7724'7029'7EBD, -396, -100},
41 {0xA6DF'BD9F'B8E5'B88F, -369, -92}, {0xF8A9'5FCF'8874'7D94, -343, -84},
42 {0xB944'7093'8FA8'9BCF, -316, -76}, {0x8A08'F0F8'BF0F'156B, -289, -68},
43 {0xCDB0'2555'6531'31B6, -263, -60}, {0x993F'E2C6'D07B'7FAC, -236, -52},
44 {0xE45C'10C4'2A2B'3B06, -210, -44}, {0xAA24'2499'6973'92D3, -183, -36},
45 {0xFD87'B5F2'8300'CA0E, -157, -28}, {0xBCE5'0864'9211'1AEB, -130, -20},
46 {0x8CBC'CC09'6F50'88CC, -103, -12}, {0xD1B7'1758'E219'652C, -77, -4},
47 {0x9C40'0000'0000'0000, -50, 4}, {0xE8D4'A510'0000'0000, -24, 12},
48 {0xAD78'EBC5'AC62'0000, 3, 20}, {0x813F'3978'F894'0984, 30, 28},
49 {0xC097'CE7B'C907'15B3, 56, 36}, {0x8F7E'32CE'7BEA'5C70, 83, 44},
50 {0xD5D2'38A4'ABE9'8068, 109, 52}, {0x9F4F'2726'179A'2245, 136, 60},
51 {0xED63'A231'D4C4'FB27, 162, 68}, {0xB0DE'6538'8CC8'ADA8, 189, 76},
52 {0x83C7'088E'1AAB'65DB, 216, 84}, {0xC45D'1DF9'4271'1D9A, 242, 92},
53 {0x924D'692C'A61B'E758, 269, 100}, {0xDA01'EE64'1A70'8DEA, 295, 108},
54 {0xA26D'A399'9AEF'774A, 322, 116}, {0xF209'787B'B47D'6B85, 348, 124},
55 {0xB454'E4A1'79DD'1877, 375, 132}, {0x865B'8692'5B9B'C5C2, 402, 140},
56 {0xC835'53C5'C896'5D3D, 428, 148}, {0x952A'B45C'FA97'A0B3, 455, 156},
57 {0xDE46'9FBD'99A0'5FE3, 481, 164}, {0xA59B'C234'DB39'8C25, 508, 172},
58 {0xF6C6'9A72'A398'9F5C, 534, 180}, {0xB7DC'BF53'54E9'BECE, 561, 188},
59 {0x88FC'F317'F222'41E2, 588, 196}, {0xCC20'CE9B'D35C'78A5, 614, 204},
60 {0x9816'5AF3'7B21'53DF, 641, 212}, {0xE2A0'B5DC'971F'303A, 667, 220},
61 {0xA8D9'D153'5CE3'B396, 694, 228}, {0xFB9B'7CD9'A4A7'443C, 720, 236},
62 {0xBB76'4C4C'A7A4'4410, 747, 244}, {0x8BAB'8EEF'B640'9C1A, 774, 252},
63 {0xD01F'EF10'A657'842C, 800, 260}, {0x9B10'A4E5'E991'3129, 827, 268},
64 {0xE710'9BFB'A19C'0C9D, 853, 276}, {0xAC28'20D9'623B'F429, 880, 284},
65 {0x8044'4B5E'7AA7'CF85, 907, 292}, {0xBF21'E440'03AC'DD2D, 933, 300},
66 {0x8E67'9C2F'5E44'FF8F, 960, 308}, {0xD433'179D'9C8C'B841, 986, 316},
67 {0x9E19'DB92'B4E3'1BA9, 1013, 324}, {0xEB96'BF6E'BADF'77D9, 1039, 332},
68 {0xAF87'023B'9BF0'EE6B, 1066, 340},
69 };
70
71 #ifdef DEBUG
72 static const int kCachedPowersLength = arraysize(kCachedPowers);
73 #endif
74
75 static const int kCachedPowersOffset = 348; // -1 * the first decimal_exponent.
76 static const double kD_1_LOG2_10 = 0.30102999566398114; // 1 / lg(10)
77 // Difference between the decimal exponents in the table above.
78 const int PowersOfTenCache::kDecimalExponentDistance = 8;
79 const int PowersOfTenCache::kMinDecimalExponent = -348;
80 const int PowersOfTenCache::kMaxDecimalExponent = 340;
81
GetCachedPowerForBinaryExponentRange(int min_exponent,int max_exponent,DiyFp * power,int * decimal_exponent)82 void PowersOfTenCache::GetCachedPowerForBinaryExponentRange(
83 int min_exponent, int max_exponent, DiyFp* power, int* decimal_exponent) {
84 int kQ = DiyFp::kSignificandSize;
85 // Some platforms return incorrect sign on 0 result. We can ignore that here,
86 // which means we can avoid depending on platform.h.
87 double k = std::ceil((min_exponent + kQ - 1) * kD_1_LOG2_10);
88 int foo = kCachedPowersOffset;
89 int index = (foo + static_cast<int>(k) - 1) / kDecimalExponentDistance + 1;
90 DCHECK(0 <= index && index < kCachedPowersLength);
91 CachedPower cached_power = kCachedPowers[index];
92 DCHECK(min_exponent <= cached_power.binary_exponent);
93 DCHECK(cached_power.binary_exponent <= max_exponent);
94 *decimal_exponent = cached_power.decimal_exponent;
95 *power = DiyFp(cached_power.significand, cached_power.binary_exponent);
96 }
97
GetCachedPowerForDecimalExponent(int requested_exponent,DiyFp * power,int * found_exponent)98 void PowersOfTenCache::GetCachedPowerForDecimalExponent(int requested_exponent,
99 DiyFp* power,
100 int* found_exponent) {
101 DCHECK_LE(kMinDecimalExponent, requested_exponent);
102 DCHECK(requested_exponent < kMaxDecimalExponent + kDecimalExponentDistance);
103 int index =
104 (requested_exponent + kCachedPowersOffset) / kDecimalExponentDistance;
105 CachedPower cached_power = kCachedPowers[index];
106 *power = DiyFp(cached_power.significand, cached_power.binary_exponent);
107 *found_exponent = cached_power.decimal_exponent;
108 DCHECK(*found_exponent <= requested_exponent);
109 DCHECK(requested_exponent < *found_exponent + kDecimalExponentDistance);
110 }
111
112 } // namespace base
113 } // namespace v8
114