add32_bits
stdlib/bits/add32_bits.nbv
add32_bits(sum, static terms)
Word-wise sum mod 2^32 of terms equal length vectors of 32-bit words, each word 32 little-endian bits, passed as their element-wise sum sum (e.g. a + b + c with terms 3). The summed vectors must be bits, outputs are fresh constrained bits.
Each word is summed as two 16-bit limbs of 16 + log2(terms) bits, so the equations hold over the integers in any field of more than 2^18 elements for up to 4 terms. Per word: 2 (16 + log2(terms)) booleanity rows and an equality per limb, 36 rows for two terms and 38 for three.
- Calls
bits/from_bits,slice,bits/to_bits_exact- Precompiles
assert_eq!,clone!,concat!,div_exact!,len!,log2_ceil!,loop_flat_map!,modulo!- Used by
blake3/blake3_g,chacha/chacha_block,chacha/chacha_quarter_round
Source
# Word-wise sum mod 2^32 of `terms` equal length vectors of 32-bit words, each
# word 32 little-endian bits, passed as their element-wise sum `sum` (e.g.
# `a + b + c` with terms 3). The summed vectors must be bits, outputs are
# fresh constrained bits.
#
# Each word is summed as two 16-bit limbs of 16 + log2(terms) bits, so the
# equations hold over the integers in any field of more than 2^18 elements
# for up to 4 terms. Per word: 2 (16 + log2(terms)) booleanity rows and an
# equality per limb, 36 rows for two terms and 38 for three.
(sum, static terms)
static n = len! sum
assert_eq! 0, (modulo! n, 32)
static width = 16 + (log2_ceil! terms)
loop_flat_map! (div_exact! n, 32), w {
# bits 16.. of each limb are its carry, the carry out of the high limb is
# dropped
let lo = to_bits_exact(from_bits(slice((clone! sum), 32 * w, 16)), width)
let hi = to_bits_exact(from_bits(slice((clone! sum), 32 * w + 16, 16)) + from_bits(slice((clone! lo), 16, width - 16)), width)
concat! slice(lo, 0, 16), slice(hi, 0, 16)
}