/src/botan/src/lib/math/bigint/big_code.cpp
Line | Count | Source (jump to first uncovered line) |
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 | | #include <botan/internal/divide.h> |
10 | | #include <botan/hex.h> |
11 | | |
12 | | namespace Botan { |
13 | | |
14 | | std::string BigInt::to_dec_string() const |
15 | 0 | { |
16 | | // Use the largest power of 10 that fits in a word |
17 | 0 | #if (BOTAN_MP_WORD_BITS == 64) |
18 | 0 | const word conversion_radix = 10000000000000000000U; |
19 | 0 | const word radix_digits = 19; |
20 | | #else |
21 | | const word conversion_radix = 1000000000U; |
22 | | const word radix_digits = 9; |
23 | | #endif |
24 | | |
25 | | // (over-)estimate of the number of digits needed; log2(10) ~ 3.3219 |
26 | 0 | const size_t digit_estimate = static_cast<size_t>(1 + (this->bits() / 3.32)); |
27 | | |
28 | | // (over-)estimate of db such that conversion_radix^db > *this |
29 | 0 | const size_t digit_blocks = (digit_estimate + radix_digits - 1) / radix_digits; |
30 | |
|
31 | 0 | BigInt value = *this; |
32 | 0 | value.set_sign(Positive); |
33 | | |
34 | | // Extract groups of digits into words |
35 | 0 | std::vector<word> digit_groups(digit_blocks); |
36 | |
|
37 | 0 | for(size_t i = 0; i != digit_blocks; ++i) |
38 | 0 | { |
39 | 0 | word remainder = 0; |
40 | 0 | ct_divide_word(value, conversion_radix, value, remainder); |
41 | 0 | digit_groups[i] = remainder; |
42 | 0 | } |
43 | |
|
44 | 0 | BOTAN_ASSERT_NOMSG(value.is_zero()); |
45 | | |
46 | | // Extract digits from the groups |
47 | 0 | std::vector<uint8_t> digits(digit_blocks * radix_digits); |
48 | |
|
49 | 0 | for(size_t i = 0; i != digit_blocks; ++i) |
50 | 0 | { |
51 | 0 | word remainder = digit_groups[i]; |
52 | 0 | for(size_t j = 0; j != radix_digits; ++j) |
53 | 0 | { |
54 | | // Compiler should convert div/mod by 10 into mul by magic constant |
55 | 0 | const word digit = remainder % 10; |
56 | 0 | remainder /= 10; |
57 | 0 | digits[radix_digits*i + j] = static_cast<uint8_t>(digit); |
58 | 0 | } |
59 | 0 | } |
60 | | |
61 | | // remove leading zeros |
62 | 0 | while(digits.size() > 0 && digits.back() == 0) |
63 | 0 | { |
64 | 0 | digits.pop_back(); |
65 | 0 | } |
66 | |
|
67 | 0 | BOTAN_ASSERT_NOMSG(digit_estimate >= digits.size()); |
68 | | |
69 | | // Reverse the digits to big-endian and format to text |
70 | 0 | std::string s; |
71 | 0 | s.reserve(1 + digits.size()); |
72 | |
|
73 | 0 | if(is_negative()) |
74 | 0 | s += "-"; |
75 | | |
76 | | // Reverse and convert to textual digits |
77 | 0 | for(auto i = digits.rbegin(); i != digits.rend(); ++i) |
78 | 0 | { |
79 | 0 | s.push_back(*i + '0'); // assumes ASCII |
80 | 0 | } |
81 | |
|
82 | 0 | if(s.empty()) |
83 | 0 | s += "0"; |
84 | |
|
85 | 0 | return s; |
86 | 0 | } |
87 | | |
88 | | std::string BigInt::to_hex_string() const |
89 | 0 | { |
90 | 0 | std::vector<uint8_t> bits = BigInt::encode(*this); |
91 | |
|
92 | 0 | if(bits.empty()) |
93 | 0 | bits.push_back(0); |
94 | |
|
95 | 0 | std::string hrep; |
96 | 0 | if(is_negative()) |
97 | 0 | hrep += "-"; |
98 | 0 | hrep += "0x"; |
99 | 0 | hrep += hex_encode(bits); |
100 | 0 | return hrep; |
101 | 0 | } |
102 | | |
103 | | /* |
104 | | * Encode a BigInt, with leading 0s if needed |
105 | | */ |
106 | | secure_vector<uint8_t> BigInt::encode_1363(const BigInt& n, size_t bytes) |
107 | 8.58k | { |
108 | 8.58k | if(n.bytes() > bytes) |
109 | 4 | throw Encoding_Error("encode_1363: n is too large to encode properly"); |
110 | | |
111 | 8.57k | secure_vector<uint8_t> output(bytes); |
112 | 8.57k | n.binary_encode(output.data(), output.size()); |
113 | 8.57k | return output; |
114 | 8.58k | } |
115 | | |
116 | | //static |
117 | | void BigInt::encode_1363(uint8_t output[], size_t bytes, const BigInt& n) |
118 | 42.6k | { |
119 | 42.6k | if(n.bytes() > bytes) |
120 | 0 | throw Encoding_Error("encode_1363: n is too large to encode properly"); |
121 | | |
122 | 42.6k | n.binary_encode(output, bytes); |
123 | 42.6k | } |
124 | | |
125 | | /* |
126 | | * Encode two BigInt, with leading 0s if needed, and concatenate |
127 | | */ |
128 | | secure_vector<uint8_t> BigInt::encode_fixed_length_int_pair(const BigInt& n1, const BigInt& n2, size_t bytes) |
129 | 0 | { |
130 | 0 | if(n1.is_negative() || n2.is_negative()) |
131 | 0 | throw Encoding_Error("encode_fixed_length_int_pair: values must be positive"); |
132 | 0 | if(n1.bytes() > bytes || n2.bytes() > bytes) |
133 | 0 | throw Encoding_Error("encode_fixed_length_int_pair: values too large to encode properly"); |
134 | 0 | secure_vector<uint8_t> output(2 * bytes); |
135 | 0 | n1.binary_encode(output.data() , bytes); |
136 | 0 | n2.binary_encode(output.data() + bytes, bytes); |
137 | 0 | return output; |
138 | 0 | } |
139 | | |
140 | | /* |
141 | | * Decode a BigInt |
142 | | */ |
143 | | BigInt BigInt::decode(const uint8_t buf[], size_t length, Base base) |
144 | 8.92k | { |
145 | 8.92k | BigInt r; |
146 | 8.92k | if(base == Binary) |
147 | 0 | { |
148 | 0 | r.binary_decode(buf, length); |
149 | 0 | } |
150 | 8.92k | else if(base == Hexadecimal) |
151 | 8.13k | { |
152 | 8.13k | secure_vector<uint8_t> binary; |
153 | | |
154 | 8.13k | if(length % 2) |
155 | 1.77k | { |
156 | | // Handle lack of leading 0 |
157 | 1.77k | const char buf0_with_leading_0[2] = |
158 | 1.77k | { '0', static_cast<char>(buf[0]) }; |
159 | | |
160 | 1.77k | binary = hex_decode_locked(buf0_with_leading_0, 2); |
161 | | |
162 | 1.77k | binary += hex_decode_locked(cast_uint8_ptr_to_char(&buf[1]), |
163 | 1.77k | length - 1, |
164 | 1.77k | false); |
165 | 1.77k | } |
166 | 6.36k | else |
167 | 6.36k | binary = hex_decode_locked(cast_uint8_ptr_to_char(buf), |
168 | 6.36k | length, false); |
169 | | |
170 | 8.13k | r.binary_decode(binary.data(), binary.size()); |
171 | 8.13k | } |
172 | 784 | else if(base == Decimal) |
173 | 784 | { |
174 | | // This could be made faster using the same trick as to_dec_string |
175 | 1.56k | for(size_t i = 0; i != length; ++i) |
176 | 784 | { |
177 | 784 | const char c = buf[i]; |
178 | | |
179 | 784 | if(c < '0' || c > '9') |
180 | 0 | throw Invalid_Argument("BigInt::decode: invalid decimal char"); |
181 | | |
182 | 784 | const uint8_t x = c - '0'; |
183 | 784 | BOTAN_ASSERT_NOMSG(x < 10); |
184 | | |
185 | 784 | r *= 10; |
186 | 784 | r += x; |
187 | 784 | } |
188 | 784 | } |
189 | 0 | else |
190 | 0 | throw Invalid_Argument("Unknown BigInt decoding method"); |
191 | 8.92k | return r; |
192 | 8.92k | } |
193 | | |
194 | | } |