aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--lvc/Cargo.lock158
-rw-r--r--lvc/Cargo.toml4
-rw-r--r--lvc/src/bench.rs19
-rw-r--r--lvc/src/debug.rs30
-rw-r--r--lvc/src/decode.rs20
-rw-r--r--lvc/src/diff.rs86
-rw-r--r--lvc/src/encode.rs86
-rw-r--r--lvc/src/impls.rs33
-rw-r--r--lvc/src/lib.rs18
-rw-r--r--lvc/src/main.rs43
-rw-r--r--lvc/src/split.rs42
11 files changed, 420 insertions, 119 deletions
diff --git a/lvc/Cargo.lock b/lvc/Cargo.lock
index 15c8961..0c9c575 100644
--- a/lvc/Cargo.lock
+++ b/lvc/Cargo.lock
@@ -3,5 +3,163 @@
version = 3
[[package]]
+name = "autocfg"
+version = "1.1.0"
+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 = "cfg-if"
+version = "1.0.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "baf1de4339761588bc0619e3cbc0120ee582ebb74b53b4efbf79117bd2da40fd"
+
+[[package]]
+name = "crossbeam-channel"
+version = "0.5.7"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "cf2b3e8478797446514c91ef04bafcb59faba183e621ad488df88983cc14128c"
+dependencies = [
+ "cfg-if",
+ "crossbeam-utils",
+]
+
+[[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.14"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "46bd5f3f85273295a9d14aedfb86f6aadbff6d8f5295c4a9edb08e819dcf5695"
+dependencies = [
+ "autocfg",
+ "cfg-if",
+ "crossbeam-utils",
+ "memoffset",
+ "scopeguard",
+]
+
+[[package]]
+name = "crossbeam-utils"
+version = "0.8.15"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "3c063cd8cc95f5c377ed0d4b49a4b21f632396ff690e8470c29b3359b346984b"
+dependencies = [
+ "cfg-if",
+]
+
+[[package]]
+name = "either"
+version = "1.8.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "7fcaabb2fef8c910e7f4c7ce9f67a1283a1715879a7c230ca9d6d1ae31f16d91"
+
+[[package]]
+name = "hermit-abi"
+version = "0.2.6"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "ee512640fe35acbfb4bb779db6f0d80704c2cacfa2e39b601ef3e3f47d1ae4c7"
+dependencies = [
+ "libc",
+]
+
+[[package]]
+name = "libc"
+version = "0.2.139"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "201de327520df007757c1f0adce6e827fe8562fbc28bfd9c15571c66ca1f5f79"
+
+[[package]]
name = "lvc"
version = "0.1.0"
+dependencies = [
+ "bincode",
+ "rayon",
+]
+
+[[package]]
+name = "memoffset"
+version = "0.8.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "d61c719bcfbcf5d62b3a09efa6088de8c54bc0bfcd3ea7ae39fcc186108b8de1"
+dependencies = [
+ "autocfg",
+]
+
+[[package]]
+name = "num_cpus"
+version = "1.15.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "0fac9e2da13b5eb447a6ce3d392f23a29d8694bff781bf03a16cd9ac8697593b"
+dependencies = [
+ "hermit-abi",
+ "libc",
+]
+
+[[package]]
+name = "rayon"
+version = "1.7.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "1d2df5196e37bcc87abebc0053e20787d73847bb33134a69841207dd0a47f03b"
+dependencies = [
+ "either",
+ "rayon-core",
+]
+
+[[package]]
+name = "rayon-core"
+version = "1.11.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "4b8f95bd6966f5c87776639160a66bd8ab9895d9d4ab01ddba9fc60661aebe8d"
+dependencies = [
+ "crossbeam-channel",
+ "crossbeam-deque",
+ "crossbeam-utils",
+ "num_cpus",
+]
+
+[[package]]
+name = "scopeguard"
+version = "1.1.0"
+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 = "virtue"
+version = "0.0.8"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "7b60dcd6a64dd45abf9bd426970c9843726da7fc08f44cd6fcebf68c21220a63"
diff --git a/lvc/Cargo.toml b/lvc/Cargo.toml
index 15df5d7..71eb470 100644
--- a/lvc/Cargo.toml
+++ b/lvc/Cargo.toml
@@ -3,6 +3,6 @@ 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]
+rayon = "1.7.0"
+bincode = "2.0.0-rc.2"
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,
+ },
+ ]
+ }
+}
generated by cgit v1.2.3-70-g09d2 (git 2.51.0) at 2025-10-08 22:27:46 +0000