2 * Copyright © 2012,2017 Google, Inc.
3 * Copyright © 2021 Behdad Esfahbod
5 * This is part of HarfBuzz, a text shaping library.
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.
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
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.
25 * Google Author(s): Behdad Esfahbod
28 #ifndef HB_BIT_PAGE_HH
29 #define HB_BIT_PAGE_HH
35 void init0 () { v.clear (); }
36 void init1 () { v.clear (0xFF); }
38 constexpr unsigned len () const
39 { return ARRAY_LENGTH_CONST (v); }
41 bool is_empty () const
43 for (unsigned int i = 0; i < len (); i++)
49 void add (hb_codepoint_t g) { elt (g) |= mask (g); }
50 void del (hb_codepoint_t g) { elt (g) &= ~mask (g); }
51 void set (hb_codepoint_t g, bool v) { if (v) add (g); else del (g); }
52 bool get (hb_codepoint_t g) const { return elt (g) & mask (g); }
54 void add_range (hb_codepoint_t a, hb_codepoint_t b)
59 *la |= (mask (b) << 1) - mask(a);
62 *la |= ~(mask (a) - 1);
65 memset (la, 0xff, (char *) lb - (char *) la);
67 *lb |= ((mask (b) << 1) - 1);
70 void del_range (hb_codepoint_t a, hb_codepoint_t b)
75 *la &= ~((mask (b) << 1) - mask(a));
81 memset (la, 0, (char *) lb - (char *) la);
83 *lb &= ~((mask (b) << 1) - 1);
86 void set_range (hb_codepoint_t a, hb_codepoint_t b, bool v)
87 { if (v) add_range (a, b); else del_range (a, b); }
89 bool is_equal (const hb_bit_page_t &other) const
91 return 0 == hb_memcmp (&v, &other.v, sizeof (v));
93 bool is_subset (const hb_bit_page_t &larger_page) const
95 for (unsigned i = 0; i < len (); i++)
96 if (~larger_page.v[i] & v[i])
101 unsigned int get_population () const
103 unsigned int pop = 0;
104 for (unsigned int i = 0; i < len (); i++)
105 pop += hb_popcount (v[i]);
109 bool next (hb_codepoint_t *codepoint) const
111 unsigned int m = (*codepoint + 1) & MASK;
114 *codepoint = INVALID;
117 unsigned int i = m / ELT_BITS;
118 unsigned int j = m & ELT_MASK;
120 const elt_t vv = v[i] & ~((elt_t (1) << j) - 1);
121 for (const elt_t *p = &vv; i < len (); p = &v[++i])
124 *codepoint = i * ELT_BITS + elt_get_min (*p);
128 *codepoint = INVALID;
131 bool previous (hb_codepoint_t *codepoint) const
133 unsigned int m = (*codepoint - 1) & MASK;
136 *codepoint = INVALID;
139 unsigned int i = m / ELT_BITS;
140 unsigned int j = m & ELT_MASK;
142 /* Fancy mask to avoid shifting by elt_t bitsize, which is undefined. */
143 const elt_t mask = j < 8 * sizeof (elt_t) - 1 ?
144 ((elt_t (1) << (j + 1)) - 1) :
146 const elt_t vv = v[i] & mask;
147 const elt_t *p = &vv;
152 *codepoint = i * ELT_BITS + elt_get_max (*p);
155 if ((int) i <= 0) break;
159 *codepoint = INVALID;
162 hb_codepoint_t get_min () const
164 for (unsigned int i = 0; i < len (); i++)
166 return i * ELT_BITS + elt_get_min (v[i]);
169 hb_codepoint_t get_max () const
171 for (int i = len () - 1; i >= 0; i--)
173 return i * ELT_BITS + elt_get_max (v[i]);
177 static constexpr hb_codepoint_t INVALID = HB_SET_VALUE_INVALID;
179 typedef unsigned long long elt_t;
180 static constexpr unsigned PAGE_BITS = 512;
181 static_assert ((PAGE_BITS & ((PAGE_BITS) - 1)) == 0, "");
183 static unsigned int elt_get_min (const elt_t &elt) { return hb_ctz (elt); }
184 static unsigned int elt_get_max (const elt_t &elt) { return hb_bit_storage (elt) - 1; }
186 typedef hb_vector_size_t<elt_t, PAGE_BITS / 8> vector_t;
188 static constexpr unsigned ELT_BITS = sizeof (elt_t) * 8;
189 static constexpr unsigned ELT_MASK = ELT_BITS - 1;
190 static constexpr unsigned BITS = sizeof (vector_t) * 8;
191 static constexpr unsigned MASK = BITS - 1;
192 static_assert ((unsigned) PAGE_BITS == (unsigned) BITS, "");
194 elt_t &elt (hb_codepoint_t g) { return v[(g & MASK) / ELT_BITS]; }
195 const elt_t& elt (hb_codepoint_t g) const { return v[(g & MASK) / ELT_BITS]; }
196 static constexpr elt_t mask (hb_codepoint_t g) { return elt_t (1) << (g & ELT_MASK); }
200 static_assert (hb_bit_page_t::PAGE_BITS == sizeof (hb_bit_page_t) * 8, "");
203 #endif /* HB_BIT_PAGE_HH */