mod.rs (21871B)
1 /* This Source Code Form is subject to the terms of the Mozilla Public 2 * License, v. 2.0. If a copy of the MPL was not distributed with this 3 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ 4 5 use api::{ColorF, ColorU, ExtendMode, GradientStop, PremultipliedColorF}; 6 use api::units::{LayoutRect, LayoutSize, LayoutVector2D}; 7 use crate::renderer::{GpuBufferAddress, GpuBufferBuilderF, GpuBufferWriterF}; 8 use std::hash; 9 10 mod linear; 11 mod radial; 12 mod conic; 13 14 pub use linear::MAX_CACHED_SIZE as LINEAR_MAX_CACHED_SIZE; 15 16 pub use linear::*; 17 pub use radial::*; 18 pub use conic::*; 19 20 #[repr(u8)] 21 #[derive(Copy, Clone, Debug)] 22 pub enum GradientKind { 23 Linear = 0, 24 Radial = 1, 25 Conic = 2, 26 } 27 28 /// A hashable gradient stop that can be used in primitive keys. 29 #[cfg_attr(feature = "capture", derive(Serialize))] 30 #[cfg_attr(feature = "replay", derive(Deserialize))] 31 #[derive(Debug, Copy, Clone, MallocSizeOf, PartialEq)] 32 pub struct GradientStopKey { 33 pub offset: f32, 34 pub color: ColorU, 35 } 36 37 impl GradientStopKey { 38 pub fn empty() -> Self { 39 GradientStopKey { 40 offset: 0.0, 41 color: ColorU::new(0, 0, 0, 0), 42 } 43 } 44 } 45 46 impl Into<GradientStopKey> for GradientStop { 47 fn into(self) -> GradientStopKey { 48 GradientStopKey { 49 offset: self.offset, 50 color: self.color.into(), 51 } 52 } 53 } 54 55 // Convert `stop_keys` into a vector of `GradientStop`s, which is a more 56 // convenient representation for the current gradient builder. Compute the 57 // minimum stop alpha along the way. 58 fn stops_and_min_alpha(stop_keys: &[GradientStopKey]) -> (Vec<GradientStop>, f32) { 59 let mut min_alpha: f32 = 1.0; 60 let stops = stop_keys.iter().map(|stop_key| { 61 let color: ColorF = stop_key.color.into(); 62 min_alpha = min_alpha.min(color.a); 63 64 GradientStop { 65 offset: stop_key.offset, 66 color, 67 } 68 }).collect(); 69 70 (stops, min_alpha) 71 } 72 73 fn write_gpu_gradient_stops_header_and_colors( 74 stops: &[GradientStop], 75 kind: GradientKind, 76 extend_mode: ExtendMode, 77 writer: &mut GpuBufferWriterF, 78 ) -> bool { 79 // Write the header. 80 writer.push_one([ 81 (kind as u8) as f32, 82 stops.len() as f32, 83 if extend_mode == ExtendMode::Repeat { 1.0 } else { 0.0 }, 84 0.0 85 ]); 86 87 // Write the stop colors. 88 let mut is_opaque = true; 89 for stop in stops { 90 writer.push_one(stop.color.premultiplied()); 91 is_opaque &= stop.color.a == 1.0; 92 } 93 94 is_opaque 95 } 96 97 // Push stop offsets in rearranged order so that the search can be carried 98 // out as an implicit tree traversal. 99 // 100 // The structure of the tree is: 101 // - Each level is plit into 5 partitions. 102 // - The root level has one node (4 offsets -> 5 partitions). 103 // - Each level has 5 more nodes than the previous one. 104 // - Levels are pushed one by one starting from the root 105 // 106 // ```ascii 107 // level : indices 108 // ------:--------- 109 // 0 : 24 ... 110 // 1 : 4 9 14 19 | ... 111 // 2 : 0,1,2,3,|,5,6,7,8,|10,11,12,13,| ,15,16,17,18,| ,20,21,22,23,| ,25, ... 112 // ``` 113 // 114 // In the example above: 115 // - The first (root) contains a single block containing the stop offsets from 116 // indices [24, 49, 74, 99]. 117 // - The second level contains blocks of offsets from indices [4, 9, 14, 19], 118 // [29, 34, 39, 44], etc. 119 // - The third (leaf) level contains blocks from indices [0,1,2,3], [5,6,7,8], 120 // [15, 16, 17, 18], etc. 121 // 122 // Placeholder offsets (1.0) are used when a level has more capacity than the 123 // input number of stops. 124 // 125 // Conceptually, blocks [0,1,2,3] and [5,6,7,8] are the first two children of 126 // the node [4,9,14,19], separated by the offset from index 4. 127 // Links are not explicitly represented via pointers or indices. Instead the 128 // position in the buffer is sufficient to represent the level and index of the 129 // stop (at the expense of having to store extra padding to round up each tree 130 // level to its power-of-5-aligned size). 131 // 132 // This scheme is meant to make the traversal efficient loading offsets in 133 // blocks of 4. The shader can converge to the leaf in very few loads. 134 fn write_gpu_gradient_stops_tree( 135 stops: &[GradientStop], 136 kind: GradientKind, 137 extend_mode: ExtendMode, 138 writer: &mut GpuBufferWriterF, 139 ) -> bool { 140 let is_opaque = write_gpu_gradient_stops_header_and_colors( 141 stops, 142 kind, 143 extend_mode, 144 writer 145 ); 146 147 let num_stops = stops.len(); 148 let mut num_levels = 1; 149 let mut index_stride = 5; 150 let mut next_index_stride = 1; 151 // Number of 4-offsets blocks for the current level. 152 // The root has 1, then each level has 5 more than the previous one. 153 let mut num_blocks_for_level = 1; 154 let mut offset_blocks = 1; 155 while offset_blocks * 4 < num_stops { 156 num_blocks_for_level *= 5; 157 offset_blocks += num_blocks_for_level; 158 159 num_levels += 1; 160 index_stride *= 5; 161 next_index_stride *= 5; 162 } 163 164 // Fix offset_blocks up to account for the fact that we don't 165 // store the entirety of the last level; 166 let num_blocks_for_last_level = num_blocks_for_level.min(num_stops / 5 + 1); 167 168 // Reset num_blocks_for_level for the traversal. 169 num_blocks_for_level = 1; 170 171 // Go over each level, starting from the root. 172 for level in 0..num_levels { 173 // This scheme rounds up the number of offsets to store for each 174 // level to the next power of 5, which can represent a lot of wasted 175 // space, especially for the last levels. We need each level to start 176 // at a specific power-of-5-aligned offset so we can't get around the 177 // wasted space for all levels except the last one (which has the most 178 // waste). 179 let is_last_level = level == num_levels - 1; 180 let num_blocks = if is_last_level { 181 num_blocks_for_last_level 182 } else { 183 num_blocks_for_level 184 }; 185 186 for block_idx in 0..num_blocks { 187 let mut block = [1.0; 4]; 188 for i in 0..4 { 189 let linear_idx = block_idx * index_stride 190 + i * next_index_stride 191 + next_index_stride - 1; 192 193 if linear_idx < num_stops { 194 block[i] = stops[linear_idx].offset; 195 } 196 } 197 writer.push_one(block); 198 } 199 200 index_stride = next_index_stride; 201 next_index_stride /= 5; 202 num_blocks_for_level *= 5; 203 } 204 205 return is_opaque; 206 } 207 208 fn gpu_gradient_stops_blocks(num_stops: usize) -> usize { 209 let header_blocks = 1; 210 let color_blocks = num_stops; 211 212 // If this is changed, matching changes should be made to the 213 // equivalent code in write_gpu_gradient_stops_tree. 214 let mut num_blocks_for_level = 1; 215 let mut offset_blocks = 1; 216 while offset_blocks * 4 < num_stops { 217 num_blocks_for_level *= 5; 218 offset_blocks += num_blocks_for_level; 219 } 220 221 // Fix the capacity up to account for the fact that we don't 222 // store the entirety of the last level; 223 let num_blocks_for_last_level = num_blocks_for_level.min(num_stops / 5 + 1); 224 offset_blocks -= num_blocks_for_level; 225 offset_blocks += num_blocks_for_last_level; 226 227 header_blocks + color_blocks + offset_blocks 228 } 229 230 impl Eq for GradientStopKey {} 231 232 impl hash::Hash for GradientStopKey { 233 fn hash<H: hash::Hasher>(&self, state: &mut H) { 234 self.offset.to_bits().hash(state); 235 self.color.hash(state); 236 } 237 } 238 239 // The gradient entry index for the first color stop 240 pub const GRADIENT_DATA_FIRST_STOP: usize = 0; 241 // The gradient entry index for the last color stop 242 pub const GRADIENT_DATA_LAST_STOP: usize = GRADIENT_DATA_SIZE - 1; 243 244 // The start of the gradient data table 245 pub const GRADIENT_DATA_TABLE_BEGIN: usize = GRADIENT_DATA_FIRST_STOP + 1; 246 // The exclusive bound of the gradient data table 247 pub const GRADIENT_DATA_TABLE_END: usize = GRADIENT_DATA_LAST_STOP; 248 // The number of entries in the gradient data table. 249 pub const GRADIENT_DATA_TABLE_SIZE: usize = 128; 250 251 // The number of entries in a gradient data: GRADIENT_DATA_TABLE_SIZE + first stop entry + last stop entry 252 pub const GRADIENT_DATA_SIZE: usize = GRADIENT_DATA_TABLE_SIZE + 2; 253 254 /// An entry in a gradient data table representing a segment of the gradient 255 /// color space. 256 #[derive(Debug, Copy, Clone)] 257 #[repr(C)] 258 struct GradientDataEntry { 259 start_color: PremultipliedColorF, 260 end_step: PremultipliedColorF, 261 } 262 263 impl GradientDataEntry { 264 fn white() -> Self { 265 Self { 266 start_color: PremultipliedColorF::WHITE, 267 end_step: PremultipliedColorF::TRANSPARENT, 268 } 269 } 270 } 271 272 // TODO(gw): Tidy this up to be a free function / module? 273 pub struct GradientGpuBlockBuilder {} 274 275 impl GradientGpuBlockBuilder { 276 /// Generate a color ramp filling the indices in [start_idx, end_idx) and interpolating 277 /// from start_color to end_color. 278 fn fill_colors( 279 start_idx: usize, 280 end_idx: usize, 281 start_color: &PremultipliedColorF, 282 end_color: &PremultipliedColorF, 283 entries: &mut [GradientDataEntry; GRADIENT_DATA_SIZE], 284 prev_step: &PremultipliedColorF, 285 ) -> PremultipliedColorF { 286 // Calculate the color difference for individual steps in the ramp. 287 let inv_steps = 1.0 / (end_idx - start_idx) as f32; 288 let mut step = PremultipliedColorF { 289 r: (end_color.r - start_color.r) * inv_steps, 290 g: (end_color.g - start_color.g) * inv_steps, 291 b: (end_color.b - start_color.b) * inv_steps, 292 a: (end_color.a - start_color.a) * inv_steps, 293 }; 294 // As a subtle form of compression, we ensure that the step values for 295 // each stop range are the same if and only if they belong to the same 296 // stop range. However, if two different stop ranges have the same step, 297 // we need to modify the steps so they compare unequally between ranges. 298 // This allows to quickly compare if two adjacent stops belong to the 299 // same range by comparing their steps. 300 if step == *prev_step { 301 // Modify the step alpha value as if by nextafter(). The difference 302 // here should be so small as to be unnoticeable, but yet allow it 303 // to compare differently. 304 step.a = f32::from_bits(if step.a == 0.0 { 1 } else { step.a.to_bits() + 1 }); 305 } 306 307 let mut cur_color = *start_color; 308 309 // Walk the ramp writing start and end colors for each entry. 310 for index in start_idx .. end_idx { 311 let entry = &mut entries[index]; 312 entry.start_color = cur_color; 313 cur_color.r += step.r; 314 cur_color.g += step.g; 315 cur_color.b += step.b; 316 cur_color.a += step.a; 317 entry.end_step = step; 318 } 319 320 step 321 } 322 323 /// Compute an index into the gradient entry table based on a gradient stop offset. This 324 /// function maps offsets from [0, 1] to indices in [GRADIENT_DATA_TABLE_BEGIN, GRADIENT_DATA_TABLE_END]. 325 #[inline] 326 fn get_index(offset: f32) -> usize { 327 (offset.max(0.0).min(1.0) * GRADIENT_DATA_TABLE_SIZE as f32 + 328 GRADIENT_DATA_TABLE_BEGIN as f32) 329 .round() as usize 330 } 331 332 // Build the gradient data from the supplied stops, reversing them if necessary. 333 pub fn build( 334 reverse_stops: bool, 335 gpu_buffer_builder: &mut GpuBufferBuilderF, 336 src_stops: &[GradientStop], 337 ) -> GpuBufferAddress { 338 // Preconditions (should be ensured by DisplayListBuilder): 339 // * we have at least two stops 340 // * first stop has offset 0.0 341 // * last stop has offset 1.0 342 let mut src_stops = src_stops.into_iter(); 343 let mut cur_color = match src_stops.next() { 344 Some(stop) => { 345 debug_assert_eq!(stop.offset, 0.0); 346 stop.color.premultiplied() 347 } 348 None => { 349 error!("Zero gradient stops found!"); 350 PremultipliedColorF::BLACK 351 } 352 }; 353 354 // A table of gradient entries, with two colors per entry, that specify the start and end color 355 // within the segment of the gradient space represented by that entry. To lookup a gradient result, 356 // first the entry index is calculated to determine which two colors to interpolate between, then 357 // the offset within that entry bucket is used to interpolate between the two colors in that entry. 358 // This layout is motivated by the fact that if one naively tries to store a single color per entry 359 // and interpolate directly between entries, then hard stops will become softened because the end 360 // color of an entry actually differs from the start color of the next entry, even though they fall 361 // at the same edge offset in the gradient space. Instead, the two-color-per-entry layout preserves 362 // hard stops, as the end color for a given entry can differ from the start color for the following 363 // entry. 364 // Colors are stored in RGBA32F format (in the GPU cache). This table requires the gradient color 365 // stops to be normalized to the range [0, 1]. The first and last entries hold the first and last 366 // color stop colors respectively, while the entries in between hold the interpolated color stop 367 // values for the range [0, 1]. 368 // As a further optimization, rather than directly storing the end color, the difference of the end 369 // color from the start color is stored instead, so that an entry can be evaluated more cheaply 370 // with start+diff*offset instead of mix(start,end,offset). Further, the color difference in two 371 // adjacent entries will always be the same if they were generated from the same set of stops/run. 372 // To allow fast searching of the table, if two adjacent entries generated from different sets of 373 // stops (a boundary) have the same difference, the floating-point bits of the stop will be nudged 374 // so that they compare differently without perceptibly altering the interpolation result. This way, 375 // one can quickly scan the table and recover runs just by comparing the color differences of the 376 // current and next entry. 377 // For example, a table with 2 inside entries (startR,startG,startB):(diffR,diffG,diffB) might look 378 // like so: 379 // first | 0.0 | 0.5 | last 380 // (0,0,0):(0,0,0) | (1,0,0):(-1,1,0) | (0,0,1):(0,1,-1) | (1,1,1):(0,0,0) 381 // ^ solid black ^ red to green ^ blue to green ^ solid white 382 let mut entries = [GradientDataEntry::white(); GRADIENT_DATA_SIZE]; 383 let mut prev_step = cur_color; 384 if reverse_stops { 385 // Fill in the first entry (for reversed stops) with the first color stop 386 prev_step = GradientGpuBlockBuilder::fill_colors( 387 GRADIENT_DATA_LAST_STOP, 388 GRADIENT_DATA_LAST_STOP + 1, 389 &cur_color, 390 &cur_color, 391 &mut entries, 392 &prev_step, 393 ); 394 395 // Fill in the center of the gradient table, generating a color ramp between each consecutive pair 396 // of gradient stops. Each iteration of a loop will fill the indices in [next_idx, cur_idx). The 397 // loop will then fill indices in [GRADIENT_DATA_TABLE_BEGIN, GRADIENT_DATA_TABLE_END). 398 let mut cur_idx = GRADIENT_DATA_TABLE_END; 399 for next in src_stops { 400 let next_color = next.color.premultiplied(); 401 let next_idx = Self::get_index(1.0 - next.offset); 402 403 if next_idx < cur_idx { 404 prev_step = GradientGpuBlockBuilder::fill_colors( 405 next_idx, 406 cur_idx, 407 &next_color, 408 &cur_color, 409 &mut entries, 410 &prev_step, 411 ); 412 cur_idx = next_idx; 413 } 414 415 cur_color = next_color; 416 } 417 if cur_idx != GRADIENT_DATA_TABLE_BEGIN { 418 error!("Gradient stops abruptly at {}, auto-completing to white", cur_idx); 419 } 420 421 // Fill in the last entry (for reversed stops) with the last color stop 422 GradientGpuBlockBuilder::fill_colors( 423 GRADIENT_DATA_FIRST_STOP, 424 GRADIENT_DATA_FIRST_STOP + 1, 425 &cur_color, 426 &cur_color, 427 &mut entries, 428 &prev_step, 429 ); 430 } else { 431 // Fill in the first entry with the first color stop 432 prev_step = GradientGpuBlockBuilder::fill_colors( 433 GRADIENT_DATA_FIRST_STOP, 434 GRADIENT_DATA_FIRST_STOP + 1, 435 &cur_color, 436 &cur_color, 437 &mut entries, 438 &prev_step, 439 ); 440 441 // Fill in the center of the gradient table, generating a color ramp between each consecutive pair 442 // of gradient stops. Each iteration of a loop will fill the indices in [cur_idx, next_idx). The 443 // loop will then fill indices in [GRADIENT_DATA_TABLE_BEGIN, GRADIENT_DATA_TABLE_END). 444 let mut cur_idx = GRADIENT_DATA_TABLE_BEGIN; 445 for next in src_stops { 446 let next_color = next.color.premultiplied(); 447 let next_idx = Self::get_index(next.offset); 448 449 if next_idx > cur_idx { 450 prev_step = GradientGpuBlockBuilder::fill_colors( 451 cur_idx, 452 next_idx, 453 &cur_color, 454 &next_color, 455 &mut entries, 456 &prev_step, 457 ); 458 cur_idx = next_idx; 459 } 460 461 cur_color = next_color; 462 } 463 if cur_idx != GRADIENT_DATA_TABLE_END { 464 error!("Gradient stops abruptly at {}, auto-completing to white", cur_idx); 465 } 466 467 // Fill in the last entry with the last color stop 468 GradientGpuBlockBuilder::fill_colors( 469 GRADIENT_DATA_LAST_STOP, 470 GRADIENT_DATA_LAST_STOP + 1, 471 &cur_color, 472 &cur_color, 473 &mut entries, 474 &prev_step, 475 ); 476 } 477 478 let mut writer = gpu_buffer_builder.write_blocks(2 * entries.len()); 479 480 for entry in entries { 481 writer.push_one(entry.start_color); 482 writer.push_one(entry.end_step); 483 } 484 485 writer.finish() 486 } 487 } 488 489 // If the gradient is not tiled we know that any content outside of the clip will not 490 // be shown. Applying the clip early reduces how much of the gradient we 491 // render and cache. We do this optimization separately on each axis. 492 // Returns the offset between the new and old primitive rect origin, to apply to the 493 // gradient parameters that are relative to the primitive origin. 494 pub fn apply_gradient_local_clip( 495 prim_rect: &mut LayoutRect, 496 stretch_size: &LayoutSize, 497 tile_spacing: &LayoutSize, 498 clip_rect: &LayoutRect, 499 ) -> LayoutVector2D { 500 let w = prim_rect.max.x.min(clip_rect.max.x) - prim_rect.min.x; 501 let h = prim_rect.max.y.min(clip_rect.max.y) - prim_rect.min.y; 502 let is_tiled_x = w > stretch_size.width + tile_spacing.width; 503 let is_tiled_y = h > stretch_size.height + tile_spacing.height; 504 505 let mut offset = LayoutVector2D::new(0.0, 0.0); 506 507 if !is_tiled_x { 508 let diff = (clip_rect.min.x - prim_rect.min.x).min(prim_rect.width()); 509 if diff > 0.0 { 510 prim_rect.min.x += diff; 511 offset.x = -diff; 512 } 513 514 let diff = prim_rect.max.x - clip_rect.max.x; 515 if diff > 0.0 { 516 prim_rect.max.x -= diff; 517 } 518 } 519 520 if !is_tiled_y { 521 let diff = (clip_rect.min.y - prim_rect.min.y).min(prim_rect.height()); 522 if diff > 0.0 { 523 prim_rect.min.y += diff; 524 offset.y = -diff; 525 } 526 527 let diff = prim_rect.max.y - clip_rect.max.y; 528 if diff > 0.0 { 529 prim_rect.max.y -= diff; 530 } 531 } 532 533 offset 534 } 535 536 #[test] 537 #[cfg(target_pointer_width = "64")] 538 fn test_struct_sizes() { 539 use std::mem; 540 // The sizes of these structures are critical for performance on a number of 541 // talos stress tests. If you get a failure here on CI, there's two possibilities: 542 // (a) You made a structure smaller than it currently is. Great work! Update the 543 // test expectations and move on. 544 // (b) You made a structure larger. This is not necessarily a problem, but should only 545 // be done with care, and after checking if talos performance regresses badly. 546 assert_eq!(mem::size_of::<LinearGradient>(), 72, "LinearGradient size changed"); 547 assert_eq!(mem::size_of::<LinearGradientTemplate>(), 136, "LinearGradientTemplate size changed"); 548 assert_eq!(mem::size_of::<LinearGradientKey>(), 96, "LinearGradientKey size changed"); 549 550 assert_eq!(mem::size_of::<RadialGradient>(), 72, "RadialGradient size changed"); 551 assert_eq!(mem::size_of::<RadialGradientTemplate>(), 136, "RadialGradientTemplate size changed"); 552 assert_eq!(mem::size_of::<RadialGradientKey>(), 96, "RadialGradientKey size changed"); 553 554 assert_eq!(mem::size_of::<ConicGradient>(), 72, "ConicGradient size changed"); 555 assert_eq!(mem::size_of::<ConicGradientTemplate>(), 136, "ConicGradientTemplate size changed"); 556 assert_eq!(mem::size_of::<ConicGradientKey>(), 96, "ConicGradientKey size changed"); 557 }