Debian Codegraph @

.cargo/vendor/png/src/decoder/transform/palette.rs

raw
1 //! Helpers for taking a slice of indices (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
19 use super::{unpack_bits, TransformFn};
20 use crate::{BitDepth, Info};
21
22 pub fn create_expansion_into_rgb8(info: &Info) -> TransformFn {
23 let rgba_palette = create_rgba_palette(info);
24
25 if info.bit_depth == BitDepth::Eight {
26 Box::new(move |input, output, _info| expand_8bit_into_rgb8(input, output, &rgba_palette))
27 } else {
28 Box::new(move |input, output, info| expand_into_rgb8(input, output, info, &rgba_palette))
29 }
30 }
31
32 pub fn create_expansion_into_rgba8(info: &Info) -> TransformFn {
33 let rgba_palette = create_rgba_palette(info);
34 Box::new(move |input, output, info| {
35 expand_paletted_into_rgba8(input, output, info, &rgba_palette)
36 })
37 }
38
39 fn 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.is_empty() {
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
93 fn 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 = &rgba_palette[input[0] as usize];
97 output[0..4].copy_from_slice(rgba);
98
99 input = &input[1..];
100 output = &mut output[3..];
101 }
102 if !output.is_empty() {
103 let rgba = &rgba_palette[input[0] as usize];
104 output[0..3].copy_from_slice(&rgba[0..3]);
105 }
106 }
107
108 fn expand_into_rgb8(row: &[u8], buffer: &mut [u8], info: &Info, rgba_palette: &[[u8; 4]; 256]) {
109 unpack_bits(row, buffer, 3, info.bit_depth as u8, |i, chunk| {
110 let rgba = &rgba_palette[i as usize];
111 chunk[0] = rgba[0];
112 chunk[1] = rgba[1];
113 chunk[2] = rgba[2];
114 })
115 }
116
117 fn expand_paletted_into_rgba8(
118 row: &[u8],
119 buffer: &mut [u8],
120 info: &Info,
121 rgba_palette: &[[u8; 4]; 256],
122 ) {
123 unpack_bits(row, buffer, 4, info.bit_depth as u8, |i, chunk| {
124 chunk.copy_from_slice(&rgba_palette[i as usize]);
125 });
126 }
127
128 #[cfg(test)]
129 mod 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 }