commit 09c25697d74cdfdefe5fa365e4691cc9401e2129 Author: Nick Mathewson nickm@torproject.org Date: Tue Jul 26 11:23:34 2016 -0400
Add a function to simplify a fraction.
Apparently remembering euclid's algorithm does pay off sooner or later. --- src/common/util.c | 23 +++++++++++++++++++++++ src/common/util.h | 2 ++ src/test/test_util.c | 26 ++++++++++++++++++++++++++ 3 files changed, 51 insertions(+)
diff --git a/src/common/util.c b/src/common/util.c index d936156..5a73098 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 a6638aa..9face0c 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 38df7bb..e173569 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" },