Botan 3.14.1
Crypto and TLS for C&
big_code.cpp
Go to the documentation of this file.
1/*
2* BigInt Encoding/Decoding
3* (C) 1999-2010,2012,2019,2021 Jack Lloyd
4*
5* Botan is released under the Simplified BSD License (see license.txt)
6*/
7
8#include <botan/bigint.h>
9
10#include <botan/assert.h>
11#include <botan/exceptn.h>
12#include <botan/hex.h>
13#include <botan/mem_ops.h>
14#include <botan/internal/buffer_stuffer.h>
15#include <botan/internal/divide.h>
16#include <botan/internal/mp_core.h>
17
18namespace Botan {
19
20namespace {
21
22consteval word decimal_conversion_radix() {
23 if constexpr(sizeof(word) == 8) {
24 return 10000000000000000000U;
25 } else {
26 return 1000000000U;
27 }
28}
29
30consteval size_t decimal_conversion_radix_digits() {
31 if constexpr(sizeof(word) == 8) {
32 return 19;
33 } else {
34 return 9;
35 }
36}
37
38} // namespace
39
40std::string BigInt::to_dec_string() const {
41 // Use the largest power of 10 that fits in a word
42 constexpr word conversion_radix = decimal_conversion_radix();
43 constexpr size_t radix_digits = decimal_conversion_radix_digits();
44
45 // (over-)estimate of the number of digits needed; log2(10) ~ 3.3219
46 const size_t digit_estimate = static_cast<size_t>(1 + (static_cast<double>(this->bits()) / 3.32));
47
48 // (over-)estimate of db such that conversion_radix^db > *this
49 const size_t digit_blocks = (digit_estimate + radix_digits - 1) / radix_digits;
50
51 BigInt value = *this;
52 value.set_sign(Positive);
53
54 // Extract groups of digits into words
55 std::vector<word> digit_groups(digit_blocks);
56
57 for(size_t i = 0; i != digit_blocks; ++i) {
58 word remainder = 0;
59 ct_divide_word(value, conversion_radix, value, remainder);
60 digit_groups[i] = remainder;
61 }
62
64
65 // Extract digits from the groups
66 std::vector<uint8_t> digits(digit_blocks * radix_digits);
67
68 constexpr auto div_10 = divide_precomp<word>::setup(10);
69
70 for(size_t i = 0; i != digit_blocks; ++i) {
71 word remainder = digit_groups[i];
72 for(size_t j = 0; j != radix_digits; ++j) {
73 const auto [q, digit] = div_10.divmod_2to1_ct(0, remainder);
74 digits[radix_digits * i + j] = static_cast<uint8_t>(digit);
75 remainder = q;
76 }
77 }
78
79 // remove leading zeros
80 while(!digits.empty() && digits.back() == 0) {
81 digits.pop_back();
82 }
83
84 BOTAN_ASSERT_NOMSG(digit_estimate >= digits.size());
85
86 // Reverse the digits to big-endian and format to text
87 std::string s;
88 s.reserve(1 + digits.size());
89
90 if(signum() < 0) {
91 s += '-';
92 }
93
94 // Reverse and convert to textual digits
95 // TODO(Botan4) use std::ranges::reverse_view here once available (need newer Clang)
96 // NOLINTNEXTLINE(modernize-loop-convert)
97 for(auto i = digits.rbegin(); i != digits.rend(); ++i) {
98 s.push_back(*i + '0'); // assumes ASCII
99 }
100
101 if(s.empty()) {
102 s += '0';
103 }
104
105 return s;
106}
107
108std::string BigInt::to_hex_string() const {
109 const size_t this_bytes = this->bytes();
110 std::vector<uint8_t> bits(std::max<size_t>(1, this_bytes));
111
112 if(this_bytes > 0) {
113 this->serialize_to(bits);
114 }
115
116 std::string hrep;
117 if(signum() < 0) {
118 hrep += '-';
119 }
120 hrep += "0x";
121 hrep += hex_encode(bits);
122 return hrep;
123}
124
125//static
126BigInt BigInt::from_radix_digits(std::string_view digits, size_t radix) {
127 if(radix == 16) {
129
130 if(digits.size() % 2 == 1) {
131 // Handle lack of leading 0
132 const char buf0_with_leading_0[2] = {'0', digits[0]};
133
134 binary = hex_decode_locked(buf0_with_leading_0, 2);
135
136 if(digits.size() > 1) {
137 binary += hex_decode_locked(&digits[1], digits.size() - 1, false);
138 }
139 } else {
140 binary = hex_decode_locked(digits, false);
141 }
142
143 return BigInt::from_bytes(binary);
144 } else if(radix == 10) {
145 // Use the largest power of 10 that fits in a word, accumulating
146 // groups of digits into word-sized chunks to minimize the number
147 // of multiprecision multiplications.
148 constexpr word conversion_radix = decimal_conversion_radix();
149 constexpr size_t radix_digits = decimal_conversion_radix_digits();
150
151 BigInt r;
152
153 // Handle the initial partial block (if digit count is not a multiple of radix_digits)
154 const size_t partial_block = digits.size() % radix_digits;
155
156 if(partial_block > 0) {
157 word acc = 0;
158 for(size_t i = 0; i < partial_block; ++i) {
159 const char c = digits[i];
160 BOTAN_ARG_CHECK(c >= '0' && c <= '9', "Invalid decimal character");
161 acc = acc * 10 + static_cast<word>(c - '0');
162 }
163 r += acc;
164 }
165
166 // Process full blocks of radix_digits
167 for(size_t i = partial_block; i != digits.size(); i += radix_digits) {
168 word acc = 0;
169 for(size_t j = 0; j < radix_digits; ++j) {
170 const char c = digits[i + j];
171 BOTAN_ARG_CHECK(c >= '0' && c <= '9', "Invalid decimal character");
172 acc = acc * 10 + static_cast<word>(c - '0');
173 }
174 r *= conversion_radix;
175 r += acc;
176 }
177
178 return r;
179 } else {
180 throw Invalid_Argument("BigInt::from_radix_digits unknown radix");
181 }
182}
183
184/*
185* Encode two BigInt, with leading 0s if needed, and concatenate
186*/
188 if(n1.signum() < 0 || n2.signum() < 0) {
189 throw Encoding_Error("encode_fixed_length_int_pair: values must be positive");
190 }
191 if(n1.bytes() > bytes || n2.bytes() > bytes) {
192 throw Encoding_Error("encode_fixed_length_int_pair: values too large to encode properly");
193 }
194 secure_vector<uint8_t> output(2 * bytes);
195 BufferStuffer stuffer(output);
196 n1.serialize_to(stuffer.next(bytes));
197 n2.serialize_to(stuffer.next(bytes));
198 return output;
199}
200
201BigInt BigInt::decode(std::span<const uint8_t> buf, Base base) {
202 if(base == Binary) {
203 return BigInt::from_bytes(buf);
204 }
205 return BigInt::decode(buf.data(), buf.size(), base);
206}
207
208/*
209* Decode a BigInt
210*/
211BigInt BigInt::decode(const uint8_t buf[], size_t length, Base base) {
212 if(base == Binary) {
213 return BigInt::from_bytes(std::span{buf, length});
214 } else if(base == Hexadecimal) {
215 const std::string_view sv{cast_uint8_ptr_to_char(buf), length};
216 return BigInt::from_radix_digits(sv, 16);
217 } else if(base == Decimal) {
218 const std::string_view sv{cast_uint8_ptr_to_char(buf), length};
219 return BigInt::from_radix_digits(sv, 10);
220 } else {
221 throw Invalid_Argument("Unknown BigInt decoding method");
222 }
223}
224
225} // namespace Botan
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:82
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:33
BigInt()=default
static BigInt decode(const uint8_t buf[], size_t length)
Definition bigint.h:943
std::string to_dec_string() const
Definition big_code.cpp:40
int signum() const
Definition bigint.h:493
std::string to_hex_string() const
Definition big_code.cpp:108
static secure_vector< uint8_t > encode_fixed_length_int_pair(const BigInt &n1, const BigInt &n2, size_t bytes)
Definition big_code.cpp:187
void serialize_to(std::span< uint8_t > out) const
Definition bigint.cpp:396
static BigInt from_bytes(std::span< const uint8_t > bytes)
Definition bigint.cpp:84
size_t bits() const
Definition bigint.cpp:308
bool is_zero() const
Definition bigint.h:510
size_t bytes() const
Definition bigint.cpp:295
static BigInt from_radix_digits(std::string_view digits, size_t radix)
Definition big_code.cpp:126
void set_sign(Sign sign)
Definition bigint.h:663
Helper class to ease in-place marshalling of concatenated fixed-length values.
constexpr std::span< uint8_t > next(size_t bytes)
static constexpr divide_precomp setup(W divisor)
Definition mp_core.h:695
secure_vector< uint8_t > hex_decode_locked(const char input[], size_t input_length, bool ignore_ws)
Definition hex.cpp:142
void hex_encode(char output[], const uint8_t input[], size_t input_length, bool uppercase)
Definition hex.cpp:34
void ct_divide_word(const BigInt &x, word y, BigInt &q_out, word &r_out)
Definition divide.cpp:205
const char * cast_uint8_ptr_to_char(const uint8_t *b)
Definition mem_ops.h:323
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:128
std::conditional_t< HasNative64BitRegisters, std::uint64_t, uint32_t > word
The native machine word, used as the limb type for multiprecision integers.
Definition types.h:131