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, 43 insertions, 0 deletions

diff --git a/src/cli/speed.cpp b/src/cli/speed.cpp
index 59771fb65..4ec4c0f31 100644
--- a/src/cli/speed.cpp
+++ b/src/cli/speed.cpp
@@ -658,6 +658,10 @@ class Speed final : public Command
                {
                bench_mp_div(msec);
                }
+            else if(algo == "mp_div10")
+               {
+               bench_mp_div10(msec);
+               }
 #endif
 
 #if defined(BOTAN_HAS_NUMBERTHEORY)
@@ -1308,6 +1312,45 @@ class Speed final : public Command
             }
          }
 
+      void bench_mp_div10(const std::chrono::milliseconds runtime)
+         {
+         std::chrono::milliseconds runtime_per_size = runtime;
+
+         for(size_t n_bits : { 256, 384, 512, 768, 1024, 1536, 2048, 3072, 4096 })
+            {
+            const std::string bit_descr = std::to_string(n_bits) + "/10";
+
+            std::unique_ptr<Timer> div_timer = make_timer("BigInt div " + bit_descr);
+            std::unique_ptr<Timer> ct_div_timer = make_timer("BigInt ct_div " + bit_descr);
+
+            Botan::BigInt x;
+            Botan::secure_vector<Botan::word> ws;
+
+            const Botan::BigInt ten(10);
+            Botan::BigInt q1, r1, q2;
+            uint8_t r2;
+
+            while(ct_div_timer->under(runtime_per_size))
+               {
+               x.randomize(rng(), n_bits);
+
+               div_timer->start();
+               Botan::divide(x, ten, q1, r1);
+               div_timer->stop();
+
+               ct_div_timer->start();
+               Botan::ct_divide_u8(x, 10, q2, r2);
+               ct_div_timer->stop();
+
+               BOTAN_ASSERT_EQUAL(q1, q2, "Quotient ok");
+               BOTAN_ASSERT_EQUAL(r1, r2, "Remainder ok");
+               }
+
+            record_result(div_timer);
+            record_result(ct_div_timer);
+            }
+         }
+
 #endif
 
 #if defined(BOTAN_HAS_DL_GROUP)