Coverage Report

Created: 2022-06-23 06:44

/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.empty() && 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.22k
   {
108
8.22k
   if(n.bytes() > bytes)
109
2
      throw Encoding_Error("encode_1363: n is too large to encode properly");
110
111
8.22k
   secure_vector<uint8_t> output(bytes);
112
8.22k
   n.binary_encode(output.data(), output.size());
113
8.22k
   return output;
114
8.22k
   }
115
116
//static
117
void BigInt::encode_1363(uint8_t output[], size_t bytes, const BigInt& n)
118
46.5k
   {
119
46.5k
   if(n.bytes() > bytes)
120
0
      throw Encoding_Error("encode_1363: n is too large to encode properly");
121
122
46.5k
   n.binary_encode(output, bytes);
123
46.5k
   }
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
11.0k
   {
145
11.0k
   BigInt r;
146
11.0k
   if(base == Binary)
147
0
      {
148
0
      r.binary_decode(buf, length);
149
0
      }
150
11.0k
   else if(base == Hexadecimal)
151
9.99k
      {
152
9.99k
      secure_vector<uint8_t> binary;
153
154
9.99k
      if(length % 2)
155
2.07k
         {
156
         // Handle lack of leading 0
157
2.07k
         const char buf0_with_leading_0[2] =
158
2.07k
            { '0', static_cast<char>(buf[0]) };
159
160
2.07k
         binary = hex_decode_locked(buf0_with_leading_0, 2);
161
162
2.07k
         binary += hex_decode_locked(cast_uint8_ptr_to_char(&buf[1]),
163
2.07k
                                     length - 1,
164
2.07k
                                     false);
165
2.07k
         }
166
7.92k
      else
167
7.92k
         binary = hex_decode_locked(cast_uint8_ptr_to_char(buf),
168
7.92k
                                    length, false);
169
170
9.99k
      r.binary_decode(binary.data(), binary.size());
171
9.99k
      }
172
1.05k
   else if(base == Decimal)
173
1.05k
      {
174
      // This could be made faster using the same trick as to_dec_string
175
2.10k
      for(size_t i = 0; i != length; ++i)
176
1.05k
         {
177
1.05k
         const char c = buf[i];
178
179
1.05k
         if(c < '0' || c > '9')
180
0
            throw Invalid_Argument("BigInt::decode: invalid decimal char");
181
182
1.05k
         const uint8_t x = c - '0';
183
1.05k
         BOTAN_ASSERT_NOMSG(x < 10);
184
185
1.05k
         r *= 10;
186
1.05k
         r += x;
187
1.05k
         }
188
1.05k
      }
189
0
   else
190
0
      throw Invalid_Argument("Unknown BigInt decoding method");
191
11.0k
   return r;
192
11.0k
   }
193
194
}