Revamp BigInt encoding and decoding.

Deprecate some crufty functions. Optimize binary encoding/decoding.

4 files changed, 130 insertions, 103 deletions

diff --git a/src/lib/math/bigint/big_code.cpp b/src/lib/math/bigint/big_code.cpp
index 6d8c61fd5..6eb27549e 100644
--- a/src/lib/math/bigint/big_code.cpp
+++ b/src/lib/math/bigint/big_code.cpp
@@ -1,6 +1,6 @@
 /*
 * BigInt Encoding/Decoding
-* (C) 1999-2010,2012 Jack Lloyd
+* (C) 1999-2010,2012,2019 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
@@ -53,36 +53,28 @@ std::string BigInt::to_hex_string() const
 */
 void BigInt::encode(uint8_t output[], const BigInt& n, Base base)
    {
-   if(base == Binary)
-      {
-      n.binary_encode(output);
-      }
-   else if(base == Hexadecimal)
-      {
-      secure_vector<uint8_t> binary(n.encoded_size(Binary));
-      n.binary_encode(binary.data());
+   secure_vector<uint8_t> enc = n.encode_locked(base);
+   copy_mem(output, enc.data(), enc.size());
+   }
 
-      hex_encode(cast_uint8_ptr_to_char(output),
-                 binary.data(), binary.size());
-      }
-   else if(base == Decimal)
-      {
-      BigInt copy = n;
-      uint8_t remainder;
-      copy.set_sign(Positive);
-      const size_t output_size = n.encoded_size(Decimal);
-      for(size_t j = 0; j != output_size; ++j)
-         {
-         ct_divide_u8(copy, 10, copy, remainder);
-         output[output_size - 1 - j] = Charset::digit2char(remainder);
-         if(copy.is_zero())
-            break;
-         }
-      }
-   else
-      throw Invalid_Argument("Unknown BigInt encoding method");
+namespace {
+
+std::vector<uint8_t> str_to_vector(const std::string& s)
+   {
+   std::vector<uint8_t> v(s.size());
+   std::memcpy(v.data(), s.data(), s.size());
+   return v;
+   }
+
+secure_vector<uint8_t> str_to_lvector(const std::string& s)
+   {
+   secure_vector<uint8_t> v(s.size());
+   std::memcpy(v.data(), s.data(), s.size());
+   return v;
    }
 
+}
+
 /*
 * Encode a BigInt
 */
@@ -90,14 +82,12 @@ std::vector<uint8_t> BigInt::encode(const BigInt& n, Base base)
    {
    if(base == Binary)
       return BigInt::encode(n);
-
-   std::vector<uint8_t> output(n.encoded_size(base));
-   encode(output.data(), n, base);
-   for(size_t j = 0; j != output.size(); ++j)
-      if(output[j] == 0)
-         output[j] = '0';
-
-   return output;
+   else if(base == Hexadecimal)
+      return str_to_vector(n.to_hex_string());
+   else if(base == Decimal)
+      return str_to_vector(n.to_dec_string());
+   else
+      throw Invalid_Argument("Unknown BigInt encoding base");
    }
 
 /*
@@ -107,14 +97,12 @@ secure_vector<uint8_t> BigInt::encode_locked(const BigInt& n, Base base)
    {
    if(base == Binary)
       return BigInt::encode_locked(n);
-
-   secure_vector<uint8_t> output(n.encoded_size(base));
-   encode(output.data(), n, base);
-   for(size_t j = 0; j != output.size(); ++j)
-      if(output[j] == 0)
-         output[j] = '0';
-
-   return output;
+   else if(base == Hexadecimal)
+      return str_to_lvector(n.to_hex_string());
+   else if(base == Decimal)
+      return str_to_lvector(n.to_dec_string());
+   else
+      throw Invalid_Argument("Unknown BigInt encoding base");
    }
 
 /*
@@ -122,20 +110,21 @@ secure_vector<uint8_t> BigInt::encode_locked(const BigInt& n, Base base)
 */
 secure_vector<uint8_t> BigInt::encode_1363(const BigInt& n, size_t bytes)
    {
+   if(n.bytes() > bytes)
+      throw Encoding_Error("encode_1363: n is too large to encode properly");
+
    secure_vector<uint8_t> output(bytes);
-   BigInt::encode_1363(output.data(), output.size(), n);
+   n.binary_encode(output.data(), output.size());
    return output;
    }
 
 //static
 void BigInt::encode_1363(uint8_t output[], size_t bytes, const BigInt& n)
    {
-   const size_t n_bytes = n.bytes();
-   if(n_bytes > bytes)
+   if(n.bytes() > bytes)
       throw Encoding_Error("encode_1363: n is too large to encode properly");
 
-   const size_t leading_0s = bytes - n_bytes;
-   encode(&output[leading_0s], n, Binary);
+   n.binary_encode(output, bytes);
    }
 
 /*
@@ -143,9 +132,11 @@ void BigInt::encode_1363(uint8_t output[], size_t bytes, const BigInt& n)
 */
 secure_vector<uint8_t> BigInt::encode_fixed_length_int_pair(const BigInt& n1, const BigInt& n2, size_t bytes)
    {
+   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);
-   BigInt::encode_1363(output.data(), bytes, n1);
-   BigInt::encode_1363(output.data() + bytes, bytes, n2);
+   n1.binary_encode(output.data()        , bytes);
+   n2.binary_encode(output.data() + bytes, bytes);
    return output;
    }
 
@@ -156,7 +147,9 @@ BigInt BigInt::decode(const uint8_t buf[], size_t length, Base base)
    {
    BigInt r;
    if(base == Binary)
+      {
       r.binary_decode(buf, length);
+      }
    else if(base == Hexadecimal)
       {
       secure_vector<uint8_t> binary;
diff --git a/src/lib/math/bigint/big_io.cpp b/src/lib/math/bigint/big_io.cpp
index 90c2253e9..b31315eac 100644
--- a/src/lib/math/bigint/big_io.cpp
+++ b/src/lib/math/bigint/big_io.cpp
@@ -16,10 +16,10 @@ namespace Botan {
 */
 std::ostream& operator<<(std::ostream& stream, const BigInt& n)
    {
-   BigInt::Base base = BigInt::Decimal;
+   size_t base = 10;
    if(stream.flags() & std::ios::hex)
-      base = BigInt::Hexadecimal;
-   else if(stream.flags() & std::ios::oct)
+      base = 16;
+   if(stream.flags() & std::ios::oct)
       throw Invalid_Argument("Octal output of BigInt not supported");
 
    if(n == 0)
@@ -28,12 +28,18 @@ std::ostream& operator<<(std::ostream& stream, const BigInt& n)
       {
       if(n < 0)
          stream.write("-", 1);
-      const std::vector<uint8_t> buffer = BigInt::encode(n, base);
+
+      std::string enc;
+
+      if(base == 10)
+         enc = n.to_dec_string();
+      else
+         enc = n.to_hex_string();
+
       size_t skip = 0;
-      while(skip < buffer.size() && buffer[skip] == '0')
+      while(skip < enc.size() && enc[skip] == '0')
          ++skip;
-      stream.write(cast_uint8_ptr_to_char(buffer.data()) + skip,
-                   buffer.size() - skip);
+      stream.write(&enc[skip], enc.size() - skip);
       }
    if(!stream.good())
       throw Stream_IO_Error("BigInt output operator has failed");
diff --git a/src/lib/math/bigint/bigint.cpp b/src/lib/math/bigint/bigint.cpp
index d2551a991..d2a2f8ee9 100644
--- a/src/lib/math/bigint/bigint.cpp
+++ b/src/lib/math/bigint/bigint.cpp
@@ -1,6 +1,6 @@
 /*
 * BigInt Base
-* (C) 1999-2011,2012,2014 Jack Lloyd
+* (C) 1999-2011,2012,2014,2019 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
@@ -381,14 +381,34 @@ BigInt BigInt::abs() const
    return x;
    }
 
+void BigInt::binary_encode(uint8_t buf[]) const
+   {
+   this->binary_encode(buf, bytes());
+   }
+
 /*
 * Encode this number into bytes
 */
-void BigInt::binary_encode(uint8_t output[]) const
+void BigInt::binary_encode(uint8_t output[], size_t len) const
    {
-   const size_t sig_bytes = bytes();
-   for(size_t i = 0; i != sig_bytes; ++i)
-      output[sig_bytes-i-1] = byte_at(i);
+   const size_t full_words = len / sizeof(word);
+   const size_t extra_bytes = len % sizeof(word);
+
+   for(size_t i = 0; i != full_words; ++i)
+      {
+      const word w = word_at(i);
+      store_be(w, output + (len - (i+1)*sizeof(word)));
+      }
+
+   if(extra_bytes > 0)
+      {
+      const word w = word_at(full_words);
+
+      for(size_t i = 0; i != extra_bytes; ++i)
+         {
+         output[extra_bytes - i - 1] = get_byte(sizeof(word) - i - 1, w);
+         }
+      }
    }
 
 /*
@@ -396,21 +416,20 @@ void BigInt::binary_encode(uint8_t output[]) const
 */
 void BigInt::binary_decode(const uint8_t buf[], size_t length)
    {
-   const size_t WORD_BYTES = sizeof(word);
-
    clear();
-   secure_vector<word> reg((round_up((length / WORD_BYTES) + 1, 8)));
 
-   // TODO can load a word at a time here
-   for(size_t i = 0; i != length / WORD_BYTES; ++i)
+   const size_t full_words = length / sizeof(word);
+   const size_t extra_bytes = length % sizeof(word);
+
+   secure_vector<word> reg((round_up(full_words + 1, 8)));
+
+   for(size_t i = 0; i != full_words; ++i)
       {
-      const size_t top = length - WORD_BYTES*i;
-      for(size_t j = WORD_BYTES; j > 0; --j)
-         reg[i] = (reg[i] << 8) | buf[top - j];
+      reg[i] = load_be<word>(buf + length - sizeof(word)*(i+1), 0);
       }
 
-   for(size_t i = 0; i != length % WORD_BYTES; ++i)
-      reg[length / WORD_BYTES] = (reg[length / WORD_BYTES] << 8) | buf[i];
+   for(size_t i = 0; i != length % sizeof(word); ++i)
+      reg[full_words] = (reg[full_words] << 8) | buf[i];
 
    m_data.swap(reg);
    }
diff --git a/src/lib/math/bigint/bigint.h b/src/lib/math/bigint/bigint.h
index 387bbe8f9..227edfb6b 100644
--- a/src/lib/math/bigint/bigint.h
+++ b/src/lib/math/bigint/bigint.h
@@ -669,6 +669,18 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
      void binary_encode(uint8_t buf[]) const;
 
      /**
+     * Store BigInt-value in a given byte array. If len is less than
+     * the size of the value, then it will be truncated. If len is
+     * greater than the size of the value, it will be zero-padded.
+     * If len exactly equals this->bytes(), this function behaves identically
+     * to binary_encode.
+     *
+     * @param buf destination byte array for the integer value
+     * @param len how many bytes to write
+     */
+     void binary_encode(uint8_t buf[], size_t len) const;
+
+     /**
      * Read integer value from a byte array with given size
      * @param buf byte array buffer containing the integer
      * @param length size of buf
@@ -676,10 +688,11 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
      void binary_decode(const uint8_t buf[], size_t length);
 
      /**
-     * Read integer value from a byte array (secure_vector<uint8_t>)
-     * @param buf the array to load from
+     * Read integer value from a byte vector
+     * @param buf the vector to load from
      */
-     void binary_decode(const secure_vector<uint8_t>& buf)
+     template<typename Alloc>
+     void binary_decode(const std::vector<uint8_t, Alloc>& buf)
         {
         binary_decode(buf.data(), buf.size());
         }
@@ -687,7 +700,11 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
      /**
      * @param base the base to measure the size for
      * @return size of this integer in base base
+     *
+     * Deprecated. This is only needed when using the `encode` and
+     * `encode_locked` functions, which are also deprecated.
      */
+     BOTAN_DEPRECATED("See comments on declaration")
      size_t encoded_size(Base base = Binary) const;
 
      /**
@@ -772,7 +789,7 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
      * @param buf destination byte array for the encoded integer
      * @param n the BigInt to use as integer source
      */
-     static void encode(uint8_t buf[], const BigInt& n)
+     static BOTAN_DEPRECATED("Use n.binary_encode") void encode(uint8_t buf[], const BigInt& n)
         {
         n.binary_encode(buf);
         }
@@ -793,17 +810,8 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
      * @param buf the binary value to load
      * @result BigInt representing the integer in the byte array
      */
-     static BigInt decode(const secure_vector<uint8_t>& buf)
-        {
-        return BigInt(buf);
-        }
-
-     /**
-     * Create a BigInt from an integer in a byte array
-     * @param buf the binary value to load
-     * @result BigInt representing the integer in the byte array
-     */
-     static BigInt decode(const std::vector<uint8_t>& buf)
+     template<typename Alloc>
+     static BigInt decode(const std::vector<uint8_t, Alloc>& buf)
         {
         return BigInt(buf);
         }
@@ -813,7 +821,12 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
      * @param n the BigInt to use as integer source
      * @param base number-base of resulting byte array representation
      * @result secure_vector of bytes containing the integer with given base
+     *
+     * Deprecated. If you need Binary, call the version of encode that doesn't
+     * take a Base. If you need Hex or Decimal output, use to_hex_string or
+     * to_dec_string resp.
      */
+     BOTAN_DEPRECATED("See comments on declaration")
      static std::vector<uint8_t> encode(const BigInt& n, Base base);
 
      /**
@@ -821,7 +834,12 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
      * @param n the BigInt to use as integer source
      * @param base number-base of resulting byte array representation
      * @result secure_vector of bytes containing the integer with given base
+     *
+     * Deprecated. If you need Binary, call the version of encode_locked that
+     * doesn't take a Base. If you need Hex or Decimal output, use to_hex_string
+     * or to_dec_string resp.
      */
+     BOTAN_DEPRECATED("See comments on declaration")
      static secure_vector<uint8_t> encode_locked(const BigInt& n,
                                                  Base base);
 
@@ -831,7 +849,11 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
      * value with given base
      * @param n the BigInt to use as integer source
      * @param base number-base of resulting byte array representation
+     *
+     * Deprecated. If you need Binary, call binary_encode. If you need
+     * Hex or Decimal output, use to_hex_string or to_dec_string resp.
      */
+     BOTAN_DEPRECATED("See comments on declaration")
      static void encode(uint8_t buf[], const BigInt& n, Base base);
 
      /**
@@ -850,21 +872,8 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
      * @param base number-base of the integer in buf
      * @result BigInt representing the integer in the byte array
      */
-     static BigInt decode(const secure_vector<uint8_t>& buf,
-                          Base base)
-        {
-        if(base == Binary)
-           return BigInt(buf);
-        return BigInt::decode(buf.data(), buf.size(), base);
-        }
-
-     /**
-     * Create a BigInt from an integer in a byte array
-     * @param buf the binary value to load
-     * @param base number-base of the integer in buf
-     * @result BigInt representing the integer in the byte array
-     */
-     static BigInt decode(const std::vector<uint8_t>& buf, Base base)
+     template<typename Alloc>
+     static BigInt decode(const std::vector<uint8_t, Alloc>& buf, Base base)
         {
         if(base == Binary)
            return BigInt(buf);