use super::*;
const UNSEEN: u16 = 0;
const AT_LEAST: u16 = 1;
const FALLBACK: u16 = 2;
const FIRST_TILE: u16 = 3;
const PAGE_BITS: usize = 3;
const PAGE_SIZE: usize = 1 << PAGE_BITS;
const PAGE_MASK: usize = PAGE_SIZE - 1;
#[derive(Default)]
pub(crate) struct CompactPlanner {
costs: Vec<f64>,
choices: Vec<u16>,
pages: Vec<u16>,
touched: Vec<u16>,
}
impl CompactPlanner {
fn reset(&mut self, width: usize, height: usize) {
for page in self.touched.drain(..) {
self.pages[usize::from(page)] = 0;
}
let pages = ((width * height + 1) << width).div_ceil(PAGE_SIZE);
if self.pages.len() < pages {
self.pages.resize(pages, 0);
}
}
fn get(&self, state: State, width: usize) -> Option<Memo> {
let index = state.key(width);
let page = usize::from(self.pages[index >> PAGE_BITS]);
if page == 0 {
return None;
}
let slot = ((page - 1) << PAGE_BITS) | (index & PAGE_MASK);
match self.choices[slot] {
UNSEEN => None,
AT_LEAST => Some(Memo::AtLeast(self.costs[slot])),
choice => Some(Memo::Solved(Entry {
cost: self.costs[slot],
choice: if choice == FALLBACK {
Choice::Fallback
} else {
Choice::Tile(choice - FIRST_TILE)
},
})),
}
}
fn insert(&mut self, state: State, width: usize, value: Memo) {
let index = state.key(width);
let physical = &mut self.pages[index >> PAGE_BITS];
if *physical == 0 {
self.touched.push((index >> PAGE_BITS) as u16);
let len = self.touched.len() * PAGE_SIZE;
if self.choices.len() < len {
self.costs.resize(len, 0.0);
self.choices.resize(len, UNSEEN);
} else {
self.choices[len - PAGE_SIZE..len].fill(UNSEEN);
}
*physical = self.touched.len() as u16;
}
let slot = ((usize::from(*physical) - 1) << PAGE_BITS) | (index & PAGE_MASK);
let (cost, choice) = match value {
Memo::AtLeast(cost) => (cost, AT_LEAST),
Memo::Solved(entry) => (
entry.cost,
match entry.choice {
Choice::Fallback => FALLBACK,
Choice::Tile(k) => FIRST_TILE + k,
_ => unreachable!("only finite nonterminal suffixes are memoized"),
},
),
};
self.costs[slot] = cost;
self.choices[slot] = choice;
}
}
#[derive(Clone, Copy)]
struct State {
cell: usize,
filled: usize,
}
impl State {
fn key(self, width: usize) -> usize {
(self.cell << width) | (self.filled >> 1)
}
fn mask(c: Candidate, width: usize) -> usize {
let row = if c.width() == 2 { 3 } else { 1 };
if c.height() == 2 {
row | row << width
} else {
row
}
}
fn advance(self, mask: usize) -> Self {
let filled = (self.filled | mask) >> 1;
let skip = filled.trailing_ones() as usize;
Self {
cell: self.cell + 1 + skip,
filled: filled >> skip,
}
}
}
static CELL_COORDS: [[u16; SIDE * SIDE + 1]; SIDE + 1] = {
let mut coords = [[0; SIDE * SIDE + 1]; SIDE + 1];
let mut width = 1;
while width <= SIDE {
let mut cell = 0;
while cell <= SIDE * SIDE {
coords[width][cell] = (((cell / width) << 8) | (cell % width)) as u16;
cell += 1;
}
width += 1;
}
coords
};
fn visit(
state: State,
profile: [u8; SIDE],
width: usize,
height: usize,
budget: f64,
candidates: &[Candidate],
s: &mut PlannerScratch,
compact: &mut CompactPlanner,
) -> Option<Entry> {
match compact.get(state, width) {
Some(Memo::Solved(best)) => return Some(best),
Some(Memo::AtLeast(bound)) if bound >= budget => return None,
_ => {}
}
let coords = CELL_COORDS[width][state.cell];
let (x, y) = (usize::from(coords & 0xff), usize::from(coords >> 8));
debug_assert_eq!(first_open(profile, width), (x, y));
if y == height {
return Some(Entry {
cost: 0.0,
choice: Choice::None,
});
}
let mut best = Entry {
cost: fallback_cost(profile, width, height, s),
choice: Choice::Fallback,
};
let anchor = y * SIDE + x;
let expand = if s.budget == 0 {
0
} else {
s.budget -= 1;
s.anchors[anchor].len()
};
for i in 0..expand {
let k = s.anchors[anchor][i];
let c = candidates[k];
let mask = State::mask(c, width);
if !c.cost.is_finite() || state.filled & mask != 0 {
continue;
}
let next = state.advance(mask);
let next_profile = advance(profile, c);
let bound = match compact.get(next, width) {
Some(Memo::Solved(entry)) => entry.cost,
Some(Memo::AtLeast(bound)) => bound,
None => {
let bound = lower_bound(next_profile, width, height, s);
compact.insert(next, width, Memo::AtLeast(bound));
bound
}
};
let limit = best.cost.min(budget);
if add_lower(c.cost, bound) >= limit {
continue;
}
let remaining = -add_lower(-limit, c.cost);
if let Some(suffix) = visit(
next,
next_profile,
width,
height,
remaining,
candidates,
s,
compact,
) {
let cost = c.cost + suffix.cost;
if cost < best.cost {
best = Entry {
cost,
choice: Choice::Tile(k as u16),
};
}
}
}
if best.cost <= budget && best.cost.is_finite() {
compact.insert(state, width, Memo::Solved(best));
Some(best)
} else {
compact.insert(state, width, Memo::AtLeast(budget));
None
}
}
pub(super) fn plan(
candidates: &[Candidate],
width: usize,
height: usize,
s: &mut PlannerScratch,
compact: &mut CompactPlanner,
out: &mut Vec<usize>,
) -> f64 {
if candidates.iter().any(|c| c.width() > 2 || c.height() > 2) {
return super::plan(candidates, width, height, s, out);
}
prepare_planner(candidates, width, height, s);
compact.reset(width, height);
let mut state = State { cell: 0, filled: 0 };
let mut profile = [0; SIDE];
let root = visit(
state,
profile,
width,
height,
f64::INFINITY,
candidates,
s,
compact,
)
.unwrap_or(EMPTY);
out.clear();
if !root.cost.is_finite() {
return root.cost;
}
while state.cell < width * height {
let Some(Memo::Solved(entry)) = compact.get(state, width) else {
unreachable!("a winning backpointer must have an exact suffix");
};
match entry.choice {
Choice::Tile(k) => {
let k = usize::from(k);
out.push(k);
state = state.advance(State::mask(candidates[k], width));
profile = advance(profile, candidates[k]);
}
Choice::Fallback => {
unpack_fallback(profile, width, height, s, out);
break;
}
_ => unreachable!("invalid compact frontier backpointer"),
}
}
root.cost
}
pub(super) fn prepare_square_bounds(
candidates: &[Candidate],
width: usize,
height: usize,
s: &mut PlannerScratch,
) {
let improve = |a: f64, b: f64| if b < a { b } else { a };
let mut leaf = [f64::INFINITY; SIDE * SIDE];
let mut wide = leaf;
let mut tall = leaf;
for &c in candidates {
if !c.cost.is_finite() {
continue;
}
let slots = match (c.width(), c.height()) {
(1, 1) => &mut leaf,
(2, 1) => &mut wide,
(1, 2) => &mut tall,
_ => unreachable!("only leaves and pairs precede squares"),
};
let slot = &mut slots[c.y() * SIDE + c.x()];
if c.cost < *slot {
*slot = c.cost;
}
}
s.region_costs.resize(REGION_COUNT, f64::INFINITY);
for y in 0..height.saturating_sub(1) {
for x in 0..width.saturating_sub(1) {
let i = y * SIDE + x;
let left = improve(tall[i], leaf[i] + leaf[i + SIDE]);
let right = improve(tall[i + 1], leaf[i + 1] + leaf[i + SIDE + 1]);
let top = improve(wide[i], leaf[i] + leaf[i + 1]);
let bottom = improve(wide[i + SIDE], leaf[i + SIDE] + leaf[i + SIDE + 1]);
s.region_costs[region_index(x, y, 2, 2)] = improve(left + right, top + bottom);
}
}
}
#[cfg(test)]
mod tests {
use super::*;
fn candidates(w: usize, h: usize, seed: usize) -> Vec<Candidate> {
let mut out = Vec::new();
for strategy in COEFFICIENT_STRATEGIES {
let p = Piece::new(0, 0, strategy);
if p.width() > w || p.height() > h {
continue;
}
for y in 0..=h - p.height() {
for x in 0..=w - p.width() {
let mut p = Piece::new(x, y, strategy);
let n = (p.key() * 1664525 + seed * 1013904223) % 257;
let cost = match seed % 6 {
0 if n.is_multiple_of(7) && n % 2 == 1 => -0.0,
0 => (n % 7) as f64,
1 => (n as f32 * 0.12345) as f64,
2 => (n as f64 - 128.0) / 8.0,
3 => ((n + 1) as f64) * 2.0f64.powi(n as i32 % 80 - 40),
4 if n.is_multiple_of(11) => f64::INFINITY,
5 if n.is_multiple_of(13) => f64::NAN,
_ => (n + 1) as f64 / 32.0,
};
if p.width() == 1 && p.height() == 1 && n.is_multiple_of(3) {
p.strategy = STRATEGY_AFV0;
}
out.push(Candidate::new(p, cost));
}
}
}
out
}
#[test]
fn memo_pages_reuse_storage_across_dimensions() {
let mut compact = CompactPlanner::default();
compact.reset(8, 8);
let first = State { cell: 0, filled: 0 };
let neighbor = State { cell: 0, filled: 2 };
let distant = State {
cell: 62,
filled: 2,
};
compact.insert(first, 8, Memo::AtLeast(7.0));
compact.insert(distant, 8, Memo::AtLeast(9.0));
assert_eq!(compact.costs.len(), 2 * PAGE_SIZE);
assert!(matches!(compact.get(first, 8), Some(Memo::AtLeast(7.0))));
assert!(matches!(compact.get(distant, 8), Some(Memo::AtLeast(9.0))));
assert!(compact.get(neighbor, 8).is_none());
compact.reset(3, 7);
compact.insert(neighbor, 3, Memo::AtLeast(11.0));
assert!(compact.get(first, 3).is_none());
assert!(matches!(
compact.get(neighbor, 3),
Some(Memo::AtLeast(11.0))
));
assert_eq!(compact.costs.len(), 2 * PAGE_SIZE);
}
#[test]
fn compact_reconstruction_matches_generic_cost_choices_and_visits() {
let mut generic = PlannerScratch::default();
let mut specialized = PlannerScratch::default();
let mut compact = CompactPlanner::default();
let mut expected = Vec::new();
let mut actual = Vec::new();
for w in (1..=8).rev() {
for h in 1..=8 {
for seed in 0..12 {
let mut c = candidates(w, h, seed);
if seed % 2 == 1 {
c.reverse(); }
let a = super::super::plan(&c, w, h, &mut generic, &mut expected);
let b = plan(&c, w, h, &mut specialized, &mut compact, &mut actual);
assert_eq!(a.to_bits(), b.to_bits(), "{w}x{h} seed {seed}");
assert_eq!(expected, actual, "{w}x{h} seed {seed}");
assert_eq!(generic.budget, specialized.budget, "{w}x{h} seed {seed}");
}
}
}
}
#[test]
fn compact_reconstruction_preserves_failed_and_exhausted_budgets() {
let c = candidates(8, 8, 1);
let mut generic = PlannerScratch::default();
let mut specialized = PlannerScratch::default();
let mut compact = CompactPlanner::default();
for visits in [0, 1, 2, 5, 50, VISIT_BUDGET] {
for limit in [0.0, 10.0, 100.0, f64::INFINITY] {
prepare_planner(&c, 8, 8, &mut generic);
prepare_planner(&c, 8, 8, &mut specialized);
compact.reset(8, 8);
generic.budget = visits;
specialized.budget = visits;
for budget in [limit, f64::INFINITY] {
let a = super::super::visit([0; SIDE], 8, 8, budget, &c, &mut generic);
let b = visit(
State { cell: 0, filled: 0 },
[0; SIDE],
8,
8,
budget,
&c,
&mut specialized,
&mut compact,
);
assert_eq!(format!("{a:?}"), format!("{b:?}"));
assert_eq!(generic.budget, specialized.budget);
}
}
}
}
#[test]
fn larger_incumbents_use_generic_planner() {
let mut compact = CompactPlanner::default();
for strategy in [STRATEGY_DCT32X8, STRATEGY_DCT32X32, STRATEGY_DCT64X64] {
let mut c = candidates(8, 8, 1);
c.push(Candidate::new(Piece::new(0, 0, strategy), 0.25));
let mut s = PlannerScratch::default();
let mut expected = Vec::new();
let a = super::super::plan(&c, 8, 8, &mut s, &mut expected);
let mut actual = Vec::new();
let b = plan(&c, 8, 8, &mut s, &mut compact, &mut actual);
assert_eq!(a.to_bits(), b.to_bits());
assert_eq!(expected, actual);
assert!(compact.choices.is_empty());
}
}
#[test]
fn square_bounds_match_generic_regions_bit_for_bit() {
let mut generic = PlannerScratch::default();
let mut specialized = PlannerScratch::default();
for w in 1..=8 {
for h in (1..=8).rev() {
for seed in 0..12 {
let c: Vec<_> = candidates(w, h, seed)
.into_iter()
.filter(|c| c.width() != 2 || c.height() != 2)
.collect();
prepare_regions(&c, w, h, SIDE, SIDE, &mut generic);
prepare_square_bounds(&c, w, h, &mut specialized);
for y in 0..h.saturating_sub(1) {
for x in 0..w.saturating_sub(1) {
let i = region_index(x, y, 2, 2);
assert_eq!(
generic.region_costs[i].to_bits(),
specialized.region_costs[i].to_bits(),
"{w}x{h} seed {seed} at {x},{y}"
);
}
}
}
}
}
}
}