From 173e0a14b8a47a67122f39ebc5ff5e93eb06d311 Mon Sep 17 00:00:00 2001
From: Kostya Shishkov <kostya.shishkov@gmail.com>
Date: Thu, 16 Apr 2026 21:09:53 +0200
Subject: [PATCH] palettise: introduce simple cache for faster palettisation

---
 src/palettise.rs | 47 ++++++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 44 insertions(+), 3 deletions(-)

diff --git a/src/palettise.rs b/src/palettise.rs
index ead1b4e..bcf1252 100644
--- a/src/palettise.rs
+++ b/src/palettise.rs
@@ -206,6 +206,31 @@ pub struct Palettiser {
     pmode:  PMode,
 }
 
+#[derive(Default)]
+struct LookupCache {
+    items:  [(u8, [u8; 3]); 32],
+    fill:   usize,
+}
+
+impl LookupCache {
+    fn lookup(&mut self, clr: [u8; 3]) -> Option<u8> {
+        for (idx, key) in self.items.iter().enumerate() {
+            if key.1 == clr {
+                let ret = key.0;
+                self.items.swap(0, idx);
+                return Some(ret);
+            }
+        }
+        None
+    }
+    fn add(&mut self, clr: [u8; 3], idx: u8) {
+        self.items[self.fill] = (idx, clr);
+        if self.fill < self.items.len() - 1 {
+            self.fill += 1;
+        }
+    }
+}
+
 #[allow(dead_code)]
 impl Palettiser {
     pub fn new(mode: PaletteSearchMode, pal: &[[u8; 3]; 256]) -> Self {
@@ -250,6 +275,7 @@ impl Palettiser {
             if !ifmt.is_unpacked() {
                 let esize = ifmt.elem_size as usize;
                 let coffs = [ifmt.comp_info[0].unwrap().comp_offs as usize, ifmt.comp_info[1].unwrap().comp_offs as usize, ifmt.comp_info[2].unwrap().comp_offs as usize];
+                let mut cache = LookupCache::default();
                 match &self.pmode {
                     PMode::Full => {
                         for (src, dline) in sdata.chunks(istride)
@@ -257,7 +283,12 @@ impl Palettiser {
                             for (pix, chunk) in dline.iter_mut()
                                     .zip(src.chunks_exact(esize)).take(w) {
                                 let spixel = [chunk[coffs[0]], chunk[coffs[1]], chunk[coffs[2]]];
-                                *pix = find_nearest(&spixel, &self.pal) as u8;
+                                if let Some(idx) = cache.lookup(spixel) {
+                                    *pix = idx;
+                                } else {
+                                    *pix = find_nearest(&spixel, &self.pal) as u8;
+                                    cache.add(spixel, *pix);
+                                }
                             }
                         }
                     },
@@ -267,7 +298,12 @@ impl Palettiser {
                             for (pix, chunk) in dline.iter_mut()
                                     .zip(src.chunks_exact(esize)).take(w) {
                                 let spixel = [chunk[coffs[0]], chunk[coffs[1]], chunk[coffs[2]]];
-                                *pix = ls.search(spixel) as u8;
+                                if let Some(idx) = cache.lookup(spixel) {
+                                    *pix = idx;
+                                } else {
+                                    *pix = ls.search(spixel) as u8;
+                                    cache.add(spixel, *pix);
+                                }
                             }
                         }
                     },
@@ -277,7 +313,12 @@ impl Palettiser {
                             for (pix, chunk) in dline.iter_mut()
                                     .zip(src.chunks_exact(esize)).take(w) {
                                 let spixel = [chunk[coffs[0]], chunk[coffs[1]], chunk[coffs[2]]];
-                                *pix = kdt.search(spixel) as u8;
+                                if let Some(idx) = cache.lookup(spixel) {
+                                    *pix = idx;
+                                } else {
+                                    *pix = kdt.search(spixel) as u8;
+                                    cache.add(spixel, *pix);
+                                }
                             }
                         }
                     },
-- 
2.39.5