• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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