1 // Digit sequence arithmetic
7 #include "cl_gmpconfig.h"
9 #include "cl_DS_endian.h"
10 #include "cl_alloca.h"
12 // Digit Sequence (DS)
13 // a memory range with n digits (n an uintC),
14 // between two pointers MSDptr and LSDptr.
15 #if CL_DS_BIG_ENDIAN_P
16 // MSDptr LSDptr = MSDptr+n
17 // | MSD ............. LSD |
18 // [short: MSDptr/n/LSDptr ]
19 // In C: uintD* MSDptr, uintC len, MSDptr[0] ... MSDptr[len-1] are the digits.
21 // LSDptr MSDptr = LSDptr+n
22 // | LSD ............. MSD |
23 // In C: uintD* LSDptr, uintC len, LSDptr[0] ... LSDptr[len-1] are the digits.
25 // If n = 0, this represents the number 0.
26 // If n > 0, the most significant bit (i.e. bit (intDsize-1) of
27 // MSDptr[CL_DS_BIG_ENDIAN_P?0:-1]) is the sign bit. If the sign
28 // bit were repeated infinitely often, one would get an
29 // "infinite bit sequence".
31 // A Normalised Digit Sequence (NDS) is one for which the MSD is necessary,
32 // i.e. n = 0 or (n > 0 and the most significant intDsize+1 bits are not
35 // Unsigned Digit Sequence (UDS)
36 // like DS, but without sign.
38 // Normalized Unsigned Digit Sequence (NUDS):
39 // an UDS for which the MSD is necessary, i.e. n = 0 or
40 // (n > 0 and the most significant intDsize bits are not all zero).
42 // For the construction of constant DS, using "digit_header":
43 #define D1(byte0) (uintD)(byte0)
44 #define D2(byte0,byte1) (((uintD)(byte0)<<8)|(uintD)(byte1))
45 #define D4(byte0,byte1,byte2,byte3) (((uintD)(byte0)<<24)|((uintD)(byte1)<<16)|((uintD)(byte2)<<8)|((uintD)(byte3)))
46 #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)))
54 // Endianness independent access of digit sequences:
55 // mspref(MSDptr,i) access a most significant digit
56 // lspref(LSDptr,i) access a least significant digit
57 // msshrink(MSDptr) shrinks the DS by throwing away the MSD
58 // msprefnext(MSDptr) combines mspref(MSDptr,0) and msshrink(MSDptr)
59 // lsshrink(LSDptr) shrinks the DS by throwing away the LSD
60 // lsprefnext(LSDptr) combines lspref(LSDptr,0) and lsshrink(LSDptr)
61 // mspop pointer operator corresponding to msshrink, arg is widened to an uintP
62 // lspop pointer operator corresponding to lsshrink, arg is widened to an uintP
63 #if CL_DS_BIG_ENDIAN_P
64 #define mspref(p,i) (p)[i]
65 #define lspref(p,i) (p)[-(uintP)(i)-1]
66 #define msshrink(p) (p)++
67 #define msprefnext(p) (*(p)++)
68 #define lsshrink(p) (p)--
69 #define lsprefnext(p) (*--(p))
73 #define mspref(p,i) (p)[-(uintP)(i)-1]
74 #define lspref(p,i) (p)[i]
75 #define msshrink(p) (p)--
76 #define msprefnext(p) (*--(p))
77 #define lsshrink(p) (p)++
78 #define lsprefnext(p) (*(p)++)
83 // Endianness independent macros for turning an array into a digit sequence.
84 // arrayMSDptr(array,length) returns the MSDptr of array[0..length-1]
85 // arrayLSDptr(array,length) returns the LSDptr of array[0..length-1]
86 #if CL_DS_BIG_ENDIAN_P
87 #define arrayMSDptr(array,length) &(array)[0]
88 #define arrayLSDptr(array,length) &(array)[length]
90 #define arrayMSDptr(array,length) &(array)[length]
91 #define arrayLSDptr(array,length) &(array)[0]
93 #define arrayLSref(array,length,i) lspref(arrayLSDptr(array,length),i)
96 // These functions on digit sequences are either inline C++ functions
97 // or external assembler functions (see files cl_asm_*).
100 // See which functions are defined as external functions.
104 // Declare the external functions.
110 extern uintD* copy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count);
112 extern uintD* copy_loop_down (const uintD* sourceptr, uintD* destptr, uintC count);
118 extern uintD* fill_loop_up (uintD* destptr, uintC count, uintD filler);
120 extern uintD* fill_loop_down (uintD* destptr, uintC count, uintD filler);
126 extern uintD* clear_loop_up (uintD* destptr, uintC count);
128 extern uintD* clear_loop_down (uintD* destptr, uintC count);
134 extern cl_boolean test_loop_up (const uintD* ptr, uintC count);
136 extern cl_boolean test_loop_down (const uintD* ptr, uintC count);
140 #if CL_DS_BIG_ENDIAN_P
144 extern void or_loop_up (uintD* xptr, const uintD* yptr, uintC count);
146 extern void xor_loop_up (uintD* xptr, const uintD* yptr, uintC count);
148 extern void and_loop_up (uintD* xptr, const uintD* yptr, uintC count);
150 extern void eqv_loop_up (uintD* xptr, const uintD* yptr, uintC count);
152 extern void nand_loop_up (uintD* xptr, const uintD* yptr, uintC count);
154 extern void nor_loop_up (uintD* xptr, const uintD* yptr, uintC count);
156 extern void andc2_loop_up (uintD* xptr, const uintD* yptr, uintC count);
158 extern void orc2_loop_up (uintD* xptr, const uintD* yptr, uintC count);
160 extern void not_loop_up (uintD* xptr, uintC count);
166 extern cl_boolean and_test_loop_up (const uintD* xptr, const uintD* yptr, uintC count);
168 extern cl_signean compare_loop_up (const uintD* xptr, const uintD* yptr, uintC count);
174 extern uintD add_loop_down (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count);
176 extern uintD addto_loop_down (const uintD* sourceptr, uintD* destptr, uintC count);
178 extern uintD inc_loop_down (uintD* ptr, uintC count);
180 extern uintD sub_loop_down (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count);
182 extern uintD subx_loop_down (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count, uintD carry);
184 extern uintD subfrom_loop_down (const uintD* sourceptr, uintD* destptr, uintC count);
186 extern uintD dec_loop_down (uintD* ptr, uintC count);
188 extern uintD neg_loop_down (uintD* ptr, uintC count);
194 extern uintD shift1left_loop_down (uintD* ptr, uintC count);
196 extern uintD shiftleft_loop_down (uintD* ptr, uintC count, uintC i, uintD carry);
198 extern uintD shiftleftcopy_loop_down (const uintD* sourceptr, uintD* destptr, uintC count, uintC i);
200 extern uintD shift1right_loop_up (uintD* ptr, uintC count, uintD carry);
202 extern uintD shiftright_loop_up (uintD* ptr, uintC count, uintC i);
204 extern uintD shiftrightsigned_loop_up (uintD* ptr, uintC count, uintC i);
206 extern uintD shiftrightcopy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count, uintC i, uintD carry);
212 extern uintD mulusmall_loop_down (uintD digit, uintD* ptr, uintC len, uintD newdigit);
214 extern void mulu_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len);
216 extern uintD muluadd_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len);
218 extern uintD mulusub_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len);
224 extern uintD divu_loop_up (uintD digit, uintD* ptr, uintC len);
226 extern uintD divucopy_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len);
230 #else // !CL_DS_BIG_ENDIAN_P
234 extern void or_loop_down (uintD* xptr, const uintD* yptr, uintC count);
236 extern void xor_loop_down (uintD* xptr, const uintD* yptr, uintC count);
238 extern void and_loop_down (uintD* xptr, const uintD* yptr, uintC count);
240 extern void eqv_loop_down (uintD* xptr, const uintD* yptr, uintC count);
242 extern void nand_loop_down (uintD* xptr, const uintD* yptr, uintC count);
244 extern void nor_loop_down (uintD* xptr, const uintD* yptr, uintC count);
246 extern void andc2_loop_down (uintD* xptr, const uintD* yptr, uintC count);
248 extern void orc2_loop_down (uintD* xptr, const uintD* yptr, uintC count);
250 extern void not_loop_down (uintD* xptr, uintC count);
256 extern cl_boolean and_test_loop_down (const uintD* xptr, const uintD* yptr, uintC count);
258 extern cl_signean compare_loop_down (const uintD* xptr, const uintD* yptr, uintC count);
264 extern uintD add_loop_up (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count);
266 extern uintD addto_loop_up (const uintD* sourceptr, uintD* destptr, uintC count);
268 extern uintD inc_loop_up (uintD* ptr, uintC count);
270 extern uintD sub_loop_up (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count);
272 extern uintD subx_loop_up (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count, uintD carry);
274 extern uintD subfrom_loop_up (const uintD* sourceptr, uintD* destptr, uintC count);
276 extern uintD dec_loop_up (uintD* ptr, uintC count);
278 extern uintD neg_loop_up (uintD* ptr, uintC count);
284 extern uintD shift1left_loop_up (uintD* ptr, uintC count);
286 extern uintD shiftleft_loop_up (uintD* ptr, uintC count, uintC i, uintD carry);
288 extern uintD shiftleftcopy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count, uintC i);
290 extern uintD shift1right_loop_down (uintD* ptr, uintC count, uintD carry);
292 extern uintD shiftright_loop_down (uintD* ptr, uintC count, uintC i);
294 extern uintD shiftrightsigned_loop_down (uintD* ptr, uintC count, uintC i);
296 extern uintD shiftrightcopy_loop_down (const uintD* sourceptr, uintD* destptr, uintC count, uintC i, uintD carry);
302 extern uintD mulusmall_loop_up (uintD digit, uintD* ptr, uintC len, uintD newdigit);
304 extern void mulu_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len);
306 extern uintD muluadd_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len);
308 extern uintD mulusub_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len);
314 extern uintD divu_loop_down (uintD digit, uintD* ptr, uintC len);
316 extern uintD divucopy_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len);
320 #endif // !CL_DS_BIG_ENDIAN_P
322 // Independently of CL_DS_BIG_ENDIAN_P:
326 extern cl_signean compare_loop_up (const uintD* xptr, const uintD* yptr, uintC count);
332 extern void xor_loop_up (uintD* xptr, const uintD* yptr, uintC count);
338 extern uintD shiftleftcopy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count, uintC i);
340 extern void shiftxor_loop_up (uintD* xptr, const uintD* yptr, uintC count, uintC i);
347 #if defined(CL_USE_GMP)
349 // Supersede the functions by wrappers around calls to gmp mpn,
350 // for those functions where gmp is believed to be faster.
354 #if 0 // not worth it, since gmp's mpn_cmp is not optimized
355 inline cl_signean compare_loop_down (const uintD* xptr, const uintD* yptr, uintC count)
357 return mpn_cmp(xptr-count,yptr-count,count);
361 inline uintD add_loop_up (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count)
365 return mpn_add_n(destptr,sourceptr1,sourceptr2,count);
368 inline uintD addto_loop_up (const uintD* sourceptr, uintD* destptr, uintC count)
372 return mpn_add_n(destptr,destptr,sourceptr,count);
375 inline uintD inc_loop_up (uintD* ptr, uintC count)
379 return mpn_add_1(ptr,ptr,count,1);
382 inline uintD sub_loop_up (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count)
386 return mpn_sub_n(destptr,sourceptr1,sourceptr2,count);
389 inline uintD subx_loop_up (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count, uintD carry)
393 var uintD res_carry = mpn_sub_n(destptr,sourceptr1,sourceptr2,count);
395 res_carry |= mpn_sub_1(destptr,destptr,count,1);
399 inline uintD subfrom_loop_up (const uintD* sourceptr, uintD* destptr, uintC count)
403 return mpn_sub_n(destptr,destptr,sourceptr,count);
406 inline uintD dec_loop_up (uintD* ptr, uintC count)
410 return -mpn_sub_1(ptr,ptr,count,1);
413 #if !defined(ADDSUB_LOOPS)
414 // No equivalent for this in gmp. But we need this function, so write it in C.
415 inline uintD neg_loop_up (uintD* ptr, uintC count)
417 // erstes Digit /=0 suchen:
418 until (count==0) { if (!(*ptr == 0)) goto L1; ptr++; count--; }
420 L1: // erstes Digit /=0 gefunden, ab jetzt gibt's Carrys
421 *ptr = - *ptr; count--; // 1 Digit negieren
422 dotimesC(count,count, { ptr++; *ptr = ~ *ptr; } ); // alle anderen Digits invertieren
429 inline uintD shift1left_loop_up (uintD* ptr, uintC count)
433 return mpn_lshift(ptr,ptr,count,1);
436 inline uintD shiftleft_loop_up (uintD* ptr, uintC count, uintC i, uintD carry)
440 var uintD res_carry = mpn_lshift(ptr,ptr,count,i);
445 inline uintD shiftleftcopy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count, uintC i)
449 return mpn_lshift(destptr,sourceptr,count,i);
452 inline uintD shift1right_loop_down (uintD* ptr, uintC count, uintD carry)
456 var uintD res_carry = mpn_rshift(ptr-count,ptr-count,count,1);
458 ptr[-1] |= bit(intDsize-1);
462 inline uintD shiftright_loop_down (uintD* ptr, uintC count, uintC i)
466 return mpn_rshift(ptr-count,ptr-count,count,i);
469 inline uintD shiftrightsigned_loop_down (uintD* ptr, uintC count, uintC i)
471 var uintD carry = ((sintD)ptr[-1] >> (intDsize-1)) << (intDsize-i);
472 var uintD res_carry = mpn_rshift(ptr-count,ptr-count,count,i);
477 inline uintD shiftrightcopy_loop_down (const uintD* sourceptr, uintD* destptr, uintC count, uintC i, uintD carry)
479 carry = carry << (intDsize-i);
482 var uintD res_carry = mpn_rshift(destptr-count,sourceptr-count,count,i);
483 destptr[-1] |= carry;
489 inline uintD mulusmall_loop_up (uintD digit, uintD* ptr, uintC len, uintD newdigit)
493 var uintD res_carry = mpn_mul_1(ptr,ptr,len,digit);
494 res_carry += mpn_add_1(ptr,ptr,len,newdigit);
498 inline void mulu_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
500 destptr[len] = (len==0 ? 0 : mpn_mul_1(destptr,sourceptr,len,digit));
503 inline uintD muluadd_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
507 return mpn_addmul_1(destptr,sourceptr,len,digit);
510 inline uintD mulusub_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
514 return mpn_submul_1(destptr,sourceptr,len,digit);
519 inline uintD divu_loop_up (uintD digit, uintD* ptr, uintC len)
521 return mpn_divrem_1(ptr,0,ptr,len,digit);
524 inline uintD divu_loop_down (uintD digit, uintD* ptr, uintC len)
526 return mpn_divrem_1(ptr-len,0,ptr-len,len,digit);
529 inline uintD divucopy_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
531 return mpn_divrem_1(destptr,0,sourceptr,len,digit);
534 inline uintD divucopy_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
536 return mpn_divrem_1(destptr-len,0,sourceptr-len,len,digit);
541 #endif // defined(CL_USE_GMP)
544 // Define the missing functions as inline functions.
549 // destptr = copy_loop_up(sourceptr,destptr,count);
550 // kopiert count (uintC>=0) Digits aufwärts von sourceptr nach destptr
551 // und liefert das neue destptr.
552 inline uintD* copy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count)
553 { dotimesC(count,count, { *destptr++ = *sourceptr++; } );
558 // destptr = copy_loop_down(sourceptr,destptr,count);
559 // kopiert count (uintC>=0) Digits abwärts von sourceptr nach destptr
560 // und liefert das neue destptr.
561 inline uintD* copy_loop_down (const uintD* sourceptr, uintD* destptr, uintC count)
562 { dotimesC(count,count, { *--destptr = *--sourceptr; } );
571 // destptr = fill_loop_up(destptr,count,filler);
572 // kopiert count (uintC>=0) mal das Digit filler aufwärts nach destptr
573 // und liefert das neue destptr.
574 inline uintD* fill_loop_up (uintD* destptr, uintC count, uintD filler)
575 { dotimesC(count,count, { *destptr++ = filler; } );
580 // destptr = fill_loop_down(destptr,count,filler);
581 // kopiert count (uintC>=0) mal das Digit filler abwärts nach destptr
582 // und liefert das neue destptr.
583 inline uintD* fill_loop_down (uintD* destptr, uintC count, uintD filler)
584 { dotimesC(count,count, { *--destptr = filler; } );
593 // destptr = clear_loop_up(destptr,count);
594 // löscht count (uintC>=0) Digits aufwärts ab destptr
595 // und liefert das neue destptr.
596 inline uintD* clear_loop_up (uintD* destptr, uintC count)
597 { dotimesC(count,count, { *destptr++ = 0; } );
602 // destptr = clear_loop_down(destptr,count);
603 // löscht count (uintC>=0) Digits abwärts ab destptr
604 // und liefert das neue destptr.
605 inline uintD* clear_loop_down (uintD* destptr, uintC count)
606 { dotimesC(count,count, { *--destptr = 0; } );
615 // test_loop_up(ptr,count)
616 // testet count (uintC>=0) Digits aufwärts ab ptr, ob darunter eines /=0 ist.
617 // Ergebnis /=0, falls ja.
618 inline cl_boolean test_loop_up (const uintD* ptr, uintC count)
619 { dotimesC(count,count, { if (*ptr++) return cl_true; } );
624 // test_loop_down(ptr,count)
625 // testet count (uintC>=0) Digits abwärts ab ptr, ob darunter eines /=0 ist.
626 // Ergebnis /=0, falls ja.
627 inline cl_boolean test_loop_down (const uintD* ptr, uintC count)
628 { dotimesC(count,count, { if (*--ptr) return cl_true; } );
634 #if CL_DS_BIG_ENDIAN_P
639 // or_loop_up(xptr,yptr,count);
640 // verknüpft count (uintC>=0) Digits aufwärts ab xptr und ab yptr
641 // mit Ziel ab xptr durch OR.
642 inline void or_loop_up (uintD* xptr, const uintD* yptr, uintC count)
643 { dotimesC(count,count, { *xptr++ |= *yptr++; } ); }
646 // xor_loop_up(xptr,yptr,count);
647 // verknüpft count (uintC>=0) Digits aufwärts ab xptr und ab yptr
648 // mit Ziel ab xptr durch XOR.
649 inline void xor_loop_up (uintD* xptr, const uintD* yptr, uintC count)
650 { dotimesC(count,count, { *xptr++ ^= *yptr++; } ); }
653 // and_loop_up(xptr,yptr,count);
654 // verknüpft count (uintC>=0) Digits aufwärts ab xptr und ab yptr
655 // mit Ziel ab xptr durch AND.
656 inline void and_loop_up (uintD* xptr, const uintD* yptr, uintC count)
657 { dotimesC(count,count, { *xptr++ &= *yptr++; } ); }
660 // eqv_loop_up(xptr,yptr,count);
661 // verknüpft count (uintC>=0) Digits aufwärts ab xptr und ab yptr
662 // mit Ziel ab xptr durch EQV (NOT XOR).
663 inline void eqv_loop_up (uintD* xptr, const uintD* yptr, uintC count)
664 { dotimesC(count,count,
665 {var uintD temp = ~ (*xptr ^ *yptr++); *xptr++ = temp; }
670 // nand_loop_up(xptr,yptr,count);
671 // verknüpft count (uintC>=0) Digits aufwärts ab xptr und ab yptr
672 // mit Ziel ab xptr durch NAND (NOT AND).
673 inline void nand_loop_up (uintD* xptr, const uintD* yptr, uintC count)
674 { dotimesC(count,count,
675 {var uintD temp = ~ (*xptr & *yptr++); *xptr++ = temp; }
680 // nor_loop_up(xptr,yptr,count);
681 // verknüpft count (uintC>=0) Digits aufwärts ab xptr und ab yptr
682 // mit Ziel ab xptr durch NOR (NOT OR).
683 inline void nor_loop_up (uintD* xptr, const uintD* yptr, uintC count)
684 { dotimesC(count,count,
685 {var uintD temp = ~ (*xptr | *yptr++); *xptr++ = temp; }
690 // andc2_loop_up(xptr,yptr,count);
691 // verknüpft count (uintC>=0) Digits aufwärts ab xptr und ab yptr
692 // mit Ziel ab xptr durch ANDC2 (AND NOT).
693 inline void andc2_loop_up (uintD* xptr, const uintD* yptr, uintC count)
694 { dotimesC(count,count, { *xptr++ &= ~(*yptr++); } ); }
697 // orc2_loop_up(xptr,yptr,count);
698 // verknüpft count (uintC>=0) Digits aufwärts ab xptr und ab yptr
699 // mit Ziel ab xptr durch ORC2 (OR NOT).
700 inline void orc2_loop_up (uintD* xptr, const uintD* yptr, uintC count)
701 { dotimesC(count,count, { *xptr++ |= ~(*yptr++); } ); }
704 // not_loop_up(xptr,count);
705 // verknüpft count (uintC>0) Digits aufwärts ab xptr mit Ziel ab xptr
707 inline void not_loop_up (uintD* xptr, uintC count)
708 { dotimespC(count,count,
709 {var uintD temp = ~ (*xptr); *xptr++ = temp; }
717 // AND-Test-Schleife:
718 // and_test_loop_up(xptr,yptr,count);
719 // verknüpft count (uintC>=0) Digits aufwärts ab xptr und ab yptr durch AND
720 // und testet, ob sich dabei ein Digit /=0 ergibt. Ergebnis cl_true, falls ja.
721 inline cl_boolean and_test_loop_up (const uintD* xptr, const uintD* yptr, uintC count)
722 { dotimesC(count,count, { if (*xptr++ & *yptr++) return cl_true; } );
726 // Vergleichsschleife:
727 // result = compare_loop_up(xptr,yptr,count);
728 // vergleicht nacheinander xptr[0] mit yptr[0], xptr[1] mit yptr[1], usw.,
729 // insgesamt count Digits, und liefert 0 falls alle gleich sind,
730 // +1 falls zuerst ein xptr[i]>yptr[i] ist,
731 // -1 falls zuerst ein xptr[i]<yptr[i] ist.
732 inline cl_signean compare_loop_up (const uintD* xptr, const uintD* yptr, uintC count)
733 { dotimesC(count,count,
734 { if (!(*xptr++ == *yptr++))
735 // verschiedene Digits gefunden
736 return (*--xptr > *--yptr ? signean_plus : signean_minus);
738 return signean_null; // alle Digits gleich
745 // Additionsschleife:
746 // übertrag = add_loop_down(sourceptr1,sourceptr2,destptr,count);
747 // addiert count (uintC>=0) Digits abwärts von sourceptr1, von sourceptr2
748 // abwärts nach destptr und liefert den Übertrag (0 oder /=0, was 1 bedeutet).
749 inline uintD add_loop_down (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count)
753 do { source1 = *--sourceptr1;
754 source2 = *--sourceptr2;
755 *--destptr = source1 + source2;
756 if (source1 > (uintD)(~source2)) goto carry_1;
762 do { source1 = *--sourceptr1;
763 source2 = *--sourceptr2;
764 *--destptr = source1 + source2 + 1;
765 if (source1 < (uintD)(~source2)) goto carry_0;
773 // Additionsschleife:
774 // übertrag = addto_loop_down(sourceptr,destptr,count);
775 // addiert count (uintC>=0) Digits abwärts von sourceptr, von destptr
776 // abwärts nach destptr und liefert den Übertrag (0 oder /=0, was 1 bedeutet).
777 inline uintD addto_loop_down (const uintD* sourceptr, uintD* destptr, uintC count)
781 do { source1 = *--sourceptr;
782 source2 = *--destptr;
783 *destptr = source1 + source2;
784 if (source1 > (uintD)(~source2)) goto carry_1;
790 do { source1 = *--sourceptr;
791 source2 = *--destptr;
792 *destptr = source1 + source2 + 1;
793 if (source1 < (uintD)(~source2)) goto carry_0;
801 // Incrementierschleife:
802 // übertrag = inc_loop_down(ptr,count);
803 // incrementiert count (uintC>=0) Digits abwärts von ptr, so lange bis kein
804 // Übertrag mehr auftritt und liefert den Übertrag (0 oder /=0, was 1 bedeutet).
805 inline uintD inc_loop_down (uintD* ptr, uintC count)
806 { dotimesC(count,count,
807 { if (!( ++(*--ptr) == 0 )) return 0; } // kein weiterer Übertrag
809 return 1; // weiterer Übertrag
812 // Subtraktionsschleife:
813 // übertrag = sub_loop_down(sourceptr1,sourceptr2,destptr,count);
814 // subtrahiert count (uintC>=0) Digits abwärts von sourceptr1, von sourceptr2
815 // abwärts nach destptr und liefert den Übertrag (0 oder /=0, was -1 bedeutet).
816 inline uintD sub_loop_down (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count)
820 do { source1 = *--sourceptr1;
821 source2 = *--sourceptr2;
822 *--destptr = source1 - source2;
823 if (source1 < source2) goto carry_1;
829 do { source1 = *--sourceptr1;
830 source2 = *--sourceptr2;
831 *--destptr = source1 - source2 - 1;
832 if (source1 > source2) goto carry_0;
840 // Subtraktionsschleife:
841 // übertrag = subx_loop_down(sourceptr1,sourceptr2,destptr,count,carry);
842 // subtrahiert count (uintC>=0) Digits abwärts von sourceptr1 und addiert
843 // einen Carry (0 oder -1), von sourceptr2 abwärts nach destptr und
844 // liefert den Übertrag (0 oder /=0, was -1 bedeutet).
845 inline uintD subx_loop_down (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count, uintD carry)
850 do { source1 = *--sourceptr1;
851 source2 = *--sourceptr2;
852 *--destptr = source1 - source2;
853 if (source1 < source2) goto carry_1;
862 do { source1 = *--sourceptr1;
863 source2 = *--sourceptr2;
864 *--destptr = source1 - source2 - 1;
865 if (source1 > source2) goto carry_0;
873 // Subtraktionsschleife:
874 // übertrag = subfrom_loop_down(sourceptr,destptr,count);
875 // subtrahiert count (uintC>=0) Digits abwärts von sourceptr, von destptr
876 // abwärts nach destptr (dest := dest - source)
877 // und liefert den Übertrag (0 oder /=0, was -1 bedeutet).
878 inline uintD subfrom_loop_down (const uintD* sourceptr, uintD* destptr, uintC count)
882 do { source1 = *--destptr;
883 source2 = *--sourceptr;
884 *destptr = source1 - source2;
885 if (source1 < source2) goto carry_1;
891 do { source1 = *--destptr;
892 source2 = *--sourceptr;
893 *destptr = source1 - source2 - 1;
894 if (source1 > source2) goto carry_0;
902 // Decrementierschleife:
903 // übertrag = dec_loop_down(ptr,count);
904 // decrementiert count (uintC>=0) Digits abwärts von ptr, so lange bis kein
905 // Übertrag mehr auftritt und liefert den Übertrag (0 oder -1).
906 inline uintD dec_loop_down (uintD* ptr, uintC count)
907 { dotimesC(count,count,
908 { if (!( (*--ptr)-- == 0 )) return 0; } // kein weiterer Übertrag
910 return (uintD)(-1); // weiterer Übertrag
914 // übertrag = neg_loop_down(ptr,count);
915 // negiert count (uintC>=0) Digits abwärts von ptr,
916 // und liefert den Übertrag (0 oder -1).
917 inline uintD neg_loop_down (uintD* ptr, uintC count)
918 { // erstes Digit /=0 suchen:
919 until (count==0) { if (!(*--ptr == 0)) goto L1; count--; }
921 L1: // erstes Digit /=0 gefunden, ab jetzt gibt's Carrys
922 *ptr = - *ptr; count--; // 1 Digit negieren
923 dotimesC(count,count, { --ptr; *ptr = ~ *ptr; } ); // alle anderen Digits invertieren
931 // Schiebeschleife um 1 Bit nach links:
932 // übertrag = shift1left_loop_down(ptr,count);
933 // schiebt count (uintC>=0) Digits abwärts von ptr um 1 Bit nach links,
934 // und liefert den Übertrag (0 oder /=0, was 1 bedeutet).
936 inline uintD shift1left_loop_down (uintD* ptr, uintC count)
937 { var uintDD accu = 0;
938 dotimesC(count,count,
939 { accu = ((uintDD)(*--ptr)<<1)+accu; *ptr = lowD(accu);
940 accu = (uintDD)(highD(accu));
945 inline uintD shift1left_loop_down (uintD* ptr, uintC count)
946 { var uintD carry = 0;
947 dotimesC(count,count,
948 { var uintD accu = *--ptr;
949 *ptr = (accu<<1) | carry;
950 carry = accu>>(intDsize-1);
956 // Schiebeschleife um i Bits nach links:
957 // übertrag = shiftleft_loop_down(ptr,count,i,übertrag_init);
958 // schiebt count (uintC>=0) Digits abwärts von ptr um i Bits (0<i<intDsize)
959 // nach links, schiebt dabei die i Bits aus übertrag_init rechts rein,
960 // und liefert den Übertrag (was links rauskommt, >=0, <2^i).
962 inline uintD shiftleft_loop_down (uintD* ptr, uintC count, uintC i, uintD carry)
963 { var uintDD accu = (uintDD)carry;
964 dotimesC(count,count,
965 { accu = ((uintDD)(*--ptr)<<i)+accu; *ptr = lowD(accu);
966 accu = (uintDD)(highD(accu));
971 inline uintD shiftleft_loop_down (uintD* ptr, uintC count, uintC i, uintD carry)
972 { var uintC j = intDsize-i;
973 dotimesC(count,count,
974 { var uintD accu = *--ptr;
975 *ptr = (accu<<i) | carry;
982 // Schiebe- und Kopierschleife um i Bits nach links:
983 // übertrag = shiftleftcopy_loop_down(sourceptr,destptr,count,i);
984 // kopiert count (uintC>=0) Digits abwärts von sourceptr nach destptr
985 // und schiebt sie dabei um i Bits (0<i<intDsize) nach links,
986 // wobei ganz rechts mit i Nullbits aufgefüllt wird,
987 // und liefert den Übertrag (was links rauskommt, >=0, <2^i).
989 inline uintD shiftleftcopy_loop_down (const uintD* sourceptr, uintD* destptr, uintC count, uintC i)
990 { var uintDD accu = 0;
991 dotimesC(count,count,
992 { accu = ((uintDD)(*--sourceptr)<<i)+accu; *--destptr = lowD(accu);
993 accu = (uintDD)(highD(accu));
998 inline uintD shiftleftcopy_loop_down (const uintD* sourceptr, uintD* destptr, uintC count, uintC i)
999 { var uintC j = intDsize-i;
1000 var uintD carry = 0;
1001 dotimesC(count,count,
1002 { var uintD accu = *--sourceptr;
1003 *--destptr = (accu<<i) | carry;
1010 // Schiebeschleife um 1 Bit nach rechts:
1011 // übertrag = shift1right_loop_up(ptr,count,übertrag_init);
1012 // schiebt count (uintC>=0) Digits aufwärts von ptr um 1 Bit nach rechts,
1013 // wobei links das Bit übertrag_init (sollte =0 oder =-1 sein) hineingeschoben
1014 // wird, und liefert den Übertrag (0 oder /=0, was 1 bedeutet).
1016 inline uintD shift1right_loop_up (uintD* ptr, uintC count, uintD carry)
1017 { var uintDD accu = (sintDD)(sintD)carry & ((uintDD)1 << (2*intDsize-1)); // 0 oder bit(2*intDsize-1)
1018 dotimesC(count,count,
1019 { accu = (highlowDD_0(*ptr)>>1)+accu; *ptr++ = highD(accu);
1020 accu = highlowDD_0(lowD(accu));
1025 inline uintD shift1right_loop_up (uintD* ptr, uintC count, uintD carry)
1026 { carry = carry << (intDsize-1); // carry zu einem einzigen Bit machen
1027 dotimesC(count,count,
1028 { var uintD accu = *ptr;
1029 *ptr++ = (accu >> 1) | carry;
1030 carry = accu << (intDsize-1);
1036 // Schiebeschleife um i Bits nach rechts:
1037 // übertrag = shiftright_loop_up(ptr,count,i);
1038 // schiebt count (uintC>=0) Digits aufwärts von ptr um i Bits (0<i<intDsize)
1039 // nach rechts, wobei links Nullen eingeschoben werden,
1040 // und liefert den Übertrag (was rechts rauskommt, als Bits intDsize-1..intDsize-i).
1042 inline uintD shiftright_loop_up (uintD* ptr, uintC count, uintC i)
1043 { var uintDD accu = 0;
1044 dotimesC(count,count,
1045 { // Die oberen i Bits von (uintD)accu bilden hier den Übertrag.
1046 accu = highlowDD_0(lowD(accu));
1047 // Die oberen i Bits von (uintDD)accu bilden hier den Übertrag.
1048 accu = (highlowDD_0(*ptr)>>i)+accu; *ptr++ = highD(accu);
1053 inline uintD shiftright_loop_up (uintD* ptr, uintC count, uintC i)
1054 { var uintC j = intDsize-i;
1055 var uintD carry = 0;
1056 dotimesC(count,count,
1057 { var uintD accu = *ptr;
1058 *ptr++ = (accu >> i) | carry;
1065 // Schiebeschleife um i Bits nach rechts:
1066 // übertrag = shiftrightsigned_loop_up(ptr,count,i);
1067 // schiebt count (uintC>0) Digits aufwärts von ptr um i Bits (0<i<intDsize)
1068 // nach rechts, wobei links das MSBit ver-i-facht wird,
1069 // und liefert den Übertrag (was rechts rauskommt, als Bits intDsize-1..intDsize-i).
1071 inline uintD shiftrightsigned_loop_up (uintD* ptr, uintC count, uintC i)
1072 { var uintDD accu = // Übertrag mit i Vorzeichenbits initialisieren
1073 highlowDD_0(sign_of_sintD((sintD)(*ptr)))>>i;
1074 dotimespC(count,count,
1075 { // Die oberen i Bits von (uintD)accu bilden hier den Übertrag.
1076 accu = highlowDD_0(lowD(accu));
1077 // Die oberen i Bits von (uintDD)accu bilden hier den Übertrag.
1078 accu = (highlowDD_0(*ptr)>>i)+accu; *ptr++ = highD(accu);
1083 inline uintD shiftrightsigned_loop_up (uintD* ptr, uintC count, uintC i)
1084 { var uintC j = intDsize-i;
1086 { var uintD accu = *ptr;
1087 *ptr++ = (sintD)accu >> i;
1091 dotimesC(count,count,
1092 { var uintD accu = *ptr;
1093 *ptr++ = (accu >> i) | carry;
1100 // Schiebe- und Kopier-Schleife um i Bits nach rechts:
1101 // übertrag = shiftrightcopy_loop_up(sourceptr,destptr,count,i,carry);
1102 // kopiert count (uintC>=0) Digits aufwärts von sourceptr nach destptr
1103 // und schiebt sie dabei um i Bits (0<i<intDsize) nach rechts, wobei carry
1104 // (sozusagen als sourceptr[-1]) die i Bits ganz links bestimmt,
1105 // und liefert den Übertrag (was rechts rauskommt, als Bits intDsize-1..intDsize-i).
1107 inline uintD shiftrightcopy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count, uintC i, uintD carry)
1108 { var uintDD accu = // Übertrag mit carry initialisieren
1109 highlowDD_0(carry)>>i;
1110 dotimesC(count,count,
1111 { // Die oberen i Bits von (uintD)accu bilden hier den Übertrag.
1112 accu = highlowDD_0(lowD(accu));
1113 // Die oberen i Bits von (uintDD)accu bilden hier den Übertrag.
1114 accu = (highlowDD_0(*sourceptr++)>>i)+accu; *destptr++ = highD(accu);
1119 inline uintD shiftrightcopy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count, uintC i, uintD carry)
1120 { var uintC j = intDsize-i;
1122 dotimesC(count,count,
1123 { var uintD accu = *sourceptr++;
1124 *destptr++ = (accu >> i) | carry;
1135 // Multiplikations-Einfachschleife:
1136 // Multipliziert eine UDS mit einem kleinen Digit und addiert ein kleines Digit.
1137 // mulusmall_loop_down(digit,ptr,len,newdigit)
1138 // multipliziert die UDS ptr[-len..-1] mit digit (>=2, <=36),
1139 // addiert dabei newdigit (>=0, <digit) zur letzten Ziffer,
1140 // und liefert den Carry (>=0, <digit).
1142 inline uintD mulusmall_loop_down (uintD digit, uintD* ptr, uintC len, uintD newdigit)
1143 { var uintDD carry = newdigit;
1145 { // Hier ist 0 <= carry < digit.
1146 carry = carry + muluD(digit,*--ptr);
1147 // Hier ist 0 <= carry < 2^intDsize*digit.
1149 carry = (uintDD)highD(carry); // carry := floor(carry/2^intDsize) < digit
1154 inline uintD mulusmall_loop_down (uintD digit, uintD* ptr, uintC len, uintD newdigit)
1155 { var uintD carry = newdigit;
1157 { // Hier ist 0 <= carry < digit.
1160 muluD(digit,*--ptr,hi=,lo=);
1161 // Hier ist 0 <= 2^intDsize*hi + lo + carry < 2^intDsize*digit.
1162 lo += carry; if (lo < carry) { hi += 1; }
1170 // Multiplikations-Einfachschleife:
1171 // Multipliziert eine UDS mit einem Digit und legt das Ergebnis in einer
1173 // mulu_loop_down(digit,sourceptr,destptr,len);
1174 // multipliziert die UDS sourceptr[-len..-1] (len>0)
1175 // mit dem einzelnen digit
1176 // und legt das Ergebnis in der UDS destptr[-len-1..-1] ab.
1178 inline void mulu_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1179 { var uintDD carry = 0;
1181 { // Hier ist carry=digit=0 oder 0 <= carry < digit.
1182 carry = carry + muluD(digit,*--sourceptr);
1183 // Hier ist carry=digit=0 oder 0 <= carry < 2^intDsize*digit.
1184 *--destptr = lowD(carry);
1185 carry = (uintDD)highD(carry); // carry := floor(carry/2^intDsize) < digit
1187 *--destptr = lowD(carry);
1190 inline void mulu_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1191 { var uintD carry = 0;
1193 { // Hier ist carry=digit=0 oder 0 <= carry < digit.
1196 muluD(digit,*--sourceptr,hi=,lo=);
1197 // Hier ist 0 <= 2^intDsize*hi + lo + carry < 2^intDsize*digit oder hi=lo=carry=digit=0.
1198 lo += carry; if (lo < carry) { hi += 1; }
1206 // Multiplikations-Einfachschleife mit Akkumulation:
1207 // Multipliziert eine UDS mit einem Digit und addiert das Ergebnis zu einer
1209 // muluadd_loop_down(digit,sourceptr,destptr,len);
1210 // multipliziert die UDS sourceptr[-len..-1] (len>0)
1211 // mit dem einzelnen digit, legt das Ergebnis in der UDS destptr[-len..-1]
1212 // ab und liefert den weiteren Übertrag.
1214 inline uintD muluadd_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1215 { var uintDD carry = 0;
1217 { dotimespC(len,len,
1218 { // Hier ist 0 <= carry <= digit.
1219 carry = carry + muluD(digit,*--sourceptr) + (uintDD)*--destptr;
1220 // Hier ist 0 <= carry <= 2^intDsize*digit + 2^intDsize-1.
1221 *destptr = lowD(carry);
1222 carry = (uintDD)highD(carry); // carry := floor(carry/2^intDsize) <= digit
1228 inline uintD muluadd_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1229 { var uintD carry = 0;
1231 { dotimespC(len,len,
1232 { // Hier ist 0 <= carry <= digit.
1235 muluD(digit,*--sourceptr,hi=,lo=);
1236 // Hier ist 0 <= 2^intDsize*hi + lo + carry + *--destptr <= 2^intDsize*digit+2^intDsize-1.
1237 lo += carry; if (lo < carry) { hi += 1; }
1239 lo += carry; if (lo < carry) { hi += 1; }
1248 // Multiplikations-Einfachschleife mit Diminution:
1249 // Multipliziert eine UDS mit einem Digit und subtrahiert das Ergebnis von
1250 // einer zweiten UDS.
1251 // mulusub_loop_down(digit,sourceptr,destptr,len);
1252 // multipliziert die UDS sourceptr[-len..-1] (len>0) mit dem einzelnen
1253 // digit, subtrahiert das Ergebnis von der UDS destptr[-len..-1] und liefert
1254 // den weiteren Übertrag (>=0, evtl. von destptr[-len-1] zu subtrahieren).
1256 inline uintD mulusub_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1257 { var uintDD carry = 0;
1259 { dotimespC(len,len,
1260 { // Hier ist 0 <= carry <= digit.
1261 carry = carry + muluD(digit,*--sourceptr) + (uintD)(~(*--destptr));
1262 // Hier ist 0 <= carry <= 2^intDsize*digit + 2^intDsize-1.
1263 *destptr = ~lowD(carry);
1264 carry = (uintDD)highD(carry); // carry := floor(carry/2^intDsize) <= digit
1265 // Hier ist 0 <= carry <= digit.
1270 return 0; // nichts zu subtrahieren -> kein Übertrag
1273 inline uintD mulusub_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1274 { var uintD carry = 0;
1276 { dotimespC(len,len,
1277 { // Hier ist 0 <= carry <= digit.
1280 muluD(digit,*--sourceptr,hi=,lo=);
1281 // Hier ist 0 <= 2^intDsize*hi + lo + carry + ~(*--destptr) <= 2^intDsize*digit+2^intDsize-1.
1282 lo += carry; if (lo < carry) { hi += 1; }
1284 *destptr = carry - lo; if (carry < lo) { hi += 1; }
1290 return 0; // nichts zu subtrahieren -> kein Übertrag
1298 // Divisions-Einfachschleife:
1299 // Dividiert eine UDS durch ein Digit.
1300 // divu_loop_up(digit,ptr,len)
1301 // dividiert die UDS ptr[0..len-1] durch digit,
1302 // legt das Ergebnis in derselben UDS ab, und liefert den Rest (>=0, <digit).
1304 inline uintD divu_loop_up (uintD digit, uintD* ptr, uintC len)
1305 { var uintD rest = 0;
1307 { divuD(highlowDD(rest,*ptr),digit,*ptr =, rest =); ptr++; }
1312 inline uintD divu_loop_up (uintD digit, uintD* ptr, uintC len)
1313 { var uintD rest = 0;
1315 { divuD(rest,*ptr,digit,*ptr =, rest =); ptr++; }
1321 // Divisions-Einfachschleife:
1322 // Dividiert eine UDS durch ein Digit und legt das Ergebnis in einer
1324 // divucopy_loop_up(digit,sourceptr,destptr,len)
1325 // dividiert die UDS sourceptr[0..len-1] durch digit,
1326 // legt das Ergebnis in der UDS destptr[0..len-1] ab,
1327 // und liefert den Rest (>=0, <digit).
1329 inline uintD divucopy_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1330 { var uintD rest = 0;
1332 { divuD(highlowDD(rest,*sourceptr++),digit,*destptr++ =, rest =); }
1337 inline uintD divucopy_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1338 { var uintD rest = 0;
1340 { divuD(rest,*sourceptr++,digit,*destptr++ =, rest =); }
1348 #else // !CL_DS_BIG_ENDIAN_P
1353 // or_loop_down(xptr,yptr,count);
1354 // verknüpft count (uintC>=0) Digits abwärts ab xptr und ab yptr
1355 // mit Ziel ab xptr durch OR.
1356 inline void or_loop_down (uintD* xptr, const uintD* yptr, uintC count)
1357 { dotimesC(count,count, { *--xptr |= *--yptr; } ); }
1360 // xor_loop_down(xptr,yptr,count);
1361 // verknüpft count (uintC>=0) Digits abwärts ab xptr und ab yptr
1362 // mit Ziel ab xptr durch XOR.
1363 inline void xor_loop_down (uintD* xptr, const uintD* yptr, uintC count)
1364 { dotimesC(count,count, { *--xptr ^= *--yptr; } ); }
1367 // and_loop_down(xptr,yptr,count);
1368 // verknüpft count (uintC>=0) Digits abwärts ab xptr und ab yptr
1369 // mit Ziel ab xptr durch AND.
1370 inline void and_loop_down (uintD* xptr, const uintD* yptr, uintC count)
1371 { dotimesC(count,count, { *--xptr &= *--yptr; } ); }
1374 // eqv_loop_down(xptr,yptr,count);
1375 // verknüpft count (uintC>=0) Digits abwärts ab xptr und ab yptr
1376 // mit Ziel ab xptr durch EQV (NOT XOR).
1377 inline void eqv_loop_down (uintD* xptr, const uintD* yptr, uintC count)
1378 { dotimesC(count,count,
1379 {var uintD temp = ~ (*--xptr ^ *--yptr); *xptr = temp; }
1384 // nand_loop_down(xptr,yptr,count);
1385 // verknüpft count (uintC>=0) Digits abwärts ab xptr und ab yptr
1386 // mit Ziel ab xptr durch NAND (NOT AND).
1387 inline void nand_loop_down (uintD* xptr, const uintD* yptr, uintC count)
1388 { dotimesC(count,count,
1389 {var uintD temp = ~ (*--xptr & *--yptr); *xptr = temp; }
1394 // nor_loop_down(xptr,yptr,count);
1395 // verknüpft count (uintC>=0) Digits abwärts ab xptr und ab yptr
1396 // mit Ziel ab xptr durch NOR (NOT OR).
1397 inline void nor_loop_down (uintD* xptr, const uintD* yptr, uintC count)
1398 { dotimesC(count,count,
1399 {var uintD temp = ~ (*--xptr | *--yptr); *xptr = temp; }
1404 // andc2_loop_down(xptr,yptr,count);
1405 // verknüpft count (uintC>=0) Digits abwärts ab xptr und ab yptr
1406 // mit Ziel ab xptr durch ANDC2 (AND NOT).
1407 inline void andc2_loop_down (uintD* xptr, const uintD* yptr, uintC count)
1408 { dotimesC(count,count, { *--xptr &= ~(*--yptr); } ); }
1411 // orc2_loop_down(xptr,yptr,count);
1412 // verknüpft count (uintC>=0) Digits abwärts ab xptr und ab yptr
1413 // mit Ziel ab xptr durch ORC2 (OR NOT).
1414 inline void orc2_loop_down (uintD* xptr, const uintD* yptr, uintC count)
1415 { dotimesC(count,count, { *--xptr |= ~(*--yptr); } ); }
1418 // not_loop_down(xptr,count);
1419 // verknüpft count (uintC>0) Digits abwärts ab xptr mit Ziel ab xptr
1421 inline void not_loop_down (uintD* xptr, uintC count)
1422 { dotimespC(count,count,
1423 {var uintD temp = ~ (*--xptr); *xptr = temp; }
1431 // AND-Test-Schleife:
1432 // and_test_loop_down(xptr,yptr,count);
1433 // verknüpft count (uintC>=0) Digits abwärts ab xptr und ab yptr durch AND
1434 // und testet, ob sich dabei ein Digit /=0 ergibt. Ergebnis cl_true, falls ja.
1435 inline cl_boolean and_test_loop_down (const uintD* xptr, const uintD* yptr, uintC count)
1436 { dotimesC(count,count, { if (*--xptr & *--yptr) return cl_true; } );
1440 // Vergleichsschleife:
1441 // result = compare_loop_down(xptr,yptr,count);
1442 // vergleicht nacheinander xptr[-1] mit yptr[-1], xptr[-2] mit yptr[-2], usw.,
1443 // insgesamt count Digits, und liefert 0 falls alle gleich sind,
1444 // +1 falls zuerst ein xptr[i]>yptr[i] ist,
1445 // -1 falls zuerst ein xptr[i]<yptr[i] ist.
1446 inline cl_signean compare_loop_down (const uintD* xptr, const uintD* yptr, uintC count)
1447 { dotimesC(count,count,
1448 { if (!(*--xptr == *--yptr))
1449 // verschiedene Digits gefunden
1450 return (*xptr > *yptr ? signean_plus : signean_minus);
1452 return signean_null; // alle Digits gleich
1457 #ifndef ADDSUB_LOOPS
1459 // Additionsschleife:
1460 // übertrag = add_loop_up(sourceptr1,sourceptr2,destptr,count);
1461 // addiert count (uintC>=0) Digits aufwärts von sourceptr1, von sourceptr2
1462 // aufwärts nach destptr und liefert den Übertrag (0 oder /=0, was 1 bedeutet).
1463 inline uintD add_loop_up (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count)
1464 { var uintD source1;
1467 do { source1 = *sourceptr1++;
1468 source2 = *sourceptr2++;
1469 *destptr++ = source1 + source2;
1470 if (source1 > (uintD)(~source2)) goto carry_1;
1476 do { source1 = *sourceptr1++;
1477 source2 = *sourceptr2++;
1478 *destptr++ = source1 + source2 + 1;
1479 if (source1 < (uintD)(~source2)) goto carry_0;
1487 // Additionsschleife:
1488 // übertrag = addto_loop_up(sourceptr,destptr,count);
1489 // addiert count (uintC>=0) Digits aufwärts von sourceptr, von destptr
1490 // aufwärts nach destptr und liefert den Übertrag (0 oder /=0, was 1 bedeutet).
1491 inline uintD addto_loop_up (const uintD* sourceptr, uintD* destptr, uintC count)
1492 { var uintD source1;
1495 do { source1 = *sourceptr++;
1497 *destptr++ = source1 + source2;
1498 if (source1 > (uintD)(~source2)) goto carry_1;
1504 do { source1 = *sourceptr++;
1506 *destptr++ = source1 + source2 + 1;
1507 if (source1 < (uintD)(~source2)) goto carry_0;
1515 // Incrementierschleife:
1516 // übertrag = inc_loop_up(ptr,count);
1517 // incrementiert count (uintC>=0) Digits aufwärts von ptr, so lange bis kein
1518 // Übertrag mehr auftritt und liefert den Übertrag (0 oder /=0, was 1 bedeutet).
1519 inline uintD inc_loop_up (uintD* ptr, uintC count)
1520 { dotimesC(count,count,
1521 { if (!( ++(*ptr++) == 0 )) return 0; } // kein weiterer Übertrag
1523 return 1; // weiterer Übertrag
1526 // Subtraktionsschleife:
1527 // übertrag = sub_loop_up(sourceptr1,sourceptr2,destptr,count);
1528 // subtrahiert count (uintC>=0) Digits aufwärts von sourceptr1, von sourceptr2
1529 // aufwärts nach destptr und liefert den Übertrag (0 oder /=0, was -1 bedeutet).
1530 inline uintD sub_loop_up (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count)
1531 { var uintD source1;
1534 do { source1 = *sourceptr1++;
1535 source2 = *sourceptr2++;
1536 *destptr++ = source1 - source2;
1537 if (source1 < source2) goto carry_1;
1543 do { source1 = *sourceptr1++;
1544 source2 = *sourceptr2++;
1545 *destptr++ = source1 - source2 - 1;
1546 if (source1 > source2) goto carry_0;
1554 // Subtraktionsschleife:
1555 // übertrag = subx_loop_up(sourceptr1,sourceptr2,destptr,count,carry);
1556 // subtrahiert count (uintC>=0) Digits aufwärts von sourceptr1 und addiert
1557 // einen Carry (0 oder -1), von sourceptr2 aufwärts nach destptr und
1558 // liefert den Übertrag (0 oder /=0, was -1 bedeutet).
1559 inline uintD subx_loop_up (const uintD* sourceptr1, const uintD* sourceptr2, uintD* destptr, uintC count, uintD carry)
1560 { var uintD source1;
1564 do { source1 = *sourceptr1++;
1565 source2 = *sourceptr2++;
1566 *destptr++ = source1 - source2;
1567 if (source1 < source2) goto carry_1;
1576 do { source1 = *sourceptr1++;
1577 source2 = *sourceptr2++;
1578 *destptr++ = source1 - source2 - 1;
1579 if (source1 > source2) goto carry_0;
1587 // Subtraktionsschleife:
1588 // übertrag = subfrom_loop_up(sourceptr,destptr,count);
1589 // subtrahiert count (uintC>=0) Digits aufwärts von sourceptr, von destptr
1590 // aufwärts nach destptr (dest := dest - source)
1591 // und liefert den Übertrag (0 oder /=0, was -1 bedeutet).
1592 inline uintD subfrom_loop_up (const uintD* sourceptr, uintD* destptr, uintC count)
1593 { var uintD source1;
1596 do { source1 = *destptr;
1597 source2 = *sourceptr++;
1598 *destptr++ = source1 - source2;
1599 if (source1 < source2) goto carry_1;
1605 do { source1 = *destptr;
1606 source2 = *sourceptr++;
1607 *destptr++ = source1 - source2 - 1;
1608 if (source1 > source2) goto carry_0;
1616 // Decrementierschleife:
1617 // übertrag = dec_loop_up(ptr,count);
1618 // decrementiert count (uintC>=0) Digits aufwärts von ptr, so lange bis kein
1619 // Übertrag mehr auftritt und liefert den Übertrag (0 oder -1).
1620 inline uintD dec_loop_up (uintD* ptr, uintC count)
1621 { dotimesC(count,count,
1622 { if (!( (*ptr++)-- == 0 )) return 0; } // kein weiterer Übertrag
1624 return (uintD)(-1); // weiterer Übertrag
1628 // übertrag = neg_loop_up(ptr,count);
1629 // negiert count (uintC>=0) Digits aufwärts von ptr,
1630 // und liefert den Übertrag (0 oder -1).
1631 inline uintD neg_loop_up (uintD* ptr, uintC count)
1632 { // erstes Digit /=0 suchen:
1633 until (count==0) { if (!(*ptr == 0)) goto L1; ptr++; count--; }
1635 L1: // erstes Digit /=0 gefunden, ab jetzt gibt's Carrys
1636 *ptr = - *ptr; count--; // 1 Digit negieren
1637 dotimesC(count,count, { ptr++; *ptr = ~ *ptr; } ); // alle anderen Digits invertieren
1645 // Schiebeschleife um 1 Bit nach links:
1646 // übertrag = shift1left_loop_up(ptr,count);
1647 // schiebt count (uintC>=0) Digits aufwärts von ptr um 1 Bit nach links,
1648 // und liefert den Übertrag (0 oder /=0, was 1 bedeutet).
1650 inline uintD shift1left_loop_up (uintD* ptr, uintC count)
1651 { var uintDD accu = 0;
1652 dotimesC(count,count,
1653 { accu = ((uintDD)(*ptr)<<1)+accu; *ptr++ = lowD(accu);
1654 accu = (uintDD)(highD(accu));
1659 inline uintD shift1left_loop_up (uintD* ptr, uintC count)
1660 { var uintD carry = 0;
1661 dotimesC(count,count,
1662 { var uintD accu = *ptr;
1663 *ptr++ = (accu<<1) | carry;
1664 carry = accu>>(intDsize-1);
1670 // Schiebeschleife um i Bits nach links:
1671 // übertrag = shiftleft_loop_up(ptr,count,i,übertrag_init);
1672 // schiebt count (uintC>=0) Digits aufwärts von ptr um i Bits (0<i<intDsize)
1673 // nach links, schiebt dabei die i Bits aus übertrag_init rechts rein,
1674 // und liefert den Übertrag (was links rauskommt, >=0, <2^i).
1676 inline uintD shiftleft_loop_up (uintD* ptr, uintC count, uintC i, uintD carry)
1677 { var uintDD accu = (uintDD)carry;
1678 dotimesC(count,count,
1679 { accu = ((uintDD)(*ptr)<<i)+accu; *ptr++ = lowD(accu);
1680 accu = (uintDD)(highD(accu));
1685 inline uintD shiftleft_loop_up (uintD* ptr, uintC count, uintC i, uintD carry)
1686 { var uintC j = intDsize-i;
1687 dotimesC(count,count,
1688 { var uintD accu = *ptr;
1689 *ptr++ = (accu<<i) | carry;
1696 // Schiebe- und Kopierschleife um i Bits nach links:
1697 // übertrag = shiftleftcopy_loop_up(sourceptr,destptr,count,i);
1698 // kopiert count (uintC>=0) Digits aufwärts von sourceptr nach destptr
1699 // und schiebt sie dabei um i Bits (0<i<intDsize) nach links,
1700 // wobei ganz rechts mit i Nullbits aufgefüllt wird,
1701 // und liefert den Übertrag (was links rauskommt, >=0, <2^i).
1703 inline uintD shiftleftcopy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count, uintC i)
1704 { var uintDD accu = 0;
1705 dotimesC(count,count,
1706 { accu = ((uintDD)(*sourceptr++)<<i)+accu; *destptr++ = lowD(accu);
1707 accu = (uintDD)(highD(accu));
1712 inline uintD shiftleftcopy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count, uintC i)
1713 { var uintC j = intDsize-i;
1714 var uintD carry = 0;
1715 dotimesC(count,count,
1716 { var uintD accu = *sourceptr++;
1717 *destptr++ = (accu<<i) | carry;
1724 // Schiebeschleife um 1 Bit nach rechts:
1725 // übertrag = shift1right_loop_down(ptr,count,übertrag_init);
1726 // schiebt count (uintC>=0) Digits abwärts von ptr um 1 Bit nach rechts,
1727 // wobei links das Bit übertrag_init (sollte =0 oder =-1 sein) hineingeschoben
1728 // wird, und liefert den Übertrag (0 oder /=0, was 1 bedeutet).
1730 inline uintD shift1right_loop_down (uintD* ptr, uintC count, uintD carry)
1731 { var uintDD accu = (sintDD)(sintD)carry & ((uintDD)1 << (2*intDsize-1)); // 0 oder bit(2*intDsize-1)
1732 dotimesC(count,count,
1733 { accu = (highlowDD_0(*--ptr)>>1)+accu; *ptr = highD(accu);
1734 accu = highlowDD_0(lowD(accu));
1739 inline uintD shift1right_loop_down (uintD* ptr, uintC count, uintD carry)
1740 { carry = carry << (intDsize-1); // carry zu einem einzigen Bit machen
1741 dotimesC(count,count,
1742 { var uintD accu = *--ptr;
1743 *ptr = (accu >> 1) | carry;
1744 carry = accu << (intDsize-1);
1750 // Schiebeschleife um i Bits nach rechts:
1751 // übertrag = shiftright_loop_down(ptr,count,i);
1752 // schiebt count (uintC>=0) Digits abwärts von ptr um i Bits (0<i<intDsize)
1753 // nach rechts, wobei links Nullen eingeschoben werden,
1754 // und liefert den Übertrag (was rechts rauskommt, als Bits intDsize-1..intDsize-i).
1756 inline uintD shiftright_loop_down (uintD* ptr, uintC count, uintC i)
1757 { var uintDD accu = 0;
1758 dotimesC(count,count,
1759 { // Die oberen i Bits von (uintD)accu bilden hier den Übertrag.
1760 accu = highlowDD_0(lowD(accu));
1761 // Die oberen i Bits von (uintDD)accu bilden hier den Übertrag.
1762 accu = (highlowDD_0(*--ptr)>>i)+accu; *ptr = highD(accu);
1767 inline uintD shiftright_loop_down (uintD* ptr, uintC count, uintC i)
1768 { var uintC j = intDsize-i;
1769 var uintD carry = 0;
1770 dotimesC(count,count,
1771 { var uintD accu = *--ptr;
1772 *ptr = (accu >> i) | carry;
1779 // Schiebeschleife um i Bits nach rechts:
1780 // übertrag = shiftrightsigned_loop_down(ptr,count,i);
1781 // schiebt count (uintC>0) Digits abwärts von ptr um i Bits (0<i<intDsize)
1782 // nach rechts, wobei links das MSBit ver-i-facht wird,
1783 // und liefert den Übertrag (was rechts rauskommt, als Bits intDsize-1..intDsize-i).
1785 inline uintD shiftrightsigned_loop_down (uintD* ptr, uintC count, uintC i)
1786 { var uintDD accu = // Übertrag mit i Vorzeichenbits initialisieren
1787 highlowDD_0(sign_of_sintD((sintD)(ptr[-1])))>>i;
1788 dotimespC(count,count,
1789 { // Die oberen i Bits von (uintD)accu bilden hier den Übertrag.
1790 accu = highlowDD_0(lowD(accu));
1791 // Die oberen i Bits von (uintDD)accu bilden hier den Übertrag.
1792 accu = (highlowDD_0(*--ptr)>>i)+accu; *ptr = highD(accu);
1797 inline uintD shiftrightsigned_loop_down (uintD* ptr, uintC count, uintC i)
1798 { var uintC j = intDsize-i;
1800 { var uintD accu = *--ptr;
1801 *ptr = (sintD)accu >> i;
1805 dotimesC(count,count,
1806 { var uintD accu = *--ptr;
1807 *ptr = (accu >> i) | carry;
1814 // Schiebe- und Kopier-Schleife um i Bits nach rechts:
1815 // übertrag = shiftrightcopy_loop_down(sourceptr,destptr,count,i,carry);
1816 // kopiert count (uintC>=0) Digits abwärts von sourceptr nach destptr
1817 // und schiebt sie dabei um i Bits (0<i<intDsize) nach rechts, wobei carry
1818 // (sozusagen als sourceptr[0]) die i Bits ganz links bestimmt,
1819 // und liefert den Übertrag (was rechts rauskommt, als Bits intDsize-1..intDsize-i).
1821 inline uintD shiftrightcopy_loop_down (const uintD* sourceptr, uintD* destptr, uintC count, uintC i, uintD carry)
1822 { var uintDD accu = // Übertrag mit carry initialisieren
1823 highlowDD_0(carry)>>i;
1824 dotimesC(count,count,
1825 { // Die oberen i Bits von (uintD)accu bilden hier den Übertrag.
1826 accu = highlowDD_0(lowD(accu));
1827 // Die oberen i Bits von (uintDD)accu bilden hier den Übertrag.
1828 accu = (highlowDD_0(*--sourceptr)>>i)+accu; *--destptr = highD(accu);
1833 inline uintD shiftrightcopy_loop_down (const uintD* sourceptr, uintD* destptr, uintC count, uintC i, uintD carry)
1834 { var uintC j = intDsize-i;
1836 dotimesC(count,count,
1837 { var uintD accu = *--sourceptr;
1838 *--destptr = (accu >> i) | carry;
1849 // Multiplikations-Einfachschleife:
1850 // Multipliziert eine UDS mit einem kleinen Digit und addiert ein kleines Digit.
1851 // mulusmall_loop_up(digit,ptr,len,newdigit)
1852 // multipliziert die UDS ptr[0..len-1] mit digit (>=2, <=36),
1853 // addiert dabei newdigit (>=0, <digit) zur letzten Ziffer,
1854 // und liefert den Carry (>=0, <digit).
1856 inline uintD mulusmall_loop_up (uintD digit, uintD* ptr, uintC len, uintD newdigit)
1857 { var uintDD carry = newdigit;
1859 { // Hier ist 0 <= carry < digit.
1860 carry = carry + muluD(digit,*ptr);
1861 // Hier ist 0 <= carry < 2^intDsize*digit.
1862 *ptr++ = lowD(carry);
1863 carry = (uintDD)highD(carry); // carry := floor(carry/2^intDsize) < digit
1868 inline uintD mulusmall_loop_up (uintD digit, uintD* ptr, uintC len, uintD newdigit)
1869 { var uintD carry = newdigit;
1871 { // Hier ist 0 <= carry < digit.
1874 muluD(digit,*ptr,hi=,lo=);
1875 // Hier ist 0 <= 2^intDsize*hi + lo + carry < 2^intDsize*digit.
1876 lo += carry; if (lo < carry) { hi += 1; }
1884 // Multiplikations-Einfachschleife:
1885 // Multipliziert eine UDS mit einem Digit und legt das Ergebnis in einer
1887 // mulu_loop_up(digit,sourceptr,destptr,len);
1888 // multipliziert die UDS sourceptr[0..len-1] (len>0)
1889 // mit dem einzelnen digit
1890 // und legt das Ergebnis in der UDS destptr[0..len] ab.
1892 inline void mulu_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1893 { var uintDD carry = 0;
1895 { // Hier ist carry=digit=0 oder 0 <= carry < digit.
1896 carry = carry + muluD(digit,*sourceptr++);
1897 // Hier ist carry=digit=0 oder 0 <= carry < 2^intDsize*digit.
1898 *destptr++ = lowD(carry);
1899 carry = (uintDD)highD(carry); // carry := floor(carry/2^intDsize) < digit
1901 *destptr++ = lowD(carry);
1904 inline void mulu_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1905 { var uintD carry = 0;
1907 { // Hier ist carry=digit=0 oder 0 <= carry < digit.
1910 muluD(digit,*sourceptr++,hi=,lo=);
1911 // Hier ist 0 <= 2^intDsize*hi + lo + carry < 2^intDsize*digit oder hi=lo=carry=digit=0.
1912 lo += carry; if (lo < carry) { hi += 1; }
1920 // Multiplikations-Einfachschleife mit Akkumulation:
1921 // Multipliziert eine UDS mit einem Digit und addiert das Ergebnis zu einer
1923 // muluadd_loop_up(digit,sourceptr,destptr,len);
1924 // multipliziert die UDS sourceptr[0..len-1] (len>0)
1925 // mit dem einzelnen digit, legt das Ergebnis in der UDS destptr[0..len-1]
1926 // ab und liefert den weiteren Übertrag.
1928 inline uintD muluadd_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1929 { var uintDD carry = 0;
1931 { dotimespC(len,len,
1932 { // Hier ist 0 <= carry <= digit.
1933 carry = carry + muluD(digit,*sourceptr++) + (uintDD)*destptr;
1934 // Hier ist 0 <= carry <= 2^intDsize*digit + 2^intDsize-1.
1935 *destptr++ = lowD(carry);
1936 carry = (uintDD)highD(carry); // carry := floor(carry/2^intDsize) <= digit
1942 inline uintD muluadd_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1943 { var uintD carry = 0;
1945 { dotimespC(len,len,
1946 { // Hier ist 0 <= carry <= digit.
1949 muluD(digit,*sourceptr++,hi=,lo=);
1950 // Hier ist 0 <= 2^intDsize*hi + lo + carry + *destptr <= 2^intDsize*digit+2^intDsize-1.
1951 lo += carry; if (lo < carry) { hi += 1; }
1953 lo += carry; if (lo < carry) { hi += 1; }
1962 // Multiplikations-Einfachschleife mit Diminution:
1963 // Multipliziert eine UDS mit einem Digit und subtrahiert das Ergebnis von
1964 // einer zweiten UDS.
1965 // mulusub_loop_up(digit,sourceptr,destptr,len);
1966 // multipliziert die UDS sourceptr[0..len-1] (len>0) mit dem einzelnen
1967 // digit, subtrahiert das Ergebnis von der UDS destptr[0..len-1] und liefert
1968 // den weiteren Übertrag (>=0, evtl. von destptr[len] zu subtrahieren).
1970 inline uintD mulusub_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1971 { var uintDD carry = 0;
1973 { dotimespC(len,len,
1974 { // Hier ist 0 <= carry <= digit.
1975 carry = carry + muluD(digit,*sourceptr++) + (uintD)(~(*destptr));
1976 // Hier ist 0 <= carry <= 2^intDsize*digit + 2^intDsize-1.
1977 *destptr++ = ~lowD(carry);
1978 carry = (uintDD)highD(carry); // carry := floor(carry/2^intDsize) <= digit
1979 // Hier ist 0 <= carry <= digit.
1984 return 0; // nichts zu subtrahieren -> kein Übertrag
1987 inline uintD mulusub_loop_up (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
1988 { var uintD carry = 0;
1990 { dotimespC(len,len,
1991 { // Hier ist 0 <= carry <= digit.
1994 muluD(digit,*sourceptr++,hi=,lo=);
1995 // Hier ist 0 <= 2^intDsize*hi + lo + carry + ~(*destptr) <= 2^intDsize*digit+2^intDsize-1.
1996 lo += carry; if (lo < carry) { hi += 1; }
1998 *destptr++ = carry - lo; if (carry < lo) { hi += 1; }
2004 return 0; // nichts zu subtrahieren -> kein Übertrag
2012 // Divisions-Einfachschleife:
2013 // Dividiert eine UDS durch ein Digit.
2014 // divu_loop_down(digit,ptr,len)
2015 // dividiert die UDS ptr[-len..-1] durch digit,
2016 // legt das Ergebnis in derselben UDS ab, und liefert den Rest (>=0, <digit).
2018 inline uintD divu_loop_down (uintD digit, uintD* ptr, uintC len)
2019 { var uintD rest = 0;
2021 { --ptr; divuD(highlowDD(rest,*ptr),digit,*ptr =, rest =); }
2026 inline uintD divu_loop_down (uintD digit, uintD* ptr, uintC len)
2027 { var uintD rest = 0;
2029 { --ptr; divuD(rest,*ptr,digit,*ptr =, rest =); }
2035 // Divisions-Einfachschleife:
2036 // Dividiert eine UDS durch ein Digit und legt das Ergebnis in einer
2038 // divucopy_loop_down(digit,sourceptr,destptr,len)
2039 // dividiert die UDS sourceptr[-len..-1] durch digit,
2040 // legt das Ergebnis in der UDS destptr[-len..-1] ab,
2041 // und liefert den Rest (>=0, <digit).
2043 inline uintD divucopy_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
2044 { var uintD rest = 0;
2046 { divuD(highlowDD(rest,*--sourceptr),digit,*--destptr =, rest =); }
2051 inline uintD divucopy_loop_down (uintD digit, const uintD* sourceptr, uintD* destptr, uintC len)
2052 { var uintD rest = 0;
2054 { divuD(rest,*--sourceptr,digit,*--destptr =, rest =); }
2062 #endif // !CL_DS_BIG_ENDIAN_P
2064 #if !defined(TEST_LOOPS) && !CL_DS_BIG_ENDIAN_P
2066 // Vergleichsschleife:
2067 // result = compare_loop_up(xptr,yptr,count);
2068 // vergleicht nacheinander xptr[0] mit yptr[0], xptr[1] mit yptr[1], usw.,
2069 // insgesamt count Digits, und liefert 0 falls alle gleich sind,
2070 // +1 falls zuerst ein xptr[i]>yptr[i] ist,
2071 // -1 falls zuerst ein xptr[i]<yptr[i] ist.
2072 inline cl_signean compare_loop_up (const uintD* xptr, const uintD* yptr, uintC count)
2073 { dotimesC(count,count,
2074 { if (!(*xptr++ == *yptr++))
2075 // verschiedene Digits gefunden
2076 return (*--xptr > *--yptr ? signean_plus : signean_minus);
2078 return signean_null; // alle Digits gleich
2083 #if !defined(LOG_LOOPS) && !CL_DS_BIG_ENDIAN_P
2086 // xor_loop_up(xptr,yptr,count);
2087 // verknüpft count (uintC>=0) Digits aufwärts ab xptr und ab yptr
2088 // mit Ziel ab xptr durch XOR.
2089 inline void xor_loop_up (uintD* xptr, const uintD* yptr, uintC count)
2090 { dotimesC(count,count, { *xptr++ ^= *yptr++; } ); }
2094 #if !defined(SHIFT_LOOPS) && CL_DS_BIG_ENDIAN_P
2096 // Schiebe- und Kopierschleife um i Bits nach links:
2097 // übertrag = shiftleftcopy_loop_up(sourceptr,destptr,count,i);
2098 // kopiert count (uintC>=0) Digits aufwärts von sourceptr nach destptr
2099 // und schiebt sie dabei um i Bits (0<i<intDsize) nach links,
2100 // wobei ganz rechts mit i Nullbits aufgefüllt wird,
2101 // und liefert den Übertrag (was links rauskommt, >=0, <2^i).
2103 inline uintD shiftleftcopy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count, uintC i)
2104 { var uintDD accu = 0;
2105 dotimesC(count,count,
2106 { accu = ((uintDD)(*sourceptr++)<<i)+accu; *destptr++ = lowD(accu);
2107 accu = (uintDD)(highD(accu));
2112 inline uintD shiftleftcopy_loop_up (const uintD* sourceptr, uintD* destptr, uintC count, uintC i)
2113 { var uintC j = intDsize-i;
2114 var uintD carry = 0;
2115 dotimesC(count,count,
2116 { var uintD accu = *sourceptr++;
2117 *destptr++ = (accu<<i) | carry;
2126 #if !defined(SHIFT_LOOPS)
2128 // Schiebe- und XOR-Schleife:
2129 // shiftxor_loop_up(xptr,yptr,count,i);
2130 // verknüpft count+1 Digits aufwärts ab xptr mit count Digits aufwärts ab yptr,
2131 // um i Bits verschoben, durch XOR. (count uintC>=0, 0<i<intDsize)
2133 inline void shiftxor_loop_up (uintD* xptr, const uintD* yptr, uintC count, uintC i)
2135 { var uintD carry = xptr[0];
2136 dotimespC(count,count,
2137 { var uintDD accu = highlowDD(xptr[1],carry);
2138 accu = ((uintDD)(*yptr++)<<i) ^ accu;
2139 *xptr++ = lowD(accu);
2140 carry = highD(accu);
2145 inline void shiftxor_loop_up (uintD* xptr, const uintD* yptr, uintC count, uintC i)
2147 { var uintC j = intDsize-i;
2148 var uintD carry = *xptr;
2149 dotimespC(count,count,
2150 { var uintD accu = *yptr++;
2151 *xptr++ = (accu<<i) ^ carry;
2152 carry = (accu>>j) ^ *xptr;
2161 // Endianness independent names for these functions.
2162 #if CL_DS_BIG_ENDIAN_P
2163 #define copy_loop_msp copy_loop_up
2164 #define copy_loop_lsp copy_loop_down
2165 #define fill_loop_msp fill_loop_up
2166 #define fill_loop_lsp fill_loop_down
2167 #define clear_loop_msp clear_loop_up
2168 #define clear_loop_lsp clear_loop_down
2169 #define test_loop_msp test_loop_up
2170 #define or_loop_msp or_loop_up
2171 #define xor_loop_msp xor_loop_up
2172 #define and_loop_msp and_loop_up
2173 #define eqv_loop_msp eqv_loop_up
2174 #define nand_loop_msp nand_loop_up
2175 #define nor_loop_msp nor_loop_up
2176 #define andc2_loop_msp andc2_loop_up
2177 #define orc2_loop_msp orc2_loop_up
2178 #define not_loop_msp not_loop_up
2179 #define and_test_loop_msp and_test_loop_up
2180 #define compare_loop_msp compare_loop_up
2181 #define add_loop_lsp add_loop_down
2182 #define addto_loop_lsp addto_loop_down
2183 #define inc_loop_lsp inc_loop_down
2184 #define sub_loop_lsp sub_loop_down
2185 #define subx_loop_lsp subx_loop_down
2186 #define subfrom_loop_lsp subfrom_loop_down
2187 #define dec_loop_lsp dec_loop_down
2188 #define neg_loop_lsp neg_loop_down
2189 #define shift1left_loop_lsp shift1left_loop_down
2190 #define shiftleft_loop_lsp shiftleft_loop_down
2191 #define shiftleftcopy_loop_lsp shiftleftcopy_loop_down
2192 #define shift1right_loop_msp shift1right_loop_up
2193 #define shiftright_loop_msp shiftright_loop_up
2194 #define shiftrightsigned_loop_msp shiftrightsigned_loop_up
2195 #define shiftrightcopy_loop_msp shiftrightcopy_loop_up
2196 #define mulusmall_loop_lsp mulusmall_loop_down
2197 #define mulu_loop_lsp mulu_loop_down
2198 #define muluadd_loop_lsp muluadd_loop_down
2199 #define mulusub_loop_lsp mulusub_loop_down
2200 #define divu_loop_msp divu_loop_up
2201 #define divucopy_loop_msp divucopy_loop_up
2203 #define copy_loop_msp copy_loop_down
2204 #define copy_loop_lsp copy_loop_up
2205 #define fill_loop_msp fill_loop_down
2206 #define fill_loop_lsp fill_loop_up
2207 #define clear_loop_msp clear_loop_down
2208 #define clear_loop_lsp clear_loop_up
2209 #define test_loop_msp test_loop_down
2210 #define or_loop_msp or_loop_down
2211 #define xor_loop_msp xor_loop_down
2212 #define and_loop_msp and_loop_down
2213 #define eqv_loop_msp eqv_loop_down
2214 #define nand_loop_msp nand_loop_down
2215 #define nor_loop_msp nor_loop_down
2216 #define andc2_loop_msp andc2_loop_down
2217 #define orc2_loop_msp orc2_loop_down
2218 #define not_loop_msp not_loop_down
2219 #define and_test_loop_msp and_test_loop_down
2220 #define compare_loop_msp compare_loop_down
2221 #define add_loop_lsp add_loop_up
2222 #define addto_loop_lsp addto_loop_up
2223 #define inc_loop_lsp inc_loop_up
2224 #define sub_loop_lsp sub_loop_up
2225 #define subx_loop_lsp subx_loop_up
2226 #define subfrom_loop_lsp subfrom_loop_up
2227 #define dec_loop_lsp dec_loop_up
2228 #define neg_loop_lsp neg_loop_up
2229 #define shift1left_loop_lsp shift1left_loop_up
2230 #define shiftleft_loop_lsp shiftleft_loop_up
2231 #define shiftleftcopy_loop_lsp shiftleftcopy_loop_up
2232 #define shift1right_loop_msp shift1right_loop_down
2233 #define shiftright_loop_msp shiftright_loop_down
2234 #define shiftrightsigned_loop_msp shiftrightsigned_loop_down
2235 #define shiftrightcopy_loop_msp shiftrightcopy_loop_down
2236 #define mulusmall_loop_lsp mulusmall_loop_up
2237 #define mulu_loop_lsp mulu_loop_up
2238 #define muluadd_loop_lsp muluadd_loop_up
2239 #define mulusub_loop_lsp mulusub_loop_up
2240 #define divu_loop_msp divu_loop_down
2241 #define divucopy_loop_msp divucopy_loop_down
2244 // Endianness independent loops where the direction doesn't matter.
2245 #if CL_DS_BIG_ENDIAN_P
2246 #define DS_clear_loop(MSDptr,len,LSDptr) (void)clear_loop_up(MSDptr,len)
2247 #define DS_test_loop(MSDptr,len,LSDptr) test_loop_up(MSDptr,len)
2249 #define DS_clear_loop(MSDptr,len,LSDptr) (void)clear_loop_up(LSDptr,len)
2250 #define DS_test_loop(MSDptr,len,LSDptr) test_loop_up(LSDptr,len)
2254 // Umwandlungsroutinen Digit-Sequence-Teil <--> Longword:
2257 // holt die nächsten 32 Bits aus den 32/intDsize Digits ab ptr.
2258 // set_32_Dptr(ptr,wert);
2259 // speichert den Wert wert (32 Bits) in die 32/intDsize Digits ab ptr.
2260 // get_max32_Dptr(count,ptr)
2261 // holt die nächsten count Bits aus den ceiling(count/intDsize) Digits ab ptr.
2262 // set_max32_Dptr(count,ptr,wert)
2263 // speichert wert (count Bits) in die ceiling(count/intDsize) Digits ab ptr.
2264 // Jeweils ptr eine Variable vom Typ uintD*,
2265 // wert eine Variable vom Typ uint32,
2266 // count eine Variable oder constant-expression mit Wert >=0, <=32.
2268 inline uint32 get_32_Dptr (const uintD* ptr)
2270 return mspref(ptr,0);
2272 inline void set_32_Dptr (uintD* ptr, uint32 wert)
2274 mspref(ptr,0) = wert;
2276 inline uint32 get_max32_Dptr (uintC count, const uintD* ptr)
2278 return count==0 ? 0 :
2281 inline void set_max32_Dptr (uintC count, uintD* ptr, uint32 wert)
2283 if (count==0) return;
2284 mspref(ptr,0) = wert; return;
2288 inline uint32 get_32_Dptr (const uintD* ptr)
2290 return ((uint32)mspref(ptr,0)<<16) | (uint32)mspref(ptr,1);
2292 inline void set_32_Dptr (uintD* ptr, uint32 wert)
2294 mspref(ptr,0) = (uintD)(wert>>16); mspref(ptr,1) = (uintD)wert;
2296 inline uint32 get_max32_Dptr (uintC count, const uintD* ptr)
2298 return count==0 ? 0 :
2299 count<=16 ? mspref(ptr,0) :
2300 ((uint32)mspref(ptr,0)<<16) | (uint32)mspref(ptr,1);
2302 inline void set_max32_Dptr (uintC count, uintD* ptr, uint32 wert)
2304 if (count==0) return;
2305 if (count<=16) { mspref(ptr,0) = (uintD)wert; return; }
2306 mspref(ptr,0) = (uintD)(wert>>16); mspref(ptr,1) = (uintD)wert; return;
2310 inline uint32 get_32_Dptr (const uintD* ptr)
2312 return ((((((uint32)mspref(ptr,0) <<8) | (uint32)mspref(ptr,1)) <<8) | (uint32)mspref(ptr,2)) <<8) | (uint32)mspref(ptr,3);
2314 inline void set_32_Dptr (uintD* ptr, uint32 wert)
2316 mspref(ptr,0) = (uintD)(wert>>24); mspref(ptr,1) = (uintD)(wert>>16); mspref(ptr,2) = (uintD)(wert>>8); mspref(ptr,3) = (uintD)wert;
2318 inline uint32 get_max32_Dptr (uintC count, const uintD* ptr)
2320 return count==0 ? 0 :
2321 count<=8 ? mspref(ptr,0) :
2322 count<=16 ? ((uint32)mspref(ptr,0)<<8) | (uint32)mspref(ptr,1) :
2323 count<=24 ? ((((uint32)mspref(ptr,0)<<8) | (uint32)mspref(ptr,1))<<8) | (uint32)mspref(ptr,2) :
2324 ((((((uint32)mspref(ptr,0)<<8) | (uint32)mspref(ptr,1))<<8) | (uint32)mspref(ptr,2))<<8) | (uint32)mspref(ptr,3);
2326 inline void set_max32_Dptr (uintC count, uintD* ptr, uint32 wert)
2328 if (count==0) return;
2329 if (count<=8) { mspref(ptr,0) = (uintD)wert; return; }
2330 if (count<=16) { mspref(ptr,0) = (uintD)(wert>>8); mspref(ptr,1) = (uintD)wert; return; }
2331 if (count<=24) { mspref(ptr,0) = (uintD)(wert>>16); mspref(ptr,1) = (uintD)(wert>>8); mspref(ptr,2) = (uintD)wert; return; }
2332 mspref(ptr,0) = (uintD)(wert>>24); mspref(ptr,1) = (uintD)(wert>>16); mspref(ptr,2) = (uintD)(wert>>8); mspref(ptr,3) = (uintD)wert; return;
2336 #if (cl_word_size==64)
2338 // holt die nächsten 64 Bits aus den 64/intDsize Digits ab ptr.
2339 // set_64_Dptr(ptr,wert);
2340 // speichert den Wert wert (64 Bits) in die 64/intDsize Digits ab ptr.
2341 // get_max64_Dptr(count,ptr)
2342 // holt die nächsten count Bits aus den ceiling(count/intDsize) Digits ab ptr.
2343 // set_max64_Dptr(count,ptr,wert)
2344 // speichert wert (count Bits) in die ceiling(count/intDsize) Digits ab ptr.
2345 // Jeweils ptr eine Variable vom Typ uintD*,
2346 // wert eine Variable vom Typ uint64,
2347 // count eine Variable oder constant-expression mit Wert >=0, <=64.
2349 inline uint64 get_64_Dptr (const uintD* ptr)
2351 return mspref(ptr,0);
2353 inline void set_64_Dptr (uintD* ptr, uint64 wert)
2355 mspref(ptr,0) = wert;
2357 inline uint64 get_max64_Dptr (uintC count, const uintD* ptr)
2359 return count==0 ? 0 : mspref(ptr,0);
2361 inline void set_max64_Dptr (uintC count, uintD* ptr, uint64 wert)
2363 if (count==0) return;
2364 mspref(ptr,0) = wert; return;
2366 #else // (intDsize<=32)
2367 inline uint64 get_64_Dptr (const uintD* ptr)
2369 return ((uint64)get_32_Dptr(ptr) << 32) | (uint64)get_32_Dptr(ptr mspop 32/intDsize);
2371 inline void set_64_Dptr (uintD* ptr, uint64 wert)
2373 set_32_Dptr(ptr,(uint32)(wert>>32));
2374 set_32_Dptr(ptr mspop 32/intDsize,(uint32)wert);
2376 inline uint64 get_max64_Dptr (uintC count, const uintD* ptr)
2378 return count==0 ? 0 :
2379 count<=32 ? (uint64)get_max32_Dptr(count,ptr) :
2380 ((uint64)get_max32_Dptr(count-32,ptr) << 32) | (uint64)get_32_Dptr(ptr mspop ceiling(count-32,intDsize));
2382 inline void set_max64_Dptr (uintC count, uintD* ptr, uint64 wert)
2384 if (count==0) return;
2385 if (count<=32) { set_max32_Dptr(count,ptr,(uint32)wert); return; }
2386 set_max32_Dptr(count-32,ptr,(uint32)(wert>>32));
2387 set_32_Dptr(ptr mspop ceiling(count-32,intDsize),(uint32)wert); return;
2392 // get_uint1D_Dptr(ptr) holt 1 Digit (unsigned) ab ptr
2393 // get_uint2D_Dptr(ptr) holt 2 Digits (unsigned) ab ptr
2394 // get_uint3D_Dptr(ptr) holt 3 Digits (unsigned) ab ptr
2395 // get_uint4D_Dptr(ptr) holt 4 Digits (unsigned) ab ptr
2396 // get_sint1D_Dptr(ptr) holt 1 Digit (signed) ab ptr
2397 // get_sint2D_Dptr(ptr) holt 2 Digits (signed) ab ptr
2398 // get_sint3D_Dptr(ptr) holt 3 Digits (signed) ab ptr
2399 // get_sint4D_Dptr(ptr) holt 4 Digits (signed) ab ptr
2400 // Jeweils ptr eine Variable vom Typ uintD*.
2401 // NB: Bei intDsize==64 sind diese Funktionen nur sehr bedingt tauglich.
2402 inline uint32 get_uint1D_Dptr (const uintD* ptr)
2404 return lspref(ptr,0);
2406 inline sint32 get_sint1D_Dptr (const uintD* ptr)
2408 return (sint32)(sintD)lspref(ptr,0);
2411 inline uint32 get_uint2D_Dptr (const uintD* ptr)
2413 return ((uint32)lspref(ptr,1) << intDsize) | (uint32)lspref(ptr,0);
2415 inline sint32 get_sint2D_Dptr (const uintD* ptr)
2417 return ((uint32)(sint32)(sintD)lspref(ptr,1) << intDsize) | (uint32)lspref(ptr,0);
2420 #define get_uint2D_Dptr(ptr) get_uint1D_Dptr(ptr)
2421 #define get_sint2D_Dptr(ptr) (sint32)get_uint2D_Dptr(ptr)
2424 inline uint32 get_uint3D_Dptr (const uintD* ptr)
2426 return ((((uint32)lspref(ptr,2) << intDsize) | (uint32)lspref(ptr,1)) << intDsize) | (uint32)lspref(ptr,0);
2428 inline sint32 get_sint3D_Dptr (const uintD* ptr)
2430 return ((((uint32)(sint32)(sintD)lspref(ptr,2) << intDsize) | (uint32)lspref(ptr,1)) << intDsize) | (uint32)lspref(ptr,0);
2432 inline uint32 get_uint4D_Dptr (const uintD* ptr)
2434 return ((((((uint32)lspref(ptr,3) << intDsize) | (uint32)lspref(ptr,2)) << intDsize) | (uint32)lspref(ptr,1)) << intDsize) | (uint32)lspref(ptr,0);
2436 inline sint32 get_sint4D_Dptr (const uintD* ptr)
2438 return ((((((uint32)(sint32)(sintD)lspref(ptr,3) << intDsize) | (uint32)lspref(ptr,2)) << intDsize) | (uint32)lspref(ptr,1)) << intDsize) | (uint32)lspref(ptr,0);
2441 #define get_uint3D_Dptr(ptr) get_uint2D_Dptr(ptr)
2442 #define get_sint3D_Dptr(ptr) (sint32)get_uint3D_Dptr(ptr)
2443 #define get_uint4D_Dptr(ptr) get_uint2D_Dptr(ptr)
2444 #define get_sint4D_Dptr(ptr) (sint32)get_uint4D_Dptr(ptr)
2448 // NUM_STACK ist eine Art Zahlen-Stack-Pointer.
2450 // {CL_ALLOCA_STACK;
2452 // num_stack_alloc(...);
2454 // num_stack_array(...);
2457 // CL_ALLOCA_STACK rettet den aktuellen Wert von NUM_STACK.
2458 // Dann darf beliebig oft mit num_stack_alloc/num_stack_array Platz auf dem
2459 // Zahlen-Stack belegt werden.
2460 // Beim Ende des Blocks wird NUM_STACK wieder auf den vorigen Wert gesetzt,
2461 // und der Platz gilt als wieder freigegeben.
2462 // In jeder C-Funktion sollte CL_ALLOCA_STACK nur einmal aufgerufen werden.
2463 // Wegen eines GCC-Bugs sollten Funktionen, die diese Macros benutzen,
2464 // nicht inline deklariert sein.
2466 // num_stack_array(need, low_addr = , high_addr = );
2467 // num_stack_small_array(need, low_addr = , high_addr = );
2468 // belegt need Digits auf dem Zahlen-Stack und legt die untere Grenze des
2469 // allozierten Bereichs in low_addr und die obere Grenze in high_addr ab.
2470 // Jedes von beiden ist optional.
2472 // num_stack_alloc(need, MSDptr = , LSDptr = );
2473 // num_stack_small_alloc(need, MSDptr = , LSDptr = );
2474 // belegt need Digits auf dem Zahlen-Stack und legt den MSDptr und den
2475 // LSDptr ab. Jedes von beiden ist optional.
2477 // num_stack_alloc_1(need, MSDptr = , LSDptr = );
2478 // num_stack_small_alloc_1(need, MSDptr = , LSDptr = );
2479 // wie num_stack_alloc, nur daß unterhalb von MSDptr noch ein Digit Platz
2480 // zusätzlich belegt wird.
2482 #define num_stack_array(need,low_zuweisung,high_zuweisung) \
2483 {var uintL __need = (uintL)(need); \
2484 var uintD* __array = cl_alloc_array(uintD,__need); \
2485 unused (low_zuweisung &__array[0]); unused (high_zuweisung &__array[__need]); \
2487 #define num_stack_small_array(need,low_zuweisung,high_zuweisung) \
2488 {var uintL __need = (uintL)(need); \
2489 var uintD* __array = cl_small_alloc_array(uintD,__need); \
2490 unused (low_zuweisung &__array[0]); unused (high_zuweisung &__array[__need]); \
2492 #if CL_DS_BIG_ENDIAN_P
2493 #define num_stack_alloc(need,MSDptr_zuweisung,LSDptr_zuweisung) \
2494 num_stack_array(need,MSDptr_zuweisung,LSDptr_zuweisung)
2495 #define num_stack_small_alloc(need,MSDptr_zuweisung,LSDptr_zuweisung) \
2496 num_stack_small_array(need,MSDptr_zuweisung,LSDptr_zuweisung)
2497 #define num_stack_alloc_1(need,MSDptr_zuweisung,LSDptr_zuweisung) \
2498 num_stack_array((uintL)(need)+1,MSDptr_zuweisung 1 + ,LSDptr_zuweisung)
2499 #define num_stack_small_alloc_1(need,MSDptr_zuweisung,LSDptr_zuweisung) \
2500 num_stack_small_array((uintL)(need)+1,MSDptr_zuweisung 1 + ,LSDptr_zuweisung)
2502 #define num_stack_alloc(need,MSDptr_zuweisung,LSDptr_zuweisung) \
2503 num_stack_array(need,LSDptr_zuweisung,MSDptr_zuweisung)
2504 #define num_stack_small_alloc(need,MSDptr_zuweisung,LSDptr_zuweisung) \
2505 num_stack_small_array(need,LSDptr_zuweisung,MSDptr_zuweisung)
2506 #define num_stack_alloc_1(need,MSDptr_zuweisung,LSDptr_zuweisung) \
2507 num_stack_array((uintL)(need)+1,LSDptr_zuweisung,MSDptr_zuweisung -1 + )
2508 #define num_stack_small_alloc_1(need,MSDptr_zuweisung,LSDptr_zuweisung) \
2509 num_stack_small_array((uintL)(need)+1,LSDptr_zuweisung,MSDptr_zuweisung -1 + )
2513 // Macro: In der DS MSDptr/len/LSDptr wird eine 1 unterhalb des Pointers ptr
2514 // addiert. Unterhalb von MSDptr muß 1 Digit Platz sein.
2515 // Dabei ist ptr - MSDptr = count und 0 < count <= len .
2516 // Eventuell wird MSDptr erniedrigt und len erhöht.
2517 #define DS_1_plus(ptr,count) \
2518 {var uintD* ptr_from_DS_1_plus = (ptr); \
2519 var uintC count_from_DS_1_plus = (count); \
2520 loop { if (--count_from_DS_1_plus==0) /* Zähler erniedrigen */\
2521 { /* Beim Most Significant Digit angelangt */\
2522 lsprefnext(ptr_from_DS_1_plus) += 1; \
2523 /* jetzt ist ptr_from_DS_1_plus = MSDptr */\
2524 if (mspref(ptr_from_DS_1_plus,0) == (uintD)bit(intDsize-1)) \
2525 { /* 7FFF + 1 muß zu 00008000 werden: */\
2526 lsprefnext(MSDptr) = 0; \
2531 if (!((lsprefnext(ptr_from_DS_1_plus) += 1) == 0)) /* weiterincrementieren */\
2532 break; /* kein weiterer Übertrag -> Schleife abbrechen */\
2535 // Macro: In der DS MSDptr/len/LSDptr wird eine 1 unterhalb des Pointers ptr
2536 // subtrahiert. Unterhalb von MSDptr muß 1 Digit Platz sein.
2537 // Dabei ist ptr - MSDptr = count und 0 < count <= len .
2538 // Eventuell wird MSDptr erniedrigt und len erhöht.
2539 #define DS_minus1_plus(ptr,count) \
2540 {var uintD* ptr_from_DS_minus1_plus = (ptr); \
2541 var uintC count_from_DS_minus1_plus = (count); \
2542 loop { if (--count_from_DS_minus1_plus==0) /* Zähler erniedrigen */\
2543 { /* Beim Most Significant Digit angelangt */\
2544 lsprefnext(ptr_from_DS_minus1_plus) -= 1; \
2545 /* jetzt ist ptr_from_DS_minus1_plus = MSDptr */\
2546 if (mspref(ptr_from_DS_minus1_plus,0) == (uintD)bit(intDsize-1)-1) \
2547 { /* 8000 - 1 muß zu FFFF7FFF werden: */\
2548 lsprefnext(MSDptr) = (uintD)(-1); \
2553 if (!((sintD)(lsprefnext(ptr_from_DS_minus1_plus) -= 1) == -1)) /* weiterdecrementieren */\
2554 break; /* kein weiterer Übertrag -> Schleife abbrechen */\
2558 // Multiplikations-Doppelschleife:
2559 // Multipliziert zwei UDS und legt das Ergebnis in einer dritten UDS ab.
2560 // cl_UDS_mul(sourceptr1,len1,sourceptr2,len2,destptr);
2561 // multipliziert die UDS sourceptr1[-len1..-1] (len1>0)
2562 // mit der UDS sourceptr2[-len1..-1] (len2>0)
2563 // und legt das Ergebnis in der UDS destptr[-len..-1] (len=len1+len2) ab.
2564 // Unterhalb von destptr werden len Digits Platz benötigt.
2565 extern void cl_UDS_mul (const uintD* sourceptr1, uintC len1,
2566 const uintD* sourceptr2, uintC len2,
2568 // Spezialfall sourceptr1 == sourceptr2 && len1 == len2.
2569 extern void cl_UDS_mul_square (const uintD* sourceptr, uintC len,
2572 // Multipliziert zwei Unsigned-Digit-sequences.
2573 // UDS_UDS_mul_UDS(len1,LSDptr1, len2,LSDptr2, MSDptr=,len=,LSDptr=);
2574 // multipliziert die UDS ../len1/LSDptr1 und ../len2/LSDptr2.
2575 // Dabei sollte len1>0 und len2>0 sein.
2576 // Ergebnis ist die UDS MSDptr/len/LSDptr, mit len=len1+len2, im Stack.
2577 // Dabei wird num_stack erniedrigt.
2578 #define UDS_UDS_mul_UDS(len1,LSDptr1,len2,LSDptr2, MSDptr_zuweisung,len_zuweisung,LSDptr_zuweisung) \
2579 var uintL CONCAT(len_from_UDSmul_,__LINE__) = (uintL)(len1) + (uintL)(len2); \
2580 var uintD* CONCAT(LSDptr_from_UDSmul_,__LINE__); \
2581 unused (len_zuweisung CONCAT(len_from_UDSmul_,__LINE__)); \
2582 num_stack_alloc(CONCAT(len_from_UDSmul_,__LINE__),MSDptr_zuweisung,LSDptr_zuweisung CONCAT(LSDptr_from_UDSmul_,__LINE__) =); \
2583 cl_UDS_mul((LSDptr1),(len1),(LSDptr2),(len2),CONCAT(LSDptr_from_UDSmul_,__LINE__));
2585 // Multipliziert zwei Digit-sequences.
2586 // DS_DS_mul_DS(MSDptr1,len1,LSDptr1, MSDptr2,len2,LSDptr2, MSDptr=,len=,LSDptr=);
2587 // multipliziert die DS MSDptr1/len1/LSDptr1 und MSDptr2/len2/LSDptr2.
2588 // Dabei sollte len1>0 und len2>0 sein, und beide DS sollten /= 0 sein.
2589 // Alles sollten Variablen sein!
2590 // Ergebnis ist die DS MSDptr/len/LSDptr, mit len=len1+len2, im Stack.
2591 // Dabei wird num_stack erniedrigt.
2593 // Erst unsigned multiplizieren. Dann bis zu zwei Subtraktionen.
2594 // Sei b=2^intDsize, k=len1, l=len2, n=DS1, m=DS2.
2595 // Gesucht ist n * m.
2596 // Wir errechnen erst das unsigned-product p (mod b^(k+l)).
2597 // n>0, m>0: p = n*m, n*m = p
2598 // n<0, m>0: p = (n+b^k)*m, n*m + b^(k+l) = p - b^k * m (mod b^(k+l)).
2599 // n>0, m<0: p = n*(m+b^l), n*m + b^(k+l) = p - b^l * n (mod b^(k+l)).
2600 // n<0, m<0: p = (n+b^k)*(m+b^l),
2601 // n*m = p - b^k * (m+b^l) - b^l * (n+b^k) (mod b^(k+l)).
2602 #define DS_DS_mul_DS(MSDptr1,len1,LSDptr1,MSDptr2,len2,LSDptr2, MSDptr_zuweisung,len_zuweisung,LSDptr_zuweisung) \
2603 var uintD* MSDptr0; \
2604 var uintD* LSDptr0; \
2605 var uintL len_from_DSmal = (uintL)(len1) + (uintL)(len2); \
2606 unused (len_zuweisung len_from_DSmal); \
2607 num_stack_alloc(len_from_DSmal,MSDptr_zuweisung MSDptr0 =,LSDptr_zuweisung LSDptr0 =); \
2608 var uintD MSD1_from_DSmal = mspref(MSDptr1,0); \
2609 var uintD MSD2_from_DSmal = mspref(MSDptr2,0); \
2610 var uintL len1_from_DSmal = (len1); \
2611 var uintL len2_from_DSmal = (len2); \
2612 if (MSD1_from_DSmal==0) { msprefnext(MSDptr0) = 0; len1_from_DSmal--; } \
2613 if (MSD2_from_DSmal==0) { msprefnext(MSDptr0) = 0; len2_from_DSmal--; } \
2614 cl_UDS_mul((LSDptr1),len1_from_DSmal,(LSDptr2),len2_from_DSmal,LSDptr0); \
2615 if ((sintD)MSD1_from_DSmal < 0) /* n<0 ? */\
2616 /* muß m bzw. m+b^l subtrahieren, um k Digits verschoben: */\
2617 { subfrom_loop_lsp(LSDptr2,LSDptr0 lspop len1,len2); } \
2618 if ((sintD)MSD2_from_DSmal < 0) /* m<0 ? */\
2619 /* muß n bzw. n+b^k subtrahieren, um l Digits verschoben: */\
2620 { subfrom_loop_lsp(LSDptr1,LSDptr0 lspop len2,len1); }
2623 // Dividiert zwei Unsigned Digit sequences durcheinander.
2624 // UDS_divide(a_MSDptr,a_len,a_LSDptr, b_MSDptr,b_len,b_LSDptr, &q,&r);
2625 // Die UDS a = a_MSDptr/a_len/a_LSDptr (a>=0) wird durch
2626 // die UDS b = b_MSDptr/b_len/b_LSDptr (b>=0) dividiert:
2627 // a = q * b + r mit 0 <= r < b. Bei b=0 Error.
2628 // q der Quotient, r der Rest.
2629 // q = q_MSDptr/q_len/q_LSDptr, r = r_MSDptr/r_len/r_LSDptr beides
2630 // Normalized Unsigned Digit sequences.
2631 // Vorsicht: q_LSDptr <= r_MSDptr,
2632 // Vorzeichenerweiterung von r kann q zerstören!
2633 // Vorzeichenerweiterung von q ist erlaubt.
2634 // a und b werden nicht modifiziert.
2635 // num_stack wird erniedrigt.
2636 #define UDS_divide(a_MSDptr,a_len,a_LSDptr,b_MSDptr,b_len,b_LSDptr,q_,r_) \
2637 /* Platz fürs Ergebnis machen. Brauche maximal a_len+1 Digits. */\
2638 var uintC _a_len = (a_len); \
2639 var uintD* roomptr; num_stack_alloc_1(_a_len+1,roomptr=,); \
2640 cl_UDS_divide(a_MSDptr,_a_len,a_LSDptr,b_MSDptr,b_len,b_LSDptr,roomptr,q_,r_);
2641 extern void cl_UDS_divide (const uintD* a_MSDptr, uintC a_len, const uintD* a_LSDptr,
2642 const uintD* b_MSDptr, uintC b_len, const uintD* b_LSDptr,
2643 uintD* roomptr, DS* q_, DS* r_);
2646 // Bildet zu einer Unsigned Digit sequence a die Wurzel
2647 // (genauer: Gaußklammer aus Wurzel aus a).
2648 // UDS_sqrt(a_MSDptr,a_len,a_LSDptr, &b, squarep=)
2649 // > a_MSDptr/a_len/a_LSDptr: eine UDS
2650 // < NUDS b: Gaußklammer der Wurzel aus a
2651 // < squarep: cl_true falls a = b^2, cl_false falls b^2 < a < (b+1)^2.
2652 // a wird nicht modifiziert.
2653 // Vorzeichenerweiterung von b ist erlaubt.
2654 // num_stack wird erniedrigt.
2655 #define UDS_sqrt(a_MSDptr,a_len,a_LSDptr,b_,squarep_zuweisung) \
2656 { /* ceiling(a_len,2) Digits Platz fürs Ergebnis machen: */\
2657 var uintC _a_len = (a_len); \
2658 num_stack_alloc_1(ceiling(_a_len,2),(b_)->MSDptr=,); \
2659 squarep_zuweisung cl_UDS_sqrt(a_MSDptr,_a_len,a_LSDptr,b_); \
2661 extern cl_boolean cl_UDS_sqrt (const uintD* a_MSDptr, uintC a_len, const uintD* a_LSDptr, DS* b_);
2664 // Auxiliary function for approximately computing 1/x
2665 // using Newton iteration.
2666 extern void cl_UDS_recip (const uintD* a_MSDptr, uintC a_len,
2667 uintD* b_MSDptr, uintC b_len);
2669 // Auxiliary function for approximately computing 1/sqrt(x)
2670 // using Newton iteration.
2671 extern void cl_UDS_recipsqrt (const uintD* a_MSDptr, uintC a_len,
2672 uintD* b_MSDptr, uintC b_len);
2675 #endif /* _CL_DS_H */