text:
/*  GRAPHITE2 LICENSING

    Copyright 2010, SIL International
    All rights reserved.

    This library is free software; you can redistribute it and/or modify
    it under the terms of the GNU Lesser General Public License as published
    by the Free Software Foundation; either version 2.1 of License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    Lesser General Public License for more details.

    You should also have received a copy of the GNU Lesser General Public
    License along with this library in the file named "LICENSE".
    If not, write to the Free Software Foundation, 51 Franklin Street,
    Suite 500, Boston, MA 02110-1335, USA or visit their web page on the
    internet at http://www.fsf.org/licenses/lgpl.html.

Alternatively, the contents of this file may be used under the terms of the
Mozilla Public License (http://mozilla.org/MPL) or the GNU General Public
License, as published by the Free Software Foundation, either version 2
of the License or (at your option) any later version.
*/
#include <algorithm>
#include <limits>
#include <cmath>
#include <string>
#include <functional>
#include "inc/Collider.h"
#include "inc/Segment.h"
#include "inc/Slot.h"
#include "inc/GlyphCache.h"
#include "inc/Sparse.h"

#define ISQRT2 0.707106781f

// Possible rounding error for subbox boundaries: 0.016 = 1/64 = 1/256 * 4
// (values in font range from 0..256)
// #define SUBBOX_RND_ERR 0.016

using namespace graphite2;

////    SHIFT-COLLIDER    ////

// Initialize the Collider to hold the basic movement limits for the
// target slot, the one we are focusing on fixing.
bool ShiftCollider::initSlot(Segment *seg, Slot *aSlot, const Rect &limit, float margin, float marginWeight,
    const Position &currShift, const Position &currOffset, int dir, GR_MAYBE_UNUSED json * const dbgout)
{
    int i;
    float mx, mn;
    float a, shift;
    const GlyphCache &gc = seg->getFace()->glyphs();
    unsigned short gid = aSlot->gid();
    if (!gc.check(gid))
        return false;
    const BBox &bb = gc.getBoundingBBox(gid);
    const SlantBox &sb = gc.getBoundingSlantBox(gid);
    //float sx = aSlot->origin().x + currShift.x;
    //float sy = aSlot->origin().y + currShift.y;
    if (currOffset.x != 0.f || currOffset.y != 0.f)
        _limit = Rect(limit.bl - currOffset, limit.tr - currOffset);
    else
        _limit = limit;
    // For a ShiftCollider, these indices indicate which vector we are moving by:
    // each _ranges represents absolute space with respect to the origin of the slot. Thus take into account true origins but subtract the vmin for the slot
    for (i = 0; i < 4; ++i)
    {
        switch (i) {
            case 0 :	// x direction
                mn = _limit.bl.x + currOffset.x;
                mx = _limit.tr.x + currOffset.x;
                _len[i] = bb.xa - bb.xi;
                a = currOffset.y + currShift.y;
                _ranges[i].initialise<XY>(mn, mx, margin, marginWeight, a);
                break;
            case 1 :	// y direction
                mn = _limit.bl.y + currOffset.y;
                mx = _limit.tr.y + currOffset.y;
                _len[i] = bb.ya - bb.yi;
                a = currOffset.x + currShift.x;
                _ranges[i].initialise<XY>(mn, mx, margin, marginWeight, a);
                break;
            case 2 :	// sum (negatively sloped diagonal boundaries)
                // pick closest x,y limit boundaries in s direction
                shift = currOffset.x + currOffset.y + currShift.x + currShift.y;
                mn = -2 * min(currShift.x - _limit.bl.x, currShift.y - _limit.bl.y) + shift;
                mx = 2 * min(_limit.tr.x - currShift.x, _limit.tr.y - currShift.y) + shift;
                _len[i] = sb.sa - sb.si;
                a = currOffset.x - currOffset.y + currShift.x - currShift.y;
                _ranges[i].initialise<SD>(mn, mx, margin / ISQRT2, marginWeight, a);
                break;
            case 3 :	// diff (positively sloped diagonal boundaries)
                // pick closest x,y limit boundaries in d direction
                shift = currOffset.x - currOffset.y + currShift.x - currShift.y;
                mn = -2 * min(currShift.x - _limit.bl.x, _limit.tr.y - currShift.y) + shift;
                mx = 2 * min(_limit.tr.x - currShift.x, currShift.y - _limit.bl.y) + shift;
                _len[i] = sb.da - sb.di;
                a = currOffset.x + currOffset.y + currShift.x + currShift.y;
                _ranges[i].initialise<SD>(mn, mx, margin / ISQRT2, marginWeight, a);
                break;
        }
    }

	_target = aSlot;
    if ((dir & 1) == 0)
    {
        // For LTR, switch and negate x limits.
        _limit.bl.x = -1 * limit.tr.x;
        //_limit.tr.x = -1 * limit.bl.x;
    }
    _currOffset = currOffset;
    _currShift = currShift;
    _origin = aSlot->origin() - currOffset;     // the original anchor position of the glyph

	_margin = margin;
	_marginWt = marginWeight;

    SlotCollision *c = seg->collisionInfo(aSlot);
    _seqClass = c->seqClass();
	_seqProxClass = c->seqProxClass();
    _seqOrder = c->seqOrder();
    return true;
}

template <class O>
float sdm(float vi, float va, float mx, float my, O op)
{
    float res = 2 * mx - vi;
    if (op(res, vi + 2 * my))
    {
        res = va + 2 * my;
        if (op(res, 2 * mx - va))
            res = mx + my;
    }
    return res;
}

// Mark an area with a cost that can vary along the x or y axis. The region is expressed in terms of the centre of the target glyph in each axis
void ShiftCollider::addBox_slope(bool isx, const Rect &box, const BBox &bb, const SlantBox &sb, const Position &org, float weight, float m, bool minright, int axis)
{
    float a, c;
    switch (axis) {
        case 0 :
             if (box.bl.y < org.y + bb.ya && box.tr.y > org.y + bb.yi && box.width() > 0)
            {
                a = org.y + 0.5f * (bb.yi + bb.ya);
                c = 0.5f * (bb.xi + bb.xa);
                if (isx)
                    _ranges[axis].weighted<XY>(box.bl.x - c, box.tr.x - c, weight, a, m,
                                                (minright ? box.tr.x : box.bl.x) - c, a, 0, false);
                else
                    _ranges[axis].weighted<XY>(box.bl.x - c, box.tr.x - c, weight, a, 0, 0, org.y,
                                                m * (a * a + sqr((minright ? box.tr.y : box.bl.y) - 0.5f * (bb.yi + bb.ya))), false);
            }
            break;
        case 1 :
            if (box.bl.x < org.x + bb.xa && box.tr.x > org.x + bb.xi && box.height() > 0)
            {
                a = org.x + 0.5f * (bb.xi + bb.xa);
                c = 0.5f * (bb.yi + bb.ya);
                if (isx)
                    _ranges[axis].weighted<XY>(box.bl.y - c, box.tr.y - c, weight, a, 0, 0, org.x,
                                                m * (a * a + sqr((minright ? box.tr.x : box.bl.x) - 0.5f * (bb.xi + bb.xa))), false);
                else
                    _ranges[axis].weighted<XY>(box.bl.y - c, box.tr.y - c, weight, a, m,
                                                (minright ? box.tr.y : box.bl.y) - c, a, 0, false);
            }
            break;
        case 2 :
            if (box.bl.x - box.tr.y < org.x - org.y + sb.da && box.tr.x - box.bl.y > org.x - org.y + sb.di)
            {
                float d = org.x - org.y + 0.5f * (sb.di + sb.da);
                c = 0.5f * (sb.si + sb.sa);
                float smax = min(2 * box.tr.x - d, 2 * box.tr.y + d);
                float smin = max(2 * box.bl.x - d, 2 * box.bl.y + d);
                if (smin > smax) return;
                float si;
                a = d;
                if (isx)
                    si = 2 * (minright ? box.tr.x : box.bl.x) - a;
                else
                    si = 2 * (minright ? box.tr.y : box.bl.y) + a;
                _ranges[axis].weighted<SD>(smin - c, smax - c, weight / 2, a, m / 2, si, 0, 0, isx);
            }
            break;
        case 3 :
            if (box.bl.x + box.bl.y < org.x + org.y + sb.sa && box.tr.x + box.tr.y > org.x + org.y + sb.si)
            {
                float s = org.x + org.y + 0.5f * (sb.si + sb.sa);
                c = 0.5f * (sb.di + sb.da);
                float dmax = min(2 * box.tr.x - s, s - 2 * box.bl.y);
                float dmin = max(2 * box.bl.x - s, s - 2 * box.tr.y);
                if (dmin > dmax) return;
                float di;
                a = s;
                if (isx)
                    di = 2 * (minright ? box.tr.x : box.bl.x) - a;
                else
                    di = 2 * (minright ? box.tr.y : box.bl.y) + a;
                _ranges[axis].weighted<SD>(dmin - c, dmax - c, weight / 2, a, m / 2, di, 0, 0, !isx);
            }
            break;
        default :
            break;
    }
    return;
}

// Mark an area with an absolute cost, making it completely inaccessible.
inline void ShiftCollider::removeBox(const Rect &box, const BBox &bb, const SlantBox &sb, const Position &org, int axis)
{
    float c;
    switch (axis) {
        case 0 :
            if (box.bl.y < org.y + bb.ya && box.tr.y > org.y + bb.yi && box.width() > 0)
            {
                c = 0.5f * (bb.xi + bb.xa);
                _ranges[axis].exclude(box.bl.x - c, box.tr.x - c);
            }
            break;
        case 1 :
            if (box.bl.x < org.x + bb.xa && box.tr.x > org.x + bb.xi && box.height() > 0)
            {
                c = 0.5f * (bb.yi + bb.ya);
                _ranges[axis].exclude(box.bl.y - c, box.tr.y - c);
            }
            break;
        case 2 :
            if (box.bl.x - box.tr.y < org.x - org.y + sb.da && box.tr.x - box.bl.y > org.x - org.y + sb.di
                && box.width() > 0 && box.height() > 0)
            {
                float di = org.x - org.y + sb.di;
                float da = org.x - org.y + sb.da;
                float smax = sdm(di, da, box.tr.x, box.tr.y, std::greater<float>());
                float smin = sdm(da, di, box.bl.x, box.bl.y, std::less<float>());
                c = 0.5f * (sb.si + sb.sa);
                _ranges[axis].exclude(smin - c, smax - c);
            }
            break;
        case 3 :
            if (box.bl.x + box.bl.y < org.x + org.y + sb.sa && box.tr.x + box.tr.y > org.x + org.y + sb.si
                && box.width() > 0 && box.height() > 0)
            {
                float si = org.x + org.y + sb.si;
                float sa = org.x + org.y + sb.sa;
                float dmax = sdm(si, sa, box.tr.x, -box.bl.y, std::greater<float>());
                float dmin = sdm(sa, si, box.bl.x, -box.tr.y, std::less<float>());
                c = 0.5f * (sb.di + sb.da);
                _ranges[axis].exclude(dmin - c, dmax - c);
            }
            break;
        default :
            break;
    }
    return;
}

// Adjust the movement limits for the target to avoid having it collide
// with the given neighbor slot. Also determine if there is in fact a collision
// between the target and the given slot.
bool ShiftCollider::mergeSlot(Segment *seg, Slot *slot, const SlotCollision *cslot, const Position &currShift,
		bool isAfter,  // slot is logically after _target
		bool sameCluster, bool &hasCol, bool isExclusion,
        GR_MAYBE_UNUSED json * const dbgout )
{
    bool isCol = false;
    const float sx = slot->origin().x - _origin.x + currShift.x;
    const float sy = slot->origin().y - _origin.y + currShift.y;
    const float sd = sx - sy;
    const float ss = sx + sy;
    float vmin, vmax;
    float omin, omax, otmin, otmax;
    float cmin, cmax;   // target limits
    float torg;
    const GlyphCache &gc = seg->getFace()->glyphs();
    const unsigned short gid = slot->gid();
    if (!gc.check(gid))
        return false;
    const BBox &bb = gc.getBoundingBBox(gid);

    // SlotCollision * cslot = seg->collisionInfo(slot);
    int orderFlags = 0;
    bool sameClass = _seqProxClass == 0 && cslot->seqClass() == _seqClass;
    if (sameCluster && _seqClass
        && (sameClass || (_seqProxClass != 0 && cslot->seqClass() == _seqProxClass)))
		// Force the target glyph to be in the specified direction from the slot we're testing.
        orderFlags = _seqOrder;

    // short circuit if only interested in direct collision and we are out of range
    if (orderFlags || (sx + bb.xa + _margin >= _limit.bl.x && sx + bb.xi - _margin <= _limit.tr.x)
                    || (sy + bb.ya + _margin >= _limit.bl.y && sy + bb.yi - _margin <= _limit.tr.y))

    {
        const float tx = _currOffset.x + _currShift.x;
        const float ty = _currOffset.y + _currShift.y;
        const float td = tx - ty;
        const float ts = tx + ty;
        const SlantBox &sb = gc.getBoundingSlantBox(gid);
        const unsigned short tgid = _target->gid();
        const BBox &tbb = gc.getBoundingBBox(tgid);
        const SlantBox &tsb = gc.getBoundingSlantBox(tgid);
        float seq_above_wt = cslot->seqAboveWt();
        float seq_below_wt = cslot->seqBelowWt();
        float seq_valign_wt = cslot->seqValignWt();
        float lmargin;
        // if isAfter, invert orderFlags for diagonal orders.
        if (isAfter)
        {
            // invert appropriate bits
            orderFlags ^= (sameClass ? 0x3F : 0x3);
            // consider 2 bits at a time, non overlapping. If both bits set, clear them
            orderFlags = orderFlags ^ ((((orderFlags >> 1) & orderFlags) & 0x15) * 3);
        }

#if !defined GRAPHITE2_NTRACING
        if (dbgout)
            dbgout->setenv(0, slot);
#endif

        // Process main bounding octabox.
        for (int i = 0; i < 4; ++i)
        {
            switch (i) {
                case 0 :	// x direction
                    vmin = max(max(bb.xi - tbb.xa + sx, sb.di - tsb.da + ty + sd), sb.si - tsb.sa - ty + ss);
                    vmax = min(min(bb.xa - tbb.xi + sx, sb.da - tsb.di + ty + sd), sb.sa - tsb.si - ty + ss);
                    otmin = tbb.yi + ty;
                    otmax = tbb.ya + ty;
                    omin = bb.yi + sy;
                    omax = bb.ya + sy;
                    torg = _currOffset.x;
                    cmin = _limit.bl.x + torg;
                    cmax = _limit.tr.x - tbb.xi + tbb.xa + torg;
                    lmargin = _margin;
                    break;
                case 1 :	// y direction
                    vmin = max(max(bb.yi - tbb.ya + sy, tsb.di - sb.da + tx - sd), sb.si - tsb.sa - tx + ss);
                    vmax = min(min(bb.ya - tbb.yi + sy, tsb.da - sb.di + tx - sd), sb.sa - tsb.si - tx + ss);
                    otmin = tbb.xi + tx;
                    otmax = tbb.xa + tx;
                    omin = bb.xi + sx;
                    omax = bb.xa + sx;
                    torg = _currOffset.y;
                    cmin = _limit.bl.y + torg;
                    cmax = _limit.tr.y - tbb.yi + tbb.ya + torg;
                    lmargin = _margin;
                    break;
                case 2 :    // sum - moving along the positively-sloped vector, so the boundaries are the
                            // negatively-sloped boundaries.
                    vmin = max(max(sb.si - tsb.sa + ss, 2 * (bb.yi - tbb.ya + sy) + td), 2 * (bb.xi - tbb.xa + sx) - td);
                    vmax = min(min(sb.sa - tsb.si + ss, 2 * (bb.ya - tbb.yi + sy) + td), 2 * (bb.xa - tbb.xi + sx) - td);
                    otmin = tsb.di + td;
                    otmax = tsb.da + td;
                    omin = sb.di + sd;
                    omax = sb.da + sd;
                    torg = _currOffset.x + _currOffset.y;
                    cmin = _limit.bl.x + _limit.bl.y + torg;
                    cmax = _limit.tr.x + _limit.tr.y - tsb.si + tsb.sa + torg;
                    lmargin = _margin / ISQRT2;
                    break;
                case 3 :    // diff - moving along the negatively-sloped vector, so the boundaries are the
                            // positively-sloped boundaries.
                    vmin = max(max(sb.di - tsb.da + sd, 2 * (bb.xi - tbb.xa + sx) - ts), -2 * (bb.ya - tbb.yi + sy) + ts);
                    vmax = min(min(sb.da - tsb.di + sd, 2 * (bb.xa - tbb.xi + sx) - ts), -2 * (bb.yi - tbb.ya + sy) + ts);
                    otmin = tsb.si + ts;
                    otmax = tsb.sa + ts;
                    omin = sb.si + ss;
                    omax = sb.sa + ss;
                    torg = _currOffset.x - _currOffset.y;
                    cmin = _limit.bl.x - _limit.tr.y + torg;
                    cmax = _limit.tr.x - _limit.bl.y - tsb.di + tsb.da + torg;
                    lmargin = _margin / ISQRT2;
                    break;
                default :
                    continue;
            }

#if !defined GRAPHITE2_NTRACING
            if (dbgout)
                dbgout->setenv(1, reinterpret_cast<void *>(-1));
#define DBGTAG(x) if (dbgout) dbgout->setenv(1, reinterpret_cast<void *>(-x));
#else
#define DBGTAG(x)
#endif

            if (orderFlags)
            {
                Position org(tx, ty);
                float xminf = _limit.bl.x + _currOffset.x + tbb.xi;
                float xpinf = _limit.tr.x + _currOffset.x + tbb.xa;
                float ypinf = _limit.tr.y + _currOffset.y + tbb.ya;
                float yminf = _limit.bl.y + _currOffset.y + tbb.yi;
                switch (orderFlags) {
                    case SlotCollision::SEQ_ORDER_RIGHTUP :
                    {
                        float r1Xedge = cslot->seqAboveXoff() + 0.5f * (bb.xi + bb.xa) + sx;
                        float r3Xedge = cslot->seqBelowXlim() + bb.xa + sx + 0.5f * (tbb.xa - tbb.xi);
                        float r2Yedge = 0.5f * (bb.yi + bb.ya) + sy;

                        // DBGTAG(1x) means the regions are up and right
                        // region 1
                        DBGTAG(11)
                        addBox_slope(true, Rect(Position(xminf, r2Yedge), Position(r1Xedge, ypinf)),
                                        tbb, tsb, org, 0, seq_above_wt, true, i);
                        // region 2
                        DBGTAG(12)
                        removeBox(Rect(Position(xminf, yminf), Position(r3Xedge, r2Yedge)), tbb, tsb, org, i);
                        // region 3, which end is zero is irrelevant since m weight is 0
                        DBGTAG(13)
                        addBox_slope(true, Rect(Position(r3Xedge, yminf), Position(xpinf, r2Yedge - cslot->seqValignHt())),
                                        tbb, tsb, org, seq_below_wt, 0, true, i);
                        // region 4
                        DBGTAG(14)
                        addBox_slope(false, Rect(Position(sx + bb.xi, r2Yedge), Position(xpinf, r2Yedge + cslot->seqValignHt())),
                                        tbb, tsb, org, 0, seq_valign_wt, true, i);
                        // region 5
                        DBGTAG(15)
                        addBox_slope(false, Rect(Position(sx + bb.xi, r2Yedge - cslot->seqValignHt()), Position(xpinf, r2Yedge)),
                                        tbb, tsb, org, seq_below_wt, seq_valign_wt, false, i);
                        break;
                    }
                    case SlotCollision::SEQ_ORDER_LEFTDOWN :
                    {
                        float r1Xedge = 0.5f * (bb.xi + bb.xa) + cslot->seqAboveXoff() + sx;
                        float r3Xedge = bb.xi - cslot->seqBelowXlim() + sx - 0.5f * (tbb.xa - tbb.xi);
                        float r2Yedge = 0.5f * (bb.yi + bb.ya) + sy;
                        // DBGTAG(2x) means the regions are up and right
                        // region 1
                        DBGTAG(21)
                        addBox_slope(true, Rect(Position(r1Xedge, yminf), Position(xpinf, r2Yedge)),
                                        tbb, tsb, org, 0, seq_above_wt, false, i);
                        // region 2
                        DBGTAG(22)
                        removeBox(Rect(Position(r3Xedge, r2Yedge), Position(xpinf, ypinf)), tbb, tsb, org, i);
                        // region 3
                        DBGTAG(23)
                        addBox_slope(true, Rect(Position(xminf, r2Yedge - cslot->seqValignHt()), Position(r3Xedge, ypinf)),
                                        tbb, tsb, org, seq_below_wt, 0, false, i);
                        // region 4
                        DBGTAG(24)
                        addBox_slope(false, Rect(Position(xminf, r2Yedge), Position(sx + bb.xa, r2Yedge + cslot->seqValignHt())),
                                        tbb, tsb, org, 0, seq_valign_wt, true, i);
                        // region 5
                        DBGTAG(25)
                        addBox_slope(false, Rect(Position(xminf, r2Yedge - cslot->seqValignHt()),
                                        Position(sx + bb.xa, r2Yedge)), tbb, tsb, org, seq_below_wt, seq_valign_wt, false, i);
                        break;
                    }
                    case SlotCollision::SEQ_ORDER_NOABOVE : // enforce neighboring glyph being above
                        DBGTAG(31);
                        removeBox(Rect(Position(bb.xi - tbb.xa + sx, sy + bb.ya),
                                        Position(bb.xa - tbb.xi + sx, ypinf)), tbb, tsb, org, i);
                        break;
                    case SlotCollision::SEQ_ORDER_NOBELOW :	// enforce neighboring glyph being below
                        DBGTAG(32);
                        removeBox(Rect(Position(bb.xi - tbb.xa + sx, yminf),
                                        Position(bb.xa - tbb.xi + sx, sy + bb.yi)), tbb, tsb, org, i);
                        break;
                    case SlotCollision::SEQ_ORDER_NOLEFT :  // enforce neighboring glyph being to the left
                        DBGTAG(33)
                        removeBox(Rect(Position(xminf, bb.yi - tbb.ya + sy),
                                        Position(bb.xi - tbb.xa + sx, bb.ya - tbb.yi + sy)), tbb, tsb, org, i);
                        break;
                    case SlotCollision::SEQ_ORDER_NORIGHT : // enforce neighboring glyph being to the right
                        DBGTAG(34)
                        removeBox(Rect(Position(bb.xa - tbb.xi + sx, bb.yi - tbb.ya + sy),
                                        Position(xpinf, bb.ya - tbb.yi + sy)), tbb, tsb, org, i);
                        break;
                    default :
                        break;
                }
            }

            if (vmax < cmin - lmargin || vmin > cmax + lmargin || omax < otmin - lmargin || omin > otmax + lmargin)
                continue;

            // Process sub-boxes that are defined for this glyph.
            // We only need to do this if there was in fact a collision with the main octabox.
            uint8 numsub = gc.numSubBounds(gid);
            if (numsub > 0)
            {
                bool anyhits = false;
                for (int j = 0; j < numsub; ++j)
                {
                    const BBox &sbb = gc.getSubBoundingBBox(gid, j);
                    const SlantBox &ssb = gc.getSubBoundingSlantBox(gid, j);
                    switch (i) {
                        case 0 :    // x
                            vmin = max(max(sbb.xi-tbb.xa+sx, ssb.di-tsb.da+sd+ty), ssb.si-tsb.sa+ss-ty);
                            vmax = min(min(sbb.xa-tbb.xi+sx, ssb.da-tsb.di+sd+ty), ssb.sa-tsb.si+ss-ty);
                            omin = sbb.yi + sy;
                            omax = sbb.ya + sy;
                            break;
                        case 1 :    // y
                            vmin = max(max(sbb.yi-tbb.ya+sy, tsb.di-ssb.da-sd+tx), ssb.si-tsb.sa+ss-tx);
                            vmax = min(min(sbb.ya-tbb.yi+sy, tsb.da-ssb.di-sd+tx), ssb.sa-tsb.si+ss-tx);
                            omin = sbb.xi + sx;
                            omax = sbb.xa + sx;
                            break;
                        case 2 :    // sum
                            vmin = max(max(ssb.si-tsb.sa+ss, 2*(sbb.yi-tbb.ya+sy)+td), 2*(sbb.xi-tbb.xa+sx)-td);
                            vmax = min(min(ssb.sa-tsb.si+ss, 2*(sbb.ya-tbb.yi+sy)+td), 2*(sbb.xa-tbb.xi+sx)-td);
                            omin = ssb.di + sd;
                            omax = ssb.da + sd;
                            break;
                        case 3 :    // diff
                            vmin = max(max(ssb.di-tsb.da+sd, 2*(sbb.xi-tbb.xa+sx)-ts), -2*(sbb.ya-tbb.yi+sy)+ts);
                            vmax = min(min(ssb.da-tsb.di+sd, 2*(sbb.xa-tbb.xi+sx)-ts), -2*(sbb.yi-tbb.ya+sy)+ts);
                            omin = ssb.si + ss;
                            omax = ssb.sa + ss;
                            break;
                    }
                    if (vmax < cmin - lmargin || vmin > cmax + lmargin || omax < otmin - lmargin || omin > otmax + lmargin)
                        continue;

#if !defined GRAPHITE2_NTRACING
                    if (dbgout)
                        dbgout->setenv(1, reinterpret_cast<void *>(j));
#endif
                    if (omin > otmax)
                        _ranges[i].weightedAxis(i, vmin - lmargin, vmax + lmargin, 0, 0, 0, 0, 0,
                                                sqr(lmargin - omin + otmax) * _marginWt, false);
                    else if (omax < otmin)
                        _ranges[i].weightedAxis(i, vmin - lmargin, vmax + lmargin, 0, 0, 0, 0, 0,
                                                sqr(lmargin - otmin + omax) * _marginWt, false);
                    else
                        _ranges[i].exclude_with_margins(vmin, vmax, i);
                    anyhits = true;
                }
                if (anyhits)
                    isCol = true;
            }
            else // no sub-boxes
            {
#if !defined GRAPHITE2_NTRACING
                    if (dbgout)
                        dbgout->setenv(1, reinterpret_cast<void *>(-1));
#endif
                isCol = true;
                if (omin > otmax)
                    _ranges[i].weightedAxis(i, vmin - lmargin, vmax + lmargin, 0, 0, 0, 0, 0,
                                            sqr(lmargin - omin + otmax) * _marginWt, false);
                else if (omax < otmin)
                    _ranges[i].weightedAxis(i, vmin - lmargin, vmax + lmargin, 0, 0, 0, 0, 0,
                                            sqr(lmargin - otmin + omax) * _marginWt, false);
                else
                    _ranges[i].exclude_with_margins(vmin, vmax, i);

            }
        }
    }
    bool res = true;
    if (cslot->exclGlyph() > 0 && gc.check(cslot->exclGlyph()) && !isExclusion)
    {
        // Set up the bogus slot representing the exclusion glyph.
        Slot *exclSlot = seg->newSlot();
        if (!exclSlot)
            return res;
        exclSlot->setGlyph(seg, cslot->exclGlyph());
        Position exclOrigin(slot->origin() + cslot->exclOffset());
        exclSlot->origin(exclOrigin);
        SlotCollision exclInfo(seg, exclSlot);
        res &= mergeSlot(seg, exclSlot, &exclInfo, currShift, isAfter, sameCluster, isCol, true, dbgout );
        seg->freeSlot(exclSlot);
    }
    hasCol |= isCol;
    return res;

}   // end of ShiftCollider::mergeSlot

// Figure out where to move the target glyph to, and return the amount to shift by.
Position ShiftCollider::resolve(GR_MAYBE_UNUSED Segment *seg, bool &isCol, GR_MAYBE_UNUSED json * const dbgout)
{
    float tbase;
    float totalCost = (float)(std::numeric_limits<float>::max() / 2);
    Position resultPos = Position(0, 0);
#if !defined GRAPHITE2_NTRACING
	int bestAxis = -1;
    if (dbgout)
    {
		outputJsonDbgStartSlot(dbgout, seg);
        *dbgout << "vectors" << json::array;
    }
#endif
    isCol = true;
    for (int i = 0; i < 4; ++i)
    {
        float bestCost = -1;
        float bestPos;
        // Calculate the margin depending on whether we are moving diagonally or not:
        switch (i) {
            case 0 :	// x direction
                tbase = _currOffset.x;
                break;
            case 1 :	// y direction
                tbase = _currOffset.y;
                break;
            case 2 :	// sum (negatively-sloped diagonals)
                tbase = _currOffset.x + _currOffset.y;
                break;
            case 3 :	// diff (positively-sloped diagonals)
                tbase = _currOffset.x - _currOffset.y;
                break;
        }
        Position testp;
        bestPos = _ranges[i].closest(0, bestCost) - tbase;     // Get the best relative position
#if !defined GRAPHITE2_NTRACING
        if (dbgout)
            outputJsonDbgOneVector(dbgout, seg, i, tbase, bestCost, bestPos) ;
#endif
        if (bestCost >= 0.0f)
        {
            isCol = false;
            switch (i) {
                case 0 : testp = Position(bestPos, _currShift.y); break;
                case 1 : testp = Position(_currShift.x, bestPos); break;
                case 2 : testp = Position(0.5f * (_currShift.x - _currShift.y + bestPos), 0.5f * (_currShift.y - _currShift.x + bestPos)); break;
                case 3 : testp = Position(0.5f * (_currShift.x + _currShift.y + bestPos), 0.5f * (_currShift.x + _currShift.y - bestPos)); break;
            }
            if (bestCost < totalCost - 0.01f)
            {
                totalCost = bestCost;
                resultPos = testp;
#if !defined GRAPHITE2_NTRACING
                bestAxis = i;
#endif
            }
        }
    }  // end of loop over 4 directions

#if !defined GRAPHITE2_NTRACING
    if (dbgout)
        outputJsonDbgEndSlot(dbgout, resultPos, bestAxis, isCol);
#endif

    return resultPos;

}   // end of ShiftCollider::resolve

#if !defined GRAPHITE2_NTRACING

void ShiftCollider::outputJsonDbg(json * const dbgout, Segment *seg, int axis)
{
    int axisMax = axis;
    if (axis < 0) // output all axes
    {
        *dbgout << "gid" << _target->gid()
            << "limit" << _limit
            << "target" << json::object
                << "origin" << _target->origin()
                << "margin" << _margin
                << "bbox" << seg->theGlyphBBoxTemporary(_target->gid())
                << "slantbox" << seg->getFace()->glyphs().slant(_target->gid())
                << json::close; // target object
        *dbgout << "ranges" << json::array;
        axis = 0;
        axisMax = 3;
    }
    for (int iAxis = axis; iAxis <= axisMax; ++iAxis)
    {
        *dbgout << json::flat << json::array << _ranges[iAxis].position();
        for (Zones::const_iterator s = _ranges[iAxis].begin(), e = _ranges[iAxis].end(); s != e; ++s)
            *dbgout << json::flat << json::array
                        << Position(s->x, s->xm) << s->sm << s->smx << s->c
                    << json::close;
        *dbgout << json::close;
    }
    if (axis < axisMax) // looped through the _ranges array for all axes
        *dbgout << json::close; // ranges array
}

void ShiftCollider::outputJsonDbgStartSlot(json * const dbgout, Segment *seg)
{
        *dbgout << json::object // slot - not closed till the end of the caller method
                << "slot" << objectid(dslot(seg, _target))
				<< "gid" << _target->gid()
                << "limit" << _limit
                << "target" << json::object
                    << "origin" << _origin
                    << "currShift" << _currShift
                    << "currOffset" << seg->collisionInfo(_target)->offset()
                    << "bbox" << seg->theGlyphBBoxTemporary(_target->gid())
                    << "slantBox" << seg->getFace()->glyphs().slant(_target->gid())
                    << "fix" << "shift";
        *dbgout     << json::close; // target object
}

void ShiftCollider::outputJsonDbgEndSlot(GR_MAYBE_UNUSED json * const dbgout,
	 Position resultPos, int bestAxis, bool isCol)
{
    *dbgout << json::close // vectors array
    << "result" << resultPos
	//<< "scraping" << _scraping[bestAxis]
	<< "bestAxis" << bestAxis
    << "stillBad" << isCol
    << json::close; // slot object
}

void ShiftCollider::outputJsonDbgOneVector(json * const dbgout, Segment *seg, int axis,
	float tleft, float bestCost, float bestVal)
{
	const char * label;
	switch (axis)
	{
		case 0:	label = "x";			break;
		case 1:	label = "y";			break;
		case 2:	label = "sum (NE-SW)";	break;
		case 3:	label = "diff (NW-SE)";	break;
		default: label = "???";			break;
	}

	*dbgout << json::object // vector
		<< "direction" << label
		<< "targetMin" << tleft;

	outputJsonDbgRemovals(dbgout, axis, seg);

    *dbgout << "ranges";
    outputJsonDbg(dbgout, seg, axis);

    *dbgout << "bestCost" << bestCost
        << "bestVal" << bestVal + tleft
        << json::close; // vectors object
}

void ShiftCollider::outputJsonDbgRemovals(json * const dbgout, int axis, Segment *seg)
{
    *dbgout << "removals" << json::array;
    _ranges[axis].jsonDbgOut(seg);
    *dbgout << json::close; // removals array
}

#endif // !defined GRAPHITE2_NTRACING

////    KERN-COLLIDER    ////

inline
static float localmax (float al, float au, float bl, float bu, float x)
{
    if (al < bl)
    { if (au < bu) return au < x ? au : x; }
    else if (au > bu) return bl < x ? bl : x;
    return x;
}

inline
static float localmin(float al, float au, float bl, float bu, float x)
{
    if (bl > al)
    { if (bu > au) return bl > x ? bl : x; }
    else if (au > bu) return al > x ? al : x;
    return x;
}

// Return the given edge of the glyph at height y, taking any slant box into account.
static float get_edge(Segment *seg, const Slot *s, const Position &shift, float y, float width, float margin, bool isRight)
{
    const GlyphCache &gc = seg->getFace()->glyphs();
    unsigned short gid = s->gid();
    float sx = s->origin().x + shift.x;
    float sy = s->origin().y + shift.y;
    uint8 numsub = gc.numSubBounds(gid);
    float res = isRight ? (float)-1e38 : (float)1e38;

    if (numsub > 0)
    {
        for (int i = 0; i < numsub; ++i)
        {
            const BBox &sbb = gc.getSubBoundingBBox(gid, i);
            const SlantBox &ssb = gc.getSubBoundingSlantBox(gid, i);
            if (sy + sbb.yi - margin > y + width / 2 || sy + sbb.ya + margin < y - width / 2)
                continue;
            if (isRight)
            {
                float x = sx + sbb.xa + margin;
                if (x > res)
                {
                    float td = sx - sy + ssb.da + margin + y;
                    float ts = sx + sy + ssb.sa + margin - y;
                    x = localmax(td - width / 2, td + width / 2,  ts - width / 2, ts + width / 2, x);
                    if (x > res)
                        res = x;
                }
            }
            else
            {
                float x = sx + sbb.xi - margin;
                if (x < res)
                {
                    float td = sx - sy + ssb.di - margin + y;
                    float ts = sx + sy + ssb.si - margin - y;
                    x = localmin(td - width / 2, td + width / 2, ts - width / 2, ts + width / 2, x);
                    if (x < res)
                        res = x;
                }
            }
        }
    }
    else
    {
        const BBox &bb = gc.getBoundingBBox(gid);
        const SlantBox &sb = gc.getBoundingSlantBox(gid);
        if (sy + bb.yi - margin > y + width / 2 || sy + bb.ya + margin < y - width / 2)
            return res;
        float td = sx - sy + y;
        float ts = sx + sy - y;
        if (isRight)
            res = localmax(td + sb.da - width / 2, td + sb.da + width / 2, ts + sb.sa - width / 2, ts + sb.sa + width / 2, sx + bb.xa) + margin;
        else
            res = localmin(td + sb.di - width / 2, td + sb.di + width / 2, ts + sb.si - width / 2, ts + sb.si + width / 2, sx + bb.xi) - margin;
    }
    return res;
}

bool KernCollider::initSlot(Segment *seg, Slot *aSlot, const Rect &limit, float margin,
    const Position &currShift, const Position &offsetPrev, int dir,
    float ymin, float ymax, GR_MAYBE_UNUSED json * const dbgout)
{
    const GlyphCache &gc = seg->getFace()->glyphs();
    const Slot *base = aSlot;
    // const Slot *last = aSlot;
    const Slot *s;
    int numSlices;
    while (base->attachedTo())
        base = base->attachedTo();
    if (margin < 10) margin = 10;

    _limit = limit;
    _offsetPrev = offsetPrev; // kern from a previous pass

    // Calculate the height of the glyph and how many horizontal slices to use.
    if (_maxy >= 1e37f)
    {
        _sliceWidth = margin / 1.5f;
        _maxy = ymax + margin;
        _miny = ymin - margin;
        numSlices = int((_maxy - _miny + 2) / (_sliceWidth / 1.5f) + 1.f);  // +2 helps with rounding errors
        _edges.clear();
        _edges.insert(_edges.begin(), numSlices, (dir & 1) ? 1e38f : -1e38f);
        _xbound = (dir & 1) ? (float)1e38f : (float)-1e38f;
    }
    else if (_maxy != ymax || _miny != ymin)
    {
        if (_miny != ymin)
        {
            numSlices = int((ymin - margin - _miny) / _sliceWidth - 1);
            _miny += numSlices * _sliceWidth;
            if (numSlices < 0)
                _edges.insert(_edges.begin(), -numSlices, (dir & 1) ? 1e38f : -1e38f);
            else if ((unsigned)numSlices < _edges.size())    // this shouldn't fire since we always grow the range
            {
                Vector<float>::iterator e = _edges.begin();
                while (numSlices--)
                    ++e;
                _edges.erase(_edges.begin(), e);
            }
        }
        if (_maxy != ymax)
        {
            numSlices = int((ymax + margin - _miny) / _sliceWidth + 1);
            _maxy = numSlices * _sliceWidth + _miny;
            if (numSlices > (int)_edges.size())
                _edges.insert(_edges.end(), numSlices - _edges.size(), (dir & 1) ? 1e38f : -1e38f);
            else if (numSlices < (int)_edges.size())   // this shouldn't fire since we always grow the range
            {
                while ((int)_edges.size() > numSlices)
                    _edges.pop_back();
            }
        }
        goto done;
    }
    numSlices = int(_edges.size());

#if !defined GRAPHITE2_NTRACING
    // Debugging
    _seg = seg;
    _slotNear.clear();
    _slotNear.insert(_slotNear.begin(), numSlices, NULL);
    _nearEdges.clear();
    _nearEdges.insert(_nearEdges.begin(), numSlices, (dir & 1) ? -1e38f : +1e38f);
#endif

    // Determine the trailing edge of each slice (ie, left edge for a RTL glyph).
    for (s = base; s; s = s->nextInCluster(s))
    {
        SlotCollision *c = seg->collisionInfo(s);
        if (!gc.check(s->gid()))
            return false;
        const BBox &bs = gc.getBoundingBBox(s->gid());
        float x = s->origin().x + c->shift().x + ((dir & 1) ? bs.xi : bs.xa);
        // Loop over slices.
        // Note smin might not be zero if glyph s is not at the bottom of the cluster; similarly for smax.
        float toffset = c->shift().y - _miny + 1 + s->origin().y;
        int smin = max(0, int((bs.yi + toffset) / _sliceWidth));
        int smax = min(numSlices - 1, int((bs.ya + toffset) / _sliceWidth + 1));
        for (int i = smin; i <= smax; ++i)
        {
            float t;
            float y = _miny - 1 + (i + .5f) * _sliceWidth; // vertical center of slice
            if ((dir & 1) && x < _edges[i])
            {
                t = get_edge(seg, s, c->shift(), y, _sliceWidth, margin, false);
                if (t < _edges[i])
                {
                    _edges[i] = t;
                    if (t < _xbound)
                        _xbound = t;
                }
            }
            else if (!(dir & 1) && x > _edges[i])
            {
                t = get_edge(seg, s, c->shift(), y, _sliceWidth, margin, true);
                if (t > _edges[i])
                {
                    _edges[i] = t;
                    if (t > _xbound)
                        _xbound = t;
                }
            }
        }
    }
    done:
    _mingap = (float)1e37;      // less than 1e38 s.t. 1e38-_mingap is really big
    _target = aSlot;
    _margin = margin;
    _currShift = currShift;
    return true;
}   // end of KernCollider::initSlot

// Determine how much the target slot needs to kern away from the given slot.
// In other words, merge information from given slot's position with what the target slot knows
// about how it can kern.
// Return false if we know there is no collision, true if we think there might be one.
bool KernCollider::mergeSlot(Segment *seg, Slot *slot, const Position &currShift, float currSpace, int dir, GR_MAYBE_UNUSED json * const dbgout)
{
    int rtl = (dir & 1) * 2 - 1;
    if (!seg->getFace()->glyphs().check(slot->gid()))
        return false;
    const Rect &bb = seg->theGlyphBBoxTemporary(slot->gid());
    const float sx = slot->origin().x + currShift.x;
    float x = (sx + (rtl > 0 ? bb.tr.x : bb.bl.x)) * rtl;
    // this isn't going to reduce _mingap so skip
    if (_hit && x < rtl * (_xbound - _mingap - currSpace))
        return false;

    const float sy = slot->origin().y + currShift.y;
    int smin = max(1, int((bb.bl.y + (1 - _miny + sy)) / _sliceWidth + 1)) - 1;
    int smax = min((int)_edges.size() - 2, int((bb.tr.y + (1 - _miny + sy)) / _sliceWidth + 1)) + 1;
    if (smin > smax)
        return false;
    bool collides = false;
    bool nooverlap = true;

    for (int i = smin; i <= smax; ++i)
    {
        float here = _edges[i] * rtl;
        if (here > (float)9e37)
            continue;
        if (!_hit || x > here - _mingap - currSpace)
        {
            float y = (float)(_miny - 1 + (i + .5f) * _sliceWidth);  // vertical center of slice
            // 2 * currSpace to account for the space that is already separating them and the space we want to add
            float m = get_edge(seg, slot, currShift, y, _sliceWidth, 0., rtl > 0) * rtl + 2 * currSpace;
            if (m < (float)-8e37)       // only true if the glyph has a gap in it
                continue;
            nooverlap = false;
            float t = here - m;
            // _mingap is positive to shrink
            if (t < _mingap || (!_hit && !collides))
            {
                _mingap = t;
                collides = true;
            }
#if !defined GRAPHITE2_NTRACING
            // Debugging - remember the closest neighboring edge for this slice.
            if (m > rtl * _nearEdges[i])
            {
                _slotNear[i] = slot;
                _nearEdges[i] = m * rtl;
            }
#endif
        }
        else
            nooverlap = false;
    }
    if (nooverlap)
        _mingap = max(_mingap, _xbound - rtl * (currSpace + _margin + x));
    if (collides && !nooverlap)
        _hit = true;
    return collides | nooverlap;   // note that true is not a necessarily reliable value

}   // end of KernCollider::mergeSlot

// Return the amount to kern by.
Position KernCollider::resolve(GR_MAYBE_UNUSED Segment *seg, GR_MAYBE_UNUSED Slot *slot,
        int dir, GR_MAYBE_UNUSED json * const dbgout)
{
    float resultNeeded = (1 - 2 * (dir & 1)) * _mingap;
    // float resultNeeded = (1 - 2 * (dir & 1)) * (_mingap - margin);
    float result = min(_limit.tr.x - _offsetPrev.x, max(resultNeeded, _limit.bl.x - _offsetPrev.x));

#if !defined GRAPHITE2_NTRACING
    if (dbgout)
    {
        *dbgout << json::object // slot
                << "slot" << objectid(dslot(seg, _target))
				<< "gid" << _target->gid()
                << "limit" << _limit
                << "miny" << _miny
                << "maxy" << _maxy
                << "slicewidth" << _sliceWidth
                << "target" << json::object
                    << "origin" << _target->origin()
                    //<< "currShift" << _currShift
                    << "offsetPrev" << _offsetPrev
                    << "bbox" << seg->theGlyphBBoxTemporary(_target->gid())
                    << "slantBox" << seg->getFace()->glyphs().slant(_target->gid())
                    << "fix" << "kern"
                    << json::close; // target object

        *dbgout << "slices" << json::array;
        for (int is = 0; is < (int)_edges.size(); is++)
        {
            *dbgout << json::flat << json::object
                << "i" << is
                << "targetEdge" << _edges[is]
                << "neighbor" << objectid(dslot(seg, _slotNear[is]))
                << "nearEdge" << _nearEdges[is]
                << json::close;
        }
        *dbgout << json::close; // slices array

        *dbgout
            << "xbound" << _xbound
            << "minGap" << _mingap
            << "needed" << resultNeeded
            << "result" << result
            << "stillBad" << (result != resultNeeded)
            << json::close; // slot object
    }
#endif

    return Position(result, 0.);

}   // end of KernCollider::resolve

void KernCollider::shift(const Position &mv, int dir)
{
    for (Vector<float>::iterator e = _edges.begin(); e != _edges.end(); ++e)
        *e += mv.x;
    _xbound += (1 - 2 * (dir & 1)) * mv.x;
}

////    SLOT-COLLISION    ////

// Initialize the collision attributes for the given slot.
SlotCollision::SlotCollision(Segment *seg, Slot *slot)
{
    initFromSlot(seg, slot);
}

void SlotCollision::initFromSlot(Segment *seg, Slot *slot)
{
    // Initialize slot attributes from glyph attributes.
	// The order here must match the order in the grcompiler code,
	// GrcSymbolTable::AssignInternalGlyphAttrIDs.
    uint16 gid = slot->gid();
    uint16 aCol = seg->silf()->aCollision(); // flags attr ID
    const GlyphFace * glyphFace = seg->getFace()->glyphs().glyphSafe(gid);
    if (!glyphFace)
        return;
    const sparse &p = glyphFace->attrs();
    _flags = p[aCol];
    _limit = Rect(Position(int16(p[aCol+1]), int16(p[aCol+2])),
                  Position(int16(p[aCol+3]), int16(p[aCol+4])));
    _margin = p[aCol+5];
    _marginWt = p[aCol+6];

    _seqClass = p[aCol+7];
	_seqProxClass = p[aCol+8];
    _seqOrder = p[aCol+9];
	_seqAboveXoff = p[aCol+10];
	_seqAboveWt = p[aCol+11];
	_seqBelowXlim = p[aCol+12];
	_seqBelowWt = p[aCol+13];
	_seqValignHt = p[aCol+14];
	_seqValignWt = p[aCol+15];

    // These attributes do not have corresponding glyph attribute:
    _exclGlyph = 0;
    _exclOffset = Position(0, 0);
}

float SlotCollision::getKern(int dir) const
{
    if ((_flags & SlotCollision::COLL_KERN) != 0)
        return float(_shift.x * ((dir & 1) ? -1 : 1));
    else
    	return 0;
}

bool SlotCollision::ignore() const
{
	return ((flags() & SlotCollision::COLL_IGNORE) || (flags() & SlotCollision::COLL_ISSPACE));
}


text:
/*  GRAPHITE2 LICENSING

    Copyright 2010, SIL International
    All rights reserved.

    This library is free software; you can redistribute it and/or modify
    it under the terms of the GNU Lesser General Public License as published
    by the Free Software Foundation; either version 2.1 of License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    Lesser General Public License for more details.

    You should also have received a copy of the GNU Lesser General Public
    License along with this library in the file named "LICENSE".
    If not, write to the Free Software Foundation, 51 Franklin Street,
    Suite 500, Boston, MA 02110-1335, USA or visit their web page on the
    internet at http://www.fsf.org/licenses/lgpl.html.

Alternatively, the contents of this file may be used under the terms of the
Mozilla Public License (http://mozilla.org/MPL) or the GNU General Public
License, as published by the Free Software Foundation, either version 2
of the License or (at your option) any later version.
*/
#include <cstring>
#include "graphite2/Segment.h"
#include "inc/CmapCache.h"
#include "inc/debug.h"
#include "inc/Decompressor.h"
#include "inc/Endian.h"
#include "inc/Face.h"
#include "inc/FileFace.h"
#include "inc/GlyphFace.h"
#include "inc/json.h"
#include "inc/Segment.h"
#include "inc/NameTable.h"
#include "inc/Error.h"

using namespace graphite2;

namespace
{
enum compression
{
    NONE,
    LZ4
};

}

Face::Face(const void* appFaceHandle/*non-NULL*/, const gr_face_ops & ops)
: m_appFaceHandle(appFaceHandle),
  m_pFileFace(NULL),
  m_pGlyphFaceCache(NULL),
  m_cmap(NULL),
  m_pNames(NULL),
  m_logger(NULL),
  m_error(0), m_errcntxt(0),
  m_silfs(NULL),
  m_numSilf(0),
  m_ascent(0),
  m_descent(0)
{
    memset(&m_ops, 0, sizeof m_ops);
    memcpy(&m_ops, &ops, min(sizeof m_ops, ops.size));
}

Face::~Face()
{
    setLogger(0);
    delete m_pGlyphFaceCache;
    delete m_cmap;
    delete[] m_silfs;
#ifndef GRAPHITE2_NFILEFACE
    delete m_pFileFace;
#endif
    delete m_pNames;
}

float Face::default_glyph_advance(const void* font_ptr, gr_uint16 glyphid)
{
    const Font & font = *reinterpret_cast<const Font *>(font_ptr);

    return font.face().glyphs().glyph(glyphid)->theAdvance().x * font.scale();
}

bool Face::readGlyphs(uint32 faceOptions)
{
    Error e;
#ifdef GRAPHITE2_TELEMETRY
    telemetry::category _glyph_cat(tele.glyph);
#endif
    error_context(EC_READGLYPHS);
    m_pGlyphFaceCache = new GlyphCache(*this, faceOptions);

    if (e.test(!m_pGlyphFaceCache, E_OUTOFMEM)
        || e.test(m_pGlyphFaceCache->numGlyphs() == 0, E_NOGLYPHS)
        || e.test(m_pGlyphFaceCache->unitsPerEm() == 0, E_BADUPEM))
    {
        return error(e);
    }

    if (faceOptions & gr_face_cacheCmap)
        m_cmap = new CachedCmap(*this);
    else
        m_cmap = new DirectCmap(*this);
    if (e.test(!m_cmap, E_OUTOFMEM) || e.test(!*m_cmap, E_BADCMAP))
        return error(e);

    if (faceOptions & gr_face_preloadGlyphs)
        nameTable();        // preload the name table along with the glyphs.

    return true;
}

bool Face::readGraphite(const Table & silf)
{
#ifdef GRAPHITE2_TELEMETRY
    telemetry::category _silf_cat(tele.silf);
#endif
    Error e;
    error_context(EC_READSILF);
    const byte * p = silf;
    if (e.test(!p, E_NOSILF) || e.test(silf.size() < 20, E_BADSIZE)) return error(e);

    const uint32 version = be::read<uint32>(p);
    if (e.test(version < 0x00020000, E_TOOOLD)) return error(e);
    if (version >= 0x00030000)
        be::skip<uint32>(p);        // compilerVersion
    m_numSilf = be::read<uint16>(p);

    be::skip<uint16>(p);            // reserved

    bool havePasses = false;
    m_silfs = new Silf[m_numSilf];
    if (e.test(!m_silfs, E_OUTOFMEM)) return error(e);
    for (int i = 0; i < m_numSilf; i++)
    {
        error_context(EC_ASILF + (i << 8));
        const uint32 offset = be::read<uint32>(p),
                     next   = i == m_numSilf - 1 ? uint32(silf.size()) : be::peek<uint32>(p);
        if (e.test(next > silf.size() || offset >= next, E_BADSIZE))
            return error(e);

        if (!m_silfs[i].readGraphite(silf + offset, next - offset, *this, version))
            return false;

        if (m_silfs[i].numPasses())
            havePasses = true;
    }

    return havePasses;
}

bool Face::readFeatures()
{
    return m_Sill.readFace(*this);
}

bool Face::runGraphite(Segment *seg, const Silf *aSilf) const
{
#if !defined GRAPHITE2_NTRACING
    json * dbgout = logger();
    if (dbgout)
    {
        *dbgout << json::object
                    << "id"         << objectid(seg)
                    << "passes"     << json::array;
    }
#endif

//    if ((seg->dir() & 1) != aSilf->dir())
//        seg->reverseSlots();
    if ((seg->dir() & 3) == 3 && aSilf->bidiPass() == 0xFF)
        seg->doMirror(aSilf->aMirror());
    bool res = aSilf->runGraphite(seg, 0, aSilf->positionPass(), true);
    if (res)
    {
        seg->associateChars(0, seg->charInfoCount());
        if (aSilf->flags() & 0x20)
            res &= seg->initCollisions();
        if (res)
            res &= aSilf->runGraphite(seg, aSilf->positionPass(), aSilf->numPasses(), false);
    }

#if !defined GRAPHITE2_NTRACING
    if (dbgout)
{
        seg->positionSlots(0, 0, 0, seg->currdir());
        *dbgout             << json::item
                            << json::close // Close up the passes array
                << "outputdir" << (seg->currdir() ? "rtl" : "ltr")
                << "output" << json::array;
        for(Slot * s = seg->first(); s; s = s->next())
            *dbgout     << dslot(seg, s);
        *dbgout         << json::close
                << "advance" << seg->advance()
                << "chars"   << json::array;
        for(size_t i = 0, n = seg->charInfoCount(); i != n; ++i)
            *dbgout     << json::flat << *seg->charinfo(int(i));
        *dbgout         << json::close  // Close up the chars array
                    << json::close;     // Close up the segment object
    }
#endif

    return res;
}

void Face::setLogger(FILE * log_file GR_MAYBE_UNUSED)
{
#if !defined GRAPHITE2_NTRACING
    delete m_logger;
    m_logger = log_file ? new json(log_file) : 0;
#endif
}

const Silf *Face::chooseSilf(uint32 script) const
{
    if (m_numSilf == 0)
        return NULL;
    else if (m_numSilf == 1 || script == 0)
        return m_silfs;
    else // do more work here
        return m_silfs;
}

uint16 Face::findPseudo(uint32 uid) const
{
    return (m_numSilf) ? m_silfs[0].findPseudo(uid) : 0;
}

int32 Face::getGlyphMetric(uint16 gid, uint8 metric) const
{
    switch (metrics(metric))
    {
        case kgmetAscent : return m_ascent;
        case kgmetDescent : return m_descent;
        default:
            if (gid >= glyphs().numGlyphs()) return 0;
            return glyphs().glyph(gid)->getMetric(metric);
    }
}

void Face::takeFileFace(FileFace* pFileFace GR_MAYBE_UNUSED/*takes ownership*/)
{
#ifndef GRAPHITE2_NFILEFACE
    if (m_pFileFace==pFileFace)
      return;

    delete m_pFileFace;
    m_pFileFace = pFileFace;
#endif
}

NameTable * Face::nameTable() const
{
    if (m_pNames) return m_pNames;
    const Table name(*this, Tag::name);
    if (name)
        m_pNames = new NameTable(name, name.size());
    return m_pNames;
}

uint16 Face::languageForLocale(const char * locale) const
{
    nameTable();
    if (m_pNames)
        return m_pNames->getLanguageId(locale);
    return 0;
}

Face::Table::Table(const Face & face, const Tag n, uint32 version) throw()
: _f(&face), _sz(0), _compressed(false)
{
    _p = static_cast<const byte *>((*_f->m_ops.get_table)(_f->m_appFaceHandle, n, &_sz));

    if (!TtfUtil::CheckTable(n, _p, _sz))
    {
        release();     // Make sure we release the table buffer even if the table failed its checks
        return;
    }

    if (be::peek<uint32>(_p) >= version)
        decompress();
}

void Face::Table::release()
{
    if (_compressed)
        free(const_cast<byte *>(_p));
    else if (_p && _f->m_ops.release_table)
        (*_f->m_ops.release_table)(_f->m_appFaceHandle, _p);
    _p = 0; _sz = 0;
}

Face::Table & Face::Table::operator = (const Table && rhs) throw()
{
    if (this == &rhs)   return *this;
    release();
    new (this) Table(std::move(rhs));
    return *this;
}

Error Face::Table::decompress()
{
    Error e;
    if (e.test(_sz < 5 * sizeof(uint32), E_BADSIZE))
        return e;
    byte * uncompressed_table = 0;
    size_t uncompressed_size = 0;

    const byte * p = _p;
    const uint32 version = be::read<uint32>(p);    // Table version number.

    // The scheme is in the top 5 bits of the 1st uint32.
    const uint32 hdr = be::read<uint32>(p);
    switch(compression(hdr >> 27))
    {
    case NONE: return e;

    case LZ4:
    {
        uncompressed_size  = hdr & 0x07ffffff;
        uncompressed_table = gralloc<byte>(uncompressed_size);
        if (!e.test(!uncompressed_table || uncompressed_size < 4, E_OUTOFMEM))
        {
            memset(uncompressed_table, 0, 4);   // make sure version number is initialised
            // coverity[forward_null : FALSE] - uncompressed_table has been checked so can't be null
            // coverity[checked_return : FALSE] - we test e later
            e.test(lz4::decompress(p, _sz - 2*sizeof(uint32), uncompressed_table, uncompressed_size) != signed(uncompressed_size), E_SHRINKERFAILED);
        }
        break;
    }

    default:
        e.error(E_BADSCHEME);
    };

    // Check the uncompressed version number against the original.
    if (!e)
        // coverity[forward_null : FALSE] - uncompressed_table has already been tested so can't be null
        // coverity[checked_return : FALSE] - we test e later
        e.test(be::peek<uint32>(uncompressed_table) != version, E_SHRINKERFAILED);

    // Tell the provider to release the compressed form since were replacing
    //   it anyway.
    release();

    if (e)
    {
        free(uncompressed_table);
        uncompressed_table = 0;
        uncompressed_size  = 0;
    }

    _p = uncompressed_table;
    _sz = uncompressed_size;
    _compressed = true;

    return e;
}

repo_language: C

mime_type: text/x-c


text:
/*  GRAPHITE2 LICENSING

    Copyright 2010, SIL International
    All rights reserved.

    This library is free software; you can redistribute it and/or modify
    it under the terms of the GNU Lesser General Public License as published
    by the Free Software Foundation; either version 2.1 of License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    Lesser General Public License for more details.

    You should also have received a copy of the GNU Lesser General Public
    License along with this library in the file named "LICENSE".
    If not, write to the Free Software Foundation, 51 Franklin Street,
    Suite 500, Boston, MA 02110-1335, USA or visit their web page on the
    internet at http://www.fsf.org/licenses/lgpl.html.

Alternatively, the contents of this file may be used under the terms of the
Mozilla Public License (http://mozilla.org/MPL) or the GNU General Public
License, as published by the Free Software Foundation, either version 2
of the License or (at your option) any later version.
*/
#include <cstdlib>
#include "graphite2/Segment.h"
#include "inc/debug.h"
#include "inc/Endian.h"
#include "inc/Silf.h"
#include "inc/Segment.h"
#include "inc/Rule.h"
#include "inc/Error.h"

using namespace graphite2;

namespace { static const uint32 ERROROFFSET = 0xFFFFFFFF; }

Silf::Silf() throw()
: m_passes(0),
  m_pseudos(0),
  m_classOffsets(0),
  m_classData(0),
  m_justs(0),
  m_numPasses(0),
  m_numJusts(0),
  m_sPass(0),
  m_pPass(0),
  m_jPass(0),
  m_bPass(0),
  m_flags(0),
  m_dir(0),
  m_aPseudo(0),
  m_aBreak(0),
  m_aUser(0),
  m_aBidi(0),
  m_aMirror(0),
  m_aPassBits(0),
  m_iMaxComp(0),
  m_aCollision(0),
  m_aLig(0),
  m_numPseudo(0),
  m_nClass(0),
  m_nLinear(0),
  m_gEndLine(0)
{
    memset(&m_silfinfo, 0, sizeof m_silfinfo);
}

Silf::~Silf() throw()
{
    releaseBuffers();
}

void Silf::releaseBuffers() throw()
{
    delete [] m_passes;
    delete [] m_pseudos;
    free(m_classOffsets);
    free(m_classData);
    free(m_justs);
    m_passes= 0;
    m_pseudos = 0;
    m_classOffsets = 0;
    m_classData = 0;
    m_justs = 0;
}

bool Silf::readGraphite(const byte * const silf_start, size_t lSilf, Face& face, uint32 version)
{
    const byte * p = silf_start,
               * const silf_end = p + lSilf;
    Error e;

    if (e.test(version >= 0x00060000, E_BADSILFVERSION))
    {
        releaseBuffers(); return face.error(e);
    }
    if (version >= 0x00030000)
    {
        if (e.test(lSilf < 28, E_BADSIZE)) { releaseBuffers(); return face.error(e); }
        be::skip<int32>(p);    // ruleVersion
        be::skip<uint16>(p,2); // passOffset & pseudosOffset
    }
    else if (e.test(lSilf < 20, E_BADSIZE)) { releaseBuffers(); return face.error(e); }
    const uint16 maxGlyph = be::read<uint16>(p);
    m_silfinfo.extra_ascent = be::read<uint16>(p);
    m_silfinfo.extra_descent = be::read<uint16>(p);
    m_numPasses = be::read<uint8>(p);
    m_sPass     = be::read<uint8>(p);
    m_pPass     = be::read<uint8>(p);
    m_jPass     = be::read<uint8>(p);
    m_bPass     = be::read<uint8>(p);
    m_flags     = be::read<uint8>(p);
    be::skip<uint8>(p,2); //  max{Pre,Post}Context.
    m_aPseudo   = be::read<uint8>(p);
    m_aBreak    = be::read<uint8>(p);
    m_aBidi     = be::read<uint8>(p);
    m_aMirror   = be::read<uint8>(p);
    m_aPassBits = be::read<uint8>(p);

    // Read Justification levels.
    m_numJusts  = be::read<uint8>(p);
    if (e.test(maxGlyph >= face.glyphs().numGlyphs(), E_BADMAXGLYPH)
        || e.test(p + m_numJusts * 8 >= silf_end, E_BADNUMJUSTS))
    {
        releaseBuffers(); return face.error(e);
    }

    if (m_numJusts)
    {
        m_justs = gralloc<Justinfo>(m_numJusts);
        if (e.test(!m_justs, E_OUTOFMEM)) return face.error(e);

        for (uint8 i = 0; i < m_numJusts; i++)
        {
            ::new(m_justs + i) Justinfo(p[0], p[1], p[2], p[3]);
            be::skip<byte>(p,8);
        }
    }

    if (e.test(p + sizeof(uint16) + sizeof(uint8)*8 >= silf_end, E_BADENDJUSTS)) { releaseBuffers(); return face.error(e); }
    m_aLig       = be::read<uint16>(p);
    m_aUser      = be::read<uint8>(p);
    m_iMaxComp   = be::read<uint8>(p);
    m_dir        = be::read<uint8>(p) - 1;
    m_aCollision = be::read<uint8>(p);
    be::skip<byte>(p,3);
    be::skip<uint16>(p, be::read<uint8>(p));    // don't need critical features yet
    be::skip<byte>(p);                          // reserved
    if (e.test(p >= silf_end, E_BADCRITFEATURES))   { releaseBuffers(); return face.error(e); }
    be::skip<uint32>(p, be::read<uint8>(p));    // don't use scriptTag array.
    if (e.test(p + sizeof(uint16) + sizeof(uint32) >= silf_end, E_BADSCRIPTTAGS)) { releaseBuffers(); return face.error(e); }
    m_gEndLine  = be::read<uint16>(p);          // lbGID
    const byte * o_passes = p;
    uint32 passes_start = be::read<uint32>(p);

    const size_t num_attrs = face.glyphs().numAttrs();
    if (e.test(m_aPseudo   >= num_attrs, E_BADAPSEUDO)
        || e.test(m_aBreak >= num_attrs, E_BADABREAK)
        || e.test(m_aBidi  >= num_attrs, E_BADABIDI)
        || e.test(m_aMirror>= num_attrs, E_BADAMIRROR)
        || e.test(m_aCollision && m_aCollision >= num_attrs - 5, E_BADACOLLISION)
        || e.test(m_numPasses > 128, E_BADNUMPASSES) || e.test(passes_start >= lSilf, E_BADPASSESSTART)
        || e.test(m_pPass < m_sPass, E_BADPASSBOUND) || e.test(m_pPass > m_numPasses, E_BADPPASS) || e.test(m_sPass > m_numPasses, E_BADSPASS)
        || e.test(m_jPass < m_pPass, E_BADJPASSBOUND) || e.test(m_jPass > m_numPasses, E_BADJPASS)
        || e.test((m_bPass != 0xFF && (m_bPass < m_jPass || m_bPass > m_numPasses)), E_BADBPASS)
        || e.test(m_aLig > 127, E_BADALIG))
    {
        releaseBuffers();
        return face.error(e);
    }
    be::skip<uint32>(p, m_numPasses);
    if (e.test(unsigned(p - silf_start) + sizeof(uint16) >= passes_start, E_BADPASSESSTART)) { releaseBuffers(); return face.error(e); }
    m_numPseudo = be::read<uint16>(p);
    be::skip<uint16>(p, 3); // searchPseudo, pseudoSelector, pseudoShift
    m_pseudos = new Pseudo[m_numPseudo];
    if (e.test(unsigned(p - silf_start) + m_numPseudo*(sizeof(uint32) + sizeof(uint16)) >= passes_start, E_BADNUMPSEUDO)
        || e.test(!m_pseudos, E_OUTOFMEM))
    {
        releaseBuffers(); return face.error(e);
    }
    for (int i = 0; i < m_numPseudo; i++)
    {
        m_pseudos[i].uid = be::read<uint32>(p);
        m_pseudos[i].gid = be::read<uint16>(p);
    }

    const size_t clen = readClassMap(p, passes_start + silf_start - p, version, e);
    m_passes = new Pass[m_numPasses];
    if (e || e.test(clen > unsigned(passes_start + silf_start - p), E_BADPASSESSTART)
          || e.test(!m_passes, E_OUTOFMEM))
    { releaseBuffers(); return face.error(e); }

    for (size_t i = 0; i < m_numPasses; ++i)
    {
        uint32 pass_start = be::read<uint32>(o_passes);
        uint32 pass_end = be::peek<uint32>(o_passes);
        face.error_context((face.error_context() & 0xFF00) + EC_ASILF + unsigned(i << 16));
        if (e.test(pass_start > pass_end, E_BADPASSSTART)
                || e.test(pass_start < passes_start, E_BADPASSSTART)
                || e.test(pass_end > lSilf, E_BADPASSEND)) {
            releaseBuffers(); return face.error(e);
        }

        enum passtype pt = PASS_TYPE_UNKNOWN;
        if (i >= m_jPass) pt = PASS_TYPE_JUSTIFICATION;
        else if (i >= m_pPass) pt = PASS_TYPE_POSITIONING;
        else if (i >= m_sPass) pt = PASS_TYPE_SUBSTITUTE;
        else pt = PASS_TYPE_LINEBREAK;

        m_passes[i].init(this);
        if (!m_passes[i].readPass(silf_start + pass_start, pass_end - pass_start, pass_start, face, pt,
            version, e))
        {
            releaseBuffers();
            return false;
        }
    }

    // fill in gr_faceinfo
    m_silfinfo.upem = face.glyphs().unitsPerEm();
    m_silfinfo.has_bidi_pass = (m_bPass != 0xFF);
    m_silfinfo.justifies = (m_numJusts != 0) || (m_jPass < m_pPass);
    m_silfinfo.line_ends = (m_flags & 1);
    m_silfinfo.space_contextuals = gr_faceinfo::gr_space_contextuals((m_flags >> 2) & 0x7);
    return true;
}

template<typename T> inline uint32 Silf::readClassOffsets(const byte *&p, size_t data_len, Error &e)
{
    const T cls_off = 2*sizeof(uint16) + sizeof(T)*(m_nClass+1);
    const uint32 max_off = (be::peek<T>(p + sizeof(T)*m_nClass) - cls_off)/sizeof(uint16);
    // Check that the last+1 offset is less than or equal to the class map length.
    if (e.test(be::peek<T>(p) != cls_off, E_MISALIGNEDCLASSES)
            || e.test(max_off > (data_len - cls_off)/sizeof(uint16), E_HIGHCLASSOFFSET))
        return ERROROFFSET;

    // Read in all the offsets.
    m_classOffsets = gralloc<uint32>(m_nClass+1);
    if (e.test(!m_classOffsets, E_OUTOFMEM)) return ERROROFFSET;
    for (uint32 * o = m_classOffsets, * const o_end = o + m_nClass + 1; o != o_end; ++o)
    {
        *o = (be::read<T>(p) - cls_off)/sizeof(uint16);
        if (e.test(*o > max_off, E_HIGHCLASSOFFSET))
            return ERROROFFSET;
    }
    return max_off;
}

size_t Silf::readClassMap(const byte *p, size_t data_len, uint32 version, Error &e)
{
    if (e.test(data_len < sizeof(uint16)*2, E_BADCLASSSIZE)) return ERROROFFSET;

    m_nClass  = be::read<uint16>(p);
    m_nLinear = be::read<uint16>(p);

    // Check that numLinear < numClass,
    // that there is at least enough data for numClasses offsets.
    if (e.test(m_nLinear > m_nClass, E_TOOMANYLINEAR)
     || e.test((m_nClass + 1) * (version >= 0x00040000 ? sizeof(uint32) : sizeof(uint16)) > (data_len - 4), E_CLASSESTOOBIG))
        return ERROROFFSET;

    uint32 max_off;
    if (version >= 0x00040000)
        max_off = readClassOffsets<uint32>(p, data_len, e);
    else
        max_off = readClassOffsets<uint16>(p, data_len, e);

    if (max_off == ERROROFFSET) return ERROROFFSET;

    if (e.test((int)max_off < m_nLinear + (m_nClass - m_nLinear) * 6, E_CLASSESTOOBIG))
        return ERROROFFSET;

    // Check the linear offsets are sane, these must be monotonically increasing.
    assert(m_nClass >= m_nLinear);
    for (const uint32 *o = m_classOffsets, * const o_end = o + m_nLinear; o != o_end; ++o)
        if (e.test(o[0] > o[1], E_BADCLASSOFFSET))
            return ERROROFFSET;

    // Fortunately the class data is all uint16s so we can decode these now
    m_classData = gralloc<uint16>(max_off);
    if (e.test(!m_classData, E_OUTOFMEM)) return ERROROFFSET;
    for (uint16 *d = m_classData, * const d_end = d + max_off; d != d_end; ++d)
        *d = be::read<uint16>(p);

    // Check the lookup class invariants for each non-linear class
    for (const uint32 *o = m_classOffsets + m_nLinear, * const o_end = m_classOffsets + m_nClass; o != o_end; ++o)
    {
        const uint16 * lookup = m_classData + *o;
        if (e.test(*o + 4 > max_off, E_HIGHCLASSOFFSET)                        // LookupClass doesn't stretch over max_off
         || e.test(lookup[0] == 0                                                   // A LookupClass with no looks is a suspicious thing ...
                    || lookup[0] * 2 + *o + 4 > max_off                             // numIDs lookup pairs fits within (start of LookupClass' lookups array, max_off]
                    || lookup[3] + lookup[1] != lookup[0], E_BADCLASSLOOKUPINFO)    // rangeShift:   numIDs  - searchRange
         || e.test(((o[1] - *o) & 1) != 0, ERROROFFSET))                         // glyphs are in pairs so difference must be even.
            return ERROROFFSET;
    }

    return max_off;
}

uint16 Silf::findPseudo(uint32 uid) const
{
    for (int i = 0; i < m_numPseudo; i++)
        if (m_pseudos[i].uid == uid) return m_pseudos[i].gid;
    return 0;
}

uint16 Silf::findClassIndex(uint16 cid, uint16 gid) const
{
    if (cid > m_nClass) return -1;

    const uint16 * cls = m_classData + m_classOffsets[cid];
    if (cid < m_nLinear)        // output class being used for input, shouldn't happen
    {
        for (unsigned int i = 0, n = m_classOffsets[cid + 1] - m_classOffsets[cid]; i < n; ++i, ++cls)
            if (*cls == gid) return i;
        return -1;
    }
    else
    {
        const uint16 *  min = cls + 4,      // lookups array
                     *  max = min + cls[0]*2; // lookups aray is numIDs (cls[0]) uint16 pairs long
        do
        {
            const uint16 * p = min + (-2 & ((max-min)/2));
            if  (p[0] > gid)    max = p;
            else                min = p;
        }
        while (max - min > 2);
        return min[0] == gid ? min[1] : -1;
    }
}

uint16 Silf::getClassGlyph(uint16 cid, unsigned int index) const
{
    if (cid > m_nClass) return 0;

    uint32 loc = m_classOffsets[cid];
    if (cid < m_nLinear)
    {
        if (index < m_classOffsets[cid + 1] - loc)
            return m_classData[index + loc];
    }
    else        // input class being used for output. Shouldn't happen
    {
        for (unsigned int i = loc + 4; i < m_classOffsets[cid + 1]; i += 2)
            if (m_classData[i + 1] == index) return m_classData[i];
    }
    return 0;
}

bool Silf::runGraphite(Segment *seg, uint8 firstPass, uint8 lastPass, int dobidi) const
{
    assert(seg != 0);
    size_t             maxSize = seg->slotCount() * MAX_SEG_GROWTH_FACTOR;
    SlotMap            map(*seg, m_dir, maxSize);
    FiniteStateMachine fsm(map, seg->getFace()->logger());
    vm::Machine        m(map);
    uint8              lbidi = m_bPass;
#if !defined GRAPHITE2_NTRACING
    json * const dbgout = seg->getFace()->logger();
#endif

    if (lastPass == 0)
    {
        if (firstPass == lastPass && lbidi == 0xFF)
            return true;
        lastPass = m_numPasses;
    }
    if ((firstPass < lbidi || (dobidi && firstPass == lbidi)) && (lastPass >= lbidi || (dobidi && lastPass + 1 == lbidi)))
        lastPass++;
    else
        lbidi = 0xFF;

    for (size_t i = firstPass; i < lastPass; ++i)
    {
        // bidi and mirroring
        if (i == lbidi)
        {
#if !defined GRAPHITE2_NTRACING
            if (dbgout)
            {
                *dbgout << json::item << json::object
//							<< "pindex" << i   // for debugging
                            << "id"     << -1
                            << "slotsdir" << (seg->currdir() ? "rtl" : "ltr")
                            << "passdir" << (m_dir & 1 ? "rtl" : "ltr")
                            << "slots"  << json::array;
                seg->positionSlots(0, 0, 0, seg->currdir());
                for(Slot * s = seg->first(); s; s = s->next())
                    *dbgout     << dslot(seg, s);
                *dbgout         << json::close
                            << "rules"  << json::array << json::close
                            << json::close;
            }
#endif
            if (seg->currdir() != (m_dir & 1))
                seg->reverseSlots();
            if (m_aMirror && (seg->dir() & 3) == 3)
                seg->doMirror(m_aMirror);
        --i;
        lbidi = lastPass;
        --lastPass;
        continue;
        }

#if !defined GRAPHITE2_NTRACING
        if (dbgout)
        {
            *dbgout << json::item << json::object
//						<< "pindex" << i   // for debugging
                        << "id"     << i+1
                        << "slotsdir" << (seg->currdir() ? "rtl" : "ltr")
                        << "passdir" << ((m_dir & 1) ^ m_passes[i].reverseDir() ? "rtl" : "ltr")
                        << "slots"  << json::array;
            seg->positionSlots(0, 0, 0, seg->currdir());
            for(Slot * s = seg->first(); s; s = s->next())
                *dbgout     << dslot(seg, s);
            *dbgout         << json::close;
        }
#endif

        // test whether to reorder, prepare for positioning
        bool reverse = (lbidi == 0xFF) && (seg->currdir() != ((m_dir & 1) ^ m_passes[i].reverseDir()));
        if ((i >= 32 || (seg->passBits() & (1 << i)) == 0 || m_passes[i].collisionLoops())
                && !m_passes[i].runGraphite(m, fsm, reverse))
            return false;
        // only subsitution passes can change segment length, cached subsegments are short for their text
        if (m.status() != vm::Machine::finished
            || (seg->slotCount() && seg->slotCount() > maxSize))
            return false;
    }
    return true;
}


text:
#    GRAPHITE2 LICENSING
#
#    Copyright 2010, SIL International
#    All rights reserved.
#
#    This library is free software; you can redistribute it and/or modify
#    it under the terms of the GNU Lesser General Public License as published
#    by the Free Software Foundation; either version 2.1 of License, or
#    (at your option) any later version.
#
#    This program is distributed in the hope that it will be useful,
#    but WITHOUT ANY WARRANTY; without even the implied warranty of
#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
#    Lesser General Public License for more details.
#
#    You should also have received a copy of the GNU Lesser General Public
#    License along with this library in the file named "LICENSE".
#    If not, write to the Free Software Foundation, 51 Franklin Street,
#    Suite 500, Boston, MA 02110-1335, USA or visit their web page on the
#    internet at http://www.fsf.org/licenses/lgpl.html.

CMAKE_MINIMUM_REQUIRED(VERSION 2.8.0 FATAL_ERROR)
project(graphite2_core)
cmake_policy(SET CMP0012 NEW)
INCLUDE(CheckCXXSourceCompiles)

set(GRAPHITE_API_CURRENT 3)
set(GRAPHITE_API_REVISION 2)
set(GRAPHITE_API_AGE 1)
set(GRAPHITE_VERSION ${GRAPHITE_API_CURRENT}.${GRAPHITE_API_REVISION}.${GRAPHITE_API_AGE})
set(GRAPHITE_SO_VERSION ${GRAPHITE_API_CURRENT})

include(TestBigEndian)

include_directories(${PROJECT_SOURCE_DIR})

set(FILEFACE FileFace.cpp)
if (GRAPHITE2_NFILEFACE)
    add_definitions(-DGRAPHITE2_NFILEFACE)
    set(FILEFACE)
endif()

set(TRACING json.cpp)
if (GRAPHITE2_NTRACING)
    add_definitions(-DGRAPHITE2_NTRACING)
    set(TRACING)
endif()

if (GRAPHITE2_TELEMETRY)
    add_definitions(-DGRAPHITE2_TELEMETRY)
endif()

if (NOT BUILD_SHARED_LIBS)
    add_definitions(-DGRAPHITE2_STATIC)
endif()

set(GRAPHITE_HEADERS
    ../include/graphite2/Font.h
    ../include/graphite2/Segment.h
    ../include/graphite2/Types.h
    ../include/graphite2/Log.h
    )

file(GLOB PRIVATE_HEADERS inc/*.h)

add_library(graphite2
    ${GRAPHITE2_VM_TYPE}_machine.cpp
    gr_char_info.cpp
    gr_features.cpp
    gr_face.cpp
    gr_font.cpp
    gr_logging.cpp
    gr_segment.cpp
    gr_slot.cpp
    CmapCache.cpp
    Code.cpp
    Collider.cpp
    Decompressor.cpp
    Face.cpp
    FeatureMap.cpp
    Font.cpp
    GlyphFace.cpp
    GlyphCache.cpp
    Intervals.cpp
    Justifier.cpp
    NameTable.cpp
    Pass.cpp
    Position.cpp
    Segment.cpp
    Silf.cpp
    Slot.cpp
    Sparse.cpp
    TtfUtil.cpp
    UtfCodec.cpp
    ${FILEFACE}
    ${TRACING})

set_target_properties(graphite2 PROPERTIES  PUBLIC_HEADER "${GRAPHITE_HEADERS}"
                                            SOVERSION ${GRAPHITE_SO_VERSION}
                                            VERSION ${GRAPHITE_VERSION}
                                            LT_VERSION_CURRENT ${GRAPHITE_API_CURRENT}
                                            LT_VERSION_REVISION ${GRAPHITE_API_REVISION}
                                            LT_VERSION_AGE ${GRAPHITE_API_AGE})

if  (${CMAKE_SYSTEM_NAME} STREQUAL "Linux")
    set_target_properties(graphite2 PROPERTIES
        COMPILE_FLAGS   "-Wall -Wextra -Wno-unknown-pragmas -Wendif-labels -Wshadow -Wctor-dtor-privacy -Wnon-virtual-dtor -fno-rtti -fno-exceptions -fvisibility=hidden -fvisibility-inlines-hidden"
        LINK_FLAGS      "-nodefaultlibs ${GRAPHITE_LINK_FLAGS}"
        LINKER_LANGUAGE C)
    if (${CMAKE_SYSTEM_PROCESSOR} MATCHES "x86|i.86")
        add_definitions(-mfpmath=sse -msse2)
    endif()
    if (CMAKE_COMPILER_IS_GNUCXX)
        add_definitions(-Wno-class-memaccess -Wdouble-promotion)
    endif()
    message(STATUS "Compiler ID is: ${CMAKE_CXX_COMPILER_ID}")
    if (${CMAKE_CXX_COMPILER_ID} STREQUAL "Clang")
        add_definitions(-Wimplicit-fallthrough -Wshorten-64-to-32)
    endif()
    if (${CMAKE_CXX_COMPILER} MATCHES  ".*mingw.*")
        target_link_libraries(graphite2 kernel32 msvcr90 mingw32 gcc user32)
    else (${CMAKE_CXX_COMPILER} MATCHES  ".*mingw.*")
        if (GRAPHITE2_SANITIZERS)
            target_link_libraries(graphite2 c gcc_s)
        else ()
            target_link_libraries(graphite2 c gcc)
        endif ()
    endif()
    include(Graphite)
    if (BUILD_SHARED_LIBS)
        nolib_test(stdc++ $<TARGET_SONAME_FILE:graphite2>)
    endif ()
    set(CMAKE_CXX_IMPLICIT_LINK_LIBRARIES "")
    CREATE_LIBTOOL_FILE(graphite2 "/lib${LIB_SUFFIX}")
endif()

if  (${CMAKE_SYSTEM_NAME} STREQUAL "Darwin")
    set_target_properties(graphite2 PROPERTIES
        COMPILE_FLAGS   "-Wall -Wextra -Wno-unknown-pragmas -Wimplicit-fallthrough -Wendif-labels -Wshadow -Wno-ctor-dtor-privacy -Wno-non-virtual-dtor -fno-rtti -fno-exceptions -fvisibility=hidden -fvisibility-inlines-hidden"
        LINK_FLAGS      "-nodefaultlibs"
        LINKER_LANGUAGE C)
    if (${CMAKE_SYSTEM_PROCESSOR} MATCHES "x86|i.86")
        add_definitions(-mfpmath=sse -msse2)
    endif()
    target_link_libraries(graphite2 c)
    include(Graphite)
    nolib_test(stdc++ $<TARGET_SONAME_FILE:graphite2>)
    set(CMAKE_CXX_IMPLICIT_LINK_LIBRARIES "")
    CREATE_LIBTOOL_FILE(graphite2 "/lib${LIB_SUFFIX}")
endif()

if  (${CMAKE_SYSTEM_NAME} STREQUAL "Windows")
    set_target_properties(graphite2 PROPERTIES
        COMPILE_DEFINITIONS "_SCL_SECURE_NO_WARNINGS;_CRT_SECURE_NO_WARNINGS;UNICODE;GRAPHITE2_EXPORTING")
endif()

install(TARGETS graphite2 EXPORT graphite2 LIBRARY DESTINATION lib${LIB_SUFFIX} ARCHIVE DESTINATION lib${LIB_SUFFIX} PUBLIC_HEADER DESTINATION include/graphite2 RUNTIME DESTINATION bin)
install(EXPORT graphite2 DESTINATION share/graphite2 NAMESPACE gr2_)


text:
/*  GRAPHITE2 LICENSING

    Copyright 2010, SIL International
    All rights reserved.

    This library is free software; you can redistribute it and/or modify
    it under the terms of the GNU Lesser General Public License as published
    by the Free Software Foundation; either version 2.1 of License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    Lesser General Public License for more details.

    You should also have received a copy of the GNU Lesser General Public
    License along with this library in the file named "LICENSE".
    If not, write to the Free Software Foundation, 51 Franklin Street,
    Suite 500, Boston, MA 02110-1335, USA or visit their web page on the
    internet at http://www.fsf.org/licenses/lgpl.html.

Alternatively, the contents of this file may be used under the terms of the
Mozilla Public License (http://mozilla.org/MPL) or the GNU General Public
License, as published by the Free Software Foundation, either version 2
of the License or (at your option) any later version.
*/
#include "graphite2/Segment.h"
#include "inc/UtfCodec.h"
#include "inc/Segment.h"

using namespace graphite2;

namespace
{

  gr_segment* makeAndInitialize(const Font *font, const Face *face, uint32 script, const Features* pFeats/*must not be NULL*/, gr_encform enc, const void* pStart, size_t nChars, int dir)
  {
      if (script == 0x20202020) script = 0;
      else if ((script & 0x00FFFFFF) == 0x00202020) script = script & 0xFF000000;
      else if ((script & 0x0000FFFF) == 0x00002020) script = script & 0xFFFF0000;
      else if ((script & 0x000000FF) == 0x00000020) script = script & 0xFFFFFF00;
      // if (!font) return NULL;
      Segment* pRes=new Segment(nChars, face, script, dir);

      if (!pRes->read_text(face, pFeats, enc, pStart, nChars) || !pRes->runGraphite())
      {
        delete pRes;
        return NULL;
      }
      pRes->finalise(font, true);

      return static_cast<gr_segment*>(pRes);
  }

  template <typename utf_iter>
  inline size_t count_unicode_chars(utf_iter first, const utf_iter last, const void **error)
  {
      size_t n_chars = 0;
      uint32 usv = 0;

      if (last)
      {
          if (!first.validate(last))
          {
              if (error)  *error = last - 1;
              return 0;
          }
          for (;first != last; ++first, ++n_chars)
              if ((usv = *first) == 0 || first.error()) break;
      }
      else
      {
          while ((usv = *first) != 0 && !first.error())
          {
              ++first;
              ++n_chars;
          }
      }

      if (error)  *error = first.error() ? first : 0;
      return n_chars;
  }
}

extern "C" {

size_t gr_count_unicode_characters(gr_encform enc, const void* buffer_begin, const void* buffer_end/*don't go on or past end, If NULL then ignored*/, const void** pError)   //Also stops on nul. Any nul is not in the count
{
    assert(buffer_begin);

    switch (enc)
    {
    case gr_utf8:   return count_unicode_chars<utf8::const_iterator>(buffer_begin, buffer_end, pError); break;
    case gr_utf16:  return count_unicode_chars<utf16::const_iterator>(buffer_begin, buffer_end, pError); break;
    case gr_utf32:  return count_unicode_chars<utf32::const_iterator>(buffer_begin, buffer_end, pError); break;
    default:        return 0;
    }
}

gr_segment* gr_make_seg(const gr_font *font, const gr_face *face, gr_uint32 script, const gr_feature_val* pFeats, gr_encform enc, const void* pStart, size_t nChars, int dir)
{
    if (!face) return nullptr;

    const gr_feature_val * tmp_feats = 0;
    if (pFeats == 0)
        pFeats = tmp_feats = static_cast<const gr_feature_val*>(face->theSill().cloneFeatures(0));
    gr_segment * seg = makeAndInitialize(font, face, script, pFeats, enc, pStart, nChars, dir);
    delete static_cast<const FeatureVal*>(tmp_feats);

    return seg;
}

void gr_seg_destroy(gr_segment* p)
{
    delete static_cast<Segment*>(p);
}

float gr_seg_advance_X(const gr_segment* pSeg/*not NULL*/)
{
    assert(pSeg);
    return pSeg->advance().x;
}

float gr_seg_advance_Y(const gr_segment* pSeg/*not NULL*/)
{
    assert(pSeg);
    return pSeg->advance().y;
}

unsigned int gr_seg_n_cinfo(const gr_segment* pSeg/*not NULL*/)
{
    assert(pSeg);
    return static_cast<unsigned int>(pSeg->charInfoCount());
}

const gr_char_info* gr_seg_cinfo(const gr_segment* pSeg/*not NULL*/, unsigned int index/*must be <number_of_CharInfo*/)
{
    assert(pSeg);
    return static_cast<const gr_char_info*>(pSeg->charinfo(index));
}

unsigned int gr_seg_n_slots(const gr_segment* pSeg/*not NULL*/)
{
    assert(pSeg);
    return static_cast<unsigned int>(pSeg->slotCount());
}

const gr_slot* gr_seg_first_slot(gr_segment* pSeg/*not NULL*/)
{
    assert(pSeg);
    return static_cast<const gr_slot*>(pSeg->first());
}

const gr_slot* gr_seg_last_slot(gr_segment* pSeg/*not NULL*/)
{
    assert(pSeg);
    return static_cast<const gr_slot*>(pSeg->last());
}

float gr_seg_justify(gr_segment* pSeg/*not NULL*/, const gr_slot* pSlot/*not NULL*/, const gr_font *pFont, double width, enum gr_justFlags flags, const gr_slot *pFirst, const gr_slot *pLast)
{
    assert(pSeg);
    assert(pSlot);
    return pSeg->justify(const_cast<gr_slot *>(pSlot), pFont, float(width), justFlags(flags), const_cast<gr_slot *>(pFirst), const_cast<gr_slot *>(pLast));
}

} // extern "C"


text:
/*  GRAPHITE2 LICENSING

    Copyright 2010, SIL International
    All rights reserved.

    This library is free software; you can redistribute it and/or modify
    it under the terms of the GNU Lesser General Public License as published
    by the Free Software Foundation; either version 2.1 of License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    Lesser General Public License for more details.

    You should also have received a copy of the GNU Lesser General Public
    License along with this library in the file named "LICENSE".
    If not, write to the Free Software Foundation, 51 Franklin Street,
    Suite 500, Boston, MA 02110-1335, USA or visit their web page on the
    internet at http://www.fsf.org/licenses/lgpl.html.

Alternatively, the contents of this file may be used under the terms of the
Mozilla Public License (http://mozilla.org/MPL) or the GNU General Public
License, as published by the Free Software Foundation, either version 2
of the License or (at your option) any later version.
*/
#include "inc/UtfCodec.h"
#include <cstring>
#include <cstdlib>

#include "inc/bits.h"
#include "inc/Segment.h"
#include "graphite2/Font.h"
#include "inc/CharInfo.h"
#include "inc/debug.h"
#include "inc/Slot.h"
#include "inc/Main.h"
#include "inc/CmapCache.h"
#include "inc/Collider.h"
#include "graphite2/Segment.h"

using namespace graphite2;

Segment::Segment(size_t numchars, const Face* face, uint32 script, int textDir)
: m_freeSlots(NULL),
  m_freeJustifies(NULL),
  m_charinfo(new CharInfo[numchars]),
  m_collisions(NULL),
  m_face(face),
  m_silf(face->chooseSilf(script)),
  m_first(NULL),
  m_last(NULL),
  m_bufSize(numchars + 10),
  m_numGlyphs(numchars),
  m_numCharinfo(numchars),
  m_defaultOriginal(0),
  m_dir(textDir),
  m_flags(((m_silf->flags() & 0x20) != 0) << 1),
  m_passBits(m_silf->aPassBits() ? -1 : 0)
{
    freeSlot(newSlot());
    m_bufSize = log_binary(numchars)+1;
}

Segment::~Segment()
{
    for (SlotRope::iterator i = m_slots.begin(); i != m_slots.end(); ++i)
        free(*i);
    for (AttributeRope::iterator i = m_userAttrs.begin(); i != m_userAttrs.end(); ++i)
        free(*i);
    for (JustifyRope::iterator i = m_justifies.begin(); i != m_justifies.end(); ++i)
        free(*i);
    delete[] m_charinfo;
    free(m_collisions);
}

void Segment::appendSlot(int id, int cid, int gid, int iFeats, size_t coffset)
{
    Slot *aSlot = newSlot();

    if (!aSlot) return;
    m_charinfo[id].init(cid);
    m_charinfo[id].feats(iFeats);
    m_charinfo[id].base(coffset);
    const GlyphFace * theGlyph = m_face->glyphs().glyphSafe(gid);
    m_charinfo[id].breakWeight(theGlyph ? theGlyph->attrs()[m_silf->aBreak()] : 0);

    aSlot->child(NULL);
    aSlot->setGlyph(this, gid, theGlyph);
    aSlot->originate(id);
    aSlot->before(id);
    aSlot->after(id);
    if (m_last) m_last->next(aSlot);
    aSlot->prev(m_last);
    m_last = aSlot;
    if (!m_first) m_first = aSlot;
    if (theGlyph && m_silf->aPassBits())
        m_passBits &= theGlyph->attrs()[m_silf->aPassBits()]
                    | (m_silf->numPasses() > 16 ? (theGlyph->attrs()[m_silf->aPassBits() + 1] << 16) : 0);
}

Slot *Segment::newSlot()
{
    if (!m_freeSlots)
    {
        // check that the segment doesn't grow indefinintely
        if (m_numGlyphs > m_numCharinfo * MAX_SEG_GROWTH_FACTOR)
            return NULL;
        int numUser = m_silf->numUser();
#if !defined GRAPHITE2_NTRACING
        if (m_face->logger()) ++numUser;
#endif
        Slot *newSlots = grzeroalloc<Slot>(m_bufSize);
        int16 *newAttrs = grzeroalloc<int16>(m_bufSize * numUser);
        if (!newSlots || !newAttrs)
        {
            free(newSlots);
            free(newAttrs);
            return NULL;
        }
        for (size_t i = 0; i < m_bufSize; i++)
        {
            ::new (newSlots + i) Slot(newAttrs + i * numUser);
            newSlots[i].next(newSlots + i + 1);
        }
        newSlots[m_bufSize - 1].next(NULL);
        newSlots[0].next(NULL);
        m_slots.push_back(newSlots);
        m_userAttrs.push_back(newAttrs);
        m_freeSlots = (m_bufSize > 1)? newSlots + 1 : NULL;
        return newSlots;
    }
    Slot *res = m_freeSlots;
    m_freeSlots = m_freeSlots->next();
    res->next(NULL);
    return res;
}

void Segment::freeSlot(Slot *aSlot)
{
    if (aSlot == nullptr) return;
    if (m_last == aSlot) m_last = aSlot->prev();
    if (m_first == aSlot) m_first = aSlot->next();
    if (aSlot->attachedTo())
        aSlot->attachedTo()->removeChild(aSlot);
    while (aSlot->firstChild())
    {
        if (aSlot->firstChild()->attachedTo() == aSlot)
        {
            aSlot->firstChild()->attachTo(nullptr);
            aSlot->removeChild(aSlot->firstChild());
        }
        else
            aSlot->firstChild(nullptr);
    }
    // reset the slot incase it is reused
    ::new (aSlot) Slot(aSlot->userAttrs());
    memset(aSlot->userAttrs(), 0, m_silf->numUser() * sizeof(int16));
    // Update generation counter for debug
#if !defined GRAPHITE2_NTRACING
    if (m_face->logger())
        ++aSlot->userAttrs()[m_silf->numUser()];
#endif
    // update next pointer
    if (!m_freeSlots)
        aSlot->next(nullptr);
    else
        aSlot->next(m_freeSlots);
    m_freeSlots = aSlot;
}

SlotJustify *Segment::newJustify()
{
    if (!m_freeJustifies)
    {
        const size_t justSize = SlotJustify::size_of(m_silf->numJustLevels());
        byte *justs = grzeroalloc<byte>(justSize * m_bufSize);
        if (!justs) return NULL;
        for (ptrdiff_t i = m_bufSize - 2; i >= 0; --i)
        {
            SlotJustify *p = reinterpret_cast<SlotJustify *>(justs + justSize * i);
            SlotJustify *next = reinterpret_cast<SlotJustify *>(justs + justSize * (i + 1));
            p->next = next;
        }
        m_freeJustifies = (SlotJustify *)justs;
        m_justifies.push_back(m_freeJustifies);
    }
    SlotJustify *res = m_freeJustifies;
    m_freeJustifies = m_freeJustifies->next;
    res->next = NULL;
    return res;
}

void Segment::freeJustify(SlotJustify *aJustify)
{
    int numJust = m_silf->numJustLevels();
    if (m_silf->numJustLevels() <= 0) numJust = 1;
    aJustify->next = m_freeJustifies;
    memset(aJustify->values, 0, numJust*SlotJustify::NUMJUSTPARAMS*sizeof(int16));
    m_freeJustifies = aJustify;
}

// reverse the slots but keep diacritics in their same position after their bases
void Segment::reverseSlots()
{
    m_dir = m_dir ^ 64;                 // invert the reverse flag
    if (m_first == m_last) return;      // skip 0 or 1 glyph runs

    Slot *t = 0;
    Slot *curr = m_first;
    Slot *tlast;
    Slot *tfirst;
    Slot *out = 0;

    while (curr && getSlotBidiClass(curr) == 16)
        curr = curr->next();
    if (!curr) return;
    tfirst = curr->prev();
    tlast = curr;

    while (curr)
    {
        if (getSlotBidiClass(curr) == 16)
        {
            Slot *d = curr->next();
            while (d && getSlotBidiClass(d) == 16)
                d = d->next();

            d = d ? d->prev() : m_last;
            Slot *p = out->next();    // one after the diacritics. out can't be null
            if (p)
                p->prev(d);
            else
                tlast = d;
            t = d->next();
            d->next(p);
            curr->prev(out);
            out->next(curr);
        }
        else    // will always fire first time round the loop
        {
            if (out)
                out->prev(curr);
            t = curr->next();
            curr->next(out);
            out = curr;
        }
        curr = t;
    }
    out->prev(tfirst);
    if (tfirst)
        tfirst->next(out);
    else
        m_first = out;
    m_last = tlast;
}

void Segment::linkClusters(Slot *s, Slot * end)
{
    end = end->next();

    for (; s != end && !s->isBase(); s = s->next());
    Slot * ls = s;

    if (m_dir & 1)
    {
        for (; s != end; s = s->next())
        {
            if (!s->isBase())   continue;

            s->sibling(ls);
            ls = s;
        }
    }
    else
    {
        for (; s != end; s = s->next())
        {
            if (!s->isBase())   continue;

            ls->sibling(s);
            ls = s;
        }
    }
}

Position Segment::positionSlots(const Font *font, Slot * iStart, Slot * iEnd, bool isRtl, bool isFinal)
{
    Position currpos(0., 0.);
    float clusterMin = 0.;
    Rect bbox;
    bool reorder = (currdir() != isRtl);

    if (reorder)
    {
        Slot *temp;
        reverseSlots();
        temp = iStart;
        iStart = iEnd;
        iEnd = temp;
    }
    if (!iStart)    iStart = m_first;
    if (!iEnd)      iEnd   = m_last;

    if (!iStart || !iEnd)   // only true for empty segments
        return currpos;

    if (isRtl)
    {
        for (Slot * s = iEnd, * const end = iStart->prev(); s && s != end; s = s->prev())
        {
            if (s->isBase())
                currpos = s->finalise(this, font, currpos, bbox, 0, clusterMin = currpos.x, isRtl, isFinal);
        }
    }
    else
    {
        for (Slot * s = iStart, * const end = iEnd->next(); s && s != end; s = s->next())
        {
            if (s->isBase())
                currpos = s->finalise(this, font, currpos, bbox, 0, clusterMin = currpos.x, isRtl, isFinal);
        }
    }
    if (reorder)
        reverseSlots();
    return currpos;
}

void Segment::associateChars(int offset, size_t numChars)
{
    int i = 0, j = 0;
    CharInfo *c, *cend;
    for (c = m_charinfo + offset, cend = m_charinfo + offset + numChars; c != cend; ++c)
    {
        c->before(-1);
        c->after(-1);
    }
    for (Slot * s = m_first; s; s->index(i++), s = s->next())
    {
        j = s->before();
        if (j < 0)  continue;

        for (const int after = s->after(); j <= after; ++j)
        {
            c = charinfo(j);
            if (c->before() == -1 || i < c->before())   c->before(i);
            if (c->after() < i)                         c->after(i);
        }
    }
    for (Slot *s = m_first; s; s = s->next())
    {
        int a;
        for (a = s->after() + 1; a < offset + int(numChars) && charinfo(a)->after() < 0; ++a)
        { charinfo(a)->after(s->index()); }
        --a;
        s->after(a);

        for (a = s->before() - 1; a >= offset && charinfo(a)->before() < 0; --a)
        { charinfo(a)->before(s->index()); }
        ++a;
        s->before(a);
    }
}

template <typename utf_iter>
inline void process_utf_data(Segment & seg, const Face & face, const int fid, utf_iter c, size_t n_chars)
{
    const Cmap    & cmap = face.cmap();
    int slotid = 0;

    const typename utf_iter::codeunit_type * const base = c;
    for (; n_chars; --n_chars, ++c, ++slotid)
    {
        const uint32 usv = *c;
        uint16 gid = cmap[usv];
        if (!gid)   gid = face.findPseudo(usv);
        seg.appendSlot(slotid, usv, gid, fid, c - base);
    }
}

bool Segment::read_text(const Face *face, const Features* pFeats/*must not be NULL*/, gr_encform enc, const void* pStart, size_t nChars)
{
    assert(face);
    assert(pFeats);
    if (!m_charinfo) return false;

    // utf iterator is self recovering so we don't care about the error state of the iterator.
    switch (enc)
    {
    case gr_utf8:   process_utf_data(*this, *face, addFeatures(*pFeats), utf8::const_iterator(pStart), nChars); break;
    case gr_utf16:  process_utf_data(*this, *face, addFeatures(*pFeats), utf16::const_iterator(pStart), nChars); break;
    case gr_utf32:  process_utf_data(*this, *face, addFeatures(*pFeats), utf32::const_iterator(pStart), nChars); break;
    }
    return true;
}

void Segment::doMirror(uint16 aMirror)
{
    Slot * s;
    for (s = m_first; s; s = s->next())
    {
        unsigned short g = glyphAttr(s->gid(), aMirror);
        if (g && (!(dir() & 4) || !glyphAttr(s->gid(), aMirror + 1)))
            s->setGlyph(this, g);
    }
}

bool Segment::initCollisions()
{
    m_collisions = grzeroalloc<SlotCollision>(slotCount());
    if (!m_collisions) return false;

    for (Slot *p = m_first; p; p = p->next())
        if (p->index() < slotCount())
            ::new (collisionInfo(p)) SlotCollision(this, p);
        else
            return false;
    return true;
}