src/base/digit/cl_D.h

   1 // Digit level arithmetic
   2
   3 #ifndef _CL_D_H
   4 #define _CL_D_H
   5
   6 #include "cl_types.h"
   7 #include "cl_low.h"
   8
   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
  16
  17 #ifdef HAVE_FAST_LONGLONG
  18   #if !((64%intDsize)==0)
  19     #error "intDsize should be a divisor of 64!"
  20   #endif
  21 #else
  22   #if !((32%intDsize)==0)
  23     #error "intDsize should be a divisor of 32!"
  24   #endif
  25 #endif
  26
  27
  28 // Vorzeichen eines Digit bestimmen
  29 // sign_of_sintD(wert)
  30 // > wert: ein Digit
  31 // < sintD ergebnis: 0 falls wert>=0, -1 falls wert<0.
  32 inline sint32 sign_of_sintD (sintD wert)
  33 {
  34         return sign_of(wert);
  35 }
  36
  37 #if HAVE_DD
  38
  39 // High-Digit eines Doppel-Digit bestimmen
  40 // highD(wert)
  41   #if (!(intDsize==16))
  42     #define highD(x)  ((uintD)((uintDD)(x)>>intDsize))
  43   #else
  44     #define highD  high16
  45   #endif
  46
  47 // Low-Digit eines Doppel-Digit bestimmen
  48 // lowD(wert)
  49   #define lowD(x)  ((uintD)(uintDD)(x))
  50
  51 // Ein Doppel-Digit aus ihrem High-Digit und ihrem Low-Digit bestimmen:
  52 // highlowDD(uintD high, uintD low)
  53   #if (!(intDsize==16))
  54     #define highlowDD(x,y)  (((uintDD)(uintD)(x)<<intDsize)|(uintDD)(uintD)(y))
  55   #else
  56     #define highlowDD  highlow32
  57   #endif
  58
  59 // Ein Doppel-Digit aus ihrem High-Digit und ihrem Low-Digit 0 bestimmen:
  60 // highlowDD_0(uintD high)
  61   #if (!(intDsize==16))
  62     #define highlowDD_0(x)  ((uintDD)(uintD)(x)<<intDsize)
  63   #else
  64     #define highlowDD_0  highlow32_0
  65   #endif
  66
  67 #endif
  68
  69 // Zwei Digits multiplizieren:
  70 // (uintDD)hilo = muluD(uintD arg1, uintD arg2)
  71 // bzw.
  72 // muluD(uintD arg1, uintD arg2, uintD hi =, uintD lo =);
  73 #if HAVE_DD
  74   #if (intDsize==8)
  75     #ifdef __GNUC__
  76       #define muluD(arg1,arg2)  ((uintDD)((uintD)(arg1)*(uintD)(arg2)))
  77     #else
  78       #define muluD(arg1,arg2)  ((uintDD)(uintD)(arg1)*(uintDD)(uintD)(arg2))
  79     #endif
  80   #endif
  81   #if (intDsize==16)
  82     #define muluD  mulu16
  83   #endif
  84   #if (intDsize==32) && defined(HAVE_LONGLONG)
  85     #define muluD(arg1,arg2)  ((uintDD)(uintD)(arg1)*(uintDD)(uintD)(arg2))
  86   #endif
  87 #else
  88   #if (intDsize==32)
  89     #define muluD  mulu32
  90   #endif
  91   #if (intDsize==64)
  92     #define muluD  mulu64
  93   #endif
  94 #endif
  95
  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)))
 101   #endif
 102   #if (intDsize==32)
 103     #define muluD_unchecked(arg1,arg2)  mulu32_unchecked(arg1,arg2)
 104   #endif
 105
 106 // Durch ein Digit dividieren:
 107 // divuD(uintDD x, uintD y, uintD q =, uintD r =);
 108 // bzw.
 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.
 112 #if HAVE_DD
 113   #if (intDsize==8)
 114     #define divuD  divu_1616_1616
 115   #endif
 116   #if (intDsize==16)
 117     #define divuD  divu_3216_1616
 118   #endif
 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; \
 125       }
 126   #endif
 127 #else
 128   #if (intDsize==32)
 129     #define divuD  divu_6432_3232
 130   #endif
 131   #if (intDsize==64)
 132     #define divuD  divu_12864_6464
 133   #endif
 134 #endif
 135
 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)))
 142   #endif
 143   #if (intDsize==32)
 144     #define floorD  divu_3232_3232_
 145   #endif
 146
 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
 153 #if (intDsize==8)
 154   #define isqrtD(xhi,xlo,y_zuweisung,sqrtp_zuweisung)  \
 155     { var uint32 _z;                                                            \
 156       isqrt_32_16((((uint32)xhi<<8) | (uint32)xlo) << 16, _z=,sqrtp_zuweisung); \
 157       y_zuweisung (_z >> 8);                                                    \
 158     }
 159 #endif
 160 #if (intDsize==16)
 161   #define isqrtD(xhi,xlo,y_zuweisung,sqrtp_zuweisung)  \
 162     isqrt_32_16(highlow32(xhi,xlo),y_zuweisung,sqrtp_zuweisung)
 163 #endif
 164 #if (intDsize==32)
 165   #define isqrtD  isqrt_64_32
 166 #endif
 167 #if (intDsize==64)
 168   #define isqrtD  isqrt_128_64
 169 #endif
 170
 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
 176 #if (intDsize==8)
 177   #define integerlengthD  integerlength8
 178 #endif
 179 #if (intDsize==16)
 180   #define integerlengthD  integerlength16
 181 #endif
 182 #if (intDsize==32)
 183   #define integerlengthD  integerlength32
 184 #endif
 185 #if (intDsize==64)
 186   #define integerlengthD  integerlength64
 187 #endif
 188
 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)
 197   #else
 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 + )    \
 203       }
 204   #endif
 205
 206 // Bits eines Wortes zählen.
 207 // logcountD(x)
 208 // > x: ein uintD
 209 // < ergebnis: Anzahl der darin gesetzten Bits
 210 #if (intDsize==8)
 211   inline uint8 logcountD (uint8 x8) { logcount_8(); return x8; }
 212 #endif
 213 #if (intDsize==16)
 214   inline uint16 logcountD (uint16 x16) { logcount_16(); return x16; }
 215 #endif
 216 #if (intDsize==32)
 217   inline uint32 logcountD (uint32 x32) { logcount_32(); return x32; }
 218 #endif
 219 #if (intDsize==64)
 220   inline uint64 logcountD (uint64 x64) { logcount_64(); return x64; }
 221 #endif
 222
 223 #endif /* _CL_D_H */