a_sixel/
bit.rs

1use std::collections::HashSet;
2
3use dilate::DilateExpand;
4use ordered_float::OrderedFloat;
5use palette::{
6    IntoColor,
7    Lab,
8    Srgb,
9};
10
11use crate::{
12    PaletteBuilder,
13    private,
14};
15
16#[derive(Debug, Clone, Copy)]
17struct Bucket {
18    color: (u64, u64, u64),
19    count: usize,
20}
21
22/// Encodes a palette by bucketing bit ranges into a power of two number of
23/// buckets. This is very fast and produces ok results for most images at larger
24/// palette sizes (e.g. 256).
25#[derive(Debug)]
26pub struct BitPaletteBuilder<const PALETTE_SIZE: usize> {
27    buckets: Vec<Bucket>,
28}
29
30impl<const PALETTE_SIZE: usize> BitPaletteBuilder<PALETTE_SIZE> {
31    const PALETTE_DEPTH: usize = PALETTE_SIZE.ilog2() as usize;
32    const SHIFT: usize = 24 - Self::PALETTE_DEPTH;
33
34    fn new() -> Self {
35        BitPaletteBuilder {
36            buckets: vec![
37                Bucket {
38                    color: (0, 0, 0),
39                    count: 0,
40                };
41                PALETTE_SIZE
42            ],
43        }
44    }
45
46    fn insert(&mut self, color: Srgb<u8>) {
47        let index = {
48            let r = color.red.dilate_expand::<3>().value();
49            let g = color.green.dilate_expand::<3>().value();
50            let b = color.blue.dilate_expand::<3>().value();
51
52            // Since elements to the right will get shifted off first, we put them in grb
53            // order (order of most-least significant for luminance). This probably doesn't
54            // make a huge difference, but the theory is nice.
55            let rgb = g << 2 | r << 1 | b;
56
57            (rgb >> Self::SHIFT) as usize
58        };
59
60        let node = &mut self.buckets[index];
61        node.color.0 += color.red as u64;
62        node.color.1 += color.green as u64;
63        node.color.2 += color.blue as u64;
64        node.count += 1;
65    }
66}
67
68impl<const PALETTE_SIZE: usize> private::Sealed for BitPaletteBuilder<PALETTE_SIZE> {}
69impl<const PALETTE_SIZE: usize> PaletteBuilder for BitPaletteBuilder<PALETTE_SIZE> {
70    const PALETTE_SIZE: usize = PALETTE_SIZE;
71
72    fn build_palette(image: &image::RgbImage) -> Vec<Lab> {
73        let mut builder = Self::new();
74
75        for pixel in image.pixels() {
76            builder.insert(Srgb::<u8>::new(pixel[0], pixel[1], pixel[2]));
77        }
78
79        builder
80            .buckets
81            .into_iter()
82            .filter(|node| node.count > 0)
83            .map(|node| {
84                let rgb = Srgb::new(
85                    (node.color.0 / node.count as u64) as u8,
86                    (node.color.1 / node.count as u64) as u8,
87                    (node.color.2 / node.count as u64) as u8,
88                );
89                let lab: Lab = rgb.into_format().into_color();
90                [
91                    OrderedFloat(lab.l),
92                    OrderedFloat(lab.a),
93                    OrderedFloat(lab.b),
94                ]
95            })
96            .collect::<HashSet<_>>()
97            .into_iter()
98            .map(|[l, a, b]| Lab::new(*l, *a, *b))
99            .collect::<Vec<_>>()
100    }
101}
a_sixel/bit.rs

a_sixel/
bit.rs
