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 struct hb_bit_page_t 34 { init0hb_bit_page_t35 void init0 () { v.clear (); } init1hb_bit_page_t36 void init1 () { v.clear (0xFF); } 37 lenhb_bit_page_t38 constexpr unsigned len () const 39 { return ARRAY_LENGTH_CONST (v); } 40 is_emptyhb_bit_page_t41 bool is_empty () const 42 { 43 for (unsigned int i = 0; i < len (); i++) 44 if (v[i]) 45 return false; 46 return true; 47 } 48 addhb_bit_page_t49 void add (hb_codepoint_t g) { elt (g) |= mask (g); } delhb_bit_page_t50 void del (hb_codepoint_t g) { elt (g) &= ~mask (g); } sethb_bit_page_t51 void set (hb_codepoint_t g, bool v) { if (v) add (g); else del (g); } gethb_bit_page_t52 bool get (hb_codepoint_t g) const { return elt (g) & mask (g); } 53 add_rangehb_bit_page_t54 void add_range (hb_codepoint_t a, hb_codepoint_t b) 55 { 56 elt_t *la = &elt (a); 57 elt_t *lb = &elt (b); 58 if (la == lb) 59 *la |= (mask (b) << 1) - mask(a); 60 else 61 { 62 *la |= ~(mask (a) - 1); 63 la++; 64 65 memset (la, 0xff, (char *) lb - (char *) la); 66 67 *lb |= ((mask (b) << 1) - 1); 68 } 69 } del_rangehb_bit_page_t70 void del_range (hb_codepoint_t a, hb_codepoint_t b) 71 { 72 elt_t *la = &elt (a); 73 elt_t *lb = &elt (b); 74 if (la == lb) 75 *la &= ~((mask (b) << 1) - mask(a)); 76 else 77 { 78 *la &= mask (a) - 1; 79 la++; 80 81 memset (la, 0, (char *) lb - (char *) la); 82 83 *lb &= ~((mask (b) << 1) - 1); 84 } 85 } set_rangehb_bit_page_t86 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); } 88 is_equalhb_bit_page_t89 bool is_equal (const hb_bit_page_t &other) const 90 { 91 return 0 == hb_memcmp (&v, &other.v, sizeof (v)); 92 } is_subsethb_bit_page_t93 bool is_subset (const hb_bit_page_t &larger_page) const 94 { 95 for (unsigned i = 0; i < len (); i++) 96 if (~larger_page.v[i] & v[i]) 97 return false; 98 return true; 99 } 100 get_populationhb_bit_page_t101 unsigned int get_population () const 102 { 103 unsigned int pop = 0; 104 for (unsigned int i = 0; i < len (); i++) 105 pop += hb_popcount (v[i]); 106 return pop; 107 } 108 nexthb_bit_page_t109 bool next (hb_codepoint_t *codepoint) const 110 { 111 unsigned int m = (*codepoint + 1) & MASK; 112 if (!m) 113 { 114 *codepoint = INVALID; 115 return false; 116 } 117 unsigned int i = m / ELT_BITS; 118 unsigned int j = m & ELT_MASK; 119 120 const elt_t vv = v[i] & ~((elt_t (1) << j) - 1); 121 for (const elt_t *p = &vv; i < len (); p = &v[++i]) 122 if (*p) 123 { 124 *codepoint = i * ELT_BITS + elt_get_min (*p); 125 return true; 126 } 127 128 *codepoint = INVALID; 129 return false; 130 } previoushb_bit_page_t131 bool previous (hb_codepoint_t *codepoint) const 132 { 133 unsigned int m = (*codepoint - 1) & MASK; 134 if (m == MASK) 135 { 136 *codepoint = INVALID; 137 return false; 138 } 139 unsigned int i = m / ELT_BITS; 140 unsigned int j = m & ELT_MASK; 141 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) : 145 (elt_t) -1; 146 const elt_t vv = v[i] & mask; 147 const elt_t *p = &vv; 148 while (true) 149 { 150 if (*p) 151 { 152 *codepoint = i * ELT_BITS + elt_get_max (*p); 153 return true; 154 } 155 if ((int) i <= 0) break; 156 p = &v[--i]; 157 } 158 159 *codepoint = INVALID; 160 return false; 161 } get_minhb_bit_page_t162 hb_codepoint_t get_min () const 163 { 164 for (unsigned int i = 0; i < len (); i++) 165 if (v[i]) 166 return i * ELT_BITS + elt_get_min (v[i]); 167 return INVALID; 168 } get_maxhb_bit_page_t169 hb_codepoint_t get_max () const 170 { 171 for (int i = len () - 1; i >= 0; i--) 172 if (v[i]) 173 return i * ELT_BITS + elt_get_max (v[i]); 174 return 0; 175 } 176 177 static constexpr hb_codepoint_t INVALID = HB_SET_VALUE_INVALID; 178 179 typedef unsigned long long elt_t; 180 static constexpr unsigned PAGE_BITS = 512; 181 static_assert ((PAGE_BITS & ((PAGE_BITS) - 1)) == 0, ""); 182 elt_get_minhb_bit_page_t183 static unsigned int elt_get_min (const elt_t &elt) { return hb_ctz (elt); } elt_get_maxhb_bit_page_t184 static unsigned int elt_get_max (const elt_t &elt) { return hb_bit_storage (elt) - 1; } 185 186 typedef hb_vector_size_t<elt_t, PAGE_BITS / 8> vector_t; 187 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, ""); 193 elthb_bit_page_t194 elt_t &elt (hb_codepoint_t g) { return v[(g & MASK) / ELT_BITS]; } elthb_bit_page_t195 const elt_t& elt (hb_codepoint_t g) const { return v[(g & MASK) / ELT_BITS]; } maskhb_bit_page_t196 static constexpr elt_t mask (hb_codepoint_t g) { return elt_t (1) << (g & ELT_MASK); } 197 198 vector_t v; 199 }; 200 static_assert (hb_bit_page_t::PAGE_BITS == sizeof (hb_bit_page_t) * 8, ""); 201 202 203 #endif /* HB_BIT_PAGE_HH */ 204