text:
/*
 * Copyright © 2018  Ebrahim Byagowi
 *
 *  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_COLOR_SVG_TABLE_HH
#define HB_OT_COLOR_SVG_TABLE_HH

#include "hb-open-type.hh"

/*
 * SVG -- SVG (Scalable Vector Graphics)
 * https://docs.microsoft.com/en-us/typography/opentype/spec/svg
 */

#define HB_OT_TAG_SVG HB_TAG('S','V','G',' ')

namespace OT {

struct SVGDocumentIndexEntry
{
  int cmp (hb_codepoint_t g) const
  { return g < startGlyphID ? -1 : g > endGlyphID ? 1 : 0; }

  hb_blob_t *reference_blob (hb_blob_t *svg_blob, unsigned int index_offset) const
  {
    return hb_blob_create_sub_blob (svg_blob,
				    index_offset + (unsigned int) svgDoc,
				    svgDocLength);
  }

  bool sanitize (hb_sanitize_context_t *c, const void *base) const
  {
    TRACE_SANITIZE (this);
    return_trace (c->check_struct (this) &&
		  svgDoc.sanitize (c, base, svgDocLength));
  }

  protected:
  HBUINT16	startGlyphID;	/* The first glyph ID in the range described by
				 * this index entry. */
  HBUINT16	endGlyphID;	/* The last glyph ID in the range described by
				 * this index entry. Must be >= startGlyphID. */
  LNNOffsetTo<UnsizedArrayOf<HBUINT8>>
		svgDoc;		/* Offset from the beginning of the SVG Document Index
				 * to an SVG document. Must be non-zero. */
  HBUINT32	svgDocLength;	/* Length of the SVG document.
				 * Must be non-zero. */
  public:
  DEFINE_SIZE_STATIC (12);
};

struct SVG
{
  static constexpr hb_tag_t tableTag = HB_OT_TAG_SVG;

  bool has_data () const { return svgDocEntries; }

  struct accelerator_t
  {
    void init (hb_face_t *face)
    { table = hb_sanitize_context_t ().reference_table<SVG> (face); }
    void fini () { table.destroy (); }

    hb_blob_t *reference_blob_for_glyph (hb_codepoint_t glyph_id) const
    {
      return table->get_glyph_entry (glyph_id).reference_blob (table.get_blob (),
							       table->svgDocEntries);
    }

    bool has_data () const { return table->has_data (); }

    private:
    hb_blob_ptr_t<SVG> table;
  };

  const SVGDocumentIndexEntry &get_glyph_entry (hb_codepoint_t glyph_id) const
  { return (this+svgDocEntries).bsearch (glyph_id); }

  bool sanitize (hb_sanitize_context_t *c) const
  {
    TRACE_SANITIZE (this);
    return_trace (likely (c->check_struct (this) &&
			  (this+svgDocEntries).sanitize_shallow (c)));
  }

  protected:
  HBUINT16	version;	/* Table version (starting at 0). */
  LOffsetTo<SortedArrayOf<SVGDocumentIndexEntry>>
		svgDocEntries;	/* Offset (relative to the start of the SVG table) to the
				 * SVG Documents Index. Must be non-zero. */
				/* Array of SVG Document Index Entries. */
  HBUINT32	reserved;	/* Set to 0. */
  public:
  DEFINE_SIZE_STATIC (10);
};

struct SVG_accelerator_t : SVG::accelerator_t {};

} /* namespace OT */

#endif /* HB_OT_COLOR_SVG_TABLE_HH */


text:
/*
 * Copyright © 2007  Chris Wilson
 * Copyright © 2009,2010  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.
 *
 * Contributor(s):
 *	Chris Wilson <chris@chris-wilson.co.uk>
 * Red Hat Author(s): Behdad Esfahbod
 * Google Author(s): Behdad Esfahbod
 */

#ifndef HB_OBJECT_HH
#define HB_OBJECT_HH

#include "hb.hh"
#include "hb-atomic.hh"
#include "hb-mutex.hh"
#include "hb-vector.hh"

/*
 * Lockable set
 */

template <typename item_t, typename lock_t>
struct hb_lockable_set_t
{
  hb_vector_t<item_t> items;

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

  template <typename T>
  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.fini ();
      }
      else {
	item = nullptr;
	l.unlock ();
      }
    } else {
      item = items.push (v);
      l.unlock ();
    }
    return item;
  }

  template <typename T>
  void remove (T v, lock_t &l)
  {
    l.lock ();
    item_t *item = items.find (v);
    if (item)
    {
      item_t old = *item;
      *item = items[items.length - 1];
      items.pop ();
      l.unlock ();
      old.fini ();
    } else {
      l.unlock ();
    }
  }

  template <typename T>
  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>
  item_t *find_or_insert (T v, lock_t &l)
  {
    l.lock ();
    item_t *item = items.find (v);
    if (!item) {
      item = items.push (v);
    }
    l.unlock ();
    return item;
  }

  void fini (lock_t &l)
  {
    if (!items.length)
    {
      /* No need to lock. */
      items.fini ();
      return;
    }
    l.lock ();
    while (items.length)
    {
      item_t old = items[items.length - 1];
      items.pop ();
      l.unlock ();
      old.fini ();
      l.lock ();
    }
    items.fini ();
    l.unlock ();
  }

};

/*
 * Reference-count.
 */

#define HB_REFERENCE_COUNT_INERT_VALUE 0
#define HB_REFERENCE_COUNT_POISON_VALUE -0x0000DEAD
#define HB_REFERENCE_COUNT_INIT {HB_ATOMIC_INT_INIT (HB_REFERENCE_COUNT_INERT_VALUE)}

struct hb_reference_count_t
{
  mutable hb_atomic_int_t ref_count;

  void init (int v = 1) { ref_count.set_relaxed (v); }
  int get_relaxed () const { return ref_count.get_relaxed (); }
  int inc () const { return ref_count.inc (); }
  int dec () const { return ref_count.dec (); }
  void fini () { ref_count.set_relaxed (HB_REFERENCE_COUNT_POISON_VALUE); }

  bool is_inert () const { return ref_count.get_relaxed () == HB_REFERENCE_COUNT_INERT_VALUE; }
  bool is_valid () const { return ref_count.get_relaxed () > 0; }
};

/* user_data */

struct hb_user_data_array_t
{
  struct hb_user_data_item_t {
    hb_user_data_key_t *key;
    void *data;
    hb_destroy_func_t destroy;

    bool operator == (hb_user_data_key_t *other_key) const { return key == other_key; }
    bool operator == (hb_user_data_item_t &other) const { return key == other.key; }

    void fini () { if (destroy) destroy (data); }
  };

  hb_mutex_t lock;
  hb_lockable_set_t<hb_user_data_item_t, hb_mutex_t> items;

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

  HB_INTERNAL bool set (hb_user_data_key_t *key,
			void *              data,
			hb_destroy_func_t   destroy,
			hb_bool_t           replace);

  HB_INTERNAL void *get (hb_user_data_key_t *key);

  void fini () { items.fini (lock); lock.fini (); }
};

/*
 * Object header
 */

struct hb_object_header_t
{
  hb_reference_count_t ref_count;
  mutable hb_atomic_int_t writable;
  hb_atomic_ptr_t<hb_user_data_array_t> user_data;
};
#define HB_OBJECT_HEADER_STATIC \
	{ \
	  HB_REFERENCE_COUNT_INIT, \
	  HB_ATOMIC_INT_INIT (false), \
	  HB_ATOMIC_PTR_INIT (nullptr) \
	}

/*
 * Object
 */

template <typename Type>
static inline void hb_object_trace (const Type *obj, const char *function)
{
  DEBUG_MSG (OBJECT, (void *) obj,
	     "%s refcount=%d",
	     function,
	     obj ? obj->header.ref_count.get_relaxed () : 0);
}

template <typename Type>
static inline Type *hb_object_create ()
{
  Type *obj = (Type *) calloc (1, sizeof (Type));

  if (unlikely (!obj))
    return obj;

  hb_object_init (obj);
  hb_object_trace (obj, HB_FUNC);
  return obj;
}
template <typename Type>
static inline void hb_object_init (Type *obj)
{
  obj->header.ref_count.init ();
  obj->header.writable.set_relaxed (true);
  obj->header.user_data.init ();
}
template <typename Type>
static inline bool hb_object_is_inert (const Type *obj)
{
  return unlikely (obj->header.ref_count.is_inert ());
}
template <typename Type>
static inline bool hb_object_is_valid (const Type *obj)
{
  return likely (obj->header.ref_count.is_valid ());
}
template <typename Type>
static inline bool hb_object_is_immutable (const Type *obj)
{
  return !obj->header.writable.get_relaxed ();
}
template <typename Type>
static inline void hb_object_make_immutable (const Type *obj)
{
  obj->header.writable.set_relaxed (false);
}
template <typename Type>
static inline Type *hb_object_reference (Type *obj)
{
  hb_object_trace (obj, HB_FUNC);
  if (unlikely (!obj || hb_object_is_inert (obj)))
    return obj;
  assert (hb_object_is_valid (obj));
  obj->header.ref_count.inc ();
  return obj;
}
template <typename Type>
static inline bool hb_object_destroy (Type *obj)
{
  hb_object_trace (obj, HB_FUNC);
  if (unlikely (!obj || hb_object_is_inert (obj)))
    return false;
  assert (hb_object_is_valid (obj));
  if (obj->header.ref_count.dec () != 1)
    return false;

  hb_object_fini (obj);
  return true;
}
template <typename Type>
static inline void hb_object_fini (Type *obj)
{
  obj->header.ref_count.fini (); /* Do this before user_data */
  hb_user_data_array_t *user_data = obj->header.user_data.get ();
  if (user_data)
  {
    user_data->fini ();
    free (user_data);
    user_data = nullptr;
  }
}
template <typename Type>
static inline bool hb_object_set_user_data (Type               *obj,
					    hb_user_data_key_t *key,
					    void *              data,
					    hb_destroy_func_t   destroy,
					    hb_bool_t           replace)
{
  if (unlikely (!obj || hb_object_is_inert (obj)))
    return false;
  assert (hb_object_is_valid (obj));

retry:
  hb_user_data_array_t *user_data = obj->header.user_data.get ();
  if (unlikely (!user_data))
  {
    user_data = (hb_user_data_array_t *) calloc (sizeof (hb_user_data_array_t), 1);
    if (unlikely (!user_data))
      return false;
    user_data->init ();
    if (unlikely (!obj->header.user_data.cmpexch (nullptr, user_data)))
    {
      user_data->fini ();
      free (user_data);
      goto retry;
    }
  }

  return user_data->set (key, data, destroy, replace);
}

template <typename Type>
static inline void *hb_object_get_user_data (Type               *obj,
					     hb_user_data_key_t *key)
{
  if (unlikely (!obj || hb_object_is_inert (obj)))
    return nullptr;
  assert (hb_object_is_valid (obj));
  hb_user_data_array_t *user_data = obj->header.user_data.get ();
  if (!user_data)
    return nullptr;
  return user_data->get (key);
}

#endif /* HB_OBJECT_HH */

repo_language: C

mime_type: text/x-c


text:
/*
 * Copyright © 2019  Adobe Inc.
 * Copyright © 2019  Ebrahim Byagowi
 *
 *  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.
 *
 * Adobe Author(s): Michiharu Ariza
 */

#ifndef HB_OT_VAR_GVAR_TABLE_HH
#define HB_OT_VAR_GVAR_TABLE_HH

#include "hb-open-type.hh"

/*
 * gvar -- Glyph Variation Table
 * https://docs.microsoft.com/en-us/typography/opentype/spec/gvar
 */
#define HB_OT_TAG_gvar HB_TAG('g','v','a','r')

namespace OT {

struct contour_point_t
{
  void init (float x_ = 0.f, float y_ = 0.f, bool is_end_point_ = false)
  { flag = 0; x = x_; y = y_; is_end_point = is_end_point_; }

  void translate (const contour_point_t &p) { x += p.x; y += p.y; }

  uint8_t flag;
  float x, y;
  bool is_end_point;
};

struct contour_point_vector_t : hb_vector_t<contour_point_t>
{
  void extend (const hb_array_t<contour_point_t> &a)
  {
    unsigned int old_len = length;
    resize (old_len + a.length);
    for (unsigned int i = 0; i < a.length; i++)
      (*this)[old_len + i] = a[i];
  }

  void transform (const float (&matrix)[4])
  {
    for (unsigned int i = 0; i < length; i++)
    {
      contour_point_t &p = (*this)[i];
      float x_ = p.x * matrix[0] + p.y * matrix[2];
	   p.y = p.x * matrix[1] + p.y * matrix[3];
      p.x = x_;
    }
  }

  void translate (const contour_point_t& delta)
  {
    for (unsigned int i = 0; i < length; i++)
      (*this)[i].translate (delta);
  }
};

/* https://docs.microsoft.com/en-us/typography/opentype/spec/otvarcommonformats#tuplevariationheader */
struct TupleVariationHeader
{
  unsigned get_size (unsigned axis_count) const
  { return min_size + get_all_tuples (axis_count).get_size (); }

  unsigned get_data_size () const { return varDataSize; }

  const TupleVariationHeader &get_next (unsigned axis_count) const
  { return StructAtOffset<TupleVariationHeader> (this, get_size (axis_count)); }

  float calculate_scalar (const int *coords, unsigned int coord_count,
			  const hb_array_t<const F2DOT14> shared_tuples) const
  {
    hb_array_t<const F2DOT14> peak_tuple;

    if (has_peak ())
      peak_tuple = get_peak_tuple (coord_count);
    else
    {
      unsigned int index = get_index ();
      if (unlikely (index * coord_count >= shared_tuples.length))
	return 0.f;
      peak_tuple = shared_tuples.sub_array (coord_count * index, coord_count);
    }

    hb_array_t<const F2DOT14> start_tuple;
    hb_array_t<const F2DOT14> end_tuple;
    if (has_intermediate ())
    {
      start_tuple = get_start_tuple (coord_count);
      end_tuple = get_end_tuple (coord_count);
    }

    float scalar = 1.f;
    for (unsigned int i = 0; i < coord_count; i++)
    {
      int v = coords[i];
      int peak = peak_tuple[i];
      if (!peak || v == peak) continue;

      if (has_intermediate ())
      {
	int start = start_tuple[i];
	int end = end_tuple[i];
	if (unlikely (start > peak || peak > end ||
		      (start < 0 && end > 0 && peak))) continue;
	if (v < start || v > end) return 0.f;
	if (v < peak)
	{ if (peak != start) scalar *= (float) (v - start) / (peak - start); }
	else
	{ if (peak != end) scalar *= (float) (end - v) / (end - peak); }
      }
      else if (!v || v < hb_min (0, peak) || v > hb_max (0, peak)) return 0.f;
      else
	scalar *= (float) v / peak;
    }
    return scalar;
  }

  bool           has_peak () const { return (tupleIndex & TuppleIndex::EmbeddedPeakTuple); }
  bool   has_intermediate () const { return (tupleIndex & TuppleIndex::IntermediateRegion); }
  bool has_private_points () const { return (tupleIndex & TuppleIndex::PrivatePointNumbers); }
  unsigned int  get_index () const { return (tupleIndex & TuppleIndex::TupleIndexMask); }

  protected:
  struct TuppleIndex : HBUINT16
  {
    enum Flags {
      EmbeddedPeakTuple   = 0x8000u,
      IntermediateRegion  = 0x4000u,
      PrivatePointNumbers = 0x2000u,
      TupleIndexMask      = 0x0FFFu
    };

    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); }
  hb_array_t<const F2DOT14> get_peak_tuple (unsigned axis_count) const
  { return get_all_tuples (axis_count).sub_array (0, axis_count); }
  hb_array_t<const F2DOT14> get_start_tuple (unsigned axis_count) const
  { return get_all_tuples (axis_count).sub_array (has_peak () * axis_count, axis_count); }
  hb_array_t<const F2DOT14> get_end_tuple (unsigned axis_count) const
  { return get_all_tuples (axis_count).sub_array (has_peak () * axis_count + axis_count, axis_count); }

  HBUINT16	varDataSize;	/* The size in bytes of the serialized
				 * data for this tuple variation table. */
  TuppleIndex	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 GlyphVariationData
{
  const TupleVariationHeader &get_tuple_var_header (void) const
  { return StructAfter<TupleVariationHeader> (data); }

  struct tuple_iterator_t
  {
    void init (hb_bytes_t var_data_bytes_, unsigned int axis_count_)
    {
      var_data_bytes = var_data_bytes_;
      var_data = var_data_bytes_.as<GlyphVariationData> ();
      index = 0;
      axis_count = axis_count_;
      current_tuple = &var_data->get_tuple_var_header ();
      data_offset = 0;
    }

    bool get_shared_indices (hb_vector_t<unsigned int> &shared_indices /* OUT */)
    {
      if (var_data->has_shared_point_numbers ())
      {
	const HBUINT8 *base = &(var_data+var_data->data);
	const HBUINT8 *p = base;
	if (!unpack_points (p, shared_indices, var_data_bytes)) return false;
	data_offset = p - base;
      }
      return true;
    }

    bool is_valid () const
    {
      return (index < var_data->tupleVarCount.get_count ()) &&
	     var_data_bytes.check_range (current_tuple, TupleVariationHeader::min_size) &&
	     var_data_bytes.check_range (current_tuple, hb_max (current_tuple->get_data_size (), current_tuple->get_size (axis_count))) &&
	     current_tuple->get_size (axis_count);
    }

    bool move_to_next ()
    {
      data_offset += current_tuple->get_data_size ();
      current_tuple = &current_tuple->get_next (axis_count);
      index++;
      return is_valid ();
    }

    const HBUINT8 *get_serialized_data () const
    { return &(var_data+var_data->data) + data_offset; }

    private:
    const GlyphVariationData *var_data;
    unsigned int index;
    unsigned int axis_count;
    unsigned int data_offset;

    public:
    hb_bytes_t var_data_bytes;
    const TupleVariationHeader *current_tuple;
  };

  static bool get_tuple_iterator (hb_bytes_t var_data_bytes, unsigned axis_count,
				  hb_vector_t<unsigned int> &shared_indices /* OUT */,
				  tuple_iterator_t *iterator /* OUT */)
  {
    iterator->init (var_data_bytes, axis_count);
    if (!iterator->get_shared_indices (shared_indices))
      return false;
    return iterator->is_valid ();
  }

  bool has_shared_point_numbers () const { return tupleVarCount.has_shared_point_numbers (); }

  static bool unpack_points (const HBUINT8 *&p /* IN/OUT */,
			     hb_vector_t<unsigned int> &points /* OUT */,
			     const hb_bytes_t &bytes)
  {
    enum packed_point_flag_t
    {
      POINTS_ARE_WORDS     = 0x80,
      POINT_RUN_COUNT_MASK = 0x7F
    };

    if (unlikely (!bytes.check_range (p))) return false;

    uint16_t count = *p++;
    if (count & POINTS_ARE_WORDS)
    {
      if (unlikely (!bytes.check_range (p))) return false;
      count = ((count & POINT_RUN_COUNT_MASK) << 8) | *p++;
    }
    points.resize (count);

    unsigned int n = 0;
    uint16_t i = 0;
    while (i < count)
    {
      if (unlikely (!bytes.check_range (p))) return false;
      uint16_t j;
      uint8_t control = *p++;
      uint16_t run_count = (control & POINT_RUN_COUNT_MASK) + 1;
      if (control & POINTS_ARE_WORDS)
      {
	for (j = 0; j < run_count && i < count; j++, i++)
	{
	  if (unlikely (!bytes.check_range ((const HBUINT16 *) p)))
	    return false;
	  n += *(const HBUINT16 *)p;
	  points[i] = n;
	  p += HBUINT16::static_size;
	}
      }
      else
      {
	for (j = 0; j < run_count && i < count; j++, i++)
	{
	  if (unlikely (!bytes.check_range (p))) return false;
	  n += *p++;
	  points[i] = n;
	}
      }
      if (j < run_count) return false;
    }
    return true;
  }

  static bool unpack_deltas (const HBUINT8 *&p /* IN/OUT */,
			     hb_vector_t<int> &deltas /* IN/OUT */,
			     const hb_bytes_t &bytes)
  {
    enum packed_delta_flag_t
    {
      DELTAS_ARE_ZERO      = 0x80,
      DELTAS_ARE_WORDS     = 0x40,
      DELTA_RUN_COUNT_MASK = 0x3F
    };

    unsigned int i = 0;
    unsigned int count = deltas.length;
    while (i < count)
    {
      if (unlikely (!bytes.check_range (p))) return false;
      uint8_t control = *p++;
      unsigned int run_count = (control & DELTA_RUN_COUNT_MASK) + 1;
      unsigned int j;
      if (control & DELTAS_ARE_ZERO)
	for (j = 0; j < run_count && i < count; j++, i++)
	  deltas[i] = 0;
      else if (control & DELTAS_ARE_WORDS)
	for (j = 0; j < run_count && i < count; j++, i++)
	{
	  if (unlikely (!bytes.check_range ((const HBUINT16 *) p)))
	    return false;
	  deltas[i] = *(const HBINT16 *) p;
	  p += HBUINT16::static_size;
	}
      else
	for (j = 0; j < run_count && i < count; j++, i++)
	{
	  if (unlikely (!bytes.check_range (p)))
	    return false;
	  deltas[i] = *(const HBINT8 *) p++;
	}
      if (j < run_count)
	return false;
    }
    return true;
  }

  bool has_data () const { return tupleVarCount; }

  protected:
  struct TupleVarCount : HBUINT16
  {
    bool has_shared_point_numbers () const { return ((*this) & SharedPointNumbers); }
    unsigned int get_count () const { return (*this) & CountMask; }

    protected:
    enum Flags
    {
      SharedPointNumbers= 0x8000u,
      CountMask		= 0x0FFFu
    };
    public:
    DEFINE_SIZE_STATIC (2);
  };

  TupleVarCount	tupleVarCount;  /* A packed field. The high 4 bits are flags, and the
				 * low 12 bits are the number of tuple variation tables
				 * for this glyph. The number of tuple variation tables
				 * can be any number between 1 and 4095. */
  OffsetTo<HBUINT8>
		data;		/* Offset from the start of the GlyphVariationData table
				 * to the serialized data. */
  /* TupleVariationHeader tupleVariationHeaders[] *//* Array of tuple variation headers. */
  public:
  DEFINE_SIZE_MIN (4);
};

struct gvar
{
  static constexpr hb_tag_t tableTag = HB_OT_TAG_gvar;

  bool sanitize_shallow (hb_sanitize_context_t *c) const
  {
    TRACE_SANITIZE (this);
    return_trace (c->check_struct (this) && (version.major == 1) &&
		  (glyphCount == c->get_num_glyphs ()) &&
		  sharedTuples.sanitize (c, this, axisCount * sharedTupleCount) &&
		  (is_long_offset () ?
		     c->check_array (get_long_offset_array (), glyphCount+1) :
		     c->check_array (get_short_offset_array (), glyphCount+1)) &&
		  c->check_array (((const HBUINT8*)&(this+dataZ)) + get_offset (0),
				  get_offset (glyphCount) - get_offset (0)));
  }

  /* GlyphVariationData not sanitized here; must be checked while accessing each glyph varation data */
  bool sanitize (hb_sanitize_context_t *c) const
  { return sanitize_shallow (c); }

  bool subset (hb_subset_context_t *c) const
  {
    TRACE_SUBSET (this);

    gvar *out = c->serializer->allocate_min<gvar> ();
    if (unlikely (!out)) return_trace (false);

    out->version.major = 1;
    out->version.minor = 0;
    out->axisCount = axisCount;
    out->sharedTupleCount = sharedTupleCount;

    unsigned int num_glyphs = c->plan->num_output_glyphs ();
    out->glyphCount = num_glyphs;

    unsigned int subset_data_size = 0;
    for (hb_codepoint_t gid = 0; gid < num_glyphs; gid++)
    {
      hb_codepoint_t old_gid;
      if (!c->plan->old_gid_for_new_gid (gid, &old_gid)) continue;
      subset_data_size += get_glyph_var_data_bytes (c->source_blob, old_gid).length;
    }

    bool long_offset = subset_data_size & ~0xFFFFu;
    out->flags = long_offset ? 1 : 0;

    HBUINT8 *subset_offsets = c->serializer->allocate_size<HBUINT8> ((long_offset ? 4 : 2) * (num_glyphs + 1));
    if (!subset_offsets) return_trace (false);

    /* shared tuples */
    if (!sharedTupleCount || !sharedTuples)
      out->sharedTuples = 0;
    else
    {
      unsigned int shared_tuple_size = F2DOT14::static_size * axisCount * sharedTupleCount;
      F2DOT14 *tuples = c->serializer->allocate_size<F2DOT14> (shared_tuple_size);
      if (!tuples) return_trace (false);
      out->sharedTuples = (char *) tuples - (char *) out;
      memcpy (tuples, this+sharedTuples, shared_tuple_size);
    }

    char *subset_data = c->serializer->allocate_size<char> (subset_data_size);
    if (!subset_data) return_trace (false);
    out->dataZ = subset_data - (char *) out;

    unsigned int glyph_offset = 0;
    for (hb_codepoint_t gid = 0; gid < num_glyphs; gid++)
    {
      hb_codepoint_t old_gid;
      hb_bytes_t var_data_bytes = c->plan->old_gid_for_new_gid (gid, &old_gid)
				? get_glyph_var_data_bytes (c->source_blob, old_gid)
				: hb_bytes_t ();

      if (long_offset)
	((HBUINT32 *) subset_offsets)[gid] = glyph_offset;
      else
	((HBUINT16 *) subset_offsets)[gid] = glyph_offset / 2;

      if (var_data_bytes.length > 0)
	memcpy (subset_data, var_data_bytes.arrayZ, var_data_bytes.length);
      subset_data += var_data_bytes.length;
      glyph_offset += var_data_bytes.length;
    }
    if (long_offset)
      ((HBUINT32 *) subset_offsets)[num_glyphs] = glyph_offset;
    else
      ((HBUINT16 *) subset_offsets)[num_glyphs] = glyph_offset / 2;

    return_trace (true);
  }

  protected:
  const hb_bytes_t get_glyph_var_data_bytes (hb_blob_t *blob, hb_codepoint_t glyph) const
  {
    unsigned start_offset = get_offset (glyph);
    unsigned length = get_offset (glyph+1) - start_offset;
    hb_bytes_t var_data = blob->as_bytes ().sub_array (((unsigned) dataZ) + start_offset, length);
    return likely (var_data.length >= GlyphVariationData::min_size) ? var_data : hb_bytes_t ();
  }

  bool is_long_offset () const { return (flags & 1) != 0; }

  unsigned int get_offset (unsigned int i) const
  {
    if (is_long_offset ())
      return get_long_offset_array ()[i];
    else
      return get_short_offset_array ()[i] * 2;
  }

  const HBUINT32 * get_long_offset_array () const { return (const HBUINT32 *) &offsetZ; }
  const HBUINT16 *get_short_offset_array () const { return (const HBUINT16 *) &offsetZ; }

  public:
  struct accelerator_t
  {
    void init (hb_face_t *face)
    { table = hb_sanitize_context_t ().reference_table<gvar> (face); }
    void fini () { table.destroy (); }

    private:
    struct x_getter { static float get (const contour_point_t &p) { return p.x; } };
    struct y_getter { static float get (const contour_point_t &p) { return p.y; } };

    template <typename T>
    static float infer_delta (const hb_array_t<contour_point_t> points,
			      const hb_array_t<contour_point_t> deltas,
			      unsigned int target, unsigned int prev, unsigned int next)
    {
      float target_val = T::get (points[target]);
      float prev_val = T::get (points[prev]);
      float next_val = T::get (points[next]);
      float prev_delta = T::get (deltas[prev]);
      float next_delta = T::get (deltas[next]);

      if (prev_val == next_val)
	return (prev_delta == next_delta) ? prev_delta : 0.f;
      else if (target_val <= hb_min (prev_val, next_val))
	return (prev_val < next_val) ? prev_delta : next_delta;
      else if (target_val >= hb_max (prev_val, next_val))
	return (prev_val > next_val) ? prev_delta : next_delta;

      /* linear interpolation */
      float r = (target_val - prev_val) / (next_val - prev_val);
      return (1.f - r) * prev_delta + r * next_delta;
    }

    static unsigned int next_index (unsigned int i, unsigned int start, unsigned int end)
    { return (i >= end) ? start : (i + 1); }

    public:
    bool apply_deltas_to_points (hb_codepoint_t glyph, hb_font_t *font,
				 const hb_array_t<contour_point_t> points) const
    {
      /* num_coords should exactly match gvar's axisCount due to how GlyphVariationData tuples are aligned */
      if (!font->num_coords || font->num_coords != table->axisCount) return true;

      hb_bytes_t var_data_bytes = table->get_glyph_var_data_bytes (table.get_blob (), glyph);
      if (!var_data_bytes.as<GlyphVariationData> ()->has_data ()) return true;
      hb_vector_t<unsigned int> shared_indices;
      GlyphVariationData::tuple_iterator_t iterator;
      if (!GlyphVariationData::get_tuple_iterator (var_data_bytes, table->axisCount,
					     shared_indices, &iterator))
	return true; /* so isn't applied at all */

      /* Save original points for inferred delta calculation */
      contour_point_vector_t orig_points;
      orig_points.resize (points.length);
      for (unsigned int i = 0; i < orig_points.length; i++)
	orig_points[i] = points[i];

      contour_point_vector_t deltas; /* flag is used to indicate referenced point */
      deltas.resize (points.length);

      hb_vector_t<unsigned> end_points;
      for (unsigned i = 0; i < points.length; ++i)
	if (points[i].is_end_point)
	  end_points.push (i);

      int *coords = font->coords;
      unsigned num_coords = font->num_coords;
      hb_array_t<const F2DOT14> shared_tuples = (table+table->sharedTuples).as_array (table->sharedTupleCount * table->axisCount);
      do
      {
	float scalar = iterator.current_tuple->calculate_scalar (coords, num_coords, shared_tuples);
	if (scalar == 0.f) continue;
	const HBUINT8 *p = iterator.get_serialized_data ();
	unsigned int length = iterator.current_tuple->get_data_size ();
	if (unlikely (!iterator.var_data_bytes.check_range (p, length)))
	  return false;

	hb_bytes_t bytes ((const char *) p, length);
	hb_vector_t<unsigned int> private_indices;
	if (iterator.current_tuple->has_private_points () &&
	    !GlyphVariationData::unpack_points (p, private_indices, bytes))
	  return false;
	const hb_array_t<unsigned int> &indices = private_indices.length ? private_indices : shared_indices;

	bool apply_to_all = (indices.length == 0);
	unsigned int num_deltas = apply_to_all ? points.length : indices.length;
	hb_vector_t<int> x_deltas;
	x_deltas.resize (num_deltas);
	if (!GlyphVariationData::unpack_deltas (p, x_deltas, bytes))
	  return false;
	hb_vector_t<int> y_deltas;
	y_deltas.resize (num_deltas);
	if (!GlyphVariationData::unpack_deltas (p, y_deltas, bytes))
	  return false;

	for (unsigned int i = 0; i < deltas.length; i++)
	  deltas[i].init ();
	for (unsigned int i = 0; i < num_deltas; i++)
	{
	  unsigned int pt_index = apply_to_all ? i : indices[i];
	  deltas[pt_index].flag = 1;	/* this point is referenced, i.e., explicit deltas specified */
	  deltas[pt_index].x += x_deltas[i] * scalar;
	  deltas[pt_index].y += y_deltas[i] * scalar;
	}

	/* infer deltas for unreferenced points */
	unsigned start_point = 0;
	for (unsigned c = 0; c < end_points.length; c++)
	{
	  unsigned end_point = end_points[c];

	  /* 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; i++)
	    if (!deltas[i].flag) 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 (deltas[i].flag && !deltas[j].flag) break;
	    }
	    prev = j = i;
	    for (;;)
	    {
	      i = j;
	      j = next_index (i, start_point, end_point);
	      if (!deltas[i].flag && deltas[j].flag) 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[i].x = infer_delta<x_getter> (orig_points.as_array (), deltas.as_array (), i, prev, next);
	      deltas[i].y = infer_delta<y_getter> (orig_points.as_array (), deltas.as_array (), i, prev, next);
	      if (--unref_count == 0) goto no_more_gaps;
	    }
	  }
no_more_gaps:
	  start_point = end_point + 1;
	}

	/* apply specified / inferred deltas to points */
	for (unsigned int i = 0; i < points.length; i++)
	{
	  points[i].x += (float) roundf (deltas[i].x);
	  points[i].y += (float) roundf (deltas[i].y);
	}
      } while (iterator.move_to_next ());

      return true;
    }

    unsigned int get_axis_count () const { return table->axisCount; }

    private:
    hb_blob_ptr_t<gvar> table;
  };

  protected:
  FixedVersion<>version;	/* Version number of the glyph variations table
				 * Set to 0x00010000u. */
  HBUINT16	axisCount;	/* The number of variation axes for this font. This must be
				 * the same number as axisCount in the 'fvar' table. */
  HBUINT16	sharedTupleCount;
				/* The number of shared tuple records. Shared tuple records
				 * can be referenced within glyph variation data tables for
				 * multiple glyphs, as opposed to other tuple records stored
				 * directly within a glyph variation data table. */
  LNNOffsetTo<UnsizedArrayOf<F2DOT14>>
		sharedTuples;	/* Offset from the start of this table to the shared tuple records.
				 * Array of tuple records shared across all glyph variation data tables. */
  HBUINT16	glyphCount;	/* The number of glyphs in this font. This must match the number of
				 * glyphs stored elsewhere in the font. */
  HBUINT16	flags;		/* Bit-field that gives the format of the offset array that follows.
				 * If bit 0 is clear, the offsets are uint16; if bit 0 is set, the
				 * offsets are uint32. */
  LOffsetTo<GlyphVariationData>
		dataZ;		/* Offset from the start of this table to the array of
				 * GlyphVariationData tables. */
  UnsizedArrayOf<HBUINT8>
		offsetZ;	/* Offsets from the start of the GlyphVariationData array
				 * to each GlyphVariationData table. */
  public:
  DEFINE_SIZE_MIN (20);
};

struct gvar_accelerator_t : gvar::accelerator_t {};

} /* namespace OT */

#endif /* HB_OT_VAR_GVAR_TABLE_HH */


text:
/*
 * Copyright © 2018  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.
 *
 * Google Author(s): Behdad Esfahbod
 */

#ifndef HB_OT_NAME_LANGUAGE_HH
#define HB_OT_NAME_LANGUAGE_HH

#include "hb.hh"

HB_INTERNAL hb_language_t
_hb_ot_name_language_for_ms_code (unsigned int code);

HB_INTERNAL hb_language_t
_hb_ot_name_language_for_mac_code (unsigned int code);

#endif /* HB_OT_NAME_LANGUAGE_HH */


text:
/*
 * Copyright © 2009  Red Hat, Inc.
 * Copyright © 2018  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_BLOB_HH
#define HB_BLOB_HH

#include "hb.hh"

/*
 * hb_blob_t
 */

struct hb_blob_t
{
  void fini_shallow () { destroy_user_data (); }

  void destroy_user_data ()
  {
    if (destroy)
    {
      destroy (user_data);
      user_data = nullptr;
      destroy = nullptr;
    }
  }

  HB_INTERNAL bool try_make_writable ();
  HB_INTERNAL bool try_make_writable_inplace ();
  HB_INTERNAL bool try_make_writable_inplace_unix ();

  hb_bytes_t as_bytes () const { return hb_bytes_t (data, length); }
  template <typename Type>
  const Type* as () const { return as_bytes ().as<Type> (); }

  public:
  hb_object_header_t header;

  const char *data;
  unsigned int length;
  hb_memory_mode_t mode;

  void *user_data;
  hb_destroy_func_t destroy;
};

/*
 * hb_blob_ptr_t
 */

template <typename P>
struct hb_blob_ptr_t
{
  typedef hb_remove_pointer<P> T;

  hb_blob_ptr_t (hb_blob_t *b_ = nullptr) : b (b_) {}
  hb_blob_t * operator = (hb_blob_t *b_) { return b = b_; }
  const T * operator -> () const { return get (); }
  const T & operator * () const  { return *get (); }
  template <typename C> operator const C * () const { return get (); }
  operator const char * () const { return (const char *) get (); }
  const T * get () const { return b->as<T> (); }
  hb_blob_t * get_blob () const { return b.get_raw (); }
  unsigned int get_length () const { return b.get ()->length; }
  void destroy () { hb_blob_destroy (b.get ()); b = nullptr; }

  hb_nonnull_ptr_t<hb_blob_t> b;
};

#endif /* HB_BLOB_HH */


text:
/*
 * Copyright © 2018 Adobe 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.
 *
 * Adobe Author(s): Michiharu Ariza
 */

#ifndef HB_SUBSET_CFF2_HH
#define HB_SUBSET_CFF2_HH

#include "hb.hh"

#include "hb-subset-plan.hh"

HB_INTERNAL bool
hb_subset_cff2 (hb_subset_context_t *c);

#endif /* HB_SUBSET_CFF2_HH */


text:
/*
 * Copyright © 2009  Red Hat, Inc.
 * Copyright © 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_H_IN
#error "Include <hb.h> instead."
#endif

#ifndef HB_SHAPE_H
#define HB_SHAPE_H

#include "hb-common.h"
#include "hb-buffer.h"
#include "hb-font.h"

HB_BEGIN_DECLS

HB_EXTERN void
hb_shape (hb_font_t           *font,
	  hb_buffer_t         *buffer,
	  const hb_feature_t  *features,
	  unsigned int         num_features);

HB_EXTERN hb_bool_t
hb_shape_full (hb_font_t          *font,
	       hb_buffer_t        *buffer,
	       const hb_feature_t *features,
	       unsigned int        num_features,
	       const char * const *shaper_list);

HB_EXTERN const char **
hb_shape_list_shapers (void);

HB_END_DECLS

#endif /* HB_SHAPE_H */


text:
/*
 * Copyright © 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.
 *
 * Google Author(s): Behdad Esfahbod
 */

#ifndef HB_SET_DIGEST_HH
#define HB_SET_DIGEST_HH

#include "hb.hh"

/*
 * The set digests here implement various "filters" that support
 * "approximate member query".  Conceptually these are like Bloom
 * Filter and Quotient Filter, however, much smaller, faster, and
 * designed to fit the requirements of our uses for glyph coverage
 * queries.
 *
 * Our filters are highly accurate if the lookup covers fairly local
 * set of glyphs, but fully flooded and ineffective if coverage is
 * all over the place.
 *
 * The frozen-set can be used instead of a digest, to trade more
 * memory for 100% accuracy, but in practice, that doesn't look like
 * an attractive trade-off.
 */

template <typename mask_t, unsigned int shift>
struct hb_set_digest_lowest_bits_t
{
  static constexpr unsigned mask_bytes = sizeof (mask_t);
  static constexpr unsigned mask_bits = sizeof (mask_t) * 8;
  static constexpr unsigned num_bits = 0
				     + (mask_bytes >= 1 ? 3 : 0)
				     + (mask_bytes >= 2 ? 1 : 0)
				     + (mask_bytes >= 4 ? 1 : 0)
				     + (mask_bytes >= 8 ? 1 : 0)
				     + (mask_bytes >= 16? 1 : 0)
				     + 0;

  static_assert ((shift < sizeof (hb_codepoint_t) * 8), "");
  static_assert ((shift + num_bits <= sizeof (hb_codepoint_t) * 8), "");

  void init () { mask = 0; }

  void add (hb_codepoint_t g) { mask |= mask_for (g); }

  bool add_range (hb_codepoint_t a, hb_codepoint_t b)
  {
    if ((b >> shift) - (a >> shift) >= mask_bits - 1)
      mask = (mask_t) -1;
    else {
      mask_t ma = mask_for (a);
      mask_t mb = mask_for (b);
      mask |= mb + (mb - ma) - (mb < ma);
    }
    return true;
  }

  template <typename T>
  void add_array (const T *array, unsigned int count, unsigned int stride=sizeof(T))
  {
    for (unsigned int i = 0; i < count; i++)
    {
      add (*array);
      array = (const T *) (stride + (const char *) array);
    }
  }
  template <typename T>
  bool add_sorted_array (const T *array, unsigned int count, unsigned int stride=sizeof(T))
  {
    for (unsigned int i = 0; i < count; i++)
    {
      add (*array);
      array = (const T *) (stride + (const char *) array);
    }
    return true;
  }

  bool may_have (hb_codepoint_t g) const
  { return !!(mask & mask_for (g)); }

  private:

  static mask_t mask_for (hb_codepoint_t g)
  { return ((mask_t) 1) << ((g >> shift) & (mask_bits - 1)); }
  mask_t mask;
};

template <typename head_t, typename tail_t>
struct hb_set_digest_combiner_t
{
  void init ()
  {
    head.init ();
    tail.init ();
  }

  void add (hb_codepoint_t g)
  {
    head.add (g);
    tail.add (g);
  }

  bool add_range (hb_codepoint_t a, hb_codepoint_t b)
  {
    head.add_range (a, b);
    tail.add_range (a, b);
    return true;
  }
  template <typename T>
  void add_array (const T *array, unsigned int count, unsigned int stride=sizeof(T))
  {
    head.add_array (array, count, stride);
    tail.add_array (array, count, stride);
  }
  template <typename T>
  bool add_sorted_array (const T *array, unsigned int count, unsigned int stride=sizeof(T))
  {
    head.add_sorted_array (array, count, stride);
    tail.add_sorted_array (array, count, stride);
    return true;
  }

  bool may_have (hb_codepoint_t g) const
  {
    return head.may_have (g) && tail.may_have (g);
  }

  private:
  head_t head;
  tail_t tail;
};

/*
 * hb_set_digest_t
 *
 * This is a combination of digests that performs "best".
 * There is not much science to this: it's a result of intuition
 * and testing.
 */
typedef hb_set_digest_combiner_t
<
  hb_set_digest_lowest_bits_t<unsigned long, 4>,
  hb_set_digest_combiner_t
  <
    hb_set_digest_lowest_bits_t<unsigned long, 0>,
    hb_set_digest_lowest_bits_t<unsigned long, 9>
  >
> hb_set_digest_t;

#endif /* HB_SET_DIGEST_HH */


text:
#!/usr/bin/env python3

import io, sys

if len (sys.argv) != 4:
	print ("""usage: ./gen-indic-table.py IndicSyllabicCategory.txt IndicPositionalCategory.txt Blocks.txt

Input files, as of Unicode 12:
* https://unicode.org/Public/UCD/latest/ucd/IndicSyllabicCategory.txt
* https://unicode.org/Public/UCD/latest/ucd/IndicPositionalCategory.txt
* https://unicode.org/Public/UCD/latest/ucd/Blocks.txt""", file=sys.stderr)
	sys.exit (1)

ALLOWED_SINGLES = [0x00A0, 0x25CC]
ALLOWED_BLOCKS = [
	'Basic Latin',
	'Latin-1 Supplement',
	'Devanagari',
	'Bengali',
	'Gurmukhi',
	'Gujarati',
	'Oriya',
	'Tamil',
	'Telugu',
	'Kannada',
	'Malayalam',
	'Sinhala',
	'Myanmar',
	'Khmer',
	'Vedic Extensions',
	'General Punctuation',
	'Superscripts and Subscripts',
	'Devanagari Extended',
	'Myanmar Extended-B',
	'Myanmar Extended-A',
]

files = [io.open (x, encoding='utf-8') for x in sys.argv[1:]]

headers = [[f.readline () for i in range (2)] for f in files]

data = [{} for f in files]
values = [{} for f in files]
for i, f in enumerate (files):
	for line in f:

		j = line.find ('#')
		if j >= 0:
			line = line[:j]

		fields = [x.strip () for x in line.split (';')]
		if len (fields) == 1:
			continue

		uu = fields[0].split ('..')
		start = int (uu[0], 16)
		if len (uu) == 1:
			end = start
		else:
			end = int (uu[1], 16)

		t = fields[1]

		for u in range (start, end + 1):
			data[i][u] = t
		values[i][t] = values[i].get (t, 0) + end - start + 1

# Merge data into one dict:
defaults = ('Other', 'Not_Applicable', 'No_Block')
for i,v in enumerate (defaults):
	values[i][v] = values[i].get (v, 0) + 1
combined = {}
for i,d in enumerate (data):
	for u,v in d.items ():
		if i == 2 and not u in combined:
			continue
		if not u in combined:
			combined[u] = list (defaults)
		combined[u][i] = v
combined = {k:v for k,v in combined.items() if k in ALLOWED_SINGLES or v[2] in ALLOWED_BLOCKS}
data = combined
del combined
num = len (data)

# Move the outliers NO-BREAK SPACE and DOTTED CIRCLE out
singles = {}
for u in ALLOWED_SINGLES:
	singles[u] = data[u]
	del data[u]

print ("/* == Start of generated table == */")
print ("/*")
print (" * The following table is generated by running:")
print (" *")
print (" *   ./gen-indic-table.py IndicSyllabicCategory.txt IndicPositionalCategory.txt Blocks.txt")
print (" *")
print (" * on files with these headers:")
print (" *")
for h in headers:
	for l in h:
		print (" * %s" % (l.strip()))
print (" */")
print ()
print ('#include "hb.hh"')
print ()
print ('#ifndef HB_NO_OT_SHAPE')
print ()
print ('#include "hb-ot-shape-complex-indic.hh"')
print ()

# Shorten values
short = [{
	"Bindu":		'Bi',
	"Cantillation_Mark":	'Ca',
	"Joiner":		'ZWJ',
	"Non_Joiner":		'ZWNJ',
	"Number":		'Nd',
	"Visarga":		'Vs',
	"Vowel":		'Vo',
	"Vowel_Dependent":	'M',
	"Consonant_Prefixed":	'CPrf',
	"Other":		'x',
},{
	"Not_Applicable":	'x',
}]
all_shorts = [{},{}]

# Add some of the values, to make them more readable, and to avoid duplicates

for i in range (2):
	for v,s in short[i].items ():
		all_shorts[i][s] = v

what = ["INDIC_SYLLABIC_CATEGORY", "INDIC_MATRA_CATEGORY"]
what_short = ["ISC", "IMC"]
print ('#pragma GCC diagnostic push')
print ('#pragma GCC diagnostic ignored "-Wunused-macros"')
cat_defs = []
for i in range (2):
	vv = sorted (values[i].keys ())
	for v in vv:
		v_no_and = v.replace ('_And_', '_')
		if v in short[i]:
			s = short[i][v]
		else:
			s = ''.join ([c for c in v_no_and if ord ('A') <= ord (c) <= ord ('Z')])
			if s in all_shorts[i]:
				raise Exception ("Duplicate short value alias", v, all_shorts[i][s])
			all_shorts[i][s] = v
			short[i][v] = s
		cat_defs.append ((what_short[i] + '_' + s, what[i] + '_' + v.upper (), str (values[i][v]), v))

maxlen_s = max ([len (c[0]) for c in cat_defs])
maxlen_l = max ([len (c[1]) for c in cat_defs])
maxlen_n = max ([len (c[2]) for c in cat_defs])
for s in what_short:
	print ()
	for c in [c for c in cat_defs if s in c[0]]:
		print ("#define %s %s /* %s chars; %s */" %
			(c[0].ljust (maxlen_s), c[1].ljust (maxlen_l), c[2].rjust (maxlen_n), c[3]))
print ()
print ('#pragma GCC diagnostic pop')
print ()
print ("#define _(S,M) INDIC_COMBINE_CATEGORIES (ISC_##S, IMC_##M)")
print ()
print ()

total = 0
used = 0
last_block = None
def print_block (block, start, end, data):
	global total, used, last_block
	if block and block != last_block:
		print ()
		print ()
		print ("  /* %s */" % block)
	num = 0
	assert start % 8 == 0
	assert (end+1) % 8 == 0
	for u in range (start, end+1):
		if u % 8 == 0:
			print ()
			print ("  /* %04X */" % u, end="")
		if u in data:
			num += 1
		d = data.get (u, defaults)
		print ("%9s" % ("_(%s,%s)," % (short[0][d[0]], short[1][d[1]])), end="")

	total += end - start + 1
	used += num
	if block:
		last_block = block

uu = sorted (data.keys ())

last = -100000
num = 0
offset = 0
starts = []
ends = []
print ("static const INDIC_TABLE_ELEMENT_TYPE indic_table[] = {")
for u in uu:
	if u <= last:
		continue
	block = data[u][2]

	start = u//8*8
	end = start+1
	while end in uu and block == data[end][2]:
		end += 1
	end = (end-1)//8*8 + 7

	if start != last + 1:
		if start - last <= 1+16*3:
			print_block (None, last+1, start-1, data)
			last = start-1
		else:
			if last >= 0:
				ends.append (last + 1)
				offset += ends[-1] - starts[-1]
			print ()
			print ()
			print ("#define indic_offset_0x%04xu %d" % (start, offset))
			starts.append (start)

	print_block (block, start, end, data)
	last = end
ends.append (last + 1)
offset += ends[-1] - starts[-1]
print ()
print ()
occupancy = used * 100. / total
page_bits = 12
print ("}; /* Table items: %d; occupancy: %d%% */" % (offset, occupancy))
print ()
print ("INDIC_TABLE_ELEMENT_TYPE")
print ("hb_indic_get_categories (hb_codepoint_t u)")
print ("{")
print ("  switch (u >> %d)" % page_bits)
print ("  {")
pages = set ([u>>page_bits for u in starts+ends+list (singles.keys ())])
for p in sorted(pages):
	print ("    case 0x%0Xu:" % p)
	for u,d in singles.items ():
		if p != u>>page_bits: continue
		print ("      if (unlikely (u == 0x%04Xu)) return _(%s,%s);" % (u, short[0][d[0]], short[1][d[1]]))
	for (start,end) in zip (starts, ends):
		if p not in [start>>page_bits, end>>page_bits]: continue
		offset = "indic_offset_0x%04xu" % start
		print ("      if (hb_in_range<hb_codepoint_t> (u, 0x%04Xu, 0x%04Xu)) return indic_table[u - 0x%04Xu + %s];" % (start, end-1, start, offset))
	print ("      break;")
	print ("")
print ("    default:")
print ("      break;")
print ("  }")
print ("  return _(x,x);")
print ("}")
print ()
print ("#undef _")
for i in range (2):
	print ()
	vv = sorted (values[i].keys ())
	for v in vv:
		print ("#undef %s_%s" %
			(what_short[i], short[i][v]))
print ()
print ('#endif')
print ()
print ("/* == End of generated table == */")

# Maintain at least 30% occupancy in the table */
if occupancy < 30:
	raise Exception ("Table too sparse, please investigate: ", occupancy)


text:
/*
 * Copyright © 2013  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.
 *
 * Google Author(s): Behdad Esfahbod
 */

#ifndef HB_OT_LAYOUT_JSTF_TABLE_HH
#define HB_OT_LAYOUT_JSTF_TABLE_HH

#include "hb-open-type.hh"
#include "hb-ot-layout-gpos-table.hh"

namespace OT {

/*
 * JstfModList -- Justification Modification List Tables
 */

typedef IndexArray JstfModList;

/*
 * JstfMax -- Justification Maximum Table
 */

typedef OffsetListOf<PosLookup> JstfMax;

/*
 * JstfPriority -- Justification Priority Table
 */

struct JstfPriority
{
  bool sanitize (hb_sanitize_context_t *c) const
  {
    TRACE_SANITIZE (this);
    return_trace (c->check_struct (this) &&
		  shrinkageEnableGSUB.sanitize (c, this) &&
		  shrinkageDisableGSUB.sanitize (c, this) &&
		  shrinkageEnableGPOS.sanitize (c, this) &&
		  shrinkageDisableGPOS.sanitize (c, this) &&
		  shrinkageJstfMax.sanitize (c, this) &&
		  extensionEnableGSUB.sanitize (c, this) &&
		  extensionDisableGSUB.sanitize (c, this) &&
		  extensionEnableGPOS.sanitize (c, this) &&
		  extensionDisableGPOS.sanitize (c, this) &&
		  extensionJstfMax.sanitize (c, this));
  }

  protected:
  OffsetTo<JstfModList>
		shrinkageEnableGSUB;	/* Offset to Shrinkage Enable GSUB
					 * JstfModList table--from beginning of
					 * JstfPriority table--may be NULL */
  OffsetTo<JstfModList>
		shrinkageDisableGSUB;	/* Offset to Shrinkage Disable GSUB
					 * JstfModList table--from beginning of
					 * JstfPriority table--may be NULL */
  OffsetTo<JstfModList>
		shrinkageEnableGPOS;	/* Offset to Shrinkage Enable GPOS
					 * JstfModList table--from beginning of
					 * JstfPriority table--may be NULL */
  OffsetTo<JstfModList>
		shrinkageDisableGPOS;	/* Offset to Shrinkage Disable GPOS
					 * JstfModList table--from beginning of
					 * JstfPriority table--may be NULL */
  OffsetTo<JstfMax>
		shrinkageJstfMax;	/* Offset to Shrinkage JstfMax table--
					 * from beginning of JstfPriority table
					 * --may be NULL */
  OffsetTo<JstfModList>
		extensionEnableGSUB;	/* Offset to Extension Enable GSUB
					 * JstfModList table--from beginning of
					 * JstfPriority table--may be NULL */
  OffsetTo<JstfModList>
		extensionDisableGSUB;	/* Offset to Extension Disable GSUB
					 * JstfModList table--from beginning of
					 * JstfPriority table--may be NULL */
  OffsetTo<JstfModList>
		extensionEnableGPOS;	/* Offset to Extension Enable GPOS
					 * JstfModList table--from beginning of
					 * JstfPriority table--may be NULL */
  OffsetTo<JstfModList>
		extensionDisableGPOS;	/* Offset to Extension Disable GPOS
					 * JstfModList table--from beginning of
					 * JstfPriority table--may be NULL */
  OffsetTo<JstfMax>
		extensionJstfMax;	/* Offset to Extension JstfMax table--
					 * from beginning of JstfPriority table
					 * --may be NULL */

  public:
  DEFINE_SIZE_STATIC (20);
};

/*
 * JstfLangSys -- Justification Language System Table
 */

struct JstfLangSys : OffsetListOf<JstfPriority>
{
  bool sanitize (hb_sanitize_context_t *c,
		 const Record_sanitize_closure_t * = nullptr) const
  {
    TRACE_SANITIZE (this);
    return_trace (OffsetListOf<JstfPriority>::sanitize (c));
  }
};

/*
 * ExtenderGlyphs -- Extender Glyph Table
 */

typedef SortedArrayOf<HBGlyphID> ExtenderGlyphs;

/*
 * JstfScript -- The Justification Table
 */

struct JstfScript
{
  unsigned int get_lang_sys_count () const
  { return langSys.len; }
  const Tag& get_lang_sys_tag (unsigned int i) const
  { return langSys.get_tag (i); }
  unsigned int get_lang_sys_tags (unsigned int start_offset,
				  unsigned int *lang_sys_count /* IN/OUT */,
				  hb_tag_t     *lang_sys_tags /* OUT */) const
  { return langSys.get_tags (start_offset, lang_sys_count, lang_sys_tags); }
  const JstfLangSys& get_lang_sys (unsigned int i) const
  {
    if (i == Index::NOT_FOUND_INDEX) return get_default_lang_sys ();
    return this+langSys[i].offset;
  }
  bool find_lang_sys_index (hb_tag_t tag, unsigned int *index) const
  { return langSys.find_index (tag, index); }

  bool has_default_lang_sys () const               { return defaultLangSys != 0; }
  const JstfLangSys& get_default_lang_sys () const { return this+defaultLangSys; }

  bool sanitize (hb_sanitize_context_t *c,
		 const Record_sanitize_closure_t * = nullptr) const
  {
    TRACE_SANITIZE (this);
    return_trace (extenderGlyphs.sanitize (c, this) &&
		  defaultLangSys.sanitize (c, this) &&
		  langSys.sanitize (c, this));
  }

  protected:
  OffsetTo<ExtenderGlyphs>
		extenderGlyphs;	/* Offset to ExtenderGlyph table--from beginning
				 * of JstfScript table-may be NULL */
  OffsetTo<JstfLangSys>
		defaultLangSys;	/* Offset to DefaultJstfLangSys table--from
				 * beginning of JstfScript table--may be Null */
  RecordArrayOf<JstfLangSys>
		langSys;	/* Array of JstfLangSysRecords--listed
				 * alphabetically by LangSysTag */
  public:
  DEFINE_SIZE_ARRAY (6, langSys);
};

/*
 * JSTF -- Justification
 * https://docs.microsoft.com/en-us/typography/opentype/spec/jstf
 */

struct JSTF
{
  static constexpr hb_tag_t tableTag = HB_OT_TAG_JSTF;

  unsigned int get_script_count () const
  { return scriptList.len; }
  const Tag& get_script_tag (unsigned int i) const
  { return scriptList.get_tag (i); }
  unsigned int get_script_tags (unsigned int start_offset,
				unsigned int *script_count /* IN/OUT */,
				hb_tag_t     *script_tags /* OUT */) const
  { return scriptList.get_tags (start_offset, script_count, script_tags); }
  const JstfScript& get_script (unsigned int i) const
  { return this+scriptList[i].offset; }
  bool find_script_index (hb_tag_t tag, unsigned int *index) const
  { return scriptList.find_index (tag, index); }

  bool sanitize (hb_sanitize_context_t *c) const
  {
    TRACE_SANITIZE (this);
    return_trace (version.sanitize (c) &&
		  likely (version.major == 1) &&
		  scriptList.sanitize (c, this));
  }

  protected:
  FixedVersion<>version;	/* Version of the JSTF table--initially set
				 * to 0x00010000u */
  RecordArrayOf<JstfScript>
		scriptList;	/* Array of JstfScripts--listed
				 * alphabetically by ScriptTag */
  public:
  DEFINE_SIZE_ARRAY (6, scriptList);
};

} /* namespace OT */

#endif /* HB_OT_LAYOUT_JSTF_TABLE_HH */


text:
/*
 * 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.
 *
 * Google Author(s): Behdad Esfahbod
 */

#include "hb.hh"

#ifndef HB_NO_OT_SHAPE

#include "hb-ot-shape-complex-khmer.hh"
#include "hb-ot-layout.hh"

/*
 * Khmer shaper.
 */

static const hb_ot_map_feature_t
khmer_features[] =
{
  /*
   * Basic features.
   * These features are applied in order, one at a time, after reordering.
   */
  {HB_TAG('p','r','e','f'), F_MANUAL_JOINERS},
  {HB_TAG('b','l','w','f'), F_MANUAL_JOINERS},
  {HB_TAG('a','b','v','f'), F_MANUAL_JOINERS},
  {HB_TAG('p','s','t','f'), F_MANUAL_JOINERS},
  {HB_TAG('c','f','a','r'), F_MANUAL_JOINERS},
  /*
   * Other features.
   * These features are applied all at once after clearing syllables.
   */
  {HB_TAG('p','r','e','s'), F_GLOBAL_MANUAL_JOINERS},
  {HB_TAG('a','b','v','s'), F_GLOBAL_MANUAL_JOINERS},
  {HB_TAG('b','l','w','s'), F_GLOBAL_MANUAL_JOINERS},
  {HB_TAG('p','s','t','s'), F_GLOBAL_MANUAL_JOINERS},
};

/*
 * Must be in the same order as the khmer_features array.
 */
enum {
  KHMER_PREF,
  KHMER_BLWF,
  KHMER_ABVF,
  KHMER_PSTF,
  KHMER_CFAR,

  _KHMER_PRES,
  _KHMER_ABVS,
  _KHMER_BLWS,
  _KHMER_PSTS,

  KHMER_NUM_FEATURES,
  KHMER_BASIC_FEATURES = _KHMER_PRES, /* Don't forget to update this! */
};

static void
setup_syllables_khmer (const hb_ot_shape_plan_t *plan,
		       hb_font_t *font,
		       hb_buffer_t *buffer);
static void
reorder_khmer (const hb_ot_shape_plan_t *plan,
	       hb_font_t *font,
	       hb_buffer_t *buffer);

static void
collect_features_khmer (hb_ot_shape_planner_t *plan)
{
  hb_ot_map_builder_t *map = &plan->map;

  /* Do this before any lookups have been applied. */
  map->add_gsub_pause (setup_syllables_khmer);
  map->add_gsub_pause (reorder_khmer);

  /* Testing suggests that Uniscribe does NOT pause between basic
   * features.  Test with KhmerUI.ttf and the following three
   * sequences:
   *
   *   U+1789,U+17BC
   *   U+1789,U+17D2,U+1789
   *   U+1789,U+17D2,U+1789,U+17BC
   *
   * https://github.com/harfbuzz/harfbuzz/issues/974
   */
  map->enable_feature (HB_TAG('l','o','c','l'));
  map->enable_feature (HB_TAG('c','c','m','p'));

  unsigned int i = 0;
  for (; i < KHMER_BASIC_FEATURES; i++)
    map->add_feature (khmer_features[i]);

  map->add_gsub_pause (_hb_clear_syllables);

  for (; i < KHMER_NUM_FEATURES; i++)
    map->add_feature (khmer_features[i]);
}

static void
override_features_khmer (hb_ot_shape_planner_t *plan)
{
  hb_ot_map_builder_t *map = &plan->map;

  /* Khmer spec has 'clig' as part of required shaping features:
   * "Apply feature 'clig' to form ligatures that are desired for
   * typographical correctness.", hence in overrides... */
  map->enable_feature (HB_TAG('c','l','i','g'));

  /* Uniscribe does not apply 'kern' in Khmer. */
  if (hb_options ().uniscribe_bug_compatible)
  {
    map->disable_feature (HB_TAG('k','e','r','n'));
  }

  map->disable_feature (HB_TAG('l','i','g','a'));
}

struct khmer_shape_plan_t
{
  bool get_virama_glyph (hb_font_t *font, hb_codepoint_t *pglyph) const
  {
    hb_codepoint_t glyph = virama_glyph;
    if (unlikely (virama_glyph == (hb_codepoint_t) -1))
    {
      if (!font->get_nominal_glyph (0x17D2u, &glyph))
	glyph = 0;
      /* Technically speaking, the spec says we should apply 'locl' to virama too.
       * Maybe one day... */

      /* Our get_nominal_glyph() function needs a font, so we can't get the virama glyph
       * during shape planning...  Instead, overwrite it here.  It's safe.  Don't worry! */
      virama_glyph = glyph;
    }

    *pglyph = glyph;
    return glyph != 0;
  }

  mutable hb_codepoint_t virama_glyph;

  hb_indic_would_substitute_feature_t pref;

  hb_mask_t mask_array[KHMER_NUM_FEATURES];
};

static void *
data_create_khmer (const hb_ot_shape_plan_t *plan)
{
  khmer_shape_plan_t *khmer_plan = (khmer_shape_plan_t *) calloc (1, sizeof (khmer_shape_plan_t));
  if (unlikely (!khmer_plan))
    return nullptr;

  khmer_plan->virama_glyph = (hb_codepoint_t) -1;

  khmer_plan->pref.init (&plan->map, HB_TAG('p','r','e','f'), true);

  for (unsigned int i = 0; i < ARRAY_LENGTH (khmer_plan->mask_array); i++)
    khmer_plan->mask_array[i] = (khmer_features[i].flags & F_GLOBAL) ?
				 0 : plan->map.get_1_mask (khmer_features[i].tag);

  return khmer_plan;
}

static void
data_destroy_khmer (void *data)
{
  free (data);
}

enum khmer_syllable_type_t {
  khmer_consonant_syllable,
  khmer_broken_cluster,
  khmer_non_khmer_cluster,
};

#include "hb-ot-shape-complex-khmer-machine.hh"

static void
setup_masks_khmer (const hb_ot_shape_plan_t *plan HB_UNUSED,
		   hb_buffer_t              *buffer,
		   hb_font_t                *font HB_UNUSED)
{
  HB_BUFFER_ALLOCATE_VAR (buffer, khmer_category);

  /* We cannot setup masks here.  We save information about characters
   * and setup masks later on in a pause-callback. */

  unsigned int count = buffer->len;
  hb_glyph_info_t *info = buffer->info;
  for (unsigned int i = 0; i < count; i++)
    set_khmer_properties (info[i]);
}

static void
setup_syllables_khmer (const hb_ot_shape_plan_t *plan HB_UNUSED,
		       hb_font_t *font HB_UNUSED,
		       hb_buffer_t *buffer)
{
  find_syllables_khmer (buffer);
  foreach_syllable (buffer, start, end)
    buffer->unsafe_to_break (start, end);
}

/* Rules from:
 * https://docs.microsoft.com/en-us/typography/script-development/devanagari */

static void
reorder_consonant_syllable (const hb_ot_shape_plan_t *plan,
			    hb_face_t *face HB_UNUSED,
			    hb_buffer_t *buffer,
			    unsigned int start, unsigned int end)
{
  const khmer_shape_plan_t *khmer_plan = (const khmer_shape_plan_t *) plan->data;
  hb_glyph_info_t *info = buffer->info;

  /* Setup masks. */
  {
    /* Post-base */
    hb_mask_t mask = khmer_plan->mask_array[KHMER_BLWF] |
		     khmer_plan->mask_array[KHMER_ABVF] |
		     khmer_plan->mask_array[KHMER_PSTF];
    for (unsigned int i = start + 1; i < end; i++)
      info[i].mask  |= mask;
  }

  unsigned int num_coengs = 0;
  for (unsigned int i = start + 1; i < end; i++)
  {
    /* """
     * When a COENG + (Cons | IndV) combination are found (and subscript count
     * is less than two) the character combination is handled according to the
     * subscript type of the character following the COENG.
     *
     * ...
     *
     * Subscript Type 2 - The COENG + RO characters are reordered to immediately
     * before the base glyph. Then the COENG + RO characters are assigned to have
     * the 'pref' OpenType feature applied to them.
     * """
     */
    if (info[i].khmer_category() == OT_Coeng && num_coengs <= 2 && i + 1 < end)
    {
      num_coengs++;

      if (info[i + 1].khmer_category() == OT_Ra)
      {
	for (unsigned int j = 0; j < 2; j++)
	  info[i + j].mask |= khmer_plan->mask_array[KHMER_PREF];

	/* Move the Coeng,Ro sequence to the start. */
	buffer->merge_clusters (start, i + 2);
	hb_glyph_info_t t0 = info[i];
	hb_glyph_info_t t1 = info[i + 1];
	memmove (&info[start + 2], &info[start], (i - start) * sizeof (info[0]));
	info[start] = t0;
	info[start + 1] = t1;

	/* Mark the subsequent stuff with 'cfar'.  Used in Khmer.
	 * Read the feature spec.
	 * This allows distinguishing the following cases with MS Khmer fonts:
	 * U+1784,U+17D2,U+179A,U+17D2,U+1782
	 * U+1784,U+17D2,U+1782,U+17D2,U+179A
	 */
	if (khmer_plan->mask_array[KHMER_CFAR])
	  for (unsigned int j = i + 2; j < end; j++)
	    info[j].mask |= khmer_plan->mask_array[KHMER_CFAR];

	num_coengs = 2; /* Done. */
      }
    }

    /* Reorder left matra piece. */
    else if (info[i].khmer_category() == OT_VPre)
    {
      /* Move to the start. */
      buffer->merge_clusters (start, i + 1);
      hb_glyph_info_t t = info[i];
      memmove (&info[start + 1], &info[start], (i - start) * sizeof (info[0]));
      info[start] = t;
    }
  }
}

static void
reorder_syllable_khmer (const hb_ot_shape_plan_t *plan,
			hb_face_t *face,
			hb_buffer_t *buffer,
			unsigned int start, unsigned int end)
{
  khmer_syllable_type_t syllable_type = (khmer_syllable_type_t) (buffer->info[start].syllable() & 0x0F);
  switch (syllable_type)
  {
    case khmer_broken_cluster: /* We already inserted dotted-circles, so just call the consonant_syllable. */
    case khmer_consonant_syllable:
     reorder_consonant_syllable (plan, face, buffer, start, end);
     break;

    case khmer_non_khmer_cluster:
      break;
  }
}

static inline void
insert_dotted_circles_khmer (const hb_ot_shape_plan_t *plan HB_UNUSED,
			     hb_font_t *font,
			     hb_buffer_t *buffer)
{
  if (unlikely (buffer->flags & HB_BUFFER_FLAG_DO_NOT_INSERT_DOTTED_CIRCLE))
    return;

  /* Note: This loop is extra overhead, but should not be measurable.
   * TODO Use a buffer scratch flag to remove the loop. */
  bool has_broken_syllables = false;
  unsigned int count = buffer->len;
  hb_glyph_info_t *info = buffer->info;
  for (unsigned int i = 0; i < count; i++)
    if ((info[i].syllable() & 0x0F) == khmer_broken_cluster)
    {
      has_broken_syllables = true;
      break;
    }
  if (likely (!has_broken_syllables))
    return;

  hb_codepoint_t dottedcircle_glyph;
  if (!font->get_nominal_glyph (0x25CCu, &dottedcircle_glyph))
    return;

  hb_glyph_info_t dottedcircle = {0};
  dottedcircle.codepoint = 0x25CCu;
  set_khmer_properties (dottedcircle);
  dottedcircle.codepoint = dottedcircle_glyph;

  buffer->clear_output ();

  buffer->idx = 0;
  unsigned int last_syllable = 0;
  while (buffer->idx < buffer->len && buffer->successful)
  {
    unsigned int syllable = buffer->cur().syllable();
    khmer_syllable_type_t syllable_type = (khmer_syllable_type_t) (syllable & 0x0F);
    if (unlikely (last_syllable != syllable && syllable_type == khmer_broken_cluster))
    {
      last_syllable = syllable;

      hb_glyph_info_t ginfo = dottedcircle;
      ginfo.cluster = buffer->cur().cluster;
      ginfo.mask = buffer->cur().mask;
      ginfo.syllable() = buffer->cur().syllable();

      /* Insert dottedcircle after possible Repha. */
      while (buffer->idx < buffer->len && buffer->successful &&
	     last_syllable == buffer->cur().syllable() &&
	     buffer->cur().khmer_category() == OT_Repha)
	buffer->next_glyph ();

      buffer->output_info (ginfo);
    }
    else
      buffer->next_glyph ();
  }
  buffer->swap_buffers ();
}

static void
reorder_khmer (const hb_ot_shape_plan_t *plan,
	       hb_font_t *font,
	       hb_buffer_t *buffer)
{
  insert_dotted_circles_khmer (plan, font, buffer);

  foreach_syllable (buffer, start, end)
    reorder_syllable_khmer (plan, font->face, buffer, start, end);

  HB_BUFFER_DEALLOCATE_VAR (buffer, khmer_category);
}

static bool
decompose_khmer (const hb_ot_shape_normalize_context_t *c,
		 hb_codepoint_t  ab,
		 hb_codepoint_t *a,
		 hb_codepoint_t *b)
{
  switch (ab)
  {
    /*
     * Decompose split matras that don't have Unicode decompositions.
     */

    /* Khmer */
    case 0x17BEu  : *a = 0x17C1u; *b= 0x17BEu; return true;
    case 0x17BFu  : *a = 0x17C1u; *b= 0x17BFu; return true;
    case 0x17C0u  : *a = 0x17C1u; *b= 0x17C0u; return true;
    case 0x17C4u  : *a = 0x17C1u; *b= 0x17C4u; return true;
    case 0x17C5u  : *a = 0x17C1u; *b= 0x17C5u; return true;
  }

  return (bool) c->unicode->decompose (ab, a, b);
}

static bool
compose_khmer (const hb_ot_shape_normalize_context_t *c,
	       hb_codepoint_t  a,
	       hb_codepoint_t  b,
	       hb_codepoint_t *ab)
{
  /* Avoid recomposing split matras. */
  if (HB_UNICODE_GENERAL_CATEGORY_IS_MARK (c->unicode->general_category (a)))
    return false;

  return (bool) c->unicode->compose (a, b, ab);
}

const hb_ot_complex_shaper_t _hb_ot_complex_shaper_khmer =
{
  collect_features_khmer,
  override_features_khmer,
  data_create_khmer,
  data_destroy_khmer,
  nullptr, /* preprocess_text */
  nullptr, /* postprocess_glyphs */
  HB_OT_SHAPE_NORMALIZATION_MODE_COMPOSED_DIACRITICS_NO_SHORT_CIRCUIT,
  decompose_khmer,
  compose_khmer,
  setup_masks_khmer,
  HB_TAG_NONE, /* gpos_tag */
  nullptr, /* reorder_marks */
  HB_OT_SHAPE_ZERO_WIDTH_MARKS_NONE,
  false, /* fallback_position */
};

#endif


text:
/*
 * Copyright © 2012,2017  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.
 *
 * Google Author(s): Behdad Esfahbod
 */

#ifndef HB_SET_HH
#define HB_SET_HH

#include "hb.hh"
#include "hb-machinery.hh"

/*
 * hb_set_t
 */

/* TODO Keep a free-list so we can free pages that are completely zeroed.  At that
 * point maybe also use a sentinel value for "all-1" pages? */

struct hb_set_t
{
  HB_DELETE_COPY_ASSIGN (hb_set_t);
  hb_set_t ()  { init (); }
  ~hb_set_t () { fini (); }

  struct page_map_t
  {
    int cmp (const page_map_t &o) const { return (int) o.major - (int) major; }

    uint32_t major;
    uint32_t index;
  };

  struct page_t
  {
    void init0 () { v.clear (); }
    void init1 () { v.clear (0xFF); }

    unsigned int len () const
    { return ARRAY_LENGTH_CONST (v); }

    bool is_empty () const
    {
      for (unsigned int i = 0; i < len (); i++)
	if (v[i])
	  return false;
      return true;
    }

    void add (hb_codepoint_t g) { elt (g) |= mask (g); }
    void del (hb_codepoint_t g) { elt (g) &= ~mask (g); }
    bool get (hb_codepoint_t g) const { return elt (g) & mask (g); }

    void add_range (hb_codepoint_t a, hb_codepoint_t b)
    {
      elt_t *la = &elt (a);
      elt_t *lb = &elt (b);
      if (la == lb)
	*la |= (mask (b) << 1) - mask(a);
      else
      {
	*la |= ~(mask (a) - 1);
	la++;

	memset (la, 0xff, (char *) lb - (char *) la);

	*lb |= ((mask (b) << 1) - 1);
      }
    }

    void del_range (hb_codepoint_t a, hb_codepoint_t b)
    {
      elt_t *la = &elt (a);
      elt_t *lb = &elt (b);
      if (la == lb)
	*la &= ~((mask (b) << 1) - mask(a));
      else
      {
	*la &= mask (a) - 1;
	la++;

	memset (la, 0, (char *) lb - (char *) la);

	*lb &= ~((mask (b) << 1) - 1);
      }
    }

    bool is_equal (const page_t *other) const
    {
      return 0 == hb_memcmp (&v, &other->v, sizeof (v));
    }

    unsigned int get_population () const
    {
      unsigned int pop = 0;
      for (unsigned int i = 0; i < len (); i++)
	pop += hb_popcount (v[i]);
      return pop;
    }

    bool next (hb_codepoint_t *codepoint) const
    {
      unsigned int m = (*codepoint + 1) & MASK;
      if (!m)
      {
	*codepoint = INVALID;
	return false;
      }
      unsigned int i = m / ELT_BITS;
      unsigned int j = m & ELT_MASK;

      const elt_t vv = v[i] & ~((elt_t (1) << j) - 1);
      for (const elt_t *p = &vv; i < len (); p = &v[++i])
	if (*p)
	{
	  *codepoint = i * ELT_BITS + elt_get_min (*p);
	  return true;
	}

      *codepoint = INVALID;
      return false;
    }
    bool previous (hb_codepoint_t *codepoint) const
    {
      unsigned int m = (*codepoint - 1) & MASK;
      if (m == MASK)
      {
	*codepoint = INVALID;
	return false;
      }
      unsigned int i = m / ELT_BITS;
      unsigned int j = m & ELT_MASK;

      /* Fancy mask to avoid shifting by elt_t bitsize, which is undefined. */
      const elt_t mask = j < 8 * sizeof (elt_t) - 1 ?
			 ((elt_t (1) << (j + 1)) - 1) :
			 (elt_t) -1;
      const elt_t vv = v[i] & mask;
      const elt_t *p = &vv;
      while (true)
      {
	if (*p)
	{
	  *codepoint = i * ELT_BITS + elt_get_max (*p);
	  return true;
	}
	if ((int) i <= 0) break;
	p = &v[--i];
      }

      *codepoint = INVALID;
      return false;
    }
    hb_codepoint_t get_min () const
    {
      for (unsigned int i = 0; i < len (); i++)
	if (v[i])
	  return i * ELT_BITS + elt_get_min (v[i]);
      return INVALID;
    }
    hb_codepoint_t get_max () const
    {
      for (int i = len () - 1; i >= 0; i--)
	if (v[i])
	  return i * ELT_BITS + elt_get_max (v[i]);
      return 0;
    }

    typedef unsigned long long elt_t;
    static constexpr unsigned PAGE_BITS = 512;
    static_assert ((PAGE_BITS & ((PAGE_BITS) - 1)) == 0, "");

    static unsigned int elt_get_min (const elt_t &elt) { return hb_ctz (elt); }
    static unsigned int elt_get_max (const elt_t &elt) { return hb_bit_storage (elt) - 1; }

    typedef hb_vector_size_t<elt_t, PAGE_BITS / 8> vector_t;

    static constexpr unsigned ELT_BITS = sizeof (elt_t) * 8;
    static constexpr unsigned ELT_MASK = ELT_BITS - 1;
    static constexpr unsigned BITS = sizeof (vector_t) * 8;
    static constexpr unsigned MASK = BITS - 1;
    static_assert ((unsigned) PAGE_BITS == (unsigned) BITS, "");

    elt_t &elt (hb_codepoint_t g) { return v[(g & MASK) / ELT_BITS]; }
    elt_t const &elt (hb_codepoint_t g) const { return v[(g & MASK) / ELT_BITS]; }
    elt_t mask (hb_codepoint_t g) const { return elt_t (1) << (g & ELT_MASK); }

    vector_t v;
  };
  static_assert (page_t::PAGE_BITS == sizeof (page_t) * 8, "");

  hb_object_header_t header;
  bool successful; /* Allocations successful */
  mutable unsigned int population;
  hb_sorted_vector_t<page_map_t> page_map;
  hb_vector_t<page_t> pages;

  void init_shallow ()
  {
    successful = true;
    population = 0;
    page_map.init ();
    pages.init ();
  }
  void init ()
  {
    hb_object_init (this);
    init_shallow ();
  }
  void fini_shallow ()
  {
    population = 0;
    page_map.fini ();
    pages.fini ();
  }
  void fini ()
  {
    hb_object_fini (this);
    fini_shallow ();
  }

  bool in_error () const { return !successful; }

  bool resize (unsigned int count)
  {
    if (unlikely (!successful)) return false;
    if (!pages.resize (count) || !page_map.resize (count))
    {
      pages.resize (page_map.length);
      successful = false;
      return false;
    }
    return true;
  }

  void reset ()
  {
    if (unlikely (hb_object_is_immutable (this)))
      return;
    clear ();
    successful = true;
  }

  void clear ()
  {
    if (unlikely (hb_object_is_immutable (this)))
      return;
    population = 0;
    page_map.resize (0);
    pages.resize (0);
  }
  bool is_empty () const
  {
    unsigned int count = pages.length;
    for (unsigned int i = 0; i < count; i++)
      if (!pages[i].is_empty ())
	return false;
    return true;
  }

  void dirty () { population = UINT_MAX; }

  void add (hb_codepoint_t g)
  {
    if (unlikely (!successful)) return;
    if (unlikely (g == INVALID)) return;
    dirty ();
    page_t *page = page_for_insert (g); if (unlikely (!page)) return;
    page->add (g);
  }
  bool add_range (hb_codepoint_t a, hb_codepoint_t b)
  {
    if (unlikely (!successful)) return true; /* https://github.com/harfbuzz/harfbuzz/issues/657 */
    if (unlikely (a > b || a == INVALID || b == INVALID)) return false;
    dirty ();
    unsigned int ma = get_major (a);
    unsigned int mb = get_major (b);
    if (ma == mb)
    {
      page_t *page = page_for_insert (a); if (unlikely (!page)) return false;
      page->add_range (a, b);
    }
    else
    {
      page_t *page = page_for_insert (a); if (unlikely (!page)) return false;
      page->add_range (a, major_start (ma + 1) - 1);

      for (unsigned int m = ma + 1; m < mb; m++)
      {
	page = page_for_insert (major_start (m)); if (unlikely (!page)) return false;
	page->init1 ();
      }

      page = page_for_insert (b); if (unlikely (!page)) return false;
      page->add_range (major_start (mb), b);
    }
    return true;
  }

  template <typename T>
  void add_array (const T *array, unsigned int count, unsigned int stride=sizeof(T))
  {
    if (unlikely (!successful)) return;
    if (!count) return;
    dirty ();
    hb_codepoint_t g = *array;
    while (count)
    {
      unsigned int m = get_major (g);
      page_t *page = page_for_insert (g); if (unlikely (!page)) return;
      unsigned int start = major_start (m);
      unsigned int end = major_start (m + 1);
      do
      {
	page->add (g);

	array = &StructAtOffsetUnaligned<T> (array, stride);
	count--;
      }
      while (count && (g = *array, start <= g && g < end));
    }
  }

  /* Might return false if array looks unsorted.
   * Used for faster rejection of corrupt data. */
  template <typename T>
  bool add_sorted_array (const T *array, unsigned int count, unsigned int stride=sizeof(T))
  {
    if (unlikely (!successful)) return true; /* https://github.com/harfbuzz/harfbuzz/issues/657 */
    if (!count) return true;
    dirty ();
    hb_codepoint_t g = *array;
    hb_codepoint_t last_g = g;
    while (count)
    {
      unsigned int m = get_major (g);
      page_t *page = page_for_insert (g); if (unlikely (!page)) return false;
      unsigned int end = major_start (m + 1);
      do
      {
	/* If we try harder we can change the following comparison to <=;
	 * Not sure if it's worth it. */
	if (g < last_g) return false;
	last_g = g;
	page->add (g);

	array = (const T *) ((const char *) array + stride);
	count--;
      }
      while (count && (g = *array, g < end));
    }
    return true;
  }

  void del (hb_codepoint_t g)
  {
    /* TODO perform op even if !successful. */
    if (unlikely (!successful)) return;
    page_t *page = page_for (g);
    if (!page)
      return;
    dirty ();
    page->del (g);
  }

  private:
  void del_pages (int ds, int de)
  {
    if (ds <= de)
    {
      unsigned int write_index = 0;
      for (unsigned int i = 0; i < page_map.length; i++)
      {
	int m = (int) page_map[i].major;
	if (m < ds || de < m)
	  page_map[write_index++] = page_map[i];
      }
      compact (write_index);
      resize (write_index);
    }
  }

  public:
  void del_range (hb_codepoint_t a, hb_codepoint_t b)
  {
    /* TODO perform op even if !successful. */
    if (unlikely (!successful)) return;
    if (unlikely (a > b || a == INVALID || b == INVALID)) return;
    dirty ();
    unsigned int ma = get_major (a);
    unsigned int mb = get_major (b);
    /* Delete pages from ds through de if ds <= de. */
    int ds = (a == major_start (ma))? (int) ma: (int) (ma + 1);
    int de = (b + 1 == major_start (mb + 1))? (int) mb: ((int) mb - 1);
    if (ds > de || (int) ma < ds)
    {
      page_t *page = page_for (a);
      if (page)
      {
	if (ma == mb)
	  page->del_range (a, b);
	else
	  page->del_range (a, major_start (ma + 1) - 1);
      }
    }
    if (de < (int) mb && ma != mb)
    {
      page_t *page = page_for (b);
      if (page)
	page->del_range (major_start (mb), b);
    }
    del_pages (ds, de);
  }

  bool get (hb_codepoint_t g) const
  {
    const page_t *page = page_for (g);
    if (!page)
      return false;
    return page->get (g);
  }

  /* Has interface. */
  static constexpr bool SENTINEL = false;
  typedef bool value_t;
  value_t operator [] (hb_codepoint_t k) const { return get (k); }
  bool has (hb_codepoint_t k) const { return (*this)[k] != SENTINEL; }
  /* Predicate. */
  bool operator () (hb_codepoint_t k) const { return has (k); }

  /* Sink interface. */
  hb_set_t& operator << (hb_codepoint_t v)
  { add (v); return *this; }
  hb_set_t& operator << (const hb_pair_t<hb_codepoint_t, hb_codepoint_t>& range)
  { add_range (range.first, range.second); return *this; }

  bool intersects (hb_codepoint_t first, hb_codepoint_t last) const
  {
    hb_codepoint_t c = first - 1;
    return next (&c) && c <= last;
  }
  void set (const hb_set_t *other)
  {
    if (unlikely (!successful)) return;
    unsigned int count = other->pages.length;
    if (!resize (count))
      return;
    population = other->population;
    memcpy ((void *) pages, (const void *) other->pages, count * pages.item_size);
    memcpy ((void *) page_map, (const void *) other->page_map, count * page_map.item_size);
  }

  bool is_equal (const hb_set_t *other) const
  {
    if (get_population () != other->get_population ())
      return false;

    unsigned int na = pages.length;
    unsigned int nb = other->pages.length;

    unsigned int a = 0, b = 0;
    for (; a < na && b < nb; )
    {
      if (page_at (a).is_empty ()) { a++; continue; }
      if (other->page_at (b).is_empty ()) { b++; continue; }
      if (page_map[a].major != other->page_map[b].major ||
	  !page_at (a).is_equal (&other->page_at (b)))
	return false;
      a++;
      b++;
    }
    for (; a < na; a++)
      if (!page_at (a).is_empty ()) { return false; }
    for (; b < nb; b++)
      if (!other->page_at (b).is_empty ()) { return false; }

    return true;
  }

  bool is_subset (const hb_set_t *larger_set) const
  {
    if (get_population () > larger_set->get_population ())
      return false;

    /* TODO Optimize to use pages. */
    hb_codepoint_t c = INVALID;
    while (next (&c))
      if (!larger_set->has (c))
	return false;

    return true;
  }

  void compact (unsigned int length)
  {
    hb_vector_t<uint32_t> old_index_to_page_map_index;
    old_index_to_page_map_index.resize(pages.length);
    for (uint32_t i = 0; i < old_index_to_page_map_index.length; i++)
      old_index_to_page_map_index[i] = 0xFFFFFFFF;

    for (uint32_t i = 0; i < length; i++)
      old_index_to_page_map_index[page_map[i].index] =  i;

    compact_pages (old_index_to_page_map_index);
  }

  void compact_pages (const hb_vector_t<uint32_t>& old_index_to_page_map_index)
  {
    unsigned int write_index = 0;
    for (unsigned int i = 0; i < pages.length; i++)
    {
      if (old_index_to_page_map_index[i] == 0xFFFFFFFF) continue;

      if (write_index < i)
	pages[write_index] = pages[i];

      page_map[old_index_to_page_map_index[i]].index = write_index;
      write_index++;
    }
  }

  template <typename Op>
  void process (const Op& op, const hb_set_t *other)
  {
    if (unlikely (!successful)) return;

    dirty ();

    unsigned int na = pages.length;
    unsigned int nb = other->pages.length;
    unsigned int next_page = na;

    unsigned int count = 0, newCount = 0;
    unsigned int a = 0, b = 0;
    unsigned int write_index = 0;
    for (; a < na && b < nb; )
    {
      if (page_map[a].major == other->page_map[b].major)
      {
	if (!Op::passthru_left)
	{
	  // Move page_map entries that we're keeping from the left side set
	  // to the front of the page_map vector. This isn't necessary if
	  // passthru_left is set since no left side pages will be removed
	  // in that case.
	  if (write_index < a)
	    page_map[write_index] = page_map[a];
	  write_index++;
	}

	count++;
	a++;
	b++;
      }
      else if (page_map[a].major < other->page_map[b].major)
      {
	if (Op::passthru_left)
	  count++;
	a++;
      }
      else
      {
	if (Op::passthru_right)
	  count++;
	b++;
      }
    }
    if (Op::passthru_left)
      count += na - a;
    if (Op::passthru_right)
      count += nb - b;

    if (!Op::passthru_left)
    {
      na  = write_index;
      next_page = write_index;
      compact (write_index);
    }

    if (!resize (count))
      return;

    newCount = count;

    /* Process in-place backward. */
    a = na;
    b = nb;
    for (; a && b; )
    {
      if (page_map[a - 1].major == other->page_map[b - 1].major)
      {
	a--;
	b--;
	count--;
	page_map[count] = page_map[a];
	page_at (count).v = op (page_at (a).v, other->page_at (b).v);
      }
      else if (page_map[a - 1].major > other->page_map[b - 1].major)
      {
	a--;
	if (Op::passthru_left)
	{
	  count--;
	  page_map[count] = page_map[a];
	}
      }
      else
      {
	b--;
	if (Op::passthru_right)
	{
	  count--;
	  page_map[count].major = other->page_map[b].major;
	  page_map[count].index = next_page++;
	  page_at (count).v = other->page_at (b).v;
	}
      }
    }
    if (Op::passthru_left)
      while (a)
      {
	a--;
	count--;
	page_map[count] = page_map [a];
      }
    if (Op::passthru_right)
      while (b)
      {
	b--;
	count--;
	page_map[count].major = other->page_map[b].major;
	page_map[count].index = next_page++;
	page_at (count).v = other->page_at (b).v;
      }
    assert (!count);
    if (pages.length > newCount)
      resize (newCount);
  }

  void union_ (const hb_set_t *other)
  {
    process (hb_bitwise_or, other);
  }
  void intersect (const hb_set_t *other)
  {
    process (hb_bitwise_and, other);
  }
  void subtract (const hb_set_t *other)
  {
    process (hb_bitwise_sub, other);
  }
  void symmetric_difference (const hb_set_t *other)
  {
    process (hb_bitwise_xor, other);
  }
  bool next (hb_codepoint_t *codepoint) const
  {
    if (unlikely (*codepoint == INVALID)) {
      *codepoint = get_min ();
      return *codepoint != INVALID;
    }

    page_map_t map = {get_major (*codepoint), 0};
    unsigned int i;
    page_map.bfind (map, &i, HB_BFIND_NOT_FOUND_STORE_CLOSEST);
    if (i < page_map.length && page_map[i].major == map.major)
    {
      if (pages[page_map[i].index].next (codepoint))
      {
	*codepoint += page_map[i].major * page_t::PAGE_BITS;
	return true;
      }
      i++;
    }
    for (; i < page_map.length; i++)
    {
      hb_codepoint_t m = pages[page_map[i].index].get_min ();
      if (m != INVALID)
      {
	*codepoint = page_map[i].major * page_t::PAGE_BITS + m;
	return true;
      }
    }
    *codepoint = INVALID;
    return false;
  }
  bool previous (hb_codepoint_t *codepoint) const
  {
    if (unlikely (*codepoint == INVALID)) {
      *codepoint = get_max ();
      return *codepoint != INVALID;
    }

    page_map_t map = {get_major (*codepoint), 0};
    unsigned int i;
    page_map.bfind (map, &i, HB_BFIND_NOT_FOUND_STORE_CLOSEST);
    if (i < page_map.length && page_map[i].major == map.major)
    {
      if (pages[page_map[i].index].previous (codepoint))
      {
	*codepoint += page_map[i].major * page_t::PAGE_BITS;
	return true;
      }
    }
    i--;
    for (; (int) i >= 0; i--)
    {
      hb_codepoint_t m = pages[page_map[i].index].get_max ();
      if (m != INVALID)
      {
	*codepoint = page_map[i].major * page_t::PAGE_BITS + m;
	return true;
      }
    }
    *codepoint = INVALID;
    return false;
  }
  bool next_range (hb_codepoint_t *first, hb_codepoint_t *last) const
  {
    hb_codepoint_t i;

    i = *last;
    if (!next (&i))
    {
      *last = *first = INVALID;
      return false;
    }

    /* TODO Speed up. */
    *last = *first = i;
    while (next (&i) && i == *last + 1)
      (*last)++;

    return true;
  }
  bool previous_range (hb_codepoint_t *first, hb_codepoint_t *last) const
  {
    hb_codepoint_t i;

    i = *first;
    if (!previous (&i))
    {
      *last = *first = INVALID;
      return false;
    }

    /* TODO Speed up. */
    *last = *first = i;
    while (previous (&i) && i == *first - 1)
      (*first)--;

    return true;
  }

  unsigned int get_population () const
  {
    if (population != UINT_MAX)
      return population;

    unsigned int pop = 0;
    unsigned int count = pages.length;
    for (unsigned int i = 0; i < count; i++)
      pop += pages[i].get_population ();

    population = pop;
    return pop;
  }
  hb_codepoint_t get_min () const
  {
    unsigned int count = pages.length;
    for (unsigned int i = 0; i < count; i++)
      if (!page_at (i).is_empty ())
	return page_map[i].major * page_t::PAGE_BITS + page_at (i).get_min ();
    return INVALID;
  }
  hb_codepoint_t get_max () const
  {
    unsigned int count = pages.length;
    for (int i = count - 1; i >= 0; i++)
      if (!page_at (i).is_empty ())
	return page_map[(unsigned) i].major * page_t::PAGE_BITS + page_at (i).get_max ();
    return INVALID;
  }

  static constexpr hb_codepoint_t INVALID = HB_SET_VALUE_INVALID;

  /*
   * Iterator implementation.
   */
  struct iter_t : hb_iter_with_fallback_t<iter_t, hb_codepoint_t>
  {
    static constexpr bool is_sorted_iterator = true;
    iter_t (const hb_set_t &s_ = Null (hb_set_t),
	    bool init = true) : s (&s_), v (INVALID), l(0)
    {
      if (init)
      {
	l = s->get_population () + 1;
	__next__ ();
      }
    }

    typedef hb_codepoint_t __item_t__;
    hb_codepoint_t __item__ () const { return v; }
    bool __more__ () const { return v != INVALID; }
    void __next__ () { s->next (&v); if (l) l--; }
    void __prev__ () { s->previous (&v); }
    unsigned __len__ () const { return l; }
    iter_t end () const { return iter_t (*s, false); }
    bool operator != (const iter_t& o) const
    { return s != o.s || v != o.v; }

    protected:
    const hb_set_t *s;
    hb_codepoint_t v;
    unsigned l;
  };
  iter_t iter () const { return iter_t (*this); }
  operator iter_t () const { return iter (); }

  protected:

  page_t *page_for_insert (hb_codepoint_t g)
  {
    page_map_t map = {get_major (g), pages.length};
    unsigned int i;
    if (!page_map.bfind (map, &i, HB_BFIND_NOT_FOUND_STORE_CLOSEST))
    {
      if (!resize (pages.length + 1))
	return nullptr;

      pages[map.index].init0 ();
      memmove (page_map + i + 1,
	       page_map + i,
	       (page_map.length - 1 - i) * page_map.item_size);
      page_map[i] = map;
    }
    return &pages[page_map[i].index];
  }
  page_t *page_for (hb_codepoint_t g)
  {
    page_map_t key = {get_major (g)};
    const page_map_t *found = page_map.bsearch (key);
    if (found)
      return &pages[found->index];
    return nullptr;
  }
  const page_t *page_for (hb_codepoint_t g) const
  {
    page_map_t key = {get_major (g)};
    const page_map_t *found = page_map.bsearch (key);
    if (found)
      return &pages[found->index];
    return nullptr;
  }
  page_t &page_at (unsigned int i) { return pages[page_map[i].index]; }
  const page_t &page_at (unsigned int i) const { return pages[page_map[i].index]; }
  unsigned int get_major (hb_codepoint_t g) const { return g / page_t::PAGE_BITS; }
  hb_codepoint_t major_start (unsigned int major) const { return major * page_t::PAGE_BITS; }
};

#endif /* HB_SET_HH */