6 #include "cln/number.h"
7 #include "cln/integer.h"
9 #include "cln/malloc.h"
10 #include "cln/abort.h"
11 #include "cl_offsetof.h"
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.
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)
33 return cl_I((struct cl_fixnum *) 0, w);
36 inline cl_uint cl_FN_word (const cl_I& x)
44 struct cl_heap_bignum : cl_heap {
45 uintC length; // length (in digits)
46 uintD data[1]; // number in two's complement representation
49 inline cl_heap_bignum* TheBignum (cl_heap_bignum* p)
51 inline cl_heap_bignum* TheBignum (const cl_number& obj)
52 { return (cl_heap_bignum*)(obj.pointer); }
54 inline cl_heap_bignum* allocate_bignum (uintC length)
56 cl_heap_bignum* p = (cl_heap_bignum*) malloc_hook(offsetofa(cl_heap_bignum,data)+sizeof(uintD)*length);
58 p->type = &cl_class_bignum;
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) {}
68 // Both work, but the first definition results in less compiler-generated
71 #define Bignum cl_heap_bignum*
77 // Integers in general.
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(); }
89 // (MINUSP x) == (< x 0)
90 inline cl_boolean minusp (const cl_I& x)
93 // This assumes cl_value_shift + cl_value_len == cl_pointer_size.
94 return (cl_boolean)((cl_sint) x.word < 0);
96 return (cl_boolean)((sintD)mspref(arrayMSDptr(TheBignum(x)->data,TheBignum(x)->length),0) < 0);
99 // (ZEROP x) == (= x 0)
100 inline cl_boolean zerop (const cl_I& x)
102 return (cl_boolean)(x.word == cl_combine(cl_FN_tag,0));
105 // (EQ x y) == (= x y), assuming y a fixnum
106 inline cl_boolean eq (const cl_I& x, sint32 y)
108 return (cl_boolean)(x.word == cl_combine(cl_FN_tag,y));
112 // Umwandlungsroutinen Integer <--> Longword:
114 // Wandelt Fixnum >=0 in Unsigned Longword um.
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)
120 // This assumes cl_value_shift + cl_value_len == cl_pointer_size.
121 return (cl_uint)(x.word) >> cl_value_shift;
124 // Wandelt Fixnum in Longword um.
127 // < ergebnis: der Wert des Fixnum als intVsize-Bit-Zahl.
128 inline sintV FN_to_V (const cl_I& x)
130 // This assumes cl_value_shift + cl_value_len == cl_pointer_size.
131 return (cl_sint)(x.word) >> cl_value_shift;
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)
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)
144 // Wandelt Fixnum in Quadword um.
147 // < ergebnis: der Wert des Fixnum als 64-Bit-Zahl.
148 inline sint64 FN_to_Q (const cl_I& x)
150 // This assumes cl_value_shift + cl_value_len == cl_pointer_size.
151 return (cl_sint)(x.word) >> cl_value_shift;
154 // Wandelt Integer >=0 in Unsigned Quadword um.
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);
160 // Wandelt Integer in Signed Quadword um.
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);
168 // Wandelt Longword in Fixnum um.
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)
175 return cl_I_from_word(cl_combine(cl_FN_tag,wert));
178 // Wandelt Longword in Integer um.
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)
185 extern cl_private_thing cl_I_constructor_from_L (sint32 wert);
186 inline const cl_I L_to_I (sint32 wert)
188 return cl_I(cl_I_constructor_from_L(wert));
192 // Wandelt Unsigned Longword in Fixnum >=0 um.
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)
198 return cl_I_from_word(cl_combine(cl_FN_tag,wert));
201 // Wandelt Unsigned Longword in Integer >=0 um.
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)
208 extern cl_private_thing cl_I_constructor_from_UL (uint32 wert);
209 inline const cl_I UL_to_I (uint32 wert)
211 return cl_I(cl_I_constructor_from_UL(wert));
217 // Wandelt Quadword in Integer um.
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)
224 return cl_I(cl_I_constructor_from_Q(wert));
227 // Wandelt Unsigned Quadword in Integer >=0 um.
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)
234 return cl_I(cl_I_constructor_from_UQ(wert));
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)
240 return cl_I(cl_I_constructor_from_Q2(wert_hi, wert_lo));
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)
251 return cl_I_constructor_from_Q(((sint64)wert_hi<<32) | (sint64)wert_lo);
254 extern cl_private_thing cl_I_constructor_from_L2 (sint32 wert_hi, uint32 wert_lo);
256 inline const cl_I L2_to_I (sint32 wert_hi, uint32 wert_lo)
258 return cl_I(cl_I_constructor_from_L2(wert_hi,wert_lo));
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)
268 return cl_I_constructor_from_UQ(((uint64)wert_hi<<32) | (uint64)wert_lo);
271 extern cl_private_thing cl_I_constructor_from_UL2 (uint32 wert_hi, uint32 wert_lo);
273 inline const cl_I UL2_to_I (uint32 wert_hi, uint32 wert_lo)
275 return cl_I(cl_I_constructor_from_UL2(wert_hi,wert_lo));
278 // Wandelt sintV in Integer um.
280 // > wert: Wert des Integers, ein sintV.
281 // < ergebnis: Integer mit diesem Wert.
283 #define V_to_I(wert) L_to_I(wert)
285 #define V_to_I(wert) Q_to_I(wert)
288 // Wandelt uintV in Integer >=0 um.
290 // > wert: Wert des Integers, ein uintV.
291 // < ergebnis: Integer mit diesem Wert.
293 #define UV_to_I(wert) UL_to_I(wert)
295 #define UV_to_I(wert) UQ_to_I(wert)
298 // Wandelt sintE in Integer um.
300 // > wert: Wert des Integers, ein sintE.
301 // < ergebnis: Integer mit diesem Wert.
303 #define E_to_I(wert) L_to_I(wert)
305 #define E_to_I(wert) Q_to_I(wert)
308 // Wandelt uintE in Integer >=0 um.
310 // > wert: Wert des Integers, ein uintE.
311 // < ergebnis: Integer mit diesem Wert.
313 #define UE_to_I(wert) UL_to_I(wert)
315 #define UE_to_I(wert) UQ_to_I(wert)
318 // Wandelt uintD in Integer >=0 um.
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)
325 #define UD_to_I(wert) UL_to_I(wert)
327 #define UD_to_I(wert) UQ_to_I(wert)
330 // Liefert die Differenz x-y zweier Unsigned Longwords x,y als Integer.
332 inline const cl_I minus (uintL x, uintL y)
334 #if (cl_word_size==64)
335 return Q_to_I((sintQ)(uintQ)x - (sintQ)(uintQ)y);
337 return L2_to_I( (x<y ? -1 : 0), x-y );
343 inline const cl_I minus (uintQ x, uintQ y)
345 return Q2_to_I( (x<y ? -1 : 0), x-y );
350 // Umwandlungsroutinen Digit sequence <--> Longword:
354 // Holt die nächsten pFN_maxlength Digits in ein uintV.
355 inline uintV pFN_maxlength_digits_at (const uintD* ptr)
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);
376 // Schreibt ein uintV in die nächsten pFN_maxlength Digits.
377 inline void set_pFN_maxlength_digits_at (uintD* ptr, uintV wert)
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);
428 // Holt die nächsten pFN_maxlength Digits in ein uint64.
429 inline uint64 pFN_maxlength_digits_at (const uintD* ptr)
431 return (uint64)lspref(ptr,0);
437 // Umwandlungsroutinen Digit sequence --> Integer:
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);
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);
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);
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);
462 // Umwandlungsroutinen Integer --> Digit sequence:
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.
469 inline sintD FN_MSD (cl_uint word)
471 // This assumes cl_value_shift + cl_value_len == cl_pointer_size.
472 return (cl_sint)word >> (cl_value_shift + (FN_maxlength-1)*intDsize);
475 #if (FN_maxlength==1)
476 #define FN_LSD0(word) FN_MSD(word)
477 #define FN_LSD1(word) (cl_abort(), (uintD)0) // never used
478 #define FN_LSD2(word) (cl_abort(), (uintD)0) // never used
479 #define FN_LSD3(word) (cl_abort(), (uintD)0) // never used
481 #if (FN_maxlength==2)
482 inline uintD FN_LSD0 (cl_uint word)
484 return (uintD)(word >> cl_value_shift);
486 #define FN_LSD1(word) FN_MSD(word)
487 #define FN_LSD2(word) (cl_abort(), (uintD)0) // never used
488 #define FN_LSD3(word) (cl_abort(), (uintD)0) // never used
490 #if (FN_maxlength==4)
491 inline uintD FN_LSD0 (cl_uint word)
493 return (uintD)(word >> cl_value_shift);
495 inline uintD FN_LSD1 (cl_uint word)
497 return (uintD)(word >> (cl_value_shift + intDsize));
499 inline uintD FN_LSD2 (cl_uint word)
501 return (uintD)(word >> (cl_value_shift + 2*intDsize));
503 #define FN_LSD3(word) FN_MSD(word)
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))
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 } \
519 { var cl_uint testMSD; \
520 if ((FN_maxlength<=1) || \
521 ((testMSD = (word) & FN_MSD1_mask) == 0) || (testMSD == FN_MSD1_mask) \
523 { len_from_FN_to_NDS = 1; \
524 lspref(destLSDptr,0) = FN_LSD0(word); \
526 elif ((FN_maxlength<=2) || \
527 ((testMSD = (word) & FN_MSD2_mask) == 0) || (testMSD == FN_MSD2_mask) \
529 { len_from_FN_to_NDS = 2; \
530 lspref(destLSDptr,0) = FN_LSD0(word); \
531 lspref(destLSDptr,1) = FN_LSD1(word); \
533 elif ((FN_maxlength<=3) || \
534 ((testMSD = (word) & FN_MSD3_mask) == 0) || (testMSD == FN_MSD3_mask) \
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); \
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); \
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)); \
554 // Bignum to Normalized Digit sequence, Kopieren unnötig
555 // BN_to_NDS_nocopy(obj, MSDptr=,len=,LSDptr=);
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 )]); \
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 )]); \
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); }
576 // Bignum to Normalized Digit sequence
577 // BN_to_NDS(obj, MSDptr=,len=,LSDptr=);
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); \
590 // Bignum to Normalized Digit sequence
591 // BN_to_NDS_1(obj, MSDptr=,len=,LSDptr=);
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); \
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); } \
617 { BN_to_NDS_nocopy(obj_from_I_to_NDS_nocopy,MSDptr_zuweisung,len_zuweisung, LSDptr_zuweisung); } \
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, cl_true,); } \
631 { BN_to_NDS(obj_from_I_to_NDS,MSDptr_zuweisung,len_zuweisung, LSDptr_zuweisung); } \
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, cl_true,); } \
646 { BN_to_NDS_1(obj_from_I_to_NDS,MSDptr_zuweisung,len_zuweisung, LSDptr_zuweisung); } \
650 // Division ganzer Zahlen
652 // Dividiert zwei Integers x,y >=0 und liefert Quotient und Rest
653 // der Division x/y. Bei y=0 Error.
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);
659 // Fehler, wenn Quotient keine ganze Zahl ist
660 nonreturning_function(extern, cl_error_exquo, (const cl_I& x, const cl_I& y));
663 // ggT und kgV von Integers
665 // Teilfunktion für die Durchführung des Euklid-Algorithmus auf
666 // den führenden Ziffern a' und b':
667 // partial_gcd(a',b',&erg); mit a'>b'
668 // liefert in erg: x1,y1,x2,y2 mit den in cl_I_gcd.cc angegebenen Invarianten.
669 typedef struct { uintD x1,y1,x2,y2; } partial_gcd_result;
670 extern void partial_gcd (uintD z1, uintD z2, partial_gcd_result* erg);
672 extern void partial_gcd (uintDD z1, uintDD z2, partial_gcd_result* erg);
674 extern void partial_gcd (uintD z1hi, uintD z1lo, uintD z2hi, uintD z2lo, partial_gcd_result* erg);
678 // Wurzel aus ganzen Zahlen
680 // Stellt fest, ob ein Integer >=0 eine n-te Potenz ist.
681 // cl_rootp_aux(x,n,&w)
682 // > x: ein Integer >=0
683 // > n: ein Integer >0
684 // > Annahme: x > 1 und n < (integer-length x).
685 // < w: Integer (expt x (/ n)) falls x eine n-te Potenz
686 // < ergebnis: cl_true ........................, cl_false sonst
687 extern cl_boolean cl_rootp_aux (cl_I x, uintL n, cl_I* w);
690 // Hilfsfunktion zur Eingabe von Integers
692 // Wandelt eine Ziffernfolge in ein Integer >=0 um.
693 // digits_to_I(MSBptr,len,base)
694 // > base: Stellenwertsystem-Basis, >=2, <=36
695 // > MSBptr/len/..: Ziffernfolge, bestehend aus Punkten (werden überlesen)
696 // und Ziffern/Buchstaben mit Wert < base.
697 // < ergebnis: der dargestellte Integer >=0
698 extern const cl_I digits_to_I (const char * MSBptr, uintC len, uintD base);
701 // Hilfsfunktion zur Ausgabe von Integers
703 // cl_digits_need(len,base) liefert eine obere Abschätzung für die Anzahl der
704 // Ziffern im Stellenwertsystem der Basis base, die x >= 0 braucht.
705 extern uintC cl_digits_need (const cl_I& x, uintL base);
707 // Wandelt ein Integer in ein Stellensystem um.
708 // I_to_digits(x,base, &ergebnis);
709 // > x: ein Integer >=0
710 // > base: Stellensystem-Basis, 2 <= base <= 36.
711 // > ergebnis.LSBptr: darunter ist mindestens digits_need(len) Bytes Platz
712 // < ergebnis: fertige Folge MSBptr/len/LSBptr von Ziffern
713 typedef struct { uintB* MSBptr; uintC len; uintB* LSBptr; } cl_digits;
714 extern void I_to_digits (const cl_I& x, uintD base, cl_digits* erg);
718 extern unsigned long hashcode (const cl_I& x);
721 // A fixnum (cl_FN) is an immediate integer.
724 class cl_FN : public cl_I {
726 // Optimization of method pointer_p().
727 cl_boolean pointer_p() const
731 inline cl_boolean fixnump (const cl_FN& x)
732 { unused x; return cl_true; }
733 inline cl_boolean bignump (const cl_FN& x)
734 { unused x; return cl_false; }
736 inline cl_boolean minusp (const cl_FN& x)
738 // This assumes cl_value_shift + cl_value_len == cl_pointer_size.
739 return (cl_boolean)((cl_sint) x.word < 0);
743 // A bignum (cl_BN) is a heap-allocated integer.
746 class cl_BN : public cl_I {
748 // Optimization of method pointer_p().
749 cl_boolean pointer_p() const
753 inline cl_boolean fixnump (const cl_BN& x)
754 { unused x; return cl_false; }
755 inline cl_boolean bignump (const cl_BN& x)
756 { unused x; return cl_true; }
758 inline cl_boolean minusp (const cl_BN& x)
760 return (cl_boolean)((sintD)mspref(arrayMSDptr(TheBignum(x)->data,TheBignum(x)->length),0) < 0);
762 inline cl_boolean zerop (const cl_BN& x)
763 { unused x; return cl_false; }