-
Notifications
You must be signed in to change notification settings - Fork 1.9k
/
Copy pathdragonbox.h
4196 lines (3772 loc) · 238 KB
/
dragonbox.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
// SPDX-FileCopyrightText: 2020-2024 Junekey Jeon
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
// SPDX-License-Identifier: BSL-1.0
// SPDX-License-Identifier: MIT
// This file is an adjusted copy of https://github.com/jk-jeon/dragonbox
// Junekey Jeon agreed to license this file under MIT license explicitly for
// usage in yaml-cpp.
//
// Changes to the original dragonbox library:
// - Added additional license information and information at top
// - Wrapped the 'jkj' namespace in an additional 'YAML' namespace
#ifndef JKJ_HEADER_DRAGONBOX
#define JKJ_HEADER_DRAGONBOX
// Attribute for storing static data into a dedicated place, e.g. flash memory. Every ODR-used
// static data declaration will be decorated with this macro. The users may define this macro,
// before including the library headers, into whatever they want.
#ifndef JKJ_STATIC_DATA_SECTION
#define JKJ_STATIC_DATA_SECTION
#else
#define JKJ_STATIC_DATA_SECTION_DEFINED 1
#endif
// To use the library with toolchains without standard C++ headers, the users may define this macro
// into their custom namespace which contains the defintions of all the standard C++ library
// features used in this header. (The list can be found below.)
#ifndef JKJ_STD_REPLACEMENT_NAMESPACE
#define JKJ_STD_REPLACEMENT_NAMESPACE std
#include <cassert>
#include <cstdint>
#include <cstring>
#include <limits>
#include <type_traits>
#ifdef __has_include
#if __has_include(<version>)
#include <version>
#endif
#endif
#else
#define JKJ_STD_REPLACEMENT_NAMESPACE_DEFINED 1
#endif
////////////////////////////////////////////////////////////////////////////////////////
// Language feature detections.
////////////////////////////////////////////////////////////////////////////////////////
// C++14 constexpr
#if defined(__cpp_constexpr) && __cpp_constexpr >= 201304L
#define JKJ_HAS_CONSTEXPR14 1
#elif __cplusplus >= 201402L
#define JKJ_HAS_CONSTEXPR14 1
#elif defined(_MSC_VER) && _MSC_VER >= 1910 && _MSVC_LANG >= 201402L
#define JKJ_HAS_CONSTEXPR14 1
#else
#define JKJ_HAS_CONSTEXPR14 0
#endif
#if JKJ_HAS_CONSTEXPR14
#define JKJ_CONSTEXPR14 constexpr
#else
#define JKJ_CONSTEXPR14
#endif
// C++17 constexpr lambdas
#if defined(__cpp_constexpr) && __cpp_constexpr >= 201603L
#define JKJ_HAS_CONSTEXPR17 1
#elif __cplusplus >= 201703L
#define JKJ_HAS_CONSTEXPR17 1
#elif defined(_MSC_VER) && _MSC_VER >= 1911 && _MSVC_LANG >= 201703L
#define JKJ_HAS_CONSTEXPR17 1
#else
#define JKJ_HAS_CONSTEXPR17 0
#endif
// C++17 inline variables
#if defined(__cpp_inline_variables) && __cpp_inline_variables >= 201606L
#define JKJ_HAS_INLINE_VARIABLE 1
#elif __cplusplus >= 201703L
#define JKJ_HAS_INLINE_VARIABLE 1
#elif defined(_MSC_VER) && _MSC_VER >= 1912 && _MSVC_LANG >= 201703L
#define JKJ_HAS_INLINE_VARIABLE 1
#else
#define JKJ_HAS_INLINE_VARIABLE 0
#endif
#if JKJ_HAS_INLINE_VARIABLE
#define JKJ_INLINE_VARIABLE inline constexpr
#else
#define JKJ_INLINE_VARIABLE static constexpr
#endif
// C++17 if constexpr
#if defined(__cpp_if_constexpr) && __cpp_if_constexpr >= 201606L
#define JKJ_HAS_IF_CONSTEXPR 1
#elif __cplusplus >= 201703L
#define JKJ_HAS_IF_CONSTEXPR 1
#elif defined(_MSC_VER) && _MSC_VER >= 1911 && _MSVC_LANG >= 201703L
#define JKJ_HAS_IF_CONSTEXPR 1
#else
#define JKJ_HAS_IF_CONSTEXPR 0
#endif
#if JKJ_HAS_IF_CONSTEXPR
#define JKJ_IF_CONSTEXPR if constexpr
#else
#define JKJ_IF_CONSTEXPR if
#endif
// C++20 std::bit_cast
#if JKJ_STD_REPLACEMENT_NAMESPACE_DEFINED
#if JKJ_STD_REPLACEMENT_HAS_BIT_CAST
#define JKJ_HAS_BIT_CAST 1
#else
#define JKJ_HAS_BIT_CAST 0
#endif
#elif defined(__cpp_lib_bit_cast) && __cpp_lib_bit_cast >= 201806L
#include <bit>
#define JKJ_HAS_BIT_CAST 1
#else
#define JKJ_HAS_BIT_CAST 0
#endif
// C++23 if consteval or C++20 std::is_constant_evaluated
#if defined(__cpp_if_consteval) && __cpp_is_consteval >= 202106L
#define JKJ_IF_CONSTEVAL if consteval
#define JKJ_IF_NOT_CONSTEVAL if !consteval
#define JKJ_CAN_BRANCH_ON_CONSTEVAL 1
#define JKJ_USE_IS_CONSTANT_EVALUATED 0
#elif JKJ_STD_REPLACEMENT_NAMESPACE_DEFINED
#if JKJ_STD_REPLACEMENT_HAS_IS_CONSTANT_EVALUATED
#define JKJ_IF_CONSTEVAL if (stdr::is_constant_evaluated())
#define JKJ_IF_NOT_CONSTEVAL if (!stdr::is_constant_evaluated())
#define JKJ_CAN_BRANCH_ON_CONSTEVAL 1
#define JKJ_USE_IS_CONSTANT_EVALUATED 1
#elif JKJ_HAS_IF_CONSTEXPR
#define JKJ_IF_CONSTEVAL if constexpr (false)
#define JKJ_IF_NOT_CONSTEVAL if constexpr (true)
#define JKJ_CAN_BRANCH_ON_CONSTEVAL 0
#define JKJ_USE_IS_CONSTANT_EVALUATED 0
#else
#define JKJ_IF_CONSTEVAL if (false)
#define JKJ_IF_NOT_CONSTEVAL if (true)
#define JKJ_CAN_BRANCH_ON_CONSTEVAL 0
#define JKJ_USE_IS_CONSTANT_EVALUATED 0
#endif
#else
#if defined(__cpp_lib_is_constant_evaluated) && __cpp_lib_is_constant_evaluated >= 201811L
#define JKJ_IF_CONSTEVAL if (stdr::is_constant_evaluated())
#define JKJ_IF_NOT_CONSTEVAL if (!stdr::is_constant_evaluated())
#define JKJ_CAN_BRANCH_ON_CONSTEVAL 1
#define JKJ_USE_IS_CONSTANT_EVALUATED 1
#elif JKJ_HAS_IF_CONSTEXPR
#define JKJ_IF_CONSTEVAL if constexpr (false)
#define JKJ_IF_NOT_CONSTEVAL if constexpr (true)
#define JKJ_CAN_BRANCH_ON_CONSTEVAL 0
#define JKJ_USE_IS_CONSTANT_EVALUATED 0
#else
#define JKJ_IF_CONSTEVAL if (false)
#define JKJ_IF_NOT_CONSTEVAL if (true)
#define JKJ_CAN_BRANCH_ON_CONSTEVAL 0
#define JKJ_USE_IS_CONSTANT_EVALUATED 0
#endif
#endif
#if JKJ_CAN_BRANCH_ON_CONSTEVAL && JKJ_HAS_BIT_CAST
#define JKJ_CONSTEXPR20 constexpr
#else
#define JKJ_CONSTEXPR20
#endif
// Suppress additional buffer overrun check.
// I have no idea why MSVC thinks some functions here are vulnerable to the buffer overrun
// attacks. No, they aren't.
#if defined(__GNUC__) || defined(__clang__)
#define JKJ_SAFEBUFFERS
#define JKJ_FORCEINLINE inline __attribute__((always_inline))
#elif defined(_MSC_VER)
#define JKJ_SAFEBUFFERS __declspec(safebuffers)
#define JKJ_FORCEINLINE __forceinline
#else
#define JKJ_SAFEBUFFERS
#define JKJ_FORCEINLINE inline
#endif
#if defined(__has_builtin)
#define JKJ_HAS_BUILTIN(x) __has_builtin(x)
#else
#define JKJ_HAS_BUILTIN(x) false
#endif
#if defined(_MSC_VER)
#include <intrin.h>
#elif defined(__INTEL_COMPILER)
#include <immintrin.h>
#endif
namespace YAML {
namespace jkj {
namespace dragonbox {
////////////////////////////////////////////////////////////////////////////////////////
// The Compatibility layer for toolchains without standard C++ headers.
////////////////////////////////////////////////////////////////////////////////////////
namespace detail {
namespace stdr {
// <bit>
#if JKJ_HAS_BIT_CAST
using JKJ_STD_REPLACEMENT_NAMESPACE::bit_cast;
#endif
// <cassert>
// We need assert() macro, but it is not namespaced anyway, so nothing to do here.
// <cstdint>
using JKJ_STD_REPLACEMENT_NAMESPACE::int_least8_t;
using JKJ_STD_REPLACEMENT_NAMESPACE::int_least16_t;
using JKJ_STD_REPLACEMENT_NAMESPACE::int_least32_t;
using JKJ_STD_REPLACEMENT_NAMESPACE::int_fast8_t;
using JKJ_STD_REPLACEMENT_NAMESPACE::int_fast16_t;
using JKJ_STD_REPLACEMENT_NAMESPACE::int_fast32_t;
using JKJ_STD_REPLACEMENT_NAMESPACE::uint_least8_t;
using JKJ_STD_REPLACEMENT_NAMESPACE::uint_least16_t;
using JKJ_STD_REPLACEMENT_NAMESPACE::uint_least32_t;
using JKJ_STD_REPLACEMENT_NAMESPACE::uint_least64_t;
using JKJ_STD_REPLACEMENT_NAMESPACE::uint_fast8_t;
using JKJ_STD_REPLACEMENT_NAMESPACE::uint_fast16_t;
using JKJ_STD_REPLACEMENT_NAMESPACE::uint_fast32_t;
// We need INT32_C, UINT32_C and UINT64_C macros too, but again there is nothing to do
// here.
// <cstring>
using JKJ_STD_REPLACEMENT_NAMESPACE::size_t;
using JKJ_STD_REPLACEMENT_NAMESPACE::memcpy;
// <limits>
template <class T>
using numeric_limits = JKJ_STD_REPLACEMENT_NAMESPACE::numeric_limits<T>;
// <type_traits>
template <bool cond, class T = void>
using enable_if = JKJ_STD_REPLACEMENT_NAMESPACE::enable_if<cond, T>;
template <class T>
using add_rvalue_reference = JKJ_STD_REPLACEMENT_NAMESPACE::add_rvalue_reference<T>;
template <bool cond, class T_true, class T_false>
using conditional = JKJ_STD_REPLACEMENT_NAMESPACE::conditional<cond, T_true, T_false>;
#if JKJ_USE_IS_CONSTANT_EVALUATED
using JKJ_STD_REPLACEMENT_NAMESPACE::is_constant_evaluated;
#endif
template <class T1, class T2>
using is_same = JKJ_STD_REPLACEMENT_NAMESPACE::is_same<T1, T2>;
#if !JKJ_HAS_BIT_CAST
template <class T>
using is_trivially_copyable = JKJ_STD_REPLACEMENT_NAMESPACE::is_trivially_copyable<T>;
#endif
template <class T>
using is_integral = JKJ_STD_REPLACEMENT_NAMESPACE::is_integral<T>;
template <class T>
using is_signed = JKJ_STD_REPLACEMENT_NAMESPACE::is_signed<T>;
template <class T>
using is_unsigned = JKJ_STD_REPLACEMENT_NAMESPACE::is_unsigned<T>;
}
}
////////////////////////////////////////////////////////////////////////////////////////
// Some general utilities for C++11-compatibility.
////////////////////////////////////////////////////////////////////////////////////////
namespace detail {
#if !JKJ_HAS_CONSTEXPR17
template <stdr::size_t... indices>
struct index_sequence {};
template <stdr::size_t current, stdr::size_t total, class Dummy, stdr::size_t... indices>
struct make_index_sequence_impl {
using type = typename make_index_sequence_impl<current + 1, total, Dummy, indices...,
current>::type;
};
template <stdr::size_t total, class Dummy, stdr::size_t... indices>
struct make_index_sequence_impl<total, total, Dummy, indices...> {
using type = index_sequence<indices...>;
};
template <stdr::size_t N>
using make_index_sequence = typename make_index_sequence_impl<0, N, void>::type;
#endif
// Available since C++11, but including <utility> just for this is an overkill.
template <class T>
typename stdr::add_rvalue_reference<T>::type declval() noexcept;
// Similarly, including <array> is an overkill.
template <class T, stdr::size_t N>
struct array {
T data_[N];
constexpr T operator[](stdr::size_t idx) const noexcept { return data_[idx]; }
JKJ_CONSTEXPR14 T& operator[](stdr::size_t idx) noexcept { return data_[idx]; }
};
}
////////////////////////////////////////////////////////////////////////////////////////
// Some basic features for encoding/decoding IEEE-754 formats.
////////////////////////////////////////////////////////////////////////////////////////
namespace detail {
template <class T>
struct physical_bits {
static constexpr stdr::size_t value =
sizeof(T) * stdr::numeric_limits<unsigned char>::digits;
};
template <class T>
struct value_bits {
static constexpr stdr::size_t value = stdr::numeric_limits<
typename stdr::enable_if<stdr::is_integral<T>::value, T>::type>::digits;
};
template <typename To, typename From>
JKJ_CONSTEXPR20 To bit_cast(const From& from) {
#if JKJ_HAS_BIT_CAST
return stdr::bit_cast<To>(from);
#else
static_assert(sizeof(From) == sizeof(To), "");
static_assert(stdr::is_trivially_copyable<To>::value, "");
static_assert(stdr::is_trivially_copyable<From>::value, "");
To to;
stdr::memcpy(&to, &from, sizeof(To));
return to;
#endif
}
}
// These classes expose encoding specs of IEEE-754-like floating-point formats.
// Currently available formats are IEEE-754 binary32 & IEEE-754 binary64.
struct ieee754_binary32 {
static constexpr int total_bits = 32;
static constexpr int significand_bits = 23;
static constexpr int exponent_bits = 8;
static constexpr int min_exponent = -126;
static constexpr int max_exponent = 127;
static constexpr int exponent_bias = -127;
static constexpr int decimal_significand_digits = 9;
static constexpr int decimal_exponent_digits = 2;
};
struct ieee754_binary64 {
static constexpr int total_bits = 64;
static constexpr int significand_bits = 52;
static constexpr int exponent_bits = 11;
static constexpr int min_exponent = -1022;
static constexpr int max_exponent = 1023;
static constexpr int exponent_bias = -1023;
static constexpr int decimal_significand_digits = 17;
static constexpr int decimal_exponent_digits = 3;
};
// A floating-point format traits class defines ways to interpret a bit pattern of given size as
// an encoding of floating-point number. This is an implementation of such a traits class,
// supporting ways to interpret IEEE-754 binary floating-point numbers.
template <class Format, class CarrierUInt, class ExponentInt = int>
struct ieee754_binary_traits {
// CarrierUInt needs to have enough size to hold the entire contents of floating-point
// numbers. The actual bits are assumed to be aligned to the LSB, and every other bits are
// assumed to be zeroed.
static_assert(detail::value_bits<CarrierUInt>::value >= Format::total_bits,
"jkj::dragonbox: insufficient number of bits");
static_assert(detail::stdr::is_unsigned<CarrierUInt>::value, "");
// ExponentUInt needs to be large enough to hold (unsigned) exponent bits as well as the
// (signed) actual exponent.
// TODO: static overflow guard against intermediate computations.
static_assert(detail::value_bits<ExponentInt>::value >= Format::exponent_bits + 1,
"jkj::dragonbox: insufficient number of bits");
static_assert(detail::stdr::is_signed<ExponentInt>::value, "");
using format = Format;
using carrier_uint = CarrierUInt;
static constexpr int carrier_bits = int(detail::value_bits<carrier_uint>::value);
using exponent_int = ExponentInt;
// Extract exponent bits from a bit pattern.
// The result must be aligned to the LSB so that there is no additional zero paddings
// on the right. This function does not do bias adjustment.
static constexpr exponent_int extract_exponent_bits(carrier_uint u) noexcept {
return exponent_int((u >> format::significand_bits) &
((exponent_int(1) << format::exponent_bits) - 1));
}
// Extract significand bits from a bit pattern.
// The result must be aligned to the LSB so that there is no additional zero paddings
// on the right. The result does not contain the implicit bit.
static constexpr carrier_uint extract_significand_bits(carrier_uint u) noexcept {
return carrier_uint(u & ((carrier_uint(1) << format::significand_bits) - 1u));
}
// Remove the exponent bits and extract significand bits together with the sign bit.
static constexpr carrier_uint remove_exponent_bits(carrier_uint u) noexcept {
return carrier_uint(u & ~(((carrier_uint(1) << format::exponent_bits) - 1u)
<< format::significand_bits));
}
// Shift the obtained signed significand bits to the left by 1 to remove the sign bit.
static constexpr carrier_uint remove_sign_bit_and_shift(carrier_uint u) noexcept {
return carrier_uint((carrier_uint(u) << 1) &
((((carrier_uint(1) << (Format::total_bits - 1)) - 1u) << 1) | 1u));
}
// Obtain the actual value of the binary exponent from the extracted exponent bits.
static constexpr exponent_int binary_exponent(exponent_int exponent_bits) noexcept {
return exponent_int(exponent_bits == 0 ? format::min_exponent
: exponent_bits + format::exponent_bias);
}
// Obtain the actual value of the binary significand from the extracted significand bits
// and exponent bits.
static constexpr carrier_uint binary_significand(carrier_uint significand_bits,
exponent_int exponent_bits) noexcept {
return carrier_uint(
exponent_bits == 0
? significand_bits
: (significand_bits | (carrier_uint(1) << format::significand_bits)));
}
/* Various boolean observer functions */
static constexpr bool is_nonzero(carrier_uint u) noexcept {
return (u & ((carrier_uint(1) << (format::significand_bits + format::exponent_bits)) -
1u)) != 0;
}
static constexpr bool is_positive(carrier_uint u) noexcept {
return u < (carrier_uint(1) << (format::significand_bits + format::exponent_bits));
}
static constexpr bool is_negative(carrier_uint u) noexcept { return !is_positive(u); }
static constexpr bool is_finite(exponent_int exponent_bits) noexcept {
return exponent_bits != ((exponent_int(1) << format::exponent_bits) - 1);
}
static constexpr bool has_all_zero_significand_bits(carrier_uint u) noexcept {
return ((u << 1) &
((((carrier_uint(1) << (Format::total_bits - 1)) - 1u) << 1) | 1u)) == 0;
}
static constexpr bool has_even_significand_bits(carrier_uint u) noexcept {
return u % 2 == 0;
}
};
// Convert between bit patterns stored in carrier_uint and instances of an actual
// floating-point type. Depending on format and carrier_uint, this operation might not
// be possible for some specific bit patterns. However, the contract is that u always
// denotes a valid bit pattern, so the functions here are assumed to be noexcept.
// Users might specialize this class to change the behavior for certain types.
// The default provided by the library is to treat the given floating-point type Float as either
// IEEE-754 binary32 or IEEE-754 binary64, depending on the bitwise size of Float.
template <class Float>
struct default_float_bit_carrier_conversion_traits {
// Guards against types that have different internal representations than IEEE-754
// binary32/64. I don't know if there is a truly reliable way of detecting IEEE-754 binary
// formats. I just did my best here. Note that in some cases
// numeric_limits<Float>::is_iec559 may report false even if the internal representation is
// IEEE-754 compatible. In such a case, the user can specialize this traits template and
// remove this static sanity check in order to make Dragonbox work for Float.
static_assert(detail::stdr::numeric_limits<Float>::is_iec559 &&
detail::stdr::numeric_limits<Float>::radix == 2 &&
(detail::physical_bits<Float>::value == 32 ||
detail::physical_bits<Float>::value == 64),
"jkj::dragonbox: Float may not be of IEEE-754 binary32/binary64");
// Specifies the unsigned integer type to hold bitwise value of Float.
using carrier_uint =
typename detail::stdr::conditional<detail::physical_bits<Float>::value == 32,
detail::stdr::uint_least32_t,
detail::stdr::uint_least64_t>::type;
// Specifies the floating-point format.
using format = typename detail::stdr::conditional<detail::physical_bits<Float>::value == 32,
ieee754_binary32, ieee754_binary64>::type;
// Converts the floating-point type into the bit-carrier unsigned integer type.
static JKJ_CONSTEXPR20 carrier_uint float_to_carrier(Float x) noexcept {
return detail::bit_cast<carrier_uint>(x);
}
// Converts the bit-carrier unsigned integer type into the floating-point type.
static JKJ_CONSTEXPR20 Float carrier_to_float(carrier_uint x) noexcept {
return detail::bit_cast<Float>(x);
}
};
// Convenient wrappers for floating-point traits classes.
// In order to reduce the argument passing overhead, these classes should be as simple as
// possible (e.g., no inheritance, no private non-static data member, etc.; this is an
// unfortunate fact about common ABI convention).
template <class FormatTraits>
struct signed_significand_bits {
using format_traits = FormatTraits;
using carrier_uint = typename format_traits::carrier_uint;
carrier_uint u;
signed_significand_bits() = default;
constexpr explicit signed_significand_bits(carrier_uint bit_pattern) noexcept
: u{bit_pattern} {}
// Shift the obtained signed significand bits to the left by 1 to remove the sign bit.
constexpr carrier_uint remove_sign_bit_and_shift() const noexcept {
return format_traits::remove_sign_bit_and_shift(u);
}
constexpr bool is_positive() const noexcept { return format_traits::is_positive(u); }
constexpr bool is_negative() const noexcept { return format_traits::is_negative(u); }
constexpr bool has_all_zero_significand_bits() const noexcept {
return format_traits::has_all_zero_significand_bits(u);
}
constexpr bool has_even_significand_bits() const noexcept {
return format_traits::has_even_significand_bits(u);
}
};
template <class FormatTraits>
struct float_bits {
using format_traits = FormatTraits;
using carrier_uint = typename format_traits::carrier_uint;
using exponent_int = typename format_traits::exponent_int;
carrier_uint u;
float_bits() = default;
constexpr explicit float_bits(carrier_uint bit_pattern) noexcept : u{bit_pattern} {}
// Extract exponent bits from a bit pattern.
// The result must be aligned to the LSB so that there is no additional zero paddings
// on the right. This function does not do bias adjustment.
constexpr exponent_int extract_exponent_bits() const noexcept {
return format_traits::extract_exponent_bits(u);
}
// Extract significand bits from a bit pattern.
// The result must be aligned to the LSB so that there is no additional zero paddings
// on the right. The result does not contain the implicit bit.
constexpr carrier_uint extract_significand_bits() const noexcept {
return format_traits::extract_significand_bits(u);
}
// Remove the exponent bits and extract significand bits together with the sign bit.
constexpr signed_significand_bits<format_traits> remove_exponent_bits() const noexcept {
return signed_significand_bits<format_traits>(format_traits::remove_exponent_bits(u));
}
// Obtain the actual value of the binary exponent from the extracted exponent bits.
static constexpr exponent_int binary_exponent(exponent_int exponent_bits) noexcept {
return format_traits::binary_exponent(exponent_bits);
}
constexpr exponent_int binary_exponent() const noexcept {
return binary_exponent(extract_exponent_bits());
}
// Obtain the actual value of the binary exponent from the extracted significand bits
// and exponent bits.
static constexpr carrier_uint binary_significand(carrier_uint significand_bits,
exponent_int exponent_bits) noexcept {
return format_traits::binary_significand(significand_bits, exponent_bits);
}
constexpr carrier_uint binary_significand() const noexcept {
return binary_significand(extract_significand_bits(), extract_exponent_bits());
}
constexpr bool is_nonzero() const noexcept { return format_traits::is_nonzero(u); }
constexpr bool is_positive() const noexcept { return format_traits::is_positive(u); }
constexpr bool is_negative() const noexcept { return format_traits::is_negative(u); }
constexpr bool is_finite(exponent_int exponent_bits) const noexcept {
return format_traits::is_finite(exponent_bits);
}
constexpr bool is_finite() const noexcept {
return format_traits::is_finite(extract_exponent_bits());
}
constexpr bool has_even_significand_bits() const noexcept {
return format_traits::has_even_significand_bits(u);
}
};
template <class Float,
class ConversionTraits = default_float_bit_carrier_conversion_traits<Float>,
class FormatTraits = ieee754_binary_traits<typename ConversionTraits::format,
typename ConversionTraits::carrier_uint>>
JKJ_CONSTEXPR20 float_bits<FormatTraits> make_float_bits(Float x) noexcept {
return float_bits<FormatTraits>(ConversionTraits::float_to_carrier(x));
}
namespace detail {
////////////////////////////////////////////////////////////////////////////////////////
// Bit operation intrinsics.
////////////////////////////////////////////////////////////////////////////////////////
namespace bits {
// Most compilers should be able to optimize this into the ROR instruction.
// n is assumed to be at most of bit_width bits.
template <stdr::size_t bit_width, class UInt>
JKJ_CONSTEXPR14 UInt rotr(UInt n, unsigned int r) noexcept {
static_assert(bit_width > 0, "jkj::dragonbox: rotation bit-width must be positive");
static_assert(bit_width <= value_bits<UInt>::value,
"jkj::dragonbox: rotation bit-width is too large");
r &= (bit_width - 1);
return (n >> r) | (n << ((bit_width - r) & (bit_width - 1)));
}
}
////////////////////////////////////////////////////////////////////////////////////////
// Utilities for wide unsigned integer arithmetic.
////////////////////////////////////////////////////////////////////////////////////////
namespace wuint {
// Compilers might support built-in 128-bit integer types. However, it seems that
// emulating them with a pair of 64-bit integers actually produces a better code,
// so we avoid using those built-ins. That said, they are still useful for
// implementing 64-bit x 64-bit -> 128-bit multiplication.
// clang-format off
#if defined(__SIZEOF_INT128__)
// To silence "error: ISO C++ does not support '__int128' for 'type name'
// [-Wpedantic]"
#if defined(__GNUC__)
__extension__
#endif
using builtin_uint128_t = unsigned __int128;
#endif
// clang-format on
struct uint128 {
uint128() = default;
stdr::uint_least64_t high_;
stdr::uint_least64_t low_;
constexpr uint128(stdr::uint_least64_t high, stdr::uint_least64_t low) noexcept
: high_{high}, low_{low} {}
constexpr stdr::uint_least64_t high() const noexcept { return high_; }
constexpr stdr::uint_least64_t low() const noexcept { return low_; }
JKJ_CONSTEXPR20 uint128& operator+=(stdr::uint_least64_t n) & noexcept {
auto const generic_impl = [&] {
auto const sum = (low_ + n) & UINT64_C(0xffffffffffffffff);
high_ += (sum < low_ ? 1 : 0);
low_ = sum;
};
// To suppress warning.
static_cast<void>(generic_impl);
JKJ_IF_CONSTEXPR(value_bits<stdr::uint_least64_t>::value > 64) {
generic_impl();
return *this;
}
JKJ_IF_CONSTEVAL {
generic_impl();
return *this;
}
// See https://github.com/fmtlib/fmt/pull/2985.
#if JKJ_HAS_BUILTIN(__builtin_addcll) && !defined(__ibmxl__)
JKJ_IF_CONSTEXPR(
stdr::is_same<stdr::uint_least64_t, unsigned long long>::value) {
unsigned long long carry{};
low_ = stdr::uint_least64_t(__builtin_addcll(low_, n, 0, &carry));
high_ = stdr::uint_least64_t(__builtin_addcll(high_, 0, carry, &carry));
return *this;
}
#endif
#if JKJ_HAS_BUILTIN(__builtin_addcl) && !defined(__ibmxl__)
JKJ_IF_CONSTEXPR(stdr::is_same<stdr::uint_least64_t, unsigned long>::value) {
unsigned long carry{};
low_ = stdr::uint_least64_t(
__builtin_addcl(static_cast<unsigned long>(low_),
static_cast<unsigned long>(n), 0, &carry));
high_ = stdr::uint_least64_t(
__builtin_addcl(static_cast<unsigned long>(high_), 0, carry, &carry));
return *this;
}
#endif
#if JKJ_HAS_BUILTIN(__builtin_addc) && !defined(__ibmxl__)
JKJ_IF_CONSTEXPR(stdr::is_same<stdr::uint_least64_t, unsigned int>::value) {
unsigned int carry{};
low_ = stdr::uint_least64_t(__builtin_addc(static_cast<unsigned int>(low_),
static_cast<unsigned int>(n), 0,
&carry));
high_ = stdr::uint_least64_t(
__builtin_addc(static_cast<unsigned int>(high_), 0, carry, &carry));
return *this;
}
#endif
#if JKJ_HAS_BUILTIN(__builtin_ia32_addcarry_u64)
// __builtin_ia32_addcarry_u64 is not documented, but it seems it takes unsigned
// long long arguments.
unsigned long long result{};
auto const carry = __builtin_ia32_addcarry_u64(0, low_, n, &result);
low_ = stdr::uint_least64_t(result);
__builtin_ia32_addcarry_u64(carry, high_, 0, &result);
high_ = stdr::uint_least64_t(result);
#elif defined(_MSC_VER) && defined(_M_X64)
// On MSVC, uint_least64_t and __int64 must be unsigned long long; see
// https://learn.microsoft.com/en-us/cpp/c-runtime-library/standard-types
// and https://learn.microsoft.com/en-us/cpp/cpp/int8-int16-int32-int64.
static_assert(stdr::is_same<unsigned long long, stdr::uint_least64_t>::value,
"");
auto const carry = _addcarry_u64(0, low_, n, &low_);
_addcarry_u64(carry, high_, 0, &high_);
#elif defined(__INTEL_COMPILER) && (defined(_M_X64) || defined(__x86_64))
// Cannot find any documentation on how things are defined, but hopefully this
// is always true...
static_assert(stdr::is_same<unsigned __int64, stdr::uint_least64_t>::value, "");
auto const carry = _addcarry_u64(0, low_, n, &low_);
_addcarry_u64(carry, high_, 0, &high_);
#else
generic_impl();
#endif
return *this;
}
};
inline JKJ_CONSTEXPR20 stdr::uint_least64_t umul64(stdr::uint_least32_t x,
stdr::uint_least32_t y) noexcept {
#if defined(_MSC_VER) && defined(_M_IX86)
JKJ_IF_NOT_CONSTEVAL { return __emulu(x, y); }
#endif
return x * stdr::uint_least64_t(y);
}
// Get 128-bit result of multiplication of two 64-bit unsigned integers.
JKJ_SAFEBUFFERS inline JKJ_CONSTEXPR20 uint128
umul128(stdr::uint_least64_t x, stdr::uint_least64_t y) noexcept {
auto const generic_impl = [=]() -> uint128 {
auto const a = stdr::uint_least32_t(x >> 32);
auto const b = stdr::uint_least32_t(x);
auto const c = stdr::uint_least32_t(y >> 32);
auto const d = stdr::uint_least32_t(y);
auto const ac = umul64(a, c);
auto const bc = umul64(b, c);
auto const ad = umul64(a, d);
auto const bd = umul64(b, d);
auto const intermediate =
(bd >> 32) + stdr::uint_least32_t(ad) + stdr::uint_least32_t(bc);
return {ac + (intermediate >> 32) + (ad >> 32) + (bc >> 32),
(intermediate << 32) + stdr::uint_least32_t(bd)};
};
// To silence warning.
static_cast<void>(generic_impl);
#if defined(__SIZEOF_INT128__)
auto const result = builtin_uint128_t(x) * builtin_uint128_t(y);
return {stdr::uint_least64_t(result >> 64), stdr::uint_least64_t(result)};
#elif defined(_MSC_VER) && defined(_M_X64)
JKJ_IF_CONSTEVAL {
// This redundant variable is to workaround MSVC's codegen bug caused by the
// interaction of NRVO and intrinsics.
auto const result = generic_impl();
return result;
}
uint128 result;
#if defined(__AVX2__)
result.low_ = _mulx_u64(x, y, &result.high_);
#else
result.low_ = _umul128(x, y, &result.high_);
#endif
return result;
#else
return generic_impl();
#endif
}
// Get high half of the 128-bit result of multiplication of two 64-bit unsigned
// integers.
JKJ_SAFEBUFFERS inline JKJ_CONSTEXPR20 stdr::uint_least64_t
umul128_upper64(stdr::uint_least64_t x, stdr::uint_least64_t y) noexcept {
auto const generic_impl = [=]() -> stdr::uint_least64_t {
auto const a = stdr::uint_least32_t(x >> 32);
auto const b = stdr::uint_least32_t(x);
auto const c = stdr::uint_least32_t(y >> 32);
auto const d = stdr::uint_least32_t(y);
auto const ac = umul64(a, c);
auto const bc = umul64(b, c);
auto const ad = umul64(a, d);
auto const bd = umul64(b, d);
auto const intermediate =
(bd >> 32) + stdr::uint_least32_t(ad) + stdr::uint_least32_t(bc);
return ac + (intermediate >> 32) + (ad >> 32) + (bc >> 32);
};
// To silence warning.
static_cast<void>(generic_impl);
#if defined(__SIZEOF_INT128__)
auto const result = builtin_uint128_t(x) * builtin_uint128_t(y);
return stdr::uint_least64_t(result >> 64);
#elif defined(_MSC_VER) && defined(_M_X64)
JKJ_IF_CONSTEVAL {
// This redundant variable is to workaround MSVC's codegen bug caused by the
// interaction of NRVO and intrinsics.
auto const result = generic_impl();
return result;
}
stdr::uint_least64_t result;
#if defined(__AVX2__)
_mulx_u64(x, y, &result);
#else
result = __umulh(x, y);
#endif
return result;
#else
return generic_impl();
#endif
}
// Get upper 128-bits of multiplication of a 64-bit unsigned integer and a 128-bit
// unsigned integer.
JKJ_SAFEBUFFERS inline JKJ_CONSTEXPR20 uint128 umul192_upper128(stdr::uint_least64_t x,
uint128 y) noexcept {
auto r = umul128(x, y.high());
r += umul128_upper64(x, y.low());
return r;
}
// Get upper 64-bits of multiplication of a 32-bit unsigned integer and a 64-bit
// unsigned integer.
inline JKJ_CONSTEXPR20 stdr::uint_least64_t
umul96_upper64(stdr::uint_least32_t x, stdr::uint_least64_t y) noexcept {
#if defined(__SIZEOF_INT128__) || (defined(_MSC_VER) && defined(_M_X64))
return umul128_upper64(stdr::uint_least64_t(x) << 32, y);
#else
auto const yh = stdr::uint_least32_t(y >> 32);
auto const yl = stdr::uint_least32_t(y);
auto const xyh = umul64(x, yh);
auto const xyl = umul64(x, yl);
return xyh + (xyl >> 32);
#endif
}
// Get lower 128-bits of multiplication of a 64-bit unsigned integer and a 128-bit
// unsigned integer.
JKJ_SAFEBUFFERS inline JKJ_CONSTEXPR20 uint128 umul192_lower128(stdr::uint_least64_t x,
uint128 y) noexcept {
auto const high = x * y.high();
auto const high_low = umul128(x, y.low());
return {(high + high_low.high()) & UINT64_C(0xffffffffffffffff), high_low.low()};
}
// Get lower 64-bits of multiplication of a 32-bit unsigned integer and a 64-bit
// unsigned integer.
constexpr stdr::uint_least64_t umul96_lower64(stdr::uint_least32_t x,
stdr::uint_least64_t y) noexcept {
return (x * y) & UINT64_C(0xffffffffffffffff);
}
}
////////////////////////////////////////////////////////////////////////////////////////
// Some simple utilities for constexpr computation.
////////////////////////////////////////////////////////////////////////////////////////
template <int k, class Int>
constexpr Int compute_power(Int a) noexcept {
static_assert(k >= 0, "");
#if JKJ_HAS_CONSTEXPR14
Int p = 1;
for (int i = 0; i < k; ++i) {
p *= a;
}
return p;
#else
return k == 0 ? 1
: k % 2 == 0 ? compute_power<k / 2, Int>(a * a)
: a * compute_power<k / 2, Int>(a * a);
#endif
}
template <int a, class UInt>
constexpr int count_factors(UInt n) noexcept {
static_assert(a > 1, "");
#if JKJ_HAS_CONSTEXPR14
int c = 0;
while (n % a == 0) {
n /= a;
++c;
}
return c;
#else
return n % a == 0 ? count_factors<a, UInt>(n / a) + 1 : 0;
#endif
}
////////////////////////////////////////////////////////////////////////////////////////
// Utilities for fast/constexpr log computation.
////////////////////////////////////////////////////////////////////////////////////////
namespace log {
static_assert((stdr::int_fast32_t(-1) >> 1) == stdr::int_fast32_t(-1) &&
(stdr::int_fast16_t(-1) >> 1) == stdr::int_fast16_t(-1),
"jkj::dragonbox: right-shift for signed integers must be arithmetic");
// For constexpr computation.
// Returns -1 when n = 0.
template <class UInt>
constexpr int floor_log2(UInt n) noexcept {
#if JKJ_HAS_CONSTEXPR14
int count = -1;
while (n != 0) {
++count;
n >>= 1;
}
return count;
#else
return n == 0 ? -1 : floor_log2<UInt>(n / 2) + 1;
#endif
}
template <template <stdr::size_t> class Info, stdr::int_least32_t min_exponent,
stdr::int_least32_t max_exponent, stdr::size_t current_tier,
stdr::int_least32_t supported_min_exponent = Info<current_tier>::min_exponent,
stdr::int_least32_t supported_max_exponent = Info<current_tier>::max_exponent>
constexpr bool is_in_range(int) noexcept {
return min_exponent >= supported_min_exponent &&
max_exponent <= supported_max_exponent;
}
template <template <stdr::size_t> class Info, stdr::int_least32_t min_exponent,
stdr::int_least32_t max_exponent, stdr::size_t current_tier>
constexpr bool is_in_range(...) noexcept {
// Supposed to be always false, but formally dependent on the template parameters.
static_assert(min_exponent > max_exponent,
"jkj::dragonbox: exponent range is too wide");
return false;
}
template <template <stdr::size_t> class Info, stdr::int_least32_t min_exponent,
stdr::int_least32_t max_exponent, stdr::size_t current_tier = 0,
bool = is_in_range<Info, min_exponent, max_exponent, current_tier>(0)>
struct compute_impl;
template <template <stdr::size_t> class Info, stdr::int_least32_t min_exponent,
stdr::int_least32_t max_exponent, stdr::size_t current_tier>
struct compute_impl<Info, min_exponent, max_exponent, current_tier, true> {
using info = Info<current_tier>;
using default_return_type = typename info::default_return_type;
template <class ReturnType, class Int>
static constexpr ReturnType compute(Int e) noexcept {
#if JKJ_HAS_CONSTEXPR14
assert(min_exponent <= e && e <= max_exponent);
#endif
// The sign is irrelevant for the mathematical validity of the formula, but
// assuming positivity makes the overflow analysis simpler.
static_assert(info::multiply >= 0 && info::subtract >= 0, "");
return static_cast<ReturnType>((e * info::multiply - info::subtract) >>
info::shift);
}
};
template <template <stdr::size_t> class Info, stdr::int_least32_t min_exponent,
stdr::int_least32_t max_exponent, stdr::size_t current_tier>
struct compute_impl<Info, min_exponent, max_exponent, current_tier, false> {
using next_tier = compute_impl<Info, min_exponent, max_exponent, current_tier + 1>;
using default_return_type = typename next_tier::default_return_type;
template <class ReturnType, class Int>
static constexpr ReturnType compute(Int e) noexcept {
return next_tier::template compute<ReturnType>(e);
}
};
template <stdr::size_t tier>
struct floor_log10_pow2_info;
template <>
struct floor_log10_pow2_info<0> {
using default_return_type = stdr::int_fast8_t;
static constexpr stdr::int_fast16_t multiply = 77;
static constexpr stdr::int_fast16_t subtract = 0;
static constexpr stdr::size_t shift = 8;
static constexpr stdr::int_least32_t min_exponent = -102;
static constexpr stdr::int_least32_t max_exponent = 102;
};
template <>
struct floor_log10_pow2_info<1> {
using default_return_type = stdr::int_fast8_t;
// 24-bits are enough in fact.
static constexpr stdr::int_fast32_t multiply = 1233;
static constexpr stdr::int_fast32_t subtract = 0;
static constexpr stdr::size_t shift = 12;
// Formula itself holds on [-680,680]; [-425,425] is to ensure that the output is
// within [-127,127].
static constexpr stdr::int_least32_t min_exponent = -425;
static constexpr stdr::int_least32_t max_exponent = 425;
};
template <>
struct floor_log10_pow2_info<2> {
using default_return_type = stdr::int_fast16_t;
static constexpr stdr::int_fast32_t multiply = INT32_C(315653);