Extract simple integer math into its own module

13 files changed, 284 insertions, 3 deletions

diff --git a/src/lib/container/.may_include b/src/lib/container/.may_include
index eaa020bf50..42458b2953 100644
--- a/src/lib/container/.may_include
+++ b/src/lib/container/.may_include
@@ -7,10 +7,10 @@ lib/malloc/*.h
 lib/err/*.h
 lib/string/*.h
 lib/testsupport/testsupport.h
+lib/intmath/*.h
 
 ht.h
 siphash.h
 
 # XXX I'd like to remove this.
-common/util.h
 common/util_bug.h
diff --git a/src/lib/container/bloomfilt.c b/src/lib/container/bloomfilt.c
index 4847408ee7..cbb4d13e5d 100644
--- a/src/lib/container/bloomfilt.c
+++ b/src/lib/container/bloomfilt.c
@@ -14,7 +14,7 @@
 #include <stdlib.h>
 #include "lib/malloc/util_malloc.h"
 #include "lib/container/bloomfilt.h"
-#include "common/util.h" // For tor_log2
+#include "lib/intmath/bits.h"
 
 /** Return a newly allocated digestset_t, optimized to hold a total of
  * <b>max_elements</b> digests with a reasonably low false positive weight. */
diff --git a/src/lib/crypt_ops/.may_include b/src/lib/crypt_ops/.may_include
index 0a9a0dda22..1b9289b2f1 100644
--- a/src/lib/crypt_ops/.may_include
+++ b/src/lib/crypt_ops/.may_include
@@ -6,6 +6,7 @@ lib/ctime/*.h
 lib/defs/*.h
 lib/malloc/*.h
 lib/err/*.h
+lib/intmath/*.h
 lib/string/*.h
 lib/testsupport/testsupport.h
 
diff --git a/src/lib/crypt_ops/crypto_pwbox.c b/src/lib/crypt_ops/crypto_pwbox.c
index 9a315d42da..6944f8ab52 100644
--- a/src/lib/crypt_ops/crypto_pwbox.c
+++ b/src/lib/crypt_ops/crypto_pwbox.c
@@ -15,6 +15,7 @@
 #include "lib/crypt_ops/crypto_s2k.h"
 #include "lib/crypt_ops/crypto_util.h"
 #include "lib/ctime/di_ops.h"
+#include "lib/intmath/muldiv.h"
 #include "common/util.h"
 #include "trunnel/pwbox.h"
 
@@ -212,4 +213,3 @@ crypto_unpwbox(uint8_t **out, size_t *outlen_out,
   memwipe(keys, 0, sizeof(keys));
   return rv;
 }
-
diff --git a/src/lib/intmath/.may_include b/src/lib/intmath/.may_include
new file mode 100644
index 0000000000..d96c112220
--- /dev/null
+++ b/src/lib/intmath/.may_include
@@ -0,0 +1,4 @@
+orconfig.h
+lib/cc/*.h
+lib/err/*.h
+lib/intmath/*.h
diff --git a/src/lib/intmath/addsub.c b/src/lib/intmath/addsub.c
new file mode 100644
index 0000000000..816c5a2bd7
--- /dev/null
+++ b/src/lib/intmath/addsub.c
@@ -0,0 +1,20 @@
+/* Copyright (c) 2003-2004, Roger Dingledine
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2018, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#include "lib/intmath/addsub.h"
+#include "lib/cc/compat_compiler.h"
+
+/* Helper: safely add two uint32_t's, capping at UINT32_MAX rather
+ * than overflow */
+uint32_t
+tor_add_u32_nowrap(uint32_t a, uint32_t b)
+{
+  /* a+b > UINT32_MAX check, without overflow */
+  if (PREDICT_UNLIKELY(a > UINT32_MAX - b)) {
+    return UINT32_MAX;
+  } else {
+    return a+b;
+  }
+}
diff --git a/src/lib/intmath/addsub.h b/src/lib/intmath/addsub.h
new file mode 100644
index 0000000000..5277adfa49
--- /dev/null
+++ b/src/lib/intmath/addsub.h
@@ -0,0 +1,13 @@
+/* Copyright (c) 2003-2004, Roger Dingledine
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2018, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#ifndef TOR_INTMATH_ADDSUB_H
+#define TOR_INTMATH_ADDSUB_H
+
+#include "lib/cc/torint.h"
+
+uint32_t tor_add_u32_nowrap(uint32_t a, uint32_t b);
+
+#endif /* !defined(TOR_INTMATH_MULDIV_H) */
diff --git a/src/lib/intmath/bits.c b/src/lib/intmath/bits.c
new file mode 100644
index 0000000000..85d901f71b
--- /dev/null
+++ b/src/lib/intmath/bits.c
@@ -0,0 +1,88 @@
+/* Copyright (c) 2003-2004, Roger Dingledine
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2018, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#include "lib/intmath/bits.h"
+
+/** Returns floor(log2(u64)).  If u64 is 0, (incorrectly) returns 0. */
+int
+tor_log2(uint64_t u64)
+{
+  int r = 0;
+  if (u64 >= (U64_LITERAL(1)<<32)) {
+    u64 >>= 32;
+    r = 32;
+  }
+  if (u64 >= (U64_LITERAL(1)<<16)) {
+    u64 >>= 16;
+    r += 16;
+  }
+  if (u64 >= (U64_LITERAL(1)<<8)) {
+    u64 >>= 8;
+    r += 8;
+  }
+  if (u64 >= (U64_LITERAL(1)<<4)) {
+    u64 >>= 4;
+    r += 4;
+  }
+  if (u64 >= (U64_LITERAL(1)<<2)) {
+    u64 >>= 2;
+    r += 2;
+  }
+  if (u64 >= (U64_LITERAL(1)<<1)) {
+    // u64 >>= 1; // not using this any more.
+    r += 1;
+  }
+  return r;
+}
+
+/** Return the power of 2 in range [1,UINT64_MAX] closest to <b>u64</b>.  If
+ * there are two powers of 2 equally close, round down. */
+uint64_t
+round_to_power_of_2(uint64_t u64)
+{
+  int lg2;
+  uint64_t low;
+  uint64_t high;
+  if (u64 == 0)
+    return 1;
+
+  lg2 = tor_log2(u64);
+  low = U64_LITERAL(1) << lg2;
+
+  if (lg2 == 63)
+    return low;
+
+  high = U64_LITERAL(1) << (lg2+1);
+  if (high - u64 < u64 - low)
+    return high;
+  else
+    return low;
+}
+
+/** Return the number of bits set in <b>v</b>. */
+int
+n_bits_set_u8(uint8_t v)
+{
+  static const int nybble_table[] = {
+    0, /* 0000 */
+    1, /* 0001 */
+    1, /* 0010 */
+    2, /* 0011 */
+    1, /* 0100 */
+    2, /* 0101 */
+    2, /* 0110 */
+    3, /* 0111 */
+    1, /* 1000 */
+    2, /* 1001 */
+    2, /* 1010 */
+    3, /* 1011 */
+    2, /* 1100 */
+    3, /* 1101 */
+    3, /* 1110 */
+    4, /* 1111 */
+  };
+
+  return nybble_table[v & 15] + nybble_table[v>>4];
+}
diff --git a/src/lib/intmath/bits.h b/src/lib/intmath/bits.h
new file mode 100644
index 0000000000..70f855089c
--- /dev/null
+++ b/src/lib/intmath/bits.h
@@ -0,0 +1,16 @@
+/* Copyright (c) 2003-2004, Roger Dingledine
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2018, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#ifndef TOR_INTMATH_BITS_H
+#define TOR_INTMATH_BITS_H
+
+#include "lib/cc/torint.h"
+#include "lib/cc/compat_compiler.h"
+
+int tor_log2(uint64_t u64) ATTR_CONST;
+uint64_t round_to_power_of_2(uint64_t u64);
+int n_bits_set_u8(uint8_t v);
+
+#endif /* !defined(TOR_INTMATH_BITS_H) */
diff --git a/src/lib/intmath/cmp.h b/src/lib/intmath/cmp.h
new file mode 100644
index 0000000000..90ea3ca079
--- /dev/null
+++ b/src/lib/intmath/cmp.h
@@ -0,0 +1,20 @@
+/* Copyright (c) 2003-2004, Roger Dingledine
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2018, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#ifndef TOR_INTMATH_CMP_H
+#define TOR_INTMATH_CMP_H
+
+/* Return <b>v</b> if it's between <b>min</b> and <b>max</b>.  Otherwise
+ * return <b>min</b> if <b>v</b> is smaller than <b>min</b>, or <b>max</b> if
+ * <b>b</b> is larger than <b>max</b>.
+ *
+ * Requires that <b>min</b> is no more than <b>max</b>. May evaluate any of
+ * its arguments more than once! */
+#define CLAMP(min,v,max)                        \
+  ( ((v) < (min)) ? (min) :                     \
+    ((v) > (max)) ? (max) :                     \
+    (v) )
+
+#endif /* !defined(TOR_INTMATH_CMP_H) */
diff --git a/src/lib/intmath/include.am b/src/lib/intmath/include.am
new file mode 100644
index 0000000000..40459d106d
--- /dev/null
+++ b/src/lib/intmath/include.am
@@ -0,0 +1,22 @@
+
+noinst_LIBRARIES += src/lib/libtor-intmath.a
+
+if UNITTESTS_ENABLED
+noinst_LIBRARIES += src/lib/libtor-intmath-testing.a
+endif
+
+src_lib_libtor_intmath_a_SOURCES =			\
+	src/lib/intmath/addsub.c			\
+	src/lib/intmath/bits.c				\
+	src/lib/intmath/muldiv.c
+
+src_lib_libtor_intmath_testing_a_SOURCES = \
+	$(src_lib_libtor_intmath_a_SOURCES)
+src_lib_libtor_intmath_testing_a_CPPFLAGS = $(AM_CPPFLAGS) $(TEST_CPPFLAGS)
+src_lib_libtor_intmath_testing_a_CFLAGS = $(AM_CFLAGS) $(TEST_CFLAGS)
+
+noinst_HEADERS +=					\
+	src/lib/intmath/addsub.h			\
+	src/lib/intmath/cmp.h				\
+	src/lib/intmath/bits.h				\
+	src/lib/intmath/muldiv.h
diff --git a/src/lib/intmath/muldiv.c b/src/lib/intmath/muldiv.c
new file mode 100644
index 0000000000..3e627b237a
--- /dev/null
+++ b/src/lib/intmath/muldiv.c
@@ -0,0 +1,75 @@
+/* Copyright (c) 2003-2004, Roger Dingledine
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2018, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#include "lib/intmath/muldiv.h"
+#include "lib/err/torerr.h"
+
+#include <stdlib.h>
+
+/** Return the lowest x such that x is at least <b>number</b>, and x modulo
+ * <b>divisor</b> == 0.  If no such x can be expressed as an unsigned, return
+ * UINT_MAX. Asserts if divisor is zero. */
+unsigned
+round_to_next_multiple_of(unsigned number, unsigned divisor)
+{
+  raw_assert(divisor > 0);
+  if (UINT_MAX - divisor + 1 < number)
+    return UINT_MAX;
+  number += divisor - 1;
+  number -= number % divisor;
+  return number;
+}
+
+/** Return the lowest x such that x is at least <b>number</b>, and x modulo
+ * <b>divisor</b> == 0. If no such x can be expressed as a uint32_t, return
+ * UINT32_MAX. Asserts if divisor is zero. */
+uint32_t
+round_uint32_to_next_multiple_of(uint32_t number, uint32_t divisor)
+{
+  raw_assert(divisor > 0);
+  if (UINT32_MAX - divisor + 1 < number)
+    return UINT32_MAX;
+
+  number += divisor - 1;
+  number -= number % divisor;
+  return number;
+}
+
+/** Return the lowest x such that x is at least <b>number</b>, and x modulo
+ * <b>divisor</b> == 0. If no such x can be expressed as a uint64_t, return
+ * UINT64_MAX. Asserts if divisor is zero. */
+uint64_t
+round_uint64_to_next_multiple_of(uint64_t number, uint64_t divisor)
+{
+  raw_assert(divisor > 0);
+  if (UINT64_MAX - divisor + 1 < number)
+    return UINT64_MAX;
+  number += divisor - 1;
+  number -= number % divisor;
+  return number;
+}
+
+/* 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)
+{
+  raw_assert(denom);
+  uint64_t gcd = gcd64(*numer, *denom);
+  *numer /= gcd;
+  *denom /= gcd;
+}
diff --git a/src/lib/intmath/muldiv.h b/src/lib/intmath/muldiv.h
new file mode 100644
index 0000000000..de76d9eb68
--- /dev/null
+++ b/src/lib/intmath/muldiv.h
@@ -0,0 +1,22 @@
+/* Copyright (c) 2003-2004, Roger Dingledine
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2018, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#ifndef TOR_INTMATH_MULDIV_H
+#define TOR_INTMATH_MULDIV_H
+
+#include "lib/cc/torint.h"
+
+unsigned round_to_next_multiple_of(unsigned number, unsigned divisor);
+uint32_t round_uint32_to_next_multiple_of(uint32_t number, uint32_t divisor);
+uint64_t round_uint64_to_next_multiple_of(uint64_t number, uint64_t divisor);
+
+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-1)
+ * can overflow. */
+#define CEIL_DIV(a,b) (((a)+((b)-1))/(b))
+
+#endif /* !defined(TOR_INTMATH_MULDIV_H) */