/* -*- mode: c++; c-basic-offset: 4 -*- */

/*
 * Modified for use within matplotlib
 * 5 July 2007
 * Michael Droettboom
 */

/*
** ~ppr/src/pprdrv/pprdrv_tt2.c
** Copyright 1995, Trinity College Computing Center.
** Written by David Chappell.
**
** Permission to use, copy, modify, and distribute this software and its
** documentation for any purpose and without fee is hereby granted, provided
** that the above copyright notice appear in all copies and that both that
** copyright notice and this permission notice appear in supporting
** documentation.  This software is provided "as is" without express or
** implied warranty.
**
** TrueType font support.  These functions allow PPR to generate
** PostScript fonts from Microsoft compatible TrueType font files.
**
** The functions in this file do most of the work to convert a
** TrueType font to a type 3 PostScript font.
**
** Most of the material in this file is derived from a program called
** "ttf2ps" which L. S. Ng posted to the usenet news group
** "comp.sources.postscript".  The author did not provide a copyright
** notice or indicate any restrictions on use.
**
** Last revised 11 July 1995.
*/

#include <cstdlib>
#include <cmath>
#include <cstring>
#include <memory>
#include "pprdrv.h"
#include "truetype.h"
#include <algorithm>
#include <stack>
#include <list>

class GlyphToType3
{
private:
    GlyphToType3& operator=(const GlyphToType3& other);
    GlyphToType3(const GlyphToType3& other);

    /* The PostScript bounding box. */
    int llx,lly,urx,ury;
    int advance_width;

    /* Variables to hold the character data. */
    int *epts_ctr;                      /* array of contour endpoints */
    int num_pts, num_ctr;               /* number of points, number of coutours */
    FWord *xcoor, *ycoor;               /* arrays of x and y coordinates */
    BYTE *tt_flags;                     /* array of TrueType flags */

    int stack_depth;            /* A book-keeping variable for keeping track of the depth of the PS stack */

    void load_char(TTFONT* font, BYTE *glyph);
    void stack(TTStreamWriter& stream, int new_elem);
    void stack_end(TTStreamWriter& stream);
    void PSConvert(TTStreamWriter& stream);
    void PSCurveto(TTStreamWriter& stream,
                   FWord x0, FWord y0,
                   FWord x1, FWord y1,
                   FWord x2, FWord y2);
    void PSMoveto(TTStreamWriter& stream, int x, int y);
    void PSLineto(TTStreamWriter& stream, int x, int y);
    void do_composite(TTStreamWriter& stream, struct TTFONT *font, BYTE *glyph);

public:
    GlyphToType3(TTStreamWriter& stream, struct TTFONT *font, int charindex, bool embedded = false);
    ~GlyphToType3();
};

// Each point on a TrueType contour is either on the path or off it (a
// control point); here's a simple representation for building such
// contours. Added by Jouni Seppänen 2012-05-27.
enum Flag { ON_PATH, OFF_PATH };
struct FlaggedPoint
{
    enum Flag flag;
    FWord x;
    FWord y;
    FlaggedPoint(Flag flag_, FWord x_, FWord y_): flag(flag_), x(x_), y(y_) {};
};

/*
** This routine is used to break the character
** procedure up into a number of smaller
** procedures.  This is necessary so as not to
** overflow the stack on certain level 1 interpreters.
**
** Prepare to push another item onto the stack,
** starting a new proceedure if necessary.
**
** Not all the stack depth calculations in this routine
** are perfectly accurate, but they do the job.
*/
void GlyphToType3::stack(TTStreamWriter& stream, int new_elem)
{
    if ( num_pts > 25 )  /* Only do something of we will have a log of points. */
    {
        if (stack_depth == 0)
        {
            stream.put_char('{');
            stack_depth=1;
        }

        stack_depth += new_elem;                /* Account for what we propose to add */

        if (stack_depth > 100)
        {
            stream.puts("}_e{");
            stack_depth = 3 + new_elem; /* A rough estimate */
        }
    }
} /* end of stack() */

void GlyphToType3::stack_end(TTStreamWriter& stream)                    /* called at end */
{
    if ( stack_depth )
    {
        stream.puts("}_e");
        stack_depth=0;
    }
} /* end of stack_end() */

/*
** We call this routine to emmit the PostScript code
** for the character we have loaded with load_char().
*/
void GlyphToType3::PSConvert(TTStreamWriter& stream)
{
    int j, k;

    /* Step thru the contours.
     * j = index to xcoor, ycoor, tt_flags (point data)
     * k = index to epts_ctr (which points belong to the same contour) */
    for(j = k = 0; k < num_ctr; k++)
    {
        // A TrueType contour consists of on-path and off-path points.
        // Two consecutive on-path points are to be joined with a
        // line; off-path points between on-path points indicate a
        // quadratic spline, where the off-path point is the control
        // point. Two consecutive off-path points have an implicit
        // on-path point midway between them.
        std::list<FlaggedPoint> points;

        // Represent flags and x/y coordinates as a C++ list
        for (; j <= epts_ctr[k]; j++)
        {
            if (!(tt_flags[j] & 1)) {
                points.push_back(FlaggedPoint(OFF_PATH, xcoor[j], ycoor[j]));
            } else {
                points.push_back(FlaggedPoint(ON_PATH, xcoor[j], ycoor[j]));
            }
        }

        if (points.size() == 0) {
            // Don't try to access the last element of an empty list
            continue;
        }

        // For any two consecutive off-path points, insert the implied
        // on-path point.
        FlaggedPoint prev = points.back();
        for (std::list<FlaggedPoint>::iterator it = points.begin();
             it != points.end();
             it++)
        {
            if (prev.flag == OFF_PATH && it->flag == OFF_PATH)
            {
                points.insert(it,
                              FlaggedPoint(ON_PATH,
                                           (prev.x + it->x) / 2,
                                           (prev.y + it->y) / 2));
            }
            prev = *it;
        }
        // Handle the wrap-around: insert a point either at the beginning
        // or at the end that has the same coordinates as the opposite point.
        // This also ensures that the initial point is ON_PATH.
        if (points.front().flag == OFF_PATH)
        {
            assert(points.back().flag == ON_PATH);
            points.insert(points.begin(), points.back());
        }
        else
        {
            assert(points.front().flag == ON_PATH);
            points.push_back(points.front());
        }

        // The first point
        stack(stream, 3);
        PSMoveto(stream, points.front().x, points.front().y);

        // Step through the remaining points
        std::list<FlaggedPoint>::const_iterator it = points.begin();
        for (it++; it != points.end(); /* incremented inside */)
        {
            const FlaggedPoint& point = *it;
            if (point.flag == ON_PATH)
            {
                stack(stream, 3);
                PSLineto(stream, point.x, point.y);
                it++;
            } else {
                std::list<FlaggedPoint>::const_iterator prev = it, next = it;
                prev--;
                next++;
                assert(prev->flag == ON_PATH);
                assert(next->flag == ON_PATH);
                stack(stream, 7);
                PSCurveto(stream,
                          prev->x, prev->y,
                          point.x, point.y,
                          next->x, next->y);
                it++;
                it++;
            }
        }
    }

    /* Now, we can fill the whole thing. */
    stack(stream, 1);
    stream.puts("_cl");
} /* end of PSConvert() */

void GlyphToType3::PSMoveto(TTStreamWriter& stream, int x, int y)
{
    stream.printf("%d %d _m\n", x, y);
}

void GlyphToType3::PSLineto(TTStreamWriter& stream, int x, int y)
{
    stream.printf("%d %d _l\n", x, y);
}

/*
** Emit a PostScript "curveto" command, assuming the current point
** is (x0, y0), the control point of a quadratic spline is (x1, y1),
** and the endpoint is (x2, y2). Note that this requires a conversion,
** since PostScript splines are cubic.
*/
void GlyphToType3::PSCurveto(TTStreamWriter& stream,
                             FWord x0, FWord y0,
                             FWord x1, FWord y1,
                             FWord x2, FWord y2)
{
    double sx[3], sy[3], cx[3], cy[3];

    sx[0] = x0;
    sy[0] = y0;
    sx[1] = x1;
    sy[1] = y1;
    sx[2] = x2;
    sy[2] = y2;
    cx[0] = (2*sx[1]+sx[0])/3;
    cy[0] = (2*sy[1]+sy[0])/3;
    cx[1] = (sx[2]+2*sx[1])/3;
    cy[1] = (sy[2]+2*sy[1])/3;
    cx[2] = sx[2];
    cy[2] = sy[2];
    stream.printf("%d %d %d %d %d %d _c\n",
                  (int)cx[0], (int)cy[0], (int)cx[1], (int)cy[1],
                  (int)cx[2], (int)cy[2]);
}

/*
** Deallocate the structures which stored
** the data for the last simple glyph.
*/
GlyphToType3::~GlyphToType3()
{
    free(tt_flags);            /* The flags array */
    free(xcoor);               /* The X coordinates */
    free(ycoor);               /* The Y coordinates */
    free(epts_ctr);            /* The array of contour endpoints */
}

/*
** Load the simple glyph data pointed to by glyph.
** The pointer "glyph" should point 10 bytes into
** the glyph data.
*/
void GlyphToType3::load_char(TTFONT* font, BYTE *glyph)
{
    int x;
    BYTE c, ct;

    /* Read the contour endpoints list. */
    epts_ctr = (int *)calloc(num_ctr,sizeof(int));
    for (x = 0; x < num_ctr; x++)
    {
        epts_ctr[x] = getUSHORT(glyph);
        glyph += 2;
    }

    /* From the endpoint of the last contour, we can */
    /* determine the number of points. */
    num_pts = epts_ctr[num_ctr-1]+1;
#ifdef DEBUG_TRUETYPE
    debug("num_pts=%d",num_pts);
    stream.printf("%% num_pts=%d\n",num_pts);
#endif

    /* Skip the instructions. */
    x = getUSHORT(glyph);
    glyph += 2;
    glyph += x;

    /* Allocate space to hold the data. */
    tt_flags = (BYTE *)calloc(num_pts,sizeof(BYTE));
    xcoor = (FWord *)calloc(num_pts,sizeof(FWord));
    ycoor = (FWord *)calloc(num_pts,sizeof(FWord));

    /* Read the flags array, uncompressing it as we go. */
    /* There is danger of overflow here. */
    for (x = 0; x < num_pts; )
    {
        tt_flags[x++] = c = *(glyph++);

        if (c&8)                /* If next byte is repeat count, */
        {
            ct = *(glyph++);

            if ( (x + ct) > num_pts )
            {
                throw TTException("Error in TT flags");
            }

            while (ct--)
            {
                tt_flags[x++] = c;
            }
        }
    }

    /* Read the x coordinates */
    for (x = 0; x < num_pts; x++)
    {
        if (tt_flags[x] & 2)            /* one byte value with */
        {
            /* external sign */
            c = *(glyph++);
            xcoor[x] = (tt_flags[x] & 0x10) ? c : (-1 * (int)c);
        }
        else if (tt_flags[x] & 0x10)    /* repeat last */
        {
            xcoor[x] = 0;
        }
        else                            /* two byte signed value */
        {
            xcoor[x] = getFWord(glyph);
            glyph+=2;
        }
    }

    /* Read the y coordinates */
    for (x = 0; x < num_pts; x++)
    {
        if (tt_flags[x] & 4)            /* one byte value with */
        {
            /* external sign */
            c = *(glyph++);
            ycoor[x] = (tt_flags[x] & 0x20) ? c : (-1 * (int)c);
        }
        else if (tt_flags[x] & 0x20)    /* repeat last value */
        {
            ycoor[x] = 0;
        }
        else                            /* two byte signed value */
        {
            ycoor[x] = getUSHORT(glyph);
            glyph+=2;
        }
    }

    /* Convert delta values to absolute values. */
    for (x = 1; x < num_pts; x++)
    {
        xcoor[x] += xcoor[x-1];
        ycoor[x] += ycoor[x-1];
    }

    for (x=0; x < num_pts; x++)
    {
        xcoor[x] = topost(xcoor[x]);
        ycoor[x] = topost(ycoor[x]);
    }

} /* end of load_char() */

/*
** Emmit PostScript code for a composite character.
*/
void GlyphToType3::do_composite(TTStreamWriter& stream, struct TTFONT *font, BYTE *glyph)
{
    USHORT flags;
    USHORT glyphIndex;
    int arg1;
    int arg2;

    /* Once around this loop for each component. */
    do
    {
        flags = getUSHORT(glyph);       /* read the flags word */
        glyph += 2;

        glyphIndex = getUSHORT(glyph);  /* read the glyphindex word */
        glyph += 2;

        if (flags & ARG_1_AND_2_ARE_WORDS)
        {
            /* The tt spec. seems to say these are signed. */
            arg1 = getSHORT(glyph);
            glyph += 2;
            arg2 = getSHORT(glyph);
            glyph += 2;
        }
        else                    /* The tt spec. does not clearly indicate */
        {
            /* whether these values are signed or not. */
            arg1 = *(signed char *)(glyph++);
            arg2 = *(signed char *)(glyph++);
        }

        if (flags & WE_HAVE_A_SCALE)
        {
            glyph += 2;
        }
        else if (flags & WE_HAVE_AN_X_AND_Y_SCALE)
        {
            glyph += 4;
        }
        else if (flags & WE_HAVE_A_TWO_BY_TWO)
        {
            glyph += 8;
        }
        else
        {
        }

        /* Debugging */
#ifdef DEBUG_TRUETYPE
        stream.printf("%% flags=%d, arg1=%d, arg2=%d\n",
                      (int)flags,arg1,arg2);
#endif

        /* If we have an (X,Y) shift and it is non-zero, */
        /* translate the coordinate system. */
        if ( flags & ARGS_ARE_XY_VALUES )
        {
            if ( arg1 != 0 || arg2 != 0 )
                stream.printf("gsave %d %d translate\n", topost(arg1), topost(arg2) );
        }
        else
        {
            stream.printf("%% unimplemented shift, arg1=%d, arg2=%d\n",arg1,arg2);
        }

        /* Invoke the CharStrings procedure to print the component. */
        stream.printf("false CharStrings /%s get exec\n",
                      ttfont_CharStrings_getname(font, glyphIndex));

        /* If we translated the coordinate system, */
        /* put it back the way it was. */
        if ( flags & ARGS_ARE_XY_VALUES && (arg1 != 0 || arg2 != 0) )
        {
            stream.puts("grestore ");
        }

    }
    while (flags & MORE_COMPONENTS);

} /* end of do_composite() */

/*
** Return a pointer to a specific glyph's data.
*/
BYTE *find_glyph_data(struct TTFONT *font, int charindex)
{
    ULONG off;
    ULONG length;

    /* Read the glyph offset from the index to location table. */
    if (font->indexToLocFormat == 0)
    {
        off = getUSHORT( font->loca_table + (charindex * 2) );
        off *= 2;
        length = getUSHORT( font->loca_table + ((charindex+1) * 2) );
        length *= 2;
        length -= off;
    }
    else
    {
        off = getULONG( font->loca_table + (charindex * 4) );
        length = getULONG( font->loca_table + ((charindex+1) * 4) );
        length -= off;
    }

    if (length > 0)
    {
        return font->glyf_table + off;
    }
    else
    {
        return (BYTE*)NULL;
    }

} /* end of find_glyph_data() */

GlyphToType3::GlyphToType3(TTStreamWriter& stream, struct TTFONT *font, int charindex, bool embedded /* = false */)
{
    BYTE *glyph;

    tt_flags = NULL;
    xcoor = NULL;
    ycoor = NULL;
    epts_ctr = NULL;
    stack_depth = 0;

    /* Get a pointer to the data. */
    glyph = find_glyph_data( font, charindex );

    /* If the character is blank, it has no bounding box, */
    /* otherwise read the bounding box. */
    if ( glyph == (BYTE*)NULL )
    {
        llx=lly=urx=ury=0;      /* A blank char has an all zero BoundingBox */
        num_ctr=0;              /* Set this for later if()s */
    }
    else
    {
        /* Read the number of contours. */
        num_ctr = getSHORT(glyph);

        /* Read PostScript bounding box. */
        llx = getFWord(glyph + 2);
        lly = getFWord(glyph + 4);
        urx = getFWord(glyph + 6);
        ury = getFWord(glyph + 8);

        /* Advance the pointer. */
        glyph += 10;
    }

    /* If it is a simple character, load its data. */
    if (num_ctr > 0)
    {
        load_char(font, glyph);
    }
    else
    {
        num_pts=0;
    }

    /* Consult the horizontal metrics table to determine */
    /* the character width. */
    if ( charindex < font->numberOfHMetrics )
    {
        advance_width = getuFWord( font->hmtx_table + (charindex * 4) );
    }
    else
    {
        advance_width = getuFWord( font->hmtx_table + ((font->numberOfHMetrics-1) * 4) );
    }

    /* Execute setcachedevice in order to inform the font machinery */
    /* of the character bounding box and advance width. */
    stack(stream, 7);
    if (font->target_type == PS_TYPE_42_3_HYBRID)
    {
        stream.printf("pop gsave .001 .001 scale %d 0 %d %d %d %d setcachedevice\n",
                      topost(advance_width),
                      topost(llx), topost(lly), topost(urx), topost(ury) );
    }
    else
    {
        stream.printf("%d 0 %d %d %d %d _sc\n",
                      topost(advance_width),
                      topost(llx), topost(lly), topost(urx), topost(ury) );
    }

    /* If it is a simple glyph, convert it, */
    /* otherwise, close the stack business. */
    if ( num_ctr > 0 )          /* simple */
    {
        PSConvert(stream);
    }
    else if ( num_ctr < 0 )     /* composite */
    {
        do_composite(stream, font, glyph);
    }

    if (font->target_type == PS_TYPE_42_3_HYBRID)
    {
        stream.printf("\ngrestore\n");
    }

    stack_end(stream);
}

/*
** This is the routine which is called from pprdrv_tt.c.
*/
void tt_type3_charproc(TTStreamWriter& stream, struct TTFONT *font, int charindex)
{
    GlyphToType3 glyph(stream, font, charindex);
} /* end of tt_type3_charproc() */

/*
** Some of the given glyph ids may refer to composite glyphs.
** This function adds all of the dependencies of those composite
** glyphs to the glyph id vector.  Michael Droettboom [06-07-07]
*/
void ttfont_add_glyph_dependencies(struct TTFONT *font, std::vector<int>& glyph_ids)
{
    std::sort(glyph_ids.begin(), glyph_ids.end());

    std::stack<int> glyph_stack;
    for (std::vector<int>::iterator i = glyph_ids.begin();
            i != glyph_ids.end(); ++i)
    {
        glyph_stack.push(*i);
    }

    while (glyph_stack.size())
    {
        int gind = glyph_stack.top();
        glyph_stack.pop();

        BYTE* glyph = find_glyph_data( font, gind );
        if (glyph != (BYTE*)NULL)
        {

            int num_ctr = getSHORT(glyph);
            if (num_ctr <= 0)   // This is a composite glyph
            {

                glyph += 10;
                USHORT flags = 0;

                do
                {
                    flags = getUSHORT(glyph);
                    glyph += 2;
                    gind = (int)getUSHORT(glyph);
                    glyph += 2;

                    std::vector<int>::iterator insertion =
                        std::lower_bound(glyph_ids.begin(), glyph_ids.end(), gind);
                    if (insertion == glyph_ids.end() || *insertion != gind)
                    {
                        glyph_ids.insert(insertion, gind);
                        glyph_stack.push(gind);
                    }

                    if (flags & ARG_1_AND_2_ARE_WORDS)
                    {
                        glyph += 4;
                    }
                    else
                    {
                        glyph += 2;
                    }

                    if (flags & WE_HAVE_A_SCALE)
                    {
                        glyph += 2;
                    }
                    else if (flags & WE_HAVE_AN_X_AND_Y_SCALE)
                    {
                        glyph += 4;
                    }
                    else if (flags & WE_HAVE_A_TWO_BY_TWO)
                    {
                        glyph += 8;
                    }
                }
                while (flags & MORE_COMPONENTS);
            }
        }
    }
}

/* end of file */