about to implement huff

11 files changed, 253 insertions, 66 deletions

diff --git a/lvc/Cargo.lock b/lvc/Cargo.lock
index 2dd5615..d7bc0da 100644
--- a/lvc/Cargo.lock
+++ b/lvc/Cargo.lock
@@ -9,25 +9,6 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "d468802bab17cbc0cc575e9b053f41e72aa36bfa6b7f55e3529ffa43161b97fa"
 
 [[package]]
-name = "bincode"
-version = "2.0.0-rc.2"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "7bb50c5a2ef4b9b1e7ae73e3a73b52ea24b20312d629f9c4df28260b7ad2c3c4"
-dependencies = [
- "bincode_derive",
- "serde",
-]
-
-[[package]]
-name = "bincode_derive"
-version = "2.0.0-rc.2"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "0a45a23389446d2dd25dc8e73a7a3b3c43522b630cac068927f0649d43d719d2"
-dependencies = [
- "virtue",
-]
-
-[[package]]
 name = "bitflags"
 version = "1.3.2"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -211,7 +192,6 @@ checksum = "f051f77a7c8e6957c0696eac88f26b0117e54f52d3fc682ab19397a8812846a4"
 name = "lvc"
 version = "0.1.0"
 dependencies = [
- "bincode",
  "clap",
  "rayon",
 ]
@@ -332,12 +312,6 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "d29ab0c6d3fc0ee92fe66e2d99f700eab17a8d57d1c1d3b748380fb20baa78cd"
 
 [[package]]
-name = "serde"
-version = "1.0.152"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "bb7d1f0d3021d347a83e556fc4683dea2ea09d87bccdf88ff5c12545d89d5efb"
-
-[[package]]
 name = "strsim"
 version = "0.10.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -376,12 +350,6 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "49874b5167b65d7193b8aba1567f5c7d93d001cafc34600cee003eda787e483f"
 
 [[package]]
-name = "virtue"
-version = "0.0.8"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "7b60dcd6a64dd45abf9bd426970c9843726da7fc08f44cd6fcebf68c21220a63"
-
-[[package]]
 name = "winapi"
 version = "0.3.9"
 source = "registry+https://github.com/rust-lang/crates.io-index"
diff --git a/lvc/Cargo.toml b/lvc/Cargo.toml
index f53a95f..0a4a301 100644
--- a/lvc/Cargo.toml
+++ b/lvc/Cargo.toml
@@ -2,8 +2,8 @@
 name = "lvc"
 version = "0.1.0"
 edition = "2021"
+default-run = "main"
 
 [dependencies]
 rayon = "1.7.0"
-bincode = "2.0.0-rc.2"
 clap = { version = "4.1.8", features = ["derive"] }
diff --git a/lvc/src/bench.rs b/lvc/src/bin/bench.rs
index 48d220c..37036f6 100644
--- a/lvc/src/bench.rs
+++ b/lvc/src/bin/bench.rs
@@ -1,4 +1,4 @@
-use crate::{diff::*, Frame, Ref, View, P2};
+use lvc::{diff::*, Frame, Ref, View, P2};
 use std::time::Instant;
 
 fn measure(f: impl FnOnce()) {
@@ -8,8 +8,7 @@ fn measure(f: impl FnOnce()) {
     eprintln!("took {:?}", (t2 - t1));
 }
 
-#[test]
-fn bench_diff() {
+fn main() {
     let size = P2 { x: 2000, y: 2000 };
     let f1 = Frame::new(size);
     let f2 = Frame::new(size);
diff --git a/lvc/src/main.rs b/lvc/src/bin/main.rs
index 9d8a6cb..d5c9bbe 100644
--- a/lvc/src/main.rs
+++ b/lvc/src/bin/main.rs
@@ -1,4 +1,3 @@
-use bincode::config::standard;
 use clap::{Parser, Subcommand};
 use lvc::{
     debug::draw_debug,
@@ -23,6 +22,7 @@ struct Args {
     #[clap(subcommand)]
     action: Action,
 }
+
 #[derive(Clone, Subcommand)]
 enum Action {
     // Compress video
@@ -58,7 +58,7 @@ fn main() {
             let mut stdout = BufWriter::new(stdout());
 
             loop {
-                let b: Block = bincode::decode_from_std_read(&mut stdin, standard()).unwrap();
+                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 {
@@ -69,7 +69,8 @@ fn main() {
                     write_frame(&mut stdout, &frame);
                 }
 
-                last_frame.pixels.copy_from_slice(&frame.pixels);
+                last_frame.pixels.copy_from_slice(&frame.pixels); // TODO use mem::swap
+                frame.pixels.iter_mut().for_each(|e| *e = Pixel::BLACK);
             }
         }
         Action::Encode {
@@ -95,7 +96,7 @@ fn main() {
                 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();
+                b.write(&mut stdout);
 
                 decode(&last_frame, &mut frame, View::all(size), &b);
                 last_frame = frame;
@@ -126,9 +127,9 @@ fn write_frame(out: &mut impl Write, frame: &Frame) {
         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;
+            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<HT>, Box<HT>),
+    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::<Vec<_>>();
+
+        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<T> {
+    inner: T,
+    byte: u8,
+    position: usize,
+}
+impl<T> BitIO<T> {
+    pub fn new(inner: T) -> Self {
+        Self {
+            inner,
+            byte: 0,
+            position: 0,
+        }
+    }
+}
+impl<T: Write> BitIO<T> {
+    #[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<Pixel> {
@@ -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<Pixel>),
     Split(Box<Block>, Box<Block>),
+    Lit(Vec<Pixel>),
     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/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<Pixel> {
+        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<Pixel> {
+        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<P2> {
+        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<Block> {
+        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<u8> {
+    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<i16> {
+    Ok((read_byte(r)? as u16 | ((read_byte(r)? as u16) << 8)) as i16)
+}
diff --git a/lvc/tools/d-save b/lvc/tools/d-save
index b79d8de..270578a 100755
--- a/lvc/tools/d-save
+++ b/lvc/tools/d-save
@@ -1,2 +1,2 @@
 #!/bin/fish
-cargo run --release -- -w 1920 -h 1080 decode | ffmpeg -pixel_format rgb24 -video_size 1920x1080 -f rawvideo -i pipe:0 -i $argv[1] -map '0:v' -map '1:a'  -c:v libsvtav1 -y data/output.webm
+cargo run --release -- -w 1920 -h 1080 decode | ffmpeg -pixel_format rgb24 -video_size 1920x1080 -framerate 30 -f rawvideo -i pipe:0 -i $argv[1] -map '0:v' -map '1:a' -c:v libsvtav1 -y data/output.webm
diff --git a/lvc/tools/d-saved b/lvc/tools/d-saved
index f342106..833ae5d 100755
--- a/lvc/tools/d-saved
+++ b/lvc/tools/d-saved
@@ -1,2 +1,2 @@
 #!/bin/fish
-cargo run --release -- -w 1920 -h 1080 decode --debug | ffmpeg -pixel_format rgb24 -video_size 1920x1080 -f rawvideo -i pipe:0 -i $argv[1] -map '0:v' -map '1:a'  -c:v libsvtav1 -y data/output-debug.webm
+cargo run --release -- -w 1920 -h 1080 decode --debug | ffmpeg -pixel_format rgb24 -video_size 1920x1080 -framerate 30 -f rawvideo -i pipe:0 -i $argv[1] -map '0:v' -map '1:a' -c:v libsvtav1 -y data/output-debug.webm