Function calculate_carry_bits

ciphercore-base/src/ops/adder.rs:284–329

This function generates a graph for the "segment tree" to calculate carry bits. It assumes both `propagate_bits` and `generate_bits` are arrays with bits dimension pulled out to the outermost level. It also assumes the number of bits is a power of two. Each node of the segment tree labeled `ij` stores two bits `(propagate, generate)` that are used to compute carry[j+1] given carry[i], as `genera

(
    propagate_bits: Node,
    generate_bits: Node,
    overflow_bit: bool,
)

/// (carry[0..n-1], None) tuple if overflow_bit=false,
/// representing carry bits and the overflow bit.
fn calculate_carry_bits(
    propagate_bits: Node,
    generate_bits: Node,
    overflow_bit: bool,
) -> Result<(Node, Option<Node>)> {
    let graph = propagate_bits.get_graph();

    let mut nodes = vec![CarryNode {
        propagate: propagate_bits,
        generate: generate_bits,
    }];
    let bit_len = nodes[0].bit_len()?;
    if !bit_len.is_power_of_two() {
        return Err(runtime_error!("BinaryAdd only supports numbers with number of bits, which is a power of 2. {} bits provided.", bit_len));
    }
    let mut shape = nodes[0].propagate.get_type()?.get_shape();
    shape[0] = 1;
    let mut carries = graph.zeros(array_type(shape, BIT))?;
    // Two special cases for the overflow_bit=false optimization:
    // If the input is 1 bit long: ignore input and just return zero:
    if !overflow_bit && bit_len == 1 {
        return Ok((carries, None));
    }
    // If the input is 2 bits long: we must not join the two nodes on the initial layer.
    if overflow_bit || bit_len > 2 {
        while nodes.last().unwrap().bit_len()? > 1 {
            let last = nodes.last().unwrap();
            nodes.push(last.shrink(overflow_bit)?);
        }
    }

    let mut node_rev_iter = nodes.iter().rev();
    let overflow_bit = if overflow_bit {
        let root_node = node_rev_iter.next().unwrap();
        Some(root_node.apply(carries.clone())?)
    } else {
        None
    };
    for node in node_rev_iter {
        let lower = node.sub_slice(0, node.bit_len()? as i64)?;
        let new_carries = lower.apply(carries.clone())?;
        carries = interleave(carries, new_carries)?;
    }

    Ok((carries, overflow_bit))
}

#[cfg(test)]
mod tests {