src/lib/intmath/muldiv.c

   1 /* Copyright (c) 2003-2004, Roger Dingledine
   2  * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
   3  * Copyright (c) 2007-2021, The Tor Project, Inc. */
   4 /* See LICENSE for licensing information */
   5
   6 /**
   7  * \file muldiv.c
   8  *
   9  * \brief Integer math related to multiplication, division, and rounding.
  10  **/
  11
  12 #include "lib/intmath/muldiv.h"
  13 #include "lib/err/torerr.h"
  14
  15 #include <stdlib.h>
  16
  17 /** Return the lowest x such that x is at least <b>number</b>, and x modulo
  18  * <b>divisor</b> == 0.  If no such x can be expressed as an unsigned, return
  19  * UINT_MAX. Asserts if divisor is zero. */
  20 unsigned
  21 round_to_next_multiple_of(unsigned number, unsigned divisor)
  22 {
  23   raw_assert(divisor > 0);
  24   if (UINT_MAX - divisor + 1 < number)
  25     return UINT_MAX;
  26   number += divisor - 1;
  27   number -= number % divisor;
  28   return number;
  29 }
  30
  31 /** Return the lowest x such that x is at least <b>number</b>, and x modulo
  32  * <b>divisor</b> == 0. If no such x can be expressed as a uint32_t, return
  33  * UINT32_MAX. Asserts if divisor is zero. */
  34 uint32_t
  35 round_uint32_to_next_multiple_of(uint32_t number, uint32_t divisor)
  36 {
  37   raw_assert(divisor > 0);
  38   if (UINT32_MAX - divisor + 1 < number)
  39     return UINT32_MAX;
  40
  41   number += divisor - 1;
  42   number -= number % divisor;
  43   return number;
  44 }
  45
  46 /** Return the lowest x such that x is at least <b>number</b>, and x modulo
  47  * <b>divisor</b> == 0. If no such x can be expressed as a uint64_t, return
  48  * UINT64_MAX. Asserts if divisor is zero. */
  49 uint64_t
  50 round_uint64_to_next_multiple_of(uint64_t number, uint64_t divisor)
  51 {
  52   raw_assert(divisor > 0);
  53   if (UINT64_MAX - divisor + 1 < number)
  54     return UINT64_MAX;
  55   number += divisor - 1;
  56   number -= number % divisor;
  57   return number;
  58 }
  59
  60 /* Helper: return greatest common divisor of a,b */
  61 static uint64_t
  62 gcd64(uint64_t a, uint64_t b)
  63 {
  64   while (b) {
  65     uint64_t t = b;
  66     b = a % b;
  67     a = t;
  68   }
  69   return a;
  70 }
  71
  72 /** Return the unsigned integer product of <b>a</b> and <b>b</b>. If overflow
  73  * is detected, return UINT64_MAX instead. */
  74 uint64_t
  75 tor_mul_u64_nowrap(uint64_t a, uint64_t b)
  76 {
  77   if (a == 0 || b == 0) {
  78     return 0;
  79   } else if (PREDICT_UNLIKELY(UINT64_MAX / a < b)) {
  80     return UINT64_MAX;
  81   } else {
  82     return a*b;
  83   }
  84 }
  85
  86 /* Given a fraction *<b>numer</b> / *<b>denom</b>, simplify it.
  87  * Requires that the denominator is greater than 0. */
  88 void
  89 simplify_fraction64(uint64_t *numer, uint64_t *denom)
  90 {
  91   raw_assert(denom);
  92   uint64_t gcd = gcd64(*numer, *denom);
  93   *numer /= gcd;
  94   *denom /= gcd;
  95 }