gfx/harfbuzz/src/hb-ms-feature-ranges.hh

   1 /*
   2  * Copyright © 2011,2012,2013  Google, Inc.
   3  * Copyright © 2021  Khaled Hosny
   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  * Google Author(s): Behdad Esfahbod
  26  */
  27
  28 #ifndef HB_MS_FEATURE_RANGES_HH
  29 #define HB_MS_FEATURE_RANGES_HH
  30
  31 #include "hb.hh"
  32
  33 /* Variations of this code exist in hb-coretext.cc as well
  34  * as hb-aat-map.cc... */
  35
  36 typedef struct hb_ms_feature_t {
  37   uint32_t tag_le;
  38   uint32_t value;
  39 } hb_ms_feature_t;
  40
  41 typedef struct hb_ms_features_t {
  42   hb_ms_feature_t *features;
  43   uint32_t         num_features;
  44 } hb_ms_features_t;
  45
  46 struct hb_ms_active_feature_t {
  47   hb_ms_feature_t fea;
  48   unsigned int order;
  49
  50   HB_INTERNAL static int cmp (const void *pa, const void *pb) {
  51     const auto *a = (const hb_ms_active_feature_t *) pa;
  52     const auto *b = (const hb_ms_active_feature_t *) pb;
  53     return a->fea.tag_le < b->fea.tag_le ? -1 : a->fea.tag_le > b->fea.tag_le ? 1 :
  54            a->order < b->order ? -1 : a->order > b->order ? 1 :
  55            a->fea.value < b->fea.value ? -1 : a->fea.value > b->fea.value ? 1 :
  56            0;
  57   }
  58   bool operator== (const hb_ms_active_feature_t& f) const
  59   { return cmp (this, &f) == 0; }
  60 };
  61
  62 struct hb_ms_feature_event_t {
  63   unsigned int index;
  64   bool start;
  65   hb_ms_active_feature_t feature;
  66
  67   HB_INTERNAL static int cmp (const void *pa, const void *pb)
  68   {
  69     const auto *a = (const hb_ms_feature_event_t *) pa;
  70     const auto *b = (const hb_ms_feature_event_t *) pb;
  71     return a->index < b->index ? -1 : a->index > b->index ? 1 :
  72            a->start < b->start ? -1 : a->start > b->start ? 1 :
  73            hb_ms_active_feature_t::cmp (&a->feature, &b->feature);
  74   }
  75 };
  76
  77 struct hb_ms_range_record_t {
  78   hb_ms_features_t features;
  79   unsigned int index_first; /* == start */
  80   unsigned int index_last;  /* == end - 1 */
  81 };
  82
  83 static inline bool
  84 hb_ms_setup_features (const hb_feature_t                *features,
  85                       unsigned int                       num_features,
  86                       hb_vector_t<hb_ms_feature_t>      &feature_records, /* OUT */
  87                       hb_vector_t<hb_ms_range_record_t> &range_records /* OUT */)
  88 {
  89   feature_records.shrink(0);
  90   range_records.shrink(0);
  91
  92   /* Sort features by start/end events. */
  93   hb_vector_t<hb_ms_feature_event_t> feature_events;
  94   for (unsigned int i = 0; i < num_features; i++)
  95   {
  96     hb_ms_active_feature_t feature;
  97     feature.fea.tag_le = hb_uint32_swap (features[i].tag);
  98     feature.fea.value = features[i].value;
  99     feature.order = i;
 100
 101     hb_ms_feature_event_t *event;
 102
 103     event = feature_events.push ();
 104     event->index = features[i].start;
 105     event->start = true;
 106     event->feature = feature;
 107
 108     event = feature_events.push ();
 109     event->index = features[i].end;
 110     event->start = false;
 111     event->feature = feature;
 112   }
 113   feature_events.qsort ();
 114   /* Add a strategic final event. */
 115   {
 116     hb_ms_active_feature_t feature;
 117     feature.fea.tag_le = 0;
 118     feature.fea.value = 0;
 119     feature.order = num_features + 1;
 120
 121     auto *event = feature_events.push ();
 122     event->index = 0; /* This value does magic. */
 123     event->start = false;
 124     event->feature = feature;
 125   }
 126
 127   /* Scan events and save features for each range. */
 128   hb_vector_t<hb_ms_active_feature_t> active_features;
 129   unsigned int last_index = 0;
 130   for (unsigned int i = 0; i < feature_events.length; i++)
 131   {
 132     auto *event = &feature_events[i];
 133
 134     if (event->index != last_index)
 135     {
 136       /* Save a snapshot of active features and the range. */
 137       auto *range = range_records.push ();
 138       auto offset = feature_records.length;
 139
 140       active_features.qsort ();
 141       for (unsigned int j = 0; j < active_features.length; j++)
 142       {
 143         if (!j || active_features[j].fea.tag_le != feature_records[feature_records.length - 1].tag_le)
 144         {
 145           feature_records.push (active_features[j].fea);
 146         }
 147         else
 148         {
 149           /* Overrides value for existing feature. */
 150           feature_records[feature_records.length - 1].value = active_features[j].fea.value;
 151         }
 152       }
 153
 154       /* Will convert to pointer after all is ready, since feature_records.array
 155        * may move as we grow it. */
 156       range->features.features = reinterpret_cast<hb_ms_feature_t *> (offset);
 157       range->features.num_features = feature_records.length - offset;
 158       range->index_first = last_index;
 159       range->index_last  = event->index - 1;
 160
 161       last_index = event->index;
 162     }
 163
 164     if (event->start)
 165     {
 166       active_features.push (event->feature);
 167     }
 168     else
 169     {
 170       auto *feature = active_features.lsearch (event->feature);
 171       if (feature)
 172         active_features.remove_ordered (feature - active_features.arrayZ);
 173     }
 174   }
 175
 176   if (!range_records.length) /* No active feature found. */
 177     num_features = 0;
 178
 179   /* Fixup the pointers. */
 180   for (unsigned int i = 0; i < range_records.length; i++)
 181   {
 182     auto *range = &range_records[i];
 183     range->features.features = (hb_ms_feature_t *) feature_records + reinterpret_cast<uintptr_t> (range->features.features);
 184   }
 185
 186   return !!num_features;
 187 }
 188
 189 static inline void
 190 hb_ms_make_feature_ranges (hb_vector_t<hb_ms_feature_t>      &feature_records,
 191                            hb_vector_t<hb_ms_range_record_t> &range_records,
 192                            unsigned int                       chars_offset,
 193                            unsigned int                       chars_len,
 194                            uint16_t                          *log_clusters,
 195                            hb_vector_t<hb_ms_features_t*>    &range_features, /* OUT */
 196                            hb_vector_t<uint32_t>             &range_counts /* OUT */)
 197 {
 198   range_features.shrink (0);
 199   range_counts.shrink (0);
 200
 201   auto *last_range = &range_records[0];
 202   for (unsigned int i = chars_offset; i < chars_len; i++)
 203   {
 204     auto *range = last_range;
 205     while (log_clusters[i] < range->index_first)
 206       range--;
 207     while (log_clusters[i] > range->index_last)
 208       range++;
 209     if (!range_features.length ||
 210         &range->features != range_features[range_features.length - 1])
 211     {
 212       auto **features = range_features.push ();
 213       auto *c = range_counts.push ();
 214       if (unlikely (!features || !c))
 215       {
 216         range_features.shrink (0);
 217         range_counts.shrink (0);
 218         break;
 219       }
 220       *features = &range->features;
 221       *c = 1;
 222     }
 223     else
 224     {
 225       range_counts[range_counts.length - 1]++;
 226     }
 227
 228     last_range = range;
 229   }
 230 }
 231
 232 #endif /* HB_MS_FEATURE_RANGES_HH */