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 for (auto g: glyphs) 99 { 100 if (last + 1 != g) 101 { 102 range++; 103 rangeRecord[range].first = g; 104 rangeRecord[range].value = count; 105 } 106 rangeRecord[range].last = g; 107 last = g; 108 count++; 109 } 110 111 return_trace (true); 112 } 113 intersectsOT::Layout::Common::CoverageFormat2_4114 bool intersects (const hb_set_t *glyphs) const 115 { 116 if (rangeRecord.len > glyphs->get_population () * hb_bit_storage ((unsigned) rangeRecord.len) / 2) 117 { 118 for (hb_codepoint_t g = HB_SET_VALUE_INVALID; glyphs->next (&g);) 119 if (get_coverage (g) != NOT_COVERED) 120 return true; 121 return false; 122 } 123 124 return hb_any (+ hb_iter (rangeRecord) 125 | hb_map ([glyphs] (const RangeRecord<Types> &range) { return range.intersects (*glyphs); })); 126 } intersects_coverageOT::Layout::Common::CoverageFormat2_4127 bool intersects_coverage (const hb_set_t *glyphs, unsigned int index) const 128 { 129 auto *range = rangeRecord.as_array ().bsearch (index); 130 if (range) 131 return range->intersects (*glyphs); 132 return false; 133 } 134 135 template <typename IterableOut, 136 hb_requires (hb_is_sink_of (IterableOut, hb_codepoint_t))> intersect_setOT::Layout::Common::CoverageFormat2_4137 void intersect_set (const hb_set_t &glyphs, IterableOut&& intersect_glyphs) const 138 { 139 /* Break out of loop for overlapping, broken, tables, 140 * to avoid fuzzer timouts. */ 141 hb_codepoint_t last = 0; 142 for (const auto& range : rangeRecord) 143 { 144 if (unlikely (range.first < last)) 145 break; 146 last = range.last; 147 for (hb_codepoint_t g = range.first - 1; 148 glyphs.next (&g) && g <= last;) 149 intersect_glyphs << g; 150 } 151 } 152 153 template <typename set_t> collect_coverageOT::Layout::Common::CoverageFormat2_4154 bool collect_coverage (set_t *glyphs) const 155 { 156 for (const auto& range: rangeRecord) 157 if (unlikely (!range.collect_coverage (glyphs))) 158 return false; 159 return true; 160 } 161 162 public: 163 /* Older compilers need this to be public. */ 164 struct iter_t 165 { initOT::Layout::Common::CoverageFormat2_4::iter_t166 void init (const CoverageFormat2_4 &c_) 167 { 168 c = &c_; 169 coverage = 0; 170 i = 0; 171 j = c->rangeRecord.len ? c->rangeRecord[0].first : 0; 172 if (unlikely (c->rangeRecord[0].first > c->rangeRecord[0].last)) 173 { 174 /* Broken table. Skip. */ 175 i = c->rangeRecord.len; 176 j = 0; 177 } 178 } __more__OT::Layout::Common::CoverageFormat2_4::iter_t179 bool __more__ () const { return i < c->rangeRecord.len; } __next__OT::Layout::Common::CoverageFormat2_4::iter_t180 void __next__ () 181 { 182 if (j >= c->rangeRecord[i].last) 183 { 184 i++; 185 if (__more__ ()) 186 { 187 unsigned int old = coverage; 188 j = c->rangeRecord[i].first; 189 coverage = c->rangeRecord[i].value; 190 if (unlikely (coverage != old + 1)) 191 { 192 /* Broken table. Skip. Important to avoid DoS. 193 * Also, our callers depend on coverage being 194 * consecutive and monotonically increasing, 195 * ie. iota(). */ 196 i = c->rangeRecord.len; 197 j = 0; 198 return; 199 } 200 } 201 else 202 j = 0; 203 return; 204 } 205 coverage++; 206 j++; 207 } get_glyphOT::Layout::Common::CoverageFormat2_4::iter_t208 hb_codepoint_t get_glyph () const { return j; } operator !=OT::Layout::Common::CoverageFormat2_4::iter_t209 bool operator != (const iter_t& o) const 210 { return i != o.i || j != o.j; } __end__OT::Layout::Common::CoverageFormat2_4::iter_t211 iter_t __end__ () const 212 { 213 iter_t it; 214 it.init (*c); 215 it.i = c->rangeRecord.len; 216 it.j = 0; 217 return it; 218 } 219 220 private: 221 const struct CoverageFormat2_4 *c; 222 unsigned int i, coverage; 223 hb_codepoint_t j; 224 }; 225 private: 226 }; 227 228 } 229 } 230 } 231 232 #endif // #ifndef OT_LAYOUT_COMMON_COVERAGEFORMAT2_HH 233