1 /*
2 ** OSSP ui128 - 128-Bit Arithmetic
3 ** Copyright (c) 2002-2005 Ralf S. Engelschall <rse@engelschall.com>
4 ** Copyright (c) 2002-2005 The OSSP Project <http://www.ossp.org/>
5 **
6 ** This file is part of OSSP ui128, a 128-bit arithmetic library
7 ** which can be found at http://www.ossp.org/pkg/lib/ui128/.
8 **
9 ** Permission to use, copy, modify, and distribute this software for
10 ** any purpose with or without fee is hereby granted, provided that
11 ** the above copyright notice and this permission notice appear in all
12 ** copies.
13 **
14 ** THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
15 ** WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
16 ** MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
17 ** IN NO EVENT SHALL THE AUTHORS AND COPYRIGHT HOLDERS AND THEIR
18 ** CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
19 ** SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
20 ** LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
21 ** USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
22 ** ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
23 ** OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
24 ** OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
25 ** SUCH DAMAGE.
26 **
27 ** ui128.c: implementation of 128-bit unsigned integer arithmetic
28 */
29
30 /* own headers (part 1/2) */
31 #include "uuid_ac.h"
32
33 /* system headers */
34 #include <string.h>
35 #include <ctype.h>
36
37 /* own headers (part 2/2) */
38 #include "uuid_ui128.h"
39
40 #define UI128_BASE 256 /* 2^8 */
41 #define UI128_DIGITS 16 /* 8*16 = 128 bit */
42 #define UIXX_T(n) struct { unsigned char x[n]; }
43
44 /* fill an ui128_t with a sequence of a particular digit */
45 #define ui128_fill(__x, __n) \
46 /*lint -save -e717*/ \
47 do { int __i; \
48 for (__i = 0; __i < UI128_DIGITS; __i++) \
49 (__x).x[__i] = (__n); \
50 } while (0) \
51 /*lint -restore*/
52
53 /* the value zero */
ui128_zero(void)54 ui128_t ui128_zero(void)
55 {
56 ui128_t z;
57
58 ui128_fill(z, 0);
59 return z;
60 }
61
62 /* the maximum value */
ui128_max(void)63 ui128_t ui128_max(void)
64 {
65 ui128_t z;
66
67 ui128_fill(z, UI128_BASE-1);
68 return z;
69 }
70
71 /* convert ISO-C "unsigned long" into internal format */
ui128_n2i(unsigned long n)72 ui128_t ui128_n2i(unsigned long n)
73 {
74 ui128_t z;
75 int i;
76
77 i = 0;
78 do {
79 z.x[i++] = (n % UI128_BASE);
80 } while ((n /= UI128_BASE) > 0 && i < UI128_DIGITS);
81 for ( ; i < UI128_DIGITS; i++)
82 z.x[i] = 0;
83 return z;
84 }
85
86 /* convert internal format into ISO-C "unsigned long";
87 truncates if sizeof(unsigned long) is less than UI128_DIGITS! */
ui128_i2n(ui128_t x)88 unsigned long ui128_i2n(ui128_t x)
89 {
90 unsigned long n;
91 int i;
92
93 n = 0;
94 i = (int)sizeof(n);
95 /*lint -save -e774*/
96 if (i > UI128_DIGITS)
97 i = UI128_DIGITS;
98 /*lint -restore*/
99 while (--i >= 0) {
100 n = (n * UI128_BASE) + x.x[i];
101 }
102 return n;
103 }
104
105 /* convert string representation of arbitrary base into internal format */
ui128_s2i(const char * str,char ** end,int base)106 ui128_t ui128_s2i(const char *str, char **end, int base)
107 {
108 ui128_t z;
109 const char *cp;
110 int carry;
111 static char map[] = {
112 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, /* 0...9 */
113 36, 36, 36, 36, 36, 36, 36, /* illegal chars */
114 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, /* A...M */
115 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, /* N...Z */
116 36, 36, 36, 36, 36, 36, /* illegal chars */
117 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, /* a...m */
118 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35 /* m...z */
119 };
120
121 ui128_fill(z, 0);
122 if (str == NULL || (base < 2 || base > 36))
123 return z;
124 cp = str;
125 while (*cp != '\0' && isspace((int)(*cp)))
126 cp++;
127 while ( *cp != '\0'
128 && isalnum((int)(*cp))
129 && map[(int)(*cp)-'0'] < base) {
130 z = ui128_muln(z, base, &carry);
131 if (carry)
132 break;
133 z = ui128_addn(z, map[(int)(*cp)-'0'], &carry);
134 if (carry)
135 break;
136 cp++;
137 }
138 if (end != NULL)
139 *end = (char *)cp;
140 return z;
141 }
142
143 /* convert internal format into string representation of arbitrary base */
ui128_i2s(ui128_t x,char * str,size_t len,int base)144 char *ui128_i2s(ui128_t x, char *str, size_t len, int base)
145 {
146 static char map[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
147 char c;
148 int r;
149 int n;
150 int i, j;
151
152 if (str == NULL || len < 2 || (base < 2 || base > 36))
153 return NULL;
154 n = ui128_len(x);
155 i = 0;
156 do {
157 x = ui128_divn(x, base, &r);
158 str[i++] = map[r];
159 while (n > 1 && x.x[n-1] == 0)
160 n--;
161 } while (i < ((int)len-1) && (n > 1 || x.x[0] != 0));
162 str[i] = '\0';
163 for (j = 0; j < --i; j++) {
164 c = str[j];
165 str[j] = str[i];
166 str[i] = c;
167 }
168 return str;
169 }
170
171 /* addition of two ui128_t */
ui128_add(ui128_t x,ui128_t y,ui128_t * ov)172 ui128_t ui128_add(ui128_t x, ui128_t y, ui128_t *ov)
173 {
174 ui128_t z;
175 int carry;
176 int i;
177
178 carry = 0;
179 for (i = 0; i < UI128_DIGITS; i++) {
180 carry += (x.x[i] + y.x[i]);
181 z.x[i] = (carry % UI128_BASE);
182 carry /= UI128_BASE;
183 }
184 if (ov != NULL)
185 *ov = ui128_n2i((unsigned long)carry);
186 return z;
187 }
188
189 /* addition of an ui128_t and a single digit */
ui128_addn(ui128_t x,int y,int * ov)190 ui128_t ui128_addn(ui128_t x, int y, int *ov)
191 {
192 ui128_t z;
193 int i;
194
195 for (i = 0; i < UI128_DIGITS; i++) {
196 y += x.x[i];
197 z.x[i] = (y % UI128_BASE);
198 y /= UI128_BASE;
199 }
200 if (ov != NULL)
201 *ov = y;
202 return z;
203 }
204
205 /* subtraction of two ui128_t */
ui128_sub(ui128_t x,ui128_t y,ui128_t * ov)206 ui128_t ui128_sub(ui128_t x, ui128_t y, ui128_t *ov)
207 {
208 ui128_t z;
209 int borrow;
210 int i;
211 int d;
212
213 borrow = 0;
214 for (i = 0; i < UI128_DIGITS; i++) {
215 d = ((x.x[i] + UI128_BASE) - borrow - y.x[i]);
216 z.x[i] = (d % UI128_BASE);
217 borrow = (1 - (d/UI128_BASE));
218 }
219 if (ov != NULL)
220 *ov = ui128_n2i((unsigned long)borrow);
221 return z;
222 }
223
224 /* subtraction of an ui128_t and a single digit */
ui128_subn(ui128_t x,int y,int * ov)225 ui128_t ui128_subn(ui128_t x, int y, int *ov)
226 {
227 ui128_t z;
228 int i;
229 int d;
230
231 for (i = 0; i < UI128_DIGITS; i++) {
232 d = (x.x[i] + UI128_BASE) - y;
233 z.x[i] = (d % UI128_BASE);
234 y = (1 - (d/UI128_BASE));
235 }
236 if (ov != NULL)
237 *ov = y;
238 return z;
239 }
240
241 /*
242 7 3 2
243 * 9 4 2 8
244 ---------
245 5 8 5 6
246 + 1 4 6 4
247 + 2 9 2 8
248 + 6 5 8 8
249 ---------------
250 = 6 9 0 1 2 9 6
251 */
252
ui128_mul(ui128_t x,ui128_t y,ui128_t * ov)253 ui128_t ui128_mul(ui128_t x, ui128_t y, ui128_t *ov)
254 {
255 UIXX_T(UI128_DIGITS+UI128_DIGITS) zx;
256 ui128_t z;
257 int carry;
258 int i, j;
259
260 /* clear temporary result buffer */
261 for (i = 0; i < (UI128_DIGITS+UI128_DIGITS); i++)
262 zx.x[i] = 0;
263
264 /* perform multiplication operation */
265 for (i = 0; i < UI128_DIGITS; i++) {
266 /* calculate partial product and immediately add to z */
267 carry = 0;
268 for (j = 0; j < UI128_DIGITS; j++) {
269 carry += (x.x[i] * y.x[j]) + zx.x[i+j];
270 zx.x[i+j] = (carry % UI128_BASE);
271 carry /= UI128_BASE;
272 }
273 /* add carry to remaining digits in z */
274 for ( ; j < UI128_DIGITS + UI128_DIGITS - i; j++) {
275 carry += zx.x[i+j];
276 zx.x[i+j] = (carry % UI128_BASE);
277 carry /= UI128_BASE;
278 }
279 }
280
281 /* provide result by splitting zx into z and ov */
282 memcpy(z.x, zx.x, UI128_DIGITS);
283 if (ov != NULL)
284 memcpy((*ov).x, &zx.x[UI128_DIGITS], UI128_DIGITS);
285
286 return z;
287 }
288
ui128_muln(ui128_t x,int y,int * ov)289 ui128_t ui128_muln(ui128_t x, int y, int *ov)
290 {
291 ui128_t z;
292 int carry;
293 int i;
294
295 carry = 0;
296 for (i = 0; i < UI128_DIGITS; i++) {
297 carry += (x.x[i] * y);
298 z.x[i] = (carry % UI128_BASE);
299 carry /= UI128_BASE;
300 }
301 if (ov != NULL)
302 *ov = carry;
303 return z;
304 }
305
306 /*
307 = 2078 [q]
308 0615367 [x] : 296 [y]
309 -0592 [dq]
310 -----
311 = 0233
312 -0000 [dq]
313 -----
314 = 2336
315 -2072 [dq]
316 -----
317 = 2647
318 -2308 [dq]
319 -----
320 = 279 [r]
321 */
ui128_div(ui128_t x,ui128_t y,ui128_t * ov)322 ui128_t ui128_div(ui128_t x, ui128_t y, ui128_t *ov)
323 {
324 ui128_t q;
325 ui128_t r;
326 int i;
327 int n, m;
328 int ovn;
329
330 /* determine actual number of involved digits */
331 n = ui128_len(x);
332 m = ui128_len(y);
333
334 if (m == 1) {
335 /* simple case #1: reduceable to ui128_divn() */
336 if (y.x[0] == 0) {
337 /* error case: division by zero! */
338 ui128_fill(q, 0);
339 ui128_fill(r, 0);
340 }
341 else {
342 q = ui128_divn(x, y.x[0], &ovn);
343 ui128_fill(r, 0);
344 r.x[0] = (unsigned char)ovn;
345 }
346
347 } else if (n < m) {
348 /* simple case #2: everything is in the remainder */
349 ui128_fill(q, 0);
350 r = x;
351
352 } else { /* n >= m, m > 1 */
353 /* standard case: x[0..n] / y[0..m] */
354 UIXX_T(UI128_DIGITS+1) rx;
355 UIXX_T(UI128_DIGITS+1) dq;
356 ui128_t t;
357 int km;
358 int k;
359 int qk;
360 unsigned long y2;
361 unsigned long r3;
362 int borrow;
363 int d;
364
365 /* rx is x with a leading zero in order to make
366 sure that n > m and not just n >= m */
367 memcpy(rx.x, x.x, UI128_DIGITS);
368 rx.x[UI128_DIGITS] = 0;
369
370 for (k = n - m; k >= 0; k--) {
371 /* efficiently compute qk by guessing
372 qk := rx[k+m-2...k+m]/y[m-2...m-1] */
373 km = k + m;
374 y2 = (y.x[m-1]*UI128_BASE) + y.x[m-2];
375 r3 = (rx.x[km]*(UI128_BASE*UI128_BASE)) +
376 (rx.x[km-1]*UI128_BASE) + rx.x[km-2];
377 qk = r3 / y2;
378 if (qk >= UI128_BASE)
379 qk = UI128_BASE - 1;
380
381 /* dq := y*qk (post-adjust qk if guessed incorrectly) */
382 t = ui128_muln(y, qk, &ovn);
383 memcpy(dq.x, t.x, UI128_DIGITS);
384 dq.x[m] = (unsigned char)ovn;
385 for (i = m; i > 0; i--)
386 if (rx.x[i+k] != dq.x[i])
387 break;
388 if (rx.x[i+k] < dq.x[i]) {
389 t = ui128_muln(y, --qk, &ovn);
390 memcpy(dq.x, t.x, UI128_DIGITS);
391 dq.x[m] = (unsigned char)ovn;
392 }
393
394 /* store qk */
395 q.x[k] = (unsigned char)qk;
396
397 /* rx := rx - dq*(b^k) */
398 borrow = 0;
399 for (i = 0; i < m+1; i++) {
400 d = ((rx.x[k+i] + UI128_BASE) - borrow - dq.x[i]);
401 rx.x[k+i] = (d % UI128_BASE);
402 borrow = (1 - (d/UI128_BASE));
403 }
404 }
405 memcpy(r.x, rx.x, m);
406
407 /* fill out results with leading zeros */
408 for (i = n-m+1; i < UI128_DIGITS; i++)
409 q.x[i] = 0;
410 for (i = m; i < UI128_DIGITS; i++)
411 r.x[i] = 0;
412 }
413
414 /* provide results */
415 if (ov != NULL)
416 *ov = r;
417 return q;
418 }
419
ui128_divn(ui128_t x,int y,int * ov)420 ui128_t ui128_divn(ui128_t x, int y, int *ov)
421 {
422 ui128_t z;
423 unsigned int carry;
424 int i;
425
426 carry = 0;
427 for (i = (UI128_DIGITS - 1); i >= 0; i--) {
428 carry = (carry * UI128_BASE) + x.x[i];
429 z.x[i] = (carry / y);
430 carry %= y;
431 }
432 if (ov != NULL)
433 *ov = carry;
434 return z;
435 }
436
ui128_and(ui128_t x,ui128_t y)437 ui128_t ui128_and(ui128_t x, ui128_t y)
438 {
439 ui128_t z;
440 int i;
441
442 for (i = 0; i < UI128_DIGITS; i++)
443 z.x[i] = (x.x[i] & y.x[i]);
444 return z;
445 }
446
ui128_or(ui128_t x,ui128_t y)447 ui128_t ui128_or(ui128_t x, ui128_t y)
448 {
449 ui128_t z;
450 int i;
451
452 for (i = 0; i < UI128_DIGITS; i++)
453 z.x[i] = (x.x[i] | y.x[i]);
454 return z;
455 }
456
ui128_xor(ui128_t x,ui128_t y)457 ui128_t ui128_xor(ui128_t x, ui128_t y)
458 {
459 ui128_t z;
460 int i;
461
462 for (i = 0; i < UI128_DIGITS; i++)
463 z.x[i] = ((x.x[i] & ~(y.x[i])) | (~(x.x[i]) & (y.x[i])));
464 return z;
465 }
466
ui128_not(ui128_t x)467 ui128_t ui128_not(ui128_t x)
468 {
469 ui128_t z;
470 int i;
471
472 for (i = 0; i < UI128_DIGITS; i++)
473 z.x[i] = ~(x.x[i]);
474 return z;
475 }
476
ui128_rol(ui128_t x,int s,ui128_t * ov)477 ui128_t ui128_rol(ui128_t x, int s, ui128_t *ov)
478 {
479 UIXX_T(UI128_DIGITS+UI128_DIGITS) zx;
480 ui128_t z;
481 int i;
482 int carry;
483
484 if (s <= 0) {
485 /* no shift at all */
486 if (ov != NULL)
487 *ov = ui128_zero();
488 return x;
489 }
490 else if (s > 128) {
491 /* too large shift */
492 if (ov != NULL)
493 *ov = ui128_zero();
494 return ui128_zero();
495 }
496 else if (s == 128) {
497 /* maximum shift */
498 if (ov != NULL)
499 *ov = x;
500 return ui128_zero();
501 }
502 else { /* regular shift */
503 /* shift (logically) left by s/8 bytes */
504 for (i = 0; i < UI128_DIGITS+UI128_DIGITS; i++)
505 zx.x[i] = 0;
506 for (i = 0; i < UI128_DIGITS; i++)
507 zx.x[i+(s/8)] = x.x[i];
508 /* shift (logically) left by remaining s%8 bits */
509 s %= 8;
510 if (s > 0) {
511 carry = 0;
512 for (i = 0; i < UI128_DIGITS+UI128_DIGITS; i++) {
513 carry += (zx.x[i] * (1 << s));
514 zx.x[i] = (carry % UI128_BASE);
515 carry /= UI128_BASE;
516 }
517 }
518 memcpy(z.x, zx.x, UI128_DIGITS);
519 if (ov != NULL)
520 memcpy((*ov).x, &zx.x[UI128_DIGITS], UI128_DIGITS);
521 }
522 return z;
523 }
524
ui128_ror(ui128_t x,int s,ui128_t * ov)525 ui128_t ui128_ror(ui128_t x, int s, ui128_t *ov)
526 {
527 UIXX_T(UI128_DIGITS+UI128_DIGITS) zx;
528 ui128_t z;
529 int i;
530 int carry;
531
532 if (s <= 0) {
533 /* no shift at all */
534 if (ov != NULL)
535 *ov = ui128_zero();
536 return x;
537 }
538 else if (s > 128) {
539 /* too large shift */
540 if (ov != NULL)
541 *ov = ui128_zero();
542 return ui128_zero();
543 }
544 else if (s == 128) {
545 /* maximum shift */
546 if (ov != NULL)
547 *ov = x;
548 return ui128_zero();
549 }
550 else { /* regular shift */
551 /* shift (logically) right by s/8 bytes */
552 for (i = 0; i < UI128_DIGITS+UI128_DIGITS; i++)
553 zx.x[i] = 0;
554 for (i = 0; i < UI128_DIGITS; i++)
555 zx.x[UI128_DIGITS+i-(s/8)] = x.x[i];
556 /* shift (logically) right by remaining s%8 bits */
557 s %= 8;
558 if (s > 0) {
559 carry = 0;
560 for (i = (UI128_DIGITS+UI128_DIGITS - 1); i >= 0; i--) {
561 carry = (carry * UI128_BASE) + zx.x[i];
562 zx.x[i] = (carry / (1 << s));
563 carry %= (1 << s);
564 }
565 }
566 memcpy(z.x, &zx.x[UI128_DIGITS], UI128_DIGITS);
567 if (ov != NULL)
568 memcpy((*ov).x, zx.x, UI128_DIGITS);
569 }
570 return z;
571 }
572
ui128_cmp(ui128_t x,ui128_t y)573 int ui128_cmp(ui128_t x, ui128_t y)
574 {
575 int i;
576
577 i = UI128_DIGITS - 1;
578 while (i > 0 && x.x[i] == y.x[i])
579 i--;
580 return (x.x[i] - y.x[i]);
581 }
582
ui128_len(ui128_t x)583 int ui128_len(ui128_t x)
584 {
585 int i;
586
587 for (i = UI128_DIGITS; i > 1 && x.x[i-1] == 0; i--)
588 ;
589 return i;
590 }
591
592