Index Mathematics Conjectures nbv lettuce Widgets

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)
}