1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
//! Helpers for taking a slice of indices (indices into `PLTE` and/or `trNS`
//! entries) and transforming this into RGB or RGBA output.
//!
//! # Memoization
//!
//! To achieve higher throughput, `create_rgba_palette` combines entries from
//! `PLTE` and `trNS` chunks into a single lookup table.  This is based on the
//! ideas explored in <https://crbug.com/706134>.
//!
//! Memoization is a trade-off:
//! * On one hand, memoization requires spending X ns before starting to call
//!   `expand_paletted_...` functions.
//! * On the other hand, memoization improves the throughput of the
//!   `expand_paletted_...` functions - they take Y ns less to process each byte
//!
//! Based on X and Y, we can try to calculate the breakeven point.  It seems
//! that memoization is a net benefit for images bigger than around 13x13 pixels.

use super::{unpack_bits, TransformFn};
use crate::{BitDepth, Info};

pub fn create_expansion_into_rgb8(info: &Info) -> TransformFn {
    let rgba_palette = create_rgba_palette(info);

    if info.bit_depth == BitDepth::Eight {
        Box::new(move |input, output, _info| expand_8bit_into_rgb8(input, output, &rgba_palette))
    } else {
        Box::new(move |input, output, info| expand_into_rgb8(input, output, info, &rgba_palette))
    }
}

pub fn create_expansion_into_rgba8(info: &Info) -> TransformFn {
    let rgba_palette = create_rgba_palette(info);
    Box::new(move |input, output, info| {
        expand_paletted_into_rgba8(input, output, info, &rgba_palette)
    })
}

fn create_rgba_palette(info: &Info) -> [[u8; 4]; 256] {
    let palette = info.palette.as_deref().expect("Caller should verify");
    let trns = info.trns.as_deref().unwrap_or(&[]);

    // > The tRNS chunk shall not contain more alpha values than there are palette
    // entries, but a tRNS chunk may contain fewer values than there are palette
    // entries. In this case, the alpha value for all remaining palette entries is
    // assumed to be 255.
    //
    // It seems, accepted reading is to fully *ignore* an invalid tRNS as if it were
    // completely empty / all pixels are non-transparent.
    let trns = if trns.len() <= palette.len() / 3 {
        trns
    } else {
        &[]
    };

    // Default to black, opaque entries.
    let mut rgba_palette = [[0, 0, 0, 0xFF]; 256];

    // Copy `palette` (RGB) entries into `rgba_palette`.  This may clobber alpha
    // values in `rgba_palette` - we need to fix this later.
    {
        let mut palette_iter = palette;
        let mut rgba_iter = &mut rgba_palette[..];
        while palette_iter.len() >= 4 {
            // Copying 4 bytes at a time is more efficient than copying 3.
            // OTOH, this clobbers the alpha value in `rgba_iter[0][3]` - we
            // need to fix this later.
            rgba_iter[0].copy_from_slice(&palette_iter[0..4]);

            palette_iter = &palette_iter[3..];
            rgba_iter = &mut rgba_iter[1..];
        }
        if palette_iter.len() > 0 {
            rgba_iter[0][0..3].copy_from_slice(&palette_iter[0..3]);
        }
    }

    // Copy `trns` (alpha) entries into `rgba_palette`.  `trns.len()` may be
    // smaller than `palette.len()` and therefore this is not sufficient to fix
    // all the clobbered alpha values.
    for (alpha, rgba) in trns.iter().copied().zip(rgba_palette.iter_mut()) {
        rgba[3] = alpha;
    }

    // Unclobber the remaining alpha values.
    for rgba in rgba_palette[trns.len()..(palette.len() / 3)].iter_mut() {
        rgba[3] = 0xFF;
    }

    rgba_palette
}

fn expand_8bit_into_rgb8(mut input: &[u8], mut output: &mut [u8], rgba_palette: &[[u8; 4]; 256]) {
    while output.len() >= 4 {
        // Copying 4 bytes at a time is more efficient than 3.
        let rgba = &rgba_palette[input[0] as usize];
        output[0..4].copy_from_slice(rgba);

        input = &input[1..];
        output = &mut output[3..];
    }
    if output.len() > 0 {
        let rgba = &rgba_palette[input[0] as usize];
        output[0..3].copy_from_slice(&rgba[0..3]);
    }
}

fn expand_into_rgb8(row: &[u8], buffer: &mut [u8], info: &Info, rgba_palette: &[[u8; 4]; 256]) {
    unpack_bits(row, buffer, 3, info.bit_depth as u8, |i, chunk| {
        let rgba = &rgba_palette[i as usize];
        chunk[0] = rgba[0];
        chunk[1] = rgba[1];
        chunk[2] = rgba[2];
    })
}

fn expand_paletted_into_rgba8(
    row: &[u8],
    buffer: &mut [u8],
    info: &Info,
    rgba_palette: &[[u8; 4]; 256],
) {
    unpack_bits(row, buffer, 4, info.bit_depth as u8, |i, chunk| {
        chunk.copy_from_slice(&rgba_palette[i as usize]);
    });
}

#[cfg(test)]
mod test {
    use crate::{BitDepth, ColorType, Info, Transformations};

    /// Old, non-memoized version of the code is used as a test oracle.
    fn oracle_expand_paletted_into_rgb8(row: &[u8], buffer: &mut [u8], info: &Info) {
        let palette = info.palette.as_deref().expect("Caller should verify");
        let black = [0, 0, 0];

        super::unpack_bits(row, buffer, 3, info.bit_depth as u8, |i, chunk| {
            let rgb = palette
                .get(3 * i as usize..3 * i as usize + 3)
                .unwrap_or(&black);
            chunk[0] = rgb[0];
            chunk[1] = rgb[1];
            chunk[2] = rgb[2];
        })
    }

    /// Old, non-memoized version of the code is used as a test oracle.
    fn oracle_expand_paletted_into_rgba8(row: &[u8], buffer: &mut [u8], info: &Info) {
        let palette = info.palette.as_deref().expect("Caller should verify");
        let trns = info.trns.as_deref().unwrap_or(&[]);
        let black = [0, 0, 0];

        // > The tRNS chunk shall not contain more alpha values than there are palette
        // entries, but a tRNS chunk may contain fewer values than there are palette
        // entries. In this case, the alpha value for all remaining palette entries is
        // assumed to be 255.
        //
        // It seems, accepted reading is to fully *ignore* an invalid tRNS as if it were
        // completely empty / all pixels are non-transparent.
        let trns = if trns.len() <= palette.len() / 3 {
            trns
        } else {
            &[]
        };

        super::unpack_bits(row, buffer, 4, info.bit_depth as u8, |i, chunk| {
            let (rgb, a) = (
                palette
                    .get(3 * i as usize..3 * i as usize + 3)
                    .unwrap_or(&black),
                *trns.get(i as usize).unwrap_or(&0xFF),
            );
            chunk[0] = rgb[0];
            chunk[1] = rgb[1];
            chunk[2] = rgb[2];
            chunk[3] = a;
        });
    }

    fn create_info<'a>(src_bit_depth: u8, palette: &'a [u8], trns: Option<&'a [u8]>) -> Info<'a> {
        Info {
            color_type: ColorType::Indexed,
            bit_depth: BitDepth::from_u8(src_bit_depth).unwrap(),
            palette: Some(palette.into()),
            trns: trns.map(Into::into),
            ..Info::default()
        }
    }

    fn expand_paletted(
        src: &[u8],
        src_bit_depth: u8,
        palette: &[u8],
        trns: Option<&[u8]>,
    ) -> Vec<u8> {
        let info = create_info(src_bit_depth, palette, trns);
        let output_bytes_per_input_sample = match trns {
            None => 3,
            Some(_) => 4,
        };
        let samples_count_per_byte = (8 / src_bit_depth) as usize;
        let samples_count = src.len() * samples_count_per_byte;

        let mut dst = vec![0; samples_count * output_bytes_per_input_sample];
        let transform_fn =
            super::super::create_transform_fn(&info, Transformations::EXPAND).unwrap();
        transform_fn(src, dst.as_mut_slice(), &info);

        {
            // Compare the memoization-based calculations with the old, non-memoized code.
            let mut simple_dst = vec![0; samples_count * output_bytes_per_input_sample];
            if trns.is_none() {
                oracle_expand_paletted_into_rgb8(src, &mut simple_dst, &info)
            } else {
                oracle_expand_paletted_into_rgba8(src, &mut simple_dst, &info)
            }
            assert_eq!(&dst, &simple_dst);
        }

        dst
    }

    #[test]
    fn test_expand_paletted_rgba_8bit() {
        let actual = expand_paletted(
            &[0, 1, 2, 3], // src
            8,             // src_bit_depth
            &[
                // palette
                0, 1, 2, //    entry #0
                4, 5, 6, //    entry #1
                8, 9, 10, //   entry #2
                12, 13, 14, // entry #3
            ],
            Some(&[3, 7, 11, 15]), // trns
        );
        assert_eq!(actual, (0..16).collect::<Vec<u8>>());
    }

    #[test]
    fn test_expand_paletted_rgb_8bit() {
        let actual = expand_paletted(
            &[0, 1, 2, 3], // src
            8,             // src_bit_depth
            &[
                // palette
                0, 1, 2, //   entry #0
                3, 4, 5, //   entry #1
                6, 7, 8, //   entry #2
                9, 10, 11, // entry #3
            ],
            None, // trns
        );
        assert_eq!(actual, (0..12).collect::<Vec<u8>>());
    }

    #[test]
    fn test_expand_paletted_rgba_4bit() {
        let actual = expand_paletted(
            &[0x01, 0x23], // src
            4,             // src_bit_depth
            &[
                // palette
                0, 1, 2, //    entry #0
                4, 5, 6, //    entry #1
                8, 9, 10, //   entry #2
                12, 13, 14, // entry #3
            ],
            Some(&[3, 7, 11, 15]), // trns
        );
        assert_eq!(actual, (0..16).collect::<Vec<u8>>());
    }

    #[test]
    fn test_expand_paletted_rgb_4bit() {
        let actual = expand_paletted(
            &[0x01, 0x23], // src
            4,             // src_bit_depth
            &[
                // palette
                0, 1, 2, //   entry #0
                3, 4, 5, //   entry #1
                6, 7, 8, //   entry #2
                9, 10, 11, // entry #3
            ],
            None, // trns
        );
        assert_eq!(actual, (0..12).collect::<Vec<u8>>());
    }

    #[test]
    fn test_expand_paletted_rgba_8bit_more_trns_entries_than_palette_entries() {
        let actual = expand_paletted(
            &[0, 1, 2, 3], // src
            8,             // src_bit_depth
            &[
                // palette
                0, 1, 2, //    entry #0
                4, 5, 6, //    entry #1
                8, 9, 10, //   entry #2
                12, 13, 14, // entry #3
            ],
            Some(&[123; 5]), // trns
        );

        // Invalid (too-long) `trns` means that we'll use 0xFF / opaque alpha everywhere.
        assert_eq!(
            actual,
            vec![0, 1, 2, 0xFF, 4, 5, 6, 0xFF, 8, 9, 10, 0xFF, 12, 13, 14, 0xFF],
        );
    }

    #[test]
    fn test_expand_paletted_rgba_8bit_less_trns_entries_than_palette_entries() {
        let actual = expand_paletted(
            &[0, 1, 2, 3], // src
            8,             // src_bit_depth
            &[
                // palette
                0, 1, 2, //    entry #0
                4, 5, 6, //    entry #1
                8, 9, 10, //   entry #2
                12, 13, 14, // entry #3
            ],
            Some(&[3, 7]), // trns
        );

        // Too-short `trns` is treated differently from too-long - only missing entries are
        // replaced with 0XFF / opaque.
        assert_eq!(
            actual,
            vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0xFF, 12, 13, 14, 0xFF],
        );
    }

    #[test]
    fn test_create_rgba_palette() {
        fn create_expected_rgba_palette(plte: &[u8], trns: &[u8]) -> [[u8; 4]; 256] {
            let mut rgba = [[1, 2, 3, 4]; 256];
            for (i, rgba) in rgba.iter_mut().enumerate() {
                rgba[0] = plte.get(i * 3 + 0).map(|&r| r).unwrap_or(0);
                rgba[1] = plte.get(i * 3 + 1).map(|&g| g).unwrap_or(0);
                rgba[2] = plte.get(i * 3 + 2).map(|&b| b).unwrap_or(0);
                rgba[3] = trns.get(i * 1 + 0).map(|&a| a).unwrap_or(0xFF);
            }
            rgba
        }

        for plte_len in 1..=32 {
            for trns_len in 0..=plte_len {
                let plte: Vec<u8> = (0..plte_len * 3).collect();
                let trns: Vec<u8> = (0..trns_len).map(|alpha| alpha + 200).collect();

                let info = create_info(8, &plte, Some(&trns));
                let expected = create_expected_rgba_palette(&plte, &trns);
                let actual = super::create_rgba_palette(&info);
                assert_eq!(actual, expected);
            }
        }
    }
}