a

8 files changed, 355 insertions, 0 deletions

diff --git a/lvc/.gitignore b/lvc/.gitignore
new file mode 100644
index 0000000..2f22d72
--- /dev/null
+++ b/lvc/.gitignore
@@ -0,0 +1,2 @@
+/data
+/target
diff --git a/lvc/Cargo.lock b/lvc/Cargo.lock
new file mode 100644
index 0000000..15c8961
--- /dev/null
+++ b/lvc/Cargo.lock
@@ -0,0 +1,7 @@
+# This file is automatically @generated by Cargo.
+# It is not intended for manual editing.
+version = 3
+
+[[package]]
+name = "lvc"
+version = "0.1.0"
diff --git a/lvc/Cargo.toml b/lvc/Cargo.toml
new file mode 100644
index 0000000..15df5d7
--- /dev/null
+++ b/lvc/Cargo.toml
@@ -0,0 +1,8 @@
+[package]
+name = "lvc"
+version = "0.1.0"
+edition = "2021"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]
diff --git a/lvc/src/diff.rs b/lvc/src/diff.rs
new file mode 100644
index 0000000..5c65c29
--- /dev/null
+++ b/lvc/src/diff.rs
@@ -0,0 +1,105 @@
+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 }];
+            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;
+        }
+    }
+    k
+}
+
+pub fn fast_diff([frame1, frame2]: [&Frame; 2], view: View, rp: Ref) -> u32 {
+    let mut k = 0;
+
+    let mut diff_lanes = i32x16::from_array([0; 16]);
+    let mut k1 = [0; 16];
+    let mut k2 = [0; 16];
+
+    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;
+
+    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;
+
+        i += 1;
+        x += 1;
+        if x > view.b.x {
+            i += next_line;
+            x = view.a.x
+        }
+
+        if kfill == 15 {
+            let pl1 = i32x16::from_array(k1);
+            let pl2 = i32x16::from_array(k2);
+            diff_lanes += (pl1 - pl2).abs();
+            kfill = 0;
+        }
+    }
+
+    return diff_lanes.reduce_sum() as u32;
+}
+
+// pub fn fast_diff([frame1, frame2]: [&Frame; 2], view: View, rp: Ref) -> u32 {
+//     let mut k = 0;
+
+//     let mut diff_lanes = i32x16::from_array([0; 16]);
+//     let mut k1 = [0; 16];
+//     let mut k2 = [0; 16];
+
+//     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;
+
+//     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;
+
+//         i += 1;
+//         x += 1;
+//         if x > view.b.x {
+//             i += next_line;
+//             x = view.a.x
+//         }
+
+//         if kfill == 15 {
+//             let pl1 = i32x16::from_array(k1);
+//             let pl2 = i32x16::from_array(k2);
+//             diff_lanes += (pl1 - pl2).abs();
+//             kfill = 0;
+//         }
+//     }
+
+//     return diff_lanes.reduce_sum() as u32;
+// }
diff --git a/lvc/src/encode.rs b/lvc/src/encode.rs
new file mode 100644
index 0000000..7737626
--- /dev/null
+++ b/lvc/src/encode.rs
@@ -0,0 +1,49 @@
+use crate::diff::diff;
+use crate::{Frame, Ref, View, P2};
+
+pub fn encode(last_frame: &Frame, frame: &Frame, view: View) {
+    let rp = Ref::default();
+
+    let d = diff([last_frame, frame], view, rp);
+}
+
+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,
+            },
+        ]
+    }
+}
diff --git a/lvc/src/impls.rs b/lvc/src/impls.rs
new file mode 100644
index 0000000..01eb1c6
--- /dev/null
+++ b/lvc/src/impls.rs
@@ -0,0 +1,68 @@
+use crate::{Frame, Pixel, View, P2};
+use std::ops::{Add, Index, IndexMut, Sub};
+
+impl Add for Pixel {
+    type Output = Pixel;
+    #[inline]
+    fn add(self, rhs: Self) -> Self::Output {
+        Self {
+            r: self.r + rhs.r,
+            g: self.g + rhs.g,
+            b: self.b + rhs.b,
+        }
+    }
+}
+impl P2 {
+    pub const ZERO: P2 = P2 { x: 0, y: 0 };
+    #[inline]
+    pub fn area(&self) -> usize {
+        (self.x * self.y) as usize
+    }
+}
+impl View {
+    #[inline]
+    pub fn all(b: P2) -> Self {
+        Self {
+            a: P2::default(),
+            b,
+        }
+    }
+    #[inline]
+    pub fn size(&self) -> P2 {
+        self.b - self.a
+    }
+}
+impl Add for P2 {
+    type Output = P2;
+    #[inline]
+    fn add(self, rhs: Self) -> Self::Output {
+        Self {
+            x: self.x + rhs.x,
+            y: self.y + rhs.y,
+        }
+    }
+}
+impl Sub for P2 {
+    type Output = P2;
+    #[inline]
+    fn sub(self, rhs: Self) -> Self::Output {
+        Self {
+            x: self.x - rhs.x,
+            y: self.y - rhs.y,
+        }
+    }
+}
+
+impl Index<P2> for Frame {
+    type Output = Pixel;
+    #[inline]
+    fn index(&self, P2 { x, y }: P2) -> &Self::Output {
+        &self.pixels[x as usize + (y as usize * self.size.x as usize)]
+    }
+}
+impl IndexMut<P2> for Frame {
+    #[inline]
+    fn index_mut(&mut self, P2 { x, y }: P2) -> &mut Self::Output {
+        &mut self.pixels[x as usize + (y as usize * self.size.x as usize)]
+    }
+}
diff --git a/lvc/src/lib.rs b/lvc/src/lib.rs
new file mode 100644
index 0000000..ad284df
--- /dev/null
+++ b/lvc/src/lib.rs
@@ -0,0 +1,44 @@
+#![feature(portable_simd)]
+
+pub mod diff;
+pub mod encode;
+pub mod impls;
+
+pub type PixelValue = u8;
+
+#[repr(C, align(2))]
+#[derive(Debug, Clone, Copy, Default)]
+pub struct Pixel {
+    pub r: PixelValue,
+    pub g: PixelValue,
+    pub b: PixelValue,
+}
+
+#[derive(Debug, Clone, Copy, Default)]
+pub struct P2 {
+    pub x: i32,
+    pub y: i32,
+}
+
+pub struct Frame {
+    pub size: P2,
+    pub pixels: Vec<Pixel>,
+}
+
+pub struct View {
+    pub a: P2,
+    pub b: P2,
+}
+
+#[derive(Debug, Clone)]
+pub enum Block {
+    Lit(Vec<Pixel>),
+    Split([Box<Block>; 2]),
+    Ref(Ref),
+}
+
+#[derive(Debug, Clone, Default)]
+pub struct Ref {
+    pub pos_off: P2,
+    pub color_off: Pixel,
+}
diff --git a/lvc/src/main.rs b/lvc/src/main.rs
new file mode 100644
index 0000000..523f22c
--- /dev/null
+++ b/lvc/src/main.rs
@@ -0,0 +1,72 @@
+use lvc::{diff::{diff, fast_diff}, Frame, Pixel, Ref, View, P2, PixelValue};
+use std::{
+    io::{stdin, stdout, BufReader, BufWriter, Read, Write},
+    time::Instant,
+};
+
+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 stdin = BufReader::new(stdin());
+    let mut stdout = BufWriter::new(stdout());
+
+    loop {
+        let 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 t1 = Instant::now();
+        let d = fast_diff([&last_frame, &frame], View::all(size), Ref::default());
+        let t2 = Instant::now();
+        eprintln!("diff2 {:?} {d}", t2 - t1);
+
+        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()],
+    };
+
+    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();
+        }
+    }
+}