/* * 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 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 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 main 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 this case) and checks whether * its pattern is amongst the patterns of any of the accepted values. * The accepted patterns are represented as a "long" integer. The * check is done using four bitwise operations only. */ template <typename mask_t, unsigned int shift> struct hb_set_digest_bits_pattern_t { … }; template <typename head_t, typename tail_t> struct hb_set_digest_combiner_t { … }; /* * 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. */ hb_set_digest_t ; #endif /* HB_SET_DIGEST_HH */
Codebase Browser
chromium