/*

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

/* We only use these two for debug output.  However, the debug code is

 * always seen by the compiler (and optimized out in non-debug builds.

 * If including these becomes a problem, we can start thinking about

 * someway around that. */

#include <stdio.h>

#include <errno.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 */

#if defined(__GNUC__) && (__GNUC__ > 2) && defined(__OPTIMIZE__)

#define _HB_BOOLEAN_EXPR(expr) ((expr) ? 1 : 0)

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

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

#else

#define likely(expr) (expr)

#define unlikely(expr) (expr)

#endif

#ifndef __GNUC__

#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

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

#    define getenv(Name) NULL

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

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

#ifndef NULL

# define NULL ((void *) 0)

#endif

#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_STATIC1(_line, _cond)   HB_UNUSED typedef int _static_assert_on_line_##_line##_failed[(_cond)?1:-1]

#define _ASSERT_STATIC0(_line, _cond)   _ASSERT_STATIC1 (_line, (_cond))

#define ASSERT_STATIC(_cond)            _ASSERT_STATIC0 (__LINE__, (_cond))

/* Note: C++ allows sizeof() of variable-lengh arrays.  So, if _cond is not

 * constant, it still compiles (ouch!), but at least we'll get a -Wvla warning. */

#define ASSERT_STATIC_EXPR_ZERO(_cond) (0 * sizeof (char[(_cond) ? 1 : -1]))

#define _PASTE1(a,b) a##b

#define PASTE(a,b) _PASTE1(a,b)

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

ASSERT_STATIC (sizeof (int8_t) == 1);

ASSERT_STATIC (sizeof (uint8_t) == 1);

ASSERT_STATIC (sizeof (int16_t) == 2);

ASSERT_STATIC (sizeof (uint16_t) == 2);

ASSERT_STATIC (sizeof (int32_t) == 4);

ASSERT_STATIC (sizeof (uint32_t) == 4);

ASSERT_STATIC (sizeof (int64_t) == 8);

ASSERT_STATIC (sizeof (uint64_t) == 8);

ASSERT_STATIC (sizeof (hb_codepoint_t) == 4);

ASSERT_STATIC (sizeof (hb_position_t) == 4);

ASSERT_STATIC (sizeof (hb_mask_t) == 4);

ASSERT_STATIC (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__)

/* Misc */

/* Void! */

struct _hb_void_t {};

typedef const _hb_void_t *hb_void_t;

#define HB_VOID ((const _hb_void_t *) NULL)

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

}

/* Type of bsearch() / qsort() compare function */

typedef int (*hb_compare_func_t) (const void *, const void *);

/* arrays and maps */

#define HB_PREALLOCED_ARRAY_INIT {0, 0, NULL}

template <typename Type, unsigned int StaticSize=16>

struct hb_prealloced_array_t

{

  unsigned int len;

  unsigned int allocated;

  Type *array;

  Type static_array[StaticSize];

  void init (void) { memset (this, 0, sizeof (*this)); }

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

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

  inline Type *push (void)

  {

    if (!array) {

      array = static_array;

      allocated = ARRAY_LENGTH (static_array);

    }

    if (likely (len < allocated))

      return &array[len++];

    /* Need to reallocate */

    unsigned int new_allocated = allocated + (allocated >> 1) + 8;

    Type *new_array = NULL;

    if (array == static_array) {

      new_array = (Type *) calloc (new_allocated, sizeof (Type));

      if (new_array)

        memcpy (new_array, array, len * sizeof (Type));

    } else {

      bool overflows = (new_allocated < allocated) || _hb_unsigned_int_mul_overflows (new_allocated, sizeof (Type));

      if (likely (!overflows)) {

        new_array = (Type *) realloc (array, new_allocated * sizeof (Type));

      }

    }

    if (unlikely (!new_array))

      return NULL;

    array = new_array;

    allocated = new_allocated;

    return &array[len++];

  }

  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];

    return NULL;

  }

  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];

    return NULL;

  }

  inline void qsort (void)

  {

    ::qsort (array, len, sizeof (Type), (hb_compare_func_t) Type::cmp);

  }

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

  {

    ::qsort (array + start, end - start, sizeof (Type), (hb_compare_func_t) Type::cmp);

  }

  template <typename T>

  inline Type *bsearch (T *key)

  {

    return (Type *) ::bsearch (key, array, len, sizeof (Type), (hb_compare_func_t) Type::cmp);

  }

  template <typename T>

  inline const Type *bsearch (T *key) const

  {

    return (const Type *) ::bsearch (key, array, len, sizeof (Type), (hb_compare_func_t) Type::cmp);

  }

  inline void finish (void)

  {

    if (array != static_array)

      free (array);

    array = NULL;

    allocated = len = 0;

  }

};

template <typename Type>

struct hb_auto_array_t : hb_prealloced_array_t <Type>

{

  hb_auto_array_t (void) { hb_prealloced_array_t<Type>::init (); }

  ~hb_auto_array_t (void) { hb_prealloced_array_t<Type>::finish (); }

};

#define HB_LOCKABLE_SET_INIT {HB_PREALLOCED_ARRAY_INIT}

template <typename item_t, typename lock_t>

struct hb_lockable_set_t

{

  hb_prealloced_array_t <item_t, 2> items;

  inline void init (void) { items.init (); }

  template <typename T>

  inline item_t *replace_or_insert (T v, lock_t &l, bool replace)

  {

    l.lock ();

    item_t *item = items.find (v);

    if (item) {

      if (replace) {

        item_t old = *item;

        *item = v;

        l.unlock ();

        old.finish ();

      }

      else {

        item = NULL;

        l.unlock ();

      }

    } else {

      item = items.push ();

      if (likely (item))

        *item = v;

      l.unlock ();

    }

    return item;

  }

  template <typename T>

  inline void remove (T v, lock_t &l)

  {

    l.lock ();

    item_t *item = items.find (v);

    if (item) {

      item_t old = *item;

      *item = items[items.len - 1];

      items.pop ();

      l.unlock ();

      old.finish ();

    } else {

      l.unlock ();

    }

  }

  template <typename T>

  inline bool find (T v, item_t *i, lock_t &l)

  {

    l.lock ();

    item_t *item = items.find (v);

    if (item)

      *i = *item;

    l.unlock ();

    return !!item;

  }

  template <typename T>

  inline item_t *find_or_insert (T v, lock_t &l)

  {

    l.lock ();

    item_t *item = items.find (v);

    if (!item) {

      item = items.push ();

      if (likely (item))

        *item = v;

    }

    l.unlock ();

    return item;

  }

  inline void finish (lock_t &l)