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

source code of boost/libs/charconv/include/boost/charconv/detail/ryu/generic_128.hpp