/*

 * 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

#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 <stdlib.h>

#include <stddef.h>

#include <string.h>

#include <assert.h>

#include <stdio.h>

#include <stdarg.h>

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

#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))

#else

#define HB_UNUSED

#endif

#ifndef HB_INTERNAL

# if !defined(__MINGW32__) && !defined(__CYGWIN__)

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

# else

#  define HB_INTERNAL

# endif

#endif

#if __GNUC__ >= 3

#define HB_FUNC __PRETTY_FUNCTION__

#elif defined(_MSC_VER)

#define HB_FUNC __FUNCSIG__

#else

#define HB_FUNC __func__

#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 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

#    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)

#  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:

 * http://msdn.microsoft.com/en-ca/library/tze57ck3.aspx

 * http://msdn.microsoft.com/en-ca/library/zk17ww08.aspx

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

 */

#    define HB_USE_ATEXIT 1

#  elif defined(__ANDROID__) && (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 6))

/* This was fixed in Android NKD r8 or r8b:

 * https://code.google.com/p/android/issues/detail?id=6455

 * which introduced GCC 4.6:

 * https://developer.android.com/tools/sdk/ndk/index.html

 */

#    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)

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

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

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

/* Misc */

/* Void! */

struct _hb_void_t {};

typedef const _hb_void_t *hb_void_t;

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

static inline HB_CONST_FUNC unsigned int

_hb_popcount32 (uint32_t mask)

{

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

  return __builtin_popcount (mask);

#else

  /* "HACKMEM 169" */

  uint32_t y;

  y = (mask >> 1) &033333333333;

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

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

#endif

}

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

static inline HB_CONST_FUNC unsigned int

_hb_bit_storage (unsigned int number)

{

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

  return likely (number) ? (sizeof (unsigned int) * 8 - __builtin_clz (number)) : 0;

#else

  unsigned int n_bits = 0;

  while (number) {

    n_bits++;

    number >>= 1;

  }

  return n_bits;

#endif

}

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

static inline HB_CONST_FUNC unsigned int

_hb_ctz (unsigned int number)

{

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

  return likely (number) ? __builtin_ctz (number) : 0;

#else

  unsigned int n_bits = 0;

  if (unlikely (!number)) return 0;

  while (!(number & 1)) {

    n_bits++;

    number >>= 1;

  }

  return n_bits;

#endif

}

static inline bool

_hb_unsigned_int_mul_overflows (unsigned int count, unsigned int size)

{

  return (size > 0) && (count >= ((unsigned int) -1) / size);

}

/* arrays and maps */

template <typename Type, unsigned int StaticSize=16>

struct hb_prealloced_array_t

{

  unsigned int len;

  unsigned int allocated;

  Type *array;

  Type static_array[StaticSize];

  inline Type& operator [] (unsigned int i) { return array[i]; }

  inline const Type& operator [] (unsigned int i) const { return array[i]; }

  inline Type *push (void)

  {

      }

    }

  }

  inline void pop (void)

  {

    len--;

  }

  inline void remove (unsigned int i)

  {

     if (unlikely (i >= len))

       return;

     memmove (static_cast<void *> (&array[i]),

              static_cast<void *> (&array[i + 1]),

              (len - i - 1) * sizeof (Type));

     len--;

  }

  inline void shrink (unsigned int l)

  {

     if (l < len)

       len = l;

  }

  template <typename T>

  inline Type *find (T v) {

    for (unsigned int i = 0; i < len; i++)

      if (array[i] == v)

        return &array[i];

  }

  template <typename T>

  inline const Type *find (T v) const {

    for (unsigned int i = 0; i < len; i++)

      if (array[i] == v)

        return &array[i];

  }

  inline void qsort (void)

  {

  }

  inline void qsort (unsigned int start, unsigned int end)

  {

  }

  template <typename T>

  {

  }

  template <typename T>

  {