1//! Helpers for taking a slice of indeces (indices into `PLTE` and/or `trNS`
2//! entries) and transforming this into RGB or RGBA output.
3//!
4//! # Memoization
5//!
6//! To achieve higher throughput, `create_rgba_palette` combines entries from
7//! `PLTE` and `trNS` chunks into a single lookup table. This is based on the
8//! ideas explored in https://crbug.com/706134.
9//!
10//! Memoization is a trade-off:
11//! * On one hand, memoization requires spending X ns before starting to call
12//! `expand_paletted_...` functions.
13//! * On the other hand, memoization improves the throughput of the
14//! `expand_paletted_...` functions - they take Y ns less to process each byte
15//!
16//! Based on X and Y, we can try to calculate the breakeven point. It seems
17//! that memoization is a net benefit for images bigger than around 13x13 pixels.
18
19use super::{unpack_bits, TransformFn};
20use crate::{BitDepth, Info};
21
22pub fn create_expansion_into_rgb8(info: &Info) -> TransformFn {
23 let rgba_palette: [[u8; 4]; 256] = create_rgba_palette(info);
24
25 if info.bit_depth == BitDepth::Eight {
26 Box::new(move |input: &[u8], output: &mut [u8], _info: &Info<'_>| expand_8bit_into_rgb8(input, output, &rgba_palette))
27 } else {
28 Box::new(move |input: &[u8], output: &mut [u8], info: &Info<'_>| expand_into_rgb8(row:input, buffer:output, info, &rgba_palette))
29 }
30}
31
32pub fn create_expansion_into_rgba8(info: &Info) -> TransformFn {
33 let rgba_palette: [[u8; 4]; 256] = create_rgba_palette(info);
34 Box::new(move |input: &[u8], output: &mut [u8], info: &Info<'_>| {
35 expand_paletted_into_rgba8(row:input, buffer:output, info, &rgba_palette)
36 })
37}
38
39fn create_rgba_palette(info: &Info) -> [[u8; 4]; 256] {
40 let palette = info.palette.as_deref().expect("Caller should verify");
41 let trns = info.trns.as_deref().unwrap_or(&[]);
42
43 // > The tRNS chunk shall not contain more alpha values than there are palette
44 // entries, but a tRNS chunk may contain fewer values than there are palette
45 // entries. In this case, the alpha value for all remaining palette entries is
46 // assumed to be 255.
47 //
48 // It seems, accepted reading is to fully *ignore* an invalid tRNS as if it were
49 // completely empty / all pixels are non-transparent.
50 let trns = if trns.len() <= palette.len() / 3 {
51 trns
52 } else {
53 &[]
54 };
55
56 // Default to black, opaque entries.
57 let mut rgba_palette = [[0, 0, 0, 0xFF]; 256];
58
59 // Copy `palette` (RGB) entries into `rgba_palette`. This may clobber alpha
60 // values in `rgba_palette` - we need to fix this later.
61 {
62 let mut palette_iter = palette;
63 let mut rgba_iter = &mut rgba_palette[..];
64 while palette_iter.len() >= 4 {
65 // Copying 4 bytes at a time is more efficient than copying 3.
66 // OTOH, this clobbers the alpha value in `rgba_iter[0][3]` - we
67 // need to fix this later.
68 rgba_iter[0].copy_from_slice(&palette_iter[0..4]);
69
70 palette_iter = &palette_iter[3..];
71 rgba_iter = &mut rgba_iter[1..];
72 }
73 if palette_iter.len() > 0 {
74 rgba_iter[0][0..3].copy_from_slice(&palette_iter[0..3]);
75 }
76 }
77
78 // Copy `trns` (alpha) entries into `rgba_palette`. `trns.len()` may be
79 // smaller than `palette.len()` and therefore this is not sufficient to fix
80 // all the clobbered alpha values.
81 for (alpha, rgba) in trns.iter().copied().zip(rgba_palette.iter_mut()) {
82 rgba[3] = alpha;
83 }
84
85 // Unclobber the remaining alpha values.
86 for rgba in rgba_palette[trns.len()..(palette.len() / 3)].iter_mut() {
87 rgba[3] = 0xFF;
88 }
89
90 rgba_palette
91}
92
93fn expand_8bit_into_rgb8(mut input: &[u8], mut output: &mut [u8], rgba_palette: &[[u8; 4]; 256]) {
94 while output.len() >= 4 {
95 // Copying 4 bytes at a time is more efficient than 3.
96 let rgba: &[u8; 4] = &rgba_palette[input[0] as usize];
97 output[0..4].copy_from_slice(src:rgba);
98
99 input = &input[1..];
100 output = &mut output[3..];
101 }
102 if output.len() > 0 {
103 let rgba: &[u8; 4] = &rgba_palette[input[0] as usize];
104 output[0..3].copy_from_slice(&rgba[0..3]);
105 }
106}
107
108fn expand_into_rgb8(row: &[u8], buffer: &mut [u8], info: &Info, rgba_palette: &[[u8; 4]; 256]) {
109 unpack_bits(input:row, output:buffer, channels:3, info.bit_depth as u8, |i: u8, chunk: &mut [u8]| {
110 let rgba: &[u8; 4] = &rgba_palette[i as usize];
111 chunk[0] = rgba[0];
112 chunk[1] = rgba[1];
113 chunk[2] = rgba[2];
114 })
115}
116
117fn expand_paletted_into_rgba8(
118 row: &[u8],
119 buffer: &mut [u8],
120 info: &Info,
121 rgba_palette: &[[u8; 4]; 256],
122) {
123 unpack_bits(input:row, output:buffer, channels:4, info.bit_depth as u8, |i: u8, chunk: &mut [u8]| {
124 chunk.copy_from_slice(&rgba_palette[i as usize]);
125 });
126}
127
128#[cfg(test)]
129mod test {
130 use crate::{BitDepth, ColorType, Info, Transformations};
131
132 /// Old, non-memoized version of the code is used as a test oracle.
133 fn oracle_expand_paletted_into_rgb8(row: &[u8], buffer: &mut [u8], info: &Info) {
134 let palette = info.palette.as_deref().expect("Caller should verify");
135 let black = [0, 0, 0];
136
137 super::unpack_bits(row, buffer, 3, info.bit_depth as u8, |i, chunk| {
138 let rgb = palette
139 .get(3 * i as usize..3 * i as usize + 3)
140 .unwrap_or(&black);
141 chunk[0] = rgb[0];
142 chunk[1] = rgb[1];
143 chunk[2] = rgb[2];
144 })
145 }
146
147 /// Old, non-memoized version of the code is used as a test oracle.
148 fn oracle_expand_paletted_into_rgba8(row: &[u8], buffer: &mut [u8], info: &Info) {
149 let palette = info.palette.as_deref().expect("Caller should verify");
150 let trns = info.trns.as_deref().unwrap_or(&[]);
151 let black = [0, 0, 0];
152
153 // > The tRNS chunk shall not contain more alpha values than there are palette
154 // entries, but a tRNS chunk may contain fewer values than there are palette
155 // entries. In this case, the alpha value for all remaining palette entries is
156 // assumed to be 255.
157 //
158 // It seems, accepted reading is to fully *ignore* an invalid tRNS as if it were
159 // completely empty / all pixels are non-transparent.
160 let trns = if trns.len() <= palette.len() / 3 {
161 trns
162 } else {
163 &[]
164 };
165
166 super::unpack_bits(row, buffer, 4, info.bit_depth as u8, |i, chunk| {
167 let (rgb, a) = (
168 palette
169 .get(3 * i as usize..3 * i as usize + 3)
170 .unwrap_or(&black),
171 *trns.get(i as usize).unwrap_or(&0xFF),
172 );
173 chunk[0] = rgb[0];
174 chunk[1] = rgb[1];
175 chunk[2] = rgb[2];
176 chunk[3] = a;
177 });
178 }
179
180 fn create_info<'a>(src_bit_depth: u8, palette: &'a [u8], trns: Option<&'a [u8]>) -> Info<'a> {
181 Info {
182 color_type: ColorType::Indexed,
183 bit_depth: BitDepth::from_u8(src_bit_depth).unwrap(),
184 palette: Some(palette.into()),
185 trns: trns.map(Into::into),
186 ..Info::default()
187 }
188 }
189
190 fn expand_paletted(
191 src: &[u8],
192 src_bit_depth: u8,
193 palette: &[u8],
194 trns: Option<&[u8]>,
195 ) -> Vec<u8> {
196 let info = create_info(src_bit_depth, palette, trns);
197 let output_bytes_per_input_sample = match trns {
198 None => 3,
199 Some(_) => 4,
200 };
201 let samples_count_per_byte = (8 / src_bit_depth) as usize;
202 let samples_count = src.len() * samples_count_per_byte;
203
204 let mut dst = vec![0; samples_count * output_bytes_per_input_sample];
205 let transform_fn =
206 super::super::create_transform_fn(&info, Transformations::EXPAND).unwrap();
207 transform_fn(src, dst.as_mut_slice(), &info);
208
209 {
210 // Compare the memoization-based calculations with the old, non-memoized code.
211 let mut simple_dst = vec![0; samples_count * output_bytes_per_input_sample];
212 if trns.is_none() {
213 oracle_expand_paletted_into_rgb8(src, &mut simple_dst, &info)
214 } else {
215 oracle_expand_paletted_into_rgba8(src, &mut simple_dst, &info)
216 }
217 assert_eq!(&dst, &simple_dst);
218 }
219
220 dst
221 }
222
223 #[test]
224 fn test_expand_paletted_rgba_8bit() {
225 let actual = expand_paletted(
226 &[0, 1, 2, 3], // src
227 8, // src_bit_depth
228 &[
229 // palette
230 0, 1, 2, // entry #0
231 4, 5, 6, // entry #1
232 8, 9, 10, // entry #2
233 12, 13, 14, // entry #3
234 ],
235 Some(&[3, 7, 11, 15]), // trns
236 );
237 assert_eq!(actual, (0..16).collect::<Vec<u8>>());
238 }
239
240 #[test]
241 fn test_expand_paletted_rgb_8bit() {
242 let actual = expand_paletted(
243 &[0, 1, 2, 3], // src
244 8, // src_bit_depth
245 &[
246 // palette
247 0, 1, 2, // entry #0
248 3, 4, 5, // entry #1
249 6, 7, 8, // entry #2
250 9, 10, 11, // entry #3
251 ],
252 None, // trns
253 );
254 assert_eq!(actual, (0..12).collect::<Vec<u8>>());
255 }
256
257 #[test]
258 fn test_expand_paletted_rgba_4bit() {
259 let actual = expand_paletted(
260 &[0x01, 0x23], // src
261 4, // src_bit_depth
262 &[
263 // palette
264 0, 1, 2, // entry #0
265 4, 5, 6, // entry #1
266 8, 9, 10, // entry #2
267 12, 13, 14, // entry #3
268 ],
269 Some(&[3, 7, 11, 15]), // trns
270 );
271 assert_eq!(actual, (0..16).collect::<Vec<u8>>());
272 }
273
274 #[test]
275 fn test_expand_paletted_rgb_4bit() {
276 let actual = expand_paletted(
277 &[0x01, 0x23], // src
278 4, // src_bit_depth
279 &[
280 // palette
281 0, 1, 2, // entry #0
282 3, 4, 5, // entry #1
283 6, 7, 8, // entry #2
284 9, 10, 11, // entry #3
285 ],
286 None, // trns
287 );
288 assert_eq!(actual, (0..12).collect::<Vec<u8>>());
289 }
290
291 #[test]
292 fn test_expand_paletted_rgba_8bit_more_trns_entries_than_palette_entries() {
293 let actual = expand_paletted(
294 &[0, 1, 2, 3], // src
295 8, // src_bit_depth
296 &[
297 // palette
298 0, 1, 2, // entry #0
299 4, 5, 6, // entry #1
300 8, 9, 10, // entry #2
301 12, 13, 14, // entry #3
302 ],
303 Some(&[123; 5]), // trns
304 );
305
306 // Invalid (too-long) `trns` means that we'll use 0xFF / opaque alpha everywhere.
307 assert_eq!(
308 actual,
309 vec![0, 1, 2, 0xFF, 4, 5, 6, 0xFF, 8, 9, 10, 0xFF, 12, 13, 14, 0xFF],
310 );
311 }
312
313 #[test]
314 fn test_expand_paletted_rgba_8bit_less_trns_entries_than_palette_entries() {
315 let actual = expand_paletted(
316 &[0, 1, 2, 3], // src
317 8, // src_bit_depth
318 &[
319 // palette
320 0, 1, 2, // entry #0
321 4, 5, 6, // entry #1
322 8, 9, 10, // entry #2
323 12, 13, 14, // entry #3
324 ],
325 Some(&[3, 7]), // trns
326 );
327
328 // Too-short `trns` is treated differently from too-long - only missing entries are
329 // replaced with 0XFF / opaque.
330 assert_eq!(
331 actual,
332 vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0xFF, 12, 13, 14, 0xFF],
333 );
334 }
335
336 #[test]
337 fn test_create_rgba_palette() {
338 fn create_expected_rgba_palette(plte: &[u8], trns: &[u8]) -> [[u8; 4]; 256] {
339 let mut rgba = [[1, 2, 3, 4]; 256];
340 for (i, rgba) in rgba.iter_mut().enumerate() {
341 rgba[0] = plte.get(i * 3 + 0).map(|&r| r).unwrap_or(0);
342 rgba[1] = plte.get(i * 3 + 1).map(|&g| g).unwrap_or(0);
343 rgba[2] = plte.get(i * 3 + 2).map(|&b| b).unwrap_or(0);
344 rgba[3] = trns.get(i * 1 + 0).map(|&a| a).unwrap_or(0xFF);
345 }
346 rgba
347 }
348
349 for plte_len in 1..=32 {
350 for trns_len in 0..=plte_len {
351 let plte: Vec<u8> = (0..plte_len * 3).collect();
352 let trns: Vec<u8> = (0..trns_len).map(|alpha| alpha + 200).collect();
353
354 let info = create_info(8, &plte, Some(&trns));
355 let expected = create_expected_rgba_palette(&plte, &trns);
356 let actual = super::create_rgba_palette(&info);
357 assert_eq!(actual, expected);
358 }
359 }
360 }
361}
362