tor-browser

hb-set-digest.hh (5454B)

---

/*
* Copyright © 2012  Google, Inc.
*
*  This is part of HarfBuzz, a text shaping library.
*
* Permission is hereby granted, without written agreement and without
* license or royalty fees, to use, copy, modify, and distribute this
* software and its documentation for any purpose, provided that the
* above copyright notice and the following two paragraphs appear in
* all copies of this software.
*
* IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR
* DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
* ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
* IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
* DAMAGE.
*
* THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,
* BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
* FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS
* ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO
* PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
*
* Google Author(s): Behdad Esfahbod
*/

#ifndef HB_SET_DIGEST_HH
#define HB_SET_DIGEST_HH

#include "hb.hh"
#include "hb-machinery.hh"

/*
* The set-digests implement "filters" that support "approximate
* member query".  Conceptually these are like Bloom Filter and
* Quotient Filter, however, much smaller, faster, and designed
* to fit the requirements of our uses for glyph coverage queries.
*
* Our filters are highly accurate if the lookup covers fairly local
* set of glyphs, but fully flooded and ineffective if coverage is
* all over the place.
*
* The way these are used is that the filter is first populated by
* a lookup's or subtable's Coverage table(s), and then when we
* want to apply the lookup or subtable to a glyph, before trying
* to apply, we ask the filter if the glyph may be covered. If it's
* not, we return early.  We can also match a digest against another
* digest.
*
* We use these filters at three levels:
*   - If the digest for all the glyphs in the buffer as a whole
*     does not match the digest for the lookup, skip the lookup.
*   - For each glyph, if it doesn't match the lookup digest,
*     skip it.
*   - For each glyph, if it doesn't match the subtable digest,
*     skip it.
*
* The filter we use is a combination of three bits-pattern
* filters. A bits-pattern filter checks a number of bits (5 or 6)
* of the input number (glyph-id in most cases) and checks whether
* its pattern is amongst the patterns of any of the accepted values.
* The accepted patterns are represented as a "long" integer. Each
* check is done using four bitwise operations only.
*/

static constexpr unsigned hb_set_digest_shifts[] = {4, 0, 6};

struct hb_set_digest_t
{
 // No science in these. Intuition and testing only.
 using mask_t = uint64_t;

 static constexpr unsigned n = ARRAY_LENGTH_CONST (hb_set_digest_shifts);
 static constexpr unsigned mask_bytes = sizeof (mask_t);
 static constexpr unsigned mask_bits = sizeof (mask_t) * 8;
 static constexpr hb_codepoint_t mb1 = mask_bits - 1;
 static constexpr mask_t one = 1;
 static constexpr mask_t all = (mask_t) -1;

 void init ()
 { for (unsigned i = 0; i < n; i++) masks[i] = 0; }

 void clear () { init (); }

 static hb_set_digest_t full ()
 {
   hb_set_digest_t d;
   for (unsigned i = 0; i < n; i++) d.masks[i] = all;
   return d;
 }

 void union_ (const hb_set_digest_t &o)
 { for (unsigned i = 0; i < n; i++) masks[i] |= o.masks[i]; }

 bool add_range (hb_codepoint_t a, hb_codepoint_t b)
 {
   bool ret;

   ret = false;
   for (unsigned i = 0; i < n; i++)
     if (masks[i] != all)
ret = true;
   if (!ret) return false;

   ret = false;
   for (unsigned i = 0; i < n; i++)
   {
     mask_t shift = hb_set_digest_shifts[i];
     if ((b >> shift) - (a >> shift) >= mb1)
masks[i] = all;
     else
     {
mask_t ma = one << ((a >> shift) & mb1);
mask_t mb = one << ((b >> shift) & mb1);
masks[i] |= mb + (mb - ma) - (mb < ma);
ret = true;
     }
   }
   return ret;
 }

 template <typename T>
 void add_array (const T *array, unsigned int count, unsigned int stride=sizeof(T))
 {
   for (unsigned int i = 0; i < count; i++)
   {
     add (*array);
     array = &StructAtOffsetUnaligned<T> ((const void *) array, stride);
   }
 }
 template <typename T>
 void add_array (const hb_array_t<const T>& arr) { add_array (&arr, arr.len ()); }
 template <typename T>
 bool add_sorted_array (const T *array, unsigned int count, unsigned int stride=sizeof(T))
 {
   add_array (array, count, stride);
   return true;
 }
 template <typename T>
 bool add_sorted_array (const hb_sorted_array_t<const T>& arr) { return add_sorted_array (&arr, arr.len ()); }

 bool operator [] (hb_codepoint_t g) const
 { return may_have (g); }


 void add (hb_codepoint_t g)
 {
   for (unsigned i = 0; i < n; i++)
     masks[i] |= one << ((g >> hb_set_digest_shifts[i]) & mb1);
 }

 HB_ALWAYS_INLINE
 bool may_have (hb_codepoint_t g) const
 {
   for (unsigned i = 0; i < n; i++)
     if (!(masks[i] & (one << ((g >> hb_set_digest_shifts[i]) & mb1))))
return false;
   return true;
 }

 bool may_intersect (const hb_set_digest_t &o) const
 {
   for (unsigned i = 0; i < n; i++)
     if (!(masks[i] & o.masks[i]))
return false;
   return true;
 }

 private:

 mask_t masks[n] = {};
};


#endif /* HB_SET_DIGEST_HH */