schubfach.cc

// Implementation of the Schubfach algorithm:
// https://fmt.dev/papers/Schubfach4.pdf.
// Copyright (c) 2025 - present, Victor Zverovich
// Distributed under the MIT license (see LICENSE).

#include "schubfach.h"

#include <assert.h>  // assert
#include <stdint.h>  // uint64_t
#include <string.h>  // memcpy

#include <bit>     // std::bit_cast
#include <limits>  // std::numeric_limits

namespace {

struct uint128 {
  uint64_t hi;
  uint64_t lo;

  explicit operator uint64_t() const noexcept { return lo; }

  auto operator>>(int shift) const noexcept -> uint128 {
    assert(shift >= 64 && shift < 128);
    return {0, hi >> (shift - 64)};
  }
};

#ifdef __SIZEOF_INT128__
using uint128_t = unsigned __int128;
#else
using uint128_t = uint128;
#endif  // __SIZEOF_INT128__

// 126-bit significands of overestimates of powers of 10.
// Generated with gen-pow10.py.
const uint128 pow10_significands[] = {
    {0x7fbbd8fe5f5e6e27, 0x497a3a2704eec3df},  // -292
    {0x4fd5679efb9b04d8, 0x5dec645863153a6c},  // -291
    {0x63cac186ba81c60e, 0x75677d6e7bda8906},  // -290
    {0x7cbd71e869223792, 0x52c15cca1ad12b48},  // -289
    {0x4df6673141b562bb, 0x53b8d9fe50c2bb0d},  // -288
    {0x617400fd9222bb6a, 0x48a7107de4f369d0},  // -287
    {0x79d1013cf6ab6a45, 0x1ad0d49d5e304444},  // -286
    {0x4c22a0c61a2b226b, 0x20c284e25ade2aab},  // -285
    {0x5f2b48f7a0b5eb06, 0x08f3261af195b555},  // -284
    {0x76f61b3588e365c7, 0x4b2fefa1adfb22ab},  // -283
    {0x4a59d101758e1f9c, 0x5efdf5c50cbcf5ab},  // -282
    {0x5cf04541d2f1a783, 0x76bd73364fec3315},  // -281
    {0x742c569247ae1164, 0x746cd003e3e73fdb},  // -280
    {0x489bb61b6ccccadf, 0x08c402026e7087e9},  // -279
    {0x5ac2a3a247fffd96, 0x6af502830a0ca9e3},  // -278
    {0x71734c8ad9fffcfc, 0x45b24323cc8fd45c},  // -277
    {0x46e80fd6c83ffe1d, 0x6b8f69f65fd9e4b9},  // -276
    {0x58a213cc7a4ffda5, 0x26734473f7d05de8},  // -275
    {0x6eca98bf98e3fd0e, 0x50101590f5c47561},  // -274
    {0x453e9f77bf8e7e29, 0x120a0d7a999ac95d},  // -273
    {0x568e4755af721db3, 0x368c90d940017bb4},  // -272
    {0x6c31d92b1b4ea520, 0x242fb50f9001daa1},  // -271
    {0x439f27baf1112734, 0x169dd129ba0128a5},  // -270
    {0x5486f1a9ad557101, 0x1c454574288172ce},  // -269
    {0x69a8ae1418aacd41, 0x435696d132a1cf81},  // -268
    {0x42096ccc8f6ac048, 0x7a161e42bfa521b1},  // -267
    {0x528bc7ffb345705b, 0x189ba5d36f8e6a1d},  // -266
    {0x672eb9ffa016cc71, 0x7ec28f484b7204a4},  // -265
    {0x407d343fc40e3fc7, 0x1f39998d2f2742e7},  // -264
    {0x509c814fb511cfb9, 0x0707fff07af113a1},  // -263
    {0x64c3a1a3a25643a7, 0x28c9ffec99ad5889},  // -262
    {0x7df48a0c8aebd491, 0x12fc7fe7c018aeab},  // -261
    {0x4eb8d647d6d364da, 0x5bddcff0d80f6d2b},  // -260
    {0x62670bd9cc883e11, 0x32d543ed0e134875},  // -259
    {0x7b00ced03faa4d95, 0x5f8a94e851981a93},  // -258
    {0x4ce0814227ca707d, 0x4bb69d1132ff109c},  // -257
    {0x6018a192b1bd0c9c, 0x7ea444557fbed4c3},  // -256
    {0x781ec9f75e2c4fc4, 0x1e4d556adfae89f3},  // -255
    {0x4b133e3a9adbb1da, 0x52f05562cbcd1638},  // -254
    {0x5dd80dc941929e51, 0x27ac6abb7ec05bc6},  // -253
    {0x754e113b91f745e5, 0x5197856a5e7072b8},  // -252
    {0x4950cac53b3a8baf, 0x42feb3627b0647b3},  // -251
    {0x5ba4fd768a092e9b, 0x33be603b19c7d99f},  // -250
    {0x728e3cd42c8b7a42, 0x20adf849e039d007},  // -249
    {0x4798e6049bd72c69, 0x346cbb2e2c242205},  // -248
    {0x597f1f85c2ccf783, 0x6187e9f9b72d2a86},  // -247
    {0x6fdee76733803564, 0x59e9e47824f87527},  // -246
    {0x45eb50a08030215e, 0x78322ecb171b4939},  // -245
    {0x576624c8a03c29b6, 0x563eba7ddce21b87},  // -244
    {0x6d3fadfac84b3424, 0x2bce691d541aa268},  // -243
    {0x4447ccbcbd2f0096, 0x5b6101b25490a581},  // -242
    {0x5559bfebec7ac0bc, 0x3239421ee9b4cee1},  // -241
    {0x6ab02fe6e79970eb, 0x3ec792a6a422029a},  // -240
    {0x42ae1df050bfe693, 0x173cbba8269541a0},  // -239
    {0x5359a56c64efe037, 0x7d0bea92303a9208},  // -238
    {0x68300ec77e2bd845, 0x7c4ee536bc49368a},  // -237
    {0x411e093caedb672b, 0x5db14f4235adc217},  // -236
    {0x51658b8bda9240f6, 0x551da312c319329c},  // -235
    {0x65beee6ed136d134, 0x2a650bd773df7f43},  // -234
    {0x7f2eaa0a85848581, 0x34fe4ecd50d75f14},  // -233
    {0x4f7d2a469372d370, 0x711ef14052869b6c},  // -232
    {0x635c74d8384f884d, 0x0d66ad9067284247},  // -231
    {0x7c33920e46636a60, 0x30c058f480f252d9},  // -230
    {0x4da03b48ebfe227c, 0x1e783798d09773c8},  // -229
    {0x61084a1b26fdab1b, 0x2616457f04bd50ba},  // -228
    {0x794a5ca1f0bd15e2, 0x0f9bd6dec5eca4e8},  // -227
    {0x4bce79e536762dad, 0x29c1664b3bb3e711},  // -226
    {0x5ec2185e8413b918, 0x5431bfde0aa0e0d5},  // -225
    {0x76729e762518a75e, 0x693e2fd58d49190b},  // -224
    {0x4a07a309d72f689b, 0x21c6dde5784dafa7},  // -223
    {0x5c898bcc4cfb42c2, 0x0a38955ed6611b90},  // -222
    {0x73abeebf603a1372, 0x4cc6bab68bf96274},  // -221
    {0x484b75379c244c27, 0x4ffc34b2177bdd89},  // -220
    {0x5a5e5285832d5f31, 0x43fb41de9d5ad4eb},  // -219
    {0x70f5e726e3f8b6fd, 0x74fa125644b18a26},  // -218
    {0x4699b0784e7b725e, 0x591c4b75eaeef658},  // -217
    {0x58401c96621a4ef6, 0x2f635e5365aab3ed},  // -216
    {0x6e5023bbfaa0e2b3, 0x7b3c35e83f1560e9},  // -215
    {0x44f216557ca48db0, 0x3d05a1b1276d5c92},  // -214
    {0x562e9beadbcdb11c, 0x4c470a1d7148b3b6},  // -213
    {0x6bba42e592c11d63, 0x5f58cca4cd9ae0a3},  // -212
    {0x435469cf7bb8b25e, 0x2b977fe70080cc66},  // -211
    {0x542984435aa6def5, 0x767d5fe0c0a0ff80},  // -210
    {0x6933e554315096b3, 0x341cb7d8f0c93f5f},  // -209
    {0x41c06f549ed25e30, 0x1091f2e7967dc79c},  // -208
    {0x52308b29c686f5bc, 0x14b66fa17c1d3983},  // -207
    {0x66bcadf43828b32b, 0x19e40b89db2487e3},  // -206
    {0x4035ecb8a3196ffb, 0x002e873628f6d4ee},  // -205
    {0x504367e6cbdfcbf9, 0x603a2903b3348a2a},  // -204
    {0x645441e07ed7bef8, 0x1848b344a001acb4},  // -203
    {0x7d6952589e8daeb6, 0x1e5ae015c80217e1},  // -202
    {0x4e61d37763188d31, 0x72f8cc0d9d014eed},  // -201
    {0x61fa48553bdeb07e, 0x2fb6ff110441a2a8},  // -200
    {0x7a78da6a8ad65c9d, 0x7ba4bed545520b52},  // -199
    {0x4c8b888296c5f9e2, 0x5d46f7454b534713},  // -198
    {0x5fae6aa33c77785b, 0x3498b5169e2818d8},  // -197
    {0x779a054c0b955672, 0x21bee25c45b21f0e},  // -196
    {0x4ac0434f873d5607, 0x35174d79ab8f5369},  // -195
    {0x5d705423690cab89, 0x225d20d816732843},  // -194
    {0x74cc692c434fd66b, 0x4af4690e1c0ff253},  // -193
    {0x48ffc1bbaa11e603, 0x1ed8c1a8d189f774},  // -192
    {0x5b3fb22a94965f84, 0x068ef21305ec7551},  // -191
    {0x720f9eb539bbf765, 0x0832ae97c76792a5},  // -190
    {0x4749c33144157a9f, 0x151fad1edca0bba8},  // -189
    {0x591c33fd951ad946, 0x7a67986693c8ea91},  // -188
    {0x6f6340fcfa618f98, 0x59017e8038bb2536},  // -187
    {0x459e089e1c7cf9bf, 0x37a0ef102374f742},  // -186
    {0x57058ac5a39c382f, 0x25892ad42c523512},  // -185
    {0x6cc6ed770c83463b, 0x0eeb75893766c256},  // -184
    {0x43fc546a67d20be4, 0x79532975c2a03976},  // -183
    {0x54fb698501c68ede, 0x17a7f3d3334847d4},  // -182
    {0x6a3a43e642383295, 0x5d91f0c8001a59c8},  // -181
    {0x42646a6fe9631f9d, 0x4a7b367d0010781d},  // -180
    {0x52fd850be3bbe784, 0x7d1a041c40149625},  // -179
    {0x67bce64edcaae166, 0x1c6085235019bbae},  // -178
    {0x40d60ff149eaccdf, 0x71bc53361210154d},  // -177
    {0x510b93ed9c658017, 0x6e2b680396941aa0},  // -176
    {0x654e78e9037ee01d, 0x69b642047c392148},  // -175
    {0x7ea21723445e9825, 0x2423d2859b476999},  // -174
    {0x4f254e760abb1f17, 0x26966393810ca200},  // -173
    {0x62eea2138d69e6dd, 0x103bfc78614fca80},  // -172
    {0x7baa4a9870c46094, 0x344afb9679a3bd20},  // -171
    {0x4d4a6e9f467abc5c, 0x60aedd3e0c065634},  // -170
    {0x609d0a4718196b73, 0x78da948d8f07ebc1},  // -169
    {0x78c44cd8de1fc650, 0x771139b0f2c9e6b1},  // -168
    {0x4b7ab0078ad3dbf2, 0x4a6ac40e97be302f},  // -167
    {0x5e595c096d88d2ef, 0x1d0575123dadbc3a},  // -166
    {0x75efb30bc8eb07ab, 0x0446d256cd192b49},  // -165
    {0x49b5cfe75d92e4ca, 0x72ac4376402fbb0e},  // -164
    {0x5c2343e134f79dfd, 0x4f575453d03ba9d1},  // -163
    {0x732c14d98235857d, 0x032d2968c44a9445},  // -162
    {0x47fb8d07f161736e, 0x11fc39e17aae9cab},  // -161
    {0x59fa7049edb9d049, 0x567b4859d95a43d6},  // -160
    {0x70790c5c6928445c, 0x0c1a1a704fb0d4cc},  // -159
    {0x464ba7b9c1b92ab9, 0x4790508631ce84ff},  // -158
    {0x57de91a832277567, 0x797464a7be42263f},  // -157
    {0x6dd636123eb152c1, 0x77d17dd1add2afcf},  // -156
    {0x44a5e1cb672ed3b9, 0x1ae2eea30ca3ade1},  // -155
    {0x55cf5a3e40fa88a7, 0x419baa4bcfcc995a},  // -154
    {0x6b4330cdd1392ad1, 0x320294dec3bfbfb0},  // -153
    {0x4309fe80a2c3bac2, 0x6f419d0b3a57d7ce},  // -152
    {0x53cc7e20cb74a973, 0x4b12044e08edcdc2},  // -151
    {0x68bf9da8fe51d3d0, 0x3dd685618b294132},  // -150
    {0x4177c2899ef32462, 0x26a6135cf6f9c8bf},  // -149
    {0x51d5b32c06afed7a, 0x704f983434b83aef},  // -148
    {0x664b1ff7085be8d9, 0x4c637e4141e649ab},  // -147
    {0x7fdde7f4ca72e30f, 0x7f7c5dd1925fdc15},  // -146
    {0x4feab0f8fe87cde9, 0x7fadbaa2fb7be98d},  // -145
    {0x63e55d373e29c164, 0x3f99294bba5ae3f1},  // -144
    {0x7cdeb4850db431bd, 0x4f7f739ea8f19ced},  // -143
    {0x4e0b30d328909f16, 0x41afa84329970214},  // -142
    {0x618dfd07f2b4c6dc, 0x121b9253f3fcc299},  // -141
    {0x79f17c49ef61f893, 0x16a276e8f0fbf33f},  // -140
    {0x4c36edae359d3b5b, 0x7e258a51969d7808},  // -139
    {0x5f44a919c3048a32, 0x7daeece5fc44d609},  // -138
    {0x7715d36033c5acbf, 0x5d1aa81f7b560b8c},  // -137
    {0x4a6da41c205b8bf7, 0x6a30a913ad15c738},  // -136
    {0x5d090d2328726ef5, 0x64bcd358985b3905},  // -135
    {0x744b506bf28f0ab3, 0x1dec082ebe720746},  // -134
    {0x48af1243779966b0, 0x02b3851d3707448c},  // -133
    {0x5adad6d4557fc05c, 0x0360666484c915af},  // -132
    {0x71918c896adfb073, 0x04387ffda5fb5b1b},  // -131
    {0x46faf7d5e2cbce47, 0x72a34ffe87bd18f1},  // -130
    {0x58b9b5cb5b7ec1d9, 0x6f4c23fe29ac5f2d},  // -129
    {0x6ee8233e325e7250, 0x2b1f2cfdb41776f8},  // -128
    {0x45511606df7b0772, 0x1af37c1e908eaa5b},  // -127
    {0x56a55b889759c94e, 0x61b05b2634b254f2},  // -126
    {0x6c4eb26abd303ba2, 0x3a1c71efc1deea2e},  // -125
    {0x43b12f82b63e2545, 0x4451c735d92b525d},  // -124
    {0x549d7b6363cdae96, 0x756639034f7626f4},  // -123
    {0x69c4da3c3cc11a3c, 0x52bfc7442353b0b1},  // -122
    {0x421b0865a5f8b065, 0x73b7dc8a96144e6f},  // -121
    {0x52a1ca7f0f76dc7f, 0x30a5d3ad3b99620b},  // -120
    {0x674a3d1ed354939f, 0x1ccf48988a7fba8d},  // -119
    {0x408e66334414dc43, 0x42018d5f568fd498},  // -118
    {0x50b1ffc0151a1354, 0x3281f0b72c33c9be},  // -117
    {0x64de7fb01a609829, 0x3f226ce4f740bc2e},  // -116
    {0x7e161f9c20f8be33, 0x6eeb081e3510eb39},  // -115
    {0x4ecdd3c1949b76e0, 0x3552e512e12a9304},  // -114
    {0x628148b1f9c25498, 0x42a79e57997537c5},  // -113
    {0x7b219ade7832e9be, 0x535185ed7fd285b6},  // -112
    {0x4cf500cb0b1fd217, 0x1412f3b46fe39392},  // -111
    {0x603240fdcde7c69c, 0x7917b0a18bdc7876},  // -110
    {0x783ed13d4161b844, 0x175d9cc9eed39694},  // -109
    {0x4b2742c648dd132a, 0x4e9a81fe35443e1c},  // -108
    {0x5df11377db1457f5, 0x2241227dc2954da3},  // -107
    {0x756d5855d1d96df2, 0x4ad16b1d333aa10c},  // -106
    {0x49645735a327e4b7, 0x4ec2e2f24004a4a8},  // -105
    {0x5bbd6d030bf1dde5, 0x42739baed005cdd2},  // -104
    {0x72acc843ceee555e, 0x7310829a84074146},  // -103
    {0x47abfd2a6154f55b, 0x27ea51a0928488cc},  // -102
    {0x5996fc74f9aa32b2, 0x11e4e608b725aaff},  // -101
    {0x6ffcbb923814bf5e, 0x565e1f8ae4ef15be},  // -100
    {0x45fdf53b630cf79b, 0x15fad3b6cf156d97},  //  -99
    {0x577d728a3bd03581, 0x7b7988a482dac8fd},  //  -98
    {0x6d5ccf2ccac442e2, 0x3a57eacda3917b3c},  //  -97
    {0x445a017bfebaa9cd, 0x4476f2c0863aed06},  //  -96
    {0x557081dafe695440, 0x7594af70a7c9a847},  //  -95
    {0x6acca251be03a951, 0x12f9db4cd1bc1258},  //  -94
    {0x42bfe57316c249d2, 0x5bdc291003158b77},  //  -93
    {0x536fdecfdc72dc47, 0x32d3335403daee55},  //  -92
    {0x684bd683d38f9359, 0x1f88002904d1a9ea},  //  -91
    {0x412f66126439bc17, 0x63b50019a3030a33},  //  -90
    {0x517b3f96fd482b1d, 0x5ca240200bc3ccbf},  //  -89
    {0x65da0f7cbc9a35e5, 0x13cad0280eb4bfef},  //  -88
    {0x7f50935bebc0c35e, 0x38bd84321261efeb},  //  -87
    {0x4f925c1973587a1b, 0x0376729f4b7d35f3},  //  -86
    {0x6376f31fd02e98a1, 0x64540f471e5c836f},  //  -85
    {0x7c54afe7c43a3eca, 0x1d691318e5f3a44b},  //  -84
    {0x4db4edf0daa4673e, 0x3261abef8fb846af},  //  -83
    {0x6122296d114d810d, 0x7efa16eb73a6585b},  //  -82
    {0x796ab3c855a0e151, 0x3eb89ca6508fee71},  //  -81
    {0x4be2b05d35848cd2, 0x773361e7f259f507},  //  -80
    {0x5edb5c7482e5b007, 0x55003a61eef07249},  //  -79
    {0x76923391a39f1c09, 0x4a4048fa6aac8edb},  //  -78
    {0x4a1b603b06437185, 0x7e682d9c82abd949},  //  -77
    {0x5ca23849c7d44de7, 0x3e023903a356cf9b},  //  -76
    {0x73cac65c39c96161, 0x2d82c7448c2c8382},  //  -75
    {0x485ebbf9a41ddcdc, 0x6c71bc8ad79bd231},  //  -74
    {0x5a766af80d255414, 0x078e2bad8d82c6bd},  //  -73
    {0x711405b6106ea919, 0x0971b698f0e3786d},  //  -72
    {0x46ac8391ca4529af, 0x55e7121f968e2b44},  //  -71
    {0x5857a4763cd6741b, 0x4b60d6a77c31b615},  //  -70
    {0x6e6d8d93cc0c1122, 0x3e390c515b3e239a},  //  -69
    {0x4504787c5f878ab5, 0x46e3a7b2d906d640},  //  -68
    {0x5645969b77696d62, 0x789c919f8f488bd0},  //  -67
    {0x6bd6fc425543c8bb, 0x56c3b607731aaec4},  //  -66
    {0x43665da9754a5d75, 0x263a51c4a7f0ad3b},  //  -65
    {0x543ff513d29cf4d2, 0x4fc8e635d1ecd88a},  //  -64
    {0x694ff258c7443207, 0x23bb1fc346680eac},  //  -63
    {0x41d1f7777c8a9f44, 0x4654f3da0c01092c},  //  -62
    {0x524675555bad4715, 0x57ea30d08f014b76},  //  -61
    {0x66d812aab29898db, 0x0de4bd04b2c19e54},  //  -60
    {0x40470baaaf9f5f88, 0x78aef622efb902f5},  //  -59
    {0x5058ce955b87376b, 0x16dab3ababa743b2},  //  -58
    {0x646f023ab2690545, 0x7c9160969691149e},  //  -57
    {0x7d8ac2c95f034697, 0x3bb5b8bc3c3559c5},  //  -56
    {0x4e76b9bddb620c1e, 0x55519375a5a1581b},  //  -55
    {0x6214682d523a8f26, 0x2aa5f8530f09ae22},  //  -54
    {0x7a998238a6c932ef, 0x754f7667d2cc19ab},  //  -53
    {0x4c9ff163683dbfd5, 0x7951aa00e3bf900b},  //  -52
    {0x5fc7edbc424d2fcb, 0x37a614811caf740d},  //  -51
    {0x77b9e92b52e07bbe, 0x258f99a163db5111},  //  -50
    {0x4ad431bb13cc4d56, 0x7779c004de6912ab},  //  -49
    {0x5d893e29d8bf60ac, 0x5558300616035755},  //  -48
    {0x74eb8db44eef38d7, 0x6aae3c079b842d2a},  //  -47
    {0x49133890b1558386, 0x72ace584c1329c3b},  //  -46
    {0x5b5806b4ddaae468, 0x4f581ee5f17f4349},  //  -45
    {0x722e086215159d82, 0x632e269f6ddf141b},  //  -44
    {0x475cc53d4d2d8271, 0x5dfcd823a4ab6c91},  //  -43
    {0x5933f68ca078e30e, 0x157c0e2c8dd647b5},  //  -42
    {0x6f80f42fc8971bd1, 0x5adb11b7b14bd9a3},  //  -41
    {0x45b0989ddd5e7163, 0x08c8eb12cecf6806},  //  -40
    {0x571cbec554b60dbb, 0x6afb25d782834207},  //  -39
    {0x6ce3ee76a9e3912a, 0x65b9ef4d63241289},  //  -38
    {0x440e750a2a2e3aba, 0x5f9435905df68b96},  //  -37
    {0x5512124cb4b9c969, 0x377942f475742e7b},  //  -36
    {0x6a5696dfe1e83bc3, 0x655793b192d13a1a},  //  -35
    {0x42761e4bed31255a, 0x2f56bc4efbc2c450},  //  -34
    {0x5313a5dee87d6eb0, 0x7b2c6b62bab37564},  //  -33
    {0x67d88f56a29cca5d, 0x19f7863b696052bd},  //  -32
    {0x40e7599625a1fe7a, 0x203ab3e521dc33b6},  //  -31
    {0x51212ffbaf0a7e18, 0x684960de6a5340a4},  //  -30
    {0x65697bfa9acd1d9f, 0x025bb91604e810cd},  //  -29
    {0x7ec3daf941806506, 0x62f2a75b86221500},  //  -28
    {0x4f3a68dbc8f03f24, 0x1dd7a89933d54d20},  //  -27
    {0x63090312bb2c4eed, 0x254d92bf80caa068},  //  -26
    {0x7bcb43d769f762a8, 0x4ea0f76f60fd4882},  //  -25
    {0x4d5f0a66a23a9da9, 0x31249aa59c9e4d51},  //  -24
    {0x60b6cd004ac94513, 0x5d6dc14f03c5e0a5},  //  -23
    {0x78e480405d7b9658, 0x54c931a2c4b758cf},  //  -22
    {0x4b8ed0283a6d3df7, 0x34fdbf05baf29781},  //  -21
    {0x5e72843249088d75, 0x223d2ec729af3d62},  //  -20
    {0x760f253edb4ab0d2, 0x4acc7a78f41b0cba},  //  -19
    {0x49c97747490eae83, 0x4ebfcc8b9890e7f4},  //  -18
    {0x5c3bd5191b525a24, 0x426fbfae7eb521f1},  //  -17
    {0x734aca5f6226f0ad, 0x530baf9a1e626a6d},  //  -16
    {0x480ebe7b9d58566c, 0x43e74dc052fd8285},  //  -15
    {0x5a126e1a84ae6c07, 0x54e1213067bce326},  //  -14
    {0x709709a125da0709, 0x4a19697c81ac1bef},  //  -13
    {0x465e6604b7a84465, 0x7e4fe1edd10b9175},  //  -12
    {0x57f5ff85e592557f, 0x3de3da69454e75d3},  //  -11
    {0x6df37f675ef6eadf, 0x2d5cd10396a21347},  //  -10
    {0x44b82fa09b5a52cb, 0x4c5a02a23e254c0d},  //   -9
    {0x55e63b88c230e77e, 0x3f70834acdae9f10},  //   -8
    {0x6b5fca6af2bd215e, 0x0f4ca41d811a46d4},  //   -7
    {0x431bde82d7b634da, 0x698fe69270b06c44},  //   -6
    {0x53e2d6238da3c211, 0x43f3e0370cdc8755},  //   -5
    {0x68db8bac710cb295, 0x74f0d844d013a92b},  //   -4
    {0x4189374bc6a7ef9d, 0x5916872b020c49bb},  //   -3
    {0x51eb851eb851eb85, 0x0f5c28f5c28f5c29},  //   -2
    {0x6666666666666666, 0x3333333333333334},  //   -1
    {0x4000000000000000, 0x0000000000000001},  //    0
    {0x5000000000000000, 0x0000000000000001},  //    1
    {0x6400000000000000, 0x0000000000000001},  //    2
    {0x7d00000000000000, 0x0000000000000001},  //    3
    {0x4e20000000000000, 0x0000000000000001},  //    4
    {0x61a8000000000000, 0x0000000000000001},  //    5
    {0x7a12000000000000, 0x0000000000000001},  //    6
    {0x4c4b400000000000, 0x0000000000000001},  //    7
    {0x5f5e100000000000, 0x0000000000000001},  //    8
    {0x7735940000000000, 0x0000000000000001},  //    9
    {0x4a817c8000000000, 0x0000000000000001},  //   10
    {0x5d21dba000000000, 0x0000000000000001},  //   11
    {0x746a528800000000, 0x0000000000000001},  //   12
    {0x48c2739500000000, 0x0000000000000001},  //   13
    {0x5af3107a40000000, 0x0000000000000001},  //   14
    {0x71afd498d0000000, 0x0000000000000001},  //   15
    {0x470de4df82000000, 0x0000000000000001},  //   16
    {0x58d15e1762800000, 0x0000000000000001},  //   17
    {0x6f05b59d3b200000, 0x0000000000000001},  //   18
    {0x4563918244f40000, 0x0000000000000001},  //   19
    {0x56bc75e2d6310000, 0x0000000000000001},  //   20
    {0x6c6b935b8bbd4000, 0x0000000000000001},  //   21
    {0x43c33c1937564800, 0x0000000000000001},  //   22
    {0x54b40b1f852bda00, 0x0000000000000001},  //   23
    {0x69e10de76676d080, 0x0000000000000001},  //   24
    {0x422ca8b0a00a4250, 0x0000000000000001},  //   25
    {0x52b7d2dcc80cd2e4, 0x0000000000000001},  //   26
    {0x6765c793fa10079d, 0x0000000000000001},  //   27
    {0x409f9cbc7c4a04c2, 0x1000000000000001},  //   28
    {0x50c783eb9b5c85f2, 0x5400000000000001},  //   29
    {0x64f964e68233a76f, 0x2900000000000001},  //   30
    {0x7e37be2022c0914b, 0x1340000000000001},  //   31
    {0x4ee2d6d415b85ace, 0x7c08000000000001},  //   32
    {0x629b8c891b267182, 0x5b0a000000000001},  //   33
    {0x7b426fab61f00de3, 0x31cc800000000001},  //   34
    {0x4d0985cb1d3608ae, 0x0f1fd00000000001},  //   35
    {0x604be73de4838ad9, 0x52e7c40000000001},  //   36
    {0x785ee10d5da46d90, 0x07a1b50000000001},  //   37
    {0x4b3b4ca85a86c47a, 0x04c5112000000001},  //   38
    {0x5e0a1fd271287598, 0x45f6556800000001},  //   39
    {0x758ca7c70d7292fe, 0x5773eac200000001},  //   40
    {0x4977e8dc68679bdf, 0x16a872b940000001},  //   41
    {0x5bd5e313828182d6, 0x7c528f6790000001},  //   42
    {0x72cb5bd86321e38c, 0x5b67334174000001},  //   43
    {0x47bf19673df52e37, 0x79208008e8800001},  //   44
    {0x59aedfc10d7279c5, 0x7768a00b22a00001},  //   45
    {0x701a97b150cf1837, 0x3542c80deb480001},  //   46
    {0x46109eced2816f22, 0x5149bd08b30d0001},  //   47
    {0x5794c6828721caeb, 0x259c2c4adfd04001},  //   48
    {0x6d79f82328ea3da6, 0x0f03375d97c45001},  //   49
    {0x446c3b15f9926687, 0x6962029a7edab201},  //   50
    {0x558749db77f70029, 0x63ba83411e915e81},  //   51
    {0x6ae91c5255f4c034, 0x1ca924116635b621},  //   52
    {0x42d1b1b375b8f820, 0x51e9b68adfe191d5},  //   53
    {0x53861e2053273628, 0x6664242d97d9f64a},  //   54
    {0x6867a5a867f103b2, 0x7ffd2d38fdd073dc},  //   55
    {0x4140c78940f6a24f, 0x6ffe3c439ea2486a},  //   56
    {0x5190f96b91344ae3, 0x6bfdcb54864ada84},  //   57
    {0x65f537c675815d9c, 0x66fd3e29a7dd9125},  //   58
    {0x7f7285b812e1b504, 0x00bc8db411d4f56e},  //   59
    {0x4fa793930bcd1122, 0x4075d8908b251965},  //   60
    {0x63917877cec0556b, 0x10934eb4adee5fbe},  //   61
    {0x7c75d695c2706ac5, 0x74b82261d969f7ad},  //   62
    {0x4dc9a61d998642bb, 0x58f3157d27e23acc},  //   63
    {0x613c0fa4ffe7d36a, 0x4f2fdadc71dac97f},  //   64
    {0x798b138e3fe1c845, 0x22fbd1938e517bdf},  //   65
    {0x4bf6ec38e7ed1d2b, 0x25dd62fc38f2ed6c},  //   66
    {0x5ef4a74721e86476, 0x0f54bbbb472fa8c6},  //   67
    {0x76b1d118ea627d93, 0x5329eaaa18fb92f8},  //   68
    {0x4a2f22af927d8e7c, 0x23fa32aa4f9d3bdb},  //   69
    {0x5cbaeb5b771cf21b, 0x2cf8bf54e3848ad2},  //   70
    {0x73e9a63254e42ea2, 0x1836ef2a1c65ad86},  //   71
    {0x487207df750e9d25, 0x2f22557a51bf8c74},  //   72
    {0x5a8e89d75252446e, 0x5aeaead8e62f6f91},  //   73
    {0x71322c4d26e6d58a, 0x31a5a58f1fbb4b75},  //   74
    {0x46bf5bb038504576, 0x3f07877973d50f29},  //   75
    {0x586f329c466456d4, 0x0ec96957d0ca52f3},  //   76
    {0x6e8aff4357fd6c89, 0x127bc3adc4fce7b0},  //   77
    {0x4516df8a16fe63d5, 0x5b8d5a4c9b1e10ce},  //   78
    {0x565c976c9cbdfccb, 0x1270b0dfc1e59502},  //   79
    {0x6bf3bd47c3ed7bfd, 0x770cdd17b25efa42},  //   80
    {0x4378564cda746d7e, 0x5a680a2ecf7b5c69},  //   81
    {0x54566be0111188de, 0x31020cba835a3384},  //   82
    {0x696c06d81555eb15, 0x7d428fe92430c065},  //   83
    {0x41e384470d55b2ed, 0x5e4999f1b69e783f},  //   84
    {0x525c6558d0ab1fa9, 0x15dc006e2446164f},  //   85
    {0x66f37eaf04d5e793, 0x3b530089ad579be2},  //   86
    {0x40582f2d6305b0bc, 0x1513e0560c56c16e},  //   87
    {0x506e3af8bbc71ceb, 0x1a58d86b8f6c71c9},  //   88
    {0x6489c9b6eab8e426, 0x00ef0e8673478e3b},  //   89
    {0x7dac3c24a5671d2f, 0x412ad228101971c9},  //   90
    {0x4e8ba596e760723d, 0x58bac3590a0fe71e},  //   91
    {0x622e8efca1388ecd, 0x0ee9742f4c93e0e6},  //   92
    {0x7aba32bbc986b280, 0x32a3d13b1fb8d91f},  //   93
    {0x4cb45fb55df42f90, 0x1fa662c4f3d387b3},  //   94
    {0x5fe177a2b5713b74, 0x278ffb7630c869a0},  //   95
    {0x77d9d58b62cd8a51, 0x3173fa53bcfa8408},  //   96
    {0x4ae825771dc07672, 0x6ee87c74561c9285},  //   97
    {0x5da22ed4e530940f, 0x4aa29b916ba3b726},  //   98
    {0x750aba8a1e7cb913, 0x3d4b4275c68ca4f0},  //   99
    {0x4926b496530df3ac, 0x164f09899c17e716},  //  100
    {0x5b7061bbe7d17097, 0x1be2cbec031de0dc},  //  101
    {0x724c7a2ae1c5ccbd, 0x02db7ee703e55912},  //  102
    {0x476fcc5acd1b9ff6, 0x11c92f50626f57ac},  //  103
    {0x594bbf71806287f3, 0x563b7b247b0b2d96},  //  104
    {0x6f9eaf4de07b29f0, 0x4bca59ed99cdf8fc},  //  105
    {0x45c32d90ac4cfa36, 0x2f5e78348020bb9e},  //  106
    {0x5733f8f4d76038c3, 0x7b361641a028ea85},  //  107
    {0x6d00f7320d3846f4, 0x7a039bd208332526},  //  108
    {0x44209a7f48432c59, 0x0c424163451ff738},  //  109
    {0x5528c11f1a53f76f, 0x2f52d1bc1667f506},  //  110
    {0x6a72f166e0e8f54b, 0x1b27862b1c01f247},  //  111
    {0x4287d6e04c91994f, 0x00f8b3daf181376d},  //  112
    {0x5329cc985fb5ffa2, 0x6136e0d1ade18548},  //  113
    {0x67f43fbe77a37f8b, 0x398499061959e699},  //  114
    {0x40f8a7d70ac62fb7, 0x13f2dfa3cfd83020},  //  115
    {0x5136d1cccd77bba4, 0x78ef978cc3ce3c28},  //  116
    {0x6584864000d5aa8e, 0x172b7d6ff4c1cb32},  //  117
    {0x7ee5a7d0010b1531, 0x5cf65ccbf1f23dfe},  //  118
    {0x4f4f88e200a6ed3f, 0x0a19f9ff773766bf},  //  119
    {0x63236b1a80d0a88e, 0x6ca0787f5505406f},  //  120
    {0x7bec45e12104d2b2, 0x47c8969f2a46908a},  //  121
    {0x4d73abacb4a303af, 0x4cdd5e237a6c1a57},  //  122
    {0x60d09697e1cbc49b, 0x4014b5ac590720ec},  //  123
    {0x7904bc3dda3eb5c2, 0x3019e3176f48e927},  //  124
    {0x4ba2f5a6a8673199, 0x3e102deea58d91b9},  //  125
    {0x5e8bb3105280fdff, 0x6d94396a4ef0f627},  //  126
    {0x762e9fd467213d7f, 0x68f947c4e2ad33b0},  //  127
    {0x49dd23e4c074c66f, 0x719bccdb0dac404e},  //  128
    {0x5c546cddf091f80b, 0x6e02c011d1175062},  //  129
    {0x736988156cb6760e, 0x69837016455d247a},  //  130
    {0x4821f50d63f209c9, 0x21f2260deb5a36cc},  //  131
    {0x5a2a7250bcee8c3b, 0x4a6eaf916630c47f},  //  132
    {0x70b50ee4ec2a2f4a, 0x3d0a5b75bfbcf59f},  //  133
    {0x4671294f139a5d8e, 0x4626792997d61984},  //  134
    {0x580d73a2d880f4f2, 0x17b01773fdcb9fe4},  //  135
    {0x6e10d08b8ea1322e, 0x5d9c1d50fd3e87dd},  //  136
    {0x44ca82573924bf5d, 0x1a8192529e4714eb},  //  137
    {0x55fd22ed076def34, 0x4121f6e745d8da25},  //  138
    {0x6b7c6ba849496b01, 0x516a74a1174f10ae},  //  139
    {0x432dc3492dcde2e1, 0x02e288e4ae916a6d},  //  140
    {0x53f9341b79415b99, 0x239b2b1dda35c508},  //  141
    {0x68f781225791b27f, 0x4c81f5e550c3364a},  //  142
    {0x419ab0b576bb0f8f, 0x5fd139af527a01ef},  //  143
    {0x52015ce2d469d373, 0x57c5881b2718826a},  //  144
    {0x6681b41b89844850, 0x4db6ea21f0dea304},  //  145
    {0x4011109135f2ad32, 0x30925255368b25e3},  //  146
    {0x501554b5836f587e, 0x7cb6e6ea842def5c},  //  147
    {0x641aa9e2e44b2e9e, 0x5be4a0a525396b32},  //  148
    {0x7d21545b9d5dfa46, 0x32ddc8ce6e87c5ff},  //  149
    {0x4e34d4b9425abc6b, 0x7fca9d810514dbbf},  //  150
    {0x61c209e792f16b86, 0x7fbd44e1465a12af},  //  151
    {0x7a328c6177adc668, 0x5fac961997f0975b},  //  152
    {0x4c5f97bceacc9c01, 0x3bcbddcffef65e99},  //  153
    {0x5f777dac257fc301, 0x6abed543feb3f63f},  //  154
    {0x77555d172edfb3c2, 0x256e8a94fe60f3cf},  //  155
    {0x4a955a2e7d4bd059, 0x3765169d1efc9861},  //  156
    {0x5d3ab0ba1c9ec46f, 0x653e5c4466bbbe7a},  //  157
    {0x74895ce8a3c6758b, 0x5e8df355806aae18},  //  158
    {0x48d5da11665c0977, 0x2b18b8157042accf},  //  159
    {0x5b0b5095bff30bd5, 0x15dee61acc535803},  //  160
    {0x71ce24bb2fefceca, 0x3b569fa17f682e03},  //  161
    {0x4720d6f4fdf5e13e, 0x451623c4efa11cc2},  //  162
    {0x58e90cb23d73598e, 0x165bacb62b8963f3},  //  163
    {0x6f234fdeccd02ff1, 0x5bf297e3b66bbcef},  //  164
    {0x457611eb40021df7, 0x09779eee52035616},  //  165
    {0x56d396661002a574, 0x6bd586a9e6842b9b},  //  166
    {0x6c887bff94034ed2, 0x06cae85460253682},  //  167
    {0x43d54d7fbc821143, 0x243ed134bc174211},  //  168
    {0x54caa0dfaba29594, 0x0d4e8581eb1d1295},  //  169
    {0x69fd4917968b3af9, 0x10a226e265e4573b},  //  170
    {0x423e4daebe1704db, 0x5a65584d7faeb685},  //  171
    {0x52cde11a6d9cc612, 0x50feae60df9a6426},  //  172
    {0x678159610903f797, 0x253e59f91780fd2f},  //  173
    {0x40b0d7dca5a27abe, 0x4746f83baeb09e3e},  //  174
    {0x50dd0dd3cf0b196e, 0x1918b64a9a5cc5cd},  //  175
    {0x65145148c2cddfc9, 0x5f5ee3dd40f3f740},  //  176
    {0x7e59659af38157bc, 0x17369cd49130f510},  //  177
    {0x4ef7df80d830d6d5, 0x4e822204dabe992a},  //  178
    {0x62b5d7610e3d0c8b, 0x0222aa86116e3f75},  //  179
    {0x7b634d3951cc4fad, 0x62ab552795c9cf52},  //  180
    {0x4d1e1043d31fb1cc, 0x4dab1538bd9e2193},  //  181
    {0x60659454c7e79e3f, 0x6115da86ed05a9f8},  //  182
    {0x787ef969f9e185cf, 0x595b5128a8471476},  //  183
    {0x4b4f5be23c2cf3a1, 0x67d912b9692c6cca},  //  184
    {0x5e2332dacb38308a, 0x21cf5767c37787fc},  //  185
    {0x75abff917e063cac, 0x6a432d41b45569fb},  //  186
    {0x498b7fbaeec3e5ec, 0x0269fc4910b5623d},  //  187
    {0x5bee5fa9aa74df67, 0x03047b5b54e2bacc},  //  188
    {0x72e9f79415121740, 0x63c59a322a1b697f},  //  189
    {0x47d23abc8d2b4e88, 0x3e5b805f5a5121f0},  //  190
    {0x59c6c96bb076222a, 0x4df2607730e56a6c},  //  191
    {0x70387bc69c93aab5, 0x216ef894fd1ec506},  //  192
    {0x46234d5c21dc4ab1, 0x24e55b5d1e333b24},  //  193
    {0x57ac20b32a535d5d, 0x4e1eb23465c009ed},  //  194
    {0x6d9728dff4e834b5, 0x01a65ec17f300c68},  //  195
    {0x447e798bf91120f1, 0x1107fb38ef7e07c1},  //  196
    {0x559e17eef755692d, 0x3549fa072b5d89b1},  //  197
    {0x6b059deab52ac378, 0x629c7888f634ec1e},  //  198
    {0x42e382b2b13aba2b, 0x3da1cb5599e11393},  //  199
    {0x539c635f5d8968b6, 0x2d0a3e2b00595877},  //  200
    {0x68837c3734ebc2e3, 0x784ccdb5c06fae95},  //  201
    {0x41522da2811359ce, 0x3b3000919845cd1d},  //  202
    {0x51a6b90b21583042, 0x09fc00b5fe574065},  //  203
    {0x6610674de9ae3c52, 0x4c7b00e37ded107e},  //  204
    {0x7f9481216419cb67, 0x1f99c11c5d68549d},  //  205
    {0x4fbcd0b4de901f20, 0x43c018b1ba6134e2},  //  206
    {0x63ac04e2163426e8, 0x54b01ede28f9821b},  //  207
    {0x7c97061a9bc130a2, 0x69dc2695b337e2a1},  //  208
    {0x4dde63d0a158be65, 0x6229981d9002eda5},  //  209
    {0x6155fcc4c9aeedff, 0x1ab3fe24f403a90e},  //  210
    {0x79ab7bf5fc1aa97f, 0x0160fdae31049351},  //  211
    {0x4c0b2d79bd90a9ef, 0x30dc9e8cdea2dc13},  //  212
    {0x5f0df8d82cf4d46b, 0x1d13c630164b9318},  //  213
    {0x76d1770e38320986, 0x0458b7bc1bde77dd},  //  214
    {0x4a42ea68e31f45f3, 0x62b772d5916b0aeb},  //  215
    {0x5cd3a5031be71770, 0x5b654f8af5c5cda5},  //  216
    {0x74088e43e2e0dd4c, 0x723ea36db337410e},  //  217
    {0x488558ea6dcc8a50, 0x07672624900288a9},  //  218
    {0x5aa6af25093face4, 0x0940efadb4032ad3},  //  219
    {0x71505aee4b8f981d, 0x0b912b992103f588},  //  220
    {0x46d238d4ef39bf12, 0x173abb3fb4a27975},  //  221
    {0x5886c70a2b082ed6, 0x5d096a0fa1cb17d2},  //  222
    {0x6ea878ccb5ca3a8c, 0x344bc4938a3dddc7},  //  223
    {0x45294b7ff19e6497, 0x60af5adc3666aa9c},  //  224
    {0x56739e5fee05fdbd, 0x58db319344005543},  //  225
    {0x6c1085f7e9877d2d, 0x0f11fdf815006a94},  //  226
    {0x438a53baf1f4ae3c, 0x196b3ebb0d20429d},  //  227
    {0x546ce8a9ae71d9cb, 0x1fc60e69d0685344},  //  228
    {0x698822d41a0e503e, 0x07b7920444826815},  //  229
    {0x41f515c49048f226, 0x64d2bb42aad1810d},  //  230
    {0x52725b35b45b2eb0, 0x3e076a135585e150},  //  231
    {0x670ef2032171fa5c, 0x4d8944982ae759a4},  //  232
    {0x40695741f4e73c79, 0x7075cadf1ad09807},  //  233
    {0x5083ad1272210b98, 0x2c933d96e184be08},  //  234
    {0x64a498570ea94e7e, 0x37b80cfc99e5ed8a},  //  235
    {0x7dcdbe6cd253a21e, 0x05a6103bc05f68ed},  //  236
    {0x4ea0970403744552, 0x6387ca25583ba194},  //  237
    {0x6248bcc5045156a7, 0x3c69bcaeae4a89f9},  //  238
    {0x7adaebf64565ac51, 0x2b842bda59dd2c77},  //  239
    {0x4cc8d379eb5f8bb2, 0x6b329b68782a3bcb},  //  240
    {0x5ffb085866376e9f, 0x45ff42429634cabd},  //  241
    {0x77f9ca6e7fc54a47, 0x377f12d33bc1fd6d},  //  242
    {0x4afc1e850fdb4e6c, 0x52af6bc405593e64},  //  243
    {0x5dbb262653d22207, 0x675b46b506af8dfd},  //  244
    {0x7529efafe8c6aa89, 0x61321862485b717c},  //  245
    {0x493a35cdf17c2a96, 0x0cbf4f3d6d3926ee},  //  246
    {0x5b88c3416ddb353b, 0x4fef230cc88770a9},  //  247
    {0x726af411c952028a, 0x43eaebcffaa94cd3},  //  248
    {0x4782d88b1dd34196, 0x4a72d361fca9d004},  //  249
    {0x59638eade54811fc, 0x1d0f883a7bd44405},  //  250
    {0x6fbc72595e9a167b, 0x24536a491ac95506},  //  251
    {0x45d5c777db204e0d, 0x06b4226db0bdd524},  //  252
    {0x574b3955d1e86190, 0x28612b091ced4a6d},  //  253
    {0x6d1e07ab466279f4, 0x327975cb64289d08},  //  254
    {0x4432c4cb0bfd8c38, 0x5f8be99f1e996225},  //  255
    {0x553f75fdcefcef46, 0x776ee406e63fbaae},  //  256
    {0x6a8f537d42bc2b18, 0x554a9d089fcfa95a},  //  257
    {0x4299942e49b59aef, 0x354ea22563e1c9d8},  //  258
    {0x533ff939dc2301ab, 0x22a24aaebcda3c4e},  //  259
    {0x680ff788532bc216, 0x0b4add5a6c10cb62},  //  260
    {0x4109fab533fb594d, 0x670eca58838a7f1d},  //  261
    {0x514c796280fa2fa1, 0x20d27ceea46d1ee4},  //  262
    {0x659f97bb2138bb89, 0x49071c2a4d88669d},  //  263
    {0x7f077da9e986ea6b, 0x7b48e334e0ea8045},  //  264
    {0x4f64ae8a31f45283, 0x3d0d8e010c92902b},  //  265
    {0x633dda2cbe716724, 0x2c50f1814fb73436},  //  266
    {0x7c0d50b7ee0dc0ed, 0x37652de1a3a50143},  //  267
    {0x4d885272f4c89894, 0x329f3cad064720ca},  //  268
    {0x60ea670fb1fabeb9, 0x3f470bd847d8e8fd},  //  269
    {0x792500d39e796e67, 0x6f18cece59cf233c},  //  270
    {0x4bb72084430be500, 0x756f8140f8217605},  //  271
    {0x5ea4e8a553cede41, 0x12cb61913629d387},  //  272
    {0x764e22cea8c295d1, 0x377e39f583b44868},  //  273
    {0x49f0d5c129799da2, 0x72aee4397250ad41},  //  274
    {0x5c6d0b3173d8050b, 0x4f5a9d47cee4d891},  //  275
    {0x73884dfdd0ce064e, 0x43314499c29e0eb6},  //  276
    {0x483530bea280c3f1, 0x09fecae019a2c932},  //  277
    {0x5a427cee4b20f4ed, 0x2c7e7d98200b7b7e},  //  278
    {0x70d31c29dde93228, 0x579e1cfe280e5a5d},  //  279
    {0x4683f19a2ab1bf59, 0x36c2d21ed908f87b},  //  280
    {0x5824ee00b55e2f2f, 0x647386a68f4b3699},  //  281
    {0x6e2e2980e2b5bafb, 0x5d906850331e043f},  //  282
    {0x44dcd9f08db194dd, 0x2a7a41321ff2c2a8},  //  283
    {0x5614106cb11dfa14, 0x5518d17ea7ef7352},  //  284
    {0x6b991487dd657899, 0x6a5f05de51eb5026},  //  285
    {0x433facd4ea5f6b60, 0x127b63aaf3331218},  //  286
    {0x540f980a24f74638, 0x171a3c95afffd69e},  //  287
    {0x69137e0cae3517c6, 0x1ce0cbbb1bffcc45},  //  288
    {0x41ac2ec7ece12edb, 0x720c7f54f17fdfab},  //  289
    {0x52173a79e8197a92, 0x6e8f9f2a2ddfd796},  //  290
    {0x669d0918621fd937, 0x4a3386f4b957cd7b},  //  291
    {0x402225af3d53e7c2, 0x5e603458f3d6e06d},  //  292
    {0x502aaf1b0ca8e1b3, 0x35f8416f30cc9888},  //  293
    {0x64355ae1cfd31a20, 0x237651cafcffbeaa},  //  294
    {0x7d42b19a43c7e0a8, 0x2c53e63dbc3fae55},  //  295
    {0x4e49af006a5cec69, 0x1bb46fe695a7ccf5},  //  296
    {0x61dc1ac084f42783, 0x42a18be03b11c033},  //  297
    {0x7a532170a6313164, 0x3349eed849d6303f},  //  298
    {0x4c73f4e667debede, 0x600e35472e25de28},  //  299
    {0x5f90f22001d66e96, 0x3811c298f9af55b1},  //  300
    {0x77752ea8024c0a3c, 0x0616333f381b2b1e},  //  301
    {0x4aa93d29016f8665, 0x43cde0078310faf3},  //  302
    {0x5d538c7341cb67fe, 0x74c1580963d539af},  //  303
    {0x74a86f90123e41fe, 0x51f1ae0bbcca881b},  //  304
    {0x48e945ba0b66e93f, 0x13370cc755fe9511},  //  305
    {0x5b2397288e40a38e, 0x7804cff92b7e3a55},  //  306
    {0x71ec7cf2b1d0cc72, 0x560603f7765dc8ea},  //  307
    {0x4733ce17af227fc7, 0x55c3c27aa9fa9d93},  //  308
    {0x5900c19d9aeb1fb9, 0x4b34b319547944f7},  //  309
    {0x6f40f20501a5e7a7, 0x7e01dfdfa9979635},  //  310
    {0x458897432107b0c8, 0x7ec12bebc9febde1},  //  311
    {0x56eabd13e9499cfb, 0x1e7176e6bc7e6d59},  //  312
    {0x6ca56c58e39c043a, 0x060dd4a06b9e08b0},  //  313
    {0x43e763b78e4182a4, 0x23c8a4e44342c56e},  //  314
    {0x54e13ca571d1e34d, 0x2cbace1d541376c9},  //  315
    {0x6a198bcece465c20, 0x57e981a4a918547b},  //  316
    {0x424ff76140ebf994, 0x36f1f106e9af34cd},  //  317
    {0x52e3f5399126f7f9, 0x44ae6d48a41b0201},  //  318
    {0x679cf287f570b5f7, 0x75da089acd21c281},  //  319
    {0x40c21794f96671ba, 0x79a84560c0351991},  //  320
    {0x50f29d7a37c00e29, 0x581256b8f0425ff5},  //  321
    {0x652f44d8c5b011b4, 0x0e16ec672c52f7f2},  //  322
    {0x7e7b160ef71c1621, 0x119ca780f767b5ee},  //  323
    {0x4f0cedc95a718dd4, 0x5b01e8b09aa0d1b5},  //  324
};

// Computes 128-bit result of multiplication of two 64-bit unsigned integers.
auto umul128(uint64_t x, uint64_t y) noexcept -> uint128_t {
#ifdef __SIZEOF_INT128__
  return uint128_t(x) * y;
#else
  constexpr uint64_t mask = ~uint32_t();

  uint64_t a = x >> 32;
  uint64_t b = x & mask;
  uint64_t c = y >> 32;
  uint64_t d = y & mask;

  uint64_t ac = a * c;
  uint64_t bc = b * c;
  uint64_t ad = a * d;
  uint64_t bd = b * d;

  uint64_t intermediate = (bd >> 32) + (ad & mask) + (bc & mask);

  return {ac + (intermediate >> 32) + (ad >> 32) + (bc >> 32),
          (intermediate << 32) + (bd & mask)};
#endif  // __SIZEOF_INT128__
}

// Computes upper 64 bits of multiplication of pow10 and scaled_sig with
// modified round-to-odd rounding of the result,
// where pow10 = (pow10_hi << 63) | pow10_lo.
auto umul192_upper64_modified(uint64_t pow10_hi, uint64_t pow10_lo,
                              uint64_t scaled_sig) noexcept -> uint64_t {
  uint64_t x_hi = uint64_t(umul128(pow10_lo, scaled_sig) >> 64);
  uint128_t y = umul128(pow10_hi, scaled_sig);
  uint64_t z = (uint64_t(y) >> 1) + x_hi;
  uint64_t result = uint64_t(y >> 64) + (z >> 63);
  constexpr uint64_t mask = (uint64_t(1) << 63) - 1;
  // OR with 1 if z is not divisible by 2**63.
  return result | (((z & mask) + mask) >> 63);
}

// log10_2_sig = round(log10(2) * 2**log10_2_exp)
constexpr int64_t log10_2_sig = 661'971'961'083;
constexpr int log10_2_exp = 41;

// Computes floor(log10(pow(2, e))) for e <= 5456721.
auto floor_log10_pow2(int e) noexcept -> int {
  return e * log10_2_sig >> log10_2_exp;
}

auto write8digits(char* buffer, unsigned n) noexcept -> char* {
  // Based on Division-Free Binary-to-Decimal Conversion:
  // https://inria.hal.science/hal-00864293/.
  constexpr int shift = 28;
  constexpr uint64_t magic = 193'428'131'138'340'668;
  unsigned y =
      static_cast<uint64_t>(umul128((uint64_t(n) + 1) << shift, magic) >> 84) -
      1;
  for (int i = 0; i < 8; ++i) {
    unsigned t = 10 * y;
    *buffer++ = '0' + (t >> shift);
    y = t & ((1 << shift) - 1);
  }
  return buffer;
}

const uint64_t pow10[] = {
    1,
    10,
    100,
    1'000,
    10'000,
    100'000,
    1'000'000,
    10'000'000,
    100'000'000,
    1'000'000'000,
    10'000'000'000,
    100'000'000'000,
    1'000'000'000'000,
    10'000'000'000'000,
    100'000'000'000'000,
    1'000'000'000'000'000,
    10'000'000'000'000'000,
    100'000'000'000'000'000,
};

// Writes the decimal FP number dec_sig * 10**dec_exp to buffer.
void write(char* buffer, uint64_t dec_sig, int dec_exp) noexcept {
  int len = floor_log10_pow2(std::numeric_limits<uint64_t>::digits -
                             std::countl_zero(dec_sig));
  if (dec_sig >= pow10[len]) ++len;
  dec_sig *= pow10[std::numeric_limits<double>::max_digits10 - len];
  dec_exp += len - 1;

  constexpr int pow10_8 = 100'000'000;
  unsigned hi = static_cast<unsigned>(dec_sig / pow10_8);
  *buffer++ = '0' + hi / pow10_8;
  *buffer++ = '.';
  buffer = write8digits(buffer, hi % pow10_8);
  unsigned lo = static_cast<unsigned>(dec_sig % pow10_8);
  if (lo != 0) buffer = write8digits(buffer, lo);

  // Remove trailing zeros.
  while (buffer[-1] == '0') --buffer;

  *buffer++ = 'e';
  char sign = '+';
  if (dec_exp < 0) {
    sign = '-';
    dec_exp = -dec_exp;
  }
  *buffer++ = sign;
  if (dec_exp >= 100) {
    *buffer++ = '0' + dec_exp / 100;
    dec_exp %= 100;
  }
  *buffer++ = '0' + dec_exp / 10;
  *buffer++ = '0' + dec_exp % 10;
  *buffer = '\0';
}

}  // namespace

void schubfach::dtoa(double value, char* buffer) noexcept {
  uint64_t bits = std::bit_cast<uint64_t>(value);
  *buffer = '-';
  buffer += bits >> 63;

  constexpr int num_sig_bits = std::numeric_limits<double>::digits - 1;
  constexpr int exp_mask = 0x7ff;
  int bin_exp = int(bits >> num_sig_bits) & exp_mask;

  constexpr uint64_t implicit_bit = uint64_t(1) << num_sig_bits;
  uint64_t bin_sig = bits & (implicit_bit - 1);  // binary significand

  bool regular = bin_sig != 0;
  if (((bin_exp + 1) & exp_mask) <= 1) [[unlikely]] {
    if (bin_exp != 0) {
      memcpy(buffer, bin_sig == 0 ? "inf" : "nan", 4);
      return;
    }
    if (bin_sig == 0) {
      memcpy(buffer, "0", 2);
      return;
    }
    // Handle subnormals.
    bin_sig ^= implicit_bit;
    ++bin_exp;
    regular = true;
  }
  bin_sig ^= implicit_bit;
  bin_exp -= num_sig_bits + 1023;  // Remove the exponent bias.

  // Handle small integers.
  if ((bin_exp < 0) & (bin_exp >= -num_sig_bits)) {
    uint64_t f = bin_sig >> -bin_exp;
    if (f << -bin_exp == bin_sig) return write(buffer, f, 0);
  }

  // Shift the significand so that boundaries are integer.
  uint64_t bin_sig_shifted = bin_sig << 2;

  // Compute the shifted boundaries of the rounding interval (Rv).
  uint64_t lower = bin_sig_shifted - (regular ? 2 : 1);
  uint64_t upper = bin_sig_shifted + 2;

  // log10_3_over_4_sig = round(log10(3/4) * 2**log10_2_exp)
  constexpr int64_t log10_3_over_4_sig = -274'743'187'321;

  // Compute the decimal exponent as floor(log10(2**bin_exp)) if regular or
  // floor(log10(3/4 * 2**bin_exp)) otherwise, without branching.
  int dec_exp = (bin_exp * log10_2_sig + (!regular ? log10_3_over_4_sig : 0)) >>
                log10_2_exp;

  constexpr int dec_exp_min = -292;
  auto [pow10_hi, pow10_lo] = pow10_significands[-dec_exp - dec_exp_min];

  // round(log2(10) * 2**log2_pow10_exp) + 1
  constexpr int log2_pow10_sig = 217'707, log2_pow10_exp = 16;

  // floor(log2(10**-dec_exp))
  int pow10_bin_exp = -dec_exp * log2_pow10_sig >> log2_pow10_exp;
  // pow10 = ((pow10_hi << 63) | pow10_lo) * 2**(pow10_bin_exp - 126 + 1)

  // Shift to ensure the intermediate result in umul192_upper64_modified has
  // a fixed 128-bit fractional width. For example, 3 * 2**59 and 3 * 2**60
  // both have dec_exp = 2 and dividing them by 10**dec_exp would have the
  // decimal point in different (bit) positions without the shift:
  //   3 * 2**59 / 100 = 1.72...e+16 (shift = 3)
  //   3 * 2**60 / 100 = 3.45...e+16 (shift = 4)
  int shift = bin_exp + pow10_bin_exp + 2;

  uint64_t scaled_sig =
      umul192_upper64_modified(pow10_hi, pow10_lo, bin_sig_shifted << shift);

  // Compute the estimates of lower and upper bounds of the rounding interval
  // by multiplying them by the power of 10 and applying modified rounding.
  lower = umul192_upper64_modified(pow10_hi, pow10_lo, lower << shift);
  upper = umul192_upper64_modified(pow10_hi, pow10_lo, upper << shift);

  uint64_t dec_sig_under = scaled_sig >> 2;
  uint64_t bin_sig_lsb = bin_sig & 1;
  if (dec_sig_under >= 10) {
    // Compute the significands of the under- and overestimate.
    uint64_t dec_sig_under2 = 10 * (dec_sig_under / 10);
    uint64_t dec_sig_over2 = dec_sig_under2 + 10;
    // Check if the under- and overestimates are in the interval.
    bool under_in = lower + bin_sig_lsb <= (dec_sig_under2 << 2);
    bool over_in = (dec_sig_over2 << 2) + bin_sig_lsb <= upper;
    if (under_in != over_in)
      return write(buffer, under_in ? dec_sig_under2 : dec_sig_over2, dec_exp);
  }

  uint64_t dec_sig_over = dec_sig_under + 1;
  bool under_in = lower + bin_sig_lsb <= (dec_sig_under << 2);
  bool over_in = (dec_sig_over << 2) + bin_sig_lsb <= upper;
  if (under_in != over_in) {
    // Only one of dec_sig_under or dec_sig_over are in the rounding interval.
    return write(buffer, under_in ? dec_sig_under : dec_sig_over, dec_exp);
  }

  // Both dec_sig_under and dec_sig_over are in the interval - pick the closest.
  int cmp = scaled_sig - ((dec_sig_under + dec_sig_over) << 1);
  bool under_closer = cmp < 0 || cmp == 0 && (dec_sig_under & 1) == 0;
  return write(buffer, under_closer ? dec_sig_under : dec_sig_over, dec_exp);
}