Add a function to simplify a fraction.

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

2 files changed, 25 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