diff options
Diffstat (limited to 'src/hb-set-digest-private.hh')
| -rw-r--r-- | src/hb-set-digest-private.hh | 179 |
1 files changed, 0 insertions, 179 deletions
diff --git a/src/hb-set-digest-private.hh b/src/hb-set-digest-private.hh deleted file mode 100644 index e099a82..0000000 --- a/src/hb-set-digest-private.hh +++ /dev/null @@ -1,179 +0,0 @@ -/* - * 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_PRIVATE_HH -#define HB_SET_DIGEST_PRIVATE_HH - -#include "hb-private.hh" - -/* - * The set digests here implement various "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 frozen-set can be used instead of a digest, to trade more - * memory for 100% accuracy, but in practice, that doesn't look like - * an attractive trade-off. - */ - -template <typename mask_t, unsigned int shift> -struct hb_set_digest_lowest_bits_t -{ - ASSERT_POD (); - - static const unsigned int mask_bytes = sizeof (mask_t); - static const unsigned int mask_bits = sizeof (mask_t) * 8; - static const unsigned int num_bits = 0 - + (mask_bytes >= 1 ? 3 : 0) - + (mask_bytes >= 2 ? 1 : 0) - + (mask_bytes >= 4 ? 1 : 0) - + (mask_bytes >= 8 ? 1 : 0) - + (mask_bytes >= 16? 1 : 0) - + 0; - - static_assert ((shift < sizeof (hb_codepoint_t) * 8), ""); - static_assert ((shift + num_bits <= sizeof (hb_codepoint_t) * 8), ""); - - inline void init (void) { - mask = 0; - } - - inline void add (hb_codepoint_t g) { - mask |= mask_for (g); - } - - inline bool add_range (hb_codepoint_t a, hb_codepoint_t b) { - if ((b >> shift) - (a >> shift) >= mask_bits - 1) - mask = (mask_t) -1; - else { - mask_t ma = mask_for (a); - mask_t mb = mask_for (b); - mask |= mb + (mb - ma) - (mb < ma); - } - return true; - } - - template <typename T> - inline 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 = (const T *) (stride + (const char *) array); - } - } - template <typename T> - inline bool add_sorted_array (const T *array, unsigned int count, unsigned int stride=sizeof(T)) - { - for (unsigned int i = 0; i < count; i++) - { - add (*array); - array = (const T *) (stride + (const char *) array); - } - return true; - } - - inline bool may_have (hb_codepoint_t g) const { - return !!(mask & mask_for (g)); - } - - private: - - static inline mask_t mask_for (hb_codepoint_t g) { - return ((mask_t) 1) << ((g >> shift) & (mask_bits - 1)); - } - mask_t mask; -}; - -template <typename head_t, typename tail_t> -struct hb_set_digest_combiner_t -{ - ASSERT_POD (); - - inline void init (void) { - head.init (); - tail.init (); - } - - inline void add (hb_codepoint_t g) { - head.add (g); - tail.add (g); - } - - inline bool add_range (hb_codepoint_t a, hb_codepoint_t b) { - head.add_range (a, b); - tail.add_range (a, b); - return true; - } - template <typename T> - inline void add_array (const T *array, unsigned int count, unsigned int stride=sizeof(T)) - { - head.add_array (array, count, stride); - tail.add_array (array, count, stride); - } - template <typename T> - inline bool add_sorted_array (const T *array, unsigned int count, unsigned int stride=sizeof(T)) - { - head.add_sorted_array (array, count, stride); - tail.add_sorted_array (array, count, stride); - return true; - } - - inline bool may_have (hb_codepoint_t g) const { - return head.may_have (g) && tail.may_have (g); - } - - private: - head_t head; - tail_t tail; -}; - - -/* - * hb_set_digest_t - * - * This is a combination of digests that performs "best". - * There is not much science to this: it's a result of intuition - * and testing. - */ -typedef hb_set_digest_combiner_t -< - hb_set_digest_lowest_bits_t<unsigned long, 4>, - hb_set_digest_combiner_t - < - hb_set_digest_lowest_bits_t<unsigned long, 0>, - hb_set_digest_lowest_bits_t<unsigned long, 9> - > -> hb_set_digest_t; - - -#endif /* HB_SET_DIGEST_PRIVATE_HH */ |