1 // Digit sequence arithmetic
7 #include "cl_gmpconfig.h"
9 #include "cl_DS_endian.h"
10 #include "cl_alloca.h"
14 // Digit Sequence (DS)
15 // a memory range with n digits (n an uintC),
16 // between two pointers MSDptr and LSDptr.
17 #if CL_DS_BIG_ENDIAN_P
18 // MSDptr LSDptr = MSDptr+n
19 // | MSD ............. LSD |
20 // [short: MSDptr/n/LSDptr ]
21 // In C: uintD* MSDptr, uintC len, MSDptr[0] ... MSDptr[len-1] are the digits.
23 // LSDptr MSDptr = LSDptr+n
24 // | LSD ............. MSD |
25 // In C: uintD* LSDptr, uintC len, LSDptr[0] ... LSDptr[len-1] are the digits.
27 // If n = 0, this represents the number 0.
28 // If n > 0, the most significant bit (i.e. bit (intDsize-1) of
29 // MSDptr[CL_DS_BIG_ENDIAN_P?0:-1]) is the sign bit. If the sign
30 // bit were repeated infinitely often, one would get an
31 // "infinite bit sequence".
33 // A Normalised Digit Sequence (NDS) is one for which the MSD is necessary,
34 // i.e. n = 0 or (n > 0 and the most significant intDsize+1 bits are not
37 // Unsigned Digit Sequence (UDS)
38 // like DS, but without sign.
40 // Normalized Unsigned Digit Sequence (NUDS):
41 // an UDS for which the MSD is necessary, i.e. n = 0 or
42 // (n > 0 and the most significant intDsize bits are not all zero).
44 // For the construction of constant DS, using "digit_header":
45 #define D1(byte0) (uintD)(byte0)
46 #define D2(byte0,byte1) (((uintD)(byte0)<<8)|(uintD)(byte1))
47 #define D4(byte0,byte1,byte2,byte3) (((uintD)(byte0)<<24)|((uintD)(byte1)<<16)|((uintD)(byte2)<<8)|((uintD)(byte3)))
48 #define D8(byte0,byte1,byte2,byte3,byte4,byte5,byte6,byte7) (((uintD)(byte0)<<56)|((uintD)(byte1)<<48)|((uintD)(byte2)<<40)|((uintD)(byte3)<<32)|((uintD)(byte4)<<24)|((uintD)(byte5)<<16)|((uintD)(byte6)<<8)|((uintD)(byte7)))
56 // Endianness independent access of digit sequences:
57 // mspref(MSDptr,i) access a most significant digit
58 // lspref(LSDptr,i) access a least significant digit
59 // msshrink(MSDptr) shrinks the DS by throwing away the MSD
60 // msprefnext(MSDptr) combines mspref(MSDptr,0) and msshrink(MSDptr)
61 // lsshrink(LSDptr) shrinks the DS by throwing away the LSD
62 // lsprefnext(LSDptr) combines lspref(LSDptr,0) and lsshrink(LSDptr)
63 // mspop pointer operator corresponding to msshrink, arg is widened to an uintP
64 // lspop pointer operator corresponding to lsshrink, arg is widened to an uintP
65 #if CL_DS_BIG_ENDIAN_P
66 #define mspref(p,i) (p)[i]
67 #define lspref(p,i) (p)[-(uintP)(i)-1]
68 #define msshrink(p) (p)++
69 #define msprefnext(p) (*(p)++)
70 #define lsshrink(p) (p)--
71 #define lsprefnext(p) (*--(p))
75 #define mspref(p,i) (p)[-(uintP)(i)-1]
76 #define lspref(p,i) (p)[i]
77 #define msshrink(p) (p)--
78 #define msprefnext(p) (*--(p))
79 #define lsshrink(p) (p)++
80 #define lsprefnext(p) (*(p)++)
85 // Endianness independent macros for turning an array into a digit sequence.
86 // arrayMSDptr(array,length) returns the MSDptr of array[0..length-1]
87 // arrayLSDptr(array,length) returns the LSDptr of array[0..length-1]
88 #if CL_DS_BIG_ENDIAN_P
89 #define arrayMSDptr(array,length) &(array)[0]
90 #define arrayLSDptr(array,length) &(array)[length]
92 #define arrayMSDptr(array,length) &(array)[length]
93 #define arrayLSDptr(array,length) &(array)[0]
95 #define arrayLSref(array,length,i) lspref(arrayLSDptr(array,length),i)
98 // These functions on digit sequences are either inline C++ functions
99 // or external assembler functions (see files cl_asm_*).
102 // See which functions are defined as external functions.
106 // Declare the external functions.
112 extern uintD* copy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count);
114 extern uintD* copy_loop_down (const uintD* sourceptr, uintD* destptr, uintC count);
120 extern uintD* fill_loop_up (uintD* destptr, uintC count, uintD filler);
122 extern uintD* fill_loop_down (uintD* destptr, uintC count, uintD filler);
128 extern uintD* clear_loop_up (uintD* destptr, uintC count);
130 extern uintD* clear_loop_down (uintD* destptr, uintC count);
136 extern cl_boolean test_loop_up (const uintD* ptr, uintC count);
138 extern cl_boolean test_loop_down (const uintD* ptr, uintC count);
142 #if CL_DS_BIG_ENDIAN_P
146 extern void or_loop_up (uintD* xptr, const uintD* yptr, uintC count);
148 extern void xor_loop_up (uintD* xptr, const uintD* yptr, uintC count);
150 extern void and_loop_up (uintD* xptr, const uintD* yptr, uintC count);
152 extern void eqv_loop_up (uintD* xptr, const uintD* yptr, uintC count);
154 extern void nand_loop_up (uintD* xptr, const uintD* yptr, uintC count);
156 extern void nor_loop_up (uintD* xptr, const uintD* yptr, uintC count);
158 extern void andc2_loop_up (uintD* xptr, const uintD* yptr, uintC count);
160 extern void orc2_loop_up (uintD* xptr, const uintD* yptr, uintC count);
162 extern void not_loop_up (uintD* xptr, uintC count);
168 extern cl_boolean and_test_loop_up (const uintD* xptr, const uintD* yptr, uintC count);
170 extern cl_signean compare_loop_up (const uintD* xptr, const uintD* yptr, uintC count);
176 extern uintD add_loop_down (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count);
178 extern uintD addto_loop_down (const uintD* sourceptr, uintD* destptr, uintC count);
180 extern uintD inc_loop_down (uintD* ptr, uintC count);
182 extern uintD sub_loop_down (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count);
184 extern uintD subx_loop_down (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count, uintD carry);
186 extern uintD subfrom_loop_down (const uintD* sourceptr, uintD* destptr, uintC count);
188 extern uintD dec_loop_down (uintD* ptr, uintC count);
190 extern uintD neg_loop_down (uintD* ptr, uintC count);
196 extern uintD shift1left_loop_down (uintD* ptr, uintC count);
198 extern uintD shiftleft_loop_down (uintD* ptr, uintC count, uintC i, uintD carry);
200 extern uintD shiftleftcopy_loop_down (const uintD* sourceptr, uintD* destptr, uintC count, uintC i);
202 extern uintD shift1right_loop_up (uintD* ptr, uintC count, uintD carry);
204 extern uintD shiftright_loop_up (uintD* ptr, uintC count, uintC i);
206 extern uintD shiftrightsigned_loop_up (uintD* ptr, uintC count, uintC i);
208 extern uintD shiftrightcopy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count, uintC i, uintD carry);
214 extern uintD mulusmall_loop_down (uintD digit, uintD* ptr, uintC len, uintD newdigit);
216 extern void mulu_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len);
218 extern uintD muluadd_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len);
220 extern uintD mulusub_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len);
226 extern uintD divu_loop_up (uintD digit, uintD* ptr, uintC len);
228 extern uintD divucopy_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len);
232 #else // !CL_DS_BIG_ENDIAN_P
236 extern void or_loop_down (uintD* xptr, const uintD* yptr, uintC count);
238 extern void xor_loop_down (uintD* xptr, const uintD* yptr, uintC count);
240 extern void and_loop_down (uintD* xptr, const uintD* yptr, uintC count);
242 extern void eqv_loop_down (uintD* xptr, const uintD* yptr, uintC count);
244 extern void nand_loop_down (uintD* xptr, const uintD* yptr, uintC count);
246 extern void nor_loop_down (uintD* xptr, const uintD* yptr, uintC count);
248 extern void andc2_loop_down (uintD* xptr, const uintD* yptr, uintC count);
250 extern void orc2_loop_down (uintD* xptr, const uintD* yptr, uintC count);
252 extern void not_loop_down (uintD* xptr, uintC count);
258 extern cl_boolean and_test_loop_down (const uintD* xptr, const uintD* yptr, uintC count);
260 extern cl_signean compare_loop_down (const uintD* xptr, const uintD* yptr, uintC count);
266 extern uintD add_loop_up (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count);
268 extern uintD addto_loop_up (const uintD* sourceptr, uintD* destptr, uintC count);
270 extern uintD inc_loop_up (uintD* ptr, uintC count);
272 extern uintD sub_loop_up (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count);
274 extern uintD subx_loop_up (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count, uintD carry);
276 extern uintD subfrom_loop_up (const uintD* sourceptr, uintD* destptr, uintC count);
278 extern uintD dec_loop_up (uintD* ptr, uintC count);
280 extern uintD neg_loop_up (uintD* ptr, uintC count);
286 extern uintD shift1left_loop_up (uintD* ptr, uintC count);
288 extern uintD shiftleft_loop_up (uintD* ptr, uintC count, uintC i, uintD carry);
290 extern uintD shiftleftcopy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count, uintC i);
292 extern uintD shift1right_loop_down (uintD* ptr, uintC count, uintD carry);
294 extern uintD shiftright_loop_down (uintD* ptr, uintC count, uintC i);
296 extern uintD shiftrightsigned_loop_down (uintD* ptr, uintC count, uintC i);
298 extern uintD shiftrightcopy_loop_down (const uintD* sourceptr, uintD* destptr, uintC count, uintC i, uintD carry);
304 extern uintD mulusmall_loop_up (uintD digit, uintD* ptr, uintC len, uintD newdigit);
306 extern void mulu_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len);
308 extern uintD muluadd_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len);
310 extern uintD mulusub_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len);
316 extern uintD divu_loop_down (uintD digit, uintD* ptr, uintC len);
318 extern uintD divucopy_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len);
322 #endif // !CL_DS_BIG_ENDIAN_P
324 // Independently of CL_DS_BIG_ENDIAN_P:
328 extern cl_signean compare_loop_up (const uintD* xptr, const uintD* yptr, uintC count);
334 extern void xor_loop_up (uintD* xptr, const uintD* yptr, uintC count);
340 extern uintD shiftleftcopy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count, uintC i);
342 extern void shiftxor_loop_up (uintD* xptr, const uintD* yptr, uintC count, uintC i);
349 #if defined(CL_USE_GMP)
351 // Supersede the functions by wrappers around calls to gmp mpn,
352 // for those functions where gmp is believed to be faster.
357 // Argh, gmp.h includes <stddef.h> which erases the definition of offsetof
358 // that we have provided in cl_offsetof.h. Restore it.
359 #include "cl_offsetof.h"
363 #if 0 // not worth it, since gmp's mpn_cmp is not optimized
364 inline cl_signean compare_loop_down (const uintD* xptr, const uintD* yptr, uintC count)
366 return mpn_cmp(xptr-count,yptr-count,count);
370 inline uintD add_loop_up (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count)
374 return mpn_add_n(destptr,sourceptr1,sourceptr2,count);
377 inline uintD addto_loop_up (const uintD* sourceptr, uintD* destptr, uintC count)
381 return mpn_add_n(destptr,destptr,sourceptr,count);
384 inline uintD inc_loop_up (uintD* ptr, uintC count)
388 return mpn_add_1(ptr,ptr,count,1);
391 inline uintD sub_loop_up (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count)
395 return mpn_sub_n(destptr,sourceptr1,sourceptr2,count);
398 inline uintD subx_loop_up (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count, uintD carry)
402 var uintD res_carry = mpn_sub_n(destptr,sourceptr1,sourceptr2,count);
404 res_carry |= mpn_sub_1(destptr,destptr,count,1);
408 inline uintD subfrom_loop_up (const uintD* sourceptr, uintD* destptr, uintC count)
412 return mpn_sub_n(destptr,destptr,sourceptr,count);
415 inline uintD dec_loop_up (uintD* ptr, uintC count)
419 return -mpn_sub_1(ptr,ptr,count,1);
422 #if !defined(ADDSUB_LOOPS)
423 // No equivalent for this in gmp. But we need this function, so write it in C.
424 inline uintD neg_loop_up (uintD* ptr, uintC count)
426 // erstes Digit /=0 suchen:
427 until (count==0) { if (!(*ptr == 0)) goto L1; ptr++; count--; }
429 L1: // erstes Digit /=0 gefunden, ab jetzt gibt's Carrys
430 *ptr = - *ptr; count--; // 1 Digit negieren
431 dotimesC(count,count, { ptr++; *ptr = ~ *ptr; } ); // alle anderen Digits invertieren
438 inline uintD shift1left_loop_up (uintD* ptr, uintC count)
442 return mpn_lshift(ptr,ptr,count,1);
445 inline uintD shiftleft_loop_up (uintD* ptr, uintC count, uintC i, uintD carry)
449 var uintD res_carry = mpn_lshift(ptr,ptr,count,i);
454 inline uintD shiftleftcopy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count, uintC i)
458 return mpn_lshift(destptr,sourceptr,count,i);
461 inline uintD shift1right_loop_down (uintD* ptr, uintC count, uintD carry)
465 var uintD res_carry = mpn_rshift(ptr-count,ptr-count,count,1);
467 ptr[-1] |= bit(intDsize-1);
471 inline uintD shiftright_loop_down (uintD* ptr, uintC count, uintC i)
475 return mpn_rshift(ptr-count,ptr-count,count,i);
478 inline uintD shiftrightsigned_loop_down (uintD* ptr, uintC count, uintC i)
480 var uintD carry = ((sintD)ptr[-1] >> (intDsize-1)) << (intDsize-i);
481 var uintD res_carry = mpn_rshift(ptr-count,ptr-count,count,i);
486 inline uintD shiftrightcopy_loop_down (const uintD* sourceptr, uintD* destptr, uintC count, uintC i, uintD carry)
488 carry = carry << (intDsize-i);
491 var uintD res_carry = mpn_rshift(destptr-count,sourceptr-count,count,i);
492 destptr[-1] |= carry;
498 inline uintD mulusmall_loop_up (uintD digit, uintD* ptr, uintC len, uintD newdigit)
502 var uintD res_carry = mpn_mul_1(ptr,ptr,len,digit);
503 res_carry += mpn_add_1(ptr,ptr,len,newdigit);
507 inline void mulu_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
509 destptr[len] = (len==0 ? 0 : mpn_mul_1(destptr,sourceptr,len,digit));
512 inline uintD muluadd_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
516 return mpn_addmul_1(destptr,sourceptr,len,digit);
519 inline uintD mulusub_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
523 return mpn_submul_1(destptr,sourceptr,len,digit);
528 inline uintD divu_loop_up (uintD digit, uintD* ptr, uintC len)
530 return mpn_divrem_1(ptr,0,ptr,len,digit);
533 inline uintD divu_loop_down (uintD digit, uintD* ptr, uintC len)
535 return mpn_divrem_1(ptr-len,0,ptr-len,len,digit);
538 inline uintD divucopy_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
540 return mpn_divrem_1(destptr,0,sourceptr,len,digit);
543 inline uintD divucopy_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
545 return mpn_divrem_1(destptr-len,0,sourceptr-len,len,digit);
550 #endif // defined(CL_USE_GMP)
553 // Define the missing functions as inline functions.
558 // destptr = copy_loop_up(sourceptr,destptr,count);
559 // kopiert count (uintC>=0) Digits aufwärts von sourceptr nach destptr
560 // und liefert das neue destptr.
561 inline uintD* copy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count)
562 { dotimesC(count,count, { *destptr++ = *sourceptr++; } );
567 // destptr = copy_loop_down(sourceptr,destptr,count);
568 // kopiert count (uintC>=0) Digits abwärts von sourceptr nach destptr
569 // und liefert das neue destptr.
570 inline uintD* copy_loop_down (const uintD* sourceptr, uintD* destptr, uintC count)
571 { dotimesC(count,count, { *--destptr = *--sourceptr; } );
580 // destptr = fill_loop_up(destptr,count,filler);
581 // kopiert count (uintC>=0) mal das Digit filler aufwärts nach destptr
582 // und liefert das neue destptr.
583 inline uintD* fill_loop_up (uintD* destptr, uintC count, uintD filler)
584 { dotimesC(count,count, { *destptr++ = filler; } );
589 // destptr = fill_loop_down(destptr,count,filler);
590 // kopiert count (uintC>=0) mal das Digit filler abwärts nach destptr
591 // und liefert das neue destptr.
592 inline uintD* fill_loop_down (uintD* destptr, uintC count, uintD filler)
593 { dotimesC(count,count, { *--destptr = filler; } );
602 // destptr = clear_loop_up(destptr,count);
603 // löscht count (uintC>=0) Digits aufwärts ab destptr
604 // und liefert das neue destptr.
605 inline uintD* clear_loop_up (uintD* destptr, uintC count)
606 { dotimesC(count,count, { *destptr++ = 0; } );
611 // destptr = clear_loop_down(destptr,count);
612 // löscht count (uintC>=0) Digits abwärts ab destptr
613 // und liefert das neue destptr.
614 inline uintD* clear_loop_down (uintD* destptr, uintC count)
615 { dotimesC(count,count, { *--destptr = 0; } );
624 // test_loop_up(ptr,count)
625 // testet count (uintC>=0) Digits aufwärts ab ptr, ob darunter eines /=0 ist.
626 // Ergebnis /=0, falls ja.
627 inline cl_boolean test_loop_up (const uintD* ptr, uintC count)
628 { dotimesC(count,count, { if (*ptr++) return cl_true; } );
633 // test_loop_down(ptr,count)
634 // testet count (uintC>=0) Digits abwärts ab ptr, ob darunter eines /=0 ist.
635 // Ergebnis /=0, falls ja.
636 inline cl_boolean test_loop_down (const uintD* ptr, uintC count)
637 { dotimesC(count,count, { if (*--ptr) return cl_true; } );
643 #if CL_DS_BIG_ENDIAN_P
648 // or_loop_up(xptr,yptr,count);
649 // verknüpft count (uintC>=0) Digits aufwärts ab xptr und ab yptr
650 // mit Ziel ab xptr durch OR.
651 inline void or_loop_up (uintD* xptr, const uintD* yptr, uintC count)
652 { dotimesC(count,count, { *xptr++ |= *yptr++; } ); }
655 // xor_loop_up(xptr,yptr,count);
656 // verknüpft count (uintC>=0) Digits aufwärts ab xptr und ab yptr
657 // mit Ziel ab xptr durch XOR.
658 inline void xor_loop_up (uintD* xptr, const uintD* yptr, uintC count)
659 { dotimesC(count,count, { *xptr++ ^= *yptr++; } ); }
662 // and_loop_up(xptr,yptr,count);
663 // verknüpft count (uintC>=0) Digits aufwärts ab xptr und ab yptr
664 // mit Ziel ab xptr durch AND.
665 inline void and_loop_up (uintD* xptr, const uintD* yptr, uintC count)
666 { dotimesC(count,count, { *xptr++ &= *yptr++; } ); }
669 // eqv_loop_up(xptr,yptr,count);
670 // verknüpft count (uintC>=0) Digits aufwärts ab xptr und ab yptr
671 // mit Ziel ab xptr durch EQV (NOT XOR).
672 inline void eqv_loop_up (uintD* xptr, const uintD* yptr, uintC count)
673 { dotimesC(count,count,
674 {var uintD temp = ~ (*xptr ^ *yptr++); *xptr++ = temp; }
679 // nand_loop_up(xptr,yptr,count);
680 // verknüpft count (uintC>=0) Digits aufwärts ab xptr und ab yptr
681 // mit Ziel ab xptr durch NAND (NOT AND).
682 inline void nand_loop_up (uintD* xptr, const uintD* yptr, uintC count)
683 { dotimesC(count,count,
684 {var uintD temp = ~ (*xptr & *yptr++); *xptr++ = temp; }
689 // nor_loop_up(xptr,yptr,count);
690 // verknüpft count (uintC>=0) Digits aufwärts ab xptr und ab yptr
691 // mit Ziel ab xptr durch NOR (NOT OR).
692 inline void nor_loop_up (uintD* xptr, const uintD* yptr, uintC count)
693 { dotimesC(count,count,
694 {var uintD temp = ~ (*xptr | *yptr++); *xptr++ = temp; }
699 // andc2_loop_up(xptr,yptr,count);
700 // verknüpft count (uintC>=0) Digits aufwärts ab xptr und ab yptr
701 // mit Ziel ab xptr durch ANDC2 (AND NOT).
702 inline void andc2_loop_up (uintD* xptr, const uintD* yptr, uintC count)
703 { dotimesC(count,count, { *xptr++ &= ~(*yptr++); } ); }
706 // orc2_loop_up(xptr,yptr,count);
707 // verknüpft count (uintC>=0) Digits aufwärts ab xptr und ab yptr
708 // mit Ziel ab xptr durch ORC2 (OR NOT).
709 inline void orc2_loop_up (uintD* xptr, const uintD* yptr, uintC count)
710 { dotimesC(count,count, { *xptr++ |= ~(*yptr++); } ); }
713 // not_loop_up(xptr,count);
714 // verknüpft count (uintC>0) Digits aufwärts ab xptr mit Ziel ab xptr
716 inline void not_loop_up (uintD* xptr, uintC count)
717 { dotimespC(count,count,
718 {var uintD temp = ~ (*xptr); *xptr++ = temp; }
726 // AND-Test-Schleife:
727 // and_test_loop_up(xptr,yptr,count);
728 // verknüpft count (uintC>=0) Digits aufwärts ab xptr und ab yptr durch AND
729 // und testet, ob sich dabei ein Digit /=0 ergibt. Ergebnis cl_true, falls ja.
730 inline cl_boolean and_test_loop_up (const uintD* xptr, const uintD* yptr, uintC count)
731 { dotimesC(count,count, { if (*xptr++ & *yptr++) return cl_true; } );
735 // Vergleichsschleife:
736 // result = compare_loop_up(xptr,yptr,count);
737 // vergleicht nacheinander xptr[0] mit yptr[0], xptr[1] mit yptr[1], usw.,
738 // insgesamt count Digits, und liefert 0 falls alle gleich sind,
739 // +1 falls zuerst ein xptr[i]>yptr[i] ist,
740 // -1 falls zuerst ein xptr[i]<yptr[i] ist.
741 inline cl_signean compare_loop_up (const uintD* xptr, const uintD* yptr, uintC count)
742 { dotimesC(count,count,
743 { if (!(*xptr++ == *yptr++))
744 // verschiedene Digits gefunden
745 return (*--xptr > *--yptr ? signean_plus : signean_minus);
747 return signean_null; // alle Digits gleich
754 // Additionsschleife:
755 // übertrag = add_loop_down(sourceptr1,sourceptr2,destptr,count);
756 // addiert count (uintC>=0) Digits abwärts von sourceptr1, von sourceptr2
757 // abwärts nach destptr und liefert den Übertrag (0 oder /=0, was 1 bedeutet).
758 inline uintD add_loop_down (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count)
762 do { source1 = *--sourceptr1;
763 source2 = *--sourceptr2;
764 *--destptr = source1 + source2;
765 if (source1 > (uintD)(~source2)) goto carry_1;
771 do { source1 = *--sourceptr1;
772 source2 = *--sourceptr2;
773 *--destptr = source1 + source2 + 1;
774 if (source1 < (uintD)(~source2)) goto carry_0;
782 // Additionsschleife:
783 // übertrag = addto_loop_down(sourceptr,destptr,count);
784 // addiert count (uintC>=0) Digits abwärts von sourceptr, von destptr
785 // abwärts nach destptr und liefert den Übertrag (0 oder /=0, was 1 bedeutet).
786 inline uintD addto_loop_down (const uintD* sourceptr, uintD* destptr, uintC count)
790 do { source1 = *--sourceptr;
791 source2 = *--destptr;
792 *destptr = source1 + source2;
793 if (source1 > (uintD)(~source2)) goto carry_1;
799 do { source1 = *--sourceptr;
800 source2 = *--destptr;
801 *destptr = source1 + source2 + 1;
802 if (source1 < (uintD)(~source2)) goto carry_0;
810 // Incrementierschleife:
811 // übertrag = inc_loop_down(ptr,count);
812 // incrementiert count (uintC>=0) Digits abwärts von ptr, so lange bis kein
813 // Übertrag mehr auftritt und liefert den Übertrag (0 oder /=0, was 1 bedeutet).
814 inline uintD inc_loop_down (uintD* ptr, uintC count)
815 { dotimesC(count,count,
816 { if (!( ++(*--ptr) == 0 )) return 0; } // kein weiterer Übertrag
818 return 1; // weiterer Übertrag
821 // Subtraktionsschleife:
822 // übertrag = sub_loop_down(sourceptr1,sourceptr2,destptr,count);
823 // subtrahiert count (uintC>=0) Digits abwärts von sourceptr1, von sourceptr2
824 // abwärts nach destptr und liefert den Übertrag (0 oder /=0, was -1 bedeutet).
825 inline uintD sub_loop_down (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count)
829 do { source1 = *--sourceptr1;
830 source2 = *--sourceptr2;
831 *--destptr = source1 - source2;
832 if (source1 < source2) goto carry_1;
838 do { source1 = *--sourceptr1;
839 source2 = *--sourceptr2;
840 *--destptr = source1 - source2 - 1;
841 if (source1 > source2) goto carry_0;
849 // Subtraktionsschleife:
850 // übertrag = subx_loop_down(sourceptr1,sourceptr2,destptr,count,carry);
851 // subtrahiert count (uintC>=0) Digits abwärts von sourceptr1 und addiert
852 // einen Carry (0 oder -1), von sourceptr2 abwärts nach destptr und
853 // liefert den Übertrag (0 oder /=0, was -1 bedeutet).
854 inline uintD subx_loop_down (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count, uintD carry)
859 do { source1 = *--sourceptr1;
860 source2 = *--sourceptr2;
861 *--destptr = source1 - source2;
862 if (source1 < source2) goto carry_1;
871 do { source1 = *--sourceptr1;
872 source2 = *--sourceptr2;
873 *--destptr = source1 - source2 - 1;
874 if (source1 > source2) goto carry_0;
882 // Subtraktionsschleife:
883 // übertrag = subfrom_loop_down(sourceptr,destptr,count);
884 // subtrahiert count (uintC>=0) Digits abwärts von sourceptr, von destptr
885 // abwärts nach destptr (dest := dest - source)
886 // und liefert den Übertrag (0 oder /=0, was -1 bedeutet).
887 inline uintD subfrom_loop_down (const uintD* sourceptr, uintD* destptr, uintC count)
891 do { source1 = *--destptr;
892 source2 = *--sourceptr;
893 *destptr = source1 - source2;
894 if (source1 < source2) goto carry_1;
900 do { source1 = *--destptr;
901 source2 = *--sourceptr;
902 *destptr = source1 - source2 - 1;
903 if (source1 > source2) goto carry_0;
911 // Decrementierschleife:
912 // übertrag = dec_loop_down(ptr,count);
913 // decrementiert count (uintC>=0) Digits abwärts von ptr, so lange bis kein
914 // Übertrag mehr auftritt und liefert den Übertrag (0 oder -1).
915 inline uintD dec_loop_down (uintD* ptr, uintC count)
916 { dotimesC(count,count,
917 { if (!( (*--ptr)-- == 0 )) return 0; } // kein weiterer Übertrag
919 return (uintD)(-1); // weiterer Übertrag
923 // übertrag = neg_loop_down(ptr,count);
924 // negiert count (uintC>=0) Digits abwärts von ptr,
925 // und liefert den Übertrag (0 oder -1).
926 inline uintD neg_loop_down (uintD* ptr, uintC count)
927 { // erstes Digit /=0 suchen:
928 until (count==0) { if (!(*--ptr == 0)) goto L1; count--; }
930 L1: // erstes Digit /=0 gefunden, ab jetzt gibt's Carrys
931 *ptr = - *ptr; count--; // 1 Digit negieren
932 dotimesC(count,count, { --ptr; *ptr = ~ *ptr; } ); // alle anderen Digits invertieren
940 // Schiebeschleife um 1 Bit nach links:
941 // übertrag = shift1left_loop_down(ptr,count);
942 // schiebt count (uintC>=0) Digits abwärts von ptr um 1 Bit nach links,
943 // und liefert den Übertrag (0 oder /=0, was 1 bedeutet).
945 inline uintD shift1left_loop_down (uintD* ptr, uintC count)
946 { var uintDD accu = 0;
947 dotimesC(count,count,
948 { accu = ((uintDD)(*--ptr)<<1)+accu; *ptr = lowD(accu);
949 accu = (uintDD)(highD(accu));
954 inline uintD shift1left_loop_down (uintD* ptr, uintC count)
955 { var uintD carry = 0;
956 dotimesC(count,count,
957 { var uintD accu = *--ptr;
958 *ptr = (accu<<1) | carry;
959 carry = accu>>(intDsize-1);
965 // Schiebeschleife um i Bits nach links:
966 // übertrag = shiftleft_loop_down(ptr,count,i,übertrag_init);
967 // schiebt count (uintC>=0) Digits abwärts von ptr um i Bits (0<i<intDsize)
968 // nach links, schiebt dabei die i Bits aus übertrag_init rechts rein,
969 // und liefert den Übertrag (was links rauskommt, >=0, <2^i).
971 inline uintD shiftleft_loop_down (uintD* ptr, uintC count, uintC i, uintD carry)
972 { var uintDD accu = (uintDD)carry;
973 dotimesC(count,count,
974 { accu = ((uintDD)(*--ptr)<<i)+accu; *ptr = lowD(accu);
975 accu = (uintDD)(highD(accu));
980 inline uintD shiftleft_loop_down (uintD* ptr, uintC count, uintC i, uintD carry)
981 { var uintC j = intDsize-i;
982 dotimesC(count,count,
983 { var uintD accu = *--ptr;
984 *ptr = (accu<<i) | carry;
991 // Schiebe- und Kopierschleife um i Bits nach links:
992 // übertrag = shiftleftcopy_loop_down(sourceptr,destptr,count,i);
993 // kopiert count (uintC>=0) Digits abwärts von sourceptr nach destptr
994 // und schiebt sie dabei um i Bits (0<i<intDsize) nach links,
995 // wobei ganz rechts mit i Nullbits aufgefüllt wird,
996 // und liefert den Übertrag (was links rauskommt, >=0, <2^i).
998 inline uintD shiftleftcopy_loop_down (const uintD* sourceptr, uintD* destptr, uintC count, uintC i)
999 { var uintDD accu = 0;
1000 dotimesC(count,count,
1001 { accu = ((uintDD)(*--sourceptr)<<i)+accu; *--destptr = lowD(accu);
1002 accu = (uintDD)(highD(accu));
1007 inline uintD shiftleftcopy_loop_down (const uintD* sourceptr, uintD* destptr, uintC count, uintC i)
1008 { var uintC j = intDsize-i;
1009 var uintD carry = 0;
1010 dotimesC(count,count,
1011 { var uintD accu = *--sourceptr;
1012 *--destptr = (accu<<i) | carry;
1019 // Schiebeschleife um 1 Bit nach rechts:
1020 // übertrag = shift1right_loop_up(ptr,count,übertrag_init);
1021 // schiebt count (uintC>=0) Digits aufwärts von ptr um 1 Bit nach rechts,
1022 // wobei links das Bit übertrag_init (sollte =0 oder =-1 sein) hineingeschoben
1023 // wird, und liefert den Übertrag (0 oder /=0, was 1 bedeutet).
1025 inline uintD shift1right_loop_up (uintD* ptr, uintC count, uintD carry)
1026 { var uintDD accu = (sintDD)(sintD)carry & ((uintDD)1 << (2*intDsize-1)); // 0 oder bit(2*intDsize-1)
1027 dotimesC(count,count,
1028 { accu = (highlowDD_0(*ptr)>>1)+accu; *ptr++ = highD(accu);
1029 accu = highlowDD_0(lowD(accu));
1034 inline uintD shift1right_loop_up (uintD* ptr, uintC count, uintD carry)
1035 { carry = carry << (intDsize-1); // carry zu einem einzigen Bit machen
1036 dotimesC(count,count,
1037 { var uintD accu = *ptr;
1038 *ptr++ = (accu >> 1) | carry;
1039 carry = accu << (intDsize-1);
1045 // Schiebeschleife um i Bits nach rechts:
1046 // übertrag = shiftright_loop_up(ptr,count,i);
1047 // schiebt count (uintC>=0) Digits aufwärts von ptr um i Bits (0<i<intDsize)
1048 // nach rechts, wobei links Nullen eingeschoben werden,
1049 // und liefert den Übertrag (was rechts rauskommt, als Bits intDsize-1..intDsize-i).
1051 inline uintD shiftright_loop_up (uintD* ptr, uintC count, uintC i)
1052 { var uintDD accu = 0;
1053 dotimesC(count,count,
1054 { // Die oberen i Bits von (uintD)accu bilden hier den Übertrag.
1055 accu = highlowDD_0(lowD(accu));
1056 // Die oberen i Bits von (uintDD)accu bilden hier den Übertrag.
1057 accu = (highlowDD_0(*ptr)>>i)+accu; *ptr++ = highD(accu);
1062 inline uintD shiftright_loop_up (uintD* ptr, uintC count, uintC i)
1063 { var uintC j = intDsize-i;
1064 var uintD carry = 0;
1065 dotimesC(count,count,
1066 { var uintD accu = *ptr;
1067 *ptr++ = (accu >> i) | carry;
1074 // Schiebeschleife um i Bits nach rechts:
1075 // übertrag = shiftrightsigned_loop_up(ptr,count,i);
1076 // schiebt count (uintC>0) Digits aufwärts von ptr um i Bits (0<i<intDsize)
1077 // nach rechts, wobei links das MSBit ver-i-facht wird,
1078 // und liefert den Übertrag (was rechts rauskommt, als Bits intDsize-1..intDsize-i).
1080 inline uintD shiftrightsigned_loop_up (uintD* ptr, uintC count, uintC i)
1081 { var uintDD accu = // Übertrag mit i Vorzeichenbits initialisieren
1082 highlowDD_0(sign_of_sintD((sintD)(*ptr)))>>i;
1083 dotimespC(count,count,
1084 { // Die oberen i Bits von (uintD)accu bilden hier den Übertrag.
1085 accu = highlowDD_0(lowD(accu));
1086 // Die oberen i Bits von (uintDD)accu bilden hier den Übertrag.
1087 accu = (highlowDD_0(*ptr)>>i)+accu; *ptr++ = highD(accu);
1092 inline uintD shiftrightsigned_loop_up (uintD* ptr, uintC count, uintC i)
1093 { var uintC j = intDsize-i;
1095 { var uintD accu = *ptr;
1096 *ptr++ = (sintD)accu >> i;
1100 dotimesC(count,count,
1101 { var uintD accu = *ptr;
1102 *ptr++ = (accu >> i) | carry;
1109 // Schiebe- und Kopier-Schleife um i Bits nach rechts:
1110 // übertrag = shiftrightcopy_loop_up(sourceptr,destptr,count,i,carry);
1111 // kopiert count (uintC>=0) Digits aufwärts von sourceptr nach destptr
1112 // und schiebt sie dabei um i Bits (0<i<intDsize) nach rechts, wobei carry
1113 // (sozusagen als sourceptr[-1]) die i Bits ganz links bestimmt,
1114 // und liefert den Übertrag (was rechts rauskommt, als Bits intDsize-1..intDsize-i).
1116 inline uintD shiftrightcopy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count, uintC i, uintD carry)
1117 { var uintDD accu = // Übertrag mit carry initialisieren
1118 highlowDD_0(carry)>>i;
1119 dotimesC(count,count,
1120 { // Die oberen i Bits von (uintD)accu bilden hier den Übertrag.
1121 accu = highlowDD_0(lowD(accu));
1122 // Die oberen i Bits von (uintDD)accu bilden hier den Übertrag.
1123 accu = (highlowDD_0(*sourceptr++)>>i)+accu; *destptr++ = highD(accu);
1128 inline uintD shiftrightcopy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count, uintC i, uintD carry)
1129 { var uintC j = intDsize-i;
1131 dotimesC(count,count,
1132 { var uintD accu = *sourceptr++;
1133 *destptr++ = (accu >> i) | carry;
1144 // Multiplikations-Einfachschleife:
1145 // Multipliziert eine UDS mit einem kleinen Digit und addiert ein kleines Digit.
1146 // mulusmall_loop_down(digit,ptr,len,newdigit)
1147 // multipliziert die UDS ptr[-len..-1] mit digit (>=2, <=36),
1148 // addiert dabei newdigit (>=0, <digit) zur letzten Ziffer,
1149 // und liefert den Carry (>=0, <digit).
1151 inline uintD mulusmall_loop_down (uintD digit, uintD* ptr, uintC len, uintD newdigit)
1152 { var uintDD carry = newdigit;
1154 { // Hier ist 0 <= carry < digit.
1155 carry = carry + muluD(digit,*--ptr);
1156 // Hier ist 0 <= carry < 2^intDsize*digit.
1158 carry = (uintDD)highD(carry); // carry := floor(carry/2^intDsize) < digit
1163 inline uintD mulusmall_loop_down (uintD digit, uintD* ptr, uintC len, uintD newdigit)
1164 { var uintD carry = newdigit;
1166 { // Hier ist 0 <= carry < digit.
1169 muluD(digit,*--ptr,hi=,lo=);
1170 // Hier ist 0 <= 2^intDsize*hi + lo + carry < 2^intDsize*digit.
1171 lo += carry; if (lo < carry) { hi += 1; }
1179 // Multiplikations-Einfachschleife:
1180 // Multipliziert eine UDS mit einem Digit und legt das Ergebnis in einer
1182 // mulu_loop_down(digit,sourceptr,destptr,len);
1183 // multipliziert die UDS sourceptr[-len..-1] (len>0)
1184 // mit dem einzelnen digit
1185 // und legt das Ergebnis in der UDS destptr[-len-1..-1] ab.
1187 inline void mulu_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1188 { var uintDD carry = 0;
1190 { // Hier ist carry=digit=0 oder 0 <= carry < digit.
1191 carry = carry + muluD(digit,*--sourceptr);
1192 // Hier ist carry=digit=0 oder 0 <= carry < 2^intDsize*digit.
1193 *--destptr = lowD(carry);
1194 carry = (uintDD)highD(carry); // carry := floor(carry/2^intDsize) < digit
1196 *--destptr = lowD(carry);
1199 inline void mulu_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1200 { var uintD carry = 0;
1202 { // Hier ist carry=digit=0 oder 0 <= carry < digit.
1205 muluD(digit,*--sourceptr,hi=,lo=);
1206 // Hier ist 0 <= 2^intDsize*hi + lo + carry < 2^intDsize*digit oder hi=lo=carry=digit=0.
1207 lo += carry; if (lo < carry) { hi += 1; }
1215 // Multiplikations-Einfachschleife mit Akkumulation:
1216 // Multipliziert eine UDS mit einem Digit und addiert das Ergebnis zu einer
1218 // muluadd_loop_down(digit,sourceptr,destptr,len);
1219 // multipliziert die UDS sourceptr[-len..-1] (len>0)
1220 // mit dem einzelnen digit, legt das Ergebnis in der UDS destptr[-len..-1]
1221 // ab und liefert den weiteren Übertrag.
1223 inline uintD muluadd_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1224 { var uintDD carry = 0;
1226 { dotimespC(len,len,
1227 { // Hier ist 0 <= carry <= digit.
1228 carry = carry + muluD(digit,*--sourceptr) + (uintDD)*--destptr;
1229 // Hier ist 0 <= carry <= 2^intDsize*digit + 2^intDsize-1.
1230 *destptr = lowD(carry);
1231 carry = (uintDD)highD(carry); // carry := floor(carry/2^intDsize) <= digit
1237 inline uintD muluadd_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1238 { var uintD carry = 0;
1240 { dotimespC(len,len,
1241 { // Hier ist 0 <= carry <= digit.
1244 muluD(digit,*--sourceptr,hi=,lo=);
1245 // Hier ist 0 <= 2^intDsize*hi + lo + carry + *--destptr <= 2^intDsize*digit+2^intDsize-1.
1246 lo += carry; if (lo < carry) { hi += 1; }
1248 lo += carry; if (lo < carry) { hi += 1; }
1257 // Multiplikations-Einfachschleife mit Diminution:
1258 // Multipliziert eine UDS mit einem Digit und subtrahiert das Ergebnis von
1259 // einer zweiten UDS.
1260 // mulusub_loop_down(digit,sourceptr,destptr,len);
1261 // multipliziert die UDS sourceptr[-len..-1] (len>0) mit dem einzelnen
1262 // digit, subtrahiert das Ergebnis von der UDS destptr[-len..-1] und liefert
1263 // den weiteren Übertrag (>=0, evtl. von destptr[-len-1] zu subtrahieren).
1265 inline uintD mulusub_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1266 { var uintDD carry = 0;
1268 { dotimespC(len,len,
1269 { // Hier ist 0 <= carry <= digit.
1270 carry = carry + muluD(digit,*--sourceptr) + (uintD)(~(*--destptr));
1271 // Hier ist 0 <= carry <= 2^intDsize*digit + 2^intDsize-1.
1272 *destptr = ~lowD(carry);
1273 carry = (uintDD)highD(carry); // carry := floor(carry/2^intDsize) <= digit
1274 // Hier ist 0 <= carry <= digit.
1279 return 0; // nichts zu subtrahieren -> kein Übertrag
1282 inline uintD mulusub_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1283 { var uintD carry = 0;
1285 { dotimespC(len,len,
1286 { // Hier ist 0 <= carry <= digit.
1289 muluD(digit,*--sourceptr,hi=,lo=);
1290 // Hier ist 0 <= 2^intDsize*hi + lo + carry + ~(*--destptr) <= 2^intDsize*digit+2^intDsize-1.
1291 lo += carry; if (lo < carry) { hi += 1; }
1293 *destptr = carry - lo; if (carry < lo) { hi += 1; }
1299 return 0; // nichts zu subtrahieren -> kein Übertrag
1307 // Divisions-Einfachschleife:
1308 // Dividiert eine UDS durch ein Digit.
1309 // divu_loop_up(digit,ptr,len)
1310 // dividiert die UDS ptr[0..len-1] durch digit,
1311 // legt das Ergebnis in derselben UDS ab, und liefert den Rest (>=0, <digit).
1313 inline uintD divu_loop_up (uintD digit, uintD* ptr, uintC len)
1314 { var uintD rest = 0;
1316 { divuD(highlowDD(rest,*ptr),digit,*ptr =, rest =); ptr++; }
1321 inline uintD divu_loop_up (uintD digit, uintD* ptr, uintC len)
1322 { var uintD rest = 0;
1324 { divuD(rest,*ptr,digit,*ptr =, rest =); ptr++; }
1330 // Divisions-Einfachschleife:
1331 // Dividiert eine UDS durch ein Digit und legt das Ergebnis in einer
1333 // divucopy_loop_up(digit,sourceptr,destptr,len)
1334 // dividiert die UDS sourceptr[0..len-1] durch digit,
1335 // legt das Ergebnis in der UDS destptr[0..len-1] ab,
1336 // und liefert den Rest (>=0, <digit).
1338 inline uintD divucopy_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1339 { var uintD rest = 0;
1341 { divuD(highlowDD(rest,*sourceptr++),digit,*destptr++ =, rest =); }
1346 inline uintD divucopy_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1347 { var uintD rest = 0;
1349 { divuD(rest,*sourceptr++,digit,*destptr++ =, rest =); }
1357 #else // !CL_DS_BIG_ENDIAN_P
1362 // or_loop_down(xptr,yptr,count);
1363 // verknüpft count (uintC>=0) Digits abwärts ab xptr und ab yptr
1364 // mit Ziel ab xptr durch OR.
1365 inline void or_loop_down (uintD* xptr, const uintD* yptr, uintC count)
1366 { dotimesC(count,count, { *--xptr |= *--yptr; } ); }
1369 // xor_loop_down(xptr,yptr,count);
1370 // verknüpft count (uintC>=0) Digits abwärts ab xptr und ab yptr
1371 // mit Ziel ab xptr durch XOR.
1372 inline void xor_loop_down (uintD* xptr, const uintD* yptr, uintC count)
1373 { dotimesC(count,count, { *--xptr ^= *--yptr; } ); }
1376 // and_loop_down(xptr,yptr,count);
1377 // verknüpft count (uintC>=0) Digits abwärts ab xptr und ab yptr
1378 // mit Ziel ab xptr durch AND.
1379 inline void and_loop_down (uintD* xptr, const uintD* yptr, uintC count)
1380 { dotimesC(count,count, { *--xptr &= *--yptr; } ); }
1383 // eqv_loop_down(xptr,yptr,count);
1384 // verknüpft count (uintC>=0) Digits abwärts ab xptr und ab yptr
1385 // mit Ziel ab xptr durch EQV (NOT XOR).
1386 inline void eqv_loop_down (uintD* xptr, const uintD* yptr, uintC count)
1387 { dotimesC(count,count,
1388 {var uintD temp = ~ (*--xptr ^ *--yptr); *xptr = temp; }
1393 // nand_loop_down(xptr,yptr,count);
1394 // verknüpft count (uintC>=0) Digits abwärts ab xptr und ab yptr
1395 // mit Ziel ab xptr durch NAND (NOT AND).
1396 inline void nand_loop_down (uintD* xptr, const uintD* yptr, uintC count)
1397 { dotimesC(count,count,
1398 {var uintD temp = ~ (*--xptr & *--yptr); *xptr = temp; }
1403 // nor_loop_down(xptr,yptr,count);
1404 // verknüpft count (uintC>=0) Digits abwärts ab xptr und ab yptr
1405 // mit Ziel ab xptr durch NOR (NOT OR).
1406 inline void nor_loop_down (uintD* xptr, const uintD* yptr, uintC count)
1407 { dotimesC(count,count,
1408 {var uintD temp = ~ (*--xptr | *--yptr); *xptr = temp; }
1413 // andc2_loop_down(xptr,yptr,count);
1414 // verknüpft count (uintC>=0) Digits abwärts ab xptr und ab yptr
1415 // mit Ziel ab xptr durch ANDC2 (AND NOT).
1416 inline void andc2_loop_down (uintD* xptr, const uintD* yptr, uintC count)
1417 { dotimesC(count,count, { *--xptr &= ~(*--yptr); } ); }
1420 // orc2_loop_down(xptr,yptr,count);
1421 // verknüpft count (uintC>=0) Digits abwärts ab xptr und ab yptr
1422 // mit Ziel ab xptr durch ORC2 (OR NOT).
1423 inline void orc2_loop_down (uintD* xptr, const uintD* yptr, uintC count)
1424 { dotimesC(count,count, { *--xptr |= ~(*--yptr); } ); }
1427 // not_loop_down(xptr,count);
1428 // verknüpft count (uintC>0) Digits abwärts ab xptr mit Ziel ab xptr
1430 inline void not_loop_down (uintD* xptr, uintC count)
1431 { dotimespC(count,count,
1432 {var uintD temp = ~ (*--xptr); *xptr = temp; }
1440 // AND-Test-Schleife:
1441 // and_test_loop_down(xptr,yptr,count);
1442 // verknüpft count (uintC>=0) Digits abwärts ab xptr und ab yptr durch AND
1443 // und testet, ob sich dabei ein Digit /=0 ergibt. Ergebnis cl_true, falls ja.
1444 inline cl_boolean and_test_loop_down (const uintD* xptr, const uintD* yptr, uintC count)
1445 { dotimesC(count,count, { if (*--xptr & *--yptr) return cl_true; } );
1449 // Vergleichsschleife:
1450 // result = compare_loop_down(xptr,yptr,count);
1451 // vergleicht nacheinander xptr[-1] mit yptr[-1], xptr[-2] mit yptr[-2], usw.,
1452 // insgesamt count Digits, und liefert 0 falls alle gleich sind,
1453 // +1 falls zuerst ein xptr[i]>yptr[i] ist,
1454 // -1 falls zuerst ein xptr[i]<yptr[i] ist.
1455 inline cl_signean compare_loop_down (const uintD* xptr, const uintD* yptr, uintC count)
1456 { dotimesC(count,count,
1457 { if (!(*--xptr == *--yptr))
1458 // verschiedene Digits gefunden
1459 return (*xptr > *yptr ? signean_plus : signean_minus);
1461 return signean_null; // alle Digits gleich
1466 #ifndef ADDSUB_LOOPS
1468 // Additionsschleife:
1469 // übertrag = add_loop_up(sourceptr1,sourceptr2,destptr,count);
1470 // addiert count (uintC>=0) Digits aufwärts von sourceptr1, von sourceptr2
1471 // aufwärts nach destptr und liefert den Übertrag (0 oder /=0, was 1 bedeutet).
1472 inline uintD add_loop_up (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count)
1473 { var uintD source1;
1476 do { source1 = *sourceptr1++;
1477 source2 = *sourceptr2++;
1478 *destptr++ = source1 + source2;
1479 if (source1 > (uintD)(~source2)) goto carry_1;
1485 do { source1 = *sourceptr1++;
1486 source2 = *sourceptr2++;
1487 *destptr++ = source1 + source2 + 1;
1488 if (source1 < (uintD)(~source2)) goto carry_0;
1496 // Additionsschleife:
1497 // übertrag = addto_loop_up(sourceptr,destptr,count);
1498 // addiert count (uintC>=0) Digits aufwärts von sourceptr, von destptr
1499 // aufwärts nach destptr und liefert den Übertrag (0 oder /=0, was 1 bedeutet).
1500 inline uintD addto_loop_up (const uintD* sourceptr, uintD* destptr, uintC count)
1501 { var uintD source1;
1504 do { source1 = *sourceptr++;
1506 *destptr++ = source1 + source2;
1507 if (source1 > (uintD)(~source2)) goto carry_1;
1513 do { source1 = *sourceptr++;
1515 *destptr++ = source1 + source2 + 1;
1516 if (source1 < (uintD)(~source2)) goto carry_0;
1524 // Incrementierschleife:
1525 // übertrag = inc_loop_up(ptr,count);
1526 // incrementiert count (uintC>=0) Digits aufwärts von ptr, so lange bis kein
1527 // Übertrag mehr auftritt und liefert den Übertrag (0 oder /=0, was 1 bedeutet).
1528 inline uintD inc_loop_up (uintD* ptr, uintC count)
1529 { dotimesC(count,count,
1530 { if (!( ++(*ptr++) == 0 )) return 0; } // kein weiterer Übertrag
1532 return 1; // weiterer Übertrag
1535 // Subtraktionsschleife:
1536 // übertrag = sub_loop_up(sourceptr1,sourceptr2,destptr,count);
1537 // subtrahiert count (uintC>=0) Digits aufwärts von sourceptr1, von sourceptr2
1538 // aufwärts nach destptr und liefert den Übertrag (0 oder /=0, was -1 bedeutet).
1539 inline uintD sub_loop_up (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count)
1540 { var uintD source1;
1543 do { source1 = *sourceptr1++;
1544 source2 = *sourceptr2++;
1545 *destptr++ = source1 - source2;
1546 if (source1 < source2) goto carry_1;
1552 do { source1 = *sourceptr1++;
1553 source2 = *sourceptr2++;
1554 *destptr++ = source1 - source2 - 1;
1555 if (source1 > source2) goto carry_0;
1563 // Subtraktionsschleife:
1564 // übertrag = subx_loop_up(sourceptr1,sourceptr2,destptr,count,carry);
1565 // subtrahiert count (uintC>=0) Digits aufwärts von sourceptr1 und addiert
1566 // einen Carry (0 oder -1), von sourceptr2 aufwärts nach destptr und
1567 // liefert den Übertrag (0 oder /=0, was -1 bedeutet).
1568 inline uintD subx_loop_up (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count, uintD carry)
1569 { var uintD source1;
1573 do { source1 = *sourceptr1++;
1574 source2 = *sourceptr2++;
1575 *destptr++ = source1 - source2;
1576 if (source1 < source2) goto carry_1;
1585 do { source1 = *sourceptr1++;
1586 source2 = *sourceptr2++;
1587 *destptr++ = source1 - source2 - 1;
1588 if (source1 > source2) goto carry_0;
1596 // Subtraktionsschleife:
1597 // übertrag = subfrom_loop_up(sourceptr,destptr,count);
1598 // subtrahiert count (uintC>=0) Digits aufwärts von sourceptr, von destptr
1599 // aufwärts nach destptr (dest := dest - source)
1600 // und liefert den Übertrag (0 oder /=0, was -1 bedeutet).
1601 inline uintD subfrom_loop_up (const uintD* sourceptr, uintD* destptr, uintC count)
1602 { var uintD source1;
1605 do { source1 = *destptr;
1606 source2 = *sourceptr++;
1607 *destptr++ = source1 - source2;
1608 if (source1 < source2) goto carry_1;
1614 do { source1 = *destptr;
1615 source2 = *sourceptr++;
1616 *destptr++ = source1 - source2 - 1;
1617 if (source1 > source2) goto carry_0;
1625 // Decrementierschleife:
1626 // übertrag = dec_loop_up(ptr,count);
1627 // decrementiert count (uintC>=0) Digits aufwärts von ptr, so lange bis kein
1628 // Übertrag mehr auftritt und liefert den Übertrag (0 oder -1).
1629 inline uintD dec_loop_up (uintD* ptr, uintC count)
1630 { dotimesC(count,count,
1631 { if (!( (*ptr++)-- == 0 )) return 0; } // kein weiterer Übertrag
1633 return (uintD)(-1); // weiterer Übertrag
1637 // übertrag = neg_loop_up(ptr,count);
1638 // negiert count (uintC>=0) Digits aufwärts von ptr,
1639 // und liefert den Übertrag (0 oder -1).
1640 inline uintD neg_loop_up (uintD* ptr, uintC count)
1641 { // erstes Digit /=0 suchen:
1642 until (count==0) { if (!(*ptr == 0)) goto L1; ptr++; count--; }
1644 L1: // erstes Digit /=0 gefunden, ab jetzt gibt's Carrys
1645 *ptr = - *ptr; count--; // 1 Digit negieren
1646 dotimesC(count,count, { ptr++; *ptr = ~ *ptr; } ); // alle anderen Digits invertieren
1654 // Schiebeschleife um 1 Bit nach links:
1655 // übertrag = shift1left_loop_up(ptr,count);
1656 // schiebt count (uintC>=0) Digits aufwärts von ptr um 1 Bit nach links,
1657 // und liefert den Übertrag (0 oder /=0, was 1 bedeutet).
1659 inline uintD shift1left_loop_up (uintD* ptr, uintC count)
1660 { var uintDD accu = 0;
1661 dotimesC(count,count,
1662 { accu = ((uintDD)(*ptr)<<1)+accu; *ptr++ = lowD(accu);
1663 accu = (uintDD)(highD(accu));
1668 inline uintD shift1left_loop_up (uintD* ptr, uintC count)
1669 { var uintD carry = 0;
1670 dotimesC(count,count,
1671 { var uintD accu = *ptr;
1672 *ptr++ = (accu<<1) | carry;
1673 carry = accu>>(intDsize-1);
1679 // Schiebeschleife um i Bits nach links:
1680 // übertrag = shiftleft_loop_up(ptr,count,i,übertrag_init);
1681 // schiebt count (uintC>=0) Digits aufwärts von ptr um i Bits (0<i<intDsize)
1682 // nach links, schiebt dabei die i Bits aus übertrag_init rechts rein,
1683 // und liefert den Übertrag (was links rauskommt, >=0, <2^i).
1685 inline uintD shiftleft_loop_up (uintD* ptr, uintC count, uintC i, uintD carry)
1686 { var uintDD accu = (uintDD)carry;
1687 dotimesC(count,count,
1688 { accu = ((uintDD)(*ptr)<<i)+accu; *ptr++ = lowD(accu);
1689 accu = (uintDD)(highD(accu));
1694 inline uintD shiftleft_loop_up (uintD* ptr, uintC count, uintC i, uintD carry)
1695 { var uintC j = intDsize-i;
1696 dotimesC(count,count,
1697 { var uintD accu = *ptr;
1698 *ptr++ = (accu<<i) | carry;
1705 // Schiebe- und Kopierschleife um i Bits nach links:
1706 // übertrag = shiftleftcopy_loop_up(sourceptr,destptr,count,i);
1707 // kopiert count (uintC>=0) Digits aufwärts von sourceptr nach destptr
1708 // und schiebt sie dabei um i Bits (0<i<intDsize) nach links,
1709 // wobei ganz rechts mit i Nullbits aufgefüllt wird,
1710 // und liefert den Übertrag (was links rauskommt, >=0, <2^i).
1712 inline uintD shiftleftcopy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count, uintC i)
1713 { var uintDD accu = 0;
1714 dotimesC(count,count,
1715 { accu = ((uintDD)(*sourceptr++)<<i)+accu; *destptr++ = lowD(accu);
1716 accu = (uintDD)(highD(accu));
1721 inline uintD shiftleftcopy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count, uintC i)
1722 { var uintC j = intDsize-i;
1723 var uintD carry = 0;
1724 dotimesC(count,count,
1725 { var uintD accu = *sourceptr++;
1726 *destptr++ = (accu<<i) | carry;
1733 // Schiebeschleife um 1 Bit nach rechts:
1734 // übertrag = shift1right_loop_down(ptr,count,übertrag_init);
1735 // schiebt count (uintC>=0) Digits abwärts von ptr um 1 Bit nach rechts,
1736 // wobei links das Bit übertrag_init (sollte =0 oder =-1 sein) hineingeschoben
1737 // wird, und liefert den Übertrag (0 oder /=0, was 1 bedeutet).
1739 inline uintD shift1right_loop_down (uintD* ptr, uintC count, uintD carry)
1740 { var uintDD accu = (sintDD)(sintD)carry & ((uintDD)1 << (2*intDsize-1)); // 0 oder bit(2*intDsize-1)
1741 dotimesC(count,count,
1742 { accu = (highlowDD_0(*--ptr)>>1)+accu; *ptr = highD(accu);
1743 accu = highlowDD_0(lowD(accu));
1748 inline uintD shift1right_loop_down (uintD* ptr, uintC count, uintD carry)
1749 { carry = carry << (intDsize-1); // carry zu einem einzigen Bit machen
1750 dotimesC(count,count,
1751 { var uintD accu = *--ptr;
1752 *ptr = (accu >> 1) | carry;
1753 carry = accu << (intDsize-1);
1759 // Schiebeschleife um i Bits nach rechts:
1760 // übertrag = shiftright_loop_down(ptr,count,i);
1761 // schiebt count (uintC>=0) Digits abwärts von ptr um i Bits (0<i<intDsize)
1762 // nach rechts, wobei links Nullen eingeschoben werden,
1763 // und liefert den Übertrag (was rechts rauskommt, als Bits intDsize-1..intDsize-i).
1765 inline uintD shiftright_loop_down (uintD* ptr, uintC count, uintC i)
1766 { var uintDD accu = 0;
1767 dotimesC(count,count,
1768 { // Die oberen i Bits von (uintD)accu bilden hier den Übertrag.
1769 accu = highlowDD_0(lowD(accu));
1770 // Die oberen i Bits von (uintDD)accu bilden hier den Übertrag.
1771 accu = (highlowDD_0(*--ptr)>>i)+accu; *ptr = highD(accu);
1776 inline uintD shiftright_loop_down (uintD* ptr, uintC count, uintC i)
1777 { var uintC j = intDsize-i;
1778 var uintD carry = 0;
1779 dotimesC(count,count,
1780 { var uintD accu = *--ptr;
1781 *ptr = (accu >> i) | carry;
1788 // Schiebeschleife um i Bits nach rechts:
1789 // übertrag = shiftrightsigned_loop_down(ptr,count,i);
1790 // schiebt count (uintC>0) Digits abwärts von ptr um i Bits (0<i<intDsize)
1791 // nach rechts, wobei links das MSBit ver-i-facht wird,
1792 // und liefert den Übertrag (was rechts rauskommt, als Bits intDsize-1..intDsize-i).
1794 inline uintD shiftrightsigned_loop_down (uintD* ptr, uintC count, uintC i)
1795 { var uintDD accu = // Übertrag mit i Vorzeichenbits initialisieren
1796 highlowDD_0(sign_of_sintD((sintD)(ptr[-1])))>>i;
1797 dotimespC(count,count,
1798 { // Die oberen i Bits von (uintD)accu bilden hier den Übertrag.
1799 accu = highlowDD_0(lowD(accu));
1800 // Die oberen i Bits von (uintDD)accu bilden hier den Übertrag.
1801 accu = (highlowDD_0(*--ptr)>>i)+accu; *ptr = highD(accu);
1806 inline uintD shiftrightsigned_loop_down (uintD* ptr, uintC count, uintC i)
1807 { var uintC j = intDsize-i;
1809 { var uintD accu = *--ptr;
1810 *ptr = (sintD)accu >> i;
1814 dotimesC(count,count,
1815 { var uintD accu = *--ptr;
1816 *ptr = (accu >> i) | carry;
1823 // Schiebe- und Kopier-Schleife um i Bits nach rechts:
1824 // übertrag = shiftrightcopy_loop_down(sourceptr,destptr,count,i,carry);
1825 // kopiert count (uintC>=0) Digits abwärts von sourceptr nach destptr
1826 // und schiebt sie dabei um i Bits (0<i<intDsize) nach rechts, wobei carry
1827 // (sozusagen als sourceptr[0]) die i Bits ganz links bestimmt,
1828 // und liefert den Übertrag (was rechts rauskommt, als Bits intDsize-1..intDsize-i).
1830 inline uintD shiftrightcopy_loop_down (const uintD* sourceptr, uintD* destptr, uintC count, uintC i, uintD carry)
1831 { var uintDD accu = // Übertrag mit carry initialisieren
1832 highlowDD_0(carry)>>i;
1833 dotimesC(count,count,
1834 { // Die oberen i Bits von (uintD)accu bilden hier den Übertrag.
1835 accu = highlowDD_0(lowD(accu));
1836 // Die oberen i Bits von (uintDD)accu bilden hier den Übertrag.
1837 accu = (highlowDD_0(*--sourceptr)>>i)+accu; *--destptr = highD(accu);
1842 inline uintD shiftrightcopy_loop_down (const uintD* sourceptr, uintD* destptr, uintC count, uintC i, uintD carry)
1843 { var uintC j = intDsize-i;
1845 dotimesC(count,count,
1846 { var uintD accu = *--sourceptr;
1847 *--destptr = (accu >> i) | carry;
1858 // Multiplikations-Einfachschleife:
1859 // Multipliziert eine UDS mit einem kleinen Digit und addiert ein kleines Digit.
1860 // mulusmall_loop_up(digit,ptr,len,newdigit)
1861 // multipliziert die UDS ptr[0..len-1] mit digit (>=2, <=36),
1862 // addiert dabei newdigit (>=0, <digit) zur letzten Ziffer,
1863 // und liefert den Carry (>=0, <digit).
1865 inline uintD mulusmall_loop_up (uintD digit, uintD* ptr, uintC len, uintD newdigit)
1866 { var uintDD carry = newdigit;
1868 { // Hier ist 0 <= carry < digit.
1869 carry = carry + muluD(digit,*ptr);
1870 // Hier ist 0 <= carry < 2^intDsize*digit.
1871 *ptr++ = lowD(carry);
1872 carry = (uintDD)highD(carry); // carry := floor(carry/2^intDsize) < digit
1877 inline uintD mulusmall_loop_up (uintD digit, uintD* ptr, uintC len, uintD newdigit)
1878 { var uintD carry = newdigit;
1880 { // Hier ist 0 <= carry < digit.
1883 muluD(digit,*ptr,hi=,lo=);
1884 // Hier ist 0 <= 2^intDsize*hi + lo + carry < 2^intDsize*digit.
1885 lo += carry; if (lo < carry) { hi += 1; }
1893 // Multiplikations-Einfachschleife:
1894 // Multipliziert eine UDS mit einem Digit und legt das Ergebnis in einer
1896 // mulu_loop_up(digit,sourceptr,destptr,len);
1897 // multipliziert die UDS sourceptr[0..len-1] (len>0)
1898 // mit dem einzelnen digit
1899 // und legt das Ergebnis in der UDS destptr[0..len] ab.
1901 inline void mulu_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1902 { var uintDD carry = 0;
1904 { // Hier ist carry=digit=0 oder 0 <= carry < digit.
1905 carry = carry + muluD(digit,*sourceptr++);
1906 // Hier ist carry=digit=0 oder 0 <= carry < 2^intDsize*digit.
1907 *destptr++ = lowD(carry);
1908 carry = (uintDD)highD(carry); // carry := floor(carry/2^intDsize) < digit
1910 *destptr++ = lowD(carry);
1913 inline void mulu_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1914 { var uintD carry = 0;
1916 { // Hier ist carry=digit=0 oder 0 <= carry < digit.
1919 muluD(digit,*sourceptr++,hi=,lo=);
1920 // Hier ist 0 <= 2^intDsize*hi + lo + carry < 2^intDsize*digit oder hi=lo=carry=digit=0.
1921 lo += carry; if (lo < carry) { hi += 1; }
1929 // Multiplikations-Einfachschleife mit Akkumulation:
1930 // Multipliziert eine UDS mit einem Digit und addiert das Ergebnis zu einer
1932 // muluadd_loop_up(digit,sourceptr,destptr,len);
1933 // multipliziert die UDS sourceptr[0..len-1] (len>0)
1934 // mit dem einzelnen digit, legt das Ergebnis in der UDS destptr[0..len-1]
1935 // ab und liefert den weiteren Übertrag.
1937 inline uintD muluadd_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1938 { var uintDD carry = 0;
1940 { dotimespC(len,len,
1941 { // Hier ist 0 <= carry <= digit.
1942 carry = carry + muluD(digit,*sourceptr++) + (uintDD)*destptr;
1943 // Hier ist 0 <= carry <= 2^intDsize*digit + 2^intDsize-1.
1944 *destptr++ = lowD(carry);
1945 carry = (uintDD)highD(carry); // carry := floor(carry/2^intDsize) <= digit
1951 inline uintD muluadd_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1952 { var uintD carry = 0;
1954 { dotimespC(len,len,
1955 { // Hier ist 0 <= carry <= digit.
1958 muluD(digit,*sourceptr++,hi=,lo=);
1959 // Hier ist 0 <= 2^intDsize*hi + lo + carry + *destptr <= 2^intDsize*digit+2^intDsize-1.
1960 lo += carry; if (lo < carry) { hi += 1; }
1962 lo += carry; if (lo < carry) { hi += 1; }
1971 // Multiplikations-Einfachschleife mit Diminution:
1972 // Multipliziert eine UDS mit einem Digit und subtrahiert das Ergebnis von
1973 // einer zweiten UDS.
1974 // mulusub_loop_up(digit,sourceptr,destptr,len);
1975 // multipliziert die UDS sourceptr[0..len-1] (len>0) mit dem einzelnen
1976 // digit, subtrahiert das Ergebnis von der UDS destptr[0..len-1] und liefert
1977 // den weiteren Übertrag (>=0, evtl. von destptr[len] zu subtrahieren).
1979 inline uintD mulusub_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1980 { var uintDD carry = 0;
1982 { dotimespC(len,len,
1983 { // Hier ist 0 <= carry <= digit.
1984 carry = carry + muluD(digit,*sourceptr++) + (uintD)(~(*destptr));
1985 // Hier ist 0 <= carry <= 2^intDsize*digit + 2^intDsize-1.
1986 *destptr++ = ~lowD(carry);
1987 carry = (uintDD)highD(carry); // carry := floor(carry/2^intDsize) <= digit
1988 // Hier ist 0 <= carry <= digit.
1993 return 0; // nichts zu subtrahieren -> kein Übertrag
1996 inline uintD mulusub_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1997 { var uintD carry = 0;
1999 { dotimespC(len,len,
2000 { // Hier ist 0 <= carry <= digit.
2003 muluD(digit,*sourceptr++,hi=,lo=);
2004 // Hier ist 0 <= 2^intDsize*hi + lo + carry + ~(*destptr) <= 2^intDsize*digit+2^intDsize-1.
2005 lo += carry; if (lo < carry) { hi += 1; }
2007 *destptr++ = carry - lo; if (carry < lo) { hi += 1; }
2013 return 0; // nichts zu subtrahieren -> kein Übertrag
2021 // Divisions-Einfachschleife:
2022 // Dividiert eine UDS durch ein Digit.
2023 // divu_loop_down(digit,ptr,len)
2024 // dividiert die UDS ptr[-len..-1] durch digit,
2025 // legt das Ergebnis in derselben UDS ab, und liefert den Rest (>=0, <digit).
2027 inline uintD divu_loop_down (uintD digit, uintD* ptr, uintC len)
2028 { var uintD rest = 0;
2030 { --ptr; divuD(highlowDD(rest,*ptr),digit,*ptr =, rest =); }
2035 inline uintD divu_loop_down (uintD digit, uintD* ptr, uintC len)
2036 { var uintD rest = 0;
2038 { --ptr; divuD(rest,*ptr,digit,*ptr =, rest =); }
2044 // Divisions-Einfachschleife:
2045 // Dividiert eine UDS durch ein Digit und legt das Ergebnis in einer
2047 // divucopy_loop_down(digit,sourceptr,destptr,len)
2048 // dividiert die UDS sourceptr[-len..-1] durch digit,
2049 // legt das Ergebnis in der UDS destptr[-len..-1] ab,
2050 // und liefert den Rest (>=0, <digit).
2052 inline uintD divucopy_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
2053 { var uintD rest = 0;
2055 { divuD(highlowDD(rest,*--sourceptr),digit,*--destptr =, rest =); }
2060 inline uintD divucopy_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
2061 { var uintD rest = 0;
2063 { divuD(rest,*--sourceptr,digit,*--destptr =, rest =); }
2071 #endif // !CL_DS_BIG_ENDIAN_P
2073 #if !defined(TEST_LOOPS) && !CL_DS_BIG_ENDIAN_P
2075 // Vergleichsschleife:
2076 // result = compare_loop_up(xptr,yptr,count);
2077 // vergleicht nacheinander xptr[0] mit yptr[0], xptr[1] mit yptr[1], usw.,
2078 // insgesamt count Digits, und liefert 0 falls alle gleich sind,
2079 // +1 falls zuerst ein xptr[i]>yptr[i] ist,
2080 // -1 falls zuerst ein xptr[i]<yptr[i] ist.
2081 inline cl_signean compare_loop_up (const uintD* xptr, const uintD* yptr, uintC count)
2082 { dotimesC(count,count,
2083 { if (!(*xptr++ == *yptr++))
2084 // verschiedene Digits gefunden
2085 return (*--xptr > *--yptr ? signean_plus : signean_minus);
2087 return signean_null; // alle Digits gleich
2092 #if !defined(LOG_LOOPS) && !CL_DS_BIG_ENDIAN_P
2095 // xor_loop_up(xptr,yptr,count);
2096 // verknüpft count (uintC>=0) Digits aufwärts ab xptr und ab yptr
2097 // mit Ziel ab xptr durch XOR.
2098 inline void xor_loop_up (uintD* xptr, const uintD* yptr, uintC count)
2099 { dotimesC(count,count, { *xptr++ ^= *yptr++; } ); }
2103 #if !defined(SHIFT_LOOPS) && CL_DS_BIG_ENDIAN_P
2105 // Schiebe- und Kopierschleife um i Bits nach links:
2106 // übertrag = shiftleftcopy_loop_up(sourceptr,destptr,count,i);
2107 // kopiert count (uintC>=0) Digits aufwärts von sourceptr nach destptr
2108 // und schiebt sie dabei um i Bits (0<i<intDsize) nach links,
2109 // wobei ganz rechts mit i Nullbits aufgefüllt wird,
2110 // und liefert den Übertrag (was links rauskommt, >=0, <2^i).
2112 inline uintD shiftleftcopy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count, uintC i)
2113 { var uintDD accu = 0;
2114 dotimesC(count,count,
2115 { accu = ((uintDD)(*sourceptr++)<<i)+accu; *destptr++ = lowD(accu);
2116 accu = (uintDD)(highD(accu));
2121 inline uintD shiftleftcopy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count, uintC i)
2122 { var uintC j = intDsize-i;
2123 var uintD carry = 0;
2124 dotimesC(count,count,
2125 { var uintD accu = *sourceptr++;
2126 *destptr++ = (accu<<i) | carry;
2135 #if !defined(SHIFT_LOOPS)
2137 // Schiebe- und XOR-Schleife:
2138 // shiftxor_loop_up(xptr,yptr,count,i);
2139 // verknüpft count+1 Digits aufwärts ab xptr mit count Digits aufwärts ab yptr,
2140 // um i Bits verschoben, durch XOR. (count uintC>=0, 0<i<intDsize)
2142 inline void shiftxor_loop_up (uintD* xptr, const uintD* yptr, uintC count, uintC i)
2144 { var uintD carry = xptr[0];
2145 dotimespC(count,count,
2146 { var uintDD accu = highlowDD(xptr[1],carry);
2147 accu = ((uintDD)(*yptr++)<<i) ^ accu;
2148 *xptr++ = lowD(accu);
2149 carry = highD(accu);
2154 inline void shiftxor_loop_up (uintD* xptr, const uintD* yptr, uintC count, uintC i)
2156 { var uintC j = intDsize-i;
2157 var uintD carry = *xptr;
2158 dotimespC(count,count,
2159 { var uintD accu = *yptr++;
2160 *xptr++ = (accu<<i) ^ carry;
2161 carry = (accu>>j) ^ *xptr;
2170 // Endianness independent names for these functions.
2171 #if CL_DS_BIG_ENDIAN_P
2172 #define copy_loop_msp copy_loop_up
2173 #define copy_loop_lsp copy_loop_down
2174 #define fill_loop_msp fill_loop_up
2175 #define fill_loop_lsp fill_loop_down
2176 #define clear_loop_msp clear_loop_up
2177 #define clear_loop_lsp clear_loop_down
2178 #define test_loop_msp test_loop_up
2179 #define or_loop_msp or_loop_up
2180 #define xor_loop_msp xor_loop_up
2181 #define and_loop_msp and_loop_up
2182 #define eqv_loop_msp eqv_loop_up
2183 #define nand_loop_msp nand_loop_up
2184 #define nor_loop_msp nor_loop_up
2185 #define andc2_loop_msp andc2_loop_up
2186 #define orc2_loop_msp orc2_loop_up
2187 #define not_loop_msp not_loop_up
2188 #define and_test_loop_msp and_test_loop_up
2189 #define compare_loop_msp compare_loop_up
2190 #define add_loop_lsp add_loop_down
2191 #define addto_loop_lsp addto_loop_down
2192 #define inc_loop_lsp inc_loop_down
2193 #define sub_loop_lsp sub_loop_down
2194 #define subx_loop_lsp subx_loop_down
2195 #define subfrom_loop_lsp subfrom_loop_down
2196 #define dec_loop_lsp dec_loop_down
2197 #define neg_loop_lsp neg_loop_down
2198 #define shift1left_loop_lsp shift1left_loop_down
2199 #define shiftleft_loop_lsp shiftleft_loop_down
2200 #define shiftleftcopy_loop_lsp shiftleftcopy_loop_down
2201 #define shift1right_loop_msp shift1right_loop_up
2202 #define shiftright_loop_msp shiftright_loop_up
2203 #define shiftrightsigned_loop_msp shiftrightsigned_loop_up
2204 #define shiftrightcopy_loop_msp shiftrightcopy_loop_up
2205 #define mulusmall_loop_lsp mulusmall_loop_down
2206 #define mulu_loop_lsp mulu_loop_down
2207 #define muluadd_loop_lsp muluadd_loop_down
2208 #define mulusub_loop_lsp mulusub_loop_down
2209 #define divu_loop_msp divu_loop_up
2210 #define divucopy_loop_msp divucopy_loop_up
2212 #define copy_loop_msp copy_loop_down
2213 #define copy_loop_lsp copy_loop_up
2214 #define fill_loop_msp fill_loop_down
2215 #define fill_loop_lsp fill_loop_up
2216 #define clear_loop_msp clear_loop_down
2217 #define clear_loop_lsp clear_loop_up
2218 #define test_loop_msp test_loop_down
2219 #define or_loop_msp or_loop_down
2220 #define xor_loop_msp xor_loop_down
2221 #define and_loop_msp and_loop_down
2222 #define eqv_loop_msp eqv_loop_down
2223 #define nand_loop_msp nand_loop_down
2224 #define nor_loop_msp nor_loop_down
2225 #define andc2_loop_msp andc2_loop_down
2226 #define orc2_loop_msp orc2_loop_down
2227 #define not_loop_msp not_loop_down
2228 #define and_test_loop_msp and_test_loop_down
2229 #define compare_loop_msp compare_loop_down
2230 #define add_loop_lsp add_loop_up
2231 #define addto_loop_lsp addto_loop_up
2232 #define inc_loop_lsp inc_loop_up
2233 #define sub_loop_lsp sub_loop_up
2234 #define subx_loop_lsp subx_loop_up
2235 #define subfrom_loop_lsp subfrom_loop_up
2236 #define dec_loop_lsp dec_loop_up
2237 #define neg_loop_lsp neg_loop_up
2238 #define shift1left_loop_lsp shift1left_loop_up
2239 #define shiftleft_loop_lsp shiftleft_loop_up
2240 #define shiftleftcopy_loop_lsp shiftleftcopy_loop_up
2241 #define shift1right_loop_msp shift1right_loop_down
2242 #define shiftright_loop_msp shiftright_loop_down
2243 #define shiftrightsigned_loop_msp shiftrightsigned_loop_down
2244 #define shiftrightcopy_loop_msp shiftrightcopy_loop_down
2245 #define mulusmall_loop_lsp mulusmall_loop_up
2246 #define mulu_loop_lsp mulu_loop_up
2247 #define muluadd_loop_lsp muluadd_loop_up
2248 #define mulusub_loop_lsp mulusub_loop_up
2249 #define divu_loop_msp divu_loop_down
2250 #define divucopy_loop_msp divucopy_loop_down
2253 // Endianness independent loops where the direction doesn't matter.
2254 #if CL_DS_BIG_ENDIAN_P
2255 #define DS_clear_loop(MSDptr,len,LSDptr) (void)clear_loop_up(MSDptr,len)
2256 #define DS_test_loop(MSDptr,len,LSDptr) test_loop_up(MSDptr,len)
2258 #define DS_clear_loop(MSDptr,len,LSDptr) (void)clear_loop_up(LSDptr,len)
2259 #define DS_test_loop(MSDptr,len,LSDptr) test_loop_up(LSDptr,len)
2263 // Umwandlungsroutinen Digit-Sequence-Teil <--> Longword:
2266 // holt die nächsten 32 Bits aus den 32/intDsize Digits ab ptr.
2267 // set_32_Dptr(ptr,wert);
2268 // speichert den Wert wert (32 Bits) in die 32/intDsize Digits ab ptr.
2269 // get_max32_Dptr(count,ptr)
2270 // holt die nächsten count Bits aus den ceiling(count/intDsize) Digits ab ptr.
2271 // set_max32_Dptr(count,ptr,wert)
2272 // speichert wert (count Bits) in die ceiling(count/intDsize) Digits ab ptr.
2273 // Jeweils ptr eine Variable vom Typ uintD*,
2274 // wert eine Variable vom Typ uint32,
2275 // count eine Variable oder constant-expression mit Wert >=0, <=32.
2277 inline uint32 get_32_Dptr (const uintD* ptr)
2279 return mspref(ptr,0);
2281 inline void set_32_Dptr (uintD* ptr, uint32 wert)
2283 mspref(ptr,0) = wert;
2285 inline uint32 get_max32_Dptr (uintC count, const uintD* ptr)
2287 return count==0 ? 0 :
2290 inline void set_max32_Dptr (uintC count, uintD* ptr, uint32 wert)
2292 if (count==0) return;
2293 mspref(ptr,0) = wert; return;
2297 inline uint32 get_32_Dptr (const uintD* ptr)
2299 return ((uint32)mspref(ptr,0)<<16) | (uint32)mspref(ptr,1);
2301 inline void set_32_Dptr (uintD* ptr, uint32 wert)
2303 mspref(ptr,0) = (uintD)(wert>>16); mspref(ptr,1) = (uintD)wert;
2305 inline uint32 get_max32_Dptr (uintC count, const uintD* ptr)
2307 return count==0 ? 0 :
2308 count<=16 ? mspref(ptr,0) :
2309 ((uint32)mspref(ptr,0)<<16) | (uint32)mspref(ptr,1);
2311 inline void set_max32_Dptr (uintC count, uintD* ptr, uint32 wert)
2313 if (count==0) return;
2314 if (count<=16) { mspref(ptr,0) = (uintD)wert; return; }
2315 mspref(ptr,0) = (uintD)(wert>>16); mspref(ptr,1) = (uintD)wert; return;
2319 inline uint32 get_32_Dptr (const uintD* ptr)
2321 return ((((((uint32)mspref(ptr,0) <<8) | (uint32)mspref(ptr,1)) <<8) | (uint32)mspref(ptr,2)) <<8) | (uint32)mspref(ptr,3);
2323 inline void set_32_Dptr (uintD* ptr, uint32 wert)
2325 mspref(ptr,0) = (uintD)(wert>>24); mspref(ptr,1) = (uintD)(wert>>16); mspref(ptr,2) = (uintD)(wert>>8); mspref(ptr,3) = (uintD)wert;
2327 inline uint32 get_max32_Dptr (uintC count, const uintD* ptr)
2329 return count==0 ? 0 :
2330 count<=8 ? mspref(ptr,0) :
2331 count<=16 ? ((uint32)mspref(ptr,0)<<8) | (uint32)mspref(ptr,1) :
2332 count<=24 ? ((((uint32)mspref(ptr,0)<<8) | (uint32)mspref(ptr,1))<<8) | (uint32)mspref(ptr,2) :
2333 ((((((uint32)mspref(ptr,0)<<8) | (uint32)mspref(ptr,1))<<8) | (uint32)mspref(ptr,2))<<8) | (uint32)mspref(ptr,3);
2335 inline void set_max32_Dptr (uintC count, uintD* ptr, uint32 wert)
2337 if (count==0) return;
2338 if (count<=8) { mspref(ptr,0) = (uintD)wert; return; }
2339 if (count<=16) { mspref(ptr,0) = (uintD)(wert>>8); mspref(ptr,1) = (uintD)wert; return; }
2340 if (count<=24) { mspref(ptr,0) = (uintD)(wert>>16); mspref(ptr,1) = (uintD)(wert>>8); mspref(ptr,2) = (uintD)wert; return; }
2341 mspref(ptr,0) = (uintD)(wert>>24); mspref(ptr,1) = (uintD)(wert>>16); mspref(ptr,2) = (uintD)(wert>>8); mspref(ptr,3) = (uintD)wert; return;
2345 #if (cl_word_size==64)
2347 // holt die nächsten 64 Bits aus den 64/intDsize Digits ab ptr.
2348 // set_64_Dptr(ptr,wert);
2349 // speichert den Wert wert (64 Bits) in die 64/intDsize Digits ab ptr.
2350 // get_max64_Dptr(count,ptr)
2351 // holt die nächsten count Bits aus den ceiling(count/intDsize) Digits ab ptr.
2352 // set_max64_Dptr(count,ptr,wert)
2353 // speichert wert (count Bits) in die ceiling(count/intDsize) Digits ab ptr.
2354 // Jeweils ptr eine Variable vom Typ uintD*,
2355 // wert eine Variable vom Typ uint64,
2356 // count eine Variable oder constant-expression mit Wert >=0, <=64.
2358 inline uint64 get_64_Dptr (const uintD* ptr)
2360 return mspref(ptr,0);
2362 inline void set_64_Dptr (uintD* ptr, uint64 wert)
2364 mspref(ptr,0) = wert;
2366 inline uint64 get_max64_Dptr (uintC count, const uintD* ptr)
2368 return count==0 ? 0 : mspref(ptr,0);
2370 inline void set_max64_Dptr (uintC count, uintD* ptr, uint64 wert)
2372 if (count==0) return;
2373 mspref(ptr,0) = wert; return;
2375 #else // (intDsize<=32)
2376 inline uint64 get_64_Dptr (const uintD* ptr)
2378 return ((uint64)get_32_Dptr(ptr) << 32) | (uint64)get_32_Dptr(ptr mspop 32/intDsize);
2380 inline void set_64_Dptr (uintD* ptr, uint64 wert)
2382 set_32_Dptr(ptr,(uint32)(wert>>32));
2383 set_32_Dptr(ptr mspop 32/intDsize,(uint32)wert);
2385 inline uint64 get_max64_Dptr (uintC count, const uintD* ptr)
2387 return count==0 ? 0 :
2388 count<=32 ? (uint64)get_max32_Dptr(count,ptr) :
2389 ((uint64)get_max32_Dptr(count-32,ptr) << 32) | (uint64)get_32_Dptr(ptr mspop ceiling(count-32,intDsize));
2391 inline void set_max64_Dptr (uintC count, uintD* ptr, uint64 wert)
2393 if (count==0) return;
2394 if (count<=32) { set_max32_Dptr(count,ptr,(uint32)wert); return; }
2395 set_max32_Dptr(count-32,ptr,(uint32)(wert>>32));
2396 set_32_Dptr(ptr mspop ceiling(count-32,intDsize),(uint32)wert); return;
2401 // get_uint1D_Dptr(ptr) holt 1 Digit (unsigned) ab ptr
2402 // get_uint2D_Dptr(ptr) holt 2 Digits (unsigned) ab ptr
2403 // get_uint3D_Dptr(ptr) holt 3 Digits (unsigned) ab ptr
2404 // get_uint4D_Dptr(ptr) holt 4 Digits (unsigned) ab ptr
2405 // get_sint1D_Dptr(ptr) holt 1 Digit (signed) ab ptr
2406 // get_sint2D_Dptr(ptr) holt 2 Digits (signed) ab ptr
2407 // get_sint3D_Dptr(ptr) holt 3 Digits (signed) ab ptr
2408 // get_sint4D_Dptr(ptr) holt 4 Digits (signed) ab ptr
2409 // Jeweils ptr eine Variable vom Typ uintD*.
2410 // NB: Bei intDsize==64 sind diese Funktionen nur sehr bedingt tauglich.
2411 inline uint32 get_uint1D_Dptr (const uintD* ptr)
2413 return lspref(ptr,0);
2415 inline sint32 get_sint1D_Dptr (const uintD* ptr)
2417 return (sint32)(sintD)lspref(ptr,0);
2420 inline uint32 get_uint2D_Dptr (const uintD* ptr)
2422 return ((uint32)lspref(ptr,1) << intDsize) | (uint32)lspref(ptr,0);
2424 inline sint32 get_sint2D_Dptr (const uintD* ptr)
2426 return ((uint32)(sint32)(sintD)lspref(ptr,1) << intDsize) | (uint32)lspref(ptr,0);
2429 #define get_uint2D_Dptr(ptr) get_uint1D_Dptr(ptr)
2430 #define get_sint2D_Dptr(ptr) (sint32)get_uint2D_Dptr(ptr)
2433 inline uint32 get_uint3D_Dptr (const uintD* ptr)
2435 return ((((uint32)lspref(ptr,2) << intDsize) | (uint32)lspref(ptr,1)) << intDsize) | (uint32)lspref(ptr,0);
2437 inline sint32 get_sint3D_Dptr (const uintD* ptr)
2439 return ((((uint32)(sint32)(sintD)lspref(ptr,2) << intDsize) | (uint32)lspref(ptr,1)) << intDsize) | (uint32)lspref(ptr,0);
2441 inline uint32 get_uint4D_Dptr (const uintD* ptr)
2443 return ((((((uint32)lspref(ptr,3) << intDsize) | (uint32)lspref(ptr,2)) << intDsize) | (uint32)lspref(ptr,1)) << intDsize) | (uint32)lspref(ptr,0);
2445 inline sint32 get_sint4D_Dptr (const uintD* ptr)
2447 return ((((((uint32)(sint32)(sintD)lspref(ptr,3) << intDsize) | (uint32)lspref(ptr,2)) << intDsize) | (uint32)lspref(ptr,1)) << intDsize) | (uint32)lspref(ptr,0);
2450 #define get_uint3D_Dptr(ptr) get_uint2D_Dptr(ptr)
2451 #define get_sint3D_Dptr(ptr) (sint32)get_uint3D_Dptr(ptr)
2452 #define get_uint4D_Dptr(ptr) get_uint2D_Dptr(ptr)
2453 #define get_sint4D_Dptr(ptr) (sint32)get_uint4D_Dptr(ptr)
2457 // NUM_STACK ist eine Art Zahlen-Stack-Pointer.
2459 // {CL_ALLOCA_STACK;
2461 // num_stack_alloc(...);
2463 // num_stack_array(...);
2466 // CL_ALLOCA_STACK rettet den aktuellen Wert von NUM_STACK.
2467 // Dann darf beliebig oft mit num_stack_alloc/num_stack_array Platz auf dem
2468 // Zahlen-Stack belegt werden.
2469 // Beim Ende des Blocks wird NUM_STACK wieder auf den vorigen Wert gesetzt,
2470 // und der Platz gilt als wieder freigegeben.
2471 // In jeder C-Funktion sollte CL_ALLOCA_STACK nur einmal aufgerufen werden.
2472 // Wegen eines GCC-Bugs sollten Funktionen, die diese Macros benutzen,
2473 // nicht inline deklariert sein.
2475 // num_stack_array(need, low_addr = , high_addr = );
2476 // num_stack_small_array(need, low_addr = , high_addr = );
2477 // belegt need Digits auf dem Zahlen-Stack und legt die untere Grenze des
2478 // allozierten Bereichs in low_addr und die obere Grenze in high_addr ab.
2479 // Jedes von beiden ist optional.
2481 // num_stack_alloc(need, MSDptr = , LSDptr = );
2482 // num_stack_small_alloc(need, MSDptr = , LSDptr = );
2483 // belegt need Digits auf dem Zahlen-Stack und legt den MSDptr und den
2484 // LSDptr ab. Jedes von beiden ist optional.
2486 // num_stack_alloc_1(need, MSDptr = , LSDptr = );
2487 // num_stack_small_alloc_1(need, MSDptr = , LSDptr = );
2488 // wie num_stack_alloc, nur daß unterhalb von MSDptr noch ein Digit Platz
2489 // zusätzlich belegt wird.
2491 #define num_stack_array(need,low_zuweisung,high_zuweisung) \
2492 {var uintL __need = (uintL)(need); \
2493 var uintD* __array = cl_alloc_array(uintD,__need); \
2494 unused (low_zuweisung &__array[0]); unused (high_zuweisung &__array[__need]); \
2496 #define num_stack_small_array(need,low_zuweisung,high_zuweisung) \
2497 {var uintL __need = (uintL)(need); \
2498 var uintD* __array = cl_small_alloc_array(uintD,__need); \
2499 unused (low_zuweisung &__array[0]); unused (high_zuweisung &__array[__need]); \
2501 #if CL_DS_BIG_ENDIAN_P
2502 #define num_stack_alloc(need,MSDptr_zuweisung,LSDptr_zuweisung) \
2503 num_stack_array(need,MSDptr_zuweisung,LSDptr_zuweisung)
2504 #define num_stack_small_alloc(need,MSDptr_zuweisung,LSDptr_zuweisung) \
2505 num_stack_small_array(need,MSDptr_zuweisung,LSDptr_zuweisung)
2506 #define num_stack_alloc_1(need,MSDptr_zuweisung,LSDptr_zuweisung) \
2507 num_stack_array((uintL)(need)+1,MSDptr_zuweisung 1 + ,LSDptr_zuweisung)
2508 #define num_stack_small_alloc_1(need,MSDptr_zuweisung,LSDptr_zuweisung) \
2509 num_stack_small_array((uintL)(need)+1,MSDptr_zuweisung 1 + ,LSDptr_zuweisung)
2511 #define num_stack_alloc(need,MSDptr_zuweisung,LSDptr_zuweisung) \
2512 num_stack_array(need,LSDptr_zuweisung,MSDptr_zuweisung)
2513 #define num_stack_small_alloc(need,MSDptr_zuweisung,LSDptr_zuweisung) \
2514 num_stack_small_array(need,LSDptr_zuweisung,MSDptr_zuweisung)
2515 #define num_stack_alloc_1(need,MSDptr_zuweisung,LSDptr_zuweisung) \
2516 num_stack_array((uintL)(need)+1,LSDptr_zuweisung,MSDptr_zuweisung -1 + )
2517 #define num_stack_small_alloc_1(need,MSDptr_zuweisung,LSDptr_zuweisung) \
2518 num_stack_small_array((uintL)(need)+1,LSDptr_zuweisung,MSDptr_zuweisung -1 + )
2522 // Macro: In der DS MSDptr/len/LSDptr wird eine 1 unterhalb des Pointers ptr
2523 // addiert. Unterhalb von MSDptr muß 1 Digit Platz sein.
2524 // Dabei ist ptr - MSDptr = count und 0 < count <= len .
2525 // Eventuell wird MSDptr erniedrigt und len erhöht.
2526 #define DS_1_plus(ptr,count) \
2527 {var uintD* ptr_from_DS_1_plus = (ptr); \
2528 var uintC count_from_DS_1_plus = (count); \
2529 loop { if (--count_from_DS_1_plus==0) /* Zähler erniedrigen */\
2530 { /* Beim Most Significant Digit angelangt */\
2531 lsprefnext(ptr_from_DS_1_plus) += 1; \
2532 /* jetzt ist ptr_from_DS_1_plus = MSDptr */\
2533 if (mspref(ptr_from_DS_1_plus,0) == (uintD)bit(intDsize-1)) \
2534 { /* 7FFF + 1 muß zu 00008000 werden: */\
2535 lsprefnext(MSDptr) = 0; \
2540 if (!((lsprefnext(ptr_from_DS_1_plus) += 1) == 0)) /* weiterincrementieren */\
2541 break; /* kein weiterer Übertrag -> Schleife abbrechen */\
2544 // Macro: In der DS MSDptr/len/LSDptr wird eine 1 unterhalb des Pointers ptr
2545 // subtrahiert. Unterhalb von MSDptr muß 1 Digit Platz sein.
2546 // Dabei ist ptr - MSDptr = count und 0 < count <= len .
2547 // Eventuell wird MSDptr erniedrigt und len erhöht.
2548 #define DS_minus1_plus(ptr,count) \
2549 {var uintD* ptr_from_DS_minus1_plus = (ptr); \
2550 var uintC count_from_DS_minus1_plus = (count); \
2551 loop { if (--count_from_DS_minus1_plus==0) /* Zähler erniedrigen */\
2552 { /* Beim Most Significant Digit angelangt */\
2553 lsprefnext(ptr_from_DS_minus1_plus) -= 1; \
2554 /* jetzt ist ptr_from_DS_minus1_plus = MSDptr */\
2555 if (mspref(ptr_from_DS_minus1_plus,0) == (uintD)bit(intDsize-1)-1) \
2556 { /* 8000 - 1 muß zu FFFF7FFF werden: */\
2557 lsprefnext(MSDptr) = (uintD)(-1); \
2562 if (!((sintD)(lsprefnext(ptr_from_DS_minus1_plus) -= 1) == -1)) /* weiterdecrementieren */\
2563 break; /* kein weiterer Übertrag -> Schleife abbrechen */\
2567 // Multiplikations-Doppelschleife:
2568 // Multipliziert zwei UDS und legt das Ergebnis in einer dritten UDS ab.
2569 // cl_UDS_mul(sourceptr1,len1,sourceptr2,len2,destptr);
2570 // multipliziert die UDS sourceptr1[-len1..-1] (len1>0)
2571 // mit der UDS sourceptr2[-len1..-1] (len2>0)
2572 // und legt das Ergebnis in der UDS destptr[-len..-1] (len=len1+len2) ab.
2573 // Unterhalb von destptr werden len Digits Platz benötigt.
2574 extern void cl_UDS_mul (const uintD* sourceptr1, uintC len1,
2575 const uintD* sourceptr2, uintC len2,
2577 // Spezialfall sourceptr1 == sourceptr2 && len1 == len2.
2578 extern void cl_UDS_mul_square (const uintD* sourceptr, uintC len,
2581 // Multipliziert zwei Unsigned-Digit-sequences.
2582 // UDS_UDS_mul_UDS(len1,LSDptr1, len2,LSDptr2, MSDptr=,len=,LSDptr=);
2583 // multipliziert die UDS ../len1/LSDptr1 und ../len2/LSDptr2.
2584 // Dabei sollte len1>0 und len2>0 sein.
2585 // Ergebnis ist die UDS MSDptr/len/LSDptr, mit len=len1+len2, im Stack.
2586 // Dabei wird num_stack erniedrigt.
2587 #define UDS_UDS_mul_UDS(len1,LSDptr1,len2,LSDptr2, MSDptr_zuweisung,len_zuweisung,LSDptr_zuweisung) \
2588 var uintL CONCAT(len_from_UDSmul_,__LINE__) = (uintL)(len1) + (uintL)(len2); \
2589 var uintD* CONCAT(LSDptr_from_UDSmul_,__LINE__); \
2590 unused (len_zuweisung CONCAT(len_from_UDSmul_,__LINE__)); \
2591 num_stack_alloc(CONCAT(len_from_UDSmul_,__LINE__),MSDptr_zuweisung,LSDptr_zuweisung CONCAT(LSDptr_from_UDSmul_,__LINE__) =); \
2592 cl_UDS_mul((LSDptr1),(len1),(LSDptr2),(len2),CONCAT(LSDptr_from_UDSmul_,__LINE__));
2594 // Multipliziert zwei Digit-sequences.
2595 // DS_DS_mul_DS(MSDptr1,len1,LSDptr1, MSDptr2,len2,LSDptr2, MSDptr=,len=,LSDptr=);
2596 // multipliziert die DS MSDptr1/len1/LSDptr1 und MSDptr2/len2/LSDptr2.
2597 // Dabei sollte len1>0 und len2>0 sein, und beide DS sollten /= 0 sein.
2598 // Alles sollten Variablen sein!
2599 // Ergebnis ist die DS MSDptr/len/LSDptr, mit len=len1+len2, im Stack.
2600 // Dabei wird num_stack erniedrigt.
2602 // Erst unsigned multiplizieren. Dann bis zu zwei Subtraktionen.
2603 // Sei b=2^intDsize, k=len1, l=len2, n=DS1, m=DS2.
2604 // Gesucht ist n * m.
2605 // Wir errechnen erst das unsigned-product p (mod b^(k+l)).
2606 // n>0, m>0: p = n*m, n*m = p
2607 // n<0, m>0: p = (n+b^k)*m, n*m + b^(k+l) = p - b^k * m (mod b^(k+l)).
2608 // n>0, m<0: p = n*(m+b^l), n*m + b^(k+l) = p - b^l * n (mod b^(k+l)).
2609 // n<0, m<0: p = (n+b^k)*(m+b^l),
2610 // n*m = p - b^k * (m+b^l) - b^l * (n+b^k) (mod b^(k+l)).
2611 #define DS_DS_mul_DS(MSDptr1,len1,LSDptr1,MSDptr2,len2,LSDptr2, MSDptr_zuweisung,len_zuweisung,LSDptr_zuweisung) \
2612 var uintD* MSDptr0; \
2613 var uintD* LSDptr0; \
2614 var uintL len_from_DSmal = (uintL)(len1) + (uintL)(len2); \
2615 unused (len_zuweisung len_from_DSmal); \
2616 num_stack_alloc(len_from_DSmal,MSDptr_zuweisung MSDptr0 =,LSDptr_zuweisung LSDptr0 =); \
2617 var uintD MSD1_from_DSmal = mspref(MSDptr1,0); \
2618 var uintD MSD2_from_DSmal = mspref(MSDptr2,0); \
2619 var uintL len1_from_DSmal = (len1); \
2620 var uintL len2_from_DSmal = (len2); \
2621 if (MSD1_from_DSmal==0) { msprefnext(MSDptr0) = 0; len1_from_DSmal--; } \
2622 if (MSD2_from_DSmal==0) { msprefnext(MSDptr0) = 0; len2_from_DSmal--; } \
2623 cl_UDS_mul((LSDptr1),len1_from_DSmal,(LSDptr2),len2_from_DSmal,LSDptr0); \
2624 if ((sintD)MSD1_from_DSmal < 0) /* n<0 ? */\
2625 /* muß m bzw. m+b^l subtrahieren, um k Digits verschoben: */\
2626 { subfrom_loop_lsp(LSDptr2,LSDptr0 lspop len1,len2); } \
2627 if ((sintD)MSD2_from_DSmal < 0) /* m<0 ? */\
2628 /* muß n bzw. n+b^k subtrahieren, um l Digits verschoben: */\
2629 { subfrom_loop_lsp(LSDptr1,LSDptr0 lspop len2,len1); }
2632 // Dividiert zwei Unsigned Digit sequences durcheinander.
2633 // UDS_divide(a_MSDptr,a_len,a_LSDptr, b_MSDptr,b_len,b_LSDptr, &q,&r);
2634 // Die UDS a = a_MSDptr/a_len/a_LSDptr (a>=0) wird durch
2635 // die UDS b = b_MSDptr/b_len/b_LSDptr (b>=0) dividiert:
2636 // a = q * b + r mit 0 <= r < b. Bei b=0 Error.
2637 // q der Quotient, r der Rest.
2638 // q = q_MSDptr/q_len/q_LSDptr, r = r_MSDptr/r_len/r_LSDptr beides
2639 // Normalized Unsigned Digit sequences.
2640 // Vorsicht: q_LSDptr <= r_MSDptr,
2641 // Vorzeichenerweiterung von r kann q zerstören!
2642 // Vorzeichenerweiterung von q ist erlaubt.
2643 // a und b werden nicht modifiziert.
2644 // num_stack wird erniedrigt.
2645 #define UDS_divide(a_MSDptr,a_len,a_LSDptr,b_MSDptr,b_len,b_LSDptr,q_,r_) \
2646 /* Platz fürs Ergebnis machen. Brauche maximal a_len+1 Digits. */\
2647 var uintC _a_len = (a_len); \
2648 var uintD* roomptr; num_stack_alloc_1(_a_len+1,roomptr=,); \
2649 cl_UDS_divide(a_MSDptr,_a_len,a_LSDptr,b_MSDptr,b_len,b_LSDptr,roomptr,q_,r_);
2650 extern void cl_UDS_divide (const uintD* a_MSDptr, uintC a_len, const uintD* a_LSDptr,
2651 const uintD* b_MSDptr, uintC b_len, const uintD* b_LSDptr,
2652 uintD* roomptr, DS* q_, DS* r_);
2655 // Bildet zu einer Unsigned Digit sequence a die Wurzel
2656 // (genauer: Gaußklammer aus Wurzel aus a).
2657 // UDS_sqrt(a_MSDptr,a_len,a_LSDptr, &b, squarep=)
2658 // > a_MSDptr/a_len/a_LSDptr: eine UDS
2659 // < NUDS b: Gaußklammer der Wurzel aus a
2660 // < squarep: cl_true falls a = b^2, cl_false falls b^2 < a < (b+1)^2.
2661 // a wird nicht modifiziert.
2662 // Vorzeichenerweiterung von b ist erlaubt.
2663 // num_stack wird erniedrigt.
2664 #define UDS_sqrt(a_MSDptr,a_len,a_LSDptr,b_,squarep_zuweisung) \
2665 { /* ceiling(a_len,2) Digits Platz fürs Ergebnis machen: */\
2666 var uintC _a_len = (a_len); \
2667 num_stack_alloc_1(ceiling(_a_len,2),(b_)->MSDptr=,); \
2668 squarep_zuweisung cl_UDS_sqrt(a_MSDptr,_a_len,a_LSDptr,b_); \
2670 extern cl_boolean cl_UDS_sqrt (const uintD* a_MSDptr, uintC a_len, const uintD* a_LSDptr, DS* b_);
2673 // Auxiliary function for approximately computing 1/x
2674 // using Newton iteration.
2675 extern void cl_UDS_recip (const uintD* a_MSDptr, uintC a_len,
2676 uintD* b_MSDptr, uintC b_len);
2678 // Auxiliary function for approximately computing 1/sqrt(x)
2679 // using Newton iteration.
2680 extern void cl_UDS_recipsqrt (const uintD* a_MSDptr, uintC a_len,
2681 uintD* b_MSDptr, uintC b_len);
2685 #endif /* _CL_DS_H */