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 #include "hb-ms-feature-ranges.hh"
29
30 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)31 hb_ms_setup_features (const hb_feature_t *features,
32 unsigned int num_features,
33 hb_vector_t<hb_ms_feature_t> &feature_records, /* OUT */
34 hb_vector_t<hb_ms_range_record_t> &range_records /* OUT */)
35 {
36 feature_records.shrink(0);
37 range_records.shrink(0);
38
39 /* Sort features by start/end events. */
40 hb_vector_t<hb_ms_feature_event_t> feature_events;
41 for (unsigned int i = 0; i < num_features; i++)
42 {
43 hb_ms_active_feature_t feature;
44 feature.fea.tag_le = hb_uint32_swap (features[i].tag);
45 feature.fea.value = features[i].value;
46 feature.order = i;
47
48 hb_ms_feature_event_t *event;
49
50 event = feature_events.push ();
51 event->index = features[i].start;
52 event->start = true;
53 event->feature = feature;
54
55 event = feature_events.push ();
56 event->index = features[i].end;
57 event->start = false;
58 event->feature = feature;
59 }
60 feature_events.qsort ();
61 /* Add a strategic final event. */
62 {
63 hb_ms_active_feature_t feature;
64 feature.fea.tag_le = 0;
65 feature.fea.value = 0;
66 feature.order = num_features + 1;
67
68 auto *event = feature_events.push ();
69 event->index = 0; /* This value does magic. */
70 event->start = false;
71 event->feature = feature;
72 }
73
74 /* Scan events and save features for each range. */
75 hb_vector_t<hb_ms_active_feature_t> active_features;
76 unsigned int last_index = 0;
77 for (unsigned int i = 0; i < feature_events.length; i++)
78 {
79 auto *event = &feature_events[i];
80
81 if (event->index != last_index)
82 {
83 /* Save a snapshot of active features and the range. */
84 auto *range = range_records.push ();
85 auto offset = feature_records.length;
86
87 active_features.qsort ();
88 for (unsigned int j = 0; j < active_features.length; j++)
89 {
90 if (!j || active_features[j].fea.tag_le != feature_records[feature_records.length - 1].tag_le)
91 {
92 feature_records.push (active_features[j].fea);
93 }
94 else
95 {
96 /* Overrides value for existing feature. */
97 feature_records[feature_records.length - 1].value = active_features[j].fea.value;
98 }
99 }
100
101 /* Will convert to pointer after all is ready, since feature_records.array
102 * may move as we grow it. */
103 range->features.features = reinterpret_cast<hb_ms_feature_t *> (offset);
104 range->features.num_features = feature_records.length - offset;
105 range->index_first = last_index;
106 range->index_last = event->index - 1;
107
108 last_index = event->index;
109 }
110
111 if (event->start)
112 {
113 active_features.push (event->feature);
114 }
115 else
116 {
117 auto *feature = active_features.find (&event->feature);
118 if (feature)
119 active_features.remove (feature - active_features.arrayZ);
120 }
121 }
122
123 if (!range_records.length) /* No active feature found. */
124 num_features = 0;
125
126 /* Fixup the pointers. */
127 for (unsigned int i = 0; i < range_records.length; i++)
128 {
129 auto *range = &range_records[i];
130 range->features.features = (hb_ms_feature_t *) feature_records + reinterpret_cast<uintptr_t> (range->features.features);
131 }
132
133 return !!num_features;
134 }
135
136 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)137 hb_ms_make_feature_ranges (hb_vector_t<hb_ms_feature_t> &feature_records,
138 hb_vector_t<hb_ms_range_record_t> &range_records,
139 unsigned int chars_offset,
140 unsigned int chars_len,
141 uint16_t *log_clusters,
142 hb_vector_t<hb_ms_features_t*> &range_features, /* OUT */
143 hb_vector_t<uint32_t> &range_counts /* OUT */)
144 {
145 range_features.shrink (0);
146 range_counts.shrink (0);
147
148 auto *last_range = &range_records[0];
149 for (unsigned int i = chars_offset; i < chars_len; i++)
150 {
151 auto *range = last_range;
152 while (log_clusters[i] < range->index_first)
153 range--;
154 while (log_clusters[i] > range->index_last)
155 range++;
156 if (!range_features.length ||
157 &range->features != range_features[range_features.length - 1])
158 {
159 auto **features = range_features.push ();
160 auto *c = range_counts.push ();
161 if (unlikely (!features || !c))
162 {
163 range_features.shrink (0);
164 range_counts.shrink (0);
165 break;
166 }
167 *features = &range->features;
168 *c = 1;
169 }
170 else
171 {
172 range_counts[range_counts.length - 1]++;
173 }
174
175 last_range = range;
176 }
177 }
178