Tor 0.4.9.0-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-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. */
20unsigned
21round_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. */
34uint32_t
35round_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. */
49uint64_t
50round_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 */
61static uint64_t
62gcd64(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. */
74uint64_t
75tor_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. */
88void
89simplify_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}
uint64_t tor_mul_u64_nowrap(uint64_t a, uint64_t b)
Definition: muldiv.c:75
uint32_t round_uint32_to_next_multiple_of(uint32_t number, uint32_t divisor)
Definition: muldiv.c:35
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