1 /* 2 * Copyright © 2012,2017 Google, Inc. 3 * 4 * This is part of HarfBuzz, a text shaping library. 5 * 6 * Permission is hereby granted, without written agreement and without 7 * license or royalty fees, to use, copy, modify, and distribute this 8 * software and its documentation for any purpose, provided that the 9 * above copyright notice and the following two paragraphs appear in 10 * all copies of this software. 11 * 12 * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR 13 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES 14 * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN 15 * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH 16 * DAMAGE. 17 * 18 * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, 19 * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND 20 * FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS 21 * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO 22 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. 23 * 24 * Google Author(s): Behdad Esfahbod 25 */ 26 27 #ifndef HB_SET_PRIVATE_HH 28 #define HB_SET_PRIVATE_HH 29 30 #include "hb-private.hh" 31 #include "hb-object-private.hh" 32 33 34 /* 35 * hb_set_t 36 */ 37 38 struct hb_set_t 39 { 40 struct page_map_t 41 { 42 inline int cmp (const page_map_t *o) const { return (int) o->major - (int) major; } 43 44 uint32_t major; 45 uint32_t index; 46 }; 47 48 struct page_t 49 { 50 inline void init (void) { 51 memset (&v, 0, sizeof (v)); 52 } 53 54 inline unsigned int len (void) const 55 { return ARRAY_LENGTH_CONST (v); } 56 57 inline bool is_empty (void) const 58 { 59 for (unsigned int i = 0; i < len (); i++) 60 if (v[i]) 61 return false; 62 return true; 63 } 64 65 inline void add (hb_codepoint_t g) { elt (g) |= mask (g); } 66 inline void del (hb_codepoint_t g) { elt (g) &= ~mask (g); } 67 inline bool has (hb_codepoint_t g) const { return !!(elt (g) & mask (g)); } 68 69 inline bool is_equal (const page_t *other) const 70 { 71 return 0 == memcmp (&v, &other->v, sizeof (v)); 72 } 73 74 inline unsigned int get_population (void) const 75 { 76 unsigned int pop = 0; 77 for (unsigned int i = 0; i < len (); i++) 78 pop += _hb_popcount (v[i]); 79 return pop; 80 } 81 82 inline bool next (hb_codepoint_t *codepoint) const 83 { 84 unsigned int m = (*codepoint + 1) & MASK; 85 if (!m) 86 { 87 *codepoint = INVALID; 88 return false; 89 } 90 unsigned int i = m / ELT_BITS; 91 unsigned int j = m & ELT_MASK; 92 93 for (; j < ELT_BITS; j++) 94 if (v[i] & (elt_t (1) << j)) 95 goto found; 96 for (i++; i < len (); i++) 97 if (v[i]) 98 for (j = 0; j < ELT_BITS; j++) 99 if (v[i] & (elt_t (1) << j)) 100 goto found; 101 102 *codepoint = INVALID; 103 return false; 104 105 found: 106 *codepoint = i * ELT_BITS + j; 107 return true; 108 } 109 inline hb_codepoint_t get_min (void) const 110 { 111 for (unsigned int i = 0; i < len (); i++) 112 if (v[i]) 113 { 114 elt_t e = v[i]; 115 for (unsigned int j = 0; j < ELT_BITS; j++) 116 if (e & (elt_t (1) << j)) 117 return i * ELT_BITS + j; 118 } 119 return INVALID; 120 } 121 inline hb_codepoint_t get_max (void) const 122 { 123 for (int i = len () - 1; i >= 0; i--) 124 if (v[i]) 125 { 126 elt_t e = v[i]; 127 for (int j = ELT_BITS - 1; j >= 0; j--) 128 if (e & (elt_t (1) << j)) 129 return i * ELT_BITS + j; 130 } 131 return 0; 132 } 133 134 static const unsigned int PAGE_BITS = 512; /* Use to tune. */ 135 static_assert ((PAGE_BITS & ((PAGE_BITS) - 1)) == 0, ""); 136 137 typedef uint64_t elt_t; 138 139 #if 0 && HAVE_VECTOR_SIZE 140 /* The vectorized version does not work with clang as non-const 141 * elt() errs "non-const reference cannot bind to vector element". */ 142 typedef elt_t vector_t __attribute__((vector_size (PAGE_BITS / 8))); 143 #else 144 typedef hb_vector_size_t<elt_t, PAGE_BITS / 8> vector_t; 145 #endif 146 147 vector_t v; 148 149 static const unsigned int ELT_BITS = sizeof (elt_t) * 8; 150 static const unsigned int ELT_MASK = ELT_BITS - 1; 151 static const unsigned int BITS = sizeof (vector_t) * 8; 152 static const unsigned int MASK = BITS - 1; 153 static_assert (PAGE_BITS == BITS, ""); 154 155 elt_t &elt (hb_codepoint_t g) { return v[(g & MASK) / ELT_BITS]; } 156 elt_t const &elt (hb_codepoint_t g) const { return v[(g & MASK) / ELT_BITS]; } 157 elt_t mask (hb_codepoint_t g) const { return elt_t (1) << (g & ELT_MASK); } 158 }; 159 static_assert (page_t::PAGE_BITS == sizeof (page_t) * 8, ""); 160 161 hb_object_header_t header; 162 ASSERT_POD (); 163 bool in_error; 164 hb_prealloced_array_t<page_map_t, 8> page_map; 165 hb_prealloced_array_t<page_t, 8> pages; 166 167 inline bool resize (unsigned int count) 168 { 169 if (unlikely (in_error)) return false; 170 if (!pages.resize (count) || !page_map.resize (count)) 171 { 172 pages.resize (page_map.len); 173 in_error = true; 174 return false; 175 } 176 return true; 177 } 178 179 inline void clear (void) { 180 if (unlikely (hb_object_is_inert (this))) 181 return; 182 in_error = false; 183 page_map.resize (0); 184 pages.resize (0); 185 } 186 inline bool is_empty (void) const { 187 unsigned int count = pages.len; 188 for (unsigned int i = 0; i < count; i++) 189 if (!pages[i].is_empty ()) 190 return false; 191 return true; 192 } 193 194 inline void add (hb_codepoint_t g) 195 { 196 if (unlikely (in_error)) return; 197 if (unlikely (g == INVALID)) return; 198 page_t *page = page_for_insert (g); 199 if (!page) 200 return; 201 page->add (g); 202 } 203 inline void add_range (hb_codepoint_t a, hb_codepoint_t b) 204 { 205 if (unlikely (in_error)) return; 206 /* TODO Speedup */ 207 for (unsigned int i = a; i < b + 1; i++) 208 add (i); 209 } 210 inline void del (hb_codepoint_t g) 211 { 212 if (unlikely (in_error)) return; 213 page_t *p = page_for (g); 214 if (!p) 215 return; 216 p->del (g); 217 } 218 inline void del_range (hb_codepoint_t a, hb_codepoint_t b) 219 { 220 if (unlikely (in_error)) return; 221 for (unsigned int i = a; i < b + 1; i++) 222 del (i); 223 } 224 inline bool has (hb_codepoint_t g) const 225 { 226 const page_t *p = page_for (g); 227 if (!p) 228 return false; 229 return p->has (g); 230 } 231 inline bool intersects (hb_codepoint_t first, 232 hb_codepoint_t last) const 233 { 234 hb_codepoint_t c = first - 1; 235 return next (&c) && c <= last; 236 } 237 inline void set (const hb_set_t *other) 238 { 239 if (unlikely (in_error)) return; 240 unsigned int count = other->pages.len; 241 if (!resize (count)) 242 return; 243 244 memcpy (pages.array, other->pages.array, count * sizeof (pages.array[0])); 245 memcpy (page_map.array, other->page_map.array, count * sizeof (page_map.array[0])); 246 } 247 248 inline bool is_equal (const hb_set_t *other) const 249 { 250 unsigned int na = pages.len; 251 unsigned int nb = other->pages.len; 252 253 unsigned int a = 0, b = 0; 254 for (; a < na && b < nb; ) 255 { 256 if (page_at (a).is_empty ()) { a++; continue; } 257 if (other->page_at (b).is_empty ()) { b++; continue; } 258 if (page_map[a].major != other->page_map[b].major || 259 !page_at (a).is_equal (&other->page_at (b))) 260 return false; 261 a++; 262 b++; 263 } 264 for (; a < na; a++) 265 if (!page_at (a).is_empty ()) { return false; } 266 for (; b < nb; b++) 267 if (!other->page_at (b).is_empty ()) { return false; } 268 269 return true; 270 } 271 272 template <class Op> 273 inline void process (const hb_set_t *other) 274 { 275 if (unlikely (in_error)) return; 276 277 unsigned int na = pages.len; 278 unsigned int nb = other->pages.len; 279 280 unsigned int count = 0; 281 unsigned int a = 0, b = 0; 282 for (; a < na && b < nb; ) 283 { 284 if (page_map[a].major == other->page_map[b].major) 285 { 286 count++; 287 a++; 288 b++; 289 } 290 else if (page_map[a].major < other->page_map[b].major) 291 { 292 if (Op::passthru_left) 293 count++; 294 a++; 295 } 296 else 297 { 298 if (Op::passthru_right) 299 count++; 300 b++; 301 } 302 } 303 if (Op::passthru_left) 304 count += na - a; 305 if (Op::passthru_right) 306 count += nb - b; 307 308 if (!resize (count)) 309 return; 310 311 /* Process in-place backward. */ 312 a = na; 313 b = nb; 314 for (; a && b; ) 315 { 316 if (page_map[a - 1].major == other->page_map[b - 1].major) 317 { 318 a--; 319 b--; 320 Op::process (page_at (--count).v, page_at (a).v, other->page_at (b).v); 321 } 322 else if (page_map[a - 1].major > other->page_map[b - 1].major) 323 { 324 a--; 325 if (Op::passthru_left) 326 page_at (--count).v = page_at (a).v; 327 } 328 else 329 { 330 b--; 331 if (Op::passthru_right) 332 page_at (--count).v = other->page_at (b).v; 333 } 334 } 335 if (Op::passthru_left) 336 while (a) 337 page_at (--count).v = page_at (--a).v; 338 if (Op::passthru_right) 339 while (b) 340 page_at (--count).v = other->page_at (--b).v; 341 assert (!count); 342 } 343 344 inline void union_ (const hb_set_t *other) 345 { 346 process<HbOpOr> (other); 347 } 348 inline void intersect (const hb_set_t *other) 349 { 350 process<HbOpAnd> (other); 351 } 352 inline void subtract (const hb_set_t *other) 353 { 354 process<HbOpMinus> (other); 355 } 356 inline void symmetric_difference (const hb_set_t *other) 357 { 358 process<HbOpXor> (other); 359 } 360 inline bool next (hb_codepoint_t *codepoint) const 361 { 362 if (unlikely (*codepoint == INVALID)) { 363 *codepoint = get_min (); 364 return *codepoint != INVALID; 365 } 366 367 page_map_t map = {get_major (*codepoint), 0}; 368 unsigned int i; 369 page_map.bfind (&map, &i); 370 if (i < page_map.len) 371 { 372 if (pages[page_map[i].index].next (codepoint)) 373 { 374 *codepoint += page_map[i].major * page_t::PAGE_BITS; 375 return true; 376 } 377 i++; 378 } 379 for (; i < page_map.len; i++) 380 { 381 hb_codepoint_t m = pages[page_map[i].index].get_min (); 382 if (m != INVALID) 383 { 384 *codepoint = page_map[i].major * page_t::PAGE_BITS + m; 385 return true; 386 } 387 } 388 *codepoint = INVALID; 389 return false; 390 } 391 inline bool next_range (hb_codepoint_t *first, hb_codepoint_t *last) const 392 { 393 hb_codepoint_t i; 394 395 i = *last; 396 if (!next (&i)) 397 { 398 *last = *first = INVALID; 399 return false; 400 } 401 402 *last = *first = i; 403 while (next (&i) && i == *last + 1) 404 (*last)++; 405 406 return true; 407 } 408 409 inline unsigned int get_population (void) const 410 { 411 unsigned int pop = 0; 412 unsigned int count = pages.len; 413 for (unsigned int i = 0; i < count; i++) 414 pop += pages[i].get_population (); 415 return pop; 416 } 417 inline hb_codepoint_t get_min (void) const 418 { 419 unsigned int count = pages.len; 420 for (unsigned int i = 0; i < count; i++) 421 if (!page_at (i).is_empty ()) 422 return page_map[i].major * page_t::PAGE_BITS + page_at (i).get_min (); 423 return INVALID; 424 } 425 inline hb_codepoint_t get_max (void) const 426 { 427 unsigned int count = pages.len; 428 for (int i = count - 1; i >= 0; i++) 429 if (!page_at (i).is_empty ()) 430 return page_map[i].major * page_t::PAGE_BITS + page_at (i).get_max (); 431 return INVALID; 432 } 433 434 static const hb_codepoint_t INVALID = HB_SET_VALUE_INVALID; 435 436 page_t *page_for_insert (hb_codepoint_t g) 437 { 438 page_map_t map = {get_major (g), pages.len}; 439 unsigned int i; 440 if (!page_map.bfind (&map, &i)) 441 { 442 if (!resize (pages.len + 1)) 443 return nullptr; 444 445 pages[map.index].init (); 446 memmove (&page_map[i + 1], &page_map[i], (page_map.len - 1 - i) * sizeof (page_map[0])); 447 page_map[i] = map; 448 } 449 return &pages[page_map[i].index]; 450 } 451 page_t *page_for (hb_codepoint_t g) 452 { 453 page_map_t key = {get_major (g)}; 454 const page_map_t *found = page_map.bsearch (&key); 455 if (found) 456 return &pages[found->index]; 457 return nullptr; 458 } 459 const page_t *page_for (hb_codepoint_t g) const 460 { 461 page_map_t key = {get_major (g)}; 462 const page_map_t *found = page_map.bsearch (&key); 463 if (found) 464 return &pages[found->index]; 465 return nullptr; 466 } 467 page_t &page_at (unsigned int i) { return pages[page_map[i].index]; } 468 const page_t &page_at (unsigned int i) const { return pages[page_map[i].index]; } 469 unsigned int get_major (hb_codepoint_t g) const { return g / page_t::PAGE_BITS; } 470 }; 471 472 473 #endif /* HB_SET_PRIVATE_HH */