1 /* 128 bit integer arithmetic.
2 *
3 * Not optimized for speed.
4 *
5 * Copyright: Copyright D Language Foundation 2022.
6 * License: $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost License 1.0)
7 * Authors: Walter Bright
8 * Source: $(DRUNTIMESRC core/_int128.d)
9 */
10
11 module core.int128;
12
13 nothrow:
14 @safe:
15 @nogc:
16
17 alias I = long;
18 alias U = ulong;
19 enum Ubits = uint(U.sizeof * 8);
20
21 version (X86_64) private enum Cent_alignment = 16;
22 else private enum Cent_alignment = (size_t.sizeof * 2);
23
24 align(Cent_alignment) struct Cent
25 {
versionCent26 version (LittleEndian)
27 {
28 U lo; // low 64 bits
29 U hi; // high 64 bits
30 }
31 else
32 {
33 U hi; // high 64 bits
34 U lo; // low 64 bits
35 }
36 }
37
38 enum Cent One = { lo:1 };
39 enum Cent Zero = { lo:0 };
40 enum Cent MinusOne = neg(One);
41
42 /*****************************
43 * Test against 0
44 * Params:
45 * c = Cent to test
46 * Returns:
47 * true if != 0
48 */
49 pure
tst(Cent c)50 bool tst(Cent c)
51 {
52 return c.hi || c.lo;
53 }
54
55
56 /*****************************
57 * Complement
58 * Params:
59 * c = Cent to complement
60 * Returns:
61 * complemented value
62 */
63 pure
com(Cent c)64 Cent com(Cent c)
65 {
66 c.lo = ~c.lo;
67 c.hi = ~c.hi;
68 return c;
69 }
70
71 /*****************************
72 * Negate
73 * Params:
74 * c = Cent to negate
75 * Returns:
76 * negated value
77 */
78 pure
neg(Cent c)79 Cent neg(Cent c)
80 {
81 if (c.lo == 0)
82 c.hi = -c.hi;
83 else
84 {
85 c.lo = -c.lo;
86 c.hi = ~c.hi;
87 }
88 return c;
89 }
90
91 /*****************************
92 * Increment
93 * Params:
94 * c = Cent to increment
95 * Returns:
96 * incremented value
97 */
98 pure
inc(Cent c)99 Cent inc(Cent c)
100 {
101 return add(c, One);
102 }
103
104 /*****************************
105 * Decrement
106 * Params:
107 * c = Cent to decrement
108 * Returns:
109 * incremented value
110 */
111 pure
dec(Cent c)112 Cent dec(Cent c)
113 {
114 return sub(c, One);
115 }
116
117 /*****************************
118 * Shift left one bit
119 * Params:
120 * c = Cent to shift
121 * Returns:
122 * shifted value
123 */
124 pure
shl1(Cent c)125 Cent shl1(Cent c)
126 {
127 c.hi = (c.hi << 1) | (cast(I)c.lo < 0);
128 c.lo <<= 1;
129 return c;
130 }
131
132 /*****************************
133 * Unsigned shift right one bit
134 * Params:
135 * c = Cent to shift
136 * Returns:
137 * shifted value
138 */
139 pure
shr1(Cent c)140 Cent shr1(Cent c)
141 {
142 c.lo = (c.lo >> 1) | ((c.hi & 1) << (Ubits - 1));
143 c.hi >>= 1;
144 return c;
145 }
146
147
148 /*****************************
149 * Arithmetic shift right one bit
150 * Params:
151 * c = Cent to shift
152 * Returns:
153 * shifted value
154 */
155 pure
sar1(Cent c)156 Cent sar1(Cent c)
157 {
158 c.lo = (c.lo >> 1) | ((c.hi & 1) << (Ubits - 1));
159 c.hi = cast(I)c.hi >> 1;
160 return c;
161 }
162
163 /*****************************
164 * Shift left n bits
165 * Params:
166 * c = Cent to shift
167 * n = number of bits to shift
168 * Returns:
169 * shifted value
170 */
171 pure
shl(Cent c,uint n)172 Cent shl(Cent c, uint n)
173 {
174 if (n >= Ubits * 2)
175 return Zero;
176
177 if (n >= Ubits)
178 {
179 c.hi = c.lo << (n - Ubits);
180 c.lo = 0;
181 }
182 else
183 {
184 c.hi = ((c.hi << n) | (c.lo >> (Ubits - n - 1) >> 1));
185 c.lo = c.lo << n;
186 }
187 return c;
188 }
189
190 /*****************************
191 * Unsigned shift right n bits
192 * Params:
193 * c = Cent to shift
194 * n = number of bits to shift
195 * Returns:
196 * shifted value
197 */
198 pure
shr(Cent c,uint n)199 Cent shr(Cent c, uint n)
200 {
201 if (n >= Ubits * 2)
202 return Zero;
203
204 if (n >= Ubits)
205 {
206 c.lo = c.hi >> (n - Ubits);
207 c.hi = 0;
208 }
209 else
210 {
211 c.lo = ((c.lo >> n) | (c.hi << (Ubits - n - 1) << 1));
212 c.hi = c.hi >> n;
213 }
214 return c;
215 }
216
217 /*****************************
218 * Arithmetic shift right n bits
219 * Params:
220 * c = Cent to shift
221 * n = number of bits to shift
222 * Returns:
223 * shifted value
224 */
225 pure
sar(Cent c,uint n)226 Cent sar(Cent c, uint n)
227 {
228 const signmask = -(c.hi >> (Ubits - 1));
229 const signshift = (Ubits * 2) - n;
230 c = shr(c, n);
231
232 // Sign extend all bits beyond the precision of Cent.
233 if (n >= Ubits * 2)
234 {
235 c.hi = signmask;
236 c.lo = signmask;
237 }
238 else if (signshift >= Ubits * 2)
239 {
240 }
241 else if (signshift >= Ubits)
242 {
243 c.hi &= ~(U.max << (signshift - Ubits));
244 c.hi |= signmask << (signshift - Ubits);
245 }
246 else
247 {
248 c.hi = signmask;
249 c.lo &= ~(U.max << signshift);
250 c.lo |= signmask << signshift;
251 }
252 return c;
253 }
254
255 /*****************************
256 * Rotate left one bit
257 * Params:
258 * c = Cent to rotate
259 * Returns:
260 * rotated value
261 */
262 pure
rol1(Cent c)263 Cent rol1(Cent c)
264 {
265 int carry = cast(I)c.hi < 0;
266
267 c.hi = (c.hi << 1) | (cast(I)c.lo < 0);
268 c.lo = (c.lo << 1) | carry;
269 return c;
270 }
271
272 /*****************************
273 * Rotate right one bit
274 * Params:
275 * c = Cent to rotate
276 * Returns:
277 * rotated value
278 */
279 pure
ror1(Cent c)280 Cent ror1(Cent c)
281 {
282 int carry = c.lo & 1;
283 c.lo = (c.lo >> 1) | (cast(U)(c.hi & 1) << (Ubits - 1));
284 c.hi = (c.hi >> 1) | (cast(U)carry << (Ubits - 1));
285 return c;
286 }
287
288
289 /*****************************
290 * Rotate left n bits
291 * Params:
292 * c = Cent to rotate
293 * n = number of bits to rotate
294 * Returns:
295 * rotated value
296 */
297 pure
rol(Cent c,uint n)298 Cent rol(Cent c, uint n)
299 {
300 n &= Ubits * 2 - 1;
301 Cent l = shl(c, n);
302 Cent r = shr(c, Ubits * 2 - n);
303 return or(l, r);
304 }
305
306 /*****************************
307 * Rotate right n bits
308 * Params:
309 * c = Cent to rotate
310 * n = number of bits to rotate
311 * Returns:
312 * rotated value
313 */
314 pure
ror(Cent c,uint n)315 Cent ror(Cent c, uint n)
316 {
317 n &= Ubits * 2 - 1;
318 Cent r = shr(c, n);
319 Cent l = shl(c, Ubits * 2 - n);
320 return or(r, l);
321 }
322
323 /****************************
324 * And c1 & c2.
325 * Params:
326 * c1 = operand 1
327 * c2 = operand 2
328 * Returns:
329 * c1 & c2
330 */
331 pure
and(Cent c1,Cent c2)332 Cent and(Cent c1, Cent c2)
333 {
334 const Cent ret = { lo:c1.lo & c2.lo, hi:c1.hi & c2.hi };
335 return ret;
336 }
337
338 /****************************
339 * Or c1 | c2.
340 * Params:
341 * c1 = operand 1
342 * c2 = operand 2
343 * Returns:
344 * c1 | c2
345 */
346 pure
or(Cent c1,Cent c2)347 Cent or(Cent c1, Cent c2)
348 {
349 const Cent ret = { lo:c1.lo | c2.lo, hi:c1.hi | c2.hi };
350 return ret;
351 }
352
353 /****************************
354 * Xor c1 ^ c2.
355 * Params:
356 * c1 = operand 1
357 * c2 = operand 2
358 * Returns:
359 * c1 ^ c2
360 */
361 pure
xor(Cent c1,Cent c2)362 Cent xor(Cent c1, Cent c2)
363 {
364 const Cent ret = { lo:c1.lo ^ c2.lo, hi:c1.hi ^ c2.hi };
365 return ret;
366 }
367
368 /****************************
369 * Add c1 to c2.
370 * Params:
371 * c1 = operand 1
372 * c2 = operand 2
373 * Returns:
374 * c1 + c2
375 */
376 pure
add(Cent c1,Cent c2)377 Cent add(Cent c1, Cent c2)
378 {
379 U r = cast(U)(c1.lo + c2.lo);
380 const Cent ret = { lo:r, hi:cast(U)(c1.hi + c2.hi + (r < c1.lo)) };
381 return ret;
382 }
383
384 /****************************
385 * Subtract c2 from c1.
386 * Params:
387 * c1 = operand 1
388 * c2 = operand 2
389 * Returns:
390 * c1 - c2
391 */
392 pure
sub(Cent c1,Cent c2)393 Cent sub(Cent c1, Cent c2)
394 {
395 return add(c1, neg(c2));
396 }
397
398 /****************************
399 * Multiply c1 * c2.
400 * Params:
401 * c1 = operand 1
402 * c2 = operand 2
403 * Returns:
404 * c1 * c2
405 */
406 pure
mul(Cent c1,Cent c2)407 Cent mul(Cent c1, Cent c2)
408 {
409 enum mulmask = (1UL << (Ubits / 2)) - 1;
410 enum mulshift = Ubits / 2;
411
412 // This algorithm splits the operands into 4 words, then computes and sums
413 // the partial products of each part.
414 const c2l0 = c2.lo & mulmask;
415 const c2l1 = c2.lo >> mulshift;
416 const c2h0 = c2.hi & mulmask;
417 const c2h1 = c2.hi >> mulshift;
418
419 const c1l0 = c1.lo & mulmask;
420 U r0 = c1l0 * c2l0;
421 U r1 = c1l0 * c2l1 + (r0 >> mulshift);
422 U r2 = c1l0 * c2h0 + (r1 >> mulshift);
423 U r3 = c1l0 * c2h1 + (r2 >> mulshift);
424
425 const c1l1 = c1.lo >> mulshift;
426 r1 = c1l1 * c2l0 + (r1 & mulmask);
427 r2 = c1l1 * c2l1 + (r2 & mulmask) + (r1 >> mulshift);
428 r3 = c1l1 * c2h0 + (r3 & mulmask) + (r2 >> mulshift);
429
430 const c1h0 = c1.hi & mulmask;
431 r2 = c1h0 * c2l0 + (r2 & mulmask);
432 r3 = c1h0 * c2l1 + (r3 & mulmask) + (r2 >> mulshift);
433
434 const c1h1 = c1.hi >> mulshift;
435 r3 = c1h1 * c2l0 + (r3 & mulmask);
436
437 const Cent ret = { lo:(r0 & mulmask) + (r1 & mulmask) * (mulmask + 1),
438 hi:(r2 & mulmask) + (r3 & mulmask) * (mulmask + 1) };
439 return ret;
440 }
441
442
443 /****************************
444 * Unsigned divide c1 / c2.
445 * Params:
446 * c1 = dividend
447 * c2 = divisor
448 * Returns:
449 * quotient c1 / c2
450 */
451 pure
udiv(Cent c1,Cent c2)452 Cent udiv(Cent c1, Cent c2)
453 {
454 Cent modulus;
455 return udivmod(c1, c2, modulus);
456 }
457
458 /****************************
459 * Unsigned divide c1 / c2. The remainder after division is stored to modulus.
460 * Params:
461 * c1 = dividend
462 * c2 = divisor
463 * modulus = set to c1 % c2
464 * Returns:
465 * quotient c1 / c2
466 */
467 pure
udivmod(Cent c1,Cent c2,out Cent modulus)468 Cent udivmod(Cent c1, Cent c2, out Cent modulus)
469 {
470 //printf("udiv c1(%llx,%llx) c2(%llx,%llx)\n", c1.lo, c1.hi, c2.lo, c2.hi);
471 // Based on "Unsigned Doubleword Division" in Hacker's Delight
472 import core.bitop;
473
474 // Divides a 128-bit dividend by a 64-bit divisor.
475 // The result must fit in 64 bits.
476 static U udivmod128_64(Cent c1, U c2, out U modulus)
477 {
478 // We work in base 2^^32
479 enum base = 1UL << 32;
480 enum divmask = (1UL << (Ubits / 2)) - 1;
481 enum divshift = Ubits / 2;
482
483 // Check for overflow and divide by 0
484 if (c1.hi >= c2)
485 {
486 modulus = 0UL;
487 return ~0UL;
488 }
489
490 // Computes [num1 num0] / den
491 static uint udiv96_64(U num1, uint num0, U den)
492 {
493 // Extract both digits of the denominator
494 const den1 = cast(uint)(den >> divshift);
495 const den0 = cast(uint)(den & divmask);
496 // Estimate ret as num1 / den1, and then correct it
497 U ret = num1 / den1;
498 const t2 = (num1 % den1) * base + num0;
499 const t1 = ret * den0;
500 if (t1 > t2)
501 ret -= (t1 - t2 > den) ? 2 : 1;
502 return cast(uint)ret;
503 }
504
505 // Determine the normalization factor. We multiply c2 by this, so that its leading
506 // digit is at least half base. In binary this means just shifting left by the number
507 // of leading zeros, so that there's a 1 in the MSB.
508 // We also shift number by the same amount. This cannot overflow because c1.hi < c2.
509 const shift = (Ubits - 1) - bsr(c2);
510 c2 <<= shift;
511 U num2 = c1.hi;
512 num2 <<= shift;
513 num2 |= (c1.lo >> (-shift & 63)) & (-cast(I)shift >> 63);
514 c1.lo <<= shift;
515
516 // Extract the low digits of the numerator (after normalizing)
517 const num1 = cast(uint)(c1.lo >> divshift);
518 const num0 = cast(uint)(c1.lo & divmask);
519
520 // Compute q1 = [num2 num1] / c2
521 const q1 = udiv96_64(num2, num1, c2);
522 // Compute the true (partial) remainder
523 const rem = num2 * base + num1 - q1 * c2;
524 // Compute q0 = [rem num0] / c2
525 const q0 = udiv96_64(rem, num0, c2);
526
527 modulus = (rem * base + num0 - q0 * c2) >> shift;
528 return (cast(U)q1 << divshift) | q0;
529 }
530
531 // Special cases
532 if (!tst(c2))
533 {
534 // Divide by zero
535 modulus = Zero;
536 return com(modulus);
537 }
538 if (c1.hi == 0 && c2.hi == 0)
539 {
540 // Single precision divide
541 const Cent rem = { lo:c1.lo % c2.lo };
542 modulus = rem;
543 const Cent ret = { lo:c1.lo / c2.lo };
544 return ret;
545 }
546 if (c1.hi == 0)
547 {
548 // Numerator is smaller than the divisor
549 modulus = c1;
550 return Zero;
551 }
552 if (c2.hi == 0)
553 {
554 // Divisor is a 64-bit value, so we just need one 128/64 division.
555 // If c1 / c2 would overflow, break c1 up into two halves.
556 const q1 = (c1.hi < c2.lo) ? 0 : (c1.hi / c2.lo);
557 if (q1)
558 c1.hi = c1.hi % c2.lo;
559 Cent rem;
560 const q0 = udivmod128_64(c1, c2.lo, rem.lo);
561 modulus = rem;
562 const Cent ret = { lo:q0, hi:q1 };
563 return ret;
564 }
565
566 // Full cent precision division.
567 // Here c2 >= 2^^64
568 // We know that c2.hi != 0, so count leading zeros is OK
569 // We have 0 <= shift <= 63
570 const shift = (Ubits - 1) - bsr(c2.hi);
571
572 // Normalize the divisor so its MSB is 1
573 // v1 = (c2 << shift) >> 64
574 U v1 = shl(c2, shift).hi;
575
576 // To ensure no overflow.
577 Cent u1 = shr1(c1);
578
579 // Get quotient from divide unsigned operation.
580 U rem_ignored;
581 const Cent q1 = { lo:udivmod128_64(u1, v1, rem_ignored) };
582
583 // Undo normalization and division of c1 by 2.
584 Cent quotient = shr(shl(q1, shift), 63);
585
586 // Make quotient correct or too small by 1
587 if (tst(quotient))
588 quotient = dec(quotient);
589
590 // Now quotient is correct.
591 // Compute rem = c1 - (quotient * c2);
592 Cent rem = sub(c1, mul(quotient, c2));
593
594 // Check if remainder is larger than the divisor
595 if (uge(rem, c2))
596 {
597 // Increment quotient
598 quotient = inc(quotient);
599 // Subtract c2 from remainder
600 rem = sub(rem, c2);
601 }
602 modulus = rem;
603 //printf("quotient "); print(quotient);
604 //printf("modulus "); print(modulus);
605 return quotient;
606 }
607
608
609 /****************************
610 * Signed divide c1 / c2.
611 * Params:
612 * c1 = dividend
613 * c2 = divisor
614 * Returns:
615 * quotient c1 / c2
616 */
617 pure
div(Cent c1,Cent c2)618 Cent div(Cent c1, Cent c2)
619 {
620 Cent modulus;
621 return divmod(c1, c2, modulus);
622 }
623
624 /****************************
625 * Signed divide c1 / c2. The remainder after division is stored to modulus.
626 * Params:
627 * c1 = dividend
628 * c2 = divisor
629 * modulus = set to c1 % c2
630 * Returns:
631 * quotient c1 / c2
632 */
633 pure
divmod(Cent c1,Cent c2,out Cent modulus)634 Cent divmod(Cent c1, Cent c2, out Cent modulus)
635 {
636 /* Muck about with the signs so we can use the unsigned divide
637 */
638 if (cast(I)c1.hi < 0)
639 {
640 if (cast(I)c2.hi < 0)
641 {
642 Cent r = udivmod(neg(c1), neg(c2), modulus);
643 modulus = neg(modulus);
644 return r;
645 }
646 Cent r = neg(udivmod(neg(c1), c2, modulus));
647 modulus = neg(modulus);
648 return r;
649 }
650 else if (cast(I)c2.hi < 0)
651 {
652 return neg(udivmod(c1, neg(c2), modulus));
653 }
654 else
655 return udivmod(c1, c2, modulus);
656 }
657
658 /****************************
659 * If c1 > c2 unsigned
660 * Params:
661 * c1 = operand 1
662 * c2 = operand 2
663 * Returns:
664 * true if c1 > c2
665 */
666 pure
ugt(Cent c1,Cent c2)667 bool ugt(Cent c1, Cent c2)
668 {
669 return (c1.hi == c2.hi) ? (c1.lo > c2.lo) : (c1.hi > c2.hi);
670 }
671
672 /****************************
673 * If c1 >= c2 unsigned
674 * Params:
675 * c1 = operand 1
676 * c2 = operand 2
677 * Returns:
678 * true if c1 >= c2
679 */
680 pure
uge(Cent c1,Cent c2)681 bool uge(Cent c1, Cent c2)
682 {
683 return !ugt(c2, c1);
684 }
685
686 /****************************
687 * If c1 < c2 unsigned
688 * Params:
689 * c1 = operand 1
690 * c2 = operand 2
691 * Returns:
692 * true if c1 < c2
693 */
694 pure
ult(Cent c1,Cent c2)695 bool ult(Cent c1, Cent c2)
696 {
697 return ugt(c2, c1);
698 }
699
700 /****************************
701 * If c1 <= c2 unsigned
702 * Params:
703 * c1 = operand 1
704 * c2 = operand 2
705 * Returns:
706 * true if c1 <= c2
707 */
708 pure
ule(Cent c1,Cent c2)709 bool ule(Cent c1, Cent c2)
710 {
711 return !ugt(c1, c2);
712 }
713
714 /****************************
715 * If c1 > c2 signed
716 * Params:
717 * c1 = operand 1
718 * c2 = operand 2
719 * Returns:
720 * true if c1 > c2
721 */
722 pure
gt(Cent c1,Cent c2)723 bool gt(Cent c1, Cent c2)
724 {
725 return (c1.hi == c2.hi)
726 ? (c1.lo > c2.lo)
727 : (cast(I)c1.hi > cast(I)c2.hi);
728 }
729
730 /****************************
731 * If c1 >= c2 signed
732 * Params:
733 * c1 = operand 1
734 * c2 = operand 2
735 * Returns:
736 * true if c1 >= c2
737 */
738 pure
ge(Cent c1,Cent c2)739 bool ge(Cent c1, Cent c2)
740 {
741 return !gt(c2, c1);
742 }
743
744 /****************************
745 * If c1 < c2 signed
746 * Params:
747 * c1 = operand 1
748 * c2 = operand 2
749 * Returns:
750 * true if c1 < c2
751 */
752 pure
lt(Cent c1,Cent c2)753 bool lt(Cent c1, Cent c2)
754 {
755 return gt(c2, c1);
756 }
757
758 /****************************
759 * If c1 <= c2 signed
760 * Params:
761 * c1 = operand 1
762 * c2 = operand 2
763 * Returns:
764 * true if c1 <= c2
765 */
766 pure
le(Cent c1,Cent c2)767 bool le(Cent c1, Cent c2)
768 {
769 return !gt(c1, c2);
770 }
771
772 /*******************************************************/
773
version(unittest)774 version (unittest)
775 {
776 version (none)
777 {
778 import core.stdc.stdio;
779
780 @trusted
781 void print(Cent c)
782 {
783 printf("%lld, %lld\n", cast(ulong)c.lo, cast(ulong)c.hi);
784 printf("x%llx, x%llx\n", cast(ulong)c.lo, cast(ulong)c.hi);
785 }
786 }
787 }
788
789 unittest
790 {
791 const Cent C0 = Zero;
792 const Cent C1 = One;
793 const Cent C2 = { lo:2 };
794 const Cent C3 = { lo:3 };
795 const Cent C5 = { lo:5 };
796 const Cent C10 = { lo:10 };
797 const Cent C20 = { lo:20 };
798 const Cent C30 = { lo:30 };
799 const Cent C100 = { lo:100 };
800
801 const Cent Cm1 = neg(One);
802 const Cent Cm3 = neg(C3);
803 const Cent Cm10 = neg(C10);
804
805 const Cent C3_1 = { lo:1, hi:3 };
806 const Cent C3_2 = { lo:2, hi:3 };
807 const Cent C4_8 = { lo:8, hi:4 };
808 const Cent C5_0 = { lo:0, hi:5 };
809 const Cent C7_1 = { lo:1, hi:7 };
810 const Cent C7_9 = { lo:9, hi:7 };
811 const Cent C9_3 = { lo:3, hi:9 };
812 const Cent C10_0 = { lo:0, hi:10 };
813 const Cent C10_1 = { lo:1, hi:10 };
814 const Cent C10_3 = { lo:3, hi:10 };
815 const Cent C11_3 = { lo:3, hi:11 };
816 const Cent C20_0 = { lo:0, hi:20 };
817 const Cent C90_30 = { lo:30, hi:90 };
818
819 const Cent Cm10_0 = inc(com(C10_0)); // Cent(lo=0, hi=-10);
820 const Cent Cm10_1 = inc(com(C10_1)); // Cent(lo=-1, hi=-11);
821 const Cent Cm10_3 = inc(com(C10_3)); // Cent(lo=-3, hi=-11);
822 const Cent Cm20_0 = inc(com(C20_0)); // Cent(lo=0, hi=-20);
823
824 enum Cent Cs_3 = { lo:3, hi:I.min };
825
826 const Cent Cbig_1 = { lo:0xa3ccac1832952398, hi:0xc3ac542864f652f8 };
827 const Cent Cbig_2 = { lo:0x5267b85f8a42fc20, hi:0 };
828 const Cent Cbig_3 = { lo:0xf0000000ffffffff, hi:0 };
829
830 /************************/
831
832 assert( ugt(C1, C0) );
833 assert( ult(C1, C2) );
834 assert( uge(C1, C0) );
835 assert( ule(C1, C2) );
836
837 assert( !ugt(C0, C1) );
838 assert( !ult(C2, C1) );
839 assert( !uge(C0, C1) );
840 assert( !ule(C2, C1) );
841
842 assert( !ugt(C1, C1) );
843 assert( !ult(C1, C1) );
844 assert( uge(C1, C1) );
845 assert( ule(C2, C2) );
846
847 assert( ugt(C10_3, C10_1) );
848 assert( ugt(C11_3, C10_3) );
849 assert( !ugt(C9_3, C10_3) );
850 assert( !ugt(C9_3, C9_3) );
851
852 assert( gt(C2, C1) );
853 assert( !gt(C1, C2) );
854 assert( !gt(C1, C1) );
855 assert( gt(C0, Cm1) );
856 assert( gt(Cm1, neg(C10)));
857 assert( !gt(Cm1, Cm1) );
858 assert( !gt(Cm1, C0) );
859
860 assert( !lt(C2, C1) );
861 assert( !le(C2, C1) );
862 assert( ge(C2, C1) );
863
864 assert(neg(C10_0) == Cm10_0);
865 assert(neg(C10_1) == Cm10_1);
866 assert(neg(C10_3) == Cm10_3);
867
868 assert(add(C7_1,C3_2) == C10_3);
869 assert(sub(C1,C2) == Cm1);
870
871 assert(inc(C3_1) == C3_2);
872 assert(dec(C3_2) == C3_1);
873
874 assert(shl(C10,0) == C10);
875 assert(shl(C10,Ubits) == C10_0);
876 assert(shl(C10,1) == C20);
877 assert(shl(C10,Ubits * 2) == C0);
878 assert(shr(C10_0,0) == C10_0);
879 assert(shr(C10_0,Ubits) == C10);
880 assert(shr(C10_0,Ubits - 1) == C20);
881 assert(shr(C10_0,Ubits + 1) == C5);
882 assert(shr(C10_0,Ubits * 2) == C0);
883 assert(sar(C10_0,0) == C10_0);
884 assert(sar(C10_0,Ubits) == C10);
885 assert(sar(C10_0,Ubits - 1) == C20);
886 assert(sar(C10_0,Ubits + 1) == C5);
887 assert(sar(C10_0,Ubits * 2) == C0);
888 assert(sar(Cm1,Ubits * 2) == Cm1);
889
890 assert(shl1(C10) == C20);
891 assert(shr1(C10_0) == C5_0);
892 assert(sar1(C10_0) == C5_0);
893 assert(sar1(Cm1) == Cm1);
894
895 Cent modulus;
896
897 assert(udiv(C10,C2) == C5);
898 assert(udivmod(C10,C2, modulus) == C5); assert(modulus == C0);
899 assert(udivmod(C10,C3, modulus) == C3); assert(modulus == C1);
900 assert(udivmod(C10,C0, modulus) == Cm1); assert(modulus == C0);
901 assert(udivmod(C2,C90_30, modulus) == C0); assert(modulus == C2);
902 assert(udiv(mul(C90_30, C2), C2) == C90_30);
903 assert(udiv(mul(C90_30, C2), C90_30) == C2);
904
905 assert(div(C10,C3) == C3);
906 assert(divmod( C10, C3, modulus) == C3); assert(modulus == C1);
907 assert(divmod(Cm10, C3, modulus) == Cm3); assert(modulus == Cm1);
908 assert(divmod( C10, Cm3, modulus) == Cm3); assert(modulus == C1);
909 assert(divmod(Cm10, Cm3, modulus) == C3); assert(modulus == Cm1);
910 assert(divmod(C2, C90_30, modulus) == C0); assert(modulus == C2);
911 assert(div(mul(C90_30, C2), C2) == C90_30);
912 assert(div(mul(C90_30, C2), C90_30) == C2);
913
914 const Cent Cb1divb2 = { lo:0x4496aa309d4d4a2f, hi:U.max };
915 const Cent Cb1modb2 = { lo:0xd83203d0fdc799b8, hi:U.max };
916 assert(divmod(Cbig_1, Cbig_2, modulus) == Cb1divb2);
917 assert(modulus == Cb1modb2);
918
919 const Cent Cb1udivb2 = { lo:0x5fe0e9bace2bedad, hi:2 };
920 const Cent Cb1umodb2 = { lo:0x2c923125a68721f8, hi:0 };
921 assert(udivmod(Cbig_1, Cbig_2, modulus) == Cb1udivb2);
922 assert(modulus == Cb1umodb2);
923
924 const Cent Cb1divb3 = { lo:0xbfa6c02b5aff8b86, hi:U.max };
925 const Cent Cb1udivb3 = { lo:0xd0b7d13b48cb350f, hi:0 };
926 assert(div(Cbig_1, Cbig_3) == Cb1divb3);
927 assert(udiv(Cbig_1, Cbig_3) == Cb1udivb3);
928
929 assert(mul(Cm10, C1) == Cm10);
930 assert(mul(C1, Cm10) == Cm10);
931 assert(mul(C9_3, C10) == C90_30);
932 assert(mul(Cs_3, C10) == C30);
933 assert(mul(Cm10, Cm10) == C100);
934 assert(mul(C20_0, Cm1) == Cm20_0);
935
936 assert( or(C4_8, C3_1) == C7_9);
937 assert(and(C4_8, C7_9) == C4_8);
938 assert(xor(C4_8, C7_9) == C3_1);
939
940 assert(rol(Cm1, 1) == Cm1);
941 assert(ror(Cm1, 45) == Cm1);
942 assert(rol(ror(C7_9, 5), 5) == C7_9);
943 assert(rol(C7_9, 1) == rol1(C7_9));
944 assert(ror(C7_9, 1) == ror1(C7_9));
945 }
946
947
948