hb-ms-feature-ranges.hh (7255B)
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-shape.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 */