src/hb-set-digest.hh

   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_HH
  28 #define HB_SET_DIGEST_HH
  29
  30 #include "hb.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   static constexpr unsigned mask_bytes = sizeof (mask_t);
  52   static constexpr unsigned mask_bits = sizeof (mask_t) * 8;
  53   static constexpr unsigned num_bits = 0
  54                                      + (mask_bytes >= 1 ? 3 : 0)
  55                                      + (mask_bytes >= 2 ? 1 : 0)
  56                                      + (mask_bytes >= 4 ? 1 : 0)
  57                                      + (mask_bytes >= 8 ? 1 : 0)
  58                                      + (mask_bytes >= 16? 1 : 0)
  59                                      + 0;
  60
  61   static_assert ((shift < sizeof (hb_codepoint_t) * 8), "");
  62   static_assert ((shift + num_bits <= sizeof (hb_codepoint_t) * 8), "");
  63
  64   void init () { mask = 0; }
  65
  66   void add (hb_codepoint_t g) { mask |= mask_for (g); }
  67
  68   bool add_range (hb_codepoint_t a, hb_codepoint_t b)
  69   {
  70     if ((b >> shift) - (a >> shift) >= mask_bits - 1)
  71       mask = (mask_t) -1;
  72     else {
  73       mask_t ma = mask_for (a);
  74       mask_t mb = mask_for (b);
  75       mask |= mb + (mb - ma) - (mb < ma);
  76     }
  77     return true;
  78   }
  79
  80   template <typename T>
  81   void add_array (const T *array, unsigned int count, unsigned int stride=sizeof(T))
  82   {
  83     for (unsigned int i = 0; i < count; i++)
  84     {
  85       add (*array);
  86       array = (const T *) (stride + (const char *) array);
  87     }
  88   }
  89   template <typename T>
  90   bool add_sorted_array (const T *array, unsigned int count, unsigned int stride=sizeof(T))
  91   {
  92     for (unsigned int i = 0; i < count; i++)
  93     {
  94       add (*array);
  95       array = (const T *) (stride + (const char *) array);
  96     }
  97     return true;
  98   }
  99
 100   bool may_have (hb_codepoint_t g) const
 101   { return !!(mask & mask_for (g)); }
 102
 103   private:
 104
 105   static mask_t mask_for (hb_codepoint_t g)
 106   { return ((mask_t) 1) << ((g >> shift) & (mask_bits - 1)); }
 107   mask_t mask;
 108 };
 109
 110 template <typename head_t, typename tail_t>
 111 struct hb_set_digest_combiner_t
 112 {
 113   void init ()
 114   {
 115     head.init ();
 116     tail.init ();
 117   }
 118
 119   void add (hb_codepoint_t g)
 120   {
 121     head.add (g);
 122     tail.add (g);
 123   }
 124
 125   bool add_range (hb_codepoint_t a, hb_codepoint_t b)
 126   {
 127     head.add_range (a, b);
 128     tail.add_range (a, b);
 129     return true;
 130   }
 131   template <typename T>
 132   void add_array (const T *array, unsigned int count, unsigned int stride=sizeof(T))
 133   {
 134     head.add_array (array, count, stride);
 135     tail.add_array (array, count, stride);
 136   }
 137   template <typename T>
 138   bool add_sorted_array (const T *array, unsigned int count, unsigned int stride=sizeof(T))
 139   {
 140     head.add_sorted_array (array, count, stride);
 141     tail.add_sorted_array (array, count, stride);
 142     return true;
 143   }
 144
 145   bool may_have (hb_codepoint_t g) const
 146   {
 147     return head.may_have (g) && tail.may_have (g);
 148   }
 149
 150   private:
 151   head_t head;
 152   tail_t tail;
 153 };
 154
 155
 156 /*
 157  * hb_set_digest_t
 158  *
 159  * This is a combination of digests that performs "best".
 160  * There is not much science to this: it's a result of intuition
 161  * and testing.
 162  */
 163 typedef hb_set_digest_combiner_t
 164 <
 165   hb_set_digest_lowest_bits_t<unsigned long, 4>,
 166   hb_set_digest_combiner_t
 167   <
 168     hb_set_digest_lowest_bits_t<unsigned long, 0>,
 169     hb_set_digest_lowest_bits_t<unsigned long, 9>
 170   >
 171 > hb_set_digest_t;
 172
 173
 174 #endif /* HB_SET_DIGEST_HH */