tor

The Tor anonymity network
git clone https://git.dasho.dev/tor.git
Log | Files | Refs | README | LICENSE

muldiv.c (2495B)

      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 }