From 593ff8fae201dce348c7f2dfdf5405b84507364f Mon Sep 17 00:00:00 2001 From: Devon Sawatsky Date: Sat, 21 Oct 2023 22:11:35 -0700 Subject: fix clippy lints in gifed --- Cargo.toml | 1 + gifed/src/block/indexedimage.rs | 6 +++--- gifed/src/block/packed.rs | 2 ++ gifed/src/block/palette.rs | 16 +++++++++++++--- gifed/src/color.rs | 6 +++--- gifed/src/gif.rs | 18 ++++++++---------- gifed/src/lzw.rs | 10 +++++----- gifed/src/reader/mod.rs | 11 ++++------- 8 files changed, 39 insertions(+), 31 deletions(-) diff --git a/Cargo.toml b/Cargo.toml index 948388b..c3f707d 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -1,2 +1,3 @@ [workspace] members = ["gifed", "gifprobe", "gaudio", "gifcheck"] +resolver = "2" diff --git a/gifed/src/block/indexedimage.rs b/gifed/src/block/indexedimage.rs index 1868382..03c2119 100644 --- a/gifed/src/block/indexedimage.rs +++ b/gifed/src/block/indexedimage.rs @@ -17,7 +17,7 @@ impl IndexedImage { } pub fn top(&self) -> u16 { - self.image_descriptor.left + self.image_descriptor.top } pub fn width(&self) -> u16 { @@ -86,7 +86,7 @@ impl CompressedImage { } pub fn top(&self) -> u16 { - self.image_descriptor.left + self.image_descriptor.top } pub fn width(&self) -> u16 { @@ -126,7 +126,7 @@ impl CompressedImage { blocks, } = self; - let data: Vec = blocks.into_iter().map(<_>::into_iter).flatten().collect(); + let data: Vec = blocks.into_iter().flat_map(<_>::into_iter).collect(); //TODO: remove unwrap let mut decompressor = weezl::decode::Decoder::new(weezl::BitOrder::Msb, lzw_code_size); diff --git a/gifed/src/block/packed.rs b/gifed/src/block/packed.rs index 455f43a..0752e39 100644 --- a/gifed/src/block/packed.rs +++ b/gifed/src/block/packed.rs @@ -1,3 +1,5 @@ +#![allow(clippy::unusual_byte_groupings)] + #[derive(Clone, Copy, Debug, PartialEq)] pub struct GraphicPacked { pub raw: u8, diff --git a/gifed/src/block/palette.rs b/gifed/src/block/palette.rs index d5cc696..534cfeb 100644 --- a/gifed/src/block/palette.rs +++ b/gifed/src/block/palette.rs @@ -35,6 +35,10 @@ impl Palette { self.table.len() } + pub fn is_empty(&self) -> bool { + self.len() > 0 + } + /// Returns the number of items that the decoder *thinks* is in the palette. /// This is 2^(n + 1) where n = [Palette::packed_len] pub fn computed_len(&self) -> usize { @@ -47,7 +51,7 @@ impl Palette { } pub fn get(&self, index: u8) -> Option { - self.table.get(index as usize).map(|v| v.clone()) + self.table.get(index as usize).copied() } pub fn from_color>(&self, color: C) -> Option { @@ -64,7 +68,7 @@ impl Palette { //TODO: gen- better docs pub fn padding(&self) -> usize { let comp = self.computed_len(); - (comp as usize - self.len()) * 3 + (comp - self.len()) * 3 } pub fn as_bytes(&self) -> Vec { @@ -77,6 +81,12 @@ impl Palette { } } +impl Default for Palette { + fn default() -> Self { + Self::new() + } +} + impl Deref for Palette { type Target = [Color]; @@ -97,7 +107,7 @@ impl TryFrom<&[u8]> for Palette { fn try_from(value: &[u8]) -> Result { if value.len() % 3 != 0 { - return Err(()); + Err(()) } else { Ok(Self { table: value diff --git a/gifed/src/color.rs b/gifed/src/color.rs index e1b727a..9f2bbe5 100644 --- a/gifed/src/color.rs +++ b/gifed/src/color.rs @@ -37,8 +37,8 @@ impl From<(u8, u8, u8)> for Color { } } -impl Into<[u8; 3]> for Color { - fn into(self) -> [u8; 3] { - [self.r, self.g, self.b] +impl From for [u8; 3] { + fn from(val: Color) -> Self { + [val.r, val.g, val.b] } } diff --git a/gifed/src/gif.rs b/gifed/src/gif.rs index 09b052e..1c71d13 100644 --- a/gifed/src/gif.rs +++ b/gifed/src/gif.rs @@ -23,7 +23,7 @@ impl Gif { pub fn as_bytes(&self) -> Vec { let mut out = vec![]; - out.extend_from_slice(&self.header.as_bytes()); + out.extend_from_slice(self.header.as_bytes()); out.extend_from_slice(&self.screen_descriptor.as_bytes()); if let Some(gct) = &self.global_color_table { @@ -44,7 +44,7 @@ impl Gif { File::create(path.as_ref())?.write_all(&self.as_bytes()) } - pub fn images<'a>(&'a self) -> ImageIterator<'a> { + pub fn images(&self) -> ImageIterator<'_> { ImageIterator { gif: self, block_index: 0, @@ -65,15 +65,14 @@ impl<'a> Iterator for ImageIterator<'a> { let img = loop { match self.gif.blocks.get(self.block_index) { - Some(block) => match block { - Block::CompressedImage(img) => { + Some(block) => { + if let Block::CompressedImage(img) = block { // Step over this image so we don't hit it next time self.block_index += 1; break img; } - _ => (), - }, + } None => return None, } @@ -81,7 +80,7 @@ impl<'a> Iterator for ImageIterator<'a> { }; Some(Image { - compressed: &img, + compressed: img, global_palette: self.gif.global_color_table.as_ref(), blocks: &self.gif.blocks[starting_block..self.block_index], }) @@ -123,8 +122,7 @@ impl<'a> Image<'a> { pub fn transparent_index(&self) -> Option { self.graphic_control() - .map(|gce| gce.transparent_index()) - .flatten() + .and_then(|gce| gce.transparent_index()) } pub fn frame_control(&self) -> Option { @@ -193,7 +191,7 @@ pub enum FrameControl { } #[cfg(test)] -pub mod gif { +pub mod gif_test { use std::convert::TryInto; use std::io::Write; diff --git a/gifed/src/lzw.rs b/gifed/src/lzw.rs index 9fdfcdd..c5ad5b3 100644 --- a/gifed/src/lzw.rs +++ b/gifed/src/lzw.rs @@ -18,7 +18,7 @@ impl LZW { let mut next_code = eoi + 1; let mut code_size = minimum_size + 1; - let mut iter = indicies.into_iter(); + let mut iter = indicies.iter(); let mut out = BitStream::new(); let mut buffer = vec![*iter.next().unwrap()]; @@ -54,7 +54,7 @@ impl LZW { } } - if buffer.len() > 0 { + if !buffer.is_empty() { match dictionary.get(&buffer) { Some(&code) => out.push_bits(code_size, code), None => { @@ -116,7 +116,7 @@ impl BitStream { loop { if new_index >= 8 { self.formed.push(current32 as u8); - current32 = current32 >> 8; + current32 >>= 8; new_index -= 8; } else { self.current = current32 as u8; @@ -155,7 +155,7 @@ mod bitstream_test { for byte in &bsvec { print!("{:b} ", byte); } - println!(""); + println!(); assert_eq!(bsvec, vec![0b1001_1111, 0b0000_0001]); } @@ -171,7 +171,7 @@ mod bitstream_test { for byte in &bsvec { print!("{:b} ", byte); } - println!(""); + println!(); assert_eq!(bsvec, vec![0b0000_0011, 0b0001_0000]); } diff --git a/gifed/src/reader/mod.rs b/gifed/src/reader/mod.rs index aed2142..763f34e 100644 --- a/gifed/src/reader/mod.rs +++ b/gifed/src/reader/mod.rs @@ -22,7 +22,7 @@ pub struct Decoder { impl Decoder> { pub fn file>(path: P) -> Result { - let file = File::open(path).map_err(|e| DecodeError::IoError(e))?; + let file = File::open(path).map_err(DecodeError::IoError)?; let buffreader = BufReader::new(file); Ok(Decoder::new(buffreader)) } @@ -61,11 +61,8 @@ impl Decoder { let mut decoder = self.read()?; let mut blocks = vec![]; - loop { - match decoder.block()? { - Some(block) => blocks.push(block.block), - None => break, - } + while let Some(block) = decoder.block()? { + blocks.push(block.block) } Ok(Gif { @@ -283,7 +280,7 @@ impl SmartReader { } pub fn read_palette(&mut self, count: usize) -> Result { - let mut buf = vec![0; count as usize * 3]; + let mut buf = vec![0; count * 3]; self.read_exact(&mut buf)?; Ok(Palette::try_from(buf.as_slice()).unwrap()) -- cgit 1.4.1-3-g733a5 From 8eb97b076f4fb22e7420708d32e11cf03fa4f2e6 Mon Sep 17 00:00:00 2001 From: Devon Sawatsky Date: Sat, 21 Oct 2023 22:12:35 -0700 Subject: fix clippy lints in gifprobe --- gifprobe/src/main.rs | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/gifprobe/src/main.rs b/gifprobe/src/main.rs index 64cee94..fd6b189 100644 --- a/gifprobe/src/main.rs +++ b/gifprobe/src/main.rs @@ -10,7 +10,7 @@ use gifed::{ use owo_colors::OwoColorize; fn main() { - let file = if let Some(file) = std::env::args().skip(1).next() { + let file = if let Some(file) = std::env::args().nth(1) { file } else { println!("usage: gifprobe file.gif"); @@ -49,7 +49,7 @@ fn main() { ); if colors { - for (idx, clr) in plt.into_iter().enumerate() { + for (idx, clr) in plt.iter().enumerate() { println!( "\t{} {}, {}, {}", idx.color(owo_colors::Rgb(clr.r, clr.g, clr.b)), @@ -217,7 +217,7 @@ fn describe_image(bli: CompressedImage, offset: Range, expand: bool, colo ); if colors { - for (idx, clr) in plt.into_iter().enumerate() { + for (idx, clr) in plt.iter().enumerate() { println!("\t{idx} {}, {}, {}", clr.r, clr.g, clr.b); } } -- cgit 1.4.1-3-g733a5 From 703c10b9a1803a3416c24be3ecf415193cc361e7 Mon Sep 17 00:00:00 2001 From: Devon Sawatsky Date: Sat, 21 Oct 2023 22:37:37 -0700 Subject: replace using pow to compute 2^n with left shift --- gifed/src/block/palette.rs | 2 +- gifed/src/lib.rs | 2 +- 2 files changed, 2 insertions(+), 2 deletions(-) diff --git a/gifed/src/block/palette.rs b/gifed/src/block/palette.rs index 534cfeb..9c4a5a9 100644 --- a/gifed/src/block/palette.rs +++ b/gifed/src/block/palette.rs @@ -42,7 +42,7 @@ impl Palette { /// Returns the number of items that the decoder *thinks* is in the palette. /// This is 2^(n + 1) where n = [Palette::packed_len] pub fn computed_len(&self) -> usize { - 2usize.pow(self.packed_len() as u32 + 1) + 1 << (self.packed_len() + 1) } /// Pushes a color on to the end of the table diff --git a/gifed/src/lib.rs b/gifed/src/lib.rs index 966b46c..cfb124f 100644 --- a/gifed/src/lib.rs +++ b/gifed/src/lib.rs @@ -16,7 +16,7 @@ pub use lzw::LZW; /// Perform the algorithm to get the length of a color table from /// the value of the packed field. The max value here is 256 pub(crate) fn packed_to_color_table_length(packed: u8) -> usize { - 2usize.pow(packed as u32 + 1) + 1 << (packed + 1) } //TODO: Be sure to check that fields in LSD and Img. Desc. that were reserved -- cgit 1.4.1-3-g733a5 From ea2a68e2772b6e1a562db644bc665787e5011267 Mon Sep 17 00:00:00 2001 From: Devon Sawatsky Date: Sat, 21 Oct 2023 22:38:05 -0700 Subject: add some bigger tests to check lzw encoding --- gifed/Cargo.toml | 3 +++ gifed/src/lzw.rs | 42 ++++++++++++++++++++++++++++++++++-------- 2 files changed, 37 insertions(+), 8 deletions(-) diff --git a/gifed/Cargo.toml b/gifed/Cargo.toml index 79f86ce..48b4bf5 100644 --- a/gifed/Cargo.toml +++ b/gifed/Cargo.toml @@ -9,3 +9,6 @@ repository = "https://github.com/genuinebyte/gifed" [dependencies] weezl = "0.1.5" + +[dev-dependencies] +rand = "0.8.5" diff --git a/gifed/src/lzw.rs b/gifed/src/lzw.rs index c5ad5b3..cd3fcd5 100644 --- a/gifed/src/lzw.rs +++ b/gifed/src/lzw.rs @@ -5,7 +5,7 @@ impl LZW { pub fn encode(minimum_size: u8, indicies: &[u8]) -> Vec { let mut dictionary: HashMap, u16> = HashMap::new(); - let cc = 2u16.pow(minimum_size as u32); + let cc = 1 << minimum_size; let eoi = cc + 1; println!("mcs {} | cc {}", minimum_size, cc); @@ -39,7 +39,7 @@ impl LZW { next_code += 1; // If the next_code can't fit in the code_size, we have to increase it - if next_code - 1 == 2u16.pow(code_size as u32) { + if next_code - 1 == 1 << code_size { code_size += 1; } @@ -58,7 +58,9 @@ impl LZW { match dictionary.get(&buffer) { Some(&code) => out.push_bits(code_size, code), None => { - panic!("Codes left in the buffer but the buffer is not a valid dictionary key!") + unreachable!( + "Codes left in the buffer but the buffer is not a valid dictionary key!" + ) } } } @@ -72,23 +74,47 @@ impl LZW { mod lzw_test { use super::*; + fn rand_against_weezl(length: usize) { + let range = rand::distributions::Uniform::from(0..=1); + let indices = rand::Rng::sample_iter(rand::thread_rng(), &range) + .take(length) + .collect::>(); + let weezl = weezl::encode::Encoder::new(weezl::BitOrder::Lsb, 2) + .encode(&indices) + .unwrap(); + let us = LZW::encode(2, &indices); + + assert_eq!(us.len(), weezl.len()); + } + + #[test] + fn fortyk_against_weezl() { + rand_against_weezl(40_000); + } + + #[test] + #[ignore] + fn thirtyeightk_against_weezl() { + rand_against_weezl(38_000); + } + #[test] fn encode() { - let indicies = vec![0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0]; + let indices = vec![0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0]; let output = vec![0x84, 0x1D, 0x81, 0x7A, 0x50]; - let lzout = LZW::encode(2, &indicies); + let lzout = LZW::encode(2, &indices); assert_eq!(lzout, output); } #[test] fn against_weezl() { - let indicies = vec![0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0]; + let indices = vec![0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0]; let weezl = weezl::encode::Encoder::new(weezl::BitOrder::Lsb, 2) - .encode(&indicies) + .encode(&indices) .unwrap(); - let us = LZW::encode(2, &indicies); + let us = LZW::encode(2, &indices); assert_eq!(weezl, us); } -- cgit 1.4.1-3-g733a5 From 1097d7d5e930cbdecb3a8360b0083407a79ad2da Mon Sep 17 00:00:00 2001 From: Devon Sawatsky Date: Sat, 21 Oct 2023 23:39:09 -0700 Subject: fix spelling & minor changes --- gifed/src/lzw.rs | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-) diff --git a/gifed/src/lzw.rs b/gifed/src/lzw.rs index cd3fcd5..f787fdd 100644 --- a/gifed/src/lzw.rs +++ b/gifed/src/lzw.rs @@ -2,13 +2,13 @@ use std::collections::HashMap; pub struct LZW {} impl LZW { - pub fn encode(minimum_size: u8, indicies: &[u8]) -> Vec { + pub fn encode(minimum_size: u8, indices: &[u8]) -> Vec { let mut dictionary: HashMap, u16> = HashMap::new(); let cc = 1 << minimum_size; let eoi = cc + 1; - println!("mcs {} | cc {}", minimum_size, cc); + println!("mcs {minimum_size} | cc {cc}"); // Fill dictionary with self-descriptive values for value in 0..cc { @@ -18,14 +18,14 @@ impl LZW { let mut next_code = eoi + 1; let mut code_size = minimum_size + 1; - let mut iter = indicies.iter(); + let mut iter = indices.iter(); let mut out = BitStream::new(); let mut buffer = vec![*iter.next().unwrap()]; out.push_bits(code_size, cc); - for &indicie in iter { - buffer.push(indicie); + for &index in iter { + buffer.push(index); if !dictionary.contains_key(&buffer) { buffer.pop(); -- cgit 1.4.1-3-g733a5 From 686c1f70fc9296bb9272649de4cd5bc31b151e61 Mon Sep 17 00:00:00 2001 From: Devon Sawatsky Date: Sat, 21 Oct 2023 23:39:18 -0700 Subject: add some test --- gifed/src/lzw.rs | 9 +++++++++ 1 file changed, 9 insertions(+) diff --git a/gifed/src/lzw.rs b/gifed/src/lzw.rs index f787fdd..513a060 100644 --- a/gifed/src/lzw.rs +++ b/gifed/src/lzw.rs @@ -88,6 +88,7 @@ mod lzw_test { } #[test] + #[ignore] fn fortyk_against_weezl() { rand_against_weezl(40_000); } @@ -98,6 +99,14 @@ mod lzw_test { rand_against_weezl(38_000); } + #[test] + #[ignore] + fn twentyk_against_weezl_repeated() { + for _ in 0..100 { + rand_against_weezl(20_000) + } + } + #[test] fn encode() { let indices = vec![0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0]; -- cgit 1.4.1-3-g733a5 From 192a75b569b05f755bfa77551a0084f0cd87b604 Mon Sep 17 00:00:00 2001 From: Devon Sawatsky Date: Sat, 21 Oct 2023 23:39:45 -0700 Subject: add suggested comments to push_bits --- gifed/src/lzw.rs | 9 +++++++++ 1 file changed, 9 insertions(+) diff --git a/gifed/src/lzw.rs b/gifed/src/lzw.rs index 513a060..65ebb06 100644 --- a/gifed/src/lzw.rs +++ b/gifed/src/lzw.rs @@ -145,15 +145,24 @@ impl BitStream { } fn push_bits(&mut self, count: u8, data: u16) { + // number of bits that are in self.current after we put in the new data let mut new_index = self.index + count; + // combine self.current an the data we were given. shifts data over by + // the number of bits that are in self.current so we don't collide let mut current32 = (self.current as u32) | ((data as u32) << self.index); + // Take bytes from current32 until we can store the partial in self.current loop { + // Will we have over a byte of data in self.current? if new_index >= 8 { + // Yes. Push the last 8-bits to the output vec self.formed.push(current32 as u8); + // and make sure we remove them from current current32 >>= 8; + // and that we adjust the index to reflect that new_index -= 8; } else { + // No, all data fits in the u8 of self.current. assign and break, we're done. self.current = current32 as u8; self.index = new_index; -- cgit 1.4.1-3-g733a5 From 2628856cf6e1b0d9c2e2ac87d1ae9d3ff716a47f Mon Sep 17 00:00:00 2001 From: Devon Sawatsky Date: Sat, 21 Oct 2023 23:40:44 -0700 Subject: stop pushing and popping the buffer, just get slices --- gifed/src/lzw.rs | 14 +++++--------- 1 file changed, 5 insertions(+), 9 deletions(-) diff --git a/gifed/src/lzw.rs b/gifed/src/lzw.rs index 65ebb06..bbf1d8c 100644 --- a/gifed/src/lzw.rs +++ b/gifed/src/lzw.rs @@ -28,14 +28,11 @@ impl LZW { buffer.push(index); if !dictionary.contains_key(&buffer) { - buffer.pop(); - - if let Some(&code) = dictionary.get(&buffer) { + if let Some(&code) = dictionary.get(&buffer[..buffer.len() - 1]) { out.push_bits(code_size, code); - // Put the code back and add the vec to the dict - buffer.push(indicie); - dictionary.insert(buffer.clone(), next_code); + // add the vec to the dict + dictionary.insert(buffer, next_code); next_code += 1; // If the next_code can't fit in the code_size, we have to increase it @@ -43,10 +40,9 @@ impl LZW { code_size += 1; } - buffer.clear(); - buffer.push(indicie); + buffer = vec![index]; } else { - println!("indicie is: {}", indicie); + println!("index is: {index}"); println!("buffer is: {:?}", buffer); println!("dictionary: {:?}", dictionary); unreachable!() -- cgit 1.4.1-3-g733a5 From 4a6344de4f81fb15c2c33e856ef2a02c40908cd9 Mon Sep 17 00:00:00 2001 From: Devon Sawatsky Date: Sun, 22 Oct 2023 00:10:50 -0700 Subject: convert a optional match into ? --- gifed/src/gif.rs | 16 ++++++---------- 1 file changed, 6 insertions(+), 10 deletions(-) diff --git a/gifed/src/gif.rs b/gifed/src/gif.rs index 1c71d13..90354a1 100644 --- a/gifed/src/gif.rs +++ b/gifed/src/gif.rs @@ -64,16 +64,12 @@ impl<'a> Iterator for ImageIterator<'a> { let starting_block = self.block_index; let img = loop { - match self.gif.blocks.get(self.block_index) { - Some(block) => { - if let Block::CompressedImage(img) = block { - // Step over this image so we don't hit it next time - self.block_index += 1; - - break img; - } - } - None => return None, + let block = self.gif.blocks.get(self.block_index)?; + if let Block::CompressedImage(img) = block { + // Step over this image so we don't hit it next time + self.block_index += 1; + + break img; } self.block_index += 1; -- cgit 1.4.1-3-g733a5 From 22a1bdf44a1f18d91d3dd286eb349e75d762c0f6 Mon Sep 17 00:00:00 2001 From: Devon Sawatsky Date: Sun, 22 Oct 2023 17:13:44 -0700 Subject: add better lzw variable names --- gifed/src/lzw.rs | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) diff --git a/gifed/src/lzw.rs b/gifed/src/lzw.rs index bbf1d8c..53451da 100644 --- a/gifed/src/lzw.rs +++ b/gifed/src/lzw.rs @@ -5,24 +5,24 @@ impl LZW { pub fn encode(minimum_size: u8, indices: &[u8]) -> Vec { let mut dictionary: HashMap, u16> = HashMap::new(); - let cc = 1 << minimum_size; - let eoi = cc + 1; + let clear_code = 1 << minimum_size; + let end_of_information_code = clear_code + 1; - println!("mcs {minimum_size} | cc {cc}"); + println!("mcs {minimum_size} | cc {clear_code}"); // Fill dictionary with self-descriptive values - for value in 0..cc { + for value in 0..clear_code { dictionary.insert(vec![value as u8], value); } - let mut next_code = eoi + 1; + let mut next_code = end_of_information_code + 1; let mut code_size = minimum_size + 1; let mut iter = indices.iter(); let mut out = BitStream::new(); let mut buffer = vec![*iter.next().unwrap()]; - out.push_bits(code_size, cc); + out.push_bits(code_size, clear_code); for &index in iter { buffer.push(index); -- cgit 1.4.1-3-g733a5 From 47f045d305b43fd3dd0938d5eda9fd61be7f6c5f Mon Sep 17 00:00:00 2001 From: Devon Sawatsky Date: Sun, 22 Oct 2023 17:33:50 -0700 Subject: switch bitstream to bitvec based --- gifed/Cargo.toml | 1 + gifed/src/lzw.rs | 48 ++++++++++-------------------------------------- 2 files changed, 11 insertions(+), 38 deletions(-) diff --git a/gifed/Cargo.toml b/gifed/Cargo.toml index 48b4bf5..a27ff7b 100644 --- a/gifed/Cargo.toml +++ b/gifed/Cargo.toml @@ -8,6 +8,7 @@ description = "Gif encoding and decoding with fine control" repository = "https://github.com/genuinebyte/gifed" [dependencies] +bitvec = "1.0.1" weezl = "0.1.5" [dev-dependencies] diff --git a/gifed/src/lzw.rs b/gifed/src/lzw.rs index 53451da..bcf1988 100644 --- a/gifed/src/lzw.rs +++ b/gifed/src/lzw.rs @@ -1,5 +1,7 @@ use std::collections::HashMap; +use bitvec::prelude::*; + pub struct LZW {} impl LZW { pub fn encode(minimum_size: u8, indices: &[u8]) -> Vec { @@ -60,7 +62,7 @@ impl LZW { } } } - out.push_bits(code_size, eoi); + out.push_bits(code_size, end_of_information_code); out.vec() } @@ -126,55 +128,25 @@ mod lzw_test { } struct BitStream { - formed: Vec, - current: u8, - index: u8, + formed: BitVec, } impl BitStream { fn new() -> Self { Self { - formed: vec![], - current: 0, - index: 0, + formed: BitVec::EMPTY, } } fn push_bits(&mut self, count: u8, data: u16) { - // number of bits that are in self.current after we put in the new data - let mut new_index = self.index + count; - // combine self.current an the data we were given. shifts data over by - // the number of bits that are in self.current so we don't collide - let mut current32 = (self.current as u32) | ((data as u32) << self.index); - - // Take bytes from current32 until we can store the partial in self.current - loop { - // Will we have over a byte of data in self.current? - if new_index >= 8 { - // Yes. Push the last 8-bits to the output vec - self.formed.push(current32 as u8); - // and make sure we remove them from current - current32 >>= 8; - // and that we adjust the index to reflect that - new_index -= 8; - } else { - // No, all data fits in the u8 of self.current. assign and break, we're done. - self.current = current32 as u8; - self.index = new_index; - - break; - } + for i in 0..count { + self.formed.push((data & (1 << i)) > 0) } } - fn vec(self) -> Vec { - let mut out = self.formed; - - if self.index != 0 { - out.push(self.current); - } - - out + fn vec(mut self) -> Vec { + self.formed.set_uninitialized(false); + self.formed.into_vec() } } -- cgit 1.4.1-3-g733a5 From ad74e0bf2721ca9086cc3e2ecacfec91c54746f2 Mon Sep 17 00:00:00 2001 From: Devon Sawatsky Date: Sun, 22 Oct 2023 17:59:09 -0700 Subject: prelim work for decoding --- gifed/src/lzw.rs | 69 ++++++++++++++++++++++++++++++++++++++++++++------------ 1 file changed, 55 insertions(+), 14 deletions(-) diff --git a/gifed/src/lzw.rs b/gifed/src/lzw.rs index bcf1988..89b43e5 100644 --- a/gifed/src/lzw.rs +++ b/gifed/src/lzw.rs @@ -2,9 +2,14 @@ use std::collections::HashMap; use bitvec::prelude::*; -pub struct LZW {} +pub struct LZW { + minimum_size: u8, + clear_code: u16, + end_of_information_code: u16, + dictionary: HashMap, u16>, +} impl LZW { - pub fn encode(minimum_size: u8, indices: &[u8]) -> Vec { + pub fn new(minimum_size: u8) -> Self { let mut dictionary: HashMap, u16> = HashMap::new(); let clear_code = 1 << minimum_size; @@ -17,24 +22,50 @@ impl LZW { dictionary.insert(vec![value as u8], value); } - let mut next_code = end_of_information_code + 1; - let mut code_size = minimum_size + 1; + Self { + minimum_size, + clear_code, + end_of_information_code, + dictionary, + } + } + + pub fn reset(&mut self) { + *self = Self::new(self.minimum_size) + } + + pub fn decode(&mut self, encoded: &[u8]) -> Vec { + let mut input = BitStream::new(); + for &byte in encoded { + input.push_bits(8, byte as u16); + } + + let mut out = BitStream::new(); + + todo!(); + + out.vec() + } + + pub fn encode(&mut self, indices: &[u8]) -> Vec { + let mut next_code = self.end_of_information_code + 1; + let mut code_size = self.minimum_size + 1; let mut iter = indices.iter(); let mut out = BitStream::new(); let mut buffer = vec![*iter.next().unwrap()]; - out.push_bits(code_size, clear_code); + out.push_bits(code_size, self.clear_code); for &index in iter { buffer.push(index); - if !dictionary.contains_key(&buffer) { - if let Some(&code) = dictionary.get(&buffer[..buffer.len() - 1]) { + if !self.dictionary.contains_key(&buffer) { + if let Some(&code) = self.dictionary.get(&buffer[..buffer.len() - 1]) { out.push_bits(code_size, code); // add the vec to the dict - dictionary.insert(buffer, next_code); + self.dictionary.insert(buffer, next_code); next_code += 1; // If the next_code can't fit in the code_size, we have to increase it @@ -46,14 +77,14 @@ impl LZW { } else { println!("index is: {index}"); println!("buffer is: {:?}", buffer); - println!("dictionary: {:?}", dictionary); + println!("dictionary: {:?}", self.dictionary); unreachable!() } } } if !buffer.is_empty() { - match dictionary.get(&buffer) { + match self.dictionary.get(&buffer) { Some(&code) => out.push_bits(code_size, code), None => { unreachable!( @@ -62,7 +93,7 @@ impl LZW { } } } - out.push_bits(code_size, end_of_information_code); + out.push_bits(code_size, self.end_of_information_code); out.vec() } @@ -80,7 +111,7 @@ mod lzw_test { let weezl = weezl::encode::Encoder::new(weezl::BitOrder::Lsb, 2) .encode(&indices) .unwrap(); - let us = LZW::encode(2, &indices); + let us = LZW::new(2).encode(&indices); assert_eq!(us.len(), weezl.len()); } @@ -110,7 +141,7 @@ mod lzw_test { let indices = vec![0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0]; let output = vec![0x84, 0x1D, 0x81, 0x7A, 0x50]; - let lzout = LZW::encode(2, &indices); + let lzout = LZW::new(2).encode(&indices); assert_eq!(lzout, output); } @@ -121,7 +152,7 @@ mod lzw_test { let weezl = weezl::encode::Encoder::new(weezl::BitOrder::Lsb, 2) .encode(&indices) .unwrap(); - let us = LZW::encode(2, &indices); + let us = LZW::new(2).encode(&indices); assert_eq!(weezl, us); } @@ -144,6 +175,16 @@ impl BitStream { } } + fn pop_bits(&mut self, count: u8) -> u16 { + let mut out = 0; + for i in (0..count).filter_map(|_| self.formed.pop()) { + out <<= 1; + let int: u16 = i.into(); + out |= int; + } + out + } + fn vec(mut self) -> Vec { self.formed.set_uninitialized(false); self.formed.into_vec() -- cgit 1.4.1-3-g733a5