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 = 512;

   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     typedef hb_vector_size_t<elt_t, PAGE_BITS / 8> vector_t;

   168 

   169     static const unsigned int ELT_BITS = sizeof (elt_t) * 8;

   170     static const unsigned int ELT_MASK = ELT_BITS - 1;

   171     static const unsigned int BITS = sizeof (vector_t) * 8;

   172     static const unsigned int MASK = BITS - 1;

   173     static_assert (PAGE_BITS == BITS, "");

   174 

   175     elt_t &elt (hb_codepoint_t g) { return v[(g & MASK) / ELT_BITS]; }

   176     elt_t const &elt (hb_codepoint_t g) const { return v[(g & MASK) / ELT_BITS]; }

   177     elt_t mask (hb_codepoint_t g) const { return elt_t (1) << (g & ELT_MASK); }

   178 

   179     vector_t v;

   180   };

   181   static_assert (page_t::PAGE_BITS == sizeof (page_t) * 8, "");

   182 

   183   hb_object_header_t header;

   184   bool successful; /* Allocations successful */

   185   mutable unsigned int population;

   186   hb_vector_t<page_map_t, 1> page_map;

   187   hb_vector_t<page_t, 1> pages;

   188 

   189   inline void init_shallow (void)

   190   {

   191     successful = true;

   192     population = 0;

   193     page_map.init ();

   194     pages.init ();

   195   }

   196   inline void init (void)

   197   {

   198     hb_object_init (this);

   199     init_shallow ();

   200   }

   201   inline void fini_shallow (void)

   202   {

   203     page_map.fini ();

   204     pages.fini ();

   205   }

   206   inline void fini (void)

   207   {

   208     hb_object_fini (this);

   209     fini_shallow ();

   210   }

   211 

   212   inline bool resize (unsigned int count)

   213   {

   214     if (unlikely (!successful)) return false;

   215     if (!pages.resize (count) || !page_map.resize (count))

   216     {

   217       pages.resize (page_map.len);

   218       successful = false;

   219       return false;

   220     }

   221     return true;

   222   }

   223 

   224   inline void clear (void) {

   225     if (unlikely (hb_object_is_inert (this)))

   226       return;

   227     successful = true;

   228     population = 0;

   229     page_map.resize (0);

   230     pages.resize (0);

   231   }

   232   inline bool is_empty (void) const {

   233     unsigned int count = pages.len;

   234     for (unsigned int i = 0; i < count; i++)

   235       if (!pages[i].is_empty ())

   236         return false;

   237     return true;

   238   }

   239 

   240   inline void dirty (void) { population = (unsigned int) -1; }

   241 

   242   inline void add (hb_codepoint_t g)

   243   {

   244     if (unlikely (!successful)) return;

   245     if (unlikely (g == INVALID)) return;

   246     dirty ();

   247     page_t *page = page_for_insert (g); if (unlikely (!page)) return;

   248     page->add (g);

   249   }

   250   inline bool add_range (hb_codepoint_t a, hb_codepoint_t b)

   251   {

   252     if (unlikely (!successful)) return true; /* https://github.com/harfbuzz/harfbuzz/issues/657 */

   253     if (unlikely (a > b || a == INVALID || b == INVALID)) return false;

   254     dirty ();

   255     unsigned int ma = get_major (a);

   256     unsigned int mb = get_major (b);

   257     if (ma == mb)

   258     {

   259       page_t *page = page_for_insert (a); if (unlikely (!page)) return false;

   260       page->add_range (a, b);

   261     }

   262     else

   263     {

   264       page_t *page = page_for_insert (a); if (unlikely (!page)) return false;

   265       page->add_range (a, major_start (ma + 1) - 1);

   266 

   267       for (unsigned int m = ma + 1; m < mb; m++)

   268       {

   269         page = page_for_insert (major_start (m)); if (unlikely (!page)) return false;

   270         page->init1 ();

   271       }

   272 

   273       page = page_for_insert (b); if (unlikely (!page)) return false;

   274       page->add_range (major_start (mb), b);

   275     }

   276     return true;

   277   }

   278 

   279   template <typename T>

   280   inline void add_array (const T *array, unsigned int count, unsigned int stride=sizeof(T))

   281   {

   282     if (unlikely (!successful)) return;

   283     if (!count) return;

   284     dirty ();

   285     hb_codepoint_t g = *array;

   286     while (count)

   287     {

   288       unsigned int m = get_major (g);

   289       page_t *page = page_for_insert (g); if (unlikely (!page)) return;

   290       unsigned int start = major_start (m);

   291       unsigned int end = major_start (m + 1);

   292       do

   293       {

   294         page->add (g);

   295 

   296         array = (const T *) ((const char *) array + stride);

   297         count--;

   298       }

   299       while (count && (g = *array, start <= g && g < end));

   300     }

   301   }

   302 

   303   /* Might return false if array looks unsorted.

   304    * Used for faster rejection of corrupt data. */

   305   template <typename T>

   306   inline bool add_sorted_array (const T *array, unsigned int count, unsigned int stride=sizeof(T))

   307   {

   308     if (unlikely (!successful)) return true; /* https://github.com/harfbuzz/harfbuzz/issues/657 */

   309     if (!count) return true;

   310     dirty ();

   311     hb_codepoint_t g = *array;

   312     hb_codepoint_t last_g = g;

   313     while (count)

   314     {

   315       unsigned int m = get_major (g);

   316       page_t *page = page_for_insert (g); if (unlikely (!page)) return false;

   317       unsigned int end = major_start (m + 1);

   318       do

   319       {

   320         /* If we try harder we can change the following comparison to <=;

   321          * Not sure if it's worth it. */

   322         if (g < last_g) return false;

   323         last_g = g;

   324         page->add (g);

   325 

   326         array = (const T *) ((const char *) array + stride);

   327         count--;

   328       }

   329       while (count && (g = *array, g < end));

   330     }

   331     return true;

   332   }

   333 

   334   inline void del (hb_codepoint_t g)

   335   {

   336     /* TODO perform op even if !successful. */

   337     if (unlikely (!successful)) return;

   338     page_t *p = page_for (g);

   339     if (!p)

   340       return;

   341     dirty ();

   342     p->del (g);

   343   }

   344   inline void del_range (hb_codepoint_t a, hb_codepoint_t b)

   345   {

   346     /* TODO perform op even if !successful. */

   347     /* TODO Optimize, like add_range(). */

   348     if (unlikely (!successful)) return;

   349     for (unsigned int i = a; i < b + 1; i++)

   350       del (i);

   351   }

   352   inline bool has (hb_codepoint_t g) const

   353   {

   354     const page_t *p = page_for (g);

   355     if (!p)

   356       return false;

   357     return p->has (g);

   358   }

   359   inline bool intersects (hb_codepoint_t first,

   360                           hb_codepoint_t last) const

   361   {

   362     hb_codepoint_t c = first - 1;

   363     return next (&c) && c <= last;

   364   }

   365   inline void set (const hb_set_t *other)

   366   {

   367     if (unlikely (!successful)) return;

   368     unsigned int count = other->pages.len;

   369     if (!resize (count))

   370       return;

   371     population = other->population;

   372     memcpy (pages.arrayZ, other->pages.arrayZ, count * sizeof (pages.arrayZ[0]));

   373     memcpy (page_map.arrayZ, other->page_map.arrayZ, count * sizeof (page_map.arrayZ[0]));

   374   }

   375 

   376   inline bool is_equal (const hb_set_t *other) const

   377   {

   378     if (get_population () != other->get_population ())

   379       return false;

   380 

   381     unsigned int na = pages.len;

   382     unsigned int nb = other->pages.len;

   383 

   384     unsigned int a = 0, b = 0;

   385     for (; a < na && b < nb; )

   386     {

   387       if (page_at (a).is_empty ()) { a++; continue; }

   388       if (other->page_at (b).is_empty ()) { b++; continue; }

   389       if (page_map[a].major != other->page_map[b].major ||

   390           !page_at (a).is_equal (&other->page_at (b)))

   391         return false;

   392       a++;

   393       b++;

   394     }

   395     for (; a < na; a++)

   396       if (!page_at (a).is_empty ()) { return false; }

   397     for (; b < nb; b++)

   398       if (!other->page_at (b).is_empty ()) { return false; }

   399 

   400     return true;

   401   }

   402 

   403   inline bool is_subset (const hb_set_t *larger_set) const

   404   {

   405     if (get_population () > larger_set->get_population ())

   406       return false;

   407 

   408     hb_codepoint_t c = INVALID;

   409     while (next (&c))

   410       if (!larger_set->has (c))

   411         return false;

   412 

   413     return true;

   414   }

   415 

   416   template <class Op>

   417   inline void process (const hb_set_t *other)

   418   {

   419     if (unlikely (!successful)) return;

   420 

   421     dirty ();

   422 

   423     unsigned int na = pages.len;

   424     unsigned int nb = other->pages.len;

   425     unsigned int next_page = na;

   426 

   427     unsigned int count = 0, newCount = 0;

   428     unsigned int a = 0, b = 0;

   429     for (; a < na && b < nb; )

   430     {

   431       if (page_map[a].major == other->page_map[b].major)

   432       {

   433         count++;

   434         a++;

   435         b++;

   436       }

   437       else if (page_map[a].major < other->page_map[b].major)

   438       {

   439         if (Op::passthru_left)

   440           count++;

   441         a++;

   442       }

   443       else

   444       {

   445         if (Op::passthru_right)

   446           count++;

   447         b++;

   448       }

   449     }

   450     if (Op::passthru_left)

   451       count += na - a;

   452     if (Op::passthru_right)

   453       count += nb - b;

   454 

   455     if (count > pages.len)

   456       if (!resize (count))

   457         return;

   458     newCount = count;

   459 

   460     /* Process in-place backward. */

   461     a = na;

   462     b = nb;

   463     for (; a && b; )

   464     {

   465       if (page_map[a - 1].major == other->page_map[b - 1].major)

   466       {

   467         a--;

   468         b--;

   469         count--;

   470         page_map[count] = page_map[a];

   471         Op::process (page_at (count).v, page_at (a).v, other->page_at (b).v);

   472       }

   473       else if (page_map[a - 1].major > other->page_map[b - 1].major)

   474       {

   475         a--;

   476         if (Op::passthru_left)

   477         {

   478           count--;

   479           page_map[count] = page_map[a];

   480         }

   481       }

   482       else

   483       {

   484         b--;

   485         if (Op::passthru_right)

   486         {

   487           count--;

   488           page_map[count].major = other->page_map[b].major;

   489           page_map[count].index = next_page++;

   490           page_at (count).v = other->page_at (b).v;

   491         }

   492       }

   493     }

   494     if (Op::passthru_left)

   495       while (a)

   496       {

   497         a--;

   498         count--;

   499         page_map[count] = page_map [a];

   500       }

   501     if (Op::passthru_right)

   502       while (b)

   503       {

   504         b--;

   505         count--;

   506         page_map[count].major = other->page_map[b].major;

   507         page_map[count].index = next_page++;

   508         page_at (count).v = other->page_at (b).v;

   509       }

   510     assert (!count);

   511     if (pages.len > newCount)

   512       resize (newCount);

   513   }

   514 

   515   inline void union_ (const hb_set_t *other)

   516   {

   517     process<HbOpOr> (other);

   518   }

   519   inline void intersect (const hb_set_t *other)

   520   {

   521     process<HbOpAnd> (other);

   522   }

   523   inline void subtract (const hb_set_t *other)

   524   {

   525     process<HbOpMinus> (other);

   526   }

   527   inline void symmetric_difference (const hb_set_t *other)

   528   {

   529     process<HbOpXor> (other);

   530   }

   531   inline bool next (hb_codepoint_t *codepoint) const

   532   {

   533     if (unlikely (*codepoint == INVALID)) {

   534       *codepoint = get_min ();

   535       return *codepoint != INVALID;

   536     }

   537 

   538     page_map_t map = {get_major (*codepoint), 0};

   539     unsigned int i;

   540     page_map.bfind (map, &i);

   541     if (i < page_map.len && page_map[i].major == map.major)

   542     {

   543       if (pages[page_map[i].index].next (codepoint))

   544       {

   545         *codepoint += page_map[i].major * page_t::PAGE_BITS;

   546         return true;

   547       }

   548       i++;

   549     }

   550     for (; i < page_map.len; i++)

   551     {

   552       hb_codepoint_t m = pages[page_map[i].index].get_min ();

   553       if (m != INVALID)

   554       {

   555         *codepoint = page_map[i].major * page_t::PAGE_BITS + m;

   556         return true;

   557       }

   558     }

   559     *codepoint = INVALID;

   560     return false;

   561   }

   562   inline bool previous (hb_codepoint_t *codepoint) const

   563   {

   564     if (unlikely (*codepoint == INVALID)) {

   565       *codepoint = get_max ();

   566       return *codepoint != INVALID;

   567     }

   568 

   569     page_map_t map = {get_major (*codepoint), 0};

   570     unsigned int i;

   571     page_map.bfind (map, &i);

   572     if (i < page_map.len && page_map[i].major == map.major)

   573     {

   574       if (pages[page_map[i].index].previous (codepoint))

   575       {

   576         *codepoint += page_map[i].major * page_t::PAGE_BITS;

   577         return true;

   578       }

   579     }

   580     i--;

   581     for (; (int) i >= 0; i--)

   582     {

   583       hb_codepoint_t m = pages[page_map[i].index].get_max ();

   584       if (m != INVALID)

   585       {

   586         *codepoint = page_map[i].major * page_t::PAGE_BITS + m;

   587         return true;

   588       }

   589     }

   590     *codepoint = INVALID;

   591     return false;

   592   }

   593   inline bool next_range (hb_codepoint_t *first, hb_codepoint_t *last) const

   594   {

   595     hb_codepoint_t i;

   596 

   597     i = *last;

   598     if (!next (&i))

   599     {

   600       *last = *first = INVALID;

   601       return false;

   602     }

   603 

   604     /* TODO Speed up. */

   605     *last = *first = i;

   606     while (next (&i) && i == *last + 1)

   607       (*last)++;

   608 

   609     return true;

   610   }

   611   inline bool previous_range (hb_codepoint_t *first, hb_codepoint_t *last) const

   612   {

   613     hb_codepoint_t i;

   614 

   615     i = *first;

   616     if (!previous (&i))

   617     {

   618       *last = *first = INVALID;

   619       return false;

   620     }

   621 

   622     /* TODO Speed up. */

   623     *last = *first = i;

   624     while (previous (&i) && i == *first - 1)

   625       (*first)--;

   626 

   627     return true;

   628   }

   629 

   630   inline unsigned int get_population (void) const

   631   {

   632     if (population != (unsigned int) -1)

   633       return population;

   634 

   635     unsigned int pop = 0;

   636     unsigned int count = pages.len;

   637     for (unsigned int i = 0; i < count; i++)

   638       pop += pages[i].get_population ();

   639 

   640     population = pop;

   641     return pop;

   642   }

   643   inline hb_codepoint_t get_min (void) const

   644   {

   645     unsigned int count = pages.len;

   646     for (unsigned int i = 0; i < count; i++)

   647       if (!page_at (i).is_empty ())

   648         return page_map[i].major * page_t::PAGE_BITS + page_at (i).get_min ();

   649     return INVALID;

   650   }

   651   inline hb_codepoint_t get_max (void) const

   652   {

   653     unsigned int count = pages.len;

   654     for (int i = count - 1; i >= 0; i++)

   655       if (!page_at (i).is_empty ())

   656         return page_map[i].major * page_t::PAGE_BITS + page_at (i).get_max ();

   657     return INVALID;

   658   }

   659 

   660   static  const hb_codepoint_t INVALID = HB_SET_VALUE_INVALID;

   661 

   662   inline page_t *page_for_insert (hb_codepoint_t g)

   663   {

   664     page_map_t map = {get_major (g), pages.len};

   665     unsigned int i;

   666     if (!page_map.bfind (map, &i))

   667     {

   668       if (!resize (pages.len + 1))

   669         return nullptr;

   670 

   671       pages[map.index].init0 ();

   672       memmove (&page_map[i + 1], &page_map[i], (page_map.len - 1 - i) * sizeof (page_map[0]));

   673       page_map[i] = map;

   674     }

   675     return &pages[page_map[i].index];

   676   }

   677   inline page_t *page_for (hb_codepoint_t g)

   678   {

   679     page_map_t key = {get_major (g)};

   680     const page_map_t *found = page_map.bsearch (key);

   681     if (found)

   682       return &pages[found->index];

   683     return nullptr;

   684   }

   685   inline const page_t *page_for (hb_codepoint_t g) const

   686   {

   687     page_map_t key = {get_major (g)};

   688     const page_map_t *found = page_map.bsearch (key);

   689     if (found)

   690       return &pages[found->index];

   691     return nullptr;

   692   }

   693   inline page_t &page_at (unsigned int i) { return pages[page_map[i].index]; }

   694   inline const page_t &page_at (unsigned int i) const { return pages[page_map[i].index]; }

   695   inline unsigned int get_major (hb_codepoint_t g) const { return g / page_t::PAGE_BITS; }

   696   inline hb_codepoint_t major_start (unsigned int major) const { return major * page_t::PAGE_BITS; }

   697 };

   698 

   699 

   700 #endif /* HB_SET_PRIVATE_HH */