detail/ryu/generic_128.hpp

0001 // Copyright 2018 - 2023 Ulf Adams
0002 // Copyright 2023 Matt Borland
0003 // Distributed under the Boost Software License, Version 1.0.
0004 // https://www.boost.org/LICENSE_1_0.txt
0005
0006 #ifndef BOOST_CHARCONV_DETAIL_RYU_GENERIC_128_HPP
0007 #define BOOST_CHARCONV_DETAIL_RYU_GENERIC_128_HPP
0008
0009 #include <boost/charconv/detail/config.hpp>
0010 #include <boost/charconv/detail/integer_search_trees.hpp>
0011 #include <boost/charconv/detail/emulated128.hpp>
0012 #include <cstdint>
0013
0014 #define BOOST_CHARCONV_POW5_TABLE_SIZE 56
0015 #define BOOST_CHARCONV_POW5_BITCOUNT 249
0016 #define BOOST_CHARCONV_POW5_INV_BITCOUNT 249
0017
0018 namespace boost { namespace charconv { namespace detail { namespace ryu {
0019
0020 #ifdef BOOST_CHARCONV_HAS_INT128
0021 using unsigned_128_type = boost::uint128_type;
0022 #else
0023 using unsigned_128_type = uint128;
0024 #endif
0025
0026 // These tables are ~4.5 kByte total, compared to ~160 kByte for the full tables.
0027 //
0028 // There's no way to define 128-bit constants in C, so we use little-endian
0029 // pairs of 64-bit constants.
0030
0031 #if (!defined(BOOST_MSVC) || BOOST_MSVC != 1900)
0032 template <bool b>
0033 struct ryu_tables_template
0034 #else
0035 struct ryu_tables
0036 #endif
0037 {
0038     static constexpr uint64_t GENERIC_POW5_TABLE[BOOST_CHARCONV_POW5_TABLE_SIZE][2] = {
0039             {1u,                    0u},
0040             {5u,                    0u},
0041             {25u,                   0u},
0042             {125u,                  0u},
0043             {625u,                  0u},
0044             {3125u,                 0u},
0045             {15625u,                0u},
0046             {78125u,                0u},
0047             {390625u,               0u},
0048             {1953125u,              0u},
0049             {9765625u,              0u},
0050             {48828125u,             0u},
0051             {244140625u,            0u},
0052             {1220703125u,           0u},
0053             {6103515625u,           0u},
0054             {30517578125u,          0u},
0055             {152587890625u,         0u},
0056             {762939453125u,         0u},
0057             {3814697265625u,        0u},
0058             {19073486328125u,       0u},
0059             {95367431640625u,       0u},
0060             {476837158203125u,      0u},
0061             {2384185791015625u,     0u},
0062             {11920928955078125u,    0u},
0063             {59604644775390625u,    0u},
0064             {298023223876953125u,   0u},
0065             {1490116119384765625u,  0u},
0066             {7450580596923828125u,  0u},
0067             {359414837200037393u,   2u},
0068             {1797074186000186965u,  10u},
0069             {8985370930000934825u,  50u},
0070             {8033366502585570893u,  252u},
0071             {3273344365508751233u,  1262u},
0072             {16366721827543756165u, 6310u},
0073             {8046632842880574361u,  31554u},
0074             {3339676066983768573u,  157772u},
0075             {16698380334918842865u, 788860u},
0076             {9704925379756007861u,  3944304u},
0077             {11631138751360936073u, 19721522u},
0078             {2815461535676025517u,  98607613u},
0079             {14077307678380127585u, 493038065u},
0080             {15046306170771983077u, 2465190328u},
0081             {1444554559021708921u,  12325951644u},
0082             {7222772795108544605u,  61629758220u},
0083             {17667119901833171409u, 308148791101u},
0084             {14548623214327650581u, 1540743955509u},
0085             {17402883850509598057u, 7703719777548u},
0086             {13227442957709783821u, 38518598887744u},
0087             {10796982567420264257u, 192592994438723u},
0088             {17091424689682218053u, 962964972193617u},
0089             {11670147153572883801u, 4814824860968089u},
0090             {3010503546735764157u,  24074124304840448u},
0091             {15052517733678820785u, 120370621524202240u},
0092             {1475612373555897461u,  601853107621011204u},
0093             {7378061867779487305u,  3009265538105056020u},
0094             {18443565265187884909u, 15046327690525280101u}
0095     };
0096
0097     static constexpr uint64_t GENERIC_POW5_SPLIT[89][4] = {
0098             {0u,                    0u,                    0u,                    72057594037927936u},
0099             {0u,                    5206161169240293376u,  4575641699882439235u,  73468396926392969u},
0100             {3360510775605221349u,  6983200512169538081u,  4325643253124434363u,  74906821675075173u},
0101             {11917660854915489451u, 9652941469841108803u,  946308467778435600u,   76373409087490117u},
0102             {1994853395185689235u,  16102657350889591545u, 6847013871814915412u,  77868710555449746u},
0103             {958415760277438274u,   15059347134713823592u, 7329070255463483331u,  79393288266368765u},
0104             {2065144883315240188u,  7145278325844925976u,  14718454754511147343u, 80947715414629833u},
0105             {8980391188862868935u,  13709057401304208685u, 8230434828742694591u,  82532576417087045u},
0106             {432148644612782575u,   7960151582448466064u,  12056089168559840552u, 84148467132788711u},
0107             {484109300864744403u,   15010663910730448582u, 16824949663447227068u, 85795995087002057u},
0108             {14793711725276144220u, 16494403799991899904u, 10145107106505865967u, 87475779699624060u},
0109             {15427548291869817042u, 12330588654550505203u, 13980791795114552342u, 89188452518064298u},
0110             {9979404135116626552u,  13477446383271537499u, 14459862802511591337u, 90934657454687378u},
0111             {12385121150303452775u, 9097130814231585614u,  6523855782339765207u,  92715051028904201u},
0112             {1822931022538209743u,  16062974719797586441u, 3619180286173516788u,  94530302614003091u},
0113             {12318611738248470829u, 13330752208259324507u, 10986694768744162601u, 96381094688813589u},
0114             {13684493829640282333u, 7674802078297225834u,  15208116197624593182u, 98268123094297527u},
0115             {5408877057066295332u,  6470124174091971006u,  15112713923117703147u, 100192097295163851u},
0116             {11407083166564425062u, 18189998238742408185u, 4337638702446708282u,  102153740646605557u},
0117             {4112405898036935485u,  924624216579956435u,   14251108172073737125u, 104153790666259019u},
0118             {16996739107011444789u, 10015944118339042475u, 2395188869672266257u,  106192999311487969u},
0119             {4588314690421337879u,  5339991768263654604u,  15441007590670620066u, 108272133262096356u},
0120             {2286159977890359825u,  14329706763185060248u, 5980012964059367667u,  110391974208576409u},
0121             {9654767503237031099u,  11293544302844823188u, 11739932712678287805u, 112553319146000238u},
0122             {11362964448496095896u, 7990659682315657680u,  251480263940996374u,   114756980673665505u},
0123             {1423410421096377129u,  14274395557581462179u, 16553482793602208894u, 117003787300607788u},
0124             {2070444190619093137u,  11517140404712147401u, 11657844572835578076u, 119294583757094535u},
0125             {7648316884775828921u,  15264332483297977688u, 247182277434709002u,   121630231312217685u},
0126             {17410896758132241352u, 10923914482914417070u, 13976383996795783649u, 124011608097704390u},
0127             {9542674537907272703u,  3079432708831728956u,  14235189590642919676u, 126439609438067572u},
0128             {10364666969937261816u, 8464573184892924210u,  12758646866025101190u, 128915148187220428u},
0129             {14720354822146013883u, 11480204489231511423u, 7449876034836187038u,  131439155071681461u},
0130             {1692907053653558553u,  17835392458598425233u, 1754856712536736598u,  134012579040499057u},
0131             {5620591334531458755u,  11361776175667106627u, 13350215315297937856u, 136636387622027174u},
0132             {17455759733928092601u, 10362573084069962561u, 11246018728801810510u, 139311567287686283u},
0133             {2465404073814044982u,  17694822665274381860u, 1509954037718722697u,  142039123822846312u},
0134             {2152236053329638369u,  11202280800589637091u, 16388426812920420176u, 72410041352485523u},
0135             {17319024055671609028u, 10944982848661280484u, 2457150158022562661u,  73827744744583080u},
0136             {17511219308535248024u, 5122059497846768077u,  2089605804219668451u,  75273205100637900u},
0137             {10082673333144031533u, 14429008783411894887u, 12842832230171903890u, 76746965869337783u},
0138             {16196653406315961184u, 10260180891682904501u, 10537411930446752461u, 78249581139456266u},
0139             {15084422041749743389u, 234835370106753111u,   16662517110286225617u, 79781615848172976u},
0140             {8199644021067702606u,  3787318116274991885u,  7438130039325743106u,  81343645993472659u},
0141             {12039493937039359765u, 9773822153580393709u,  5945428874398357806u,  82936258850702722u},
0142             {984543865091303961u,   7975107621689454830u,  6556665988501773347u,  84560053193370726u},
0143             {9633317878125234244u,  16099592426808915028u, 9706674539190598200u,  86215639518264828u},
0144             {6860695058870476186u,  4471839111886709592u,  7828342285492709568u,  87903640274981819u},
0145             {14583324717644598331u, 4496120889473451238u,  5290040788305728466u,  89624690099949049u},
0146             {18093669366515003715u, 12879506572606942994u, 18005739787089675377u, 91379436055028227u},
0147             {17997493966862379937u, 14646222655265145582u, 10265023312844161858u, 93168537870790806u},
0148             {12283848109039722318u, 11290258077250314935u, 9878160025624946825u,  94992668194556404u},
0149             {8087752761883078164u,  5262596608437575693u,  11093553063763274413u, 96852512843287537u},
0150             {15027787746776840781u, 12250273651168257752u, 9290470558712181914u,  98748771061435726u},
0151             {15003915578366724489u, 2937334162439764327u,  5404085603526796602u,  100682155783835929u},
0152             {5225610465224746757u,  14932114897406142027u, 2774647558180708010u,  102653393903748137u},
0153             {17112957703385190360u, 12069082008339002412u, 3901112447086388439u,  104663226546146909u},
0154             {4062324464323300238u,  3992768146772240329u,  15757196565593695724u, 106712409346361594u},
0155             {5525364615810306701u,  11855206026704935156u, 11344868740897365300u, 108801712734172003u},
0156             {9274143661888462646u,  4478365862348432381u,  18010077872551661771u, 110931922223466333u},
0157             {12604141221930060148u, 8930937759942591500u,  9382183116147201338u,  113103838707570263u},
0158             {14513929377491886653u, 1410646149696279084u,  587092196850797612u,   115318278760358235u},
0159             {2226851524999454362u,  7717102471110805679u,  7187441550995571734u,  117576074943260147u},
0160             {5527526061344932763u,  2347100676188369132u,  16976241418824030445u, 119878076118278875u},
0161             {6088479778147221611u,  17669593130014777580u, 10991124207197663546u, 122225147767136307u},
0162             {11107734086759692041u, 3391795220306863431u,  17233960908859089158u, 124618172316667879u},
0163             {7913172514655155198u,  17726879005381242552u, 641069866244011540u,   127058049470587962u},
0164             {12596991768458713949u, 15714785522479904446u, 6035972567136116512u,  129545696547750811u},
0165             {16901996933781815980u, 4275085211437148707u,  14091642539965169063u, 132082048827034281u},
0166             {7524574627987869240u,  15661204384239316051u, 2444526454225712267u,  134668059898975949u},
0167             {8199251625090479942u,  6803282222165044067u,  16064817666437851504u, 137304702024293857u},
0168             {4453256673338111920u,  15269922543084434181u, 3139961729834750852u,  139992966499426682u},
0169             {15841763546372731299u, 3013174075437671812u,  4383755396295695606u,  142733864029230733u},
0170             {9771896230907310329u,  4900659362437687569u,  12386126719044266361u, 72764212553486967u},
0171             {9420455527449565190u,  1859606122611023693u,  6555040298902684281u,  74188850200884818u},
0172             {5146105983135678095u,  2287300449992174951u,  4325371679080264751u,  75641380576797959u},
0173             {11019359372592553360u, 8422686425957443718u,  7175176077944048210u,  77122349788024458u},
0174             {11005742969399620716u, 4132174559240043701u,  9372258443096612118u,  78632314633490790u},
0175             {8887589641394725840u,  8029899502466543662u,  14582206497241572853u, 80171842813591127u},
0176             {360247523705545899u,   12568341805293354211u, 14653258284762517866u, 81741513143625247u},
0177             {12314272731984275834u, 4740745023227177044u,  6141631472368337539u,  83341915771415304u},
0178             {441052047733984759u,   7940090120939869826u,  11750200619921094248u, 84973652399183278u},
0179             {3436657868127012749u,  9187006432149937667u,  16389726097323041290u, 86637336509772529u},
0180             {13490220260784534044u, 15339072891382896702u, 8846102360835316895u,  88333593597298497u},
0181             {4125672032094859833u,  158347675704003277u,   10592598512749774447u, 90063061402315272u},
0182             {12189928252974395775u, 2386931199439295891u,  7009030566469913276u,  91826390151586454u},
0183             {9256479608339282969u,  2844900158963599229u,  11148388908923225596u, 93624242802550437u},
0184             {11584393507658707408u, 2863659090805147914u,  9873421561981063551u,  95457295292572042u},
0185             {13984297296943171390u, 1931468383973130608u,  12905719743235082319u, 97326236793074198u},
0186             {5837045222254987499u,  10213498696735864176u, 14893951506257020749u, 99231769968645227u}
0187     };
0188
0189     // Unfortunately, the results are sometimes off by one or two. We use an additional
0190     // lookup table to store those cases and adjust the result.
0191     static constexpr uint64_t POW5_ERRORS[156] = {
0192             0x0000000000000000u, 0x0000000000000000u, 0x0000000000000000u, 0x9555596400000000u,
0193             0x65a6569525565555u, 0x4415551445449655u, 0x5105015504144541u, 0x65a69969a6965964u,
0194             0x5054955969959656u, 0x5105154515554145u, 0x4055511051591555u, 0x5500514455550115u,
0195             0x0041140014145515u, 0x1005440545511051u, 0x0014405450411004u, 0x0414440010500000u,
0196             0x0044000440010040u, 0x5551155000004001u, 0x4554555454544114u, 0x5150045544005441u,
0197             0x0001111400054501u, 0x6550955555554554u, 0x1504159645559559u, 0x4105055141454545u,
0198             0x1411541410405454u, 0x0415555044545555u, 0x0014154115405550u, 0x1540055040411445u,
0199             0x0000000500000000u, 0x5644000000000000u, 0x1155555591596555u, 0x0410440054569565u,
0200             0x5145100010010005u, 0x0555041405500150u, 0x4141450455140450u, 0x0000000144000140u,
0201             0x5114004001105410u, 0x4444100404005504u, 0x0414014410001015u, 0x5145055155555015u,
0202             0x0141041444445540u, 0x0000100451541414u, 0x4105041104155550u, 0x0500501150451145u,
0203             0x1001050000004114u, 0x5551504400141045u, 0x5110545410151454u, 0x0100001400004040u,
0204             0x5040010111040000u, 0x0140000150541100u, 0x4400140400104110u, 0x5011014405545004u,
0205             0x0000000044155440u, 0x0000000010000000u, 0x1100401444440001u, 0x0040401010055111u,
0206             0x5155155551405454u, 0x0444440015514411u, 0x0054505054014101u, 0x0451015441115511u,
0207             0x1541411401140551u, 0x4155104514445110u, 0x4141145450145515u, 0x5451445055155050u,
0208             0x4400515554110054u, 0x5111145104501151u, 0x565a655455500501u, 0x5565555555525955u,
0209             0x0550511500405695u, 0x4415504051054544u, 0x6555595965555554u, 0x0100915915555655u,
0210             0x5540001510001001u, 0x5450051414000544u, 0x1405010555555551u, 0x5555515555644155u,
0211             0x5555055595496555u, 0x5451045004415000u, 0x5450510144040144u, 0x5554155555556455u,
0212             0x5051555495415555u, 0x5555554555555545u, 0x0000000010005455u, 0x4000005000040000u,
0213             0x5565555555555954u, 0x5554559555555505u, 0x9645545495552555u, 0x4000400055955564u,
0214             0x0040000000000001u, 0x4004100100000000u, 0x5540040440000411u, 0x4565555955545644u,
0215             0x1140659549651556u, 0x0100000410010000u, 0x5555515400004001u, 0x5955545555155255u,
0216             0x5151055545505556u, 0x5051454510554515u, 0x0501500050415554u, 0x5044154005441005u,
0217             0x1455445450550455u, 0x0010144055144545u, 0x0000401100000004u, 0x1050145050000010u,
0218             0x0415004554011540u, 0x1000510100151150u, 0x0100040400001144u, 0x0000000000000000u,
0219             0x0550004400000100u, 0x0151145041451151u, 0x0000400400005450u, 0x0000100044010004u,
0220             0x0100054100050040u, 0x0504400005410010u, 0x4011410445500105u, 0x0000404000144411u,
0221             0x0101504404500000u, 0x0000005044400400u, 0x0000000014000100u, 0x0404440414000000u,
0222             0x5554100410000140u, 0x4555455544505555u, 0x5454105055455455u, 0x0115454155454015u,
0223             0x4404110000045100u, 0x4400001100101501u, 0x6596955956966a94u, 0x0040655955665965u,
0224             0x5554144400100155u, 0xa549495401011041u, 0x5596555565955555u, 0x5569965959549555u,
0225             0x969565a655555456u, 0x0000001000000000u, 0x0000000040000140u, 0x0000040100000000u,
0226             0x1415454400000000u, 0x5410415411454114u, 0x0400040104000154u, 0x0504045000000411u,
0227             0x0000001000000010u, 0x5554000000001040u, 0x5549155551556595u, 0x1455541055515555u,
0228             0x0510555454554541u, 0x9555555555540455u, 0x6455456555556465u, 0x4524565555654514u,
0229             0x5554655255559545u, 0x9555455441155556u, 0x0000000051515555u, 0x0010005040000550u,
0230             0x5044044040000000u, 0x1045040440010500u, 0x0000400000040000u, 0x0000000000000000u
0231     };
0232
0233     static constexpr uint64_t GENERIC_POW5_INV_SPLIT[89][4] = {
0234             {0u,                    0u,                    0u,                    144115188075855872u},
0235             {1573859546583440065u,  2691002611772552616u,  6763753280790178510u,  141347765182270746u},
0236             {12960290449513840412u, 12345512957918226762u, 18057899791198622765u, 138633484706040742u},
0237             {7615871757716765416u,  9507132263365501332u,  4879801712092008245u,  135971326161092377u},
0238             {7869961150745287587u,  5804035291554591636u,  8883897266325833928u,  133360288657597085u},
0239             {2942118023529634767u,  15128191429820565086u, 10638459445243230718u, 130799390525667397u},
0240             {14188759758411913794u, 5362791266439207815u,  8068821289119264054u,  128287668946279217u},
0241             {7183196927902545212u,  1952291723540117099u,  12075928209936341512u, 125824179589281448u},
0242             {5672588001402349748u,  17892323620748423487u, 9874578446960390364u,  123407996258356868u},
0243             {4442590541217566325u,  4558254706293456445u,  10343828952663182727u, 121038210542800766u},
0244             {3005560928406962566u,  2082271027139057888u,  13961184524927245081u, 118713931475986426u},
0245             {13299058168408384786u, 17834349496131278595u, 9029906103900731664u,  116434285200389047u},
0246             {5414878118283973035u,  13079825470227392078u, 17897304791683760280u, 114198414639042157u},
0247             {14609755883382484834u, 14991702445765844156u, 3269802549772755411u,  112005479173303009u},
0248             {15967774957605076027u, 2511532636717499923u,  16221038267832563171u, 109854654326805788u},
0249             {9269330061621627145u,  3332501053426257392u,  16223281189403734630u, 107745131455483836u},
0250             {16739559299223642282u, 1873986623300664530u,  6546709159471442872u,  105676117443544318u},
0251             {17116435360051202055u, 1359075105581853924u,  2038341371621886470u,  103646834405281051u},
0252             {17144715798009627550u, 3201623802661132408u,  9757551605154622431u,  101656519392613377u},
0253             {17580479792687825857u, 6546633380567327312u,  15099972427870912398u, 99704424108241124u},
0254             {9726477118325522902u,  14578369026754005435u, 11728055595254428803u, 97789814624307808u},
0255             {134593949518343635u,   5715151379816901985u,  1660163707976377376u,  95911971106466306u},
0256             {5515914027713859358u,  7124354893273815720u,  5548463282858794077u,  94070187543243255u},
0257             {6188403395862945512u,  5681264392632320838u,  15417410852121406654u, 92263771480600430u},
0258             {15908890877468271457u, 10398888261125597540u, 4817794962769172309u,  90492043761593298u},
0259             {1413077535082201005u,  12675058125384151580u, 7731426132303759597u,  88754338271028867u},
0260             {1486733163972670293u,  11369385300195092554u, 11610016711694864110u, 87050001685026843u},
0261             {8788596583757589684u,  3978580923851924802u,  9255162428306775812u,  85378393225389919u},
0262             {7203518319660962120u,  15044736224407683725u, 2488132019818199792u,  83738884418690858u},
0263             {4004175967662388707u,  18236988667757575407u, 15613100370957482671u, 82130858859985791u},
0264             {18371903370586036463u, 53497579022921640u,    16465963977267203307u, 80553711981064899u},
0265             {10170778323887491315u, 1999668801648976001u,  10209763593579456445u, 79006850823153334u},
0266             {17108131712433974546u, 16825784443029944237u, 2078700786753338945u,  77489693813976938u},
0267             {17221789422665858532u, 12145427517550446164u, 5391414622238668005u,  76001670549108934u},
0268             {4859588996898795878u,  1715798948121313204u,  3950858167455137171u,  74542221577515387u},
0269             {13513469241795711526u, 631367850494860526u,   10517278915021816160u, 73110798191218799u},
0270             {11757513142672073111u, 2581974932255022228u,  17498959383193606459u, 143413724438001539u},
0271             {14524355192525042817u, 5640643347559376447u,  1309659274756813016u,  140659771648132296u},
0272             {2765095348461978538u,  11021111021896007722u, 3224303603779962366u,  137958702611185230u},
0273             {12373410389187981037u, 13679193545685856195u, 11644609038462631561u, 135309501808182158u},
0274             {12813176257562780151u, 3754199046160268020u,  9954691079802960722u,  132711173221007413u},
0275             {17557452279667723458u, 3237799193992485824u,  17893947919029030695u, 130162739957935629u},
0276             {14634200999559435155u, 4123869946105211004u,  6955301747350769239u,  127663243886350468u},
0277             {2185352760627740240u,  2864813346878886844u,  13049218671329690184u, 125211745272516185u},
0278             {6143438674322183002u,  10464733336980678750u, 6982925169933978309u,  122807322428266620u},
0279             {1099509117817174576u,  10202656147550524081u, 754997032816608484u,   120449071364478757u},
0280             {2410631293559367023u,  17407273750261453804u, 15307291918933463037u, 118136105451200587u},
0281             {12224968375134586697u, 1664436604907828062u,  11506086230137787358u, 115867555084305488u},
0282             {3495926216898000888u,  18392536965197424288u, 10992889188570643156u, 113642567358547782u},
0283             {8744506286256259680u,  3966568369496879937u,  18342264969761820037u, 111460305746896569u},
0284             {7689600520560455039u,  5254331190877624630u,  9628558080573245556u,  109319949786027263u},
0285             {11862637625618819436u, 3456120362318976488u,  14690471063106001082u, 107220694767852583u},
0286             {5697330450030126444u,  12424082405392918899u, 358204170751754904u,   105161751436977040u},
0287             {11257457505097373622u, 15373192700214208870u, 671619062372033814u,   103142345693961148u},
0288             {16850355018477166700u, 1913910419361963966u,  4550257919755970531u,  101161718304283822u},
0289             {9670835567561997011u,  10584031339132130638u, 3060560222974851757u,  99219124612893520u},
0290             {7698686577353054710u,  11689292838639130817u, 11806331021588878241u, 97313834264240819u},
0291             {12233569599615692137u, 3347791226108469959u,  10333904326094451110u, 95445130927687169u},
0292             {13049400362825383933u, 17142621313007799680u, 3790542585289224168u,  93612312028186576u},
0293             {12430457242474442072u, 5625077542189557960u,  14765055286236672238u, 91814688482138969u},
0294             {4759444137752473128u,  2230562561567025078u,  4954443037339580076u,  90051584438315940u},
0295             {7246913525170274758u,  8910297835195760709u,  4015904029508858381u,  88322337023761438u},
0296             {12854430245836432067u, 8135139748065431455u,  11548083631386317976u, 86626296094571907u},
0297             {4848827254502687803u,  4789491250196085625u,  3988192420450664125u,  84962823991462151u},
0298             {7435538409611286684u,  904061756819742353u,   14598026519493048444u, 83331295300025028u},
0299             {11042616160352530997u, 8948390828345326218u,  10052651191118271927u, 81731096615594853u},
0300             {11059348291563778943u, 11696515766184685544u, 3783210511290897367u,  80161626312626082u},
0301             {7020010856491885826u,  5025093219346041680u,  8960210401638911765u,  78622294318500592u},
0302             {17732844474490699984u, 7820866704994446502u,  6088373186798844243u,  77112521891678506u},
0303             {688278527545590501u,   3045610706602776618u,  8684243536999567610u,  75631741404109150u},
0304             {2734573255120657297u,  3903146411440697663u,  9470794821691856713u,  74179396127820347u},
0305             {15996457521023071259u, 4776627823451271680u,  12394856457265744744u, 72754940025605801u},
0306             {13492065758834518331u, 7390517611012222399u,  1630485387832860230u,  142715675091463768u},
0307             {13665021627282055864u, 9897834675523659302u,  17907668136755296849u, 139975126841173266u},
0308             {9603773719399446181u,  10771916301484339398u, 10672699855989487527u, 137287204938390542u},
0309             {3630218541553511265u,  8139010004241080614u,  2876479648932814543u,  134650898807055963u},
0310             {8318835909686377084u,  9525369258927993371u,  2796120270400437057u,  132065217277054270u},
0311             {11190003059043290163u, 12424345635599592110u, 12539346395388933763u, 129529188211565064u},
0312             {8701968833973242276u,  820569587086330727u,   2315591597351480110u,  127041858141569228u},
0313             {5115113890115690487u,  16906305245394587826u, 9899749468931071388u,  124602291907373862u},
0314             {15543535488939245974u, 10945189844466391399u, 3553863472349432246u,  122209572307020975u},
0315             {7709257252608325038u,  1191832167690640880u,  15077137020234258537u, 119862799751447719u},
0316             {7541333244210021737u,  9790054727902174575u,  5160944773155322014u,  117561091926268545u},
0317             {12297384708782857832u, 1281328873123467374u,  4827925254630475769u,  115303583460052092u},
0318             {13243237906232367265u, 15873887428139547641u, 3607993172301799599u,  113089425598968120u},
0319             {11384616453739611114u, 15184114243769211033u, 13148448124803481057u, 110917785887682141u},
0320             {17727970963596660683u, 1196965221832671990u,  14537830463956404138u, 108787847856377790u},
0321             {17241367586707330931u, 8880584684128262874u,  11173506540726547818u, 106698810713789254u},
0322             {7184427196661305643u,  14332510582433188173u, 14230167953789677901u, 104649889046128358u}
0323     };
0324
0325     static constexpr uint64_t POW5_INV_ERRORS[154] = {
0326             0x1144155514145504u, 0x0000541555401141u, 0x0000000000000000u, 0x0154454000000000u,
0327             0x4114105515544440u, 0x0001001111500415u, 0x4041411410011000u, 0x5550114515155014u,
0328             0x1404100041554551u, 0x0515000450404410u, 0x5054544401140004u, 0x5155501005555105u,
0329             0x1144141000105515u, 0x0541500000500000u, 0x1104105540444140u, 0x4000015055514110u,
0330             0x0054010450004005u, 0x4155515404100005u, 0x5155145045155555u, 0x1511555515440558u,
0331             0x5558544555515555u, 0x0000000000000010u, 0x5004000000000050u, 0x1415510100000010u,
0332             0x4545555444514500u, 0x5155151555555551u, 0x1441540144044554u, 0x5150104045544400u,
0333             0x5450545401444040u, 0x5554455045501400u, 0x4655155555555145u, 0x1000010055455055u,
0334             0x1000004000055004u, 0x4455405104000005u, 0x4500114504150545u, 0x0000000014000000u,
0335             0x5450000000000000u, 0x5514551511445555u, 0x4111501040555451u, 0x4515445500054444u,
0336             0x5101500104100441u, 0x1545115155545055u, 0x0000000000000000u, 0x1554000000100000u,
0337             0x5555545595551555u, 0x5555051851455955u, 0x5555555555555559u, 0x0000400011001555u,
0338             0x0000004400040000u, 0x5455511555554554u, 0x5614555544115445u, 0x6455156145555155u,
0339             0x5455855455415455u, 0x5515555144555545u, 0x0114400000145155u, 0x0000051000450511u,
0340             0x4455154554445100u, 0x4554150141544455u, 0x65955555559a5965u, 0x5555555854559559u,
0341             0x9569654559616595u, 0x1040044040005565u, 0x1010010500011044u, 0x1554015545154540u,
0342             0x4440555401545441u, 0x1014441450550105u, 0x4545400410504145u, 0x5015111541040151u,
0343             0x5145051154000410u, 0x1040001044545044u, 0x4001400000151410u, 0x0540000044040000u,
0344             0x0510555454411544u, 0x0400054054141550u, 0x1001041145001100u, 0x0000000140000000u,
0345             0x0000000014100000u, 0x1544005454000140u, 0x4050055505445145u, 0x0011511104504155u,
0346             0x5505544415045055u, 0x1155154445515554u, 0x0000000000004555u, 0x0000000000000000u,
0347             0x5101010510400004u, 0x1514045044440400u, 0x5515519555515555u, 0x4554545441555545u,
0348             0x1551055955551515u, 0x0150000011505515u, 0x0044005040400000u, 0x0004001004010050u,
0349             0x0000051004450414u, 0x0114001101001144u, 0x0401000001000001u, 0x4500010001000401u,
0350             0x0004100000005000u, 0x0105000441101100u, 0x0455455550454540u, 0x5404050144105505u,
0351             0x4101510540555455u, 0x1055541411451555u, 0x5451445110115505u, 0x1154110010101545u,
0352             0x1145140450054055u, 0x5555565415551554u, 0x1550559555555555u, 0x5555541545045141u,
0353             0x4555455450500100u, 0x5510454545554555u, 0x1510140115045455u, 0x1001050040111510u,
0354             0x5555454555555504u, 0x9954155545515554u, 0x6596656555555555u, 0x0140410051555559u,
0355             0x0011104010001544u, 0x965669659a680501u, 0x5655a55955556955u, 0x4015111014404514u,
0356             0x1414155554505145u, 0x0540040011051404u, 0x1010000000015005u, 0x0010054050004410u,
0357             0x5041104014000100u, 0x4440010500100001u, 0x1155510504545554u, 0x0450151545115541u,
0358             0x4000100400110440u, 0x1004440010514440u, 0x0000115050450000u, 0x0545404455541500u,
0359             0x1051051555505101u, 0x5505144554544144u, 0x4550545555515550u, 0x0015400450045445u,
0360             0x4514155400554415u, 0x4555055051050151u, 0x1511441450001014u, 0x4544554510404414u,
0361             0x4115115545545450u, 0x5500541555551555u, 0x5550010544155015u, 0x0144414045545500u,
0362             0x4154050001050150u, 0x5550511111000145u, 0x1114504055000151u, 0x5104041101451040u,
0363             0x0010501401051441u, 0x0010501450504401u, 0x4554585440044444u, 0x5155555951450455u,
0364             0x0040000400105555u, 0x0000000000000001u,
0365     };
0366
0367 };
0368
0369 #if defined(BOOST_NO_CXX17_INLINE_VARIABLES) && (!defined(BOOST_MSVC) || BOOST_MSVC != 1900)
0370
0371 template <bool b> constexpr uint64_t ryu_tables_template<b>::GENERIC_POW5_TABLE[BOOST_CHARCONV_POW5_TABLE_SIZE][2];
0372 template <bool b> constexpr uint64_t ryu_tables_template<b>::GENERIC_POW5_SPLIT[89][4];
0373 template <bool b> constexpr uint64_t ryu_tables_template<b>::GENERIC_POW5_INV_SPLIT[89][4];
0374 template <bool b> constexpr uint64_t ryu_tables_template<b>::POW5_ERRORS[156];
0375 template <bool b> constexpr uint64_t ryu_tables_template<b>::POW5_INV_ERRORS[154];
0376
0377 #endif
0378
0379 #if (!defined(BOOST_MSVC) || BOOST_MSVC != 1900)
0380
0381 using ryu_tables = ryu_tables_template<true>;
0382
0383 #endif
0384
0385 // Returns e == 0 ? 1 : ceil(log_2(5^e)); requires 0 <= e <= 32768.
0386 static BOOST_CHARCONV_CXX14_CONSTEXPR uint32_t pow5bits(const uint32_t e) noexcept
0387 {
0388     BOOST_CHARCONV_ASSERT(e <= 1 << 15);
0389     return static_cast<uint32_t>(((e * UINT64_C(163391164108059)) >> 46) + 1);
0390 }
0391
0392 static BOOST_CHARCONV_CXX14_CONSTEXPR
0393 void mul_128_256_shift(
0394         const uint64_t* const a, const uint64_t* const b,
0395         const uint32_t shift, const uint32_t corr,
0396         uint64_t* const result) noexcept
0397 {
0398     BOOST_CHARCONV_ASSERT(shift > 0);
0399     BOOST_CHARCONV_ASSERT(shift < 256);
0400     const unsigned_128_type b00 = static_cast<unsigned_128_type>(a[0]) * b[0]; // 0
0401     const unsigned_128_type b01 = static_cast<unsigned_128_type>(a[0]) * b[1]; // 64
0402     const unsigned_128_type b02 = static_cast<unsigned_128_type>(a[0]) * b[2]; // 128
0403     const unsigned_128_type b03 = static_cast<unsigned_128_type>(a[0]) * b[3]; // 196
0404     const unsigned_128_type b10 = static_cast<unsigned_128_type>(a[1]) * b[0]; // 64
0405     const unsigned_128_type b11 = static_cast<unsigned_128_type>(a[1]) * b[1]; // 128
0406     const unsigned_128_type b12 = static_cast<unsigned_128_type>(a[1]) * b[2]; // 196
0407     const unsigned_128_type b13 = static_cast<unsigned_128_type>(a[1]) * b[3]; // 256
0408
0409     const unsigned_128_type s0 = b00;       // 0   x
0410     const unsigned_128_type s1 = b01 + b10; // 64  x
0411     const unsigned_128_type c1 = s1 < b01;  // 196 x
0412     const unsigned_128_type s2 = b02 + b11; // 128 x
0413     const unsigned_128_type c2 = s2 < b02;  // 256 x
0414     const unsigned_128_type s3 = b03 + b12; // 196 x
0415     const unsigned_128_type c3 = s3 < b03;  // 324 x
0416
0417     const unsigned_128_type p0 = s0 + (s1 << 64);                                // 0
0418     const unsigned_128_type d0 = p0 < b00;                                       // 128
0419     const unsigned_128_type q1 = s2 + (s1 >> 64) + (s3 << 64);                   // 128
0420     const unsigned_128_type d1 = q1 < s2;                                        // 256
0421     const unsigned_128_type p1 = q1 + (c1 << 64) + d0;                           // 128
0422     const unsigned_128_type d2 = p1 < q1;                                        // 256
0423     const unsigned_128_type p2 = b13 + (s3 >> 64) + c2 + (c3 << 64) + d1 + d2;   // 256
0424
0425     if (shift < 128)
0426     {
0427         const unsigned_128_type r0 = corr + ((p0 >> shift) | (p1 << (128 - shift)));
0428         const unsigned_128_type r1 = ((p1 >> shift) | (p2 << (128 - shift))) + (r0 < corr);
0429         result[0] = static_cast<uint64_t>(r0);
0430         result[1] = static_cast<uint64_t>(r0 >> 64);
0431         result[2] = static_cast<uint64_t>(r1);
0432         result[3] = static_cast<uint64_t>(r1 >> 64);
0433     }
0434     else if (shift == 128)
0435     {
0436         const unsigned_128_type r0 = corr + p1;
0437         const unsigned_128_type r1 = p2 + (r0 < corr);
0438         result[0] = static_cast<uint64_t>(r0);
0439         result[1] = static_cast<uint64_t>(r0 >> 64);
0440         result[2] = static_cast<uint64_t>(r1);
0441         result[3] = static_cast<uint64_t>(r1 >> 64);
0442     }
0443     else
0444     {
0445         const unsigned_128_type r0 = corr + ((p1 >> (shift - 128)) | (p2 << (256 - shift)));
0446         const unsigned_128_type r1 = (p2 >> (shift - 128)) + (r0 < corr);
0447         result[0] = static_cast<uint64_t>(r0);
0448         result[1] = static_cast<uint64_t>(r0 >> 64);
0449         result[2] = static_cast<uint64_t>(r1);
0450         result[3] = static_cast<uint64_t>(r1 >> 64);
0451     }
0452 }
0453
0454 // Computes 5^i in the form required by Ryu, and stores it in the given pointer.
0455 static BOOST_CXX14_CONSTEXPR void generic_computePow5(const uint32_t i, uint64_t* const result) noexcept
0456 {
0457     const uint32_t base = i / BOOST_CHARCONV_POW5_TABLE_SIZE;
0458     const uint32_t base2 = base * BOOST_CHARCONV_POW5_TABLE_SIZE;
0459     const uint64_t* const mul = ryu_tables::GENERIC_POW5_SPLIT[base];
0460     if (i == base2)
0461     {
0462         result[0] = mul[0];
0463         result[1] = mul[1];
0464         result[2] = mul[2];
0465         result[3] = mul[3];
0466     }
0467     else
0468     {
0469         const uint32_t offset = i - base2;
0470         const uint64_t* const m = ryu_tables::GENERIC_POW5_TABLE[offset];
0471         const uint32_t delta = pow5bits(i) - pow5bits(base2);
0472         const uint32_t corr = static_cast<uint32_t>((ryu_tables::POW5_ERRORS[i / 32] >> (2 * (i % 32))) & 3);
0473         mul_128_256_shift(m, mul, delta, corr, result);
0474     }
0475 }
0476
0477 // Computes 5^-i in the form required by Ryu, and stores it in the given pointer.
0478 static BOOST_CXX14_CONSTEXPR void generic_computeInvPow5(const uint32_t i, uint64_t* const result) noexcept
0479 {
0480     const uint32_t base = (i + BOOST_CHARCONV_POW5_TABLE_SIZE - 1) / BOOST_CHARCONV_POW5_TABLE_SIZE;
0481     const uint32_t base2 = base * BOOST_CHARCONV_POW5_TABLE_SIZE;
0482     const uint64_t* const mul = ryu_tables::GENERIC_POW5_INV_SPLIT[base]; // 1/5^base2
0483     if (i == base2)
0484     {
0485         result[0] = mul[0] + 1;
0486         result[1] = mul[1];
0487         result[2] = mul[2];
0488         result[3] = mul[3];
0489     }
0490     else
0491     {
0492         const uint32_t offset = base2 - i;
0493         const uint64_t* const m = ryu_tables::GENERIC_POW5_TABLE[offset]; // 5^offset
0494         const uint32_t delta = pow5bits(base2) - pow5bits(i);
0495         const uint32_t corr = static_cast<uint32_t>((ryu_tables::POW5_INV_ERRORS[i / 32] >> (2 * (i % 32))) & 3) + UINT32_C(1);
0496         mul_128_256_shift(m, mul, delta, corr, result);
0497     }
0498 }
0499
0500 static BOOST_CXX14_CONSTEXPR uint32_t pow5Factor(unsigned_128_type value) noexcept
0501 {
0502     for (uint32_t count = 0; value > 0; ++count)
0503     {
0504         if (value % 5 != 0)
0505         {
0506             return count;
0507         }
0508         value /= 5;
0509     }
0510     return 0;
0511 }
0512
0513 // Returns true if value is divisible by 5^p.
0514 static BOOST_CHARCONV_CXX14_CONSTEXPR bool multipleOfPowerOf5(const unsigned_128_type value, const uint32_t p) noexcept
0515 {
0516     // I tried a case distinction on p, but there was no performance difference.
0517     return pow5Factor(value) >= p;
0518 }
0519
0520 // Returns true if value is divisible by 2^p.
0521 static BOOST_CHARCONV_CXX14_CONSTEXPR bool multipleOfPowerOf2(const unsigned_128_type value, const uint32_t p) noexcept
0522 {
0523     return (value & ((static_cast<unsigned_128_type>(1) << p) - 1)) == 0;
0524 }
0525
0526 static BOOST_CHARCONV_CXX14_CONSTEXPR
0527 unsigned_128_type mulShift(const unsigned_128_type m, const uint64_t* const mul, const int32_t j) noexcept
0528 {
0529     BOOST_CHARCONV_ASSERT(j > 128);
0530     uint64_t a[2] {};
0531     a[0] = static_cast<uint64_t>(m);
0532     a[1] = static_cast<uint64_t>(m >> 64);
0533     uint64_t result[4] {};
0534     mul_128_256_shift(a, mul, static_cast<uint32_t>(j), 0, result);
0535     return (static_cast<unsigned_128_type>(result[1]) << 64) | result[0];
0536 }
0537
0538 // Returns floor(log_10(2^e)).
0539 static BOOST_CHARCONV_CXX14_CONSTEXPR uint32_t log10Pow2(const int32_t e) noexcept
0540 {
0541     // The first value this approximation fails for is 2^1651 which is just greater than 10^297.
0542     BOOST_CHARCONV_ASSERT(e >= 0);
0543     BOOST_CHARCONV_ASSERT(e <= 1 << 15);
0544     return static_cast<uint32_t>((static_cast<uint64_t>(e) * UINT64_C(169464822037455)) >> 49);
0545 }
0546
0547 // Returns floor(log_10(5^e)).
0548 static BOOST_CHARCONV_CXX14_CONSTEXPR uint32_t log10Pow5(const int32_t e) noexcept
0549 {
0550     // The first value this approximation fails for is 5^2621 which is just greater than 10^1832.
0551     assert(e >= 0);
0552     assert(e <= 1 << 15);
0553     return static_cast<uint32_t>((static_cast<uint64_t>(e) * UINT64_C(196742565691928)) >> 48);
0554 }
0555
0556 }}}} // Namespaces
0557
0558 #endif // BOOST_CHARCONV_DETAIL_RYU_GENERIC_128_HPP