Merge GH #2258 Optimize BigInt::get_substring

2 files changed, 25 insertions, 18 deletions

diff --git a/src/lib/math/bigint/bigint.cpp b/src/lib/math/bigint/bigint.cpp
index bdb0f4214..3ada94dce 100644
--- a/src/lib/math/bigint/bigint.cpp
+++ b/src/lib/math/bigint/bigint.cpp
@@ -216,18 +216,27 @@ uint32_t BigInt::get_substring(size_t offset, size_t length) const
    if(length == 0 || length > 32)
       throw Invalid_Argument("BigInt::get_substring invalid substring length");
 
-   const size_t byte_offset = offset / 8;
-   const size_t shift = (offset % 8);
    const uint32_t mask = 0xFFFFFFFF >> (32 - length);
 
-   const uint8_t b0 = byte_at(byte_offset);
-   const uint8_t b1 = byte_at(byte_offset + 1);
-   const uint8_t b2 = byte_at(byte_offset + 2);
-   const uint8_t b3 = byte_at(byte_offset + 3);
-   const uint8_t b4 = byte_at(byte_offset + 4);
-   const uint64_t piece = make_uint64(0, 0, 0, b4, b3, b2, b1, b0);
+   const size_t word_offset = offset / BOTAN_MP_WORD_BITS;
+   const size_t wshift = (offset % BOTAN_MP_WORD_BITS);
 
-   return static_cast<uint32_t>((piece >> shift) & mask);
+   /*
+   * The substring is contained within one or at most two words. The
+   * offset and length are not secret, so we can perform conditional
+   * operations on those values.
+   */
+   const word w0 = word_at(word_offset);
+
+   if(wshift == 0 || (offset + length) / BOTAN_MP_WORD_BITS == word_offset)
+      {
+      return static_cast<uint32_t>(w0 >> wshift) & mask;
+      }
+   else
+      {
+      const word w1 = word_at(word_offset + 1);
+      return static_cast<uint32_t>((w0 >> wshift) | (w1 << (BOTAN_MP_WORD_BITS - wshift))) & mask;
+      }
    }
 
 /*
diff --git a/src/tests/test_bigint.cpp b/src/tests/test_bigint.cpp
index ad898fe4c..dbe308079 100644
--- a/src/tests/test_bigint.cpp
+++ b/src/tests/test_bigint.cpp
@@ -154,22 +154,20 @@ class BigInt_Unit_Tests final : public Test
 
       Test::Result test_get_substring()
          {
-         const size_t trials = 1000;
-
          Test::Result result("BigInt get_substring");
 
-         const Botan::BigInt r(Test::rng(), 250);
+         const size_t rbits = 1024;
+
+         const Botan::BigInt r(Test::rng(), rbits);
 
-         for(size_t s = 1; s <= 32; ++s)
+         for(size_t wlen = 1; wlen <= 32; ++wlen)
             {
-            for(size_t trial = 0; trial != trials; ++trial)
+            for(size_t offset = 0; offset != rbits + 64; ++offset)
                {
-               const size_t offset = Test::rng().next_byte();
-
-               const uint32_t val = r.get_substring(offset, s);
+               const uint32_t val = r.get_substring(offset, wlen);
 
                Botan::BigInt t = r >> offset;
-               t.mask_bits(s);
+               t.mask_bits(wlen);
 
                const uint32_t cmp = t.to_u32bit();