1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
|
/* Copyright (c) 2003-2004, Roger Dingledine
* Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
* Copyright (c) 2007-2020, The Tor Project, Inc. */
/* See LICENSE for licensing information */
/**
* \file muldiv.c
*
* \brief Integer math related to multiplication, division, and rounding.
**/
#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;
}
/** Return the unsigned integer product of <b>a</b> and <b>b</b>. If overflow
* is detected, return UINT64_MAX instead. */
uint64_t
tor_mul_u64_nowrap(uint64_t a, uint64_t b)
{
if (a == 0 || b == 0) {
return 0;
} else if (PREDICT_UNLIKELY(UINT64_MAX / a < b)) {
return UINT64_MAX;
} else {
return a*b;
}
}
/* 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;
}
|
