include/boost/json /detail /charconv /detail /fast_float /bigint.hpp
89.87% Lines (213/237) 100.00% Functions (36/36)
[ ] prev/next file n p prev/next uncovered line
TLA Baseline Branch
Line Hits Code Line Hits Code
1   // Copyright 2020-2023 Daniel Lemire 1   // Copyright 2020-2023 Daniel Lemire
2   // Copyright 2023 Matt Borland 2   // Copyright 2023 Matt Borland
3   // Distributed under the Boost Software License, Version 1.0. 3   // Distributed under the Boost Software License, Version 1.0.
4   // https://www.boost.org/LICENSE_1_0.txt 4   // https://www.boost.org/LICENSE_1_0.txt
5   // 5   //
6   // Derivative of: https://github.com/fastfloat/fast_float 6   // Derivative of: https://github.com/fastfloat/fast_float
7   7  
8   #ifndef BOOST_JSON_DETAIL_CHARCONV_DETAIL_FASTFLOAT_BIGINT_HPP 8   #ifndef BOOST_JSON_DETAIL_CHARCONV_DETAIL_FASTFLOAT_BIGINT_HPP
9   #define BOOST_JSON_DETAIL_CHARCONV_DETAIL_FASTFLOAT_BIGINT_HPP 9   #define BOOST_JSON_DETAIL_CHARCONV_DETAIL_FASTFLOAT_BIGINT_HPP
10   10  
11   #include <boost/json/detail/charconv/detail/fast_float/float_common.hpp> 11   #include <boost/json/detail/charconv/detail/fast_float/float_common.hpp>
12   #include <algorithm> 12   #include <algorithm>
13   #include <cstdint> 13   #include <cstdint>
14   #include <climits> 14   #include <climits>
15   #include <cstring> 15   #include <cstring>
16   16  
17   namespace boost { namespace json { namespace detail { namespace charconv { namespace detail { namespace fast_float { 17   namespace boost { namespace json { namespace detail { namespace charconv { namespace detail { namespace fast_float {
18   18  
19   // the limb width: we want efficient multiplication of double the bits in 19   // the limb width: we want efficient multiplication of double the bits in
20   // limb, or for 64-bit limbs, at least 64-bit multiplication where we can 20   // limb, or for 64-bit limbs, at least 64-bit multiplication where we can
21   // extract the high and low parts efficiently. this is every 64-bit 21   // extract the high and low parts efficiently. this is every 64-bit
22   // architecture except for sparc, which emulates 128-bit multiplication. 22   // architecture except for sparc, which emulates 128-bit multiplication.
23   // we might have platforms where `CHAR_BIT` is not 8, so let's avoid 23   // we might have platforms where `CHAR_BIT` is not 8, so let's avoid
24   // doing `8 * sizeof(limb)`. 24   // doing `8 * sizeof(limb)`.
25   #if defined(BOOST_JSON_FASTFLOAT_64BIT) && !defined(__sparc) 25   #if defined(BOOST_JSON_FASTFLOAT_64BIT) && !defined(__sparc)
26   #define BOOST_JSON_FASTFLOAT_64BIT_LIMB 1 26   #define BOOST_JSON_FASTFLOAT_64BIT_LIMB 1
27   typedef uint64_t limb; 27   typedef uint64_t limb;
28   constexpr size_t limb_bits = 64; 28   constexpr size_t limb_bits = 64;
29   #else 29   #else
30   #define BOOST_JSON_FASTFLOAT_32BIT_LIMB 30   #define BOOST_JSON_FASTFLOAT_32BIT_LIMB
31   typedef uint32_t limb; 31   typedef uint32_t limb;
32   constexpr size_t limb_bits = 32; 32   constexpr size_t limb_bits = 32;
33   #endif 33   #endif
34   34  
35   typedef span<limb> limb_span; 35   typedef span<limb> limb_span;
36   36  
37   // number of bits in a bigint. this needs to be at least the number 37   // number of bits in a bigint. this needs to be at least the number
38   // of bits required to store the largest bigint, which is 38   // of bits required to store the largest bigint, which is
39   // `log2(10**(digits + max_exp))`, or `log2(10**(767 + 342))`, or 39   // `log2(10**(digits + max_exp))`, or `log2(10**(767 + 342))`, or
40   // ~3600 bits, so we round to 4000. 40   // ~3600 bits, so we round to 4000.
41   constexpr size_t bigint_bits = 4000; 41   constexpr size_t bigint_bits = 4000;
42   constexpr size_t bigint_limbs = bigint_bits / limb_bits; 42   constexpr size_t bigint_limbs = bigint_bits / limb_bits;
43   43  
44   // vector-like type that is allocated on the stack. the entire 44   // vector-like type that is allocated on the stack. the entire
45   // buffer is pre-allocated, and only the length changes. 45   // buffer is pre-allocated, and only the length changes.
46   template <uint16_t size> 46   template <uint16_t size>
47   struct stackvec { 47   struct stackvec {
48   limb data[size]; 48   limb data[size];
49   // we never need more than 150 limbs 49   // we never need more than 150 limbs
50   uint16_t length{0}; 50   uint16_t length{0};
51   51  
HITCBC 52   12693 stackvec() = default; 52   12693 stackvec() = default;
53   stackvec(const stackvec &) = delete; 53   stackvec(const stackvec &) = delete;
54   stackvec &operator=(const stackvec &) = delete; 54   stackvec &operator=(const stackvec &) = delete;
55   stackvec(stackvec &&) = delete; 55   stackvec(stackvec &&) = delete;
56   stackvec &operator=(stackvec &&other) = delete; 56   stackvec &operator=(stackvec &&other) = delete;
57   57  
58   // create stack vector from existing limb span. 58   // create stack vector from existing limb span.
HITCBC 59   2024 BOOST_JSON_FASTFLOAT_CONSTEXPR20 stackvec(limb_span s) { 59   2024 BOOST_JSON_FASTFLOAT_CONSTEXPR20 stackvec(limb_span s) {
HITCBC 60   2024 try_extend(s); 60   2024 try_extend(s);
HITCBC 61   2024 } 61   2024 }
62   62  
HITCBC 63   255428 BOOST_JSON_CXX14_CONSTEXPR limb& operator[](size_t index) noexcept { 63   255428 BOOST_JSON_CXX14_CONSTEXPR limb& operator[](size_t index) noexcept {
HITCBC 64   255428 BOOST_ASSERT(index < length); 64   255428 BOOST_ASSERT(index < length);
HITCBC 65   255428 return data[index]; 65   255428 return data[index];
66   } 66   }
HITCBC 67   6198 BOOST_JSON_CXX14_CONSTEXPR const limb& operator[](size_t index) const noexcept { 67   6198 BOOST_JSON_CXX14_CONSTEXPR const limb& operator[](size_t index) const noexcept {
HITCBC 68   6198 BOOST_ASSERT(index < length); 68   6198 BOOST_ASSERT(index < length);
HITCBC 69   6198 return data[index]; 69   6198 return data[index];
70   } 70   }
71   // index from the end of the container 71   // index from the end of the container
HITCBC 72   9129 BOOST_JSON_CXX14_CONSTEXPR const limb& rindex(size_t index) const noexcept { 72   9129 BOOST_JSON_CXX14_CONSTEXPR const limb& rindex(size_t index) const noexcept {
HITCBC 73   9129 BOOST_ASSERT(index < length); 73   9129 BOOST_ASSERT(index < length);
HITCBC 74   9129 size_t rindex = length - index - 1; 74   9129 size_t rindex = length - index - 1;
HITCBC 75   9129 return data[rindex]; 75   9129 return data[rindex];
76   } 76   }
77   77  
78   // set the length, without bounds checking. 78   // set the length, without bounds checking.
HITCBC 79   28303 BOOST_JSON_CXX14_CONSTEXPR void set_len(size_t len) noexcept { 79   28303 BOOST_JSON_CXX14_CONSTEXPR void set_len(size_t len) noexcept {
HITCBC 80   28303 length = uint16_t(len); 80   28303 length = uint16_t(len);
HITCBC 81   28303 } 81   28303 }
HITCBC 82   259478 constexpr size_t len() const noexcept { 82   259478 constexpr size_t len() const noexcept {
HITCBC 83   259478 return length; 83   259478 return length;
84   } 84   }
HITCBC 85   3789 constexpr bool is_empty() const noexcept { 85   3789 constexpr bool is_empty() const noexcept {
HITCBC 86   3789 return length == 0; 86   3789 return length == 0;
87   } 87   }
HITCBC 88   45829 constexpr size_t capacity() const noexcept { 88   45829 constexpr size_t capacity() const noexcept {
HITCBC 89   45829 return size; 89   45829 return size;
90   } 90   }
91   // append item to vector, without bounds checking 91   // append item to vector, without bounds checking
HITCBC 92   27233 BOOST_JSON_CXX14_CONSTEXPR void push_unchecked(limb value) noexcept { 92   27233 BOOST_JSON_CXX14_CONSTEXPR void push_unchecked(limb value) noexcept {
HITCBC 93   27233 data[length] = value; 93   27233 data[length] = value;
HITCBC 94   27233 length++; 94   27233 length++;
HITCBC 95   27233 } 95   27233 }
96   // append item to vector, returning if item was added 96   // append item to vector, returning if item was added
HITCBC 97   25622 BOOST_JSON_CXX14_CONSTEXPR bool try_push(limb value) noexcept { 97   25622 BOOST_JSON_CXX14_CONSTEXPR bool try_push(limb value) noexcept {
HITCBC 98   25622 if (len() < capacity()) { 98   25622 if (len() < capacity()) {
HITCBC 99   25622 push_unchecked(value); 99   25622 push_unchecked(value);
HITCBC 100   25622 return true; 100   25622 return true;
101   } else { 101   } else {
MISUBC 102   ✗ return false; 102   ✗ return false;
103   } 103   }
104   } 104   }
105   // add items to the vector, from a span, without bounds checking 105   // add items to the vector, from a span, without bounds checking
HITCBC 106   10120 BOOST_JSON_FASTFLOAT_CONSTEXPR20 void extend_unchecked(limb_span s) noexcept { 106   10120 BOOST_JSON_FASTFLOAT_CONSTEXPR20 void extend_unchecked(limb_span s) noexcept {
HITCBC 107   10120 limb* ptr = data + length; 107   10120 limb* ptr = data + length;
HITCBC 108   10120 std::copy_n(s.ptr, s.len(), ptr); 108   10120 std::copy_n(s.ptr, s.len(), ptr);
HITCBC 109   10120 set_len(len() + s.len()); 109   10120 set_len(len() + s.len());
HITCBC 110   10120 } 110   10120 }
111   // try to add items to the vector, returning if items were added 111   // try to add items to the vector, returning if items were added
HITCBC 112   10120 BOOST_JSON_FASTFLOAT_CONSTEXPR20 bool try_extend(limb_span s) noexcept { 112   10120 BOOST_JSON_FASTFLOAT_CONSTEXPR20 bool try_extend(limb_span s) noexcept {
HITCBC 113   10120 if (len() + s.len() <= capacity()) { 113   10120 if (len() + s.len() <= capacity()) {
HITCBC 114   10120 extend_unchecked(s); 114   10120 extend_unchecked(s);
HITCBC 115   10120 return true; 115   10120 return true;
116   } else { 116   } else {
MISUBC 117   ✗ return false; 117   ✗ return false;
118   } 118   }
119   } 119   }
120   // resize the vector, without bounds checking 120   // resize the vector, without bounds checking
121   // if the new size is longer than the vector, assign value to each 121   // if the new size is longer than the vector, assign value to each
122   // appended item. 122   // appended item.
123   BOOST_JSON_FASTFLOAT_CONSTEXPR20 123   BOOST_JSON_FASTFLOAT_CONSTEXPR20
HITCBC 124   7673 void resize_unchecked(size_t new_len, limb value) noexcept { 124   7673 void resize_unchecked(size_t new_len, limb value) noexcept {
HITCBC 125   7673 if (new_len > len()) { 125   7673 if (new_len > len()) {
HITCBC 126   7673 size_t count = new_len - len(); 126   7673 size_t count = new_len - len();
HITCBC 127   7673 limb* first = data + len(); 127   7673 limb* first = data + len();
HITCBC 128   7673 limb* last = first + count; 128   7673 limb* last = first + count;
HITCBC 129   7673 ::std::fill(first, last, value); 129   7673 ::std::fill(first, last, value);
HITCBC 130   7673 set_len(new_len); 130   7673 set_len(new_len);
131   } else { 131   } else {
MISUBC 132   ✗ set_len(new_len); 132   ✗ set_len(new_len);
133   } 133   }
HITCBC 134   7673 } 134   7673 }
135   // try to resize the vector, returning if the vector was resized. 135   // try to resize the vector, returning if the vector was resized.
HITCBC 136   7673 BOOST_JSON_FASTFLOAT_CONSTEXPR20 bool try_resize(size_t new_len, limb value) noexcept { 136   7673 BOOST_JSON_FASTFLOAT_CONSTEXPR20 bool try_resize(size_t new_len, limb value) noexcept {
HITCBC 137   7673 if (new_len > capacity()) { 137   7673 if (new_len > capacity()) {
MISUBC 138   ✗ return false; 138   ✗ return false;
139   } else { 139   } else {
HITCBC 140   7673 resize_unchecked(new_len, value); 140   7673 resize_unchecked(new_len, value);
HITCBC 141   7673 return true; 141   7673 return true;
142   } 142   }
143   } 143   }
144   // check if any limbs are non-zero after the given index. 144   // check if any limbs are non-zero after the given index.
145   // this needs to be done in reverse order, since the index 145   // this needs to be done in reverse order, since the index
146   // is relative to the most significant limbs. 146   // is relative to the most significant limbs.
HITCBC 147   1375 BOOST_JSON_CXX14_CONSTEXPR bool nonzero(size_t index) const noexcept { 147   1375 BOOST_JSON_CXX14_CONSTEXPR bool nonzero(size_t index) const noexcept {
HITCBC 148   1375 while (index < len()) { 148   1375 while (index < len()) {
HITCBC 149   1369 if (rindex(index) != 0) { 149   1369 if (rindex(index) != 0) {
HITCBC 150   1369 return true; 150   1369 return true;
151   } 151   }
MISUBC 152   ✗ index++; 152   ✗ index++;
153   } 153   }
HITCBC 154   6 return false; 154   6 return false;
155   } 155   }
156   // normalize the big integer, so most-significant zero limbs are removed. 156   // normalize the big integer, so most-significant zero limbs are removed.
HITCBC 157   3635 BOOST_JSON_CXX14_CONSTEXPR void normalize() noexcept { 157   3635 BOOST_JSON_CXX14_CONSTEXPR void normalize() noexcept {
HITCBC 158   3635 while (len() > 0 && rindex(0) == 0) { 158   3635 while (len() > 0 && rindex(0) == 0) {
MISUBC 159   ✗ length--; 159   ✗ length--;
160   } 160   }
HITCBC 161   3635 } 161   3635 }
162   }; 162   };
163   163  
164   BOOST_FORCEINLINE BOOST_JSON_CXX14_CONSTEXPR_NO_INLINE 164   BOOST_FORCEINLINE BOOST_JSON_CXX14_CONSTEXPR_NO_INLINE
165   uint64_t empty_hi64(bool& truncated) noexcept { 165   uint64_t empty_hi64(bool& truncated) noexcept {
MISUBC 166   ✗ truncated = false; 166   ✗ truncated = false;
MISUBC 167   ✗ return 0; 167   ✗ return 0;
168   } 168   }
169   169  
170   BOOST_FORCEINLINE BOOST_JSON_FASTFLOAT_CONSTEXPR20 170   BOOST_FORCEINLINE BOOST_JSON_FASTFLOAT_CONSTEXPR20
171   uint64_t uint64_hi64(uint64_t r0, bool& truncated) noexcept { 171   uint64_t uint64_hi64(uint64_t r0, bool& truncated) noexcept {
MISUBC 172   ✗ truncated = false; 172   ✗ truncated = false;
MISUBC 173   ✗ int shl = leading_zeroes(r0); 173   ✗ int shl = leading_zeroes(r0);
MISUBC 174   ✗ return r0 << shl; 174   ✗ return r0 << shl;
175   } 175   }
176   176  
177   BOOST_FORCEINLINE BOOST_JSON_FASTFLOAT_CONSTEXPR20 177   BOOST_FORCEINLINE BOOST_JSON_FASTFLOAT_CONSTEXPR20
178   uint64_t uint64_hi64(uint64_t r0, uint64_t r1, bool& truncated) noexcept { 178   uint64_t uint64_hi64(uint64_t r0, uint64_t r1, bool& truncated) noexcept {
HITCBC 179   1375 int shl = leading_zeroes(r0); 179   1375 int shl = leading_zeroes(r0);
HITCBC 180   1375 if (shl == 0) { 180   1375 if (shl == 0) {
HITCBC 181   27 truncated = r1 != 0; 181   27 truncated = r1 != 0;
HITCBC 182   27 return r0; 182   27 return r0;
183   } else { 183   } else {
HITCBC 184   1348 int shr = 64 - shl; 184   1348 int shr = 64 - shl;
HITCBC 185   1348 truncated = (r1 << shl) != 0; 185   1348 truncated = (r1 << shl) != 0;
HITCBC 186   1348 return (r0 << shl) | (r1 >> shr); 186   1348 return (r0 << shl) | (r1 >> shr);
187   } 187   }
188   } 188   }
189   189  
190   BOOST_FORCEINLINE BOOST_JSON_FASTFLOAT_CONSTEXPR20 190   BOOST_FORCEINLINE BOOST_JSON_FASTFLOAT_CONSTEXPR20
191   uint64_t uint32_hi64(uint32_t r0, bool& truncated) noexcept { 191   uint64_t uint32_hi64(uint32_t r0, bool& truncated) noexcept {
192   return uint64_hi64(r0, truncated); 192   return uint64_hi64(r0, truncated);
193   } 193   }
194   194  
195   BOOST_FORCEINLINE BOOST_JSON_FASTFLOAT_CONSTEXPR20 195   BOOST_FORCEINLINE BOOST_JSON_FASTFLOAT_CONSTEXPR20
196   uint64_t uint32_hi64(uint32_t r0, uint32_t r1, bool& truncated) noexcept { 196   uint64_t uint32_hi64(uint32_t r0, uint32_t r1, bool& truncated) noexcept {
197   uint64_t x0 = r0; 197   uint64_t x0 = r0;
198   uint64_t x1 = r1; 198   uint64_t x1 = r1;
199   return uint64_hi64((x0 << 32) | x1, truncated); 199   return uint64_hi64((x0 << 32) | x1, truncated);
200   } 200   }
201   201  
202   BOOST_FORCEINLINE BOOST_JSON_FASTFLOAT_CONSTEXPR20 202   BOOST_FORCEINLINE BOOST_JSON_FASTFLOAT_CONSTEXPR20
203   uint64_t uint32_hi64(uint32_t r0, uint32_t r1, uint32_t r2, bool& truncated) noexcept { 203   uint64_t uint32_hi64(uint32_t r0, uint32_t r1, uint32_t r2, bool& truncated) noexcept {
204   uint64_t x0 = r0; 204   uint64_t x0 = r0;
205   uint64_t x1 = r1; 205   uint64_t x1 = r1;
206   uint64_t x2 = r2; 206   uint64_t x2 = r2;
207   return uint64_hi64(x0, (x1 << 32) | x2, truncated); 207   return uint64_hi64(x0, (x1 << 32) | x2, truncated);
208   } 208   }
209   209  
210   // add two small integers, checking for overflow. 210   // add two small integers, checking for overflow.
211   // we want an efficient operation. for msvc, where 211   // we want an efficient operation. for msvc, where
212   // we don't have built-in intrinsics, this is still 212   // we don't have built-in intrinsics, this is still
213   // pretty fast. 213   // pretty fast.
214   BOOST_FORCEINLINE BOOST_JSON_FASTFLOAT_CONSTEXPR20 214   BOOST_FORCEINLINE BOOST_JSON_FASTFLOAT_CONSTEXPR20
215   limb scalar_add(limb x, limb y, bool& overflow) noexcept { 215   limb scalar_add(limb x, limb y, bool& overflow) noexcept {
216   limb z; 216   limb z;
217   // gcc and clang 217   // gcc and clang
218   #if defined(__has_builtin) 218   #if defined(__has_builtin)
219   #if __has_builtin(__builtin_add_overflow) 219   #if __has_builtin(__builtin_add_overflow)
HITCBC 220   38490 if (!cpp20_and_in_constexpr()) { 220   38490 if (!cpp20_and_in_constexpr()) {
HITCBC 221   38490 overflow = __builtin_add_overflow(x, y, &z); 221   38490 overflow = __builtin_add_overflow(x, y, &z);
HITCBC 222   38490 return z; 222   38490 return z;
223   } 223   }
224   #endif 224   #endif
225   #endif 225   #endif
226   226  
227   // generic, this still optimizes correctly on MSVC. 227   // generic, this still optimizes correctly on MSVC.
MISUBC 228   ✗ z = x + y; 228   ✗ z = x + y;
MISUBC 229   ✗ overflow = z < x; 229   ✗ overflow = z < x;
MISUBC 230   ✗ return z; 230   ✗ return z;
231   } 231   }
232   232  
233   // multiply two small integers, getting both the high and low bits. 233   // multiply two small integers, getting both the high and low bits.
234   BOOST_FORCEINLINE BOOST_JSON_FASTFLOAT_CONSTEXPR20 234   BOOST_FORCEINLINE BOOST_JSON_FASTFLOAT_CONSTEXPR20
235   limb scalar_mul(limb x, limb y, limb& carry) noexcept { 235   limb scalar_mul(limb x, limb y, limb& carry) noexcept {
236   #ifdef BOOST_JSON_FASTFLOAT_64BIT_LIMB 236   #ifdef BOOST_JSON_FASTFLOAT_64BIT_LIMB
237   #if defined(__SIZEOF_INT128__) 237   #if defined(__SIZEOF_INT128__)
238   // GCC and clang both define it as an extension. 238   // GCC and clang both define it as an extension.
HITCBC 239   80707 __uint128_t z = __uint128_t(x) * __uint128_t(y) + __uint128_t(carry); 239   80707 __uint128_t z = __uint128_t(x) * __uint128_t(y) + __uint128_t(carry);
HITCBC 240   80707 carry = limb(z >> limb_bits); 240   80707 carry = limb(z >> limb_bits);
HITCBC 241   80707 return limb(z); 241   80707 return limb(z);
242   #else 242   #else
243   // fallback, no native 128-bit integer multiplication with carry. 243   // fallback, no native 128-bit integer multiplication with carry.
244   // on msvc, this optimizes identically, somehow. 244   // on msvc, this optimizes identically, somehow.
245   value128 z = full_multiplication(x, y); 245   value128 z = full_multiplication(x, y);
246   bool overflow; 246   bool overflow;
247   z.low = scalar_add(z.low, carry, overflow); 247   z.low = scalar_add(z.low, carry, overflow);
248   z.high += uint64_t(overflow); // cannot overflow 248   z.high += uint64_t(overflow); // cannot overflow
249   carry = z.high; 249   carry = z.high;
250   return z.low; 250   return z.low;
251   #endif 251   #endif
252   #else 252   #else
253   uint64_t z = uint64_t(x) * uint64_t(y) + uint64_t(carry); 253   uint64_t z = uint64_t(x) * uint64_t(y) + uint64_t(carry);
254   carry = limb(z >> limb_bits); 254   carry = limb(z >> limb_bits);
255   return limb(z); 255   return limb(z);
256   #endif 256   #endif
257   } 257   }
258   258  
259   // add scalar value to bigint starting from offset. 259   // add scalar value to bigint starting from offset.
260   // used in grade school multiplication 260   // used in grade school multiplication
261   template <uint16_t size> 261   template <uint16_t size>
262   inline BOOST_JSON_FASTFLOAT_CONSTEXPR20 262   inline BOOST_JSON_FASTFLOAT_CONSTEXPR20
HITCBC 263   9437 bool small_add_from(stackvec<size>& vec, limb y, size_t start) noexcept { 263   9437 bool small_add_from(stackvec<size>& vec, limb y, size_t start) noexcept {
HITCBC 264   9437 size_t index = start; 264   9437 size_t index = start;
HITCBC 265   9437 limb carry = y; 265   9437 limb carry = y;
266   bool overflow; 266   bool overflow;
HITCBC 267   16116 while (carry != 0 && index < vec.len()) { 267   16116 while (carry != 0 && index < vec.len()) {
HITCBC 268   6679 vec[index] = scalar_add(vec[index], carry, overflow); 268   6679 vec[index] = scalar_add(vec[index], carry, overflow);
HITCBC 269   6679 carry = limb(overflow); 269   6679 carry = limb(overflow);
HITCBC 270   6679 index += 1; 270   6679 index += 1;
271   } 271   }
HITCBC 272   9437 if (carry != 0) { 272   9437 if (carry != 0) {
HITCBC 273   2986 BOOST_JSON_FASTFLOAT_TRY(vec.try_push(carry)); 273   2986 BOOST_JSON_FASTFLOAT_TRY(vec.try_push(carry));
274   } 274   }
HITCBC 275   9437 return true; 275   9437 return true;
276   } 276   }
277   277  
278   // add scalar value to bigint. 278   // add scalar value to bigint.
279   template <uint16_t size> 279   template <uint16_t size>
280   BOOST_FORCEINLINE BOOST_JSON_FASTFLOAT_CONSTEXPR20 280   BOOST_FORCEINLINE BOOST_JSON_FASTFLOAT_CONSTEXPR20
281   bool small_add(stackvec<size>& vec, limb y) noexcept { 281   bool small_add(stackvec<size>& vec, limb y) noexcept {
HITCBC 282   9437 return small_add_from(vec, y, 0); 282   9437 return small_add_from(vec, y, 0);
283   } 283   }
284   284  
285   // multiply bigint by scalar value. 285   // multiply bigint by scalar value.
286   template <uint16_t size> 286   template <uint16_t size>
287   inline BOOST_JSON_FASTFLOAT_CONSTEXPR20 287   inline BOOST_JSON_FASTFLOAT_CONSTEXPR20
HITCBC 288   28029 bool small_mul(stackvec<size>& vec, limb y) noexcept { 288   28029 bool small_mul(stackvec<size>& vec, limb y) noexcept {
HITCBC 289   28029 limb carry = 0; 289   28029 limb carry = 0;
HITCBC 290   108736 for (size_t index = 0; index < vec.len(); index++) { 290   108736 for (size_t index = 0; index < vec.len(); index++) {
HITCBC 291   161414 vec[index] = scalar_mul(vec[index], y, carry); 291   161414 vec[index] = scalar_mul(vec[index], y, carry);
292   } 292   }
HITCBC 293   28029 if (carry != 0) { 293   28029 if (carry != 0) {
HITCBC 294   21102 BOOST_JSON_FASTFLOAT_TRY(vec.try_push(carry)); 294   21102 BOOST_JSON_FASTFLOAT_TRY(vec.try_push(carry));
295   } 295   }
HITCBC 296   28029 return true; 296   28029 return true;
297   } 297   }
298   298  
299   // add bigint to bigint starting from index. 299   // add bigint to bigint starting from index.
300   // used in grade school multiplication 300   // used in grade school multiplication
301   template <uint16_t size> 301   template <uint16_t size>
302   BOOST_JSON_FASTFLOAT_CONSTEXPR20 302   BOOST_JSON_FASTFLOAT_CONSTEXPR20
HITCBC 303   8096 bool large_add_from(stackvec<size>& x, limb_span y, size_t start) noexcept { 303   8096 bool large_add_from(stackvec<size>& x, limb_span y, size_t start) noexcept {
304   // the effective x buffer is from `xstart..x.len()`, so exit early 304   // the effective x buffer is from `xstart..x.len()`, so exit early
305   // if we can't get that current range. 305   // if we can't get that current range.
HITCBC 306   8096 if (x.len() < start || y.len() > x.len() - start) { 306   8096 if (x.len() < start || y.len() > x.len() - start) {
HITCBC 307   7673 BOOST_JSON_FASTFLOAT_TRY(x.try_resize(y.len() + start, 0)); 307   7673 BOOST_JSON_FASTFLOAT_TRY(x.try_resize(y.len() + start, 0));
308   } 308   }
309   309  
HITCBC 310   8096 bool carry = false; 310   8096 bool carry = false;
HITCBC 311   34341 for (size_t index = 0; index < y.len(); index++) { 311   34341 for (size_t index = 0; index < y.len(); index++) {
HITCBC 312   26245 limb xi = x[index + start]; 312   26245 limb xi = x[index + start];
HITCBC 313   26245 limb yi = y[index]; 313   26245 limb yi = y[index];
HITCBC 314   26245 bool c1 = false; 314   26245 bool c1 = false;
HITCBC 315   26245 bool c2 = false; 315   26245 bool c2 = false;
HITCBC 316   26245 xi = scalar_add(xi, yi, c1); 316   26245 xi = scalar_add(xi, yi, c1);
HITCBC 317   26245 if (carry) { 317   26245 if (carry) {
HITCBC 318   5566 xi = scalar_add(xi, 1, c2); 318   5566 xi = scalar_add(xi, 1, c2);
319   } 319   }
HITCBC 320   26245 x[index + start] = xi; 320   26245 x[index + start] = xi;
HITCBC 321   26245 carry = c1 | c2; 321   26245 carry = c1 | c2;
322   } 322   }
323   323  
324   // handle overflow 324   // handle overflow
HITCBC 325   8096 if (carry) { 325   8096 if (carry) {
MISUBC 326   ✗ BOOST_JSON_FASTFLOAT_TRY(small_add_from(x, 1, y.len() + start)); 326   ✗ BOOST_JSON_FASTFLOAT_TRY(small_add_from(x, 1, y.len() + start));
327   } 327   }
HITCBC 328   8096 return true; 328   8096 return true;
329   } 329   }
330   330  
331   // add bigint to bigint. 331   // add bigint to bigint.
332   template <uint16_t size> 332   template <uint16_t size>
333   BOOST_FORCEINLINE BOOST_JSON_FASTFLOAT_CONSTEXPR20 333   BOOST_FORCEINLINE BOOST_JSON_FASTFLOAT_CONSTEXPR20
334   bool large_add_from(stackvec<size>& x, limb_span y) noexcept { 334   bool large_add_from(stackvec<size>& x, limb_span y) noexcept {
335   return large_add_from(x, y, 0); 335   return large_add_from(x, y, 0);
336   } 336   }
337   337  
338   // grade-school multiplication algorithm 338   // grade-school multiplication algorithm
339   template <uint16_t size> 339   template <uint16_t size>
340   BOOST_JSON_FASTFLOAT_CONSTEXPR20 340   BOOST_JSON_FASTFLOAT_CONSTEXPR20
HITCBC 341   2024 bool long_mul(stackvec<size>& x, limb_span y) noexcept { 341   2024 bool long_mul(stackvec<size>& x, limb_span y) noexcept {
HITCBC 342   2024 limb_span xs = limb_span(x.data, x.len()); 342   2024 limb_span xs = limb_span(x.data, x.len());
HITCBC 343   2024 stackvec<size> z(xs); 343   2024 stackvec<size> z(xs);
HITCBC 344   2024 limb_span zs = limb_span(z.data, z.len()); 344   2024 limb_span zs = limb_span(z.data, z.len());
345   345  
HITCBC 346   2024 if (y.len() != 0) { 346   2024 if (y.len() != 0) {
HITCBC 347   2024 limb y0 = y[0]; 347   2024 limb y0 = y[0];
HITCBC 348   2024 BOOST_JSON_FASTFLOAT_TRY(small_mul(x, y0)); 348   2024 BOOST_JSON_FASTFLOAT_TRY(small_mul(x, y0));
HITCBC 349   10120 for (size_t index = 1; index < y.len(); index++) { 349   10120 for (size_t index = 1; index < y.len(); index++) {
HITCBC 350   8096 limb yi = y[index]; 350   8096 limb yi = y[index];
HITCBC 351   8096 stackvec<size> zi; 351   8096 stackvec<size> zi;
HITCBC 352   8096 if (yi != 0) { 352   8096 if (yi != 0) {
353   // re-use the same buffer throughout 353   // re-use the same buffer throughout
HITCBC 354   8096 zi.set_len(0); 354   8096 zi.set_len(0);
HITCBC 355   8096 BOOST_JSON_FASTFLOAT_TRY(zi.try_extend(zs)); 355   8096 BOOST_JSON_FASTFLOAT_TRY(zi.try_extend(zs));
HITCBC 356   8096 BOOST_JSON_FASTFLOAT_TRY(small_mul(zi, yi)); 356   8096 BOOST_JSON_FASTFLOAT_TRY(small_mul(zi, yi));
HITCBC 357   8096 limb_span zis = limb_span(zi.data, zi.len()); 357   8096 limb_span zis = limb_span(zi.data, zi.len());
HITCBC 358   8096 BOOST_JSON_FASTFLOAT_TRY(large_add_from(x, zis, index)); 358   8096 BOOST_JSON_FASTFLOAT_TRY(large_add_from(x, zis, index));
359   } 359   }
360   } 360   }
361   } 361   }
362   362  
HITCBC 363   2024 x.normalize(); 363   2024 x.normalize();
HITCBC 364   2024 return true; 364   2024 return true;
365   } 365   }
366   366  
367   // grade-school multiplication algorithm 367   // grade-school multiplication algorithm
368   template <uint16_t size> 368   template <uint16_t size>
369   BOOST_JSON_FASTFLOAT_CONSTEXPR20 369   BOOST_JSON_FASTFLOAT_CONSTEXPR20
HITCBC 370   2024 bool large_mul(stackvec<size>& x, limb_span y) noexcept { 370   2024 bool large_mul(stackvec<size>& x, limb_span y) noexcept {
HITCBC 371   2024 if (y.len() == 1) { 371   2024 if (y.len() == 1) {
MISUBC 372   ✗ BOOST_JSON_FASTFLOAT_TRY(small_mul(x, y[0])); 372   ✗ BOOST_JSON_FASTFLOAT_TRY(small_mul(x, y[0]));
373   } else { 373   } else {
HITCBC 374   2024 BOOST_JSON_FASTFLOAT_TRY(long_mul(x, y)); 374   2024 BOOST_JSON_FASTFLOAT_TRY(long_mul(x, y));
375   } 375   }
HITCBC 376   2024 return true; 376   2024 return true;
377   } 377   }
378   378  
379   template <typename = void> 379   template <typename = void>
380   struct pow5_tables { 380   struct pow5_tables {
381   static constexpr uint32_t large_step = 135; 381   static constexpr uint32_t large_step = 135;
382   static constexpr uint64_t small_power_of_5[] = { 382   static constexpr uint64_t small_power_of_5[] = {
383   1UL, 5UL, 25UL, 125UL, 625UL, 3125UL, 15625UL, 78125UL, 390625UL, 383   1UL, 5UL, 25UL, 125UL, 625UL, 3125UL, 15625UL, 78125UL, 390625UL,
384   1953125UL, 9765625UL, 48828125UL, 244140625UL, 1220703125UL, 384   1953125UL, 9765625UL, 48828125UL, 244140625UL, 1220703125UL,
385   6103515625UL, 30517578125UL, 152587890625UL, 762939453125UL, 385   6103515625UL, 30517578125UL, 152587890625UL, 762939453125UL,
386   3814697265625UL, 19073486328125UL, 95367431640625UL, 476837158203125UL, 386   3814697265625UL, 19073486328125UL, 95367431640625UL, 476837158203125UL,
387   2384185791015625UL, 11920928955078125UL, 59604644775390625UL, 387   2384185791015625UL, 11920928955078125UL, 59604644775390625UL,
388   298023223876953125UL, 1490116119384765625UL, 7450580596923828125UL, 388   298023223876953125UL, 1490116119384765625UL, 7450580596923828125UL,
389   }; 389   };
390   #ifdef BOOST_JSON_FASTFLOAT_64BIT_LIMB 390   #ifdef BOOST_JSON_FASTFLOAT_64BIT_LIMB
391   constexpr static limb large_power_of_5[] = { 391   constexpr static limb large_power_of_5[] = {
392   1414648277510068013UL, 9180637584431281687UL, 4539964771860779200UL, 392   1414648277510068013UL, 9180637584431281687UL, 4539964771860779200UL,
393   10482974169319127550UL, 198276706040285095UL}; 393   10482974169319127550UL, 198276706040285095UL};
394   #else 394   #else
395   constexpr static limb large_power_of_5[] = { 395   constexpr static limb large_power_of_5[] = {
396   4279965485U, 329373468U, 4020270615U, 2137533757U, 4287402176U, 396   4279965485U, 329373468U, 4020270615U, 2137533757U, 4287402176U,
397   1057042919U, 1071430142U, 2440757623U, 381945767U, 46164893U}; 397   1057042919U, 1071430142U, 2440757623U, 381945767U, 46164893U};
398   #endif 398   #endif
399   }; 399   };
400   400  
401   template <typename T> 401   template <typename T>
402   constexpr uint32_t pow5_tables<T>::large_step; 402   constexpr uint32_t pow5_tables<T>::large_step;
403   403  
404   template <typename T> 404   template <typename T>
405   constexpr uint64_t pow5_tables<T>::small_power_of_5[]; 405   constexpr uint64_t pow5_tables<T>::small_power_of_5[];
406   406  
407   template <typename T> 407   template <typename T>
408   constexpr limb pow5_tables<T>::large_power_of_5[]; 408   constexpr limb pow5_tables<T>::large_power_of_5[];
409   409  
410   // big integer type. implements a small subset of big integer 410   // big integer type. implements a small subset of big integer
411   // arithmetic, using simple algorithms since asymptotically 411   // arithmetic, using simple algorithms since asymptotically
412   // faster algorithms are slower for a small number of limbs. 412   // faster algorithms are slower for a small number of limbs.
413   // all operations assume the big-integer is normalized. 413   // all operations assume the big-integer is normalized.
414   struct bigint : pow5_tables<> { 414   struct bigint : pow5_tables<> {
415   // storage of the limbs, in little-endian order. 415   // storage of the limbs, in little-endian order.
416   stackvec<bigint_limbs> vec; 416   stackvec<bigint_limbs> vec;
417   417  
HITCBC 418   2986 BOOST_JSON_FASTFLOAT_CONSTEXPR20 bigint(): vec() {} 418   2986 BOOST_JSON_FASTFLOAT_CONSTEXPR20 bigint(): vec() {}
419   bigint(const bigint &) = delete; 419   bigint(const bigint &) = delete;
420   bigint &operator=(const bigint &) = delete; 420   bigint &operator=(const bigint &) = delete;
421   bigint(bigint &&) = delete; 421   bigint(bigint &&) = delete;
422   bigint &operator=(bigint &&other) = delete; 422   bigint &operator=(bigint &&other) = delete;
423   423  
HITCBC 424   1611 BOOST_JSON_FASTFLOAT_CONSTEXPR20 bigint(uint64_t value): vec() { 424   1611 BOOST_JSON_FASTFLOAT_CONSTEXPR20 bigint(uint64_t value): vec() {
425   #ifdef BOOST_JSON_FASTFLOAT_64BIT_LIMB 425   #ifdef BOOST_JSON_FASTFLOAT_64BIT_LIMB
HITCBC 426   1611 vec.push_unchecked(value); 426   1611 vec.push_unchecked(value);
427   #else 427   #else
428   vec.push_unchecked(uint32_t(value)); 428   vec.push_unchecked(uint32_t(value));
429   vec.push_unchecked(uint32_t(value >> 32)); 429   vec.push_unchecked(uint32_t(value >> 32));
430   #endif 430   #endif
HITCBC 431   1611 vec.normalize(); 431   1611 vec.normalize();
HITCBC 432   1611 } 432   1611 }
433   433  
434   // get the high 64 bits from the vector, and if bits were truncated. 434   // get the high 64 bits from the vector, and if bits were truncated.
435   // this is to get the significant digits for the float. 435   // this is to get the significant digits for the float.
HITCBC 436   1375 BOOST_JSON_FASTFLOAT_CONSTEXPR20 uint64_t hi64(bool& truncated) const noexcept { 436   1375 BOOST_JSON_FASTFLOAT_CONSTEXPR20 uint64_t hi64(bool& truncated) const noexcept {
437   #ifdef BOOST_JSON_FASTFLOAT_64BIT_LIMB 437   #ifdef BOOST_JSON_FASTFLOAT_64BIT_LIMB
HITCBC 438   1375 if (vec.len() == 0) { 438   1375 if (vec.len() == 0) {
MISUBC 439   ✗ return empty_hi64(truncated); 439   ✗ return empty_hi64(truncated);
HITCBC 440   1375 } else if (vec.len() == 1) { 440   1375 } else if (vec.len() == 1) {
MISUBC 441   ✗ return uint64_hi64(vec.rindex(0), truncated); 441   ✗ return uint64_hi64(vec.rindex(0), truncated);
442   } else { 442   } else {
HITCBC 443   1375 uint64_t result = uint64_hi64(vec.rindex(0), vec.rindex(1), truncated); 443   1375 uint64_t result = uint64_hi64(vec.rindex(0), vec.rindex(1), truncated);
HITCBC 444   1375 truncated |= vec.nonzero(2); 444   1375 truncated |= vec.nonzero(2);
HITCBC 445   1375 return result; 445   1375 return result;
446   } 446   }
447   #else 447   #else
448   if (vec.len() == 0) { 448   if (vec.len() == 0) {
449   return empty_hi64(truncated); 449   return empty_hi64(truncated);
450   } else if (vec.len() == 1) { 450   } else if (vec.len() == 1) {
451   return uint32_hi64(vec.rindex(0), truncated); 451   return uint32_hi64(vec.rindex(0), truncated);
452   } else if (vec.len() == 2) { 452   } else if (vec.len() == 2) {
453   return uint32_hi64(vec.rindex(0), vec.rindex(1), truncated); 453   return uint32_hi64(vec.rindex(0), vec.rindex(1), truncated);
454   } else { 454   } else {
455   uint64_t result = uint32_hi64(vec.rindex(0), vec.rindex(1), vec.rindex(2), truncated); 455   uint64_t result = uint32_hi64(vec.rindex(0), vec.rindex(1), vec.rindex(2), truncated);
456   truncated |= vec.nonzero(3); 456   truncated |= vec.nonzero(3);
457   return result; 457   return result;
458   } 458   }
459   #endif 459   #endif
460   } 460   }
461   461  
462   // compare two big integers, returning the large value. 462   // compare two big integers, returning the large value.
463   // assumes both are normalized. if the return value is 463   // assumes both are normalized. if the return value is
464   // negative, other is larger, if the return value is 464   // negative, other is larger, if the return value is
465   // positive, this is larger, otherwise they are equal. 465   // positive, this is larger, otherwise they are equal.
466   // the limbs are stored in little-endian order, so we 466   // the limbs are stored in little-endian order, so we
467   // must compare the limbs in ever order. 467   // must compare the limbs in ever order.
HITCBC 468   1611 BOOST_JSON_FASTFLOAT_CONSTEXPR20 int compare(const bigint& other) const noexcept { 468   1611 BOOST_JSON_FASTFLOAT_CONSTEXPR20 int compare(const bigint& other) const noexcept {
HITCBC 469   1611 if (vec.len() > other.vec.len()) { 469   1611 if (vec.len() > other.vec.len()) {
MISUBC 470   ✗ return 1; 470   ✗ return 1;
HITCBC 471   1611 } else if (vec.len() < other.vec.len()) { 471   1611 } else if (vec.len() < other.vec.len()) {
MISUBC 472   ✗ return -1; 472   ✗ return -1;
473   } else { 473   } else {
HITCBC 474   3099 for (size_t index = vec.len(); index > 0; index--) { 474   3099 for (size_t index = vec.len(); index > 0; index--) {
HITCBC 475   3099 limb xi = vec[index - 1]; 475   3099 limb xi = vec[index - 1];
HITCBC 476   3099 limb yi = other.vec[index - 1]; 476   3099 limb yi = other.vec[index - 1];
HITCBC 477   3099 if (xi > yi) { 477   3099 if (xi > yi) {
HITCBC 478   767 return 1; 478   767 return 1;
HITCBC 479   2332 } else if (xi < yi) { 479   2332 } else if (xi < yi) {
HITCBC 480   844 return -1; 480   844 return -1;
481   } 481   }
482   } 482   }
MISUBC 483   ✗ return 0; 483   ✗ return 0;
484   } 484   }
485   } 485   }
486   486  
487   // shift left each limb n bits, carrying over to the new limb 487   // shift left each limb n bits, carrying over to the new limb
488   // returns true if we were able to shift all the digits. 488   // returns true if we were able to shift all the digits.
HITCBC 489   2931 BOOST_JSON_FASTFLOAT_CONSTEXPR20 bool shl_bits(size_t n) noexcept { 489   2931 BOOST_JSON_FASTFLOAT_CONSTEXPR20 bool shl_bits(size_t n) noexcept {
490   // Internally, for each item, we shift left by n, and add the previous 490   // Internally, for each item, we shift left by n, and add the previous
491   // right shifted limb-bits. 491   // right shifted limb-bits.
492   // For example, we transform (for u8) shifted left 2, to: 492   // For example, we transform (for u8) shifted left 2, to:
493   // b10100100 b01000010 493   // b10100100 b01000010
494   // b10 b10010001 b00001000 494   // b10 b10010001 b00001000
HITCBC 495   2931 BOOST_ASSERT(n != 0); 495   2931 BOOST_ASSERT(n != 0);
HITCBC 496   2931 BOOST_ASSERT(n < sizeof(limb) * 8); 496   2931 BOOST_ASSERT(n < sizeof(limb) * 8);
497   497  
HITCBC 498   2931 size_t shl = n; 498   2931 size_t shl = n;
HITCBC 499   2931 size_t shr = limb_bits - shl; 499   2931 size_t shr = limb_bits - shl;
HITCBC 500   2931 limb prev = 0; 500   2931 limb prev = 0;
HITCBC 501   17014 for (size_t index = 0; index < vec.len(); index++) { 501   17014 for (size_t index = 0; index < vec.len(); index++) {
HITCBC 502   14083 limb xi = vec[index]; 502   14083 limb xi = vec[index];
HITCBC 503   14083 vec[index] = (xi << shl) | (prev >> shr); 503   14083 vec[index] = (xi << shl) | (prev >> shr);
HITCBC 504   14083 prev = xi; 504   14083 prev = xi;
505   } 505   }
506   506  
HITCBC 507   2931 limb carry = prev >> shr; 507   2931 limb carry = prev >> shr;
HITCBC 508   2931 if (carry != 0) { 508   2931 if (carry != 0) {
HITCBC 509   1534 return vec.try_push(carry); 509   1534 return vec.try_push(carry);
510   } 510   }
HITCBC 511   1397 return true; 511   1397 return true;
512   } 512   }
513   513  
514   // move the limbs left by `n` limbs. 514   // move the limbs left by `n` limbs.
HITCBC 515   2414 BOOST_JSON_FASTFLOAT_CONSTEXPR20 bool shl_limbs(size_t n) noexcept { 515   2414 BOOST_JSON_FASTFLOAT_CONSTEXPR20 bool shl_limbs(size_t n) noexcept {
HITCBC 516   2414 BOOST_ASSERT(n != 0); 516   2414 BOOST_ASSERT(n != 0);
HITCBC 517   2414 if (n + vec.len() > vec.capacity()) { 517   2414 if (n + vec.len() > vec.capacity()) {
MISUBC 518   ✗ return false; 518   ✗ return false;
HITCBC 519   2414 } else if (!vec.is_empty()) { 519   2414 } else if (!vec.is_empty()) {
520   // move limbs 520   // move limbs
HITCBC 521   2414 limb* dst = vec.data + n; 521   2414 limb* dst = vec.data + n;
HITCBC 522   2414 const limb* src = vec.data; 522   2414 const limb* src = vec.data;
HITCBC 523   2414 std::copy_backward(src, src + vec.len(), dst + vec.len()); 523   2414 std::copy_backward(src, src + vec.len(), dst + vec.len());
524   // fill in empty limbs 524   // fill in empty limbs
HITCBC 525   2414 limb* first = vec.data; 525   2414 limb* first = vec.data;
HITCBC 526   2414 limb* last = first + n; 526   2414 limb* last = first + n;
HITCBC 527   2414 ::std::fill(first, last, 0); 527   2414 ::std::fill(first, last, 0);
HITCBC 528   2414 vec.set_len(n + vec.len()); 528   2414 vec.set_len(n + vec.len());
HITCBC 529   2414 return true; 529   2414 return true;
530   } else { 530   } else {
MISUBC 531   ✗ return true; 531   ✗ return true;
532   } 532   }
533   } 533   }
534   534  
535   // move the limbs left by `n` bits. 535   // move the limbs left by `n` bits.
HITCBC 536   2984 BOOST_JSON_FASTFLOAT_CONSTEXPR20 bool shl(size_t n) noexcept { 536   2984 BOOST_JSON_FASTFLOAT_CONSTEXPR20 bool shl(size_t n) noexcept {
HITCBC 537   2984 size_t rem = n % limb_bits; 537   2984 size_t rem = n % limb_bits;
HITCBC 538   2984 size_t div = n / limb_bits; 538   2984 size_t div = n / limb_bits;
HITCBC 539   2984 if (rem != 0) { 539   2984 if (rem != 0) {
HITCBC 540   2931 BOOST_JSON_FASTFLOAT_TRY(shl_bits(rem)); 540   2931 BOOST_JSON_FASTFLOAT_TRY(shl_bits(rem));
541   } 541   }
HITCBC 542   2984 if (div != 0) { 542   2984 if (div != 0) {
HITCBC 543   2414 BOOST_JSON_FASTFLOAT_TRY(shl_limbs(div)); 543   2414 BOOST_JSON_FASTFLOAT_TRY(shl_limbs(div));
544   } 544   }
HITCBC 545   2984 return true; 545   2984 return true;
546   } 546   }
547   547  
548   // get the number of leading zeros in the bigint. 548   // get the number of leading zeros in the bigint.
HITCBC 549   1375 BOOST_JSON_FASTFLOAT_CONSTEXPR20 int ctlz() const noexcept { 549   1375 BOOST_JSON_FASTFLOAT_CONSTEXPR20 int ctlz() const noexcept {
HITCBC 550   1375 if (vec.is_empty()) { 550   1375 if (vec.is_empty()) {
MISUBC 551   ✗ return 0; 551   ✗ return 0;
552   } else { 552   } else {
553   #ifdef BOOST_JSON_FASTFLOAT_64BIT_LIMB 553   #ifdef BOOST_JSON_FASTFLOAT_64BIT_LIMB
HITCBC 554   2750 return leading_zeroes(vec.rindex(0)); 554   2750 return leading_zeroes(vec.rindex(0));
555   #else 555   #else
556   // no use defining a specialized leading_zeroes for a 32-bit type. 556   // no use defining a specialized leading_zeroes for a 32-bit type.
557   uint64_t r0 = vec.rindex(0); 557   uint64_t r0 = vec.rindex(0);
558   return leading_zeroes(r0 << 32); 558   return leading_zeroes(r0 << 32);
559   #endif 559   #endif
560   } 560   }
561   } 561   }
562   562  
563   // get the number of bits in the bigint. 563   // get the number of bits in the bigint.
HITCBC 564   1375 BOOST_JSON_FASTFLOAT_CONSTEXPR20 int bit_length() const noexcept { 564   1375 BOOST_JSON_FASTFLOAT_CONSTEXPR20 int bit_length() const noexcept {
HITCBC 565   1375 int lz = ctlz(); 565   1375 int lz = ctlz();
HITCBC 566   1375 return int(limb_bits * vec.len()) - lz; 566   1375 return int(limb_bits * vec.len()) - lz;
567   } 567   }
568   568  
HITCBC 569   9437 BOOST_JSON_FASTFLOAT_CONSTEXPR20 bool mul(limb y) noexcept { 569   9437 BOOST_JSON_FASTFLOAT_CONSTEXPR20 bool mul(limb y) noexcept {
HITCBC 570   9437 return small_mul(vec, y); 570   9437 return small_mul(vec, y);
571   } 571   }
572   572  
HITCBC 573   9437 BOOST_JSON_FASTFLOAT_CONSTEXPR20 bool add(limb y) noexcept { 573   9437 BOOST_JSON_FASTFLOAT_CONSTEXPR20 bool add(limb y) noexcept {
HITCBC 574   18874 return small_add(vec, y); 574   18874 return small_add(vec, y);
575   } 575   }
576   576  
577   // multiply as if by 2 raised to a power. 577   // multiply as if by 2 raised to a power.
HITCBC 578   2984 BOOST_JSON_FASTFLOAT_CONSTEXPR20 bool pow2(uint32_t exp) noexcept { 578   2984 BOOST_JSON_FASTFLOAT_CONSTEXPR20 bool pow2(uint32_t exp) noexcept {
HITCBC 579   2984 return shl(exp); 579   2984 return shl(exp);
580   } 580   }
581   581  
582   // multiply as if by 5 raised to a power. 582   // multiply as if by 5 raised to a power.
HITCBC 583   2986 BOOST_JSON_FASTFLOAT_CONSTEXPR20 bool pow5(uint32_t exp) noexcept { 583   2986 BOOST_JSON_FASTFLOAT_CONSTEXPR20 bool pow5(uint32_t exp) noexcept {
584   // multiply by a power of 5 584   // multiply by a power of 5
HITCBC 585   2986 constexpr size_t large_length = sizeof(large_power_of_5) / sizeof(limb); 585   2986 constexpr size_t large_length = sizeof(large_power_of_5) / sizeof(limb);
HITCBC 586   2986 limb_span large = limb_span(large_power_of_5, large_length); 586   2986 limb_span large = limb_span(large_power_of_5, large_length);
HITCBC 587   5010 while (exp >= large_step) { 587   5010 while (exp >= large_step) {
HITCBC 588   2024 BOOST_JSON_FASTFLOAT_TRY(large_mul(vec, large)); 588   2024 BOOST_JSON_FASTFLOAT_TRY(large_mul(vec, large));
HITCBC 589   2024 exp -= large_step; 589   2024 exp -= large_step;
590   } 590   }
591   #ifdef BOOST_JSON_FASTFLOAT_64BIT_LIMB 591   #ifdef BOOST_JSON_FASTFLOAT_64BIT_LIMB
HITCBC 592   2986 constexpr uint32_t small_step = 27; 592   2986 constexpr uint32_t small_step = 27;
HITCBC 593   2986 constexpr limb max_native = 7450580596923828125UL; 593   2986 constexpr limb max_native = 7450580596923828125UL;
594   #else 594   #else
595   constexpr uint32_t small_step = 13; 595   constexpr uint32_t small_step = 13;
596   constexpr limb max_native = 1220703125U; 596   constexpr limb max_native = 1220703125U;
597   #endif 597   #endif
HITCBC 598   8590 while (exp >= small_step) { 598   8590 while (exp >= small_step) {
HITCBC 599   5604 BOOST_JSON_FASTFLOAT_TRY(small_mul(vec, max_native)); 599   5604 BOOST_JSON_FASTFLOAT_TRY(small_mul(vec, max_native));
HITCBC 600   5604 exp -= small_step; 600   5604 exp -= small_step;
601   } 601   }
HITCBC 602   2986 if (exp != 0) { 602   2986 if (exp != 0) {
603   // Work around clang bug https://godbolt.org/z/zedh7rrhc 603   // Work around clang bug https://godbolt.org/z/zedh7rrhc
604   // This is similar to https://github.com/llvm/llvm-project/issues/47746, 604   // This is similar to https://github.com/llvm/llvm-project/issues/47746,
605   // except the workaround described there don't work here 605   // except the workaround described there don't work here
HITCBC 606   2868 BOOST_JSON_FASTFLOAT_TRY( 606   2868 BOOST_JSON_FASTFLOAT_TRY(
607   small_mul(vec, limb(((void)small_power_of_5[0], small_power_of_5[exp]))) 607   small_mul(vec, limb(((void)small_power_of_5[0], small_power_of_5[exp])))
608   ); 608   );
609   } 609   }
610   610  
HITCBC 611   2986 return true; 611   2986 return true;
612   } 612   }
613   613  
614   // multiply as if by 10 raised to a power. 614   // multiply as if by 10 raised to a power.
HITCBC 615   1375 BOOST_JSON_FASTFLOAT_CONSTEXPR20 bool pow10(uint32_t exp) noexcept { 615   1375 BOOST_JSON_FASTFLOAT_CONSTEXPR20 bool pow10(uint32_t exp) noexcept {
HITCBC 616   1375 BOOST_JSON_FASTFLOAT_TRY(pow5(exp)); 616   1375 BOOST_JSON_FASTFLOAT_TRY(pow5(exp));
HITCBC 617   1375 return pow2(exp); 617   1375 return pow2(exp);
618   } 618   }
619   }; 619   };
620   620  
621   }}}}}} // namespace fast_float 621   }}}}}} // namespace fast_float
622   622  
623   #endif 623   #endif