xref: /aosp_15_r20/external/harfbuzz_ng/src/OT/Layout/Common/CoverageFormat2.hh (revision 2d1272b857b1f7575e6e246373e1cb218663db8a)
1 /*
2  * Copyright © 2007,2008,2009  Red Hat, Inc.
3  * Copyright © 2010,2012  Google, Inc.
4  *
5  *  This is part of HarfBuzz, a text shaping library.
6  *
7  * Permission is hereby granted, without written agreement and without
8  * license or royalty fees, to use, copy, modify, and distribute this
9  * software and its documentation for any purpose, provided that the
10  * above copyright notice and the following two paragraphs appear in
11  * all copies of this software.
12  *
13  * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR
14  * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
15  * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
16  * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
17  * DAMAGE.
18  *
19  * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,
20  * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
21  * FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS
22  * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO
23  * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
24  *
25  * Red Hat Author(s): Behdad Esfahbod
26  * Google Author(s): Behdad Esfahbod, Garret Rieger
27  */
28 
29 #ifndef OT_LAYOUT_COMMON_COVERAGEFORMAT2_HH
30 #define OT_LAYOUT_COMMON_COVERAGEFORMAT2_HH
31 
32 #include "RangeRecord.hh"
33 
34 namespace OT {
35 namespace Layout {
36 namespace Common {
37 
38 template <typename Types>
39 struct CoverageFormat2_4
40 {
41   friend struct Coverage;
42 
43   protected:
44   HBUINT16      coverageFormat; /* Format identifier--format = 2 */
45   SortedArray16Of<RangeRecord<Types>>
46                 rangeRecord;    /* Array of glyph ranges--ordered by
47                                  * Start GlyphID. rangeCount entries
48                                  * long */
49   public:
50   DEFINE_SIZE_ARRAY (4, rangeRecord);
51 
52   private:
53 
sanitizeOT::Layout::Common::CoverageFormat2_454   bool sanitize (hb_sanitize_context_t *c) const
55   {
56     TRACE_SANITIZE (this);
57     return_trace (rangeRecord.sanitize (c));
58   }
59 
get_coverageOT::Layout::Common::CoverageFormat2_460   unsigned int get_coverage (hb_codepoint_t glyph_id) const
61   {
62     const RangeRecord<Types> &range = rangeRecord.bsearch (glyph_id);
63     return likely (range.first <= range.last)
64          ? (unsigned int) range.value + (glyph_id - range.first)
65          : NOT_COVERED;
66   }
67 
get_populationOT::Layout::Common::CoverageFormat2_468   unsigned get_population () const
69   {
70     typename Types::large_int ret = 0;
71     for (const auto &r : rangeRecord)
72       ret += r.get_population ();
73     return ret > UINT_MAX ? UINT_MAX : (unsigned) ret;
74   }
75 
76   template <typename Iterator,
77       hb_requires (hb_is_sorted_source_of (Iterator, hb_codepoint_t))>
serializeOT::Layout::Common::CoverageFormat2_478   bool serialize (hb_serialize_context_t *c, Iterator glyphs)
79   {
80     TRACE_SERIALIZE (this);
81     if (unlikely (!c->extend_min (this))) return_trace (false);
82 
83     unsigned num_ranges = 0;
84     hb_codepoint_t last = (hb_codepoint_t) -2;
85     for (auto g: glyphs)
86     {
87       if (last + 1 != g)
88         num_ranges++;
89       last = g;
90     }
91 
92     if (unlikely (!rangeRecord.serialize (c, num_ranges))) return_trace (false);
93     if (!num_ranges) return_trace (true);
94 
95     unsigned count = 0;
96     unsigned range = (unsigned) -1;
97     last = (hb_codepoint_t) -2;
98     unsigned unsorted = false;
99     for (auto g: glyphs)
100     {
101       if (last + 1 != g)
102       {
103 	if (unlikely (last != (hb_codepoint_t) -2 && last + 1 > g))
104 	  unsorted = true;
105 
106         range++;
107         rangeRecord.arrayZ[range].first = g;
108         rangeRecord.arrayZ[range].value = count;
109       }
110       rangeRecord.arrayZ[range].last = g;
111       last = g;
112       count++;
113     }
114 
115     if (unlikely (unsorted))
116       rangeRecord.as_array ().qsort (RangeRecord<Types>::cmp_range);
117 
118     return_trace (true);
119   }
120 
intersectsOT::Layout::Common::CoverageFormat2_4121   bool intersects (const hb_set_t *glyphs) const
122   {
123     if (rangeRecord.len > glyphs->get_population () * hb_bit_storage ((unsigned) rangeRecord.len) / 2)
124     {
125       for (auto g : *glyphs)
126         if (get_coverage (g) != NOT_COVERED)
127 	  return true;
128       return false;
129     }
130 
131     return hb_any (+ hb_iter (rangeRecord)
132                    | hb_map ([glyphs] (const RangeRecord<Types> &range) { return range.intersects (*glyphs); }));
133   }
intersects_coverageOT::Layout::Common::CoverageFormat2_4134   bool intersects_coverage (const hb_set_t *glyphs, unsigned int index) const
135   {
136     auto *range = rangeRecord.as_array ().bsearch (index);
137     if (range)
138       return range->intersects (*glyphs);
139     return false;
140   }
141 
142   template <typename IterableOut,
143 	    hb_requires (hb_is_sink_of (IterableOut, hb_codepoint_t))>
intersect_setOT::Layout::Common::CoverageFormat2_4144   void intersect_set (const hb_set_t &glyphs, IterableOut&& intersect_glyphs) const
145   {
146     /* Break out of loop for overlapping, broken, tables,
147      * to avoid fuzzer timouts. */
148     hb_codepoint_t last = 0;
149     for (const auto& range : rangeRecord)
150     {
151       if (unlikely (range.first < last))
152         break;
153       last = range.last;
154       for (hb_codepoint_t g = range.first - 1;
155 	   glyphs.next (&g) && g <= last;)
156 	intersect_glyphs << g;
157     }
158   }
159 
160   template <typename set_t>
collect_coverageOT::Layout::Common::CoverageFormat2_4161   bool collect_coverage (set_t *glyphs) const
162   {
163     for (const auto& range: rangeRecord)
164       if (unlikely (!range.collect_coverage (glyphs)))
165         return false;
166     return true;
167   }
168 
169   public:
170   /* Older compilers need this to be public. */
171   struct iter_t
172   {
initOT::Layout::Common::CoverageFormat2_4::iter_t173     void init (const CoverageFormat2_4 &c_)
174     {
175       c = &c_;
176       coverage = 0;
177       i = 0;
178       j = c->rangeRecord.len ? c->rangeRecord[0].first : 0;
179       if (unlikely (c->rangeRecord[0].first > c->rangeRecord[0].last))
180       {
181         /* Broken table. Skip. */
182         i = c->rangeRecord.len;
183         j = 0;
184       }
185     }
__more__OT::Layout::Common::CoverageFormat2_4::iter_t186     bool __more__ () const { return i < c->rangeRecord.len; }
__next__OT::Layout::Common::CoverageFormat2_4::iter_t187     void __next__ ()
188     {
189       if (j >= c->rangeRecord[i].last)
190       {
191         i++;
192         if (__more__ ())
193         {
194           unsigned int old = coverage;
195           j = c->rangeRecord.arrayZ[i].first;
196           coverage = c->rangeRecord.arrayZ[i].value;
197           if (unlikely (coverage != old + 1))
198           {
199             /* Broken table. Skip. Important to avoid DoS.
200              * Also, our callers depend on coverage being
201              * consecutive and monotonically increasing,
202              * ie. iota(). */
203            i = c->rangeRecord.len;
204            j = 0;
205            return;
206           }
207         }
208         else
209           j = 0;
210         return;
211       }
212       coverage++;
213       j++;
214     }
get_glyphOT::Layout::Common::CoverageFormat2_4::iter_t215     hb_codepoint_t get_glyph () const { return j; }
operator !=OT::Layout::Common::CoverageFormat2_4::iter_t216     bool operator != (const iter_t& o) const
217     { return i != o.i || j != o.j; }
__end__OT::Layout::Common::CoverageFormat2_4::iter_t218     iter_t __end__ () const
219     {
220       iter_t it;
221       it.init (*c);
222       it.i = c->rangeRecord.len;
223       it.j = 0;
224       return it;
225     }
226 
227     private:
228     const struct CoverageFormat2_4 *c;
229     unsigned int i, coverage;
230     hb_codepoint_t j;
231   };
232   private:
233 };
234 
235 }
236 }
237 }
238 
239 #endif  // #ifndef OT_LAYOUT_COMMON_COVERAGEFORMAT2_HH
240