1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/harfbuzz/src/hb-set-private.hh Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,340 @@
1.4 +/*
1.5 + * Copyright © 2012 Google, Inc.
1.6 + *
1.7 + * This is part of HarfBuzz, a text shaping library.
1.8 + *
1.9 + * Permission is hereby granted, without written agreement and without
1.10 + * license or royalty fees, to use, copy, modify, and distribute this
1.11 + * software and its documentation for any purpose, provided that the
1.12 + * above copyright notice and the following two paragraphs appear in
1.13 + * all copies of this software.
1.14 + *
1.15 + * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR
1.16 + * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
1.17 + * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
1.18 + * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
1.19 + * DAMAGE.
1.20 + *
1.21 + * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,
1.22 + * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
1.23 + * FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
1.24 + * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO
1.25 + * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
1.26 + *
1.27 + * Google Author(s): Behdad Esfahbod
1.28 + */
1.29 +
1.30 +#ifndef HB_SET_PRIVATE_HH
1.31 +#define HB_SET_PRIVATE_HH
1.32 +
1.33 +#include "hb-private.hh"
1.34 +#include "hb-object-private.hh"
1.35 +
1.36 +
1.37 +/*
1.38 + * The set digests here implement various "filters" that support
1.39 + * "approximate member query". Conceptually these are like Bloom
1.40 + * Filter and Quotient Filter, however, much smaller, faster, and
1.41 + * designed to fit the requirements of our uses for glyph coverage
1.42 + * queries. As a result, our filters have much higher.
1.43 + */
1.44 +
1.45 +template <typename mask_t, unsigned int shift>
1.46 +struct hb_set_digest_lowest_bits_t
1.47 +{
1.48 + ASSERT_POD ();
1.49 +
1.50 + static const unsigned int mask_bytes = sizeof (mask_t);
1.51 + static const unsigned int mask_bits = sizeof (mask_t) * 8;
1.52 + static const unsigned int num_bits = 0
1.53 + + (mask_bytes >= 1 ? 3 : 0)
1.54 + + (mask_bytes >= 2 ? 1 : 0)
1.55 + + (mask_bytes >= 4 ? 1 : 0)
1.56 + + (mask_bytes >= 8 ? 1 : 0)
1.57 + + (mask_bytes >= 16? 1 : 0)
1.58 + + 0;
1.59 +
1.60 + ASSERT_STATIC (shift < sizeof (hb_codepoint_t) * 8);
1.61 + ASSERT_STATIC (shift + num_bits <= sizeof (hb_codepoint_t) * 8);
1.62 +
1.63 + inline void init (void) {
1.64 + mask = 0;
1.65 + }
1.66 +
1.67 + inline void add (hb_codepoint_t g) {
1.68 + mask |= mask_for (g);
1.69 + }
1.70 +
1.71 + inline void add_range (hb_codepoint_t a, hb_codepoint_t b) {
1.72 + if ((b >> shift) - (a >> shift) >= mask_bits - 1)
1.73 + mask = (mask_t) -1;
1.74 + else {
1.75 + mask_t ma = mask_for (a);
1.76 + mask_t mb = mask_for (b);
1.77 + mask |= mb + (mb - ma) - (mb < ma);
1.78 + }
1.79 + }
1.80 +
1.81 + inline bool may_have (hb_codepoint_t g) const {
1.82 + return !!(mask & mask_for (g));
1.83 + }
1.84 +
1.85 + private:
1.86 +
1.87 + static inline mask_t mask_for (hb_codepoint_t g) {
1.88 + return ((mask_t) 1) << ((g >> shift) & (mask_bits - 1));
1.89 + }
1.90 + mask_t mask;
1.91 +};
1.92 +
1.93 +template <typename head_t, typename tail_t>
1.94 +struct hb_set_digest_combiner_t
1.95 +{
1.96 + ASSERT_POD ();
1.97 +
1.98 + inline void init (void) {
1.99 + head.init ();
1.100 + tail.init ();
1.101 + }
1.102 +
1.103 + inline void add (hb_codepoint_t g) {
1.104 + head.add (g);
1.105 + tail.add (g);
1.106 + }
1.107 +
1.108 + inline void add_range (hb_codepoint_t a, hb_codepoint_t b) {
1.109 + head.add_range (a, b);
1.110 + tail.add_range (a, b);
1.111 + }
1.112 +
1.113 + inline bool may_have (hb_codepoint_t g) const {
1.114 + return head.may_have (g) && tail.may_have (g);
1.115 + }
1.116 +
1.117 + private:
1.118 + head_t head;
1.119 + tail_t tail;
1.120 +};
1.121 +
1.122 +
1.123 +/*
1.124 + * hb_set_digest_t
1.125 + *
1.126 + * This is a combination of digests that performs "best".
1.127 + * There is not much science to this: it's a result of intuition
1.128 + * and testing.
1.129 + */
1.130 +typedef hb_set_digest_combiner_t
1.131 +<
1.132 + hb_set_digest_lowest_bits_t<unsigned long, 4>,
1.133 + hb_set_digest_combiner_t
1.134 + <
1.135 + hb_set_digest_lowest_bits_t<unsigned long, 0>,
1.136 + hb_set_digest_lowest_bits_t<unsigned long, 9>
1.137 + >
1.138 +> hb_set_digest_t;
1.139 +
1.140 +
1.141 +
1.142 +/*
1.143 + * hb_set_t
1.144 + */
1.145 +
1.146 +
1.147 +/* TODO Make this faster and memmory efficient. */
1.148 +
1.149 +struct hb_set_t
1.150 +{
1.151 + hb_object_header_t header;
1.152 + ASSERT_POD ();
1.153 + bool in_error;
1.154 +
1.155 + inline void init (void) {
1.156 + header.init ();
1.157 + clear ();
1.158 + }
1.159 + inline void fini (void) {
1.160 + }
1.161 + inline void clear (void) {
1.162 + if (unlikely (hb_object_is_inert (this)))
1.163 + return;
1.164 + in_error = false;
1.165 + memset (elts, 0, sizeof elts);
1.166 + }
1.167 + inline bool is_empty (void) const {
1.168 + for (unsigned int i = 0; i < ARRAY_LENGTH (elts); i++)
1.169 + if (elts[i])
1.170 + return false;
1.171 + return true;
1.172 + }
1.173 + inline void add (hb_codepoint_t g)
1.174 + {
1.175 + if (unlikely (in_error)) return;
1.176 + if (unlikely (g == INVALID)) return;
1.177 + if (unlikely (g > MAX_G)) return;
1.178 + elt (g) |= mask (g);
1.179 + }
1.180 + inline void add_range (hb_codepoint_t a, hb_codepoint_t b)
1.181 + {
1.182 + if (unlikely (in_error)) return;
1.183 + /* TODO Speedup */
1.184 + for (unsigned int i = a; i < b + 1; i++)
1.185 + add (i);
1.186 + }
1.187 + inline void del (hb_codepoint_t g)
1.188 + {
1.189 + if (unlikely (in_error)) return;
1.190 + if (unlikely (g > MAX_G)) return;
1.191 + elt (g) &= ~mask (g);
1.192 + }
1.193 + inline void del_range (hb_codepoint_t a, hb_codepoint_t b)
1.194 + {
1.195 + if (unlikely (in_error)) return;
1.196 + /* TODO Speedup */
1.197 + for (unsigned int i = a; i < b + 1; i++)
1.198 + del (i);
1.199 + }
1.200 + inline bool has (hb_codepoint_t g) const
1.201 + {
1.202 + if (unlikely (g > MAX_G)) return false;
1.203 + return !!(elt (g) & mask (g));
1.204 + }
1.205 + inline bool intersects (hb_codepoint_t first,
1.206 + hb_codepoint_t last) const
1.207 + {
1.208 + if (unlikely (first > MAX_G)) return false;
1.209 + if (unlikely (last > MAX_G)) last = MAX_G;
1.210 + unsigned int end = last + 1;
1.211 + for (hb_codepoint_t i = first; i < end; i++)
1.212 + if (has (i))
1.213 + return true;
1.214 + return false;
1.215 + }
1.216 + inline bool is_equal (const hb_set_t *other) const
1.217 + {
1.218 + for (unsigned int i = 0; i < ELTS; i++)
1.219 + if (elts[i] != other->elts[i])
1.220 + return false;
1.221 + return true;
1.222 + }
1.223 + inline void set (const hb_set_t *other)
1.224 + {
1.225 + if (unlikely (in_error)) return;
1.226 + for (unsigned int i = 0; i < ELTS; i++)
1.227 + elts[i] = other->elts[i];
1.228 + }
1.229 + inline void union_ (const hb_set_t *other)
1.230 + {
1.231 + if (unlikely (in_error)) return;
1.232 + for (unsigned int i = 0; i < ELTS; i++)
1.233 + elts[i] |= other->elts[i];
1.234 + }
1.235 + inline void intersect (const hb_set_t *other)
1.236 + {
1.237 + if (unlikely (in_error)) return;
1.238 + for (unsigned int i = 0; i < ELTS; i++)
1.239 + elts[i] &= other->elts[i];
1.240 + }
1.241 + inline void subtract (const hb_set_t *other)
1.242 + {
1.243 + if (unlikely (in_error)) return;
1.244 + for (unsigned int i = 0; i < ELTS; i++)
1.245 + elts[i] &= ~other->elts[i];
1.246 + }
1.247 + inline void symmetric_difference (const hb_set_t *other)
1.248 + {
1.249 + if (unlikely (in_error)) return;
1.250 + for (unsigned int i = 0; i < ELTS; i++)
1.251 + elts[i] ^= other->elts[i];
1.252 + }
1.253 + inline void invert (void)
1.254 + {
1.255 + if (unlikely (in_error)) return;
1.256 + for (unsigned int i = 0; i < ELTS; i++)
1.257 + elts[i] = ~elts[i];
1.258 + }
1.259 + inline bool next (hb_codepoint_t *codepoint) const
1.260 + {
1.261 + if (unlikely (*codepoint == INVALID)) {
1.262 + hb_codepoint_t i = get_min ();
1.263 + if (i != INVALID) {
1.264 + *codepoint = i;
1.265 + return true;
1.266 + } else {
1.267 + *codepoint = INVALID;
1.268 + return false;
1.269 + }
1.270 + }
1.271 + for (hb_codepoint_t i = *codepoint + 1; i < MAX_G + 1; i++)
1.272 + if (has (i)) {
1.273 + *codepoint = i;
1.274 + return true;
1.275 + }
1.276 + *codepoint = INVALID;
1.277 + return false;
1.278 + }
1.279 + inline bool next_range (hb_codepoint_t *first, hb_codepoint_t *last) const
1.280 + {
1.281 + hb_codepoint_t i;
1.282 +
1.283 + i = *last;
1.284 + if (!next (&i))
1.285 + {
1.286 + *last = *first = INVALID;
1.287 + return false;
1.288 + }
1.289 +
1.290 + *last = *first = i;
1.291 + while (next (&i) && i == *last + 1)
1.292 + (*last)++;
1.293 +
1.294 + return true;
1.295 + }
1.296 +
1.297 + inline unsigned int get_population (void) const
1.298 + {
1.299 + unsigned int count = 0;
1.300 + for (unsigned int i = 0; i < ELTS; i++)
1.301 + count += _hb_popcount32 (elts[i]);
1.302 + return count;
1.303 + }
1.304 + inline hb_codepoint_t get_min (void) const
1.305 + {
1.306 + for (unsigned int i = 0; i < ELTS; i++)
1.307 + if (elts[i])
1.308 + for (unsigned int j = 0; j < BITS; j++)
1.309 + if (elts[i] & (1 << j))
1.310 + return i * BITS + j;
1.311 + return INVALID;
1.312 + }
1.313 + inline hb_codepoint_t get_max (void) const
1.314 + {
1.315 + for (unsigned int i = ELTS; i; i--)
1.316 + if (elts[i - 1])
1.317 + for (unsigned int j = BITS; j; j--)
1.318 + if (elts[i - 1] & (1 << (j - 1)))
1.319 + return (i - 1) * BITS + (j - 1);
1.320 + return INVALID;
1.321 + }
1.322 +
1.323 + typedef uint32_t elt_t;
1.324 + static const unsigned int MAX_G = 65536 - 1; /* XXX Fix this... */
1.325 + static const unsigned int SHIFT = 5;
1.326 + static const unsigned int BITS = (1 << SHIFT);
1.327 + static const unsigned int MASK = BITS - 1;
1.328 + static const unsigned int ELTS = (MAX_G + 1 + (BITS - 1)) / BITS;
1.329 + static const hb_codepoint_t INVALID = HB_SET_VALUE_INVALID;
1.330 +
1.331 + elt_t &elt (hb_codepoint_t g) { return elts[g >> SHIFT]; }
1.332 + elt_t elt (hb_codepoint_t g) const { return elts[g >> SHIFT]; }
1.333 + elt_t mask (hb_codepoint_t g) const { return elt_t (1) << (g & MASK); }
1.334 +
1.335 + elt_t elts[ELTS]; /* XXX 8kb */
1.336 +
1.337 + ASSERT_STATIC (sizeof (elt_t) * 8 == BITS);
1.338 + ASSERT_STATIC (sizeof (elt_t) * 8 * ELTS > MAX_G);
1.339 +};
1.340 +
1.341 +
1.342 +
1.343 +#endif /* HB_SET_PRIVATE_HH */
