src/integer/cl_I.h

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