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         uintC 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 (uintC 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_UV(obj)
 116 // > obj: ein Fixnum >=0
 117 // < ergebnis: der Wert des Fixnum als intVsize-Bit-Zahl.
 118 inline uintV FN_to_UV (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_V(obj)
 126 // > obj: ein Fixnum
 127 // < ergebnis: der Wert des Fixnum als intVsize-Bit-Zahl.
 128 inline sintV FN_to_V (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_V_zerop(x,x_) stellt fest, ob x = 0 ist.
 135 // Dabei ist x ein Fixnum und x_ = FN_to_V(x).
 136   #define FN_V_zerop(x,x_)  (x_==0)
 137
 138 // FN_V_minusp(x,x_) stellt fest, ob x < 0 ist.
 139 // Dabei ist x ein Fixnum und x_ = FN_to_V(x).
 140   #define FN_V_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 #ifdef intQsize
 216
 217 // Wandelt Quadword in Integer um.
 218 // Q_to_I(wert)
 219 // > wert: Wert des Integers, ein signed 64-Bit-Integer.
 220 // < ergebnis: Integer mit diesem Wert.
 221   extern cl_private_thing cl_I_constructor_from_Q (sint64 wert);
 222   inline const cl_I Q_to_I (sint64 wert)
 223   {
 224         return cl_I(cl_I_constructor_from_Q(wert));
 225   }
 226
 227 // Wandelt Unsigned Quadword in Integer >=0 um.
 228 // UQ_to_I(wert)
 229 // > wert: Wert des Integers, ein unsigned 64-Bit-Integer.
 230 // < ergebnis: Integer mit diesem Wert.
 231   extern cl_private_thing cl_I_constructor_from_UQ (uint64 wert);
 232   inline const cl_I UQ_to_I (uint64 wert)
 233   {
 234         return cl_I(cl_I_constructor_from_UQ(wert));
 235   }
 236
 237 #endif
 238
 239 // Wandelt Doppel-Longword in Integer um.
 240 // L2_to_I(wert_hi,wert_lo)
 241 // > wert_hi|wert_lo: Wert des Integers, ein signed 64-Bit-Integer.
 242 // < ergebnis: Integer mit diesem Wert.
 243 #if (cl_word_size==64)
 244   inline cl_private_thing cl_I_constructor_from_L2 (sint32 wert_hi, uint32 wert_lo)
 245   {
 246         return cl_I_constructor_from_Q(((sint64)wert_hi<<32) | (sint64)wert_lo);
 247   }
 248 #else
 249   extern cl_private_thing cl_I_constructor_from_L2 (sint32 wert_hi, uint32 wert_lo);
 250 #endif
 251   inline const cl_I L2_to_I (sint32 wert_hi, uint32 wert_lo)
 252   {
 253         return cl_I(cl_I_constructor_from_L2(wert_hi,wert_lo));
 254   }
 255
 256 // Wandelt Unsigned Doppel-Longword in Integer um.
 257 // UL2_to_I(wert_hi,wert_lo)
 258 // > wert_hi|wert_lo: Wert des Integers, ein unsigned 64-Bit-Integer.
 259 // < ergebnis: Integer mit diesem Wert.
 260 #if (cl_word_size==64)
 261   inline cl_private_thing cl_I_constructor_from_UL2 (uint32 wert_hi, uint32 wert_lo)
 262   {
 263         return cl_I_constructor_from_UQ(((uint64)wert_hi<<32) | (uint64)wert_lo);
 264   }
 265 #else
 266   extern cl_private_thing cl_I_constructor_from_UL2 (uint32 wert_hi, uint32 wert_lo);
 267 #endif
 268   inline const cl_I UL2_to_I (uint32 wert_hi, uint32 wert_lo)
 269   {
 270         return cl_I(cl_I_constructor_from_UL2(wert_hi,wert_lo));
 271   }
 272
 273 // Wandelt sintV in Integer um.
 274 // V_to_I(wert)
 275 // > wert: Wert des Integers, ein sintV.
 276 // < ergebnis: Integer mit diesem Wert.
 277 #if (intVsize<=32)
 278   #define V_to_I(wert)  L_to_I(wert)
 279 #else
 280   #define V_to_I(wert)  Q_to_I(wert)
 281 #endif
 282
 283 // Wandelt uintV in Integer >=0 um.
 284 // UV_to_I(wert)
 285 // > wert: Wert des Integers, ein uintV.
 286 // < ergebnis: Integer mit diesem Wert.
 287 #if (intVsize<=32)
 288   #define UV_to_I(wert)  UL_to_I(wert)
 289 #else
 290   #define UV_to_I(wert)  UQ_to_I(wert)
 291 #endif
 292
 293 // Wandelt uintD in Integer >=0 um.
 294 // UD_to_I(wert)
 295 // > wert: Wert des Integers, ein uintD.
 296 // < ergebnis: Integer mit diesem Wert.
 297 #if (intDsize < cl_value_len)
 298   #define UD_to_I(wert)  UL_to_FN(wert)
 299 #elif (intDsize<=32)
 300   #define UD_to_I(wert)  UL_to_I(wert)
 301 #elif (intDsize==64)
 302   #define UD_to_I(wert)  UQ_to_I(wert)
 303 #endif
 304
 305 // Liefert die Differenz x-y zweier Unsigned Longwords x,y als Integer.
 306 // minus(x,y)
 307 inline const cl_I minus (uintL x, uintL y)
 308 {
 309 #if (cl_word_size==64)
 310         return Q_to_I((sintQ)(uintQ)x - (sintQ)(uintQ)y);
 311 #else
 312         return L2_to_I( (x<y ? -1 : 0), x-y );
 313 #endif
 314 }
 315
 316
 317 // Umwandlungsroutinen Digit sequence <--> Longword:
 318
 319 #if (intDsize<=32)
 320
 321 // Holt die nächsten pFN_maxlength Digits in ein uintV.
 322 inline uintV pFN_maxlength_digits_at (const uintD* ptr)
 323 {
 324 #if (pFN_maxlength==1)
 325         return (uintV)lspref(ptr,0);
 326 #elif (pFN_maxlength==2)
 327         return ((uintV)lspref(ptr,1)<<intDsize) | (uintV)lspref(ptr,0);
 328 #elif (pFN_maxlength==3)
 329         return ((((uintV)lspref(ptr,2)<<intDsize) | (uintV)lspref(ptr,1))<<intDsize) | (uintV)lspref(ptr,0);
 330 #elif (pFN_maxlength==4)
 331         return ((((((uintV)lspref(ptr,3)<<intDsize) | (uintV)lspref(ptr,2))<<intDsize) | (uintV)lspref(ptr,1))<<intDsize) | (uintV)lspref(ptr,0);
 332 #elif (pFN_maxlength==5)
 333         return ((((((((uintV)lspref(ptr,4)<<intDsize) | (uintV)lspref(ptr,3))<<intDsize) | (uintV)lspref(ptr,2))<<intDsize) | (uintV)lspref(ptr,1))<<intDsize) | (uintV)lspref(ptr,0);
 334 #elif (pFN_maxlength==6)
 335         return ((((((((((uintV)lspref(ptr,5)<<intDsize) | (uintV)lspref(ptr,4))<<intDsize) | (uintV)lspref(ptr,3))<<intDsize) | (uintV)lspref(ptr,2))<<intDsize) | (uintV)lspref(ptr,1))<<intDsize) | (uintV)lspref(ptr,0);
 336 #elif (pFN_maxlength==7)
 337         return ((((((((((((uintV)lspref(ptr,6)<<intDsize) | (uintV)lspref(ptr,5))<<intDsize) | (uintV)lspref(ptr,4))<<intDsize) | (uintV)lspref(ptr,3))<<intDsize) | (uintV)lspref(ptr,2))<<intDsize) | (uintV)lspref(ptr,1))<<intDsize) | (uintV)lspref(ptr,0);
 338 #elif (pFN_maxlength==8)
 339         return ((((((((((((((uintV)lspref(ptr,7)<<intDsize) | (uintV)lspref(ptr,6))<<intDsize) | (uintV)lspref(ptr,5))<<intDsize) | (uintV)lspref(ptr,4))<<intDsize) | (uintV)lspref(ptr,3))<<intDsize) | (uintV)lspref(ptr,2))<<intDsize) | (uintV)lspref(ptr,1))<<intDsize) | (uintV)lspref(ptr,0);
 340 #endif
 341 }
 342
 343 // Schreibt ein uintV in die nächsten pFN_maxlength Digits.
 344 inline void set_pFN_maxlength_digits_at (uintD* ptr, uintV wert)
 345 {
 346 #if (pFN_maxlength==1)
 347         lspref(ptr,0) = (uintD)wert;
 348 #elif (pFN_maxlength==2)
 349         lspref(ptr,1) = (uintD)(wert>>intDsize);
 350         lspref(ptr,0) = (uintD)(wert);
 351 #elif (pFN_maxlength==3)
 352         lspref(ptr,2) = (uintD)(wert>>(2*intDsize));
 353         lspref(ptr,1) = (uintD)(wert>>intDsize);
 354         lspref(ptr,0) = (uintD)(wert);
 355 #elif (pFN_maxlength==4)
 356         lspref(ptr,3) = (uintD)(wert>>(3*intDsize));
 357         lspref(ptr,2) = (uintD)(wert>>(2*intDsize));
 358         lspref(ptr,1) = (uintD)(wert>>intDsize);
 359         lspref(ptr,0) = (uintD)(wert);
 360 #elif (pFN_maxlength==5)
 361         lspref(ptr,4) = (uintD)(wert>>(4*intDsize));
 362         lspref(ptr,3) = (uintD)(wert>>(3*intDsize));
 363         lspref(ptr,2) = (uintD)(wert>>(2*intDsize));
 364         lspref(ptr,1) = (uintD)(wert>>intDsize);
 365         lspref(ptr,0) = (uintD)(wert);
 366 #elif (pFN_maxlength==6)
 367         lspref(ptr,5) = (uintD)(wert>>(5*intDsize));
 368         lspref(ptr,4) = (uintD)(wert>>(4*intDsize));
 369         lspref(ptr,3) = (uintD)(wert>>(3*intDsize));
 370         lspref(ptr,2) = (uintD)(wert>>(2*intDsize));
 371         lspref(ptr,1) = (uintD)(wert>>intDsize);
 372         lspref(ptr,0) = (uintD)(wert);
 373 #elif (pFN_maxlength==7)
 374         lspref(ptr,6) = (uintD)(wert>>(6*intDsize));
 375         lspref(ptr,5) = (uintD)(wert>>(5*intDsize));
 376         lspref(ptr,4) = (uintD)(wert>>(4*intDsize));
 377         lspref(ptr,3) = (uintD)(wert>>(3*intDsize));
 378         lspref(ptr,2) = (uintD)(wert>>(2*intDsize));
 379         lspref(ptr,1) = (uintD)(wert>>intDsize);
 380         lspref(ptr,0) = (uintD)(wert);
 381 #elif (pFN_maxlength==8)
 382         lspref(ptr,7) = (uintD)(wert>>(7*intDsize));
 383         lspref(ptr,6) = (uintD)(wert>>(6*intDsize));
 384         lspref(ptr,5) = (uintD)(wert>>(5*intDsize));
 385         lspref(ptr,4) = (uintD)(wert>>(4*intDsize));
 386         lspref(ptr,3) = (uintD)(wert>>(3*intDsize));
 387         lspref(ptr,2) = (uintD)(wert>>(2*intDsize));
 388         lspref(ptr,1) = (uintD)(wert>>intDsize);
 389         lspref(ptr,0) = (uintD)(wert);
 390 #endif
 391 }
 392
 393 #elif (intDsize==64)
 394
 395 // Holt die nächsten pFN_maxlength Digits in ein uint64.
 396 inline uint64 pFN_maxlength_digits_at (const uintD* ptr)
 397 {
 398         return (uint64)lspref(ptr,0);
 399 }
 400
 401 #endif
 402
 403
 404 // Umwandlungsroutinen Digit sequence --> Integer:
 405
 406 // Normalized Digit sequence to Integer
 407 // NDS_to_I(MSDptr,len)
 408 // Digit Sequence MSDptr/len/.. in Integer umwandeln.
 409   extern const cl_I NDS_to_I (const uintD* MSDptr, uintC len);
 410
 411 // Normalized Unsigned Digit Sequence to Integer
 412 // NUDS_to_I(MSDptr,len)
 413 // Normalized UDS MSDptr/len/.. in Integer >=0 umwandeln.
 414 // Unterhalb von MSDptr muß 1 Digit Platz sein.
 415   extern const cl_I NUDS_to_I (uintD* MSDptr, uintC len);
 416
 417 // Unsigned Digit Sequence to Integer
 418 // UDS_to_I(MSDptr,len)
 419 // UDS MSDptr/len/.. in Integer >=0 umwandeln.
 420 // Unterhalb von MSDptr muß 1 Digit Platz sein.
 421   extern const cl_I UDS_to_I (uintD* MSDptr, uintC len);
 422
 423 // Digit Sequence to Integer
 424 // DS_to_I(MSDptr,len)
 425 // DS MSDptr/len/.. in Integer umwandeln.
 426   extern const cl_I DS_to_I (const uintD* MSDptr, uintC len);
 427
 428
 429 // Umwandlungsroutinen Integer --> Digit sequence:
 430
 431 // Unterteilung eines Fixnums in Digits:
 432 // intDsize=8 -> MSD=LSD3,LSD2,LSD1,LSD0, sollte FN_maxlength=4 sein.
 433 // intDsize=16 -> MSD=LSD1,LSD0, sollte FN_maxlength=2 sein.
 434 // intDsize=32 -> MSD=LSD0, sollte FN_maxlength=1 sein.
 435
 436 inline sintD FN_MSD (cl_uint word)
 437 {
 438         // This assumes cl_value_shift + cl_value_len == cl_pointer_size.
 439         return (cl_sint)word >> (cl_value_shift + (FN_maxlength-1)*intDsize);
 440 }
 441
 442 #if (FN_maxlength==1)
 443   #define FN_LSD0(word)  FN_MSD(word)
 444   #define FN_LSD1(word)  (cl_abort(), (uintD)0)  // never used
 445   #define FN_LSD2(word)  (cl_abort(), (uintD)0)  // never used
 446   #define FN_LSD3(word)  (cl_abort(), (uintD)0)  // never used
 447 #endif
 448 #if (FN_maxlength==2)
 449   inline uintD FN_LSD0 (cl_uint word)
 450   {
 451         return (uintD)(word >> cl_value_shift);
 452   }
 453   #define FN_LSD1(word)  FN_MSD(word)
 454   #define FN_LSD2(word)  (cl_abort(), (uintD)0)  // never used
 455   #define FN_LSD3(word)  (cl_abort(), (uintD)0)  // never used
 456 #endif
 457 #if (FN_maxlength==4)
 458   inline uintD FN_LSD0 (cl_uint word)
 459   {
 460         return (uintD)(word >> cl_value_shift);
 461   }
 462   inline uintD FN_LSD1 (cl_uint word)
 463   {
 464         return (uintD)(word >> (cl_value_shift + intDsize));
 465   }
 466   inline uintD FN_LSD2 (cl_uint word)
 467   {
 468         return (uintD)(word >> (cl_value_shift + 2*intDsize));
 469   }
 470   #define FN_LSD3(word)  FN_MSD(word)
 471 #endif
 472
 473 // wird nur bei FN_maxlength >= 2 gebraucht, d.h. intDsize < cl_value_len
 474 #define FN_MSD1_mask  (~((cl_uint)(bitc(intDsize-1)-1) << cl_value_shift))
 475 // wird nur bei FN_maxlength >= 3 gebraucht, d.h. 2*intDsize < cl_value_len
 476 #define FN_MSD2_mask  (~((cl_uint)(bitc(2*intDsize-1)-1) << cl_value_shift))
 477 // wird nur bei FN_maxlength >= 4 gebraucht, d.h. 3*intDsize < cl_value_len
 478 #define FN_MSD3_mask  (~((cl_uint)(bitc(3*intDsize-1)-1) << cl_value_shift))
 479
 480 // Store a Fixnum at destLSDptr, <= FN_maxlength digits below destLSDptr needed.
 481 #define FN_to_NDS(destLSDptr, word, MSDptr_zuweisung,len_zuweisung,LSDptr_zuweisung, check_for_0,zero_statement)  \
 482 { var uintC len_from_FN_to_NDS;                                         \
 483   if (check_for_0 && (word == cl_combine(cl_FN_tag,0)))                 \
 484     { len_from_FN_to_NDS = 0; zero_statement }                          \
 485     else                                                                \
 486     { var cl_uint testMSD;                                              \
 487       if ((FN_maxlength<=1) ||                                          \
 488           ((testMSD = (word) & FN_MSD1_mask) == 0) || (testMSD == FN_MSD1_mask) \
 489          )                                                              \
 490         { len_from_FN_to_NDS = 1;                                       \
 491           lspref(destLSDptr,0) = FN_LSD0(word);                         \
 492         }                                                               \
 493       elif ((FN_maxlength<=2) ||                                        \
 494             ((testMSD = (word) & FN_MSD2_mask) == 0) || (testMSD == FN_MSD2_mask) \
 495            )                                                            \
 496         { len_from_FN_to_NDS = 2;                                       \
 497           lspref(destLSDptr,0) = FN_LSD0(word);                         \
 498           lspref(destLSDptr,1) = FN_LSD1(word);                         \
 499         }                                                               \
 500       elif ((FN_maxlength<=3) ||                                        \
 501             ((testMSD = (word) & FN_MSD3_mask) == 0) || (testMSD == FN_MSD3_mask) \
 502            )                                                            \
 503         { len_from_FN_to_NDS = 3;                                       \
 504           lspref(destLSDptr,0) = FN_LSD0(word);                         \
 505           lspref(destLSDptr,1) = FN_LSD1(word);                         \
 506           lspref(destLSDptr,2) = FN_LSD2(word);                         \
 507         }                                                               \
 508       else /* (FN_maxlength<=4) */                                      \
 509         { len_from_FN_to_NDS = 4;                                       \
 510           lspref(destLSDptr,0) = FN_LSD0(word);                         \
 511           lspref(destLSDptr,1) = FN_LSD1(word);                         \
 512           lspref(destLSDptr,2) = FN_LSD2(word);                         \
 513           lspref(destLSDptr,3) = FN_LSD3(word);                         \
 514         }                                                               \
 515     }                                                                   \
 516   unused (MSDptr_zuweisung (destLSDptr) lspop len_from_FN_to_NDS);      \
 517   unused (len_zuweisung len_from_FN_to_NDS);                            \
 518   unused (LSDptr_zuweisung (destLSDptr));                               \
 519 }
 520
 521 // Bignum to Normalized Digit sequence, Kopieren unnötig
 522 // BN_to_NDS_nocopy(obj, MSDptr=,len=,LSDptr=);
 523 // > obj: ein Bignum
 524 // < MSDptr/len/LSDptr: Normalized Digit sequence
 525 #if CL_DS_BIG_ENDIAN_P
 526   #define BN_to_NDS_nocopy(obj, MSDptr_zuweisung,len_zuweisung,LSDptr_zuweisung)  \
 527     { var Bignum bn_from_BN_to_NDS_nocopy = TheBignum(obj);             \
 528       unused (MSDptr_zuweisung (const uintD*) &bn_from_BN_to_NDS_nocopy->data[0]);      \
 529       unused (LSDptr_zuweisung (const uintD*) &bn_from_BN_to_NDS_nocopy->data[(uintP)( len_zuweisung bn_from_BN_to_NDS_nocopy->length )]);              \
 530     }
 531 #else
 532   #define BN_to_NDS_nocopy(obj, MSDptr_zuweisung,len_zuweisung,LSDptr_zuweisung)  \
 533     { var Bignum bn_from_BN_to_NDS_nocopy = TheBignum(obj);             \
 534       unused (LSDptr_zuweisung (const uintD*) &bn_from_BN_to_NDS_nocopy->data[0]);      \
 535       unused (MSDptr_zuweisung (const uintD*) &bn_from_BN_to_NDS_nocopy->data[(uintP)( len_zuweisung bn_from_BN_to_NDS_nocopy->length )]);              \
 536     }
 537 #endif
 538   inline const uintD* BN_MSDptr (const cl_I& obj)
 539     { var Bignum bn = TheBignum(obj); return (const uintD*) arrayMSDptr(bn->data,bn->length); }
 540   inline const uintD* BN_LSDptr (const cl_I& obj)
 541     { var Bignum bn = TheBignum(obj); return (const uintD*) arrayLSDptr(bn->data,bn->length); }
 542
 543 // Bignum to Normalized Digit sequence
 544 // BN_to_NDS(obj, MSDptr=,len=,LSDptr=);
 545 // > obj: ein Bignum
 546 // < MSDptr/len/LSDptr: Normalized Digit sequence, darf modifiziert werden.
 547 // Dabei wird num_stack erniedrigt.
 548   #define BN_to_NDS(obj, MSDptr_zuweisung,len_zuweisung,LSDptr_zuweisung)  \
 549     { var const cl_I& obj_from_BN_to_NDS = (obj);                       \
 550       var uintD* MSDptr_from_BN_to_NDS;                                 \
 551       var uintC len_from_BN_to_NDS;                                     \
 552       len_zuweisung len_from_BN_to_NDS = TheBignum(obj_from_BN_to_NDS)->length; \
 553       num_stack_alloc(len_from_BN_to_NDS, MSDptr_zuweisung MSDptr_from_BN_to_NDS = , LSDptr_zuweisung); \
 554       copy_loop_msp(BN_MSDptr(obj_from_BN_to_NDS),MSDptr_from_BN_to_NDS,len_from_BN_to_NDS); \
 555     }
 556
 557 // Bignum to Normalized Digit sequence
 558 // BN_to_NDS_1(obj, MSDptr=,len=,LSDptr=);
 559 // > obj: ein Bignum
 560 // < MSDptr/len/LSDptr: Normalized Digit sequence, darf modifiziert werden.
 561 // Unterhalb von MSDptr ist noch 1 Digit Platz.
 562 // Dabei wird num_stack erniedrigt.
 563   #define BN_to_NDS_1(obj, MSDptr_zuweisung,len_zuweisung,LSDptr_zuweisung)  \
 564     { var const cl_I& obj_from_BN_to_NDS = (obj);                       \
 565       var uintD* MSDptr_from_BN_to_NDS;                                 \
 566       var uintC len_from_BN_to_NDS;                                     \
 567       len_zuweisung len_from_BN_to_NDS = TheBignum(obj_from_BN_to_NDS)->length; \
 568       num_stack_alloc_1(len_from_BN_to_NDS, MSDptr_zuweisung MSDptr_from_BN_to_NDS = , LSDptr_zuweisung); \
 569       copy_loop_msp(BN_MSDptr(obj_from_BN_to_NDS),MSDptr_from_BN_to_NDS,len_from_BN_to_NDS); \
 570     }
 571
 572 // Integer to Normalized Digit sequence, Kopieren unnötig.
 573 // I_to_NDS_nocopy(obj, MSDptr=,len=,LSDptr=,check_for_0,zero_statement);
 574 // > obj: ein Integer
 575 // > check_for_0: ob obj möglicherweise =0 sein kann
 576 // > zero_statement: wird bei obj=0 ausgeführt
 577 // < MSDptr/len/LSDptr: Normalized Digit sequence
 578   #define I_to_NDS_nocopy(obj, MSDptr_zuweisung,len_zuweisung,LSDptr_zuweisung, check_for_0,zero_statement)  \
 579     var uintD CONCAT(FN_store_,__LINE__) [FN_maxlength];                \
 580     { var const cl_I& obj_from_I_to_NDS_nocopy = (obj);                 \
 581       if (fixnump(obj_from_I_to_NDS_nocopy))                            \
 582         { 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); } \
 583         else                                                            \
 584         { BN_to_NDS_nocopy(obj_from_I_to_NDS_nocopy,MSDptr_zuweisung,len_zuweisung, LSDptr_zuweisung); } \
 585     }
 586
 587 // Integer to Normalized Digit sequence
 588 // I_to_NDS(obj, MSDptr=,len=,LSDptr=);
 589 // > obj: ein Integer
 590 // < MSDptr/len/LSDptr: Normalized Digit sequence, darf modifiziert werden.
 591 // Dabei wird num_stack erniedrigt.
 592   #define I_to_NDS(obj, MSDptr_zuweisung,len_zuweisung,LSDptr_zuweisung)  \
 593     var uintD CONCAT(FN_store_,__LINE__) [FN_maxlength];                \
 594     { var const cl_I& obj_from_I_to_NDS = (obj);                        \
 595       if (fixnump(obj_from_I_to_NDS))                                   \
 596         { 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,); } \
 597         else                                                              \
 598         { BN_to_NDS(obj_from_I_to_NDS,MSDptr_zuweisung,len_zuweisung, LSDptr_zuweisung); } \
 599     }
 600
 601 // Integer to Normalized Digit sequence
 602 // I_to_NDS_1(obj, MSDptr=,len=,LSDptr=);
 603 // > obj: ein Integer
 604 // < MSDptr/len/LSDptr: Normalized Digit sequence, darf modifiziert werden.
 605 // Unterhalb von MSDptr ist noch 1 Digit Platz.
 606 // Dabei wird num_stack erniedrigt.
 607   #define I_to_NDS_1(obj, MSDptr_zuweisung,len_zuweisung,LSDptr_zuweisung)  \
 608     var uintD CONCAT(FN_store_,__LINE__) [1+FN_maxlength];              \
 609     { var const cl_I& obj_from_I_to_NDS = (obj);                        \
 610       if (fixnump(obj_from_I_to_NDS))                                   \
 611         { 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,); } \
 612         else                                                              \
 613         { BN_to_NDS_1(obj_from_I_to_NDS,MSDptr_zuweisung,len_zuweisung, LSDptr_zuweisung); } \
 614     }
 615
 616
 617 // Division ganzer Zahlen
 618
 619 // Dividiert zwei Integers x,y >=0 und liefert Quotient und Rest
 620 // der Division x/y. Bei y=0 Error.
 621 // cl_divide(x,y)
 622 // > x,y: Integers >=0
 623 // < q,r: Quotient q, Rest r
 624   extern const cl_I_div_t cl_divide (const cl_I& x, const cl_I& y);
 625
 626 // Fehler, wenn Quotient keine ganze Zahl ist
 627   nonreturning_function(extern, cl_error_exquo, (const cl_I& x, const cl_I& y));
 628
 629
 630 // ggT und kgV von Integers
 631
 632   // Teilfunktion für die Durchführung des Euklid-Algorithmus auf
 633   // den führenden Ziffern a' und b':
 634   // partial_gcd(a',b',&erg); mit a'>b'
 635   // liefert in erg: x1,y1,x2,y2 mit den in cl_I_gcd.cc angegebenen Invarianten.
 636   typedef struct { uintD x1,y1,x2,y2; } partial_gcd_result;
 637   extern void partial_gcd (uintD z1, uintD z2, partial_gcd_result* erg);
 638   #if HAVE_DD
 639     extern void partial_gcd (uintDD z1, uintDD z2, partial_gcd_result* erg);
 640   #else
 641     extern void partial_gcd (uintD z1hi, uintD z1lo, uintD z2hi, uintD z2lo, partial_gcd_result* erg);
 642   #endif
 643
 644
 645 // Wurzel aus ganzen Zahlen
 646
 647 // Stellt fest, ob ein Integer >=0 eine n-te Potenz ist.
 648 // cl_rootp_aux(x,n,&w)
 649 // > x: ein Integer >=0
 650 // > n: ein Integer >0
 651 // > Annahme: x > 1 und n < (integer-length x).
 652 // < w: Integer (expt x (/ n)) falls x eine n-te Potenz
 653 // < ergebnis: cl_true         ........................, cl_false sonst
 654   extern cl_boolean cl_rootp_aux (cl_I x, uintL n, cl_I* w);
 655
 656
 657 // Hilfsfunktion zur Eingabe von Integers
 658
 659 // Wandelt eine Ziffernfolge in ein Integer >=0 um.
 660 // digits_to_I(MSBptr,len,base)
 661 // > base: Stellenwertsystem-Basis, >=2, <=36
 662 // > MSBptr/len/..: Ziffernfolge, bestehend aus Punkten (werden überlesen)
 663 //     und Ziffern/Buchstaben mit Wert < base.
 664 // < ergebnis: der dargestellte Integer >=0
 665   extern const cl_I digits_to_I (const char * MSBptr, uintC len, uintD base);
 666
 667
 668 // Hilfsfunktion zur Ausgabe von Integers
 669
 670 // cl_digits_need(len,base) liefert eine obere Abschätzung für die Anzahl der
 671 // Ziffern im Stellenwertsystem der Basis base, die x >= 0 braucht.
 672   extern uintC cl_digits_need (const cl_I& x, uintL base);
 673
 674 // Wandelt ein Integer in ein Stellensystem um.
 675 // I_to_digits(x,base, &ergebnis);
 676 // > x: ein Integer >=0
 677 // > base: Stellensystem-Basis, 2 <= base <= 36.
 678 // > ergebnis.LSBptr: darunter ist mindestens digits_need(len) Bytes Platz
 679 // < ergebnis: fertige Folge MSBptr/len/LSBptr von Ziffern
 680   typedef struct { uintB* MSBptr; uintC len; uintB* LSBptr; } cl_digits;
 681   extern void I_to_digits (const cl_I& x, uintD base, cl_digits* erg);
 682
 683
 684 // Hash code.
 685   extern unsigned long hashcode (const cl_I& x);
 686
 687
 688 // A fixnum (cl_FN) is an immediate integer.
 689
 690 // typedef
 691 class cl_FN : public cl_I {
 692 public:
 693 // Optimization of method pointer_p().
 694         cl_boolean pointer_p() const
 695                 { return cl_false; }
 696 };
 697
 698 inline cl_boolean fixnump (const cl_FN& x)
 699         { unused x; return cl_true; }
 700 inline cl_boolean bignump (const cl_FN& x)
 701         { unused x; return cl_false; }
 702
 703 inline cl_boolean minusp (const cl_FN& x)
 704 {
 705         // This assumes cl_value_shift + cl_value_len == cl_pointer_size.
 706         return (cl_boolean)((cl_sint) x.word < 0);
 707 }
 708
 709
 710 // A bignum (cl_BN) is a heap-allocated integer.
 711
 712 // typedef
 713 class cl_BN : public cl_I {
 714 public:
 715 // Optimization of method pointer_p().
 716         cl_boolean pointer_p() const
 717                 { return cl_true; }
 718 };
 719
 720 inline cl_boolean fixnump (const cl_BN& x)
 721         { unused x; return cl_false; }
 722 inline cl_boolean bignump (const cl_BN& x)
 723         { unused x; return cl_true; }
 724
 725 inline cl_boolean minusp (const cl_BN& x)
 726 {
 727         return (cl_boolean)((sintD)mspref(arrayMSDptr(TheBignum(x)->data,TheBignum(x)->length),0) < 0);
 728 }
 729 inline cl_boolean zerop (const cl_BN& x)
 730         { unused x; return cl_false; }
 731
 732 }  // namespace cln
 733
 734 #endif /* _CL_I_H */