gif.rs

1use crate::board::Board;2use crate::ink;3use crate::out;4use mrlycore::errors::{value_error, MrlyError, Result};5use mrlycore::Color;6use std::collections::HashMap;7use std::path::PathBuf;89// REEL1011/// A strip of frames over one palette, printed as a gif that loops forever.12pub struct Reel {13    /// The width in pixels.14    pub width: usize,15    /// The height in pixels.16    pub height: usize,17    /// The colors every frame indexes, at most 256.18    pub palette: Vec<Color>,19    /// The frames, each the palette index of every pixel and a delay in centiseconds.20    pub frames: Vec<(Vec<u8>, u16)>,21}2223impl Reel {24    /// Opens an empty reel of the given size.25    pub fn new(width: usize, height: usize) -> Reel {26        Reel {27            width,28            height,29            palette: Vec::new(),30            frames: Vec::new(),31        }32    }33    /// Indexes the board exactly against the palette, growing it, and holds it for a delay in centiseconds.34    pub fn add(&mut self, board: &Board, delay: u16) -> Result<()> {35        if board.width != self.width || board.height != self.height {36            return value_error(format!(37                "a {}x{} board does not fit a {}x{} reel.",38                board.width, board.height, self.width, self.height39            ));40        }41        let mut palette = self.palette.clone();42        let mut seen: HashMap<[u8; 3], u8> = palette43            .iter()44            .enumerate()45            .map(|(id, color)| ([color.r, color.g, color.b], id as u8))46            .collect();47        let mut indices = Vec::with_capacity(board.pixels.len());48        for pixel in &board.pixels {49            let rgb = [pixel[0], pixel[1], pixel[2]];50            let id = match seen.get(&rgb) {51                Some(&id) => id,52                None => {53                    if palette.len() == 256 {54                        return value_error("a reel holds at most 256 colors.");55                    }56                    let id = palette.len() as u8;57                    palette.push(Color::rgb(rgb[0], rgb[1], rgb[2]));58                    seen.insert(rgb, id);59                    id60                }61            };62            indices.push(id);63        }64        self.palette = palette;65        self.frames.push((indices, delay));66        Ok(())67    }68    /// Encodes the reel as a gif89a: one global color table, one graphic control per frame, looping forever.69    pub fn bytes(&self) -> Result<Vec<u8>> {70        let (width, height) = match (u16::try_from(self.width), u16::try_from(self.height)) {71            (Ok(width), Ok(height)) => (width, height),72            _ => return value_error("a reel is at most 65535 by 65535 pixels."),73        };74        if self.palette.len() > 256 {75            return value_error("a reel holds at most 256 colors.");76        }77        let slots = self.palette.len().max(2).next_power_of_two();78        let bits = slots.trailing_zeros();79        let mut out = Vec::new();80        out.extend_from_slice(b"GIF89a");81        out.extend_from_slice(&width.to_le_bytes());82        out.extend_from_slice(&height.to_le_bytes());83        out.extend_from_slice(&[0xF0 | (bits as u8 - 1), 0x00, 0x00]);84        for slot in 0..slots {85            let color = self86                .palette87                .get(slot)88                .copied()89                .unwrap_or(Color::rgb(0, 0, 0));90            out.extend_from_slice(&[color.r, color.g, color.b]);91        }92        out.extend_from_slice(&[0x21, 0xFF, 0x0B]);93        out.extend_from_slice(b"NETSCAPE2.0");94        out.extend_from_slice(&[0x03, 0x01, 0x00, 0x00, 0x00]);95        for (indices, delay) in &self.frames {96            out.extend_from_slice(&[0x21, 0xF9, 0x04, 0x00]);97            out.extend_from_slice(&delay.to_le_bytes());98            out.extend_from_slice(&[0x00, 0x00]);99            out.extend_from_slice(&[0x2C, 0x00, 0x00, 0x00, 0x00]);100            out.extend_from_slice(&width.to_le_bytes());101            out.extend_from_slice(&height.to_le_bytes());102            out.push(0x00);103            let min = bits.max(2);104            out.push(min as u8);105            for block in lzw(indices, min).chunks(255) {106                out.push(block.len() as u8);107                out.extend_from_slice(block);108            }109            out.push(0x00);110        }111        out.push(0x3B);112        Ok(out)113    }114    /// Writes the reel to files/figures/<name>-<theme>.gif and announces the one line it printed.115    pub fn save(&self, name: &str) -> Result<PathBuf> {116        let name = format!("{name}-{}", ink::name());117        let folder = out::root().join("files").join("figures");118        std::fs::create_dir_all(&folder)119            .map_err(|e| MrlyError::Value(format!("cannot make {folder:?}: {e}")))?;120        let path = folder.join(format!("{name}.gif"));121        let bytes = self.bytes()?;122        std::fs::write(&path, bytes)123            .map_err(|e| MrlyError::Value(format!("cannot write {path:?}: {e}")))?;124        println!(125            "reel {name} {}x{} {} frames",126            self.width,127            self.height,128            self.frames.len()129        );130        Ok(path)131    }132}133134// LZW135136struct Stream {137    out: Vec<u8>,138    acc: u32,139    used: u32,140    width: u32,141}142143impl Stream {144    fn emit(&mut self, code: u16, next: u16) {145        self.acc |= (code as u32) << self.used;146        self.used += self.width;147        while self.used >= 8 {148            self.out.push((self.acc & 0xFF) as u8);149            self.acc >>= 8;150            self.used -= 8;151        }152        if u32::from(next) >= 1 << self.width && self.width < 12 {153            self.width += 1;154        }155    }156    fn flush(&mut self) {157        if self.used > 0 {158            self.out.push((self.acc & 0xFF) as u8);159        }160    }161}162163fn lzw(indices: &[u8], min: u32) -> Vec<u8> {164    let clear = 1u16 << min;165    let end = clear + 1;166    let mut stream = Stream {167        out: Vec::new(),168        acc: 0,169        used: 0,170        width: min + 1,171    };172    let mut table: HashMap<(u16, u8), u16> = HashMap::new();173    let mut next = clear + 2;174    stream.emit(clear, next);175    let mut prefix = match indices.first() {176        Some(&first) => u16::from(first),177        None => {178            stream.emit(end, next);179            stream.flush();180            return stream.out;181        }182    };183    for &index in &indices[1..] {184        if let Some(&code) = table.get(&(prefix, index)) {185            prefix = code;186            continue;187        }188        stream.emit(prefix, next);189        if next < 4096 {190            table.insert((prefix, index), next);191            next += 1;192        } else {193            stream.emit(clear, next);194            table.clear();195            next = clear + 2;196            stream.width = min + 1;197        }198        prefix = u16::from(index);199    }200    stream.emit(prefix, next);201    stream.emit(end, next);202    stream.flush();203    stream.out204}205206#[cfg(test)]207mod tests {208    use super::*;209210    fn painted(pattern: &[u8], colors: &[Color]) -> Board {211        let mut board = Board::new(4, 4, colors[0]);212        for (at, &id) in pattern.iter().enumerate() {213            let color = colors[id as usize];214            board.pixels[at] = [color.r, color.g, color.b, color.a];215        }216        board217    }218219    struct Reader<'a> {220        bytes: &'a [u8],221        at: usize,222    }223224    impl Reader<'_> {225        fn byte(&mut self) -> u8 {226            self.at += 1;227            self.bytes[self.at - 1]228        }229        fn word(&mut self) -> u16 {230            u16::from_le_bytes([self.byte(), self.byte()])231        }232        fn blocks(&mut self) -> Vec<u8> {233            let mut out = Vec::new();234            loop {235                let len = self.byte() as usize;236                if len == 0 {237                    return out;238                }239                out.extend_from_slice(&self.bytes[self.at..self.at + len]);240                self.at += len;241            }242        }243    }244245    fn inflate(data: &[u8], min: u32) -> Vec<u8> {246        let clear = 1usize << min;247        let roots = || {248            (0..clear + 2)249                .map(|id| vec![id as u8])250                .collect::<Vec<Vec<u8>>>()251        };252        let mut table = roots();253        let mut width = min + 1;254        let mut at = 0usize;255        let mut prev: Option<Vec<u8>> = None;256        let mut out = Vec::new();257        while at + width as usize <= data.len() * 8 {258            let mut code = 0usize;259            for bit in 0..width as usize {260                let pos = at + bit;261                code |= usize::from((data[pos / 8] >> (pos % 8)) & 1) << bit;262            }263            at += width as usize;264            if code == clear {265                table = roots();266                width = min + 1;267                prev = None;268                continue;269            }270            if code == clear + 1 {271                break;272            }273            let entry = match table.get(code) {274                Some(entry) => entry.clone(),275                None => {276                    let mut grown = prev.clone().unwrap();277                    grown.push(grown[0]);278                    grown279                }280            };281            out.extend_from_slice(&entry);282            if let Some(mut grown) = prev {283                grown.push(entry[0]);284                table.push(grown);285                if table.len() == 1 << width && width < 12 {286                    width += 1;287                }288            }289            prev = Some(entry);290        }291        out292    }293294    fn decode(bytes: &[u8]) -> (Vec<Color>, Vec<(Vec<u8>, u16)>) {295        assert_eq!(&bytes[0..6], b"GIF89a");296        let mut read = Reader { bytes, at: 6 };297        let size = (read.word(), read.word());298        let packed = read.byte();299        read.byte();300        read.byte();301        let mut palette = Vec::new();302        for _ in 0..(2usize << (packed & 7)) {303            palette.push(Color::rgb(read.byte(), read.byte(), read.byte()));304        }305        let mut frames = Vec::new();306        let mut delay = 0u16;307        loop {308            match read.byte() {309                0x21 => {310                    let label = read.byte();311                    let data = read.blocks();312                    if label == 0xF9 {313                        delay = u16::from_le_bytes([data[1], data[2]]);314                    }315                }316                0x2C => {317                    assert_eq!((read.word(), read.word()), (0, 0));318                    assert_eq!((read.word(), read.word()), size);319                    assert_eq!(read.byte(), 0x00);320                    let min = u32::from(read.byte());321                    let indices = inflate(&read.blocks(), min);322                    assert_eq!(indices.len(), size.0 as usize * size.1 as usize);323                    frames.push((indices, delay));324                }325                0x3B => return (palette, frames),326                other => panic!("stray block {other:#x}"),327            }328        }329    }330331    #[test]332    fn one_frame_encodes_to_the_bytes_of_the_spec() {333        let mut board = Board::new(3, 2, Color::rgb(255, 0, 0));334        board.pixels[2] = [0, 0, 255, 255];335        board.pixels[3] = [0, 0, 255, 255];336        let mut reel = Reel::new(3, 2);337        reel.add(&board, 7).unwrap();338        let mut want = Vec::new();339        want.extend_from_slice(b"GIF89a");340        want.extend_from_slice(&[0x03, 0x00, 0x02, 0x00, 0xF0, 0x00, 0x00]);341        want.extend_from_slice(&[0xFF, 0x00, 0x00, 0x00, 0x00, 0xFF]);342        want.extend_from_slice(&[0x21, 0xFF, 0x0B]);343        want.extend_from_slice(b"NETSCAPE2.0");344        want.extend_from_slice(&[0x03, 0x01, 0x00, 0x00, 0x00]);345        want.extend_from_slice(&[0x21, 0xF9, 0x04, 0x00, 0x07, 0x00, 0x00, 0x00]);346        want.extend_from_slice(&[0x2C, 0x00, 0x00, 0x00, 0x00, 0x03, 0x00, 0x02, 0x00, 0x00]);347        want.extend_from_slice(&[0x02, 0x03, 0x04, 0x12, 0x56, 0x00]);348        want.push(0x3B);349        assert_eq!(reel.bytes().unwrap(), want);350    }351352    #[test]353    fn a_two_frame_reel_round_trips_through_a_decoder() {354        let colors = [355            Color::rgb(9, 9, 9),356            Color::rgb(200, 30, 40),357            Color::rgb(0, 80, 255),358        ];359        let first: Vec<u8> = (0..16u8).map(|at| at % 3).collect();360        let second: Vec<u8> = (0..16u8).map(|at| (at / 2) % 3).collect();361        let mut reel = Reel::new(4, 4);362        reel.add(&painted(&first, &colors), 4).unwrap();363        reel.add(&painted(&second, &colors), 11).unwrap();364        let (palette, frames) = decode(&reel.bytes().unwrap());365        assert_eq!(&palette[..3], &colors[..]);366        assert_eq!(frames, vec![(first, 4), (second, 11)]);367    }368369    #[test]370    fn the_palette_refuses_a_two_hundred_and_fifty_seventh_color() {371        let mut board = Board::new(257, 1, Color::rgb(0, 0, 0));372        for at in 0..257 {373            board.pixels[at] = [(at / 256) as u8, (at % 256) as u8, 0, 255];374        }375        let mut reel = Reel::new(257, 1);376        assert!(reel.add(&board, 1).is_err());377        assert!(reel.palette.is_empty());378    }379}