Perfecting TrueType parsing

Let's review what happened last chapter when we tried to read the TrueType file.

First, the TrueType font is a binary file and therefore we needed a class rpnBinary for all data types that binary files have: bytes (8bit), words (16bit), long words (32 bit), rational numbers (actually 32 bit integers divided by 256*256, strings and date.

Then, a TrueType is just a collection of tables, so we read first the header which gives us at offset 4 a word with the number of tables. Then we start at offset 10 reading the table index into a dictionary, where each entry is 16 bytes: a type (4 letters), checksum, offset and length. For each table, we can then jump to the offset and start read. Each type of table has it's own structure.

The tables are deeply interconnected. You net to jump to get all the information.

Table head: the only values we are interested are unitsPerEm which is the scaling factor and indexToLocFormat which tells us if the offsets in the glyphs are 16bit or 32bit (for big font files).
Table maxp: this gives us the number of glyphs numglypghs.
Table cmap makes the translation between the character values and the position inside the glyphs. This table is quite complicated because there are multiple methods to make the translation, depending on platform and encoding. We assume there is at least a method supporting unicode and either windows or unix. This is the famous format 4, apparently most TrueType fonts support. The table is then a list of segments that have the same offset. For example 10-19 is mapped to 0-9, 30-90 to 10-70, 100-127 to 70-87 and 65535-65535 is always mapped to 0.
Table hhea: this gives us typographic values like lineGap, ascent and descent we do not yet use, but PS Type 3 fonts had them too in their dictionary. It gives us also the number of widths numOfLongHorMetrics. I wonder why this should be different from numglypghs.
Table hmtx gives the widths advanceWidth for each glyph (actually numOfLongHorMetrics times).
Table loca gives for each of the numGlyphs glyphs the offset in the glyf table.

Table glyf finally gives us the paths for each glyph in a highly compressed offset. Every byte is optimised.

First, we get the numberOfContours paths. A letter like F has only one path, O and R have 2, % has 5.
For each path we then get the final point that closes the path endPtsOfContours.
We then have instruction but apparently of no use, I ignore them.
Then we have the points and that is highly compressed. Every information that can be induced will be omitted.
We read first for each point a one byte flag and prefill the positions x and y with 0. The flag tells us if the point is on the curve, if x and y are the same values as the previous values. In that case, it has to read only one and not two coordinates.
We then read the x and y values with a function readCoords
But actually, we do not get all points. Normally, on quadratic bezier curves there should always be a point on curve and a control point that is not on curve. However, when you inspect the values, there a much more control points than curve points. This is en extra compression: If two control points follow, there is an implied on-curve point exactly between the control points. This happens quite often because symmetrical control points make well balanced paths.

Javascript Editor

rpnBinary = class { 
   constructor (buffer) {
       this.data = new Uint8Array(buffer.length);
       for(var i=0; i < buffer.length; i++) {
           this.data[i] = buffer.codePointAt(i);
       }
       this.position = 0
       this.position = 0;
   }
   getUint8() { return this.data[this.position++]; }
   getUint16() { return this.getUint8() * 256 + this.getUint8(); }
   getUint32() { return this.getUint8() * 256*256*256 + this.getUint8() * 256*256 + this.getUint8() * 256 + this.getUint8(); }
   getInt16() { 
       var n = this.getUint16(); 
       if (n & 0x8000) n -= 1 * 256*256;
       return n;
   }
   getInt32 () { return this.getUint32(); }
   getFWord() { return this.getInt16() ; }
   getUFWord() { return this.getUint16() ; }
   getOffset16() { return this.getUint16() ; }
   getOffset32() { return this.getUint32() ; }
   getF2Dot14() { return this.getInt16() * 1.0 / (256*64) ; }
   getFixed() { return this.getInt32() * 1.0 / (256*256)  ; }
   getString(n) { 
       var string = "";
       for (var i = 0; i < n; i++) {
           string += String.fromCharCode(this.getUint8());
       }
       return string;
   }
   getDate() { 
       const macTime = this.getUint32() * 0x100000000 + this.getUint32();
       const utcTime = macTime * 1000 + Date.UTC(1904, 1, 1)
       return new Date(utcTime);
   }
   getPosition() { return this.position; }
   setPosition(p) { this.position = p; } 
}

readSyncURL = function(url){
   const xhr=new XMLHttpRequest();
   xhr.open("GET",url,false);
   xhr.overrideMimeType("text/plain; charset=x-user-defined");//Override MIME Type to prevent UTF-8 related errors
   xhr.send();
   URL.revokeObjectURL(url);
   return xhr.responseText;
}

Javascript Editor

rpnTTF = class {
    constructor(path) {
        const file = readSyncURL(path);
        this.reader = new rpnBinary(file);

this.reader.getUint32() // scalarType
        const numTables = this.reader.getUint16()
        this.reader.getUint16() // searchRange
        this.reader.getUint16() // entrySelector
        this.reader.getUint16() // rangeShift

this.tables = {};
        for (var i = 0; i < numTables; i++) {
             const tag = this.reader.getString(4)
             this.tables[tag] = {
                 checksum: this.reader.getUint32(),
                 offset: this.reader.getUint32(),
                 length: this.reader.getUint32(),
             }
        }

this.reader.setPosition(this.tables.head.offset);
        this.head = {
            majorVersion: this.reader.getUint16(),
            minorVersion: this.reader.getUint16(),
            fontRevision: this.reader.getFixed(),
            checksumAdjustment: this.reader.getUint32(),
            magicNumber: this.reader.getUint32(),
            flags: this.reader.getUint16(),
            unitsPerEm: this.reader.getUint16(),
            created: this.reader.getDate(),
            modified: this.reader.getDate(),
            xMin: this.reader.getFWord(),
            yMin: this.reader.getFWord(),
            xMax: this.reader.getFWord(),
            yMax: this.reader.getFWord(),
            macStyle: this.reader.getUint16(),
            lowestRecPPEM: this.reader.getUint16(),
            fontDirectionHint: this.reader.getInt16(),
            indexToLocFormat: this.reader.getInt16(),
            glyphDataFormat: this.reader.getInt16()
        };
        this.reader.setPosition(this.tables.maxp.offset);
        this.maxp = {
           version: this.reader.getFixed(),
           numGlyphs: this.reader.getUint16(),
           maxPoints: this.reader.getUint16(),
           maxContours: this.reader.getUint16(),
           maxCompositePoints: this.reader.getUint16(),
           maxCompositeContours: this.reader.getUint16(),
           maxZones: this.reader.getUint16(),
           maxTwilightPoints: this.reader.getUint16(),
           maxStorage: this.reader.getUint16(),
           maxFunctionDefs: this.reader.getUint16(),
           maxInstructionDefs: this.reader.getUint16(),
           maxStackElements: this.reader.getUint16(),
           maxSizeOfInstructions: this.reader.getUint16(),
           maxComponentElements: this.reader.getUint16(),
           maxComponentDepth: this.reader.getUint16()
        }
        this.reader.setPosition(this.tables.cmap.offset);
        this.cmap = {
            version: this.reader.getUint16(),
            numTables: this.reader.getUint16(),
            encodingRecords: [],
            glyphIndexMap: {},
        }
        if (this.cmap.version) throw "truetype error camp version not 0";
        for (var i = 0; i < this.cmap.numTables; i++) {
            this.cmap.encodingRecords.push({
                platformID: this.reader.getUint16(),
                encodingID: this.reader.getUint16(),
                offset: this.reader.getOffset32(),
            })
        }
        // we only support platform 0 and and encoding 3
        var encodingsOffset = -1;
        for (var i = 0; i < this.cmap.encodingRecords.length; i++) {
            const  { platformID, encodingID, offset } =  this.cmap. encodingRecords[i];
            if ( platformID == 0 && encodingID == 3 ) encodingsOffset = offset; // unicode 
            if ( platformID == 3 && encodingID == 1 ) encodingsOffset = offset; // windows
            if (encodingsOffset > -1 ) break;
        }
        if (encodingsOffset == -1 ) throw "truetype unsupported encoding";
        this.reader.setPosition(this.tables.cmap.offset + encodingsOffset);
        const format = this.reader.getUint16();
        if (!(format == 4) ) throw "truetype unsupported format";

this.cmap.format = {
            format: 4,
            length: this.reader.getUint16(),
            language: this.reader.getUint16(),
            segCountX2: this.reader.getUint16(),
            searchRange: this.reader.getUint16(),
            entrySelector: this.reader.getUint16(),
            rangeShift: this.reader.getUint16(),
            endCode: [],
            startCode: [],
            idDelta: [],
            idRangeOffset: [],
            glyphIndexMap: {}, // This one is my addition, contains final unicode->index mapping
}
        const segCount = this.cmap.format.segCountX2 / 2; 
        for (var i = 0; i < segCount; i++) {
            this.cmap.format.endCode.push(this.reader.getUint16())
        }

this.reader.getUint16() // Reserved pad.

for (var i = 0; i < segCount; i++) {
            this.cmap.format.startCode.push(this.reader.getUint16())
        }

for (var i = 0; i < segCount; i++) {
            this.cmap.format.idDelta.push(this.reader.getInt16())
        }

const idRangeOffsetsStart = this.reader.getPosition()

for (var i = 0; i < segCount; i++) {
            this.cmap.format.idRangeOffset.push(this.reader.getUint16())
        }
 
        
         
        this.reader.setPosition(this.tables.hhea.offset);
        this.hhea = {
           version: this.reader.getFixed(),
           ascent: this.reader.getFWord(),
           descent: this.reader.getFWord(),
           lineGap: this.reader.getFWord(),
           advanceWidthMax: this.reader.getUFWord(),
           minLeftSideBearing: this.reader.getFWord(),
           minRightSideBearing: this.reader.getFWord(),
           xMaxExtent: this.reader.getFWord(),
           caretSlopeRise: this.reader.getInt16(),
           caretSlopeRun: this.reader.getInt16(),
           caretOffset: this.reader.getFWord(),
           reserved0: this.reader.getInt16(),
           reserved1: this.reader.getInt16(),
           reserved2: this.reader.getInt16(),
           reserved3: this.reader.getInt16(),
           metricDataFormat: this.reader.getInt16(),
           numOfLongHorMetrics: this.reader.getInt16()
         }
         this.reader.setPosition(this.tables.hmtx.offset);
         const hMetrics = [];
         for (var i = 0; i < this.hhea.numOfLongHorMetrics; i++) {
             hMetrics.push({
                 advanceWidth: this.reader.getUint16(),
                 leftSideBearing: this.reader.getInt16()
             })
         } 
         const leftSideBearing = [];
         for (var i = 0; i < this.maxp.numGlyphs - this.hhea.numOfLongHorMetrics; i++) {
             leftSideBearing.push(reader.getFWord())
         }
         this.hmtx = {
             hMetrics,
             leftSideBearing
         }
         this.reader.setPosition(this.tables.loca.offset);
         const loca = [];
         for (let i = 0; i < this.maxp.numGlyphs + 1; i++) {
             if (this.head.indexToLocFormat)
                 loca.push(this.reader.getOffset32());
             else
                 loca.push(this.reader.getOffset16());
         }
         this.glyphs = [];
         for (var i = 0; i < loca.length - 1; i++) {
             const multiplier = this.head.indexToLocFormat === 0 ? 2 : 1
             const locaOffset = loca[i] * multiplier;
             this.reader.setPosition(this.tables.glyf.offset + locaOffset)
             const glyph = {
                 numberOfContours: this.reader.getInt16(),
                 xMin: this.reader.getInt16(),
                 yMin: this.reader.getInt16(),
                 xMax: this.reader.getInt16(),
                 yMax: this.reader.getInt16()
             };
             glyph.endPtsOfContours = []
             for (var j = 0; j < glyph.numberOfContours; j++) {
                 glyph.endPtsOfContours.push(this.reader.getUint16());
             }
             glyph.instructionLength = this.reader.getUint16();
             glyph.instructions = [];
             for (var j = 0; j < glyph.instructionLength; j++) {
                 glyph.instructions.push(this.reader.getUint8());
             }
             const numPoints = Math.max(...glyph.endPtsOfContours)+1;
             const flags = [];
             glyph.points = []; 
             for (var j = 0; j < numPoints; j++) {
                 const flag = this.reader.getUint8();
                 flags.push(flag);
                 glyph.points.push( { x: 0, y: 0, onCurve: flag & 1 });
                 if (flag & 8) {
                     var repeatCount = this.reader.getUint8();
                     j += repeatCount;
                     while (repeatCount--) {
                         flags.push(flag);     
                          glyph.points.push( { x: 0, y: 0, onCurve: flag & 1 });              
                     }
                 } 
             }
             if (glyph.points.length) glyph.points[0]["onCurve"] = 1;

function readCoords(name, byteFlag, deltaFlag, reader) {
                var value = 0;

for (var i = 0; i < numPoints; i++) {
                    var flag = flags[i];
                    if (flag & byteFlag) {
                        if (flag & deltaFlag) {
                            value += reader.getUint8();
                        } else {
                            value -= reader.getUint8();
                        }
                    } else if (~flag & deltaFlag) {
                        value += reader.getInt16();
                    } else {
                        // value is unchanged.
                    }

glyph.points[i][name] = value;
                }
            }
            readCoords("x", 2, 16, this.reader);
            readCoords("y", 4, 32, this.reader);

this.glyphs.push(glyph); 
       
          }

}
    unicodeOffset(unicode) {
        for(var i = 0; i < this.cmap.format.segCountX2 / 2 ; i++) {
            if (unicode >= this.cmap.format.startCode[i] && unicode <= this.cmap.format.endCode[i] ) {
                 return unicode + this.cmap.format.idDelta[i]; 
            }           
        }
        return 0; //missing glyph
    }
    glyphMetrics(g) {
       
    }
    
}

Now, what does our test operator function showttf? For testing purposes, we just defined a global font variable that should be the current font. We will do this properly with findfont scalefont definefont, when we include it in the workflow. For now, we just want to see the font rendered.

For each character it finds the glyph and constructs postscript code to render the character.

It loops the point list
It adds a moveto for the first point.
If the next point is on curve, it adds a lineto.
If it is off curve, it keeps the controls point as bezier variable.
Now, if the next point is on-curve, it uses the bezier and adds a qcurveto (we will define below).

If it is off-curve, the we calculate the middle point, set a qcurveto and keep the control point as a bezier.

For each round, we must check if we reached the end of a segment and close the path with closepath and start a new one with moveto. (frankly, we could also have made the segmentation before the loop).

At the end we fill.

The entire code must be enclosed with a graphics context, where we translate to the current point and scale. We need to offset at the end by the width.

The qcurveto' is the quadratic variant of the curveto operator. As a matter of fact, each quadratic bezier can be represented by a cubic curve. Having start, end point and quadratic control points, you calculate the two cubic points being 2/3 between the endpoints and the control point

Javascript Editor

font = new rpnTTF("site/files/CMUSerif-Italic.ttf")

operators.showttf = function(context) {
    const [s] = context.pop("string");
    if (!context.graphics.current.length) {
       context.stack.push(new rpnError("nocurrentpoint"));
       return context;
    }
    if (!s) return context;
    const scale = 60 / font.head.unitsPerEm;  
    var ps = " currentpoint currentpoint translate gsave " + scale + " " + scale + " scale ";
    for(var i = 0; i < s.value.length; i++) {
        const c = s.value.charCodeAt(i);
        const gi = font.unicodeOffset(c);
        const width = font.hmtx.hMetrics[gi].advanceWidth;
        const glyph = font.glyphs[gi];
        
        if (glyph.points.length) { 
            var p = glyph.points[0]; 
            ps += p.x + " " + p.y + " moveto "; 
            var bezier = [];
            for (var j = 1; j <  glyph.points.length; j++) {
                p = glyph.points[j];  
                if (p.onCurve) {
                   if (bezier.length) {
                       ps += bezier[0] + " " + bezier[1] + " " + p.x + " " + p.y + " qcurveto ";
                       bezier = [];
                   } else
                   ps += p.x + " " + p.y + " lineto ";
                } else {
                  if (bezier.length) {
                      ps += bezier[0] + " " + bezier[1] + " " + (bezier[0] + p.x)/2 + " " + (bezier[1] + p.y)/2 + " qcurveto ";
                  } 
                  bezier = [p.x, p.y];  
                } 
                if (glyph.endPtsOfContours.includes(j)) { 
                    ps += " closepath " ;
                    if (j <  glyph.points.length-1) {
                        j++;
                         p = glyph.points[j];  
                        ps += p.x + " " + p.y + " moveto "; 
                        bezier = [];
                    }
                }      
          
           }
            ps += " fill "
        } 
        ps +=  width + " 0 translate ";
       
        
    }
    ps += " grestore neg exch neg exch translate "; 
    context = rpn(ps, context); 
    return context;
}

operators.qcurveto = function(context) {
    const [y3, x3, yq, xq] = context.pop("number","number","number","number");
    if (!y3) return context;
    if (!context.graphics.current.length) {
       context.stack.push(new rpnError("nocurrentpoint"));
    } else if (!context.graphics.path.length) {
       context.stack.push(new rpnError("nocurrentpath"));
    } else {
      const subpath = context.graphics.path.pop();
      const [xqt, yqt] = context.transform(xq.value, yq.value); 
      const [x3t, y3t] = context.transform(x3.value, y3.value);
      const [x0t, y0t] = context.graphics.current;
      const [x1t, y1t] = [x0t + 2/3*(xqt-x0t), y0t + 1/3*(yqt-y0t)];
      const [x2t, y2t] = [x3t + 2/3*(xqt-x3t), y3t + 2/3*(yqt-y3t)]; 
      subpath.push([ "C", context.graphics.current[0], context.graphics.current[1], x1t, y1t, x2t, y2t, x3t, y3t ]);
      context.graphics.path.push(subpath); 
      context.graphics.current = [ x3t, y3t ];
    }
    return context;
};

This seems to render quite well

Javascript Editor

How is our rainbow?

Javascript Editor

You need only four segments for a decent circle of cubic bezier.
With quadratic bezier, this is clumsy. You need 8 points. I did with trial and error.

Javascript Editor

We are ready now to replace the PostScript Type 3 fonts with TrueType fonts. Actually we can still decide to convert them to PostScript Type 3 fonts as the TrueType code we produce here creates PostScript code.

We wait to the next chapter to include that in the code base.

My Journey to PostScript