/*

 * Copyright © 2007,2008,2009  Red Hat, Inc.

 * Copyright © 2011,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.

 *

 * Red Hat Author(s): Behdad Esfahbod

 * Google Author(s): Behdad Esfahbod

 */

#ifndef HB_PRIVATE_HH

#define HB_PRIVATE_HH

#define _GNU_SOURCE 1

#ifdef HAVE_CONFIG_H

#include "config.h"

#endif

#include "hb.h"

#define HB_H_IN

#ifdef HAVE_OT

#include "hb-ot.h"

#define HB_OT_H_IN

#endif

#include <math.h>

#include <stdlib.h>

#include <stddef.h>

#include <string.h>

#include <assert.h>

#include <errno.h>

#include <stdio.h>

#include <stdarg.h>

#include <intrin.h>

#endif

#define HB_PASTE1(a,b) a##b

#define HB_PASTE(a,b) HB_PASTE1(a,b)

/* Compile-time custom allocator support. */

#if defined(hb_malloc_impl) \

 && defined(hb_calloc_impl) \

 && defined(hb_realloc_impl) \

 && defined(hb_free_impl)

extern "C" void* hb_malloc_impl(size_t size);

extern "C" void* hb_calloc_impl(size_t nmemb, size_t size);

extern "C" void* hb_realloc_impl(void *ptr, size_t size);

extern "C" void  hb_free_impl(void *ptr);

#define malloc hb_malloc_impl

#define calloc hb_calloc_impl

#define realloc hb_realloc_impl

#define free hb_free_impl

#endif

/* Compiler attributes */

#if __cplusplus < 201103L

#ifndef nullptr

#define nullptr NULL

#endif

// Static assertions

#ifndef static_assert

#define static_assert(e, msg) \

        HB_UNUSED typedef int HB_PASTE(static_assertion_failed_at_line_, __LINE__) [(e) ? 1 : -1]

#endif // static_assert

#endif // __cplusplus < 201103L

#if (defined(__GNUC__) || defined(__clang__)) && defined(__OPTIMIZE__)

#define likely(expr) (__builtin_expect (!!(expr), 1))

#define unlikely(expr) (__builtin_expect (!!(expr), 0))

#else

#define likely(expr) (expr)

#define unlikely(expr) (expr)

#endif

#if !defined(__GNUC__) && !defined(__clang__)

#undef __attribute__

#define __attribute__(x)

#endif

#if __GNUC__ >= 3

#define HB_PURE_FUNC    __attribute__((pure))

#define HB_CONST_FUNC   __attribute__((const))

#define HB_PRINTF_FUNC(format_idx, arg_idx) __attribute__((__format__ (__printf__, format_idx, arg_idx)))

#else

#define HB_PURE_FUNC

#define HB_CONST_FUNC

#define HB_PRINTF_FUNC(format_idx, arg_idx)

#endif

#if __GNUC__ >= 4

#define HB_UNUSED       __attribute__((unused))

#elif defined(_MSC_VER) /* https://github.com/harfbuzz/harfbuzz/issues/635 */

#define HB_UNUSED __pragma(warning(suppress: 4100 4101))

#else

#define HB_UNUSED

#endif

#ifndef HB_INTERNAL

# if !defined(HB_NO_VISIBILITY) && !defined(__MINGW32__) && !defined(__CYGWIN__) && !defined(_MSC_VER) && !defined(__SUNPRO_CC)

#  define HB_INTERNAL __attribute__((__visibility__("hidden")))

# else

#  define HB_INTERNAL

#  define HB_NO_VISIBILITY 1

# endif

#endif

#if __GNUC__ >= 3

#define HB_FUNC __PRETTY_FUNCTION__

#elif defined(_MSC_VER)

#define HB_FUNC __FUNCSIG__

#else

#define HB_FUNC __func__

#endif

#if defined(__SUNPRO_CC) && (__SUNPRO_CC < 0x5140)

/* https://github.com/harfbuzz/harfbuzz/issues/630 */

#define __restrict

#endif

/*

 * Borrowed from https://bugzilla.mozilla.org/show_bug.cgi?id=1215411

 * HB_FALLTHROUGH is an annotation to suppress compiler warnings about switch

 * cases that fall through without a break or return statement. HB_FALLTHROUGH

 * is only needed on cases that have code:

 *

 * switch (foo) {

 *   case 1: // These cases have no code. No fallthrough annotations are needed.

 *   case 2:

 *   case 3:

 *     foo = 4; // This case has code, so a fallthrough annotation is needed:

 *     HB_FALLTHROUGH;

 *   default:

 *     return foo;

 * }

 */

#if defined(__clang__) && __cplusplus >= 201103L

   /* clang's fallthrough annotations are only available starting in C++11. */

#  define HB_FALLTHROUGH [[clang::fallthrough]]

#elif __GNUC__ >= 7

   /* GNU fallthrough attribute is available from GCC7 */

#  define HB_FALLTHROUGH __attribute__((fallthrough))

#elif defined(_MSC_VER)

   /*

    * MSVC's __fallthrough annotations are checked by /analyze (Code Analysis):

    * https://msdn.microsoft.com/en-us/library/ms235402%28VS.80%29.aspx

    */

#  include <sal.h>

#  define HB_FALLTHROUGH __fallthrough

#else

#  define HB_FALLTHROUGH /* FALLTHROUGH */

#endif

#if defined(_WIN32) || defined(__CYGWIN__)

   /* We need Windows Vista for both Uniscribe backend and for

    * MemoryBarrier.  We don't support compiling on Windows XP,

    * though we run on it fine. */

#  if defined(_WIN32_WINNT) && _WIN32_WINNT < 0x0600

#    undef _WIN32_WINNT

#  endif

#  ifndef _WIN32_WINNT

#    define _WIN32_WINNT 0x0600

#  endif

#  ifndef WIN32_LEAN_AND_MEAN

#    define WIN32_LEAN_AND_MEAN 1

#  endif

#  ifndef STRICT

#    define STRICT 1

#  endif

#  if defined(_WIN32_WCE)

     /* Some things not defined on Windows CE. */

#    define vsnprintf _vsnprintf

#    define getenv(Name) nullptr

#    if _WIN32_WCE < 0x800

#      define setlocale(Category, Locale) "C"

static int errno = 0; /* Use something better? */

#    endif

#  elif defined(WINAPI_FAMILY) && (WINAPI_FAMILY==WINAPI_FAMILY_PC_APP || WINAPI_FAMILY==WINAPI_FAMILY_PHONE_APP)

#    define getenv(Name) nullptr

#  endif

#  if defined(_MSC_VER) && _MSC_VER < 1900

#    define snprintf _snprintf

#  endif

#endif

#if HAVE_ATEXIT

/* atexit() is only safe to be called from shared libraries on certain

 * platforms.  Whitelist.

 * https://bugs.freedesktop.org/show_bug.cgi?id=82246 */

#  if defined(__linux) && defined(__GLIBC_PREREQ)

#    if __GLIBC_PREREQ(2,3)

/* From atexit() manpage, it's safe with glibc 2.2.3 on Linux. */

#      define HB_USE_ATEXIT 1

#    endif

#  elif defined(_MSC_VER) || defined(__MINGW32__)

/* For MSVC:

 * mingw32 headers say atexit is safe to use in shared libraries.

 */

#    define HB_USE_ATEXIT 1

 */

#    define HB_USE_ATEXIT 1

#  elif defined(__APPLE__)

/* For macOS and related platforms, the atexit man page indicates

 * that it will be invoked when the library is unloaded, not only

 * at application exit.

 */

#    define HB_USE_ATEXIT 1

#  endif

#endif

/* Basics */

#undef MIN

template <typename Type>

static inline Type MIN (const Type &a, const Type &b) { return a < b ? a : b; }

#undef MAX

template <typename Type>

static inline Type MAX (const Type &a, const Type &b) { return a > b ? a : b; }

static inline unsigned int DIV_CEIL (const unsigned int a, unsigned int b)

{ return (a + (b - 1)) / b; }

#undef  ARRAY_LENGTH

template <typename Type, unsigned int n>

static inline unsigned int ARRAY_LENGTH (const Type (&)[n]) { return n; }

/* A const version, but does not detect erratically being called on pointers. */

#define ARRAY_LENGTH_CONST(__array) ((signed int) (sizeof (__array) / sizeof (__array[0])))

#define HB_STMT_START do

#define HB_STMT_END   while (0)

template <unsigned int cond> class hb_assert_constant_t;

template <> class hb_assert_constant_t<1> {};

#define ASSERT_STATIC_EXPR_ZERO(_cond) (0 * (unsigned int) sizeof (hb_assert_constant_t<_cond>))

/* Lets assert int types.  Saves trouble down the road. */

static_assert ((sizeof (int8_t) == 1), "");

static_assert ((sizeof (uint8_t) == 1), "");

static_assert ((sizeof (int16_t) == 2), "");

static_assert ((sizeof (uint16_t) == 2), "");

static_assert ((sizeof (int32_t) == 4), "");

static_assert ((sizeof (uint32_t) == 4), "");

static_assert ((sizeof (int64_t) == 8), "");

static_assert ((sizeof (uint64_t) == 8), "");

static_assert ((sizeof (hb_codepoint_t) == 4), "");

static_assert ((sizeof (hb_position_t) == 4), "");

static_assert ((sizeof (hb_mask_t) == 4), "");

static_assert ((sizeof (hb_var_int_t) == 4), "");

/* We like our types POD */

#define _ASSERT_TYPE_POD1(_line, _type) union _type_##_type##_on_line_##_line##_is_not_POD { _type instance; }

#define _ASSERT_TYPE_POD0(_line, _type) _ASSERT_TYPE_POD1 (_line, _type)

#define ASSERT_TYPE_POD(_type)          _ASSERT_TYPE_POD0 (__LINE__, _type)

#ifdef __GNUC__

# define _ASSERT_INSTANCE_POD1(_line, _instance) \

        HB_STMT_START { \

                typedef __typeof__(_instance) _type_##_line; \

                _ASSERT_TYPE_POD1 (_line, _type_##_line); \

        } HB_STMT_END

#else

# define _ASSERT_INSTANCE_POD1(_line, _instance)        typedef int _assertion_on_line_##_line##_not_tested

#endif

# define _ASSERT_INSTANCE_POD0(_line, _instance)        _ASSERT_INSTANCE_POD1 (_line, _instance)

# define ASSERT_INSTANCE_POD(_instance)                 _ASSERT_INSTANCE_POD0 (__LINE__, _instance)

/* Check _assertion in a method environment */

#define _ASSERT_POD1(_line) \

        HB_UNUSED inline void _static_assertion_on_line_##_line (void) const \

        { _ASSERT_INSTANCE_POD1 (_line, *this); /* Make sure it's POD. */ }

# define _ASSERT_POD0(_line)    _ASSERT_POD1 (_line)

# define ASSERT_POD()           _ASSERT_POD0 (__LINE__)

/*

 * Void!

 */

typedef const struct _hb_void_t *hb_void_t;

#define HB_VOID ((const _hb_void_t *) nullptr)

/* Return the number of 1 bits in v. */

template <typename T>

static inline HB_CONST_FUNC unsigned int

_hb_popcount (T v)

{

#if (__GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)) && defined(__OPTIMIZE__)

  if (sizeof (T) <= sizeof (unsigned int))

    return __builtin_popcount (v);

  if (sizeof (T) <= sizeof (unsigned long))

    return __builtin_popcountl (v);

  if (sizeof (T) <= sizeof (unsigned long long))

    return __builtin_popcountll (v);

#endif

  if (sizeof (T) <= 4)

  {

    /* "HACKMEM 169" */

    uint32_t y;

    y = (v >> 1) &033333333333;

    y = v - y - ((y >>1) & 033333333333);

    return (((y + (y >> 3)) & 030707070707) % 077);

  }

  if (sizeof (T) == 8)

  {

    unsigned int shift = 32;

    return _hb_popcount<uint32_t> ((uint32_t) v) + _hb_popcount ((uint32_t) (v >> shift));

  }

  if (sizeof (T) == 16)

  {

    unsigned int shift = 64;

    return _hb_popcount<uint64_t> ((uint64_t) v) + _hb_popcount ((uint64_t) (v >> shift));

  }

  assert (0);

}

/* Returns the number of bits needed to store number */

template <typename T>

static inline HB_CONST_FUNC unsigned int

_hb_bit_storage (T v)

{

  if (unlikely (!v)) return 0;

#if defined(__GNUC__) && (__GNUC__ >= 4) && defined(__OPTIMIZE__)

  if (sizeof (T) <= sizeof (unsigned int))

    return sizeof (unsigned int) * 8 - __builtin_clz (v);

  if (sizeof (T) <= sizeof (unsigned long))

    return sizeof (unsigned long) * 8 - __builtin_clzl (v);

  if (sizeof (T) <= sizeof (unsigned long long))

    return sizeof (unsigned long long) * 8 - __builtin_clzll (v);

#endif

  if (sizeof (T) <= sizeof (unsigned int))

  {

    unsigned long where;

    _BitScanReverse (&where, v);

    return 1 + where;

  }

# if _WIN64

  if (sizeof (T) <= 8)

  {

    unsigned long where;

    _BitScanReverse64 (&where, v);

    return 1 + where;

  }

# endif

#endif

  if (sizeof (T) <= 4)

  {

    /* "bithacks" */

    const unsigned int b[] = {0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000};

    const unsigned int S[] = {1, 2, 4, 8, 16};

    unsigned int r = 0;

    for (int i = 4; i >= 0; i--)

      if (v & b[i])

      {

        v >>= S[i];

        r |= S[i];

      }

    return r + 1;

  }

  if (sizeof (T) <= 8)

  {

    /* "bithacks" */

    const unsigned int S[] = {1, 2, 4, 8, 16, 32};

    unsigned int r = 0;

    for (int i = 5; i >= 0; i--)

      if (v & b[i])

      {

        v >>= S[i];

        r |= S[i];

      }

    return r + 1;

  }

  if (sizeof (T) == 16)

  {

    unsigned int shift = 64;

                          _hb_bit_storage<uint64_t> ((uint64_t) v);

  }

  assert (0);

}

/* Returns the number of zero bits in the least significant side of v */

template <typename T>

static inline HB_CONST_FUNC unsigned int

_hb_ctz (T v)

{

  if (unlikely (!v)) return 0;

#if defined(__GNUC__) && (__GNUC__ >= 4) && defined(__OPTIMIZE__)

  if (sizeof (T) <= sizeof (unsigned int))

    return __builtin_ctz (v);

  if (sizeof (T) <= sizeof (unsigned long))

    return __builtin_ctzl (v);

  if (sizeof (T) <= sizeof (unsigned long long))

    return __builtin_ctzll (v);

#endif

  if (sizeof (T) <= sizeof (unsigned int))

  {

    unsigned long where;

    _BitScanForward (&where, v);

    return where;

  }

# if _WIN64

  if (sizeof (T) <= 8)

  {

    unsigned long where;

    _BitScanForward64 (&where, v);

    return where;

  }

# endif

#endif

  if (sizeof (T) <= 4)

  {

    /* "bithacks" */

    unsigned int c = 32;

    v &= - (int32_t) v;

    if (v) c--;

    if (v & 0x0000FFFF) c -= 16;

    if (v & 0x00FF00FF) c -= 8;

    if (v & 0x0F0F0F0F) c -= 4;

    if (v & 0x33333333) c -= 2;

    if (v & 0x55555555) c -= 1;

    return c;

  }

  if (sizeof (T) <= 8)

  {

    /* "bithacks" */

    unsigned int c = 64;

    v &= - (int64_t) (v);

    if (v) c--;