truncate

Truncate an integer to a number of bits, following 2s-complement semantics. r may alias a.

Asserts r has enough storage to compute the result. The upper bound is calcTwosCompLimbCount(a.len).

Function parameters

Parameters

r:*Mutable
a:Const
signedness:Signedness
bit_count:usize

Used to indicate either limit of a 2s-complement integer.

Types

TwosCompIntLimit: Used to indicate either limit of a 2s-complement integer.
Round
Exactness
Mutable: A arbitrary-precision big integer, with a fixed set of mutable limbs.
Const: A arbitrary-precision big integer, with a fixed set of immutable limbs.
Managed: An arbitrary-precision big integer along with an allocator which manages the memory.

Returns the number of limbs needed to store `scalar`, which must be a

Functions

calcLimbLen: Returns the number of limbs needed to store `scalar`, which must be a
calcToStringLimbsBufferLen
calcDivLimbsBufferLen
calcMulLimbsBufferLen
calcMulWrapLimbsBufferLen
calcSetStringLimbsBufferLen
calcSetStringLimbCount: Assumes `string_len` doesn't account for minus signs if the number is negative.
calcPowLimbsBufferLen
calcSqrtLimbsBufferLen
calcNonZeroTwosCompLimbCount: Compute the number of limbs required to store a 2s-complement number of `bit_count` bits.
calcTwosCompLimbCount: Compute the number of limbs required to store a 2s-complement number of `bit_count` bits.
addMulLimbWithCarry: a + b * c + *carry, sets carry to the overflow bits
llcmp: Returns -1, 0, 1 if |a| < |b|, |a| == |b| or |a| > |b| respectively for limbs.

Source

Implementation

pub fn truncate(r: *Mutable, a: Const, signedness: Signedness, bit_count: usize) void {
    // Handle 0-bit integers.
    if (bit_count == 0) {
        @branchHint(.unlikely);
        r.set(0);
        return;
    }

    const max_limbs = calcTwosCompLimbCount(bit_count);
    const sign_bit = @as(Limb, 1) << @truncate(bit_count - 1);
    const mask = @as(Limb, maxInt(Limb)) >> @truncate(-%bit_count);

    // Guess whether the result will have the same sign as `a`.
    //  * If the result will be signed zero, the guess is `true`.
    //  * If the result will be the minimum signed integer, the guess is `false`.
    //  * If the result will be unsigned zero, the guess is `a.positive`.
    //  * Otherwise the guess is correct.
    const same_sign_guess = switch (signedness) {
        .signed => max_limbs > a.limbs.len or a.limbs[max_limbs - 1] & sign_bit == 0,
        .unsigned => a.positive,
    };

    const abs_trunc_a: Const = .{
        .positive = true,
        .limbs = a.limbs[0..llnormalize(a.limbs[0..@min(a.limbs.len, max_limbs)])],
    };
    if (same_sign_guess or abs_trunc_a.eqlZero()) {
        // One of the following is true:
        //  * The result is zero.
        //  * The result is non-zero and has the same sign as `a`.
        r.copy(abs_trunc_a);
        if (max_limbs <= r.len) r.limbs[max_limbs - 1] &= mask;
        r.normalize(r.len);
        r.positive = a.positive or r.eqlZero();
    } else {
        // One of the following is true:
        //  * The result is the minimum signed integer.
        //  * The result is unsigned zero.
        //  * The result is non-zero and has the opposite sign as `a`.
        r.addScalar(abs_trunc_a, -1);
        llnot(r.limbs[0..r.len]);
        @memset(r.limbs[r.len..max_limbs], maxInt(Limb));
        r.limbs[max_limbs - 1] &= mask;
        r.normalize(max_limbs);
        r.positive = switch (signedness) {
            // The only value with the sign bit still set is the minimum signed integer.
            .signed => !a.positive and r.limbs[max_limbs - 1] & sign_bit == 0,
            .unsigned => !a.positive or r.eqlZero(),
        };
    }
}