works

9 files changed, 260 insertions, 117 deletions

diff --git a/lvc/src/bench.rs b/lvc/src/bench.rs
new file mode 100644
index 0000000..91b13b6
--- /dev/null
+++ b/lvc/src/bench.rs
@@ -0,0 +1,19 @@
+use crate::{diff::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(move || {
+        diff([&f1, &f2], View::all(size), Ref::default());
+    })
+}
diff --git a/lvc/src/debug.rs b/lvc/src/debug.rs
new file mode 100644
index 0000000..9959e9a
--- /dev/null
+++ b/lvc/src/debug.rs
@@ -0,0 +1,30 @@
+use crate::{split::split, Block, Frame, Pixel, View, P2};
+
+pub fn draw_debug(frame: &mut Frame, view: View, block: &Block) {
+    match block {
+        Block::Lit(_) => rect(frame, view, Pixel::GREEN),
+        Block::Split([a, b]) => {
+            let [av, bv] = split(view);
+            draw_debug(frame, av, &a);
+            draw_debug(frame, bv, &b);
+        }
+        Block::Ref(_r) => {}
+    }
+}
+
+fn rect(frame: &mut Frame, view: View, color: Pixel) {
+    for x in view.a.x..view.b.x {
+        frame[P2 { x, y: view.a.y }] = color;
+        frame[P2 { x, y: view.b.y - 1 }] = color;
+    }
+    for y in view.a.y..view.b.y {
+        frame[P2 { y, x: view.a.x }] = color;
+        frame[P2 { y, x: view.b.x - 1 }] = color;
+    }
+}
+
+impl Pixel {
+    pub const RED: Pixel = Pixel { r: 255, g: 0, b: 0 };
+    pub const GREEN: Pixel = Pixel { r: 0, g: 255, b: 0 };
+    pub const BLUE: Pixel = Pixel { r: 0, g: 0, b: 255 };
+}
diff --git a/lvc/src/decode.rs b/lvc/src/decode.rs
new file mode 100644
index 0000000..b4f2391
--- /dev/null
+++ b/lvc/src/decode.rs
@@ -0,0 +1,20 @@
+use crate::{split::split, Block, Frame, View, P2};
+
+pub fn decode(last_frame: &Frame, frame: &mut Frame, view: View, block: &Block) {
+    match block {
+        Block::Lit(pxs) => frame.import(view, &pxs),
+        Block::Split([a, b]) => {
+            let [av, bv] = split(view);
+            decode(last_frame, frame, av, &a);
+            decode(last_frame, frame, bv, &b);
+        }
+        Block::Ref(r) => {
+            for y in view.a.y..view.b.y {
+                for x in view.a.x..view.b.x {
+                    let p = P2 { x, y };
+                    frame[p] = last_frame[p + r.pos_off] + r.color_off
+                }
+            }
+        }
+    }
+}
diff --git a/lvc/src/diff.rs b/lvc/src/diff.rs
index 5c65c29..354f146 100644
--- a/lvc/src/diff.rs
+++ b/lvc/src/diff.rs
@@ -1,13 +1,13 @@
 use crate::{Frame, Ref, View, P2};
-use std::simd::{i32x16, SimdInt};
 
 // 4ms
 pub fn diff([frame1, frame2]: [&Frame; 2], view: View, rp: Ref) -> u32 {
     let mut k = 0;
     for y in view.a.y..view.b.y {
         for x in view.a.x..view.b.x {
-            let p1 = frame1[P2 { x, y }] + rp.color_off;
-            let p2 = frame2[P2 { x, y }];
+            let pos = P2 { x, y };
+            let p1 = frame1[pos + rp.pos_off] + rp.color_off;
+            let p2 = frame2[pos];
             k += p1.r.abs_diff(p2.r) as u32
                 + p1.g.abs_diff(p2.g) as u32
                 + p1.b.abs_diff(p2.b) as u32;
@@ -16,53 +16,57 @@ pub fn diff([frame1, frame2]: [&Frame; 2], view: View, rp: Ref) -> u32 {
     k
 }
 
-pub fn fast_diff([frame1, frame2]: [&Frame; 2], view: View, rp: Ref) -> u32 {
-    let mut k = 0;
+// pub fn fast_diff([frame1, frame2]: [&Frame; 2], view: View, rp: Ref) -> u32 {
+//     assert!(view.size().x % 5 == 0);
 
-    let mut diff_lanes = i32x16::from_array([0; 16]);
-    let mut k1 = [0; 16];
-    let mut k2 = [0; 16];
+//     let mut diff_lanes = i32x16::from_array([0; 16]);
+//     let mut k1 = [0; 32];
+//     let mut k2 = [0; 32];
 
-    let next_line = frame1.size.x as usize - view.size().x as usize;
-    let index_start = view.a.x as usize + view.a.y as usize * frame1.size.x as usize;
-    let index_end = view.b.x as usize + (view.b.y as usize - 1) * frame1.size.x as usize;
+//     let next_line = frame1.size.x as usize - view.size().x as usize;
+//     let index_start = view.a.x as usize + view.a.y as usize * frame1.size.x as usize;
+//     let index_end = view.b.x as usize + (view.b.y as usize - 1) * frame1.size.x as usize;
 
-    let mut i = index_start;
-    let mut x = view.a.x;
-    let mut kfill = 0;
+//     let mut i = index_start;
+//     let mut x = view.a.x;
 
-    while i < index_end {
-        k1[kfill] = frame1.pixels[i].r as i32;
-        k2[kfill] = frame2.pixels[i].r as i32;
-        kfill += 1;
-        k1[kfill] = frame1.pixels[i].g as i32;
-        k2[kfill] = frame2.pixels[i].g as i32;
-        kfill += 1;
-        k1[kfill] = frame1.pixels[i].b as i32;
-        k2[kfill] = frame2.pixels[i].b as i32;
-        kfill += 1;
+//     while i < index_end {
 
-        i += 1;
-        x += 1;
-        if x > view.b.x {
-            i += next_line;
-            x = view.a.x
-        }
+//         let f1: &[u8] =
+//             unsafe { std::slice::from_raw_parts(frame1.pixels[sl_start..].as_ptr() as *mut u8, sl_size) };
+//         let f2: &[u8] =
+//             unsafe { std::slice::from_raw_parts(frame2.pixels[sl_start..].as_ptr() as *mut u8, sl_size) };
 
-        if kfill == 15 {
-            let pl1 = i32x16::from_array(k1);
-            let pl2 = i32x16::from_array(k2);
-            diff_lanes += (pl1 - pl2).abs();
-            kfill = 0;
-        }
-    }
+//         for i in 0..15 {
+//             k1[i] = f1[i] as i32;
+//             k2[i] = f2[i] as i32;
+//         }
 
-    return diff_lanes.reduce_sum() as u32;
-}
+//         // for j in 0..5 {
+//         //     let j3 = j * 3;
+//         //     k1[j3] = frame1.pixels[i + j].r as i32;
+//         //     k2[j3] = frame2.pixels[i + j].r as i32;
+//         //     k1[j3 + 1] = frame1.pixels[i + j].g as i32;
+//         //     k2[j3 + 1] = frame2.pixels[i + j].g as i32;
+//         //     k1[j3 + 2] = frame1.pixels[i + j].b as i32;
+//         //     k2[j3 + 2] = frame2.pixels[i + j].b as i32;
+//         // }
+//         let pl1 = i16x32::from_array(k1);
+//         let pl2 = i16x32::from_array(k2);
+//         diff_lanes += (pl1 - pl2).abs();
 
-// pub fn fast_diff([frame1, frame2]: [&Frame; 2], view: View, rp: Ref) -> u32 {
-//     let mut k = 0;
+//         i += 5;
+//         x += 5;
+//         if x > view.b.x {
+//             i += next_line;
+//             x = view.a.x
+//         }
+//     }
+
+//     return diff_lanes.reduce_sum() as u32;
+// }
 
+// pub fn fast_diff([frame1, frame2]: [&Frame; 2], view: View, rp: Ref) -> u32 {
 //     let mut diff_lanes = i32x16::from_array([0; 16]);
 //     let mut k1 = [0; 16];
 //     let mut k2 = [0; 16];
diff --git a/lvc/src/encode.rs b/lvc/src/encode.rs
index 7737626..d85ac30 100644
--- a/lvc/src/encode.rs
+++ b/lvc/src/encode.rs
@@ -1,49 +1,51 @@
 use crate::diff::diff;
-use crate::{Frame, Ref, View, P2};
+use crate::split::split;
+use crate::{Block, Frame, Ref, View};
 
-pub fn encode(last_frame: &Frame, frame: &Frame, view: View) {
-    let rp = Ref::default();
+pub fn encode(last_frame: &Frame, frame: &Frame, view: View) -> Block {
+    if view.size().area() > 1024 {
+        let [av, bv] = split(view);
+        return Block::Split([
+            Box::new(encode(last_frame, frame, av)),
+            Box::new(encode(last_frame, frame, bv)),
+        ]);
+    }
 
-    let d = diff([last_frame, frame], view, rp);
-}
+    let mut rp = Ref::default();
+    let mut d = diff([last_frame, frame], view, rp);
+
+    for _ in 0..500 {
+        let (nd, nrp) = optimize_ref(last_frame, frame, view, rp);
+        if nd < d {
+            rp = nrp;
+            d = nd;
+        } else {
+            break;
+        }
+    }
 
-pub fn split(view: View) -> [View; 2] {
-    let s = view.size();
-    if s.x > s.y {
-        let mid_x = (view.a.x + view.b.x) / 2;
-        [
-            View {
-                a: view.a,
-                b: P2 {
-                    x: mid_x,
-                    y: view.b.y,
-                },
-            },
-            View {
-                a: P2 {
-                    x: mid_x,
-                    y: view.a.y,
-                },
-                b: view.b,
-            },
-        ]
+    if d < 10000 {
+        return Block::Ref(rp);
     } else {
-        let mid_y = (view.a.y + view.b.y) / 2;
-        [
-            View {
-                a: view.a,
-                b: P2 {
-                    x: view.b.x,
-                    y: mid_y,
-                },
-            },
-            View {
-                a: P2 {
-                    x: view.a.x,
-                    y: mid_y,
-                },
-                b: view.b,
-            },
-        ]
+        Block::Lit(frame.export(view))
     }
 }
+
+pub fn optimize_ref(last_frame: &Frame, frame: &Frame, view: View, rp: Ref) -> (u32, Ref) {
+    [
+        rp.apply(|r| r.pos_off.x += 1),
+        rp.apply(|r| r.pos_off.x -= 1),
+        rp.apply(|r| r.pos_off.y += 1),
+        rp.apply(|r| r.pos_off.y -= 1),
+        rp.apply(|r| r.color_off.r += 10),
+        rp.apply(|r| r.color_off.r -= 10),
+        rp.apply(|r| r.color_off.g += 10),
+        rp.apply(|r| r.color_off.g -= 10),
+        rp.apply(|r| r.color_off.b += 10),
+        rp.apply(|r| r.color_off.b -= 10),
+    ]
+    .map(|p| (diff([last_frame, frame], view, p), p))
+    .into_iter()
+    .min_by_key(|x| x.0)
+    .unwrap()
+}
diff --git a/lvc/src/impls.rs b/lvc/src/impls.rs
index 01eb1c6..0801361 100644
--- a/lvc/src/impls.rs
+++ b/lvc/src/impls.rs
@@ -1,6 +1,37 @@
-use crate::{Frame, Pixel, View, P2};
+use crate::{Frame, Pixel, Ref, View, P2};
 use std::ops::{Add, Index, IndexMut, Sub};
 
+impl Frame {
+    pub fn export(&self, view: View) -> Vec<Pixel> {
+        let mut o = vec![];
+        for y in view.a.y..view.b.y {
+            for x in view.a.x..view.b.x {
+                o.push(self[P2 { x, y }])
+            }
+        }
+        o
+    }
+    pub fn import(&mut self, view: View, mut source: &[Pixel]) {
+        for y in view.a.y..view.b.y {
+            for x in view.a.x..view.b.x {
+                self[P2 { x, y }] = source[0];
+                source = &source[1..];
+            }
+        }
+    }
+    pub fn new(size: P2) -> Self {
+        Self {
+            pixels: vec![Pixel::default(); size.area()],
+            size,
+        }
+    }
+}
+impl Ref {
+    pub fn apply<F: Fn(&mut Self)>(mut self, f: F) -> Self {
+        f(&mut self);
+        self
+    }
+}
 impl Add for Pixel {
     type Output = Pixel;
     #[inline]
diff --git a/lvc/src/lib.rs b/lvc/src/lib.rs
index ad284df..4a88b93 100644
--- a/lvc/src/lib.rs
+++ b/lvc/src/lib.rs
@@ -1,20 +1,27 @@
 #![feature(portable_simd)]
 
+use bincode::{Decode, Encode};
+
 pub mod diff;
 pub mod encode;
 pub mod impls;
+pub mod decode;
+pub mod split;
+pub mod debug;
+#[cfg(test)]
+pub mod bench;
 
 pub type PixelValue = u8;
 
-#[repr(C, align(2))]
-#[derive(Debug, Clone, Copy, Default)]
+#[repr(C, align(1))]
+#[derive(Debug, Clone, Copy, Default, Encode, Decode)]
 pub struct Pixel {
     pub r: PixelValue,
     pub g: PixelValue,
     pub b: PixelValue,
 }
 
-#[derive(Debug, Clone, Copy, Default)]
+#[derive(Debug, Clone, Copy, Default, Encode, Decode)]
 pub struct P2 {
     pub x: i32,
     pub y: i32,
@@ -25,19 +32,20 @@ pub struct Frame {
     pub pixels: Vec<Pixel>,
 }
 
+#[derive(Debug, Clone, Copy)]
 pub struct View {
     pub a: P2,
     pub b: P2,
 }
 
-#[derive(Debug, Clone)]
+#[derive(Debug, Clone, Encode, Decode)]
 pub enum Block {
     Lit(Vec<Pixel>),
     Split([Box<Block>; 2]),
     Ref(Ref),
 }
 
-#[derive(Debug, Clone, Default)]
+#[derive(Debug, Clone, Copy, Default, Encode, Decode)]
 pub struct Ref {
     pub pos_off: P2,
     pub color_off: Pixel,
diff --git a/lvc/src/main.rs b/lvc/src/main.rs
index 523f22c..413e4a4 100644
--- a/lvc/src/main.rs
+++ b/lvc/src/main.rs
@@ -1,48 +1,35 @@
-use lvc::{diff::{diff, fast_diff}, Frame, Pixel, Ref, View, P2, PixelValue};
-use std::{
-    io::{stdin, stdout, BufReader, BufWriter, Read, Write},
-    time::Instant,
-};
+use lvc::{debug::draw_debug, decode::decode, encode::encode, Frame, Pixel, PixelValue, View, P2};
+use std::io::{stdin, stdout, BufReader, BufWriter, Read, Write};
 
 fn main() {
     let size = P2 { x: 1920, y: 1080 };
 
-    // let frame1 = read_frame(size);
-    // let frame2 = read_frame(size);
-
-    // encode(&frame1, &frame2, View::all(size));
-
-    let mut last_frame = Frame {
-        pixels: vec![Pixel::default(); size.area()],
-        size,
-    };
+    let mut last_frame = Frame::new(size);
+    let mut debug_frame = Some(Frame::new(size));
 
     let mut stdin = BufReader::new(stdin());
     let mut stdout = BufWriter::new(stdout());
 
     loop {
-        let frame = read_frame(&mut stdin, size);
+        let mut frame = read_frame(&mut stdin, size);
 
-        let t1 = Instant::now();
-        let d = diff([&last_frame, &frame], View::all(size), Ref::default());
-        let t2 = Instant::now();
-        eprintln!("diff {:?} {d}", t2 - t1);
+        let b = encode(&last_frame, &frame, View::all(size));
+        decode(&last_frame, &mut frame, View::all(size), &b);
 
-        let t1 = Instant::now();
-        let d = fast_diff([&last_frame, &frame], View::all(size), Ref::default());
-        let t2 = Instant::now();
-        eprintln!("diff2 {:?} {d}", t2 - t1);
+        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);
+        }
 
-        write_frame(&mut stdout, &frame);
         last_frame = frame;
     }
 }
 
 fn read_frame(inp: &mut impl Read, size: P2) -> Frame {
-    let mut f = Frame {
-        size,
-        pixels: vec![Pixel::default(); size.area()],
-    };
+    let mut f = Frame::new(size);
 
     for y in 0..size.y {
         for x in 0..size.x {
diff --git a/lvc/src/split.rs b/lvc/src/split.rs
new file mode 100644
index 0000000..c17179e
--- /dev/null
+++ b/lvc/src/split.rs
@@ -0,0 +1,42 @@
+use crate::{View, P2};
+
+pub fn split(view: View) -> [View; 2] {
+    let s = view.size();
+    if s.x > s.y {
+        let mid_x = (view.a.x + view.b.x) / 2;
+        [
+            View {
+                a: view.a,
+                b: P2 {
+                    x: mid_x,
+                    y: view.b.y,
+                },
+            },
+            View {
+                a: P2 {
+                    x: mid_x,
+                    y: view.a.y,
+                },
+                b: view.b,
+            },
+        ]
+    } else {
+        let mid_y = (view.a.y + view.b.y) / 2;
+        [
+            View {
+                a: view.a,
+                b: P2 {
+                    x: view.b.x,
+                    y: mid_y,
+                },
+            },
+            View {
+                a: P2 {
+                    x: view.a.x,
+                    y: mid_y,
+                },
+                b: view.b,
+            },
+        ]
+    }
+}