Adding upstream version 1:115.7.0.upstream/1%115.7.0upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 464 insertions, 0 deletions

diff --git a/gfx/harfbuzz/src/hb-subset-instancer-solver.cc b/gfx/harfbuzz/src/hb-subset-instancer-solver.cc
new file mode 100644
index 0000000000..7a2735c529
--- /dev/null
+++ b/gfx/harfbuzz/src/hb-subset-instancer-solver.cc
@@ -0,0 +1,464 @@
+/*
+ * Copyright © 2023  Behdad Esfahbod
+ *
+ *  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.
+ */
+
+#include "hb.hh"
+
+/* This file is a straight port of the following:
+ *
+ * https://github.com/fonttools/fonttools/blob/f73220816264fc383b8a75f2146e8d69e455d398/Lib/fontTools/varLib/instancer/solver.py
+ *
+ * Where that file returns None for a triple, we return Triple{}.
+ * This should be safe.
+ */
+
+constexpr static float EPSILON = 1.f / (1 << 14);
+constexpr static float MAX_F2DOT14 = float (0x7FFF) / (1 << 14);
+
+struct Triple {
+
+  Triple () :
+    minimum (0.f), middle (0.f), maximum (0.f) {}
+
+  Triple (float minimum_, float middle_, float maximum_) :
+    minimum (minimum_), middle (middle_), maximum (maximum_) {}
+
+  bool operator == (const Triple &o) const
+  {
+    return minimum == o.minimum &&
+	   middle  == o.middle  &&
+	   maximum == o.maximum;
+  }
+
+  float minimum;
+  float middle;
+  float maximum;
+};
+
+static inline Triple _reverse_negate(const Triple &v)
+{ return {-v.maximum, -v.middle, -v.minimum}; }
+
+
+static inline float supportScalar (float coord, const Triple &tent)
+{
+  /* Copied from VarRegionAxis::evaluate() */
+  float start = tent.minimum, peak = tent.middle, end = tent.maximum;
+
+  if (unlikely (start > peak || peak > end))
+    return 1.;
+  if (unlikely (start < 0 && end > 0 && peak != 0))
+    return 1.;
+
+  if (peak == 0 || coord == peak)
+    return 1.;
+
+  if (coord <= start || end <= coord)
+    return 0.;
+
+  /* Interpolate */
+  if (coord < peak)
+    return (coord - start) / (peak - start);
+  else
+    return  (end - coord) / (end - peak);
+}
+
+
+using result_item_t = hb_pair_t<float, Triple>;
+using result_t = hb_vector_t<result_item_t>;
+
+static inline result_t
+_solve (Triple tent, Triple axisLimit, bool negative = false)
+{
+  float axisMin = axisLimit.minimum;
+  float axisDef = axisLimit.middle;
+  float axisMax = axisLimit.maximum;
+  float lower = tent.minimum;
+  float peak  = tent.middle;
+  float upper = tent.maximum;
+
+  // Mirror the problem such that axisDef <= peak
+  if (axisDef > peak)
+  {
+    result_t vec = _solve (_reverse_negate (tent),
+			   _reverse_negate (axisLimit),
+			   !negative);
+
+    for (auto &p : vec)
+      p = hb_pair (p.first, _reverse_negate (p.second));
+
+    return vec;
+  }
+  // axisDef <= peak
+
+  /* case 1: The whole deltaset falls outside the new limit; we can drop it
+   *
+   *                                          peak
+   *  1.........................................o..........
+   *                                           / \
+   *                                          /   \
+   *                                         /     \
+   *                                        /       \
+   *  0---|-----------|----------|-------- o         o----1
+   *    axisMin     axisDef    axisMax   lower     upper
+   */
+  if (axisMax <= lower && axisMax < peak)
+      return result_t{};  // No overlap
+
+  /* case 2: Only the peak and outermost bound fall outside the new limit;
+   * we keep the deltaset, update peak and outermost bound and scale deltas
+   * by the scalar value for the restricted axis at the new limit, and solve
+   * recursively.
+   *
+   *                                  |peak
+   *  1...............................|.o..........
+   *                                  |/ \
+   *                                  /   \
+   *                                 /|    \
+   *                                / |     \
+   *  0--------------------------- o  |      o----1
+   *                           lower  |      upper
+   *                                  |
+   *                                axisMax
+   *
+   * Convert to:
+   *
+   *  1............................................
+   *                                  |
+   *                                  o peak
+   *                                 /|
+   *                                /x|
+   *  0--------------------------- o  o upper ----1
+   *                           lower  |
+   *                                  |
+   *                                axisMax
+   */
+  if (axisMax < peak)
+  {
+    float mult = supportScalar (axisMax, tent);
+    tent = Triple{lower, axisMax, axisMax};
+
+    result_t vec = _solve (tent, axisLimit);
+
+    for (auto &p : vec)
+      p = hb_pair (p.first * mult, p.second);
+
+    return vec;
+  }
+
+  // lower <= axisDef <= peak <= axisMax
+
+  float gain = supportScalar (axisDef, tent);
+  result_t out {hb_pair (gain, Triple{})};
+
+  // First, the positive side
+
+  // outGain is the scalar of axisMax at the tent.
+  float outGain = supportScalar (axisMax, tent);
+
+  /* Case 3a: Gain is more than outGain. The tent down-slope crosses
+   * the axis into negative. We have to split it into multiples.
+   *
+   *                      | peak  |
+   *  1...................|.o.....|..............
+   *                      |/x\_   |
+   *  gain................+....+_.|..............
+   *                     /|    |y\|
+   *  ................../.|....|..+_......outGain
+   *                   /  |    |  | \
+   *  0---|-----------o   |    |  |  o----------1
+   *    axisMin    lower  |    |  |   upper
+   *                      |    |  |
+   *                axisDef    |  axisMax
+   *                           |
+   *                      crossing
+   */
+  if (gain > outGain)
+  {
+    // Crossing point on the axis.
+    float crossing = peak + ((1 - gain) * (upper - peak) / (1 - outGain));
+
+    Triple loc{peak, peak, crossing};
+    float scalar = 1.f;
+
+    // The part before the crossing point.
+    out.push (hb_pair (scalar - gain, loc));
+
+    /* The part after the crossing point may use one or two tents,
+     * depending on whether upper is before axisMax or not, in one
+     * case we need to keep it down to eternity.
+     *
+     * Case 3a1, similar to case 1neg; just one tent needed, as in
+     * the drawing above.
+     */
+    if (upper >= axisMax)
+    {
+      Triple loc {crossing, axisMax, axisMax};
+      float scalar = supportScalar (axisMax, tent);
+
+      out.push (hb_pair (scalar - gain, loc));
+    }
+
+    /* Case 3a2: Similar to case 2neg; two tents needed, to keep
+     * down to eternity.
+     *
+     *                      | peak             |
+     *  1...................|.o................|...
+     *                      |/ \_              |
+     *  gain................+....+_............|...
+     *                     /|    | \xxxxxxxxxxy|
+     *                    / |    |  \_xxxxxyyyy|
+     *                   /  |    |    \xxyyyyyy|
+     *  0---|-----------o   |    |     o-------|--1
+     *    axisMin    lower  |    |      upper  |
+     *                      |    |             |
+     *                axisDef    |             axisMax
+     *                           |
+     *                      crossing
+     */
+    else
+    {
+      // A tent's peak cannot fall on axis default. Nudge it.
+      if (upper == axisDef)
+	upper += EPSILON;
+
+      // Downslope.
+      Triple loc1 {crossing, upper, axisMax};
+      float scalar1 = 0.f;
+
+      // Eternity justify.
+      Triple loc2 {upper, axisMax, axisMax};
+      float scalar2 = 1.f; // supportScalar({"tag": axisMax}, {"tag": tent})
+
+      out.push (hb_pair (scalar1 - gain, loc1));
+      out.push (hb_pair (scalar2 - gain, loc2));
+    }
+  }
+
+  /* Case 3: Outermost limit still fits within F2Dot14 bounds;
+   * we keep deltas as is and only scale the axes bounds. Deltas beyond -1.0
+   * or +1.0 will never be applied as implementations must clamp to that range.
+   *
+   * A second tent is needed for cases when gain is positive, though we add it
+   * unconditionally and it will be dropped because scalar ends up 0.
+   *
+   * TODO: See if we can just move upper closer to adjust the slope, instead of
+   * second tent.
+   *
+   *            |           peak |
+   *  1.........|............o...|..................
+   *            |           /x\  |
+   *            |          /xxx\ |
+   *            |         /xxxxx\|
+   *            |        /xxxxxxx+
+   *            |       /xxxxxxxx|\
+   *  0---|-----|------oxxxxxxxxx|xo---------------1
+   *    axisMin |  lower         | upper
+   *            |                |
+   *          axisDef          axisMax
+   */
+  else if (axisDef + (axisMax - axisDef) * 2 >= upper)
+  {
+    if (!negative && axisDef + (axisMax - axisDef) * MAX_F2DOT14 < upper)
+    {
+      // we clamp +2.0 to the max F2Dot14 (~1.99994) for convenience
+      upper = axisDef + (axisMax - axisDef) * MAX_F2DOT14;
+      assert (peak < upper);
+    }
+
+    // Special-case if peak is at axisMax.
+    if (axisMax == peak)
+	upper = peak;
+
+    Triple loc1 {hb_max (axisDef, lower), peak, upper};
+    float scalar1 = 1.f;
+
+    Triple loc2 {peak, upper, upper};
+    float scalar2 = 0.f;
+
+    // Don't add a dirac delta!
+    if (axisDef < upper)
+	out.push (hb_pair (scalar1 - gain, loc1));
+    if (peak < upper)
+	out.push (hb_pair (scalar2 - gain, loc2));
+  }
+
+  /* Case 4: New limit doesn't fit; we need to chop into two tents,
+   * because the shape of a triangle with part of one side cut off
+   * cannot be represented as a triangle itself.
+   *
+   *            |   peak |
+   *  1.........|......o.|...................
+   *            |     /x\|
+   *            |    |xxy|\_
+   *            |   /xxxy|  \_
+   *            |  |xxxxy|    \_
+   *            |  /xxxxy|      \_
+   *  0---|-----|-oxxxxxx|        o----------1
+   *    axisMin | lower  |        upper
+   *            |        |
+   *          axisDef  axisMax
+   */
+  else
+  {
+    Triple loc1 {hb_max (axisDef, lower), peak, axisMax};
+    float scalar1 = 1.f;
+
+    Triple loc2 {peak, axisMax, axisMax};
+    float scalar2 = supportScalar (axisMax, tent);
+
+    out.push (hb_pair (scalar1 - gain, loc1));
+    // Don't add a dirac delta!
+    if (peak < axisMax)
+      out.push (hb_pair (scalar2 - gain, loc2));
+  }
+
+  /* Now, the negative side
+   *
+   * Case 1neg: Lower extends beyond axisMin: we chop. Simple.
+   *
+   *                     |   |peak
+   *  1..................|...|.o.................
+   *                     |   |/ \
+   *  gain...............|...+...\...............
+   *                     |x_/|    \
+   *                     |/  |     \
+   *                   _/|   |      \
+   *  0---------------o  |   |       o----------1
+   *              lower  |   |       upper
+   *                     |   |
+   *               axisMin   axisDef
+   */
+  if (lower <= axisMin)
+  {
+    Triple loc {axisMin, axisMin, axisDef};
+    float scalar = supportScalar (axisMin, tent);
+
+    out.push (hb_pair (scalar - gain, loc));
+  }
+
+  /* Case 2neg: Lower is betwen axisMin and axisDef: we add two
+   * tents to keep it down all the way to eternity.
+   *
+   *      |               |peak
+   *  1...|...............|.o.................
+   *      |               |/ \
+   *  gain|...............+...\...............
+   *      |yxxxxxxxxxxxxx/|    \
+   *      |yyyyyyxxxxxxx/ |     \
+   *      |yyyyyyyyyyyx/  |      \
+   *  0---|-----------o   |       o----------1
+   *    axisMin    lower  |       upper
+   *                      |
+   *                    axisDef
+   */
+  else
+  {
+    // A tent's peak cannot fall on axis default. Nudge it.
+    if (lower == axisDef)
+      lower -= EPSILON;
+
+    // Downslope.
+    Triple loc1 {axisMin, lower, axisDef};
+    float scalar1 = 0.f;
+
+    // Eternity justify.
+    Triple loc2 {axisMin, axisMin, lower};
+    float scalar2 = 0.f;
+
+    out.push (hb_pair (scalar1 - gain, loc1));
+    out.push (hb_pair (scalar2 - gain, loc2));
+  }
+
+  return out;
+}
+
+/* Normalizes value based on a min/default/max triple. */
+static inline float normalizeValue (float v, const Triple &triple, bool extrapolate = false)
+{
+  /*
+  >>> normalizeValue(400, (100, 400, 900))
+  0.0
+  >>> normalizeValue(100, (100, 400, 900))
+  -1.0
+  >>> normalizeValue(650, (100, 400, 900))
+  0.5
+  */
+  float lower = triple.minimum, def = triple.middle, upper = triple.maximum;
+  assert (lower <= def && def <= upper);
+
+  if (!extrapolate)
+      v = hb_max (hb_min (v, upper), lower);
+
+  if ((v == def) || (lower == upper))
+    return 0.f;
+
+  if ((v < def && lower != def) || (v > def && upper == def))
+    return (v - def) / (def - lower);
+  else
+  {
+    assert ((v > def && upper != def) ||
+	    (v < def && lower == def));
+    return (v - def) / (upper - def);
+  }
+}
+
+/* Given a tuple (lower,peak,upper) "tent" and new axis limits
+ * (axisMin,axisDefault,axisMax), solves how to represent the tent
+ * under the new axis configuration.  All values are in normalized
+ * -1,0,+1 coordinate system. Tent values can be outside this range.
+ *
+ * Return value: a list of tuples. Each tuple is of the form
+ * (scalar,tent), where scalar is a multipler to multiply any
+ * delta-sets by, and tent is a new tent for that output delta-set.
+ * If tent value is Triple{}, that is a special deltaset that should
+ * be always-enabled (called "gain").
+ */
+HB_INTERNAL result_t rebase_tent (Triple tent, Triple axisLimit);
+
+result_t
+rebase_tent (Triple tent, Triple axisLimit)
+{
+  assert (-1.f <= axisLimit.minimum && axisLimit.minimum <= axisLimit.middle && axisLimit.middle <= axisLimit.maximum && axisLimit.maximum <= +1.f);
+  assert (-2.f <= tent.minimum && tent.minimum <= tent.middle && tent.middle <= tent.maximum && tent.maximum <= +2.f);
+  assert (tent.middle != 0.f);
+
+  result_t sols = _solve (tent, axisLimit);
+
+  auto n = [&axisLimit] (float v) { return normalizeValue (v, axisLimit, true); };
+
+  result_t out;
+  for (auto &p : sols)
+  {
+    if (!p.first) continue;
+    if (p.second == Triple{})
+    {
+      out.push (p);
+      continue;
+    }
+    Triple t = p.second;
+    out.push (hb_pair (p.first,
+		       Triple{n (t.minimum), n (t.middle), n (t.maximum)}));
+  }
+
+  return sols;
+}