1 use super::Indeo3Writer;
3 use super::cell::{CellEncoder, MAX_CELL_SIZE};
4 use std::ops::DerefMut;
6 pub enum Indeo3PrimaryTree {
7 VSplit(Box<Indeo3PrimaryTree>, Box<Indeo3PrimaryTree>),
8 HSplit(Box<Indeo3PrimaryTree>, Box<Indeo3PrimaryTree>),
9 RelFill(MV, Box<Indeo3SecondaryTree>),
10 AbsFill(Box<Indeo3SecondaryTree>),
13 impl Indeo3PrimaryTree {
15 println!("Plane tree:");
18 fn print1(&self, depth: u8) {
23 Indeo3PrimaryTree::VSplit(t1, t2) => {
24 println!("vertical split");
28 Indeo3PrimaryTree::HSplit(t1, t2) => {
29 println!("horizontal split");
33 Indeo3PrimaryTree::RelFill(mv, sec) => {
34 println!("relative fill {},{}", mv.x, mv.y);
35 sec.print1(depth + 1);
37 Indeo3PrimaryTree::AbsFill(sec) => {
38 println!("absolute fill");
39 sec.print1(depth + 1);
45 pub enum Indeo3SecondaryTree {
46 VSplit(Box<Indeo3SecondaryTree>, Box<Indeo3SecondaryTree>),
47 HSplit(Box<Indeo3SecondaryTree>, Box<Indeo3SecondaryTree>),
52 impl Indeo3SecondaryTree {
53 fn print1(&self, depth: u8) {
58 Indeo3SecondaryTree::VSplit(t1, t2) => {
59 println!("vertical split");
63 Indeo3SecondaryTree::HSplit(t1, t2) => {
64 println!("horizontal split");
68 Indeo3SecondaryTree::VQData(mode) => {
69 println!("VQ data ({})", mode);
71 Indeo3SecondaryTree::VQNull(mode) => {
72 println!("VQ Null ({})", mode);
78 const THRESHOLD: u32 = 64;
80 #[derive(Clone, Copy)]
81 pub struct Indeo3Cell {
90 pub fn new(width: usize, height: usize) -> Self {
95 h: (height / 4) as u8,
100 pub fn get_x(&self) -> usize { usize::from(self.x) * 4 }
101 pub fn get_y(&self) -> usize { usize::from(self.y) * 4 }
102 pub fn get_width(&self) -> usize { usize::from(self.w) * 4 }
103 pub fn get_height(&self) -> usize { usize::from(self.h) * 4 }
104 pub fn is_intra(&self) -> bool { self.intra }
106 fn split_h(&self) -> (Self, Self) {
107 let h1 = if self.h > 2 { ((self.h + 2) >> 2) << 1 } else { 1 };
108 let h2 = self.h - h1;
109 let mut cell1 = *self;
111 let mut cell2 = *self;
116 fn split_v(&self, stripw: u8) -> (Self, Self) {
117 let w1 = if self.w > stripw {
118 if self.w > stripw * 2 { stripw * 2 } else { stripw }
120 if self.w > 2 { ((self.w + 2) >> 2) << 1 } else { 1 }
122 let w2 = self.w - w1;
123 let mut cell1 = *self;
125 let mut cell2 = *self;
132 impl std::fmt::Display for Indeo3Cell {
133 fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
134 write!(f, "[{}x{} @ {},{}{}]", self.get_width(), self.get_height(), self.get_x(), self.get_y(), if self.intra { " intra" } else { "" })
144 pub mvs: Vec<(MV, u16)>,
147 fn ssd(a: u8, b: u8) -> u32 {
148 let diff = i32::from(a) - i32::from(b);
153 pub fn alloc(&mut self, width: usize, height: usize, stripw: u8) {
154 self.data.resize(width * height, 0);
156 self.height = height;
157 self.stripw = stripw;
158 if self.mvs.capacity() < 256 {
159 self.mvs.reserve(256);
162 pub fn fill(&mut self, src: &[u8], stride: usize) {
163 for (dline, sline) in self.data.chunks_mut(self.width).zip(src.chunks(stride)) {
164 for (dst, &src) in dline.iter_mut().zip(sline.iter()) {
169 pub fn clear_mvs(&mut self){
172 pub fn checksum(&self) -> u16 {
173 let xors = self.data.chunks(2).fold([0u8; 2], |acc, pair| [acc[0] ^ pair[0], acc[1] ^ pair[1]]);
174 u16::from(xors[0]) | (u16::from(xors[1]) * 256)
176 pub fn find_cells(&mut self, is_intra: bool, pplane: &Plane, mv_est: &MotionEstimator) -> Box<Indeo3PrimaryTree> {
177 let cell = Indeo3Cell::new(self.width, self.height);
178 self.split_pri(cell, pplane, mv_est, is_intra)
180 fn split_pri(&mut self, mut cell: Indeo3Cell, pplane: &Plane, mv_est: &MotionEstimator, is_intra: bool) -> Box<Indeo3PrimaryTree> {
181 let width = cell.get_width();
182 let height = cell.get_height();
183 if width * height > MAX_CELL_SIZE {
184 let (hsplit, vsplit) = if width != height {
185 (width > (self.stripw as usize) * 4 || width > height, height > width)
187 let (hdiff, vdiff) = self.calculate_diffs(cell);
188 (vdiff > THRESHOLD && vdiff > hdiff,
189 hdiff > THRESHOLD && hdiff > vdiff)
191 match (hsplit, vsplit) {
193 let (cell1, cell2) = cell.split_v(self.stripw);
194 let tree1 = self.split_pri(cell1, pplane, mv_est, is_intra);
195 let tree2 = self.split_pri(cell2, pplane, mv_est, is_intra);
196 Box::new(Indeo3PrimaryTree::VSplit(tree1, tree2))
199 let (cell1, cell2) = cell.split_h();
200 let tree1 = self.split_pri(cell1, pplane, mv_est, is_intra);
201 let tree2 = self.split_pri(cell2, pplane, mv_est, is_intra);
202 Box::new(Indeo3PrimaryTree::HSplit(tree1, tree2))
205 let sec = self.split_sec(cell);
206 Box::new(Indeo3PrimaryTree::AbsFill(sec))
211 if let Some((mv, flat)) = mv_est.mv_search(self, pplane, cell) {
212 return self.add_mv_tree(mv, flat, cell);
215 // try splitting once to see if it improves situation
216 if width >= 16 && height >= 16 {
217 let vsplit = width > height;
218 let (mut cell1, mut cell2) = if vsplit {
219 cell.split_v(self.stripw)
223 let search1 = mv_est.mv_search(self, pplane, cell1);
224 let search2 = mv_est.mv_search(self, pplane, cell2);
225 if search1.is_some() || search2.is_some() {
226 let tree1 = if let Some((mv, flat)) = search1 {
227 self.add_mv_tree(mv, flat, cell1)
230 let sec = self.split_sec(cell1);
231 Box::new(Indeo3PrimaryTree::AbsFill(sec))
233 let tree2 = if let Some((mv, flat)) = search2 {
234 self.add_mv_tree(mv, flat, cell2)
237 let sec = self.split_sec(cell2);
238 Box::new(Indeo3PrimaryTree::AbsFill(sec))
241 Box::new(Indeo3PrimaryTree::VSplit(tree1, tree2))
243 Box::new(Indeo3PrimaryTree::HSplit(tree1, tree2))
249 let sec = self.split_sec(cell);
250 Box::new(Indeo3PrimaryTree::AbsFill(sec))
253 fn add_mv_tree(&mut self, mv: MV, flat: bool, cell: Indeo3Cell) -> Box<Indeo3PrimaryTree> {
255 Box::new(Indeo3SecondaryTree::VQNull(0))
257 Box::new(Indeo3SecondaryTree::VQData(0))
260 let mut found = false;
261 for (ref cmv, ref mut count) in self.mvs.iter_mut() {
263 *count += u16::from(cell.w) * u16::from(cell.h);
269 self.mvs.push((mv, 1));
272 Box::new(Indeo3PrimaryTree::RelFill(mv, sec))
274 fn split_sec(&mut self, cell: Indeo3Cell) -> Box<Indeo3SecondaryTree> {
275 let (hdiff, vdiff) = self.calculate_diffs(cell);
276 if hdiff == 0 && vdiff == 0 {
278 return Box::new(Indeo3SecondaryTree::VQNull(0));
280 return Box::new(Indeo3SecondaryTree::VQData(0));
283 if cell.get_width() > 16 && cell.get_height() > 16 {
284 let hsplit = vdiff > THRESHOLD && vdiff > hdiff * 2;
285 let vsplit = hdiff > THRESHOLD && hdiff > vdiff * 2;
286 match (vsplit, hsplit) {
288 let (cell1, cell2) = cell.split_v(self.stripw);
289 let tree1 = self.split_sec(cell1);
290 let tree2 = self.split_sec(cell2);
291 Box::new(Indeo3SecondaryTree::VSplit(tree1, tree2))
294 let (cell1, cell2) = cell.split_h();
295 let tree1 = self.split_sec(cell1);
296 let tree2 = self.split_sec(cell2);
297 Box::new(Indeo3SecondaryTree::HSplit(tree1, tree2))
300 Box::new(Indeo3SecondaryTree::VQData(0))
304 let is_w8 = (cell.get_width() & 7) == 0;
305 let is_h8 = (cell.get_height() & 7) == 0;
306 let mode = match (hdiff > THRESHOLD, vdiff > THRESHOLD) {
307 (false, false) if is_w8 && is_h8 => 10,
308 (_, true) if is_h8 => 3,
311 Box::new(Indeo3SecondaryTree::VQData(mode))
314 fn calculate_diffs(&self, cell: Indeo3Cell) -> (u32, u32) {
315 let offset = cell.get_x() + cell.get_y() * self.width;
316 let mut w = cell.get_width();
317 if cell.get_x() + w == self.width { w -= 1; }
318 let mut h = cell.get_height();
319 if cell.get_y() + h == self.height { h -= 1; }
323 let src0 = &self.data[offset..];
324 let src1 = &self.data[offset + self.width..];
325 for (line0, line1) in src0.chunks(self.width).zip(src1.chunks(self.width)).take(h) {
326 for ((&cur, &right), &bottom) in line0.iter().zip(line0[1..].iter()).zip(line1.iter()).take(w) {
327 hdiff += ssd(cur, right);
328 vdiff += ssd(cur, bottom);
331 let area = (w * h) as u32;
332 (hdiff * 16 / area, vdiff * 16 / area)
334 pub fn prune_extra_mvs(&mut self, tree: &mut Box<Indeo3PrimaryTree>) {
335 let cell = Indeo3Cell::new(self.width, self.height);
336 self.prune_pri(cell, tree)
338 fn prune_pri(&mut self, cell: Indeo3Cell, tree: &mut Box<Indeo3PrimaryTree>) {
339 match tree.deref_mut() {
340 Indeo3PrimaryTree::HSplit(ref mut tree1, ref mut tree2) => {
341 let (cell1, cell2) = cell.split_h();
342 self.prune_pri(cell1, tree1);
343 self.prune_pri(cell2, tree2);
345 Indeo3PrimaryTree::VSplit(ref mut tree1, ref mut tree2) => {
346 let (cell1, cell2) = cell.split_v(self.stripw);
347 self.prune_pri(cell1, tree1);
348 self.prune_pri(cell2, tree2);
350 Indeo3PrimaryTree::AbsFill(_) => {},
351 Indeo3PrimaryTree::RelFill(ref mv, ref _sec) => {
352 if find_mv(*mv, &self.mvs).is_none() {
353 let sec = self.split_sec(cell);
354 *tree = Box::new(Indeo3PrimaryTree::AbsFill(sec));
359 pub fn encode_tree(&mut self, iw: &mut Indeo3Writer, tree: &Indeo3PrimaryTree, cenc: &mut CellEncoder, refp: &Plane) {
360 let cell = Indeo3Cell::new(self.width, self.height);
361 self.encode_pri(iw, cell, tree, cenc, refp);
363 fn encode_pri(&mut self, iw: &mut Indeo3Writer, mut cell: Indeo3Cell, tree: &Indeo3PrimaryTree, cenc: &mut CellEncoder, refp: &Plane) {
365 Indeo3PrimaryTree::HSplit(t1, t2) => {
367 let (cell1, cell2) = cell.split_h();
368 self.encode_pri(iw, cell1, t1, cenc, refp);
369 self.encode_pri(iw, cell2, t2, cenc, refp);
371 Indeo3PrimaryTree::VSplit(t1, t2) => {
373 let (cell1, cell2) = cell.split_v(self.stripw);
374 self.encode_pri(iw, cell1, t1, cenc, refp);
375 self.encode_pri(iw, cell2, t2, cenc, refp);
377 Indeo3PrimaryTree::AbsFill(sec) => {
380 self.encode_sec(iw, cell, sec, cenc);
382 Indeo3PrimaryTree::RelFill(mv, sec) => {
383 if let Some(mv_idx) = find_mv(*mv, &self.mvs) {
387 let real_mv = self.mvs[usize::from(mv_idx)].0;
388 self.encode_sec_inter(iw, cell, sec, cenc, real_mv, refp);
392 self.encode_sec(iw, cell, sec, cenc);
397 fn encode_sec(&mut self, iw: &mut Indeo3Writer, cell: Indeo3Cell, tree: &Indeo3SecondaryTree, cenc: &mut CellEncoder) {
399 Indeo3SecondaryTree::HSplit(t1, t2) => {
401 let (cell1, cell2) = cell.split_h();
402 self.encode_sec(iw, cell1, t1, cenc);
403 self.encode_sec(iw, cell2, t2, cenc);
405 Indeo3SecondaryTree::VSplit(t1, t2) => {
407 let (cell1, cell2) = cell.split_v(self.stripw);
408 self.encode_sec(iw, cell1, t1, cenc);
409 self.encode_sec(iw, cell2, t2, cenc);
411 Indeo3SecondaryTree::VQNull(mode) => {
415 Indeo3SecondaryTree::VQData(mode) => {
417 self.encode_cell_data_intra(iw, cell, cenc, *mode);
421 fn encode_sec_inter(&mut self, iw: &mut Indeo3Writer, cell: Indeo3Cell, tree: &Indeo3SecondaryTree, cenc: &mut CellEncoder, mv: MV, refp: &Plane) {
423 Indeo3SecondaryTree::HSplit(_t1, _t2) => {
426 Indeo3SecondaryTree::VSplit(_t1, _t2) => {
429 Indeo3SecondaryTree::VQNull(mode) => {
432 cenc.read_mv_buffer(refp, cell, mv);
434 cenc.put_buffer(self);
436 Indeo3SecondaryTree::VQData(_mode) => {
438 self.encode_cell_data_inter(iw, cell, cenc, mv, refp);
442 fn encode_cell_data_intra(&mut self, iw: &mut Indeo3Writer, cell: Indeo3Cell, cenc: &mut CellEncoder, mode: u8) {
443 cenc.read_buffer(self, cell);
444 cenc.gen_diffs_intra();
445 cenc.compress_intra(mode);
446 cenc.put_buffer(self);
447 for &b in cenc.out[..cenc.osize].iter() {
451 fn encode_cell_data_inter(&mut self, iw: &mut Indeo3Writer, cell: Indeo3Cell, cenc: &mut CellEncoder, mv: MV, refp: &Plane) {
452 cenc.read_buffer(self, cell);
453 cenc.read_mv_buffer(refp, cell, mv);
454 cenc.gen_diffs_inter();
455 cenc.compress_inter();
456 cenc.put_buffer(self);
457 for &b in cenc.out[..cenc.osize].iter() {