a

3 files changed, 274 insertions, 42 deletions

diff --git a/tweak/Cargo.lock b/tweak/Cargo.lock
index 7f45493..6093019 100644
--- a/tweak/Cargo.lock
+++ b/tweak/Cargo.lock
@@ -3,5 +3,154 @@
 version = 3
 
 [[package]]
+name = "autocfg"
+version = "1.1.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "d468802bab17cbc0cc575e9b053f41e72aa36bfa6b7f55e3529ffa43161b97fa"
+
+[[package]]
+name = "cfg-if"
+version = "1.0.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "baf1de4339761588bc0619e3cbc0120ee582ebb74b53b4efbf79117bd2da40fd"
+
+[[package]]
+name = "crossbeam-deque"
+version = "0.8.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "ce6fd6f855243022dcecf8702fef0c297d4338e226845fe067f6341ad9fa0cef"
+dependencies = [
+ "cfg-if",
+ "crossbeam-epoch",
+ "crossbeam-utils",
+]
+
+[[package]]
+name = "crossbeam-epoch"
+version = "0.9.15"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "ae211234986c545741a7dc064309f67ee1e5ad243d0e48335adc0484d960bcc7"
+dependencies = [
+ "autocfg",
+ "cfg-if",
+ "crossbeam-utils",
+ "memoffset",
+ "scopeguard",
+]
+
+[[package]]
+name = "crossbeam-utils"
+version = "0.8.16"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "5a22b2d63d4d1dc0b7f1b6b2747dd0088008a9be28b6ddf0b1e7d335e3037294"
+dependencies = [
+ "cfg-if",
+]
+
+[[package]]
+name = "either"
+version = "1.9.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "a26ae43d7bcc3b814de94796a5e736d4029efb0ee900c12e2d54c993ad1a1e07"
+
+[[package]]
+name = "getrandom"
+version = "0.2.11"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "fe9006bed769170c11f845cf00c7c1e9092aeb3f268e007c3e760ac68008070f"
+dependencies = [
+ "cfg-if",
+ "libc",
+ "wasi",
+]
+
+[[package]]
+name = "libc"
+version = "0.2.150"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "89d92a4743f9a61002fae18374ed11e7973f530cb3a3255fb354818118b2203c"
+
+[[package]]
+name = "memoffset"
+version = "0.9.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "5a634b1c61a95585bd15607c6ab0c4e5b226e695ff2800ba0cdccddf208c406c"
+dependencies = [
+ "autocfg",
+]
+
+[[package]]
+name = "ppv-lite86"
+version = "0.2.17"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "5b40af805b3121feab8a3c29f04d8ad262fa8e0561883e7653e024ae4479e6de"
+
+[[package]]
+name = "rand"
+version = "0.8.5"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "34af8d1a0e25924bc5b7c43c079c942339d8f0a8b57c39049bef581b46327404"
+dependencies = [
+ "libc",
+ "rand_chacha",
+ "rand_core",
+]
+
+[[package]]
+name = "rand_chacha"
+version = "0.3.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "e6c10a63a0fa32252be49d21e7709d4d4baf8d231c2dbce1eaa8141b9b127d88"
+dependencies = [
+ "ppv-lite86",
+ "rand_core",
+]
+
+[[package]]
+name = "rand_core"
+version = "0.6.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "ec0be4795e2f6a28069bec0b5ff3e2ac9bafc99e6a9a7dc3547996c5c816922c"
+dependencies = [
+ "getrandom",
+]
+
+[[package]]
+name = "rayon"
+version = "1.8.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "9c27db03db7734835b3f53954b534c91069375ce6ccaa2e065441e07d9b6cdb1"
+dependencies = [
+ "either",
+ "rayon-core",
+]
+
+[[package]]
+name = "rayon-core"
+version = "1.12.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "5ce3fb6ad83f861aac485e76e1985cd109d9a3713802152be56c3b1f0e0658ed"
+dependencies = [
+ "crossbeam-deque",
+ "crossbeam-utils",
+]
+
+[[package]]
+name = "scopeguard"
+version = "1.2.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "94143f37725109f92c262ed2cf5e59bce7498c01bcc1502d7b9afe439a4e9f49"
+
+[[package]]
 name = "tweak"
 version = "0.1.0"
+dependencies = [
+ "rand",
+ "rayon",
+]
+
+[[package]]
+name = "wasi"
+version = "0.11.0+wasi-snapshot-preview1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "9c8d87e72b64a3b4db28d11ce29237c246188f4f51057d65a7eab63b7987e423"
diff --git a/tweak/Cargo.toml b/tweak/Cargo.toml
index 813497e..2c19efb 100644
--- a/tweak/Cargo.toml
+++ b/tweak/Cargo.toml
@@ -3,6 +3,6 @@ name = "tweak"
 version = "0.1.0"
 edition = "2021"
 
-# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
-
 [dependencies]
+rayon = "1.8.0"
+rand = "0.8.5"
diff --git a/tweak/src/main.rs b/tweak/src/main.rs
index a46d561..b2144a3 100644
--- a/tweak/src/main.rs
+++ b/tweak/src/main.rs
@@ -1,6 +1,7 @@
+use rayon::join;
 use std::{
     io::{stdin, stdout, Read, Write},
-    ops::Index,
+    time::Instant,
 };
 
 const WIDTH: usize = 1920;
@@ -8,42 +9,115 @@ const HEIGHT: usize = 1080;
 
 fn main() {
     let mut oframe = Frame::new();
+    let mut dframe = Frame::new();
+    let mut out = Vec::<u8>::new();
+    let do_debug = false;
     loop {
+        let timer = Instant::now();
         let iframe = Frame::read(stdin());
 
-        // let diff = oframe.average_area_diff(&iframe, Area::root());
-        // eprintln!("{diff:?}");
+        let t = encode(&oframe, &iframe, Area::root());
+        decode(&mut oframe, Area::root(), &t);
 
-        oframe.apply_area_diff(Area::root(), diff);
+        write(&mut out, &t);
 
-        oframe.write(stdout());
-        // oframe = iframe;
+        if do_debug {
+            dframe.0.copy_from_slice(&oframe.0);
+            debug(&mut dframe, Area::root(), &t);
+            dframe.write(stdout());
+        } else {
+            oframe.write(stdout());
+        }
+
+        eprintln!(
+            "compression={:.01} time={:?}",
+            (WIDTH * HEIGHT * 3) as f64 / out.len() as f64,
+            timer.elapsed()
+        );
+        out.clear();
     }
 }
 
-pub fn decode(f: &mut Frame, area: Area, tree: DiffTree) {
-    oframe.apply_area_diff(Area::root(), diff);
-
-} 
+pub fn write(w: &mut Vec<u8>, t: &DiffTree) {
+    match t {
+        DiffTree::Split([a, b]) => {
+            w.push(0);
+            write(w, a);
+            write(w, b);
+        }
+        DiffTree::Diff(d) => w.extend([1, d.0[0] as u8, d.0[1] as u8, d.0[2] as u8]),
+    }
+}
 
-pub enum DiffTree {
-    Split([Box<DiffTree>; 2]),
-    Diff(PixelDiff),
+pub fn decode(f: &mut Frame, area: Area, tree: &DiffTree) {
+    match tree {
+        DiffTree::Split([ta, tb]) => {
+            let (aa, ab) = area.split();
+            decode(f, aa, ta);
+            decode(f, ab, tb);
+        }
+        DiffTree::Diff(diff) => {
+            f.apply_area_diff(area, *diff);
+        }
+    }
+}
+pub fn debug(f: &mut Frame, area: Area, tree: &DiffTree) {
+    match tree {
+        DiffTree::Split([ta, tb]) => {
+            let (aa, ab) = area.split();
+            decode(f, aa, ta);
+            decode(f, ab, tb);
+        }
+        DiffTree::Diff(_diff) => {
+            let Area { x1, y1, x2, y2 } = area;
+            for x in x1..x2 {
+                for y in y1..y2 {
+                    let o = (x + y * WIDTH) * 3;
+                    f.0[o + 0] = 255;
+                    f.0[o + 1] = 0;
+                    f.0[o + 2] = 255;
+                }
+            }
+        }
+    }
 }
 
-pub fn stuff(a: &Frame, b: &Frame, area: Area) -> DiffTree {
+pub fn encode(a: &Frame, b: &Frame, area: Area) -> DiffTree {
     if area.area() == 1 {
         DiffTree::Diff(Frame::diff_pixel(a, b, area.x1, area.y1))
     } else {
         let (aa, ba) = area.split();
-        let (at, bt) = (stuff(a, b, aa), stuff(a, b, ba));
+        let (at, bt) = join(|| encode(a, b, aa), || encode(a, b, ba));
+
+        match (&at, &bt) {
+            (DiffTree::Diff(ad), DiffTree::Diff(bd)) => {
+                let d_r = ad.0[0].abs_diff(bd.0[0]);
+                let d_g = ad.0[1].abs_diff(bd.0[1]);
+                let d_b = ad.0[2].abs_diff(bd.0[2]);
+
+                let visdiff = (d_r as usize + d_g as usize + d_b as usize) * aa.area();
+                if visdiff < 100 {
+                    return DiffTree::Diff(PixelDiff([
+                        ((ad.0[0] as i16 + bd.0[0] as i16) / 2) as i8,
+                        ((ad.0[1] as i16 + bd.0[1] as i16) / 2) as i8,
+                        ((ad.0[2] as i16 + bd.0[2] as i16) / 2) as i8,
+                    ]));
+                }
+            }
+            _ => (),
+        }
         DiffTree::Split([Box::new(at), Box::new(bt)])
     }
 }
 
+pub enum DiffTree {
+    Split([Box<DiffTree>; 2]),
+    Diff(PixelDiff),
+}
+
 #[derive(Debug)]
 pub struct Frame(Vec<u8>);
-#[derive(Debug)]
+#[derive(Debug, Clone, Copy)]
 pub struct PixelDiff([i8; 3]);
 #[derive(Debug, Clone, Copy)]
 pub struct Area {
@@ -53,6 +127,15 @@ pub struct Area {
     y2: usize,
 }
 
+#[inline]
+fn diff_clamp(x: u8, y: u8) -> i8 {
+    if y >= x {
+        (y - x).min(127) as i8
+    } else {
+        -((x - y).min(128) as i8)
+    }
+}
+
 impl Frame {
     pub fn new() -> Self {
         Self(vec![0u8; WIDTH * HEIGHT * 3])
@@ -69,9 +152,9 @@ impl Frame {
     pub fn diff_pixel(a: &Frame, b: &Frame, x: usize, y: usize) -> PixelDiff {
         let o = (x + y * WIDTH) * 3;
         PixelDiff([
-            (a.0[o + 0] as i16 - b.0[o + 0] as i16).clamp(i8::MIN as i16, i8::MAX as i16) as i8,
-            (a.0[o + 1] as i16 - b.0[o + 1] as i16).clamp(i8::MIN as i16, i8::MAX as i16) as i8,
-            (a.0[o + 2] as i16 - b.0[o + 2] as i16).clamp(i8::MIN as i16, i8::MAX as i16) as i8,
+            diff_clamp(a.0[o + 0], b.0[o + 0]),
+            diff_clamp(a.0[o + 1], b.0[o + 1]),
+            diff_clamp(a.0[o + 2], b.0[o + 2]),
         ])
     }
 
@@ -85,27 +168,27 @@ impl Frame {
             }
         }
     }
-    pub fn average_area_diff(
-        &self,
-        other: &Frame,
-        area @ Area { x1, y1, x2, y2 }: Area,
-    ) -> PixelDiff {
-        let (mut r, mut g, mut b) = (0i32, 0i32, 0i32);
-        for x in x1..x2 {
-            for y in y1..y2 {
-                let o = (x + y * WIDTH) * 3;
-                r += other.0[o + 0] as i32 - self.0[o + 0] as i32;
-                g += other.0[o + 1] as i32 - self.0[o + 1] as i32;
-                b += other.0[o + 2] as i32 - self.0[o + 2] as i32;
-            }
-        }
-        let a = area.area() as i32;
-        PixelDiff([
-            (r / a).clamp(i8::MIN as i32, i8::MAX as i32) as i8,
-            (g / a).clamp(i8::MIN as i32, i8::MAX as i32) as i8,
-            (b / a).clamp(i8::MIN as i32, i8::MAX as i32) as i8,
-        ])
-    }
+    // pub fn average_area_diff(
+    //     &self,
+    //     other: &Frame,
+    //     area @ Area { x1, y1, x2, y2 }: Area,
+    // ) -> PixelDiff {
+    //     let (mut r, mut g, mut b) = (0i32, 0i32, 0i32);
+    //     for x in x1..x2 {
+    //         for y in y1..y2 {
+    //             let o = (x + y * WIDTH) * 3;
+    //             r += other.0[o + 0] as i32 - self.0[o + 0] as i32;
+    //             g += other.0[o + 1] as i32 - self.0[o + 1] as i32;
+    //             b += other.0[o + 2] as i32 - self.0[o + 2] as i32;
+    //         }
+    //     }
+    //     let a = area.area() as i32;
+    //     PixelDiff([
+    //         (r / a).clamp(i8::MIN as i32, i8::MAX as i32) as i8,
+    //         (g / a).clamp(i8::MIN as i32, i8::MAX as i32) as i8,
+    //         (b / a).clamp(i8::MIN as i32, i8::MAX as i32) as i8,
+    //     ])
+    // }
 }
 impl Area {
     pub fn area(&self) -> usize {