1 // Copyright 2018 Ulf Adams
2 //
3 // The contents of this file may be used under the terms of the Apache License,
4 // Version 2.0.
5 //
6 // (See accompanying file LICENSE-Apache or copy at
7 // http://www.apache.org/licenses/LICENSE-2.0)
8 //
9 // Alternatively, the contents of this file may be used under the terms of
10 // the Boost Software License, Version 1.0.
11 // (See accompanying file LICENSE-Boost or copy at
12 // https://www.boost.org/LICENSE_1_0.txt)
13 //
14 // Unless required by applicable law or agreed to in writing, this software
15 // is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
16 // KIND, either express or implied.
17 #ifndef RYU_GENERIC128_H
18 #define RYU_GENERIC128_H
19
20 #define FLOAT_128_POW5_INV_BITCOUNT 249
21 #define FLOAT_128_POW5_BITCOUNT 249
22 #define POW5_TABLE_SIZE 56
23
24 // These tables are ~4.5 kByte total, compared to ~160 kByte for the full tables.
25
26 // There's no way to define 128-bit constants in C, so we use little-endian
27 // pairs of 64-bit constants.
28 static const uint64_t GENERIC_POW5_TABLE[POW5_TABLE_SIZE][2] = {
29 { 1u, 0u },
30 { 5u, 0u },
31 { 25u, 0u },
32 { 125u, 0u },
33 { 625u, 0u },
34 { 3125u, 0u },
35 { 15625u, 0u },
36 { 78125u, 0u },
37 { 390625u, 0u },
38 { 1953125u, 0u },
39 { 9765625u, 0u },
40 { 48828125u, 0u },
41 { 244140625u, 0u },
42 { 1220703125u, 0u },
43 { 6103515625u, 0u },
44 { 30517578125u, 0u },
45 { 152587890625u, 0u },
46 { 762939453125u, 0u },
47 { 3814697265625u, 0u },
48 { 19073486328125u, 0u },
49 { 95367431640625u, 0u },
50 { 476837158203125u, 0u },
51 { 2384185791015625u, 0u },
52 { 11920928955078125u, 0u },
53 { 59604644775390625u, 0u },
54 { 298023223876953125u, 0u },
55 { 1490116119384765625u, 0u },
56 { 7450580596923828125u, 0u },
57 { 359414837200037393u, 2u },
58 { 1797074186000186965u, 10u },
59 { 8985370930000934825u, 50u },
60 { 8033366502585570893u, 252u },
61 { 3273344365508751233u, 1262u },
62 { 16366721827543756165u, 6310u },
63 { 8046632842880574361u, 31554u },
64 { 3339676066983768573u, 157772u },
65 { 16698380334918842865u, 788860u },
66 { 9704925379756007861u, 3944304u },
67 { 11631138751360936073u, 19721522u },
68 { 2815461535676025517u, 98607613u },
69 { 14077307678380127585u, 493038065u },
70 { 15046306170771983077u, 2465190328u },
71 { 1444554559021708921u, 12325951644u },
72 { 7222772795108544605u, 61629758220u },
73 { 17667119901833171409u, 308148791101u },
74 { 14548623214327650581u, 1540743955509u },
75 { 17402883850509598057u, 7703719777548u },
76 { 13227442957709783821u, 38518598887744u },
77 { 10796982567420264257u, 192592994438723u },
78 { 17091424689682218053u, 962964972193617u },
79 { 11670147153572883801u, 4814824860968089u },
80 { 3010503546735764157u, 24074124304840448u },
81 { 15052517733678820785u, 120370621524202240u },
82 { 1475612373555897461u, 601853107621011204u },
83 { 7378061867779487305u, 3009265538105056020u },
84 { 18443565265187884909u, 15046327690525280101u }
85 };
86
87 static const uint64_t GENERIC_POW5_SPLIT[89][4] = {
88 { 0u, 0u, 0u, 72057594037927936u },
89 { 0u, 5206161169240293376u, 4575641699882439235u, 73468396926392969u },
90 { 3360510775605221349u, 6983200512169538081u, 4325643253124434363u, 74906821675075173u },
91 { 11917660854915489451u, 9652941469841108803u, 946308467778435600u, 76373409087490117u },
92 { 1994853395185689235u, 16102657350889591545u, 6847013871814915412u, 77868710555449746u },
93 { 958415760277438274u, 15059347134713823592u, 7329070255463483331u, 79393288266368765u },
94 { 2065144883315240188u, 7145278325844925976u, 14718454754511147343u, 80947715414629833u },
95 { 8980391188862868935u, 13709057401304208685u, 8230434828742694591u, 82532576417087045u },
96 { 432148644612782575u, 7960151582448466064u, 12056089168559840552u, 84148467132788711u },
97 { 484109300864744403u, 15010663910730448582u, 16824949663447227068u, 85795995087002057u },
98 { 14793711725276144220u, 16494403799991899904u, 10145107106505865967u, 87475779699624060u },
99 { 15427548291869817042u, 12330588654550505203u, 13980791795114552342u, 89188452518064298u },
100 { 9979404135116626552u, 13477446383271537499u, 14459862802511591337u, 90934657454687378u },
101 { 12385121150303452775u, 9097130814231585614u, 6523855782339765207u, 92715051028904201u },
102 { 1822931022538209743u, 16062974719797586441u, 3619180286173516788u, 94530302614003091u },
103 { 12318611738248470829u, 13330752208259324507u, 10986694768744162601u, 96381094688813589u },
104 { 13684493829640282333u, 7674802078297225834u, 15208116197624593182u, 98268123094297527u },
105 { 5408877057066295332u, 6470124174091971006u, 15112713923117703147u, 100192097295163851u },
106 { 11407083166564425062u, 18189998238742408185u, 4337638702446708282u, 102153740646605557u },
107 { 4112405898036935485u, 924624216579956435u, 14251108172073737125u, 104153790666259019u },
108 { 16996739107011444789u, 10015944118339042475u, 2395188869672266257u, 106192999311487969u },
109 { 4588314690421337879u, 5339991768263654604u, 15441007590670620066u, 108272133262096356u },
110 { 2286159977890359825u, 14329706763185060248u, 5980012964059367667u, 110391974208576409u },
111 { 9654767503237031099u, 11293544302844823188u, 11739932712678287805u, 112553319146000238u },
112 { 11362964448496095896u, 7990659682315657680u, 251480263940996374u, 114756980673665505u },
113 { 1423410421096377129u, 14274395557581462179u, 16553482793602208894u, 117003787300607788u },
114 { 2070444190619093137u, 11517140404712147401u, 11657844572835578076u, 119294583757094535u },
115 { 7648316884775828921u, 15264332483297977688u, 247182277434709002u, 121630231312217685u },
116 { 17410896758132241352u, 10923914482914417070u, 13976383996795783649u, 124011608097704390u },
117 { 9542674537907272703u, 3079432708831728956u, 14235189590642919676u, 126439609438067572u },
118 { 10364666969937261816u, 8464573184892924210u, 12758646866025101190u, 128915148187220428u },
119 { 14720354822146013883u, 11480204489231511423u, 7449876034836187038u, 131439155071681461u },
120 { 1692907053653558553u, 17835392458598425233u, 1754856712536736598u, 134012579040499057u },
121 { 5620591334531458755u, 11361776175667106627u, 13350215315297937856u, 136636387622027174u },
122 { 17455759733928092601u, 10362573084069962561u, 11246018728801810510u, 139311567287686283u },
123 { 2465404073814044982u, 17694822665274381860u, 1509954037718722697u, 142039123822846312u },
124 { 2152236053329638369u, 11202280800589637091u, 16388426812920420176u, 72410041352485523u },
125 { 17319024055671609028u, 10944982848661280484u, 2457150158022562661u, 73827744744583080u },
126 { 17511219308535248024u, 5122059497846768077u, 2089605804219668451u, 75273205100637900u },
127 { 10082673333144031533u, 14429008783411894887u, 12842832230171903890u, 76746965869337783u },
128 { 16196653406315961184u, 10260180891682904501u, 10537411930446752461u, 78249581139456266u },
129 { 15084422041749743389u, 234835370106753111u, 16662517110286225617u, 79781615848172976u },
130 { 8199644021067702606u, 3787318116274991885u, 7438130039325743106u, 81343645993472659u },
131 { 12039493937039359765u, 9773822153580393709u, 5945428874398357806u, 82936258850702722u },
132 { 984543865091303961u, 7975107621689454830u, 6556665988501773347u, 84560053193370726u },
133 { 9633317878125234244u, 16099592426808915028u, 9706674539190598200u, 86215639518264828u },
134 { 6860695058870476186u, 4471839111886709592u, 7828342285492709568u, 87903640274981819u },
135 { 14583324717644598331u, 4496120889473451238u, 5290040788305728466u, 89624690099949049u },
136 { 18093669366515003715u, 12879506572606942994u, 18005739787089675377u, 91379436055028227u },
137 { 17997493966862379937u, 14646222655265145582u, 10265023312844161858u, 93168537870790806u },
138 { 12283848109039722318u, 11290258077250314935u, 9878160025624946825u, 94992668194556404u },
139 { 8087752761883078164u, 5262596608437575693u, 11093553063763274413u, 96852512843287537u },
140 { 15027787746776840781u, 12250273651168257752u, 9290470558712181914u, 98748771061435726u },
141 { 15003915578366724489u, 2937334162439764327u, 5404085603526796602u, 100682155783835929u },
142 { 5225610465224746757u, 14932114897406142027u, 2774647558180708010u, 102653393903748137u },
143 { 17112957703385190360u, 12069082008339002412u, 3901112447086388439u, 104663226546146909u },
144 { 4062324464323300238u, 3992768146772240329u, 15757196565593695724u, 106712409346361594u },
145 { 5525364615810306701u, 11855206026704935156u, 11344868740897365300u, 108801712734172003u },
146 { 9274143661888462646u, 4478365862348432381u, 18010077872551661771u, 110931922223466333u },
147 { 12604141221930060148u, 8930937759942591500u, 9382183116147201338u, 113103838707570263u },
148 { 14513929377491886653u, 1410646149696279084u, 587092196850797612u, 115318278760358235u },
149 { 2226851524999454362u, 7717102471110805679u, 7187441550995571734u, 117576074943260147u },
150 { 5527526061344932763u, 2347100676188369132u, 16976241418824030445u, 119878076118278875u },
151 { 6088479778147221611u, 17669593130014777580u, 10991124207197663546u, 122225147767136307u },
152 { 11107734086759692041u, 3391795220306863431u, 17233960908859089158u, 124618172316667879u },
153 { 7913172514655155198u, 17726879005381242552u, 641069866244011540u, 127058049470587962u },
154 { 12596991768458713949u, 15714785522479904446u, 6035972567136116512u, 129545696547750811u },
155 { 16901996933781815980u, 4275085211437148707u, 14091642539965169063u, 132082048827034281u },
156 { 7524574627987869240u, 15661204384239316051u, 2444526454225712267u, 134668059898975949u },
157 { 8199251625090479942u, 6803282222165044067u, 16064817666437851504u, 137304702024293857u },
158 { 4453256673338111920u, 15269922543084434181u, 3139961729834750852u, 139992966499426682u },
159 { 15841763546372731299u, 3013174075437671812u, 4383755396295695606u, 142733864029230733u },
160 { 9771896230907310329u, 4900659362437687569u, 12386126719044266361u, 72764212553486967u },
161 { 9420455527449565190u, 1859606122611023693u, 6555040298902684281u, 74188850200884818u },
162 { 5146105983135678095u, 2287300449992174951u, 4325371679080264751u, 75641380576797959u },
163 { 11019359372592553360u, 8422686425957443718u, 7175176077944048210u, 77122349788024458u },
164 { 11005742969399620716u, 4132174559240043701u, 9372258443096612118u, 78632314633490790u },
165 { 8887589641394725840u, 8029899502466543662u, 14582206497241572853u, 80171842813591127u },
166 { 360247523705545899u, 12568341805293354211u, 14653258284762517866u, 81741513143625247u },
167 { 12314272731984275834u, 4740745023227177044u, 6141631472368337539u, 83341915771415304u },
168 { 441052047733984759u, 7940090120939869826u, 11750200619921094248u, 84973652399183278u },
169 { 3436657868127012749u, 9187006432149937667u, 16389726097323041290u, 86637336509772529u },
170 { 13490220260784534044u, 15339072891382896702u, 8846102360835316895u, 88333593597298497u },
171 { 4125672032094859833u, 158347675704003277u, 10592598512749774447u, 90063061402315272u },
172 { 12189928252974395775u, 2386931199439295891u, 7009030566469913276u, 91826390151586454u },
173 { 9256479608339282969u, 2844900158963599229u, 11148388908923225596u, 93624242802550437u },
174 { 11584393507658707408u, 2863659090805147914u, 9873421561981063551u, 95457295292572042u },
175 { 13984297296943171390u, 1931468383973130608u, 12905719743235082319u, 97326236793074198u },
176 { 5837045222254987499u, 10213498696735864176u, 14893951506257020749u, 99231769968645227u }
177 };
178
179 // Unfortunately, the results are sometimes off by one or two. We use an additional
180 // lookup table to store those cases and adjust the result.
181 static const uint64_t POW5_ERRORS[156] = {
182 0x0000000000000000u, 0x0000000000000000u, 0x0000000000000000u, 0x9555596400000000u,
183 0x65a6569525565555u, 0x4415551445449655u, 0x5105015504144541u, 0x65a69969a6965964u,
184 0x5054955969959656u, 0x5105154515554145u, 0x4055511051591555u, 0x5500514455550115u,
185 0x0041140014145515u, 0x1005440545511051u, 0x0014405450411004u, 0x0414440010500000u,
186 0x0044000440010040u, 0x5551155000004001u, 0x4554555454544114u, 0x5150045544005441u,
187 0x0001111400054501u, 0x6550955555554554u, 0x1504159645559559u, 0x4105055141454545u,
188 0x1411541410405454u, 0x0415555044545555u, 0x0014154115405550u, 0x1540055040411445u,
189 0x0000000500000000u, 0x5644000000000000u, 0x1155555591596555u, 0x0410440054569565u,
190 0x5145100010010005u, 0x0555041405500150u, 0x4141450455140450u, 0x0000000144000140u,
191 0x5114004001105410u, 0x4444100404005504u, 0x0414014410001015u, 0x5145055155555015u,
192 0x0141041444445540u, 0x0000100451541414u, 0x4105041104155550u, 0x0500501150451145u,
193 0x1001050000004114u, 0x5551504400141045u, 0x5110545410151454u, 0x0100001400004040u,
194 0x5040010111040000u, 0x0140000150541100u, 0x4400140400104110u, 0x5011014405545004u,
195 0x0000000044155440u, 0x0000000010000000u, 0x1100401444440001u, 0x0040401010055111u,
196 0x5155155551405454u, 0x0444440015514411u, 0x0054505054014101u, 0x0451015441115511u,
197 0x1541411401140551u, 0x4155104514445110u, 0x4141145450145515u, 0x5451445055155050u,
198 0x4400515554110054u, 0x5111145104501151u, 0x565a655455500501u, 0x5565555555525955u,
199 0x0550511500405695u, 0x4415504051054544u, 0x6555595965555554u, 0x0100915915555655u,
200 0x5540001510001001u, 0x5450051414000544u, 0x1405010555555551u, 0x5555515555644155u,
201 0x5555055595496555u, 0x5451045004415000u, 0x5450510144040144u, 0x5554155555556455u,
202 0x5051555495415555u, 0x5555554555555545u, 0x0000000010005455u, 0x4000005000040000u,
203 0x5565555555555954u, 0x5554559555555505u, 0x9645545495552555u, 0x4000400055955564u,
204 0x0040000000000001u, 0x4004100100000000u, 0x5540040440000411u, 0x4565555955545644u,
205 0x1140659549651556u, 0x0100000410010000u, 0x5555515400004001u, 0x5955545555155255u,
206 0x5151055545505556u, 0x5051454510554515u, 0x0501500050415554u, 0x5044154005441005u,
207 0x1455445450550455u, 0x0010144055144545u, 0x0000401100000004u, 0x1050145050000010u,
208 0x0415004554011540u, 0x1000510100151150u, 0x0100040400001144u, 0x0000000000000000u,
209 0x0550004400000100u, 0x0151145041451151u, 0x0000400400005450u, 0x0000100044010004u,
210 0x0100054100050040u, 0x0504400005410010u, 0x4011410445500105u, 0x0000404000144411u,
211 0x0101504404500000u, 0x0000005044400400u, 0x0000000014000100u, 0x0404440414000000u,
212 0x5554100410000140u, 0x4555455544505555u, 0x5454105055455455u, 0x0115454155454015u,
213 0x4404110000045100u, 0x4400001100101501u, 0x6596955956966a94u, 0x0040655955665965u,
214 0x5554144400100155u, 0xa549495401011041u, 0x5596555565955555u, 0x5569965959549555u,
215 0x969565a655555456u, 0x0000001000000000u, 0x0000000040000140u, 0x0000040100000000u,
216 0x1415454400000000u, 0x5410415411454114u, 0x0400040104000154u, 0x0504045000000411u,
217 0x0000001000000010u, 0x5554000000001040u, 0x5549155551556595u, 0x1455541055515555u,
218 0x0510555454554541u, 0x9555555555540455u, 0x6455456555556465u, 0x4524565555654514u,
219 0x5554655255559545u, 0x9555455441155556u, 0x0000000051515555u, 0x0010005040000550u,
220 0x5044044040000000u, 0x1045040440010500u, 0x0000400000040000u, 0x0000000000000000u
221 };
222
223 static const uint64_t GENERIC_POW5_INV_SPLIT[89][4] = {
224 { 0u, 0u, 0u, 144115188075855872u },
225 { 1573859546583440065u, 2691002611772552616u, 6763753280790178510u, 141347765182270746u },
226 { 12960290449513840412u, 12345512957918226762u, 18057899791198622765u, 138633484706040742u },
227 { 7615871757716765416u, 9507132263365501332u, 4879801712092008245u, 135971326161092377u },
228 { 7869961150745287587u, 5804035291554591636u, 8883897266325833928u, 133360288657597085u },
229 { 2942118023529634767u, 15128191429820565086u, 10638459445243230718u, 130799390525667397u },
230 { 14188759758411913794u, 5362791266439207815u, 8068821289119264054u, 128287668946279217u },
231 { 7183196927902545212u, 1952291723540117099u, 12075928209936341512u, 125824179589281448u },
232 { 5672588001402349748u, 17892323620748423487u, 9874578446960390364u, 123407996258356868u },
233 { 4442590541217566325u, 4558254706293456445u, 10343828952663182727u, 121038210542800766u },
234 { 3005560928406962566u, 2082271027139057888u, 13961184524927245081u, 118713931475986426u },
235 { 13299058168408384786u, 17834349496131278595u, 9029906103900731664u, 116434285200389047u },
236 { 5414878118283973035u, 13079825470227392078u, 17897304791683760280u, 114198414639042157u },
237 { 14609755883382484834u, 14991702445765844156u, 3269802549772755411u, 112005479173303009u },
238 { 15967774957605076027u, 2511532636717499923u, 16221038267832563171u, 109854654326805788u },
239 { 9269330061621627145u, 3332501053426257392u, 16223281189403734630u, 107745131455483836u },
240 { 16739559299223642282u, 1873986623300664530u, 6546709159471442872u, 105676117443544318u },
241 { 17116435360051202055u, 1359075105581853924u, 2038341371621886470u, 103646834405281051u },
242 { 17144715798009627550u, 3201623802661132408u, 9757551605154622431u, 101656519392613377u },
243 { 17580479792687825857u, 6546633380567327312u, 15099972427870912398u, 99704424108241124u },
244 { 9726477118325522902u, 14578369026754005435u, 11728055595254428803u, 97789814624307808u },
245 { 134593949518343635u, 5715151379816901985u, 1660163707976377376u, 95911971106466306u },
246 { 5515914027713859358u, 7124354893273815720u, 5548463282858794077u, 94070187543243255u },
247 { 6188403395862945512u, 5681264392632320838u, 15417410852121406654u, 92263771480600430u },
248 { 15908890877468271457u, 10398888261125597540u, 4817794962769172309u, 90492043761593298u },
249 { 1413077535082201005u, 12675058125384151580u, 7731426132303759597u, 88754338271028867u },
250 { 1486733163972670293u, 11369385300195092554u, 11610016711694864110u, 87050001685026843u },
251 { 8788596583757589684u, 3978580923851924802u, 9255162428306775812u, 85378393225389919u },
252 { 7203518319660962120u, 15044736224407683725u, 2488132019818199792u, 83738884418690858u },
253 { 4004175967662388707u, 18236988667757575407u, 15613100370957482671u, 82130858859985791u },
254 { 18371903370586036463u, 53497579022921640u, 16465963977267203307u, 80553711981064899u },
255 { 10170778323887491315u, 1999668801648976001u, 10209763593579456445u, 79006850823153334u },
256 { 17108131712433974546u, 16825784443029944237u, 2078700786753338945u, 77489693813976938u },
257 { 17221789422665858532u, 12145427517550446164u, 5391414622238668005u, 76001670549108934u },
258 { 4859588996898795878u, 1715798948121313204u, 3950858167455137171u, 74542221577515387u },
259 { 13513469241795711526u, 631367850494860526u, 10517278915021816160u, 73110798191218799u },
260 { 11757513142672073111u, 2581974932255022228u, 17498959383193606459u, 143413724438001539u },
261 { 14524355192525042817u, 5640643347559376447u, 1309659274756813016u, 140659771648132296u },
262 { 2765095348461978538u, 11021111021896007722u, 3224303603779962366u, 137958702611185230u },
263 { 12373410389187981037u, 13679193545685856195u, 11644609038462631561u, 135309501808182158u },
264 { 12813176257562780151u, 3754199046160268020u, 9954691079802960722u, 132711173221007413u },
265 { 17557452279667723458u, 3237799193992485824u, 17893947919029030695u, 130162739957935629u },
266 { 14634200999559435155u, 4123869946105211004u, 6955301747350769239u, 127663243886350468u },
267 { 2185352760627740240u, 2864813346878886844u, 13049218671329690184u, 125211745272516185u },
268 { 6143438674322183002u, 10464733336980678750u, 6982925169933978309u, 122807322428266620u },
269 { 1099509117817174576u, 10202656147550524081u, 754997032816608484u, 120449071364478757u },
270 { 2410631293559367023u, 17407273750261453804u, 15307291918933463037u, 118136105451200587u },
271 { 12224968375134586697u, 1664436604907828062u, 11506086230137787358u, 115867555084305488u },
272 { 3495926216898000888u, 18392536965197424288u, 10992889188570643156u, 113642567358547782u },
273 { 8744506286256259680u, 3966568369496879937u, 18342264969761820037u, 111460305746896569u },
274 { 7689600520560455039u, 5254331190877624630u, 9628558080573245556u, 109319949786027263u },
275 { 11862637625618819436u, 3456120362318976488u, 14690471063106001082u, 107220694767852583u },
276 { 5697330450030126444u, 12424082405392918899u, 358204170751754904u, 105161751436977040u },
277 { 11257457505097373622u, 15373192700214208870u, 671619062372033814u, 103142345693961148u },
278 { 16850355018477166700u, 1913910419361963966u, 4550257919755970531u, 101161718304283822u },
279 { 9670835567561997011u, 10584031339132130638u, 3060560222974851757u, 99219124612893520u },
280 { 7698686577353054710u, 11689292838639130817u, 11806331021588878241u, 97313834264240819u },
281 { 12233569599615692137u, 3347791226108469959u, 10333904326094451110u, 95445130927687169u },
282 { 13049400362825383933u, 17142621313007799680u, 3790542585289224168u, 93612312028186576u },
283 { 12430457242474442072u, 5625077542189557960u, 14765055286236672238u, 91814688482138969u },
284 { 4759444137752473128u, 2230562561567025078u, 4954443037339580076u, 90051584438315940u },
285 { 7246913525170274758u, 8910297835195760709u, 4015904029508858381u, 88322337023761438u },
286 { 12854430245836432067u, 8135139748065431455u, 11548083631386317976u, 86626296094571907u },
287 { 4848827254502687803u, 4789491250196085625u, 3988192420450664125u, 84962823991462151u },
288 { 7435538409611286684u, 904061756819742353u, 14598026519493048444u, 83331295300025028u },
289 { 11042616160352530997u, 8948390828345326218u, 10052651191118271927u, 81731096615594853u },
290 { 11059348291563778943u, 11696515766184685544u, 3783210511290897367u, 80161626312626082u },
291 { 7020010856491885826u, 5025093219346041680u, 8960210401638911765u, 78622294318500592u },
292 { 17732844474490699984u, 7820866704994446502u, 6088373186798844243u, 77112521891678506u },
293 { 688278527545590501u, 3045610706602776618u, 8684243536999567610u, 75631741404109150u },
294 { 2734573255120657297u, 3903146411440697663u, 9470794821691856713u, 74179396127820347u },
295 { 15996457521023071259u, 4776627823451271680u, 12394856457265744744u, 72754940025605801u },
296 { 13492065758834518331u, 7390517611012222399u, 1630485387832860230u, 142715675091463768u },
297 { 13665021627282055864u, 9897834675523659302u, 17907668136755296849u, 139975126841173266u },
298 { 9603773719399446181u, 10771916301484339398u, 10672699855989487527u, 137287204938390542u },
299 { 3630218541553511265u, 8139010004241080614u, 2876479648932814543u, 134650898807055963u },
300 { 8318835909686377084u, 9525369258927993371u, 2796120270400437057u, 132065217277054270u },
301 { 11190003059043290163u, 12424345635599592110u, 12539346395388933763u, 129529188211565064u },
302 { 8701968833973242276u, 820569587086330727u, 2315591597351480110u, 127041858141569228u },
303 { 5115113890115690487u, 16906305245394587826u, 9899749468931071388u, 124602291907373862u },
304 { 15543535488939245974u, 10945189844466391399u, 3553863472349432246u, 122209572307020975u },
305 { 7709257252608325038u, 1191832167690640880u, 15077137020234258537u, 119862799751447719u },
306 { 7541333244210021737u, 9790054727902174575u, 5160944773155322014u, 117561091926268545u },
307 { 12297384708782857832u, 1281328873123467374u, 4827925254630475769u, 115303583460052092u },
308 { 13243237906232367265u, 15873887428139547641u, 3607993172301799599u, 113089425598968120u },
309 { 11384616453739611114u, 15184114243769211033u, 13148448124803481057u, 110917785887682141u },
310 { 17727970963596660683u, 1196965221832671990u, 14537830463956404138u, 108787847856377790u },
311 { 17241367586707330931u, 8880584684128262874u, 11173506540726547818u, 106698810713789254u },
312 { 7184427196661305643u, 14332510582433188173u, 14230167953789677901u, 104649889046128358u }
313 };
314
315 static const uint64_t POW5_INV_ERRORS[154] = {
316 0x1144155514145504u, 0x0000541555401141u, 0x0000000000000000u, 0x0154454000000000u,
317 0x4114105515544440u, 0x0001001111500415u, 0x4041411410011000u, 0x5550114515155014u,
318 0x1404100041554551u, 0x0515000450404410u, 0x5054544401140004u, 0x5155501005555105u,
319 0x1144141000105515u, 0x0541500000500000u, 0x1104105540444140u, 0x4000015055514110u,
320 0x0054010450004005u, 0x4155515404100005u, 0x5155145045155555u, 0x1511555515440558u,
321 0x5558544555515555u, 0x0000000000000010u, 0x5004000000000050u, 0x1415510100000010u,
322 0x4545555444514500u, 0x5155151555555551u, 0x1441540144044554u, 0x5150104045544400u,
323 0x5450545401444040u, 0x5554455045501400u, 0x4655155555555145u, 0x1000010055455055u,
324 0x1000004000055004u, 0x4455405104000005u, 0x4500114504150545u, 0x0000000014000000u,
325 0x5450000000000000u, 0x5514551511445555u, 0x4111501040555451u, 0x4515445500054444u,
326 0x5101500104100441u, 0x1545115155545055u, 0x0000000000000000u, 0x1554000000100000u,
327 0x5555545595551555u, 0x5555051851455955u, 0x5555555555555559u, 0x0000400011001555u,
328 0x0000004400040000u, 0x5455511555554554u, 0x5614555544115445u, 0x6455156145555155u,
329 0x5455855455415455u, 0x5515555144555545u, 0x0114400000145155u, 0x0000051000450511u,
330 0x4455154554445100u, 0x4554150141544455u, 0x65955555559a5965u, 0x5555555854559559u,
331 0x9569654559616595u, 0x1040044040005565u, 0x1010010500011044u, 0x1554015545154540u,
332 0x4440555401545441u, 0x1014441450550105u, 0x4545400410504145u, 0x5015111541040151u,
333 0x5145051154000410u, 0x1040001044545044u, 0x4001400000151410u, 0x0540000044040000u,
334 0x0510555454411544u, 0x0400054054141550u, 0x1001041145001100u, 0x0000000140000000u,
335 0x0000000014100000u, 0x1544005454000140u, 0x4050055505445145u, 0x0011511104504155u,
336 0x5505544415045055u, 0x1155154445515554u, 0x0000000000004555u, 0x0000000000000000u,
337 0x5101010510400004u, 0x1514045044440400u, 0x5515519555515555u, 0x4554545441555545u,
338 0x1551055955551515u, 0x0150000011505515u, 0x0044005040400000u, 0x0004001004010050u,
339 0x0000051004450414u, 0x0114001101001144u, 0x0401000001000001u, 0x4500010001000401u,
340 0x0004100000005000u, 0x0105000441101100u, 0x0455455550454540u, 0x5404050144105505u,
341 0x4101510540555455u, 0x1055541411451555u, 0x5451445110115505u, 0x1154110010101545u,
342 0x1145140450054055u, 0x5555565415551554u, 0x1550559555555555u, 0x5555541545045141u,
343 0x4555455450500100u, 0x5510454545554555u, 0x1510140115045455u, 0x1001050040111510u,
344 0x5555454555555504u, 0x9954155545515554u, 0x6596656555555555u, 0x0140410051555559u,
345 0x0011104010001544u, 0x965669659a680501u, 0x5655a55955556955u, 0x4015111014404514u,
346 0x1414155554505145u, 0x0540040011051404u, 0x1010000000015005u, 0x0010054050004410u,
347 0x5041104014000100u, 0x4440010500100001u, 0x1155510504545554u, 0x0450151545115541u,
348 0x4000100400110440u, 0x1004440010514440u, 0x0000115050450000u, 0x0545404455541500u,
349 0x1051051555505101u, 0x5505144554544144u, 0x4550545555515550u, 0x0015400450045445u,
350 0x4514155400554415u, 0x4555055051050151u, 0x1511441450001014u, 0x4544554510404414u,
351 0x4115115545545450u, 0x5500541555551555u, 0x5550010544155015u, 0x0144414045545500u,
352 0x4154050001050150u, 0x5550511111000145u, 0x1114504055000151u, 0x5104041101451040u,
353 0x0010501401051441u, 0x0010501450504401u, 0x4554585440044444u, 0x5155555951450455u,
354 0x0040000400105555u, 0x0000000000000001u,
355 };
356
357 // Returns e == 0 ? 1 : ceil(log_2(5^e)); requires 0 <= e <= 32768.
pow5bits(const int32_t e)358 static inline uint32_t pow5bits(const int32_t e) {
359 assert(e >= 0);
360 assert(e <= 1 << 15);
361 return (uint32_t) (((e * 163391164108059ull) >> 46) + 1);
362 }
363
mul_128_256_shift(const uint64_t * const a,const uint64_t * const b,const uint32_t shift,const uint32_t corr,uint64_t * const result)364 static inline void mul_128_256_shift(
365 const uint64_t* const a, const uint64_t* const b, const uint32_t shift, const uint32_t corr, uint64_t* const result) {
366 assert(shift > 0);
367 assert(shift < 256);
368 const uint128_t b00 = ((uint128_t) a[0]) * b[0]; // 0
369 const uint128_t b01 = ((uint128_t) a[0]) * b[1]; // 64
370 const uint128_t b02 = ((uint128_t) a[0]) * b[2]; // 128
371 const uint128_t b03 = ((uint128_t) a[0]) * b[3]; // 196
372 const uint128_t b10 = ((uint128_t) a[1]) * b[0]; // 64
373 const uint128_t b11 = ((uint128_t) a[1]) * b[1]; // 128
374 const uint128_t b12 = ((uint128_t) a[1]) * b[2]; // 196
375 const uint128_t b13 = ((uint128_t) a[1]) * b[3]; // 256
376
377 const uint128_t s0 = b00; // 0 x
378 const uint128_t s1 = b01 + b10; // 64 x
379 const uint128_t c1 = s1 < b01; // 196 x
380 const uint128_t s2 = b02 + b11; // 128 x
381 const uint128_t c2 = s2 < b02; // 256 x
382 const uint128_t s3 = b03 + b12; // 196 x
383 const uint128_t c3 = s3 < b03; // 324 x
384
385 const uint128_t p0 = s0 + (s1 << 64); // 0
386 const uint128_t d0 = p0 < b00; // 128
387 const uint128_t q1 = s2 + (s1 >> 64) + (s3 << 64); // 128
388 const uint128_t d1 = q1 < s2; // 256
389 const uint128_t p1 = q1 + (c1 << 64) + d0; // 128
390 const uint128_t d2 = p1 < q1; // 256
391 const uint128_t p2 = b13 + (s3 >> 64) + c2 + (c3 << 64) + d1 + d2; // 256
392
393 if (shift < 128) {
394 const uint128_t r0 = corr + ((p0 >> shift) | (p1 << (128 - shift)));
395 const uint128_t r1 = ((p1 >> shift) | (p2 << (128 - shift))) + (r0 < corr);
396 result[0] = (uint64_t) r0;
397 result[1] = (uint64_t) (r0 >> 64);
398 result[2] = (uint64_t) r1;
399 result[3] = (uint64_t) (r1 >> 64);
400 } else if (shift == 128) {
401 const uint128_t r0 = corr + p1;
402 const uint128_t r1 = p2 + (r0 < corr);
403 result[0] = (uint64_t) r0;
404 result[1] = (uint64_t) (r0 >> 64);
405 result[2] = (uint64_t) r1;
406 result[3] = (uint64_t) (r1 >> 64);
407 } else {
408 const uint128_t r0 = corr + ((p1 >> (shift - 128)) | (p2 << (256 - shift)));
409 const uint128_t r1 = (p2 >> (shift - 128)) + (r0 < corr);
410 result[0] = (uint64_t) r0;
411 result[1] = (uint64_t) (r0 >> 64);
412 result[2] = (uint64_t) r1;
413 result[3] = (uint64_t) (r1 >> 64);
414 }
415 }
416
417 // Computes 5^i in the form required by Ryu, and stores it in the given pointer.
generic_computePow5(const uint32_t i,uint64_t * const result)418 static inline void generic_computePow5(const uint32_t i, uint64_t* const result) {
419 const uint32_t base = i / POW5_TABLE_SIZE;
420 const uint32_t base2 = base * POW5_TABLE_SIZE;
421 const uint64_t* const mul = GENERIC_POW5_SPLIT[base];
422 if (i == base2) {
423 result[0] = mul[0];
424 result[1] = mul[1];
425 result[2] = mul[2];
426 result[3] = mul[3];
427 } else {
428 const uint32_t offset = i - base2;
429 const uint64_t* const m = GENERIC_POW5_TABLE[offset];
430 const uint32_t delta = pow5bits(i) - pow5bits(base2);
431 const uint32_t corr = (uint32_t) ((POW5_ERRORS[i / 32] >> (2 * (i % 32))) & 3);
432 mul_128_256_shift(m, mul, delta, corr, result);
433 }
434 }
435
436 // Computes 5^-i in the form required by Ryu, and stores it in the given pointer.
generic_computeInvPow5(const uint32_t i,uint64_t * const result)437 static inline void generic_computeInvPow5(const uint32_t i, uint64_t* const result) {
438 const uint32_t base = (i + POW5_TABLE_SIZE - 1) / POW5_TABLE_SIZE;
439 const uint32_t base2 = base * POW5_TABLE_SIZE;
440 const uint64_t* const mul = GENERIC_POW5_INV_SPLIT[base]; // 1/5^base2
441 if (i == base2) {
442 result[0] = mul[0] + 1;
443 result[1] = mul[1];
444 result[2] = mul[2];
445 result[3] = mul[3];
446 } else {
447 const uint32_t offset = base2 - i;
448 const uint64_t* const m = GENERIC_POW5_TABLE[offset]; // 5^offset
449 const uint32_t delta = pow5bits(base2) - pow5bits(i);
450 const uint32_t corr = (uint32_t) ((POW5_INV_ERRORS[i / 32] >> (2 * (i % 32))) & 3) + 1;
451 mul_128_256_shift(m, mul, delta, corr, result);
452 }
453 }
454
pow5Factor(uint128_t value)455 static inline uint32_t pow5Factor(uint128_t value) {
456 for (uint32_t count = 0; value > 0; ++count) {
457 if (value % 5 != 0) {
458 return count;
459 }
460 value /= 5;
461 }
462 return 0;
463 }
464
465 // Returns true if value is divisible by 5^p.
multipleOfPowerOf5(const uint128_t value,const uint32_t p)466 static inline bool multipleOfPowerOf5(const uint128_t value, const uint32_t p) {
467 // I tried a case distinction on p, but there was no performance difference.
468 return pow5Factor(value) >= p;
469 }
470
471 // Returns true if value is divisible by 2^p.
multipleOfPowerOf2(const uint128_t value,const uint32_t p)472 static inline bool multipleOfPowerOf2(const uint128_t value, const uint32_t p) {
473 return (value & ((((uint128_t) 1) << p) - 1)) == 0;
474 }
475
mulShift(const uint128_t m,const uint64_t * const mul,const int32_t j)476 static inline uint128_t mulShift(const uint128_t m, const uint64_t* const mul, const int32_t j) {
477 assert(j > 128);
478 uint64_t a[2];
479 a[0] = (uint64_t) m;
480 a[1] = (uint64_t) (m >> 64);
481 uint64_t result[4];
482 mul_128_256_shift(a, mul, j, 0, result);
483 return (((uint128_t) result[1]) << 64) | result[0];
484 }
485
decimalLength(const uint128_t v)486 static inline uint32_t decimalLength(const uint128_t v) {
487 static uint128_t LARGEST_POW10 = (((uint128_t) 5421010862427522170ull) << 64) | 687399551400673280ull;
488 uint128_t p10 = LARGEST_POW10;
489 for (uint32_t i = 39; i > 0; i--) {
490 if (v >= p10) {
491 return i;
492 }
493 p10 /= 10;
494 }
495 return 1;
496 }
497
498 // Returns floor(log_10(2^e)).
log10Pow2(const int32_t e)499 static inline uint32_t log10Pow2(const int32_t e) {
500 // The first value this approximation fails for is 2^1651 which is just greater than 10^297.
501 assert(e >= 0);
502 assert(e <= 1 << 15);
503 return (uint32_t) ((((uint64_t) e) * 169464822037455ull) >> 49);
504 }
505
506 // Returns floor(log_10(5^e)).
log10Pow5(const int32_t e)507 static inline uint32_t log10Pow5(const int32_t e) {
508 // The first value this approximation fails for is 5^2621 which is just greater than 10^1832.
509 assert(e >= 0);
510 assert(e <= 1 << 15);
511 return (uint32_t) ((((uint64_t) e) * 196742565691928ull) >> 48);
512 }
513
514 #endif // RYU_GENERIC128_H
515