dymokomi/luce-browser-foundation
Source of release 0.6.1
0.6.1 / src / ak / u_fixed_big_int_1.lucb
#==============================================================================================
#
# u_fixed_big_int_1 - the word and storage operations under UFixedBigInt
#
# DESCRIPTION:
# Port of the parts of AK/BigIntBase.h (lines 154-677: IntegerWrapper, add_words,
# sub_words, wide_multiply, dword, div_mod_words and the unsigned StorageOperations)
# and AK/UFixedBigIntDivision.h (lines 1-80) that AK/UFixedBigInt.h is built on. No
# region owns BigIntBase.h, so these are private helpers of the UFixedBigInt port.
#
# Storages are spans of u64 words, least significant first, as on the donor's 64-bit
# targets (NativeWord is u64). UFixedBigInt only uses unsigned storages, so the sign
# extension of the donor's signed storages is not needed. There is no 128-bit type:
# NativeDoubleWord arithmetic is done on (low, high) word pairs, and the 128/64
# division of div_mod_words is Hacker's Delight's divlu.
#
#==============================================================================================
# mark: IntegerWrapper ==========================================================================
## BigIntBase.h:160 AK::Detail::IntegerWrapper::IntegerWrapper(int): a non-negative int as a
## one-word storage (the donor rejects a negative value at compile time; here it traps).
pub func integer_wrapper(value: i32) -> IntegerWrapper:
assert(value >= 0, "Requested implicit conversion of an integer to the unsigned one will underflow.")
return IntegerWrapper(m_data = [(u64)value])
# mark: Words ===================================================================================
# BigIntBase.h:189 add_words: word1 + word2 + carry, with the carry out.
func add_words(word1: u64, word2: u64, carry: bool*) -> u64:
var output = word1 +% word2
var ncarry = output < word1
if *carry:
output = output +% 1
if output == 0:
ncarry = true
*carry = ncarry
return output
# BigIntBase.h:232 sub_words: word1 - word2 - carry, with the borrow out.
func sub_words(word1: u64, word2: u64, carry: bool*) -> u64:
var output = word1 -% word2
var ncarry = word2 > word1
if *carry:
if output == 0:
ncarry = true
output = output -% 1
*carry = ncarry
return output
# BigIntBase.h:275 wide_multiply: the double word word1 * word2 as (low, high).
func wide_multiply_words(word1: u64, word2: u64) -> (u64, u64):
let a_low = word1 & 0xffffffff
let a_high = word1 >> 32
let b_low = word2 & 0xffffffff
let b_high = word2 >> 32
let low_low = a_low * b_low
let low_high = a_low * b_high
let high_low = a_high * b_low
let high_high = a_high * b_high
let middle = (low_low >> 32) + (low_high & 0xffffffff) + (high_low & 0xffffffff)
let low = (middle << 32) | (low_low & 0xffffffff)
let high = high_high + (low_high >> 32) + (high_low >> 32) + (middle >> 32)
return (low, high)
# Compare two double words given as (low, high): whether a > b.
func dword_greater(a_low: u64, a_high: u64, b_low: u64, b_high: u64) -> bool:
if a_high != b_high:
return a_high > b_high
return a_low > b_low
# BigIntBase.h:290 div_mod_words: ((dividend_high << 64) + dividend_low) / divisor; the quotient
# must fit in a word (dividend_high < divisor).
func div_mod_words(dividend_low: u64, dividend_high: u64, divisor: u64, remainder: u64*) -> u64:
assert(dividend_high < divisor)
let s = (u64)count_leading_zeroes_u64(divisor)
let v = divisor << s
let vn1 = v >> 32
let vn0 = v & 0xffffffff
let un32 = (dividend_high << s) | ((dividend_low >> (64 - s)) if s > 0 else 0)
let un10 = dividend_low << s
let un1 = un10 >> 32
let un0 = un10 & 0xffffffff
var q1 = un32 // vn1
var rhat = un32 - q1 * vn1
while q1 >= 0x100000000 or q1 *% vn0 > ((rhat << 32) | un1):
q1 -= 1
rhat += vn1
if rhat >= 0x100000000:
break
let un21 = ((un32 << 32) | un1) -% q1 *% v
var q0 = un21 // vn1
rhat = un21 - q0 * vn1
while q0 >= 0x100000000 or q0 *% vn0 > ((rhat << 32) | un0):
q0 -= 1
rhat += vn1
if rhat >= 0x100000000:
break
*remainder = (((un21 << 32) | un0) -% q0 *% v) >> s
return (q1 << 32) | q0
# BuiltinWrappers.h popcount for a word.
func popcount_u64(value: u64) -> usize:
var count: usize = 0
var bits = value
while bits != 0:
bits = bits & (bits - 1)
count += 1
return count
# BuiltinWrappers.h count_trailing_zeroes for a nonzero word.
func count_trailing_zeroes_u64(value: u64) -> usize:
assert(value != 0)
var count: usize = 0
var bits = value
while (bits & 1) == 0:
bits = bits >> 1
count += 1
return count
# mark: StorageOperations =======================================================================
# BigIntBase.h:305 StorageOperations::copy (unsigned storages: the fill is zero).
func storage_copy(operand: const u64[], result: u64[], offset: usize = 0):
let size1 = operand.length
for i in 0..<result.length:
result[i] = operand[i + offset] if i + offset < size1 else 0
# BigIntBase.h:314 StorageOperations::set.
func storage_set(value: u64, result: u64[]):
result[0] = value
for i in 1..<result.length:
result[i] = 0
# BigIntBase.h:322 StorageOperations::compare (unsigned storages).
# `is_for_inequality' is a hint to compiler that we do not need to differentiate between < and >.
func storage_compare(operand1: const u64[], operand2: const u64[], is_for_inequality: bool) -> i32:
let size1 = operand1.length
let size2 = operand2.length
var differ_in_high_bits = false
if size1 > size2:
var i = size1
while i > size2:
i -= 1
if operand1[i] != 0:
differ_in_high_bits = true
elif size1 < size2:
var i = size2
while i > size1:
i -= 1
if operand2[i] != 0:
differ_in_high_bits = true
if differ_in_high_bits:
return 1 if size1 > size2 else -1
var i = size2 if size1 > size2 else size1
while i > 0:
i -= 1
let word1 = operand1[i]
let word2 = operand2[i]
if is_for_inequality:
if word1 != word2:
return 1
else:
if word1 > word2:
return 1
if word1 < word2:
return -1
return 0
# BigIntBase.h:370 StorageOperations::Bitwise.
enum StorageBitwise as u8:
and_ = 0
or_ = 1
xor_ = 2
invert = 3
# BigIntBase.h:379 StorageOperations::compute_bitwise.
func storage_compute_bitwise(operation: StorageBitwise, operand1: const u64[], operand2: const u64[], result: u64[]):
let size1 = operand1.length
let size2 = operand2.length
for i in 0..<result.length:
let word1: u64 = operand1[i] if i < size1 else 0
let word2: u64 = operand2[i] if i < size2 else 0
match operation:
.and_: result[i] = word1 & word2
.or_: result[i] = word1 | word2
.xor_: result[i] = word1 ^ word2
_: result[i] = ~word1
# BigIntBase.h:407 StorageOperations::compute_inplace_bitwise.
func storage_compute_inplace_bitwise(operation: StorageBitwise, operand2: const u64[], result: u64[]):
let min_size = result.length if result.length < operand2.length else operand2.length
for i in 0..<min_size:
match operation:
.and_: result[i] = result[i] & operand2[i]
.or_: result[i] = result[i] | operand2[i]
_: result[i] = result[i] ^ operand2[i]
# BigIntBase.h:426 StorageOperations::shift_left.
# Requirements for the next two functions:
# - shift < result.size() * word_size;
# - result.size() == operand.size().
func storage_shift_left(operand: const u64[], shift: usize, result: u64[]):
let size = operand.length
let offset = shift // 64
let remainder = (u64)(shift % 64)
if shift % 64 == 0:
var i = size
while i > offset:
i -= 1
result[i] = operand[i - offset]
for j in 0..<offset:
result[j] = 0
else:
var i = size - 1
while i > offset:
result[i] = (operand[i - offset] << remainder) | (operand[i - offset - 1] >> (64 - remainder))
i -= 1
result[offset] = operand[0] << remainder
for j in 0..<offset:
result[j] = 0
# BigIntBase.h:445 StorageOperations::shift_right.
func storage_shift_right(operand: const u64[], shift: usize, result: u64[]):
let size = operand.length
let offset = shift // 64
let remainder = (u64)(shift % 64)
if shift % 64 == 0:
for i in 0..<size - offset:
result[i] = operand[i + offset]
for i in size - offset..<size:
result[i] = 0
else:
for i in 0..<size - offset - 1:
result[i] = (operand[i + offset] >> remainder) | (operand[i + offset + 1] << (64 - remainder))
result[size - offset - 1] = operand[size - 1] >> remainder
for i in size - offset..<size:
result[i] = 0
# BigIntBase.h:474 StorageOperations::add (unsigned storages).
# Return value: 0 iff no overflow has happened (the carry or borrow out of the result).
func storage_add(subtract: bool, operand1: const u64[], operand2: const u64[], result: u64[], carry_in: bool = false) -> i32:
var carry = carry_in
let size1 = operand1.length
let size2 = operand2.length
for i in 0..<result.length:
let word1: u64 = operand1[i] if i < size1 else 0
let word2: u64 = operand2[i] if i < size2 else 0
if not subtract:
result[i] = add_words(word1, word2, &carry)
else:
result[i] = sub_words(word1, word2, &carry)
if not subtract:
return (i32)carry
return -(i32)carry
# BigIntBase.h:498 StorageOperations::increment (unsigned storages).
func storage_increment(subtract: bool, operand: u64[]) -> i32:
var carry = true
for i in 0..<operand.length:
if not subtract:
operand[i] = add_words(operand[i], 0, &carry)
else:
operand[i] = sub_words(operand[i], 0, &carry)
if not subtract:
return (i32)carry
return -(i32)carry
# BigIntBase.h:532 StorageOperations::baseline_mul (unsigned operands: no sign normalization,
# no allocation).
func storage_baseline_mul(operand1: const u64[], operand2: const u64[], result: u64[]):
var size1 = operand1.length
var size2 = operand2.length
let size = result.length
if size1 == 1 and size2 == 1:
# We do not want to compete with the cleverness of the compiler of multiplying NativeWords.
let (low, high) = wide_multiply_words(operand1[0], operand2[0])
result[0] = low
if size > 1:
result[1] = high
for i in 2..<size:
result[i] = 0
return
if size1 < size2:
storage_baseline_mul(operand2, operand1, result)
return
# Now size1 >= size2
size1 = size1 if size1 < size else size
size2 = size2 if size2 < size else size
# Do schoolbook O(size1 * size2).
# The double-word carry is kept as (carry_low, carry_high).
var carry_low: u64 = 0
var carry_high: u64 = 0
for i in 0..<size:
result[i] = carry_low
carry_low = carry_high
carry_high = 0
let start_index = i - size2 + 1 if i >= size2 else 0
let end_index = i + 1 if i + 1 < size1 else size1
var j = start_index
while j < end_index:
let (x_low, x_high) = wide_multiply_words(operand1[j], operand2[i - j])
var ncarry = false
result[i] = add_words(result[i], x_low, &ncarry)
# carry += (x >> word_size) + ncarry
var c = false
carry_low = add_words(carry_low, x_high, &c)
carry_high = carry_high + (u64)c
c = false
carry_low = add_words(carry_low, (u64)ncarry, &c)
carry_high = carry_high + (u64)c
j += 1
# The is_qhat_too_large lambda of div_mod_internal: qhat * divisor_second > dword(dividend_low, rhat).
func knuth_is_qhat_too_large(qhat: u64, divisor_second: u64, dividend_low: u64, rhat: u64) -> bool:
let (product_low, product_high) = wide_multiply_words(qhat, divisor_second)
return dword_greater(product_low, product_high, dividend_low, rhat)
# BigIntBase.h:614 StorageOperations::div_mod_internal: Knuth's algorithm D on normalized
# copies. `dividend` has at least dividend_len + 1 words.
func storage_div_mod_internal(restore_remainder: bool, dividend: u64[], divisor: u64[], quotient: u64[], remainder: u64[], dividend_len: usize, divisor_len: usize):
# Knuth's algorithm D
# D1. Normalize
let shift = (usize)count_leading_zeroes_u64(divisor[divisor_len - 1])
storage_shift_left(dividend, shift, dividend)
storage_shift_left(divisor, shift, divisor)
let divisor_approx = divisor[divisor_len - 1]
var i = dividend_len + 1
while i > divisor_len:
i -= 1
# D3. Calculate qhat
var qhat: u64
assert(dividend[i] <= divisor_approx)
if dividend[i] == divisor_approx:
qhat = u64_max
else:
var rhat: u64 = 0
qhat = div_mod_words(dividend[i - 1], dividend[i], divisor_approx, &rhat)
if knuth_is_qhat_too_large(qhat, divisor[divisor_len - 2], dividend[i - 2], rhat):
qhat -= 1
var carry = false
rhat = add_words(rhat, divisor_approx, &carry)
if not carry and knuth_is_qhat_too_large(qhat, divisor[divisor_len - 2], dividend[i - 2], rhat):
qhat -= 1
# D4. Multiply & subtract
var mul_carry: u64 = 0
var sub_carry = false
for j in 0..<divisor_len:
let (product_low, product_high) = wide_multiply_words(qhat, divisor[j])
var c = false
let mul_low = add_words(product_low, mul_carry, &c)
let mul_high = product_high + (u64)c
let index = i + j - divisor_len
dividend[index] = sub_words(dividend[index], mul_low, &sub_carry)
mul_carry = mul_high
dividend[i] = sub_words(dividend[i], mul_carry, &sub_carry)
if sub_carry:
# D6. Add back
let dividend_part = dividend[i - divisor_len..<i + 1]
let overflow = storage_add(false, dividend_part, divisor[0..<divisor_len], dividend_part)
assert(overflow == 1)
quotient[i - divisor_len] = qhat - (u64)sub_carry
for j in dividend_len - divisor_len + 1..<quotient.length:
quotient[j] = 0
# D8. Unnormalize
if restore_remainder:
storage_shift_right(dividend[0..<remainder.length], shift, remainder)
# The largest UFixedBigInt (u4096) in words, plus the extra word Knuth's algorithm needs.
let max_big_int_words: usize = 65
## Ported from AK/UFixedBigIntDivision.h:15 AK::Detail::div_mod_internal: quotient and
## (when `restore_remainder`) remainder of operand1 / operand2.
pub func div_mod_internal(restore_remainder: bool, operand1: const u64[], operand2: const u64[], quotient: u64[], remainder: u64[]):
var dividend_len = operand1.length
var divisor_len = operand2.length
while divisor_len > 0 and operand2[divisor_len - 1] == 0:
divisor_len -= 1
while dividend_len > 0 and operand1[dividend_len - 1] == 0:
dividend_len -= 1
# FIXME: Should raise SIGFPE instead
assert(divisor_len != 0) # VERIFY(divisor != 0)
# Fast paths
if divisor_len == 1 and operand2[0] == 1: # divisor == 1
storage_copy(operand1, quotient)
if restore_remainder:
storage_set(0, remainder)
return
if dividend_len < divisor_len: # dividend < divisor
storage_set(0, quotient)
if restore_remainder:
storage_copy(operand1, remainder)
return
if divisor_len == 1 and dividend_len == 1: # NativeWord / NativeWord
storage_set(operand1[0] // operand2[0], quotient)
if restore_remainder:
storage_set(operand1[0] % operand2[0], remainder)
return
if divisor_len == 1: # BigInt by NativeWord
# u = dword(operand1[len - 2], operand1[len - 1]); top = u / divisor; carry = u % divisor
let divisor = operand2[0]
let top_high = operand1[dividend_len - 1] // divisor
var carry: u64 = 0
let top_low = div_mod_words(operand1[dividend_len - 2], operand1[dividend_len - 1] % divisor, divisor, &carry)
quotient[dividend_len - 1] = top_high
quotient[dividend_len - 2] = top_low
var i = dividend_len - 2
while i > 0:
i -= 1
quotient[i] = div_mod_words(operand1[i], carry, divisor, &carry)
for j in dividend_len..<quotient.length:
quotient[j] = 0
if restore_remainder:
storage_set(carry, remainder)
return
# Knuth's algorithm D
assert(operand1.length + 1 <= max_big_int_words and operand2.length <= max_big_int_words)
var dividend_storage: u64[65]
let dividend = dividend_storage[0..<operand1.length + 1]
storage_copy(operand1, dividend)
var divisor_storage: u64[65]
let divisor = divisor_storage[0..<operand2.length]
storage_copy(operand2, divisor)
storage_div_mod_internal(restore_remainder, dividend, divisor, quotient, remainder, dividend_len, divisor_len)