1 /*

     2  * Copyright © 2012  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_DIGEST_PRIVATE_HH

    28 #define HB_SET_DIGEST_PRIVATE_HH

    29 

    30 #include "hb-private.hh"

    31 

    32 /*

    33  * The set digests here implement various "filters" that support

    34  * "approximate member query".  Conceptually these are like Bloom

    35  * Filter and Quotient Filter, however, much smaller, faster, and

    36  * designed to fit the requirements of our uses for glyph coverage

    37  * queries.

    38  *

    39  * Our filters are highly accurate if the lookup covers fairly local

    40  * set of glyphs, but fully flooded and ineffective if coverage is

    41  * all over the place.

    42  *

    43  * The frozen-set can be used instead of a digest, to trade more

    44  * memory for 100% accuracy, but in practice, that doesn't look like

    45  * an attractive trade-off.

    46  */

    47 

    48 template <typename mask_t, unsigned int shift>

    49 struct hb_set_digest_lowest_bits_t

    50 {

    51   ASSERT_POD ();

    52 

    53   static const unsigned int mask_bytes = sizeof (mask_t);

    54   static const unsigned int mask_bits = sizeof (mask_t) * 8;

    55   static const unsigned int num_bits = 0

    56                                      + (mask_bytes >= 1 ? 3 : 0)

    57                                      + (mask_bytes >= 2 ? 1 : 0)

    58                                      + (mask_bytes >= 4 ? 1 : 0)

    59                                      + (mask_bytes >= 8 ? 1 : 0)

    60                                      + (mask_bytes >= 16? 1 : 0)

    61                                      + 0;

    62 

    63   static_assert ((shift < sizeof (hb_codepoint_t) * 8), "");

    64   static_assert ((shift + num_bits <= sizeof (hb_codepoint_t) * 8), "");

    65 

    66   inline void init (void) {

    67     mask = 0;

    68   }

    69 

    70   inline void add (hb_codepoint_t g) {

    71     mask |= mask_for (g);

    72   }

    73 

    74   inline void add_range (hb_codepoint_t a, hb_codepoint_t b) {

    75     if ((b >> shift) - (a >> shift) >= mask_bits - 1)

    76       mask = (mask_t) -1;

    77     else {

    78       mask_t ma = mask_for (a);

    79       mask_t mb = mask_for (b);

    80       mask |= mb + (mb - ma) - (mb < ma);

    81     }

    82   }

    83 

    84   inline bool may_have (hb_codepoint_t g) const {

    85     return !!(mask & mask_for (g));

    86   }

    87 

    88   private:

    89 

    90   static inline mask_t mask_for (hb_codepoint_t g) {

    91     return ((mask_t) 1) << ((g >> shift) & (mask_bits - 1));

    92   }

    93   mask_t mask;

    94 };

    95 

    96 template <typename head_t, typename tail_t>

    97 struct hb_set_digest_combiner_t

    98 {

    99   ASSERT_POD ();

   100 

   101   inline void init (void) {

   102     head.init ();

   103     tail.init ();

   104   }

   105 

   106   inline void add (hb_codepoint_t g) {

   107     head.add (g);

   108     tail.add (g);

   109   }

   110 

   111   inline void add_range (hb_codepoint_t a, hb_codepoint_t b) {

   112     head.add_range (a, b);

   113     tail.add_range (a, b);

   114   }

   115 

   116   inline bool may_have (hb_codepoint_t g) const {

   117     return head.may_have (g) && tail.may_have (g);

   118   }

   119 

   120   private:

   121   head_t head;

   122   tail_t tail;

   123 };

   124 

   125 

   126 /*

   127  * hb_set_digest_t

   128  *

   129  * This is a combination of digests that performs "best".

   130  * There is not much science to this: it's a result of intuition

   131  * and testing.

   132  */

   133 typedef hb_set_digest_combiner_t

   134 <

   135   hb_set_digest_lowest_bits_t<unsigned long, 4>,

   136   hb_set_digest_combiner_t

   137   <

   138     hb_set_digest_lowest_bits_t<unsigned long, 0>,

   139     hb_set_digest_lowest_bits_t<unsigned long, 9>

   140   >

   141 > hb_set_digest_t;

   142 

   143 

   144 #endif /* HB_SET_DIGEST_PRIVATE_HH */