use crate::{
layout::{self, MAX_OPS, Op, STACK, VARIABLES, Varint},
steps::Entry,
};
const SIZE_MAX: u128 = isize::MAX as u128;
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
pub struct Range {
hi: (u64, u64),
lo: (u64, u64),
}
pub type Vars = [Range; VARIABLES];
const fn min64(a: u64, b: u64) -> u64 {
if a < b { a } else { b }
}
const fn max64(a: u64, b: u64) -> u64 {
if a > b { a } else { b }
}
const fn min128(a: u128, b: u128) -> u128 {
if a < b { a } else { b }
}
const fn ones(x: u64) -> u64 {
if x == 0 { 0 } else { u64::MAX >> x.leading_zeros() }
}
impl Range {
pub const ANY: Range = Range { hi: (0, u64::MAX), lo: (0, u64::MAX) };
pub const fn new(min: u128, max: u128) -> Range {
let (a, b) = ((min >> 64) as u64, (max >> 64) as u64);
if a == b {
Range { hi: (a, a), lo: (min as u64, max as u64) }
} else {
Range { hi: (a, b), lo: (0, u64::MAX) }
}
}
pub const fn exact(value: u128) -> Range {
Range::new(value, value)
}
const fn bytes(bytes: u8) -> Range {
if bytes >= 16 { Range::ANY } else { Range::new(0, (1 << (8 * bytes as u32)) - 1) }
}
pub const fn min(self) -> u128 {
(self.hi.0 as u128) << 64 | self.lo.0 as u128
}
pub const fn max(self) -> u128 {
(self.hi.1 as u128) << 64 | self.lo.1 as u128
}
#[cfg(test)]
pub const fn holds(self, value: u128) -> bool {
let (hi, lo) = ((value >> 64) as u64, value as u64);
self.hi.0 <= hi && hi <= self.hi.1 && self.lo.0 <= lo && lo <= self.lo.1
}
#[cfg(test)]
pub const fn halves(hi: (u64, u64), lo: (u64, u64)) -> Range {
Range { hi, lo }
}
const fn join(self, other: Range) -> Range {
Range {
hi: (min64(self.hi.0, other.hi.0), max64(self.hi.1, other.hi.1)),
lo: (min64(self.lo.0, other.lo.0), max64(self.lo.1, other.lo.1)),
}
}
const fn same(self, other: Range) -> bool {
self.hi.0 == other.hi.0
&& self.hi.1 == other.hi.1
&& self.lo.0 == other.lo.0
&& self.lo.1 == other.lo.1
}
const fn widen(self, to: Range) -> Range {
Range {
hi: (
if to.hi.0 < self.hi.0 { 0 } else { self.hi.0 },
if to.hi.1 > self.hi.1 { u64::MAX } else { self.hi.1 },
),
lo: (
if to.lo.0 < self.lo.0 { 0 } else { self.lo.0 },
if to.lo.1 > self.lo.1 { u64::MAX } else { self.lo.1 },
),
}
}
const fn at_most(self, max: u128) -> Range {
if self.min() > max {
return self;
}
let cut = Range::new(self.min(), min128(self.max(), max));
Range {
hi: (max64(self.hi.0, cut.hi.0), min64(self.hi.1, cut.hi.1)),
lo: (max64(self.lo.0, cut.lo.0), min64(self.lo.1, cut.lo.1)),
}
}
pub const fn fits(self) -> u8 {
let bits = self.bits();
if bits < REGISTER { REGISTER } else { bits }
}
pub const fn bits(self) -> u8 {
let max = self.max();
if max <= u32::MAX as u128 {
32
} else if max <= u64::MAX as u128 {
64
} else {
128
}
}
}
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
pub struct How {
pub result: u8,
pub width: u8,
pub fails: bool,
pub halves: bool,
}
impl How {
pub const WIDE: How = How { result: 128, width: 128, fails: true, halves: false };
}
#[inline(always)]
pub const fn fit(value: u128, bits: u8) -> u128 {
match bits {
32 => value as u32 as u128,
64 => value as u64 as u128,
_ => value,
}
}
#[inline(always)]
pub const fn binary(op: Op, how: How, a: u128, b: u128) -> Option<u128> {
match how.width {
32 => match narrow32(op, how.fails, a as u32, b as u32) {
Some(value) => Some(value as u128),
None => None,
},
64 => match narrow64(op, how.fails, a as u64, b as u64) {
Some(value) => Some(value as u128),
None => None,
},
_ => wide(op, how, a, b),
}
}
#[inline(always)]
const fn wide(op: Op, how: How, a: u128, b: u128) -> Option<u128> {
match op {
Op::Add if !how.fails => Some(if how.halves {
let hi = ((a >> 64) as u64).wrapping_add((b >> 64) as u64);
(hi as u128) << 64 | (a as u64).wrapping_add(b as u64) as u128
} else {
a.wrapping_add(b)
}),
Op::Sub if !how.fails => Some(if how.halves {
let hi = ((a >> 64) as u64).wrapping_sub((b >> 64) as u64);
(hi as u128) << 64 | (a as u64).wrapping_sub(b as u64) as u128
} else {
a.wrapping_sub(b)
}),
Op::Mul if !how.fails => Some(a.wrapping_mul(b)),
Op::Shl if !how.fails => Some(a.wrapping_shl(b as u32)),
Op::Shr if !how.fails => Some(a.wrapping_shr(b as u32)),
_ => layout::binary(op, a, b),
}
}
macro_rules! narrow {
($($name:ident: $t:ty)+) => {$(
#[inline(always)]
const fn $name(op: Op, fails: bool, a: $t, b: $t) -> Option<$t> {
Some(match op {
Op::Add => a.wrapping_add(b),
Op::Sub if fails => match a.checked_sub(b) {
Some(value) => value,
None => return None,
},
Op::Sub => a.wrapping_sub(b),
Op::Mul => a.wrapping_mul(b),
Op::Div => match a.checked_div(b) {
Some(value) => value,
None => return None,
},
Op::Rem => match a.checked_rem(b) {
Some(value) => value,
None => return None,
},
Op::And => a & b,
Op::Or => a | b,
Op::Xor => a ^ b,
Op::Shl => a.wrapping_shl(b as u32),
Op::Shr => a.wrapping_shr(b as u32),
Op::Eq => (a == b) as $t,
Op::Ne => (a != b) as $t,
Op::Lt => (a < b) as $t,
Op::Le => (a <= b) as $t,
Op::Gt => (a > b) as $t,
Op::Ge => (a >= b) as $t,
_ => return None,
})
}
)+};
}
narrow! {
narrow32: u32
narrow64: u64
}
pub const fn binary_range(op: Op, a: Range, b: Range) -> (Range, bool, bool) {
match op {
Op::Add => {
if let (Some(lo), Some(hi)) = (a.lo.1.checked_add(b.lo.1), a.hi.1.checked_add(b.hi.1)) {
let range = Range { hi: (a.hi.0 + b.hi.0, hi), lo: (a.lo.0 + b.lo.0, lo) };
return (range, false, true);
}
match a.max().checked_add(b.max()) {
Some(max) => (Range::new(a.min() + b.min(), max), false, false),
None => (Range::new(a.min().saturating_add(b.min()), u128::MAX), true, false),
}
}
Op::Sub => {
if a.lo.0 >= b.lo.1 && a.hi.0 >= b.hi.1 {
let range =
Range { hi: (a.hi.0 - b.hi.1, a.hi.1 - b.hi.0), lo: (a.lo.0 - b.lo.1, a.lo.1 - b.lo.0) };
return (range, false, true);
}
let range = Range::new(a.min().saturating_sub(b.max()), a.max().saturating_sub(b.min()));
(range, a.min() < b.max(), false)
}
Op::Mul => match a.max().checked_mul(b.max()) {
Some(max) => (Range::new(a.min() * b.min(), max), false, false),
None => (Range::new(a.min().saturating_mul(b.min()), u128::MAX), true, false),
},
Op::Div => {
let least = if b.min() == 0 { 1 } else { b.min() };
let range = match a.min().checked_div(b.max()) {
Some(min) => Range::new(min, a.max() / least),
None => Range::exact(0),
};
(range, b.min() == 0, false)
}
Op::Rem => {
let range =
if b.max() == 0 { Range::exact(0) } else { Range::new(0, min128(a.max(), b.max() - 1)) };
(range, b.min() == 0, false)
}
Op::And => {
(Range { hi: (0, min64(a.hi.1, b.hi.1)), lo: (0, min64(a.lo.1, b.lo.1)) }, false, false)
}
Op::Or | Op::Xor => {
let range =
Range { hi: (0, ones(max64(a.hi.1, b.hi.1))), lo: (0, ones(max64(a.lo.1, b.lo.1))) };
(range, false, false)
}
Op::Shl => {
let fails = b.max() >= 128;
if b.min() == 64 && b.max() == 64 {
return (Range { hi: a.lo, lo: (0, 0) }, false, false);
}
let range = if b.max() < 128 && a.max().leading_zeros() as u128 >= b.max() {
Range::new(a.min() << b.min(), a.max() << b.max())
} else {
Range::ANY
};
(range, fails, false)
}
Op::Shr => {
if b.min() == 64 && b.max() == 64 {
return (Range { hi: (0, 0), lo: a.hi }, false, false);
}
let (least, most) = (min128(b.min(), 127), min128(b.max(), 127));
(Range::new(a.min() >> most, a.max() >> least), b.max() >= 128, false)
}
Op::Eq | Op::Ne | Op::Lt | Op::Le | Op::Gt | Op::Ge => (Range::new(0, 1), false, false),
_ => (Range::ANY, true, false),
}
}
const REGISTER: u8 = if usize::BITS >= 64 { 64 } else { 32 };
pub const fn binary_how(op: Op, a: Range, b: Range) -> (How, Range) {
binary_in(op, a, b, REGISTER)
}
pub const fn binary_in(op: Op, a: Range, b: Range, register: u8) -> (How, Range) {
let (range, fails, halves) = binary_range(op, a, b);
let mut width = register;
if a.bits() > width {
width = a.bits();
}
if b.bits() > width {
width = b.bits();
}
if range.bits() > width {
width = range.bits();
}
if matches!(op, Op::Shl | Op::Shr) && b.max() >= width as u128 {
width = 128;
}
let result = if range.bits() < register { register } else { range.bits() };
(How { result, width, fails, halves: halves && width == 128 }, range)
}
pub struct Plan {
pub how: [How; MAX_OPS],
pub result: Range,
pub entry: Vars,
}
const NONE: u8 = u8::MAX;
#[derive(Copy, Clone)]
struct Part {
end: usize,
vars: Vars,
}
const fn join_vars(a: Vars, b: Vars) -> Vars {
let (mut vars, mut i) = (a, 0);
while i < VARIABLES {
vars[i] = a[i].join(b[i]);
i += 1;
}
vars
}
pub const fn plan(ops: &[Op], entry: &Entry) -> Plan {
analyze(ops, entry.vars, usize::MAX, entry.walks)
}
pub const fn walk_entry(ops: &[Op], entry: &Entry, at: usize) -> Entry {
Entry { vars: analyze(ops, entry.vars, at, entry.walks).entry, walks: entry.walks + 1 }
}
const FIXED_WALKS: usize = 2;
const fn fixed_point(next: &[Op], vars: Vars, var: u8, start: Range, walks: usize) -> Range {
if walks >= FIXED_WALKS {
return Range::ANY;
}
let (mut state, mut round) = (start, 0);
loop {
let mut inner = vars;
inner[var as usize] = state;
let after = state.join(analyze(next, inner, usize::MAX, walks + 1).result);
if after.same(state) {
return state;
}
state = if round < 2 { after } else { state.widen(after) };
round += 1;
}
}
const fn analyze(ops: &[Op], vars: Vars, stop: usize, walks: usize) -> Plan {
let mut plan = Plan { how: [How::WIDE; MAX_OPS], result: Range::ANY, entry: vars };
let mut vars = vars;
let (mut stack, mut tags, mut depth) = ([Range::ANY; STACK], [NONE; STACK], 0usize);
let (mut parts, mut open) = ([Part { end: usize::MAX, vars }; STACK], 0usize);
let mut i = 0;
while i < ops.len() && i < MAX_OPS {
let op = ops[i];
let mut before = vars;
if open > 0 && parts[open - 1].end == i {
open -= 1;
before = parts[open].vars;
if !matches!(op, Op::Else(_)) {
vars = join_vars(vars, before);
}
}
let (pops, value) = match op {
Op::Lit(value) => (0, Range::exact(value)),
Op::Load { size, .. } => (0, Range::bytes(size)),
Op::Size => (0, Range::new(0, SIZE_MAX)),
Op::Get(index) => {
stack[depth] = vars[index as usize];
tags[depth] = index;
plan.how[i].result = vars[index as usize].fits();
depth += 1;
i += 1;
continue;
}
Op::Set(index) => {
depth -= 1;
vars[index as usize] = stack[depth];
let mut k = 0;
while k < depth {
if tags[k] == index {
tags[k] = NONE;
}
k += 1;
}
i += 1;
continue;
}
Op::Not => (1, Range::new(0, 1)),
Op::At { size, .. } => {
refine(&mut vars, tags[depth - 1], SIZE_MAX - size as u128);
(1, Range::bytes(size))
}
Op::Varint { form, length } => {
refine(&mut vars, tags[depth - 1], SIZE_MAX);
let value = match (form, length) {
(Varint::Quic, false) => Range::new(0, (1 << 62) - 1),
(Varint::Quic, true) => Range::new(1, 8),
(_, false) => Range::ANY,
(_, true) => Range::new(1, SIZE_MAX),
};
(1, value)
}
Op::Crc32 | Op::Sum16 | Op::Crc(_) | Op::CrcZeros(_) | Op::Checksum(_) | Op::Matches(_) => {
let operands = if matches!(op, Op::CrcZeros(_)) { 4 } else { 2 };
let mut k = depth - operands;
while k < depth {
refine(&mut vars, tags[k], SIZE_MAX);
k += 1;
}
let value = match op {
Op::Crc32 | Op::Checksum(layout::Checksum::Adler32) => Range::bytes(4),
Op::Sum16 | Op::Checksum(layout::Checksum::Fletcher16) => Range::bytes(2),
Op::Crc(_) | Op::CrcZeros(_) => Range::bytes(8),
Op::Matches(_) => Range::new(0, 1),
_ => Range::new(0, 255 * SIZE_MAX),
};
(operands, value)
}
Op::Shortcut { len, .. } => {
parts[open] = Part { end: i + len as usize, vars };
open += 1;
(1, stack[depth - 1])
}
Op::Then(len) => {
parts[open] = Part { end: i + len as usize, vars };
open += 1;
i += 1;
continue;
}
Op::Else(len) => {
parts[open] = Part { end: i + len as usize + 1, vars };
open += 1;
vars = before;
i += 1;
continue;
}
Op::Both | Op::Either => (2, Range::new(0, 1)),
Op::Select => (3, stack[depth - 2].join(stack[depth - 1])),
Op::Walk { var, next, .. } => {
let state = fixed_point(next, vars, var, stack[depth - 1], walks);
if i == stop {
plan.entry = vars;
plan.entry[var as usize] = state;
return plan;
}
(1, state)
}
op => {
let (how, value) = binary_how(op, stack[depth - 2], stack[depth - 1]);
plan.how[i] = how;
(2, value)
}
};
depth -= pops;
stack[depth] = value;
tags[depth] = NONE;
plan.how[i].result = value.fits();
depth += 1;
i += 1;
}
plan.result = stack[0];
plan
}
const fn refine(vars: &mut Vars, index: u8, max: u128) {
if index != NONE {
vars[index as usize] = vars[index as usize].at_most(max);
}
}
pub struct Planned<X>(core::marker::PhantomData<X>);
impl<X: crate::steps::Ops> Planned<X> {
pub const PLAN: Plan = plan(X::OPS, &X::ENTRY);
}