From 292519649c4244adb6672488efe7c2e906726c58 Mon Sep 17 00:00:00 2001 From: metamuffin Date: Wed, 8 Mar 2023 21:26:35 +0100 Subject: about to implement huff --- lvc/src/bench.rs | 29 ----------- lvc/src/bin/bench.rs | 28 +++++++++++ lvc/src/bin/main.rs | 136 +++++++++++++++++++++++++++++++++++++++++++++++++++ lvc/src/encode.rs | 26 +++++----- lvc/src/huff.rs | 85 ++++++++++++++++++++++++++++++++ lvc/src/impls.rs | 9 +++- lvc/src/lib.rs | 18 +++---- lvc/src/main.rs | 135 -------------------------------------------------- lvc/src/serialize.rs | 123 ++++++++++++++++++++++++++++++++++++++++++++++ 9 files changed, 404 insertions(+), 185 deletions(-) delete mode 100644 lvc/src/bench.rs create mode 100644 lvc/src/bin/bench.rs create mode 100644 lvc/src/bin/main.rs create mode 100644 lvc/src/huff.rs delete mode 100644 lvc/src/main.rs create mode 100644 lvc/src/serialize.rs (limited to 'lvc/src') diff --git a/lvc/src/bench.rs b/lvc/src/bench.rs deleted file mode 100644 index 48d220c..0000000 --- a/lvc/src/bench.rs +++ /dev/null @@ -1,29 +0,0 @@ -use crate::{diff::*, Frame, Ref, View, P2}; -use std::time::Instant; - -fn measure(f: impl FnOnce()) { - let t1 = Instant::now(); - f(); - let t2 = Instant::now(); - eprintln!("took {:?}", (t2 - t1)); -} - -#[test] -fn bench_diff() { - let size = P2 { x: 2000, y: 2000 }; - let f1 = Frame::new(size); - let f2 = Frame::new(size); - measure(|| { - diff([&f1, &f2], View::all(size), Ref::default()); - }); -} - -// #[test] -// fn bench_fast_diff() { -// let size = P2 { x: 2000, y: 2000 }; -// let f1 = Frame::new(size); -// let f2 = Frame::new(size); -// measure(|| { -// diff_fast([&f1, &f2], View::all(size), Ref::default()); -// }); -// } diff --git a/lvc/src/bin/bench.rs b/lvc/src/bin/bench.rs new file mode 100644 index 0000000..37036f6 --- /dev/null +++ b/lvc/src/bin/bench.rs @@ -0,0 +1,28 @@ +use lvc::{diff::*, Frame, Ref, View, P2}; +use std::time::Instant; + +fn measure(f: impl FnOnce()) { + let t1 = Instant::now(); + f(); + let t2 = Instant::now(); + eprintln!("took {:?}", (t2 - t1)); +} + +fn main() { + let size = P2 { x: 2000, y: 2000 }; + let f1 = Frame::new(size); + let f2 = Frame::new(size); + measure(|| { + diff([&f1, &f2], View::all(size), Ref::default()); + }); +} + +// #[test] +// fn bench_fast_diff() { +// let size = P2 { x: 2000, y: 2000 }; +// let f1 = Frame::new(size); +// let f2 = Frame::new(size); +// measure(|| { +// diff_fast([&f1, &f2], View::all(size), Ref::default()); +// }); +// } diff --git a/lvc/src/bin/main.rs b/lvc/src/bin/main.rs new file mode 100644 index 0000000..d5c9bbe --- /dev/null +++ b/lvc/src/bin/main.rs @@ -0,0 +1,136 @@ +use clap::{Parser, Subcommand}; +use lvc::{ + debug::draw_debug, + decode::decode, + encode::{encode, EncodeConfig}, + Block, Frame, Pixel, PixelValue, View, P2, +}; +use std::{ + io::{stdin, stdout, BufReader, BufWriter, Read, Write}, + time::Instant, +}; + +#[derive(Parser)] +#[clap(about, version)] +struct Args { + // Width of the video signal + #[arg(short, long)] + width: u16, + // Height of the video signal + #[arg(short, long)] + height: u16, + #[clap(subcommand)] + action: Action, +} + +#[derive(Clone, Subcommand)] +enum Action { + // Compress video + Encode { + #[arg(short, long, default_value_t = 400)] + max_block_size: usize, + #[arg(short, long, default_value_t = 10)] + iters: usize, + #[arg(short, long, default_value_t = 5_000)] + threshold: u32, + }, + // Decompress video + Decode { + #[arg(short, long)] + debug: bool, + }, +} + +fn main() { + let args = Args::parse(); + + let size = P2 { + x: args.width as i32, + y: args.height as i32, + }; + match args.action { + Action::Decode { debug } => { + let mut frame = Frame::new(size); + let mut last_frame = Frame::new(size); + let mut debug_frame = if debug { Some(Frame::new(size)) } else { None }; + + let mut stdin = BufReader::new(stdin()); + let mut stdout = BufWriter::new(stdout()); + + loop { + let b = Block::read(&mut stdin, View::all(size)).unwrap(); + decode(&last_frame, &mut frame, View::all(size), &b); + + if let Some(debug_frame) = &mut debug_frame { + debug_frame.pixels.copy_from_slice(&frame.pixels); + draw_debug(debug_frame, View::all(size), &b); + write_frame(&mut stdout, &debug_frame); + } else { + write_frame(&mut stdout, &frame); + } + + last_frame.pixels.copy_from_slice(&frame.pixels); // TODO use mem::swap + frame.pixels.iter_mut().for_each(|e| *e = Pixel::BLACK); + } + } + Action::Encode { + max_block_size, + threshold, + iters, + } => { + let config = EncodeConfig { + threshold, + max_block_size, + iters, + }; + + let mut last_frame = Frame::new(size); + + let mut stdin = BufReader::new(stdin()); + let mut stdout = BufWriter::new(stdout()); + + for frame_number in 0.. { + let mut frame = read_frame(&mut stdin, size); + + let t = Instant::now(); + let b: Block = encode(&last_frame, &frame, View::all(size), &config); + eprintln!("frame {frame_number} took {:?}", t.elapsed()); + + b.write(&mut stdout); + + decode(&last_frame, &mut frame, View::all(size), &b); + last_frame = frame; + } + } + } +} + +fn read_frame(inp: &mut impl Read, size: P2) -> Frame { + let mut f = Frame::new(size); + + for y in 0..size.y { + for x in 0..size.x { + let mut cc = [0u8; 3]; + inp.read_exact(&mut cc).unwrap(); + f[P2 { x, y }] = Pixel { + r: cc[0] as PixelValue, + g: cc[1] as PixelValue, + b: cc[2] as PixelValue, + }; + } + } + f +} + +fn write_frame(out: &mut impl Write, frame: &Frame) { + for y in 0..frame.size.y { + for x in 0..frame.size.x { + let p = frame[P2 { x, y }]; + let mut cc = [0u8; 3]; + cc[0] = p.r.clamp(0, 255) as u8; + cc[1] = p.g.clamp(0, 255) as u8; + cc[2] = p.b.clamp(0, 255) as u8; + out.write_all(&mut cc).unwrap(); + } + } +} diff --git a/lvc/src/encode.rs b/lvc/src/encode.rs index fde4f94..4ec72cf 100644 --- a/lvc/src/encode.rs +++ b/lvc/src/encode.rs @@ -49,14 +49,18 @@ pub fn optimize_ref( frame: &Frame, view: View, r: Ref, - granularity: i32, + g: i32, target_average: Pixel, ) -> (u32, Ref) { [ - Some(r.apply(|r| r.pos_off.x += granularity)), - Some(r.apply(|r| r.pos_off.x -= granularity)), - Some(r.apply(|r| r.pos_off.y += granularity)), - Some(r.apply(|r| r.pos_off.y -= granularity)), + Some(r.apply(|r| r.pos_off += P2 { x: g, y: 0 })), + Some(r.apply(|r| r.pos_off += P2 { x: g, y: g })), + Some(r.apply(|r| r.pos_off += P2 { x: 0, y: g })), + Some(r.apply(|r| r.pos_off += P2 { x: -g, y: g })), + Some(r.apply(|r| r.pos_off += P2 { x: -g, y: 0 })), + Some(r.apply(|r| r.pos_off += P2 { x: -g, y: -g })), + Some(r.apply(|r| r.pos_off += P2 { x: 0, y: -g })), + Some(r.apply(|r| r.pos_off += P2 { x: g, y: -g })), { let mut r = r; let last_avr = average_color(last_frame, view); @@ -68,12 +72,12 @@ pub fn optimize_ref( None } }, - // n(|r, g| r.color_off.r += (g as i16) << 2); - // n(|r, g| r.color_off.r -= (g as i16) << 2); - // n(|r, g| r.color_off.g += (g as i16) << 2); - // n(|r, g| r.color_off.g -= (g as i16) << 2); - // n(|r, g| r.color_off.b += (g as i16) << 2); - // n(|r, g| r.color_off.b -= (g as i16) << 2); + // Some(r.apply(|r| r.color_off.r += (g as i16) << 2)), + // Some(r.apply(|r| r.color_off.r -= (g as i16) << 2)), + // Some(r.apply(|r| r.color_off.g += (g as i16) << 2)), + // Some(r.apply(|r| r.color_off.g -= (g as i16) << 2)), + // Some(r.apply(|r| r.color_off.b += (g as i16) << 2)), + // Some(r.apply(|r| r.color_off.b -= (g as i16) << 2)), ] .into_iter() .flatten() diff --git a/lvc/src/huff.rs b/lvc/src/huff.rs new file mode 100644 index 0000000..5943207 --- /dev/null +++ b/lvc/src/huff.rs @@ -0,0 +1,85 @@ +use std::io::Write; + +#[derive(Debug, Clone)] +enum HT { + Branch(Box, Box), + Terminal(u8), +} + +fn write_huffman(buf: &[u8], w: &mut impl Write) -> usize { + let mut w = BitIO::new(w); + + let mut probs = [0usize; 256]; + for b in buf { + probs[*b as usize] += 1; + } + + let tree = HT::from_probabilities(probs); + let mut table = [0u16; 256]; + tree.create_lut(&mut table, 1); + + for b in buf { + let mut k = table[*b as usize]; + while k != 1 { + w.wbit(k & 1 == 1); + k <<= 1; + } + } + + w.position +} + +impl HT { + pub fn from_probabilities(ps: [usize; 256]) -> Self { + let mut parts = ps + .into_iter() + .enumerate() + .map(|(n, p)| (p, HT::Terminal(n as u8))) + .collect::>(); + + while parts.len() != 1 { + parts.sort_by_key(|e| -(e.0 as isize)); + let ((ap, at), (bp, bt)) = (parts.pop().unwrap(), parts.pop().unwrap()); + parts.push((ap + bp, HT::Branch(box at, box bt))) + } + parts[0].1.clone() + } + pub fn create_lut(&self, table: &mut [u16; 256], prefix: u16) { + match self { + HT::Branch(a, b) => { + a.create_lut(table, (prefix << 1) | 0); + b.create_lut(table, (prefix << 1) | 1); + } + HT::Terminal(n) => { + assert_eq!(table[*n as usize], 0); + table[*n as usize] = prefix + } + } + } +} + +struct BitIO { + inner: T, + byte: u8, + position: usize, +} +impl BitIO { + pub fn new(inner: T) -> Self { + Self { + inner, + byte: 0, + position: 0, + } + } +} +impl BitIO { + #[inline] + pub fn wbit(&mut self, b: bool) { + self.byte <<= 1; + self.byte |= b as u8; + self.position += 1; + if self.position & 0b111 == 0 { + self.inner.write_all(&[self.byte]).unwrap(); + } + } +} diff --git a/lvc/src/impls.rs b/lvc/src/impls.rs index 04699c6..098db39 100644 --- a/lvc/src/impls.rs +++ b/lvc/src/impls.rs @@ -1,5 +1,5 @@ use crate::{Frame, Pixel, Ref, View, P2}; -use std::ops::{Add, Index, IndexMut, Sub}; +use std::ops::{Add, AddAssign, Index, IndexMut, Sub}; impl Frame { pub fn export(&self, view: View) -> Vec { @@ -18,6 +18,7 @@ impl Frame { source = &source[1..]; } } + assert_eq!(source.len(), 0) } pub fn new(size: P2) -> Self { Self { @@ -39,6 +40,12 @@ impl Pixel { pub const GREEN: Pixel = Pixel { r: 0, g: 255, b: 0 }; pub const BLUE: Pixel = Pixel { r: 0, g: 0, b: 255 }; } +impl AddAssign for P2 { + fn add_assign(&mut self, rhs: Self) { + self.x += rhs.x; + self.y += rhs.y; + } +} impl Add for Pixel { type Output = Pixel; #[inline] diff --git a/lvc/src/lib.rs b/lvc/src/lib.rs index 94a432d..5ebd91c 100644 --- a/lvc/src/lib.rs +++ b/lvc/src/lib.rs @@ -1,26 +1,26 @@ #![feature(portable_simd)] +#![feature(io_error_other)] +#![feature(box_syntax)] -use bincode::{Decode, Encode}; - -#[cfg(test)] -pub mod bench; pub mod debug; pub mod decode; pub mod diff; pub mod encode; +pub mod huff; pub mod impls; +pub mod serialize; pub mod split; pub type PixelValue = i16; -#[derive(Debug, Clone, Copy, Default, Encode, Decode, PartialEq, Eq)] +#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)] pub struct Pixel { pub r: PixelValue, pub g: PixelValue, pub b: PixelValue, } -#[derive(Debug, Clone, Copy, Default, Encode, Decode, PartialEq, Eq)] +#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)] pub struct P2 { pub x: i32, pub y: i32, @@ -37,14 +37,14 @@ pub struct View { pub b: P2, } -#[derive(Debug, Clone, Encode, Decode)] +#[derive(Debug, Clone)] pub enum Block { - Lit(Vec), Split(Box, Box), + Lit(Vec), Ref(Ref), } -#[derive(Debug, Clone, Copy, Default, Encode, Decode)] +#[derive(Debug, Clone, Copy, Default)] pub struct Ref { pub pos_off: P2, pub color_off: Pixel, diff --git a/lvc/src/main.rs b/lvc/src/main.rs deleted file mode 100644 index 9d8a6cb..0000000 --- a/lvc/src/main.rs +++ /dev/null @@ -1,135 +0,0 @@ -use bincode::config::standard; -use clap::{Parser, Subcommand}; -use lvc::{ - debug::draw_debug, - decode::decode, - encode::{encode, EncodeConfig}, - Block, Frame, Pixel, PixelValue, View, P2, -}; -use std::{ - io::{stdin, stdout, BufReader, BufWriter, Read, Write}, - time::Instant, -}; - -#[derive(Parser)] -#[clap(about, version)] -struct Args { - // Width of the video signal - #[arg(short, long)] - width: u16, - // Height of the video signal - #[arg(short, long)] - height: u16, - #[clap(subcommand)] - action: Action, -} -#[derive(Clone, Subcommand)] -enum Action { - // Compress video - Encode { - #[arg(short, long, default_value_t = 400)] - max_block_size: usize, - #[arg(short, long, default_value_t = 10)] - iters: usize, - #[arg(short, long, default_value_t = 5_000)] - threshold: u32, - }, - // Decompress video - Decode { - #[arg(short, long)] - debug: bool, - }, -} - -fn main() { - let args = Args::parse(); - - let size = P2 { - x: args.width as i32, - y: args.height as i32, - }; - match args.action { - Action::Decode { debug } => { - let mut frame = Frame::new(size); - let mut last_frame = Frame::new(size); - let mut debug_frame = if debug { Some(Frame::new(size)) } else { None }; - - let mut stdin = BufReader::new(stdin()); - let mut stdout = BufWriter::new(stdout()); - - loop { - let b: Block = bincode::decode_from_std_read(&mut stdin, standard()).unwrap(); - decode(&last_frame, &mut frame, View::all(size), &b); - - if let Some(debug_frame) = &mut debug_frame { - debug_frame.pixels.copy_from_slice(&frame.pixels); - draw_debug(debug_frame, View::all(size), &b); - write_frame(&mut stdout, &debug_frame); - } else { - write_frame(&mut stdout, &frame); - } - - last_frame.pixels.copy_from_slice(&frame.pixels); - } - } - Action::Encode { - max_block_size, - threshold, - iters, - } => { - let config = EncodeConfig { - threshold, - max_block_size, - iters, - }; - - let mut last_frame = Frame::new(size); - - let mut stdin = BufReader::new(stdin()); - let mut stdout = BufWriter::new(stdout()); - - for frame_number in 0.. { - let mut frame = read_frame(&mut stdin, size); - - let t = Instant::now(); - let b: Block = encode(&last_frame, &frame, View::all(size), &config); - eprintln!("frame {frame_number} took {:?}", t.elapsed()); - - bincode::encode_into_std_write(&b, &mut stdout, standard()).unwrap(); - - decode(&last_frame, &mut frame, View::all(size), &b); - last_frame = frame; - } - } - } -} - -fn read_frame(inp: &mut impl Read, size: P2) -> Frame { - let mut f = Frame::new(size); - - for y in 0..size.y { - for x in 0..size.x { - let mut cc = [0u8; 3]; - inp.read_exact(&mut cc).unwrap(); - f[P2 { x, y }] = Pixel { - r: cc[0] as PixelValue, - g: cc[1] as PixelValue, - b: cc[2] as PixelValue, - }; - } - } - f -} - -fn write_frame(out: &mut impl Write, frame: &Frame) { - for y in 0..frame.size.y { - for x in 0..frame.size.x { - let p = frame[P2 { x, y }]; - let mut cc = [0u8; 3]; - cc[0] = p.r as u8; - cc[1] = p.g as u8; - cc[2] = p.b as u8; - out.write_all(&mut cc).unwrap(); - } - } -} diff --git a/lvc/src/serialize.rs b/lvc/src/serialize.rs new file mode 100644 index 0000000..ac6230e --- /dev/null +++ b/lvc/src/serialize.rs @@ -0,0 +1,123 @@ +use crate::split::split; +use crate::Block; +use crate::Pixel; +use crate::Ref; +use crate::View; +use crate::P2; +use std::io::Read; +use std::io::Result; +use std::io::Write; + +impl Pixel { + #[inline] + pub fn write(&self, w: &mut impl Write) -> Result<()> { + w.write_all(&[ + self.r.clamp(0, 255) as u8, + self.g.clamp(0, 255) as u8, + self.b.clamp(0, 255) as u8, + ]) + } + #[inline] + pub fn read(r: &mut impl Read) -> Result { + Ok(Self { + r: read_byte(r)? as i16, + g: read_byte(r)? as i16, + b: read_byte(r)? as i16, + }) + } +} +impl Pixel { + #[inline] + pub fn write_full(&self, w: &mut impl Write) -> Result<()> { + write_word(w, self.r)?; + write_word(w, self.g)?; + write_word(w, self.b)?; + Ok(()) + } + #[inline] + pub fn read_full(r: &mut impl Read) -> Result { + Ok(Self { + r: read_word(r)?, + g: read_word(r)?, + b: read_word(r)?, + }) + } +} +impl P2 { + #[inline] + pub fn write(&self, w: &mut impl Write) -> Result<()> { + write_word(w, self.x as i16)?; + write_word(w, self.y as i16)?; + Ok(()) + } + + #[inline] + pub fn read(r: &mut impl Read) -> Result { + Ok(Self { + x: read_word(r)? as i32, + y: read_word(r)? as i32, + }) + } +} + +impl Block { + pub fn write(&self, w: &mut impl Write) -> Result<()> { + match self { + Block::Split(a, b) => { + w.write_all(&[0])?; + a.write(w)?; + b.write(w)?; + } + Block::Lit(pixels) => { + w.write_all(&[1])?; + for p in pixels { + p.write(w)?; + } + } + Block::Ref(k) => { + w.write_all(&[2])?; + k.pos_off.write(w)?; + k.color_off.write_full(w)?; + } + } + Ok(()) + } + pub fn read(r: &mut impl Read, view: View) -> Result { + match read_byte(r)? { + 0 => { + let [av, bv] = split(view); + Ok(Block::Split( + box Block::read(r, av)?, + box Block::read(r, bv)?, + )) + } + 1 => { + let mut px = vec![]; + for _ in 0..view.size().area() { + px.push(Pixel::read(r)?) + } + Ok(Block::Lit(px)) + } + 2 => Ok(Block::Ref(Ref { + pos_off: P2::read(r)?, + color_off: Pixel::read_full(r)?, + })), + _ => Err(std::io::Error::other("unknown block variant")), + } + } +} + +#[inline] +fn read_byte(r: &mut impl Read) -> Result { + let mut buf = [0u8]; + r.read_exact(&mut buf)?; + Ok(buf[0]) +} +#[inline] +fn write_word(w: &mut impl Write, v: i16) -> Result<()> { + w.write_all(&[(v & 0xff) as u8, (v >> 8) as u8]) +} +#[inline] +fn read_word(r: &mut impl Read) -> Result { + Ok((read_byte(r)? as u16 | ((read_byte(r)? as u16) << 8)) as i16) +} -- cgit v1.2.3-70-g09d2