src/integer/cl_I.h

   1 // cl_I internals
   2
   3 #ifndef _CL_I_H
   4 #define _CL_I_H
   5
   6 #include "cln/number.h"
   7 #include "cln/integer.h"
   8 #include "cl_macros.h"
   9 #include "cln/malloc.h"
  10 #include "cln/abort.h"
  11 #include "cl_offsetof.h"
  12 #include "cl_DS.h"
  13
  14 namespace cln {
  15
  16 // maximal needed length of a digit sequence for a fixnum
  17   #define FN_maxlength  ceiling(cl_value_len,intDsize)
  18 // maximal needed length (without sign) of a digit sequence for a fixnum
  19   #define pFN_maxlength  ceiling(cl_value_len-1,intDsize)
  20 // minimum length of a digit sequence for a bignum
  21   #define bn_minlength  ceiling((cl_value_len+1),intDsize)
  22   // Because bignums with n < ceiling((cl_value_len+1)/intDsize) digits are
  23   // integers with at most n*intDsize < cl_value_len+1 bits, so they fit into
  24   // a fixnum, including the sign bit.
  25   // 1 <= bn_minlength <= 5.
  26 // We have pFN_maxlength <= FN_maxlength <= bn_minlength.
  27
  28 // Private fixnum constructor.
  29 inline cl_I::cl_I (struct cl_fixnum * null, cl_uint w)
  30         : cl_RA ((cl_private_thing) w) { unused null; }
  31 inline const cl_I cl_I_from_word (cl_uint w)
  32 {
  33         return cl_I((struct cl_fixnum *) 0, w);
  34 }
  35
  36 inline cl_uint cl_FN_word (const cl_I& x)
  37 {
  38         return x.word;
  39 }
  40
  41
  42 // Bignums.
  43
  44 struct cl_heap_bignum : cl_heap {
  45         unsigned int length;    // length (in digits)
  46         uintD data[1];          // number in two's complement representation
  47 };
  48
  49 inline cl_heap_bignum* TheBignum (cl_heap_bignum* p)
  50         { return p; }
  51 inline cl_heap_bignum* TheBignum (const cl_number& obj)
  52         { return (cl_heap_bignum*)(obj.pointer); }
  53
  54 inline cl_heap_bignum* allocate_bignum (unsigned int length)
  55 {
  56         cl_heap_bignum* p = (cl_heap_bignum*) malloc_hook(offsetofa(cl_heap_bignum,data)+sizeof(uintD)*length);
  57         p->refcount = 1;
  58         p->type = &cl_class_bignum;
  59         p->length = length;
  60         return p;
  61 }
  62
  63 // Private constructor.
  64 // ptr should be the result of some allocate_bignum() call.
  65 inline cl_I::cl_I (cl_heap_bignum* ptr)
  66         : cl_RA ((cl_private_thing) ptr) {}
  67
  68 // Both work, but the first definition results in less compiler-generated
  69 // temporaries.
  70 #if 1
  71   #define Bignum  cl_heap_bignum*
  72 #else
  73   #define Bignum  cl_I
  74 #endif
  75
  76
  77 // Integers in general.
  78
  79 // Type tests.
  80 inline cl_boolean integerp (const cl_I& x)
  81         { unused x; return cl_true; }
  82 inline cl_boolean fixnump (const cl_I& x)
  83         { return (cl_boolean) !x.pointer_p(); }
  84 inline cl_boolean bignump (const cl_I& x)
  85         { return x.pointer_p(); }
  86
  87 // Sign test:
  88
  89 // (MINUSP x) == (< x 0)
  90 inline cl_boolean minusp (const cl_I& x)
  91 {
  92         if (fixnump(x))
  93                 // This assumes cl_value_shift + cl_value_len == cl_pointer_size.
  94                 return (cl_boolean)((cl_sint) x.word < 0);
  95         else
  96                 return (cl_boolean)((sintD)mspref(arrayMSDptr(TheBignum(x)->data,TheBignum(x)->length),0) < 0);
  97 }
  98
  99 // (ZEROP x) == (= x 0)
 100 inline cl_boolean zerop (const cl_I& x)
 101 {
 102         return (cl_boolean)(x.word == cl_combine(cl_FN_tag,0));
 103 }
 104
 105 // (EQ x y) == (= x y), assuming y a fixnum
 106 inline cl_boolean eq (const cl_I& x, sint32 y)
 107 {
 108         return (cl_boolean)(x.word == cl_combine(cl_FN_tag,y));
 109 }
 110
 111
 112 // Umwandlungsroutinen Integer <--> Longword:
 113
 114 // Wandelt Fixnum >=0 in Unsigned Longword um.
 115 // FN_to_UL(obj)
 116 // > obj: ein Fixnum >=0
 117 // < ergebnis: der Wert des Fixnum als 32-Bit-Zahl.
 118 inline uint32 FN_to_UL (const cl_I& x)
 119 {
 120         // This assumes cl_value_shift + cl_value_len == cl_pointer_size.
 121         return (cl_uint)(x.word) >> cl_value_shift;
 122 }
 123
 124 // Wandelt Fixnum in Longword um.
 125 // FN_to_L(obj)
 126 // > obj: ein Fixnum
 127 // < ergebnis: der Wert des Fixnum als 32-Bit-Zahl.
 128 inline sint32 FN_to_L (const cl_I& x)
 129 {
 130         // This assumes cl_value_shift + cl_value_len == cl_pointer_size.
 131         return (cl_sint)(x.word) >> cl_value_shift;
 132 }
 133
 134 // FN_L_zerop(x,x_) stellt fest, ob x = 0 ist.
 135 // Dabei ist x ein Fixnum und x_ = FN_to_L(x).
 136   #define FN_L_zerop(x,x_)  (x_==0)
 137
 138 // FN_L_minusp(x,x_) stellt fest, ob x < 0 ist.
 139 // Dabei ist x ein Fixnum und x_ = FN_to_L(x).
 140   #define FN_L_minusp(x,x_)  (x_<0)
 141
 142 #ifdef intQsize
 143
 144 // Wandelt Fixnum in Quadword um.
 145 // FN_to_Q(obj)
 146 // > obj: ein Fixnum
 147 // < ergebnis: der Wert des Fixnum als 64-Bit-Zahl.
 148 inline sint64 FN_to_Q (const cl_I& x)
 149 {
 150         // This assumes cl_value_shift + cl_value_len == cl_pointer_size.
 151         return (cl_sint)(x.word) >> cl_value_shift;
 152 }
 153
 154 // Wandelt Integer >=0 in Unsigned Quadword um.
 155 // cl_I_to_UQ(obj)
 156 // > obj: ein Objekt, sollte ein Integer >=0, <2^64 sein
 157 // < ergebnis: der Wert des Integer als 64-Bit-Zahl.
 158   extern uint64 cl_I_to_UQ (const cl_I& obj);
 159
 160 // Wandelt Integer in Signed Quadword um.
 161 // cl_I_to_Q(obj)
 162 // > obj: ein Objekt, sollte ein Integer >=-2^63, <2^63 sein
 163 // < ergebnis: der Wert des Integer als 64-Bit-Zahl.
 164   extern sint64 cl_I_to_Q (const cl_I& obj);
 165
 166 #endif
 167
 168 // Wandelt Longword in Fixnum um.
 169 // L_to_FN(wert)
 170 // > wert: Wert des Fixnums, ein signed 32-Bit-Integer
 171 //         >= -2^(cl_value_len-1), < 2^(cl_value_len-1)
 172 // < ergebnis: Fixnum mit diesem Wert.
 173   inline const cl_I L_to_FN (sint32 wert)
 174   {
 175         return cl_I_from_word(cl_combine(cl_FN_tag,wert));
 176   }
 177
 178 // Wandelt Longword in Integer um.
 179 // L_to_I(wert)
 180 // > wert: Wert des Integers, ein signed 32-Bit-Integer.
 181 // < ergebnis: Integer mit diesem Wert.
 182 #if (cl_value_len >= 32)
 183   #define L_to_I(wert)  L_to_FN(wert)
 184 #else
 185   extern cl_private_thing cl_I_constructor_from_L (sint32 wert);
 186   inline const cl_I L_to_I (sint32 wert)
 187   {
 188         return cl_I(cl_I_constructor_from_L(wert));
 189   }
 190 #endif
 191
 192 // Wandelt Unsigned Longword in Fixnum >=0 um.
 193 // UL_to_FN(wert)
 194 // > wert: Wert des Integers, ein unsigned 32-Bit-Integer < 2^(cl_value_len-1).
 195 // < ergebnis: Fixnum mit diesem Wert.
 196   inline const cl_I UL_to_FN (uint32 wert)
 197   {
 198         return cl_I_from_word(cl_combine(cl_FN_tag,wert));
 199   }
 200
 201 // Wandelt Unsigned Longword in Integer >=0 um.
 202 // UL_to_I(wert)
 203 // > wert: Wert des Integers, ein unsigned 32-Bit-Integer.
 204 // < ergebnis: Integer mit diesem Wert.
 205 #if (cl_value_len > 32)
 206   #define UL_to_I(wert)  UL_to_FN(wert)
 207 #else
 208   extern cl_private_thing cl_I_constructor_from_UL (uint32 wert);
 209   inline const cl_I UL_to_I (uint32 wert)
 210   {
 211         return cl_I(cl_I_constructor_from_UL(wert));
 212   }
 213 #endif
 214
 215 // Wandelt Doppel-Longword in Integer um.
 216 // L2_to_I(wert_hi,wert_lo)
 217 // > wert_hi|wert_lo: Wert des Integers, ein signed 64-Bit-Integer.
 218 // < ergebnis: Integer mit diesem Wert.
 219   extern cl_private_thing cl_I_constructor_from_L2 (sint32 wert_hi, uint32 wert_lo);
 220   inline const cl_I L2_to_I (sint32 wert_hi, uint32 wert_lo)
 221   {
 222         return cl_I(cl_I_constructor_from_L2(wert_hi,wert_lo));
 223   }
 224
 225 // Wandelt Unsigned Doppel-Longword in Integer um.
 226 // UL2_to_I(wert_hi,wert_lo)
 227 // > wert_hi|wert_lo: Wert des Integers, ein unsigned 64-Bit-Integer.
 228 // < ergebnis: Integer mit diesem Wert.
 229   extern cl_private_thing cl_I_constructor_from_UL2 (uint32 wert_hi, uint32 wert_lo);
 230   inline const cl_I UL2_to_I (uint32 wert_hi, uint32 wert_lo)
 231   {
 232         return cl_I(cl_I_constructor_from_UL2(wert_hi,wert_lo));
 233   }
 234
 235 #ifdef intQsize
 236
 237 // Wandelt Quadword in Integer um.
 238 // Q_to_I(wert)
 239 // > wert: Wert des Integers, ein signed 64-Bit-Integer.
 240 // < ergebnis: Integer mit diesem Wert.
 241   extern cl_private_thing cl_I_constructor_from_Q (sint64 wert);
 242   inline const cl_I Q_to_I (sint64 wert)
 243   {
 244         return cl_I(cl_I_constructor_from_Q(wert));
 245   }
 246
 247 // Wandelt Unsigned Quadword in Integer >=0 um.
 248 // UQ_to_I(wert)
 249 // > wert: Wert des Integers, ein unsigned 64-Bit-Integer.
 250 // < ergebnis: Integer mit diesem Wert.
 251   extern cl_private_thing cl_I_constructor_from_UQ (uint64 wert);
 252   inline const cl_I UQ_to_I (uint64 wert)
 253   {
 254         return cl_I(cl_I_constructor_from_UQ(wert));
 255   }
 256
 257 #endif
 258
 259 // Wandelt uintD in Integer >=0 um.
 260 // UD_to_I(wert)
 261 // > wert: Wert des Integers, ein uintD.
 262 // < ergebnis: Integer mit diesem Wert.
 263 #if (intDsize < cl_value_len)
 264   #define UD_to_I(wert)  UL_to_FN(wert)
 265 #elif (intDsize<=32)
 266   #define UD_to_I(wert)  UL_to_I(wert)
 267 #elif (intDsize==64)
 268   #define UD_to_I(wert)  UQ_to_I(wert)
 269 #endif
 270
 271 // Liefert die Differenz x-y zweier Unsigned Longwords x,y als Integer.
 272 // minus(x,y)
 273 inline const cl_I minus (uintL x, uintL y)
 274 {
 275 #if (cl_word_size==64)
 276         return Q_to_I((sintQ)(uintQ)x - (sintQ)(uintQ)y);
 277 #else
 278         return L2_to_I( (x<y ? -1 : 0), x-y );
 279 #endif
 280 }
 281
 282
 283 // Umwandlungsroutinen Digit sequence <--> Longword:
 284
 285 #if (intDsize<=32)
 286
 287 // Holt die nächsten pFN_maxlength Digits in ein uint32.
 288 inline uint32 pFN_maxlength_digits_at (const uintD* ptr)
 289 {
 290 #if (pFN_maxlength==1)
 291         return (uint32)lspref(ptr,0);
 292 #elif (pFN_maxlength==2)
 293         return ((uint32)lspref(ptr,1)<<intDsize) | (uint32)lspref(ptr,0);
 294 #elif (pFN_maxlength==3)
 295         return ((((uint32)lspref(ptr,2)<<intDsize) | (uint32)lspref(ptr,1))<<intDsize) | (uint32)lspref(ptr,0);
 296 #elif (pFN_maxlength==4)
 297         return ((((((uint32)lspref(ptr,3)<<intDsize) | (uint32)lspref(ptr,2))<<intDsize) | (uint32)lspref(ptr,1))<<intDsize) | (uint32)lspref(ptr,0);
 298 #endif
 299 }
 300
 301 // Schreibt ein uint32 in die nächsten pFN_maxlength Digits.
 302 inline void set_pFN_maxlength_digits_at (uintD* ptr, uint32 wert)
 303 {
 304 #if (pFN_maxlength==1)
 305         lspref(ptr,0) = (uintD)wert;
 306 #elif (pFN_maxlength==2)
 307         lspref(ptr,1) = (uintD)(wert>>intDsize);
 308         lspref(ptr,0) = (uintD)(wert);
 309 #elif (pFN_maxlength==3)
 310         lspref(ptr,2) = (uintD)(wert>>(2*intDsize));
 311         lspref(ptr,1) = (uintD)(wert>>intDsize);
 312         lspref(ptr,0) = (uintD)(wert);
 313 #elif (pFN_maxlength==4)
 314         lspref(ptr,3) = (uintD)(wert>>(3*intDsize));
 315         lspref(ptr,2) = (uintD)(wert>>(2*intDsize));
 316         lspref(ptr,1) = (uintD)(wert>>intDsize);
 317         lspref(ptr,0) = (uintD)(wert);
 318 #endif
 319 }
 320
 321 #elif (intDsize==64)
 322
 323 // Holt die nächsten pFN_maxlength Digits in ein uint64.
 324 inline uint64 pFN_maxlength_digits_at (const uintD* ptr)
 325 {
 326         return (uint64)lspref(ptr,0);
 327 }
 328
 329 #endif
 330
 331
 332 // Umwandlungsroutinen Digit sequence --> Integer:
 333
 334 // Normalized Digit sequence to Integer
 335 // NDS_to_I(MSDptr,len)
 336 // Digit Sequence MSDptr/len/.. in Integer umwandeln.
 337   extern const cl_I NDS_to_I (const uintD* MSDptr, uintC len);
 338
 339 // Normalized Unsigned Digit Sequence to Integer
 340 // NUDS_to_I(MSDptr,len)
 341 // Normalized UDS MSDptr/len/.. in Integer >=0 umwandeln.
 342 // Unterhalb von MSDptr muß 1 Digit Platz sein.
 343   extern const cl_I NUDS_to_I (uintD* MSDptr, uintC len);
 344
 345 // Unsigned Digit Sequence to Integer
 346 // UDS_to_I(MSDptr,len)
 347 // UDS MSDptr/len/.. in Integer >=0 umwandeln.
 348 // Unterhalb von MSDptr muß 1 Digit Platz sein.
 349   extern const cl_I UDS_to_I (uintD* MSDptr, uintC len);
 350
 351 // Digit Sequence to Integer
 352 // DS_to_I(MSDptr,len)
 353 // DS MSDptr/len/.. in Integer umwandeln.
 354   extern const cl_I DS_to_I (const uintD* MSDptr, uintC len);
 355
 356
 357 // Umwandlungsroutinen Integer --> Digit sequence:
 358
 359 // Unterteilung eines Fixnums in Digits:
 360 // intDsize=8 -> MSD=LSD3,LSD2,LSD1,LSD0, sollte FN_maxlength=4 sein.
 361 // intDsize=16 -> MSD=LSD1,LSD0, sollte FN_maxlength=2 sein.
 362 // intDsize=32 -> MSD=LSD0, sollte FN_maxlength=1 sein.
 363
 364 inline sintD FN_MSD (cl_uint word)
 365 {
 366         // This assumes cl_value_shift + cl_value_len == cl_pointer_size.
 367         return (cl_sint)word >> (cl_value_shift + (FN_maxlength-1)*intDsize);
 368 }
 369
 370 #if (FN_maxlength==1)
 371   #define FN_LSD0(word)  FN_MSD(word)
 372   #define FN_LSD1(word)  (cl_abort(), (uintD)0)  // never used
 373   #define FN_LSD2(word)  (cl_abort(), (uintD)0)  // never used
 374   #define FN_LSD3(word)  (cl_abort(), (uintD)0)  // never used
 375 #endif
 376 #if (FN_maxlength==2)
 377   inline uintD FN_LSD0 (cl_uint word)
 378   {
 379         return (uintD)(word >> cl_value_shift);
 380   }
 381   #define FN_LSD1(word)  FN_MSD(word)
 382   #define FN_LSD2(word)  (cl_abort(), (uintD)0)  // never used
 383   #define FN_LSD3(word)  (cl_abort(), (uintD)0)  // never used
 384 #endif
 385 #if (FN_maxlength==4)
 386   inline uintD FN_LSD0 (cl_uint word)
 387   {
 388         return (uintD)(word >> cl_value_shift);
 389   }
 390   inline uintD FN_LSD1 (cl_uint word)
 391   {
 392         return (uintD)(word >> (cl_value_shift + intDsize));
 393   }
 394   inline uintD FN_LSD2 (cl_uint word)
 395   {
 396         return (uintD)(word >> (cl_value_shift + 2*intDsize));
 397   }
 398   #define FN_LSD3(word)  FN_MSD(word)
 399 #endif
 400
 401 // wird nur bei FN_maxlength >= 2 gebraucht, d.h. intDsize < cl_value_len
 402 #define FN_MSD1_mask  (~((cl_uint)(bitc(intDsize-1)-1) << cl_value_shift))
 403 // wird nur bei FN_maxlength >= 3 gebraucht, d.h. 2*intDsize < cl_value_len
 404 #define FN_MSD2_mask  (~((cl_uint)(bitc(2*intDsize-1)-1) << cl_value_shift))
 405 // wird nur bei FN_maxlength >= 4 gebraucht, d.h. 3*intDsize < cl_value_len
 406 #define FN_MSD3_mask  (~((cl_uint)(bitc(3*intDsize-1)-1) << cl_value_shift))
 407
 408 // Store a Fixnum at destLSDptr, <= FN_maxlength digits below destLSDptr needed.
 409 #define FN_to_NDS(destLSDptr, word, MSDptr_zuweisung,len_zuweisung,LSDptr_zuweisung, check_for_0,zero_statement)  \
 410 { var uintC len_from_FN_to_NDS;                                         \
 411   if (check_for_0 && (word == cl_combine(cl_FN_tag,0)))                 \
 412     { len_from_FN_to_NDS = 0; zero_statement }                          \
 413     else                                                                \
 414     { var cl_uint testMSD;                                              \
 415       if ((FN_maxlength<=1) ||                                          \
 416           ((testMSD = (word) & FN_MSD1_mask) == 0) || (testMSD == FN_MSD1_mask) \
 417          )                                                              \
 418         { len_from_FN_to_NDS = 1;                                       \
 419           lspref(destLSDptr,0) = FN_LSD0(word);                         \
 420         }                                                               \
 421       elif ((FN_maxlength<=2) ||                                        \
 422             ((testMSD = (word) & FN_MSD2_mask) == 0) || (testMSD == FN_MSD2_mask) \
 423            )                                                            \
 424         { len_from_FN_to_NDS = 2;                                       \
 425           lspref(destLSDptr,0) = FN_LSD0(word);                         \
 426           lspref(destLSDptr,1) = FN_LSD1(word);                         \
 427         }                                                               \
 428       elif ((FN_maxlength<=3) ||                                        \
 429             ((testMSD = (word) & FN_MSD3_mask) == 0) || (testMSD == FN_MSD3_mask) \
 430            )                                                            \
 431         { len_from_FN_to_NDS = 3;                                       \
 432           lspref(destLSDptr,0) = FN_LSD0(word);                         \
 433           lspref(destLSDptr,1) = FN_LSD1(word);                         \
 434           lspref(destLSDptr,2) = FN_LSD2(word);                         \
 435         }                                                               \
 436       else /* (FN_maxlength<=4) */                                      \
 437         { len_from_FN_to_NDS = 4;                                       \
 438           lspref(destLSDptr,0) = FN_LSD0(word);                         \
 439           lspref(destLSDptr,1) = FN_LSD1(word);                         \
 440           lspref(destLSDptr,2) = FN_LSD2(word);                         \
 441           lspref(destLSDptr,3) = FN_LSD3(word);                         \
 442         }                                                               \
 443     }                                                                   \
 444   unused (MSDptr_zuweisung (destLSDptr) lspop len_from_FN_to_NDS);      \
 445   unused (len_zuweisung len_from_FN_to_NDS);                            \
 446   unused (LSDptr_zuweisung (destLSDptr));                               \
 447 }
 448
 449 // Bignum to Normalized Digit sequence, Kopieren unnötig
 450 // BN_to_NDS_nocopy(obj, MSDptr=,len=,LSDptr=);
 451 // > obj: ein Bignum
 452 // < MSDptr/len/LSDptr: Normalized Digit sequence
 453 #if CL_DS_BIG_ENDIAN_P
 454   #define BN_to_NDS_nocopy(obj, MSDptr_zuweisung,len_zuweisung,LSDptr_zuweisung)  \
 455     { var Bignum bn_from_BN_to_NDS_nocopy = TheBignum(obj);             \
 456       unused (MSDptr_zuweisung (const uintD*) &bn_from_BN_to_NDS_nocopy->data[0]);      \
 457       unused (LSDptr_zuweisung (const uintD*) &bn_from_BN_to_NDS_nocopy->data[(uintP)( len_zuweisung bn_from_BN_to_NDS_nocopy->length )]);              \
 458     }
 459 #else
 460   #define BN_to_NDS_nocopy(obj, MSDptr_zuweisung,len_zuweisung,LSDptr_zuweisung)  \
 461     { var Bignum bn_from_BN_to_NDS_nocopy = TheBignum(obj);             \
 462       unused (LSDptr_zuweisung (const uintD*) &bn_from_BN_to_NDS_nocopy->data[0]);      \
 463       unused (MSDptr_zuweisung (const uintD*) &bn_from_BN_to_NDS_nocopy->data[(uintP)( len_zuweisung bn_from_BN_to_NDS_nocopy->length )]);              \
 464     }
 465 #endif
 466   inline const uintD* BN_MSDptr (const cl_I& obj)
 467     { var Bignum bn = TheBignum(obj); return (const uintD*) arrayMSDptr(bn->data,bn->length); }
 468   inline const uintD* BN_LSDptr (const cl_I& obj)
 469     { var Bignum bn = TheBignum(obj); return (const uintD*) arrayLSDptr(bn->data,bn->length); }
 470
 471 // Bignum to Normalized Digit sequence
 472 // BN_to_NDS(obj, MSDptr=,len=,LSDptr=);
 473 // > obj: ein Bignum
 474 // < MSDptr/len/LSDptr: Normalized Digit sequence, darf modifiziert werden.
 475 // Dabei wird num_stack erniedrigt.
 476   #define BN_to_NDS(obj, MSDptr_zuweisung,len_zuweisung,LSDptr_zuweisung)  \
 477     { var const cl_I& obj_from_BN_to_NDS = (obj);                       \
 478       var uintD* MSDptr_from_BN_to_NDS;                                 \
 479       var uintC len_from_BN_to_NDS;                                     \
 480       len_zuweisung len_from_BN_to_NDS = TheBignum(obj_from_BN_to_NDS)->length; \
 481       num_stack_alloc(len_from_BN_to_NDS, MSDptr_zuweisung MSDptr_from_BN_to_NDS = , LSDptr_zuweisung); \
 482       copy_loop_msp(BN_MSDptr(obj_from_BN_to_NDS),MSDptr_from_BN_to_NDS,len_from_BN_to_NDS); \
 483     }
 484
 485 // Bignum to Normalized Digit sequence
 486 // BN_to_NDS_1(obj, MSDptr=,len=,LSDptr=);
 487 // > obj: ein Bignum
 488 // < MSDptr/len/LSDptr: Normalized Digit sequence, darf modifiziert werden.
 489 // Unterhalb von MSDptr ist noch 1 Digit Platz.
 490 // Dabei wird num_stack erniedrigt.
 491   #define BN_to_NDS_1(obj, MSDptr_zuweisung,len_zuweisung,LSDptr_zuweisung)  \
 492     { var const cl_I& obj_from_BN_to_NDS = (obj);                       \
 493       var uintD* MSDptr_from_BN_to_NDS;                                 \
 494       var uintC len_from_BN_to_NDS;                                     \
 495       len_zuweisung len_from_BN_to_NDS = TheBignum(obj_from_BN_to_NDS)->length; \
 496       num_stack_alloc_1(len_from_BN_to_NDS, MSDptr_zuweisung MSDptr_from_BN_to_NDS = , LSDptr_zuweisung); \
 497       copy_loop_msp(BN_MSDptr(obj_from_BN_to_NDS),MSDptr_from_BN_to_NDS,len_from_BN_to_NDS); \
 498     }
 499
 500 // Integer to Normalized Digit sequence, Kopieren unnötig.
 501 // I_to_NDS_nocopy(obj, MSDptr=,len=,LSDptr=,check_for_0,zero_statement);
 502 // > obj: ein Integer
 503 // > check_for_0: ob obj möglicherweise =0 sein kann
 504 // > zero_statement: wird bei obj=0 ausgeführt
 505 // < MSDptr/len/LSDptr: Normalized Digit sequence
 506   #define I_to_NDS_nocopy(obj, MSDptr_zuweisung,len_zuweisung,LSDptr_zuweisung, check_for_0,zero_statement)  \
 507     var uintD CONCAT(FN_store_,__LINE__) [FN_maxlength];                \
 508     { var const cl_I& obj_from_I_to_NDS_nocopy = (obj);                 \
 509       if (fixnump(obj_from_I_to_NDS_nocopy))                            \
 510         { FN_to_NDS(arrayLSDptr(CONCAT(FN_store_,__LINE__),FN_maxlength), cl_FN_word(obj_from_I_to_NDS_nocopy), MSDptr_zuweisung,len_zuweisung,LSDptr_zuweisung, check_for_0,zero_statement); } \
 511         else                                                            \
 512         { BN_to_NDS_nocopy(obj_from_I_to_NDS_nocopy,MSDptr_zuweisung,len_zuweisung, LSDptr_zuweisung); } \
 513     }
 514
 515 // Integer to Normalized Digit sequence
 516 // I_to_NDS(obj, MSDptr=,len=,LSDptr=);
 517 // > obj: ein Integer
 518 // < MSDptr/len/LSDptr: Normalized Digit sequence, darf modifiziert werden.
 519 // Dabei wird num_stack erniedrigt.
 520   #define I_to_NDS(obj, MSDptr_zuweisung,len_zuweisung,LSDptr_zuweisung)  \
 521     var uintD CONCAT(FN_store_,__LINE__) [FN_maxlength];                \
 522     { var const cl_I& obj_from_I_to_NDS = (obj);                        \
 523       if (fixnump(obj_from_I_to_NDS))                                   \
 524         { FN_to_NDS(arrayLSDptr(CONCAT(FN_store_,__LINE__),FN_maxlength), cl_FN_word(obj_from_I_to_NDS), MSDptr_zuweisung,len_zuweisung,LSDptr_zuweisung, cl_true,); } \
 525         else                                                              \
 526         { BN_to_NDS(obj_from_I_to_NDS,MSDptr_zuweisung,len_zuweisung, LSDptr_zuweisung); } \
 527     }
 528
 529 // Integer to Normalized Digit sequence
 530 // I_to_NDS_1(obj, MSDptr=,len=,LSDptr=);
 531 // > obj: ein Integer
 532 // < MSDptr/len/LSDptr: Normalized Digit sequence, darf modifiziert werden.
 533 // Unterhalb von MSDptr ist noch 1 Digit Platz.
 534 // Dabei wird num_stack erniedrigt.
 535   #define I_to_NDS_1(obj, MSDptr_zuweisung,len_zuweisung,LSDptr_zuweisung)  \
 536     var uintD CONCAT(FN_store_,__LINE__) [1+FN_maxlength];              \
 537     { var const cl_I& obj_from_I_to_NDS = (obj);                        \
 538       if (fixnump(obj_from_I_to_NDS))                                   \
 539         { FN_to_NDS(arrayLSDptr(CONCAT(FN_store_,__LINE__),1+FN_maxlength), cl_FN_word(obj_from_I_to_NDS), MSDptr_zuweisung,len_zuweisung,LSDptr_zuweisung, cl_true,); } \
 540         else                                                              \
 541         { BN_to_NDS_1(obj_from_I_to_NDS,MSDptr_zuweisung,len_zuweisung, LSDptr_zuweisung); } \
 542     }
 543
 544
 545 // Division ganzer Zahlen
 546
 547 // Dividiert zwei Integers x,y >=0 und liefert Quotient und Rest
 548 // der Division x/y. Bei y=0 Error.
 549 // cl_divide(x,y)
 550 // > x,y: Integers >=0
 551 // < q,r: Quotient q, Rest r
 552   extern const cl_I_div_t cl_divide (const cl_I& x, const cl_I& y);
 553
 554 // Fehler, wenn Quotient keine ganze Zahl ist
 555   nonreturning_function(extern, cl_error_exquo, (const cl_I& x, const cl_I& y));
 556
 557
 558 // ggT und kgV von Integers
 559
 560   // Teilfunktion für die Durchführung des Euklid-Algorithmus auf
 561   // den führenden Ziffern a' und b':
 562   // partial_gcd(a',b',&erg); mit a'>b'
 563   // liefert in erg: x1,y1,x2,y2 mit den in cl_I_gcd.cc angegebenen Invarianten.
 564   typedef struct { uintD x1,y1,x2,y2; } partial_gcd_result;
 565   extern void partial_gcd (uintD z1, uintD z2, partial_gcd_result* erg);
 566   #if HAVE_DD
 567     extern void partial_gcd (uintDD z1, uintDD z2, partial_gcd_result* erg);
 568   #else
 569     extern void partial_gcd (uintD z1hi, uintD z1lo, uintD z2hi, uintD z2lo, partial_gcd_result* erg);
 570   #endif
 571
 572
 573 // Wurzel aus ganzen Zahlen
 574
 575 // Stellt fest, ob ein Integer >=0 eine n-te Potenz ist.
 576 // cl_rootp_aux(x,n,&w)
 577 // > x: ein Integer >=0
 578 // > n: ein Integer >0
 579 // > Annahme: x > 1 und n < (integer-length x).
 580 // < w: Integer (expt x (/ n)) falls x eine n-te Potenz
 581 // < ergebnis: cl_true         ........................, cl_false sonst
 582   extern cl_boolean cl_rootp_aux (cl_I x, uintL n, cl_I* w);
 583
 584
 585 // Hilfsfunktion zur Eingabe von Integers
 586
 587 // Wandelt eine Ziffernfolge in ein Integer >=0 um.
 588 // digits_to_I(MSBptr,len,base)
 589 // > base: Stellenwertsystem-Basis, >=2, <=36
 590 // > MSBptr/len/..: Ziffernfolge, bestehend aus Punkten (werden überlesen)
 591 //     und Ziffern/Buchstaben mit Wert < base.
 592 // < ergebnis: der dargestellte Integer >=0
 593   extern const cl_I digits_to_I (const char * MSBptr, uintL len, uintD base);
 594
 595
 596 // Hilfsfunktion zur Ausgabe von Integers
 597
 598 // cl_digits_need(len,base) liefert eine obere Abschätzung für die Anzahl der
 599 // Ziffern im Stellenwertsystem der Basis base, die x >= 0 braucht.
 600   extern uintL cl_digits_need (const cl_I& x, uintL base);
 601
 602 // Wandelt ein Integer in ein Stellensystem um.
 603 // I_to_digits(x,base, &ergebnis);
 604 // > x: ein Integer >=0
 605 // > base: Stellensystem-Basis, 2 <= base <= 36.
 606 // > ergebnis.LSBptr: darunter ist mindestens digits_need(len) Bytes Platz
 607 // < ergebnis: fertige Folge MSBptr/len/LSBptr von Ziffern
 608   typedef struct { uintB* MSBptr; uintL len; uintB* LSBptr; } cl_digits;
 609   extern void I_to_digits (const cl_I& x, uintD base, cl_digits* erg);
 610
 611
 612 // Hash code.
 613   extern unsigned long hashcode (const cl_I& x);
 614
 615
 616 // A fixnum (cl_FN) is an immediate integer.
 617
 618 // typedef
 619 class cl_FN : public cl_I {
 620 public:
 621 // Optimization of method pointer_p().
 622         cl_boolean pointer_p() const
 623                 { return cl_false; }
 624 };
 625
 626 inline cl_boolean fixnump (const cl_FN& x)
 627         { unused x; return cl_true; }
 628 inline cl_boolean bignump (const cl_FN& x)
 629         { unused x; return cl_false; }
 630
 631 inline cl_boolean minusp (const cl_FN& x)
 632 {
 633         // This assumes cl_value_shift + cl_value_len == cl_pointer_size.
 634         return (cl_boolean)((cl_sint) x.word < 0);
 635 }
 636
 637
 638 // A bignum (cl_BN) is a heap-allocated integer.
 639
 640 // typedef
 641 class cl_BN : public cl_I {
 642 public:
 643 // Optimization of method pointer_p().
 644         cl_boolean pointer_p() const
 645                 { return cl_true; }
 646 };
 647
 648 inline cl_boolean fixnump (const cl_BN& x)
 649         { unused x; return cl_false; }
 650 inline cl_boolean bignump (const cl_BN& x)
 651         { unused x; return cl_true; }
 652
 653 inline cl_boolean minusp (const cl_BN& x)
 654 {
 655         return (cl_boolean)((sintD)mspref(arrayMSDptr(TheBignum(x)->data,TheBignum(x)->length),0) < 0);
 656 }
 657 inline cl_boolean zerop (const cl_BN& x)
 658         { unused x; return cl_false; }
 659
 660 }  // namespace cln
 661
 662 #endif /* _CL_I_H */