tvision_rs/backend/quantize.rs
1//! RGB colour-quantization ladder (documented in the `backend` module docs).
2
3// ---------------------------------------------------------------------------
4// Hue-Chroma-Lightness helper
5// ---------------------------------------------------------------------------
6
7/// Hue-Chroma-Lightness record used internally by [`rgb_to_xterm16`].
8struct Hcl {
9 h: u8,
10 c: u8,
11 l: u8,
12}
13
14/// Hue units per sector.
15const HUE_PRECISION: u8 = 32;
16/// Full hue circle = 6 sectors.
17const HUE_MAX: u8 = 6 * HUE_PRECISION; // 192
18
19/// Convert an RGB triplet to Hue-Chroma-Lightness.
20///
21/// The hue-angle arithmetic uses `i16` to keep the intermediate products exact
22/// (`HUE_PRECISION * 255 = 8160` fits in `i16`).
23const fn rgb_to_hcl(r: u8, g: u8, b: u8) -> Hcl {
24 // min/max are not available as const fn in std; inline with if/else.
25 let xmin = if r < g {
26 if r < b { r } else { b }
27 } else {
28 if g < b { g } else { b }
29 };
30 let xmax = if r > g {
31 if r > b { r } else { b }
32 } else {
33 if g > b { g } else { b }
34 };
35
36 let v = xmax;
37 // Lightness = (max + min) / 2; u16 intermediate avoids overflow.
38 let l = ((xmax as u16 + xmin as u16) / 2) as u8;
39 let c = xmax - xmin; // safe: xmax >= xmin
40
41 let h: i16 = if c != 0 {
42 // Select the first matching arm (when R==G, V==R wins).
43 let raw: i16 = if v == r {
44 // int16_t(HUE_PRECISION * (G - B)) / C
45 (HUE_PRECISION as i16 * (g as i16 - b as i16)) / c as i16
46 } else if v == g {
47 // int16_t(HUE_PRECISION * (B - R)) / C + 2 * HUE_PRECISION
48 (HUE_PRECISION as i16 * (b as i16 - r as i16)) / c as i16 + 2 * HUE_PRECISION as i16
49 } else {
50 // v == b
51 // int16_t(HUE_PRECISION * (R - G)) / C + 4 * HUE_PRECISION
52 (HUE_PRECISION as i16 * (r as i16 - g as i16)) / c as i16 + 4 * HUE_PRECISION as i16
53 };
54 if raw < 0 {
55 raw + HUE_MAX as i16
56 } else if raw >= HUE_MAX as i16 {
57 raw - HUE_MAX as i16
58 } else {
59 raw
60 }
61 } else {
62 0
63 };
64
65 Hcl { h: h as u8, c, l }
66}
67
68// ---------------------------------------------------------------------------
69// Lightness thresholds: fractions of 255, truncated toward zero.
70// 0.25 → 63 0.5 → 127 0.625 → 159
71// 0.875 → 223 0.925 → 235
72// Baked as integer literals to avoid floating-point in a const fn.
73// ---------------------------------------------------------------------------
74const THRESH_025: u8 = 63;
75const THRESH_050: u8 = 127;
76const THRESH_0625: u8 = 159;
77const THRESH_0875: u8 = 223;
78const THRESH_0925: u8 = 235;
79
80// ---------------------------------------------------------------------------
81// Public API
82// ---------------------------------------------------------------------------
83
84/// Convert an RGB triplet to the nearest xterm-16 / BIOS-style index (0..=15).
85///
86/// Uses the Hue-Chroma-Lightness colour model for perceptually plausible
87/// quantization.
88pub const fn rgb_to_xterm16(r: u8, g: u8, b: u8) -> u8 {
89 let c = rgb_to_hcl(r, g, b);
90 if c.c >= 12 {
91 // Chromatic: pick the hue sector by rounding the hue to the nearest
92 // sector boundary (add half a sector, wrapping to [0, HUE_MAX)).
93 let adjusted_h = if (c.h as u16) < (HUE_MAX as u16 - HUE_PRECISION as u16 / 2) {
94 c.h + HUE_PRECISION / 2
95 } else {
96 // Wraps: subtract so it stays in 0..HUE_MAX. The value is always
97 // < HUE_MAX, so no actual wrap occurs for valid inputs.
98 c.h - (HUE_MAX - HUE_PRECISION / 2)
99 };
100 let index = (adjusted_h / HUE_PRECISION) as usize;
101
102 #[rustfmt::skip]
103 const NORMAL: [u8; 6] = [0x1, 0x3, 0x2, 0x6, 0x4, 0x5];
104 #[rustfmt::skip]
105 const BRIGHT: [u8; 6] = [0x9, 0xB, 0xA, 0xE, 0xC, 0xD];
106
107 if c.l < THRESH_050 {
108 NORMAL[index]
109 } else if c.l < THRESH_0925 {
110 BRIGHT[index]
111 } else {
112 15
113 }
114 } else {
115 // Achromatic: pick by lightness only.
116 if c.l < THRESH_025 {
117 0
118 } else if c.l < THRESH_0625 {
119 8
120 } else if c.l < THRESH_0875 {
121 7
122 } else {
123 15
124 }
125 }
126}
127
128/// Map an RGB triplet to the nearest xterm-256 index **in the range 16..=255**.
129///
130/// The result is never in 0..=15 (the xterm-16 palette). The colour is first
131/// quantized to the 6×6×6 colour cube; if that index does not round-trip back to
132/// the input, the colour is too achromatic and falls back to the 24-step
133/// grayscale ramp.
134pub fn rgb_to_xterm256(r: u8, g: u8, b: u8) -> u8 {
135 // Map a single channel to a cube index 0..=5.
136 let scale = |c: u8| -> u8 {
137 // Dark-compensation: add 20 iff c < 75 (c+20 < 95, no u8 overflow).
138 let c = if c < 75 { c.wrapping_add(20) } else { c };
139 // max(c, 35) - 35, then divide by 40 (truncating).
140 let c = c.saturating_sub(35);
141 c / 40
142 };
143
144 // Pack the three channel indices into a cube index.
145 let ri = scale(r);
146 let gi = scale(g);
147 let bi = scale(b);
148 // 16 + r*36 + g*6 + b, rewritten as (r*6 + g)*6 + b.
149 let idx = 16u8 + (ri * 6 + gi) * 6 + bi;
150
151 // Map a lightness value to the 24-step grayscale ramp.
152 let cnv_gray = |l: u8| -> u8 {
153 if l < 3 {
154 // l < 8-5 → totally black → cube index 16 (= black in the 6x6x6 cube)
155 16
156 } else if l >= 243 {
157 // l >= 238+5 → totally white → cube index 231 (= white)
158 231
159 } else {
160 // 232 + (max(l, 3) - 3) / 10
161 232 + (l - 3) / 10
162 }
163 };
164
165 // If the cube quantization round-trips exactly, use it; otherwise fall back
166 // to grayscale when the colour is achromatic (low chroma or idx==16).
167 let packed = XTERM256_TO_RGB[idx as usize];
168 let (qr, qg, qb) = (
169 ((packed >> 16) & 0xFF) as u8,
170 ((packed >> 8) & 0xFF) as u8,
171 (packed & 0xFF) as u8,
172 );
173 if r == qr && g == qg && b == qb {
174 idx
175 } else {
176 let xmin = r.min(g).min(b);
177 let xmax = r.max(g).max(b);
178 let chroma = xmax - xmin;
179 if chroma < 12 || idx == 16 {
180 let l = ((xmax as u16 + xmin as u16) / 2) as u8;
181 cnv_gray(l)
182 } else {
183 idx
184 }
185 }
186}
187
188/// Swap the red and blue bits of a 4-bit BIOS colour index.
189///
190/// BIOS bit layout: bit0=blue, bit1=green, bit2=red, bit3=bright.
191/// xterm-16 layout: bit0=red, bit1=green, bit2=blue, bit3=bright.
192///
193/// The swap is `(x & 0b1010) | ((x & 1) << 2) | ((x >> 2) & 1)`. It is its own
194/// inverse, so the same operation converts in both directions.
195pub const fn bios_to_xterm16(bios: u8) -> u8 {
196 (bios & 0b1010) | ((bios & 1) << 2) | ((bios >> 2) & 1)
197}
198
199/// Convert an xterm-16 index to a BIOS colour index.
200///
201/// Identical bit-swap as [`bios_to_xterm16`] — the function is its own inverse.
202pub const fn xterm16_to_bios(idx: u8) -> u8 {
203 bios_to_xterm16(idx)
204}
205
206/// Convert an RGB triplet directly to a BIOS colour index (0..=15).
207///
208/// Equivalent to `xterm16_to_bios(rgb_to_xterm16(r, g, b))`.
209pub const fn rgb_to_bios(r: u8, g: u8, b: u8) -> u8 {
210 xterm16_to_bios(rgb_to_xterm16(r, g, b))
211}
212
213/// Look up the nearest xterm-16 index for an xterm-256 index.
214///
215/// For indices 0..=15 the result is the identity (the first 16 xterm-256 entries
216/// *are* the xterm-16 palette).
217pub const fn xterm256_to_xterm16(idx: u8) -> u8 {
218 XTERM256_TO_XTERM16[idx as usize]
219}
220
221/// Look up the RGB value for an xterm-256 index, as `(red, green, blue)`.
222///
223/// Valid for indices 16..=255 (the 6×6×6 cube and 24-step grayscale ramp).
224/// Indices 0..=15 return `(0, 0, 0)` — they are never looked up via this path
225/// (the caller already has the exact RGB from the palette).
226pub const fn xterm256_to_rgb(idx: u8) -> (u8, u8, u8) {
227 let packed = XTERM256_TO_RGB[idx as usize];
228 let r = ((packed >> 16) & 0xFF) as u8;
229 let g = ((packed >> 8) & 0xFF) as u8;
230 let b = (packed & 0xFF) as u8;
231 (r, g, b)
232}
233
234// ---------------------------------------------------------------------------
235// Compile-time LUT builders
236// ---------------------------------------------------------------------------
237
238/// xterm-256 cube channel values for indices 0..=5.
239/// `i=0 → 0`, `i=1..5 → 55 + i*40` (i.e. 0, 95, 135, 175, 215, 255).
240const fn cube_channel(i: u8) -> u8 {
241 if i == 0 { 0 } else { 55 + i * 40 }
242}
243
244/// Build `XTERM256_TO_XTERM16`: for each xterm-256 index, the closest xterm-16
245/// colour.
246///
247/// - Indices 0..=15: identity (those entries *are* the xterm-16 palette).
248/// - Indices 16..=231: 6×6×6 cube — `rgb_to_xterm16(R, G, B)`.
249/// - Indices 232..=255: 24-step grayscale — `rgb_to_xterm16(L, L, L)`.
250const fn build_xterm256_to_xterm16() -> [u8; 256] {
251 let mut table = [0u8; 256];
252
253 // Indices 0..15: identity.
254 let mut i = 0u8;
255 while i < 16 {
256 table[i as usize] = i;
257 i += 1;
258 }
259
260 // Indices 16..231: 6×6×6 cube.
261 let mut ri = 0u8;
262 while ri < 6 {
263 let mut gi = 0u8;
264 while gi < 6 {
265 let mut bi = 0u8;
266 while bi < 6 {
267 let r = cube_channel(ri);
268 let g = cube_channel(gi);
269 let b = cube_channel(bi);
270 let idx = 16 + (ri * 6 + gi) * 6 + bi;
271 table[idx as usize] = rgb_to_xterm16(r, g, b);
272 bi += 1;
273 }
274 gi += 1;
275 }
276 ri += 1;
277 }
278
279 // Indices 232..255: 24-step grayscale ramp. L = i*10 + 8.
280 let mut i = 0u8;
281 while i < 24 {
282 let l = i * 10 + 8;
283 table[(232 + i) as usize] = rgb_to_xterm16(l, l, l);
284 i += 1;
285 }
286
287 table
288}
289
290/// Build `XTERM256_TO_RGB`: for each xterm-256 index, the packed `0xRRGGBB`
291/// value.
292///
293/// - Indices 0..=15: left as 0 (never looked up via [`xterm256_to_rgb`]).
294/// - Indices 16..=231: 6×6×6 cube.
295/// - Indices 232..=255: 24-step grayscale ramp.
296const fn build_xterm256_to_rgb() -> [u32; 256] {
297 let mut table = [0u32; 256];
298
299 // 6×6×6 cube.
300 let mut ri = 0u8;
301 while ri < 6 {
302 let mut gi = 0u8;
303 while gi < 6 {
304 let mut bi = 0u8;
305 while bi < 6 {
306 let r = cube_channel(ri);
307 let g = cube_channel(gi);
308 let b = cube_channel(bi);
309 let idx = 16 + (ri * 6 + gi) * 6 + bi;
310 table[idx as usize] = ((r as u32) << 16) | ((g as u32) << 8) | (b as u32);
311 bi += 1;
312 }
313 gi += 1;
314 }
315 ri += 1;
316 }
317
318 // Grayscale ramp.
319 let mut i = 0u8;
320 while i < 24 {
321 let l = i * 10 + 8;
322 table[(232 + i) as usize] = ((l as u32) << 16) | ((l as u32) << 8) | (l as u32);
323 i += 1;
324 }
325
326 table
327}
328
329/// LUT: xterm-256 index → nearest xterm-16 index.
330///
331/// Built at compile time from [`rgb_to_xterm16`]. Indices 0..=15 map to
332/// themselves; 16..=231 are the 6×6×6 cube; 232..=255 are the grayscale ramp.
333pub const XTERM256_TO_XTERM16: [u8; 256] = build_xterm256_to_xterm16();
334
335/// LUT: xterm-256 index → packed `0xRRGGBB`.
336///
337/// Built at compile time. Indices 0..=15 are 0 (never looked up via
338/// [`xterm256_to_rgb`]). 16..=231 are the 6×6×6 cube; 232..=255 are the 24-step
339/// grayscale ramp.
340pub const XTERM256_TO_RGB: [u32; 256] = build_xterm256_to_rgb();
341
342// ---------------------------------------------------------------------------
343// Tests
344// ---------------------------------------------------------------------------
345
346#[cfg(test)]
347mod tests {
348 use super::*;
349
350 // --- xterm256_to_rgb ---
351
352 #[test]
353 fn xterm256_to_rgb_cube_black() {
354 // Index 16 = (0,0,0) in the 6×6×6 cube.
355 assert_eq!(xterm256_to_rgb(16), (0, 0, 0));
356 }
357
358 #[test]
359 fn xterm256_to_rgb_cube_white() {
360 // Index 231 = (255,255,255) — last entry of the cube.
361 assert_eq!(xterm256_to_rgb(231), (255, 255, 255));
362 }
363
364 #[test]
365 fn xterm256_to_rgb_mid_cube() {
366 // Index 16 + (3*6+3)*6+3 = 16 + 117 = 133.
367 // ri=3 → 175, gi=3 → 175, bi=3 → 175 (all mid-cube).
368 let idx = 16 + (3 * 6 + 3) * 6 + 3;
369 assert_eq!(xterm256_to_rgb(idx), (175, 175, 175));
370 }
371
372 #[test]
373 fn xterm256_to_rgb_grayscale_first() {
374 // Index 232: L = 0*10+8 = 8.
375 assert_eq!(xterm256_to_rgb(232), (8, 8, 8));
376 }
377
378 #[test]
379 fn xterm256_to_rgb_grayscale_last() {
380 // Index 255: L = 23*10+8 = 238.
381 assert_eq!(xterm256_to_rgb(255), (238, 238, 238));
382 }
383
384 // --- cube channel values ---
385
386 #[test]
387 fn cube_channels_are_exactly_correct() {
388 let expected = [0u8, 95, 135, 175, 215, 255];
389 for (i, &expected_val) in expected.iter().enumerate() {
390 assert_eq!(cube_channel(i as u8), expected_val, "cube_channel({i})");
391 }
392 }
393
394 // --- bios/xterm16 bit-swap ---
395
396 #[test]
397 fn bios_xterm16_swap_is_involution() {
398 // bios_to_xterm16 ∘ bios_to_xterm16 == identity for all 4-bit values.
399 for x in 0u8..=15 {
400 assert_eq!(
401 bios_to_xterm16(bios_to_xterm16(x)),
402 x,
403 "involution failed for {x}"
404 );
405 }
406 }
407
408 #[test]
409 fn bios_xterm16_swap_spot_check() {
410 // BIOS red = 0b0100 (bit2=red) ↔ xterm-16 red = 0b0001 (bit0=red).
411 // BIOS blue = 0b0001 (bit0=blue) ↔ xterm-16 blue = 0b0100 (bit2=blue).
412 assert_eq!(bios_to_xterm16(0b0100), 0b0001); // BIOS red → xterm16 red
413 assert_eq!(bios_to_xterm16(0b0001), 0b0100); // BIOS blue → xterm16 blue
414 // Bright bit (bit3) must be preserved.
415 assert_eq!(bios_to_xterm16(0b1100), 0b1001); // bright BIOS red → bright xterm16 red
416 assert_eq!(bios_to_xterm16(0b1001), 0b1100); // bright BIOS blue → bright xterm16 blue
417 // Green (bit1) is unchanged by the swap.
418 assert_eq!(bios_to_xterm16(0b0010), 0b0010);
419 }
420
421 #[test]
422 fn xterm16_to_bios_is_same_as_bios_to_xterm16() {
423 for x in 0u8..=15 {
424 assert_eq!(xterm16_to_bios(x), bios_to_xterm16(x));
425 }
426 }
427
428 // --- rgb_to_xterm16 ---
429
430 #[test]
431 fn rgb_to_xterm16_pure_colors() {
432 // Black and white (achromatic).
433 assert_eq!(rgb_to_xterm16(0, 0, 0), 0); // black
434 assert_eq!(rgb_to_xterm16(255, 255, 255), 15); // bright white
435
436 // Pure red, green, blue.
437 // xterm-16 uses the standard VGA layout: bit0=red, bit1=green, bit2=blue,
438 // bit3=bright. So: bright-red=0x9, bright-green=0xA, bright-blue=0xC.
439 // (Note: xterm-16 != BIOS. The bit-swap only applies to the BIOS variant.)
440 assert_eq!(rgb_to_xterm16(255, 0, 0), 0x9); // bright red (BRIGHT[0])
441 assert_eq!(rgb_to_xterm16(0, 255, 0), 0xA); // bright green (BRIGHT[2])
442 assert_eq!(rgb_to_xterm16(0, 0, 255), 0xC); // bright blue (BRIGHT[4])
443
444 // Mid gray — achromatic, should map to 8 (dark gray) or 7 (light gray).
445 let mid_gray = rgb_to_xterm16(128, 128, 128);
446 assert!(
447 mid_gray == 8 || mid_gray == 7,
448 "mid gray {mid_gray} unexpected"
449 );
450 }
451
452 #[test]
453 fn rgb_to_xterm16_gray_thresholds() {
454 // l < 63 → 0 (black)
455 assert_eq!(rgb_to_xterm16(40, 40, 40), 0);
456 // 63 <= l < 159 → 8 (dark gray)
457 assert_eq!(rgb_to_xterm16(100, 100, 100), 8);
458 // 159 <= l < 223 → 7 (light gray)
459 assert_eq!(rgb_to_xterm16(180, 180, 180), 7);
460 // l >= 223 → 15 (bright white)
461 assert_eq!(rgb_to_xterm16(230, 230, 230), 15);
462 }
463
464 // --- rgb_to_bios ---
465
466 #[test]
467 fn rgb_to_bios_matches_composition() {
468 // rgb_to_bios == xterm16_to_bios(rgb_to_xterm16(...)) for all test colors.
469 let cases = [
470 (0u8, 0u8, 0u8),
471 (255, 0, 0),
472 (0, 255, 0),
473 (0, 0, 255),
474 (255, 255, 255),
475 (128, 128, 128),
476 (200, 100, 50),
477 ];
478 for (r, g, b) in cases {
479 let expected = xterm16_to_bios(rgb_to_xterm16(r, g, b));
480 assert_eq!(rgb_to_bios(r, g, b), expected, "rgb_to_bios({r},{g},{b})");
481 }
482 }
483
484 // --- rgb_to_xterm256 ---
485
486 #[test]
487 fn rgb_to_xterm256_always_ge_16() {
488 // Spot-check several values including edge cases.
489 let cases = [
490 (0u8, 0u8, 0u8),
491 (255, 255, 255),
492 (128, 0, 0),
493 (0, 128, 0),
494 (0, 0, 128),
495 (10, 10, 10), // dark, exercises grayscale fallback
496 (255, 128, 64), // chromatic, stays in cube
497 ];
498 for (r, g, b) in cases {
499 let idx = rgb_to_xterm256(r, g, b);
500 assert!(idx >= 16, "rgb_to_xterm256({r},{g},{b}) = {idx} < 16");
501 }
502 }
503
504 #[test]
505 fn rgb_to_xterm256_dark_compensation() {
506 // A channel value < 75 gets +20 added before scaling — exercise this path.
507 // (50,50,50): all channels < 75, gets +20 → (70,70,70). scale(70): 70>35 → 35; 35/40=0.
508 // So cube index = 16+(0*6+0)*6+0 = 16.
509 // Round-trip: xterm256_to_rgb(16) = (0,0,0) ≠ (50,50,50).
510 // Chroma = 0 < 12 → grayscale: L=50, cnvGray(50) = 232 + (50-3)/10 = 232+4 = 236.
511 let idx = rgb_to_xterm256(50, 50, 50);
512 assert!(idx >= 232, "expected grayscale idx, got {idx}");
513 }
514
515 #[test]
516 fn rgb_to_xterm256_grayscale_fallback_black() {
517 // Pure black: cube gives idx=16, round-trip fails, chroma=0 → cnvGray(0) → 16.
518 let idx = rgb_to_xterm256(0, 0, 0);
519 assert_eq!(idx, 16);
520 }
521
522 #[test]
523 fn rgb_to_xterm256_grayscale_fallback_white() {
524 // Pure white: cube gives idx=231, round-trip succeeds → stays in cube.
525 let idx = rgb_to_xterm256(255, 255, 255);
526 assert_eq!(idx, 231);
527 }
528
529 #[test]
530 fn rgb_to_xterm256_chromatic_stays_in_cube() {
531 // A strongly chromatic color: pure red (255,0,0).
532 // scale(255): 255 >= 75, no compensation; 255-35=220; 220/40=5. ri=5.
533 // scale(0): 0 < 75 → +20=20; max(20,35)=35; 35-35=0; 0/40=0. gi=0, bi=0.
534 // idx = 16 + (5*6+0)*6+0 = 16+180 = 196.
535 // xterm256_to_rgb(196) = (cube_channel(5), cube_channel(0), cube_channel(0)) = (255,0,0).
536 // Round-trip matches → stays at 196.
537 let idx = rgb_to_xterm256(255, 0, 0);
538 assert_eq!(idx, 196);
539 }
540
541 // --- xterm256_to_xterm16 identity for 0..16 ---
542
543 #[test]
544 fn xterm256_to_xterm16_identity_for_low_indices() {
545 for i in 0u8..16 {
546 assert_eq!(xterm256_to_xterm16(i), i, "identity failed for {i}");
547 }
548 }
549}