22853126324

Committed 09 Mar 2026 12:19PM UTC coverage: 90.174% (-0.01%) from 90.184%

Build # 22853126324

Build Type

Pull #5425

github

Committed by

web-flow

Commit Message

Merge 78217ae0f into cdaa9c0ff

Pull Request Pull Request #5425: BigInt encoding cleanups

Run Details

103792 of 115102 relevant lines covered (90.17%)

11778053.81 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

80.43

/src/lib/math/bigint/big_code.cpp

/*
* BigInt Encoding/Decoding
* (C) 1999-2010,2012,2019,2021 Jack Lloyd
*
* Botan is released under the Simplified BSD License (see license.txt)
*/

#include <botan/bigint.h>

#include <botan/assert.h>
#include <botan/exceptn.h>
#include <botan/hex.h>
#include <botan/mem_ops.h>
#include <botan/internal/buffer_stuffer.h>
#include <botan/internal/divide.h>
#include <botan/internal/mp_core.h>

namespace Botan {

namespace {

consteval word decimal_conversion_radix() {
   if constexpr(sizeof(word) == 8) {
      return 10000000000000000000U;
   } else {
      return 1000000000U;
   }
}

consteval size_t decimal_conversion_radix_digits() {
   if constexpr(sizeof(word) == 8) {
      return 19;
   } else {
      return 9;
   }
}

}  // namespace

std::string BigInt::to_dec_string() const {
   // Use the largest power of 10 that fits in a word
   constexpr word conversion_radix = decimal_conversion_radix();
   constexpr size_t radix_digits = decimal_conversion_radix_digits();

   // (over-)estimate of the number of digits needed; log2(10) ~ 3.3219
   const size_t digit_estimate = static_cast<size_t>(1 + (static_cast<double>(this->bits()) / 3.32));

   // (over-)estimate of db such that conversion_radix^db > *this
   const size_t digit_blocks = (digit_estimate + radix_digits - 1) / radix_digits;

   BigInt value = *this;
   value.set_sign(Positive);

   // Extract groups of digits into words
   std::vector<word> digit_groups(digit_blocks);

   for(size_t i = 0; i != digit_blocks; ++i) {
      word remainder = 0;
      ct_divide_word(value, conversion_radix, value, remainder);
      digit_groups[i] = remainder;
   }

   BOTAN_ASSERT_NOMSG(value.is_zero());

   // Extract digits from the groups
   std::vector<uint8_t> digits(digit_blocks * radix_digits);

   for(size_t i = 0; i != digit_blocks; ++i) {
      word remainder = digit_groups[i];
      for(size_t j = 0; j != radix_digits; ++j) {
         const word new_remainder = divide_10(remainder);
         const word digit = remainder - new_remainder * 10;
         digits[radix_digits * i + j] = static_cast<uint8_t>(digit);
         remainder = new_remainder;
      }
   }

   // remove leading zeros
   while(!digits.empty() && digits.back() == 0) {
      digits.pop_back();
   }

   BOTAN_ASSERT_NOMSG(digit_estimate >= digits.size());

   // Reverse the digits to big-endian and format to text
   std::string s;
   s.reserve(1 + digits.size());

   if(is_negative()) {
      s += "-";
   }

   // Reverse and convert to textual digits
   // TODO(Botan4) use std::ranges::reverse_view here once available (need newer Clang)
   // NOLINTNEXTLINE(modernize-loop-convert)
   for(auto i = digits.rbegin(); i != digits.rend(); ++i) {
      s.push_back(*i + '0');  // assumes ASCII
   }

   if(s.empty()) {
      s += "0";
   }

   return s;
}

std::string BigInt::to_hex_string() const {
   const size_t this_bytes = this->bytes();
   std::vector<uint8_t> bits(std::max<size_t>(1, this_bytes));

   if(this_bytes > 0) {
      this->serialize_to(bits);
   }

   std::string hrep;
   if(is_negative()) {
      hrep += "-";
   }
   hrep += "0x";
   hrep += hex_encode(bits);
   return hrep;
}

//static
BigInt BigInt::from_radix_digits(std::string_view digits, size_t radix) {
   if(radix == 16) {
      secure_vector<uint8_t> binary;

      if(digits.size() % 2 == 1) {
         // Handle lack of leading 0
         const char buf0_with_leading_0[2] = {'0', digits[0]};

         binary = hex_decode_locked(buf0_with_leading_0, 2);

         if(digits.size() > 1) {
            binary += hex_decode_locked(&digits[1], digits.size() - 1, false);
         }
      } else {
         binary = hex_decode_locked(digits, false);
      }

      return BigInt::from_bytes(binary);
   } else if(radix == 10) {
      BigInt r;
      // TODO: This could be made faster using the same trick as to_dec_string
      for(const char c : digits) {
         BOTAN_ARG_CHECK(c >= '0' && c <= '9', "Invalid decimal character");

         const uint8_t x = c - '0';
         BOTAN_ASSERT_NOMSG(x < 10);

         r *= 10;
         r += x;
      }
      return r;
   } else {
      throw Invalid_Argument("BigInt::from_radix_digits unknown radix");
   }
}

/*
* Encode two BigInt, with leading 0s if needed, and concatenate
*/
secure_vector<uint8_t> BigInt::encode_fixed_length_int_pair(const BigInt& n1, const BigInt& n2, size_t bytes) {
   if(n1.is_negative() || n2.is_negative()) {
      throw Encoding_Error("encode_fixed_length_int_pair: values must be positive");
   }
   if(n1.bytes() > bytes || n2.bytes() > bytes) {
      throw Encoding_Error("encode_fixed_length_int_pair: values too large to encode properly");
   }
   secure_vector<uint8_t> output(2 * bytes);
   BufferStuffer stuffer(output);
   n1.serialize_to(stuffer.next(bytes));
   n2.serialize_to(stuffer.next(bytes));
   return output;
}

BigInt BigInt::decode(std::span<const uint8_t> buf, Base base) {
   if(base == Binary) {
      return BigInt::from_bytes(buf);
   }
   return BigInt::decode(buf.data(), buf.size(), base);
}

/*
* Decode a BigInt
*/
BigInt BigInt::decode(const uint8_t buf[], size_t length, Base base) {
   if(base == Binary) {
      return BigInt::from_bytes(std::span{buf, length});
   } else if(base == Hexadecimal) {
      std::string_view sv{cast_uint8_ptr_to_char(buf), length};
      return BigInt::from_radix_digits(sv, 16);

      /*
      */
   } else if(base == Decimal) {
      std::string_view sv{cast_uint8_ptr_to_char(buf), length};
      return BigInt::from_radix_digits(sv, 10);
   } else {
      throw Invalid_Argument("Unknown BigInt decoding method");
   }
}

}  // namespace Botan

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
18	namespace Botan {
19
20	namespace {
21
22	consteval word decimal_conversion_radix() {
23	if constexpr(sizeof(word) == 8) {
24	return 10000000000000000000U;
25	} else {
26	return 1000000000U;
27	}
28	}
29
30	consteval 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
40	std::string BigInt::to_dec_string() const {	60✔
41	// Use the largest power of 10 that fits in a word
42	constexpr word conversion_radix = decimal_conversion_radix();	60✔
43	constexpr size_t radix_digits = decimal_conversion_radix_digits();	60✔
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));	60✔
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;	60✔
50
51	BigInt value = *this;	60✔
52	value.set_sign(Positive);	60✔
53
54	// Extract groups of digits into words
55	std::vector<word> digit_groups(digit_blocks);	60✔
56
57	for(size_t i = 0; i != digit_blocks; ++i) {	132✔
58	word remainder = 0;	72✔
59	ct_divide_word(value, conversion_radix, value, remainder);	72✔
60	digit_groups[i] = remainder;	72✔
61	}
62
63	BOTAN_ASSERT_NOMSG(value.is_zero());	120✔
64
65	// Extract digits from the groups
66	std::vector<uint8_t> digits(digit_blocks * radix_digits);	60✔
67
68	for(size_t i = 0; i != digit_blocks; ++i) {	132✔
69	word remainder = digit_groups[i];	72✔
70	for(size_t j = 0; j != radix_digits; ++j) {	1,440✔
71	const word new_remainder = divide_10(remainder);	1,368✔
72	const word digit = remainder - new_remainder * 10;	1,368✔
73	digits[radix_digits * i + j] = static_cast<uint8_t>(digit);	1,368✔
74	remainder = new_remainder;	1,368✔
75	}
76	}
77
78	// remove leading zeros
79	while(!digits.empty() && digits.back() == 0) {	960✔
80	digits.pop_back();	900✔
81	}
82
83	BOTAN_ASSERT_NOMSG(digit_estimate >= digits.size());	60✔
84
85	// Reverse the digits to big-endian and format to text
86	std::string s;	60✔
87	s.reserve(1 + digits.size());	60✔
88
89	if(is_negative()) {	60✔
90	s += "-";	5✔
91	}
92
93	// Reverse and convert to textual digits
94	// TODO(Botan4) use std::ranges::reverse_view here once available (need newer Clang)
95	// NOLINTNEXTLINE(modernize-loop-convert)
96	for(auto i = digits.rbegin(); i != digits.rend(); ++i) {	528✔
97	s.push_back(*i + '0'); // assumes ASCII	468✔
98	}
99
100	if(s.empty()) {	60✔
101	s += "0";	6✔
102	}
103
104	return s;	120✔
105	}	120✔
106
107	std::string BigInt::to_hex_string() const {	86✔
108	const size_t this_bytes = this->bytes();	86✔
109	std::vector<uint8_t> bits(std::max<size_t>(1, this_bytes));	145✔
110
111	if(this_bytes > 0) {	86✔
112	this->serialize_to(bits);	84✔
113	}
114
115	std::string hrep;	86✔
116	if(is_negative()) {	86✔
117	hrep += "-";	5✔
118	}
119	hrep += "0x";	86✔
120	hrep += hex_encode(bits);	172✔
121	return hrep;	86✔
122	}	86✔
123
124	//static
125	BigInt BigInt::from_radix_digits(std::string_view digits, size_t radix) {	47,089✔
126	if(radix == 16) {	47,089✔
127	secure_vector<uint8_t> binary;	42,820✔
128
129	if(digits.size() % 2 == 1) {	42,820✔
130	// Handle lack of leading 0
131	const char buf0_with_leading_0[2] = {'0', digits[0]};	4,290✔
132
133	binary = hex_decode_locked(buf0_with_leading_0, 2);	8,580✔
134
135	if(digits.size() > 1) {	4,290✔
136	binary += hex_decode_locked(&digits[1], digits.size() - 1, false);	6,162✔
137	}
138	} else {
139	binary = hex_decode_locked(digits, false);	77,060✔
140	}
141
142	return BigInt::from_bytes(binary);	42,820✔
143	} else if(radix == 10) {	47,089✔
144	BigInt r;	4,269✔
145	// TODO: This could be made faster using the same trick as to_dec_string
146	for(const char c : digits) {	383,041✔
147	BOTAN_ARG_CHECK(c >= '0' && c <= '9', "Invalid decimal character");	378,772✔
148
149	const uint8_t x = c - '0';	378,772✔
150	BOTAN_ASSERT_NOMSG(x < 10);	378,772✔
151
152	r *= 10;	378,772✔
153	r += x;	378,772✔
154	}
155	return r;	4,269✔
156	} else {	4,269✔
157	throw Invalid_Argument("BigInt::from_radix_digits unknown radix");	×
158	}
159	}
160
161	/*
162	* Encode two BigInt, with leading 0s if needed, and concatenate
163	*/
164	secure_vector<uint8_t> BigInt::encode_fixed_length_int_pair(const BigInt& n1, const BigInt& n2, size_t bytes) {	1✔
165	if(n1.is_negative() \|\| n2.is_negative()) {	1✔
166	throw Encoding_Error("encode_fixed_length_int_pair: values must be positive");	×
167	}
168	if(n1.bytes() > bytes \|\| n2.bytes() > bytes) {	1✔
169	throw Encoding_Error("encode_fixed_length_int_pair: values too large to encode properly");	×
170	}
171	secure_vector<uint8_t> output(2 * bytes);	1✔
172	BufferStuffer stuffer(output);	1✔
173	n1.serialize_to(stuffer.next(bytes));	1✔
174	n2.serialize_to(stuffer.next(bytes));	1✔
175	return output;	1✔
176	}	×
177
178	BigInt BigInt::decode(std::span<const uint8_t> buf, Base base) {	×
179	if(base == Binary) {	×
180	return BigInt::from_bytes(buf);	×
181	}
182	return BigInt::decode(buf.data(), buf.size(), base);	×
183	}
184
185	/*
186	* Decode a BigInt
187	*/
188	BigInt BigInt::decode(const uint8_t buf[], size_t length, Base base) {	×
189	if(base == Binary) {	×
190	return BigInt::from_bytes(std::span{buf, length});	×
191	} else if(base == Hexadecimal) {	×
192	std::string_view sv{cast_uint8_ptr_to_char(buf), length};	×
193	return BigInt::from_radix_digits(sv, 16);	×
194
195	/*
196	*/
197	} else if(base == Decimal) {	×
198	std::string_view sv{cast_uint8_ptr_to_char(buf), length};	×
199	return BigInt::from_radix_digits(sv, 10);	×
200	} else {
201	throw Invalid_Argument("Unknown BigInt decoding method");	×
202	}
203	}
204
205	} // namespace Botan

randombit / botan / 22853126324

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous