1use super::{
2 Arc, Color, Error, Image2d, ImageBatch2d, ImageBatchBudget, ImageBatchUploadReport,
3 ImageBudget, ImageError, ImageSprite2d, ImageTexelRect, LogicalScreenPosition, LogicalViewport,
4 LogicalViewportRegion, WgpuRenderer, fmt, image,
5};
6
7#[cfg(test)]
8use super::Vec2;
9
10#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
16pub struct GlyphId(u32);
17
18impl GlyphId {
19 pub const fn new(value: u32) -> Self {
21 Self(value)
22 }
23
24 pub const fn value(self) -> u32 {
26 self.0
27 }
28}
29
30#[derive(Debug, Clone, Copy, PartialEq, Eq)]
32pub struct GlyphAtlasEntry {
33 glyph: GlyphId,
34 source: ImageTexelRect,
35}
36
37impl GlyphAtlasEntry {
38 pub const fn new(glyph: GlyphId, source: ImageTexelRect) -> Self {
40 Self { glyph, source }
41 }
42
43 pub const fn glyph(self) -> GlyphId {
45 self.glyph
46 }
47
48 pub const fn source(self) -> ImageTexelRect {
50 self.source
51 }
52}
53
54#[derive(Debug, Clone, Copy, PartialEq, Eq)]
56pub struct GlyphAtlasBudget {
57 image: ImageBudget,
58 max_entries: usize,
59 max_metadata_bytes: usize,
60}
61
62impl GlyphAtlasBudget {
63 pub fn new(
65 image: ImageBudget,
66 max_entries: usize,
67 max_metadata_bytes: usize,
68 ) -> Result<Self, GlyphError> {
69 if max_entries == 0 || max_metadata_bytes < std::mem::size_of::<GlyphAtlasEntry>() {
70 return Err(GlyphError::InvalidBudget);
71 }
72 Ok(Self {
73 image,
74 max_entries,
75 max_metadata_bytes,
76 })
77 }
78
79 pub const fn image(self) -> ImageBudget {
81 self.image
82 }
83
84 pub const fn max_entries(self) -> usize {
86 self.max_entries
87 }
88
89 pub const fn max_metadata_bytes(self) -> usize {
91 self.max_metadata_bytes
92 }
93}
94
95impl Default for GlyphAtlasBudget {
96 fn default() -> Self {
97 Self {
98 image: ImageBudget::default(),
99 max_entries: 65_536,
100 max_metadata_bytes: 4 * 1024 * 1024,
101 }
102 }
103}
104
105#[derive(Debug, Clone, Copy, PartialEq, Eq)]
107pub struct GlyphRunBudget {
108 max_glyphs: usize,
109 max_retained_bytes: usize,
110}
111
112impl GlyphRunBudget {
113 pub const RETAINED_BYTES_PER_GLYPH: usize =
116 std::mem::size_of::<PositionedGlyph2d>() + ImageBatchBudget::RETAINED_BYTES_PER_SPRITE;
117
118 pub fn new(max_glyphs: usize, max_retained_bytes: usize) -> Result<Self, GlyphError> {
120 if max_glyphs == 0 || max_retained_bytes < glyph_retained_bytes(1).unwrap_or(usize::MAX) {
121 return Err(GlyphError::InvalidBudget);
122 }
123 Ok(Self {
124 max_glyphs,
125 max_retained_bytes,
126 })
127 }
128
129 pub const fn max_glyphs(self) -> usize {
131 self.max_glyphs
132 }
133
134 pub const fn max_retained_bytes(self) -> usize {
136 self.max_retained_bytes
137 }
138}
139
140impl Default for GlyphRunBudget {
141 fn default() -> Self {
142 Self {
143 max_glyphs: 100_000,
144 max_retained_bytes: 32 * 1024 * 1024,
145 }
146 }
147}
148
149#[derive(Debug, Clone, Copy, PartialEq, Eq)]
151pub enum GlyphError {
152 Image(ImageError),
154 InvalidBudget,
156 EntryBudgetExceeded {
158 limit: usize,
160 actual: usize,
162 },
163 MetadataBudgetExceeded {
165 limit: usize,
167 actual: usize,
169 },
170 DuplicateGlyph {
172 glyph: GlyphId,
174 },
175 OverlappingGlyph {
177 glyph: GlyphId,
179 conflicting_glyph: GlyphId,
181 },
182 MissingGlyph {
184 glyph: GlyphId,
186 index: usize,
188 },
189 InvalidGlyph,
191 AllocationFailed {
194 requested_bytes: usize,
196 },
197}
198
199impl fmt::Display for GlyphError {
200 fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
201 match self {
202 Self::Image(error) => write!(formatter, "glyph image error: {error}"),
203 Self::InvalidBudget => write!(formatter, "glyph budget must fit one entry"),
204 Self::EntryBudgetExceeded { limit, actual } => {
205 write!(formatter, "glyph count {actual} exceeds limit {limit}")
206 }
207 Self::MetadataBudgetExceeded { limit, actual } => write!(
208 formatter,
209 "glyph recovery metadata requires {actual} bytes, over limit {limit}"
210 ),
211 Self::DuplicateGlyph { glyph } => {
212 write!(formatter, "glyph identity {} is duplicated", glyph.value())
213 }
214 Self::OverlappingGlyph {
215 glyph,
216 conflicting_glyph,
217 } => write!(
218 formatter,
219 "glyph identity {} overlaps atlas texels owned by glyph {}",
220 glyph.value(),
221 conflicting_glyph.value()
222 ),
223 Self::MissingGlyph { glyph, index } => write!(
224 formatter,
225 "glyph identity {} at run index {index} is absent from the atlas",
226 glyph.value()
227 ),
228 Self::InvalidGlyph => write!(formatter, "glyph placement or atlas region is invalid"),
229 Self::AllocationFailed { requested_bytes } => write!(
230 formatter,
231 "could not reserve {requested_bytes} bytes for glyph metadata or scratch storage"
232 ),
233 }
234 }
235}
236
237impl Error for GlyphError {}
238
239impl From<ImageError> for GlyphError {
240 fn from(error: ImageError) -> Self {
241 Self::Image(error)
242 }
243}
244
245#[derive(Debug, Clone, Copy, PartialEq, Eq)]
247pub struct GlyphUploadReport {
248 uploaded_bytes: usize,
249 inserted_entry: bool,
250}
251
252impl GlyphUploadReport {
253 pub const fn uploaded_bytes(self) -> usize {
255 self.uploaded_bytes
256 }
257
258 pub const fn inserted_entry(self) -> bool {
260 self.inserted_entry
261 }
262}
263
264pub struct GlyphAtlas2d {
270 pub(super) image: Image2d,
271 entries: Vec<GlyphAtlasEntry>,
272 budget: GlyphAtlasBudget,
273}
274
275impl GlyphAtlas2d {
276 pub const fn size(&self) -> (u32, u32) {
278 self.image.size()
279 }
280
281 pub fn entries(&self) -> &[GlyphAtlasEntry] {
283 &self.entries
284 }
285
286 pub fn source_for(&self, glyph: GlyphId) -> Option<ImageTexelRect> {
288 find_entry(&self.entries, glyph).map(GlyphAtlasEntry::source)
289 }
290
291 pub const fn budget(&self) -> GlyphAtlasBudget {
293 self.budget
294 }
295
296 pub fn recovery_memory_bytes(&self) -> usize {
298 self.image.recovery_memory_bytes().saturating_add(
299 self.entries
300 .capacity()
301 .saturating_mul(std::mem::size_of::<GlyphAtlasEntry>()),
302 )
303 }
304
305 pub fn gpu_allocation_bytes(&self) -> usize {
308 self.image.gpu_allocation_bytes()
309 }
310}
311
312#[derive(Debug, Clone, Copy, PartialEq)]
314pub struct PositionedGlyph2d {
315 glyph: GlyphId,
316 destination: LogicalViewportRegion,
317 tint: Color,
318}
319
320impl PositionedGlyph2d {
321 pub fn new(
323 glyph: GlyphId,
324 destination: LogicalViewportRegion,
325 tint: Color,
326 ) -> Result<Self, GlyphError> {
327 if !tint.is_normalized() || !logical_region_arithmetic_is_finite(destination) {
328 return Err(GlyphError::InvalidGlyph);
329 }
330 Ok(Self {
331 glyph,
332 destination,
333 tint,
334 })
335 }
336
337 pub const fn glyph(self) -> GlyphId {
339 self.glyph
340 }
341
342 pub const fn destination(self) -> LogicalViewportRegion {
344 self.destination
345 }
346
347 pub const fn tint(self) -> Color {
349 self.tint
350 }
351}
352
353#[derive(Debug, Clone, Copy, PartialEq)]
355pub struct GlyphRunBounds {
356 region: Option<LogicalViewportRegion>,
357}
358
359impl GlyphRunBounds {
360 pub const fn region(self) -> Option<LogicalViewportRegion> {
362 self.region
363 }
364
365 pub const fn is_empty(self) -> bool {
367 self.region.is_none()
368 }
369}
370
371#[derive(Debug, Clone, Copy, PartialEq, Eq)]
373pub struct GlyphRunStatistics {
374 submitted_glyphs: usize,
375 rendered_quads: usize,
376 atlas_misses: usize,
377 retained_bytes: usize,
378}
379
380impl GlyphRunStatistics {
381 pub const fn submitted_glyphs(self) -> usize {
383 self.submitted_glyphs
384 }
385
386 pub const fn rendered_quads(self) -> usize {
388 self.rendered_quads
389 }
390
391 pub const fn atlas_misses(self) -> usize {
393 self.atlas_misses
394 }
395
396 pub const fn retained_bytes(self) -> usize {
398 self.retained_bytes
399 }
400}
401
402pub struct GlyphRun2d {
409 pub(super) batch: ImageBatch2d,
410 glyphs: Vec<PositionedGlyph2d>,
411 bounds: GlyphRunBounds,
412 budget: GlyphRunBudget,
413}
414
415#[derive(Debug, Clone, Copy, PartialEq, Eq)]
417pub struct GlyphRunUploadReport {
418 batch: ImageBatchUploadReport,
419 capacity: usize,
420 retained_bytes: usize,
421 peak_retained_bytes: usize,
422}
423
424impl GlyphRunUploadReport {
425 pub const fn glyph_count(self) -> usize {
427 self.batch.sprite_count()
428 }
429 pub const fn capacity(self) -> usize {
431 self.capacity
432 }
433 pub const fn instances(self) -> ImageBatchUploadReport {
435 self.batch
436 }
437 pub const fn retained_bytes(self) -> usize {
439 self.retained_bytes
440 }
441 pub const fn peak_retained_bytes(self) -> usize {
443 self.peak_retained_bytes
444 }
445}
446
447impl GlyphRun2d {
448 pub fn glyphs(&self) -> &[PositionedGlyph2d] {
450 &self.glyphs
451 }
452
453 pub fn glyph_count(&self) -> usize {
455 self.glyphs.len()
456 }
457
458 pub fn capacity(&self) -> usize {
460 self.glyphs.capacity().min(self.batch.capacity())
461 }
462
463 pub const fn bounds(&self) -> GlyphRunBounds {
465 self.bounds
466 }
467
468 pub const fn budget(&self) -> GlyphRunBudget {
470 self.budget
471 }
472
473 pub fn statistics(&self) -> GlyphRunStatistics {
475 GlyphRunStatistics {
476 submitted_glyphs: self.glyphs.len(),
477 rendered_quads: self.glyphs.len(),
478 atlas_misses: 0,
479 retained_bytes: self.recovery_memory_bytes(),
480 }
481 }
482
483 pub fn recovery_memory_bytes(&self) -> usize {
485 self.glyphs
486 .capacity()
487 .saturating_mul(std::mem::size_of::<PositionedGlyph2d>())
488 .saturating_add(self.batch.recovery_memory_bytes())
489 }
490
491 pub fn gpu_allocation_bytes(&self) -> usize {
493 self.batch.gpu_allocation_bytes()
494 }
495}
496
497impl WgpuRenderer {
498 pub fn create_glyph_atlas(
500 &self,
501 width: u32,
502 height: u32,
503 pixels: Vec<u8>,
504 entries: Vec<GlyphAtlasEntry>,
505 budget: GlyphAtlasBudget,
506 ) -> Result<GlyphAtlas2d, GlyphError> {
507 create_glyph_atlas_resources(
508 &self.device,
509 &self.queue,
510 Arc::clone(&self.renderer_identity),
511 width,
512 height,
513 pixels,
514 entries,
515 budget,
516 )
517 }
518
519 pub fn upload_glyph(
525 &self,
526 atlas: &mut GlyphAtlas2d,
527 entry: GlyphAtlasEntry,
528 pixels: &[u8],
529 ) -> Result<GlyphUploadReport, GlyphError> {
530 self.validate_image(&atlas.image)?;
531 if !entry.source.fits(atlas.image.width(), atlas.image.height()) {
532 return Err(GlyphError::InvalidGlyph);
533 }
534 image::validate_image_region_upload(&atlas.image, entry.source, pixels.len())?;
535 let insertion = validate_glyph_insertion(&atlas.entries, entry)?;
536 if insertion.is_some() {
537 validate_metadata_capacity(atlas.entries.len().saturating_add(1), atlas.budget)?;
538 }
539 let replacement_entries = if let Some(index) = insertion {
540 let new_len = atlas.entries.len() + 1;
541 let requested_bytes = new_len
542 .checked_mul(std::mem::size_of::<GlyphAtlasEntry>())
543 .ok_or(GlyphError::InvalidGlyph)?;
544 let mut replacement = Vec::new();
545 replacement
546 .try_reserve_exact(new_len)
547 .map_err(|_| GlyphError::AllocationFailed { requested_bytes })?;
548 replacement.extend_from_slice(&atlas.entries[..index]);
549 replacement.push(entry);
550 replacement.extend_from_slice(&atlas.entries[index..]);
551 let actual = replacement
552 .capacity()
553 .saturating_mul(std::mem::size_of::<GlyphAtlasEntry>());
554 if actual > atlas.budget.max_metadata_bytes {
555 return Err(GlyphError::MetadataBudgetExceeded {
556 limit: atlas.budget.max_metadata_bytes,
557 actual,
558 });
559 }
560 Some(replacement)
561 } else {
562 None
563 };
564 let report = self.update_image_region(&mut atlas.image, entry.source, pixels)?;
565 if let Some(replacement) = replacement_entries {
566 atlas.entries = replacement;
567 }
568 Ok(GlyphUploadReport {
569 uploaded_bytes: report.uploaded_bytes(),
570 inserted_entry: insertion.is_some(),
571 })
572 }
573
574 pub fn create_glyph_run(
576 &self,
577 atlas: &GlyphAtlas2d,
578 glyphs: Vec<PositionedGlyph2d>,
579 budget: GlyphRunBudget,
580 ) -> Result<GlyphRun2d, GlyphError> {
581 self.validate_image(&atlas.image)?;
582 create_glyph_run_resources(
583 &self.device,
584 &self.queue,
585 Arc::clone(&self.renderer_identity),
586 atlas,
587 glyphs,
588 budget,
589 )
590 }
591
592 pub fn update_glyph_run(
600 &self,
601 atlas: &GlyphAtlas2d,
602 run: &mut GlyphRun2d,
603 glyphs: &[PositionedGlyph2d],
604 ) -> Result<GlyphRunUploadReport, GlyphError> {
605 self.validate_glyph_run(atlas, run)?;
606 update_glyph_run_resources(&self.device, &self.queue, atlas, run, glyphs)
607 }
608
609 pub fn restore_glyph_atlas(&self, source: &GlyphAtlas2d) -> Result<GlyphAtlas2d, GlyphError> {
611 image::validate_image_shape(
612 source.image.width(),
613 source.image.height(),
614 source.image.pixels().len(),
615 source.budget.image,
616 self.device.limits().max_texture_dimension_2d,
617 )?;
618 let mut entries = Vec::new();
619 entries
620 .try_reserve_exact(source.entries.len())
621 .map_err(|_| GlyphError::AllocationFailed {
622 requested_bytes: std::mem::size_of_val(source.entries.as_slice()),
623 })?;
624 entries.extend_from_slice(&source.entries);
625 validate_atlas_entries(
626 &mut entries,
627 source.image.width(),
628 source.image.height(),
629 source.budget,
630 )?;
631 entries = compact_glyph_vec(entries, source.budget.max_metadata_bytes)?;
632 let actual = entries
633 .capacity()
634 .saturating_mul(std::mem::size_of::<GlyphAtlasEntry>());
635 if actual > source.budget.max_metadata_bytes {
636 return Err(GlyphError::MetadataBudgetExceeded {
637 limit: source.budget.max_metadata_bytes,
638 actual,
639 });
640 }
641 let image = self.restore_image(&source.image)?;
642 Ok(GlyphAtlas2d {
643 image,
644 entries,
645 budget: source.budget,
646 })
647 }
648
649 pub fn restore_glyph_run(
651 &self,
652 atlas: &GlyphAtlas2d,
653 source: &GlyphRun2d,
654 ) -> Result<GlyphRun2d, GlyphError> {
655 self.validate_image(&atlas.image)?;
656 if !Arc::ptr_eq(
657 &atlas.image.recovery_identity,
658 &source.batch.image_recovery_identity,
659 ) {
660 return Err(ImageError::RecoverySourceMismatch.into());
661 }
662 validate_glyph_run_sources(&atlas.entries, &source.glyphs, source.batch.sprites())?;
663 validate_glyph_run_budget(source.glyphs.len(), source.budget)?;
664 validate_glyph_membership(&atlas.entries, &source.glyphs)?;
665 measure_glyphs(&source.glyphs)?;
666 let batch_budget =
667 ImageBatchBudget::new(source.budget.max_glyphs, source.budget.max_retained_bytes)?;
668 image::preflight_image_batch_capacity(&self.device, source.glyphs.len(), batch_budget)?;
669 let retained_bytes = source
670 .glyphs
671 .len()
672 .checked_mul(std::mem::size_of::<PositionedGlyph2d>())
673 .ok_or(GlyphError::InvalidGlyph)?;
674 let mut glyphs = Vec::new();
675 glyphs.try_reserve_exact(source.glyphs.len()).map_err(|_| {
676 GlyphError::AllocationFailed {
677 requested_bytes: retained_bytes,
678 }
679 })?;
680 glyphs.extend_from_slice(&source.glyphs);
681 self.create_glyph_run(atlas, glyphs, source.budget)
682 }
683
684 pub(super) fn validate_glyph_run(
685 &self,
686 atlas: &GlyphAtlas2d,
687 run: &GlyphRun2d,
688 ) -> Result<(), GlyphError> {
689 self.validate_image_batch(&atlas.image, &run.batch)?;
690 Ok(())
691 }
692}
693
694#[allow(clippy::too_many_arguments)]
695pub(super) fn create_glyph_atlas_resources(
696 device: &wgpu::Device,
697 queue: &wgpu::Queue,
698 renderer_identity: Arc<()>,
699 width: u32,
700 height: u32,
701 pixels: Vec<u8>,
702 mut entries: Vec<GlyphAtlasEntry>,
703 budget: GlyphAtlasBudget,
704) -> Result<GlyphAtlas2d, GlyphError> {
705 image::validate_image_shape(
706 width,
707 height,
708 pixels.len(),
709 budget.image,
710 device.limits().max_texture_dimension_2d,
711 )?;
712 validate_atlas_entries(&mut entries, width, height, budget)?;
713 entries = compact_glyph_vec(entries, budget.max_metadata_bytes)?;
714 let actual_metadata_bytes = entries
715 .capacity()
716 .saturating_mul(std::mem::size_of::<GlyphAtlasEntry>());
717 if actual_metadata_bytes > budget.max_metadata_bytes {
718 return Err(GlyphError::MetadataBudgetExceeded {
719 limit: budget.max_metadata_bytes,
720 actual: actual_metadata_bytes,
721 });
722 }
723 let image = image::create_image_resources(
724 device,
725 queue,
726 renderer_identity,
727 width,
728 height,
729 pixels,
730 budget.image,
731 )?;
732 Ok(GlyphAtlas2d {
733 image,
734 entries,
735 budget,
736 })
737}
738
739pub(super) fn create_glyph_run_resources(
740 device: &wgpu::Device,
741 queue: &wgpu::Queue,
742 renderer_identity: Arc<()>,
743 atlas: &GlyphAtlas2d,
744 glyphs: Vec<PositionedGlyph2d>,
745 budget: GlyphRunBudget,
746) -> Result<GlyphRun2d, GlyphError> {
747 validate_glyph_run_budget(glyphs.len(), budget)?;
748 validate_glyph_membership(&atlas.entries, &glyphs)?;
749 let bounds = measure_glyphs(&glyphs)?;
750 let batch_budget = ImageBatchBudget::new(budget.max_glyphs, budget.max_retained_bytes)?;
751 image::preflight_image_batch_capacity(device, glyphs.len(), batch_budget)?;
752 let glyph_byte_limit = budget
753 .max_retained_bytes
754 .saturating_sub(image::batch_retained_bytes(glyphs.len().max(1)));
755 let glyphs = compact_glyph_vec(glyphs, glyph_byte_limit)?;
756 let sprites = resolve_glyph_sprites(&atlas.entries, &glyphs)?;
757 let actual_retained_bytes = glyphs
758 .capacity()
759 .saturating_mul(std::mem::size_of::<PositionedGlyph2d>())
760 .saturating_add(
761 sprites
762 .capacity()
763 .saturating_mul(std::mem::size_of::<ImageSprite2d>()),
764 );
765 if actual_retained_bytes > budget.max_retained_bytes {
766 return Err(GlyphError::MetadataBudgetExceeded {
767 limit: budget.max_retained_bytes,
768 actual: actual_retained_bytes,
769 });
770 }
771 let batch_budget = ImageBatchBudget::new(
772 budget.max_glyphs,
773 budget.max_retained_bytes.saturating_sub(
774 glyphs
775 .capacity()
776 .saturating_mul(std::mem::size_of::<PositionedGlyph2d>()),
777 ),
778 )?;
779 let batch = image::create_image_batch_resources(
780 device,
781 queue,
782 renderer_identity,
783 &atlas.image,
784 sprites,
785 batch_budget,
786 )?;
787 Ok(GlyphRun2d {
788 batch,
789 glyphs,
790 bounds,
791 budget,
792 })
793}
794
795pub(super) fn update_glyph_run_resources(
796 device: &wgpu::Device,
797 queue: &wgpu::Queue,
798 atlas: &GlyphAtlas2d,
799 run: &mut GlyphRun2d,
800 glyphs: &[PositionedGlyph2d],
801) -> Result<GlyphRunUploadReport, GlyphError> {
802 validate_glyph_run_budget(glyphs.len(), run.budget)?;
803 image::preflight_image_batch_capacity(
804 device,
805 glyphs.len(),
806 ImageBatchBudget::new(run.budget.max_glyphs, run.budget.max_retained_bytes)?,
807 )?;
808 validate_glyph_membership(&atlas.entries, glyphs)?;
809 if glyphs.iter().any(|glyph| !glyph.tint.is_normalized()) {
810 return Err(GlyphError::InvalidGlyph);
811 }
812 let bounds = measure_glyphs(glyphs)?;
813 let old_glyph_bytes = run
814 .glyphs
815 .capacity()
816 .saturating_mul(std::mem::size_of::<PositionedGlyph2d>());
817 let mut replacement = if glyphs.len() > run.glyphs.capacity() {
818 let mut values = Vec::new();
819 values
820 .try_reserve_exact(glyphs.len())
821 .map_err(|_| GlyphError::AllocationFailed {
822 requested_bytes: std::mem::size_of_val(glyphs),
823 })?;
824 Some(values)
825 } else {
826 None
827 };
828 let glyph_capacity = replacement
829 .as_ref()
830 .map_or(run.glyphs.capacity(), Vec::capacity);
831 let glyph_bytes = glyph_capacity.saturating_mul(std::mem::size_of::<PositionedGlyph2d>());
832 let batch_budget = ImageBatchBudget::new(
833 run.budget.max_glyphs,
834 run.budget.max_retained_bytes.saturating_sub(glyph_bytes),
835 )?;
836 let sprites = glyphs.iter().filter_map(|glyph| {
839 let source = find_entry(&atlas.entries, glyph.glyph)?.source;
840 ImageSprite2d::new(source, glyph.destination, glyph.tint).ok()
841 });
842 let batch = image::update_image_batch_resources(
843 device,
844 queue,
845 &atlas.image,
846 &mut run.batch,
847 sprites,
848 glyphs.len(),
849 batch_budget,
850 )?;
851 let peak_retained_bytes = batch
852 .peak_retained_bytes()
853 .saturating_add(old_glyph_bytes)
854 .saturating_add(if replacement.is_some() {
855 glyph_bytes
856 } else {
857 0
858 });
859 if let Some(values) = replacement.take() {
860 run.glyphs = values;
861 }
862 run.glyphs.clear();
863 run.glyphs.extend_from_slice(glyphs);
864 run.bounds = bounds;
865 Ok(GlyphRunUploadReport {
866 batch,
867 capacity: run.capacity(),
868 retained_bytes: run.recovery_memory_bytes(),
869 peak_retained_bytes,
870 })
871}
872
873fn compact_glyph_vec<T: Copy>(values: Vec<T>, maximum_bytes: usize) -> Result<Vec<T>, GlyphError> {
874 if values.capacity().saturating_mul(std::mem::size_of::<T>()) <= maximum_bytes {
875 return Ok(values);
876 }
877 let requested_bytes = values
878 .len()
879 .checked_mul(std::mem::size_of::<T>())
880 .ok_or(GlyphError::InvalidGlyph)?;
881 let mut compact = Vec::new();
882 compact
883 .try_reserve_exact(values.len())
884 .map_err(|_| GlyphError::AllocationFailed { requested_bytes })?;
885 compact.extend_from_slice(&values);
886 Ok(compact)
887}
888
889fn validate_atlas_entries(
890 entries: &mut [GlyphAtlasEntry],
891 width: u32,
892 height: u32,
893 budget: GlyphAtlasBudget,
894) -> Result<(), GlyphError> {
895 validate_metadata_capacity(entries.len(), budget)?;
896 entries.sort_unstable_by_key(|entry| entry.glyph);
897 for (index, entry) in entries.iter().enumerate() {
898 if !entry.source.fits(width, height) {
899 return Err(GlyphError::InvalidGlyph);
900 }
901 if index > 0 && entries[index - 1].glyph == entry.glyph {
902 return Err(GlyphError::DuplicateGlyph { glyph: entry.glyph });
903 }
904 }
905 validate_non_overlapping_glyph_entries(entries)
906}
907
908#[derive(Clone, Copy)]
909struct GlyphSweepEvent {
910 x: u32,
911 starts: bool,
912 entry_index: usize,
913 minimum_y: u32,
914 maximum_y: u32,
915}
916
917fn validate_non_overlapping_glyph_entries(entries: &[GlyphAtlasEntry]) -> Result<(), GlyphError> {
918 if entries.len() < 2 {
919 return Ok(());
920 }
921 let endpoint_count = entries
922 .len()
923 .checked_mul(2)
924 .ok_or(GlyphError::InvalidGlyph)?;
925 let mut events = Vec::new();
926 events
927 .try_reserve_exact(endpoint_count)
928 .map_err(|_| GlyphError::AllocationFailed {
929 requested_bytes: endpoint_count.saturating_mul(std::mem::size_of::<GlyphSweepEvent>()),
930 })?;
931 let mut vertical_coordinates = Vec::new();
932 vertical_coordinates
933 .try_reserve_exact(endpoint_count)
934 .map_err(|_| GlyphError::AllocationFailed {
935 requested_bytes: endpoint_count.saturating_mul(std::mem::size_of::<u32>()),
936 })?;
937 for (entry_index, entry) in entries.iter().copied().enumerate() {
938 let source = entry.source;
939 let maximum_x = source
940 .x()
941 .checked_add(source.width())
942 .ok_or(GlyphError::InvalidGlyph)?;
943 let maximum_y = source
944 .y()
945 .checked_add(source.height())
946 .ok_or(GlyphError::InvalidGlyph)?;
947 events.push(GlyphSweepEvent {
948 x: source.x(),
949 starts: true,
950 entry_index,
951 minimum_y: source.y(),
952 maximum_y,
953 });
954 events.push(GlyphSweepEvent {
955 x: maximum_x,
956 starts: false,
957 entry_index,
958 minimum_y: source.y(),
959 maximum_y,
960 });
961 vertical_coordinates.push(source.y());
962 vertical_coordinates.push(maximum_y);
963 }
964 events.sort_unstable_by_key(|event| (event.x, event.starts));
967 vertical_coordinates.sort_unstable();
968 vertical_coordinates.dedup();
969 let interval_count = vertical_coordinates.len().saturating_sub(1);
970 let tree_len = interval_count
971 .checked_mul(4)
972 .and_then(|value| value.checked_add(4))
973 .ok_or(GlyphError::InvalidGlyph)?;
974 let mut maximum_coverage = Vec::new();
975 maximum_coverage
976 .try_reserve_exact(tree_len)
977 .map_err(|_| GlyphError::AllocationFailed {
978 requested_bytes: tree_len.saturating_mul(std::mem::size_of::<i32>()),
979 })?;
980 maximum_coverage.resize(tree_len, 0_i32);
981 let mut lazy_coverage = Vec::new();
982 lazy_coverage
983 .try_reserve_exact(tree_len)
984 .map_err(|_| GlyphError::AllocationFailed {
985 requested_bytes: tree_len.saturating_mul(std::mem::size_of::<i32>()),
986 })?;
987 lazy_coverage.resize(tree_len, 0_i32);
988 let mut active = Vec::new();
989 active
990 .try_reserve_exact(entries.len())
991 .map_err(|_| GlyphError::AllocationFailed {
992 requested_bytes: entries.len().saturating_mul(std::mem::size_of::<bool>()),
993 })?;
994 active.resize(entries.len(), false);
995
996 for event in events {
997 let minimum = vertical_coordinates
998 .binary_search(&event.minimum_y)
999 .expect("glyph sweep endpoints came from the coordinate set");
1000 let maximum = vertical_coordinates
1001 .binary_search(&event.maximum_y)
1002 .expect("glyph sweep endpoints came from the coordinate set");
1003 if event.starts {
1004 if glyph_coverage_max(
1005 &maximum_coverage,
1006 &lazy_coverage,
1007 1,
1008 0,
1009 interval_count,
1010 minimum,
1011 maximum,
1012 ) > 0
1013 {
1014 let entry = entries[event.entry_index];
1015 let conflict = active
1016 .iter()
1017 .enumerate()
1018 .find(|(index, active)| {
1019 **active && glyph_rectangles_overlap(entries[*index].source, entry.source)
1020 })
1021 .map(|(index, _)| entries[index].glyph)
1022 .expect("positive sweep coverage has an active owning glyph");
1023 return Err(GlyphError::OverlappingGlyph {
1024 glyph: entry.glyph,
1025 conflicting_glyph: conflict,
1026 });
1027 }
1028 glyph_coverage_add(
1029 &mut maximum_coverage,
1030 &mut lazy_coverage,
1031 1,
1032 0,
1033 interval_count,
1034 minimum,
1035 maximum,
1036 1,
1037 );
1038 active[event.entry_index] = true;
1039 } else {
1040 glyph_coverage_add(
1041 &mut maximum_coverage,
1042 &mut lazy_coverage,
1043 1,
1044 0,
1045 interval_count,
1046 minimum,
1047 maximum,
1048 -1,
1049 );
1050 active[event.entry_index] = false;
1051 }
1052 }
1053 Ok(())
1054}
1055
1056#[allow(clippy::too_many_arguments)]
1057fn glyph_coverage_add(
1058 maximum_coverage: &mut [i32],
1059 lazy_coverage: &mut [i32],
1060 node: usize,
1061 left: usize,
1062 right: usize,
1063 query_left: usize,
1064 query_right: usize,
1065 amount: i32,
1066) {
1067 if query_left <= left && right <= query_right {
1068 maximum_coverage[node] += amount;
1069 lazy_coverage[node] += amount;
1070 return;
1071 }
1072 let middle = left + (right - left) / 2;
1073 if query_left < middle {
1074 glyph_coverage_add(
1075 maximum_coverage,
1076 lazy_coverage,
1077 node * 2,
1078 left,
1079 middle,
1080 query_left,
1081 query_right,
1082 amount,
1083 );
1084 }
1085 if query_right > middle {
1086 glyph_coverage_add(
1087 maximum_coverage,
1088 lazy_coverage,
1089 node * 2 + 1,
1090 middle,
1091 right,
1092 query_left,
1093 query_right,
1094 amount,
1095 );
1096 }
1097 maximum_coverage[node] =
1098 lazy_coverage[node] + maximum_coverage[node * 2].max(maximum_coverage[node * 2 + 1]);
1099}
1100
1101#[allow(clippy::too_many_arguments)]
1102fn glyph_coverage_max(
1103 maximum_coverage: &[i32],
1104 lazy_coverage: &[i32],
1105 node: usize,
1106 left: usize,
1107 right: usize,
1108 query_left: usize,
1109 query_right: usize,
1110) -> i32 {
1111 if query_left <= left && right <= query_right {
1112 return maximum_coverage[node];
1113 }
1114 let middle = left + (right - left) / 2;
1115 let mut maximum = 0;
1116 if query_left < middle {
1117 maximum = maximum.max(glyph_coverage_max(
1118 maximum_coverage,
1119 lazy_coverage,
1120 node * 2,
1121 left,
1122 middle,
1123 query_left,
1124 query_right,
1125 ));
1126 }
1127 if query_right > middle {
1128 maximum = maximum.max(glyph_coverage_max(
1129 maximum_coverage,
1130 lazy_coverage,
1131 node * 2 + 1,
1132 middle,
1133 right,
1134 query_left,
1135 query_right,
1136 ));
1137 }
1138 lazy_coverage[node] + maximum
1139}
1140
1141fn validate_glyph_insertion(
1142 entries: &[GlyphAtlasEntry],
1143 entry: GlyphAtlasEntry,
1144) -> Result<Option<usize>, GlyphError> {
1145 match entries.binary_search_by_key(&entry.glyph, |candidate| candidate.glyph) {
1146 Ok(index) => {
1147 if entries[index].source != entry.source {
1148 return Err(GlyphError::DuplicateGlyph { glyph: entry.glyph });
1149 }
1150 Ok(None)
1151 }
1152 Err(index) => {
1153 if let Some(conflict) = entries
1154 .iter()
1155 .find(|candidate| glyph_rectangles_overlap(candidate.source, entry.source))
1156 {
1157 return Err(GlyphError::OverlappingGlyph {
1158 glyph: entry.glyph,
1159 conflicting_glyph: conflict.glyph,
1160 });
1161 }
1162 Ok(Some(index))
1163 }
1164 }
1165}
1166
1167fn glyph_rectangles_overlap(left: ImageTexelRect, right: ImageTexelRect) -> bool {
1168 let left_max_x = u64::from(left.x()) + u64::from(left.width());
1169 let left_max_y = u64::from(left.y()) + u64::from(left.height());
1170 let right_max_x = u64::from(right.x()) + u64::from(right.width());
1171 let right_max_y = u64::from(right.y()) + u64::from(right.height());
1172 u64::from(left.x()) < right_max_x
1173 && u64::from(right.x()) < left_max_x
1174 && u64::from(left.y()) < right_max_y
1175 && u64::from(right.y()) < left_max_y
1176}
1177
1178fn validate_metadata_capacity(
1179 entry_count: usize,
1180 budget: GlyphAtlasBudget,
1181) -> Result<(), GlyphError> {
1182 if entry_count > budget.max_entries {
1183 return Err(GlyphError::EntryBudgetExceeded {
1184 limit: budget.max_entries,
1185 actual: entry_count,
1186 });
1187 }
1188 let bytes = entry_count
1189 .checked_mul(std::mem::size_of::<GlyphAtlasEntry>())
1190 .ok_or(GlyphError::InvalidGlyph)?;
1191 if bytes > budget.max_metadata_bytes {
1192 return Err(GlyphError::MetadataBudgetExceeded {
1193 limit: budget.max_metadata_bytes,
1194 actual: bytes,
1195 });
1196 }
1197 Ok(())
1198}
1199
1200pub(super) fn validate_glyph_run_budget(
1201 glyph_count: usize,
1202 budget: GlyphRunBudget,
1203) -> Result<(), GlyphError> {
1204 if glyph_count > budget.max_glyphs {
1205 return Err(GlyphError::EntryBudgetExceeded {
1206 limit: budget.max_glyphs,
1207 actual: glyph_count,
1208 });
1209 }
1210 let retained_bytes = glyph_retained_bytes(glyph_count).ok_or(GlyphError::InvalidGlyph)?;
1211 if retained_bytes > budget.max_retained_bytes {
1212 return Err(GlyphError::MetadataBudgetExceeded {
1213 limit: budget.max_retained_bytes,
1214 actual: retained_bytes,
1215 });
1216 }
1217 Ok(())
1218}
1219
1220fn glyph_retained_bytes(glyph_count: usize) -> Option<usize> {
1221 glyph_count.checked_mul(GlyphRunBudget::RETAINED_BYTES_PER_GLYPH)
1222}
1223
1224fn find_entry(entries: &[GlyphAtlasEntry], glyph: GlyphId) -> Option<GlyphAtlasEntry> {
1225 entries
1226 .binary_search_by_key(&glyph, |entry| entry.glyph)
1227 .ok()
1228 .map(|index| entries[index])
1229}
1230
1231fn resolve_glyph_sprites(
1232 entries: &[GlyphAtlasEntry],
1233 glyphs: &[PositionedGlyph2d],
1234) -> Result<Vec<ImageSprite2d>, GlyphError> {
1235 validate_glyph_membership(entries, glyphs)?;
1236 let mut sprites = Vec::new();
1237 sprites
1238 .try_reserve_exact(glyphs.len())
1239 .map_err(|_| GlyphError::AllocationFailed {
1240 requested_bytes: glyphs
1241 .len()
1242 .saturating_mul(std::mem::size_of::<ImageSprite2d>()),
1243 })?;
1244 for (index, glyph) in glyphs.iter().copied().enumerate() {
1245 let source = find_entry(entries, glyph.glyph)
1246 .map(GlyphAtlasEntry::source)
1247 .ok_or(GlyphError::MissingGlyph {
1249 glyph: glyph.glyph,
1250 index,
1251 })?;
1252 sprites.push(ImageSprite2d::new(source, glyph.destination, glyph.tint)?);
1253 }
1254 Ok(sprites)
1255}
1256
1257fn validate_glyph_membership(
1258 entries: &[GlyphAtlasEntry],
1259 glyphs: &[PositionedGlyph2d],
1260) -> Result<(), GlyphError> {
1261 if let Some((index, glyph)) = glyphs
1262 .iter()
1263 .enumerate()
1264 .find(|(_, glyph)| find_entry(entries, glyph.glyph).is_none())
1265 {
1266 return Err(GlyphError::MissingGlyph {
1267 glyph: glyph.glyph,
1268 index,
1269 });
1270 }
1271 Ok(())
1272}
1273
1274fn validate_glyph_run_sources(
1275 entries: &[GlyphAtlasEntry],
1276 glyphs: &[PositionedGlyph2d],
1277 sprites: &[ImageSprite2d],
1278) -> Result<(), GlyphError> {
1279 if glyphs.len() != sprites.len()
1280 || glyphs.iter().zip(sprites).any(|(glyph, sprite)| {
1281 find_entry(entries, glyph.glyph).map(GlyphAtlasEntry::source) != Some(sprite.source())
1282 })
1283 {
1284 return Err(ImageError::RecoverySourceMismatch.into());
1285 }
1286 Ok(())
1287}
1288
1289fn measure_glyphs(glyphs: &[PositionedGlyph2d]) -> Result<GlyphRunBounds, GlyphError> {
1290 if glyphs
1291 .iter()
1292 .any(|glyph| !image::logical_image_region_is_portable(glyph.destination))
1293 {
1294 return Err(GlyphError::InvalidGlyph);
1295 }
1296 let Some(first) = glyphs.first().copied() else {
1297 return Ok(GlyphRunBounds { region: None });
1298 };
1299 let first_origin = first.destination.origin().to_vec2();
1300 let first_size = first.destination.viewport().size();
1301 let mut minimum = first_origin;
1302 let mut maximum = first_origin + first_size;
1303 for glyph in &glyphs[1..] {
1304 if !logical_region_arithmetic_is_finite(glyph.destination) {
1305 return Err(GlyphError::InvalidGlyph);
1306 }
1307 let origin = glyph.destination.origin().to_vec2();
1308 let end = origin + glyph.destination.viewport().size();
1309 minimum.x = minimum.x.min(origin.x);
1310 minimum.y = minimum.y.min(origin.y);
1311 maximum.x = maximum.x.max(end.x);
1312 maximum.y = maximum.y.max(end.y);
1313 }
1314 if !minimum.is_finite() || !maximum.is_finite() {
1315 return Err(GlyphError::InvalidGlyph);
1316 }
1317 let viewport = LogicalViewport::new(maximum.x - minimum.x, maximum.y - minimum.y)
1318 .map_err(|_| GlyphError::InvalidGlyph)?;
1319 let region = LogicalViewportRegion::new(LogicalScreenPosition::from_vec2(minimum), viewport)
1320 .map_err(|_| GlyphError::InvalidGlyph)?;
1321 Ok(GlyphRunBounds {
1322 region: Some(region),
1323 })
1324}
1325
1326fn logical_region_arithmetic_is_finite(region: LogicalViewportRegion) -> bool {
1327 let origin = region.origin().to_vec2();
1328 let end = origin + region.viewport().size();
1329 origin.is_finite() && end.is_finite()
1330}
1331
1332#[cfg(test)]
1333mod tests {
1334 use super::*;
1335
1336 fn rectangle(x: u32) -> ImageTexelRect {
1337 ImageTexelRect::new(x, 0, 1, 1).unwrap()
1338 }
1339
1340 fn positioned(glyph: u32, x: f32) -> PositionedGlyph2d {
1341 PositionedGlyph2d::new(
1342 GlyphId::new(glyph),
1343 LogicalViewportRegion::new(
1344 LogicalScreenPosition::new(x, 2.0),
1345 LogicalViewport::new(4.0, 6.0).unwrap(),
1346 )
1347 .unwrap(),
1348 Color::WHITE,
1349 )
1350 .unwrap()
1351 }
1352
1353 #[test]
1354 fn atlas_entries_sort_and_reject_duplicate_or_out_of_bounds_glyphs() {
1355 let budget = GlyphAtlasBudget::default();
1356 let mut entries = vec![
1357 GlyphAtlasEntry::new(GlyphId::new(2), rectangle(1)),
1358 GlyphAtlasEntry::new(GlyphId::new(1), rectangle(0)),
1359 ];
1360 assert_eq!(validate_atlas_entries(&mut entries, 2, 1, budget), Ok(()));
1361 assert_eq!(entries[0].glyph(), GlyphId::new(1));
1362
1363 let mut duplicate = vec![
1364 GlyphAtlasEntry::new(GlyphId::new(7), rectangle(0)),
1365 GlyphAtlasEntry::new(GlyphId::new(7), rectangle(1)),
1366 ];
1367 assert_eq!(
1368 validate_atlas_entries(&mut duplicate, 2, 1, budget),
1369 Err(GlyphError::DuplicateGlyph {
1370 glyph: GlyphId::new(7)
1371 })
1372 );
1373
1374 let mut outside = vec![GlyphAtlasEntry::new(GlyphId::new(9), rectangle(2))];
1375 assert_eq!(
1376 validate_atlas_entries(&mut outside, 2, 1, budget),
1377 Err(GlyphError::InvalidGlyph)
1378 );
1379
1380 let mut overlapping = vec![
1381 GlyphAtlasEntry::new(GlyphId::new(10), ImageTexelRect::new(0, 0, 2, 2).unwrap()),
1382 GlyphAtlasEntry::new(GlyphId::new(11), ImageTexelRect::new(1, 1, 2, 2).unwrap()),
1383 ];
1384 assert_eq!(
1385 validate_atlas_entries(&mut overlapping, 4, 4, budget),
1386 Err(GlyphError::OverlappingGlyph {
1387 glyph: GlyphId::new(11),
1388 conflicting_glyph: GlyphId::new(10),
1389 })
1390 );
1391 }
1392
1393 #[test]
1394 fn incremental_glyph_overlap_is_rejected_before_metadata_or_pixel_update() {
1395 let entries = [GlyphAtlasEntry::new(
1396 GlyphId::new(1),
1397 ImageTexelRect::new(0, 0, 4, 4).unwrap(),
1398 )];
1399 let overlapping =
1400 GlyphAtlasEntry::new(GlyphId::new(2), ImageTexelRect::new(3, 0, 4, 4).unwrap());
1401 assert_eq!(
1402 validate_glyph_insertion(&entries, overlapping),
1403 Err(GlyphError::OverlappingGlyph {
1404 glyph: GlyphId::new(2),
1405 conflicting_glyph: GlyphId::new(1),
1406 })
1407 );
1408 assert_eq!(entries.len(), 1);
1409
1410 let adjacent =
1411 GlyphAtlasEntry::new(GlyphId::new(2), ImageTexelRect::new(4, 0, 4, 4).unwrap());
1412 assert_eq!(validate_glyph_insertion(&entries, adjacent), Ok(Some(1)));
1413
1414 let below = GlyphAtlasEntry::new(GlyphId::new(2), ImageTexelRect::new(0, 8, 4, 4).unwrap());
1415 assert_eq!(validate_glyph_insertion(&entries, below), Ok(Some(1)));
1416
1417 let entries_below = [GlyphAtlasEntry::new(
1418 GlyphId::new(1),
1419 ImageTexelRect::new(0, 8, 4, 4).unwrap(),
1420 )];
1421 let above = GlyphAtlasEntry::new(GlyphId::new(2), ImageTexelRect::new(0, 0, 4, 4).unwrap());
1422 assert_eq!(validate_glyph_insertion(&entries_below, above), Ok(Some(1)));
1423 }
1424
1425 #[test]
1426 fn default_maximum_non_overlapping_atlas_validation_is_subquadratic() {
1427 let mut entries = Vec::with_capacity(65_536);
1428 for glyph in 0..65_536_u32 {
1429 entries.push(GlyphAtlasEntry::new(
1430 GlyphId::new(glyph),
1431 ImageTexelRect::new(glyph % 256, glyph / 256, 1, 1).unwrap(),
1432 ));
1433 }
1434 assert_eq!(
1435 validate_atlas_entries(&mut entries, 256, 256, GlyphAtlasBudget::default()),
1436 Ok(())
1437 );
1438 }
1439
1440 #[test]
1441 fn positioned_run_resolves_opaque_scientific_glyphs_and_measures_bounds() {
1442 let entries = [
1443 GlyphAtlasEntry::new(GlyphId::new('Δ' as u32), rectangle(1)),
1444 GlyphAtlasEntry::new(GlyphId::new('μ' as u32), rectangle(0)),
1445 GlyphAtlasEntry::new(GlyphId::new('∫' as u32), rectangle(2)),
1446 ];
1447 let glyphs = [
1448 positioned('μ' as u32, 1.0),
1449 positioned('Δ' as u32, 5.0),
1450 positioned('∫' as u32, 9.0),
1451 ];
1452 assert_eq!(resolve_glyph_sprites(&entries, &glyphs).unwrap().len(), 3);
1453 let bounds = measure_glyphs(&glyphs).unwrap().region().unwrap();
1454 assert_eq!(bounds.origin(), LogicalScreenPosition::new(1.0, 2.0));
1455 assert_eq!(bounds.viewport().size(), Vec2::new(12.0, 6.0));
1456
1457 let missing = [positioned('Σ' as u32, 1.0)];
1458 assert_eq!(
1459 resolve_glyph_sprites(&entries, &missing),
1460 Err(GlyphError::MissingGlyph {
1461 glyph: GlyphId::new('Σ' as u32),
1462 index: 0,
1463 })
1464 );
1465 }
1466
1467 #[test]
1468 fn glyph_run_recovery_rejects_forked_atlas_mapping() {
1469 let glyph = positioned(42, 1.0);
1470 let left = rectangle(0);
1471 let right = rectangle(1);
1472 let source_entries = [GlyphAtlasEntry::new(GlyphId::new(42), left)];
1473 let forked_entries = [GlyphAtlasEntry::new(GlyphId::new(42), right)];
1474 let source_sprites = [ImageSprite2d::new(left, glyph.destination(), glyph.tint()).unwrap()];
1475
1476 assert_eq!(
1477 validate_glyph_run_sources(&source_entries, &[glyph], &source_sprites),
1478 Ok(())
1479 );
1480 assert_eq!(
1481 validate_glyph_run_sources(&forked_entries, &[glyph], &source_sprites),
1482 Err(GlyphError::Image(ImageError::RecoverySourceMismatch))
1483 );
1484 }
1485}