Add a function to simplify a fraction.

Apparently remembering euclid's algorithm does pay off sooner or later.

3 files changed, 51 insertions, 0 deletions

diff --git a/src/common/util.c b/src/common/util.c
index d9361563ef..5a73098b91 100644
--- a/src/common/util.c
+++ b/src/common/util.c
@@ -580,6 +580,29 @@ add_laplace_noise(int64_t signal, double random, double delta_f,
     return signal + noise;
 }
 
+/* Helper: return greatest common divisor of a,b */
+static uint64_t
+gcd64(uint64_t a, uint64_t b)
+{
+  while (b) {
+    uint64_t t = b;
+    b = a % b;
+    a = t;
+  }
+  return a;
+}
+
+/* Given a fraction *<b>numer</b> / *<b>denom</b>, simplify it.
+ * Requires that the denominator is greater than 0. */
+void
+simplify_fraction64(uint64_t *numer, uint64_t *denom)
+{
+  tor_assert(denom);
+  uint64_t gcd = gcd64(*numer, *denom);
+  *numer /= gcd;
+  *denom /= gcd;
+}
+
 /** Return the number of bits set in <b>v</b>. */
 int
 n_bits_set_u8(uint8_t v)
diff --git a/src/common/util.h b/src/common/util.h
index a6638aa39b..9face0c322 100644
--- a/src/common/util.h
+++ b/src/common/util.h
@@ -152,6 +152,8 @@ int64_t add_laplace_noise(int64_t signal, double random, double delta_f,
                           double epsilon);
 int n_bits_set_u8(uint8_t v);
 int64_t clamp_double_to_int64(double number);
+void simplify_fraction64(uint64_t *numer, uint64_t *denom);
+
 
 /* Compute the CEIL of <b>a</b> divided by <b>b</b>, for nonnegative <b>a</b>
  * and positive <b>b</b>.  Works on integer types only. Not defined if a+b can
diff --git a/src/test/test_util.c b/src/test/test_util.c
index 38df7bb445..e173569c37 100644
--- a/src/test/test_util.c
+++ b/src/test/test_util.c
@@ -4657,6 +4657,31 @@ test_util_mathlog(void *arg)
 }
 
 static void
+test_util_fraction(void *arg)
+{
+  uint64_t a,b;
+  (void)arg;
+
+  a = 99; b = 30;
+  simplify_fraction64(&a,&b);
+  tt_u64_op(a, OP_EQ, 33);
+  tt_u64_op(b, OP_EQ, 10);
+
+  a = 3000000; b = 10000000;
+  simplify_fraction64(&a,&b);
+  tt_u64_op(a, OP_EQ, 3);
+  tt_u64_op(b, OP_EQ, 10);
+
+  a = 0; b = 15;
+  simplify_fraction64(&a,&b);
+  tt_u64_op(a, OP_EQ, 0);
+  tt_u64_op(b, OP_EQ, 1);
+
+ done:
+  ;
+}
+
+static void
 test_util_round_to_next_multiple_of(void *arg)
 {
   (void)arg;
@@ -5479,6 +5504,7 @@ struct testcase_t util_tests[] = {
   UTIL_TEST(read_file_eof_zero_bytes, 0),
   UTIL_TEST(write_chunks_to_file, 0),
   UTIL_TEST(mathlog, 0),
+  UTIL_TEST(fraction, 0),
   UTIL_TEST(weak_random, 0),
   { "socket_ipv4", test_util_socket, TT_FORK, &passthrough_setup,
     (void*)"4" },