[nihav.git] / nihav-indeo / src / codecs / indeo3enc / tree.rs

use super::Indeo3Writer;
use super::mv::*;
use super::cell::{CellEncoder, MAX_CELL_SIZE};

pub enum Indeo3PrimaryTree {
    VSplit(Box<Indeo3PrimaryTree>, Box<Indeo3PrimaryTree>),
    HSplit(Box<Indeo3PrimaryTree>, Box<Indeo3PrimaryTree>),
    RelFill(MV, Box<Indeo3SecondaryTree>),
    AbsFill(Box<Indeo3SecondaryTree>),
}

impl Indeo3PrimaryTree {
    pub fn print(&self) {
        println!("Plane tree:");
        self.print1(1);
    }
    fn print1(&self, depth: u8) {
        for _ in 0..depth {
            print!("    ");
        }
        match self {
            Indeo3PrimaryTree::VSplit(t1, t2) => {
                println!("vertical split");
                t1.print1(depth + 1);
                t2.print1(depth + 1);
            },
            Indeo3PrimaryTree::HSplit(t1, t2) => {
                println!("horizontal split");
                t1.print1(depth + 1);
                t2.print1(depth + 1);
            },
            Indeo3PrimaryTree::RelFill(mv, sec) => {
                println!("relative fill {},{}", mv.x, mv.y);
                sec.print1(depth + 1);
            },
            Indeo3PrimaryTree::AbsFill(sec) => {
                println!("absolute fill");
                sec.print1(depth + 1);
            }
        }
    }
}

pub enum Indeo3SecondaryTree {
    VSplit(Box<Indeo3SecondaryTree>, Box<Indeo3SecondaryTree>),
    HSplit(Box<Indeo3SecondaryTree>, Box<Indeo3SecondaryTree>),
    VQData(u8),
    VQNull(u8),
}

impl Indeo3SecondaryTree {
    fn print1(&self, depth: u8) {
        for _ in 0..depth {
            print!("    ");
        }
        match self {
            Indeo3SecondaryTree::VSplit(t1, t2) => {
                println!("vertical split");
                t1.print1(depth + 1);
                t2.print1(depth + 1);
            },
            Indeo3SecondaryTree::HSplit(t1, t2) => {
                println!("horizontal split");
                t1.print1(depth + 1);
                t2.print1(depth + 1);
            },
            Indeo3SecondaryTree::VQData(mode) => {
                println!("VQ data ({})", mode);
            },
            Indeo3SecondaryTree::VQNull(mode) => {
                println!("VQ Null ({})", mode);
            }
        }
    }
}

const THRESHOLD: u32 = 64;

#[derive(Clone, Copy)]
pub struct Indeo3Cell {
    x:      u8,
    y:      u8,
    w:      u8,
    h:      u8,
    intra:  bool,
}

impl Indeo3Cell {
    pub fn new(width: usize, height: usize, intra: bool) -> Self {
        Self {
            x:      0,
            y:      0,
            w:      (width / 4) as u8,
            h:      (height / 4) as u8,
            intra,
        }
    }

    pub fn get_x(&self) -> usize { usize::from(self.x) * 4 }
    pub fn get_y(&self) -> usize { usize::from(self.y) * 4 }
    pub fn get_width(&self) -> usize { usize::from(self.w) * 4 }
    pub fn get_height(&self) -> usize { usize::from(self.h) * 4 }
    pub fn is_intra(&self) -> bool { self.intra }

    fn split_h(&self) -> (Self, Self) {
        let h1 = if self.h > 2 { ((self.h + 2) >> 2) << 1 } else { 1 };
        let h2 = self.h - h1;
        let mut cell1 = *self;
        cell1.h  = h1;
        let mut cell2 = *self;
        cell2.y += h1;
        cell2.h  = h2;
        (cell1, cell2)
    }
    fn split_v(&self, stripw: u8) -> (Self, Self) {
        let w1 = if self.w > stripw {
                if self.w > stripw * 2 { stripw * 2 } else { stripw }
            } else {
                if self.w > 2 { ((self.w + 2) >> 2) << 1 } else { 1 }
            };
        let w2 = self.w - w1;
        let mut cell1 = *self;
        cell1.w  = w1;
        let mut cell2 = *self;
        cell2.x += w1;
        cell2.w  = w2;
        (cell1, cell2)
    }
}

impl std::fmt::Display for Indeo3Cell {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        write!(f, "[{}x{} @ {},{}{}]", self.get_width(), self.get_height(), self.get_x(), self.get_y(), if self.intra { " intra" } else { "" })
    }
}

#[derive(Default)]
pub struct Plane {
    pub data:   Vec<u8>,
    pub width:  usize,
    pub height: usize,
    pub stripw: u8,
    pub mvs:    Vec<(MV, u16)>,
}

fn ssd(a: u8, b: u8) -> u32 {
    let diff = i32::from(a) - i32::from(b);
    (diff * diff) as u32
}

impl Plane {
    pub fn alloc(&mut self, width: usize, height: usize, stripw: u8) {
        self.data.resize(width * height, 0);
        self.width  = width;
        self.height = height;
        self.stripw = stripw;
        if self.mvs.capacity() < 256 {
            self.mvs.reserve(256);
        }
    }
    pub fn fill(&mut self, src: &[u8], stride: usize) {
        for (dline, sline) in self.data.chunks_mut(self.width).zip(src.chunks(stride)) {
            for (dst, &src) in dline.iter_mut().zip(sline.iter()) {
                *dst = src >> 1;
            }
        }
    }
    pub fn clear_mvs(&mut self){
        self.mvs.clear();
    }
    pub fn checksum(&self) -> u16 {
        let xors = self.data.chunks(2).fold([0u8; 2], |acc, pair| [acc[0] ^ pair[0], acc[1] ^ pair[1]]);
        u16::from(xors[0]) | (u16::from(xors[1]) * 256)
    }
    pub fn find_cells(&mut self, is_intra: bool, pplane: &Plane, mv_est: &MotionEstimator) -> Box<Indeo3PrimaryTree> {
        let cell = Indeo3Cell::new(self.width, self.height, is_intra);
        self.split_pri(cell, pplane, mv_est)
    }
    fn split_pri(&mut self, cell: Indeo3Cell, pplane: &Plane, mv_est: &MotionEstimator) -> Box<Indeo3PrimaryTree> {
        let width  = cell.get_width();
        let height = cell.get_height();
        if width * height > MAX_CELL_SIZE {
            let (hsplit, vsplit) = if width != height {
                    (width > (self.stripw as usize) * 4 || width > height, height > width)
                } else {
                    let (hdiff, vdiff) = self.calculate_diffs(cell);
                    (vdiff > THRESHOLD && vdiff > hdiff,
                     hdiff > THRESHOLD && hdiff > vdiff)
                };
            match (hsplit, vsplit) {
                (true, _) => {
                    let (cell1, cell2) = cell.split_v(self.stripw);
                    let tree1 = self.split_pri(cell1, pplane, mv_est);
                    let tree2 = self.split_pri(cell2, pplane, mv_est);
                    Box::new(Indeo3PrimaryTree::VSplit(tree1, tree2))
                },
                (_, true) => {
                    let (cell1, cell2) = cell.split_h();
                    let tree1 = self.split_pri(cell1, pplane, mv_est);
                    let tree2 = self.split_pri(cell2, pplane, mv_est);
                    Box::new(Indeo3PrimaryTree::HSplit(tree1, tree2))
                },
                (false, false) => {
                    let sec = self.split_sec(cell);
                    Box::new(Indeo3PrimaryTree::AbsFill(sec))
                },
            }
        } else {
            if !cell.intra {
                if let Some((mv, flat)) = mv_est.mv_search(self, pplane, cell) {
                    return self.add_mv_tree(mv, flat);
                }

                // try splitting once to see if it improves situation
                if width >= 16 && height >= 16 {
                    let vsplit = width > height;
                    let (cell1, cell2) = if vsplit {
                            cell.split_v(self.stripw)
                        } else {
                            cell.split_h()
                        };
                    let search1 = mv_est.mv_search(self, pplane, cell1);
                    let search2 = mv_est.mv_search(self, pplane, cell2);
                    if search1.is_some() || search2.is_some() {
                        let tree1 = if let Some((mv, flat)) = search1 {
                                self.add_mv_tree(mv, flat)
                            } else {
                                let sec = self.split_sec(cell1);
                                Box::new(Indeo3PrimaryTree::AbsFill(sec))
                            };
                        let tree2 = if let Some((mv, flat)) = search2 {
                                self.add_mv_tree(mv, flat)
                            } else {
                                let sec = self.split_sec(cell2);
                                Box::new(Indeo3PrimaryTree::AbsFill(sec))
                            };
                        return if vsplit {
                                Box::new(Indeo3PrimaryTree::VSplit(tree1, tree2))
                            } else {
                                Box::new(Indeo3PrimaryTree::HSplit(tree1, tree2))
                            }
                    }
                }
            }
            let sec = self.split_sec(cell);
            Box::new(Indeo3PrimaryTree::AbsFill(sec))
        }
    }
    fn add_mv_tree(&mut self, mv: MV, flat: bool) -> Box<Indeo3PrimaryTree> {
        let sec = if flat {
                Box::new(Indeo3SecondaryTree::VQNull(0))
            } else {
                Box::new(Indeo3SecondaryTree::VQData(0))
            };

        let mut found = false;
        for (ref cmv, ref mut count) in self.mvs.iter_mut() {
            if cmv == &mv {
                *count += 1;
                found = true;
                break;
            }
        }
        if !found {
            self.mvs.push((mv, 1));
        }

        Box::new(Indeo3PrimaryTree::RelFill(mv, sec))
    }
    fn split_sec(&mut self, cell: Indeo3Cell) -> Box<Indeo3SecondaryTree> {
        let (hdiff, vdiff) = self.calculate_diffs(cell);
        if hdiff == 0 && vdiff == 0 {
            if !cell.intra {
                return Box::new(Indeo3SecondaryTree::VQNull(0));
            } else {
                return Box::new(Indeo3SecondaryTree::VQData(0));
            }
        }
        if cell.get_width() > 16 && cell.get_height() > 16 {
            let hsplit = vdiff > THRESHOLD && vdiff > hdiff * 2;
            let vsplit = hdiff > THRESHOLD && hdiff > vdiff * 2;
            match (vsplit, hsplit) {
                (true, _) => {
                    let (cell1, cell2) = cell.split_v(self.stripw);
                    let tree1 = self.split_sec(cell1);
                    let tree2 = self.split_sec(cell2);
                    Box::new(Indeo3SecondaryTree::VSplit(tree1, tree2))
                },
                (_, true) => {
                    let (cell1, cell2) = cell.split_h();
                    let tree1 = self.split_sec(cell1);
                    let tree2 = self.split_sec(cell2);
                    Box::new(Indeo3SecondaryTree::HSplit(tree1, tree2))
                },
                _ => {
                    Box::new(Indeo3SecondaryTree::VQData(0))
                },
            }
        } else {
            let is_w8 = (cell.get_width()  & 7) == 0;
            let is_h8 = (cell.get_height() & 7) == 0;
            let mode = match (hdiff > THRESHOLD, vdiff > THRESHOLD) {
                    (false, false) if is_w8 && is_h8 => 10,
                    (_, true)      if is_h8          => 3,
                    _                                => 0,
                };
            Box::new(Indeo3SecondaryTree::VQData(mode))
        }
    }
    fn calculate_diffs(&self, cell: Indeo3Cell) -> (u32, u32) {
        let offset = cell.get_x() + cell.get_y() * self.width;
        let mut w = cell.get_width();
        if cell.get_x() + w == self.width { w -= 1; }
        let mut h = cell.get_height();
        if cell.get_y() + h == self.height { h -= 1; }

        let mut vdiff = 0;
        let mut hdiff = 0;
        let src0 = &self.data[offset..];
        let src1 = &self.data[offset + self.width..];
        for (line0, line1) in src0.chunks(self.width).zip(src1.chunks(self.width)).take(h) {
            for ((&cur, &right), &bottom) in line0.iter().zip(line0[1..].iter()).zip(line1.iter()).take(w) {
                hdiff += ssd(cur, right);
                vdiff += ssd(cur, bottom);
            }
        }
        let area = (w * h) as u32;
        (hdiff * 16 / area, vdiff * 16 / area)
    }
    pub fn encode_tree(&mut self, iw: &mut Indeo3Writer, tree: &Indeo3PrimaryTree, cenc: &mut CellEncoder, is_intra: bool, refp: &Plane) {
        let cell = Indeo3Cell::new(self.width, self.height, is_intra);
        self.encode_pri(iw, cell, tree, cenc, refp);
    }
    fn encode_pri(&mut self, iw: &mut Indeo3Writer, mut cell: Indeo3Cell, tree: &Indeo3PrimaryTree, cenc: &mut CellEncoder, refp: &Plane) {
        match tree {
            Indeo3PrimaryTree::HSplit(t1, t2) => {
                iw.put_2bits(0);
                let (cell1, cell2) = cell.split_h();
                self.encode_pri(iw, cell1, t1, cenc, refp);
                self.encode_pri(iw, cell2, t2, cenc, refp);
            },
            Indeo3PrimaryTree::VSplit(t1, t2) => {
                iw.put_2bits(1);
                let (cell1, cell2) = cell.split_v(self.stripw);
                self.encode_pri(iw, cell1, t1, cenc, refp);
                self.encode_pri(iw, cell2, t2, cenc, refp);
            },
            Indeo3PrimaryTree::AbsFill(sec) => {
                iw.put_2bits(2);
                cell.intra = true;
                self.encode_sec(iw, cell, sec, cenc);
            }
            Indeo3PrimaryTree::RelFill(mv, sec) => {
                if let Some(mv_idx) = find_mv(*mv, &self.mvs) {
                    iw.put_2bits(3);
                    iw.put_byte(mv_idx);
                    cell.intra = false;
                    let real_mv = self.mvs[usize::from(mv_idx)].0;
                    self.encode_sec_inter(iw, cell, sec, cenc, real_mv, refp);
                } else {
                    iw.put_2bits(2);
                    cell.intra = true;
                    self.encode_sec(iw, cell, sec, cenc);
                }
            },
        }
    }
    fn encode_sec(&mut self, iw: &mut Indeo3Writer, cell: Indeo3Cell, tree: &Indeo3SecondaryTree, cenc: &mut CellEncoder) {
        match tree {
            Indeo3SecondaryTree::HSplit(t1, t2) => {
                iw.put_2bits(0);
                let (cell1, cell2) = cell.split_h();
                self.encode_sec(iw, cell1, t1, cenc);
                self.encode_sec(iw, cell2, t2, cenc);
            },
            Indeo3SecondaryTree::VSplit(t1, t2) => {
                iw.put_2bits(1);
                let (cell1, cell2) = cell.split_v(self.stripw);
                self.encode_sec(iw, cell1, t1, cenc);
                self.encode_sec(iw, cell2, t2, cenc);
            },
            Indeo3SecondaryTree::VQNull(mode) => {
                iw.put_2bits(2);
                iw.put_2bits(*mode);
            },
            Indeo3SecondaryTree::VQData(mode) => {
                iw.put_2bits(3);
                self.encode_cell_data_intra(iw, cell, cenc, *mode);
            },
        }
    }
    fn encode_sec_inter(&mut self, iw: &mut Indeo3Writer, cell: Indeo3Cell, tree: &Indeo3SecondaryTree, cenc: &mut CellEncoder, mv: MV, refp: &Plane) {
        match tree {
            Indeo3SecondaryTree::HSplit(_t1, _t2) => {
                unimplemented!();
            },
            Indeo3SecondaryTree::VSplit(_t1, _t2) => {
                unimplemented!();
            },
            Indeo3SecondaryTree::VQNull(mode) => {
                iw.put_2bits(2);
                iw.put_2bits(*mode);
                cenc.read_mv_buffer(refp, cell, mv);
                cenc.null_mv();
                cenc.put_buffer(self);
            },
            Indeo3SecondaryTree::VQData(_mode) => {
                iw.put_2bits(3);
                self.encode_cell_data_inter(iw, cell, cenc, mv, refp);
            },
        }
    }
    fn encode_cell_data_intra(&mut self, iw: &mut Indeo3Writer, cell: Indeo3Cell, cenc: &mut CellEncoder, mode: u8) {
        cenc.read_buffer(self, cell);
        cenc.gen_diffs_intra();
        cenc.compress_intra(mode);
        cenc.put_buffer(self);
        for &b in cenc.out[..cenc.osize].iter() {
            iw.put_byte(b);
        }
    }
    fn encode_cell_data_inter(&mut self, iw: &mut Indeo3Writer, cell: Indeo3Cell, cenc: &mut CellEncoder, mv: MV, refp: &Plane) {
        cenc.read_buffer(self, cell);
        cenc.read_mv_buffer(refp, cell, mv);
        cenc.gen_diffs_inter();
        cenc.compress_inter();
        cenc.put_buffer(self);
        for &b in cenc.out[..cenc.osize].iter() {
            iw.put_byte(b);
        }
    }
}
Commit	Line	Data
77c25c7b KS	1	use super::Indeo3Writer;
	2	use super::mv::*;
	3	use super::cell::{CellEncoder, MAX_CELL_SIZE};
	4
	5	pub enum Indeo3PrimaryTree {
	6	VSplit(Box<Indeo3PrimaryTree>, Box<Indeo3PrimaryTree>),
	7	HSplit(Box<Indeo3PrimaryTree>, Box<Indeo3PrimaryTree>),
	8	RelFill(MV, Box<Indeo3SecondaryTree>),
	9	AbsFill(Box<Indeo3SecondaryTree>),
	10	}
	11
	12	impl Indeo3PrimaryTree {
	13	pub fn print(&self) {
	14	println!("Plane tree:");
	15	self.print1(1);
	16	}
	17	fn print1(&self, depth: u8) {
	18	for _ in 0..depth {
	19	print!(" ");
	20	}
	21	match self {
	22	Indeo3PrimaryTree::VSplit(t1, t2) => {
	23	println!("vertical split");
	24	t1.print1(depth + 1);
	25	t2.print1(depth + 1);
	26	},
	27	Indeo3PrimaryTree::HSplit(t1, t2) => {
	28	println!("horizontal split");
	29	t1.print1(depth + 1);
	30	t2.print1(depth + 1);
	31	},
	32	Indeo3PrimaryTree::RelFill(mv, sec) => {
	33	println!("relative fill {},{}", mv.x, mv.y);
	34	sec.print1(depth + 1);
	35	},
	36	Indeo3PrimaryTree::AbsFill(sec) => {
	37	println!("absolute fill");
	38	sec.print1(depth + 1);
	39	}
	40	}
	41	}
	42	}
	43
	44	pub enum Indeo3SecondaryTree {
	45	VSplit(Box<Indeo3SecondaryTree>, Box<Indeo3SecondaryTree>),
	46	HSplit(Box<Indeo3SecondaryTree>, Box<Indeo3SecondaryTree>),
	47	VQData(u8),
	48	VQNull(u8),
	49	}
	50
	51	impl Indeo3SecondaryTree {
	52	fn print1(&self, depth: u8) {
	53	for _ in 0..depth {
	54	print!(" ");
	55	}
	56	match self {
	57	Indeo3SecondaryTree::VSplit(t1, t2) => {
	58	println!("vertical split");
	59	t1.print1(depth + 1);
	60	t2.print1(depth + 1);
	61	},
	62	Indeo3SecondaryTree::HSplit(t1, t2) => {
	63	println!("horizontal split");
	64	t1.print1(depth + 1);
65	t2.print1(depth + 1);
66	},
67	Indeo3SecondaryTree::VQData(mode) => {
68	println!("VQ data ({})", mode);
69	},
70	Indeo3SecondaryTree::VQNull(mode) => {
71	println!("VQ Null ({})", mode);
72	}
73	}
74	}
75	}
76
77	const THRESHOLD: u32 = 64;
78
79	#[derive(Clone, Copy)]
80	pub struct Indeo3Cell {
81	x: u8,
82	y: u8,
83	w: u8,
84	h: u8,
85	intra: bool,
86	}
87
88	impl Indeo3Cell {
89	pub fn new(width: usize, height: usize, intra: bool) -> Self {
90	Self {
91	x: 0,
92	y: 0,
93	w: (width / 4) as u8,
94	h: (height / 4) as u8,
95	intra,
96	}
97	}
98
99	pub fn get_x(&self) -> usize { usize::from(self.x) * 4 }
100	pub fn get_y(&self) -> usize { usize::from(self.y) * 4 }
101	pub fn get_width(&self) -> usize { usize::from(self.w) * 4 }
102	pub fn get_height(&self) -> usize { usize::from(self.h) * 4 }
103	pub fn is_intra(&self) -> bool { self.intra }
104
105	fn split_h(&self) -> (Self, Self) {
106	let h1 = if self.h > 2 { ((self.h + 2) >> 2) << 1 } else { 1 };
107	let h2 = self.h - h1;
108	let mut cell1 = *self;
109	cell1.h = h1;
110	let mut cell2 = *self;
111	cell2.y += h1;
112	cell2.h = h2;
113	(cell1, cell2)
114	}
115	fn split_v(&self, stripw: u8) -> (Self, Self) {
116	let w1 = if self.w > stripw {
117	if self.w > stripw * 2 { stripw * 2 } else { stripw }
118	} else {
119	if self.w > 2 { ((self.w + 2) >> 2) << 1 } else { 1 }
120	};
121	let w2 = self.w - w1;
122	let mut cell1 = *self;
123	cell1.w = w1;
124	let mut cell2 = *self;
125	cell2.x += w1;
126	cell2.w = w2;
127	(cell1, cell2)
128	}
129	}
130
131	impl std::fmt::Display for Indeo3Cell {
132	fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
133	write!(f, "[{}x{} @ {},{}{}]", self.get_width(), self.get_height(), self.get_x(), self.get_y(), if self.intra { " intra" } else { "" })
134	}
135	}
136
137	#[derive(Default)]
138	pub struct Plane {
139	pub data: Vec<u8>,
140	pub width: usize,
141	pub height: usize,
142	pub stripw: u8,
143	pub mvs: Vec<(MV, u16)>,
144	}
145
146	fn ssd(a: u8, b: u8) -> u32 {
147	let diff = i32::from(a) - i32::from(b);
148	(diff * diff) as u32
149	}
150
151	impl Plane {
152	pub fn alloc(&mut self, width: usize, height: usize, stripw: u8) {
153	self.data.resize(width * height, 0);
154	self.width = width;
155	self.height = height;
156	self.stripw = stripw;
157	if self.mvs.capacity() < 256 {
158	self.mvs.reserve(256);
159	}
160	}
161	pub fn fill(&mut self, src: &[u8], stride: usize) {
162	for (dline, sline) in self.data.chunks_mut(self.width).zip(src.chunks(stride)) {
163	for (dst, &src) in dline.iter_mut().zip(sline.iter()) {
164	*dst = src >> 1;
165	}
166	}
167	}
168	pub fn clear_mvs(&mut self){
169	self.mvs.clear();
170	}
171	pub fn checksum(&self) -> u16 {
7b430a1e	172	let xors = self.data.chunks(2).fold([0u8; 2], \|acc, pair\| [acc[0] ^ pair[0], acc[1] ^ pair[1]]);
77c25c7b KS	173	u16::from(xors[0]) \| (u16::from(xors[1]) * 256)
	174	}
	175	pub fn find_cells(&mut self, is_intra: bool, pplane: &Plane, mv_est: &MotionEstimator) -> Box<Indeo3PrimaryTree> {
	176	let cell = Indeo3Cell::new(self.width, self.height, is_intra);
	177	self.split_pri(cell, pplane, mv_est)
	178	}
	179	fn split_pri(&mut self, cell: Indeo3Cell, pplane: &Plane, mv_est: &MotionEstimator) -> Box<Indeo3PrimaryTree> {
	180	let width = cell.get_width();
	181	let height = cell.get_height();
	182	if width * height > MAX_CELL_SIZE {
	183	let (hsplit, vsplit) = if width != height {
	184	(width > (self.stripw as usize) * 4 \|\| width > height, height > width)
	185	} else {
	186	let (hdiff, vdiff) = self.calculate_diffs(cell);
	187	(vdiff > THRESHOLD && vdiff > hdiff,
	188	hdiff > THRESHOLD && hdiff > vdiff)
	189	};
	190	match (hsplit, vsplit) {
	191	(true, _) => {
	192	let (cell1, cell2) = cell.split_v(self.stripw);
	193	let tree1 = self.split_pri(cell1, pplane, mv_est);
	194	let tree2 = self.split_pri(cell2, pplane, mv_est);
	195	Box::new(Indeo3PrimaryTree::VSplit(tree1, tree2))
	196	},
	197	(_, true) => {
	198	let (cell1, cell2) = cell.split_h();
	199	let tree1 = self.split_pri(cell1, pplane, mv_est);
	200	let tree2 = self.split_pri(cell2, pplane, mv_est);
	201	Box::new(Indeo3PrimaryTree::HSplit(tree1, tree2))
	202	},
	203	(false, false) => {
	204	let sec = self.split_sec(cell);
	205	Box::new(Indeo3PrimaryTree::AbsFill(sec))
	206	},
	207	}
	208	} else {
	209	if !cell.intra {
	210	if let Some((mv, flat)) = mv_est.mv_search(self, pplane, cell) {
	211	return self.add_mv_tree(mv, flat);
	212	}
	213
	214	// try splitting once to see if it improves situation
	215	if width >= 16 && height >= 16 {
	216	let vsplit = width > height;
	217	let (cell1, cell2) = if vsplit {
	218	cell.split_v(self.stripw)
	219	} else {
	220	cell.split_h()
	221	};
	222	let search1 = mv_est.mv_search(self, pplane, cell1);
	223	let search2 = mv_est.mv_search(self, pplane, cell2);
	224	if search1.is_some() \|\| search2.is_some() {
	225	let tree1 = if let Some((mv, flat)) = search1 {
	226	self.add_mv_tree(mv, flat)
	227	} else {
	228	let sec = self.split_sec(cell1);
	229	Box::new(Indeo3PrimaryTree::AbsFill(sec))
	230	};
	231	let tree2 = if let Some((mv, flat)) = search2 {
	232	self.add_mv_tree(mv, flat)
	233	} else {
	234	let sec = self.split_sec(cell2);
	235	Box::new(Indeo3PrimaryTree::AbsFill(sec))
	236	};
237	return if vsplit {
238	Box::new(Indeo3PrimaryTree::VSplit(tree1, tree2))
239	} else {
240	Box::new(Indeo3PrimaryTree::HSplit(tree1, tree2))
241	}
242	}
243	}
244	}
245	let sec = self.split_sec(cell);
246	Box::new(Indeo3PrimaryTree::AbsFill(sec))
247	}
248	}
249	fn add_mv_tree(&mut self, mv: MV, flat: bool) -> Box<Indeo3PrimaryTree> {
250	let sec = if flat {
251	Box::new(Indeo3SecondaryTree::VQNull(0))
252	} else {
253	Box::new(Indeo3SecondaryTree::VQData(0))
254	};
255
256	let mut found = false;
257	for (ref cmv, ref mut count) in self.mvs.iter_mut() {
258	if cmv == &mv {
259	*count += 1;
260	found = true;
261	break;
262	}
263	}
264	if !found {
265	self.mvs.push((mv, 1));
266	}
267
268	Box::new(Indeo3PrimaryTree::RelFill(mv, sec))
269	}
270	fn split_sec(&mut self, cell: Indeo3Cell) -> Box<Indeo3SecondaryTree> {
271	let (hdiff, vdiff) = self.calculate_diffs(cell);
272	if hdiff == 0 && vdiff == 0 {
273	if !cell.intra {
274	return Box::new(Indeo3SecondaryTree::VQNull(0));
275	} else {
276	return Box::new(Indeo3SecondaryTree::VQData(0));
277	}
278	}
279	if cell.get_width() > 16 && cell.get_height() > 16 {
280	let hsplit = vdiff > THRESHOLD && vdiff > hdiff * 2;
281	let vsplit = hdiff > THRESHOLD && hdiff > vdiff * 2;
282	match (vsplit, hsplit) {
283	(true, _) => {
284	let (cell1, cell2) = cell.split_v(self.stripw);
285	let tree1 = self.split_sec(cell1);
286	let tree2 = self.split_sec(cell2);
287	Box::new(Indeo3SecondaryTree::VSplit(tree1, tree2))
288	},
289	(_, true) => {
290	let (cell1, cell2) = cell.split_h();
291	let tree1 = self.split_sec(cell1);
292	let tree2 = self.split_sec(cell2);
293	Box::new(Indeo3SecondaryTree::HSplit(tree1, tree2))
294	},
295	_ => {
296	Box::new(Indeo3SecondaryTree::VQData(0))
297	},
298	}
299	} else {
300	let is_w8 = (cell.get_width() & 7) == 0;
301	let is_h8 = (cell.get_height() & 7) == 0;
302	let mode = match (hdiff > THRESHOLD, vdiff > THRESHOLD) {
303	(false, false) if is_w8 && is_h8 => 10,
304	(_, true) if is_h8 => 3,
305	_ => 0,
306	};
307	Box::new(Indeo3SecondaryTree::VQData(mode))
308	}
309	}
310	fn calculate_diffs(&self, cell: Indeo3Cell) -> (u32, u32) {
311	let offset = cell.get_x() + cell.get_y() * self.width;
312	let mut w = cell.get_width();
313	if cell.get_x() + w == self.width { w -= 1; }
314	let mut h = cell.get_height();
315	if cell.get_y() + h == self.height { h -= 1; }
316
317	let mut vdiff = 0;
318	let mut hdiff = 0;
319	let src0 = &self.data[offset..];
320	let src1 = &self.data[offset + self.width..];
321	for (line0, line1) in src0.chunks(self.width).zip(src1.chunks(self.width)).take(h) {
322	for ((&cur, &right), &bottom) in line0.iter().zip(line0[1..].iter()).zip(line1.iter()).take(w) {
323	hdiff += ssd(cur, right);
324	vdiff += ssd(cur, bottom);
325	}
326	}
327	let area = (w * h) as u32;
328	(hdiff * 16 / area, vdiff * 16 / area)
329	}
330	pub fn encode_tree(&mut self, iw: &mut Indeo3Writer, tree: &Indeo3PrimaryTree, cenc: &mut CellEncoder, is_intra: bool, refp: &Plane) {
331	let cell = Indeo3Cell::new(self.width, self.height, is_intra);
332	self.encode_pri(iw, cell, tree, cenc, refp);
333	}
334	fn encode_pri(&mut self, iw: &mut Indeo3Writer, mut cell: Indeo3Cell, tree: &Indeo3PrimaryTree, cenc: &mut CellEncoder, refp: &Plane) {
335	match tree {
336	Indeo3PrimaryTree::HSplit(t1, t2) => {
337	iw.put_2bits(0);
338	let (cell1, cell2) = cell.split_h();
339	self.encode_pri(iw, cell1, t1, cenc, refp);
340	self.encode_pri(iw, cell2, t2, cenc, refp);
341	},
342	Indeo3PrimaryTree::VSplit(t1, t2) => {
343	iw.put_2bits(1);
344	let (cell1, cell2) = cell.split_v(self.stripw);
345	self.encode_pri(iw, cell1, t1, cenc, refp);
346	self.encode_pri(iw, cell2, t2, cenc, refp);
347	},
348	Indeo3PrimaryTree::AbsFill(sec) => {
349	iw.put_2bits(2);
350	cell.intra = true;
351	self.encode_sec(iw, cell, sec, cenc);
352	}
353	Indeo3PrimaryTree::RelFill(mv, sec) => {
354	if let Some(mv_idx) = find_mv(*mv, &self.mvs) {
355	iw.put_2bits(3);
356	iw.put_byte(mv_idx);
357	cell.intra = false;
358	let real_mv = self.mvs[usize::from(mv_idx)].0;
359	self.encode_sec_inter(iw, cell, sec, cenc, real_mv, refp);
360	} else {
361	iw.put_2bits(2);
362	cell.intra = true;
363	self.encode_sec(iw, cell, sec, cenc);
364	}
365	},
366	}
367	}
368	fn encode_sec(&mut self, iw: &mut Indeo3Writer, cell: Indeo3Cell, tree: &Indeo3SecondaryTree, cenc: &mut CellEncoder) {
369	match tree {
370	Indeo3SecondaryTree::HSplit(t1, t2) => {
371	iw.put_2bits(0);
372	let (cell1, cell2) = cell.split_h();
373	self.encode_sec(iw, cell1, t1, cenc);
374	self.encode_sec(iw, cell2, t2, cenc);
375	},
376	Indeo3SecondaryTree::VSplit(t1, t2) => {
377	iw.put_2bits(1);
378	let (cell1, cell2) = cell.split_v(self.stripw);
379	self.encode_sec(iw, cell1, t1, cenc);
380	self.encode_sec(iw, cell2, t2, cenc);
381	},
382	Indeo3SecondaryTree::VQNull(mode) => {
383	iw.put_2bits(2);
384	iw.put_2bits(*mode);
385	},
386	Indeo3SecondaryTree::VQData(mode) => {
387	iw.put_2bits(3);
388	self.encode_cell_data_intra(iw, cell, cenc, *mode);
389	},
390	}
391	}
392	fn encode_sec_inter(&mut self, iw: &mut Indeo3Writer, cell: Indeo3Cell, tree: &Indeo3SecondaryTree, cenc: &mut CellEncoder, mv: MV, refp: &Plane) {
393	match tree {
394	Indeo3SecondaryTree::HSplit(_t1, _t2) => {
395	unimplemented!();
396	},
397	Indeo3SecondaryTree::VSplit(_t1, _t2) => {
398	unimplemented!();
399	},
400	Indeo3SecondaryTree::VQNull(mode) => {
401	iw.put_2bits(2);
402	iw.put_2bits(*mode);
403	cenc.read_mv_buffer(refp, cell, mv);
404	cenc.null_mv();
405	cenc.put_buffer(self);
406	},
407	Indeo3SecondaryTree::VQData(_mode) => {
408	iw.put_2bits(3);
409	self.encode_cell_data_inter(iw, cell, cenc, mv, refp);
410	},
411	}
412	}
413	fn encode_cell_data_intra(&mut self, iw: &mut Indeo3Writer, cell: Indeo3Cell, cenc: &mut CellEncoder, mode: u8) {
414	cenc.read_buffer(self, cell);
415	cenc.gen_diffs_intra();
416	cenc.compress_intra(mode);
417	cenc.put_buffer(self);
418	for &b in cenc.out[..cenc.osize].iter() {
419	iw.put_byte(b);
420	}
421	}
422	fn encode_cell_data_inter(&mut self, iw: &mut Indeo3Writer, cell: Indeo3Cell, cenc: &mut CellEncoder, mv: MV, refp: &Plane) {
423	cenc.read_buffer(self, cell);
424	cenc.read_mv_buffer(refp, cell, mv);
425	cenc.gen_diffs_inter();
426	cenc.compress_inter();
427	cenc.put_buffer(self);
428	for &b in cenc.out[..cenc.osize].iter() {
429	iw.put_byte(b);
430	}
431	}
432	}