The FreeRADIUS server  $Id: 15bac2a4c627c01d1aa2047687b3418955ac7f00 $
uint128.h
Go to the documentation of this file.
1 #pragma once
2 /*
3  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
4  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
5  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
6  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
7  * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
8  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
9  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
10  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
11  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
12  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
13  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
14  *
15  * The original 128bit maths functions were mostly taken from:
16  *
17  * http://www.codeproject.com/Tips/617214/UInt-Addition-Subtraction
18  *
19  * As indicated by the original author, this code is redistributed here
20  * under the 2-Clause BSD license.
21  *
22  * This code is copyright 2014 Jacob F. W.
23  *
24  * Other code in this file is distributed under the GPLv2 license.
25  */
26 
27 /*
28  * This program is free software; you can redistribute it and/or modify
29  * it under the terms of the GNU General Public License as published by
30  * the Free Software Foundation; either version 2 of the License, or (at
31  * your option) any later version.
32  *
33  * This program is distributed in the hope that it will be useful,
34  * but WITHOUT ANY WARRANTY; without even the implied warranty of
35  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
36  * GNU General Public License for more details.
37  *
38  * You should have received a copy of the GNU General Public License
39  * along with this program; if not, write to the Free Software
40  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
41  */
42 
43 /**
44  * $Id: 6acf0f34a2c358e843c2e98f610676cc24d36337 $
45  * @file uint128.h
46  * @brief Common functions for manipulating unsigned 128bit integers on
47  * platforms without compiler support.
48  *
49  * @author Jacob F. W
50  * @author Arran Cudbard-Bell
51  *
52  * @copyright 2019 Arran Cudbard-Bell (a.cudbardb@freeradius.org)
53  * @copyright 2019 The FreeRADIUS server project
54  */
55 
56 /*
57  * 128bit integers are not standard on many compilers
58  * despite SSE2 instructions for dealing with them
59  * specifically.
60  */
61 #ifndef HAVE_128BIT_INTEGERS
62 /** Create a 128 bit integer value with n bits high
63  *
64  */
65 static inline uint128_t uint128_gen_mask(uint8_t bits)
66 {
67  uint128_t ret;
68 
69  fr_assert(bits < 128);
70 
71  if (bits > 64) {
72  ret.l = 0xffffffffffffffff;
73  ret.h = (uint64_t)1 << (bits - 64);
74  ret.h ^= (ret.h - 1);
75  return ret;
76  }
77  ret.h = 0;
78  ret.l = (uint64_t)1 << bits;
79  ret.l ^= (ret.l - 1);
80 
81  return ret;
82 }
83 
84 /** Increment a 128bit unsigned integer
85  *
86  * @author Jacob F. W
87  */
88 static inline uint128_t uint128_increment(uint128_t n)
89 {
90  uint64_t t = (n.l + 1);
91 
92  n.h += ((n.l ^ t) & n.l) >> 63;
93  n.l = t;
94 
95  return n;
96 }
97 
98 /** Decrement a 128bit unsigned integer
99  *
100  * @author Jacob F. W
101  */
102 static inline uint128_t uint128_decrement(uint128_t n)
103 {
104  uint64_t t = (n.l - 1);
105  n.h -= ((t ^ n.l) & t) >> 63;
106  n.l = t;
107 
108  return n;
109 }
110 
111 /** Add two 128bit unsigned integers
112  *
113  * @author Jacob F. W
114  */
115 static inline uint128_t uint128_add(uint128_t a, uint128_t b)
116 {
117  uint128_t ret;
118  uint64_t tmp = (((a.l & b.l) & 1) + (a.l >> 1) + (b.l >> 1)) >> 63;
119  ret.l = a.l + b.l;
120  ret.h = a.h + b.h + tmp;
121  return ret;
122 }
123 
124 /** Subtract one 128bit integer from another
125  *
126  * @author Jacob F. W
127  */
128 static inline uint128_t uint128_sub(uint128_t a, uint128_t b)
129 {
130  uint128_t ret;
131  uint64_t c;
132 
133  ret.l = a.l - b.l;
134  c = (((ret.l & b.l) & 1) + (b.l >> 1) + (ret.l >> 1)) >> 63;
135  ret.h = a.h - (b.h + c);
136 
137  return ret;
138 }
139 
140 /** Multiply two unsigned 64bit integers to get an unsigned 128bit integer
141  *
142  * @author Jacob F. W
143  */
144 static inline uint128_t uint128_mul64(uint64_t u, uint64_t v)
145 {
146  uint128_t ret;
147  uint64_t u1 = (u & 0xffffffff);
148  uint64_t v1 = (v & 0xffffffff);
149 
150  uint64_t t = (u1 * v1);
151 
152  uint64_t w3 = (t & 0xffffffff);
153 
154  uint64_t k = (t >> 32);
155 
156  uint64_t w1;
157 
158  u >>= 32;
159  t = (u * v1) + k;
160  k = (t & 0xffffffff);
161  w1 = (t >> 32);
162 
163  v >>= 32;
164  t = (u1 * v) + k;
165  k = (t >> 32);
166 
167  ret.h = (u * v) + w1 + k;
168  ret.l = (t << 32) + w3;
169 
170  return ret;
171 }
172 
173 /** Multiply two unsigned 128bit integers
174  *
175  * @author Jacob F. W
176  */
177 static inline uint128_t uint128_mul(uint128_t n, uint128_t m)
178 {
179  uint128_t ret;
180 
181  ret = uint128_mul64(n.l, m.l);
182  ret.h += (n.h * m.l) + (n.l * m.h);
183 
184  return ret;
185 }
186 
187 /** Left shift 128 bit integer
188  *
189  * @note shift must be 127 bits or less.
190  */
191 static inline uint128_t uint128_lshift(uint128_t num, uint8_t bits)
192 {
193  fr_assert(bits < 128);
194 
195  if (bits >= 64) {
196  num.l = 0;
197  num.h = num.l << (bits - 64);
198  return num;
199  }
200  num.h = (num.h << bits) | (num.l >> (64 - bits));
201  num.l <<= bits;
202 
203  return num;
204 }
205 
206 /** Right shift 128 bit integer
207  *
208  * @note shift must be 127 bits or less.
209  */
210 static inline uint128_t uint128_rshift(uint128_t num, uint8_t bits)
211 {
212  fr_assert(bits < 128);
213 
214  if (bits >= 64) {
215  num.h = 0;
216  num.l = num.h >> (bits - 64);
217  return num;
218  }
219  num.l = (num.l >> bits) | (num.h << (64 - bits));
220  num.h >>= bits;
221 
222  return num;
223 }
224 
225 /** Perform bitwise & of two 128bit unsigned integers
226  *
227  */
228 static inline uint128_t uint128_band(uint128_t a, uint128_t b)
229 {
230  uint128_t ret;
231  ret.l = a.l & b.l;
232  ret.h = a.h & b.h;
233  return ret;
234 }
235 
236 /** Perform bitwise | of two 128bit unsigned integers
237  *
238  */
239 static inline uint128_t uint128_bor(uint128_t a, uint128_t b)
240 {
241  uint128_t ret;
242  ret.l = a.l | b.l;
243  ret.h = a.h | b.h;
244  return ret;
245 }
246 
247 /** Return whether the integers are equal
248  *
249  */
250 static inline bool uint128_eq(uint128_t a, uint128_t b)
251 {
252  return (a.h == b.h) && (a.l == b.l);
253 }
254 
255 /** Return whether one integer is greater than the other
256  *
257  */
258 static inline bool uint128_gt(uint128_t a, uint128_t b)
259 {
260  if (a.h < b.h) return false;
261  if (a.h > b.h) return true;
262  return (a.l > b.l);
263 }
264 
265 /** Creates a new uint128_t from a uint64_t
266  *
267  */
268 static inline uint128_t uint128_new(uint64_t h, uint64_t l)
269 {
270  uint128_t ret;
271  ret.l = l;
272  ret.h = h;
273  return ret;
274 }
275 
276 /** Returns the low bits of a 128bit integer
277  *
278  */
279 static inline uint64_t uint128_to_64(uint128_t a)
280 {
281  return a.l;
282 }
283 #else
284 #define uint128_gen_mask(_bits) (((_bits) >= 128) ? ~(uint128_t)0x00 : (((uint128_t)1) << (_bits)) - 1)
285 
286 #define uint128_increment(_a) (*_a++)
287 #define uint128_decrement(_a) (*_a--)
288 #define uint128_add(_a, _b) (_a + _b)
289 #define uint128_sub(_a, _b) (_a - _b)
290 #define uint128_mul64(_a, _b) (((uint128_t)(_a)) * ((uint128_t)(_b)))
291 #define uint128_mul(_a, _b) ((_a) * (_b))
292 
293 #define uint128_lshift(_num, _bits) (_num << _bits)
294 #define uint128_rshift(_num, _bits) (_num >> _bits)
295 #define uint128_band(_a, _b) (_a & _b)
296 #define uint128_bor(_a, _b) (_a | _b)
297 
298 #define uint128_eq(_a, _b) (_a == _b)
299 #define uint128_gt(_a, _b) (_a > _b)
300 
301 #define uint128_new(_a, _b) ((uint128_t)_b | ((uint128_t)_a << 64))
302 
303 #define uint128_to_64(_a) ((uint64_t)(_a))
304 #endif
int n
Definition: acutest.h:577
unsigned char uint8_t
Definition: merged_model.c:30
fr_assert(0)
static uint128_t uint128_new(uint64_t h, uint64_t l)
Creates a new uint128_t from a uint64_t.
Definition: uint128.h:268
static uint128_t uint128_band(uint128_t a, uint128_t b)
Perform bitwise & of two 128bit unsigned integers.
Definition: uint128.h:228
static uint128_t uint128_gen_mask(uint8_t bits)
Create a 128 bit integer value with n bits high.
Definition: uint128.h:65
static uint64_t uint128_to_64(uint128_t a)
Returns the low bits of a 128bit integer.
Definition: uint128.h:279
static uint128_t uint128_increment(uint128_t n)
Increment a 128bit unsigned integer.
Definition: uint128.h:88
static uint128_t uint128_bor(uint128_t a, uint128_t b)
Perform bitwise | of two 128bit unsigned integers.
Definition: uint128.h:239
static uint128_t uint128_lshift(uint128_t num, uint8_t bits)
Left shift 128 bit integer.
Definition: uint128.h:191
static bool uint128_gt(uint128_t a, uint128_t b)
Return whether one integer is greater than the other.
Definition: uint128.h:258
static bool uint128_eq(uint128_t a, uint128_t b)
Return whether the integers are equal.
Definition: uint128.h:250
static uint128_t uint128_mul64(uint64_t u, uint64_t v)
Multiply two unsigned 64bit integers to get an unsigned 128bit integer.
Definition: uint128.h:144
static uint128_t uint128_sub(uint128_t a, uint128_t b)
Subtract one 128bit integer from another.
Definition: uint128.h:128
static uint128_t uint128_rshift(uint128_t num, uint8_t bits)
Right shift 128 bit integer.
Definition: uint128.h:210
static uint128_t uint128_add(uint128_t a, uint128_t b)
Add two 128bit unsigned integers.
Definition: uint128.h:115
static uint128_t uint128_decrement(uint128_t n)
Decrement a 128bit unsigned integer.
Definition: uint128.h:102
static uint128_t uint128_mul(uint128_t n, uint128_t m)
Multiply two unsigned 128bit integers.
Definition: uint128.h:177