Tor  0.4.3.1-alpha-dev
muldiv.c
Go to the documentation of this file.
1 /* Copyright (c) 2003-2004, Roger Dingledine
2  * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
3  * Copyright (c) 2007-2020, 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 }
unsigned round_to_next_multiple_of(unsigned number, unsigned divisor)
Definition: muldiv.c:21
uint64_t round_uint64_to_next_multiple_of(uint64_t number, uint64_t divisor)
Definition: muldiv.c:50
Header for muldiv.c.
Headers for torerr.c.
uint32_t round_uint32_to_next_multiple_of(uint32_t number, uint32_t divisor)
Definition: muldiv.c:35
uint64_t tor_mul_u64_nowrap(uint64_t a, uint64_t b)
Definition: muldiv.c:75