use super::GroupLayout;
use super::rct::write_rct_transform;
use crate::bit_writer::BitWriter;
use crate::coder_scratch::CoderScratch;
use crate::entropy::{Token, pack_signed};
use crate::patches::{ModularFrameKind, NUM_PATCH_CONTEXTS, PATCH_REF_ID, PatchReference};
use crate::path_order;
use crate::shared_sort::SharedSort;
pub(crate) fn write_u64(value: u64, w: &mut BitWriter) {
match value {
0 => w.write(2, 0),
1..=16 => {
w.write(2, 1);
w.write(4, value - 1);
}
17..=272 => {
w.write(2, 2);
w.write(8, value - 17);
}
_ => unreachable!("lossless frame flags fit the short U64 form"),
}
}
pub(crate) fn write_frame_dimension(value: usize, w: &mut BitWriter) {
let value = value as u64;
if value < 256 {
w.write(2, 0);
w.write(8, value);
} else if value < 2304 {
w.write(2, 1);
w.write(11, value - 256);
} else if value < 18688 {
w.write(2, 2);
w.write(14, value - 2304);
} else {
w.write(2, 3);
w.write(30, value - 18688);
}
}
pub(super) fn write_dc_quant(kind: ModularFrameKind<'_>, w: &mut BitWriter) {
let scale = match kind {
ModularFrameKind::XybCrop { .. } | ModularFrameKind::XybBlend { .. } => {
crate::xyb::CROP_LATTICE_SCALE
}
_ => 1,
};
if scale == 1 {
w.write(1, 1); return;
}
use crate::quant_weights::INV_DC_QUANT;
w.write(1, 0);
for inv in INV_DC_QUANT {
let step_x128 = 128.0 / (inv * scale as f32);
w.write(16, crate::util::f32_to_f16_bits(step_x128) as u64);
}
}
pub(super) fn write_frame_header_modular_kind(
has_alpha: bool,
kind: ModularFrameKind<'_>,
layout: GroupLayout,
w: &mut BitWriter,
) {
match kind {
ModularFrameKind::Regular => write_frame_header_modular(has_alpha, layout, w),
ModularFrameKind::RgbSavedFirst => {
write_frame_header_modular_layer(has_alpha, false, layout, w)
}
ModularFrameKind::RgbBlendLast => {
write_frame_header_modular_layer(has_alpha, true, layout, w)
}
ModularFrameKind::Patched { saved_first, .. } => {
write_frame_header_modular_flags(has_alpha, 2, saved_first, layout, w)
}
ModularFrameKind::RgbCrop {
x0,
y0,
width,
height,
full,
last,
} => write_frame_header_modular_crop(
has_alpha,
false,
[x0, y0, width, height],
layout,
full,
last,
w,
),
ModularFrameKind::XybCrop {
x0,
y0,
width,
height,
full,
last,
} => write_frame_header_modular_crop(
has_alpha,
true,
[x0, y0, width, height],
layout,
full,
last,
w,
),
ModularFrameKind::RgbBlendCrop {
x0,
y0,
width,
height,
} => write_frame_header_modular_blend_crop([x0, y0, width, height], layout, w),
ModularFrameKind::XybReferenceOnly {
width,
height,
slot,
} => write_frame_header_modular_xyb_reference(width, height, slot, has_alpha, layout, w),
ModularFrameKind::XybBlend { last } => {
write_frame_header_modular_xyb_blend(has_alpha, last, layout, w)
}
ModularFrameKind::ReferenceOnly { width, height } => {
w.write(1, 0); w.write(2, 0b10); w.write(1, 1); write_u64(0, w); w.write(1, 0); w.write(2, 0); if has_alpha {
w.write(2, 0); }
w.write(2, layout.shift as u64);
w.write(1, 1); write_frame_dimension(width, w);
write_frame_dimension(height, w);
w.write(2, PATCH_REF_ID as u64); w.write(1, 1); w.write(2, 0); w.write(1, 0); w.write(1, 0); w.write(2, 0); w.write(2, 0); w.write(2, 0); }
}
}
fn write_frame_header_modular_xyb_blend(
has_alpha: bool,
last: bool,
layout: GroupLayout,
w: &mut BitWriter,
) {
w.write(1, 0); w.write(2, 0b00); w.write(1, 1); write_u64(0, w); w.write(2, 0b00); if has_alpha {
w.write(2, 0b00); }
w.write(2, layout.shift as u64);
w.write(2, 0b00); w.write(1, 0); for _ in 0..1 + usize::from(has_alpha) {
w.write(2, 2); w.write(2, 0); w.write(1, 0); w.write(2, 0); }
if last {
w.write(1, 1); } else {
w.write(1, 0); w.write(2, 0); }
w.write(2, 0b00); w.write(1, 0); w.write(1, 0); w.write(2, 0); w.write(2, 0b00); w.write(2, 0b00); }
pub(super) fn write_frame_header_modular_xyb_reference(
width: usize,
height: usize,
slot: u32,
has_alpha: bool,
layout: GroupLayout,
w: &mut BitWriter,
) {
w.write(1, 0); w.write(2, 0b10); w.write(1, 1); write_u64(0, w); w.write(2, 0); if has_alpha {
w.write(2, 0); }
w.write(2, layout.shift as u64);
w.write(1, 1); write_frame_dimension(width, w);
write_frame_dimension(height, w);
w.write(2, slot as u64); w.write(1, 1); w.write(2, 0); w.write(1, 0); w.write(1, 0); w.write(2, 0); w.write(2, 0); w.write(2, 0); }
fn write_frame_header_modular_layer(
has_alpha: bool,
blend_last: bool,
layout: GroupLayout,
w: &mut BitWriter,
) {
w.write(1, 0); w.write(2, 0b00); w.write(1, 1); write_u64(0, w); w.write(1, 0); write_upsampling(has_alpha, layout, w);
w.write(2, layout.shift as u64);
w.write(2, 0b00); w.write(1, 0); if blend_last {
for _ in 0..1 + usize::from(has_alpha) {
w.write(2, 2); w.write(2, 0); w.write(1, 0); w.write(2, 0); }
w.write(1, 1); } else {
w.write(2, 0b00); if has_alpha {
w.write(2, 0b00); }
w.write(1, 0); w.write(2, 0); w.write(1, 0); }
w.write(2, 0b00); w.write(1, 0); w.write(1, 0); w.write(2, 0); w.write(2, 0b00); w.write(2, 0b00); }
fn write_upsampling(has_alpha: bool, layout: GroupLayout, w: &mut BitWriter) {
w.write(2, layout.upsampling_selector()); if has_alpha {
w.write(2, layout.upsampling_selector()); }
}
pub(super) fn write_frame_header_modular(has_alpha: bool, layout: GroupLayout, w: &mut BitWriter) {
write_frame_header_modular_flags(has_alpha, 0, false, layout, w);
}
fn write_frame_header_modular_crop(
has_alpha: bool,
xyb_encoded: bool,
rect: [usize; 4],
layout: GroupLayout,
full: bool,
last: bool,
w: &mut BitWriter,
) {
w.write(1, 0); w.write(2, 0b00); w.write(1, 1); write_u64(0, w); if !xyb_encoded {
w.write(1, 0); }
write_upsampling(has_alpha, layout, w);
w.write(2, layout.shift as u64);
w.write(2, 0b00); w.write(1, 1); write_frame_dimension(2 * rect[0], w); write_frame_dimension(2 * rect[1], w);
write_frame_dimension(rect[2], w);
write_frame_dimension(rect[3], w);
for _ in 0..1 + usize::from(has_alpha) {
w.write(2, 0b00); if !full {
w.write(2, 0); }
}
if last {
w.write(1, 1); } else {
w.write(1, 0); w.write(2, 0); if full {
w.write(1, 0); }
}
w.write(2, 0b00); w.write(1, 0); w.write(1, 0); w.write(2, 0); w.write(2, 0b00); w.write(2, 0b00); }
fn write_frame_header_modular_blend_crop(rect: [usize; 4], layout: GroupLayout, w: &mut BitWriter) {
w.write(1, 0); w.write(2, 0b00); w.write(1, 1); write_u64(0, w); w.write(1, 0); write_upsampling(true, layout, w);
w.write(2, layout.shift as u64);
w.write(2, 0b00); w.write(1, 1); write_frame_dimension(2 * rect[0], w); write_frame_dimension(2 * rect[1], w);
write_frame_dimension(rect[2], w);
write_frame_dimension(rect[3], w);
for _ in 0..2 {
w.write(2, 2); w.write(2, 0); w.write(1, 0); w.write(2, 0); }
w.write(1, 1); w.write(2, 0b00); w.write(1, 0); w.write(1, 0); w.write(2, 0); w.write(2, 0b00); w.write(2, 0b00); }
fn write_frame_header_modular_flags(
has_alpha: bool,
flags: u64,
saved_first: bool,
layout: GroupLayout,
w: &mut BitWriter,
) {
w.write(1, 0); w.write(2, 0b00); w.write(1, 1); write_u64(flags, w);
w.write(1, 0); write_upsampling(has_alpha, layout, w);
w.write(2, layout.shift as u64);
w.write(2, 0b00); w.write(1, 0); w.write(2, 0b00); if has_alpha {
w.write(2, 0b00);
}
if saved_first {
w.write(1, 0); w.write(2, 0); w.write(1, 0); } else {
w.write(1, 1); }
w.write(2, 0b00); w.write(1, 0); w.write(1, 0); w.write(2, 0); w.write(2, 0b00); w.write(2, 0b00); }
pub(crate) fn write_patch_dictionary(
references: &[PatchReference],
has_alpha: bool,
scratch: &mut CoderScratch,
w: &mut BitWriter,
) {
write_patch_dictionary_with_pool(references, has_alpha, scratch, w, None);
}
pub(crate) fn write_patch_dictionary_with_pool(
references: &[PatchReference],
has_alpha: bool,
scratch: &mut CoderScratch,
w: &mut BitWriter,
pool: Option<&crate::thread_pool::ThreadPool>,
) {
let given = encode_patch_dictionary(&patch_dictionary_tokens(references, has_alpha), scratch);
if let Some(reordered) = reorder_occurrences(references, pool.map(|pool| (pool, &mut *scratch)))
{
let candidate =
encode_patch_dictionary(&patch_dictionary_tokens(&reordered, has_alpha), scratch);
if candidate.bits_written() < given.bits_written() {
w.append(&candidate);
return;
}
}
w.append(&given);
}
const PATCH_POSITION: u32 = 4;
const PATCH_OFFSET: u32 = 6;
fn patch_dictionary_tokens(references: &[PatchReference], has_alpha: bool) -> Vec<Token> {
const NUM_REF: u32 = 0;
const REFERENCE_FRAME: u32 = 1;
const PATCH_SIZE: u32 = 2;
const REF_POSITION: u32 = 3;
const BLEND_MODE: u32 = 5;
const COUNT: u32 = 7;
const CLAMP: u32 = 9;
let mut tokens = Vec::new();
tokens.push(Token::new(NUM_REF, references.len() as u32));
for reference in references {
tokens.push(Token::new(REFERENCE_FRAME, reference.ref_frame));
tokens.push(Token::new(REF_POSITION, reference.atlas_x as u32));
tokens.push(Token::new(REF_POSITION, reference.atlas_y as u32));
tokens.push(Token::new(PATCH_SIZE, (reference.width - 1) as u32));
tokens.push(Token::new(PATCH_SIZE, (reference.height - 1) as u32));
tokens.push(Token::new(COUNT, (reference.positions.len() - 1) as u32));
for (i, &(x, y)) in reference.positions.iter().enumerate() {
if i == 0 {
tokens.push(Token::new(PATCH_POSITION, x as u32));
tokens.push(Token::new(PATCH_POSITION, y as u32));
} else {
let (px, py) = reference.positions[i - 1];
tokens.push(Token::new(PATCH_OFFSET, pack_signed(x as i32 - px as i32)));
tokens.push(Token::new(PATCH_OFFSET, pack_signed(y as i32 - py as i32)));
}
let alpha_only = reference.alpha_only;
tokens.push(Token::new(
BLEND_MODE,
if alpha_only {
0
} else if reference.mul && !reference.add {
4
} else if reference.mul {
3
} else if reference.add {
2
} else {
1
},
));
if reference.mul {
tokens.push(Token::new(CLAMP, 0));
}
if has_alpha {
tokens.push(Token::new(BLEND_MODE, if alpha_only { 1 } else { 0 }));
}
}
}
tokens
}
fn encode_patch_dictionary(tokens: &[Token], scratch: &mut CoderScratch) -> BitWriter {
crate::entropy::raced_token_stream(tokens, NUM_PATCH_CONTEXTS, &mut scratch.huffman_pool)
}
fn occurrences_commute(reference: &PatchReference) -> bool {
if reference.add || reference.mul {
return true;
}
let mut boxes = reference.positions.clone();
boxes.shared_sort_unstable_by_key(|&(x, y)| (y, x));
for (k, &(x, y)) in boxes.iter().enumerate() {
for &(ox, oy) in &boxes[k + 1..] {
if oy >= y + reference.height {
break;
}
if ox.abs_diff(x) < reference.width {
return false;
}
}
}
true
}
fn reorder_occurrences(
references: &[PatchReference],
workers: Option<(&crate::thread_pool::ThreadPool, &mut CoderScratch)>,
) -> Option<Vec<PatchReference>> {
let movable: Vec<bool> = references
.iter()
.map(|r| r.positions.len() > 1 && occurrences_commute(r))
.collect();
if !movable.contains(&true) {
return None;
}
let points: Vec<Vec<path_order::Pos>> = references
.iter()
.map(|r| {
r.positions
.iter()
.map(|&(x, y)| (x as i32, y as i32))
.collect()
})
.collect();
let given = points.iter().map(|p| (0..p.len()).collect()).collect();
let orders = path_order::order_sets(&points, &movable, given, false, workers);
if orders
.iter()
.all(|order| order.iter().enumerate().all(|(k, &i)| k == i))
{
return None;
}
Some(
references
.iter()
.zip(&orders)
.map(|(reference, order)| PatchReference {
positions: order.iter().map(|&i| reference.positions[i]).collect(),
..reference.clone()
})
.collect(),
)
}
pub(super) fn write_modular_transforms(nb_chans: usize, rct_type: u32, w: &mut BitWriter) {
if nb_chans >= 3 {
w.write(2, 0b01);
write_rct_transform(rct_type, w);
} else {
w.write(2, 0b00); }
}
pub(crate) fn write_toc_entry(byte_len: usize, w: &mut BitWriter) {
static OFFSETS: [usize; 4] = [0, 1024, 17_408, 4_211_712];
static BITS: [usize; 4] = [10, 14, 22, 30];
let mut bucket = 0usize;
while bucket < 3 && byte_len >= OFFSETS[bucket + 1] {
bucket += 1;
}
w.write(2, bucket as u64);
w.write(BITS[bucket], (byte_len - OFFSETS[bucket]) as u64);
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn whole_image_crop_header_follows_full_frame_syntax() {
let bits = |has_alpha: bool, full: bool, last: bool| {
let mut w = BitWriter::new();
write_frame_header_modular_kind(
has_alpha,
ModularFrameKind::XybCrop {
x0: 0,
y0: 0,
width: 128,
height: 128,
full,
last,
},
GroupLayout::DEFAULT,
&mut w,
);
w.bits_written()
};
for has_alpha in [false, true] {
let sources = 2 * (1 + usize::from(has_alpha));
assert_eq!(
bits(has_alpha, true, true) + sources,
bits(has_alpha, false, true)
);
assert_eq!(
bits(has_alpha, true, false) + sources,
bits(has_alpha, false, false) + 1
);
}
}
fn entry(positions: Vec<(usize, usize)>, add: bool) -> PatchReference {
PatchReference {
atlas_x: 0,
atlas_y: 0,
width: 8,
height: 10,
ref_frame: PATCH_REF_ID,
alpha_only: false,
add,
mul: false,
positions,
}
}
fn scattered(n: usize) -> Vec<(usize, usize)> {
(0..n)
.map(|k| (k * 37 % n, k))
.map(|(a, _)| ((a % 25) * 20, (a / 25) * 20))
.collect()
}
#[test]
fn alpha_patch_keeps_color_patch_operations_independent() {
let color = entry(vec![(0, 0)], false);
let mut alpha = entry(vec![(20, 0)], false);
alpha.alpha_only = true;
let tokens = patch_dictionary_tokens(&[color, alpha], true);
let modes: Vec<_> = tokens
.iter()
.filter(|t| t.context == 5)
.map(|t| t.value)
.collect();
assert_eq!(modes, [1, 0, 0, 1]); }
#[test]
fn replace_occurrences_commute_only_without_overlap() {
assert!(occurrences_commute(&entry(
vec![(0, 0), (8, 0), (0, 10)],
false
)));
assert!(!occurrences_commute(&entry(
vec![(0, 0), (40, 3), (7, 9)],
false
)));
assert!(occurrences_commute(&entry(
vec![(0, 0), (40, 3), (7, 9)],
true
)));
}
#[test]
fn reorder_moves_only_commuting_entries_and_keeps_their_occurrences() {
let overlapping = entry(vec![(300, 0), (0, 0), (150, 0), (5, 5)], false);
let free = entry(scattered(200), false);
let reordered = reorder_occurrences(&[overlapping.clone(), free.clone()], None).unwrap();
assert_eq!(reordered[0].positions, overlapping.positions);
assert_ne!(reordered[1].positions, free.positions);
let mut a = reordered[1].positions.clone();
let mut b = free.positions.clone();
a.shared_sort();
b.shared_sort();
assert_eq!(a, b);
}
#[test]
fn dictionary_is_never_larger_than_in_given_order() {
let mut scratch = CoderScratch::default();
let references = [entry(scattered(200), false), entry(scattered(50), true)];
let given =
encode_patch_dictionary(&patch_dictionary_tokens(&references, false), &mut scratch);
let mut w = BitWriter::new();
write_patch_dictionary(&references, false, &mut scratch, &mut w);
assert!(w.bits_written() < given.bits_written());
}
#[test]
fn parallel_dictionary_matches_serial_with_shared_prices() {
let pool = crate::thread_pool::ThreadPool::new_lossless(4);
let references = [
entry(scattered(823), true),
entry(scattered(701), true),
entry(scattered(57), false),
entry(vec![(0, 0), (1, 0), (0, 1)], false),
];
let mut scratch = CoderScratch::lossless();
let serial_order = reorder_occurrences(&references, None).unwrap();
let parallel_order = reorder_occurrences(&references, Some((&pool, &mut scratch))).unwrap();
for (a, b) in serial_order.iter().zip(¶llel_order) {
assert_eq!(a.positions, b.positions);
}
let mut serial = BitWriter::new();
let mut parallel = BitWriter::new();
write_patch_dictionary(&references, false, &mut scratch, &mut serial);
write_patch_dictionary_with_pool(
&references,
false,
&mut scratch,
&mut parallel,
Some(&pool),
);
assert_eq!(serial.bits_written(), parallel.bits_written());
serial.zero_pad_to_byte();
parallel.zero_pad_to_byte();
assert_eq!(serial.into_bytes(), parallel.into_bytes());
}
}