/*

 * 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 void 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);

    }

  }

  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 void add_range (hb_codepoint_t a, hb_codepoint_t b) {

    head.add_range (a, b);

    tail.add_range (a, b);

  }

  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 */