λ

pastry

truetype font renderer

settings

pastry.c

50017 bytes raw

#define _POSIX_C_SOURCE 200809L
#include <assert.h>
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#if defined(_MSC_VER)
# define restrict __restrict
#endif

#if defined(_WIN32)
# define WIN32_LEAN_AND_MEAN 1
# include <windows.h>
#else
# include <fcntl.h>
# include <sys/mman.h>
# include <sys/stat.h>
# include <unistd.h>
#endif

#include "pastry.h"

#define PASTRY_VERSION "1.0.0"

#define FILE_MAGIC_ONE             0x00010000
#define FILE_MAGIC_TWO             0x74727565

#define HORIZONTAL_KERNING         0x01
#define MINIMUM_KERNING            0x02
#define CROSS_STREAM_KERNING       0x04
#define OVERRIDE_KERNING           0x08

#define POINT_IS_ON_CURVE          0x01
#define X_CHANGE_IS_SMALL          0x02
#define Y_CHANGE_IS_SMALL          0x04
#define REPEAT_FLAG                0x08
#define X_CHANGE_IS_ZERO           0x10
#define X_CHANGE_IS_POSITIVE       0x10
#define Y_CHANGE_IS_ZERO           0x20
#define Y_CHANGE_IS_POSITIVE       0x20

#define OFFSETS_ARE_LARGE          0x001
#define ACTUAL_XY_OFFSETS          0x002
#define GOT_A_SINGLE_SCALE         0x008
#define THERE_ARE_MORE_COMPONENTS  0x020
#define GOT_AN_X_AND_Y_SCALE       0x040
#define GOT_A_SCALE_MATRIX         0x080

#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define SIGN(x)   (((x) > 0) - ((x) < 0))
// alloc vals on stack if small enough, else spill to heap
#define PASTRY_STACK_ALLOC(var, type, thresh, count) \
    type var##_stack_[thresh]; \
    var = (count) <= (thresh) ? var##_stack_ : PASTRY_CALLOC(count, sizeof(type));
#define PASTRY_STACK_FREE(var) \
    if (var != var##_stack_) PASTRY_FREE(var);

enum
{ SrcMapping, SrcUser };

typedef struct Point   Point;
typedef struct Line    Line;
typedef struct Curve   Curve;
typedef struct Cell    Cell;
typedef struct Outline Outline;
typedef struct Raster  Raster;

struct Point
{
    double x, y;
};
struct Line
{
    uint_least16_t beg, end;
};
struct Curve
{
    uint_least16_t beg, end, ctrl;
};
struct Cell
{
    double area, cover;
};

struct Outline
{
    Point *points;
    Curve *curves;
    Line  *lines;
    uint_least16_t numPoints;
    uint_least16_t capPoints;
    uint_least16_t numCurves;
    uint_least16_t capCurves;
    uint_least16_t numLines;
    uint_least16_t capLines;
};

struct Raster
{
    Cell *cells;
    int   width;
    int   height;
};

struct PASTRY_Font
{
    const uint8_t *memory;
    uint_fast32_t  size;
#if defined(_WIN32)
    HANDLE         mapping;
#endif
    int            source;

    uint_least16_t unitsPerEm;
    int_least16_t  locaFormat;
    uint_least16_t numLongHmtx;
};

// generic utils
static void  *realloc_array(void *optr, size_t nmemb, size_t size);
static inline int fast_floor(double x);
static inline int fast_ceil (double x);

// files
static int  map_file  (PASTRY_Font *font, const char *filename);
static void unmap_file(PASTRY_Font *font);
static int  init_font (PASTRY_Font *font);

// math
static Point midpoint(Point a, Point b);
static void transform_points(unsigned int numPts, Point *points, double trf[6]);
static void clip_points(unsigned int numPts, Point *points, int width, int height);

// outline stuff
static int  init_outline(Outline *outl);
static void free_outline(Outline *outl);
static int  grow_points (Outline *outl);
static int  grow_curves (Outline *outl);
static int  grow_lines  (Outline *outl);

// parsing utils
static inline int is_safe_offset(PASTRY_Font *font, uint_fast32_t offset, uint_fast32_t margin);
static void *csearch(const void *key, const void *base,
                     size_t nmemb, size_t size, int (*compar)(const void *, const void *));
static void *binsearch(const void *key, const void *base,
                       size_t nmemb, size_t size, int (*compar)(const void *, const void *));
static int  cmpu16(const void *a, const void *b);
static int  cmpu32(const void *a, const void *b);
static inline uint_least8_t  getu8 (PASTRY_Font *font, uint_fast32_t offset);
static inline int_least8_t   geti8 (PASTRY_Font *font, uint_fast32_t offset);
static inline uint_least16_t getu16(PASTRY_Font *font, uint_fast32_t offset);
static inline int_least16_t  geti16(PASTRY_Font *font, uint_fast32_t offset);
static inline uint_least32_t getu32(PASTRY_Font *font, uint_fast32_t offset);
static int gettable(PASTRY_Font *font, const char tag[4], uint_fast32_t *offset);

// codepoint to glyph id translation
static int  cmap_fmt4(PASTRY_Font *font, uint_fast32_t table, PASTRY_UChar charCode, uint_fast32_t *glyph);
static int  cmap_fmt6(PASTRY_Font *font, uint_fast32_t table, PASTRY_UChar charCode, uint_fast32_t *glyph);
static int  glyph_id(PASTRY_Font *font, PASTRY_UChar charCode, uint_fast32_t *glyph);

// glyph metrics lookup
static int  hor_metrics(PASTRY_Font *font, uint_fast32_t glyph, int *advanceWidth, int *leftSideBearing);
static int  glyph_bbox(const PASTRY *pastry, uint_fast32_t outline, int box[4]);

// decoding outlines
static int  outline_offset(PASTRY_Font *font, uint_fast32_t glyph, uint_fast32_t *offset);
static int  simple_flags(PASTRY_Font *font, uint_fast32_t *offset, uint_fast16_t numPts, uint8_t *flags);
static int  simple_points(PASTRY_Font *font, uint_fast32_t offset, uint_fast16_t numPts, uint8_t *flags, Point *points);
static int  decode_contour(uint8_t *flags, uint_fast16_t basePoint, uint_fast16_t count, Outline *outl);
static int  simple_outline(PASTRY_Font *font, uint_fast32_t offset, unsigned int numContours, Outline *outl);
static int  compound_outline(PASTRY_Font *font, uint_fast32_t offset, int recDepth, Outline *outl);
static int  decode_outline(PASTRY_Font *font, uint_fast32_t offset, int recDepth, Outline *outl);

// tessellation
static int  is_flat(Outline *outl, Curve curve);
static int  tessellate_curve(Curve curve, Outline *outl);
static int  tessellate_curves(Outline *outl);

// silhouette rasterization
static void draw_line(Raster buf, Point origin, Point goal);
static void draw_lines(Outline *outl, Raster buf);

// post processing
static void post_process(Raster buf, uint8_t *image);

// glyph rendering
static int  render_outline(Outline *outl, double transform[6], PASTRY_Image image);

// ---------- impls start here ----------

const char *
pastry_version(void)
{
    return PASTRY_VERSION;
}

// loads a font from a given mem range
PASTRY_Font *
pastry_loadmem(const void *mem, size_t size)
{
    PASTRY_Font *font;
    if (size > UINT32_MAX) {
        return NULL;
    }
    if (!(font = PASTRY_CALLOC(1, sizeof *font))) {
        return NULL;
    }
    font->memory = mem;
    font->size   = (uint_fast32_t) size;
    font->source = SrcUser;
    if (init_font(font) < 0) {
        pastry_freefont(font);
        return NULL;
    }
    return font;
}

// loads a font from the fs
PASTRY_Font *
pastry_loadfile(char const *filename)
{
    PASTRY_Font *font;
    if (!(font = PASTRY_CALLOC(1, sizeof *font))) {
        return NULL;
    }
    if (map_file(font, filename) < 0) {
        PASTRY_FREE(font);
        return NULL;
    }
    if (init_font(font) < 0) {
        pastry_freefont(font);
        return NULL;
    }
    return font;
}

void
pastry_freefont(PASTRY_Font *font)
{
    if (!font) return;
    // only unmap if it was mapped by pastry
    if (font->source == SrcMapping)
        unmap_file(font);
    PASTRY_FREE(font);
}

int
pastry_lmetrics(const PASTRY *pastry, PASTRY_LMetrics *metrics)
{
    double factor;
    uint_fast32_t hhea;
    memset(metrics, 0, sizeof *metrics);
    if (gettable(pastry->font, "hhea", &hhea) < 0)
        return -1;
    if (!is_safe_offset(pastry->font, hhea, 36))
        return -1;
    factor = pastry->yScale / pastry->font->unitsPerEm;
    metrics->ascender  = geti16(pastry->font, hhea + 4) * factor;
    metrics->descender = geti16(pastry->font, hhea + 6) * factor;
    metrics->lineGap   = geti16(pastry->font, hhea + 8) * factor;
    return 0;
}

int
pastry_lookup(const PASTRY *pastry, PASTRY_UChar codepoint, PASTRY_Glyph *glyph)
{
    return glyph_id(pastry->font, codepoint, glyph);
}

int
pastry_gmetrics(const PASTRY *pastry, PASTRY_Glyph glyph, PASTRY_GMetrics *metrics)
{
    int adv, lsb;
    double xScale = pastry->xScale / pastry->font->unitsPerEm;
    uint_fast32_t outline;
    int bbox[4];

    memset(metrics, 0, sizeof *metrics);

    if (hor_metrics(pastry->font, glyph, &adv, &lsb) < 0)
        return -1;
    metrics->advanceWidth    = adv * xScale;
    metrics->leftSideBearing = lsb * xScale + pastry->xOffset;

    if (outline_offset(pastry->font, glyph, &outline) < 0)
        return -1;
    if (!outline)
        return 0;
    if (glyph_bbox(pastry, outline, bbox) < 0)
        return -1;
    metrics->minWidth  = bbox[2] - bbox[0] + 1;
    metrics->minHeight = bbox[3] - bbox[1] + 1;
    metrics->yOffset   = pastry->flags & PASTRY_DOWNWARD_Y ? -bbox[3] : bbox[1];

    return 0;
}

int
pastry_kerning(const PASTRY *pastry, PASTRY_Glyph leftGlyph, PASTRY_Glyph rightGlyph,
               PASTRY_Kerning *kerning)
{
    void *match;
    uint_fast32_t offset;
    unsigned int numTables, numPairs, length, format, flags;
    int value;
    uint8_t key[4];

    memset(kerning, 0, sizeof *kerning);

    if (gettable(pastry->font, "kern", &offset) < 0)
        return 0;

    // read kern table header
    if (!is_safe_offset(pastry->font, offset, 4))
        return -1;
    if (getu16(pastry->font, offset) != 0)
        return 0;
    numTables = getu16(pastry->font, offset + 2);
    offset += 4;

    while (numTables > 0) {
        // read subtable header
        if (!is_safe_offset(pastry->font, offset, 6))
            return -1;
        length = getu16(pastry->font, offset + 2);
        format = getu8 (pastry->font, offset + 4);
        flags  = getu8 (pastry->font, offset + 5);
        offset += 6;

        if (format == 0 && (flags & HORIZONTAL_KERNING) && !(flags & MINIMUM_KERNING)) {
            // read format 0 header
            if (!is_safe_offset(pastry->font, offset, 8))
                return -1;
            numPairs = getu16(pastry->font, offset);
            offset += 8;
            // look up char code pair
            key[0] = (leftGlyph  >> 8) & 0xFF;
            key[1] =  leftGlyph  & 0xFF;
            key[2] = (rightGlyph >> 8) & 0xFF;
            key[3] =  rightGlyph & 0xFF;
            if ((match = binsearch(key, pastry->font->memory + offset,
                                   numPairs, 6, cmpu32)) != NULL) {

                value = geti16(pastry->font, (uint_fast32_t) ((uint8_t *) match - pastry->font->memory + 4));
                if (flags & CROSS_STREAM_KERNING) {
                    kerning->yShift += value;
                } else {
                    kerning->xShift += value;
                }
            }

        }

        offset += length;
        --numTables;
    }

    kerning->xShift = kerning->xShift / pastry->font->unitsPerEm * pastry->xScale;
    kerning->yShift = kerning->yShift / pastry->font->unitsPerEm * pastry->yScale;

    return 0;
}

int
pastry_render(const PASTRY *pastry, PASTRY_Glyph glyph, PASTRY_Image image)
{
    uint_fast32_t outline;
    double transform[6];
    int bbox[4];
    Outline outl;

    if (outline_offset(pastry->font, glyph, &outline) < 0)
        return -1;
    if (!outline)
        return 0;
    if (glyph_bbox(pastry, outline, bbox) < 0)
        return -1;
    /* set up transformation matrix such that
     * transformed bounding boxes min corner
     * lines up with the (0, 0) point */
    transform[0] = pastry->xScale / pastry->font->unitsPerEm;
    transform[1] = 0.0;
    transform[2] = 0.0;
    transform[4] = pastry->xOffset - bbox[0];
    if (pastry->flags & PASTRY_DOWNWARD_Y) {
        transform[3] = -pastry->yScale / pastry->font->unitsPerEm;
        transform[5] = bbox[3] - pastry->yOffset;
    } else {
        transform[3] = +pastry->yScale / pastry->font->unitsPerEm;
        transform[5] = pastry->yOffset - bbox[1];
    }

    memset(&outl, 0, sizeof outl);
    if (init_outline(&outl) < 0)
        goto failure;

    if (decode_outline(pastry->font, outline, 0, &outl) < 0)
        goto failure;
    if (render_outline(&outl, transform, image) < 0)
        goto failure;

    free_outline(&outl);
    return 0;

failure:
    free_outline(&outl);
    return -1;
}

/* sqrt(SIZE_MAX+1), as s1*s2 <= SIZE_MAX
 * if both s1 < MUL_NO_OVERFLOW and s2 < MUL_NO_OVERFLOW */
#define MUL_NO_OVERFLOW    ((size_t)1 << (sizeof(size_t) * 4))

/* copy of openbsd's reallocarray function from the stdlib
 * a wrapper for realloc() that takes two size args like calloc()
 * useful cuz it eliminates some integer overflow bugs that pmo */
static void *
realloc_array(void *optr, size_t nmemb, size_t size)
{
    if ((nmemb >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) &&
            nmemb > 0 && SIZE_MAX / nmemb < size) {
        errno = ENOMEM;
        return NULL;
    }
    return PASTRY_REALLOC(optr, (size * nmemb));
}

static inline int
fast_floor(double x)
{
    int i = (int) x;
    return i - (i > x);
}

static inline double
fast_abs(double x)
{
    return x < 0.0 ? -x : x;
}

static inline int
fast_ceil(double x)
{
    int i = (int) x;
    return i + (i < x);
}

// largest double strictly less than x; x must be finite and positive.
// stands in for nextafter(x, 0.0) without pulling in libm.
static inline double
fast_prev(double x)
{
    union { double d; uint64_t u; } bits;
    bits.d = x;
    bits.u -= 1;
    return bits.d;
}

#if defined(_WIN32)

static int
map_file(PASTRY_Font *font, const char *filename)
{
    HANDLE file;
    DWORD high, low;

    font->mapping = NULL;
    font->memory  = NULL;

    file = CreateFileA(filename, GENERIC_READ, FILE_SHARE_READ, NULL, OPEN_EXISTING, 0, NULL);
    if (file == INVALID_HANDLE_VALUE) {
        return -1;
    }

    low = GetFileSize(file, &high);
    if (low == INVALID_FILE_SIZE) {
        CloseHandle(file);
        return -1;
    }

    font->size = (size_t)high << (8 * sizeof(DWORD)) | low;

    font->mapping = CreateFileMapping(file, NULL, PAGE_READONLY, high, low, NULL);
    if (!font->mapping) {
        CloseHandle(file);
        return -1;
    }

    CloseHandle(file);

    font->memory = MapViewOfFile(font->mapping, FILE_MAP_READ, 0, 0, 0);
    if (!font->memory) {
        CloseHandle(font->mapping);
        font->mapping = NULL;
        return -1;
    }

    return 0;
}

static void
unmap_file(PASTRY_Font *font)
{
    if (font->memory) {
        UnmapViewOfFile(font->memory);
        font->memory = NULL;
    }
    if (font->mapping) {
        CloseHandle(font->mapping);
        font->mapping = NULL;
    }
}

#elif defined(PASTRY_NO_MMAP)

static int
map_file(PASTRY_Font *font, const char *filename)
{
    FILE *f = fopen(filename, "rb");
    if (!f) return -1;

    if (fseek(f, 0, SEEK_END) != 0) {
        fclose(f);
        return -1;
    }

    long sz = ftell(f);
    if (sz < 0) {
        fclose(f);
        return -1;
    }
    rewind(f);

    // allocate and read
    void *mem = PASTRY_MALLOC((size_t)sz);
    if (!mem) {
        fclose(f);
        return -1;
    }

    size_t read_bytes = fread(mem, 1, (size_t)sz, f);
    fclose(f);
    if (read_bytes != (size_t)sz) {
        PASTRY_FREE(mem);
        return -1;
    }

    font->memory = mem;
    font->size   = (uint_fast32_t) sz;
    font->source = SrcCopy;

    return 0;
}

static void
unmap_file(PASTRY_Font *font)
{
    if (font->memory) {
        PASTRY_FREE(font->memory);
        font->memory = NULL;
        font->size   = 0;
    }
}

#else

static int
map_file(PASTRY_Font *font, const char *filename)
{
    struct stat info;
    int fd;
    font->memory = MAP_FAILED;
    font->size   = 0;
    font->source = SrcMapping;
    if ((fd = open(filename, O_RDONLY)) < 0) {
        return -1;
    }
    if (fstat(fd, &info) < 0) {
        close(fd);
        return -1;
    }
    // gottem
    assert(info.st_size > 0);
    font->memory = mmap(NULL, (size_t) info.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
    font->size   = (uint_fast32_t) info.st_size;
    close(fd);
    return font->memory == MAP_FAILED ? -1 : 0;
}

static void
unmap_file(PASTRY_Font *font)
{
    assert(font->memory != MAP_FAILED);
    munmap((void *) (uintptr_t) font->memory, font->size);
}

#endif

static int
init_font(PASTRY_Font *font)
{
    uint_fast32_t scalerType, head, hhea;

    if (!is_safe_offset(font, 0, 12))
        return -1;
    // check for a compatible scalerType (magic number). */
    scalerType = getu32(font, 0);
    if (scalerType != FILE_MAGIC_ONE && scalerType != FILE_MAGIC_TWO)
        return -1;

    if (gettable(font, "head", &head) < 0)
        return -1;
    if (!is_safe_offset(font, head, 54))
        return -1;
    font->unitsPerEm = getu16(font, head + 18);
    font->locaFormat = geti16(font, head + 50);

    if (gettable(font, "hhea", &hhea) < 0)
        return -1;
    if (!is_safe_offset(font, hhea, 36))
        return -1;
    font->numLongHmtx = getu16(font, hhea + 34);

    return 0;
}

static Point
midpoint(Point a, Point b)
{
    return (Point) {
        0.5 * (a.x + b.x),
            0.5 * (a.y + b.y)
    };
}

// apply an affine linear transformation matrix to a set of points
static void
transform_points(unsigned int numPts, Point *points, double trf[6])
{
    assert(numPts == 0 || points != NULL);
    assert(trf != NULL);
    Point pt;
    unsigned int i;
    for (i = 0; i < numPts; ++i) {
        pt = points[i];
        points[i] = (Point) {
            pt.x * trf[0] + pt.y * trf[2] + trf[4],
                 pt.x * trf[1] + pt.y * trf[3] + trf[5]
        };
    }
}

static void
clip_points(unsigned int numPts, Point *points, int width, int height)
{
    assert(numPts == 0 || points != NULL);
    assert(width > 0 && height > 0);
    Point pt;
    unsigned int i;

    for (i = 0; i < numPts; ++i) {
        pt = points[i];

        if (pt.x < 0.0) {
            points[i].x = 0.0;
        }
        if (pt.x >= width) {
            points[i].x = fast_prev((double) width);
        }
        if (pt.y < 0.0) {
            points[i].y = 0.0;
        }
        if (pt.y >= height) {
            points[i].y = fast_prev((double) height);
        }
    }
}

static int
init_outline(Outline *outl)
{
    assert(outl != NULL);
    // add smaller initial allocations later (someday)
    outl->numPoints = 0;
    outl->capPoints = 64;
    if (!(outl->points = PASTRY_MALLOC(outl->capPoints * sizeof *outl->points)))
        return -1;
    outl->numCurves = 0;
    outl->capCurves = 64;
    if (!(outl->curves = PASTRY_MALLOC(outl->capCurves * sizeof *outl->curves)))
        return -1;
    outl->numLines = 0;
    outl->capLines = 64;
    if (!(outl->lines = PASTRY_MALLOC(outl->capLines * sizeof *outl->lines)))
        return -1;
    return 0;
}

static void
free_outline(Outline *outl)
{
    PASTRY_FREE(outl->points);
    PASTRY_FREE(outl->curves);
    PASTRY_FREE(outl->lines);
}

static int
grow_points(Outline *outl)
{
    void *mem;
    uint_fast16_t cap;
    assert(outl->capPoints);
    // since uint_fast16_t is used for capacities, be extra careful not to trigger int overflow
    if (outl->capPoints > UINT16_MAX / 2)
        return -1;
    cap = (uint_fast16_t) (2U * outl->capPoints);
    if (!(mem = realloc_array(outl->points, cap, sizeof *outl->points)))
        return -1;
    outl->capPoints = (uint_least16_t) cap;
    outl->points    = mem;
    return 0;
}

static int
grow_curves(Outline *outl)
{
    void *mem;
    uint_fast16_t cap;
    assert(outl->capCurves);
    if (outl->capCurves > UINT16_MAX / 2)
        return -1;
    cap = (uint_fast16_t) (2U * outl->capCurves);
    if (!(mem = realloc_array(outl->curves, cap, sizeof *outl->curves)))
        return -1;
    outl->capCurves = (uint_least16_t) cap;
    outl->curves    = mem;
    return 0;
}

static int
grow_lines(Outline *outl)
{
    void *mem;
    uint_fast16_t cap;
    assert(outl->capLines);
    if (outl->capLines > UINT16_MAX / 2)
        return -1;
    cap = (uint_fast16_t) (2U * outl->capLines);
    if (!(mem = realloc_array(outl->lines, cap, sizeof *outl->lines)))
        return -1;
    outl->capLines = (uint_least16_t) cap;
    outl->lines    = mem;
    return 0;
}

static inline int
is_safe_offset(PASTRY_Font *font, uint_fast32_t offset, uint_fast32_t margin)
{
    if (offset > font->size) return 0;
    if (font->size - offset < margin) return 0;
    return 1;
}

// like bsearch(), but returns next highest element if key could not be found`
static void *
csearch(const void *key, const void *base,
        size_t nmemb, size_t size,
        int (*compar)(const void *, const void *))
{
    const uint8_t *bytes = base, *sample;
    size_t low = 0, high = nmemb - 1, mid;
    if (!nmemb) return NULL;
    while (low != high) {
        mid = low + (high - low) / 2;
        sample = bytes + mid * size;
        if (compar(key, sample) > 0) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return (void *) ((uintptr_t)bytes + low * size);
}

// bsearch(), minus the libc. returns NULL when the key is absent.
static void *
binsearch(const void *key, const void *base,
          size_t nmemb, size_t size,
          int (*compar)(const void *, const void *))
{
    const uint8_t *bytes = base;
    size_t low = 0, high = nmemb;
    while (low < high) {
        size_t mid = low + (high - low) / 2;
        const uint8_t *sample = bytes + mid * size;
        int cmp = compar(key, sample);
        if (cmp == 0)
            return (void *) (uintptr_t) sample;
        if (cmp < 0)
            high = mid;
        else
            low = mid + 1;
    }
    return NULL;
}

// used as comparison function for [bc]search()
static int
cmpu16(const void *a, const void *b)
{
    return memcmp(a, b, 2);
}

// used as comparison function for [bc]search()
static int
cmpu32(const void *a, const void *b)
{
    return memcmp(a, b, 4);
}

static inline uint_least8_t
getu8(PASTRY_Font *font, uint_fast32_t offset)
{
    assert(offset + 1 <= font->size);
    return *(font->memory + offset);
}

static inline int_least8_t
geti8(PASTRY_Font *font, uint_fast32_t offset)
{
    return (int_least8_t) getu8(font, offset);
}

static inline uint_least16_t
getu16(PASTRY_Font *font, uint_fast32_t offset)
{
    assert(offset + 2 <= font->size);
    const uint8_t *base = font->memory + offset;
    uint_least16_t b1 = base[0], b0 = base[1];
    return (uint_least16_t) (b1 << 8 | b0);
}

static inline int16_t
geti16(PASTRY_Font *font, uint_fast32_t offset)
{
    return (int_least16_t) getu16(font, offset);
}

static inline uint32_t
getu32(PASTRY_Font *font, uint_fast32_t offset)
{
    assert(offset + 4 <= font->size);
    const uint8_t *base = font->memory + offset;
    uint_least32_t b3 = base[0], b2 = base[1], b1 = base[2], b0 = base[3];
    return (uint_least32_t) (b3 << 24 | b2 << 16 | b1 << 8 | b0);
}

static int
gettable(PASTRY_Font *font, const char tag[4], uint_fast32_t *offset)
{
    void *match;
    unsigned int numTables;
    // no need to bounds-check access to the first 12 bytes cuz it's already checked by init_font()
    numTables = getu16(font, 4);
    if (!is_safe_offset(font, 12, (uint_fast32_t) numTables * 16))
        return -1;
    if (!(match = binsearch(tag, font->memory + 12, numTables, 16, cmpu32)))
        return -1;
    *offset = getu32(font, (uint_fast32_t) ((uint8_t *) match - font->memory + 8));
    return 0;
}

static int
cmap_fmt4(PASTRY_Font *font, uint_fast32_t table, PASTRY_UChar charCode, PASTRY_Glyph *glyph)
{
    const uint8_t *segPtr;
    uint_fast32_t segIdxX2;
    uint_fast32_t endCodes, startCodes, idDeltas, idRangeOffsets, idOffset;
    uint_fast16_t segCountX2, idRangeOffset, startCode, shortCode, idDelta, id;
    uint8_t key[2] = { (uint8_t) (charCode >> 8), (uint8_t) charCode };
    // cmap format 4 only supports the unicode bmp
    if (charCode > 0xFFFF) {
        *glyph = 0;
        return 0;
    }
    shortCode = (uint_fast16_t) charCode;
    if (!is_safe_offset(font, table, 8))
        return -1;
    segCountX2 = getu16(font, table);
    if ((segCountX2 & 1) || !segCountX2)
        return -1;
    // find starting positions of the relevant arrays
    endCodes       = table + 8;
    startCodes     = endCodes + segCountX2 + 2;
    idDeltas       = startCodes + segCountX2;
    idRangeOffsets = idDeltas + segCountX2;
    if (!is_safe_offset(font, idRangeOffsets, segCountX2))
        return -1;
    /* find the segment that contains shortCode by binary searching over
     * the highest codes in the segments. */
    segPtr = csearch(key, font->memory + endCodes, segCountX2 / 2, 2, cmpu16);
    segIdxX2 = (uint_fast32_t) (segPtr - (font->memory + endCodes));
    // look up segment info from the arrays & short circuit if the spec requires
    if ((startCode = getu16(font, startCodes + segIdxX2)) > shortCode)
        return 0;
    idDelta = getu16(font, idDeltas + segIdxX2);
    if (!(idRangeOffset = getu16(font, idRangeOffsets + segIdxX2))) {
        // intentional integer under/overflow
        *glyph = (shortCode + idDelta) & 0xFFFF;
        return 0;
    }
    // calculate offset into glyph array and determine ultimate value.
    idOffset = idRangeOffsets + segIdxX2 + idRangeOffset + 2U * (unsigned int) (shortCode - startCode);
    if (!is_safe_offset(font, idOffset, 2))
        return -1;
    id = getu16(font, idOffset);
    // intentional integer under/overflow
    *glyph = id ? (id + idDelta) & 0xFFFF : 0;
    return 0;
}

static int
cmap_fmt6(PASTRY_Font *font, uint_fast32_t table, PASTRY_UChar charCode, PASTRY_Glyph *glyph)
{
    unsigned int firstCode, entryCount;
    // cmap format 6 only supports the unicode bmp
    if (charCode > 0xFFFF) {
        *glyph = 0;
        return 0;
    }
    if (!is_safe_offset(font, table, 4))
        return -1;
    firstCode  = getu16(font, table);
    entryCount = getu16(font, table + 2);
    if (!is_safe_offset(font, table, 4 + 2 * entryCount))
        return -1;
    if (charCode < firstCode)
        return -1;
    charCode -= firstCode;
    if (!(charCode < entryCount))
        return -1;
    *glyph = getu16(font, table + 4 + 2 * charCode);
    return 0;
}

static int
cmap_fmt12_13(PASTRY_Font *font, uint_fast32_t table, PASTRY_UChar charCode, PASTRY_Glyph *glyph, int which)
{
    uint32_t len, numEntries;
    uint_fast32_t i;

    *glyph = 0;

    // ensure entire header
    if (!is_safe_offset(font, table, 16))
        return -1;

    len = getu32(font, table + 4);

    // smol header is 16 bytes
    if (len < 16)
        return -1;

    if (!is_safe_offset(font, table, len))
        return -1;

    numEntries = getu32(font, table + 12);

    for (i = 0; i < numEntries; ++i) {
        uint32_t firstCode, lastCode, glyphOffset;
        firstCode = getu32(font, table + (i * 12) + 16);
        lastCode = getu32(font, table + (i * 12) + 16 + 4);
        if (charCode < firstCode || charCode > lastCode)
            continue;
        glyphOffset = getu32(font, table + (i * 12) + 16 + 8);
        if (which == 12)
            *glyph = (charCode-firstCode) + glyphOffset;
        else
            *glyph = glyphOffset;
        return 0;
    }

    return 0;
}

// maps unicode code points to glyph indices
static int
glyph_id(PASTRY_Font *font, PASTRY_UChar charCode, PASTRY_Glyph *glyph)
{
    uint_fast32_t cmap, entry, table;
    unsigned int idx, numEntries;
    int type, format;

    *glyph = 0;

    if (gettable(font, "cmap", &cmap) < 0)
        return -1;

    if (!is_safe_offset(font, cmap, 4))
        return -1;
    numEntries = getu16(font, cmap + 2);

    if (!is_safe_offset(font, cmap, 4 + numEntries * 8))
        return -1;

    // first look for a full repertoire map
    for (idx = 0; idx < numEntries; ++idx) {
        entry = cmap + 4 + idx * 8;
        type = getu16(font, entry) * 0100 + getu16(font, entry + 2);
        // complete unicode map
        if (type == 0004 || type == 0312) {
            table = cmap + getu32(font, entry + 4);
            if (!is_safe_offset(font, table, 8))
                return -1;
            /* Dispatch based on cmap format. */
            format = getu16(font, table);
            switch (format) {
            case 12:
                return cmap_fmt12_13(font, table, charCode, glyph, 12);
            default:
                return -1;
            }
        }
    }

    // if no full repertoire cmap was found, try looking for a bmp map
    for (idx = 0; idx < numEntries; ++idx) {
        entry = cmap + 4 + idx * 8;
        type = getu16(font, entry) * 0100 + getu16(font, entry + 2);
        // unicode bmp
        if (type == 0003 || type == 0301) {
            table = cmap + getu32(font, entry + 4);
            if (!is_safe_offset(font, table, 6))
                return -1;
            // dispatch based on cmap format
            switch (getu16(font, table)) {
            case 4:
                return cmap_fmt4(font, table + 6, charCode, glyph);
            case 6:
                return cmap_fmt6(font, table + 6, charCode, glyph);
            default:
                return -1;
            }
        }
    }

    return -1;
}

static int
hor_metrics(PASTRY_Font *font, PASTRY_Glyph glyph, int *advanceWidth, int *leftSideBearing)
{
    uint_fast32_t hmtx, offset, boundary;
    if (gettable(font, "hmtx", &hmtx) < 0)
        return -1;
    if (glyph < font->numLongHmtx) {
        // glyph is inside long metrics segment
        offset = hmtx + 4 * glyph;
        if (!is_safe_offset(font, offset, 4))
            return -1;
        *advanceWidth = getu16(font, offset);
        *leftSideBearing = geti16(font, offset + 2);
        return 0;
    } else {
        // glyph is inside short metrics segment
        boundary = hmtx + 4U * (uint_fast32_t) font->numLongHmtx;
        if (boundary < 4)
            return -1;

        offset = boundary - 4;
        if (!is_safe_offset(font, offset, 4))
            return -1;
        *advanceWidth = getu16(font, offset);

        offset = boundary + 2 * (glyph - font->numLongHmtx);
        if (!is_safe_offset(font, offset, 2))
            return -1;
        *leftSideBearing = geti16(font, offset);
        return 0;
    }
}

static int
glyph_bbox(const PASTRY *pastry, uint_fast32_t outline, int box[4])
{
    double xScale, yScale;
    // raad bounding box from the font file verbatim
    if (!is_safe_offset(pastry->font, outline, 10))
        return -1;
    box[0] = geti16(pastry->font, outline + 2);
    box[1] = geti16(pastry->font, outline + 4);
    box[2] = geti16(pastry->font, outline + 6);
    box[3] = geti16(pastry->font, outline + 8);
    if (box[2] <= box[0] || box[3] <= box[1])
        return -1;
    // transform bounding box into PASTRY coordinate space
    xScale = pastry->xScale / pastry->font->unitsPerEm;
    yScale = pastry->yScale / pastry->font->unitsPerEm;
    box[0] = fast_floor(box[0] * xScale + pastry->xOffset);
    box[1] = fast_floor(box[1] * yScale + pastry->yOffset);
    box[2] = fast_ceil (box[2] * xScale + pastry->xOffset);
    box[3] = fast_ceil (box[3] * yScale + pastry->yOffset);
    return 0;
}

// returns the offset into the font that the glyph's outline is stored at
static int
outline_offset(PASTRY_Font *font, PASTRY_Glyph glyph, uint_fast32_t *offset)
{
    uint_fast32_t loca, glyf;
    uint_fast32_t base, this, next;

    if (gettable(font, "loca", &loca) < 0)
        return -1;
    if (gettable(font, "glyf", &glyf) < 0)
        return -1;

    if (font->locaFormat == 0) {
        base = loca + 2 * glyph;

        if (!is_safe_offset(font, base, 4))
            return -1;

        this = 2U * (uint_fast32_t) getu16(font, base);
        next = 2U * (uint_fast32_t) getu16(font, base + 2);
    } else {
        base = loca + 4 * glyph;

        if (!is_safe_offset(font, base, 8))
            return -1;

        this = getu32(font, base);
        next = getu32(font, base + 4);
    }

    *offset = this == next ? 0 : glyf + this;
    return 0;
}

// for a simple outline, determines each point of the outline with a set of flags
static int
simple_flags(PASTRY_Font *font, uint_fast32_t *offset, uint_fast16_t numPts, uint8_t *flags)
{
    assert(flags != NULL);
    uint_fast32_t off = *offset;
    uint_fast16_t i;
    uint8_t value = 0, repeat = 0;
    for (i = 0; i < numPts; ++i) {
        if (repeat) {
            --repeat;
        } else {
            if (!is_safe_offset(font, off, 1))
                return -1;
            value = getu8(font, off++);
            if (value & REPEAT_FLAG) {
                if (!is_safe_offset(font, off, 1))
                    return -1;
                repeat = getu8(font, off++);
            }
        }
        flags[i] = value;
    }
    *offset = off;
    return 0;
}

// for a simple outline, decodes both X and Y coordinates for each point of the outline
static int
simple_points(PASTRY_Font *font, uint_fast32_t offset, uint_fast16_t numPts, uint8_t *flags, Point *points)
{
    assert(flags != NULL);
    assert(points != NULL);
    long accum, value, bit;
    uint_fast16_t i;

    accum = 0L;
    for (i = 0; i < numPts; ++i) {
        if (flags[i] & X_CHANGE_IS_SMALL) {
            if (!is_safe_offset(font, offset, 1))
                return -1;
            value = (long) getu8(font, offset++);
            bit = !!(flags[i] & X_CHANGE_IS_POSITIVE);
            accum -= (value ^ -bit) + bit;
        } else if (!(flags[i] & X_CHANGE_IS_ZERO)) {
            if (!is_safe_offset(font, offset, 2))
                return -1;
            accum += geti16(font, offset);
            offset += 2;
        }
        points[i].x = (double) accum;
    }

    accum = 0L;
    for (i = 0; i < numPts; ++i) {
        if (flags[i] & Y_CHANGE_IS_SMALL) {
            if (!is_safe_offset(font, offset, 1))
                return -1;
            value = (long) getu8(font, offset++);
            bit = !!(flags[i] & Y_CHANGE_IS_POSITIVE);
            accum -= (value ^ -bit) + bit;
        } else if (!(flags[i] & Y_CHANGE_IS_ZERO)) {
            if (!is_safe_offset(font, offset, 2))
                return -1;
            accum += geti16(font, offset);
            offset += 2;
        }
        points[i].y = (double) accum;
    }

    return 0;
}

static int
decode_contour(uint8_t *flags, uint_fast16_t basePoint, uint_fast16_t count, Outline *outl)
{
    assert(basePoint + count <= outl->numPoints);
    uint_fast16_t i;
    uint_least16_t looseEnd, beg, ctrl, center, cur;
    unsigned int gotCtrl;

    /* skip contours with less than two points, since my algo can't handle them and
     * they should appear invisible either way (because they don't have any area lmao) */
    if (count < 2) return 0;

    assert(basePoint <= UINT16_MAX - count);

    if (flags[0] & POINT_IS_ON_CURVE) {
        looseEnd = (uint_least16_t) basePoint++;
        ++flags;
        --count;
    } else if (flags[count - 1] & POINT_IS_ON_CURVE) {
        looseEnd = (uint_least16_t) (basePoint + --count);
    } else {
        if (outl->numPoints >= outl->capPoints && grow_points(outl) < 0)
            return -1;

        looseEnd = outl->numPoints;
        outl->points[outl->numPoints++] = midpoint(
                                              outl->points[basePoint],
                                              outl->points[basePoint + count - 1]);
    }
    beg = looseEnd;
    gotCtrl = 0;
    for (i = 0; i < count; ++i) {
        // cur can't overflow because we ensure that basePoint + count < 0xFFFF before calling decode_contour()
        cur = (uint_least16_t) (basePoint + i);
        if (flags[i] & POINT_IS_ON_CURVE) {
            if (gotCtrl) {
                if (outl->numCurves >= outl->capCurves && grow_curves(outl) < 0)
                    return -1;
                outl->curves[outl->numCurves++] = (Curve) {
                    beg, cur, ctrl
                };
            } else {
                if (outl->numLines >= outl->capLines && grow_lines(outl) < 0)
                    return -1;
                outl->lines[outl->numLines++] = (Line) {
                    beg, cur
                };
            }
            beg = cur;
            gotCtrl = 0;
        } else {
            if (gotCtrl) {
                center = outl->numPoints;
                if (outl->numPoints >= outl->capPoints && grow_points(outl) < 0)
                    return -1;
                outl->points[center] = midpoint(outl->points[ctrl], outl->points[cur]);
                ++outl->numPoints;

                if (outl->numCurves >= outl->capCurves && grow_curves(outl) < 0)
                    return -1;
                outl->curves[outl->numCurves++] = (Curve) {
                    beg, center, ctrl
                };

                beg = center;
            }
            ctrl = cur;
            gotCtrl = 1;
        }
    }
    if (gotCtrl) {
        if (outl->numCurves >= outl->capCurves && grow_curves(outl) < 0)
            return -1;
        outl->curves[outl->numCurves++] = (Curve) {
            beg, looseEnd, ctrl
        };
    } else {
        if (outl->numLines >= outl->capLines && grow_lines(outl) < 0)
            return -1;
        outl->lines[outl->numLines++] = (Line) {
            beg, looseEnd
        };
    }

    return 0;
}

static int
simple_outline(PASTRY_Font *font, uint_fast32_t offset, unsigned int numContours, Outline *outl)
{
    uint_fast16_t *endPts = NULL;
    uint8_t *flags = NULL;
    uint_fast16_t numPts;
    unsigned int i;
    uint_fast16_t beg;

    assert(numContours > 0);

    uint_fast16_t basePoint = outl->numPoints;

    if (!is_safe_offset(font, offset, numContours * 2 + 2))
        goto failure;
    numPts = getu16(font, offset + (numContours - 1) * 2);
    if (numPts >= UINT16_MAX)
        goto failure;
    numPts++;
    if (outl->numPoints > UINT16_MAX - numPts)
        goto failure;

    while (outl->capPoints < basePoint + numPts) {
        if (grow_points(outl) < 0)
            goto failure;
    }

    PASTRY_STACK_ALLOC(endPts, uint_fast16_t, 16, numContours);
    if (endPts == NULL)
        goto failure;
    PASTRY_STACK_ALLOC(flags, uint8_t, 128, numPts);
    if (flags == NULL)
        goto failure;

    for (i = 0; i < numContours; ++i) {
        endPts[i] = getu16(font, offset);
        offset += 2;
    }
    /* ensure that endPts are never falling
     * falling endPts have no sensible interpretation and idk probably only exist in bad inputs
     *
     * so... just bail? */
    for (i = 0; i < numContours - 1; ++i) {
        if (endPts[i + 1] < endPts[i] + 1)
            goto failure;
    }
    offset += 2U + getu16(font, offset);

    if (simple_flags(font, &offset, numPts, flags) < 0)
        goto failure;
    if (simple_points(font, offset, numPts, flags, outl->points + basePoint) < 0)
        goto failure;
    outl->numPoints = (uint_least16_t) (outl->numPoints + numPts);

    beg = 0;
    for (i = 0; i < numContours; ++i) {
        uint_fast16_t count = endPts[i] - beg + 1;
        if (decode_contour(flags + beg, basePoint + beg, count, outl) < 0)
            goto failure;
        beg = endPts[i] + 1;
    }

    PASTRY_STACK_FREE(endPts);
    PASTRY_STACK_FREE(flags);
    return 0;
failure:
    PASTRY_STACK_FREE(endPts);
    PASTRY_STACK_FREE(flags);
    return -1;
}

static int
compound_outline(PASTRY_Font *font, uint_fast32_t offset, int recDepth, Outline *outl)
{
    double local[6];
    uint_fast32_t outline;
    unsigned int flags, glyph, basePoint;
    // guard against compound glyphs that have themselves as component (wtf)
    if (recDepth >= 4)
        return -1;
    do {
        memset(local, 0, sizeof local);
        if (!is_safe_offset(font, offset, 4))
            return -1;
        flags = getu16(font, offset);
        glyph = getu16(font, offset + 2);
        offset += 4;
        // i refuse to implement point matching, and neither does stb_truetype for that matter, so fuck you
        if (!(flags & ACTUAL_XY_OFFSETS))
            return -1;
        // read additional X and Y offsets (in FUnits) of this component
        if (flags & OFFSETS_ARE_LARGE) {
            if (!is_safe_offset(font, offset, 4))
                return -1;
            local[4] = geti16(font, offset);
            local[5] = geti16(font, offset + 2);
            offset += 4;
        } else {
            if (!is_safe_offset(font, offset, 2))
                return -1;
            local[4] = geti8(font, offset);
            local[5] = geti8(font, offset + 1);
            offset += 2;
        }
        if (flags & GOT_A_SINGLE_SCALE) {
            if (!is_safe_offset(font, offset, 2))
                return -1;
            local[0] = geti16(font, offset) / 16384.0;
            local[3] = local[0];
            offset += 2;
        } else if (flags & GOT_AN_X_AND_Y_SCALE) {
            if (!is_safe_offset(font, offset, 4))
                return -1;
            local[0] = geti16(font, offset + 0) / 16384.0;
            local[3] = geti16(font, offset + 2) / 16384.0;
            offset += 4;
        } else if (flags & GOT_A_SCALE_MATRIX) {
            if (!is_safe_offset(font, offset, 8))
                return -1;
            local[0] = geti16(font, offset + 0) / 16384.0;
            local[1] = geti16(font, offset + 2) / 16384.0;
            local[2] = geti16(font, offset + 4) / 16384.0;
            local[3] = geti16(font, offset + 6) / 16384.0;
            offset += 8;
        } else {
            local[0] = 1.0;
            local[3] = 1.0;
        }
        /* at this point, apple more or less tells you to scale the matrix by its own L1
         * norm but stb_truetype scales by the L2 norm, and freetype doesn't scale at all
         * microsoft's spec doesn't even mention anything like this, it just tells you to
         * go fuck yourself
         *
         * hm idk it feels like nobody ever uses this feature */
        if (outline_offset(font, glyph, &outline) < 0)
            return -1;
        if (outline) {
            basePoint = outl->numPoints;
            if (decode_outline(font, outline, recDepth + 1, outl) < 0)
                return -1;
            transform_points(outl->numPoints - basePoint, outl->points + basePoint, local);
        }
    } while (flags & THERE_ARE_MORE_COMPONENTS);

    return 0;
}

static int
decode_outline(PASTRY_Font *font, uint_fast32_t offset, int recDepth, Outline *outl)
{
    int numContours;
    if (!is_safe_offset(font, offset, 10))
        return -1;
    numContours = geti16(font, offset);
    if (numContours > 0) {
        // glyph has a simple outline consisting of a number of contours
        return simple_outline(font, offset + 10, (unsigned int) numContours, outl);
    } else if (numContours < 0) {
        // glyph has a compound outline combined from mutiple other outlines
        return compound_outline(font, offset + 10, recDepth, outl);
    } else {
        return 0;
    }
}

// weird thing to tell whether a given curve can be approximated closely enough by a line
static int
is_flat(Outline *outl, Curve curve)
{
    const double maxArea2 = 2.0;
    Point a = outl->points[curve.beg];
    Point b = outl->points[curve.ctrl];
    Point c = outl->points[curve.end];
    Point g = { b.x-a.x, b.y-a.y };
    Point h = { c.x-a.x, c.y-a.y };
    double area2 = fast_abs(g.x*h.y-h.x*g.y);
    return area2 <= maxArea2;
}

static int
tessellate_curve(Curve curve, Outline *outl)
{
    /* i can conclude that this stack barely reaches a top height of 4 elements
     * even for the largest font sizes that i wanna support, and as space reqs
     * only grow logarithmically, 6 feels like it's more than enough */
#define STACK_SIZE 6
    Curve stack[STACK_SIZE];
    unsigned int top = 0;
    for (;;) {
        if (is_flat(outl, curve) || top >= STACK_SIZE) {
            if (outl->numLines >= outl->capLines && grow_lines(outl) < 0)
                return -1;
            outl->lines[outl->numLines++] = (Line) {
                curve.beg, curve.end
            };
            if (top == 0) break;
            curve = stack[--top];
        } else {
            uint_least16_t ctrl0 = outl->numPoints;
            if (outl->numPoints >= outl->capPoints && grow_points(outl) < 0)
                return -1;
            outl->points[ctrl0] = midpoint(outl->points[curve.beg], outl->points[curve.ctrl]);
            ++outl->numPoints;

            uint_least16_t ctrl1 = outl->numPoints;
            if (outl->numPoints >= outl->capPoints && grow_points(outl) < 0)
                return -1;
            outl->points[ctrl1] = midpoint(outl->points[curve.ctrl], outl->points[curve.end]);
            ++outl->numPoints;

            uint_least16_t pivot = outl->numPoints;
            if (outl->numPoints >= outl->capPoints && grow_points(outl) < 0)
                return -1;
            outl->points[pivot] = midpoint(outl->points[ctrl0], outl->points[ctrl1]);
            ++outl->numPoints;

            stack[top++] = (Curve) {
                curve.beg, pivot, ctrl0
            };
            curve = (Curve) {
                pivot, curve.end, ctrl1
            };
        }
    }
    return 0;
#undef STACK_SIZE
}

static int
tessellate_curves(Outline *outl)
{
    unsigned int i;
    for (i = 0; i < outl->numCurves; ++i) {
        if (tessellate_curve(outl->curves[i], outl) < 0)
            return -1;
    }
    return 0;
}

// draws a line into the buffer, custom 2d raycasting algo is used
static void
draw_line(Raster buf, Point origin, Point goal)
{
    assert(buf.cells != NULL);
    assert(buf.width > 0 && buf.height > 0);
    Point delta;
    Point nextCrossing;
    Point crossingIncr;
    double halfDeltaX;
    double prevDistance = 0.0, nextDistance;
    double xAverage, yDifference;
    struct
    {
        int x, y;
    } pixel;
    struct
    {
        int x, y;
    } dir;
    int step, numSteps = 0;
    Cell *restrict cptr, cell;

    delta.x = goal.x - origin.x;
    delta.y = goal.y - origin.y;
    dir.x = SIGN(delta.x);
    dir.y = SIGN(delta.y);

    if (!dir.y) {
        return;
    }

    crossingIncr.x = dir.x ? fast_abs(1.0 / delta.x) : 1.0;
    crossingIncr.y = fast_abs(1.0 / delta.y);

    if (!dir.x) {
        pixel.x = fast_floor(origin.x);
        nextCrossing.x = 100.0;
    } else {
        if (dir.x > 0) {
            pixel.x = fast_floor(origin.x);
            nextCrossing.x = (origin.x - pixel.x) * crossingIncr.x;
            nextCrossing.x = crossingIncr.x - nextCrossing.x;
            numSteps += fast_ceil(goal.x) - fast_floor(origin.x) - 1;
        } else {
            pixel.x = fast_ceil(origin.x) - 1;
            nextCrossing.x = (origin.x - pixel.x) * crossingIncr.x;
            numSteps += fast_ceil(origin.x) - fast_floor(goal.x) - 1;
        }
    }

    if (dir.y > 0) {
        pixel.y = fast_floor(origin.y);
        nextCrossing.y = (origin.y - pixel.y) * crossingIncr.y;
        nextCrossing.y = crossingIncr.y - nextCrossing.y;
        numSteps += fast_ceil(goal.y) - fast_floor(origin.y) - 1;
    } else {
        pixel.y = fast_ceil(origin.y) - 1;
        nextCrossing.y = (origin.y - pixel.y) * crossingIncr.y;
        numSteps += fast_ceil(origin.y) - fast_floor(goal.y) - 1;
    }

    nextDistance = MIN(nextCrossing.x, nextCrossing.y);
    halfDeltaX = 0.5 * delta.x;

    for (step = 0; step < numSteps; ++step) {
        xAverage = origin.x + (prevDistance + nextDistance) * halfDeltaX;
        yDifference = (nextDistance - prevDistance) * delta.y;
        cptr = &buf.cells[pixel.y * buf.width + pixel.x];
        cell = *cptr;
        cell.cover += yDifference;
        xAverage -= (double) pixel.x;
        cell.area += (1.0 - xAverage) * yDifference;
        *cptr = cell;
        prevDistance = nextDistance;
        int alongX = nextCrossing.x < nextCrossing.y;
        pixel.x += alongX ? dir.x : 0;
        pixel.y += alongX ? 0 : dir.y;
        nextCrossing.x += alongX ? crossingIncr.x : 0.0;
        nextCrossing.y += alongX ? 0.0 : crossingIncr.y;
        nextDistance = MIN(nextCrossing.x, nextCrossing.y);
    }

    xAverage = origin.x + (prevDistance + 1.0) * halfDeltaX;
    yDifference = (1.0 - prevDistance) * delta.y;
    cptr = &buf.cells[pixel.y * buf.width + pixel.x];
    cell = *cptr;
    cell.cover += yDifference;
    xAverage -= (double) pixel.x;
    cell.area += (1.0 - xAverage) * yDifference;
    *cptr = cell;
}

static void
draw_lines(Outline *outl, Raster buf)
{
    unsigned int i;
    for (i = 0; i < outl->numLines; ++i) {
        Line  line   = outl->lines[i];
        Point origin = outl->points[line.beg];
        Point goal   = outl->points[line.end];
        draw_line(buf, origin, goal);
    }
}

// integrate the values in the buffer to arrive at the final grayscale image
static void
post_process(Raster buf, uint8_t *image)
{
    Cell cell;
    double accum = 0.0, value;
    unsigned int i, num;
    num = (unsigned int) buf.width * (unsigned int) buf.height;
    for (i = 0; i < num; ++i) {
        cell     = buf.cells[i];
        value    = fast_abs(accum + cell.area);
        value    = MIN(value, 1.0);
        value    = value * 255.0 + 0.5;
        image[i] = (uint8_t) value;
        accum   += cell.cover;
    }
}

static int
render_outline(Outline *outl, double transform[6], PASTRY_Image image)
{
    assert(outl != NULL);
    assert(transform != NULL);
    assert(image.pixels != NULL);
    assert(image.width > 0 && image.height > 0);
    Cell *cells = NULL;
    Raster buf;
    unsigned int numPixels;

    numPixels = (unsigned int) image.width * (unsigned int) image.height;

    PASTRY_STACK_ALLOC(cells, Cell, 128 * 128, numPixels);
    if (!cells) {
        return -1;
    }
    memset(cells, 0, numPixels * sizeof *cells);
    buf.cells  = cells;
    buf.width  = image.width;
    buf.height = image.height;

    transform_points(outl->numPoints, outl->points, transform);

    clip_points(outl->numPoints, outl->points, image.width, image.height);

    if (tessellate_curves(outl) < 0) {
        PASTRY_STACK_FREE(cells);
        return -1;
    }

    draw_lines(outl, buf);

    post_process(buf, image.pixels);

    PASTRY_STACK_FREE(cells);
    return 0;
}