Add a constant time divide variant for dividing by uint8_t

Originally wrote it for div-by-word but that ends up requiring a dword
type which we don't always have. And uint8_t covers the most important
cases of n = 10 and n = 58 (whenever I get around to writing base58).
We could portably support up to div-by-uint32, but I don't think we need it.

Nicely for n = 10, this is actually faster than the variable time division.

1 files changed, 22 insertions, 5 deletions

diff --git a/src/fuzzer/divide.cpp b/src/fuzzer/divide.cpp
index c0c86f051..b6342ff7d 100644
--- a/src/fuzzer/divide.cpp
+++ b/src/fuzzer/divide.cpp
@@ -11,25 +11,42 @@ void fuzz(const uint8_t in[], size_t len)
    if(len % 2 == 1 || len > 2*4096/8)
       return;
 
-   const Botan::BigInt x = Botan::BigInt::decode(in, len / 2);
-   const Botan::BigInt y = Botan::BigInt::decode(in + len / 2, len / 2);
+   // Save on allocations by making these static
+   static Botan::BigInt x, y, q, r, ct_q, ct_r, z;
+
+   x = Botan::BigInt::decode(in, len / 2);
+   y = Botan::BigInt::decode(in + len / 2, len / 2);
 
    if(y == 0)
       return;
 
-   Botan::BigInt q, r;
    Botan::divide(x, y, q, r);
 
    FUZZER_ASSERT_TRUE(r < y);
 
-   Botan::BigInt z = q*y + r;
+   z = q*y + r;
 
    FUZZER_ASSERT_EQUAL(z, x);
 
-   Botan::BigInt ct_q, ct_r;
    Botan::ct_divide(x, y, ct_q, ct_r);
 
    FUZZER_ASSERT_EQUAL(q, ct_q);
    FUZZER_ASSERT_EQUAL(r, ct_r);
+
+   // Now divide by just low byte of y
+
+   y = y.byte_at(0);
+   if(y == 0)
+      y = 251;
+   Botan::divide(x, y, q, r);
+
+   z = q*y + r;
+   FUZZER_ASSERT_EQUAL(z, x);
+
+   uint8_t r8;
+   Botan::ct_divide_u8(x, y.byte_at(0), ct_q, r8);
+   FUZZER_ASSERT_EQUAL(ct_q, q);
+   FUZZER_ASSERT_EQUAL(r8, r.byte_at(0));
+
    }