# ===== HELPER FUNCTIONS ==========================================================================
# Asserts that both values at the top of the stack are u64 values.
# The input values are assumed to be represented using 32 bit limbs, fails if they are not.
proc.u32assert4
u32assert.2
movup.3
movup.3
u32assert.2
movup.3
movup.3
end
# ===== ADDITION ==================================================================================
# Performs addition of two unsigned 64 bit integers preserving the overflow.
# The input values are assumed to be represented using 32 bit limbs, but this is not checked.
# Stack transition looks as follows:
# [b_hi, b_lo, a_hi, a_lo, ...] -> [overflowing_flag, c_hi, c_lo, ...], where c = (a + b) % 2^64
export.overflowing_add
swap
movup.3
u32overflowing_add
movup.3
movup.3
u32overflowing_add3
end
# Performs addition of two unsigned 64 bit integers discarding the overflow.
# The input values are assumed to be represented using 32 bit limbs, but this is not checked.
# Stack transition looks as follows:
# [b_hi, b_lo, a_hi, a_lo, ...] -> [c_hi, c_lo, ...], where c = (a + b) % 2^64
export.wrapping_add
exec.overflowing_add
drop
end
# Performs addition of two unsigned 64 bit integers, fails when overflowing.
# The input values are assumed to be represented using 32 bit limbs, fails if they are not.
# Stack transition looks as follows:
# [b_hi, b_lo, a_hi, a_lo, ...] -> [c_hi, c_lo, ...], where c = (a + b) % 2^64
export.checked_add
swap
movup.3
u32assert.2
u32overflowing_add
movup.3
movup.3
u32assert.2
u32overflowing_add3
eq.0
assert
end
# ===== SUBTRACTION ===============================================================================
# Performs subtraction of two unsigned 64 bit integers discarding the overflow.
# The input values are assumed to be represented using 32 bit limbs, but this is not checked.
# Stack transition looks as follows:
# [b_hi, b_lo, a_hi, a_lo, ...] -> [c_hi, c_lo, ...], where c = (a - b) % 2^64
export.wrapping_sub
movup.3
movup.2
u32overflowing_sub
movup.3
movup.3
u32overflowing_sub
drop
swap
u32overflowing_sub
drop
end
# Performs subtraction of two unsigned 64 bit integers, fails when underflowing.
# The input values are assumed to be represented using 32 bit limbs, fails if they are not.
# Stack transition looks as follows:
# [b_hi, b_lo, a_hi, a_lo, ...] -> [c_hi, c_lo, ...], where c = (a - b) % 2^64
export.checked_sub
movup.3
movup.2
u32assert.2
u32overflowing_sub
movup.3
movup.3
u32assert.2
u32overflowing_sub
eq.0
assert
swap
u32overflowing_sub
eq.0
assert
end
# Performs subtraction of two unsigned 64 bit integers preserving the overflow.
# The input values are assumed to be represented using 32 bit limbs, but this is not checked.
# Stack transition looks as follows:
# [b_hi, b_lo, a_hi, a_lo, ...] -> [underflowing_flag, c_hi, c_lo, ...], where c = (a - b) % 2^64
export.overflowing_sub
movup.3
movup.2
u32overflowing_sub
movup.3
movup.3
u32overflowing_sub
swap
movup.2
u32overflowing_sub
movup.2
or
end
# ===== MULTIPLICATION ============================================================================
# Performs multiplication of two unsigned 64 bit integers discarding the overflow.
# The input values are assumed to be represented using 32 bit limbs, but this is not checked.
# Stack transition looks as follows:
# [b_hi, b_lo, a_hi, a_lo, ...] -> [c_hi, c_lo, ...], where c = (a * b) % 2^64
export.wrapping_mul
dup.3
dup.2
u32overflowing_mul
movup.4
movup.4
u32overflowing_madd
drop
movup.3
movup.3
u32overflowing_madd
drop
end
# Performs multiplication of two unsigned 64 bit integers preserving the overflow.
# The input values are assumed to be represented using 32 bit limbs, but this is not checked.
# Stack transition looks as follows:
# [b_hi, b_lo, a_hi, a_lo, ...] -> [c_hi, c_mid_hi, c_mid_lo, c_lo, ...], where c = (a * b) % 2^64
# This takes 18 cycles.
export.overflowing_mul
dup.3
dup.2
u32overflowing_mul
dup.4
movup.4
u32overflowing_madd
swap
movup.5
dup.4
u32overflowing_madd
movup.5
movup.5
u32overflowing_madd
movup.3
movup.2
u32overflowing_add
movup.2
add
end
# Performs multiplication of two unsigned 64 bit integers, fails when overflowing.
# The input values are assumed to be represented using 32 bit limbs, fails if they are not.
# Stack transition looks as follows:
# [b_hi, b_lo, a_hi, a_lo, ...] -> [c_hi, c_lo, ...], where c = (a * b) % 2^64
export.checked_mul
dup.3
dup.2
u32assert.2 # make sure lower limbs of operands are 32-bit
u32overflowing_mul
dup.4
movup.4
u32overflowing_madd
swap
movup.5
dup.4
u32overflowing_madd
movup.5
movup.5
u32assert.2 # make sure higher limbs of operands are 32-bit
u32overflowing_madd
movup.3
movup.2
u32overflowing_add
add
add
eq.0
assert
end
# ===== COMPARISONS ===============================================================================
# Performs less-than comparison of two unsigned 64 bit integers.
# The input values are assumed to be represented using 32 bit limbs, but this is not checked.
# Stack transition looks as follows:
# [b_hi, b_lo, a_hi, a_lo, ...] -> [c, ...], where c = 1 when a < b, and 0 otherwise.
export.unchecked_lt
movup.3
movup.2
u32overflowing_sub
movdn.3
drop
u32overflowing_sub
swap
eq.0
movup.2
and
or
end
# Performs less-than comparison of two unsigned 64 bit integers.
# The input values are assumed to be represented using 32 bit limbs, fails if they are not.
# Stack transition looks as follows:
# [b_hi, b_lo, a_hi, a_lo, ...] -> [c, ...], where c = 1 when a < b, and 0 otherwise.
export.checked_lt
movup.3
movup.2
u32assert.2
u32overflowing_sub
movdn.3
drop
u32assert.2
u32overflowing_sub
swap
eq.0
movup.2
and
or
end
# Performs greater-than comparison of two unsigned 64 bit integers.
# The input values are assumed to be represented using 32 bit limbs, but this is not checked.
# Stack transition looks as follows:
# [b_hi, b_lo, a_hi, a_lo, ...] -> [c, ...], where c = 1 when a > b, and 0 otherwise.
# This takes 11 cycles.
export.unchecked_gt
movup.2
u32overflowing_sub
movup.2
movup.3
u32overflowing_sub
swap
drop
movup.2
eq.0
and
or
end
# Performs greater-than comparison of two unsigned 64 bit integers.
# The input values are assumed to be represented using 32 bit limbs, fails if they are not.
# Stack transition looks as follows:
# [b_hi, b_lo, a_hi, a_lo, ...] -> [c, ...], where c = 1 when a > b, and 0 otherwise.
export.checked_gt
movup.2
u32assert.2
u32overflowing_sub
movup.2
movup.3
u32assert.2
u32overflowing_sub
swap
drop
movup.2
eq.0
and
or
end
# Performs less-than-or-equal comparison of two unsigned 64 bit integers.
# The input values are assumed to be represented using 32 bit limbs, but this is not checked.
# Stack transition looks as follows:
# [b_hi, b_lo, a_hi, a_lo, ...] -> [c, ...], where c = 1 when a <= b, and 0 otherwise.
export.unchecked_lte
exec.unchecked_gt
not
end
# Performs less-than-or-equal comparison of two unsigned 64 bit integers.
# The input values are assumed to be represented using 32 bit limbs, fails if they are not.
# Stack transition looks as follows:
# [b_hi, b_lo, a_hi, a_lo, ...] -> [c, ...], where c = 1 when a <= b, and 0 otherwise.
export.checked_lte
exec.checked_gt
not
end
# Performs greater-than-or-equal comparison of two unsigned 64 bit integers.
# The input values are assumed to be represented using 32 bit limbs, but this is not checked.
# Stack transition looks as follows:
# [b_hi, b_lo, a_hi, a_lo, ...] -> [c, ...], where c = 1 when a >= b, and 0 otherwise.
export.unchecked_gte
exec.unchecked_lt
not
end
# Performs greater-than-or-equal comparison of two unsigned 64 bit integers.
# The input values are assumed to be represented using 32 bit limbs, fails if they are not.
# Stack transition looks as follows:
# [b_hi, b_lo, a_hi, a_lo, ...] -> [c, ...], where c = 1 when a >= b, and 0 otherwise.
export.checked_gte
exec.checked_lt
not
end
# Performs equality comparison of two unsigned 64 bit integers.
# The input values are assumed to be represented using 32 bit limbs, but this is not checked.
# Stack transition looks as follows:
# [b_hi, b_lo, a_hi, a_lo, ...] -> [c, ...], where c = 1 when a == b, and 0 otherwise.
export.unchecked_eq
movup.2
u32checked_eq
swap
movup.2
u32checked_eq
and
end
# Performs equality comparison of two unsigned 64 bit integers.
# The input values are assumed to be represented using 32 bit limbs, fails if they are not.
# Stack transition looks as follows:
# [b_hi, b_lo, a_hi, a_lo, ...] -> [c, ...], where c = 1 when a == b, and 0 otherwise.
export.checked_eq
movup.2
u32checked_eq
swap
movup.2
u32checked_eq
and
end
# Performs inequality comparison of two unsigned 64 bit integers.
# The input values are assumed to be represented using 32 bit limbs, but this is not checked.
# Stack transition looks as follows:
# [b_hi, b_lo, a_hi, a_lo, ...] -> [c, ...], where c = 1 when a != b, and 0 otherwise.
export.unchecked_neq
movup.2
u32checked_neq
swap
movup.2
u32checked_neq
or
end
# Performs inequality comparison of two unsigned 64 bit integers.
# The input values are assumed to be represented using 32 bit limbs, fails if they are not.
# Stack transition looks as follows:
# [b_hi, b_lo, a_hi, a_lo, ...] -> [c, ...], where c = 1 when a == b, and 0 otherwise.
export.checked_neq
exec.checked_eq
not
end
# Performs comparison to zero of an unsigned 64 bit integer.
# The input value is assumed to be represented using 32 bit limbs, but this is not checked.
# Stack transition looks as follows:
# [a_hi, a_lo, ...] -> [c, ...], where c = 1 when a == 0, and 0 otherwise.
export.unchecked_eqz
eq.0
swap
eq.0
and
end
# Performs comparison to zero of an unsigned 64 bit integer.
# The input value is assumed to be represented using 32 bit limbs, fails if it is not.
# Stack transition looks as follows:
# [a_hi, a_lo, ...] -> [c, ...], where c = 1 when a == 0, and 0 otherwise.
export.checked_eqz
u32assert.2
eq.0
swap
eq.0
and
end
# Compares two unsigned 64 bit integers and drop the larger one from the stack.
# The input values are assumed to be represented using 32 bit limbs, but this is not checked.
# Stack transition looks as follows:
# [b_hi, b_lo, a_hi, a_lo, ...] -> [c_hi, c_lo, ...], where c = a when a < b, and b otherwise.
export.unchecked_min
dupw
exec.unchecked_gt
movup.4
movup.3
dup.2
cdrop
movdn.3
cdrop
end
# Compares two unsigned 64 bit integers and drop the larger one from the stack.
# The input values are assumed to be represented using 32 bit limbs, fails if they are not.
# Stack transition looks as follows:
# [b_hi, b_lo, a_hi, a_lo, ...] -> [c_hi, c_lo, ...], where c = a when a < b, and b otherwise.
export.checked_min
exec.u32assert4
exec.unchecked_min
end
# Compares two unsigned 64 bit integers and drop the smaller one from the stack.
# The input values are assumed to be represented using 32 bit limbs, but this is not checked.
# Stack transition looks as follows:
# [b_hi, b_lo, a_hi, a_lo, ...] -> [c_hi, c_lo, ...], where c = a when a > b, and b otherwise.
export.unchecked_max
dupw
exec.unchecked_lt
movup.4
movup.3
dup.2
cdrop
movdn.3
cdrop
end
# Compares two unsigned 64 bit integers and drop the smaller one from the stack.
# The input values are assumed to be represented using 32 bit limbs, fails if they are not.
# Stack transition looks as follows:
# [b_hi, b_lo, a_hi, a_lo, ...] -> [c_hi, c_lo, ...], where c = a when a > b, and b otherwise.
export.checked_max
exec.u32assert4
exec.unchecked_max
end
# ===== DIVISION ==================================================================================
# Performs division of two unsigned 64 bit integers discarding the remainder.
# The input values are assumed to be represented using 32 bit limbs, but this is not checked.
# Stack transition looks as follows:
# [b_hi, b_lo, a_hi, a_lo, ...] -> [c_hi, c_lo, ...], where c = a // b
export.unchecked_div
adv.u64div # inject the quotient and the remainder into the advice tape
push.adv.2 # read the quotient from the advice tape and make sure it consists of
u32assert.2 # 32-bit limbs
dup.3 # multiply quotient by the divisor and make sure the resulting value
dup.2 # fits into 2 32-bit limbs
u32overflowing_mul
dup.4
dup.4
u32overflowing_madd
eq.0
assert
dup.5
dup.3
u32overflowing_madd
eq.0
assert
dup.4
dup.3
mul
eq.0
assert
push.adv.2 # read the remainder from the advice tape and make sure it consists of
u32assert.2 # 32-bit limbs
movup.7 # make sure the divisor is greater than the remainder. this also consumes
movup.7 # the divisor
dup.3
dup.3
exec.unchecked_gt
assert
swap # add remainder to the previous result; this also consumes the remainder
movup.3
u32overflowing_add
movup.3
movup.3
u32overflowing_add3
eq.0
assert
movup.4 # make sure the result we got is equal to the dividend
assert_eq
movup.3
assert_eq # quotient remains on the stack
end
# Performs division of two unsigned 64 bit integers discarding the remainder.
# The input values are assumed to be represented using 32 bit limbs, fails if they are not.
# Stack transition looks as follows:
# [b_hi, b_lo, a_hi, a_lo, ...] -> [c_hi, c_lo, ...], where c = a // b
export.checked_div
exec.u32assert4
exec.unchecked_div
end
# ===== MODULO OPERATION ==========================================================================
# Performs modulo operation of two unsigned 64 bit integers.
# The input values are assumed to be represented using 32 bit limbs, but this is not checked.
# Stack transition looks as follows:
# [b_hi, b_lo, a_hi, a_lo, ...] -> [c_hi, c_lo, ...], where c = a % b
export.unchecked_mod
adv.u64div # inject the quotient and the remainder into the advice tape
push.adv.2 # read the quotient from the advice tape and make sure it consists of
u32assert.2 # 32-bit limbs
dup.3 # multiply quotient by the divisor and make sure the resulting value
dup.2 # fits into 2 32-bit limbs
u32overflowing_mul
dup.4
movup.4
u32overflowing_madd
eq.0
assert
dup.4
dup.3
u32overflowing_madd
eq.0
assert
dup.3
movup.3
mul
eq.0
assert
push.adv.2 # read the remainder from the advice tape and make sure it consists of
u32assert.2 # 32-bit limbs
movup.5 # make sure the divisor is greater than the remainder. this also consumes
movup.5 # the divisor
dup.3
dup.3
exec.unchecked_gt
assert
dup.1 # add remainder to the previous result
movup.4
u32overflowing_add
movup.4
dup.3
u32overflowing_add3
eq.0
assert
movup.4 # make sure the result we got is equal to the dividend
assert_eq
movup.3
assert_eq # remainder remains on the stack
end
# Performs modulo operation of two unsigned 64 bit integers.
# The input values are assumed to be represented using 32 bit limbs, fails if they are not.
# Stack transition looks as follows:
# [b_hi, b_lo, a_hi, a_lo, ...] -> [c_hi, c_lo, ...], where c = a % b
export.checked_mod
exec.u32assert4
exec.unchecked_mod
end
# ===== DIVMOD OPERATION ==========================================================================
# Performs divmod operation of two unsigned 64 bit integers.
# The input values are assumed to be represented using 32 bit limbs, but this is not checked.
# Stack transition looks as follows:
# [b_hi, b_lo, a_hi, a_lo, ...] -> [r_hi, r_lo, q_hi, q_lo ...], where r = a % b, q = a / b
export.unchecked_divmod
adv.u64div # inject the quotient and the remainder into the advice tape
push.adv.2 # read the quotient from the advice tape and make sure it consists of
u32assert.2 # 32-bit limbs
dup.3 # multiply quotient by the divisor and make sure the resulting value
dup.2 # fits into 2 32-bit limbs
u32overflowing_mul
dup.4
dup.4
u32overflowing_madd
eq.0
assert
dup.5
dup.3
u32overflowing_madd
eq.0
assert
dup.4
dup.3
mul
eq.0
assert
push.adv.2 # read the remainder from the advice tape and make sure it consists of
u32assert.2 # 32-bit limbs
movup.7 # make sure the divisor is greater than the remainder. this also consumes
movup.7 # the divisor
dup.3
dup.3
exec.unchecked_gt
assert
dup.1 # add remainder to the previous result
movup.4
u32overflowing_add
movup.4
dup.3
u32overflowing_add3
eq.0
assert
movup.6 # make sure the result we got is equal to the dividend
assert_eq
movup.5
assert_eq # remainder remains on the stack
end
# Performs divmod operation of two unsigned 64 bit integers.
# The input values are assumed to be represented using 32 bit limbs, fails if they are not.
# Stack transition looks as follows:
# [b_hi, b_lo, a_hi, a_lo, ...] -> [r_hi, r_lo, q_hi, q_lo ...], where r = a % b, q = a / b
export.checked_divmod
exec.u32assert4
exec.unchecked_divmod
end
# ===== BITWISE OPERATIONS ========================================================================
# Performs bitwise AND of two unsigned 64-bit integers.
# The input values are assumed to be represented using 32 bit limbs, but this is not checked.
# Stack transition looks as follows:
# [b_hi, b_lo, a_hi, a_lo, ...] -> [c_hi, c_lo, ...], where c = a AND b.
export.checked_and
swap
movup.3
u32checked_and
swap
movup.2
u32checked_and
end
# Performs bitwise OR of two unsigned 64 bit integers.
# The input values are assumed to be represented using 32 bit limbs, fails if they are not.
# Stack transition looks as follows:
# [b_hi, b_lo, a_hi, a_lo, ...] -> [c_hi, c_lo, ...], where c = a OR b.
export.checked_or
swap
movup.3
u32checked_or
swap
movup.2
u32checked_or
end
# Performs bitwise XOR of two unsigned 64 bit integers.
# The input values are assumed to be represented using 32 bit limbs, fails if they are not.
# Stack transition looks as follows:
# [b_hi, b_lo, a_hi, a_lo, ...] -> [c_hi, c_lo, ...], where c = a XOR b.
export.checked_xor
swap
movup.3
u32checked_xor
swap
movup.2
u32checked_xor
end
# Performs left shift of one unsigned 64-bit integer using the pow2 operation.
# The input value to be shifted is assumed to be represented using 32 bit limbs.
# The shift value is assumed to be in the range [0, 64).
# Stack transition looks as follows:
# [b, a_hi, a_lo, ...] -> [c_hi, c_lo, ...], where c = a << b mod 2^64.
# This takes 50 cycles.
export.unchecked_shl
unchecked_pow2
u32split
exec.wrapping_mul
end
# Performs right shift of one unsigned 64-bit integer using the pow2 operation.
# The input value to be shifted is assumed to be represented using 32 bit limbs.
# The shift value is assumed to be in the range [0, 64).
# Stack transition looks as follows:
# [b, a_hi, a_lo, ...] -> [c_hi, c_lo, ...], where c = a >> b.
# This takes 66 cycles.
export.unchecked_shr
unchecked_pow2
u32split
dup.1
add
movup.2
swap
u32unchecked_divmod
movup.3
movup.3
dup
eq.0
u32overflowing_sub
not
movdn.4
dup
movdn.4
u32unchecked_divmod
drop
push.4294967296
dup.5
mul
movup.4
div
movup.2
mul
add
movup.2
cswap
end
# Performs left shift of one unsigned 64-bit integer preserving the overflow and
# using the pow2 operation.
# The input value to be shifted is assumed to be represented using 32 bit limbs.
# The shift value is assumed to be in the range [0, 64).
# Stack transition looks as follows:
# [b, a_hi, a_lo, ...] -> [d_hi, d_lo, c_hi, c_lo, ...], where (d,c) = a << b,
# which d contains the bits shifted out.
# This takes 57 cycles.
export.overflowing_shl
unchecked_pow2
u32split
exec.overflowing_mul
end
# Performs right shift of one unsigned 64-bit integer preserving the overflow and
# using the pow2 operation.
# The input value to be shifted is assumed to be represented using 32 bit limbs.
# The shift value is assumed to be in the range [0, 64).
# Stack transition looks as follows:
# [b, a_hi, a_lo, ...] -> [d_hi, d_lo, c_hi, c_lo, ...], where c = a >> b, d = a << (64 - b).
# This takes 138 cycles.
export.overflowing_shr
push.64 # (64 - b)
dup.1
sub
dup.3 # dup [b, a_hi, a_lo]
dup.3
dup.3
exec.unchecked_shr # c = a >> b
movdn.5 # move result [c_hi, c_lo] to be in the format [d_hi, d_lo, c_hi, c_lo, ...]
movdn.5
padw # padding positions 0, 1, 2, 3 and 4 to be able to use cdropw
push.0
movup.6 # bring and b
eq.0
cdropw # if b is 0, swap the positions 0, 1, 2 and 3 with 0, (64 - b), a_hi, a_lo
# regardless of this condition, drop 0, 1, 2 and 3
drop # drop the last added 0 or dup b to keep the format [b, a_hi, a_lo, ....]
exec.unchecked_shl # d = a << (64 - b)
end
# Performs left rotation of one unsigned 64-bit integer using the pow2 operation.
# The input value to be shifted is assumed to be represented using 32 bit limbs.
# The shift value is assumed to be in the range [0, 64).
# Stack transition looks as follows:
# [b, a_hi, a_lo, ...] -> [c_hi, c_lo, ...], where c = a << b mod 2^64.
# This takes 57 cycles.
export.unchecked_rotl
push.31
dup.1
u32overflowing_sub
swap
drop
movdn.3
# Shift the low limb.
push.31
u32checked_and
unchecked_pow2
dup
movup.3
u32overflowing_mul
# Shift the high limb.
movup.3
movup.3
u32overflowing_madd
# Carry the overflow shift to the low bits.
movup.2
add
swap
# Conditionally select the limb order based on whether it's shifting by > 31 or not.
movup.2
cswap
end
# Performs right rotation of one unsigned 64-bit integer using the pow2 operation.
# The input value to be shifted is assumed to be represented using 32 bit limbs.
# The shift value is assumed to be in the range [0, 64).
# Stack transition looks as follows:
# [b, a_hi, a_lo, ...] -> [c_hi, c_lo, ...], where c = a << b mod 2^64.
# This takes 62 cycles.
export.unchecked_rotr
push.31
dup.1
u32overflowing_sub
swap
drop
movdn.3
# Shift the low limb left by 32-b.
push.31
u32checked_and
push.32
swap
u32overflowing_sub
drop
unchecked_pow2
dup
movup.3
u32overflowing_mul
# Shift the high limb left by 32-b.
movup.3
movup.3
u32overflowing_madd
# Carry the overflow shift to the low bits.
movup.2
add
swap
# Conditionally select the limb order based on whether it's shifting by > 31 or not.
movup.2
not
cswap
end