1 // Digit sequence arithmetic
7 #include "base/cl_gmpconfig.h"
8 #include "base/digit/cl_D.h"
9 #include "base/digitseq/cl_DS_endian.h"
10 #include "base/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)))
50 // i386-pc-solaris #defines DS.
60 // Endianness independent access of digit sequences:
61 // mspref(MSDptr,i) access a most significant digit
62 // lspref(LSDptr,i) access a least significant digit
63 // msshrink(MSDptr) shrinks the DS by throwing away the MSD
64 // msprefnext(MSDptr) combines mspref(MSDptr,0) and msshrink(MSDptr)
65 // lsshrink(LSDptr) shrinks the DS by throwing away the LSD
66 // lsprefnext(LSDptr) combines lspref(LSDptr,0) and lsshrink(LSDptr)
67 // mspop pointer operator corresponding to msshrink, arg is widened to an uintP
68 // lspop pointer operator corresponding to lsshrink, arg is widened to an uintP
69 #if CL_DS_BIG_ENDIAN_P
70 #define mspref(p,i) (p)[i]
71 #define lspref(p,i) (p)[-(uintP)(i)-1]
72 #define msshrink(p) (p)++
73 #define msprefnext(p) (*(p)++)
74 #define lsshrink(p) (p)--
75 #define lsprefnext(p) (*--(p))
79 #define mspref(p,i) (p)[-(uintP)(i)-1]
80 #define lspref(p,i) (p)[i]
81 #define msshrink(p) (p)--
82 #define msprefnext(p) (*--(p))
83 #define lsshrink(p) (p)++
84 #define lsprefnext(p) (*(p)++)
89 // Endianness independent macros for turning an array into a digit sequence.
90 // arrayMSDptr(array,length) returns the MSDptr of array[0..length-1]
91 // arrayLSDptr(array,length) returns the LSDptr of array[0..length-1]
92 #if CL_DS_BIG_ENDIAN_P
93 #define arrayMSDptr(array,length) &(array)[0]
94 #define arrayLSDptr(array,length) &(array)[length]
96 #define arrayMSDptr(array,length) &(array)[length]
97 #define arrayLSDptr(array,length) &(array)[0]
99 #define arrayLSref(array,length,i) lspref(arrayLSDptr(array,length),i)
102 // These functions on digit sequences are either inline C++ functions
103 // or external assembler functions (see files cl_asm_*).
106 // See which functions are defined as external functions.
107 #include "base/digitseq/cl_asm.h"
110 // Declare the external functions.
116 extern uintD* copy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count);
118 extern uintD* copy_loop_down (const uintD* sourceptr, uintD* destptr, uintC count);
124 extern uintD* fill_loop_up (uintD* destptr, uintC count, uintD filler);
126 extern uintD* fill_loop_down (uintD* destptr, uintC count, uintD filler);
132 extern uintD* clear_loop_up (uintD* destptr, uintC count);
134 extern uintD* clear_loop_down (uintD* destptr, uintC count);
140 extern bool test_loop_up (const uintD* ptr, uintC count);
142 extern bool test_loop_down (const uintD* ptr, uintC count);
146 #if CL_DS_BIG_ENDIAN_P
150 extern void or_loop_up (uintD* xptr, const uintD* yptr, uintC count);
152 extern void xor_loop_up (uintD* xptr, const uintD* yptr, uintC count);
154 extern void and_loop_up (uintD* xptr, const uintD* yptr, uintC count);
156 extern void eqv_loop_up (uintD* xptr, const uintD* yptr, uintC count);
158 extern void nand_loop_up (uintD* xptr, const uintD* yptr, uintC count);
160 extern void nor_loop_up (uintD* xptr, const uintD* yptr, uintC count);
162 extern void andc2_loop_up (uintD* xptr, const uintD* yptr, uintC count);
164 extern void orc2_loop_up (uintD* xptr, const uintD* yptr, uintC count);
166 extern void not_loop_up (uintD* xptr, uintC count);
172 extern bool and_test_loop_up (const uintD* xptr, const uintD* yptr, uintC count);
174 extern cl_signean compare_loop_up (const uintD* xptr, const uintD* yptr, uintC count);
180 extern uintD add_loop_down (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count);
182 extern uintD addto_loop_down (const uintD* sourceptr, uintD* destptr, uintC count);
184 extern uintD inc_loop_down (uintD* ptr, uintC count);
186 extern uintD sub_loop_down (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count);
188 extern uintD subx_loop_down (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count, uintD carry);
190 extern uintD subfrom_loop_down (const uintD* sourceptr, uintD* destptr, uintC count);
192 extern uintD dec_loop_down (uintD* ptr, uintC count);
194 extern uintD neg_loop_down (uintD* ptr, uintC count);
200 extern uintD shift1left_loop_down (uintD* ptr, uintC count);
202 extern uintD shiftleft_loop_down (uintD* ptr, uintC count, uintC i, uintD carry);
204 extern uintD shiftleftcopy_loop_down (const uintD* sourceptr, uintD* destptr, uintC count, uintC i);
206 extern uintD shift1right_loop_up (uintD* ptr, uintC count, uintD carry);
208 extern uintD shiftright_loop_up (uintD* ptr, uintC count, uintC i);
210 extern uintD shiftrightsigned_loop_up (uintD* ptr, uintC count, uintC i);
212 extern uintD shiftrightcopy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count, uintC i, uintD carry);
218 extern uintD mulusmall_loop_down (uintD digit, uintD* ptr, uintC len, uintD newdigit);
220 extern void mulu_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len);
222 extern uintD muluadd_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len);
224 extern uintD mulusub_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len);
230 extern uintD divu_loop_up (uintD digit, uintD* ptr, uintC len);
232 extern uintD divucopy_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len);
236 #else // !CL_DS_BIG_ENDIAN_P
240 extern void or_loop_down (uintD* xptr, const uintD* yptr, uintC count);
242 extern void xor_loop_down (uintD* xptr, const uintD* yptr, uintC count);
244 extern void and_loop_down (uintD* xptr, const uintD* yptr, uintC count);
246 extern void eqv_loop_down (uintD* xptr, const uintD* yptr, uintC count);
248 extern void nand_loop_down (uintD* xptr, const uintD* yptr, uintC count);
250 extern void nor_loop_down (uintD* xptr, const uintD* yptr, uintC count);
252 extern void andc2_loop_down (uintD* xptr, const uintD* yptr, uintC count);
254 extern void orc2_loop_down (uintD* xptr, const uintD* yptr, uintC count);
256 extern void not_loop_down (uintD* xptr, uintC count);
262 extern bool and_test_loop_down (const uintD* xptr, const uintD* yptr, uintC count);
264 extern cl_signean compare_loop_down (const uintD* xptr, const uintD* yptr, uintC count);
270 extern uintD add_loop_up (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count);
272 extern uintD addto_loop_up (const uintD* sourceptr, uintD* destptr, uintC count);
274 extern uintD inc_loop_up (uintD* ptr, uintC count);
276 extern uintD sub_loop_up (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count);
278 extern uintD subx_loop_up (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count, uintD carry);
280 extern uintD subfrom_loop_up (const uintD* sourceptr, uintD* destptr, uintC count);
282 extern uintD dec_loop_up (uintD* ptr, uintC count);
284 extern uintD neg_loop_up (uintD* ptr, uintC count);
290 extern uintD shift1left_loop_up (uintD* ptr, uintC count);
292 extern uintD shiftleft_loop_up (uintD* ptr, uintC count, uintC i, uintD carry);
294 extern uintD shiftleftcopy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count, uintC i);
296 extern uintD shift1right_loop_down (uintD* ptr, uintC count, uintD carry);
298 extern uintD shiftright_loop_down (uintD* ptr, uintC count, uintC i);
300 extern uintD shiftrightsigned_loop_down (uintD* ptr, uintC count, uintC i);
302 extern uintD shiftrightcopy_loop_down (const uintD* sourceptr, uintD* destptr, uintC count, uintC i, uintD carry);
308 extern uintD mulusmall_loop_up (uintD digit, uintD* ptr, uintC len, uintD newdigit);
310 extern void mulu_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len);
312 extern uintD muluadd_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len);
314 extern uintD mulusub_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len);
320 extern uintD divu_loop_down (uintD digit, uintD* ptr, uintC len);
322 extern uintD divucopy_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len);
326 #endif // !CL_DS_BIG_ENDIAN_P
328 // Independently of CL_DS_BIG_ENDIAN_P:
332 extern cl_signean compare_loop_up (const uintD* xptr, const uintD* yptr, uintC count);
338 extern void xor_loop_up (uintD* xptr, const uintD* yptr, uintC count);
344 extern uintD shiftleftcopy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count, uintC i);
346 extern void shiftxor_loop_up (uintD* xptr, const uintD* yptr, uintC count, uintC i);
353 #if defined(CL_USE_GMP)
355 // Supersede the functions by wrappers around calls to gmp mpn,
356 // for those functions where gmp is believed to be faster.
361 // Argh, gmp.h includes <stddef.h> which erases the definition of offsetof
362 // that we have provided in cl_offsetof.h. Restore it.
363 #include "base/cl_offsetof.h"
367 #if 0 // not worth it, since gmp's mpn_cmp is not optimized
368 inline cl_signean compare_loop_down (const uintD* xptr, const uintD* yptr, uintC count)
370 return mpn_cmp(xptr-count,yptr-count,count);
374 inline uintD add_loop_up (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count)
378 return mpn_add_n(destptr,sourceptr1,sourceptr2,count);
381 inline uintD addto_loop_up (const uintD* sourceptr, uintD* destptr, uintC count)
385 return mpn_add_n(destptr,destptr,sourceptr,count);
388 inline uintD inc_loop_up (uintD* ptr, uintC count)
392 return mpn_add_1(ptr,ptr,count,1);
395 inline uintD sub_loop_up (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count)
399 return mpn_sub_n(destptr,sourceptr1,sourceptr2,count);
402 inline uintD subx_loop_up (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count, uintD carry)
406 var uintD res_carry = mpn_sub_n(destptr,sourceptr1,sourceptr2,count);
408 res_carry |= mpn_sub_1(destptr,destptr,count,1);
412 inline uintD subfrom_loop_up (const uintD* sourceptr, uintD* destptr, uintC count)
416 return mpn_sub_n(destptr,destptr,sourceptr,count);
419 inline uintD dec_loop_up (uintD* ptr, uintC count)
423 return -mpn_sub_1(ptr,ptr,count,1);
426 #if !defined(ADDSUB_LOOPS)
427 // No equivalent for this in gmp. But we need this function, so write it in C.
428 inline uintD neg_loop_up (uintD* ptr, uintC count)
430 // erstes Digit /=0 suchen:
431 until (count==0) { if (!(*ptr == 0)) goto L1; ptr++; count--; }
433 L1: // erstes Digit /=0 gefunden, ab jetzt gibt's Carrys
434 *ptr = - *ptr; count--; // 1 Digit negieren
435 dotimesC(count,count, { ptr++; *ptr = ~ *ptr; } ); // alle anderen Digits invertieren
442 inline uintD shift1left_loop_up (uintD* ptr, uintC count)
446 return mpn_lshift(ptr,ptr,count,1);
449 inline uintD shiftleft_loop_up (uintD* ptr, uintC count, uintC i, uintD carry)
453 var uintD res_carry = mpn_lshift(ptr,ptr,count,i);
458 inline uintD shiftleftcopy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count, uintC i)
462 return mpn_lshift(destptr,sourceptr,count,i);
465 inline uintD shift1right_loop_down (uintD* ptr, uintC count, uintD carry)
469 var uintD res_carry = mpn_rshift(ptr-count,ptr-count,count,1);
471 ptr[-1] |= bit(intDsize-1);
475 inline uintD shiftright_loop_down (uintD* ptr, uintC count, uintC i)
479 return mpn_rshift(ptr-count,ptr-count,count,i);
482 inline uintD shiftrightsigned_loop_down (uintD* ptr, uintC count, uintC i)
484 var uintD carry = ((sintD)ptr[-1] >> (intDsize-1)) << (intDsize-i);
485 var uintD res_carry = mpn_rshift(ptr-count,ptr-count,count,i);
490 inline uintD shiftrightcopy_loop_down (const uintD* sourceptr, uintD* destptr, uintC count, uintC i, uintD carry)
492 carry = carry << (intDsize-i);
495 var uintD res_carry = mpn_rshift(destptr-count,sourceptr-count,count,i);
496 destptr[-1] |= carry;
502 inline uintD mulusmall_loop_up (uintD digit, uintD* ptr, uintC len, uintD newdigit)
506 var uintD res_carry = mpn_mul_1(ptr,ptr,len,digit);
507 res_carry += mpn_add_1(ptr,ptr,len,newdigit);
511 inline void mulu_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
513 destptr[len] = (len==0 ? 0 : mpn_mul_1(destptr,sourceptr,len,digit));
516 inline uintD muluadd_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
520 return mpn_addmul_1(destptr,sourceptr,len,digit);
523 inline uintD mulusub_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
527 return mpn_submul_1(destptr,sourceptr,len,digit);
532 inline uintD divu_loop_up (uintD digit, uintD* ptr, uintC len)
534 return mpn_divrem_1(ptr,0,ptr,len,digit);
537 inline uintD divu_loop_down (uintD digit, uintD* ptr, uintC len)
539 return mpn_divrem_1(ptr-len,0,ptr-len,len,digit);
542 inline uintD divucopy_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
544 return mpn_divrem_1(destptr,0,sourceptr,len,digit);
547 inline uintD divucopy_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
549 return mpn_divrem_1(destptr-len,0,sourceptr-len,len,digit);
554 #endif // defined(CL_USE_GMP)
557 // Define the missing functions as inline functions.
562 // destptr = copy_loop_up(sourceptr,destptr,count);
563 // kopiert count (uintC>=0) Digits aufwärts von sourceptr nach destptr
564 // und liefert das neue destptr.
565 inline uintD* copy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count)
566 { dotimesC(count,count, { *destptr++ = *sourceptr++; } );
571 // destptr = copy_loop_down(sourceptr,destptr,count);
572 // kopiert count (uintC>=0) Digits abwärts von sourceptr nach destptr
573 // und liefert das neue destptr.
574 inline uintD* copy_loop_down (const uintD* sourceptr, uintD* destptr, uintC count)
575 { dotimesC(count,count, { *--destptr = *--sourceptr; } );
584 // destptr = fill_loop_up(destptr,count,filler);
585 // kopiert count (uintC>=0) mal das Digit filler aufwärts nach destptr
586 // und liefert das neue destptr.
587 inline uintD* fill_loop_up (uintD* destptr, uintC count, uintD filler)
588 { dotimesC(count,count, { *destptr++ = filler; } );
593 // destptr = fill_loop_down(destptr,count,filler);
594 // kopiert count (uintC>=0) mal das Digit filler abwärts nach destptr
595 // und liefert das neue destptr.
596 inline uintD* fill_loop_down (uintD* destptr, uintC count, uintD filler)
597 { dotimesC(count,count, { *--destptr = filler; } );
606 // destptr = clear_loop_up(destptr,count);
607 // löscht count (uintC>=0) Digits aufwärts ab destptr
608 // und liefert das neue destptr.
609 inline uintD* clear_loop_up (uintD* destptr, uintC count)
610 { dotimesC(count,count, { *destptr++ = 0; } );
615 // destptr = clear_loop_down(destptr,count);
616 // löscht count (uintC>=0) Digits abwärts ab destptr
617 // und liefert das neue destptr.
618 inline uintD* clear_loop_down (uintD* destptr, uintC count)
619 { dotimesC(count,count, { *--destptr = 0; } );
628 // test_loop_up(ptr,count)
629 // testet count (uintC>=0) Digits aufwärts ab ptr, ob darunter eines /=0 ist.
630 // Ergebnis /=0, falls ja.
631 inline bool test_loop_up (const uintD* ptr, uintC count)
632 { dotimesC(count,count, { if (*ptr++) return true; } );
637 // test_loop_down(ptr,count)
638 // testet count (uintC>=0) Digits abwärts ab ptr, ob darunter eines /=0 ist.
639 // Ergebnis /=0, falls ja.
640 inline bool test_loop_down (const uintD* ptr, uintC count)
641 { dotimesC(count,count, { if (*--ptr) return true; } );
647 #if CL_DS_BIG_ENDIAN_P
652 // or_loop_up(xptr,yptr,count);
653 // verknüpft count (uintC>=0) Digits aufwärts ab xptr und ab yptr
654 // mit Ziel ab xptr durch OR.
655 inline void or_loop_up (uintD* xptr, const uintD* yptr, uintC count)
656 { dotimesC(count,count, { *xptr++ |= *yptr++; } ); }
659 // xor_loop_up(xptr,yptr,count);
660 // verknüpft count (uintC>=0) Digits aufwärts ab xptr und ab yptr
661 // mit Ziel ab xptr durch XOR.
662 inline void xor_loop_up (uintD* xptr, const uintD* yptr, uintC count)
663 { dotimesC(count,count, { *xptr++ ^= *yptr++; } ); }
666 // and_loop_up(xptr,yptr,count);
667 // verknüpft count (uintC>=0) Digits aufwärts ab xptr und ab yptr
668 // mit Ziel ab xptr durch AND.
669 inline void and_loop_up (uintD* xptr, const uintD* yptr, uintC count)
670 { dotimesC(count,count, { *xptr++ &= *yptr++; } ); }
673 // eqv_loop_up(xptr,yptr,count);
674 // verknüpft count (uintC>=0) Digits aufwärts ab xptr und ab yptr
675 // mit Ziel ab xptr durch EQV (NOT XOR).
676 inline void eqv_loop_up (uintD* xptr, const uintD* yptr, uintC count)
677 { dotimesC(count,count,
678 {var uintD temp = ~ (*xptr ^ *yptr++); *xptr++ = temp; }
683 // nand_loop_up(xptr,yptr,count);
684 // verknüpft count (uintC>=0) Digits aufwärts ab xptr und ab yptr
685 // mit Ziel ab xptr durch NAND (NOT AND).
686 inline void nand_loop_up (uintD* xptr, const uintD* yptr, uintC count)
687 { dotimesC(count,count,
688 {var uintD temp = ~ (*xptr & *yptr++); *xptr++ = temp; }
693 // nor_loop_up(xptr,yptr,count);
694 // verknüpft count (uintC>=0) Digits aufwärts ab xptr und ab yptr
695 // mit Ziel ab xptr durch NOR (NOT OR).
696 inline void nor_loop_up (uintD* xptr, const uintD* yptr, uintC count)
697 { dotimesC(count,count,
698 {var uintD temp = ~ (*xptr | *yptr++); *xptr++ = temp; }
703 // andc2_loop_up(xptr,yptr,count);
704 // verknüpft count (uintC>=0) Digits aufwärts ab xptr und ab yptr
705 // mit Ziel ab xptr durch ANDC2 (AND NOT).
706 inline void andc2_loop_up (uintD* xptr, const uintD* yptr, uintC count)
707 { dotimesC(count,count, { *xptr++ &= ~(*yptr++); } ); }
710 // orc2_loop_up(xptr,yptr,count);
711 // verknüpft count (uintC>=0) Digits aufwärts ab xptr und ab yptr
712 // mit Ziel ab xptr durch ORC2 (OR NOT).
713 inline void orc2_loop_up (uintD* xptr, const uintD* yptr, uintC count)
714 { dotimesC(count,count, { *xptr++ |= ~(*yptr++); } ); }
717 // not_loop_up(xptr,count);
718 // verknüpft count (uintC>0) Digits aufwärts ab xptr mit Ziel ab xptr
720 inline void not_loop_up (uintD* xptr, uintC count)
721 { dotimespC(count,count,
722 {var uintD temp = ~ (*xptr); *xptr++ = temp; }
730 // AND-Test-Schleife:
731 // and_test_loop_up(xptr,yptr,count);
732 // verknüpft count (uintC>=0) Digits aufwärts ab xptr und ab yptr durch AND
733 // und testet, ob sich dabei ein Digit /=0 ergibt. Ergebnis true, falls ja.
734 inline bool and_test_loop_up (const uintD* xptr, const uintD* yptr, uintC count)
735 { dotimesC(count,count, { if (*xptr++ & *yptr++) return true; } );
739 // Vergleichsschleife:
740 // result = compare_loop_up(xptr,yptr,count);
741 // vergleicht nacheinander xptr[0] mit yptr[0], xptr[1] mit yptr[1], usw.,
742 // insgesamt count Digits, und liefert 0 falls alle gleich sind,
743 // +1 falls zuerst ein xptr[i]>yptr[i] ist,
744 // -1 falls zuerst ein xptr[i]<yptr[i] ist.
745 inline cl_signean compare_loop_up (const uintD* xptr, const uintD* yptr, uintC count)
746 { dotimesC(count,count,
747 { if (!(*xptr++ == *yptr++))
748 // verschiedene Digits gefunden
749 return (*--xptr > *--yptr ? signean_plus : signean_minus);
751 return signean_null; // alle Digits gleich
758 // Additionsschleife:
759 // übertrag = add_loop_down(sourceptr1,sourceptr2,destptr,count);
760 // addiert count (uintC>=0) Digits abwärts von sourceptr1, von sourceptr2
761 // abwärts nach destptr und liefert den Übertrag (0 oder /=0, was 1 bedeutet).
762 inline uintD add_loop_down (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count)
766 do { source1 = *--sourceptr1;
767 source2 = *--sourceptr2;
768 *--destptr = source1 + source2;
769 if (source1 > (uintD)(~source2)) goto carry_1;
775 do { source1 = *--sourceptr1;
776 source2 = *--sourceptr2;
777 *--destptr = source1 + source2 + 1;
778 if (source1 < (uintD)(~source2)) goto carry_0;
786 // Additionsschleife:
787 // übertrag = addto_loop_down(sourceptr,destptr,count);
788 // addiert count (uintC>=0) Digits abwärts von sourceptr, von destptr
789 // abwärts nach destptr und liefert den Übertrag (0 oder /=0, was 1 bedeutet).
790 inline uintD addto_loop_down (const uintD* sourceptr, uintD* destptr, uintC count)
794 do { source1 = *--sourceptr;
795 source2 = *--destptr;
796 *destptr = source1 + source2;
797 if (source1 > (uintD)(~source2)) goto carry_1;
803 do { source1 = *--sourceptr;
804 source2 = *--destptr;
805 *destptr = source1 + source2 + 1;
806 if (source1 < (uintD)(~source2)) goto carry_0;
814 // Incrementierschleife:
815 // übertrag = inc_loop_down(ptr,count);
816 // incrementiert count (uintC>=0) Digits abwärts von ptr, so lange bis kein
817 // Übertrag mehr auftritt und liefert den Übertrag (0 oder /=0, was 1 bedeutet).
818 inline uintD inc_loop_down (uintD* ptr, uintC count)
819 { dotimesC(count,count,
820 { if (!( ++(*--ptr) == 0 )) return 0; } // kein weiterer Übertrag
822 return 1; // weiterer Übertrag
825 // Subtraktionsschleife:
826 // übertrag = sub_loop_down(sourceptr1,sourceptr2,destptr,count);
827 // subtrahiert count (uintC>=0) Digits abwärts von sourceptr1, von sourceptr2
828 // abwärts nach destptr und liefert den Übertrag (0 oder /=0, was -1 bedeutet).
829 inline uintD sub_loop_down (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count)
833 do { source1 = *--sourceptr1;
834 source2 = *--sourceptr2;
835 *--destptr = source1 - source2;
836 if (source1 < source2) goto carry_1;
842 do { source1 = *--sourceptr1;
843 source2 = *--sourceptr2;
844 *--destptr = source1 - source2 - 1;
845 if (source1 > source2) goto carry_0;
853 // Subtraktionsschleife:
854 // übertrag = subx_loop_down(sourceptr1,sourceptr2,destptr,count,carry);
855 // subtrahiert count (uintC>=0) Digits abwärts von sourceptr1 und addiert
856 // einen Carry (0 oder -1), von sourceptr2 abwärts nach destptr und
857 // liefert den Übertrag (0 oder /=0, was -1 bedeutet).
858 inline uintD subx_loop_down (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count, uintD carry)
863 do { source1 = *--sourceptr1;
864 source2 = *--sourceptr2;
865 *--destptr = source1 - source2;
866 if (source1 < source2) goto carry_1;
875 do { source1 = *--sourceptr1;
876 source2 = *--sourceptr2;
877 *--destptr = source1 - source2 - 1;
878 if (source1 > source2) goto carry_0;
886 // Subtraktionsschleife:
887 // übertrag = subfrom_loop_down(sourceptr,destptr,count);
888 // subtrahiert count (uintC>=0) Digits abwärts von sourceptr, von destptr
889 // abwärts nach destptr (dest := dest - source)
890 // und liefert den Übertrag (0 oder /=0, was -1 bedeutet).
891 inline uintD subfrom_loop_down (const uintD* sourceptr, uintD* destptr, uintC count)
895 do { source1 = *--destptr;
896 source2 = *--sourceptr;
897 *destptr = source1 - source2;
898 if (source1 < source2) goto carry_1;
904 do { source1 = *--destptr;
905 source2 = *--sourceptr;
906 *destptr = source1 - source2 - 1;
907 if (source1 > source2) goto carry_0;
915 // Decrementierschleife:
916 // übertrag = dec_loop_down(ptr,count);
917 // decrementiert count (uintC>=0) Digits abwärts von ptr, so lange bis kein
918 // Übertrag mehr auftritt und liefert den Übertrag (0 oder -1).
919 inline uintD dec_loop_down (uintD* ptr, uintC count)
920 { dotimesC(count,count,
921 { if (!( (*--ptr)-- == 0 )) return 0; } // kein weiterer Übertrag
923 return (uintD)(-1); // weiterer Übertrag
927 // übertrag = neg_loop_down(ptr,count);
928 // negiert count (uintC>=0) Digits abwärts von ptr,
929 // und liefert den Übertrag (0 oder -1).
930 inline uintD neg_loop_down (uintD* ptr, uintC count)
931 { // erstes Digit /=0 suchen:
932 until (count==0) { if (!(*--ptr == 0)) goto L1; count--; }
934 L1: // erstes Digit /=0 gefunden, ab jetzt gibt's Carrys
935 *ptr = - *ptr; count--; // 1 Digit negieren
936 dotimesC(count,count, { --ptr; *ptr = ~ *ptr; } ); // alle anderen Digits invertieren
944 // Schiebeschleife um 1 Bit nach links:
945 // übertrag = shift1left_loop_down(ptr,count);
946 // schiebt count (uintC>=0) Digits abwärts von ptr um 1 Bit nach links,
947 // und liefert den Übertrag (0 oder /=0, was 1 bedeutet).
949 inline uintD shift1left_loop_down (uintD* ptr, uintC count)
950 { var uintDD accu = 0;
951 dotimesC(count,count,
952 { accu = ((uintDD)(*--ptr)<<1)+accu; *ptr = lowD(accu);
953 accu = (uintDD)(highD(accu));
958 inline uintD shift1left_loop_down (uintD* ptr, uintC count)
959 { var uintD carry = 0;
960 dotimesC(count,count,
961 { var uintD accu = *--ptr;
962 *ptr = (accu<<1) | carry;
963 carry = accu>>(intDsize-1);
969 // Schiebeschleife um i Bits nach links:
970 // übertrag = shiftleft_loop_down(ptr,count,i,übertrag_init);
971 // schiebt count (uintC>=0) Digits abwärts von ptr um i Bits (0<i<intDsize)
972 // nach links, schiebt dabei die i Bits aus übertrag_init rechts rein,
973 // und liefert den Übertrag (was links rauskommt, >=0, <2^i).
975 inline uintD shiftleft_loop_down (uintD* ptr, uintC count, uintC i, uintD carry)
976 { var uintDD accu = (uintDD)carry;
977 dotimesC(count,count,
978 { accu = ((uintDD)(*--ptr)<<i)+accu; *ptr = lowD(accu);
979 accu = (uintDD)(highD(accu));
984 inline uintD shiftleft_loop_down (uintD* ptr, uintC count, uintC i, uintD carry)
985 { var uintC j = intDsize-i;
986 dotimesC(count,count,
987 { var uintD accu = *--ptr;
988 *ptr = (accu<<i) | carry;
995 // Schiebe- und Kopierschleife um i Bits nach links:
996 // übertrag = shiftleftcopy_loop_down(sourceptr,destptr,count,i);
997 // kopiert count (uintC>=0) Digits abwärts von sourceptr nach destptr
998 // und schiebt sie dabei um i Bits (0<i<intDsize) nach links,
999 // wobei ganz rechts mit i Nullbits aufgefüllt wird,
1000 // und liefert den Übertrag (was links rauskommt, >=0, <2^i).
1002 inline uintD shiftleftcopy_loop_down (const uintD* sourceptr, uintD* destptr, uintC count, uintC i)
1003 { var uintDD accu = 0;
1004 dotimesC(count,count,
1005 { accu = ((uintDD)(*--sourceptr)<<i)+accu; *--destptr = lowD(accu);
1006 accu = (uintDD)(highD(accu));
1011 inline uintD shiftleftcopy_loop_down (const uintD* sourceptr, uintD* destptr, uintC count, uintC i)
1012 { var uintC j = intDsize-i;
1013 var uintD carry = 0;
1014 dotimesC(count,count,
1015 { var uintD accu = *--sourceptr;
1016 *--destptr = (accu<<i) | carry;
1023 // Schiebeschleife um 1 Bit nach rechts:
1024 // übertrag = shift1right_loop_up(ptr,count,übertrag_init);
1025 // schiebt count (uintC>=0) Digits aufwärts von ptr um 1 Bit nach rechts,
1026 // wobei links das Bit übertrag_init (sollte =0 oder =-1 sein) hineingeschoben
1027 // wird, und liefert den Übertrag (0 oder /=0, was 1 bedeutet).
1029 inline uintD shift1right_loop_up (uintD* ptr, uintC count, uintD carry)
1030 { var uintDD accu = (sintDD)(sintD)carry & ((uintDD)1 << (2*intDsize-1)); // 0 oder bit(2*intDsize-1)
1031 dotimesC(count,count,
1032 { accu = (highlowDD_0(*ptr)>>1)+accu; *ptr++ = highD(accu);
1033 accu = highlowDD_0(lowD(accu));
1038 inline uintD shift1right_loop_up (uintD* ptr, uintC count, uintD carry)
1039 { carry = carry << (intDsize-1); // carry zu einem einzigen Bit machen
1040 dotimesC(count,count,
1041 { var uintD accu = *ptr;
1042 *ptr++ = (accu >> 1) | carry;
1043 carry = accu << (intDsize-1);
1049 // Schiebeschleife um i Bits nach rechts:
1050 // übertrag = shiftright_loop_up(ptr,count,i);
1051 // schiebt count (uintC>=0) Digits aufwärts von ptr um i Bits (0<i<intDsize)
1052 // nach rechts, wobei links Nullen eingeschoben werden,
1053 // und liefert den Übertrag (was rechts rauskommt, als Bits intDsize-1..intDsize-i).
1055 inline uintD shiftright_loop_up (uintD* ptr, uintC count, uintC i)
1056 { var uintDD accu = 0;
1057 dotimesC(count,count,
1058 { // Die oberen i Bits von (uintD)accu bilden hier den Übertrag.
1059 accu = highlowDD_0(lowD(accu));
1060 // Die oberen i Bits von (uintDD)accu bilden hier den Übertrag.
1061 accu = (highlowDD_0(*ptr)>>i)+accu; *ptr++ = highD(accu);
1066 inline uintD shiftright_loop_up (uintD* ptr, uintC count, uintC i)
1067 { var uintC j = intDsize-i;
1068 var uintD carry = 0;
1069 dotimesC(count,count,
1070 { var uintD accu = *ptr;
1071 *ptr++ = (accu >> i) | carry;
1078 // Schiebeschleife um i Bits nach rechts:
1079 // übertrag = shiftrightsigned_loop_up(ptr,count,i);
1080 // schiebt count (uintC>0) Digits aufwärts von ptr um i Bits (0<i<intDsize)
1081 // nach rechts, wobei links das MSBit ver-i-facht wird,
1082 // und liefert den Übertrag (was rechts rauskommt, als Bits intDsize-1..intDsize-i).
1084 inline uintD shiftrightsigned_loop_up (uintD* ptr, uintC count, uintC i)
1085 { var uintDD accu = // Übertrag mit i Vorzeichenbits initialisieren
1086 highlowDD_0(sign_of_sintD((sintD)(*ptr)))>>i;
1087 dotimespC(count,count,
1088 { // Die oberen i Bits von (uintD)accu bilden hier den Übertrag.
1089 accu = highlowDD_0(lowD(accu));
1090 // Die oberen i Bits von (uintDD)accu bilden hier den Übertrag.
1091 accu = (highlowDD_0(*ptr)>>i)+accu; *ptr++ = highD(accu);
1096 inline uintD shiftrightsigned_loop_up (uintD* ptr, uintC count, uintC i)
1097 { var uintC j = intDsize-i;
1099 { var uintD accu = *ptr;
1100 *ptr++ = (sintD)accu >> i;
1104 dotimesC(count,count,
1105 { var uintD accu = *ptr;
1106 *ptr++ = (accu >> i) | carry;
1113 // Schiebe- und Kopier-Schleife um i Bits nach rechts:
1114 // übertrag = shiftrightcopy_loop_up(sourceptr,destptr,count,i,carry);
1115 // kopiert count (uintC>=0) Digits aufwärts von sourceptr nach destptr
1116 // und schiebt sie dabei um i Bits (0<i<intDsize) nach rechts, wobei carry
1117 // (sozusagen als sourceptr[-1]) die i Bits ganz links bestimmt,
1118 // und liefert den Übertrag (was rechts rauskommt, als Bits intDsize-1..intDsize-i).
1120 inline uintD shiftrightcopy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count, uintC i, uintD carry)
1121 { var uintDD accu = // Übertrag mit carry initialisieren
1122 highlowDD_0(carry)>>i;
1123 dotimesC(count,count,
1124 { // Die oberen i Bits von (uintD)accu bilden hier den Übertrag.
1125 accu = highlowDD_0(lowD(accu));
1126 // Die oberen i Bits von (uintDD)accu bilden hier den Übertrag.
1127 accu = (highlowDD_0(*sourceptr++)>>i)+accu; *destptr++ = highD(accu);
1132 inline uintD shiftrightcopy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count, uintC i, uintD carry)
1133 { var uintC j = intDsize-i;
1135 dotimesC(count,count,
1136 { var uintD accu = *sourceptr++;
1137 *destptr++ = (accu >> i) | carry;
1148 // Multiplikations-Einfachschleife:
1149 // Multipliziert eine UDS mit einem kleinen Digit und addiert ein kleines Digit.
1150 // mulusmall_loop_down(digit,ptr,len,newdigit)
1151 // multipliziert die UDS ptr[-len..-1] mit digit (>=2, <=36),
1152 // addiert dabei newdigit (>=0, <digit) zur letzten Ziffer,
1153 // und liefert den Carry (>=0, <digit).
1155 inline uintD mulusmall_loop_down (uintD digit, uintD* ptr, uintC len, uintD newdigit)
1156 { var uintDD carry = newdigit;
1158 { // Hier ist 0 <= carry < digit.
1159 carry = carry + muluD(digit,*--ptr);
1160 // Hier ist 0 <= carry < 2^intDsize*digit.
1162 carry = (uintDD)highD(carry); // carry := floor(carry/2^intDsize) < digit
1167 inline uintD mulusmall_loop_down (uintD digit, uintD* ptr, uintC len, uintD newdigit)
1168 { var uintD carry = newdigit;
1170 { // Hier ist 0 <= carry < digit.
1173 muluD(digit,*--ptr,hi=,lo=);
1174 // Hier ist 0 <= 2^intDsize*hi + lo + carry < 2^intDsize*digit.
1175 lo += carry; if (lo < carry) { hi += 1; }
1183 // Multiplikations-Einfachschleife:
1184 // Multipliziert eine UDS mit einem Digit und legt das Ergebnis in einer
1186 // mulu_loop_down(digit,sourceptr,destptr,len);
1187 // multipliziert die UDS sourceptr[-len..-1] (len>0)
1188 // mit dem einzelnen digit
1189 // und legt das Ergebnis in der UDS destptr[-len-1..-1] ab.
1191 inline void mulu_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1192 { var uintDD carry = 0;
1194 { // Hier ist carry=digit=0 oder 0 <= carry < digit.
1195 carry = carry + muluD(digit,*--sourceptr);
1196 // Hier ist carry=digit=0 oder 0 <= carry < 2^intDsize*digit.
1197 *--destptr = lowD(carry);
1198 carry = (uintDD)highD(carry); // carry := floor(carry/2^intDsize) < digit
1200 *--destptr = lowD(carry);
1203 inline void mulu_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1204 { var uintD carry = 0;
1206 { // Hier ist carry=digit=0 oder 0 <= carry < digit.
1209 muluD(digit,*--sourceptr,hi=,lo=);
1210 // Hier ist 0 <= 2^intDsize*hi + lo + carry < 2^intDsize*digit oder hi=lo=carry=digit=0.
1211 lo += carry; if (lo < carry) { hi += 1; }
1219 // Multiplikations-Einfachschleife mit Akkumulation:
1220 // Multipliziert eine UDS mit einem Digit und addiert das Ergebnis zu einer
1222 // muluadd_loop_down(digit,sourceptr,destptr,len);
1223 // multipliziert die UDS sourceptr[-len..-1] (len>0)
1224 // mit dem einzelnen digit, legt das Ergebnis in der UDS destptr[-len..-1]
1225 // ab und liefert den weiteren Übertrag.
1227 inline uintD muluadd_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1228 { var uintDD carry = 0;
1230 { dotimespC(len,len,
1231 { // Hier ist 0 <= carry <= digit.
1232 carry = carry + muluD(digit,*--sourceptr) + (uintDD)*--destptr;
1233 // Hier ist 0 <= carry <= 2^intDsize*digit + 2^intDsize-1.
1234 *destptr = lowD(carry);
1235 carry = (uintDD)highD(carry); // carry := floor(carry/2^intDsize) <= digit
1241 inline uintD muluadd_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1242 { var uintD carry = 0;
1244 { dotimespC(len,len,
1245 { // Hier ist 0 <= carry <= digit.
1248 muluD(digit,*--sourceptr,hi=,lo=);
1249 // Hier ist 0 <= 2^intDsize*hi + lo + carry + *--destptr <= 2^intDsize*digit+2^intDsize-1.
1250 lo += carry; if (lo < carry) { hi += 1; }
1252 lo += carry; if (lo < carry) { hi += 1; }
1261 // Multiplikations-Einfachschleife mit Diminution:
1262 // Multipliziert eine UDS mit einem Digit und subtrahiert das Ergebnis von
1263 // einer zweiten UDS.
1264 // mulusub_loop_down(digit,sourceptr,destptr,len);
1265 // multipliziert die UDS sourceptr[-len..-1] (len>0) mit dem einzelnen
1266 // digit, subtrahiert das Ergebnis von der UDS destptr[-len..-1] und liefert
1267 // den weiteren Übertrag (>=0, evtl. von destptr[-len-1] zu subtrahieren).
1269 inline uintD mulusub_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1270 { var uintDD carry = 0;
1272 { dotimespC(len,len,
1273 { // Hier ist 0 <= carry <= digit.
1274 carry = carry + muluD(digit,*--sourceptr) + (uintD)(~(*--destptr));
1275 // Hier ist 0 <= carry <= 2^intDsize*digit + 2^intDsize-1.
1276 *destptr = ~lowD(carry);
1277 carry = (uintDD)highD(carry); // carry := floor(carry/2^intDsize) <= digit
1278 // Hier ist 0 <= carry <= digit.
1283 return 0; // nichts zu subtrahieren -> kein Übertrag
1286 inline uintD mulusub_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1287 { var uintD carry = 0;
1289 { dotimespC(len,len,
1290 { // Hier ist 0 <= carry <= digit.
1293 muluD(digit,*--sourceptr,hi=,lo=);
1294 // Hier ist 0 <= 2^intDsize*hi + lo + carry + ~(*--destptr) <= 2^intDsize*digit+2^intDsize-1.
1295 lo += carry; if (lo < carry) { hi += 1; }
1297 *destptr = carry - lo; if (carry < lo) { hi += 1; }
1303 return 0; // nichts zu subtrahieren -> kein Übertrag
1311 // Divisions-Einfachschleife:
1312 // Dividiert eine UDS durch ein Digit.
1313 // divu_loop_up(digit,ptr,len)
1314 // dividiert die UDS ptr[0..len-1] durch digit,
1315 // legt das Ergebnis in derselben UDS ab, und liefert den Rest (>=0, <digit).
1317 inline uintD divu_loop_up (uintD digit, uintD* ptr, uintC len)
1318 { var uintD rest = 0;
1320 { divuD(highlowDD(rest,*ptr),digit,*ptr =, rest =); ptr++; }
1325 inline uintD divu_loop_up (uintD digit, uintD* ptr, uintC len)
1326 { var uintD rest = 0;
1328 { divuD(rest,*ptr,digit,*ptr =, rest =); ptr++; }
1334 // Divisions-Einfachschleife:
1335 // Dividiert eine UDS durch ein Digit und legt das Ergebnis in einer
1337 // divucopy_loop_up(digit,sourceptr,destptr,len)
1338 // dividiert die UDS sourceptr[0..len-1] durch digit,
1339 // legt das Ergebnis in der UDS destptr[0..len-1] ab,
1340 // und liefert den Rest (>=0, <digit).
1342 inline uintD divucopy_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1343 { var uintD rest = 0;
1345 { divuD(highlowDD(rest,*sourceptr++),digit,*destptr++ =, rest =); }
1350 inline uintD divucopy_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1351 { var uintD rest = 0;
1353 { divuD(rest,*sourceptr++,digit,*destptr++ =, rest =); }
1361 #else // !CL_DS_BIG_ENDIAN_P
1366 // or_loop_down(xptr,yptr,count);
1367 // verknüpft count (uintC>=0) Digits abwärts ab xptr und ab yptr
1368 // mit Ziel ab xptr durch OR.
1369 inline void or_loop_down (uintD* xptr, const uintD* yptr, uintC count)
1370 { dotimesC(count,count, { *--xptr |= *--yptr; } ); }
1373 // xor_loop_down(xptr,yptr,count);
1374 // verknüpft count (uintC>=0) Digits abwärts ab xptr und ab yptr
1375 // mit Ziel ab xptr durch XOR.
1376 inline void xor_loop_down (uintD* xptr, const uintD* yptr, uintC count)
1377 { dotimesC(count,count, { *--xptr ^= *--yptr; } ); }
1380 // and_loop_down(xptr,yptr,count);
1381 // verknüpft count (uintC>=0) Digits abwärts ab xptr und ab yptr
1382 // mit Ziel ab xptr durch AND.
1383 inline void and_loop_down (uintD* xptr, const uintD* yptr, uintC count)
1384 { dotimesC(count,count, { *--xptr &= *--yptr; } ); }
1387 // eqv_loop_down(xptr,yptr,count);
1388 // verknüpft count (uintC>=0) Digits abwärts ab xptr und ab yptr
1389 // mit Ziel ab xptr durch EQV (NOT XOR).
1390 inline void eqv_loop_down (uintD* xptr, const uintD* yptr, uintC count)
1391 { dotimesC(count,count,
1392 {var uintD temp = ~ (*--xptr ^ *--yptr); *xptr = temp; }
1397 // nand_loop_down(xptr,yptr,count);
1398 // verknüpft count (uintC>=0) Digits abwärts ab xptr und ab yptr
1399 // mit Ziel ab xptr durch NAND (NOT AND).
1400 inline void nand_loop_down (uintD* xptr, const uintD* yptr, uintC count)
1401 { dotimesC(count,count,
1402 {var uintD temp = ~ (*--xptr & *--yptr); *xptr = temp; }
1407 // nor_loop_down(xptr,yptr,count);
1408 // verknüpft count (uintC>=0) Digits abwärts ab xptr und ab yptr
1409 // mit Ziel ab xptr durch NOR (NOT OR).
1410 inline void nor_loop_down (uintD* xptr, const uintD* yptr, uintC count)
1411 { dotimesC(count,count,
1412 {var uintD temp = ~ (*--xptr | *--yptr); *xptr = temp; }
1417 // andc2_loop_down(xptr,yptr,count);
1418 // verknüpft count (uintC>=0) Digits abwärts ab xptr und ab yptr
1419 // mit Ziel ab xptr durch ANDC2 (AND NOT).
1420 inline void andc2_loop_down (uintD* xptr, const uintD* yptr, uintC count)
1421 { dotimesC(count,count, { *--xptr &= ~(*--yptr); } ); }
1424 // orc2_loop_down(xptr,yptr,count);
1425 // verknüpft count (uintC>=0) Digits abwärts ab xptr und ab yptr
1426 // mit Ziel ab xptr durch ORC2 (OR NOT).
1427 inline void orc2_loop_down (uintD* xptr, const uintD* yptr, uintC count)
1428 { dotimesC(count,count, { *--xptr |= ~(*--yptr); } ); }
1431 // not_loop_down(xptr,count);
1432 // verknüpft count (uintC>0) Digits abwärts ab xptr mit Ziel ab xptr
1434 inline void not_loop_down (uintD* xptr, uintC count)
1435 { dotimespC(count,count,
1436 {var uintD temp = ~ (*--xptr); *xptr = temp; }
1444 // AND-Test-Schleife:
1445 // and_test_loop_down(xptr,yptr,count);
1446 // verknüpft count (uintC>=0) Digits abwärts ab xptr und ab yptr durch AND
1447 // und testet, ob sich dabei ein Digit /=0 ergibt. Ergebnis true, falls ja.
1448 inline bool and_test_loop_down (const uintD* xptr, const uintD* yptr, uintC count)
1449 { dotimesC(count,count, { if (*--xptr & *--yptr) return true; } );
1453 // Vergleichsschleife:
1454 // result = compare_loop_down(xptr,yptr,count);
1455 // vergleicht nacheinander xptr[-1] mit yptr[-1], xptr[-2] mit yptr[-2], usw.,
1456 // insgesamt count Digits, und liefert 0 falls alle gleich sind,
1457 // +1 falls zuerst ein xptr[i]>yptr[i] ist,
1458 // -1 falls zuerst ein xptr[i]<yptr[i] ist.
1459 inline cl_signean compare_loop_down (const uintD* xptr, const uintD* yptr, uintC count)
1460 { dotimesC(count,count,
1461 { if (!(*--xptr == *--yptr))
1462 // verschiedene Digits gefunden
1463 return (*xptr > *yptr ? signean_plus : signean_minus);
1465 return signean_null; // alle Digits gleich
1470 #ifndef ADDSUB_LOOPS
1472 // Additionsschleife:
1473 // übertrag = add_loop_up(sourceptr1,sourceptr2,destptr,count);
1474 // addiert count (uintC>=0) Digits aufwärts von sourceptr1, von sourceptr2
1475 // aufwärts nach destptr und liefert den Übertrag (0 oder /=0, was 1 bedeutet).
1476 inline uintD add_loop_up (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count)
1477 { var uintD source1;
1480 do { source1 = *sourceptr1++;
1481 source2 = *sourceptr2++;
1482 *destptr++ = source1 + source2;
1483 if (source1 > (uintD)(~source2)) goto carry_1;
1489 do { source1 = *sourceptr1++;
1490 source2 = *sourceptr2++;
1491 *destptr++ = source1 + source2 + 1;
1492 if (source1 < (uintD)(~source2)) goto carry_0;
1500 // Additionsschleife:
1501 // übertrag = addto_loop_up(sourceptr,destptr,count);
1502 // addiert count (uintC>=0) Digits aufwärts von sourceptr, von destptr
1503 // aufwärts nach destptr und liefert den Übertrag (0 oder /=0, was 1 bedeutet).
1504 inline uintD addto_loop_up (const uintD* sourceptr, uintD* destptr, uintC count)
1505 { var uintD source1;
1508 do { source1 = *sourceptr++;
1510 *destptr++ = source1 + source2;
1511 if (source1 > (uintD)(~source2)) goto carry_1;
1517 do { source1 = *sourceptr++;
1519 *destptr++ = source1 + source2 + 1;
1520 if (source1 < (uintD)(~source2)) goto carry_0;
1528 // Incrementierschleife:
1529 // übertrag = inc_loop_up(ptr,count);
1530 // incrementiert count (uintC>=0) Digits aufwärts von ptr, so lange bis kein
1531 // Übertrag mehr auftritt und liefert den Übertrag (0 oder /=0, was 1 bedeutet).
1532 inline uintD inc_loop_up (uintD* ptr, uintC count)
1533 { dotimesC(count,count,
1534 { if (!( ++(*ptr++) == 0 )) return 0; } // kein weiterer Übertrag
1536 return 1; // weiterer Übertrag
1539 // Subtraktionsschleife:
1540 // übertrag = sub_loop_up(sourceptr1,sourceptr2,destptr,count);
1541 // subtrahiert count (uintC>=0) Digits aufwärts von sourceptr1, von sourceptr2
1542 // aufwärts nach destptr und liefert den Übertrag (0 oder /=0, was -1 bedeutet).
1543 inline uintD sub_loop_up (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count)
1544 { var uintD source1;
1547 do { source1 = *sourceptr1++;
1548 source2 = *sourceptr2++;
1549 *destptr++ = source1 - source2;
1550 if (source1 < source2) goto carry_1;
1556 do { source1 = *sourceptr1++;
1557 source2 = *sourceptr2++;
1558 *destptr++ = source1 - source2 - 1;
1559 if (source1 > source2) goto carry_0;
1567 // Subtraktionsschleife:
1568 // übertrag = subx_loop_up(sourceptr1,sourceptr2,destptr,count,carry);
1569 // subtrahiert count (uintC>=0) Digits aufwärts von sourceptr1 und addiert
1570 // einen Carry (0 oder -1), von sourceptr2 aufwärts nach destptr und
1571 // liefert den Übertrag (0 oder /=0, was -1 bedeutet).
1572 inline uintD subx_loop_up (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count, uintD carry)
1573 { var uintD source1;
1577 do { source1 = *sourceptr1++;
1578 source2 = *sourceptr2++;
1579 *destptr++ = source1 - source2;
1580 if (source1 < source2) goto carry_1;
1589 do { source1 = *sourceptr1++;
1590 source2 = *sourceptr2++;
1591 *destptr++ = source1 - source2 - 1;
1592 if (source1 > source2) goto carry_0;
1600 // Subtraktionsschleife:
1601 // übertrag = subfrom_loop_up(sourceptr,destptr,count);
1602 // subtrahiert count (uintC>=0) Digits aufwärts von sourceptr, von destptr
1603 // aufwärts nach destptr (dest := dest - source)
1604 // und liefert den Übertrag (0 oder /=0, was -1 bedeutet).
1605 inline uintD subfrom_loop_up (const uintD* sourceptr, uintD* destptr, uintC count)
1606 { var uintD source1;
1609 do { source1 = *destptr;
1610 source2 = *sourceptr++;
1611 *destptr++ = source1 - source2;
1612 if (source1 < source2) goto carry_1;
1618 do { source1 = *destptr;
1619 source2 = *sourceptr++;
1620 *destptr++ = source1 - source2 - 1;
1621 if (source1 > source2) goto carry_0;
1629 // Decrementierschleife:
1630 // übertrag = dec_loop_up(ptr,count);
1631 // decrementiert count (uintC>=0) Digits aufwärts von ptr, so lange bis kein
1632 // Übertrag mehr auftritt und liefert den Übertrag (0 oder -1).
1633 inline uintD dec_loop_up (uintD* ptr, uintC count)
1634 { dotimesC(count,count,
1635 { if (!( (*ptr++)-- == 0 )) return 0; } // kein weiterer Übertrag
1637 return (uintD)(-1); // weiterer Übertrag
1641 // übertrag = neg_loop_up(ptr,count);
1642 // negiert count (uintC>=0) Digits aufwärts von ptr,
1643 // und liefert den Übertrag (0 oder -1).
1644 inline uintD neg_loop_up (uintD* ptr, uintC count)
1645 { // erstes Digit /=0 suchen:
1646 until (count==0) { if (!(*ptr == 0)) goto L1; ptr++; count--; }
1648 L1: // erstes Digit /=0 gefunden, ab jetzt gibt's Carrys
1649 *ptr = - *ptr; count--; // 1 Digit negieren
1650 dotimesC(count,count, { ptr++; *ptr = ~ *ptr; } ); // alle anderen Digits invertieren
1658 // Schiebeschleife um 1 Bit nach links:
1659 // übertrag = shift1left_loop_up(ptr,count);
1660 // schiebt count (uintC>=0) Digits aufwärts von ptr um 1 Bit nach links,
1661 // und liefert den Übertrag (0 oder /=0, was 1 bedeutet).
1663 inline uintD shift1left_loop_up (uintD* ptr, uintC count)
1664 { var uintDD accu = 0;
1665 dotimesC(count,count,
1666 { accu = ((uintDD)(*ptr)<<1)+accu; *ptr++ = lowD(accu);
1667 accu = (uintDD)(highD(accu));
1672 inline uintD shift1left_loop_up (uintD* ptr, uintC count)
1673 { var uintD carry = 0;
1674 dotimesC(count,count,
1675 { var uintD accu = *ptr;
1676 *ptr++ = (accu<<1) | carry;
1677 carry = accu>>(intDsize-1);
1683 // Schiebeschleife um i Bits nach links:
1684 // übertrag = shiftleft_loop_up(ptr,count,i,übertrag_init);
1685 // schiebt count (uintC>=0) Digits aufwärts von ptr um i Bits (0<i<intDsize)
1686 // nach links, schiebt dabei die i Bits aus übertrag_init rechts rein,
1687 // und liefert den Übertrag (was links rauskommt, >=0, <2^i).
1689 inline uintD shiftleft_loop_up (uintD* ptr, uintC count, uintC i, uintD carry)
1690 { var uintDD accu = (uintDD)carry;
1691 dotimesC(count,count,
1692 { accu = ((uintDD)(*ptr)<<i)+accu; *ptr++ = lowD(accu);
1693 accu = (uintDD)(highD(accu));
1698 inline uintD shiftleft_loop_up (uintD* ptr, uintC count, uintC i, uintD carry)
1699 { var uintC j = intDsize-i;
1700 dotimesC(count,count,
1701 { var uintD accu = *ptr;
1702 *ptr++ = (accu<<i) | carry;
1709 // Schiebe- und Kopierschleife um i Bits nach links:
1710 // übertrag = shiftleftcopy_loop_up(sourceptr,destptr,count,i);
1711 // kopiert count (uintC>=0) Digits aufwärts von sourceptr nach destptr
1712 // und schiebt sie dabei um i Bits (0<i<intDsize) nach links,
1713 // wobei ganz rechts mit i Nullbits aufgefüllt wird,
1714 // und liefert den Übertrag (was links rauskommt, >=0, <2^i).
1716 inline uintD shiftleftcopy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count, uintC i)
1717 { var uintDD accu = 0;
1718 dotimesC(count,count,
1719 { accu = ((uintDD)(*sourceptr++)<<i)+accu; *destptr++ = lowD(accu);
1720 accu = (uintDD)(highD(accu));
1725 inline uintD shiftleftcopy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count, uintC i)
1726 { var uintC j = intDsize-i;
1727 var uintD carry = 0;
1728 dotimesC(count,count,
1729 { var uintD accu = *sourceptr++;
1730 *destptr++ = (accu<<i) | carry;
1737 // Schiebeschleife um 1 Bit nach rechts:
1738 // übertrag = shift1right_loop_down(ptr,count,übertrag_init);
1739 // schiebt count (uintC>=0) Digits abwärts von ptr um 1 Bit nach rechts,
1740 // wobei links das Bit übertrag_init (sollte =0 oder =-1 sein) hineingeschoben
1741 // wird, und liefert den Übertrag (0 oder /=0, was 1 bedeutet).
1743 inline uintD shift1right_loop_down (uintD* ptr, uintC count, uintD carry)
1744 { var uintDD accu = (sintDD)(sintD)carry & ((uintDD)1 << (2*intDsize-1)); // 0 oder bit(2*intDsize-1)
1745 dotimesC(count,count,
1746 { accu = (highlowDD_0(*--ptr)>>1)+accu; *ptr = highD(accu);
1747 accu = highlowDD_0(lowD(accu));
1752 inline uintD shift1right_loop_down (uintD* ptr, uintC count, uintD carry)
1753 { carry = carry << (intDsize-1); // carry zu einem einzigen Bit machen
1754 dotimesC(count,count,
1755 { var uintD accu = *--ptr;
1756 *ptr = (accu >> 1) | carry;
1757 carry = accu << (intDsize-1);
1763 // Schiebeschleife um i Bits nach rechts:
1764 // übertrag = shiftright_loop_down(ptr,count,i);
1765 // schiebt count (uintC>=0) Digits abwärts von ptr um i Bits (0<i<intDsize)
1766 // nach rechts, wobei links Nullen eingeschoben werden,
1767 // und liefert den Übertrag (was rechts rauskommt, als Bits intDsize-1..intDsize-i).
1769 inline uintD shiftright_loop_down (uintD* ptr, uintC count, uintC i)
1770 { var uintDD accu = 0;
1771 dotimesC(count,count,
1772 { // Die oberen i Bits von (uintD)accu bilden hier den Übertrag.
1773 accu = highlowDD_0(lowD(accu));
1774 // Die oberen i Bits von (uintDD)accu bilden hier den Übertrag.
1775 accu = (highlowDD_0(*--ptr)>>i)+accu; *ptr = highD(accu);
1780 inline uintD shiftright_loop_down (uintD* ptr, uintC count, uintC i)
1781 { var uintC j = intDsize-i;
1782 var uintD carry = 0;
1783 dotimesC(count,count,
1784 { var uintD accu = *--ptr;
1785 *ptr = (accu >> i) | carry;
1792 // Schiebeschleife um i Bits nach rechts:
1793 // übertrag = shiftrightsigned_loop_down(ptr,count,i);
1794 // schiebt count (uintC>0) Digits abwärts von ptr um i Bits (0<i<intDsize)
1795 // nach rechts, wobei links das MSBit ver-i-facht wird,
1796 // und liefert den Übertrag (was rechts rauskommt, als Bits intDsize-1..intDsize-i).
1798 inline uintD shiftrightsigned_loop_down (uintD* ptr, uintC count, uintC i)
1799 { var uintDD accu = // Übertrag mit i Vorzeichenbits initialisieren
1800 highlowDD_0(sign_of_sintD((sintD)(ptr[-1])))>>i;
1801 dotimespC(count,count,
1802 { // Die oberen i Bits von (uintD)accu bilden hier den Übertrag.
1803 accu = highlowDD_0(lowD(accu));
1804 // Die oberen i Bits von (uintDD)accu bilden hier den Übertrag.
1805 accu = (highlowDD_0(*--ptr)>>i)+accu; *ptr = highD(accu);
1810 inline uintD shiftrightsigned_loop_down (uintD* ptr, uintC count, uintC i)
1811 { var uintC j = intDsize-i;
1813 { var uintD accu = *--ptr;
1814 *ptr = (sintD)accu >> i;
1818 dotimesC(count,count,
1819 { var uintD accu = *--ptr;
1820 *ptr = (accu >> i) | carry;
1827 // Schiebe- und Kopier-Schleife um i Bits nach rechts:
1828 // übertrag = shiftrightcopy_loop_down(sourceptr,destptr,count,i,carry);
1829 // kopiert count (uintC>=0) Digits abwärts von sourceptr nach destptr
1830 // und schiebt sie dabei um i Bits (0<i<intDsize) nach rechts, wobei carry
1831 // (sozusagen als sourceptr[0]) die i Bits ganz links bestimmt,
1832 // und liefert den Übertrag (was rechts rauskommt, als Bits intDsize-1..intDsize-i).
1834 inline uintD shiftrightcopy_loop_down (const uintD* sourceptr, uintD* destptr, uintC count, uintC i, uintD carry)
1835 { var uintDD accu = // Übertrag mit carry initialisieren
1836 highlowDD_0(carry)>>i;
1837 dotimesC(count,count,
1838 { // Die oberen i Bits von (uintD)accu bilden hier den Übertrag.
1839 accu = highlowDD_0(lowD(accu));
1840 // Die oberen i Bits von (uintDD)accu bilden hier den Übertrag.
1841 accu = (highlowDD_0(*--sourceptr)>>i)+accu; *--destptr = highD(accu);
1846 inline uintD shiftrightcopy_loop_down (const uintD* sourceptr, uintD* destptr, uintC count, uintC i, uintD carry)
1847 { var uintC j = intDsize-i;
1849 dotimesC(count,count,
1850 { var uintD accu = *--sourceptr;
1851 *--destptr = (accu >> i) | carry;
1862 // Multiplikations-Einfachschleife:
1863 // Multipliziert eine UDS mit einem kleinen Digit und addiert ein kleines Digit.
1864 // mulusmall_loop_up(digit,ptr,len,newdigit)
1865 // multipliziert die UDS ptr[0..len-1] mit digit (>=2, <=36),
1866 // addiert dabei newdigit (>=0, <digit) zur letzten Ziffer,
1867 // und liefert den Carry (>=0, <digit).
1869 inline uintD mulusmall_loop_up (uintD digit, uintD* ptr, uintC len, uintD newdigit)
1870 { var uintDD carry = newdigit;
1872 { // Hier ist 0 <= carry < digit.
1873 carry = carry + muluD(digit,*ptr);
1874 // Hier ist 0 <= carry < 2^intDsize*digit.
1875 *ptr++ = lowD(carry);
1876 carry = (uintDD)highD(carry); // carry := floor(carry/2^intDsize) < digit
1881 inline uintD mulusmall_loop_up (uintD digit, uintD* ptr, uintC len, uintD newdigit)
1882 { var uintD carry = newdigit;
1884 { // Hier ist 0 <= carry < digit.
1887 muluD(digit,*ptr,hi=,lo=);
1888 // Hier ist 0 <= 2^intDsize*hi + lo + carry < 2^intDsize*digit.
1889 lo += carry; if (lo < carry) { hi += 1; }
1897 // Multiplikations-Einfachschleife:
1898 // Multipliziert eine UDS mit einem Digit und legt das Ergebnis in einer
1900 // mulu_loop_up(digit,sourceptr,destptr,len);
1901 // multipliziert die UDS sourceptr[0..len-1] (len>0)
1902 // mit dem einzelnen digit
1903 // und legt das Ergebnis in der UDS destptr[0..len] ab.
1905 inline void mulu_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1906 { var uintDD carry = 0;
1908 { // Hier ist carry=digit=0 oder 0 <= carry < digit.
1909 carry = carry + muluD(digit,*sourceptr++);
1910 // Hier ist carry=digit=0 oder 0 <= carry < 2^intDsize*digit.
1911 *destptr++ = lowD(carry);
1912 carry = (uintDD)highD(carry); // carry := floor(carry/2^intDsize) < digit
1914 *destptr++ = lowD(carry);
1917 inline void mulu_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1918 { var uintD carry = 0;
1920 { // Hier ist carry=digit=0 oder 0 <= carry < digit.
1923 muluD(digit,*sourceptr++,hi=,lo=);
1924 // Hier ist 0 <= 2^intDsize*hi + lo + carry < 2^intDsize*digit oder hi=lo=carry=digit=0.
1925 lo += carry; if (lo < carry) { hi += 1; }
1933 // Multiplikations-Einfachschleife mit Akkumulation:
1934 // Multipliziert eine UDS mit einem Digit und addiert das Ergebnis zu einer
1936 // muluadd_loop_up(digit,sourceptr,destptr,len);
1937 // multipliziert die UDS sourceptr[0..len-1] (len>0)
1938 // mit dem einzelnen digit, legt das Ergebnis in der UDS destptr[0..len-1]
1939 // ab und liefert den weiteren Übertrag.
1941 inline uintD muluadd_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1942 { var uintDD carry = 0;
1944 { dotimespC(len,len,
1945 { // Hier ist 0 <= carry <= digit.
1946 carry = carry + muluD(digit,*sourceptr++) + (uintDD)*destptr;
1947 // Hier ist 0 <= carry <= 2^intDsize*digit + 2^intDsize-1.
1948 *destptr++ = lowD(carry);
1949 carry = (uintDD)highD(carry); // carry := floor(carry/2^intDsize) <= digit
1955 inline uintD muluadd_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1956 { var uintD carry = 0;
1958 { dotimespC(len,len,
1959 { // Hier ist 0 <= carry <= digit.
1962 muluD(digit,*sourceptr++,hi=,lo=);
1963 // Hier ist 0 <= 2^intDsize*hi + lo + carry + *destptr <= 2^intDsize*digit+2^intDsize-1.
1964 lo += carry; if (lo < carry) { hi += 1; }
1966 lo += carry; if (lo < carry) { hi += 1; }
1975 // Multiplikations-Einfachschleife mit Diminution:
1976 // Multipliziert eine UDS mit einem Digit und subtrahiert das Ergebnis von
1977 // einer zweiten UDS.
1978 // mulusub_loop_up(digit,sourceptr,destptr,len);
1979 // multipliziert die UDS sourceptr[0..len-1] (len>0) mit dem einzelnen
1980 // digit, subtrahiert das Ergebnis von der UDS destptr[0..len-1] und liefert
1981 // den weiteren Übertrag (>=0, evtl. von destptr[len] zu subtrahieren).
1983 inline uintD mulusub_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1984 { var uintDD carry = 0;
1986 { dotimespC(len,len,
1987 { // Hier ist 0 <= carry <= digit.
1988 carry = carry + muluD(digit,*sourceptr++) + (uintD)(~(*destptr));
1989 // Hier ist 0 <= carry <= 2^intDsize*digit + 2^intDsize-1.
1990 *destptr++ = ~lowD(carry);
1991 carry = (uintDD)highD(carry); // carry := floor(carry/2^intDsize) <= digit
1992 // Hier ist 0 <= carry <= digit.
1997 return 0; // nichts zu subtrahieren -> kein Übertrag
2000 inline uintD mulusub_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
2001 { var uintD carry = 0;
2003 { dotimespC(len,len,
2004 { // Hier ist 0 <= carry <= digit.
2007 muluD(digit,*sourceptr++,hi=,lo=);
2008 // Hier ist 0 <= 2^intDsize*hi + lo + carry + ~(*destptr) <= 2^intDsize*digit+2^intDsize-1.
2009 lo += carry; if (lo < carry) { hi += 1; }
2011 *destptr++ = carry - lo; if (carry < lo) { hi += 1; }
2017 return 0; // nichts zu subtrahieren -> kein Übertrag
2025 // Divisions-Einfachschleife:
2026 // Dividiert eine UDS durch ein Digit.
2027 // divu_loop_down(digit,ptr,len)
2028 // dividiert die UDS ptr[-len..-1] durch digit,
2029 // legt das Ergebnis in derselben UDS ab, und liefert den Rest (>=0, <digit).
2031 inline uintD divu_loop_down (uintD digit, uintD* ptr, uintC len)
2032 { var uintD rest = 0;
2034 { --ptr; divuD(highlowDD(rest,*ptr),digit,*ptr =, rest =); }
2039 inline uintD divu_loop_down (uintD digit, uintD* ptr, uintC len)
2040 { var uintD rest = 0;
2042 { --ptr; divuD(rest,*ptr,digit,*ptr =, rest =); }
2048 // Divisions-Einfachschleife:
2049 // Dividiert eine UDS durch ein Digit und legt das Ergebnis in einer
2051 // divucopy_loop_down(digit,sourceptr,destptr,len)
2052 // dividiert die UDS sourceptr[-len..-1] durch digit,
2053 // legt das Ergebnis in der UDS destptr[-len..-1] ab,
2054 // und liefert den Rest (>=0, <digit).
2056 inline uintD divucopy_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
2057 { var uintD rest = 0;
2059 { divuD(highlowDD(rest,*--sourceptr),digit,*--destptr =, rest =); }
2064 inline uintD divucopy_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
2065 { var uintD rest = 0;
2067 { divuD(rest,*--sourceptr,digit,*--destptr =, rest =); }
2075 #endif // !CL_DS_BIG_ENDIAN_P
2077 #if !defined(TEST_LOOPS) && !CL_DS_BIG_ENDIAN_P
2079 // Vergleichsschleife:
2080 // result = compare_loop_up(xptr,yptr,count);
2081 // vergleicht nacheinander xptr[0] mit yptr[0], xptr[1] mit yptr[1], usw.,
2082 // insgesamt count Digits, und liefert 0 falls alle gleich sind,
2083 // +1 falls zuerst ein xptr[i]>yptr[i] ist,
2084 // -1 falls zuerst ein xptr[i]<yptr[i] ist.
2085 inline cl_signean compare_loop_up (const uintD* xptr, const uintD* yptr, uintC count)
2086 { dotimesC(count,count,
2087 { if (!(*xptr++ == *yptr++))
2088 // verschiedene Digits gefunden
2089 return (*--xptr > *--yptr ? signean_plus : signean_minus);
2091 return signean_null; // alle Digits gleich
2096 #if !defined(LOG_LOOPS) && !CL_DS_BIG_ENDIAN_P
2099 // xor_loop_up(xptr,yptr,count);
2100 // verknüpft count (uintC>=0) Digits aufwärts ab xptr und ab yptr
2101 // mit Ziel ab xptr durch XOR.
2102 inline void xor_loop_up (uintD* xptr, const uintD* yptr, uintC count)
2103 { dotimesC(count,count, { *xptr++ ^= *yptr++; } ); }
2107 #if !defined(SHIFT_LOOPS) && CL_DS_BIG_ENDIAN_P
2109 // Schiebe- und Kopierschleife um i Bits nach links:
2110 // übertrag = shiftleftcopy_loop_up(sourceptr,destptr,count,i);
2111 // kopiert count (uintC>=0) Digits aufwärts von sourceptr nach destptr
2112 // und schiebt sie dabei um i Bits (0<i<intDsize) nach links,
2113 // wobei ganz rechts mit i Nullbits aufgefüllt wird,
2114 // und liefert den Übertrag (was links rauskommt, >=0, <2^i).
2116 inline uintD shiftleftcopy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count, uintC i)
2117 { var uintDD accu = 0;
2118 dotimesC(count,count,
2119 { accu = ((uintDD)(*sourceptr++)<<i)+accu; *destptr++ = lowD(accu);
2120 accu = (uintDD)(highD(accu));
2125 inline uintD shiftleftcopy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count, uintC i)
2126 { var uintC j = intDsize-i;
2127 var uintD carry = 0;
2128 dotimesC(count,count,
2129 { var uintD accu = *sourceptr++;
2130 *destptr++ = (accu<<i) | carry;
2139 #if !defined(SHIFT_LOOPS)
2141 // Schiebe- und XOR-Schleife:
2142 // shiftxor_loop_up(xptr,yptr,count,i);
2143 // verknüpft count+1 Digits aufwärts ab xptr mit count Digits aufwärts ab yptr,
2144 // um i Bits verschoben, durch XOR. (count uintC>=0, 0<i<intDsize)
2146 inline void shiftxor_loop_up (uintD* xptr, const uintD* yptr, uintC count, uintC i)
2148 { var uintD carry = xptr[0];
2149 dotimespC(count,count,
2150 { var uintDD accu = highlowDD(xptr[1],carry);
2151 accu = ((uintDD)(*yptr++)<<i) ^ accu;
2152 *xptr++ = lowD(accu);
2153 carry = highD(accu);
2158 inline void shiftxor_loop_up (uintD* xptr, const uintD* yptr, uintC count, uintC i)
2160 { var uintC j = intDsize-i;
2161 var uintD carry = *xptr;
2162 dotimespC(count,count,
2163 { var uintD accu = *yptr++;
2164 *xptr++ = (accu<<i) ^ carry;
2165 carry = (accu>>j) ^ *xptr;
2174 // Endianness independent names for these functions.
2175 #if CL_DS_BIG_ENDIAN_P
2176 #define copy_loop_msp copy_loop_up
2177 #define copy_loop_lsp copy_loop_down
2178 #define fill_loop_msp fill_loop_up
2179 #define fill_loop_lsp fill_loop_down
2180 #define clear_loop_msp clear_loop_up
2181 #define clear_loop_lsp clear_loop_down
2182 #define test_loop_msp test_loop_up
2183 #define or_loop_msp or_loop_up
2184 #define xor_loop_msp xor_loop_up
2185 #define and_loop_msp and_loop_up
2186 #define eqv_loop_msp eqv_loop_up
2187 #define nand_loop_msp nand_loop_up
2188 #define nor_loop_msp nor_loop_up
2189 #define andc2_loop_msp andc2_loop_up
2190 #define orc2_loop_msp orc2_loop_up
2191 #define not_loop_msp not_loop_up
2192 #define and_test_loop_msp and_test_loop_up
2193 #define compare_loop_msp compare_loop_up
2194 #define add_loop_lsp add_loop_down
2195 #define addto_loop_lsp addto_loop_down
2196 #define inc_loop_lsp inc_loop_down
2197 #define sub_loop_lsp sub_loop_down
2198 #define subx_loop_lsp subx_loop_down
2199 #define subfrom_loop_lsp subfrom_loop_down
2200 #define dec_loop_lsp dec_loop_down
2201 #define neg_loop_lsp neg_loop_down
2202 #define shift1left_loop_lsp shift1left_loop_down
2203 #define shiftleft_loop_lsp shiftleft_loop_down
2204 #define shiftleftcopy_loop_lsp shiftleftcopy_loop_down
2205 #define shift1right_loop_msp shift1right_loop_up
2206 #define shiftright_loop_msp shiftright_loop_up
2207 #define shiftrightsigned_loop_msp shiftrightsigned_loop_up
2208 #define shiftrightcopy_loop_msp shiftrightcopy_loop_up
2209 #define mulusmall_loop_lsp mulusmall_loop_down
2210 #define mulu_loop_lsp mulu_loop_down
2211 #define muluadd_loop_lsp muluadd_loop_down
2212 #define mulusub_loop_lsp mulusub_loop_down
2213 #define divu_loop_msp divu_loop_up
2214 #define divucopy_loop_msp divucopy_loop_up
2216 #define copy_loop_msp copy_loop_down
2217 #define copy_loop_lsp copy_loop_up
2218 #define fill_loop_msp fill_loop_down
2219 #define fill_loop_lsp fill_loop_up
2220 #define clear_loop_msp clear_loop_down
2221 #define clear_loop_lsp clear_loop_up
2222 #define test_loop_msp test_loop_down
2223 #define or_loop_msp or_loop_down
2224 #define xor_loop_msp xor_loop_down
2225 #define and_loop_msp and_loop_down
2226 #define eqv_loop_msp eqv_loop_down
2227 #define nand_loop_msp nand_loop_down
2228 #define nor_loop_msp nor_loop_down
2229 #define andc2_loop_msp andc2_loop_down
2230 #define orc2_loop_msp orc2_loop_down
2231 #define not_loop_msp not_loop_down
2232 #define and_test_loop_msp and_test_loop_down
2233 #define compare_loop_msp compare_loop_down
2234 #define add_loop_lsp add_loop_up
2235 #define addto_loop_lsp addto_loop_up
2236 #define inc_loop_lsp inc_loop_up
2237 #define sub_loop_lsp sub_loop_up
2238 #define subx_loop_lsp subx_loop_up
2239 #define subfrom_loop_lsp subfrom_loop_up
2240 #define dec_loop_lsp dec_loop_up
2241 #define neg_loop_lsp neg_loop_up
2242 #define shift1left_loop_lsp shift1left_loop_up
2243 #define shiftleft_loop_lsp shiftleft_loop_up
2244 #define shiftleftcopy_loop_lsp shiftleftcopy_loop_up
2245 #define shift1right_loop_msp shift1right_loop_down
2246 #define shiftright_loop_msp shiftright_loop_down
2247 #define shiftrightsigned_loop_msp shiftrightsigned_loop_down
2248 #define shiftrightcopy_loop_msp shiftrightcopy_loop_down
2249 #define mulusmall_loop_lsp mulusmall_loop_up
2250 #define mulu_loop_lsp mulu_loop_up
2251 #define muluadd_loop_lsp muluadd_loop_up
2252 #define mulusub_loop_lsp mulusub_loop_up
2253 #define divu_loop_msp divu_loop_down
2254 #define divucopy_loop_msp divucopy_loop_down
2257 // Endianness independent loops where the direction doesn't matter.
2258 #if CL_DS_BIG_ENDIAN_P
2259 #define DS_clear_loop(MSDptr,len,LSDptr) (void)clear_loop_up(MSDptr,len)
2260 #define DS_test_loop(MSDptr,len,LSDptr) test_loop_up(MSDptr,len)
2262 #define DS_clear_loop(MSDptr,len,LSDptr) (void)clear_loop_up(LSDptr,len)
2263 #define DS_test_loop(MSDptr,len,LSDptr) test_loop_up(LSDptr,len)
2267 // Umwandlungsroutinen Digit-Sequence-Teil <--> Longword:
2270 // holt die nächsten 32 Bits aus den 32/intDsize Digits ab ptr.
2271 // set_32_Dptr(ptr,wert);
2272 // speichert den Wert wert (32 Bits) in die 32/intDsize Digits ab ptr.
2273 // get_max32_Dptr(count,ptr)
2274 // holt die nächsten count Bits aus den ceiling(count/intDsize) Digits ab ptr.
2275 // set_max32_Dptr(count,ptr,wert)
2276 // speichert wert (count Bits) in die ceiling(count/intDsize) Digits ab ptr.
2277 // Jeweils ptr eine Variable vom Typ uintD*,
2278 // wert eine Variable vom Typ uint32,
2279 // count eine Variable oder constant-expression mit Wert >=0, <=32.
2281 inline uint32 get_32_Dptr (const uintD* ptr)
2283 return mspref(ptr,0);
2285 inline void set_32_Dptr (uintD* ptr, uint32 wert)
2287 mspref(ptr,0) = wert;
2289 inline uint32 get_max32_Dptr (uintC count, const uintD* ptr)
2291 return count==0 ? 0 :
2294 inline void set_max32_Dptr (uintC count, uintD* ptr, uint32 wert)
2296 if (count==0) return;
2297 mspref(ptr,0) = wert; return;
2301 inline uint32 get_32_Dptr (const uintD* ptr)
2303 return ((uint32)mspref(ptr,0)<<16) | (uint32)mspref(ptr,1);
2305 inline void set_32_Dptr (uintD* ptr, uint32 wert)
2307 mspref(ptr,0) = (uintD)(wert>>16); mspref(ptr,1) = (uintD)wert;
2309 inline uint32 get_max32_Dptr (uintC count, const uintD* ptr)
2311 return count==0 ? 0 :
2312 count<=16 ? mspref(ptr,0) :
2313 ((uint32)mspref(ptr,0)<<16) | (uint32)mspref(ptr,1);
2315 inline void set_max32_Dptr (uintC count, uintD* ptr, uint32 wert)
2317 if (count==0) return;
2318 if (count<=16) { mspref(ptr,0) = (uintD)wert; return; }
2319 mspref(ptr,0) = (uintD)(wert>>16); mspref(ptr,1) = (uintD)wert; return;
2323 inline uint32 get_32_Dptr (const uintD* ptr)
2325 return ((((((uint32)mspref(ptr,0) <<8) | (uint32)mspref(ptr,1)) <<8) | (uint32)mspref(ptr,2)) <<8) | (uint32)mspref(ptr,3);
2327 inline void set_32_Dptr (uintD* ptr, uint32 wert)
2329 mspref(ptr,0) = (uintD)(wert>>24); mspref(ptr,1) = (uintD)(wert>>16); mspref(ptr,2) = (uintD)(wert>>8); mspref(ptr,3) = (uintD)wert;
2331 inline uint32 get_max32_Dptr (uintC count, const uintD* ptr)
2333 return count==0 ? 0 :
2334 count<=8 ? mspref(ptr,0) :
2335 count<=16 ? ((uint32)mspref(ptr,0)<<8) | (uint32)mspref(ptr,1) :
2336 count<=24 ? ((((uint32)mspref(ptr,0)<<8) | (uint32)mspref(ptr,1))<<8) | (uint32)mspref(ptr,2) :
2337 ((((((uint32)mspref(ptr,0)<<8) | (uint32)mspref(ptr,1))<<8) | (uint32)mspref(ptr,2))<<8) | (uint32)mspref(ptr,3);
2339 inline void set_max32_Dptr (uintC count, uintD* ptr, uint32 wert)
2341 if (count==0) return;
2342 if (count<=8) { mspref(ptr,0) = (uintD)wert; return; }
2343 if (count<=16) { mspref(ptr,0) = (uintD)(wert>>8); mspref(ptr,1) = (uintD)wert; return; }
2344 if (count<=24) { mspref(ptr,0) = (uintD)(wert>>16); mspref(ptr,1) = (uintD)(wert>>8); mspref(ptr,2) = (uintD)wert; return; }
2345 mspref(ptr,0) = (uintD)(wert>>24); mspref(ptr,1) = (uintD)(wert>>16); mspref(ptr,2) = (uintD)(wert>>8); mspref(ptr,3) = (uintD)wert; return;
2349 #if (cl_word_size==64)
2351 // holt die nächsten 64 Bits aus den 64/intDsize Digits ab ptr.
2352 // set_64_Dptr(ptr,wert);
2353 // speichert den Wert wert (64 Bits) in die 64/intDsize Digits ab ptr.
2354 // get_max64_Dptr(count,ptr)
2355 // holt die nächsten count Bits aus den ceiling(count/intDsize) Digits ab ptr.
2356 // set_max64_Dptr(count,ptr,wert)
2357 // speichert wert (count Bits) in die ceiling(count/intDsize) Digits ab ptr.
2358 // Jeweils ptr eine Variable vom Typ uintD*,
2359 // wert eine Variable vom Typ uint64,
2360 // count eine Variable oder constant-expression mit Wert >=0, <=64.
2362 inline uint64 get_64_Dptr (const uintD* ptr)
2364 return mspref(ptr,0);
2366 inline void set_64_Dptr (uintD* ptr, uint64 wert)
2368 mspref(ptr,0) = wert;
2370 inline uint64 get_max64_Dptr (uintC count, const uintD* ptr)
2372 return count==0 ? 0 : mspref(ptr,0);
2374 inline void set_max64_Dptr (uintC count, uintD* ptr, uint64 wert)
2376 if (count==0) return;
2377 mspref(ptr,0) = wert; return;
2379 #else // (intDsize<=32)
2380 inline uint64 get_64_Dptr (const uintD* ptr)
2382 return ((uint64)get_32_Dptr(ptr) << 32) | (uint64)get_32_Dptr(ptr mspop 32/intDsize);
2384 inline void set_64_Dptr (uintD* ptr, uint64 wert)
2386 set_32_Dptr(ptr,(uint32)(wert>>32));
2387 set_32_Dptr(ptr mspop 32/intDsize,(uint32)wert);
2389 inline uint64 get_max64_Dptr (uintC count, const uintD* ptr)
2391 return count==0 ? 0 :
2392 count<=32 ? (uint64)get_max32_Dptr(count,ptr) :
2393 ((uint64)get_max32_Dptr(count-32,ptr) << 32) | (uint64)get_32_Dptr(ptr mspop ceiling(count-32,intDsize));
2395 inline void set_max64_Dptr (uintC count, uintD* ptr, uint64 wert)
2397 if (count==0) return;
2398 if (count<=32) { set_max32_Dptr(count,ptr,(uint32)wert); return; }
2399 set_max32_Dptr(count-32,ptr,(uint32)(wert>>32));
2400 set_32_Dptr(ptr mspop ceiling(count-32,intDsize),(uint32)wert); return;
2405 // get_uint1D_Dptr(ptr) holt 1 Digit (unsigned) ab ptr
2406 // get_uint2D_Dptr(ptr) holt 2 Digits (unsigned) ab ptr
2407 // get_uint3D_Dptr(ptr) holt 3 Digits (unsigned) ab ptr
2408 // get_uint4D_Dptr(ptr) holt 4 Digits (unsigned) ab ptr
2409 // get_sint1D_Dptr(ptr) holt 1 Digit (signed) ab ptr
2410 // get_sint2D_Dptr(ptr) holt 2 Digits (signed) ab ptr
2411 // get_sint3D_Dptr(ptr) holt 3 Digits (signed) ab ptr
2412 // get_sint4D_Dptr(ptr) holt 4 Digits (signed) ab ptr
2413 // Jeweils ptr eine Variable vom Typ uintD*.
2414 // NB: Bei intDsize==64 sind diese Funktionen nur sehr bedingt tauglich.
2415 inline uint32 get_uint1D_Dptr (const uintD* ptr)
2417 return lspref(ptr,0);
2419 inline sint32 get_sint1D_Dptr (const uintD* ptr)
2421 return (sint32)(sintD)lspref(ptr,0);
2424 inline uint32 get_uint2D_Dptr (const uintD* ptr)
2426 return ((uint32)lspref(ptr,1) << intDsize) | (uint32)lspref(ptr,0);
2428 inline sint32 get_sint2D_Dptr (const uintD* ptr)
2430 return ((uint32)(sint32)(sintD)lspref(ptr,1) << intDsize) | (uint32)lspref(ptr,0);
2433 #define get_uint2D_Dptr(ptr) get_uint1D_Dptr(ptr)
2434 #define get_sint2D_Dptr(ptr) (sint32)get_uint2D_Dptr(ptr)
2437 inline uint32 get_uint3D_Dptr (const uintD* ptr)
2439 return ((((uint32)lspref(ptr,2) << intDsize) | (uint32)lspref(ptr,1)) << intDsize) | (uint32)lspref(ptr,0);
2441 inline sint32 get_sint3D_Dptr (const uintD* ptr)
2443 return ((((uint32)(sint32)(sintD)lspref(ptr,2) << intDsize) | (uint32)lspref(ptr,1)) << intDsize) | (uint32)lspref(ptr,0);
2445 inline uint32 get_uint4D_Dptr (const uintD* ptr)
2447 return ((((((uint32)lspref(ptr,3) << intDsize) | (uint32)lspref(ptr,2)) << intDsize) | (uint32)lspref(ptr,1)) << intDsize) | (uint32)lspref(ptr,0);
2449 inline sint32 get_sint4D_Dptr (const uintD* ptr)
2451 return ((((((uint32)(sint32)(sintD)lspref(ptr,3) << intDsize) | (uint32)lspref(ptr,2)) << intDsize) | (uint32)lspref(ptr,1)) << intDsize) | (uint32)lspref(ptr,0);
2454 #define get_uint3D_Dptr(ptr) get_uint2D_Dptr(ptr)
2455 #define get_sint3D_Dptr(ptr) (sint32)get_uint3D_Dptr(ptr)
2456 #define get_uint4D_Dptr(ptr) get_uint2D_Dptr(ptr)
2457 #define get_sint4D_Dptr(ptr) (sint32)get_uint4D_Dptr(ptr)
2461 // NUM_STACK ist eine Art Zahlen-Stack-Pointer.
2463 // {CL_ALLOCA_STACK;
2465 // num_stack_alloc(...);
2467 // num_stack_array(...);
2470 // CL_ALLOCA_STACK rettet den aktuellen Wert von NUM_STACK.
2471 // Dann darf beliebig oft mit num_stack_alloc/num_stack_array Platz auf dem
2472 // Zahlen-Stack belegt werden.
2473 // Beim Ende des Blocks wird NUM_STACK wieder auf den vorigen Wert gesetzt,
2474 // und der Platz gilt als wieder freigegeben.
2475 // In jeder C-Funktion sollte CL_ALLOCA_STACK nur einmal aufgerufen werden.
2476 // Wegen eines GCC-Bugs sollten Funktionen, die diese Macros benutzen,
2477 // nicht inline deklariert sein.
2479 // num_stack_array(need, low_addr = , high_addr = );
2480 // num_stack_small_array(need, low_addr = , high_addr = );
2481 // belegt need Digits auf dem Zahlen-Stack und legt die untere Grenze des
2482 // allozierten Bereichs in low_addr und die obere Grenze in high_addr ab.
2483 // Jedes von beiden ist optional.
2485 // num_stack_alloc(need, MSDptr = , LSDptr = );
2486 // num_stack_small_alloc(need, MSDptr = , LSDptr = );
2487 // belegt need Digits auf dem Zahlen-Stack und legt den MSDptr und den
2488 // LSDptr ab. Jedes von beiden ist optional.
2490 // num_stack_alloc_1(need, MSDptr = , LSDptr = );
2491 // num_stack_small_alloc_1(need, MSDptr = , LSDptr = );
2492 // wie num_stack_alloc, nur daß unterhalb von MSDptr noch ein Digit Platz
2493 // zusätzlich belegt wird.
2495 #define num_stack_array(need,low_zuweisung,high_zuweisung) \
2496 {var uintC __need = (uintC)(need); \
2497 var uintD* __array = cl_alloc_array(uintD,__need); \
2498 unused (low_zuweisung &__array[0]); unused (high_zuweisung &__array[__need]); \
2500 #define num_stack_small_array(need,low_zuweisung,high_zuweisung) \
2501 {var uintC __need = (uintC)(need); \
2502 var uintD* __array = cl_small_alloc_array(uintD,__need); \
2503 unused (low_zuweisung &__array[0]); unused (high_zuweisung &__array[__need]); \
2505 #if CL_DS_BIG_ENDIAN_P
2506 #define num_stack_alloc(need,MSDptr_zuweisung,LSDptr_zuweisung) \
2507 num_stack_array(need,MSDptr_zuweisung,LSDptr_zuweisung)
2508 #define num_stack_small_alloc(need,MSDptr_zuweisung,LSDptr_zuweisung) \
2509 num_stack_small_array(need,MSDptr_zuweisung,LSDptr_zuweisung)
2510 #define num_stack_alloc_1(need,MSDptr_zuweisung,LSDptr_zuweisung) \
2511 num_stack_array((uintC)(need)+1,MSDptr_zuweisung 1 + ,LSDptr_zuweisung)
2512 #define num_stack_small_alloc_1(need,MSDptr_zuweisung,LSDptr_zuweisung) \
2513 num_stack_small_array((uintC)(need)+1,MSDptr_zuweisung 1 + ,LSDptr_zuweisung)
2515 #define num_stack_alloc(need,MSDptr_zuweisung,LSDptr_zuweisung) \
2516 num_stack_array(need,LSDptr_zuweisung,MSDptr_zuweisung)
2517 #define num_stack_small_alloc(need,MSDptr_zuweisung,LSDptr_zuweisung) \
2518 num_stack_small_array(need,LSDptr_zuweisung,MSDptr_zuweisung)
2519 #define num_stack_alloc_1(need,MSDptr_zuweisung,LSDptr_zuweisung) \
2520 num_stack_array((uintC)(need)+1,LSDptr_zuweisung,MSDptr_zuweisung -1 + )
2521 #define num_stack_small_alloc_1(need,MSDptr_zuweisung,LSDptr_zuweisung) \
2522 num_stack_small_array((uintC)(need)+1,LSDptr_zuweisung,MSDptr_zuweisung -1 + )
2526 // Macro: In der DS MSDptr/len/LSDptr wird eine 1 unterhalb des Pointers ptr
2527 // addiert. Unterhalb von MSDptr muß 1 Digit Platz sein.
2528 // Dabei ist ptr - MSDptr = count und 0 < count <= len .
2529 // Eventuell wird MSDptr erniedrigt und len erhöht.
2530 #define DS_1_plus(ptr,count) \
2531 {var uintD* ptr_from_DS_1_plus = (ptr); \
2532 var uintC count_from_DS_1_plus = (count); \
2533 loop { if (--count_from_DS_1_plus==0) /* Zähler erniedrigen */\
2534 { /* Beim Most Significant Digit angelangt */\
2535 lsprefnext(ptr_from_DS_1_plus) += 1; \
2536 /* jetzt ist ptr_from_DS_1_plus = MSDptr */\
2537 if (mspref(ptr_from_DS_1_plus,0) == (uintD)bit(intDsize-1)) \
2538 { /* 7FFF + 1 muß zu 00008000 werden: */\
2539 lsprefnext(MSDptr) = 0; \
2544 if (!((lsprefnext(ptr_from_DS_1_plus) += 1) == 0)) /* weiterincrementieren */\
2545 break; /* kein weiterer Übertrag -> Schleife abbrechen */\
2548 // Macro: In der DS MSDptr/len/LSDptr wird eine 1 unterhalb des Pointers ptr
2549 // subtrahiert. Unterhalb von MSDptr muß 1 Digit Platz sein.
2550 // Dabei ist ptr - MSDptr = count und 0 < count <= len .
2551 // Eventuell wird MSDptr erniedrigt und len erhöht.
2552 #define DS_minus1_plus(ptr,count) \
2553 {var uintD* ptr_from_DS_minus1_plus = (ptr); \
2554 var uintC count_from_DS_minus1_plus = (count); \
2555 loop { if (--count_from_DS_minus1_plus==0) /* Zähler erniedrigen */\
2556 { /* Beim Most Significant Digit angelangt */\
2557 lsprefnext(ptr_from_DS_minus1_plus) -= 1; \
2558 /* jetzt ist ptr_from_DS_minus1_plus = MSDptr */\
2559 if (mspref(ptr_from_DS_minus1_plus,0) == (uintD)bit(intDsize-1)-1) \
2560 { /* 8000 - 1 muß zu FFFF7FFF werden: */\
2561 lsprefnext(MSDptr) = (uintD)(-1); \
2566 if (!((sintD)(lsprefnext(ptr_from_DS_minus1_plus) -= 1) == -1)) /* weiterdecrementieren */\
2567 break; /* kein weiterer Übertrag -> Schleife abbrechen */\
2571 // Multiplikations-Doppelschleife:
2572 // Multipliziert zwei UDS und legt das Ergebnis in einer dritten UDS ab.
2573 // cl_UDS_mul(sourceptr1,len1,sourceptr2,len2,destptr);
2574 // multipliziert die UDS sourceptr1[-len1..-1] (len1>0)
2575 // mit der UDS sourceptr2[-len1..-1] (len2>0)
2576 // und legt das Ergebnis in der UDS destptr[-len..-1] (len=len1+len2) ab.
2577 // Unterhalb von destptr werden len Digits Platz benötigt.
2578 extern void cl_UDS_mul (const uintD* sourceptr1, uintC len1,
2579 const uintD* sourceptr2, uintC len2,
2581 // Spezialfall sourceptr1 == sourceptr2 && len1 == len2.
2582 extern void cl_UDS_mul_square (const uintD* sourceptr, uintC len,
2585 // Multipliziert zwei Unsigned-Digit-sequences.
2586 // UDS_UDS_mul_UDS(len1,LSDptr1, len2,LSDptr2, MSDptr=,len=,LSDptr=);
2587 // multipliziert die UDS ../len1/LSDptr1 und ../len2/LSDptr2.
2588 // Dabei sollte len1>0 und len2>0 sein.
2589 // Ergebnis ist die UDS MSDptr/len/LSDptr, mit len=len1+len2, im Stack.
2590 // Dabei wird num_stack erniedrigt.
2591 #define UDS_UDS_mul_UDS(len1,LSDptr1,len2,LSDptr2, MSDptr_zuweisung,len_zuweisung,LSDptr_zuweisung) \
2592 var uintC CONCAT(len_from_UDSmul_,__LINE__) = (uintC)(len1) + (uintC)(len2); \
2593 var uintD* CONCAT(LSDptr_from_UDSmul_,__LINE__); \
2594 unused (len_zuweisung CONCAT(len_from_UDSmul_,__LINE__)); \
2595 num_stack_alloc(CONCAT(len_from_UDSmul_,__LINE__),MSDptr_zuweisung,LSDptr_zuweisung CONCAT(LSDptr_from_UDSmul_,__LINE__) =); \
2596 cl_UDS_mul((LSDptr1),(len1),(LSDptr2),(len2),CONCAT(LSDptr_from_UDSmul_,__LINE__));
2598 // Multipliziert zwei Digit-sequences.
2599 // DS_DS_mul_DS(MSDptr1,len1,LSDptr1, MSDptr2,len2,LSDptr2, MSDptr=,len=,LSDptr=);
2600 // multipliziert die DS MSDptr1/len1/LSDptr1 und MSDptr2/len2/LSDptr2.
2601 // Dabei sollte len1>0 und len2>0 sein, und beide DS sollten /= 0 sein.
2602 // Alles sollten Variablen sein!
2603 // Ergebnis ist die DS MSDptr/len/LSDptr, mit len=len1+len2, im Stack.
2604 // Dabei wird num_stack erniedrigt.
2606 // Erst unsigned multiplizieren. Dann bis zu zwei Subtraktionen.
2607 // Sei b=2^intDsize, k=len1, l=len2, n=DS1, m=DS2.
2608 // Gesucht ist n * m.
2609 // Wir errechnen erst das unsigned-product p (mod b^(k+l)).
2610 // n>0, m>0: p = n*m, n*m = p
2611 // n<0, m>0: p = (n+b^k)*m, n*m + b^(k+l) = p - b^k * m (mod b^(k+l)).
2612 // n>0, m<0: p = n*(m+b^l), n*m + b^(k+l) = p - b^l * n (mod b^(k+l)).
2613 // n<0, m<0: p = (n+b^k)*(m+b^l),
2614 // n*m = p - b^k * (m+b^l) - b^l * (n+b^k) (mod b^(k+l)).
2615 #define DS_DS_mul_DS(MSDptr1,len1,LSDptr1,MSDptr2,len2,LSDptr2, MSDptr_zuweisung,len_zuweisung,LSDptr_zuweisung) \
2616 var uintD* MSDptr0; \
2617 var uintD* LSDptr0; \
2618 var uintC len_from_DSmal = (uintC)(len1) + (uintC)(len2); \
2619 unused (len_zuweisung len_from_DSmal); \
2620 num_stack_alloc(len_from_DSmal,MSDptr_zuweisung MSDptr0 =,LSDptr_zuweisung LSDptr0 =); \
2621 var uintD MSD1_from_DSmal = mspref(MSDptr1,0); \
2622 var uintD MSD2_from_DSmal = mspref(MSDptr2,0); \
2623 var uintC len1_from_DSmal = (len1); \
2624 var uintC len2_from_DSmal = (len2); \
2625 if (MSD1_from_DSmal==0) { msprefnext(MSDptr0) = 0; len1_from_DSmal--; } \
2626 if (MSD2_from_DSmal==0) { msprefnext(MSDptr0) = 0; len2_from_DSmal--; } \
2627 cl_UDS_mul((LSDptr1),len1_from_DSmal,(LSDptr2),len2_from_DSmal,LSDptr0); \
2628 if ((sintD)MSD1_from_DSmal < 0) /* n<0 ? */\
2629 /* muß m bzw. m+b^l subtrahieren, um k Digits verschoben: */\
2630 { subfrom_loop_lsp(LSDptr2,LSDptr0 lspop len1,len2); } \
2631 if ((sintD)MSD2_from_DSmal < 0) /* m<0 ? */\
2632 /* muß n bzw. n+b^k subtrahieren, um l Digits verschoben: */\
2633 { subfrom_loop_lsp(LSDptr1,LSDptr0 lspop len2,len1); }
2636 // Dividiert zwei Unsigned Digit sequences durcheinander.
2637 // UDS_divide(a_MSDptr,a_len,a_LSDptr, b_MSDptr,b_len,b_LSDptr, &q,&r);
2638 // Die UDS a = a_MSDptr/a_len/a_LSDptr (a>=0) wird durch
2639 // die UDS b = b_MSDptr/b_len/b_LSDptr (b>=0) dividiert:
2640 // a = q * b + r mit 0 <= r < b. Bei b=0 Error.
2641 // q der Quotient, r der Rest.
2642 // q = q_MSDptr/q_len/q_LSDptr, r = r_MSDptr/r_len/r_LSDptr beides
2643 // Normalized Unsigned Digit sequences.
2644 // Vorsicht: q_LSDptr <= r_MSDptr,
2645 // Vorzeichenerweiterung von r kann q zerstören!
2646 // Vorzeichenerweiterung von q ist erlaubt.
2647 // a und b werden nicht modifiziert.
2648 // num_stack wird erniedrigt.
2649 #define UDS_divide(a_MSDptr,a_len,a_LSDptr,b_MSDptr,b_len,b_LSDptr,q_,r_) \
2650 /* Platz fürs Ergebnis machen. Brauche maximal a_len+1 Digits. */\
2651 var uintC _a_len = (a_len); \
2652 var uintD* roomptr; num_stack_alloc_1(_a_len+1,roomptr=,); \
2653 cl_UDS_divide(a_MSDptr,_a_len,a_LSDptr,b_MSDptr,b_len,b_LSDptr,roomptr,q_,r_);
2654 extern void cl_UDS_divide (const uintD* a_MSDptr, uintC a_len, const uintD* a_LSDptr,
2655 const uintD* b_MSDptr, uintC b_len, const uintD* b_LSDptr,
2656 uintD* roomptr, DS* q_, DS* r_);
2659 // Bildet zu einer Unsigned Digit sequence a die Wurzel
2660 // (genauer: Gaußklammer aus Wurzel aus a).
2661 // UDS_sqrt(a_MSDptr,a_len,a_LSDptr, &b, squarep=)
2662 // > a_MSDptr/a_len/a_LSDptr: eine UDS
2663 // < NUDS b: Gaußklammer der Wurzel aus a
2664 // < squarep: true falls a = b^2, false falls b^2 < a < (b+1)^2.
2665 // a wird nicht modifiziert.
2666 // Vorzeichenerweiterung von b ist erlaubt.
2667 // num_stack wird erniedrigt.
2668 #define UDS_sqrt(a_MSDptr,a_len,a_LSDptr,b_,squarep_zuweisung) \
2669 { /* ceiling(a_len,2) Digits Platz fürs Ergebnis machen: */\
2670 var uintC _a_len = (a_len); \
2671 num_stack_alloc_1(ceiling(_a_len,2),(b_)->MSDptr=,); \
2672 squarep_zuweisung cl_UDS_sqrt(a_MSDptr,_a_len,a_LSDptr,b_); \
2674 extern bool cl_UDS_sqrt (const uintD* a_MSDptr, uintC a_len, const uintD* a_LSDptr, DS* b_);
2677 // Auxiliary function for approximately computing 1/x
2678 // using Newton iteration.
2679 extern void cl_UDS_recip (const uintD* a_MSDptr, uintC a_len,
2680 uintD* b_MSDptr, uintC b_len);
2682 // Auxiliary function for approximately computing 1/sqrt(x)
2683 // using Newton iteration.
2684 extern void cl_UDS_recipsqrt (const uintD* a_MSDptr, uintC a_len,
2685 uintD* b_MSDptr, uintC b_len);
2689 #endif /* _CL_DS_H */