Working with fonts

We have mace a long journey to write our PostScript interpreter and we are finally ready to approach text. Text is what is most rendered in PostScript documents. Most layout contain texts.

Handling text in PostScript is both simple and complex. Drawing text is no other thing than defining paths and filling them with black. Text will use the same bezier and scanFill algorithms as any other shape.

But defining shapes for every document would be complex. That's where fonts enter in. Fonts are collections of paths for each character, called glyphs.

Where do we get the fonts from? Fonts are files provided in different formats. At the introduction of PostScript, most fonts where Type 1 fonts, a format promoted by Adobe and adopted by most foundaries because it was encrypted. This will not working for us. We could use TrueType fonts, but their format is very complex (hello Microsoft!). OpenType is just Type 1 and TrueType in an envelope. We could use the SVG fonts, where the paths are provided in XML format. For a reason I cannot understand, propably also to protect foundaries.

But there are Type 3 fonts. At the introduction of PostScript, Adobe proposed also this lower range format to all foundries who would not want to license Type 1. Type 3 fonts are just PostScript code.

For our interpreter, we will use the open source fonts Computer Modern. This font was created by Donald E. Knuth and it has an amazing history. Knuth is a pioneer in computer programming and wrote the book series The Art of Computer Programming which describes virtually all fundamental algorithms that have been created. The series is supposed to have 7 volumes. The first volume was published 1968, volume 4 was published 2011 and volume 5 is expected for 2030. If you are interested in programming, you should read them. I have never seen as good explanations.

When Knuth published volume 1, the book was printed in lead type. Typesetting mathematical formulas was complicated manual work with Monotype machines. And forget about a typewriter font for code. All lead fonts were proportional.

The book production was too expensive for the editor, given that the book sold less than the spy novels by Ian Fleming, the editor wanted a cheaper production for the subsequent volumes. He proposed Knuth to use a typewriter for the formulas, take a photograph of the paper and use a clichée of the photograph for the book. The graphical quality of the formulas was much lower.

Knuth could not really accept compromises and heard about recent progress of phototypesetting. This method of typesetting existed since the forties and allowed to create type optically. In the sixties, with the progress of television, experiences were made representing the type on a cathodic tube and photograph that. This transforms type into an electronic signal, furthermore a bitmap. Once the resolution was good enough (1000 lines per inch, much more than our interpreter), the type was the same quality than lead type.

So a computer provided a digital image based on a bitmap, which itself is just a sequence of 0 for black and 1 for white. With this, typesetting became an algorithmic problem. This is something Knuth could handle.

Knuth spent much of his time not only to write a word processor (TeX), but he also created a font generator (Metafont), leading to the Computer Modern font family. Knuth studied the geometry of the renaissance fonts derived from mathematical principles. But Knuth also had to learn the hard way that the Masters only loosely followed them, because pure mathematical fonts weren't so pretty. To design beautiful curves, he created an algorithm based on cubic splines. For the first font versions, he didn't know about Bézier.

There is a Truetype font at https://www.fontsquirrel.com/fonts/computer-modern
We download the fonts and convert them with FontForge to Type 3 fonts (ignore warnings on Em-Size) Note that the Metafont fonts have version for each point size. We use size 12 points.

Let's take a closer look to CMUSerif-Roman.ps

The font file starts with some comments and then creates a nested dictionary. We will comment the ones that are of interest for us.

/FontType (Type 3)
/FontMatrix [0.000488281 0 0 0.000488281 0 0 ] is the transformation matrix for point size 1. All paths are reduced by the factor of 2048.
/FontName /CMUSerif-Roman
/FontBBox {-2324 -723 2982 1915 }
/PaintType 0 def
/FontInfo

/version (0.7.0)
/Notice (Converted by Andrey V. Panov from TeX fonts. Some glyphs are copied from Blue Sky fonts released by AMS.)
/FullName (CMU Serif Roman)
/FamilyName (CMU Serif)
/Weight (Medium)
/FSType 4
/ItalicAngle 0
/isFixedPitch
/UnderlinePosition -307
/UnderlineThickness 102

/Encoding has 256 entries

13 /uni000
32 /space
33 /exclam ...
255 /ydieresis

/BuildChar { 1 index /Encoding get exch get 1 index /BuildGlyph get exec }
/BuildGlyph { 2 copy exch /CharProcs get exch 2 copy known not { pop /.notdef} if get exch pop 0 exch exec pop pop fill}
/CharProcs are the actual paths

/.notdef { 1556 0 20 20 1536 1567 setcachedevice 20 20 moveto 20 1567 lineto ... closepathh

Note that each path starts with a setchachedevice operator. This operator shows the geometry of the font with 6 values: wx wy llx lly urx ury. wx and wy define the width and height for the space used, llx, lly lower left and urx, ury the upper right corner.

Note also that Type 3 fonts do not allow for kerning.

At the end, definefont binds the dictionary to the font name CMUSerif-Roman.

To use the font, we embed it in a Javascript file and define the variable rpnFiles["CMUSerif-Roman"]. The operator run will run the code
Let's start to implement the operators we need: array, bind, definefont, for, index, readonly, run, setcachedevice. We need also to to add fontdict to the context and a rpnDictionary class.

Javascript Editor

operators.array = function(context) {
    const [n] = context.pop("number");
    if (!n) return context;
    if (n.value < 1) {
        context.error("limitcheck");
        return context;
    }
    const a = [];
    for (var i = 0; i < n.value; i++) {
        a.push(new rpnNumber(0));
    }
    context.stack.push(new rpnArray(a, context));
    return context;
}; 
unitTest("3 array","[0 0 0]");
unitTest("-3 array","!limitcheck");
unitTest("0 array","!limitcheck");
unitTest("array","!stackunderflow");

operators.bind = function(context) {
    // Expands all defined operators in procedure. We ignore that operator for the moment
    return context; 
};

operators.definefont = function(context) {
    const [d, n] = context.pop("dictionary", "name");
    if (!n) return context;
    context.fontdict[n.value] = d; 
    return context;
};

operators.for = function(context) {
    const [proc, limit, increment, initial] = context.pop("procedure", "number", "number", "number");
    if (!initial) return context;
    if (! increment.value) {
        context.error("limitcheck");
        return context;
    }
    if (increment.value > 0) { 
        for (var i = initial.value; i <= limit.value; i+= increment.value) { 
            context.stack.push(new rpnNumber(i));
            context = rpn(proc.value, context);
        }
    } else {
        for (var i = initial.value; i >= limit.value; i+= increment.value) { 
            context.stack.push(new rpnNumber(i));
            context = rpn(doit.value, context);
       }
    }
    return context;
}; 
unitTest("0 1 1 5 { add } for", "15")

operators.index = function(context) {
    const [i] = context.pop("number");
    if (!i) return context;
    if (i.value < 0) {
        context.error("limitcheck");
        return context;
    }
    if (i.value >= context.stack.length) {
        context.error("limitcheck");
        return context;
    }
    const v = context.stack[context.stack.length - i.value - 1];
    if (v.type == "array") v.reference.inc();
    if (v.type == "string") v.reference.inc();
    context.stack.push(v);
    return context;
};
unitTest("3 4 5 0 index","3 4 5 5");
unitTest("3 4 5 2 index","3 4 5 3");
unitTest("3 4 5 3 index","3 4 5 !limitcheck");
unitTest("3 4 5 -1 index","3 4 5 !limitcheck");
unitTest("index","!stackunderflow");

operators.readonly = function(context) {
    // makes a dictionary entry readonly. We ignore that operator for the moment
    return context; 
};

operators.run = function(context) {
    const [filename] = context.pop("string");
    if (!filename) return context;
    const s = rpnFiles[filename.value];
    context = rpn(s, context);
    return context;
    
}

rpnContext = class {
    constructor() { 
        this.stack = [];
        this.heap = [];
        this.lasterror = "";
        this.currentcode = "";
        this.width = 600;
        this.height = 800;
        this.data = new Uint8ClampedArray(this.width * this.height * 4);
        this.dictstack = [];
        this.dictstack.push({});
        this.graphicsstack = [];
        this.graphicsstack.push({ path: [], current: [], color: [0, 0, 0, 255], linewidth: 1, matrix : [1, 0, 0, 1, 0, 0] , font: "", size: 12 });
        this.fontdict = {};
    }
    get dict() {
        return this.dictstack[this.dictstack.length - 1];
    }
    get graphics() {
        return this.graphicsstack[this.graphicsstack.length - 1];
    }
    error(s) {
        this.lasterror = s;
        this.stack.push(new rpnError(s));
        return this;
    }
    itransform(x,y) {
       const m = this.graphics.matrix; 
       const det = m[0]*m[3] - m[1]*m[2]
       return [ (x*m[3] - y*m[2] +m[2]*m[5] - m[4]*m[3])/det, 
(-x*m[1] + y*m[0] + m[4]*m[1] - m[0]*m[5])/det ]
    }
    pop(...parameters) {
        if (this.stack.length < parameters.length) {
            this.error("stackunderflow");
            return [];
        }
        const result = [];
        for (var p of parameters) {
            const data = this.stack.pop(); 
            if (p == "any") {
                result.push(data);
            } else if (p.includes(data.type)) {
                result.push(data);   
            } else {
                this.error("typeerror");
                return [];
            }
         }
         return result;
    }
    popArray() {
        var found = false;
        var arr = [];
        while (this.stack.length && ! found) {
            const value = this.stack.pop();
            if (value.type == "mark") {
                found = true;
            } else {
                arr.push(value);
            }   
        }
        if (! found) {
            return this.error("stackunderflow");
        }
        arr.reverse();
        const a = new rpnArray(arr, this);
        a.reference.inc();
        this.stack.push(a); 
    }
    transform(x,y) {
       const m = this.graphics.matrix; 
       return [ x * m[0] + y * m[2] + m[4],
x * m[1] + y * m[3] + m[5] ];
    }
};

And we test it with the font.

Javascript Editor

We get syntax errors. It looks like our parser for name was too strict. Name can also have "-" and "." We need to adapt the parser. Run the fix below an try again

Javascript Editor

rpn = function(s, context = null ) {  
    if (!context) context = new rpnContext();
    const list = s.concat(" ").split("");
    var state = "start";
    var current = "";
    var depth = 0;
    for (elem of list) {
        if (context.lasterror) {
           return context;
        }
        context.currentcode += elem;
        switch (state) {
            case "start":
                if (/[0-9-]/.test(elem)) {
                    state = "number";
                    current = elem;
                } else if (/[a-zA-Z]/.test(elem)) {
                    state = "operator";
                    current = elem;
                }  else if (elem == "/") {
                    state = "namestart";
                }  else if (elem == "{") {
                    state = "procedure";
                }  else if (elem == "(") {
                    state = "string";
                }  else if (elem == "[") {
                    context.stack.push(new rpnMark()); //mark
                }  else if (elem == "]") {
                    context.popArray();
                }  else if (elem == "%") {
                    state = "comment";
                }  else if (elem.trim() === '') {
                    // ignore whitespace
                }  else  {
                    context.error("syntaxerror");
                } 
                break;
            case "number":
                if (/[0-9]/.test(elem)) {
                    current += elem;
                } else if (elem == ".") {
                    state = "fraction";
                    current += elem;
                } else if (/[a-zA-Z-]/.test(elem)) {
                    context.error("syntaxerror");
                }  else if (elem.trim() === "") {
                    context.stack.push(new rpnNumber(parseFloat(current)));
                    state = "start";
                    current = "";
                } else if (elem == "]") {
                    context.stack.push(new rpnNumber(parseFloat(current)));
                    state = "start";
                    current = "";
                    context.popArray();
                } else if (elem == "/") {
                    context.stack.push(new rpnNumber(parseFloat(current)));
                    state = "name";
                    current = "";
                }  else {
                    context.error("syntaxerror");
                }
                break;
            case "fraction":
                if (/[0-9]/.test(elem)) {
                    current += elem;
                } else if (elem.trim() === "") {
                    context.stack.push(new rpnNumber(parseFloat(current)));
                    state = "start";
                    current = "";
               } else if (elem == "]") {
                    context.stack.push(new rpnNumber(parseFloat(current)));
                    state = "start";
                    current = "";
                    context.popArray();
                } else if (elem == "/") {
                    context.stack.push(new rpnNumber(parseFloat(current)));
                    state = "name";
                    current = "";
               } else {
                    context.error("syntaxerror");
               }
               break;
            case "operator":
                if (/[a-zA-Z0-9]/.test(elem)) {
                    current += elem;
                } else if (elem.trim() !== "" && elem != "]"){
                    context.error("syntaxerror");
                } else {
                    var data = context.dict[current];
                    if (!data) {
                        for(var i = context.dictstack.length - 1; i >= 0; i--) {
                            data = context.dictstack[i][current];
                            if (data) {
                                i = 0; // break
                            }
                        }
                    }
                    const op = operators[current];
                    if (data) {
                       if (data.type == "procedure") {
                          context = rpn(data.value, context);
                       } else if (data.type == "array"){
                            data.reference.inc();
                            context.stack.push(data);
                       } else if (data.type == "string"){
                            data.reference.inc();
                            context.stack.push(data);
                       } else {
                            context.stack.push(data);
                       }
                    } else if (op) {
                       context = op(context);
                    } else {
                    context.error("syntaxerror");
                    }
                    state = "start";
                    current = "";
                    if (elem == "]") {
                       context.popArray();
                    }

}
                break;
           case "namestart":
                if (/[a-zA-Z.]/.test(elem)) {
                    state = "name";
                    current = elem;
                } else {
                    context.error("syntaxerror");
                }
                break;
            case "name":
                if (/[a-zA-Z0-9-.]/.test(elem)) {
                    current += elem;
                } else if (elem.trim() === "") {
                    context.stack.push(new rpnName(current));
                    state = "start";
                    current = "";
               } else if (elem == "]") {
                    context.stack.push(new rpnName(current));
                    state = "start";
                    current = "";
                    context.popArray();
               } else  {
                    context.error("syntaxerror");
               }
                break;
            case "procedure":
               if (elem == "}") {
                   if (depth) {
                      depth--;
                      current += elem;
                   } else {
                        context.stack.push(new rpnProcedure(current));
                        state = "start";
                        current = "";
                   }
               } else if (elem == "{") {
                  depth++;
                  current += elem;
               } else {
                   current += elem;
               }
               break;
           case "string":
               if (elem == ")") {
                   if (depth) {
                      depth--;
                      current += elem;
                   } else {
                        const s = new rpnString(current, context);
                        s.reference.inc();
                        context.stack.push(s);
                        state = "start";
                        current = "";
                   }
               } else if (elem == "(") {
                  depth++;
                  current += elem;
               } else {
                   current += elem;
               }
               break;
           case "comment":
             if (elem == endofline ) {
                state = "start";
             }
        } // switch state
    } // for
    if (state !== "start") {
       context.error("syntaxerror");
    }
    return context;
};

operators.put = function(context) {
    const [c, b, a] = context.pop("any", "number", "array,string");
    if (!c) return context;
    if (b.value < 0) return context.error("rangerror");
    if (b.value >= a.value.length) return context.error("rangerror");
    if (a.type == "array") {
       const ch = [ c ];
       const s = a.value.slice(0, b.value).concat(ch).concat(a.value.slice(b.value + 1, a.value.length));
       a.replace(s);
    } else {
       const ch = String.fromCharCode(c.value);
       const s = a.value.slice(0, b.value) + ch + a.value.slice(b.value + 1, a.value.length);
       a.replace(s);
    }
   // a.reference.inc();
    return context;
};

postScriptEditor = function(code) {
    const id = Math.floor(Math.random() * 1000);  // create unique id for console.log
    const node = document.createElement("DIV");   // build the HTML nodes
    node.id = "id" & id;
    node.className = "psmain";
    const node2 = document.createElement("DIV");
    node2.className = "editzone";
    node.appendChild(node2);
    const node3 = document.createElement("DIV");
    node3.className = "editheader";
    node3.innerHTML = "PostScript";
    node2.appendChild(node3);
    const node4 = document.createElement("FORM");
    node2.appendChild(node4);
    const node5 = document.createElement("BUTTON");
    node5.type = "button";
    node5.id = "button" + id;
    node5.innerHTML = "Run";
    node4.appendChild(node5);
    const node6 = document.createElement("TEXTAREA"); 
    node6.id = "editor" + id; 
    node6.className = "pseditor"; 
    node6.innerHTML = code;
    node6.rows = code.split(endofline).length + 1;
    node4.appendChild(node6);
    const node7 = document.createElement("DIV");
    node7.id = "console" + id;
    node7.className = "jsconsole";
   
    const node8 = document.createElement("CANVAS");
    node8.id = "canvas" + id;
    node8.className = "jscanvas";
    node8.width = 590;
    node8.height = 330;
    node.appendChild(node8);
    node.appendChild(node7);

console.log(node.outerHTML);  // add the node to the parent element

const script = `redirectConsole($id);
        run$id = function() {
        redirectConsole($id);
        const width = 590;
        const height = 330;
        const data = new Uint8ClampedArray(width * height * 4);
        // make it white
        for(i = 0; i< data.length; i++) data[i] = 255;
        const code = document.getElementById("editor$id").value;
        var context = new rpnContext; 
        context.data = data;
        context.width = width;
        context.height = height; 
        context = rpn(code, context);

console.log("stack: " + context.stack.reduce((acc,v) => acc + v.dump + " " , " "));
        if (context.lasterror) {
            console.log("rpn: " + context.currentcode);
        }
        for (key in context.graphics) {
            console.log(key + ": " + context.graphics[key]);
        }
        for (key in context.fontdict) {
            console.log("Font " + key);
        }
        for (key in context.dict) {
            console.log(key + " = " + (context.dict[key].dump));
        }
       if (context.heap.length) { 
       console.log("heap: " + context.heap.reduce(                            function(acc, v) { 
          const val = v.value; 
          if (Array.isArray(val)) {
            return acc + "<br>[" + val.reduce( (acc2, v2) => acc2 + v2.dump + " " , " ") + "] "+v.counter+"<br>";
          } else if (val === null) {
            return acc + "<br>";
          } else {
            return acc + "<br>(" + val + ") "+v.counter;
          }
       }  , "")); 
    }
    const image = new ImageData(context.data, width);
    const canvas = document.getElementById("canvas$id");
    ctx = canvas.getContext("2d");
    ctx.putImageData(image, 0,0);
    };
    document.getElementById("button$id").onclick = run$id;`.replaceAll("$id", id).replaceAll("$code",code);
    const scriptnode = document.createElement("SCRIPT");
    scriptnode.innerHTML = script;
    document.body.appendChild(scriptnode);  // run the script
};

The codebase is now 1728 lines. ps20240803.js

In the next chapter we will use the fonts.

Links on Type 3 fonts

https://luc.devroye.org/type3.html

My Journey to PostScript