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