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
cmphb_ms_active_feature_t50 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 }
operator ==hb_ms_active_feature_t58 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
cmphb_ms_feature_event_t67 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
hb_ms_setup_features(const hb_feature_t * features,unsigned int num_features,hb_vector_t<hb_ms_feature_t> & feature_records,hb_vector_t<hb_ms_range_record_t> & range_records)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
hb_ms_make_feature_ranges(hb_vector_t<hb_ms_feature_t> & feature_records,hb_vector_t<hb_ms_range_record_t> & range_records,unsigned int chars_offset,unsigned int chars_len,uint16_t * log_clusters,hb_vector_t<hb_ms_features_t * > & range_features,hb_vector_t<uint32_t> & range_counts)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 */
233