1 // Digit level arithmetic
9 // Aus cl_types.h importiere:
10 // intDsize Anzahl Bits in einem Digit
11 // uintD, sintD Integer-Typen für ein Digit
12 // log2_intDsize log2(intDsize)
13 // HAVE_DD Flag, das anzeigt, ob ein Integertyp für Doppel-Digits da ist
14 // intDDsize Anzahl Bits in einem Doppel-Digit
15 // uintDD,sintDD Integer-Typen für ein Doppel-Digit
17 #ifdef HAVE_FAST_LONGLONG
18 #if !((64%intDsize)==0)
19 #error "intDsize should be a divisor of 64!"
22 #if !((32%intDsize)==0)
23 #error "intDsize should be a divisor of 32!"
28 // Vorzeichen eines Digit bestimmen
29 // sign_of_sintD(wert)
31 // < sintD ergebnis: 0 falls wert>=0, -1 falls wert<0.
32 inline sint32 sign_of_sintD (sintD wert)
39 // High-Digit eines Doppel-Digit bestimmen
42 #define highD(x) ((uintD)((uintDD)(x)>>intDsize))
47 // Low-Digit eines Doppel-Digit bestimmen
49 #define lowD(x) ((uintD)(uintDD)(x))
51 // Ein Doppel-Digit aus ihrem High-Digit und ihrem Low-Digit bestimmen:
52 // highlowDD(uintD high, uintD low)
54 #define highlowDD(x,y) (((uintDD)(uintD)(x)<<intDsize)|(uintDD)(uintD)(y))
56 #define highlowDD highlow32
59 // Ein Doppel-Digit aus ihrem High-Digit und ihrem Low-Digit 0 bestimmen:
60 // highlowDD_0(uintD high)
62 #define highlowDD_0(x) ((uintDD)(uintD)(x)<<intDsize)
64 #define highlowDD_0 highlow32_0
69 // Zwei Digits multiplizieren:
70 // (uintDD)hilo = muluD(uintD arg1, uintD arg2)
72 // muluD(uintD arg1, uintD arg2, uintD hi =, uintD lo =);
76 #define muluD(arg1,arg2) ((uintDD)((uintD)(arg1)*(uintD)(arg2)))
78 #define muluD(arg1,arg2) ((uintDD)(uintD)(arg1)*(uintDD)(uintD)(arg2))
84 #if (intDsize==32) && defined(HAVE_LONGLONG)
85 #define muluD(arg1,arg2) ((uintDD)(uintD)(arg1)*(uintDD)(uintD)(arg2))
96 // Zwei Digits multiplizieren, mit einem Digit als Ergebnis.
97 // (uintD)lo = muluD_unchecked(uintD arg1, uintD arg2)
98 // Es wird vorausgesetzt, daß arg1*arg2 < 2^intDsize.
99 #if (intDsize==8) || (intDsize==16) || (intDsize==64)
100 #define muluD_unchecked(arg1,arg2) ((uintD)((uintD)(arg1)*(uintD)(arg2)))
103 #define muluD_unchecked(arg1,arg2) mulu32_unchecked(arg1,arg2)
106 // Durch ein Digit dividieren:
107 // divuD(uintDD x, uintD y, uintD q =, uintD r =);
109 // divuD(uintD xhi, uintD xlo, uintD y, uintD q =, uintD r =);
110 // dividiert x/y und liefert q = floor(x/y) und r = (x mod y). x = q*y+r.
111 // Es wird vorausgesetzt, daß 0 <= x < 2^intDsize*y.
114 #define divuD divu_1616_1616
117 #define divuD divu_3216_1616
119 #if (intDsize==32) && defined(HAVE_LONGLONG)
120 #define divuD(x,y,q_zuweisung,r_zuweisung) \
121 { var uint64 __x = (x); \
122 var uint32 __y = (y); \
123 var uint32 __q = floor(__x,(uint64)__y); \
124 q_zuweisung __q; r_zuweisung (uint32)__x - __q * __y; \
129 #define divuD divu_6432_3232
132 #define divuD divu_12864_6464
136 // Durch ein Digit dividieren:
137 // floorD(uintD x, uintD y)
138 // dividiert x/y und liefert q = floor(x/y).
139 // Es wird vorausgesetzt, daß y > 0.
140 #if (intDsize==8) || (intDsize==16) || (intDsize==64)
141 #define floorD(arg1,arg2) (floor((uintD)(arg1),(uintD)(arg2)))
144 #define floorD divu_3232_3232_
147 // Ganzzahl-Wurzel eines Doppel-Digits berechnen.
148 // isqrtD(xhi,xlo,y=,sqrtp=);
149 // > uintD xhi,xlo: Radikand x = 2^intDsize*xhi+xlo,
150 // >= 2^(2*intDsize-2), < 2^(2*intDsize)
151 // < uintD y: floor(sqrt(x)), >= 2^(intDsize-1), < 2^intDsize
152 // < boolean sqrtp: /=0, falls x=y^2
154 #define isqrtD(xhi,xlo,y_zuweisung,sqrtp_zuweisung) \
156 isqrt_32_16((((uint32)xhi<<8) | (uint32)xlo) << 16, _z=,sqrtp_zuweisung); \
157 y_zuweisung (_z >> 8); \
161 #define isqrtD(xhi,xlo,y_zuweisung,sqrtp_zuweisung) \
162 isqrt_32_16(highlow32(xhi,xlo),y_zuweisung,sqrtp_zuweisung)
165 #define isqrtD isqrt_64_32
168 #define isqrtD isqrt_128_64
171 // Bits eines Digit zählen:
172 // integerlengthD(digit,size=);
173 // setzt size auf die höchste in digit vorkommende Bitnummer.
174 // > digit: ein uintD >0
175 // < size: >0, <=intDsize, mit 2^(size-1) <= digit < 2^size
177 #define integerlengthD integerlength8
180 #define integerlengthD integerlength16
183 #define integerlengthD integerlength32
186 #define integerlengthD integerlength64
189 // Hintere Nullbits eines Digits zählen:
190 // ord2_D(digit,count=);
191 // setzt size auf die kleinste in digit vorkommende Bitnummer.
192 // > digit: ein uintD >0
193 // < count: >=0, <intDsize, mit 2^count | digit, digit/2^count ungerade
194 #if defined(FAST_ORD2)
195 #define ord2_D(digit,count_zuweisung) \
196 ord2_32((uint32)(digit),count_zuweisung)
198 // Sei n = ord2(x). Dann ist logxor(x,x-1) = 2^n + (2^n-1) = 2^(n+1)-1.
199 // Also (ord2 x) = (1- (integer-length (logxor x (1- x)))) .
200 #define ord2_D(digit,count_zuweisung) \
201 { var uintD _digit = digit ^ (digit - 1); \
202 integerlengthD(_digit,count_zuweisung -1 + ) \
206 // Bits eines Wortes zählen.
209 // < ergebnis: Anzahl der darin gesetzten Bits
211 inline uint8 logcountD (uint8 x8) { logcount_8(); return x8; }
214 inline uint16 logcountD (uint16 x16) { logcount_16(); return x16; }
217 inline uint32 logcountD (uint32 x32) { logcount_32(); return x32; }
220 inline uint64 logcountD (uint64 x64) { logcount_64(); return x64; }