src/base/digit/cl_D.h

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