gamut_webp/vp8l/
color_cache.rs

1//! VP8L color cache (RFC 9649 §3.6.3).
2//!
3//! The color cache is a small hash table of recently emitted ARGB colors; a pixel can be coded as a
4//! short index into it instead of a literal or a backward reference. It is a multiplicative hash
5//! with a configurable bit width and **no conflict resolution** — only one slot is checked per
6//! color. Both the decoder and the encoder maintain an identical cache and insert **every** produced
7//! pixel (literal, copied, or cache hit) in stream order, so their states stay in lock-step.
8
9use gamut_core::{Error, Result};
10
11/// The multiplicative hash constant the spec mandates (RFC 9649 §3.6.3).
12const HASH_MULTIPLIER: u32 = 0x1e35_a7bd;
13
14/// Minimum and maximum `color_cache_code_bits` (RFC 9649 §3.6.3).
15const MIN_CACHE_BITS: u32 = 1;
16const MAX_CACHE_BITS: u32 = 11;
17
18/// A VP8L color cache: `2^bits` slots, each holding one ARGB color, all initialized to zero.
19#[derive(Debug, Clone)]
20pub struct ColorCache {
21    /// The hash width (`color_cache_code_bits`, 1..=11).
22    bits: u32,
23    /// The slots, indexed by the high `bits` of the multiplicative hash.
24    entries: Vec<u32>,
25}
26
27impl ColorCache {
28    /// Creates a cache with `bits` (1..=11) hash bits and `2^bits` zeroed slots.
29    ///
30    /// # Errors
31    ///
32    /// Returns [`Error::InvalidInput`] if `bits` is outside `1..=11`.
33    pub fn new(bits: u32) -> Result<Self> {
34        if !(MIN_CACHE_BITS..=MAX_CACHE_BITS).contains(&bits) {
35            return Err(Error::InvalidInput("VP8L: color cache bits out of range"));
36        }
37        Ok(Self {
38            bits,
39            entries: vec![0u32; 1usize << bits],
40        })
41    }
42
43    /// Number of slots (`2^bits`), which is also the size of the color-cache alphabet.
44    #[must_use]
45    pub fn size(&self) -> usize {
46        self.entries.len()
47    }
48
49    /// The hash slot a `color` maps to.
50    #[inline]
51    #[must_use]
52    pub fn slot(&self, color: u32) -> usize {
53        (HASH_MULTIPLIER.wrapping_mul(color) >> (32 - self.bits)) as usize
54    }
55
56    /// Inserts `color`, overwriting whatever shared its slot.
57    pub fn insert(&mut self, color: u32) {
58        let slot = self.slot(color);
59        if let Some(entry) = self.entries.get_mut(slot) {
60            *entry = color;
61        }
62    }
63
64    /// Returns the color stored at `index` (the decoded cache code). Out-of-range indices yield 0,
65    /// but callers bound `index` by [`size`](Self::size) via the green alphabet.
66    #[must_use]
67    pub fn lookup(&self, index: u32) -> u32 {
68        self.entries.get(index as usize).copied().unwrap_or(0)
69    }
70}
71
72#[cfg(test)]
73mod tests {
74    use super::*;
75
76    #[test]
77    fn rejects_out_of_range_bits() {
78        assert!(ColorCache::new(0).is_err());
79        assert!(ColorCache::new(12).is_err());
80        assert!(ColorCache::new(1).is_ok());
81        assert!(ColorCache::new(11).is_ok());
82    }
83
84    #[test]
85    fn size_is_two_to_the_bits() {
86        assert_eq!(ColorCache::new(1).unwrap().size(), 2);
87        assert_eq!(ColorCache::new(10).unwrap().size(), 1024);
88    }
89
90    #[test]
91    fn insert_then_lookup_round_trips_a_color() {
92        let mut cache = ColorCache::new(8).unwrap();
93        let color = 0xdead_beef;
94        let slot = cache.slot(color);
95        assert_eq!(cache.lookup(slot as u32), 0); // empty before insert
96        cache.insert(color);
97        assert_eq!(cache.lookup(slot as u32), color);
98    }
99
100    #[test]
101    fn hash_matches_spec_formula() {
102        let cache = ColorCache::new(6).unwrap();
103        let color = 0x1234_5678;
104        let expected = (HASH_MULTIPLIER.wrapping_mul(color) >> (32 - 6)) as usize;
105        assert_eq!(cache.slot(color), expected);
106        assert!(cache.slot(color) < cache.size());
107    }
108
109    #[test]
110    fn lookup_out_of_range_is_zero() {
111        let cache = ColorCache::new(1).unwrap();
112        assert_eq!(cache.lookup(99), 0);
113    }
114}
gamut_webp/vp8l/color_cache.rs

gamut_webp/vp8l/
color_cache.rs
