use crate::index::{GroupSizer, IndexPermutation, ALL_PERMS};
use crate::quad::{pack, unzigzag, zigzag};
use crate::varint::{read_uvarint, write_uvarint};
pub(crate) const NUM_SLOTS: usize = 9;
pub(crate) const FIRST_LAST_SLOT: usize = 6;
pub(crate) const LAST_MASK: u16 = 0b1_1100_0000;
pub(crate) fn is_last(si: usize) -> bool {
si >= FIRST_LAST_SLOT
}
pub(crate) fn perm_of(si: usize) -> IndexPermutation {
ALL_PERMS[if is_last(si) {
si - FIRST_LAST_SLOT
} else {
si
}]
}
pub(crate) fn last_slot(perm: IndexPermutation) -> usize {
FIRST_LAST_SLOT + perm.section_index()
}
pub(crate) fn slot_name(si: usize) -> String {
let p = perm_of(si).name();
if is_last(si) {
format!("{p}+G")
} else {
format!("G+{p}")
}
}
pub(crate) fn subject_col(perm: IndexPermutation) -> usize {
let r = perm.roles();
r.iter().position(|&x| x == 0).unwrap_or(0)
}
pub(crate) type Row4 = (u32, u32, u32, u32);
fn subj(r: &Row4, col: usize) -> u32 {
match col {
0 => r.0,
1 => r.1,
_ => r.2,
}
}
fn varint_len(mut v: u64) -> usize {
let mut n = 1;
while v >= 0x80 {
v >>= 7;
n += 1;
}
n
}
fn graph_code(g: u32, s: u32, prev: i64) -> (u64, i64) {
let d = g as i64 - s as i64;
(zigzag(d - prev), d)
}
pub(crate) fn encode_tile(rows: &[Row4], scol: usize) -> Vec<u8> {
let mut out = Vec::with_capacity(rows.len() * 3 + 16);
let mut num_a = 0u64;
let mut i = 0;
while i < rows.len() {
let a = rows[i].0;
while i < rows.len() && rows[i].0 == a {
i += 1;
}
num_a += 1;
}
write_uvarint(&mut out, num_a);
let mut prev_a = 0u32;
let mut prev_gs = 0i64;
let mut i = 0;
while i < rows.len() {
let a = rows[i].0;
let mut j = i;
let mut num_b = 0u64;
let mut last_b = None;
while j < rows.len() && rows[j].0 == a {
if last_b != Some(rows[j].1) {
num_b += 1;
last_b = Some(rows[j].1);
}
j += 1;
}
write_uvarint(&mut out, (a - prev_a) as u64);
write_uvarint(&mut out, num_b);
prev_a = a;
let mut prev_b = 0u32;
let mut k = i;
while k < j {
let b = rows[k].1;
let mut l = k;
while l < j && rows[l].1 == b {
l += 1;
}
write_uvarint(&mut out, (b - prev_b) as u64);
write_uvarint(&mut out, (l - k) as u64);
prev_b = b;
let mut prev_c = 0u32;
for r in &rows[k..l] {
write_uvarint(&mut out, (r.2 - prev_c) as u64);
let (code, d) = graph_code(r.3, subj(r, scol), prev_gs);
write_uvarint(&mut out, code);
prev_gs = d;
prev_c = r.2;
}
k = l;
}
i = j;
}
out
}
pub(crate) fn decode_tile(body: &[u8], scol: usize, out: &mut Vec<Row4>) -> Option<()> {
let mut pos = 0usize;
let mut take = || -> Option<u64> {
let (v, n) = read_uvarint(body.get(pos..)?)?;
pos += n;
Some(v)
};
let num_a = u32::try_from(take()?).ok()?;
let mut a = 0u32;
let mut prev_gs = 0i64;
for _ in 0..num_a {
a = a.checked_add(u32::try_from(take()?).ok()?)?;
let num_b = u32::try_from(take()?).ok()?;
let mut b = 0u32;
for _ in 0..num_b {
b = b.checked_add(u32::try_from(take()?).ok()?)?;
let n = u32::try_from(take()?).ok()?;
let mut c = 0u32;
for _ in 0..n {
c = c.checked_add(u32::try_from(take()?).ok()?)?;
let code = take()?;
if out.len() >= body.len() {
return None; }
let mut row = (a, b, c, 0u32);
let s = subj(&row, scol) as i64;
let d = prev_gs.checked_add(unzigzag(code))?;
prev_gs = d;
row.3 = u32::try_from(s.checked_add(d)?).ok()?;
out.push(row);
}
}
}
Some(())
}
pub(crate) struct EncodedTile {
pub(crate) first: (u32, u32),
pub(crate) last: (u32, u32),
pub(crate) syn: (u32, u32, u32, u32),
pub(crate) bytes: Vec<u8>,
pub(crate) raw: bool,
}
pub(crate) fn encode_packed(rows: &[Row4], scol: usize, codec: u8) -> EncodedTile {
let (mut min_c, mut max_c, mut min_g, mut max_g) = (u32::MAX, 0u32, u32::MAX, 0u32);
for r in rows {
min_c = min_c.min(r.2);
max_c = max_c.max(r.2);
min_g = min_g.min(r.3);
max_g = max_g.max(r.3);
}
let first = (rows[0].0, rows[0].1);
let last = (rows[rows.len() - 1].0, rows[rows.len() - 1].1);
let (bytes, raw) = pack(codec, encode_tile(rows, scol));
EncodedTile {
first,
last,
syn: (min_c, max_c, min_g, max_g),
bytes,
raw,
}
}
pub(crate) fn encode_batch(batch: &[Vec<Row4>], scol: usize, codec: u8) -> Vec<EncodedTile> {
#[cfg(feature = "parallel")]
{
use rayon::prelude::*;
batch
.par_iter()
.map(|t| encode_packed(t, scol, codec))
.collect()
}
#[cfg(not(feature = "parallel"))]
{
batch
.iter()
.map(|t| encode_packed(t, scol, codec))
.collect()
}
}
pub(crate) struct Tiler {
budget: usize,
scol: usize,
tile: Vec<Row4>,
tile_size: usize,
tile_a: Option<u32>,
tile_gs: i64,
group: Vec<Row4>,
sizer: GroupSizer,
group_gs: i64,
gbytes: usize,
gtotal: usize,
count: u64,
}
impl Tiler {
pub(crate) fn new(perm: IndexPermutation) -> Self {
Self::with_budget(perm, crate::write_opts::tile_budget())
}
pub(crate) fn with_budget(perm: IndexPermutation, budget: usize) -> Self {
Tiler {
budget: budget.max(1),
scol: subject_col(perm),
tile: Vec::new(),
tile_size: 0,
tile_a: None,
tile_gs: 0,
group: Vec::new(),
sizer: GroupSizer::start(0, 0),
group_gs: 0,
gbytes: 0,
gtotal: 0,
count: 0,
}
}
pub(crate) fn push(&mut self, r: Row4, emit: &mut dyn FnMut(Vec<Row4>)) {
self.count += 1;
if let Some(first) = self.group.first() {
if first.0 != r.0 {
self.close_group(emit);
}
}
if self.group.is_empty() {
self.sizer = GroupSizer::start(r.0, self.tile_a.unwrap_or(0));
self.group_gs = self.tile_gs;
self.gbytes = 0;
}
let (code, d) = graph_code(r.3, subj(&r, self.scol), self.group_gs);
self.group_gs = d;
self.gbytes += varint_len(code);
self.group.push(r);
self.gtotal = self.sizer.push(r.1, r.2) + self.gbytes;
if self.gtotal > self.budget {
self.tile.append(&mut self.group);
self.flush(emit);
self.gtotal = 0;
}
}
fn close_group(&mut self, emit: &mut dyn FnMut(Vec<Row4>)) {
let Some(&(a, ..)) = self.group.first() else {
return;
};
if !self.tile.is_empty() && self.tile_size + self.gtotal > self.budget {
self.flush(emit);
}
self.tile_size += self.gtotal;
self.tile_a = Some(a);
self.tile_gs = self.group_gs;
self.tile.append(&mut self.group);
self.gtotal = 0;
}
fn flush(&mut self, emit: &mut dyn FnMut(Vec<Row4>)) {
if !self.tile.is_empty() {
emit(std::mem::take(&mut self.tile));
}
self.tile_size = 0;
self.tile_a = None;
self.tile_gs = 0;
}
pub(crate) fn finish(mut self, emit: &mut dyn FnMut(Vec<Row4>)) -> u64 {
self.close_group(emit);
self.flush(emit);
self.count
}
}
pub(crate) fn row_of(perm: IndexPermutation, g: u32, s: u32, p: u32, o: u32) -> Row4 {
let (a, b, c) = perm.forward((s, p, o));
(a, b, c, g)
}
pub(crate) fn quad_of(perm: IndexPermutation, r: &Row4) -> (u32, (u32, u32, u32)) {
(r.3, perm.back((r.0, r.1, r.2)))
}
#[cfg(test)]
mod tests {
use super::*;
fn rows(n: u32) -> Vec<Row4> {
let mut v = Vec::new();
for a in 1..=n {
for b in [3, 5, 9] {
for c in [a, a + 1, a + 7] {
for g in [a, a + 2, 4000 + a] {
v.push((a * 2, b, c, g));
}
}
}
}
v.sort_unstable();
v.dedup();
v
}
#[test]
fn tile_round_trips_in_every_subject_column() {
let v = rows(40);
for scol in 0..3 {
let body = encode_tile(&v, scol);
let mut got = Vec::new();
decode_tile(&body, scol, &mut got).unwrap();
assert_eq!(got, v);
}
}
#[test]
fn a_truncated_tile_is_refused() {
let v = rows(5);
let body = encode_tile(&v, 0);
for cut in [0, 1, body.len() / 2, body.len() - 1] {
let mut got = Vec::new();
assert!(
decode_tile(&body[..cut], 0, &mut got).is_none() || got.len() < v.len(),
"cut {cut}"
);
}
}
#[test]
fn the_tiler_covers_every_row_once_and_cuts_a_mega_group() {
let v = rows(300);
for budget in [40usize, 500, 64 << 10] {
let mut t = Tiler::with_budget(IndexPermutation::Spo, budget);
let mut tiles: Vec<Vec<Row4>> = Vec::new();
for &r in &v {
t.push(r, &mut |x| tiles.push(x));
}
assert_eq!(t.finish(&mut |x| tiles.push(x)), v.len() as u64);
let flat: Vec<Row4> = tiles.iter().flatten().copied().collect();
assert_eq!(flat, v);
if budget == 40 {
assert!(tiles.len() > 300, "tiny budget cuts inside a group");
}
}
}
}