src/hb-set-private.hh

   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 /* TODO Keep a free-list so we can free pages that are completely zeroed.  At that
  39  * point maybe also use a sentinel value for "all-1" pages? */
  40
  41 struct hb_set_t
  42 {
  43   struct page_map_t
  44   {
  45     inline int cmp (const page_map_t *o) const { return (int) o->major - (int) major; }
  46
  47     uint32_t major;
  48     uint32_t index;
  49   };
  50
  51   struct page_t
  52   {
  53     inline void init0 (void) { memset (&v, 0, sizeof (v)); }
  54     inline void init1 (void) { memset (&v, 0xff, sizeof (v)); }
  55
  56     inline unsigned int len (void) const
  57     { return ARRAY_LENGTH_CONST (v); }
  58
  59     inline bool is_empty (void) const
  60     {
  61       for (unsigned int i = 0; i < len (); i++)
  62         if (v[i])
  63           return false;
  64       return true;
  65     }
  66
  67     inline void add (hb_codepoint_t g) { elt (g) |= mask (g); }
  68     inline void del (hb_codepoint_t g) { elt (g) &= ~mask (g); }
  69     inline bool has (hb_codepoint_t g) const { return !!(elt (g) & mask (g)); }
  70
  71     inline void add_range (hb_codepoint_t a, hb_codepoint_t b)
  72     {
  73       elt_t *la = &elt (a);
  74       elt_t *lb = &elt (b);
  75       if (la == lb)
  76         *la |= (mask (b) << 1) - mask(a);
  77       else
  78       {
  79         *la |= ~(mask (a) - 1);
  80         la++;
  81
  82         memset (la, 0xff, (char *) lb - (char *) la);
  83
  84         *lb |= ((mask (b) << 1) - 1);
  85       }
  86     }
  87
  88     inline bool is_equal (const page_t *other) const
  89     {
  90       return 0 == memcmp (&v, &other->v, sizeof (v));
  91     }
  92
  93     inline unsigned int get_population (void) const
  94     {
  95       unsigned int pop = 0;
  96       for (unsigned int i = 0; i < len (); i++)
  97         pop += _hb_popcount (v[i]);
  98       return pop;
  99     }
 100
 101     inline bool next (hb_codepoint_t *codepoint) const
 102     {
 103       unsigned int m = (*codepoint + 1) & MASK;
 104       if (!m)
 105       {
 106         *codepoint = INVALID;
 107         return false;
 108       }
 109       unsigned int i = m / ELT_BITS;
 110       unsigned int j = m & ELT_MASK;
 111
 112       const elt_t vv = v[i] & ~((elt_t (1) << j) - 1);
 113       for (const elt_t *p = &vv; i < len (); p = &v[++i])
 114         if (*p)
 115         {
 116           *codepoint = i * ELT_BITS + elt_get_min (*p);
 117           return true;
 118         }
 119
 120       *codepoint = INVALID;
 121       return false;
 122     }
 123     inline bool previous (hb_codepoint_t *codepoint) const
 124     {
 125       unsigned int m = (*codepoint - 1) & MASK;
 126       if (m == MASK)
 127       {
 128         *codepoint = INVALID;
 129         return false;
 130       }
 131       unsigned int i = m / ELT_BITS;
 132       unsigned int j = m & ELT_MASK;
 133
 134       const elt_t vv = v[i] & ((elt_t (1) << (j + 1)) - 1);
 135       for (const elt_t *p = &vv; (int) i >= 0; p = &v[--i])
 136         if (*p)
 137         {
 138           *codepoint = i * ELT_BITS + elt_get_max (*p);
 139           return true;
 140         }
 141
 142       *codepoint = INVALID;
 143       return false;
 144     }
 145     inline hb_codepoint_t get_min (void) const
 146     {
 147       for (unsigned int i = 0; i < len (); i++)
 148         if (v[i])
 149           return i * ELT_BITS + elt_get_min (v[i]);
 150       return INVALID;
 151     }
 152     inline hb_codepoint_t get_max (void) const
 153     {
 154       for (int i = len () - 1; i >= 0; i--)
 155         if (v[i])
 156           return i * ELT_BITS + elt_get_max (v[i]);
 157       return 0;
 158     }
 159
 160     typedef unsigned long long elt_t;
 161     static const unsigned int PAGE_BITS = 1024;
 162     static_assert ((PAGE_BITS & ((PAGE_BITS) - 1)) == 0, "");
 163
 164     static inline unsigned int elt_get_min (const elt_t &elt) { return _hb_ctz (elt); }
 165     static inline unsigned int elt_get_max (const elt_t &elt) { return _hb_bit_storage (elt) - 1; }
 166
 167 #if 0 && HAVE_VECTOR_SIZE
 168     /* The vectorized version does not work with clang as non-const
 169      * elt() errs "non-const reference cannot bind to vector element". */
 170     typedef elt_t vector_t __attribute__((vector_size (PAGE_BITS / 8)));
 171 #else
 172     typedef hb_vector_size_t<elt_t, PAGE_BITS / 8> vector_t;
 173 #endif
 174
 175     vector_t v;
 176
 177     static const unsigned int ELT_BITS = sizeof (elt_t) * 8;
 178     static const unsigned int ELT_MASK = ELT_BITS - 1;
 179     static const unsigned int BITS = sizeof (vector_t) * 8;
 180     static const unsigned int MASK = BITS - 1;
 181     static_assert (PAGE_BITS == BITS, "");
 182
 183     elt_t &elt (hb_codepoint_t g) { return v[(g & MASK) / ELT_BITS]; }
 184     elt_t const &elt (hb_codepoint_t g) const { return v[(g & MASK) / ELT_BITS]; }
 185     elt_t mask (hb_codepoint_t g) const { return elt_t (1) << (g & ELT_MASK); }
 186   };
 187   static_assert (page_t::PAGE_BITS == sizeof (page_t) * 8, "");
 188
 189   hb_object_header_t header;
 190   ASSERT_POD ();
 191   bool in_error;
 192   hb_prealloced_array_t<page_map_t, 8> page_map;
 193   hb_prealloced_array_t<page_t, 1> pages;
 194
 195   inline void init (void)
 196   {
 197     in_error = false;
 198     page_map.init ();
 199     pages.init ();
 200   }
 201   inline void finish (void)
 202   {
 203     page_map.finish ();
 204     pages.finish ();
 205   }
 206
 207   inline bool resize (unsigned int count)
 208   {
 209     if (unlikely (in_error)) return false;
 210     if (!pages.resize (count) || !page_map.resize (count))
 211     {
 212       pages.resize (page_map.len);
 213       in_error = true;
 214       return false;
 215     }
 216     return true;
 217   }
 218
 219   inline void clear (void) {
 220     if (unlikely (hb_object_is_inert (this)))
 221       return;
 222     in_error = false;
 223     page_map.resize (0);
 224     pages.resize (0);
 225   }
 226   inline bool is_empty (void) const {
 227     unsigned int count = pages.len;
 228     for (unsigned int i = 0; i < count; i++)
 229       if (!pages[i].is_empty ())
 230         return false;
 231     return true;
 232   }
 233
 234   inline void add (hb_codepoint_t g)
 235   {
 236     if (unlikely (in_error)) return;
 237     if (unlikely (g == INVALID)) return;
 238     page_t *page = page_for_insert (g); if (unlikely (!page)) return;
 239     page->add (g);
 240   }
 241   inline bool add_range (hb_codepoint_t a, hb_codepoint_t b)
 242   {
 243     if (unlikely (in_error)) return true; /* https://github.com/harfbuzz/harfbuzz/issues/657 */
 244     if (unlikely (a > b || a == INVALID || b == INVALID)) return false;
 245     unsigned int ma = get_major (a);
 246     unsigned int mb = get_major (b);
 247     if (ma == mb)
 248     {
 249       page_t *page = page_for_insert (a); if (unlikely (!page)) return false;
 250       page->add_range (a, b);
 251     }
 252     else
 253     {
 254       page_t *page = page_for_insert (a); if (unlikely (!page)) return false;
 255       page->add_range (a, major_start (ma + 1) - 1);
 256
 257       for (unsigned int m = ma + 1; m < mb; m++)
 258       {
 259         page = page_for_insert (major_start (m)); if (unlikely (!page)) return false;
 260         page->init1 ();
 261       }
 262
 263       page = page_for_insert (b); if (unlikely (!page)) return false;
 264       page->add_range (major_start (mb), b);
 265     }
 266     return true;
 267   }
 268
 269   template <typename T>
 270   inline void add_array (const T *array, unsigned int count, unsigned int stride=sizeof(T))
 271   {
 272     if (unlikely (in_error)) return;
 273     if (!count) return;
 274     hb_codepoint_t g = *array;
 275     while (count)
 276     {
 277       unsigned int m = get_major (g);
 278       page_t *page = page_for_insert (g); if (unlikely (!page)) return;
 279       unsigned int start = major_start (m);
 280       unsigned int end = major_start (m + 1);
 281       do
 282       {
 283         page->add (g);
 284
 285         array = (const T *) ((const char *) array + stride);
 286         count--;
 287       }
 288       while (count && (g = *array, start <= g && g < end));
 289     }
 290   }
 291
 292   /* Might return false if array looks unsorted.
 293    * Used for faster rejection of corrupt data. */
 294   template <typename T>
 295   inline bool add_sorted_array (const T *array, unsigned int count, unsigned int stride=sizeof(T))
 296   {
 297     if (unlikely (in_error)) return true; /* https://github.com/harfbuzz/harfbuzz/issues/657 */
 298     if (!count) return true;
 299     hb_codepoint_t g = *array;
 300     hb_codepoint_t last_g = g;
 301     while (count)
 302     {
 303       unsigned int m = get_major (g);
 304       page_t *page = page_for_insert (g); if (unlikely (!page)) return false;
 305       unsigned int end = major_start (m + 1);
 306       do
 307       {
 308         /* If we try harder we can change the following comparison to <=;
 309          * Not sure if it's worth it. */
 310         if (g < last_g) return false;
 311         last_g = g;
 312         page->add (g);
 313
 314         array = (const T *) ((const char *) array + stride);
 315         count--;
 316       }
 317       while (count && (g = *array, g < end));
 318     }
 319     return true;
 320   }
 321
 322   inline void del (hb_codepoint_t g)
 323   {
 324     if (unlikely (in_error)) return;
 325     page_t *p = page_for (g);
 326     if (!p)
 327       return;
 328     p->del (g);
 329   }
 330   inline void del_range (hb_codepoint_t a, hb_codepoint_t b)
 331   {
 332     /* TODO Optimize, like add_range(). */
 333     if (unlikely (in_error)) return;
 334     for (unsigned int i = a; i < b + 1; i++)
 335       del (i);
 336   }
 337   inline bool has (hb_codepoint_t g) const
 338   {
 339     const page_t *p = page_for (g);
 340     if (!p)
 341       return false;
 342     return p->has (g);
 343   }
 344   inline bool intersects (hb_codepoint_t first,
 345                           hb_codepoint_t last) const
 346   {
 347     hb_codepoint_t c = first - 1;
 348     return next (&c) && c <= last;
 349   }
 350   inline void set (const hb_set_t *other)
 351   {
 352     if (unlikely (in_error)) return;
 353     unsigned int count = other->pages.len;
 354     if (!resize (count))
 355       return;
 356
 357     memcpy (pages.array, other->pages.array, count * sizeof (pages.array[0]));
 358     memcpy (page_map.array, other->page_map.array, count * sizeof (page_map.array[0]));
 359   }
 360
 361   inline bool is_equal (const hb_set_t *other) const
 362   {
 363     unsigned int na = pages.len;
 364     unsigned int nb = other->pages.len;
 365
 366     unsigned int a = 0, b = 0;
 367     for (; a < na && b < nb; )
 368     {
 369       if (page_at (a).is_empty ()) { a++; continue; }
 370       if (other->page_at (b).is_empty ()) { b++; continue; }
 371       if (page_map[a].major != other->page_map[b].major ||
 372           !page_at (a).is_equal (&other->page_at (b)))
 373         return false;
 374       a++;
 375       b++;
 376     }
 377     for (; a < na; a++)
 378       if (!page_at (a).is_empty ()) { return false; }
 379     for (; b < nb; b++)
 380       if (!other->page_at (b).is_empty ()) { return false; }
 381
 382     return true;
 383   }
 384
 385   template <class Op>
 386   inline void process (const hb_set_t *other)
 387   {
 388     if (unlikely (in_error)) return;
 389
 390     unsigned int na = pages.len;
 391     unsigned int nb = other->pages.len;
 392     unsigned int next_page = na;
 393
 394     unsigned int count = 0;
 395     unsigned int a = 0, b = 0;
 396     for (; a < na && b < nb; )
 397     {
 398       if (page_map[a].major == other->page_map[b].major)
 399       {
 400         count++;
 401         a++;
 402         b++;
 403       }
 404       else if (page_map[a].major < other->page_map[b].major)
 405       {
 406         if (Op::passthru_left)
 407           count++;
 408         a++;
 409       }
 410       else
 411       {
 412         if (Op::passthru_right)
 413           count++;
 414         b++;
 415       }
 416     }
 417     if (Op::passthru_left)
 418       count += na - a;
 419     if (Op::passthru_right)
 420       count += nb - b;
 421
 422     if (!resize (count))
 423       return;
 424
 425     /* Process in-place backward. */
 426     a = na;
 427     b = nb;
 428     for (; a && b; )
 429     {
 430       if (page_map[a - 1].major == other->page_map[b - 1].major)
 431       {
 432         a--;
 433         b--;
 434         count--;
 435         page_map[count] = page_map[a];
 436         Op::process (page_at (count).v, page_at (a).v, other->page_at (b).v);
 437       }
 438       else if (page_map[a - 1].major > other->page_map[b - 1].major)
 439       {
 440         a--;
 441         if (Op::passthru_left)
 442         {
 443           count--;
 444           page_map[count] = page_map[a];
 445         }
 446       }
 447       else
 448       {
 449         b--;
 450         if (Op::passthru_right)
 451         {
 452           count--;
 453           page_map[count].major = other->page_map[b].major;
 454           page_map[count].index = next_page++;
 455           page_at (count).v = other->page_at (b).v;
 456         }
 457       }
 458     }
 459     if (Op::passthru_left)
 460       while (a)
 461       {
 462         a--;
 463         count--;
 464         page_map[count] = page_map [a];
 465       }
 466     if (Op::passthru_right)
 467       while (b)
 468       {
 469         b--;
 470         count--;
 471         page_map[count].major = other->page_map[b].major;
 472         page_map[count].index = next_page++;
 473         page_at (count).v = other->page_at (b).v;
 474       }
 475     assert (!count);
 476   }
 477
 478   inline void union_ (const hb_set_t *other)
 479   {
 480     process<HbOpOr> (other);
 481   }
 482   inline void intersect (const hb_set_t *other)
 483   {
 484     process<HbOpAnd> (other);
 485   }
 486   inline void subtract (const hb_set_t *other)
 487   {
 488     process<HbOpMinus> (other);
 489   }
 490   inline void symmetric_difference (const hb_set_t *other)
 491   {
 492     process<HbOpXor> (other);
 493   }
 494   inline bool next (hb_codepoint_t *codepoint) const
 495   {
 496     if (unlikely (*codepoint == INVALID)) {
 497       *codepoint = get_min ();
 498       return *codepoint != INVALID;
 499     }
 500
 501     page_map_t map = {get_major (*codepoint), 0};
 502     unsigned int i;
 503     page_map.bfind (map, &i);
 504     if (i < page_map.len && page_map[i].major == map.major)
 505     {
 506       if (pages[page_map[i].index].next (codepoint))
 507       {
 508         *codepoint += page_map[i].major * page_t::PAGE_BITS;
 509         return true;
 510       }
 511       i++;
 512     }
 513     for (; i < page_map.len; i++)
 514     {
 515       hb_codepoint_t m = pages[page_map[i].index].get_min ();
 516       if (m != INVALID)
 517       {
 518         *codepoint = page_map[i].major * page_t::PAGE_BITS + m;
 519         return true;
 520       }
 521     }
 522     *codepoint = INVALID;
 523     return false;
 524   }
 525   inline bool previous (hb_codepoint_t *codepoint) const
 526   {
 527     if (unlikely (*codepoint == INVALID)) {
 528       *codepoint = get_max ();
 529       return *codepoint != INVALID;
 530     }
 531
 532     page_map_t map = {get_major (*codepoint), 0};
 533     unsigned int i;
 534     page_map.bfind (map, &i);
 535     if (i < page_map.len && page_map[i].major == map.major)
 536     {
 537       if (pages[page_map[i].index].previous (codepoint))
 538       {
 539         *codepoint += page_map[i].major * page_t::PAGE_BITS;
 540         return true;
 541       }
 542     }
 543     i--;
 544     for (; (int) i >= 0; i--)
 545     {
 546       hb_codepoint_t m = pages[page_map[i].index].get_max ();
 547       if (m != INVALID)
 548       {
 549         *codepoint = page_map[i].major * page_t::PAGE_BITS + m;
 550         return true;
 551       }
 552     }
 553     *codepoint = INVALID;
 554     return false;
 555   }
 556   inline bool next_range (hb_codepoint_t *first, hb_codepoint_t *last) const
 557   {
 558     hb_codepoint_t i;
 559
 560     i = *last;
 561     if (!next (&i))
 562     {
 563       *last = *first = INVALID;
 564       return false;
 565     }
 566
 567     /* TODO Speed up. */
 568     *last = *first = i;
 569     while (next (&i) && i == *last + 1)
 570       (*last)++;
 571
 572     return true;
 573   }
 574   inline bool previous_range (hb_codepoint_t *first, hb_codepoint_t *last) const
 575   {
 576     hb_codepoint_t i;
 577
 578     i = *first;
 579     if (!previous (&i))
 580     {
 581       *last = *first = INVALID;
 582       return false;
 583     }
 584
 585     /* TODO Speed up. */
 586     *last = *first = i;
 587     while (previous (&i) && i == *first - 1)
 588       (*first)--;
 589
 590     return true;
 591   }
 592
 593   inline unsigned int get_population (void) const
 594   {
 595     unsigned int pop = 0;
 596     unsigned int count = pages.len;
 597     for (unsigned int i = 0; i < count; i++)
 598       pop += pages[i].get_population ();
 599     return pop;
 600   }
 601   inline hb_codepoint_t get_min (void) const
 602   {
 603     unsigned int count = pages.len;
 604     for (unsigned int i = 0; i < count; i++)
 605       if (!page_at (i).is_empty ())
 606         return page_map[i].major * page_t::PAGE_BITS + page_at (i).get_min ();
 607     return INVALID;
 608   }
 609   inline hb_codepoint_t get_max (void) const
 610   {
 611     unsigned int count = pages.len;
 612     for (int i = count - 1; i >= 0; i++)
 613       if (!page_at (i).is_empty ())
 614         return page_map[i].major * page_t::PAGE_BITS + page_at (i).get_max ();
 615     return INVALID;
 616   }
 617
 618   static  const hb_codepoint_t INVALID = HB_SET_VALUE_INVALID;
 619
 620   inline page_t *page_for_insert (hb_codepoint_t g)
 621   {
 622     page_map_t map = {get_major (g), pages.len};
 623     unsigned int i;
 624     if (!page_map.bfind (map, &i))
 625     {
 626       if (!resize (pages.len + 1))
 627         return nullptr;
 628
 629       pages[map.index].init0 ();
 630       memmove (&page_map[i + 1], &page_map[i], (page_map.len - 1 - i) * sizeof (page_map[0]));
 631       page_map[i] = map;
 632     }
 633     return &pages[page_map[i].index];
 634   }
 635   inline page_t *page_for (hb_codepoint_t g)
 636   {
 637     page_map_t key = {get_major (g)};
 638     const page_map_t *found = page_map.bsearch (key);
 639     if (found)
 640       return &pages[found->index];
 641     return nullptr;
 642   }
 643   inline const page_t *page_for (hb_codepoint_t g) const
 644   {
 645     page_map_t key = {get_major (g)};
 646     const page_map_t *found = page_map.bsearch (key);
 647     if (found)
 648       return &pages[found->index];
 649     return nullptr;
 650   }
 651   inline page_t &page_at (unsigned int i) { return pages[page_map[i].index]; }
 652   inline const page_t &page_at (unsigned int i) const { return pages[page_map[i].index]; }
 653   inline unsigned int get_major (hb_codepoint_t g) const { return g / page_t::PAGE_BITS; }
 654   inline hb_codepoint_t major_start (unsigned int major) const { return major * page_t::PAGE_BITS; }
 655 };
 656
 657
 658 #endif /* HB_SET_PRIVATE_HH */