Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/harfbuzz/src/hb-bit-page.hh @ 2:b50eed0cc0ef upstream

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ADD: MuPDF v1.26.7: the MuPDF source as downloaded by a default build of PyMuPDF 1.26.4. The directory name has changed: no version number in the expanded directory now.
author Franz Glasner <fzglas.hg@dom66.de>
date Mon, 15 Sep 2025 11:43:07 +0200
parents
children
comparison
equal deleted inserted replaced
1:1d09e1dec1d9 2:b50eed0cc0ef
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. */
38 template <typename elt_t, unsigned int byte_size>
39 struct hb_vector_size_t
40 {
41 elt_t& operator [] (unsigned int i) { return v[i]; }
42 const elt_t& operator [] (unsigned int i) const { return v[i]; }
43
44 void clear (unsigned char v = 0) { hb_memset (this, v, sizeof (*this)); }
45
46 template <typename Op>
47 hb_vector_size_t process (const Op& op) const
48 {
49 hb_vector_size_t r;
50 for (unsigned int i = 0; i < ARRAY_LENGTH (v); i++)
51 r.v[i] = op (v[i]);
52 return r;
53 }
54 template <typename Op>
55 hb_vector_size_t process (const Op& op, const hb_vector_size_t &o) const
56 {
57 hb_vector_size_t r;
58 for (unsigned int i = 0; i < ARRAY_LENGTH (v); i++)
59 r.v[i] = op (v[i], o.v[i]);
60 return r;
61 }
62 hb_vector_size_t operator | (const hb_vector_size_t &o) const
63 { return process (hb_bitwise_or, o); }
64 hb_vector_size_t operator & (const hb_vector_size_t &o) const
65 { return process (hb_bitwise_and, o); }
66 hb_vector_size_t operator ^ (const hb_vector_size_t &o) const
67 { return process (hb_bitwise_xor, o); }
68 hb_vector_size_t operator ~ () const
69 { return process (hb_bitwise_neg); }
70
71 hb_array_t<const elt_t> iter () const
72 { return hb_array (v); }
73
74 private:
75 static_assert (0 == byte_size % sizeof (elt_t), "");
76 elt_t v[byte_size / sizeof (elt_t)];
77 };
78
79
80 struct hb_bit_page_t
81 {
82 void init0 () { v.clear (); }
83 void init1 () { v.clear (0xFF); }
84
85 constexpr unsigned len () const
86 { return ARRAY_LENGTH_CONST (v); }
87
88 bool is_empty () const
89 {
90 return
91 + hb_iter (v)
92 | hb_none
93 ;
94 }
95 uint32_t hash () const
96 {
97 return
98 + hb_iter (v)
99 | hb_reduce ([] (uint32_t h, const elt_t &_) { return h * 31 + hb_hash (_); }, (uint32_t) 0u)
100 ;
101 }
102
103 void add (hb_codepoint_t g) { elt (g) |= mask (g); }
104 void del (hb_codepoint_t g) { elt (g) &= ~mask (g); }
105 void set (hb_codepoint_t g, bool value) { if (value) add (g); else del (g); }
106 bool get (hb_codepoint_t g) const { return elt (g) & mask (g); }
107
108 void add_range (hb_codepoint_t a, hb_codepoint_t b)
109 {
110 elt_t *la = &elt (a);
111 elt_t *lb = &elt (b);
112 if (la == lb)
113 *la |= (mask (b) << 1) - mask(a);
114 else
115 {
116 *la |= ~(mask (a) - 1);
117 la++;
118
119 hb_memset (la, 0xff, (char *) lb - (char *) la);
120
121 *lb |= ((mask (b) << 1) - 1);
122 }
123 }
124 void del_range (hb_codepoint_t a, hb_codepoint_t b)
125 {
126 elt_t *la = &elt (a);
127 elt_t *lb = &elt (b);
128 if (la == lb)
129 *la &= ~((mask (b) << 1) - mask(a));
130 else
131 {
132 *la &= mask (a) - 1;
133 la++;
134
135 hb_memset (la, 0, (char *) lb - (char *) la);
136
137 *lb &= ~((mask (b) << 1) - 1);
138 }
139 }
140 void set_range (hb_codepoint_t a, hb_codepoint_t b, bool v)
141 { if (v) add_range (a, b); else del_range (a, b); }
142
143
144 // Writes out page values to the array p. Returns the number of values
145 // written. At most size codepoints will be written.
146 unsigned int write (uint32_t base,
147 unsigned int start_value,
148 hb_codepoint_t *p,
149 unsigned int size) const
150 {
151 unsigned int start_v = start_value / ELT_BITS;
152 unsigned int start_bit = start_value & ELT_MASK;
153 unsigned int count = 0;
154 for (unsigned i = start_v; i < len () && count < size; i++)
155 {
156 elt_t bits = v[i];
157 uint32_t v_base = base | (i * ELT_BITS);
158 for (unsigned int j = start_bit; j < ELT_BITS && count < size; j++)
159 {
160 if ((elt_t(1) << j) & bits) {
161 *p++ = v_base | j;
162 count++;
163 }
164 }
165 start_bit = 0;
166 }
167 return count;
168 }
169
170 // Writes out the values NOT in this page to the array p. Returns the
171 // number of values written. At most size codepoints will be written.
172 // Returns the number of codepoints written. next_value holds the next value
173 // that should be written (if not present in this page). This is used to fill
174 // any missing value gaps between this page and the previous page, if any.
175 // next_value is updated to one more than the last value present in this page.
176 unsigned int write_inverted (uint32_t base,
177 unsigned int start_value,
178 hb_codepoint_t *p,
179 unsigned int size,
180 hb_codepoint_t *next_value) const
181 {
182 unsigned int start_v = start_value / ELT_BITS;
183 unsigned int start_bit = start_value & ELT_MASK;
184 unsigned int count = 0;
185 for (unsigned i = start_v; i < len () && count < size; i++)
186 {
187 elt_t bits = v[i];
188 uint32_t v_offset = i * ELT_BITS;
189 for (unsigned int j = start_bit; j < ELT_BITS && count < size; j++)
190 {
191 if ((elt_t(1) << j) & bits)
192 {
193 hb_codepoint_t value = base | v_offset | j;
194 // Emit all the missing values from next_value up to value - 1.
195 for (hb_codepoint_t k = *next_value; k < value && count < size; k++)
196 {
197 *p++ = k;
198 count++;
199 }
200 // Skip over this value;
201 *next_value = value + 1;
202 }
203 }
204 start_bit = 0;
205 }
206 return count;
207 }
208
209 bool is_equal (const hb_bit_page_t &other) const
210 {
211 for (unsigned i = 0; i < len (); i++)
212 if (v[i] != other.v[i])
213 return false;
214 return true;
215 }
216 bool is_subset (const hb_bit_page_t &larger_page) const
217 {
218 for (unsigned i = 0; i < len (); i++)
219 if (~larger_page.v[i] & v[i])
220 return false;
221 return true;
222 }
223
224 unsigned int get_population () const
225 {
226 return
227 + hb_iter (v)
228 | hb_reduce ([] (unsigned pop, const elt_t &_) { return pop + hb_popcount (_); }, 0u)
229 ;
230 }
231
232 bool next (hb_codepoint_t *codepoint) const
233 {
234 unsigned int m = (*codepoint + 1) & MASK;
235 if (!m)
236 {
237 *codepoint = INVALID;
238 return false;
239 }
240 unsigned int i = m / ELT_BITS;
241 unsigned int j = m & ELT_MASK;
242
243 const elt_t vv = v[i] & ~((elt_t (1) << j) - 1);
244 for (const elt_t *p = &vv; i < len (); p = &v[++i])
245 if (*p)
246 {
247 *codepoint = i * ELT_BITS + elt_get_min (*p);
248 return true;
249 }
250
251 *codepoint = INVALID;
252 return false;
253 }
254 bool previous (hb_codepoint_t *codepoint) const
255 {
256 unsigned int m = (*codepoint - 1) & MASK;
257 if (m == MASK)
258 {
259 *codepoint = INVALID;
260 return false;
261 }
262 unsigned int i = m / ELT_BITS;
263 unsigned int j = m & ELT_MASK;
264
265 /* Fancy mask to avoid shifting by elt_t bitsize, which is undefined. */
266 const elt_t mask = j < 8 * sizeof (elt_t) - 1 ?
267 ((elt_t (1) << (j + 1)) - 1) :
268 (elt_t) -1;
269 const elt_t vv = v[i] & mask;
270 const elt_t *p = &vv;
271 while (true)
272 {
273 if (*p)
274 {
275 *codepoint = i * ELT_BITS + elt_get_max (*p);
276 return true;
277 }
278 if ((int) i <= 0) break;
279 p = &v[--i];
280 }
281
282 *codepoint = INVALID;
283 return false;
284 }
285 hb_codepoint_t get_min () const
286 {
287 for (unsigned int i = 0; i < len (); i++)
288 if (v[i])
289 return i * ELT_BITS + elt_get_min (v[i]);
290 return INVALID;
291 }
292 hb_codepoint_t get_max () const
293 {
294 for (int i = len () - 1; i >= 0; i--)
295 if (v[i])
296 return i * ELT_BITS + elt_get_max (v[i]);
297 return 0;
298 }
299
300 static constexpr hb_codepoint_t INVALID = HB_SET_VALUE_INVALID;
301
302 typedef unsigned long long elt_t;
303 static constexpr unsigned PAGE_BITS = 512;
304 static_assert ((PAGE_BITS & ((PAGE_BITS) - 1)) == 0, "");
305 static constexpr unsigned PAGE_BITS_LOG_2 = 9;
306 static_assert (1 << PAGE_BITS_LOG_2 == PAGE_BITS, "");
307 static constexpr unsigned PAGE_BITMASK = PAGE_BITS - 1;
308
309 static unsigned int elt_get_min (const elt_t &elt) { return hb_ctz (elt); }
310 static unsigned int elt_get_max (const elt_t &elt) { return hb_bit_storage (elt) - 1; }
311
312 typedef hb_vector_size_t<elt_t, PAGE_BITS / 8> vector_t;
313
314 static constexpr unsigned ELT_BITS = sizeof (elt_t) * 8;
315 static constexpr unsigned ELT_MASK = ELT_BITS - 1;
316
317 static constexpr unsigned BITS = sizeof (vector_t) * 8;
318 static constexpr unsigned MASK = BITS - 1;
319 static_assert ((unsigned) PAGE_BITS == (unsigned) BITS, "");
320
321 elt_t &elt (hb_codepoint_t g) { return v[(g & MASK) / ELT_BITS]; }
322 const elt_t& elt (hb_codepoint_t g) const { return v[(g & MASK) / ELT_BITS]; }
323 static constexpr elt_t mask (hb_codepoint_t g) { return elt_t (1) << (g & ELT_MASK); }
324
325 vector_t v;
326 };
327 static_assert (hb_bit_page_t::PAGE_BITS == sizeof (hb_bit_page_t) * 8, "");
328
329
330 #endif /* HB_BIT_PAGE_HH */