/*

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

 *

 */

#ifndef HB_OT_VAR_COMMON_HH

#define HB_OT_VAR_COMMON_HH

#include "hb-ot-layout-common.hh"

#include "hb-alloc-pool.hh"

#include "hb-priority-queue.hh"

#include "hb-subset-instancer-iup.hh"

namespace OT {

using rebase_tent_result_scratch_t = hb_pair_t<rebase_tent_result_t, rebase_tent_result_t>;

/* https://docs.microsoft.com/en-us/typography/opentype/spec/otvarcommonformats#tuplevariationheader */

struct TupleVariationHeader

{

  friend struct tuple_delta_t;

  size_t get_size (unsigned axis_count_times_2) const

  {

    // This function is super hot in mega-var-fonts with hundreds of masters.

    unsigned ti = tupleIndex;

    if (unlikely ((ti & (TupleIndex::EmbeddedPeakTuple | TupleIndex::IntermediateRegion))))

    {

      unsigned count = ((ti & TupleIndex::EmbeddedPeakTuple) != 0) + ((ti & TupleIndex::IntermediateRegion) != 0) * 2;

      return hb_unsigned_mul_add_saturate (count, axis_count_times_2, min_size);

    }

    return min_size;

  }

  unsigned get_data_size () const { return varDataSize; }

  const TupleVariationHeader &get_next (unsigned axis_count_times_2) const

  { return StructAtOffset<TupleVariationHeader> (this, get_size (axis_count_times_2)); }

  bool unpack_axis_tuples (unsigned axis_count,

                           const hb_array_t<const F2DOT14> shared_tuples,

                           const hb_map_t *axes_old_index_tag_map,

                           hb_hashmap_t<hb_tag_t, Triple>& axis_tuples /* OUT */) const

  {

    const F2DOT14 *peak_tuple = nullptr;

    if (has_peak ())

      peak_tuple = get_peak_tuple (axis_count);

    else

    {

      unsigned int index = get_index ();

      if (unlikely ((index + 1) * axis_count > shared_tuples.length))

        return false;

      peak_tuple = shared_tuples.sub_array (axis_count * index, axis_count).arrayZ;

    }

    const F2DOT14 *start_tuple = nullptr;

    const F2DOT14 *end_tuple = nullptr;

    bool has_interm = has_intermediate ();

    if (has_interm)

    {

      start_tuple = get_start_tuple (axis_count);

      end_tuple = get_end_tuple (axis_count);

    }

    for (unsigned i = 0; i < axis_count; i++)

    {

      float peak = peak_tuple[i].to_float ();

      if (peak == 0.f) continue;

      hb_tag_t *axis_tag;

      if (!axes_old_index_tag_map->has (i, &axis_tag))

        return false;

      float start, end;

      if (has_interm)

      {

        start = start_tuple[i].to_float ();

        end = end_tuple[i].to_float ();

      }

      else

      {

        start = hb_min (peak, 0.f);

        end = hb_max (peak, 0.f);

      }

      axis_tuples.set (*axis_tag, Triple ((double) start, (double) peak, (double) end));

    }

    return true;

  }

  HB_ALWAYS_INLINE

  double calculate_scalar (hb_array_t<const int> coords, unsigned int coord_count,

         const hb_array_t<const F2DOT14> shared_tuples,

         hb_scalar_cache_t *shared_tuple_scalar_cache = (hb_scalar_cache_t *) &Null(hb_scalar_cache_t)) const

  {

    unsigned tuple_index = tupleIndex;

    unsigned int index = tuple_index & TupleIndex::TupleIndexMask;

    /* The gvar shared-tuple cache is clamped to the 12-bit tuple-index range.

     * Only PrivatePointNumbers may accompany a cached shared-tuple index; any

     * other flag sets a bit at or above 0x1000, making this range test fail.

     */

    bool plain_shared_tuple = (tuple_index & ~TupleIndex::PrivatePointNumbers) < shared_tuple_scalar_cache->length;

    if (likely (plain_shared_tuple))

    {

      float scalar;

      if (likely (shared_tuple_scalar_cache->get (index, &scalar)))

  return (double) scalar;

    }

    const F2DOT14 *peak_tuple;

    bool has_interm = tuple_index & TupleIndex::IntermediateRegion; // Inlined for performance

    if (unlikely (tuple_index & TupleIndex::EmbeddedPeakTuple)) // Inlined for performance

    {

      peak_tuple = get_peak_tuple (coord_count);

      shared_tuple_scalar_cache = nullptr;

    }

    else

    {

      float scalar;

      if (!plain_shared_tuple &&

    shared_tuple_scalar_cache->length &&

    shared_tuple_scalar_cache->get (index, &scalar))

      {

        if (has_interm && (scalar != 0 && scalar != 1.f))

    shared_tuple_scalar_cache = nullptr;

  else

    return (double) scalar;

      }

      if (unlikely ((index + 1) * coord_count > shared_tuples.length))

        return 0.0;

      peak_tuple = shared_tuples.arrayZ + (coord_count * index);

    }

    const F2DOT14 *start_tuple = nullptr;

    const F2DOT14 *end_tuple = nullptr;

    if (has_interm)

    {

      start_tuple = get_start_tuple (coord_count);

      end_tuple = get_end_tuple (coord_count);

    }

    double scalar = 1.0;

#ifndef HB_OPTIMIZE_SIZE

#if HB_FAST_NUM_ACCESS

    bool skip = coord_count >= 16;

#endif

#endif

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

    {

#ifndef HB_OPTIMIZE_SIZE

#if HB_FAST_NUM_ACCESS

      if (skip)

      {

  while (i + 4 <= coord_count && * (HBUINT64LE *) &peak_tuple[i] == 0)

    i += 4;

  while (i < coord_count && peak_tuple[i].to_int () == 0)

    i += 1;

  if (i >= coord_count)

    break;

      }

#endif

#endif

      int peak = peak_tuple[i].to_int ();

      if (!peak) continue;

      int v = coords[i];

      if (!v) { scalar = 0.0; break; }

      if (v == peak) continue;

      if (has_interm)

      {

  shared_tuple_scalar_cache = nullptr;

        int start = start_tuple[i].to_int ();

        int end = end_tuple[i].to_int ();

        if (unlikely (start > peak || peak > end ||

                      (start < 0 && end > 0 && peak))) continue;

        if (v < start || v > end) { scalar = 0.0; break; }

        if (v < peak)

        { if (peak != start) scalar *= (double) (v - start) / (peak - start); }

        else

        { if (peak != end) scalar *= (double) (end - v) / (end - peak); }

      }

      else if (v < hb_min (0, peak) || v > hb_max (0, peak)) { scalar = 0.0; break; }

      else

        scalar *= (double) v / peak;

    }

    if (shared_tuple_scalar_cache)

      shared_tuple_scalar_cache->set (index, scalar);

    return scalar;

  }

  bool           has_peak () const { return tupleIndex & TupleIndex::EmbeddedPeakTuple; }

  bool   has_intermediate () const { return tupleIndex & TupleIndex::IntermediateRegion; }

  bool has_private_points () const { return tupleIndex & TupleIndex::PrivatePointNumbers; }

  unsigned      get_index () const { return tupleIndex & TupleIndex::TupleIndexMask; }

  static constexpr unsigned max_shared_tuple_count = 0x1000u;

  protected:

  struct TupleIndex : HBUINT16

  {

    enum Flags {

      EmbeddedPeakTuple   = 0x8000u,

      IntermediateRegion  = 0x4000u,

      PrivatePointNumbers = 0x2000u,

      TupleIndexMask      = 0x0FFFu

    };

    TupleIndex& operator = (uint16_t i) { HBUINT16::operator= (i); return *this; }

    DEFINE_SIZE_STATIC (2);

  };

  hb_array_t<const F2DOT14> get_all_tuples (unsigned axis_count) const

  { return StructAfter<UnsizedArrayOf<F2DOT14>> (tupleIndex).as_array ((has_peak () + has_intermediate () * 2) * axis_count); }

  const F2DOT14* get_all_tuples_base (unsigned axis_count) const

  { return StructAfter<UnsizedArrayOf<F2DOT14>> (tupleIndex).arrayZ; }

  const F2DOT14* get_peak_tuple (unsigned axis_count) const

  { return get_all_tuples_base (axis_count); }

  const F2DOT14* get_start_tuple (unsigned axis_count) const

  { return get_all_tuples_base (axis_count) + has_peak () * axis_count; }

  const F2DOT14* get_end_tuple (unsigned axis_count) const

  { return get_all_tuples_base (axis_count) + has_peak () * axis_count + axis_count; }

  HBUINT16      varDataSize;    /* The size in bytes of the serialized

                                 * data for this tuple variation table. */

  TupleIndex    tupleIndex;     /* A packed field. The high 4 bits are flags (see below).

                                   The low 12 bits are an index into a shared tuple

                                   records array. */

  /* UnsizedArrayOf<F2DOT14> peakTuple - optional */

                                /* Peak tuple record for this tuple variation table — optional,

                                 * determined by flags in the tupleIndex value.

                                 *

                                 * Note that this must always be included in the 'cvar' table. */

  /* UnsizedArrayOf<F2DOT14> intermediateStartTuple - optional */

                                /* Intermediate start tuple record for this tuple variation table — optional,

                                   determined by flags in the tupleIndex value. */

  /* UnsizedArrayOf<F2DOT14> intermediateEndTuple - optional */

                                /* Intermediate end tuple record for this tuple variation table — optional,

                                 * determined by flags in the tupleIndex value. */

  public:

  DEFINE_SIZE_MIN (4);

};

struct optimize_scratch_t

{

  iup_scratch_t iup;

  hb_vector_t<bool> opt_indices;

  hb_vector_t<int> rounded_x_deltas;

  hb_vector_t<int> rounded_y_deltas;

  hb_vector_t<float> opt_deltas_x;

  hb_vector_t<float> opt_deltas_y;

  hb_vector_t<unsigned char> opt_point_data;

  hb_vector_t<unsigned char> opt_deltas_data;

  hb_vector_t<unsigned char> point_data;

  hb_vector_t<unsigned char> deltas_data;

  hb_vector_t<int> rounded_deltas;

};

struct tuple_delta_t

{

  static constexpr bool realloc_move = true;  // Watch out when adding new members!

  public:

  hb_hashmap_t<hb_tag_t, Triple> axis_tuples;

  /* indices_length = point_count, indice[i] = 1 means point i is referenced */

  hb_vector_t<bool> indices;

  hb_vector_t<float> deltas_x;

  /* empty for cvar tuples */

  hb_vector_t<float> deltas_y;

  /* compiled data: header and deltas

   * compiled point data is saved in a hashmap within tuple_variations_t cause

   * some point sets might be reused by different tuple variations */

  hb_vector_t<unsigned char> compiled_tuple_header;

  hb_vector_t<unsigned char> compiled_deltas;

  hb_vector_t<F2DOT14> compiled_peak_coords;

  hb_vector_t<F2DOT14> compiled_interm_coords;

  tuple_delta_t (hb_alloc_pool_t *pool = nullptr) {}

  tuple_delta_t (const tuple_delta_t& o) = default;

  tuple_delta_t& operator = (const tuple_delta_t& o) = default;

  friend void swap (tuple_delta_t& a, tuple_delta_t& b) noexcept

  {

    hb_swap (a.axis_tuples, b.axis_tuples);

    hb_swap (a.indices, b.indices);

    hb_swap (a.deltas_x, b.deltas_x);

    hb_swap (a.deltas_y, b.deltas_y);

    hb_swap (a.compiled_tuple_header, b.compiled_tuple_header);

    hb_swap (a.compiled_deltas, b.compiled_deltas);

    hb_swap (a.compiled_peak_coords, b.compiled_peak_coords);

  }

  tuple_delta_t (tuple_delta_t&& o)  noexcept : tuple_delta_t ()

  { hb_swap (*this, o); }

  tuple_delta_t& operator = (tuple_delta_t&& o) noexcept

  {

    hb_swap (*this, o);

    return *this;

  }

  void copy_from (const tuple_delta_t& o, hb_alloc_pool_t *pool = nullptr)

  {

    axis_tuples = o.axis_tuples;

    indices.duplicate_vector_from_pool (pool, o.indices);

    deltas_x.duplicate_vector_from_pool (pool, o.deltas_x);

    deltas_y.duplicate_vector_from_pool (pool, o.deltas_y);

    compiled_tuple_header.duplicate_vector_from_pool (pool, o.compiled_tuple_header);

    compiled_deltas.duplicate_vector_from_pool (pool, o.compiled_deltas);

    compiled_peak_coords.duplicate_vector_from_pool (pool, o.compiled_peak_coords);

    compiled_interm_coords.duplicate_vector_from_pool (pool, o.compiled_interm_coords);

  }

  void remove_axis (hb_tag_t axis_tag)

  { axis_tuples.del (axis_tag); }

  bool set_tent (hb_tag_t axis_tag, Triple tent)

  { return axis_tuples.set (axis_tag, tent); }

  tuple_delta_t& operator += (const tuple_delta_t& o)

  {

    unsigned num = indices.length;

    for (unsigned i = 0; i < num; i++)

    {

      if (indices.arrayZ[i])

      {

        if (o.indices.arrayZ[i])

        {

          deltas_x[i] += o.deltas_x[i];

          if (deltas_y && o.deltas_y)

            deltas_y[i] += o.deltas_y[i];

        }

      }

      else

      {

        if (!o.indices.arrayZ[i]) continue;

        indices.arrayZ[i] = true;

        deltas_x[i] = o.deltas_x[i];

        if (deltas_y && o.deltas_y)

          deltas_y[i] = o.deltas_y[i];

      }

    }

    return *this;

  }

  tuple_delta_t& operator *= (float scalar)

  {

    if (scalar == 1.0f)

      return *this;

    unsigned num = indices.length;

    if (deltas_y)

      for (unsigned i = 0; i < num; i++)

      {

  if (!indices.arrayZ[i]) continue;

  deltas_x[i] *= scalar;

  deltas_y[i] *= scalar;

      }

    else

      for (unsigned i = 0; i < num; i++)

      {

  if (!indices.arrayZ[i]) continue;

  deltas_x[i] *= scalar;

      }

    return *this;

  }

  void change_tuple_var_axis_limit (hb_tag_t axis_tag, Triple axis_limit,

            TripleDistances axis_triple_distances,

            hb_vector_t<tuple_delta_t>& out,

            rebase_tent_result_scratch_t &scratch,

            hb_alloc_pool_t *pool = nullptr)

  {

    // May move *this out.

    out.reset ();

    Triple *tent;

    if (!axis_tuples.has (axis_tag, &tent))

    {

      out.push (std::move (*this));

      return;

    }

    if ((tent->minimum < 0.0 && tent->maximum > 0.0) ||

        !(tent->minimum <= tent->middle && tent->middle <= tent->maximum))

      return;

    if (tent->middle == 0.0)

    {

      out.push (std::move (*this));

      return;

    }

    if (!axis_limit.is_point () &&

        !(-1.0 <= axis_limit.minimum &&

          axis_limit.minimum <= axis_limit.middle &&

          axis_limit.middle <= axis_limit.maximum &&

          axis_limit.maximum <= +1.0))

      return;

    rebase_tent_result_t &solutions = scratch.first;

    rebase_tent (*tent, axis_limit, axis_triple_distances, solutions, scratch.second);

    for (unsigned i = 0; i < solutions.length; i++)

    {

      auto &t = solutions.arrayZ[i];

      tuple_delta_t new_var;

      if (i < solutions.length - 1)

  new_var.copy_from (*this, pool);

      else

  new_var = std::move (*this);

      if (t.second == Triple ())

        new_var.remove_axis (axis_tag);

      else

        new_var.set_tent (axis_tag, t.second);

      new_var *= t.first;

      out.push (std::move (new_var));

    }

  }

  bool compile_coords (const hb_map_t& axes_index_map,

           const hb_map_t& axes_old_index_tag_map,

           hb_alloc_pool_t *pool= nullptr)

  {

    unsigned cur_axis_count = axes_index_map.get_population ();

    if (pool)

    {

      if (unlikely (!compiled_peak_coords.allocate_from_pool (pool, cur_axis_count)))

  return false;

    }

    else if (unlikely (!compiled_peak_coords.resize (cur_axis_count)))

      return false;

    hb_array_t<F2DOT14> start_coords, end_coords;

    unsigned orig_axis_count = axes_old_index_tag_map.get_population ();

    unsigned j = 0;

    for (unsigned i = 0; i < orig_axis_count; i++)

    {

      if (!axes_index_map.has (i))

        continue;

      hb_tag_t axis_tag = axes_old_index_tag_map.get (i);

      Triple *coords = nullptr;

      if (axis_tuples.has (axis_tag, &coords))

      {

  float min_val = coords->minimum;

  float val = coords->middle;

  float max_val = coords->maximum;

  compiled_peak_coords.arrayZ[j].set_float (val);

  if (min_val != hb_min (val, 0.f) || max_val != hb_max (val, 0.f))

  {

    if (!compiled_interm_coords)

    {

      if (pool)

      {

        if (unlikely (!compiled_interm_coords.allocate_from_pool (pool, 2 * cur_axis_count)))

    return false;

      }

      else if (unlikely (!compiled_interm_coords.resize (2 * cur_axis_count)))

        return false;

      start_coords = compiled_interm_coords.as_array ().sub_array (0, cur_axis_count);

      end_coords = compiled_interm_coords.as_array ().sub_array (cur_axis_count);

      for (unsigned k = 0; k < j; k++)

      {

        signed peak = compiled_peak_coords.arrayZ[k].to_int ();

        if (!peak) continue;

        start_coords.arrayZ[k].set_int (hb_min (peak, 0));

        end_coords.arrayZ[k].set_int (hb_max (peak, 0));

      }

    }

  }

  if (compiled_interm_coords)

  {

    start_coords.arrayZ[j].set_float (min_val);

    end_coords.arrayZ[j].set_float (max_val);

  }

      }

      j++;

    }

    return !compiled_peak_coords.in_error () && !compiled_interm_coords.in_error ();

  }

  /* deltas should be compiled already before we compile tuple

   * variation header cause we need to fill in the size of the

   * serialized data for this tuple variation */

  bool compile_tuple_var_header (const hb_map_t& axes_index_map,

                                 unsigned points_data_length,

                                 const hb_map_t& axes_old_index_tag_map,

                                 const hb_hashmap_t<const hb_vector_t<F2DOT14>*, unsigned>* shared_tuples_idx_map,

         hb_alloc_pool_t *pool = nullptr)

  {

    /* compiled_deltas could be empty after iup delta optimization, we can skip

     * compiling this tuple and return true */

    if (!compiled_deltas) return true;

    unsigned cur_axis_count = axes_index_map.get_population ();

    /* allocate enough memory: 1 peak + 2 intermediate coords + fixed header size */

    unsigned alloc_len = 3 * cur_axis_count * (F2DOT14::static_size) + 4;

    if (unlikely (!compiled_tuple_header.allocate_from_pool (pool, alloc_len, false))) return false;

    unsigned flag = 0;

    /* skip the first 4 header bytes: variationDataSize+tupleIndex */

    F2DOT14* p = reinterpret_cast<F2DOT14 *> (compiled_tuple_header.begin () + 4);

    F2DOT14* end = reinterpret_cast<F2DOT14 *> (compiled_tuple_header.end ());

    hb_array_t<F2DOT14> coords (p, end - p);

    if (!shared_tuples_idx_map)

      compile_coords (axes_index_map, axes_old_index_tag_map); // non-gvar tuples do not have compiled coords yet

    /* encode peak coords */

    unsigned peak_count = 0;

    unsigned *shared_tuple_idx;

    if (shared_tuples_idx_map &&

        shared_tuples_idx_map->has (&compiled_peak_coords, &shared_tuple_idx))

    {

      flag = *shared_tuple_idx;

    }

    else

    {

      peak_count = encode_peak_coords(coords, flag);

      if (!peak_count) return false;

    }

    /* encode interim coords, it's optional so returned num could be 0 */

    unsigned interim_count = encode_interm_coords (coords.sub_array (peak_count), flag);

    /* pointdata length = 0 implies "use shared points" */

    if (points_data_length)

      flag |= TupleVariationHeader::TupleIndex::PrivatePointNumbers;

    unsigned serialized_data_size = points_data_length + compiled_deltas.length;

    TupleVariationHeader *o = reinterpret_cast<TupleVariationHeader *> (compiled_tuple_header.begin ());

    o->varDataSize = serialized_data_size;

    o->tupleIndex = flag;

    unsigned total_header_len = 4 + (peak_count + interim_count) * (F2DOT14::static_size);

    compiled_tuple_header.shrink_back_to_pool (pool, total_header_len);

    return true;

  }

  unsigned encode_peak_coords (hb_array_t<F2DOT14> peak_coords,

                               unsigned& flag) const

  {

    hb_memcpy (&peak_coords[0], &compiled_peak_coords[0], compiled_peak_coords.length * sizeof (compiled_peak_coords[0]));

    flag |= TupleVariationHeader::TupleIndex::EmbeddedPeakTuple;

    return compiled_peak_coords.length;

  }

  /* if no need to encode intermediate coords, then just return p */

  unsigned encode_interm_coords (hb_array_t<F2DOT14> coords,

                                 unsigned& flag) const

  {

    if (compiled_interm_coords)

    {

      hb_memcpy (&coords[0], &compiled_interm_coords[0], compiled_interm_coords.length * sizeof (compiled_interm_coords[0]));

      flag |= TupleVariationHeader::TupleIndex::IntermediateRegion;

    }

    return compiled_interm_coords.length;

  }

  bool compile_deltas (hb_vector_t<int> &rounded_deltas_scratch,

           hb_alloc_pool_t *pool = nullptr)

  { return compile_deltas (indices, deltas_x, deltas_y, compiled_deltas, rounded_deltas_scratch, pool); }

  static bool compile_deltas (hb_array_t<const bool> point_indices,

            hb_array_t<const float> x_deltas,

            hb_array_t<const float> y_deltas,

            hb_vector_t<unsigned char> &compiled_deltas, /* OUT */

            hb_vector_t<int> &rounded_deltas, /* scratch */

            hb_alloc_pool_t *pool = nullptr)

  {

    if (unlikely (!rounded_deltas.resize_dirty  (point_indices.length)))

      return false;

    unsigned j = 0;

    for (unsigned i = 0; i < point_indices.length; i++)

    {

      if (!point_indices[i]) continue;

      rounded_deltas.arrayZ[j++] = hb_clamp_to<int> (roundf ((double) x_deltas.arrayZ[i]));

    }

    rounded_deltas.resize (j);

    if (!rounded_deltas) return true;

    /* Allocate enough memory: this is the correct bound:

     * Worst case scenario is that each delta has to be encoded in 4 bytes, and there

     * are runs of 64 items each. Any delta encoded in less than 4 bytes (2, 1, or 0)

     * is still smaller than the 4-byte encoding even with their control byte.

     * The initial 2 is to handle length==0, for both x and y deltas. */

    unsigned alloc_len = 2 + 4 * rounded_deltas.length + (rounded_deltas.length + 63) / 64;

    if (y_deltas)

      alloc_len *= 2;

    if (unlikely (!compiled_deltas.allocate_from_pool (pool, alloc_len, false))) return false;

    unsigned encoded_len = compile_deltas (compiled_deltas, rounded_deltas);

    if (y_deltas)

    {

      /* reuse the rounded_deltas vector, check that y_deltas have the same num of deltas as x_deltas */

      unsigned j = 0;

      for (unsigned idx = 0; idx < point_indices.length; idx++)

      {

        if (!point_indices[idx]) continue;

        int rounded_delta = hb_clamp_to<int> (roundf ((double) y_deltas.arrayZ[idx]));

        if (j >= rounded_deltas.length) return false;

        rounded_deltas[j++] = rounded_delta;

      }

      if (j != rounded_deltas.length) return false;

      encoded_len += compile_deltas (compiled_deltas.as_array ().sub_array (encoded_len), rounded_deltas);

    }

    compiled_deltas.shrink_back_to_pool (pool, encoded_len);

    return true;

  }

  static unsigned compile_deltas (hb_array_t<unsigned char> encoded_bytes,

          hb_array_t<const int> deltas)

  {

    return TupleValues::compile_unsafe (deltas, encoded_bytes);

  }

  bool calc_inferred_deltas (const contour_point_vector_t& orig_points,

           hb_vector_t<unsigned> &scratch)

  {

    unsigned point_count = orig_points.length;

    if (point_count != indices.length)

      return false;

    unsigned ref_count = 0;

    hb_vector_t<unsigned> &end_points = scratch.reset ();

    for (unsigned i = 0; i < point_count; i++)

    {

      ref_count += indices.arrayZ[i];

      if (orig_points.arrayZ[i].is_end_point)

        end_points.push (i);

    }

    /* all points are referenced, nothing to do */

    if (ref_count == point_count)

      return true;

    if (unlikely (end_points.in_error ())) return false;

    hb_bit_set_t inferred_idxes;

    unsigned start_point = 0;

    for (unsigned end_point : end_points)

    {

      /* Check the number of unreferenced points in a contour. If no unref points or no ref points, nothing to do. */

      unsigned unref_count = 0;

      for (unsigned i = start_point; i < end_point + 1; i++)

        unref_count += indices.arrayZ[i];

      unref_count = (end_point - start_point + 1) - unref_count;

      unsigned j = start_point;

      if (unref_count == 0 || unref_count > end_point - start_point)

        goto no_more_gaps;

      for (;;)

      {

        /* Locate the next gap of unreferenced points between two referenced points prev and next.

         * Note that a gap may wrap around at left (start_point) and/or at right (end_point).

         */

        unsigned int prev, next, i;

        for (;;)

        {

          i = j;

          j = next_index (i, start_point, end_point);

          if (indices.arrayZ[i] && !indices.arrayZ[j]) break;

        }

        prev = j = i;

        for (;;)

        {

          i = j;

          j = next_index (i, start_point, end_point);

          if (!indices.arrayZ[i] && indices.arrayZ[j]) break;

        }

        next = j;

       /* Infer deltas for all unref points in the gap between prev and next */

        i = prev;

        for (;;)

        {

          i = next_index (i, start_point, end_point);

          if (i == next) break;

          deltas_x.arrayZ[i] = infer_delta ((double) orig_points.arrayZ[i].x,

                                            (double) orig_points.arrayZ[prev].x,

                                            (double) orig_points.arrayZ[next].x,

                                            (double) deltas_x.arrayZ[prev], (double) deltas_x.arrayZ[next]);

          deltas_y.arrayZ[i] = infer_delta ((double) orig_points.arrayZ[i].y,

                                            (double) orig_points.arrayZ[prev].y,

                                            (double) orig_points.arrayZ[next].y,

                                            (double) deltas_y.arrayZ[prev], (double) deltas_y.arrayZ[next]);

          inferred_idxes.add (i);

          if (--unref_count == 0) goto no_more_gaps;

        }

      }

    no_more_gaps:

      start_point = end_point + 1;

    }

    for (unsigned i = 0; i < point_count; i++)

    {

      /* if points are not referenced and deltas are not inferred, set to 0.

       * reference all points for gvar */

      if ( !indices[i])

      {

        if (!inferred_idxes.has (i))

        {

          deltas_x.arrayZ[i] = 0.0;

          deltas_y.arrayZ[i] = 0.0;

        }

        indices[i] = true;

      }

    }

    return true;

  }

  bool optimize (const contour_point_vector_t& contour_points,

                 bool is_composite,

     optimize_scratch_t &scratch,

                 double tolerance = 0.5 + 1e-10)

  {

    unsigned count = contour_points.length;

    if (deltas_x.length != count ||

        deltas_y.length != count)

      return false;

    hb_vector_t<bool> &opt_indices = scratch.opt_indices.reset ();

    hb_vector_t<int> &rounded_x_deltas = scratch.rounded_x_deltas;

    hb_vector_t<int> &rounded_y_deltas = scratch.rounded_y_deltas;

    if (unlikely (!rounded_x_deltas.resize_dirty  (count) ||

                  !rounded_y_deltas.resize_dirty  (count)))

      return false;

    for (unsigned i = 0; i < count; i++)

    {

      rounded_x_deltas.arrayZ[i] = hb_clamp_to<int> (roundf ((double) deltas_x.arrayZ[i]));

      rounded_y_deltas.arrayZ[i] = hb_clamp_to<int> (roundf ((double) deltas_y.arrayZ[i]));

    }

    if (!iup_delta_optimize (contour_points, rounded_x_deltas, rounded_y_deltas, opt_indices, scratch.iup, tolerance))

      return false;

    unsigned ref_count = 0;

    for (bool ref_flag : opt_indices)

       ref_count += ref_flag;

    if (ref_count == count) return true;

    hb_vector_t<float> &opt_deltas_x = scratch.opt_deltas_x.reset ();

    hb_vector_t<float> &opt_deltas_y = scratch.opt_deltas_y.reset ();

    bool is_comp_glyph_wo_deltas = (is_composite && ref_count == 0);

    if (is_comp_glyph_wo_deltas)

    {

      if (unlikely (!opt_deltas_x.resize (count) ||

                    !opt_deltas_y.resize (count)))

        return false;

      opt_indices.arrayZ[0] = true;

      for (unsigned i = 1; i < count; i++)

        opt_indices.arrayZ[i] = false;

    }

    hb_vector_t<unsigned char> &opt_point_data = scratch.opt_point_data.reset ();

    if (!compile_point_set (opt_indices, opt_point_data))

      return false;

    hb_vector_t<unsigned char> &opt_deltas_data = scratch.opt_deltas_data.reset ();

    if (!compile_deltas (opt_indices,

                         is_comp_glyph_wo_deltas ? opt_deltas_x : deltas_x,

                         is_comp_glyph_wo_deltas ? opt_deltas_y : deltas_y,

                         opt_deltas_data,

       scratch.rounded_deltas))

      return false;

    hb_vector_t<unsigned char> &point_data = scratch.point_data.reset ();

    if (!compile_point_set (indices, point_data))

      return false;

    hb_vector_t<unsigned char> &deltas_data = scratch.deltas_data.reset ();

    if (!compile_deltas (indices, deltas_x, deltas_y, deltas_data, scratch.rounded_deltas))

      return false;

    if (opt_point_data.length + opt_deltas_data.length < point_data.length + deltas_data.length)

    {

      indices = std::move (opt_indices);

      if (is_comp_glyph_wo_deltas)

      {

        deltas_x = std::move (opt_deltas_x);

        deltas_y = std::move (opt_deltas_y);

      }

    }

    return !indices.in_error () && !deltas_x.in_error () && !deltas_y.in_error ();

  }

  static bool compile_point_set (const hb_vector_t<bool> &point_indices,

                                 hb_vector_t<unsigned char>& compiled_points /* OUT */)

  {

    unsigned num_points = 0;

    for (bool i : point_indices)

      if (i) num_points++;

    /* when iup optimization is enabled, num of referenced points could be 0 */

    if (!num_points) return true;

    unsigned indices_length = point_indices.length;

    /* If the points set consists of all points in the glyph, it's encoded with a

     * single zero byte */

    if (num_points == indices_length)

      return compiled_points.resize (1);

    /* allocate enough memories: 2 bytes for count + 3 bytes for each point */

    unsigned num_bytes = 2 + 3 *num_points;

    if (unlikely (!compiled_points.resize_dirty  (num_bytes)))

      return false;

    unsigned pos = 0;

    /* binary data starts with the total number of reference points */

    if (num_points < 0x80)

      compiled_points.arrayZ[pos++] = num_points;

    else

    {

      compiled_points.arrayZ[pos++] = ((num_points >> 8) | 0x80);

      compiled_points.arrayZ[pos++] = num_points & 0xFF;

    }

    const unsigned max_run_length = 0x7F;

    unsigned i = 0;

    unsigned last_value = 0;

    unsigned num_encoded = 0;

    while (i < indices_length && num_encoded < num_points)

    {

      unsigned run_length = 0;

      unsigned header_pos = pos;

      compiled_points.arrayZ[pos++] = 0;

      bool use_byte_encoding = false;

      bool new_run = true;

      while (i < indices_length && num_encoded < num_points &&

             run_length <= max_run_length)

      {

        // find out next referenced point index

        while (i < indices_length && !point_indices[i])