Vicare Scheme: objects bignums

13.13 Bignum objects

Bignums are multi–precision exact integers bigger than fixnums; they are implemented using the mpn API of GNU GMP, See (gmp)Low-level Functions.

Vicare only uses a bignum to represent an exact integer when the value does not fit in a fixnum; it follows that the following ranges are enforced:

negative bignums < (least-fixnum) <= all fixnums

all fixnums <= (greatest-fixnum) < positive bignums

and notice that:

The smallest positive bignum is (+ 1 (greatest-fixnum)) which can also be computed as (- (least-fixnum)).
The greatest negative bignum is (- (least-fixnum) 1).

A bignum is a variable length memory block referenced by machine words tagged as vectors. The first machine word of a bignum block is tagged has bignum in its least significant bits; then comes a sign bit, zero if positive; the remaining most significant bits represent the number of words in the memory block after the first one.

|------------------------|-------------| reference to bignum
      heap pointer         vector tag

                     sign bit
|----------------------|-|-------------| bignum first word
   number of words         bignum tag

A pointer to the second machine word in a bignum memory block is the pointer of type mp_limb_t accepted by the mpn_ functions of GMP; limb, in GMP jargon, is a machine word holding a portion of multi–precision number. The layout of a bignum memory block is as follows:

|----|-----|-----|-----|-----| ...
 1st  limb0 limb1 limb2 limb3

where the first word 1st is a header of meta informations encoded as explained above and each limb is a machine word stored in native endianness; the big number is the concatenation of limbs with limb0 being the least significant one. There is always at least one limb; when a bignum is composed of a single limb, its value is always non–zero and outside the range of fixnums.

Basic operations

To allocate a bignum we must know the number of required limbs:

ikpcb_t *  pcb        = ik_the_pcb();
ikuword_t  nlimbs     = the_number_of_limbs;
ikuword_t  block_size = disp_bignum_data + nlimbs * wordsize;
ikuword_t  align_size = IK_ALIGN(block_size);
ikptr_t s_bn = ik_safe_alloc(pcb, align_size) | vector_tag;

we must explicitly build and encode the first word; the number of limbs is encoded as follows:

ikuword_t  nlimbs      = the_number_of_limbs;
ikptr_t    meta_nlimbs = nlimbs << bignum_nlimbs_shift;

the sign bit is encoded as follows:

ikuword_t  sign      = zero_if_positive_one_if_negative;
ikptr_t    meta_sign = sign << bignum_sign_shift;

and the full first word is composed and stored as follows:

ikptr_t  s_bn        = the_bignum;
ikptr_t  meta_nlimbs = ...;
ikptr_t  meta_sign   = ...;
ikptr_t  s_fst       = meta_nlimbs | meta_sign | bignum_tag;

IK_REF(s_bn, off_bignum_tag) = s_fst;

To identify an object as bignum we do:

ikptr_t  X = the_object;

if ((vector_tag == IK_TAGOF(X)) &&
    (bignum_tag == (bignum_mask & IK_REF(X, off_bignum_tag))))
  it_is_a_bignum();
else
  it_is_not();

to extract meta informations we must first extract the first word:

ikptr_t    s_bn  = the_bignum;
ikptr_t    s_fst = IK_REF(s_bn, off_bignum_tag);
ikuword_t  nlimbs;
ikuword_t  meta_sign;

nlimbs    = ((ikuword_t)s_fst) >> bignum_nlimbs_shift;
meta_sign = ((ikuword_t)s_fst) &  bignum_sign_mask;

if meta_sign is zero the bignum is positive, else it is negative.

To acquire a pointer to the data area we do:

ikptr_t      s_bn = the_bignum;
mp_limb_t *  data = IK_BIGNUM_DATA_LIMBP(s_bn);

to extract the N-th limb we do:

ikptr_t    s_bn = the_bignum;
ikuword_t  N    = the_index;
mp_limb_t  limb = IK_LIMB(s_bn, N);

Preprocessor Symbol: bignum_mask
Preprocessor Symbol: bignum_tag: bignum_mask is the bit pattern used to isolate a bignum tag from an ikptr_t value; bignum_tag is the tag of ikptr_t values used as first words in bignum memory blocks.

Preprocessor Symbol: bignum_sign_mask: A bit pattern used to isolate the sign bit from the ikptr_t value used as first word in bignum memory blocks.

Preprocessor Symbol: bignum_sign_shift: The number representing the bit left–shift offset of the sign bit in the ikptr_t value used as first word in bignum memory blocks.

Preprocessor Symbol: bignum_nlimbs_shift: The number representing the bit left–shift offset of the number of limbs in the ikptr_t value used as first word in bignum memory blocks.

Preprocessor Symbol: disp_bignum_tag: Offset in bytes of the first word in a bignum memory block from the beginning of the block. It is zero.

Preprocessor Symbol: disp_bignum_data: Offset in bytes of the first byte in the data area of a bignum memory block from the beginning of the block.

Preprocessor Symbol: off_bignum_tag: Number to add to a tagged ikptr_t reference to bignum to obtain a pointer to the first word in a bignum memory block.

Preprocessor Symbol: off_bignum_data: Number to add to a tagged ikptr_t reference to bignum to obtain a pointer to the first byte in the data area of bignum memory block.

Convenience preprocessor macros

Preprocessor Macro: ikuword_t IK_BIGNUM_ALLOC_SIZE (ikuword_t nlimbs): Given a number of limbs: evaluate to the aligned size of the memory block needed to hold the bignum.

Preprocessor Macro: ikptr_t IKA_BIGNUM_ALLOC (ikpcb_t * pcb, ikuword_t nlimb): Given a number of limbs: allocate, using ik_safe_alloc(), the memory block needed to hold the bignum and return an untagged pointer to it.

Preprocessor Macro: ikptr_t IK_COMPOSE_BIGNUM_FIRST_WORD (ikuword_t nlimb, ikptr_t meta_sign)

Given a number of limbs and the encoded sign bit: evaluate to the first word of a bignum object. It is equivalent to the following:

ikptr_t  meta_nlimbs;
ikptr_t  s_fst;

meta_nlimbs = (nlimbs << bignum_nlimbs_shift)
s_fst       = meta_nlimbs | meta_sign | bignum_tag;

Preprocessor Macro: ikptr_t IK_POSITIVE_BIGNUM_FIRST_WORD (ikuword_t nlimb)
Preprocessor Macro: ikptr_t IK_NEGATIVE_BIGNUM_FIRST_WORD (ikuword_t nlimb): Given a number of limbs evaluate to the corresponding first word of bignum representing a positive or negative number.

Preprocessor Macro: ikptr_t IK_BIGNUM_FIRST (ikptr_t bn)

Given a reference to bignum: evaluate to the location of the first word holding meta informations. Can be used both as operand or left–side of assignment:

ikptr_t  s_bn = the_bignum;
ikptr_t  s_fst;

s_fst = IK_BIGNUM_FIRST(s_bn);
IK_BIGNUM_FIRST(s_bn) = s_fst;

Preprocessor Macro: ikptr_t IK_LIMB (ikptr_t bn, ikuword_t N)

Given a reference to bignum: evaluate to the location of the N-th limb in the data area. Can be used both as operand or left–side of assignment:

ikptr_t      s_bn = the_bignum;
mp_limb_t  limb;

limb = (mp_limb_t)IK_LIMB(s_bn);
IK_LIMB(s_bn) = (ikptr_t)limb;

Preprocessor Macro: mp_limb_t * IK_BIGNUM_DATA_LIMBP (ikptr_t bn)
Preprocessor Macro: void * IK_BIGNUM_DATA_VOIDP (ikptr_t bn): Given a reference to bignum: evaluate to a pointer to the first byte in the data area, which is a pointer to the least significant limb.

Preprocessor Macro: mp_limb_t IK_BIGNUM_FIRST_LIMB (ikptr_t bn): Given a reference to bignum: evaluate to the least significant limb in the data area.

Preprocessor Macro: mp_limb_t IK_BIGNUM_LAST_LIMB (ikptr_t bn, ikuword_t nlimbs): Given a reference to bignum and its number of limbs: evaluate to the most significant limb in the data area.