llshr

Performs r = a >> shift and returns the amount of limbs affected

if a and r overlaps, then r.ptr <= a.ptr is asserted r must have the capacity to store a >> shift

See tests below for examples of behaviour

Function parameters

Parameters

r:[]Limb
a:[]const Limb
shift: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

fn llshr(r: []Limb, a: []const Limb, shift: usize) usize {
    if (slicesOverlap(a, r))
        std.debug.assert(@intFromPtr(r.ptr) <= @intFromPtr(a.ptr));

    if (a.len == 0) return 0;

    if (shift == 0) {
        std.debug.assert(r.len >= a.len);

        if (a.ptr != r.ptr) @memmove(r[0..a.len], a);
        return a.len;
    }
    if (shift >= limb_bits) {
        if (shift / limb_bits >= a.len) {
            r[0] = 0;
            return 1;
        }
        return llshr(r, a[shift / limb_bits ..], shift % limb_bits);
    }

    // shift is guaranteed to be < limb_bits
    const bit_shift: Log2Limb = @truncate(shift);
    const opposite_bit_shift: Log2Limb = @truncate(limb_bits - bit_shift);

    // special case, where there is a risk to set r to 0
    if (a.len == 1) {
        r[0] = a[0] >> bit_shift;
        return 1;
    }
    if (a.len == 0) {
        r[0] = 0;
        return 1;
    }

    // if the most significant limb becomes 0 after the shift
    const shrink = a[a.len - 1] >> bit_shift == 0;
    std.debug.assert(r.len >= a.len - @intFromBool(shrink));

    var i: usize = 0;
    while (i < a.len - 1) : (i += 1) {
        r[i] = (a[i] >> bit_shift) | (a[i + 1] << opposite_bit_shift);
    }

    if (!shrink)
        r[i] = a[i] >> bit_shift;

    return a.len - @intFromBool(shrink);
}