moi 0.1.1

//! encoder and decoder for the MOI image format, a format inspired by [QOI](https://qoiformat.org/), with more focus on beating PNG in all aspects (speed, size, simplicity).
//! 
//! ### Example
//! ```rust
//! use moi::Image;
//!
//! let image = Image {
//!   width,
//!   height,
//!   pixels,
//! };
//!
//! let encoded = image.encode();
//! let decoded = Image::decode(&encoded)?;
//!
//! assert_eq!(image, decoded);
//! ```
//!
//! ### Benchmarks
//!
//! ```
//! fmt  | encode  | decode  | size
//! moi  | 20.745s | 11.192s | 21.65%
//! qoi  |  6.774s |  5.712s | 25.58%
//! png5 | 111.28s | 15.128s | 23.66%
//! png9 | 512.90s | 15.021s | 22.92%
//! ```
//!
//! Benchmark timings were collected on an AMD Ryzen 7 3750H  
//! The same [test suite](https://qoiformat.org/benchmark/qoi_benchmark_suite.tar) as QOI was used, ignoring two images with broken checksums.

#![feature(exclusive_range_pattern,portable_simd)]

mod consts;
mod visitor;
mod algorithm;
use algorithm::*;
use consts::*;
use visitor::*;

/// current moi encoding version
pub const VERSION: u8 = 0;

/// An uncompressed image
#[derive(Default,Debug,Clone,Eq,PartialEq)]
pub struct Image {
	/// Image width in pixels
	pub width: u32,
	/// Image height in pixels
	pub height: u32,
	/// The image pixels, stored as 8 bit rgba values, encoded left to right, top to bottom 
	pub pixels: Vec<[u8; 4]>,
}

impl Image {
	/// Encode the image to a newly allocated Vector, panics if `pixels.len() < width * height`
	pub fn encode(&self) -> Vec<u8> {
		self.try_encode().expect("cannot encode an image with missing pixels")
	}

	/// Encode the image to a newly allocated Vector, returns None if `pixels.len() < width * height`
	pub fn try_encode(&self) -> Option<Vec<u8>> {
		if self.pixels.len() < (self.width * self.height) as usize {
			return None;
		}
		let mut history = MoiHistory::new();
		
		let mut pixels = PixelVisitor::new(self.width, self.height, &self.pixels);
		let mut writer = MoiWriter::new(MoiHeader {
			magic: *b"moi",
			version: VERSION,
			width: self.width,
			height: self.height,
		});
		
		while let Some(pixel) = pixels.next() {
			if let Some(i) = history.find_index(pixel, 0, INDEX_MAX) {
				let i = i as u8;
				history.move_to_front(i);
				if i == 0 {
					let mut len = 1;
					while pixels.peek() == Some(pixel) {
						len += 1;
						pixels.next();
					}
					writer.encode_run(len);
				} else {
					let max_values = [DOUBLE_MAX, TRIPLE_MAX, QUAD_MAX];
					let mut j = 0;

					while j < 3 && i < max_values[j] && pixels.peek() == Some(pixel) {
						pixels.next();
						j += 1;
					}

					let codes = [INDEX, DOUBLE, TRIPLE, QUAD];
					writer.write(codes[j] + i);
				}
			} else if pixel[3] == history.first()[3] {
				let mut diff = [pixel[0].wrapping_sub(history.first()[0]), pixel[1].wrapping_sub(history.first()[1]), pixel[2].wrapping_sub(history.first()[2])];
				let [r,g,b] = diff;
				
				if diff == [0,0,2] {
					diff = [0; 3]; //special case: we encode [0,0,2] using the unused luma as described in the spec
				}
				let absr = if r < 128 { r.wrapping_sub(DIFFU_MIN) } else { 0u8.wrapping_sub(r).wrapping_sub(DIFFU_MIN) };
				
				if diff == [2,0,0] {
					history.push(pixel);
					writer.write(DIFF200);
				} else if writer.try_luma(diff, 1) {
					history.push(pixel);
				} else if r == g && r == b && absr < DIFFU_RANGE {
					history.push(pixel);
					if r < 128 {
						writer.write(DIFFU + DIFFU_RANGE + absr);
					} else {
						writer.write(DIFFU + absr);
					}
				//we can try luma2 or index2 first, index2 doesn't bloat the queue
				//index2 is 0.09% better compression, luma2 is 5-10% faster, we choose speed
				} else if writer.try_luma(diff, 2) {
					history.push(pixel);
				} else if let Some(i) = history.find_index(pixel, INDEX_MAX, HISTORY_SIZE) {
					history.move_to_front(i as u8);
					writer.write(UTIL);
					writer.write(i as u8);
				} else {
					history.push(pixel);
					if (writer.unwritten_rgb > 0 && writer.unwritten_rgb < RGB_MAX) || !writer.try_luma(diff, 3) {
						writer.add_rgb(pixel);
					}
				}
			} else if let Some(i) = history.find_index(pixel, INDEX_MAX, HISTORY_SIZE) {
				history.move_to_front(i as u8);
				writer.write(UTIL);
				writer.write(i as u8);
			} else {
				history.push(pixel);
				writer.add_rgba(pixel);
			}
		}
		
		Some(writer.finish())
	}

	/// decodes an `Image` from a stream of bytes, returns an error if the header is invalid or the stream does not have enough bytes
	pub fn decode<'a>(bytes: impl IntoIterator<Item=&'a u8>) -> Result<Self, &'static str> {
		let mut bytes = bytes.into_iter().copied();
		let mut byte = || bytes.next().ok_or("missing data");
		
		let mut header = [0; 12];
		for b in &mut header {
			*b  = byte()?;
		}
		let MoiHeader {
			magic,
			version,
			width,
			height
		} = MoiHeader::decode(header);
		if magic != *b"moi" {
			Err("bad magic")?
		} else if version > VERSION {
			Err("unsupported version")?
		}
		
		let mut history = MoiHistory::new();
		let mut writer = PixelWriter::new(width, height);
		
		while !writer.finished() {
			let tag = match byte() {
				Ok(tag) => tag,
				Err(_) => break,
			};
			
			match tag {
				INDEX..INDEX_END => {
					history.move_to_front(tag - INDEX);
					writer.output(history.first());
				},
				DOUBLE..DOUBLE_END => {
					history.move_to_front(tag - DOUBLE);
					for _ in 0..2 { writer.output(history.first()); }
				},
				TRIPLE..TRIPLE_END => {
					history.move_to_front(tag - TRIPLE);
					for _ in 0..3 { writer.output(history.first()); }
				},
				QUAD..QUAD_END => {
					history.move_to_front(tag - QUAD);
					for _ in 0..4 { writer.output(history.first()); }
				},
				RUN..RUN_END => for _ in 0..(tag - RUN + 5) { writer.output(history.first()); },
				LUMA3..LUMA3_END => {
					let db_dr = byte()?;
					let g = byte()?;
					let db = db_dr & 63;
					let dr = (tag - LUMA3) << 2 | db_dr >> 6;
					let bias = if g > 127 { 31 } else { 32 };
					let r = dr.wrapping_add(g).wrapping_sub(bias);
					let b = db.wrapping_add(g).wrapping_sub(bias);
					let p = [history.first()[0].wrapping_add(r), history.first()[1].wrapping_add(g), history.first()[2].wrapping_add(b), history.first()[3]];
					history.push(p);
					writer.output(p);
				},
				DIFFU..DIFFU_END => {
					let diff = if tag - DIFFU >= DIFFU_RANGE {
						3 + (tag - DIFFU) - DIFFU_RANGE
					} else {
						253 - (tag - DIFFU)
					};
					let mut p = history.first();
					p[0] = p[0].wrapping_add(diff);
					p[1] = p[1].wrapping_add(diff);
					p[2] = p[2].wrapping_add(diff);
					history.push(p);
					writer.output(p);
				},
				RGB..RGB_END => for _ in 0..(tag - RGB + 1) {
					history.push([byte()?, byte()?, byte()?, history.first()[3]]);
					writer.output(history.first());
				},
				RGBA => {
					history.push([byte()?, byte()?, byte()?, byte()?]);
					writer.output(history.first());
				},
				RGBA2 => for _ in 0..2 {
					history.push([byte()?, byte()?, byte()?, byte()?]);
					writer.output(history.first());
				},
				UTIL => {
					let len = match byte()? as usize {
						i if i >= INDEX_MAX => {
							history.move_to_front(i as u8);
							writer.output(history.first());
							0
						},
						len if len < INDEX_MAX - 2 => {
							len + LONG_RUN_MIN
						},
						n if n == INDEX_MAX - 2 => {
							LONG_RUN_MAX + byte()? as usize
						},
						_ => LONG_RUN_MAX + 256 + u16::from_le_bytes([byte()?, byte()?]) as usize,
					};
					for _ in 0..len { writer.output(history.first()); }
				},
				DIFF200 => {
					let mut p = history.first();
					p[0] = p[0].wrapping_add(2);
					history.push(p);
					writer.output(p);
				},
				LUMA..LUMA_END => {
					let diff = tag - LUMA;
					let dg = diff / 16;
					let dr = diff / 4 % 4;
					let db = diff % 4;
					let g = dg.wrapping_sub(LUMA_BIAS);
					let bias = if g > 127 { 1 } else { 2 };
					let r = dr.wrapping_add(g).wrapping_sub(bias);
					let mut b = db.wrapping_add(g).wrapping_sub(bias);
					if [r,g,b] == [0;3] {
						b = 2;
					}
					let p = [history.first()[0].wrapping_add(r), history.first()[1].wrapping_add(g), history.first()[2].wrapping_add(b), history.first()[3]];
					history.push(p);
					writer.output(p);
				},
				LUMA2..=255 => {
					let dg = tag - LUMA2;
					let byte = byte()?;
					let dr = byte >> 4;
					let db = byte & 15;
					let g = dg.wrapping_sub(LUMA2_BIAS);
					let bias = if g > 127 { 7 } else { 8 };
					let r = dr.wrapping_add(g).wrapping_sub(bias);
					let b = db.wrapping_add(g).wrapping_sub(bias);
					let p = [history.first()[0].wrapping_add(r), history.first()[1].wrapping_add(g), history.first()[2].wrapping_add(b), history.first()[3]];
					history.push(p);
					writer.output(p);
				},
			}
		}
		
		writer.finish()
	}
}