big_code.cpp

Go to the documentation of this file.

/*
* 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) {
      // Use the largest power of 10 that fits in a word, accumulating
      // groups of digits into word-sized chunks to minimize the number
      // of multiprecision multiplications.
      constexpr word conversion_radix = decimal_conversion_radix();
      constexpr size_t radix_digits = decimal_conversion_radix_digits();
 
      BigInt r;
 
      // Handle the initial partial block (if digit count is not a multiple of radix_digits)
      const size_t partial_block = digits.size() % radix_digits;
 
      if(partial_block > 0) {
         word acc = 0;
         for(size_t i = 0; i < partial_block; ++i) {
            const char c = digits[i];
            BOTAN_ARG_CHECK(c >= '0' && c <= '9', "Invalid decimal character");
            acc = acc * 10 + static_cast<word>(c - '0');
         }
         r += acc;
      }
 
      // Process full blocks of radix_digits
      for(size_t i = partial_block; i != digits.size(); i += radix_digits) {
         word acc = 0;
         for(size_t j = 0; j < radix_digits; ++j) {
            const char c = digits[i + j];
            BOTAN_ARG_CHECK(c >= '0' && c <= '9', "Invalid decimal character");
            acc = acc * 10 + static_cast<word>(c - '0');
         }
         r *= conversion_radix;
         r += acc;
      }
 
      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) {
      const std::string_view sv{cast_uint8_ptr_to_char(buf), length};
      return BigInt::from_radix_digits(sv, 16);
   } else if(base == Decimal) {
      const 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