use std::collections::HashMap;
use std::rc::Rc;
use std::time::Instant;
use crate::bv::{Bv, Cmp, Node, Op};
use crate::sat::Cnf;
#[derive(Clone, PartialEq, Eq, Hash)]
struct ShapeKey {
tag: u8,
width: u32,
arg: u128,
kids: Vec<usize>,
}
fn op_tag(op: Op) -> u128 {
match op {
Op::And => 0,
Op::Or => 1,
Op::Xor => 2,
Op::Add => 3,
Op::Sub => 4,
Op::Mul => 5,
Op::Udiv => 6,
Op::Urem => 7,
Op::Sdiv => 8,
Op::Srem => 9,
}
}
fn cmp_tag(cmp: Cmp) -> u128 {
match cmp {
Cmp::Eq => 0,
Cmp::Ne => 1,
Cmp::Ult => 2,
Cmp::Ule => 3,
Cmp::Slt => 4,
Cmp::Sle => 5,
}
}
pub(crate) struct Blaster<'b> {
pub cnf: Cnf<'b>,
true_lit: i32,
memo: HashMap<usize, Vec<i32>>,
canon: HashMap<usize, usize>,
shapes: HashMap<ShapeKey, usize>,
struct_memo: HashMap<usize, Vec<i32>>,
pub var_bits: HashMap<usize, Vec<i32>>,
pub deadline: Option<Instant>,
}
impl<'b> Blaster<'b> {
pub fn new(bump: &'b bumpalo::Bump) -> Self {
let mut cnf = Cnf::new(bump);
let true_lit = cnf.new_var();
cnf.add_clause(&[true_lit]); Self {
cnf,
true_lit,
memo: HashMap::new(),
canon: HashMap::new(),
shapes: HashMap::new(),
struct_memo: HashMap::new(),
var_bits: HashMap::new(),
deadline: None,
}
}
fn over(&self) -> bool {
self.deadline.is_some_and(|d| Instant::now() >= d)
}
fn t(&self) -> i32 {
self.true_lit
}
fn f(&self) -> i32 {
-self.true_lit
}
pub fn declare_var(&mut self, id: usize, width: u32) {
if self.var_bits.contains_key(&id) {
return;
}
let bits: Vec<i32> = (0..width).map(|_| self.cnf.new_var()).collect();
self.var_bits.insert(id, bits);
}
fn canon_id(&mut self, bv: &Bv) -> usize {
let ptr = Rc::as_ptr(&bv.0) as usize;
if let Some(&id) = self.canon.get(&ptr) {
return id;
}
let width = bv.width();
let (tag, arg, kids) = match &*bv.0 {
Node::Const(_, v) => (0, *v, Vec::new()),
Node::Var(_, id) => (1, *id as u128, Vec::new()),
Node::Not(x) => (2, 0, vec![self.canon_id(x)]),
Node::Neg(x) => (3, 0, vec![self.canon_id(x)]),
Node::Bin(op, x, y) => {
let (mut l, mut r) = (self.canon_id(x), self.canon_id(y));
if matches!(op, Op::And | Op::Or | Op::Xor | Op::Add | Op::Mul) && l > r {
std::mem::swap(&mut l, &mut r);
}
(4, op_tag(*op), vec![l, r])
}
Node::ShlC(x, k) => (5, *k as u128, vec![self.canon_id(x)]),
Node::ShrC(x, k, arith) => (
6,
(*k as u128) | ((u128::from(*arith)) << 32),
vec![self.canon_id(x)],
),
Node::ShlV(x, k) => (7, 0, vec![self.canon_id(x), self.canon_id(k)]),
Node::ShrV(x, k, arith) => (
8,
u128::from(*arith),
vec![self.canon_id(x), self.canon_id(k)],
),
Node::RotC(x, k, left) => (
9,
(*k as u128) | ((u128::from(*left)) << 32),
vec![self.canon_id(x)],
),
Node::RotV(x, k, left) => (
10,
u128::from(*left),
vec![self.canon_id(x), self.canon_id(k)],
),
Node::Compare(cmp, x, y) => {
let (mut l, mut r) = (self.canon_id(x), self.canon_id(y));
if matches!(cmp, Cmp::Eq | Cmp::Ne) && l > r {
std::mem::swap(&mut l, &mut r);
}
(11, cmp_tag(*cmp), vec![l, r])
}
Node::Zext(x, to) => (12, *to as u128, vec![self.canon_id(x)]),
Node::Sext(x, to) => (13, *to as u128, vec![self.canon_id(x)]),
Node::Extract(x, hi, lo) => (
14,
((*hi as u128) << 32) | (*lo as u128),
vec![self.canon_id(x)],
),
Node::Concat(hi, lo) => (15, 0, vec![self.canon_id(hi), self.canon_id(lo)]),
Node::Ite(c, t, e) => (
16,
0,
vec![self.canon_id(c), self.canon_id(t), self.canon_id(e)],
),
};
let key = ShapeKey {
tag,
width,
arg,
kids,
};
let next = self.shapes.len();
let id = *self.shapes.entry(key).or_insert(next);
self.canon.insert(ptr, id);
id
}
fn and(&mut self, a: i32, b: i32) -> i32 {
let (t, f) = (self.true_lit, -self.true_lit);
if a == t {
return b;
}
if b == t {
return a;
}
if a == f || b == f {
return f;
}
if a == b {
return a;
}
if a == -b {
return f;
}
let o = self.cnf.new_var();
self.cnf.add_clause(&[-o, a]);
self.cnf.add_clause(&[-o, b]);
self.cnf.add_clause(&[o, -a, -b]);
o
}
fn or(&mut self, a: i32, b: i32) -> i32 {
let (t, f) = (self.true_lit, -self.true_lit);
if a == t || b == t {
return t;
}
if a == f {
return b;
}
if b == f {
return a;
}
if a == b {
return a;
}
if a == -b {
return t;
}
let o = self.cnf.new_var();
self.cnf.add_clause(&[o, -a]);
self.cnf.add_clause(&[o, -b]);
self.cnf.add_clause(&[-o, a, b]);
o
}
fn xor(&mut self, a: i32, b: i32) -> i32 {
let (t, f) = (self.true_lit, -self.true_lit);
if a == f {
return b;
}
if b == f {
return a;
}
if a == t {
return -b;
}
if b == t {
return -a;
}
if a == b {
return f;
}
if a == -b {
return t;
}
let o = self.cnf.new_var();
self.cnf.add_clause(&[-o, -a, -b]);
self.cnf.add_clause(&[-o, a, b]);
self.cnf.add_clause(&[o, -a, b]);
self.cnf.add_clause(&[o, a, -b]);
o
}
fn full_adder(&mut self, a: i32, b: i32, cin: i32) -> (i32, i32) {
let axb = self.xor(a, b);
let sum = self.xor(axb, cin);
let ab = self.and(a, b);
let axb_cin = self.and(axb, cin);
let cout = self.or(ab, axb_cin);
(sum, cout)
}
fn add_bits(&mut self, a: &[i32], b: &[i32], cin: i32) -> (Vec<i32>, i32) {
let mut carry = cin;
let mut out = Vec::with_capacity(a.len());
for i in 0..a.len() {
let (s, c) = self.full_adder(a[i], b[i], carry);
out.push(s);
carry = c;
}
(out, carry)
}
fn ult_bits(&mut self, a: &[i32], b: &[i32]) -> i32 {
let not_b: Vec<i32> = b.iter().map(|&l| -l).collect();
let (_, cout) = self.add_bits(a, ¬_b, self.t());
-cout
}
fn eq_bits(&mut self, a: &[i32], b: &[i32]) -> i32 {
let mut acc = self.t();
for i in 0..a.len() {
let x = self.xor(a[i], b[i]);
acc = self.and(acc, -x); }
acc
}
pub fn encode(&mut self, bv: &Bv) -> Vec<i32> {
let key = Rc::as_ptr(&bv.0) as usize;
if let Some(bits) = self.memo.get(&key) {
return bits.clone();
}
let shape = self.canon_id(bv);
if let Some(bits) = self.struct_memo.get(&shape) {
self.memo.insert(key, bits.clone());
return bits.clone();
}
let bits = if self.over() || self.cnf.full {
vec![self.f(); bv.width() as usize]
} else {
self.encode_node(bv)
};
self.memo.insert(key, bits.clone());
self.struct_memo.insert(shape, bits.clone());
bits
}
fn encode_node(&mut self, bv: &Bv) -> Vec<i32> {
let w = bv.width() as usize;
match &*bv.0 {
Node::Const(_, v) => (0..w)
.map(|i| {
if (v >> i) & 1 == 1 {
self.t()
} else {
self.f()
}
})
.collect(),
Node::Var(_, id) => {
match self.var_bits.get(id) {
Some(bits) => bits.clone(),
None => {
let bits: Vec<i32> = (0..w).map(|_| self.cnf.new_var()).collect();
self.var_bits.insert(*id, bits.clone());
bits
}
}
}
Node::Not(a) => self.encode(a).iter().map(|&l| -l).collect(),
Node::Neg(a) => {
let ab: Vec<i32> = self.encode(a).iter().map(|&l| -l).collect();
let zero = vec![self.f(); w];
self.add_bits(&ab, &zero, self.t()).0 }
Node::Bin(op, a, b) => {
if matches!(op, Op::Udiv | Op::Urem)
&& let Some(c) = b.as_const()
&& c.is_power_of_two()
{
let ab = self.encode(a);
let k = c.trailing_zeros() as usize;
let f = self.f();
return (0..w)
.map(|i| match op {
Op::Udiv if i + k < w => ab[i + k],
Op::Udiv => f,
_ if i < k => ab[i],
_ => f,
})
.collect();
}
let (ab, bb) = (self.encode(a), self.encode(b));
if matches!(op, Op::Udiv | Op::Urem) {
let f = self.f();
let k = known_zero_high(&ab, f).min(known_zero_high(&bb, f));
if k > 0 && k < w {
let n = w - k;
let (q, r) = self.udivrem_bits(&ab[..n], &bb[..n]);
let mut wide = if matches!(op, Op::Udiv) { q } else { r };
wide.resize(w, f);
let bzero = self.eq_bits(&bb[..n], &vec![f; n]);
let on_zero = if matches!(op, Op::Udiv) {
vec![self.t(); w]
} else {
ab.clone()
};
return self.mux_vec(bzero, &on_zero, &wide);
}
}
match op {
Op::And => (0..w).map(|i| self.and(ab[i], bb[i])).collect(),
Op::Or => (0..w).map(|i| self.or(ab[i], bb[i])).collect(),
Op::Xor => (0..w).map(|i| self.xor(ab[i], bb[i])).collect(),
Op::Add => self.add_bits(&ab, &bb, self.f()).0,
Op::Sub => {
let not_b: Vec<i32> = bb.iter().map(|&l| -l).collect();
self.add_bits(&ab, ¬_b, self.t()).0
}
Op::Mul => self.mul_bits(&ab, &bb),
Op::Udiv => self.udivrem_bits(&ab, &bb).0,
Op::Urem => self.udivrem_bits(&ab, &bb).1,
Op::Sdiv => self.sdiv_bits(&ab, &bb),
Op::Srem => self.srem_bits(&ab, &bb),
}
}
Node::ShlC(a, k) => {
let ab = self.encode(a);
let k = *k as usize;
(0..w)
.map(|i| if i < k { self.f() } else { ab[i - k] })
.collect()
}
Node::ShrC(a, k, arith) => {
let ab = self.encode(a);
let k = *k as usize;
let fill = if *arith { ab[w - 1] } else { self.f() };
(0..w)
.map(|i| if i + k < w { ab[i + k] } else { fill })
.collect()
}
Node::ShlV(a, k) => {
let ab = self.encode(a);
let kb = self.encode(k);
self.shift_var_bits(&ab, &kb, ShKind::Left)
}
Node::ShrV(a, k, arith) => {
let ab = self.encode(a);
let kb = self.encode(k);
let kind = if *arith {
ShKind::Aright
} else {
ShKind::Lright
};
self.shift_var_bits(&ab, &kb, kind)
}
Node::RotC(a, k, left) => {
let ab = self.encode(a);
rot_const(&ab, *k, *left)
}
Node::RotV(a, k, left) => {
let ab = self.encode(a);
let kb = self.encode(k);
self.rot_var_bits(&ab, &kb, *left)
}
Node::Compare(c, a, b) => {
let (ab, bb) = (self.encode(a), self.encode(b));
let bit = match c {
Cmp::Eq => self.eq_bits(&ab, &bb),
Cmp::Ne => -self.eq_bits(&ab, &bb),
Cmp::Ult => self.ult_bits(&ab, &bb),
Cmp::Ule => {
let lt = self.ult_bits(&ab, &bb);
let eq = self.eq_bits(&ab, &bb);
self.or(lt, eq)
}
Cmp::Slt => self.slt_bits(&ab, &bb),
Cmp::Sle => {
let lt = self.slt_bits(&ab, &bb);
let eq = self.eq_bits(&ab, &bb);
self.or(lt, eq)
}
};
vec![bit]
}
Node::Zext(a, _) => {
let mut bits = self.encode(a);
bits.resize(w, self.f());
bits
}
Node::Sext(a, _) => {
let ab = self.encode(a);
let sign = *ab.last().unwrap_or(&self.f());
let mut bits = ab.clone();
bits.resize(w, sign);
bits
}
Node::Extract(a, hi, lo) => {
let ab = self.encode(a);
ab[*lo as usize..=*hi as usize].to_vec()
}
Node::Concat(hi, lo) => {
let mut bits = self.encode(lo);
bits.extend(self.encode(hi));
bits
}
Node::Ite(cond, then, els) => {
let c = self.encode(cond)[0];
let (tb, eb) = (self.encode(then), self.encode(els));
(0..w)
.map(|i| {
let a = self.and(c, tb[i]);
let b = self.and(-c, eb[i]);
self.or(a, b)
})
.collect()
}
}
}
fn slt_bits(&mut self, a: &[i32], b: &[i32]) -> i32 {
let top = a.len() - 1;
let mut aa = a.to_vec();
let mut bb = b.to_vec();
aa[top] = -aa[top];
bb[top] = -bb[top];
self.ult_bits(&aa, &bb)
}
fn mul_bits(&mut self, a: &[i32], b: &[i32]) -> Vec<i32> {
let w = a.len();
let mut acc = vec![self.f(); w];
for (j, &bj) in b.iter().enumerate() {
if self.over() {
return vec![self.f(); w];
}
let mut partial = vec![self.f(); w];
for i in 0..(w - j) {
partial[i + j] = self.and(a[i], bj);
}
acc = self.add_bits(&acc, &partial, self.f()).0;
}
acc
}
fn mux(&mut self, c: i32, t: i32, e: i32) -> i32 {
let (tl, fl) = (self.true_lit, -self.true_lit);
if c == tl {
return t;
}
if c == fl {
return e;
}
if t == e {
return t;
}
if t == tl && e == fl {
return c;
}
if t == fl && e == tl {
return -c;
}
if t == tl {
return self.or(c, e); }
if e == fl {
return self.and(c, t); }
if t == fl {
return self.and(-c, e); }
if e == tl {
return self.or(-c, t); }
let a = self.and(c, t);
let b = self.and(-c, e);
self.or(a, b)
}
fn mux_vec(&mut self, c: i32, t: &[i32], e: &[i32]) -> Vec<i32> {
let mut out = Vec::with_capacity(t.len());
for i in 0..t.len() {
let (ti, ei) = (t[i], e[i]);
out.push(self.mux(c, ti, ei));
}
out
}
fn const_bits(&mut self, v: u64, w: usize) -> Vec<i32> {
(0..w)
.map(|i| {
if (v >> i) & 1 == 1 {
self.t()
} else {
self.f()
}
})
.collect()
}
fn abs_bits(&mut self, a: &[i32]) -> Vec<i32> {
let w = a.len();
let sign = a[w - 1];
let na: Vec<i32> = a.iter().map(|&l| -l).collect();
let zero = vec![self.f(); w];
let neg = self.add_bits(&na, &zero, self.t()).0;
self.mux_vec(sign, &neg, a)
}
fn udivrem_bits(&mut self, a: &[i32], b: &[i32]) -> (Vec<i32>, Vec<i32>) {
let w = a.len();
let mut rem = vec![self.f(); w + 1]; let mut bext = b.to_vec();
bext.push(self.f()); let not_b: Vec<i32> = bext.iter().map(|&l| -l).collect();
let mut quot = vec![self.f(); w];
for i in (0..w).rev() {
if self.over() {
return (vec![self.f(); w], vec![self.f(); w]);
}
let mut shifted = Vec::with_capacity(w + 1);
shifted.push(a[i]);
shifted.extend_from_slice(&rem[0..w]);
rem = shifted;
let (diff, carry) = self.add_bits(&rem, ¬_b, self.t());
let ge = carry; rem = self.mux_vec(ge, &diff, &rem);
quot[i] = ge;
}
(quot, rem[0..w].to_vec())
}
fn sdiv_bits(&mut self, a: &[i32], b: &[i32]) -> Vec<i32> {
let w = a.len();
let (aa, bb) = (self.abs_bits(a), self.abs_bits(b));
let (q, _) = self.udivrem_bits(&aa, &bb);
let nq: Vec<i32> = q.iter().map(|&l| -l).collect();
let zero = vec![self.f(); w];
let neg_q = self.add_bits(&nq, &zero, self.t()).0;
let sign = self.xor(a[w - 1], b[w - 1]);
let quotient = self.mux_vec(sign, &neg_q, &q);
let bzero = self.eq_bits(b, &vec![self.f(); w]);
let one = self.const_bits(1, w);
let all_ones = vec![self.t(); w];
let on_zero = self.mux_vec(a[w - 1], &one, &all_ones);
self.mux_vec(bzero, &on_zero, "ient)
}
fn srem_bits(&mut self, a: &[i32], b: &[i32]) -> Vec<i32> {
let w = a.len();
let (aa, bb) = (self.abs_bits(a), self.abs_bits(b));
let (_, r) = self.udivrem_bits(&aa, &bb);
let nr: Vec<i32> = r.iter().map(|&l| -l).collect();
let zero = vec![self.f(); w];
let neg_r = self.add_bits(&nr, &zero, self.t()).0;
let rem = self.mux_vec(a[w - 1], &neg_r, &r);
let bzero = self.eq_bits(b, &vec![self.f(); w]);
self.mux_vec(bzero, a, &rem)
}
fn shift_var_bits(&mut self, a: &[i32], k: &[i32], kind: ShKind) -> Vec<i32> {
let w = a.len();
let f = self.f();
let stages = shift_stages(w);
let mut cur = a.to_vec();
for j in 0..stages {
if self.over() {
return vec![f; w];
}
let Some(&sel) = k.get(j) else { break };
let sh = 1usize << j;
let mut moved = Vec::with_capacity(w);
for i in 0..w {
moved.push(match kind {
ShKind::Left => {
if i >= sh {
cur[i - sh]
} else {
f
}
}
ShKind::Lright => {
if i + sh < w {
cur[i + sh]
} else {
f
}
}
ShKind::Aright => {
if i + sh < w {
cur[i + sh]
} else {
cur[w - 1]
}
}
});
}
cur = self.mux_vec(sel, &moved, &cur);
}
let mut overflow = f;
for &bit in k.iter().skip(stages) {
overflow = self.or(overflow, bit);
}
if stages > 0 && (1usize << stages) != w {
let low: Vec<i32> = (0..stages)
.map(|j| k.get(j).copied().unwrap_or(f))
.collect();
let wbits = self.const_bits(w as u64, stages);
let ge = -self.ult_bits(&low, &wbits);
overflow = self.or(overflow, ge);
}
let fill = match kind {
ShKind::Aright => a[w - 1],
ShKind::Left | ShKind::Lright => f,
};
let mut out = Vec::with_capacity(w);
for &c in &cur {
out.push(self.mux(overflow, fill, c));
}
out
}
fn rot_var_bits(&mut self, a: &[i32], k: &[i32], left: bool) -> Vec<i32> {
let w = a.len();
let f = self.f();
let stages = shift_stages(w);
if stages == 0 {
return a.to_vec(); }
let amount: Vec<i32> = if (1usize << stages) == w {
(0..stages)
.map(|j| k.get(j).copied().unwrap_or(f))
.collect()
} else {
let m = w.max(k.len());
let mut kext = k.to_vec();
kext.resize(m, f);
let wc = self.const_bits(w as u64, m);
let (_, r) = self.udivrem_bits(&kext, &wc);
r[0..stages].to_vec() };
let mut cur = a.to_vec();
for (j, &sel) in amount.iter().enumerate() {
if self.over() {
return vec![f; w];
}
let sh = (1usize << j) % w;
let mut rotated = Vec::with_capacity(w);
for i in 0..w {
rotated.push(if left {
cur[(i + w - sh) % w]
} else {
cur[(i + sh) % w]
});
}
cur = self.mux_vec(sel, &rotated, &cur);
}
cur
}
pub fn assert_true(&mut self, bv: &Bv) {
assert_eq!(
bv.width(),
1,
"a constraint must be 1 bit, got {}",
bv.width()
);
let bits = self.encode(bv);
self.cnf.add_clause(&[bits[0]]);
}
}
fn known_zero_high(bits: &[i32], f: i32) -> usize {
bits.iter().rev().take_while(|&&l| l == f).count()
}
#[derive(Clone, Copy, PartialEq, Eq)]
enum ShKind {
Left,
Lright,
Aright,
}
fn shift_stages(w: usize) -> usize {
let mut stages = 0;
let mut span = 1usize;
while span < w {
span <<= 1;
stages += 1;
}
stages
}
fn rot_const(a: &[i32], k: u32, left: bool) -> Vec<i32> {
let w = a.len();
let sh = (k as usize) % w;
(0..w)
.map(|i| {
if left {
a[(i + w - sh) % w]
} else {
a[(i + sh) % w]
}
})
.collect()
}
#[cfg(test)]
mod tests {
use super::*;
use crate::bv::Node;
fn var(w: u32, id: usize) -> Bv {
Bv::wrap(Node::Var(w, id))
}
fn circuit_size(bv: &Bv) -> usize {
let bump = bumpalo::Bump::new();
let mut b = Blaster::new(&bump);
b.encode(bv);
b.cnf.clauses.len() - 1
}
#[test]
fn symbolic_operands_generate_the_real_circuits() {
let (x, y) = (var(64, 0), var(64, 1));
let measured: [(&str, usize); 7] = [
("udiv64", circuit_size(&x.udiv(&y))),
("sdiv64", circuit_size(&x.sdiv(&y))),
("mul64", circuit_size(&x.mul(&y))),
("shl_var64", circuit_size(&x.shl_var(&y))),
("rot_var64", circuit_size(&x.rotl_var(&y))),
("sgt64", circuit_size(&x.sgt(&y))),
(
"rot_var5 (modulo-divider path)",
circuit_size(&var(5, 0).rotl_var(&var(5, 1))),
),
];
for (name, n) in &measured {
println!("{name}: {n} clauses");
}
for (name, n) in measured {
let floor = match name {
"udiv64" => 50_000,
"sdiv64" => 50_000,
"mul64" => 35_000,
"shl_var64" => 2_000,
"rot_var64" => 1_500,
"sgt64" => 500,
"rot_var5 (modulo-divider path)" => 200,
_ => unreachable!(),
};
assert!(
n >= floor,
"{name} blasted only {n} clauses (floor {floor}) - did the operands fold?"
);
}
}
#[test]
fn a_literal_power_of_two_divisor_blasts_no_divider() {
let x = var(64, 0);
assert_eq!(circuit_size(&x.udiv(&Bv::val(1024, 64))), 0);
assert_eq!(circuit_size(&x.urem(&Bv::val(1024, 64))), 0);
let general = circuit_size(&x.udiv(&Bv::val(1000, 64)));
assert!(
general > 10_000,
"a literal non-power-of-two still builds a divider"
);
assert!(
general < 50_000,
"constant folding shrank the constant-divisor divider"
);
}
#[test]
fn a_zero_extended_division_runs_at_the_narrow_width() {
let z = Bv::val(0, 64);
let (x, y) = (var(64, 0), var(64, 1));
let narrow = circuit_size(&x.udiv(&y));
let wide = circuit_size(&z.concat(&x).udiv(&z.concat(&y)));
assert!(
wide < narrow * 2,
"zero-extended 128-bit divide blasted {wide} clauses against {narrow} at 64 bits"
);
let literal = circuit_size(&x.udiv(&Bv::val(1000, 64)));
let wide_literal = circuit_size(&z.concat(&x).udiv(&Bv::val(1000, 128)));
assert!(
wide_literal < literal + 1_000,
"zero-extended literal divide blasted {wide_literal} against {literal} at 64 bits"
);
}
#[test]
fn constant_operands_fold_to_no_circuit_at_all() {
let folded = Bv::val(u64::MAX, 64).udiv(&Bv::val(7, 64));
assert!(folded.as_const().is_some());
assert_eq!(circuit_size(&folded), 0);
}
}