From 414990bb53f5c9e2028d42db46fa641fa606cd86 Mon Sep 17 00:00:00 2001 From: metamuffin Date: Tue, 7 Mar 2023 17:15:49 +0100 Subject: works --- lvc/src/bench.rs | 19 +++++++++++ lvc/src/debug.rs | 30 ++++++++++++++++++ lvc/src/decode.rs | 20 ++++++++++++ lvc/src/diff.rs | 94 +++++++++++++++++++++++++++++-------------------------- lvc/src/encode.rs | 86 +++++++++++++++++++++++++------------------------- lvc/src/impls.rs | 33 ++++++++++++++++++- lvc/src/lib.rs | 18 ++++++++--- lvc/src/main.rs | 43 +++++++++---------------- lvc/src/split.rs | 42 +++++++++++++++++++++++++ 9 files changed, 264 insertions(+), 121 deletions(-) create mode 100644 lvc/src/bench.rs create mode 100644 lvc/src/debug.rs create mode 100644 lvc/src/decode.rs create mode 100644 lvc/src/split.rs (limited to 'lvc/src') 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 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 - } +// let mut diff_lanes = i32x16::from_array([0; 16]); +// let mut k1 = [0; 32]; +// let mut k2 = [0; 32]; - if kfill == 15 { - let pl1 = i32x16::from_array(k1); - let pl2 = i32x16::from_array(k2); - diff_lanes += (pl1 - pl2).abs(); - kfill = 0; - } - } +// 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; - return diff_lanes.reduce_sum() as u32; -} +// let mut i = index_start; +// let mut x = view.a.x; -// pub fn fast_diff([frame1, frame2]: [&Frame; 2], view: View, rp: Ref) -> u32 { -// let mut k = 0; +// while i < index_end { +// 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) }; + +// for i in 0..15 { +// k1[i] = f1[i] as i32; +// k2[i] = f2[i] as i32; +// } + +// // 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(); + +// 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 { + 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(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, } +#[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), Split([Box; 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, + }, + ] + } +} -- cgit v1.2.3-70-g09d2