1 // Digit level arithmetic
7 #include "base/cl_low.h"
9 // Aus cln/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!"
29 // Vorzeichen eines Digit bestimmen
30 // sign_of_sintD(wert)
32 // < sintD ergebnis: 0 falls wert>=0, -1 falls wert<0.
33 inline sint32 sign_of_sintD (sintD wert)
40 // High-Digit eines Doppel-Digit bestimmen
43 #define highD(x) ((uintD)((uintDD)(x)>>intDsize))
48 // Low-Digit eines Doppel-Digit bestimmen
50 #define lowD(x) ((uintD)(uintDD)(x))
52 // Ein Doppel-Digit aus ihrem High-Digit und ihrem Low-Digit bestimmen:
53 // highlowDD(uintD high, uintD low)
55 #define highlowDD(x,y) (((uintDD)(uintD)(x)<<intDsize)|(uintDD)(uintD)(y))
57 #define highlowDD highlow32
60 // Ein Doppel-Digit aus ihrem High-Digit und ihrem Low-Digit 0 bestimmen:
61 // highlowDD_0(uintD high)
63 #define highlowDD_0(x) ((uintDD)(uintD)(x)<<intDsize)
65 #define highlowDD_0 highlow32_0
70 // Zwei Digits multiplizieren:
71 // (uintDD)hilo = muluD(uintD arg1, uintD arg2)
73 // muluD(uintD arg1, uintD arg2, uintD hi =, uintD lo =);
77 #define muluD(arg1,arg2) ((uintDD)((uintD)(arg1)*(uintD)(arg2)))
79 #define muluD(arg1,arg2) ((uintDD)(uintD)(arg1)*(uintDD)(uintD)(arg2))
86 #define muluD(arg1,arg2) ((uintDD)(uintD)(arg1)*(uintDD)(uintD)(arg2))
97 // Zwei Digits multiplizieren, mit einem Digit als Ergebnis.
98 // (uintD)lo = muluD_unchecked(uintD arg1, uintD arg2)
99 // Es wird vorausgesetzt, daß arg1*arg2 < 2^intDsize.
100 #if (intDsize==8) || (intDsize==16) || (intDsize==64)
101 #define muluD_unchecked(arg1,arg2) ((uintD)((uintD)(arg1)*(uintD)(arg2)))
104 #define muluD_unchecked(arg1,arg2) mulu32_unchecked(arg1,arg2)
107 // Durch ein Digit dividieren:
108 // divuD(uintDD x, uintD y, uintD q =, uintD r =);
110 // divuD(uintD xhi, uintD xlo, uintD y, uintD q =, uintD r =);
111 // dividiert x/y und liefert q = floor(x/y) und r = (x mod y). x = q*y+r.
112 // Es wird vorausgesetzt, daß 0 <= x < 2^intDsize*y.
115 #define divuD divu_1616_1616
118 #define divuD divu_3216_1616
121 #define divuD(x,y,q_zuweisung,r_zuweisung) \
122 { var uint64 __x = (x); \
123 var uint32 __y = (y); \
124 var uint32 __q = floor(__x,(uint64)__y); \
125 q_zuweisung __q; r_zuweisung (uint32)__x - __q * __y; \
130 #define divuD divu_6432_3232
133 #define divuD divu_12864_6464
137 // Durch ein Digit dividieren:
138 // floorD(uintD x, uintD y)
139 // dividiert x/y und liefert q = floor(x/y).
140 // Es wird vorausgesetzt, daß y > 0.
141 #if (intDsize==8) || (intDsize==16) || (intDsize==64)
142 #define floorD(arg1,arg2) (floor((uintD)(arg1),(uintD)(arg2)))
145 #define floorD divu_3232_3232_
148 // Ganzzahl-Wurzel eines Doppel-Digits berechnen.
149 // isqrtD(xhi,xlo,y=,sqrtp=);
150 // > uintD xhi,xlo: Radikand x = 2^intDsize*xhi+xlo,
151 // >= 2^(2*intDsize-2), < 2^(2*intDsize)
152 // < uintD y: floor(sqrt(x)), >= 2^(intDsize-1), < 2^intDsize
153 // < boolean sqrtp: /=0, falls x=y^2
155 #define isqrtD(xhi,xlo,y_zuweisung,sqrtp_zuweisung) \
157 isqrt_32_16((((uint32)xhi<<8) | (uint32)xlo) << 16, _z=,sqrtp_zuweisung); \
158 y_zuweisung (_z >> 8); \
162 #define isqrtD(xhi,xlo,y_zuweisung,sqrtp_zuweisung) \
163 isqrt_32_16(highlow32(xhi,xlo),y_zuweisung,sqrtp_zuweisung)
166 #define isqrtD isqrt_64_32
169 #define isqrtD isqrt_128_64
172 // Bits eines Digit zählen:
173 // integerlengthD(digit,size=);
174 // setzt size auf die höchste in digit vorkommende Bitnummer.
175 // > digit: ein uintD >0
176 // < size: >0, <=intDsize, mit 2^(size-1) <= digit < 2^size
178 #define integerlengthD integerlength8
181 #define integerlengthD integerlength16
184 #define integerlengthD integerlength32
187 #define integerlengthD integerlength64
190 // Hintere Nullbits eines Digits zählen:
191 // ord2_D(digit,count=);
192 // setzt size auf die kleinste in digit vorkommende Bitnummer.
193 // > digit: ein uintD >0
194 // < count: >=0, <intDsize, mit 2^count | digit, digit/2^count ungerade
195 #if defined(FAST_ORD2)
196 #define ord2_D(digit,count_zuweisung) \
197 ord2_32((uint32)(digit),count_zuweisung)
199 // Sei n = ord2(x). Dann ist logxor(x,x-1) = 2^n + (2^n-1) = 2^(n+1)-1.
200 // Also (ord2 x) = (1- (integer-length (logxor x (1- x)))) .
201 #define ord2_D(digit,count_zuweisung) \
202 { var uintD _digit = digit ^ (digit - 1); \
203 integerlengthD(_digit,count_zuweisung -1 + ) \
207 // Bits eines Wortes zählen.
210 // < ergebnis: Anzahl der darin gesetzten Bits
212 inline uint8 logcountD (uint8 x8) { logcount_8(); return x8; }
215 inline uint16 logcountD (uint16 x16) { logcount_16(); return x16; }
218 inline uint32 logcountD (uint32 x32) { logcount_32(); return x32; }
221 inline uint64 logcountD (uint64 x64) { logcount_64(); return x64; }