src/OT/Layout/Common/Coverage.hh

   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_COVERAGE_HH
  30 #define OT_LAYOUT_COMMON_COVERAGE_HH
  31
  32 #include "../types.hh"
  33 #include "CoverageFormat1.hh"
  34 #include "CoverageFormat2.hh"
  35
  36 namespace OT {
  37 namespace Layout {
  38 namespace Common {
  39
  40 template<typename Iterator>
  41 static inline void Coverage_serialize (hb_serialize_context_t *c,
  42                                        Iterator it);
  43
  44 struct Coverage
  45 {
  46
  47   protected:
  48   union {
  49   HBUINT16                      format;         /* Format identifier */
  50   CoverageFormat1_3<SmallTypes> format1;
  51   CoverageFormat2_4<SmallTypes> format2;
  52 #ifndef HB_NO_BEYOND_64K
  53   CoverageFormat1_3<MediumTypes>format3;
  54   CoverageFormat2_4<MediumTypes>format4;
  55 #endif
  56   } u;
  57   public:
  58   DEFINE_SIZE_UNION (2, format);
  59
  60 #ifndef HB_OPTIMIZE_SIZE
  61   HB_ALWAYS_INLINE
  62 #endif
  63   bool sanitize (hb_sanitize_context_t *c) const
  64   {
  65     TRACE_SANITIZE (this);
  66     if (!u.format.sanitize (c)) return_trace (false);
  67     switch (u.format)
  68     {
  69     case 1: return_trace (u.format1.sanitize (c));
  70     case 2: return_trace (u.format2.sanitize (c));
  71 #ifndef HB_NO_BEYOND_64K
  72     case 3: return_trace (u.format3.sanitize (c));
  73     case 4: return_trace (u.format4.sanitize (c));
  74 #endif
  75     default:return_trace (true);
  76     }
  77   }
  78
  79   /* Has interface. */
  80   unsigned operator [] (hb_codepoint_t k) const { return get (k); }
  81   bool has (hb_codepoint_t k) const { return (*this)[k] != NOT_COVERED; }
  82   /* Predicate. */
  83   bool operator () (hb_codepoint_t k) const { return has (k); }
  84
  85   unsigned int get (hb_codepoint_t k) const { return get_coverage (k); }
  86   unsigned int get_coverage (hb_codepoint_t glyph_id) const
  87   {
  88     switch (u.format) {
  89     case 1: return u.format1.get_coverage (glyph_id);
  90     case 2: return u.format2.get_coverage (glyph_id);
  91 #ifndef HB_NO_BEYOND_64K
  92     case 3: return u.format3.get_coverage (glyph_id);
  93     case 4: return u.format4.get_coverage (glyph_id);
  94 #endif
  95     default:return NOT_COVERED;
  96     }
  97   }
  98
  99   unsigned get_population () const
 100   {
 101     switch (u.format) {
 102     case 1: return u.format1.get_population ();
 103     case 2: return u.format2.get_population ();
 104 #ifndef HB_NO_BEYOND_64K
 105     case 3: return u.format3.get_population ();
 106     case 4: return u.format4.get_population ();
 107 #endif
 108     default:return NOT_COVERED;
 109     }
 110   }
 111
 112   template <typename Iterator,
 113       hb_requires (hb_is_sorted_source_of (Iterator, hb_codepoint_t))>
 114   bool serialize (hb_serialize_context_t *c, Iterator glyphs)
 115   {
 116     TRACE_SERIALIZE (this);
 117     if (unlikely (!c->extend_min (this))) return_trace (false);
 118
 119     unsigned count = hb_len (glyphs);
 120     unsigned num_ranges = 0;
 121     hb_codepoint_t last = (hb_codepoint_t) -2;
 122     hb_codepoint_t max = 0;
 123     bool unsorted = false;
 124     for (auto g: glyphs)
 125     {
 126       if (last != (hb_codepoint_t) -2 && g < last)
 127         unsorted = true;
 128       if (last + 1 != g)
 129         num_ranges++;
 130       last = g;
 131       if (g > max) max = g;
 132     }
 133     u.format = !unsorted && count <= num_ranges * 3 ? 1 : 2;
 134
 135 #ifndef HB_NO_BEYOND_64K
 136     if (max > 0xFFFFu)
 137       u.format += 2;
 138     if (unlikely (max > 0xFFFFFFu))
 139 #else
 140     if (unlikely (max > 0xFFFFu))
 141 #endif
 142     {
 143       c->check_success (false, HB_SERIALIZE_ERROR_INT_OVERFLOW);
 144       return_trace (false);
 145     }
 146
 147     switch (u.format)
 148     {
 149     case 1: return_trace (u.format1.serialize (c, glyphs));
 150     case 2: return_trace (u.format2.serialize (c, glyphs));
 151 #ifndef HB_NO_BEYOND_64K
 152     case 3: return_trace (u.format3.serialize (c, glyphs));
 153     case 4: return_trace (u.format4.serialize (c, glyphs));
 154 #endif
 155     default:return_trace (false);
 156     }
 157   }
 158
 159   bool subset (hb_subset_context_t *c) const
 160   {
 161     TRACE_SUBSET (this);
 162     auto it =
 163     + iter ()
 164     | hb_take (c->plan->source->get_num_glyphs ())
 165     | hb_map_retains_sorting (c->plan->glyph_map_gsub)
 166     | hb_filter ([] (hb_codepoint_t glyph) { return glyph != HB_MAP_VALUE_INVALID; })
 167     ;
 168
 169     // Cache the iterator result as it will be iterated multiple times
 170     // by the serialize code below.
 171     hb_sorted_vector_t<hb_codepoint_t> glyphs (it);
 172     Coverage_serialize (c->serializer, glyphs.iter ());
 173     return_trace (bool (glyphs));
 174   }
 175
 176   bool intersects (const hb_set_t *glyphs) const
 177   {
 178     switch (u.format)
 179     {
 180     case 1: return u.format1.intersects (glyphs);
 181     case 2: return u.format2.intersects (glyphs);
 182 #ifndef HB_NO_BEYOND_64K
 183     case 3: return u.format3.intersects (glyphs);
 184     case 4: return u.format4.intersects (glyphs);
 185 #endif
 186     default:return false;
 187     }
 188   }
 189   bool intersects_coverage (const hb_set_t *glyphs, unsigned int index) const
 190   {
 191     switch (u.format)
 192     {
 193     case 1: return u.format1.intersects_coverage (glyphs, index);
 194     case 2: return u.format2.intersects_coverage (glyphs, index);
 195 #ifndef HB_NO_BEYOND_64K
 196     case 3: return u.format3.intersects_coverage (glyphs, index);
 197     case 4: return u.format4.intersects_coverage (glyphs, index);
 198 #endif
 199     default:return false;
 200     }
 201   }
 202
 203   /* Might return false if array looks unsorted.
 204    * Used for faster rejection of corrupt data. */
 205   template <typename set_t>
 206   bool collect_coverage (set_t *glyphs) const
 207   {
 208     switch (u.format)
 209     {
 210     case 1: return u.format1.collect_coverage (glyphs);
 211     case 2: return u.format2.collect_coverage (glyphs);
 212 #ifndef HB_NO_BEYOND_64K
 213     case 3: return u.format3.collect_coverage (glyphs);
 214     case 4: return u.format4.collect_coverage (glyphs);
 215 #endif
 216     default:return false;
 217     }
 218   }
 219
 220   template <typename IterableOut,
 221             hb_requires (hb_is_sink_of (IterableOut, hb_codepoint_t))>
 222   void intersect_set (const hb_set_t &glyphs, IterableOut&& intersect_glyphs) const
 223   {
 224     switch (u.format)
 225     {
 226     case 1: return u.format1.intersect_set (glyphs, intersect_glyphs);
 227     case 2: return u.format2.intersect_set (glyphs, intersect_glyphs);
 228 #ifndef HB_NO_BEYOND_64K
 229     case 3: return u.format3.intersect_set (glyphs, intersect_glyphs);
 230     case 4: return u.format4.intersect_set (glyphs, intersect_glyphs);
 231 #endif
 232     default:return ;
 233     }
 234   }
 235
 236   struct iter_t : hb_iter_with_fallback_t<iter_t, hb_codepoint_t>
 237   {
 238     static constexpr bool is_sorted_iterator = true;
 239     iter_t (const Coverage &c_ = Null (Coverage))
 240     {
 241       hb_memset (this, 0, sizeof (*this));
 242       format = c_.u.format;
 243       switch (format)
 244       {
 245       case 1: u.format1.init (c_.u.format1); return;
 246       case 2: u.format2.init (c_.u.format2); return;
 247 #ifndef HB_NO_BEYOND_64K
 248       case 3: u.format3.init (c_.u.format3); return;
 249       case 4: u.format4.init (c_.u.format4); return;
 250 #endif
 251       default:                               return;
 252       }
 253     }
 254     bool __more__ () const
 255     {
 256       switch (format)
 257       {
 258       case 1: return u.format1.__more__ ();
 259       case 2: return u.format2.__more__ ();
 260 #ifndef HB_NO_BEYOND_64K
 261       case 3: return u.format3.__more__ ();
 262       case 4: return u.format4.__more__ ();
 263 #endif
 264       default:return false;
 265       }
 266     }
 267     void __next__ ()
 268     {
 269       switch (format)
 270       {
 271       case 1: u.format1.__next__ (); break;
 272       case 2: u.format2.__next__ (); break;
 273 #ifndef HB_NO_BEYOND_64K
 274       case 3: u.format3.__next__ (); break;
 275       case 4: u.format4.__next__ (); break;
 276 #endif
 277       default:                   break;
 278       }
 279     }
 280     typedef hb_codepoint_t __item_t__;
 281     __item_t__ __item__ () const { return get_glyph (); }
 282
 283     hb_codepoint_t get_glyph () const
 284     {
 285       switch (format)
 286       {
 287       case 1: return u.format1.get_glyph ();
 288       case 2: return u.format2.get_glyph ();
 289 #ifndef HB_NO_BEYOND_64K
 290       case 3: return u.format3.get_glyph ();
 291       case 4: return u.format4.get_glyph ();
 292 #endif
 293       default:return 0;
 294       }
 295     }
 296     bool operator != (const iter_t& o) const
 297     {
 298       if (unlikely (format != o.format)) return true;
 299       switch (format)
 300       {
 301       case 1: return u.format1 != o.u.format1;
 302       case 2: return u.format2 != o.u.format2;
 303 #ifndef HB_NO_BEYOND_64K
 304       case 3: return u.format3 != o.u.format3;
 305       case 4: return u.format4 != o.u.format4;
 306 #endif
 307       default:return false;
 308       }
 309     }
 310     iter_t __end__ () const
 311     {
 312       iter_t it = {};
 313       it.format = format;
 314       switch (format)
 315       {
 316       case 1: it.u.format1 = u.format1.__end__ (); break;
 317       case 2: it.u.format2 = u.format2.__end__ (); break;
 318 #ifndef HB_NO_BEYOND_64K
 319       case 3: it.u.format3 = u.format3.__end__ (); break;
 320       case 4: it.u.format4 = u.format4.__end__ (); break;
 321 #endif
 322       default: break;
 323       }
 324       return it;
 325     }
 326
 327     private:
 328     unsigned int format;
 329     union {
 330 #ifndef HB_NO_BEYOND_64K
 331     CoverageFormat2_4<MediumTypes>::iter_t      format4; /* Put this one first since it's larger; helps shut up compiler. */
 332     CoverageFormat1_3<MediumTypes>::iter_t      format3;
 333 #endif
 334     CoverageFormat2_4<SmallTypes>::iter_t       format2; /* Put this one first since it's larger; helps shut up compiler. */
 335     CoverageFormat1_3<SmallTypes>::iter_t       format1;
 336     } u;
 337   };
 338   iter_t iter () const { return iter_t (*this); }
 339 };
 340
 341 template<typename Iterator>
 342 static inline void
 343 Coverage_serialize (hb_serialize_context_t *c,
 344                     Iterator it)
 345 { c->start_embed<Coverage> ()->serialize (c, it); }
 346
 347 }
 348 }
 349 }
 350
 351 #endif  // #ifndef OT_LAYOUT_COMMON_COVERAGE_HH