1/*
2 * Copyright © 2012,2017 Google, Inc.
3 * Copyright © 2021 Behdad Esfahbod
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_BIT_PAGE_HH
29#define HB_BIT_PAGE_HH
30
31#include "hb.hh"
32
33
34/* Compiler-assisted vectorization. */
35
36/* Type behaving similar to vectorized vars defined using __attribute__((vector_size(...))),
37 * basically a fixed-size bitset. We can't use the compiler type because hb_vector_t cannot
38 * guarantee alignment requirements. */
39template <typename elt_t, unsigned int byte_size>
40struct hb_vector_size_t
41{
42 elt_t& operator [] (unsigned int i) { return v[i]; }
43 const elt_t& operator [] (unsigned int i) const { return v[i]; }
44
45 void init0 ()
46 {
47 for (unsigned int i = 0; i < ARRAY_LENGTH (v); i++)
48 v[i] = 0;
49 }
50 void init1 ()
51 {
52 for (unsigned int i = 0; i < ARRAY_LENGTH (v); i++)
53 v[i] = (elt_t) -1;
54 }
55
56 template <typename Op>
57 hb_vector_size_t process (const Op& op) const
58 {
59 hb_vector_size_t r;
60 for (unsigned int i = 0; i < ARRAY_LENGTH (v); i++)
61 r.v[i] = op (v[i]);
62 return r;
63 }
64 template <typename Op>
65 hb_vector_size_t process (const Op& op, const hb_vector_size_t &o) const
66 {
67 hb_vector_size_t r;
68 for (unsigned int i = 0; i < ARRAY_LENGTH (v); i++)
69 r.v[i] = op (v[i], o.v[i]);
70 return r;
71 }
72 hb_vector_size_t operator | (const hb_vector_size_t &o) const
73 { return process (hb_bitwise_or, o); }
74 hb_vector_size_t operator & (const hb_vector_size_t &o) const
75 { return process (hb_bitwise_and, o); }
76 hb_vector_size_t operator ^ (const hb_vector_size_t &o) const
77 { return process (hb_bitwise_xor, o); }
78 hb_vector_size_t operator ~ () const
79 { return process (hb_bitwise_neg); }
80
81 hb_array_t<const elt_t> iter () const
82 { return hb_array (v); }
83
84 private:
85 static_assert (0 == byte_size % sizeof (elt_t), "");
86 elt_t v[byte_size / sizeof (elt_t)];
87};
88
89
90struct hb_bit_page_t
91{
92 void init0 () { v.init0 (); population = 0; }
93 void init1 () { v.init1 (); population = PAGE_BITS; }
94
95 void dirty () { population = UINT_MAX; }
96
97 static inline constexpr unsigned len ()
98 { return ARRAY_LENGTH_CONST (v); }
99
100 bool is_empty () const
101 {
102 if (has_population ()) return !population;
103 return
104 + hb_iter (v)
105 | hb_none
106 ;
107 }
108 uint32_t hash () const
109 {
110 return hb_bytes_t ((const char *) &v, sizeof (v)).hash ();
111 }
112
113 void add (hb_codepoint_t g) { elt (g) |= mask (g); dirty (); }
114 void del (hb_codepoint_t g) { elt (g) &= ~mask (g); dirty (); }
115 void set (hb_codepoint_t g, bool value) { if (value) add (g); else del (g); }
116 bool get (hb_codepoint_t g) const { return elt (g) & mask (g); }
117
118 void add_range (hb_codepoint_t a, hb_codepoint_t b)
119 {
120 elt_t *la = &elt (a);
121 elt_t *lb = &elt (b);
122 if (la == lb)
123 *la |= (mask (b) << 1) - mask(a);
124 else
125 {
126 *la |= ~(mask (a) - 1llu);
127 la++;
128
129 hb_memset (la, 0xff, (char *) lb - (char *) la);
130
131 *lb |= ((mask (b) << 1) - 1llu);
132 }
133 dirty ();
134 }
135 void del_range (hb_codepoint_t a, hb_codepoint_t b)
136 {
137 elt_t *la = &elt (a);
138 elt_t *lb = &elt (b);
139 if (la == lb)
140 *la &= ~((mask (b) << 1llu) - mask(a));
141 else
142 {
143 *la &= mask (a) - 1;
144 la++;
145
146 hb_memset (la, 0, (char *) lb - (char *) la);
147
148 *lb &= ~((mask (b) << 1) - 1llu);
149 }
150 dirty ();
151 }
152 void set_range (hb_codepoint_t a, hb_codepoint_t b, bool v)
153 { if (v) add_range (a, b); else del_range (a, b); }
154
155
156 // Writes out page values to the array p. Returns the number of values
157 // written. At most size codepoints will be written.
158 unsigned int write (uint32_t base,
159 unsigned int start_value,
160 hb_codepoint_t *p,
161 unsigned int size) const
162 {
163 unsigned int start_v = start_value / ELT_BITS;
164 unsigned int start_bit = start_value & ELT_MASK;
165 unsigned int count = 0;
166 for (unsigned i = start_v; i < len () && count < size; i++)
167 {
168 elt_t bits = v[i];
169 uint32_t v_base = base | (i * ELT_BITS);
170 for (unsigned int j = start_bit; j < ELT_BITS && count < size; j++)
171 {
172 if ((elt_t(1) << j) & bits) {
173 *p++ = v_base | j;
174 count++;
175 }
176 }
177 start_bit = 0;
178 }
179 return count;
180 }
181
182 // Writes out the values NOT in this page to the array p. Returns the
183 // number of values written. At most size codepoints will be written.
184 // Returns the number of codepoints written. next_value holds the next value
185 // that should be written (if not present in this page). This is used to fill
186 // any missing value gaps between this page and the previous page, if any.
187 // next_value is updated to one more than the last value present in this page.
188 unsigned int write_inverted (uint32_t base,
189 unsigned int start_value,
190 hb_codepoint_t *p,
191 unsigned int size,
192 hb_codepoint_t *next_value) const
193 {
194 unsigned int start_v = start_value / ELT_BITS;
195 unsigned int start_bit = start_value & ELT_MASK;
196 unsigned int count = 0;
197 for (unsigned i = start_v; i < len () && count < size; i++)
198 {
199 elt_t bits = v[i];
200 uint32_t v_offset = i * ELT_BITS;
201 for (unsigned int j = start_bit; j < ELT_BITS && count < size; j++)
202 {
203 if ((elt_t(1) << j) & bits)
204 {
205 hb_codepoint_t value = base | v_offset | j;
206 // Emit all the missing values from next_value up to value - 1.
207 for (hb_codepoint_t k = *next_value; k < value && count < size; k++)
208 {
209 *p++ = k;
210 count++;
211 }
212 // Skip over this value;
213 *next_value = value + 1;
214 }
215 }
216 start_bit = 0;
217 }
218 return count;
219 }
220
221 bool is_equal (const hb_bit_page_t &other) const
222 {
223 for (unsigned i = 0; i < len (); i++)
224 if (v[i] != other.v[i])
225 return false;
226 return true;
227 }
228 bool is_subset (const hb_bit_page_t &larger_page) const
229 {
230 if (has_population () && larger_page.has_population () &&
231 population > larger_page.population)
232 return false;
233
234 for (unsigned i = 0; i < len (); i++)
235 if (~larger_page.v[i] & v[i])
236 return false;
237 return true;
238 }
239
240 bool has_population () const { return population != UINT_MAX; }
241 unsigned int get_population () const
242 {
243 if (has_population ()) return population;
244 population =
245 + hb_iter (v)
246 | hb_reduce ([] (unsigned pop, const elt_t &_) { return pop + hb_popcount (_); }, 0u)
247 ;
248 return population;
249 }
250
251 bool next (hb_codepoint_t *codepoint) const
252 {
253 unsigned int m = (*codepoint + 1) & MASK;
254 if (!m)
255 {
256 *codepoint = INVALID;
257 return false;
258 }
259 unsigned int i = m / ELT_BITS;
260 unsigned int j = m & ELT_MASK;
261
262 const elt_t vv = v[i] & ~((elt_t (1) << j) - 1);
263 for (const elt_t *p = &vv; i < len (); p = &v[++i])
264 if (*p)
265 {
266 *codepoint = i * ELT_BITS + elt_get_min (*p);
267 return true;
268 }
269
270 *codepoint = INVALID;
271 return false;
272 }
273 bool previous (hb_codepoint_t *codepoint) const
274 {
275 unsigned int m = (*codepoint - 1) & MASK;
276 if (m == MASK)
277 {
278 *codepoint = INVALID;
279 return false;
280 }
281 unsigned int i = m / ELT_BITS;
282 unsigned int j = m & ELT_MASK;
283
284 /* Fancy mask to avoid shifting by elt_t bitsize, which is undefined. */
285 const elt_t mask = j < 8 * sizeof (elt_t) - 1 ?
286 ((elt_t (1) << (j + 1)) - 1) :
287 (elt_t) -1;
288 const elt_t vv = v[i] & mask;
289 const elt_t *p = &vv;
290 while (true)
291 {
292 if (*p)
293 {
294 *codepoint = i * ELT_BITS + elt_get_max (*p);
295 return true;
296 }
297 if ((int) i <= 0) break;
298 p = &v[--i];
299 }
300
301 *codepoint = INVALID;
302 return false;
303 }
304 hb_codepoint_t get_min () const
305 {
306 for (unsigned int i = 0; i < len (); i++)
307 if (v[i])
308 return i * ELT_BITS + elt_get_min (v[i]);
309 return INVALID;
310 }
311 hb_codepoint_t get_max () const
312 {
313 for (int i = len () - 1; i >= 0; i--)
314 if (v[i])
315 return i * ELT_BITS + elt_get_max (v[i]);
316 return 0;
317 }
318
319 static constexpr hb_codepoint_t INVALID = HB_SET_VALUE_INVALID;
320
321 typedef unsigned long long elt_t;
322 static constexpr unsigned PAGE_BITS_LOG_2 = 9; // 512 bits
323 static constexpr unsigned PAGE_BITS = 1 << PAGE_BITS_LOG_2;
324 static_assert (1 << PAGE_BITS_LOG_2 == PAGE_BITS, "");
325 static_assert ((PAGE_BITS & ((PAGE_BITS) - 1)) == 0, "");
326 static constexpr unsigned PAGE_BITMASK = PAGE_BITS - 1;
327
328 static unsigned int elt_get_min (const elt_t &elt) { return hb_ctz (elt); }
329 static unsigned int elt_get_max (const elt_t &elt) { return hb_bit_storage (elt) - 1; }
330
331 typedef hb_vector_size_t<elt_t, PAGE_BITS / 8> vector_t;
332
333 static constexpr unsigned ELT_BITS = sizeof (elt_t) * 8;
334 static constexpr unsigned ELT_MASK = ELT_BITS - 1;
335
336 static constexpr unsigned BITS = sizeof (vector_t) * 8;
337 static constexpr unsigned MASK = BITS - 1;
338 static_assert ((unsigned) PAGE_BITS == (unsigned) BITS, "");
339
340 elt_t &elt (hb_codepoint_t g) { return v[(g & MASK) / ELT_BITS]; }
341 const elt_t& elt (hb_codepoint_t g) const { return v[(g & MASK) / ELT_BITS]; }
342 static constexpr elt_t mask (hb_codepoint_t g) { return elt_t (1) << (g & ELT_MASK); }
343
344 mutable unsigned population;
345 vector_t v;
346};
347
348
349#endif /* HB_BIT_PAGE_HH */
350