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