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 { operator []hb_vector_size_t41 elt_t& operator [] (unsigned int i) { return v[i]; } operator []hb_vector_size_t42 const elt_t& operator [] (unsigned int i) const { return v[i]; } 43 clearhb_vector_size_t44 void clear (unsigned char v = 0) { hb_memset (this, v, sizeof (*this)); } 45 46 template <typename Op> processhb_vector_size_t47 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> processhb_vector_size_t55 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 } operator |hb_vector_size_t62 hb_vector_size_t operator | (const hb_vector_size_t &o) const 63 { return process (hb_bitwise_or, o); } operator &hb_vector_size_t64 hb_vector_size_t operator & (const hb_vector_size_t &o) const 65 { return process (hb_bitwise_and, o); } operator ^hb_vector_size_t66 hb_vector_size_t operator ^ (const hb_vector_size_t &o) const 67 { return process (hb_bitwise_xor, o); } operator ~hb_vector_size_t68 hb_vector_size_t operator ~ () const 69 { return process (hb_bitwise_neg); } 70 iterhb_vector_size_t71 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 { init0hb_bit_page_t82 void init0 () { v.clear (); } init1hb_bit_page_t83 void init1 () { v.clear (0xFF); } 84 lenhb_bit_page_t85 constexpr unsigned len () const 86 { return ARRAY_LENGTH_CONST (v); } 87 is_emptyhb_bit_page_t88 bool is_empty () const 89 { 90 return 91 + hb_iter (v) 92 | hb_none 93 ; 94 } hashhb_bit_page_t95 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 addhb_bit_page_t103 void add (hb_codepoint_t g) { elt (g) |= mask (g); } delhb_bit_page_t104 void del (hb_codepoint_t g) { elt (g) &= ~mask (g); } sethb_bit_page_t105 void set (hb_codepoint_t g, bool value) { if (value) add (g); else del (g); } gethb_bit_page_t106 bool get (hb_codepoint_t g) const { return elt (g) & mask (g); } 107 add_rangehb_bit_page_t108 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 } del_rangehb_bit_page_t124 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 } set_rangehb_bit_page_t140 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. writehb_bit_page_t146 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. write_invertedhb_bit_page_t176 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 is_equalhb_bit_page_t209 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 } is_subsethb_bit_page_t216 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 get_populationhb_bit_page_t224 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 nexthb_bit_page_t232 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 } previoushb_bit_page_t254 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 } get_minhb_bit_page_t285 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 } get_maxhb_bit_page_t292 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 elt_get_minhb_bit_page_t309 static unsigned int elt_get_min (const elt_t &elt) { return hb_ctz (elt); } elt_get_maxhb_bit_page_t310 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 elthb_bit_page_t321 elt_t &elt (hb_codepoint_t g) { return v[(g & MASK) / ELT_BITS]; } elthb_bit_page_t322 const elt_t& elt (hb_codepoint_t g) const { return v[(g & MASK) / ELT_BITS]; } maskhb_bit_page_t323 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 */ 331