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.
358 #if 0 // not worth it, since gmp's mpn_cmp is not optimized
359 inline cl_signean compare_loop_down (const uintD* xptr, const uintD* yptr, uintC count)
361 return mpn_cmp(xptr-count,yptr-count,count);
365 inline uintD add_loop_up (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count)
369 return mpn_add_n(destptr,sourceptr1,sourceptr2,count);
372 inline uintD addto_loop_up (const uintD* sourceptr, uintD* destptr, uintC count)
376 return mpn_add_n(destptr,destptr,sourceptr,count);
379 inline uintD inc_loop_up (uintD* ptr, uintC count)
383 return mpn_add_1(ptr,ptr,count,1);
386 inline uintD sub_loop_up (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count)
390 return mpn_sub_n(destptr,sourceptr1,sourceptr2,count);
393 inline uintD subx_loop_up (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count, uintD carry)
397 var uintD res_carry = mpn_sub_n(destptr,sourceptr1,sourceptr2,count);
399 res_carry |= mpn_sub_1(destptr,destptr,count,1);
403 inline uintD subfrom_loop_up (const uintD* sourceptr, uintD* destptr, uintC count)
407 return mpn_sub_n(destptr,destptr,sourceptr,count);
410 inline uintD dec_loop_up (uintD* ptr, uintC count)
414 return -mpn_sub_1(ptr,ptr,count,1);
417 #if !defined(ADDSUB_LOOPS)
418 // No equivalent for this in gmp. But we need this function, so write it in C.
419 inline uintD neg_loop_up (uintD* ptr, uintC count)
421 // erstes Digit /=0 suchen:
422 until (count==0) { if (!(*ptr == 0)) goto L1; ptr++; count--; }
424 L1: // erstes Digit /=0 gefunden, ab jetzt gibt's Carrys
425 *ptr = - *ptr; count--; // 1 Digit negieren
426 dotimesC(count,count, { ptr++; *ptr = ~ *ptr; } ); // alle anderen Digits invertieren
433 inline uintD shift1left_loop_up (uintD* ptr, uintC count)
437 return mpn_lshift(ptr,ptr,count,1);
440 inline uintD shiftleft_loop_up (uintD* ptr, uintC count, uintC i, uintD carry)
444 var uintD res_carry = mpn_lshift(ptr,ptr,count,i);
449 inline uintD shiftleftcopy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count, uintC i)
453 return mpn_lshift(destptr,sourceptr,count,i);
456 inline uintD shift1right_loop_down (uintD* ptr, uintC count, uintD carry)
460 var uintD res_carry = mpn_rshift(ptr-count,ptr-count,count,1);
462 ptr[-1] |= bit(intDsize-1);
466 inline uintD shiftright_loop_down (uintD* ptr, uintC count, uintC i)
470 return mpn_rshift(ptr-count,ptr-count,count,i);
473 inline uintD shiftrightsigned_loop_down (uintD* ptr, uintC count, uintC i)
475 var uintD carry = ((sintD)ptr[-1] >> (intDsize-1)) << (intDsize-i);
476 var uintD res_carry = mpn_rshift(ptr-count,ptr-count,count,i);
481 inline uintD shiftrightcopy_loop_down (const uintD* sourceptr, uintD* destptr, uintC count, uintC i, uintD carry)
483 carry = carry << (intDsize-i);
486 var uintD res_carry = mpn_rshift(destptr-count,sourceptr-count,count,i);
487 destptr[-1] |= carry;
493 inline uintD mulusmall_loop_up (uintD digit, uintD* ptr, uintC len, uintD newdigit)
497 var uintD res_carry = mpn_mul_1(ptr,ptr,len,digit);
498 res_carry += mpn_add_1(ptr,ptr,len,newdigit);
502 inline void mulu_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
504 destptr[len] = (len==0 ? 0 : mpn_mul_1(destptr,sourceptr,len,digit));
507 inline uintD muluadd_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
511 return mpn_addmul_1(destptr,sourceptr,len,digit);
514 inline uintD mulusub_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
518 return mpn_submul_1(destptr,sourceptr,len,digit);
523 inline uintD divu_loop_up (uintD digit, uintD* ptr, uintC len)
525 return mpn_divrem_1(ptr,0,ptr,len,digit);
528 inline uintD divu_loop_down (uintD digit, uintD* ptr, uintC len)
530 return mpn_divrem_1(ptr-len,0,ptr-len,len,digit);
533 inline uintD divucopy_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
535 return mpn_divrem_1(destptr,0,sourceptr,len,digit);
538 inline uintD divucopy_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
540 return mpn_divrem_1(destptr-len,0,sourceptr-len,len,digit);
545 #endif // defined(CL_USE_GMP)
548 // Define the missing functions as inline functions.
553 // destptr = copy_loop_up(sourceptr,destptr,count);
554 // kopiert count (uintC>=0) Digits aufwärts von sourceptr nach destptr
555 // und liefert das neue destptr.
556 inline uintD* copy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count)
557 { dotimesC(count,count, { *destptr++ = *sourceptr++; } );
562 // destptr = copy_loop_down(sourceptr,destptr,count);
563 // kopiert count (uintC>=0) Digits abwärts von sourceptr nach destptr
564 // und liefert das neue destptr.
565 inline uintD* copy_loop_down (const uintD* sourceptr, uintD* destptr, uintC count)
566 { dotimesC(count,count, { *--destptr = *--sourceptr; } );
575 // destptr = fill_loop_up(destptr,count,filler);
576 // kopiert count (uintC>=0) mal das Digit filler aufwärts nach destptr
577 // und liefert das neue destptr.
578 inline uintD* fill_loop_up (uintD* destptr, uintC count, uintD filler)
579 { dotimesC(count,count, { *destptr++ = filler; } );
584 // destptr = fill_loop_down(destptr,count,filler);
585 // kopiert count (uintC>=0) mal das Digit filler abwärts nach destptr
586 // und liefert das neue destptr.
587 inline uintD* fill_loop_down (uintD* destptr, uintC count, uintD filler)
588 { dotimesC(count,count, { *--destptr = filler; } );
597 // destptr = clear_loop_up(destptr,count);
598 // löscht count (uintC>=0) Digits aufwärts ab destptr
599 // und liefert das neue destptr.
600 inline uintD* clear_loop_up (uintD* destptr, uintC count)
601 { dotimesC(count,count, { *destptr++ = 0; } );
606 // destptr = clear_loop_down(destptr,count);
607 // löscht count (uintC>=0) Digits abwärts ab destptr
608 // und liefert das neue destptr.
609 inline uintD* clear_loop_down (uintD* destptr, uintC count)
610 { dotimesC(count,count, { *--destptr = 0; } );
619 // test_loop_up(ptr,count)
620 // testet count (uintC>=0) Digits aufwärts ab ptr, ob darunter eines /=0 ist.
621 // Ergebnis /=0, falls ja.
622 inline cl_boolean test_loop_up (const uintD* ptr, uintC count)
623 { dotimesC(count,count, { if (*ptr++) return cl_true; } );
628 // test_loop_down(ptr,count)
629 // testet count (uintC>=0) Digits abwärts ab ptr, ob darunter eines /=0 ist.
630 // Ergebnis /=0, falls ja.
631 inline cl_boolean test_loop_down (const uintD* ptr, uintC count)
632 { dotimesC(count,count, { if (*--ptr) return cl_true; } );
638 #if CL_DS_BIG_ENDIAN_P
643 // or_loop_up(xptr,yptr,count);
644 // verknüpft count (uintC>=0) Digits aufwärts ab xptr und ab yptr
645 // mit Ziel ab xptr durch OR.
646 inline void or_loop_up (uintD* xptr, const uintD* yptr, uintC count)
647 { dotimesC(count,count, { *xptr++ |= *yptr++; } ); }
650 // xor_loop_up(xptr,yptr,count);
651 // verknüpft count (uintC>=0) Digits aufwärts ab xptr und ab yptr
652 // mit Ziel ab xptr durch XOR.
653 inline void xor_loop_up (uintD* xptr, const uintD* yptr, uintC count)
654 { dotimesC(count,count, { *xptr++ ^= *yptr++; } ); }
657 // and_loop_up(xptr,yptr,count);
658 // verknüpft count (uintC>=0) Digits aufwärts ab xptr und ab yptr
659 // mit Ziel ab xptr durch AND.
660 inline void and_loop_up (uintD* xptr, const uintD* yptr, uintC count)
661 { dotimesC(count,count, { *xptr++ &= *yptr++; } ); }
664 // eqv_loop_up(xptr,yptr,count);
665 // verknüpft count (uintC>=0) Digits aufwärts ab xptr und ab yptr
666 // mit Ziel ab xptr durch EQV (NOT XOR).
667 inline void eqv_loop_up (uintD* xptr, const uintD* yptr, uintC count)
668 { dotimesC(count,count,
669 {var uintD temp = ~ (*xptr ^ *yptr++); *xptr++ = temp; }
674 // nand_loop_up(xptr,yptr,count);
675 // verknüpft count (uintC>=0) Digits aufwärts ab xptr und ab yptr
676 // mit Ziel ab xptr durch NAND (NOT AND).
677 inline void nand_loop_up (uintD* xptr, const uintD* yptr, uintC count)
678 { dotimesC(count,count,
679 {var uintD temp = ~ (*xptr & *yptr++); *xptr++ = temp; }
684 // nor_loop_up(xptr,yptr,count);
685 // verknüpft count (uintC>=0) Digits aufwärts ab xptr und ab yptr
686 // mit Ziel ab xptr durch NOR (NOT OR).
687 inline void nor_loop_up (uintD* xptr, const uintD* yptr, uintC count)
688 { dotimesC(count,count,
689 {var uintD temp = ~ (*xptr | *yptr++); *xptr++ = temp; }
694 // andc2_loop_up(xptr,yptr,count);
695 // verknüpft count (uintC>=0) Digits aufwärts ab xptr und ab yptr
696 // mit Ziel ab xptr durch ANDC2 (AND NOT).
697 inline void andc2_loop_up (uintD* xptr, const uintD* yptr, uintC count)
698 { dotimesC(count,count, { *xptr++ &= ~(*yptr++); } ); }
701 // orc2_loop_up(xptr,yptr,count);
702 // verknüpft count (uintC>=0) Digits aufwärts ab xptr und ab yptr
703 // mit Ziel ab xptr durch ORC2 (OR NOT).
704 inline void orc2_loop_up (uintD* xptr, const uintD* yptr, uintC count)
705 { dotimesC(count,count, { *xptr++ |= ~(*yptr++); } ); }
708 // not_loop_up(xptr,count);
709 // verknüpft count (uintC>0) Digits aufwärts ab xptr mit Ziel ab xptr
711 inline void not_loop_up (uintD* xptr, uintC count)
712 { dotimespC(count,count,
713 {var uintD temp = ~ (*xptr); *xptr++ = temp; }
721 // AND-Test-Schleife:
722 // and_test_loop_up(xptr,yptr,count);
723 // verknüpft count (uintC>=0) Digits aufwärts ab xptr und ab yptr durch AND
724 // und testet, ob sich dabei ein Digit /=0 ergibt. Ergebnis cl_true, falls ja.
725 inline cl_boolean and_test_loop_up (const uintD* xptr, const uintD* yptr, uintC count)
726 { dotimesC(count,count, { if (*xptr++ & *yptr++) return cl_true; } );
730 // Vergleichsschleife:
731 // result = compare_loop_up(xptr,yptr,count);
732 // vergleicht nacheinander xptr[0] mit yptr[0], xptr[1] mit yptr[1], usw.,
733 // insgesamt count Digits, und liefert 0 falls alle gleich sind,
734 // +1 falls zuerst ein xptr[i]>yptr[i] ist,
735 // -1 falls zuerst ein xptr[i]<yptr[i] ist.
736 inline cl_signean compare_loop_up (const uintD* xptr, const uintD* yptr, uintC count)
737 { dotimesC(count,count,
738 { if (!(*xptr++ == *yptr++))
739 // verschiedene Digits gefunden
740 return (*--xptr > *--yptr ? signean_plus : signean_minus);
742 return signean_null; // alle Digits gleich
749 // Additionsschleife:
750 // übertrag = add_loop_down(sourceptr1,sourceptr2,destptr,count);
751 // addiert count (uintC>=0) Digits abwärts von sourceptr1, von sourceptr2
752 // abwärts nach destptr und liefert den Übertrag (0 oder /=0, was 1 bedeutet).
753 inline uintD add_loop_down (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count)
757 do { source1 = *--sourceptr1;
758 source2 = *--sourceptr2;
759 *--destptr = source1 + source2;
760 if (source1 > (uintD)(~source2)) goto carry_1;
766 do { source1 = *--sourceptr1;
767 source2 = *--sourceptr2;
768 *--destptr = source1 + source2 + 1;
769 if (source1 < (uintD)(~source2)) goto carry_0;
777 // Additionsschleife:
778 // übertrag = addto_loop_down(sourceptr,destptr,count);
779 // addiert count (uintC>=0) Digits abwärts von sourceptr, von destptr
780 // abwärts nach destptr und liefert den Übertrag (0 oder /=0, was 1 bedeutet).
781 inline uintD addto_loop_down (const uintD* sourceptr, uintD* destptr, uintC count)
785 do { source1 = *--sourceptr;
786 source2 = *--destptr;
787 *destptr = source1 + source2;
788 if (source1 > (uintD)(~source2)) goto carry_1;
794 do { source1 = *--sourceptr;
795 source2 = *--destptr;
796 *destptr = source1 + source2 + 1;
797 if (source1 < (uintD)(~source2)) goto carry_0;
805 // Incrementierschleife:
806 // übertrag = inc_loop_down(ptr,count);
807 // incrementiert count (uintC>=0) Digits abwärts von ptr, so lange bis kein
808 // Übertrag mehr auftritt und liefert den Übertrag (0 oder /=0, was 1 bedeutet).
809 inline uintD inc_loop_down (uintD* ptr, uintC count)
810 { dotimesC(count,count,
811 { if (!( ++(*--ptr) == 0 )) return 0; } // kein weiterer Übertrag
813 return 1; // weiterer Übertrag
816 // Subtraktionsschleife:
817 // übertrag = sub_loop_down(sourceptr1,sourceptr2,destptr,count);
818 // subtrahiert count (uintC>=0) Digits abwärts von sourceptr1, von sourceptr2
819 // abwärts nach destptr und liefert den Übertrag (0 oder /=0, was -1 bedeutet).
820 inline uintD sub_loop_down (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count)
824 do { source1 = *--sourceptr1;
825 source2 = *--sourceptr2;
826 *--destptr = source1 - source2;
827 if (source1 < source2) goto carry_1;
833 do { source1 = *--sourceptr1;
834 source2 = *--sourceptr2;
835 *--destptr = source1 - source2 - 1;
836 if (source1 > source2) goto carry_0;
844 // Subtraktionsschleife:
845 // übertrag = subx_loop_down(sourceptr1,sourceptr2,destptr,count,carry);
846 // subtrahiert count (uintC>=0) Digits abwärts von sourceptr1 und addiert
847 // einen Carry (0 oder -1), von sourceptr2 abwärts nach destptr und
848 // liefert den Übertrag (0 oder /=0, was -1 bedeutet).
849 inline uintD subx_loop_down (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count, uintD carry)
854 do { source1 = *--sourceptr1;
855 source2 = *--sourceptr2;
856 *--destptr = source1 - source2;
857 if (source1 < source2) goto carry_1;
866 do { source1 = *--sourceptr1;
867 source2 = *--sourceptr2;
868 *--destptr = source1 - source2 - 1;
869 if (source1 > source2) goto carry_0;
877 // Subtraktionsschleife:
878 // übertrag = subfrom_loop_down(sourceptr,destptr,count);
879 // subtrahiert count (uintC>=0) Digits abwärts von sourceptr, von destptr
880 // abwärts nach destptr (dest := dest - source)
881 // und liefert den Übertrag (0 oder /=0, was -1 bedeutet).
882 inline uintD subfrom_loop_down (const uintD* sourceptr, uintD* destptr, uintC count)
886 do { source1 = *--destptr;
887 source2 = *--sourceptr;
888 *destptr = source1 - source2;
889 if (source1 < source2) goto carry_1;
895 do { source1 = *--destptr;
896 source2 = *--sourceptr;
897 *destptr = source1 - source2 - 1;
898 if (source1 > source2) goto carry_0;
906 // Decrementierschleife:
907 // übertrag = dec_loop_down(ptr,count);
908 // decrementiert count (uintC>=0) Digits abwärts von ptr, so lange bis kein
909 // Übertrag mehr auftritt und liefert den Übertrag (0 oder -1).
910 inline uintD dec_loop_down (uintD* ptr, uintC count)
911 { dotimesC(count,count,
912 { if (!( (*--ptr)-- == 0 )) return 0; } // kein weiterer Übertrag
914 return (uintD)(-1); // weiterer Übertrag
918 // übertrag = neg_loop_down(ptr,count);
919 // negiert count (uintC>=0) Digits abwärts von ptr,
920 // und liefert den Übertrag (0 oder -1).
921 inline uintD neg_loop_down (uintD* ptr, uintC count)
922 { // erstes Digit /=0 suchen:
923 until (count==0) { if (!(*--ptr == 0)) goto L1; count--; }
925 L1: // erstes Digit /=0 gefunden, ab jetzt gibt's Carrys
926 *ptr = - *ptr; count--; // 1 Digit negieren
927 dotimesC(count,count, { --ptr; *ptr = ~ *ptr; } ); // alle anderen Digits invertieren
935 // Schiebeschleife um 1 Bit nach links:
936 // übertrag = shift1left_loop_down(ptr,count);
937 // schiebt count (uintC>=0) Digits abwärts von ptr um 1 Bit nach links,
938 // und liefert den Übertrag (0 oder /=0, was 1 bedeutet).
940 inline uintD shift1left_loop_down (uintD* ptr, uintC count)
941 { var uintDD accu = 0;
942 dotimesC(count,count,
943 { accu = ((uintDD)(*--ptr)<<1)+accu; *ptr = lowD(accu);
944 accu = (uintDD)(highD(accu));
949 inline uintD shift1left_loop_down (uintD* ptr, uintC count)
950 { var uintD carry = 0;
951 dotimesC(count,count,
952 { var uintD accu = *--ptr;
953 *ptr = (accu<<1) | carry;
954 carry = accu>>(intDsize-1);
960 // Schiebeschleife um i Bits nach links:
961 // übertrag = shiftleft_loop_down(ptr,count,i,übertrag_init);
962 // schiebt count (uintC>=0) Digits abwärts von ptr um i Bits (0<i<intDsize)
963 // nach links, schiebt dabei die i Bits aus übertrag_init rechts rein,
964 // und liefert den Übertrag (was links rauskommt, >=0, <2^i).
966 inline uintD shiftleft_loop_down (uintD* ptr, uintC count, uintC i, uintD carry)
967 { var uintDD accu = (uintDD)carry;
968 dotimesC(count,count,
969 { accu = ((uintDD)(*--ptr)<<i)+accu; *ptr = lowD(accu);
970 accu = (uintDD)(highD(accu));
975 inline uintD shiftleft_loop_down (uintD* ptr, uintC count, uintC i, uintD carry)
976 { var uintC j = intDsize-i;
977 dotimesC(count,count,
978 { var uintD accu = *--ptr;
979 *ptr = (accu<<i) | carry;
986 // Schiebe- und Kopierschleife um i Bits nach links:
987 // übertrag = shiftleftcopy_loop_down(sourceptr,destptr,count,i);
988 // kopiert count (uintC>=0) Digits abwärts von sourceptr nach destptr
989 // und schiebt sie dabei um i Bits (0<i<intDsize) nach links,
990 // wobei ganz rechts mit i Nullbits aufgefüllt wird,
991 // und liefert den Übertrag (was links rauskommt, >=0, <2^i).
993 inline uintD shiftleftcopy_loop_down (const uintD* sourceptr, uintD* destptr, uintC count, uintC i)
994 { var uintDD accu = 0;
995 dotimesC(count,count,
996 { accu = ((uintDD)(*--sourceptr)<<i)+accu; *--destptr = lowD(accu);
997 accu = (uintDD)(highD(accu));
1002 inline uintD shiftleftcopy_loop_down (const uintD* sourceptr, uintD* destptr, uintC count, uintC i)
1003 { var uintC j = intDsize-i;
1004 var uintD carry = 0;
1005 dotimesC(count,count,
1006 { var uintD accu = *--sourceptr;
1007 *--destptr = (accu<<i) | carry;
1014 // Schiebeschleife um 1 Bit nach rechts:
1015 // übertrag = shift1right_loop_up(ptr,count,übertrag_init);
1016 // schiebt count (uintC>=0) Digits aufwärts von ptr um 1 Bit nach rechts,
1017 // wobei links das Bit übertrag_init (sollte =0 oder =-1 sein) hineingeschoben
1018 // wird, und liefert den Übertrag (0 oder /=0, was 1 bedeutet).
1020 inline uintD shift1right_loop_up (uintD* ptr, uintC count, uintD carry)
1021 { var uintDD accu = (sintDD)(sintD)carry & ((uintDD)1 << (2*intDsize-1)); // 0 oder bit(2*intDsize-1)
1022 dotimesC(count,count,
1023 { accu = (highlowDD_0(*ptr)>>1)+accu; *ptr++ = highD(accu);
1024 accu = highlowDD_0(lowD(accu));
1029 inline uintD shift1right_loop_up (uintD* ptr, uintC count, uintD carry)
1030 { carry = carry << (intDsize-1); // carry zu einem einzigen Bit machen
1031 dotimesC(count,count,
1032 { var uintD accu = *ptr;
1033 *ptr++ = (accu >> 1) | carry;
1034 carry = accu << (intDsize-1);
1040 // Schiebeschleife um i Bits nach rechts:
1041 // übertrag = shiftright_loop_up(ptr,count,i);
1042 // schiebt count (uintC>=0) Digits aufwärts von ptr um i Bits (0<i<intDsize)
1043 // nach rechts, wobei links Nullen eingeschoben werden,
1044 // und liefert den Übertrag (was rechts rauskommt, als Bits intDsize-1..intDsize-i).
1046 inline uintD shiftright_loop_up (uintD* ptr, uintC count, uintC i)
1047 { var uintDD accu = 0;
1048 dotimesC(count,count,
1049 { // Die oberen i Bits von (uintD)accu bilden hier den Übertrag.
1050 accu = highlowDD_0(lowD(accu));
1051 // Die oberen i Bits von (uintDD)accu bilden hier den Übertrag.
1052 accu = (highlowDD_0(*ptr)>>i)+accu; *ptr++ = highD(accu);
1057 inline uintD shiftright_loop_up (uintD* ptr, uintC count, uintC i)
1058 { var uintC j = intDsize-i;
1059 var uintD carry = 0;
1060 dotimesC(count,count,
1061 { var uintD accu = *ptr;
1062 *ptr++ = (accu >> i) | carry;
1069 // Schiebeschleife um i Bits nach rechts:
1070 // übertrag = shiftrightsigned_loop_up(ptr,count,i);
1071 // schiebt count (uintC>0) Digits aufwärts von ptr um i Bits (0<i<intDsize)
1072 // nach rechts, wobei links das MSBit ver-i-facht wird,
1073 // und liefert den Übertrag (was rechts rauskommt, als Bits intDsize-1..intDsize-i).
1075 inline uintD shiftrightsigned_loop_up (uintD* ptr, uintC count, uintC i)
1076 { var uintDD accu = // Übertrag mit i Vorzeichenbits initialisieren
1077 highlowDD_0(sign_of_sintD((sintD)(*ptr)))>>i;
1078 dotimespC(count,count,
1079 { // Die oberen i Bits von (uintD)accu bilden hier den Übertrag.
1080 accu = highlowDD_0(lowD(accu));
1081 // Die oberen i Bits von (uintDD)accu bilden hier den Übertrag.
1082 accu = (highlowDD_0(*ptr)>>i)+accu; *ptr++ = highD(accu);
1087 inline uintD shiftrightsigned_loop_up (uintD* ptr, uintC count, uintC i)
1088 { var uintC j = intDsize-i;
1090 { var uintD accu = *ptr;
1091 *ptr++ = (sintD)accu >> i;
1095 dotimesC(count,count,
1096 { var uintD accu = *ptr;
1097 *ptr++ = (accu >> i) | carry;
1104 // Schiebe- und Kopier-Schleife um i Bits nach rechts:
1105 // übertrag = shiftrightcopy_loop_up(sourceptr,destptr,count,i,carry);
1106 // kopiert count (uintC>=0) Digits aufwärts von sourceptr nach destptr
1107 // und schiebt sie dabei um i Bits (0<i<intDsize) nach rechts, wobei carry
1108 // (sozusagen als sourceptr[-1]) die i Bits ganz links bestimmt,
1109 // und liefert den Übertrag (was rechts rauskommt, als Bits intDsize-1..intDsize-i).
1111 inline uintD shiftrightcopy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count, uintC i, uintD carry)
1112 { var uintDD accu = // Übertrag mit carry initialisieren
1113 highlowDD_0(carry)>>i;
1114 dotimesC(count,count,
1115 { // Die oberen i Bits von (uintD)accu bilden hier den Übertrag.
1116 accu = highlowDD_0(lowD(accu));
1117 // Die oberen i Bits von (uintDD)accu bilden hier den Übertrag.
1118 accu = (highlowDD_0(*sourceptr++)>>i)+accu; *destptr++ = highD(accu);
1123 inline uintD shiftrightcopy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count, uintC i, uintD carry)
1124 { var uintC j = intDsize-i;
1126 dotimesC(count,count,
1127 { var uintD accu = *sourceptr++;
1128 *destptr++ = (accu >> i) | carry;
1139 // Multiplikations-Einfachschleife:
1140 // Multipliziert eine UDS mit einem kleinen Digit und addiert ein kleines Digit.
1141 // mulusmall_loop_down(digit,ptr,len,newdigit)
1142 // multipliziert die UDS ptr[-len..-1] mit digit (>=2, <=36),
1143 // addiert dabei newdigit (>=0, <digit) zur letzten Ziffer,
1144 // und liefert den Carry (>=0, <digit).
1146 inline uintD mulusmall_loop_down (uintD digit, uintD* ptr, uintC len, uintD newdigit)
1147 { var uintDD carry = newdigit;
1149 { // Hier ist 0 <= carry < digit.
1150 carry = carry + muluD(digit,*--ptr);
1151 // Hier ist 0 <= carry < 2^intDsize*digit.
1153 carry = (uintDD)highD(carry); // carry := floor(carry/2^intDsize) < digit
1158 inline uintD mulusmall_loop_down (uintD digit, uintD* ptr, uintC len, uintD newdigit)
1159 { var uintD carry = newdigit;
1161 { // Hier ist 0 <= carry < digit.
1164 muluD(digit,*--ptr,hi=,lo=);
1165 // Hier ist 0 <= 2^intDsize*hi + lo + carry < 2^intDsize*digit.
1166 lo += carry; if (lo < carry) { hi += 1; }
1174 // Multiplikations-Einfachschleife:
1175 // Multipliziert eine UDS mit einem Digit und legt das Ergebnis in einer
1177 // mulu_loop_down(digit,sourceptr,destptr,len);
1178 // multipliziert die UDS sourceptr[-len..-1] (len>0)
1179 // mit dem einzelnen digit
1180 // und legt das Ergebnis in der UDS destptr[-len-1..-1] ab.
1182 inline void mulu_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1183 { var uintDD carry = 0;
1185 { // Hier ist carry=digit=0 oder 0 <= carry < digit.
1186 carry = carry + muluD(digit,*--sourceptr);
1187 // Hier ist carry=digit=0 oder 0 <= carry < 2^intDsize*digit.
1188 *--destptr = lowD(carry);
1189 carry = (uintDD)highD(carry); // carry := floor(carry/2^intDsize) < digit
1191 *--destptr = lowD(carry);
1194 inline void mulu_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1195 { var uintD carry = 0;
1197 { // Hier ist carry=digit=0 oder 0 <= carry < digit.
1200 muluD(digit,*--sourceptr,hi=,lo=);
1201 // Hier ist 0 <= 2^intDsize*hi + lo + carry < 2^intDsize*digit oder hi=lo=carry=digit=0.
1202 lo += carry; if (lo < carry) { hi += 1; }
1210 // Multiplikations-Einfachschleife mit Akkumulation:
1211 // Multipliziert eine UDS mit einem Digit und addiert das Ergebnis zu einer
1213 // muluadd_loop_down(digit,sourceptr,destptr,len);
1214 // multipliziert die UDS sourceptr[-len..-1] (len>0)
1215 // mit dem einzelnen digit, legt das Ergebnis in der UDS destptr[-len..-1]
1216 // ab und liefert den weiteren Übertrag.
1218 inline uintD muluadd_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1219 { var uintDD carry = 0;
1221 { dotimespC(len,len,
1222 { // Hier ist 0 <= carry <= digit.
1223 carry = carry + muluD(digit,*--sourceptr) + (uintDD)*--destptr;
1224 // Hier ist 0 <= carry <= 2^intDsize*digit + 2^intDsize-1.
1225 *destptr = lowD(carry);
1226 carry = (uintDD)highD(carry); // carry := floor(carry/2^intDsize) <= digit
1232 inline uintD muluadd_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1233 { var uintD carry = 0;
1235 { dotimespC(len,len,
1236 { // Hier ist 0 <= carry <= digit.
1239 muluD(digit,*--sourceptr,hi=,lo=);
1240 // Hier ist 0 <= 2^intDsize*hi + lo + carry + *--destptr <= 2^intDsize*digit+2^intDsize-1.
1241 lo += carry; if (lo < carry) { hi += 1; }
1243 lo += carry; if (lo < carry) { hi += 1; }
1252 // Multiplikations-Einfachschleife mit Diminution:
1253 // Multipliziert eine UDS mit einem Digit und subtrahiert das Ergebnis von
1254 // einer zweiten UDS.
1255 // mulusub_loop_down(digit,sourceptr,destptr,len);
1256 // multipliziert die UDS sourceptr[-len..-1] (len>0) mit dem einzelnen
1257 // digit, subtrahiert das Ergebnis von der UDS destptr[-len..-1] und liefert
1258 // den weiteren Übertrag (>=0, evtl. von destptr[-len-1] zu subtrahieren).
1260 inline uintD mulusub_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1261 { var uintDD carry = 0;
1263 { dotimespC(len,len,
1264 { // Hier ist 0 <= carry <= digit.
1265 carry = carry + muluD(digit,*--sourceptr) + (uintD)(~(*--destptr));
1266 // Hier ist 0 <= carry <= 2^intDsize*digit + 2^intDsize-1.
1267 *destptr = ~lowD(carry);
1268 carry = (uintDD)highD(carry); // carry := floor(carry/2^intDsize) <= digit
1269 // Hier ist 0 <= carry <= digit.
1274 return 0; // nichts zu subtrahieren -> kein Übertrag
1277 inline uintD mulusub_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1278 { var uintD carry = 0;
1280 { dotimespC(len,len,
1281 { // Hier ist 0 <= carry <= digit.
1284 muluD(digit,*--sourceptr,hi=,lo=);
1285 // Hier ist 0 <= 2^intDsize*hi + lo + carry + ~(*--destptr) <= 2^intDsize*digit+2^intDsize-1.
1286 lo += carry; if (lo < carry) { hi += 1; }
1288 *destptr = carry - lo; if (carry < lo) { hi += 1; }
1294 return 0; // nichts zu subtrahieren -> kein Übertrag
1302 // Divisions-Einfachschleife:
1303 // Dividiert eine UDS durch ein Digit.
1304 // divu_loop_up(digit,ptr,len)
1305 // dividiert die UDS ptr[0..len-1] durch digit,
1306 // legt das Ergebnis in derselben UDS ab, und liefert den Rest (>=0, <digit).
1308 inline uintD divu_loop_up (uintD digit, uintD* ptr, uintC len)
1309 { var uintD rest = 0;
1311 { divuD(highlowDD(rest,*ptr),digit,*ptr =, rest =); ptr++; }
1316 inline uintD divu_loop_up (uintD digit, uintD* ptr, uintC len)
1317 { var uintD rest = 0;
1319 { divuD(rest,*ptr,digit,*ptr =, rest =); ptr++; }
1325 // Divisions-Einfachschleife:
1326 // Dividiert eine UDS durch ein Digit und legt das Ergebnis in einer
1328 // divucopy_loop_up(digit,sourceptr,destptr,len)
1329 // dividiert die UDS sourceptr[0..len-1] durch digit,
1330 // legt das Ergebnis in der UDS destptr[0..len-1] ab,
1331 // und liefert den Rest (>=0, <digit).
1333 inline uintD divucopy_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1334 { var uintD rest = 0;
1336 { divuD(highlowDD(rest,*sourceptr++),digit,*destptr++ =, rest =); }
1341 inline uintD divucopy_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1342 { var uintD rest = 0;
1344 { divuD(rest,*sourceptr++,digit,*destptr++ =, rest =); }
1352 #else // !CL_DS_BIG_ENDIAN_P
1357 // or_loop_down(xptr,yptr,count);
1358 // verknüpft count (uintC>=0) Digits abwärts ab xptr und ab yptr
1359 // mit Ziel ab xptr durch OR.
1360 inline void or_loop_down (uintD* xptr, const uintD* yptr, uintC count)
1361 { dotimesC(count,count, { *--xptr |= *--yptr; } ); }
1364 // xor_loop_down(xptr,yptr,count);
1365 // verknüpft count (uintC>=0) Digits abwärts ab xptr und ab yptr
1366 // mit Ziel ab xptr durch XOR.
1367 inline void xor_loop_down (uintD* xptr, const uintD* yptr, uintC count)
1368 { dotimesC(count,count, { *--xptr ^= *--yptr; } ); }
1371 // and_loop_down(xptr,yptr,count);
1372 // verknüpft count (uintC>=0) Digits abwärts ab xptr und ab yptr
1373 // mit Ziel ab xptr durch AND.
1374 inline void and_loop_down (uintD* xptr, const uintD* yptr, uintC count)
1375 { dotimesC(count,count, { *--xptr &= *--yptr; } ); }
1378 // eqv_loop_down(xptr,yptr,count);
1379 // verknüpft count (uintC>=0) Digits abwärts ab xptr und ab yptr
1380 // mit Ziel ab xptr durch EQV (NOT XOR).
1381 inline void eqv_loop_down (uintD* xptr, const uintD* yptr, uintC count)
1382 { dotimesC(count,count,
1383 {var uintD temp = ~ (*--xptr ^ *--yptr); *xptr = temp; }
1388 // nand_loop_down(xptr,yptr,count);
1389 // verknüpft count (uintC>=0) Digits abwärts ab xptr und ab yptr
1390 // mit Ziel ab xptr durch NAND (NOT AND).
1391 inline void nand_loop_down (uintD* xptr, const uintD* yptr, uintC count)
1392 { dotimesC(count,count,
1393 {var uintD temp = ~ (*--xptr & *--yptr); *xptr = temp; }
1398 // nor_loop_down(xptr,yptr,count);
1399 // verknüpft count (uintC>=0) Digits abwärts ab xptr und ab yptr
1400 // mit Ziel ab xptr durch NOR (NOT OR).
1401 inline void nor_loop_down (uintD* xptr, const uintD* yptr, uintC count)
1402 { dotimesC(count,count,
1403 {var uintD temp = ~ (*--xptr | *--yptr); *xptr = temp; }
1408 // andc2_loop_down(xptr,yptr,count);
1409 // verknüpft count (uintC>=0) Digits abwärts ab xptr und ab yptr
1410 // mit Ziel ab xptr durch ANDC2 (AND NOT).
1411 inline void andc2_loop_down (uintD* xptr, const uintD* yptr, uintC count)
1412 { dotimesC(count,count, { *--xptr &= ~(*--yptr); } ); }
1415 // orc2_loop_down(xptr,yptr,count);
1416 // verknüpft count (uintC>=0) Digits abwärts ab xptr und ab yptr
1417 // mit Ziel ab xptr durch ORC2 (OR NOT).
1418 inline void orc2_loop_down (uintD* xptr, const uintD* yptr, uintC count)
1419 { dotimesC(count,count, { *--xptr |= ~(*--yptr); } ); }
1422 // not_loop_down(xptr,count);
1423 // verknüpft count (uintC>0) Digits abwärts ab xptr mit Ziel ab xptr
1425 inline void not_loop_down (uintD* xptr, uintC count)
1426 { dotimespC(count,count,
1427 {var uintD temp = ~ (*--xptr); *xptr = temp; }
1435 // AND-Test-Schleife:
1436 // and_test_loop_down(xptr,yptr,count);
1437 // verknüpft count (uintC>=0) Digits abwärts ab xptr und ab yptr durch AND
1438 // und testet, ob sich dabei ein Digit /=0 ergibt. Ergebnis cl_true, falls ja.
1439 inline cl_boolean and_test_loop_down (const uintD* xptr, const uintD* yptr, uintC count)
1440 { dotimesC(count,count, { if (*--xptr & *--yptr) return cl_true; } );
1444 // Vergleichsschleife:
1445 // result = compare_loop_down(xptr,yptr,count);
1446 // vergleicht nacheinander xptr[-1] mit yptr[-1], xptr[-2] mit yptr[-2], usw.,
1447 // insgesamt count Digits, und liefert 0 falls alle gleich sind,
1448 // +1 falls zuerst ein xptr[i]>yptr[i] ist,
1449 // -1 falls zuerst ein xptr[i]<yptr[i] ist.
1450 inline cl_signean compare_loop_down (const uintD* xptr, const uintD* yptr, uintC count)
1451 { dotimesC(count,count,
1452 { if (!(*--xptr == *--yptr))
1453 // verschiedene Digits gefunden
1454 return (*xptr > *yptr ? signean_plus : signean_minus);
1456 return signean_null; // alle Digits gleich
1461 #ifndef ADDSUB_LOOPS
1463 // Additionsschleife:
1464 // übertrag = add_loop_up(sourceptr1,sourceptr2,destptr,count);
1465 // addiert count (uintC>=0) Digits aufwärts von sourceptr1, von sourceptr2
1466 // aufwärts nach destptr und liefert den Übertrag (0 oder /=0, was 1 bedeutet).
1467 inline uintD add_loop_up (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count)
1468 { var uintD source1;
1471 do { source1 = *sourceptr1++;
1472 source2 = *sourceptr2++;
1473 *destptr++ = source1 + source2;
1474 if (source1 > (uintD)(~source2)) goto carry_1;
1480 do { source1 = *sourceptr1++;
1481 source2 = *sourceptr2++;
1482 *destptr++ = source1 + source2 + 1;
1483 if (source1 < (uintD)(~source2)) goto carry_0;
1491 // Additionsschleife:
1492 // übertrag = addto_loop_up(sourceptr,destptr,count);
1493 // addiert count (uintC>=0) Digits aufwärts von sourceptr, von destptr
1494 // aufwärts nach destptr und liefert den Übertrag (0 oder /=0, was 1 bedeutet).
1495 inline uintD addto_loop_up (const uintD* sourceptr, uintD* destptr, uintC count)
1496 { var uintD source1;
1499 do { source1 = *sourceptr++;
1501 *destptr++ = source1 + source2;
1502 if (source1 > (uintD)(~source2)) goto carry_1;
1508 do { source1 = *sourceptr++;
1510 *destptr++ = source1 + source2 + 1;
1511 if (source1 < (uintD)(~source2)) goto carry_0;
1519 // Incrementierschleife:
1520 // übertrag = inc_loop_up(ptr,count);
1521 // incrementiert count (uintC>=0) Digits aufwärts von ptr, so lange bis kein
1522 // Übertrag mehr auftritt und liefert den Übertrag (0 oder /=0, was 1 bedeutet).
1523 inline uintD inc_loop_up (uintD* ptr, uintC count)
1524 { dotimesC(count,count,
1525 { if (!( ++(*ptr++) == 0 )) return 0; } // kein weiterer Übertrag
1527 return 1; // weiterer Übertrag
1530 // Subtraktionsschleife:
1531 // übertrag = sub_loop_up(sourceptr1,sourceptr2,destptr,count);
1532 // subtrahiert count (uintC>=0) Digits aufwärts von sourceptr1, von sourceptr2
1533 // aufwärts nach destptr und liefert den Übertrag (0 oder /=0, was -1 bedeutet).
1534 inline uintD sub_loop_up (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count)
1535 { var uintD source1;
1538 do { source1 = *sourceptr1++;
1539 source2 = *sourceptr2++;
1540 *destptr++ = source1 - source2;
1541 if (source1 < source2) goto carry_1;
1547 do { source1 = *sourceptr1++;
1548 source2 = *sourceptr2++;
1549 *destptr++ = source1 - source2 - 1;
1550 if (source1 > source2) goto carry_0;
1558 // Subtraktionsschleife:
1559 // übertrag = subx_loop_up(sourceptr1,sourceptr2,destptr,count,carry);
1560 // subtrahiert count (uintC>=0) Digits aufwärts von sourceptr1 und addiert
1561 // einen Carry (0 oder -1), von sourceptr2 aufwärts nach destptr und
1562 // liefert den Übertrag (0 oder /=0, was -1 bedeutet).
1563 inline uintD subx_loop_up (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count, uintD carry)
1564 { var uintD source1;
1568 do { source1 = *sourceptr1++;
1569 source2 = *sourceptr2++;
1570 *destptr++ = source1 - source2;
1571 if (source1 < source2) goto carry_1;
1580 do { source1 = *sourceptr1++;
1581 source2 = *sourceptr2++;
1582 *destptr++ = source1 - source2 - 1;
1583 if (source1 > source2) goto carry_0;
1591 // Subtraktionsschleife:
1592 // übertrag = subfrom_loop_up(sourceptr,destptr,count);
1593 // subtrahiert count (uintC>=0) Digits aufwärts von sourceptr, von destptr
1594 // aufwärts nach destptr (dest := dest - source)
1595 // und liefert den Übertrag (0 oder /=0, was -1 bedeutet).
1596 inline uintD subfrom_loop_up (const uintD* sourceptr, uintD* destptr, uintC count)
1597 { var uintD source1;
1600 do { source1 = *destptr;
1601 source2 = *sourceptr++;
1602 *destptr++ = source1 - source2;
1603 if (source1 < source2) goto carry_1;
1609 do { source1 = *destptr;
1610 source2 = *sourceptr++;
1611 *destptr++ = source1 - source2 - 1;
1612 if (source1 > source2) goto carry_0;
1620 // Decrementierschleife:
1621 // übertrag = dec_loop_up(ptr,count);
1622 // decrementiert count (uintC>=0) Digits aufwärts von ptr, so lange bis kein
1623 // Übertrag mehr auftritt und liefert den Übertrag (0 oder -1).
1624 inline uintD dec_loop_up (uintD* ptr, uintC count)
1625 { dotimesC(count,count,
1626 { if (!( (*ptr++)-- == 0 )) return 0; } // kein weiterer Übertrag
1628 return (uintD)(-1); // weiterer Übertrag
1632 // übertrag = neg_loop_up(ptr,count);
1633 // negiert count (uintC>=0) Digits aufwärts von ptr,
1634 // und liefert den Übertrag (0 oder -1).
1635 inline uintD neg_loop_up (uintD* ptr, uintC count)
1636 { // erstes Digit /=0 suchen:
1637 until (count==0) { if (!(*ptr == 0)) goto L1; ptr++; count--; }
1639 L1: // erstes Digit /=0 gefunden, ab jetzt gibt's Carrys
1640 *ptr = - *ptr; count--; // 1 Digit negieren
1641 dotimesC(count,count, { ptr++; *ptr = ~ *ptr; } ); // alle anderen Digits invertieren
1649 // Schiebeschleife um 1 Bit nach links:
1650 // übertrag = shift1left_loop_up(ptr,count);
1651 // schiebt count (uintC>=0) Digits aufwärts von ptr um 1 Bit nach links,
1652 // und liefert den Übertrag (0 oder /=0, was 1 bedeutet).
1654 inline uintD shift1left_loop_up (uintD* ptr, uintC count)
1655 { var uintDD accu = 0;
1656 dotimesC(count,count,
1657 { accu = ((uintDD)(*ptr)<<1)+accu; *ptr++ = lowD(accu);
1658 accu = (uintDD)(highD(accu));
1663 inline uintD shift1left_loop_up (uintD* ptr, uintC count)
1664 { var uintD carry = 0;
1665 dotimesC(count,count,
1666 { var uintD accu = *ptr;
1667 *ptr++ = (accu<<1) | carry;
1668 carry = accu>>(intDsize-1);
1674 // Schiebeschleife um i Bits nach links:
1675 // übertrag = shiftleft_loop_up(ptr,count,i,übertrag_init);
1676 // schiebt count (uintC>=0) Digits aufwärts von ptr um i Bits (0<i<intDsize)
1677 // nach links, schiebt dabei die i Bits aus übertrag_init rechts rein,
1678 // und liefert den Übertrag (was links rauskommt, >=0, <2^i).
1680 inline uintD shiftleft_loop_up (uintD* ptr, uintC count, uintC i, uintD carry)
1681 { var uintDD accu = (uintDD)carry;
1682 dotimesC(count,count,
1683 { accu = ((uintDD)(*ptr)<<i)+accu; *ptr++ = lowD(accu);
1684 accu = (uintDD)(highD(accu));
1689 inline uintD shiftleft_loop_up (uintD* ptr, uintC count, uintC i, uintD carry)
1690 { var uintC j = intDsize-i;
1691 dotimesC(count,count,
1692 { var uintD accu = *ptr;
1693 *ptr++ = (accu<<i) | carry;
1700 // Schiebe- und Kopierschleife um i Bits nach links:
1701 // übertrag = shiftleftcopy_loop_up(sourceptr,destptr,count,i);
1702 // kopiert count (uintC>=0) Digits aufwärts von sourceptr nach destptr
1703 // und schiebt sie dabei um i Bits (0<i<intDsize) nach links,
1704 // wobei ganz rechts mit i Nullbits aufgefüllt wird,
1705 // und liefert den Übertrag (was links rauskommt, >=0, <2^i).
1707 inline uintD shiftleftcopy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count, uintC i)
1708 { var uintDD accu = 0;
1709 dotimesC(count,count,
1710 { accu = ((uintDD)(*sourceptr++)<<i)+accu; *destptr++ = lowD(accu);
1711 accu = (uintDD)(highD(accu));
1716 inline uintD shiftleftcopy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count, uintC i)
1717 { var uintC j = intDsize-i;
1718 var uintD carry = 0;
1719 dotimesC(count,count,
1720 { var uintD accu = *sourceptr++;
1721 *destptr++ = (accu<<i) | carry;
1728 // Schiebeschleife um 1 Bit nach rechts:
1729 // übertrag = shift1right_loop_down(ptr,count,übertrag_init);
1730 // schiebt count (uintC>=0) Digits abwärts von ptr um 1 Bit nach rechts,
1731 // wobei links das Bit übertrag_init (sollte =0 oder =-1 sein) hineingeschoben
1732 // wird, und liefert den Übertrag (0 oder /=0, was 1 bedeutet).
1734 inline uintD shift1right_loop_down (uintD* ptr, uintC count, uintD carry)
1735 { var uintDD accu = (sintDD)(sintD)carry & ((uintDD)1 << (2*intDsize-1)); // 0 oder bit(2*intDsize-1)
1736 dotimesC(count,count,
1737 { accu = (highlowDD_0(*--ptr)>>1)+accu; *ptr = highD(accu);
1738 accu = highlowDD_0(lowD(accu));
1743 inline uintD shift1right_loop_down (uintD* ptr, uintC count, uintD carry)
1744 { carry = carry << (intDsize-1); // carry zu einem einzigen Bit machen
1745 dotimesC(count,count,
1746 { var uintD accu = *--ptr;
1747 *ptr = (accu >> 1) | carry;
1748 carry = accu << (intDsize-1);
1754 // Schiebeschleife um i Bits nach rechts:
1755 // übertrag = shiftright_loop_down(ptr,count,i);
1756 // schiebt count (uintC>=0) Digits abwärts von ptr um i Bits (0<i<intDsize)
1757 // nach rechts, wobei links Nullen eingeschoben werden,
1758 // und liefert den Übertrag (was rechts rauskommt, als Bits intDsize-1..intDsize-i).
1760 inline uintD shiftright_loop_down (uintD* ptr, uintC count, uintC i)
1761 { var uintDD accu = 0;
1762 dotimesC(count,count,
1763 { // Die oberen i Bits von (uintD)accu bilden hier den Übertrag.
1764 accu = highlowDD_0(lowD(accu));
1765 // Die oberen i Bits von (uintDD)accu bilden hier den Übertrag.
1766 accu = (highlowDD_0(*--ptr)>>i)+accu; *ptr = highD(accu);
1771 inline uintD shiftright_loop_down (uintD* ptr, uintC count, uintC i)
1772 { var uintC j = intDsize-i;
1773 var uintD carry = 0;
1774 dotimesC(count,count,
1775 { var uintD accu = *--ptr;
1776 *ptr = (accu >> i) | carry;
1783 // Schiebeschleife um i Bits nach rechts:
1784 // übertrag = shiftrightsigned_loop_down(ptr,count,i);
1785 // schiebt count (uintC>0) Digits abwärts von ptr um i Bits (0<i<intDsize)
1786 // nach rechts, wobei links das MSBit ver-i-facht wird,
1787 // und liefert den Übertrag (was rechts rauskommt, als Bits intDsize-1..intDsize-i).
1789 inline uintD shiftrightsigned_loop_down (uintD* ptr, uintC count, uintC i)
1790 { var uintDD accu = // Übertrag mit i Vorzeichenbits initialisieren
1791 highlowDD_0(sign_of_sintD((sintD)(ptr[-1])))>>i;
1792 dotimespC(count,count,
1793 { // Die oberen i Bits von (uintD)accu bilden hier den Übertrag.
1794 accu = highlowDD_0(lowD(accu));
1795 // Die oberen i Bits von (uintDD)accu bilden hier den Übertrag.
1796 accu = (highlowDD_0(*--ptr)>>i)+accu; *ptr = highD(accu);
1801 inline uintD shiftrightsigned_loop_down (uintD* ptr, uintC count, uintC i)
1802 { var uintC j = intDsize-i;
1804 { var uintD accu = *--ptr;
1805 *ptr = (sintD)accu >> i;
1809 dotimesC(count,count,
1810 { var uintD accu = *--ptr;
1811 *ptr = (accu >> i) | carry;
1818 // Schiebe- und Kopier-Schleife um i Bits nach rechts:
1819 // übertrag = shiftrightcopy_loop_down(sourceptr,destptr,count,i,carry);
1820 // kopiert count (uintC>=0) Digits abwärts von sourceptr nach destptr
1821 // und schiebt sie dabei um i Bits (0<i<intDsize) nach rechts, wobei carry
1822 // (sozusagen als sourceptr[0]) die i Bits ganz links bestimmt,
1823 // und liefert den Übertrag (was rechts rauskommt, als Bits intDsize-1..intDsize-i).
1825 inline uintD shiftrightcopy_loop_down (const uintD* sourceptr, uintD* destptr, uintC count, uintC i, uintD carry)
1826 { var uintDD accu = // Übertrag mit carry initialisieren
1827 highlowDD_0(carry)>>i;
1828 dotimesC(count,count,
1829 { // Die oberen i Bits von (uintD)accu bilden hier den Übertrag.
1830 accu = highlowDD_0(lowD(accu));
1831 // Die oberen i Bits von (uintDD)accu bilden hier den Übertrag.
1832 accu = (highlowDD_0(*--sourceptr)>>i)+accu; *--destptr = highD(accu);
1837 inline uintD shiftrightcopy_loop_down (const uintD* sourceptr, uintD* destptr, uintC count, uintC i, uintD carry)
1838 { var uintC j = intDsize-i;
1840 dotimesC(count,count,
1841 { var uintD accu = *--sourceptr;
1842 *--destptr = (accu >> i) | carry;
1853 // Multiplikations-Einfachschleife:
1854 // Multipliziert eine UDS mit einem kleinen Digit und addiert ein kleines Digit.
1855 // mulusmall_loop_up(digit,ptr,len,newdigit)
1856 // multipliziert die UDS ptr[0..len-1] mit digit (>=2, <=36),
1857 // addiert dabei newdigit (>=0, <digit) zur letzten Ziffer,
1858 // und liefert den Carry (>=0, <digit).
1860 inline uintD mulusmall_loop_up (uintD digit, uintD* ptr, uintC len, uintD newdigit)
1861 { var uintDD carry = newdigit;
1863 { // Hier ist 0 <= carry < digit.
1864 carry = carry + muluD(digit,*ptr);
1865 // Hier ist 0 <= carry < 2^intDsize*digit.
1866 *ptr++ = lowD(carry);
1867 carry = (uintDD)highD(carry); // carry := floor(carry/2^intDsize) < digit
1872 inline uintD mulusmall_loop_up (uintD digit, uintD* ptr, uintC len, uintD newdigit)
1873 { var uintD carry = newdigit;
1875 { // Hier ist 0 <= carry < digit.
1878 muluD(digit,*ptr,hi=,lo=);
1879 // Hier ist 0 <= 2^intDsize*hi + lo + carry < 2^intDsize*digit.
1880 lo += carry; if (lo < carry) { hi += 1; }
1888 // Multiplikations-Einfachschleife:
1889 // Multipliziert eine UDS mit einem Digit und legt das Ergebnis in einer
1891 // mulu_loop_up(digit,sourceptr,destptr,len);
1892 // multipliziert die UDS sourceptr[0..len-1] (len>0)
1893 // mit dem einzelnen digit
1894 // und legt das Ergebnis in der UDS destptr[0..len] ab.
1896 inline void mulu_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1897 { var uintDD carry = 0;
1899 { // Hier ist carry=digit=0 oder 0 <= carry < digit.
1900 carry = carry + muluD(digit,*sourceptr++);
1901 // Hier ist carry=digit=0 oder 0 <= carry < 2^intDsize*digit.
1902 *destptr++ = lowD(carry);
1903 carry = (uintDD)highD(carry); // carry := floor(carry/2^intDsize) < digit
1905 *destptr++ = lowD(carry);
1908 inline void mulu_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1909 { var uintD carry = 0;
1911 { // Hier ist carry=digit=0 oder 0 <= carry < digit.
1914 muluD(digit,*sourceptr++,hi=,lo=);
1915 // Hier ist 0 <= 2^intDsize*hi + lo + carry < 2^intDsize*digit oder hi=lo=carry=digit=0.
1916 lo += carry; if (lo < carry) { hi += 1; }
1924 // Multiplikations-Einfachschleife mit Akkumulation:
1925 // Multipliziert eine UDS mit einem Digit und addiert das Ergebnis zu einer
1927 // muluadd_loop_up(digit,sourceptr,destptr,len);
1928 // multipliziert die UDS sourceptr[0..len-1] (len>0)
1929 // mit dem einzelnen digit, legt das Ergebnis in der UDS destptr[0..len-1]
1930 // ab und liefert den weiteren Übertrag.
1932 inline uintD muluadd_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1933 { var uintDD carry = 0;
1935 { dotimespC(len,len,
1936 { // Hier ist 0 <= carry <= digit.
1937 carry = carry + muluD(digit,*sourceptr++) + (uintDD)*destptr;
1938 // Hier ist 0 <= carry <= 2^intDsize*digit + 2^intDsize-1.
1939 *destptr++ = lowD(carry);
1940 carry = (uintDD)highD(carry); // carry := floor(carry/2^intDsize) <= digit
1946 inline uintD muluadd_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1947 { var uintD carry = 0;
1949 { dotimespC(len,len,
1950 { // Hier ist 0 <= carry <= digit.
1953 muluD(digit,*sourceptr++,hi=,lo=);
1954 // Hier ist 0 <= 2^intDsize*hi + lo + carry + *destptr <= 2^intDsize*digit+2^intDsize-1.
1955 lo += carry; if (lo < carry) { hi += 1; }
1957 lo += carry; if (lo < carry) { hi += 1; }
1966 // Multiplikations-Einfachschleife mit Diminution:
1967 // Multipliziert eine UDS mit einem Digit und subtrahiert das Ergebnis von
1968 // einer zweiten UDS.
1969 // mulusub_loop_up(digit,sourceptr,destptr,len);
1970 // multipliziert die UDS sourceptr[0..len-1] (len>0) mit dem einzelnen
1971 // digit, subtrahiert das Ergebnis von der UDS destptr[0..len-1] und liefert
1972 // den weiteren Übertrag (>=0, evtl. von destptr[len] zu subtrahieren).
1974 inline uintD mulusub_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1975 { var uintDD carry = 0;
1977 { dotimespC(len,len,
1978 { // Hier ist 0 <= carry <= digit.
1979 carry = carry + muluD(digit,*sourceptr++) + (uintD)(~(*destptr));
1980 // Hier ist 0 <= carry <= 2^intDsize*digit + 2^intDsize-1.
1981 *destptr++ = ~lowD(carry);
1982 carry = (uintDD)highD(carry); // carry := floor(carry/2^intDsize) <= digit
1983 // Hier ist 0 <= carry <= digit.
1988 return 0; // nichts zu subtrahieren -> kein Übertrag
1991 inline uintD mulusub_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1992 { var uintD carry = 0;
1994 { dotimespC(len,len,
1995 { // Hier ist 0 <= carry <= digit.
1998 muluD(digit,*sourceptr++,hi=,lo=);
1999 // Hier ist 0 <= 2^intDsize*hi + lo + carry + ~(*destptr) <= 2^intDsize*digit+2^intDsize-1.
2000 lo += carry; if (lo < carry) { hi += 1; }
2002 *destptr++ = carry - lo; if (carry < lo) { hi += 1; }
2008 return 0; // nichts zu subtrahieren -> kein Übertrag
2016 // Divisions-Einfachschleife:
2017 // Dividiert eine UDS durch ein Digit.
2018 // divu_loop_down(digit,ptr,len)
2019 // dividiert die UDS ptr[-len..-1] durch digit,
2020 // legt das Ergebnis in derselben UDS ab, und liefert den Rest (>=0, <digit).
2022 inline uintD divu_loop_down (uintD digit, uintD* ptr, uintC len)
2023 { var uintD rest = 0;
2025 { --ptr; divuD(highlowDD(rest,*ptr),digit,*ptr =, rest =); }
2030 inline uintD divu_loop_down (uintD digit, uintD* ptr, uintC len)
2031 { var uintD rest = 0;
2033 { --ptr; divuD(rest,*ptr,digit,*ptr =, rest =); }
2039 // Divisions-Einfachschleife:
2040 // Dividiert eine UDS durch ein Digit und legt das Ergebnis in einer
2042 // divucopy_loop_down(digit,sourceptr,destptr,len)
2043 // dividiert die UDS sourceptr[-len..-1] durch digit,
2044 // legt das Ergebnis in der UDS destptr[-len..-1] ab,
2045 // und liefert den Rest (>=0, <digit).
2047 inline uintD divucopy_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
2048 { var uintD rest = 0;
2050 { divuD(highlowDD(rest,*--sourceptr),digit,*--destptr =, rest =); }
2055 inline uintD divucopy_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
2056 { var uintD rest = 0;
2058 { divuD(rest,*--sourceptr,digit,*--destptr =, rest =); }
2066 #endif // !CL_DS_BIG_ENDIAN_P
2068 #if !defined(TEST_LOOPS) && !CL_DS_BIG_ENDIAN_P
2070 // Vergleichsschleife:
2071 // result = compare_loop_up(xptr,yptr,count);
2072 // vergleicht nacheinander xptr[0] mit yptr[0], xptr[1] mit yptr[1], usw.,
2073 // insgesamt count Digits, und liefert 0 falls alle gleich sind,
2074 // +1 falls zuerst ein xptr[i]>yptr[i] ist,
2075 // -1 falls zuerst ein xptr[i]<yptr[i] ist.
2076 inline cl_signean compare_loop_up (const uintD* xptr, const uintD* yptr, uintC count)
2077 { dotimesC(count,count,
2078 { if (!(*xptr++ == *yptr++))
2079 // verschiedene Digits gefunden
2080 return (*--xptr > *--yptr ? signean_plus : signean_minus);
2082 return signean_null; // alle Digits gleich
2087 #if !defined(LOG_LOOPS) && !CL_DS_BIG_ENDIAN_P
2090 // xor_loop_up(xptr,yptr,count);
2091 // verknüpft count (uintC>=0) Digits aufwärts ab xptr und ab yptr
2092 // mit Ziel ab xptr durch XOR.
2093 inline void xor_loop_up (uintD* xptr, const uintD* yptr, uintC count)
2094 { dotimesC(count,count, { *xptr++ ^= *yptr++; } ); }
2098 #if !defined(SHIFT_LOOPS) && CL_DS_BIG_ENDIAN_P
2100 // Schiebe- und Kopierschleife um i Bits nach links:
2101 // übertrag = shiftleftcopy_loop_up(sourceptr,destptr,count,i);
2102 // kopiert count (uintC>=0) Digits aufwärts von sourceptr nach destptr
2103 // und schiebt sie dabei um i Bits (0<i<intDsize) nach links,
2104 // wobei ganz rechts mit i Nullbits aufgefüllt wird,
2105 // und liefert den Übertrag (was links rauskommt, >=0, <2^i).
2107 inline uintD shiftleftcopy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count, uintC i)
2108 { var uintDD accu = 0;
2109 dotimesC(count,count,
2110 { accu = ((uintDD)(*sourceptr++)<<i)+accu; *destptr++ = lowD(accu);
2111 accu = (uintDD)(highD(accu));
2116 inline uintD shiftleftcopy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count, uintC i)
2117 { var uintC j = intDsize-i;
2118 var uintD carry = 0;
2119 dotimesC(count,count,
2120 { var uintD accu = *sourceptr++;
2121 *destptr++ = (accu<<i) | carry;
2130 #if !defined(SHIFT_LOOPS)
2132 // Schiebe- und XOR-Schleife:
2133 // shiftxor_loop_up(xptr,yptr,count,i);
2134 // verknüpft count+1 Digits aufwärts ab xptr mit count Digits aufwärts ab yptr,
2135 // um i Bits verschoben, durch XOR. (count uintC>=0, 0<i<intDsize)
2137 inline void shiftxor_loop_up (uintD* xptr, const uintD* yptr, uintC count, uintC i)
2139 { var uintD carry = xptr[0];
2140 dotimespC(count,count,
2141 { var uintDD accu = highlowDD(xptr[1],carry);
2142 accu = ((uintDD)(*yptr++)<<i) ^ accu;
2143 *xptr++ = lowD(accu);
2144 carry = highD(accu);
2149 inline void shiftxor_loop_up (uintD* xptr, const uintD* yptr, uintC count, uintC i)
2151 { var uintC j = intDsize-i;
2152 var uintD carry = *xptr;
2153 dotimespC(count,count,
2154 { var uintD accu = *yptr++;
2155 *xptr++ = (accu<<i) ^ carry;
2156 carry = (accu>>j) ^ *xptr;
2165 // Endianness independent names for these functions.
2166 #if CL_DS_BIG_ENDIAN_P
2167 #define copy_loop_msp copy_loop_up
2168 #define copy_loop_lsp copy_loop_down
2169 #define fill_loop_msp fill_loop_up
2170 #define fill_loop_lsp fill_loop_down
2171 #define clear_loop_msp clear_loop_up
2172 #define clear_loop_lsp clear_loop_down
2173 #define test_loop_msp test_loop_up
2174 #define or_loop_msp or_loop_up
2175 #define xor_loop_msp xor_loop_up
2176 #define and_loop_msp and_loop_up
2177 #define eqv_loop_msp eqv_loop_up
2178 #define nand_loop_msp nand_loop_up
2179 #define nor_loop_msp nor_loop_up
2180 #define andc2_loop_msp andc2_loop_up
2181 #define orc2_loop_msp orc2_loop_up
2182 #define not_loop_msp not_loop_up
2183 #define and_test_loop_msp and_test_loop_up
2184 #define compare_loop_msp compare_loop_up
2185 #define add_loop_lsp add_loop_down
2186 #define addto_loop_lsp addto_loop_down
2187 #define inc_loop_lsp inc_loop_down
2188 #define sub_loop_lsp sub_loop_down
2189 #define subx_loop_lsp subx_loop_down
2190 #define subfrom_loop_lsp subfrom_loop_down
2191 #define dec_loop_lsp dec_loop_down
2192 #define neg_loop_lsp neg_loop_down
2193 #define shift1left_loop_lsp shift1left_loop_down
2194 #define shiftleft_loop_lsp shiftleft_loop_down
2195 #define shiftleftcopy_loop_lsp shiftleftcopy_loop_down
2196 #define shift1right_loop_msp shift1right_loop_up
2197 #define shiftright_loop_msp shiftright_loop_up
2198 #define shiftrightsigned_loop_msp shiftrightsigned_loop_up
2199 #define shiftrightcopy_loop_msp shiftrightcopy_loop_up
2200 #define mulusmall_loop_lsp mulusmall_loop_down
2201 #define mulu_loop_lsp mulu_loop_down
2202 #define muluadd_loop_lsp muluadd_loop_down
2203 #define mulusub_loop_lsp mulusub_loop_down
2204 #define divu_loop_msp divu_loop_up
2205 #define divucopy_loop_msp divucopy_loop_up
2207 #define copy_loop_msp copy_loop_down
2208 #define copy_loop_lsp copy_loop_up
2209 #define fill_loop_msp fill_loop_down
2210 #define fill_loop_lsp fill_loop_up
2211 #define clear_loop_msp clear_loop_down
2212 #define clear_loop_lsp clear_loop_up
2213 #define test_loop_msp test_loop_down
2214 #define or_loop_msp or_loop_down
2215 #define xor_loop_msp xor_loop_down
2216 #define and_loop_msp and_loop_down
2217 #define eqv_loop_msp eqv_loop_down
2218 #define nand_loop_msp nand_loop_down
2219 #define nor_loop_msp nor_loop_down
2220 #define andc2_loop_msp andc2_loop_down
2221 #define orc2_loop_msp orc2_loop_down
2222 #define not_loop_msp not_loop_down
2223 #define and_test_loop_msp and_test_loop_down
2224 #define compare_loop_msp compare_loop_down
2225 #define add_loop_lsp add_loop_up
2226 #define addto_loop_lsp addto_loop_up
2227 #define inc_loop_lsp inc_loop_up
2228 #define sub_loop_lsp sub_loop_up
2229 #define subx_loop_lsp subx_loop_up
2230 #define subfrom_loop_lsp subfrom_loop_up
2231 #define dec_loop_lsp dec_loop_up
2232 #define neg_loop_lsp neg_loop_up
2233 #define shift1left_loop_lsp shift1left_loop_up
2234 #define shiftleft_loop_lsp shiftleft_loop_up
2235 #define shiftleftcopy_loop_lsp shiftleftcopy_loop_up
2236 #define shift1right_loop_msp shift1right_loop_down
2237 #define shiftright_loop_msp shiftright_loop_down
2238 #define shiftrightsigned_loop_msp shiftrightsigned_loop_down
2239 #define shiftrightcopy_loop_msp shiftrightcopy_loop_down
2240 #define mulusmall_loop_lsp mulusmall_loop_up
2241 #define mulu_loop_lsp mulu_loop_up
2242 #define muluadd_loop_lsp muluadd_loop_up
2243 #define mulusub_loop_lsp mulusub_loop_up
2244 #define divu_loop_msp divu_loop_down
2245 #define divucopy_loop_msp divucopy_loop_down
2248 // Endianness independent loops where the direction doesn't matter.
2249 #if CL_DS_BIG_ENDIAN_P
2250 #define DS_clear_loop(MSDptr,len,LSDptr) (void)clear_loop_up(MSDptr,len)
2251 #define DS_test_loop(MSDptr,len,LSDptr) test_loop_up(MSDptr,len)
2253 #define DS_clear_loop(MSDptr,len,LSDptr) (void)clear_loop_up(LSDptr,len)
2254 #define DS_test_loop(MSDptr,len,LSDptr) test_loop_up(LSDptr,len)
2258 // Umwandlungsroutinen Digit-Sequence-Teil <--> Longword:
2261 // holt die nächsten 32 Bits aus den 32/intDsize Digits ab ptr.
2262 // set_32_Dptr(ptr,wert);
2263 // speichert den Wert wert (32 Bits) in die 32/intDsize Digits ab ptr.
2264 // get_max32_Dptr(count,ptr)
2265 // holt die nächsten count Bits aus den ceiling(count/intDsize) Digits ab ptr.
2266 // set_max32_Dptr(count,ptr,wert)
2267 // speichert wert (count Bits) in die ceiling(count/intDsize) Digits ab ptr.
2268 // Jeweils ptr eine Variable vom Typ uintD*,
2269 // wert eine Variable vom Typ uint32,
2270 // count eine Variable oder constant-expression mit Wert >=0, <=32.
2272 inline uint32 get_32_Dptr (const uintD* ptr)
2274 return mspref(ptr,0);
2276 inline void set_32_Dptr (uintD* ptr, uint32 wert)
2278 mspref(ptr,0) = wert;
2280 inline uint32 get_max32_Dptr (uintC count, const uintD* ptr)
2282 return count==0 ? 0 :
2285 inline void set_max32_Dptr (uintC count, uintD* ptr, uint32 wert)
2287 if (count==0) return;
2288 mspref(ptr,0) = wert; return;
2292 inline uint32 get_32_Dptr (const uintD* ptr)
2294 return ((uint32)mspref(ptr,0)<<16) | (uint32)mspref(ptr,1);
2296 inline void set_32_Dptr (uintD* ptr, uint32 wert)
2298 mspref(ptr,0) = (uintD)(wert>>16); mspref(ptr,1) = (uintD)wert;
2300 inline uint32 get_max32_Dptr (uintC count, const uintD* ptr)
2302 return count==0 ? 0 :
2303 count<=16 ? mspref(ptr,0) :
2304 ((uint32)mspref(ptr,0)<<16) | (uint32)mspref(ptr,1);
2306 inline void set_max32_Dptr (uintC count, uintD* ptr, uint32 wert)
2308 if (count==0) return;
2309 if (count<=16) { mspref(ptr,0) = (uintD)wert; return; }
2310 mspref(ptr,0) = (uintD)(wert>>16); mspref(ptr,1) = (uintD)wert; return;
2314 inline uint32 get_32_Dptr (const uintD* ptr)
2316 return ((((((uint32)mspref(ptr,0) <<8) | (uint32)mspref(ptr,1)) <<8) | (uint32)mspref(ptr,2)) <<8) | (uint32)mspref(ptr,3);
2318 inline void set_32_Dptr (uintD* ptr, uint32 wert)
2320 mspref(ptr,0) = (uintD)(wert>>24); mspref(ptr,1) = (uintD)(wert>>16); mspref(ptr,2) = (uintD)(wert>>8); mspref(ptr,3) = (uintD)wert;
2322 inline uint32 get_max32_Dptr (uintC count, const uintD* ptr)
2324 return count==0 ? 0 :
2325 count<=8 ? mspref(ptr,0) :
2326 count<=16 ? ((uint32)mspref(ptr,0)<<8) | (uint32)mspref(ptr,1) :
2327 count<=24 ? ((((uint32)mspref(ptr,0)<<8) | (uint32)mspref(ptr,1))<<8) | (uint32)mspref(ptr,2) :
2328 ((((((uint32)mspref(ptr,0)<<8) | (uint32)mspref(ptr,1))<<8) | (uint32)mspref(ptr,2))<<8) | (uint32)mspref(ptr,3);
2330 inline void set_max32_Dptr (uintC count, uintD* ptr, uint32 wert)
2332 if (count==0) return;
2333 if (count<=8) { mspref(ptr,0) = (uintD)wert; return; }
2334 if (count<=16) { mspref(ptr,0) = (uintD)(wert>>8); mspref(ptr,1) = (uintD)wert; return; }
2335 if (count<=24) { mspref(ptr,0) = (uintD)(wert>>16); mspref(ptr,1) = (uintD)(wert>>8); mspref(ptr,2) = (uintD)wert; return; }
2336 mspref(ptr,0) = (uintD)(wert>>24); mspref(ptr,1) = (uintD)(wert>>16); mspref(ptr,2) = (uintD)(wert>>8); mspref(ptr,3) = (uintD)wert; return;
2340 #if (cl_word_size==64)
2342 // holt die nächsten 64 Bits aus den 64/intDsize Digits ab ptr.
2343 // set_64_Dptr(ptr,wert);
2344 // speichert den Wert wert (64 Bits) in die 64/intDsize Digits ab ptr.
2345 // get_max64_Dptr(count,ptr)
2346 // holt die nächsten count Bits aus den ceiling(count/intDsize) Digits ab ptr.
2347 // set_max64_Dptr(count,ptr,wert)
2348 // speichert wert (count Bits) in die ceiling(count/intDsize) Digits ab ptr.
2349 // Jeweils ptr eine Variable vom Typ uintD*,
2350 // wert eine Variable vom Typ uint64,
2351 // count eine Variable oder constant-expression mit Wert >=0, <=64.
2353 inline uint64 get_64_Dptr (const uintD* ptr)
2355 return mspref(ptr,0);
2357 inline void set_64_Dptr (uintD* ptr, uint64 wert)
2359 mspref(ptr,0) = wert;
2361 inline uint64 get_max64_Dptr (uintC count, const uintD* ptr)
2363 return count==0 ? 0 : mspref(ptr,0);
2365 inline void set_max64_Dptr (uintC count, uintD* ptr, uint64 wert)
2367 if (count==0) return;
2368 mspref(ptr,0) = wert; return;
2370 #else // (intDsize<=32)
2371 inline uint64 get_64_Dptr (const uintD* ptr)
2373 return ((uint64)get_32_Dptr(ptr) << 32) | (uint64)get_32_Dptr(ptr mspop 32/intDsize);
2375 inline void set_64_Dptr (uintD* ptr, uint64 wert)
2377 set_32_Dptr(ptr,(uint32)(wert>>32));
2378 set_32_Dptr(ptr mspop 32/intDsize,(uint32)wert);
2380 inline uint64 get_max64_Dptr (uintC count, const uintD* ptr)
2382 return count==0 ? 0 :
2383 count<=32 ? (uint64)get_max32_Dptr(count,ptr) :
2384 ((uint64)get_max32_Dptr(count-32,ptr) << 32) | (uint64)get_32_Dptr(ptr mspop ceiling(count-32,intDsize));
2386 inline void set_max64_Dptr (uintC count, uintD* ptr, uint64 wert)
2388 if (count==0) return;
2389 if (count<=32) { set_max32_Dptr(count,ptr,(uint32)wert); return; }
2390 set_max32_Dptr(count-32,ptr,(uint32)(wert>>32));
2391 set_32_Dptr(ptr mspop ceiling(count-32,intDsize),(uint32)wert); return;
2396 // get_uint1D_Dptr(ptr) holt 1 Digit (unsigned) ab ptr
2397 // get_uint2D_Dptr(ptr) holt 2 Digits (unsigned) ab ptr
2398 // get_uint3D_Dptr(ptr) holt 3 Digits (unsigned) ab ptr
2399 // get_uint4D_Dptr(ptr) holt 4 Digits (unsigned) ab ptr
2400 // get_sint1D_Dptr(ptr) holt 1 Digit (signed) ab ptr
2401 // get_sint2D_Dptr(ptr) holt 2 Digits (signed) ab ptr
2402 // get_sint3D_Dptr(ptr) holt 3 Digits (signed) ab ptr
2403 // get_sint4D_Dptr(ptr) holt 4 Digits (signed) ab ptr
2404 // Jeweils ptr eine Variable vom Typ uintD*.
2405 // NB: Bei intDsize==64 sind diese Funktionen nur sehr bedingt tauglich.
2406 inline uint32 get_uint1D_Dptr (const uintD* ptr)
2408 return lspref(ptr,0);
2410 inline sint32 get_sint1D_Dptr (const uintD* ptr)
2412 return (sint32)(sintD)lspref(ptr,0);
2415 inline uint32 get_uint2D_Dptr (const uintD* ptr)
2417 return ((uint32)lspref(ptr,1) << intDsize) | (uint32)lspref(ptr,0);
2419 inline sint32 get_sint2D_Dptr (const uintD* ptr)
2421 return ((uint32)(sint32)(sintD)lspref(ptr,1) << intDsize) | (uint32)lspref(ptr,0);
2424 #define get_uint2D_Dptr(ptr) get_uint1D_Dptr(ptr)
2425 #define get_sint2D_Dptr(ptr) (sint32)get_uint2D_Dptr(ptr)
2428 inline uint32 get_uint3D_Dptr (const uintD* ptr)
2430 return ((((uint32)lspref(ptr,2) << intDsize) | (uint32)lspref(ptr,1)) << intDsize) | (uint32)lspref(ptr,0);
2432 inline sint32 get_sint3D_Dptr (const uintD* ptr)
2434 return ((((uint32)(sint32)(sintD)lspref(ptr,2) << intDsize) | (uint32)lspref(ptr,1)) << intDsize) | (uint32)lspref(ptr,0);
2436 inline uint32 get_uint4D_Dptr (const uintD* ptr)
2438 return ((((((uint32)lspref(ptr,3) << intDsize) | (uint32)lspref(ptr,2)) << intDsize) | (uint32)lspref(ptr,1)) << intDsize) | (uint32)lspref(ptr,0);
2440 inline sint32 get_sint4D_Dptr (const uintD* ptr)
2442 return ((((((uint32)(sint32)(sintD)lspref(ptr,3) << intDsize) | (uint32)lspref(ptr,2)) << intDsize) | (uint32)lspref(ptr,1)) << intDsize) | (uint32)lspref(ptr,0);
2445 #define get_uint3D_Dptr(ptr) get_uint2D_Dptr(ptr)
2446 #define get_sint3D_Dptr(ptr) (sint32)get_uint3D_Dptr(ptr)
2447 #define get_uint4D_Dptr(ptr) get_uint2D_Dptr(ptr)
2448 #define get_sint4D_Dptr(ptr) (sint32)get_uint4D_Dptr(ptr)
2452 // NUM_STACK ist eine Art Zahlen-Stack-Pointer.
2454 // {CL_ALLOCA_STACK;
2456 // num_stack_alloc(...);
2458 // num_stack_array(...);
2461 // CL_ALLOCA_STACK rettet den aktuellen Wert von NUM_STACK.
2462 // Dann darf beliebig oft mit num_stack_alloc/num_stack_array Platz auf dem
2463 // Zahlen-Stack belegt werden.
2464 // Beim Ende des Blocks wird NUM_STACK wieder auf den vorigen Wert gesetzt,
2465 // und der Platz gilt als wieder freigegeben.
2466 // In jeder C-Funktion sollte CL_ALLOCA_STACK nur einmal aufgerufen werden.
2467 // Wegen eines GCC-Bugs sollten Funktionen, die diese Macros benutzen,
2468 // nicht inline deklariert sein.
2470 // num_stack_array(need, low_addr = , high_addr = );
2471 // num_stack_small_array(need, low_addr = , high_addr = );
2472 // belegt need Digits auf dem Zahlen-Stack und legt die untere Grenze des
2473 // allozierten Bereichs in low_addr und die obere Grenze in high_addr ab.
2474 // Jedes von beiden ist optional.
2476 // num_stack_alloc(need, MSDptr = , LSDptr = );
2477 // num_stack_small_alloc(need, MSDptr = , LSDptr = );
2478 // belegt need Digits auf dem Zahlen-Stack und legt den MSDptr und den
2479 // LSDptr ab. Jedes von beiden ist optional.
2481 // num_stack_alloc_1(need, MSDptr = , LSDptr = );
2482 // num_stack_small_alloc_1(need, MSDptr = , LSDptr = );
2483 // wie num_stack_alloc, nur daß unterhalb von MSDptr noch ein Digit Platz
2484 // zusätzlich belegt wird.
2486 #define num_stack_array(need,low_zuweisung,high_zuweisung) \
2487 {var uintL __need = (uintL)(need); \
2488 var uintD* __array = cl_alloc_array(uintD,__need); \
2489 unused (low_zuweisung &__array[0]); unused (high_zuweisung &__array[__need]); \
2491 #define num_stack_small_array(need,low_zuweisung,high_zuweisung) \
2492 {var uintL __need = (uintL)(need); \
2493 var uintD* __array = cl_small_alloc_array(uintD,__need); \
2494 unused (low_zuweisung &__array[0]); unused (high_zuweisung &__array[__need]); \
2496 #if CL_DS_BIG_ENDIAN_P
2497 #define num_stack_alloc(need,MSDptr_zuweisung,LSDptr_zuweisung) \
2498 num_stack_array(need,MSDptr_zuweisung,LSDptr_zuweisung)
2499 #define num_stack_small_alloc(need,MSDptr_zuweisung,LSDptr_zuweisung) \
2500 num_stack_small_array(need,MSDptr_zuweisung,LSDptr_zuweisung)
2501 #define num_stack_alloc_1(need,MSDptr_zuweisung,LSDptr_zuweisung) \
2502 num_stack_array((uintL)(need)+1,MSDptr_zuweisung 1 + ,LSDptr_zuweisung)
2503 #define num_stack_small_alloc_1(need,MSDptr_zuweisung,LSDptr_zuweisung) \
2504 num_stack_small_array((uintL)(need)+1,MSDptr_zuweisung 1 + ,LSDptr_zuweisung)
2506 #define num_stack_alloc(need,MSDptr_zuweisung,LSDptr_zuweisung) \
2507 num_stack_array(need,LSDptr_zuweisung,MSDptr_zuweisung)
2508 #define num_stack_small_alloc(need,MSDptr_zuweisung,LSDptr_zuweisung) \
2509 num_stack_small_array(need,LSDptr_zuweisung,MSDptr_zuweisung)
2510 #define num_stack_alloc_1(need,MSDptr_zuweisung,LSDptr_zuweisung) \
2511 num_stack_array((uintL)(need)+1,LSDptr_zuweisung,MSDptr_zuweisung -1 + )
2512 #define num_stack_small_alloc_1(need,MSDptr_zuweisung,LSDptr_zuweisung) \
2513 num_stack_small_array((uintL)(need)+1,LSDptr_zuweisung,MSDptr_zuweisung -1 + )
2517 // Macro: In der DS MSDptr/len/LSDptr wird eine 1 unterhalb des Pointers ptr
2518 // addiert. Unterhalb von MSDptr muß 1 Digit Platz sein.
2519 // Dabei ist ptr - MSDptr = count und 0 < count <= len .
2520 // Eventuell wird MSDptr erniedrigt und len erhöht.
2521 #define DS_1_plus(ptr,count) \
2522 {var uintD* ptr_from_DS_1_plus = (ptr); \
2523 var uintC count_from_DS_1_plus = (count); \
2524 loop { if (--count_from_DS_1_plus==0) /* Zähler erniedrigen */\
2525 { /* Beim Most Significant Digit angelangt */\
2526 lsprefnext(ptr_from_DS_1_plus) += 1; \
2527 /* jetzt ist ptr_from_DS_1_plus = MSDptr */\
2528 if (mspref(ptr_from_DS_1_plus,0) == (uintD)bit(intDsize-1)) \
2529 { /* 7FFF + 1 muß zu 00008000 werden: */\
2530 lsprefnext(MSDptr) = 0; \
2535 if (!((lsprefnext(ptr_from_DS_1_plus) += 1) == 0)) /* weiterincrementieren */\
2536 break; /* kein weiterer Übertrag -> Schleife abbrechen */\
2539 // Macro: In der DS MSDptr/len/LSDptr wird eine 1 unterhalb des Pointers ptr
2540 // subtrahiert. Unterhalb von MSDptr muß 1 Digit Platz sein.
2541 // Dabei ist ptr - MSDptr = count und 0 < count <= len .
2542 // Eventuell wird MSDptr erniedrigt und len erhöht.
2543 #define DS_minus1_plus(ptr,count) \
2544 {var uintD* ptr_from_DS_minus1_plus = (ptr); \
2545 var uintC count_from_DS_minus1_plus = (count); \
2546 loop { if (--count_from_DS_minus1_plus==0) /* Zähler erniedrigen */\
2547 { /* Beim Most Significant Digit angelangt */\
2548 lsprefnext(ptr_from_DS_minus1_plus) -= 1; \
2549 /* jetzt ist ptr_from_DS_minus1_plus = MSDptr */\
2550 if (mspref(ptr_from_DS_minus1_plus,0) == (uintD)bit(intDsize-1)-1) \
2551 { /* 8000 - 1 muß zu FFFF7FFF werden: */\
2552 lsprefnext(MSDptr) = (uintD)(-1); \
2557 if (!((sintD)(lsprefnext(ptr_from_DS_minus1_plus) -= 1) == -1)) /* weiterdecrementieren */\
2558 break; /* kein weiterer Übertrag -> Schleife abbrechen */\
2562 // Multiplikations-Doppelschleife:
2563 // Multipliziert zwei UDS und legt das Ergebnis in einer dritten UDS ab.
2564 // cl_UDS_mul(sourceptr1,len1,sourceptr2,len2,destptr);
2565 // multipliziert die UDS sourceptr1[-len1..-1] (len1>0)
2566 // mit der UDS sourceptr2[-len1..-1] (len2>0)
2567 // und legt das Ergebnis in der UDS destptr[-len..-1] (len=len1+len2) ab.
2568 // Unterhalb von destptr werden len Digits Platz benötigt.
2569 extern void cl_UDS_mul (const uintD* sourceptr1, uintC len1,
2570 const uintD* sourceptr2, uintC len2,
2572 // Spezialfall sourceptr1 == sourceptr2 && len1 == len2.
2573 extern void cl_UDS_mul_square (const uintD* sourceptr, uintC len,
2576 // Multipliziert zwei Unsigned-Digit-sequences.
2577 // UDS_UDS_mul_UDS(len1,LSDptr1, len2,LSDptr2, MSDptr=,len=,LSDptr=);
2578 // multipliziert die UDS ../len1/LSDptr1 und ../len2/LSDptr2.
2579 // Dabei sollte len1>0 und len2>0 sein.
2580 // Ergebnis ist die UDS MSDptr/len/LSDptr, mit len=len1+len2, im Stack.
2581 // Dabei wird num_stack erniedrigt.
2582 #define UDS_UDS_mul_UDS(len1,LSDptr1,len2,LSDptr2, MSDptr_zuweisung,len_zuweisung,LSDptr_zuweisung) \
2583 var uintL CONCAT(len_from_UDSmul_,__LINE__) = (uintL)(len1) + (uintL)(len2); \
2584 var uintD* CONCAT(LSDptr_from_UDSmul_,__LINE__); \
2585 unused (len_zuweisung CONCAT(len_from_UDSmul_,__LINE__)); \
2586 num_stack_alloc(CONCAT(len_from_UDSmul_,__LINE__),MSDptr_zuweisung,LSDptr_zuweisung CONCAT(LSDptr_from_UDSmul_,__LINE__) =); \
2587 cl_UDS_mul((LSDptr1),(len1),(LSDptr2),(len2),CONCAT(LSDptr_from_UDSmul_,__LINE__));
2589 // Multipliziert zwei Digit-sequences.
2590 // DS_DS_mul_DS(MSDptr1,len1,LSDptr1, MSDptr2,len2,LSDptr2, MSDptr=,len=,LSDptr=);
2591 // multipliziert die DS MSDptr1/len1/LSDptr1 und MSDptr2/len2/LSDptr2.
2592 // Dabei sollte len1>0 und len2>0 sein, und beide DS sollten /= 0 sein.
2593 // Alles sollten Variablen sein!
2594 // Ergebnis ist die DS MSDptr/len/LSDptr, mit len=len1+len2, im Stack.
2595 // Dabei wird num_stack erniedrigt.
2597 // Erst unsigned multiplizieren. Dann bis zu zwei Subtraktionen.
2598 // Sei b=2^intDsize, k=len1, l=len2, n=DS1, m=DS2.
2599 // Gesucht ist n * m.
2600 // Wir errechnen erst das unsigned-product p (mod b^(k+l)).
2601 // n>0, m>0: p = n*m, n*m = p
2602 // n<0, m>0: p = (n+b^k)*m, n*m + b^(k+l) = p - b^k * m (mod b^(k+l)).
2603 // n>0, m<0: p = n*(m+b^l), n*m + b^(k+l) = p - b^l * n (mod b^(k+l)).
2604 // n<0, m<0: p = (n+b^k)*(m+b^l),
2605 // n*m = p - b^k * (m+b^l) - b^l * (n+b^k) (mod b^(k+l)).
2606 #define DS_DS_mul_DS(MSDptr1,len1,LSDptr1,MSDptr2,len2,LSDptr2, MSDptr_zuweisung,len_zuweisung,LSDptr_zuweisung) \
2607 var uintD* MSDptr0; \
2608 var uintD* LSDptr0; \
2609 var uintL len_from_DSmal = (uintL)(len1) + (uintL)(len2); \
2610 unused (len_zuweisung len_from_DSmal); \
2611 num_stack_alloc(len_from_DSmal,MSDptr_zuweisung MSDptr0 =,LSDptr_zuweisung LSDptr0 =); \
2612 var uintD MSD1_from_DSmal = mspref(MSDptr1,0); \
2613 var uintD MSD2_from_DSmal = mspref(MSDptr2,0); \
2614 var uintL len1_from_DSmal = (len1); \
2615 var uintL len2_from_DSmal = (len2); \
2616 if (MSD1_from_DSmal==0) { msprefnext(MSDptr0) = 0; len1_from_DSmal--; } \
2617 if (MSD2_from_DSmal==0) { msprefnext(MSDptr0) = 0; len2_from_DSmal--; } \
2618 cl_UDS_mul((LSDptr1),len1_from_DSmal,(LSDptr2),len2_from_DSmal,LSDptr0); \
2619 if ((sintD)MSD1_from_DSmal < 0) /* n<0 ? */\
2620 /* muß m bzw. m+b^l subtrahieren, um k Digits verschoben: */\
2621 { subfrom_loop_lsp(LSDptr2,LSDptr0 lspop len1,len2); } \
2622 if ((sintD)MSD2_from_DSmal < 0) /* m<0 ? */\
2623 /* muß n bzw. n+b^k subtrahieren, um l Digits verschoben: */\
2624 { subfrom_loop_lsp(LSDptr1,LSDptr0 lspop len2,len1); }
2627 // Dividiert zwei Unsigned Digit sequences durcheinander.
2628 // UDS_divide(a_MSDptr,a_len,a_LSDptr, b_MSDptr,b_len,b_LSDptr, &q,&r);
2629 // Die UDS a = a_MSDptr/a_len/a_LSDptr (a>=0) wird durch
2630 // die UDS b = b_MSDptr/b_len/b_LSDptr (b>=0) dividiert:
2631 // a = q * b + r mit 0 <= r < b. Bei b=0 Error.
2632 // q der Quotient, r der Rest.
2633 // q = q_MSDptr/q_len/q_LSDptr, r = r_MSDptr/r_len/r_LSDptr beides
2634 // Normalized Unsigned Digit sequences.
2635 // Vorsicht: q_LSDptr <= r_MSDptr,
2636 // Vorzeichenerweiterung von r kann q zerstören!
2637 // Vorzeichenerweiterung von q ist erlaubt.
2638 // a und b werden nicht modifiziert.
2639 // num_stack wird erniedrigt.
2640 #define UDS_divide(a_MSDptr,a_len,a_LSDptr,b_MSDptr,b_len,b_LSDptr,q_,r_) \
2641 /* Platz fürs Ergebnis machen. Brauche maximal a_len+1 Digits. */\
2642 var uintC _a_len = (a_len); \
2643 var uintD* roomptr; num_stack_alloc_1(_a_len+1,roomptr=,); \
2644 cl_UDS_divide(a_MSDptr,_a_len,a_LSDptr,b_MSDptr,b_len,b_LSDptr,roomptr,q_,r_);
2645 extern void cl_UDS_divide (const uintD* a_MSDptr, uintC a_len, const uintD* a_LSDptr,
2646 const uintD* b_MSDptr, uintC b_len, const uintD* b_LSDptr,
2647 uintD* roomptr, DS* q_, DS* r_);
2650 // Bildet zu einer Unsigned Digit sequence a die Wurzel
2651 // (genauer: Gaußklammer aus Wurzel aus a).
2652 // UDS_sqrt(a_MSDptr,a_len,a_LSDptr, &b, squarep=)
2653 // > a_MSDptr/a_len/a_LSDptr: eine UDS
2654 // < NUDS b: Gaußklammer der Wurzel aus a
2655 // < squarep: cl_true falls a = b^2, cl_false falls b^2 < a < (b+1)^2.
2656 // a wird nicht modifiziert.
2657 // Vorzeichenerweiterung von b ist erlaubt.
2658 // num_stack wird erniedrigt.
2659 #define UDS_sqrt(a_MSDptr,a_len,a_LSDptr,b_,squarep_zuweisung) \
2660 { /* ceiling(a_len,2) Digits Platz fürs Ergebnis machen: */\
2661 var uintC _a_len = (a_len); \
2662 num_stack_alloc_1(ceiling(_a_len,2),(b_)->MSDptr=,); \
2663 squarep_zuweisung cl_UDS_sqrt(a_MSDptr,_a_len,a_LSDptr,b_); \
2665 extern cl_boolean cl_UDS_sqrt (const uintD* a_MSDptr, uintC a_len, const uintD* a_LSDptr, DS* b_);
2668 // Auxiliary function for approximately computing 1/x
2669 // using Newton iteration.
2670 extern void cl_UDS_recip (const uintD* a_MSDptr, uintC a_len,
2671 uintD* b_MSDptr, uintC b_len);
2673 // Auxiliary function for approximately computing 1/sqrt(x)
2674 // using Newton iteration.
2675 extern void cl_UDS_recipsqrt (const uintD* a_MSDptr, uintC a_len,
2676 uintD* b_MSDptr, uintC b_len);
2680 #endif /* _CL_DS_H */