/* * Copyright © 2017 Google, Inc. * Copyright © 2019 Facebook, 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 * Facebook Author(s): Behdad Esfahbod */ #ifndef HB_ALGS_HH #define HB_ALGS_HH #include "hb.hh" #include "hb-meta.hh" #include "hb-null.hh" #include "hb-number.hh" #include <algorithm> #include <initializer_list> #include <functional> #include <new> /* * Flags */ /* Enable bitwise ops on enums marked as flags_t */ /* To my surprise, looks like the function resolver is happy to silently cast * one enum to another... So this doesn't provide the type-checking that I * originally had in mind... :(. * * For MSVC warnings, see: https://github.com/harfbuzz/harfbuzz/pull/163 */ #ifdef _MSC_VER # pragma warning(disable:4200) # pragma warning(disable:4800) #endif #define HB_MARK_AS_FLAG_T(T) … /* Useful for set-operations on small enums. * For example, for testing "x ∈ {x1, x2, x3}" use: * (FLAG_UNSAFE(x) & (FLAG(x1) | FLAG(x2) | FLAG(x3))) */ #define FLAG(x) … #define FLAG_UNSAFE(x) … #define FLAG_RANGE(x,y) … #define FLAG64(x) … #define FLAG64_UNSAFE(x) … /* * Big-endian integers. */ /* Endian swap, used in Windows related backends */ static inline constexpr uint16_t hb_uint16_swap (uint16_t v) { … } static inline constexpr uint32_t hb_uint32_swap (uint32_t v) { … } #ifndef HB_FAST_INT_ACCESS #if defined(__OPTIMIZE__) && \ defined(__BYTE_ORDER) && \ (__BYTE_ORDER == __BIG_ENDIAN || \ (__BYTE_ORDER == __LITTLE_ENDIAN && \ hb_has_builtin(__builtin_bswap16) && \ hb_has_builtin(__builtin_bswap32))) #define HB_FAST_INT_ACCESS … #else #define HB_FAST_INT_ACCESS … #endif #endif template <typename Type, int Bytes = sizeof (Type)> struct BEInt; BEInt<Type, 1>; BEInt<Type, 2>; BEInt<Type, 3>; BEInt<Type, 4>; /* Floats. */ /* We want our rounding towards +infinity. */ static inline double _hb_roundf (double x) { … } static inline float _hb_roundf (float x) { … } #define roundf(x) … /* Encodes three unsigned integers in one 64-bit number. If the inputs have more than 21 bits, * values will be truncated / overlap, and might not decode exactly. */ #define HB_CODEPOINT_ENCODE3(x,y,z) … #define HB_CODEPOINT_DECODE3_1(v) … #define HB_CODEPOINT_DECODE3_2(v) … #define HB_CODEPOINT_DECODE3_3(v) … /* Custom encoding used by hb-ucd. */ #define HB_CODEPOINT_ENCODE3_11_7_14(x,y,z) … #define HB_CODEPOINT_DECODE3_11_7_14_1(v) … #define HB_CODEPOINT_DECODE3_11_7_14_2(v) … #define HB_CODEPOINT_DECODE3_11_7_14_3(v) … struct { … } HB_FUNCOBJ(…); struct { … } HB_FUNCOBJ(…); struct { … } HB_FUNCOBJ(…); struct { … } HB_FUNCOBJ(…); /* The MIT License Copyright (C) 2012 Zilong Tan ([email protected]) Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ // Compression function for Merkle-Damgard construction. // This function is generated using the framework provided. #define mix(h) … static inline uint64_t fasthash64(const void *buf, size_t len, uint64_t seed) { … } static inline uint32_t fasthash32(const void *buf, size_t len, uint32_t seed) { … } struct { … } HB_FUNCOBJ(…); struct { … } HB_FUNCOBJ(…); template <unsigned Pos, typename Appl, typename V> struct hb_partial_t { … }; template <unsigned Pos=1, typename Appl, typename V> auto hb_partial (Appl&& a, V&& v) HB_AUTO_RETURN (( hb_partial_t<Pos, Appl, V> (a, v) )) /* The following, HB_PARTIALIZE, macro uses a particular corner-case * of C++11 that is not particularly well-supported by all compilers. * What's happening is that it's using "this" in a trailing return-type * via decltype(). Broken compilers deduce the type of "this" pointer * in that context differently from what it resolves to in the body * of the function. * * One probable cause of this is that at the time of trailing return * type declaration, "this" points to an incomplete type, whereas in * the function body the type is complete. That doesn't justify the * error in any way, but is probably what's happening. * * In the case of MSVC, we get around this by using C++14 "decltype(auto)" * which deduces the type from the actual return statement. For gcc 4.8 * we use "+this" instead of "this" which produces an rvalue that seems * to be deduced as the same type with this particular compiler, and seem * to be fine as default code path as well. */ #ifdef _MSC_VER /* https://github.com/harfbuzz/harfbuzz/issues/1730 */ \ #define HB_PARTIALIZE(Pos) \ template <typename _T> \ decltype(auto) operator () (_T&& _v) const \ { return hb_partial<Pos> (this, std::forward<_T> (_v)); } \ static_assert (true, "") #else /* https://github.com/harfbuzz/harfbuzz/issues/1724 */ #define HB_PARTIALIZE(Pos) … #endif struct { … } HB_FUNCOBJ(…); struct { … } HB_FUNCOBJ(…); struct { … } HB_FUNCOBJ(…); struct { … } HB_FUNCOBJ(…); struct { … } HB_FUNCOBJ(…); template <typename T1, typename T2> struct hb_pair_t { … }; template <typename T1, typename T2> static inline hb_pair_t<T1, T2> hb_pair (T1&& a, T2&& b) { … } hb_codepoint_pair_t; struct { … } HB_FUNCOBJ(…); struct { … } HB_FUNCOBJ(…); /* Note. In min/max impl, we can use hb_type_identity<T> for second argument. * However, that would silently convert between different-signedness integers. * Instead we accept two different types, such that compiler can err if * comparing integers of different signedness. */ struct { … } HB_FUNCOBJ(…); struct { … } HB_FUNCOBJ(…); struct { … } HB_FUNCOBJ(…); /* * Bithacks. */ /* Return the number of 1 bits in v. */ template <typename T> static inline unsigned int hb_popcount (T v) { … } /* Returns the number of bits needed to store number */ template <typename T> static inline unsigned int hb_bit_storage (T v) { … } /* Returns the number of zero bits in the least significant side of v */ template <typename T> static inline unsigned int hb_ctz (T v) { … } /* * Tiny stuff. */ /* ASCII tag/character handling */ static inline bool ISALPHA (unsigned char c) { … } static inline bool ISALNUM (unsigned char c) { … } static inline bool ISSPACE (unsigned char c) { … } static inline unsigned char TOUPPER (unsigned char c) { … } static inline unsigned char TOLOWER (unsigned char c) { … } static inline bool ISHEX (unsigned char c) { … } static inline unsigned char TOHEX (uint8_t c) { … } static inline uint8_t FROMHEX (unsigned char c) { … } static inline unsigned int DIV_CEIL (const unsigned int a, unsigned int b) { … } #undef ARRAY_LENGTH template <typename Type, unsigned int n> static inline unsigned int ARRAY_LENGTH (const Type (&)[n]) { … } /* A const version, but does not detect erratically being called on pointers. */ #define ARRAY_LENGTH_CONST(__array) … static inline void * hb_memcpy (void *__restrict dst, const void *__restrict src, size_t len) { … } static inline int hb_memcmp (const void *a, const void *b, unsigned int len) { … } static inline void * hb_memset (void *s, int c, unsigned int n) { … } static inline unsigned int hb_ceil_to_4 (unsigned int v) { … } template <typename T> static inline bool hb_in_range (T u, T lo, T hi) { … } template <typename T> static inline bool hb_in_ranges (T u, T lo1, T hi1) { … } template <typename T, typename ...Ts> static inline bool hb_in_ranges (T u, T lo1, T hi1, Ts... ds) { … } /* * Overflow checking. */ static inline bool hb_unsigned_mul_overflows (unsigned int count, unsigned int size, unsigned *result = nullptr) { … } /* * Sort and search. */ template <typename K, typename V, typename ...Ts> static int _hb_cmp_method (const void *pkey, const void *pval, Ts... ds) { … } template <typename K, typename V> static int _hb_cmp_operator (const void *pkey, const void *pval) { … } template <typename V, typename K, typename ...Ts> static inline bool hb_bsearch_impl (unsigned *pos, /* Out */ const K& key, V* base, size_t nmemb, size_t stride, int (*compar)(const void *_key, const void *_item, Ts... _ds), Ts... ds) { … } template <typename V, typename K> static inline V* hb_bsearch (const K& key, V* base, size_t nmemb, size_t stride = sizeof (V), int (*compar)(const void *_key, const void *_item) = _hb_cmp_method<K, V>) { … } template <typename V, typename K, typename ...Ts> static inline V* hb_bsearch (const K& key, V* base, size_t nmemb, size_t stride, int (*compar)(const void *_key, const void *_item, Ts... _ds), Ts... ds) { … } /* From https://github.com/noporpoise/sort_r Feb 5, 2019 (c8c65c1e) Modified to support optional argument using templates */ /* Isaac Turner 29 April 2014 Public Domain */ /* hb_qsort function to be exported. Parameters: base is the array to be sorted nel is the number of elements in the array width is the size in bytes of each element of the array compar is the comparison function arg (optional) is a pointer to be passed to the comparison function void hb_qsort(void *base, size_t nel, size_t width, int (*compar)(const void *_a, const void *_b, [void *_arg]), [void *arg]); */ #define SORT_R_SWAP(a,b,tmp) … /* swap a and b */ /* a and b must not be equal! */ static inline void sort_r_swap(char *__restrict a, char *__restrict b, size_t w) { … } /* swap a, b iff a>b */ /* a and b must not be equal! */ /* __restrict is same as restrict but better support on old machines */ template <typename ...Ts> static inline int sort_r_cmpswap(char *__restrict a, char *__restrict b, size_t w, int (*compar)(const void *_a, const void *_b, Ts... _ds), Ts... ds) { … } /* Swap consecutive blocks of bytes of size na and nb starting at memory addr ptr, with the smallest swap so that the blocks are in the opposite order. Blocks may be internally re-ordered e.g. 12345ab -> ab34512 123abc -> abc123 12abcde -> deabc12 */ static inline void sort_r_swap_blocks(char *ptr, size_t na, size_t nb) { … } /* Implement recursive quicksort ourselves */ /* Note: quicksort is not stable, equivalent values may be swapped */ template <typename ...Ts> static inline void sort_r_simple(void *base, size_t nel, size_t w, int (*compar)(const void *_a, const void *_b, Ts... _ds), Ts... ds) { … } static inline void hb_qsort (void *base, size_t nel, size_t width, int (*compar)(const void *_a, const void *_b)) { … } static inline void hb_qsort (void *base, size_t nel, size_t width, int (*compar)(const void *_a, const void *_b, void *_arg), void *arg) { … } template <typename T, typename T2, typename T3 = int> static inline void hb_stable_sort (T *array, unsigned int len, int(*compar)(const T2 *, const T2 *), T3 *array2 = nullptr) { … } static inline hb_bool_t hb_codepoint_parse (const char *s, unsigned int len, int base, hb_codepoint_t *out) { … } /* Operators. */ struct { … } HB_FUNCOBJ(…); struct { … } HB_FUNCOBJ(…); struct { … } HB_FUNCOBJ(…); struct { … } HB_FUNCOBJ(…); struct { … } HB_FUNCOBJ(…); // aka sub struct { … } HB_FUNCOBJ(…); struct { … } HB_FUNCOBJ(…); struct { … } HB_FUNCOBJ(…); struct { … } HB_FUNCOBJ(…); struct { … } HB_FUNCOBJ(…); struct { … } HB_FUNCOBJ(…); struct { … } HB_FUNCOBJ(…); struct { … } HB_FUNCOBJ(…); struct { … } HB_FUNCOBJ(…); struct { … } HB_FUNCOBJ(…); struct { … } HB_FUNCOBJ(…); struct { … } HB_FUNCOBJ(…); struct { … } HB_FUNCOBJ(…); /* Adapted from kurbo implementation with extra parameters added, * and finding for a particular range instead of 0. * * For documentation and implementation see: * * [ITP method]: https://en.wikipedia.org/wiki/ITP_Method * [An Enhancement of the Bisection Method Average Performance Preserving Minmax Optimality]: https://dl.acm.org/doi/10.1145/3423597 * https://docs.rs/kurbo/0.8.1/kurbo/common/fn.solve_itp.html * https://github.com/linebender/kurbo/blob/fd839c25ea0c98576c7ce5789305822675a89938/src/common.rs#L162-L248 */ template <typename func_t> double solve_itp (func_t f, double a, double b, double epsilon, double min_y, double max_y, double &ya, double &yb, double &y) { … } #endif /* HB_ALGS_HH */
Codebase Browser
chromium