| 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 |
} |