Addition Font

Shaping

When laying out text using a font file, the code points in the string are mapped one-to-one to glyphs inside the file. A glyph is a little picture inside the font file, and is identified by ID, which is a number from 0 - 65535. However, there’s a step after character mapping but before rasterization: shaping.

For example, one application of shaping is seen in Arabic text. In Arabic, each letter has four different forms, depending on which letters are next to it. For example, two letters in their isolated form look like ف and ي but as soon as you put them together, they form new shapes and look like في. This type of modification isn’t possible if characters are naively mapped to glyphs and then rasterized directly. Instead, there needs to be a step in the middle to modify the glyph forms so the correct thing is rasterized.

This “middle step” is called shaping, and is implemented by three tables inside the OpenType font file: GSUB, GPOS, and GDEF. Let’s consider GSUB alone.

GSUB

The GSUB table, or “glyph substitution” table, is designed to let font authors replace glyphs with other glyphs. It describes a transformation where the input is a sequence of glyphs and the output is a different sequence of glyphs. It is made up of a collection of constituent “lookup tables,” each of which has a “type.”

Type 1 (“single substitution”) provides a map from glyph to glyph. This is used for example, when someone enables the ‘swsh’ feature, the font can substitute out the ampersand with a fancy ampersand. In that situation, the map would contain a mapping from the regular ampersand to the fancy ampersand (possibly in addition to some more additional mappings, too).

Type 2 (“multiple substitution”) provides a map from glyph to sequence-of-glyphs. This is used, for example, if diacritic (accent) marks are represented as separate glyphs inside the font. The font can replace the “è” glyph with the “e" glyph followed by the ◌̀ glyph (and then the GPOS table later can position the two glyphs physically on top of each other).

Type 4 (“ligature substitution”) provides a map of sequence-of-glyphs to single glyph (the opposite of type 2). This is used for ligatures, so if you have a fancy “ffi” ligature, you can represent all three of those letters in the same fancy glyph.

Type 5 (“contextual substitution”) is special. It doesn’t do any replacements directly, but instead maps a sequence of glyphs to a list of other tables that should be applied at specific points in the glyph sequence. So it can say things like “in the glyph sequence ‘abcde’, apply table #7 at index 2, and then when you’re done with that, apply table #13 at index 4.” Tables #7 and #13 can be any of the types above, so you could use this table to say something like “swap out the ‘d’ for an ‘f’, but only if it appears in the sequence ‘abcde’.” This sort of thing is used to implement the “contextual alternates” feature.

There are also three other types, but they’re not particularly relevant, so I’m going to ignore them.

So, the inputs to the text system are a set of features and an input string of glyphs (The characters have already been mapped to glyphs via the “cmap” table). Features are mapped to a set of lookup tables, each of which is of a type listed above. Each of those lookup tables describes a map where the keys are sequences of glyphs, so the runtime iterates through the glyph sequence until it finds a sequence that’s an input to one of the tables. The runtime then performs that glyph replacement according to the rules of the tables, and continues iterating.

Turing Complete

So this is pretty cool, but it turns out that the contextual substitution lookup type is really powerful. This is because the table that it references can be itself, which means it can be recursive.

Let’s pretend we have a lookup table named 42 (presumably because it’s the 42nd lookup table inside the font), and it’s a contextual substitution lookup table. This table maps glyph sequences to tuples of (lookup table to recurse to, offset in glyph sequence to recurse). Let’s say we design it with these two mappings:

Table42 {
    A A : (Table42, 1);
    A B : (Table100, 1);
}

If the runtime is operating on a glyph sequence of “AAAAB”, the first two “AA”s will match the first rule, so then the system recurses and runs Table42 on the stream “AAAB”. Then these first two “AA”s will match, and so-on. This happens until you get to the end of the string, “AB” matches, and then Table100 is run on the string “B”.

This is “tail recursion,” and can be used to implement all different types of loops. Also, each mapping in the table acts as an “if” statement because it only executes if the pattern is matched.

You can use the glyph stream as memory by reading and writing to it; that is, after all, what the shaping algorithm is designed to do. You can delete a glyph by using Type 2 to map it to an empty sequence. You can insert a glyph by using Type 2 to map the preceding glyph to a sequence of [itself, the new glyph you want to insert]. And, once you’ve inserted a glyph, you can check for its presence by using the “if” statements described above.

So thats a pretty powerful virtual machine. I think the above is sufficient to prove Turing complete-ness.

Caveat

So it turns out the example (“Table42”) above doesn’t actually work in DirectWrite. This is because, in DirectWrite, inner matches have to be entirely contained within outer matches. So when the outer call to Table42 matched “AA”, the inner call to Table42 can only match within that specific “AA”. This means it’s impossible to, for example, find the first even glyphID and move it to the beginning. So, DirectWrite’s implementation isn’t Turing complete. However, it does work in HarfBuzz and CoreText, so those implementations are Turing complete.

But even in HarfBuzz and CoreText, there are hard limits on the recursion depth. HarfBuzz sets its limit to 6. Therefore, the above example will only work on strings of length 7 or fewer. HarfBuzz is open source, though, so I simply used a custom build of HarfBuzz which bumps up this limit to 4 billion. This let me recurse to my heart’s content. A limit of 6 is probably a good thing; I don’t think users generally expect their text engines to be running arbitrary computation during layout. But I want to go beyond it.

DSL

After making the above realizations, I decided to try to implement a nontrivial algorithm using only the GSUB table in a font. I wanted to try to implement addition. The input glyph stream would be of the form “=1234+5678=” and the shaping process would turn that string into “6912”.

When thinking about how to do this, I started jotting down some ideas on paper for what the lookup tables should be, and the things I were writing down were very similar to that “Table42” example above. However, writing down tables of types 1, 2, and 4 was quite cumbersome, because what I really wanted to describe were things like “move this glyph to the beginning of the sequence” rather than individual insertions or deletions.

I looked at the “fea” language, which is how these lookups are traditionally written by font designers. However, after reading the parser, it looks like it doesn’t support recursive or mutually-recursive lookups. So, I rolled my own.

So, I did what any good programmer does in this situation: I invented a new domain-specific language.

The DSL has two types of statements. The first is a way of giving a set of glyphs a name. I wanted to be able to address all of the digits without having to write out every individual digit. So, there’s a statement that looks like this:

digit: 1 2 3 4 5 6 7 8 9 10;

Note that those numbers are glyph IDs, not code points. In my specific font, the “0” character is mapped to glyph 1, “1” is mapped to glyph 2, etc.

Then, you can describe a lookup using the syntax above:

digitMove {
    digit digit: (1, digitMove), (1, digitMove2);
    digit plus: (1, digitMove2);
}

The lookup is named digitMove, and it has two rules inside it. The first rule matches any two digits next to each other, and if they match, it invokes the lookup named digitMove (which is the name of the current lookup, so this is recursive) at index 1, and then after that, invokes the lookup named digitMove2 at index 1.

Each of these stanzas gets translated fairly trivially to lookup with type 5.

These rules are recursive, as above, but they need a terminal form so that the recursion will eventually end. Those are described like this:

flagPayload {
    digit digit plus digit: flag \3 \0 \1 \2;
}

This rule is a terminal because there are no parentheses on the right side of the colon. The right side represents a glyph sequence to replace the match with. The values on the right side are either a literal glyph ID, a glyph set that contains exactly one glyph, or a backreference which starts with a backslash. “\3” means “whatever glyph was third glyph in the matched sequence”. So the rule above would turn the glyph sequence “34+5” into the sequence “F534+”. (The flag glyph is read and removed in a later stage of processing).

Translating one of these rules to lookups is nontrivial. I tried a few things, but ended up with the following design:

For each output glyph, right to left:

• If it’s a backreference, duplicate the glyph it’s referencing, and perform a sequence of swaps to move the new glyph all the way to the right.
• If it’s a literal glyph, insert it at the beginning, and perform a sequence of swaps to move it all the way to the right.

This means we need to have a way to do the following operations:

• Duplicate. This is a type 4 lookup that maps every glyph to a sequence of two of that glyph.
• Swap. This has two pieces: a type 5 lookup that has a rule for every combination of two glyphs, and each rule maps each glyph to a lookup of type 1 which replaces it with the appropriate glyph. This means you need n of these inner (type 1) lookups, allowing you to map any glyph to any other glyph. However, the encoding format allows us to encode each of these inner lookups in constant space in the font, so these inner lookups don’t take that much space. Instead, the outer type 5 lookup takes n^2 space.
• Insert a literal. If you implemented this by simply making a type 2 that mapped every glyph to that same glyph + the literal, you would need n^2 space because there would be n of these tables. Instead, you can cut down the size by doing it in two phases: inserting a flag glyph (which is O(n) space using a lookup type 2) and mapping that glyph to any constant value (also O(n) space using a type 1).

Above, I’m worried about space constraints in the file because pointers in the file are (in general) 2 bytes, meaning the maximum size that anything can be is 2^16. If n^2 space is needed, that means n can only be 2^8 = 256, which isn’t that big. Most fonts have on the order of 256 glyphs. Therefore, we need to reduce the places where we require O(n^2) space as much as possible. LookupType 7 helps somewhat, because it allows you to use 32-bit pointers in on specific place, but it only helps that one place.

My font only has 14 glyphs in it, so i didn’t end up near any of these limits, but it’s still important to watch out for out-of-bounds problems.

So, given all that, we can make a parser which builds an AST for the language, and we can build an intermediate representation which represents the bytes in the file, and we can make a lowering phase which lowers the AST to the IR. Then we can serialize the IR and write out the data to the file.

Addition

So, once the language was up and running, I had to actually write a program that represented addition. It works in four phases.

First, define some glyphs:

digit: 1 2 3 4 5 6 7 8 9 10;
flag: 13;
plus: 11;
equals: 12;
digit0: 1;

Then, parse the string. If the string didn’t match the form “=digits+digits=” then I wanted nothing to happen. You can do this by recursing across the string, and if you find that it matches the pattern, insert a flag, and then when all the calls return, move the flag leftward.

parse {
    equals digit: (1, parseLeft), (0, afterParse);
}

parseLeft {
    digit digit: (1, parseLeft), (0, moveFlagAcrossDigit);
    digit plus digit: (2, parseRight), (0, moveFlagAcrossPlus);
}

parseRight {
    digit digit: (1, parseRight), (0, moveFlagAcrossDigit);
    digit equals: flag \0 \1;
}

moveFlagAcrossDigit {
    digit flag digit: \1 \0 \2;
}

moveFlagAcrossPlus {
    digit plus flag digit: \2 \0 \1 \3;
}

afterParse {
    equals flag: (0, removeFlag), (0, startDigitMove);
}

removeFlag {
    equals flag: \0;
}

The next step is to pair up the glyphs. For example, this would turn “1234+5678” into “15263748+”.

startDigitMove {
    equals digit: (1, digitMove), (1, startPhase2), (0, removeEquals);
}

removeEquals {
    equals digit: \1;
}

digitMove {
    digit digit: (1, digitMove), (1, digitMove2);
    digit plus: (1, digitMove2);
}

digitMove2 {
    digit digit: (1, digitMove2), (0, swapDigits);
    digit plus digit: (2, digitMove2), (0, digitMove3);
    digit plus equals: digit0 \0 \1 \2;
    plus digit: (1, digitMove2), (0, swapPlusDigit);
    plus equals: digit0 \0 \1;
    digit equals: \0 \1;
}

swapDigits {
    digit digit: \1 \0;
}

digitMove3 {
   digit plus digit: \2 \0 \1;
}

swapPlusDigit {
    plus digit: \1 \0;
}

The next step is to see if there were any glyphs left over on the right side that didn’t get moved. This happens if the right side is longer than the left side. For example, if the input string is “12+3456” we now would have “1526+34”. We want to turn this into “03041526”

startPhase2 {
    digit digit: (0, phase2), (0, beginPhase3);
}

phase2 {
    digit digit: (0, phase2Move), (0, checkPayload);
}

phase2Move {
    digit digit digit digit: (2, phase2Move), (0, movePayload);
    digit digit plus equals: \0 \1 \2 \3;
    digit digit plus digit: (3, payload), (0, flagPayload);
}

payload {
    digit digit: (1, payload), (0, swapDigits);
    digit equals: \0 \1;
}

flagPayload {
    digit digit plus digit: flag \3 \0 \1 \2;
}

movePayload {
    digit digit flag digit: \2 \3 \0 \1;
}

checkPayload {
    flag digit digit digit: (0, rearrangePayload), (0, phase2);
}

rearrangePayload {
    flag digit digit digit: digit0 \1 \2 \3;
}

The last step is to actually perform the addition. This works like a ripple carry adder. We want to take the glyphs two-at-a-time, and add them, and produce a carry. Then the next pair of glyphs will add, and include the carry. We start the process by introducing a carry = 0.

beginPhase3 {
    digit digit: (0, phase3), (0, removeZero);
}

phase3 {
    digit digit digit digit: (2, phase3), (0, addPair);
    digit digit plus equals: (0, insertCarry), (0, addPair);
}

insertCarry {
    digit digit plus equals: \0 \1 digit0;
}

removeZero {
    digit0 digit: (1, removeZero), (0, removeSingleZero);
}

removeSingleZero {
    digit0 digit: \1;
}

addPair {
    1 1 1: 1 1;
    1 1 2: 1 2;
    1 2 1: 1 2;
    1 2 2: 1 3;
    1 3 1: 1 3;
    1 3 2: 1 4;
    … more here
}

HarfBuzz

So I’m doing this whole thing using the HarfBuzz shaper, as described above. This is because it’s open source, so I can find where I’m hitting limits and increase the limits. It turned out that I not only had to increase the HB_MAX_NESTING_LEVEL to 4294967294, but I also was running into more limits. I ended up just taking all the limits in hb-buffer.hh, hb-machinery.hh, and hb-ot-layout-common.hh and increasing them by a factor of 10.

There’s one more piece that was necessary to get it to work. Inside apply_lookup() in hb-ot-layout-gsubgpos.hh, there’s a section if (end <= int (match_positions[idx])). It looks to me like this section is detecting if a recursive call caused the glyph sequence to get shorter than the size of the match. Inside this block, it says  /* There can't be any further changes. */ break; which seems to stop the recursion (which seems incorrect to me, but I’m not a HarfBuzz developer, so I could be wrong). In order to get this whole system to work, I had to comment out the “break” statement.

So that’s it! After doing that, the system works, and the font correctly adds numbers. The font has 75 shaping rules and is 32KB large.

The glyph paths (contours) were taken from from the Retroscape font.

Font file download

Wide color vs HDR

Over the past few years, there’s been something of a renaissance in display technology. It started with retina displays and now is extending to wide color and HDR. Wide color has been added to Apple’s devices, and HDR support has arrived in Windows. These are similar technologies, but they aren’t the same.

HDR allows you to display the same colors you could display with out, but at a higher luminosity (colloquially: brightness). This is sort of like the difference between one red lightbulb and two red lightbulbs. Looking at two red lightbulbs doesn’t change the color of the red, but instead it’s just brighter.

Wide color, on the other hand, lets you see colors that weren’t possible to see before. It is possible to display colors that are more saturated than otherwise could have been.

HDR monitors use the same color primaries as non-HDR monitors, but the luminosity of each of those primaries can grow beyond 1.0. On the other hand, wide color monitors use different, more saturated primaries.


Click and drag to rotate!
The colorful cube is sRGB, normalized to the luminosity of an iPad Pro screen. The white lines describe the gamut of an iPad Pro screen using the Display-P3 color space. The light blue describes the gamut of an ASUS ROG PG27UQ monitor, which is both HDR and wide color. The purple describes the gamut of a SurfaceBook laptop. The coordinate system is XYZ, but transformed such that sRGB is a unit cube.

In the above diagram, luminosity is roughly equivalent to distance in the +X+Y+Z direction. The chroma (hue and saturation) of a point is roughly the angle between two lines, one of which goes through the origin and the point, and the other goes through the origin and pure white. Therefore, wider colors are characterized by the three primary axes pointing in more opposite directions, whereas luminosity is roughly how far those lines extend.

You can see this above. The black and white points are shared between sRGB and Display P3, but the Display P3 monitor can show more points around the middle. So it isn’t more luminous, but it is wider. The ASUS monitor is both wide and HDR, so its axes open up widely, and also extend very far. A monitor that’s HDR but not wide would have the same primaries as sRGB, but would extend out far like the ASUS monitor.

Luminosity isn’t only tangentially related to color; in fact, each color has exactly one luminosity value. If you take a color and convert it to the XYZ color space, the Y component is luminosity. So, an HDR monitor can show colors with Y components significantly larger than non HDR monitors. A wide color monitor can’t, but it can show colors with X and Z values other than the values non-wide monitors can.

This is kind of interesting, because the sRGB spec says that its white point is defined to be 80 nits (which is the unit of luminosity). However, over the decades, monitors have gotten brighter, presumably because psychologically, consumers prefer to buy brighter displays than dimmer displays. Nowadays, most monitors are around 200-300 nits. Therefore, if you strictly adhere to the spec, an sRGB color value (r, g, b) should be some particular point in XYZ space, but in practice, because everyone bought brighter monitors, those same color values (r, g, b) are actually a point with a much greater Y value in XYZ. So different displays have different primaries, but they also have a different luminosity, which affects how far away from 0 the white point is in sRGB. You can see this in the above diagram - the SurfaceBook’s maximum white point is significantly smaller than the color cube, which is because the Surface Book reports a luminosity of only 270 nits. The diagram above is normalized to the luminosity of an iPad pro, which is measured by laptopmag.com to be 368 nits.

You can get all this information on Windows by using the IDXGIOutput6::GetDesc1() API call. This call gives you a lot of information, and it’s a little bit difficult to decipher. The redPrimary, greenPrimary, and bluePrimary give you the direction of each of the primaries in XYZ space. Each one is reported as an (x, y) tuple, which is the result of the calculation X/(X+Y+Z) and Y/(X+Y+Z), respectively[6]. Notice that you’re only given two pieces of information; that means that this isn’t a 3D point in XYZ space, but it’s rather a line. The line can be given in parametric form:

X(t) = x * t
Y(t) = y * t
Z(t) = (1-x-y) * t

As you can see, this passes through the origin and extends outward in some direction forever. Therefore, these xy values give you direction, but not magnitude.

To get magnitude, you need to consider the white point. The white point also has a direction, given in xy coordinates, which tells you which direction that farthest corner of the cube lies, but it doesn’t tell you how far along that line the corner is. To figure this out, you have to use the luminance figures reported by that API. Luminance is the Y channel of XYZ, so if you know the Y value and the direction of the line, you can solve for X and Z. Then, once you know that point, you can solve the maximum extents of the primaries by using the formula of redPrimary + greenPrimary + bluePrimary = whitePoint. That gives you the entire cube.

Calculating the cube for iOS is less detailed. The Display P3 color space is supposed to match the colors representable on the monitor, so we can interrogate the color space instead of the monitor’s reported info. You can construct a CGColor using the CGColorSpace.displayP3 and then use CGColor’s conversion function to turn it into an XYZ color. You can then scale the result by the luminosity of the display (which I looked up from laptopmag.com).

Here's the full text of the Swift Playground I used to calculate the Windows information:
import Foundation
import CoreGraphics
import GLKit

func calculateWhitePoint() -> (CGFloat, CGFloat, CGFloat) {
    let xWhite = CGFloat(0.3125)
    let yWhite = CGFloat(0.329101563)
    let zWhite = 1 - xWhite - yWhite
    let luminance = CGFloat(658.345215)
    let normalizedLuminance = luminance / 374

    let t = normalizedLuminance / yWhite
    let XWhite = xWhite * t
    let YWhite = yWhite * t
    let ZWhite = (1 - xWhite - yWhite) * t

    return (XWhite, YWhite, ZWhite)
}

func convertXYZToRGB(X: CGFloat, Y: CGFloat, Z: CGFloat) -> (CGFloat, CGFloat, CGFloat) {
    let r = 3.2406 * X - 1.5372 * Y - 0.4986 * Z
    let g = -0.9689 * X + 1.8758 * Y + 0.0415 * Z
    let b = 0.0557 * X - 0.2040 * Y + 1.0570 * Z
    return (r, g, b)
}

let (XWhite, YWhite, ZWhite) = calculateWhitePoint()

// X(t) = x * t
// Y(t) = y * t
// Z(t) = (1 - x - y) * t

let xRed = Float(0.674804688)
let yRed = Float(0.316406250)
let zRed = 1 - xRed - yRed
let xGreen = Float(0.1953125)
let yGreen = Float(0.708007813)
let zGreen = 1 - xGreen - yGreen
let xBlue = Float(0.151367188)
let yBlue = Float(0.046875)
let zBlue = 1 - xBlue - yBlue

// Red primary (XRed, YRed, ZRed): s * (xRed, yRed, zRed)
// Green primary (XGreen, YGreen, ZGreen): t * (xGreen, yGreen, zGreen)
// Blue primary (XBlue, YBlue, ZBlue): u * (xBlue, yBlue, zBlue)

// XWhite = XRed + XGreen + XBlue
// YWhite = YRed + YGreen + YBlue
// ZWhite = ZRed + ZGreen + ZBlue

// XWhite = s * xRed + t * xGreen + u * xBlue
// YWhite = s * yRed + t * yGreen + u * yBlue
// ZWhite = s * zRed + t * zGreen + u * zBlue

// [xRed, xGreen, xBlue]   [s]   [XWhite]
// [yRed, yGreen, yBlue] * [t] = [YWhite]
// [zRed, zGreen, zBlue]   [u]   [ZWhite]

let matrix = GLKMatrix3MakeAndTranspose(xRed, xGreen, xBlue, yRed, yGreen, yBlue, zRed, zGreen, zBlue)
let inverted = GLKMatrix3Invert(matrix, nil)
let solution = GLKMatrix3MultiplyVector3(inverted, GLKVector3Make(Float(XWhite), Float(YWhite), Float(ZWhite)))
let s = solution.x
let t = solution.y
let u = solution.z

let XRed = s * xRed
let YRed = s * yRed
let ZRed = s * zRed
let XGreen = t * xGreen
let YGreen = t * yGreen
let ZGreen = t * zGreen
let XBlue = u * xBlue
let YBlue = u * yBlue
let ZBlue = u * zBlue

// Let's check our work
XRed + XGreen + XBlue
XWhite
YRed + YGreen + YBlue
YWhite
ZRed + ZGreen + ZBlue
ZWhite
XRed / (XRed + YRed + ZRed)
xRed
YRed / (XRed + YRed + ZRed)
yRed
XGreen / (XGreen + YGreen + ZGreen)
xGreen
YGreen / (XGreen + YGreen + ZGreen)
yGreen
XBlue / (XBlue + YBlue + ZBlue)
xBlue
YBlue / (XBlue + YBlue + ZBlue)
yBlue

// 0 0 0 -> 0 0 0
// 1 0 0 -> XRed, YRed, ZRed
// 0 1 0 -> XGreen, YGreen, ZGreen
// 0 0 1 -> XBlue, YBlue, ZBlue
// 1 1 0 -> XRed + XGreen, YRed + YGreen, ZRed + ZGreen
// 0 1 1 -> XGreen + XBlue, YGreen + YBlue, ZGreen + ZBlue
// 1 0 1 -> XRed + XBlue, YRed + YBlue, ZRed + ZBlue
// 1 1 1 -> XRed + XGreen + XBlue, YRed + YGreen + YBlue, ZRed + ZGreen + ZBlue

let _000 = convertXYZToRGB(X: 0, Y: 0, Z: 0)
let _100 = convertXYZToRGB(X: CGFloat(XRed), Y: CGFloat(YRed), Z: CGFloat(ZRed))
let _010 = convertXYZToRGB(X: CGFloat(XGreen), Y: CGFloat(YGreen), Z: CGFloat(ZGreen))
let _001 = convertXYZToRGB(X: CGFloat(XBlue), Y: CGFloat(YBlue), Z: CGFloat(ZBlue))
let _110 = convertXYZToRGB(X: CGFloat(XRed + XGreen), Y: CGFloat(YRed + YGreen), Z: CGFloat(ZRed + ZGreen))
let _011 = convertXYZToRGB(X: CGFloat(XGreen + XBlue), Y: CGFloat(YGreen + YBlue), Z: CGFloat(ZGreen + ZBlue))
let _101 = convertXYZToRGB(X: CGFloat(XRed + XBlue), Y: CGFloat(YRed + YBlue), Z: CGFloat(ZRed + ZBlue))
let _111 = convertXYZToRGB(X: CGFloat(XRed + XGreen + XBlue), Y: CGFloat(YRed + YGreen + YBlue), Z: CGFloat(ZRed + ZGreen + ZBlue))

/*
0, 0, 0, 0, 1, 0, // left front
0, 0, 0, 1, 0, 0, // bottom front
1, 0, 0, 1, 1, 0, // right front
0, 1, 0, 1, 1, 0, // top front
*/
print("\(_000.0), \(_000.1), \(_000.2), \(_010.0), \(_010.1), \(_010.2), // left front")
print("\(_000.0), \(_000.1), \(_000.2), \(_100.0), \(_100.1), \(_100.2), // bottom front")
print("\(_100.0), \(_100.1), \(_100.2), \(_110.0), \(_110.1), \(_110.2), // right front")
print("\(_010.0), \(_010.1), \(_010.2), \(_110.0), \(_110.1), \(_110.2), // top front")

/*
0, 0, 1, 0, 1, 1, // left back
0, 0, 1, 1, 0, 1, // bottom back
1, 0, 1, 1, 1, 1, // right back
0, 1, 1, 1, 1, 1, // top back
*/
print("\(_001.0), \(_001.1), \(_001.2), \(_011.0), \(_011.1), \(_011.2), // left back")
print("\(_001.0), \(_001.1), \(_001.2), \(_101.0), \(_101.1), \(_101.2), // bottom back")
print("\(_101.0), \(_101.1), \(_101.2), \(_111.0), \(_111.1), \(_111.2), // right back")
print("\(_011.0), \(_011.1), \(_011.2), \(_111.0), \(_111.1), \(_111.2), // top back")

/*
0, 1, 0, 0, 1, 1, // top left
0, 0, 0, 0, 0, 1, // bottom left
1, 1, 0, 1, 1, 1, // top right
1, 0, 0, 1, 0, 1  // bottom right
*/
print("\(_010.0), \(_010.1), \(_010.2), \(_011.0), \(_011.1), \(_011.2), // top left")
print("\(_000.0), \(_000.1), \(_000.2), \(_001.0), \(_001.1), \(_001.2), // bottom left")
print("\(_110.0), \(_110.1), \(_110.2), \(_111.0), \(_111.1), \(_111.2), // top right")
print("\(_100.0), \(_100.1), \(_100.2), \(_101.0), \(_101.1), \(_101.2), // bottom right")

Texture Sampling

Textures are one of the fundamental data types in 3D graphics. Any time you want to show an image on a 3D surface, you use a texture.

Texture Types

First of all, there are many kinds of textures. The simplest kind of texture to understand is a 2D texture, whose purpose is to act like a rectangular image. Each element in the image is configurable; you can specify that it’s a float, or an int, or 4 floats (for each channel of RGBA), etc. These “elements” are usually called “texels.” Similarly, there are 1D textures and 3D textures, which act similarly.

Then, you’ve got 1D texture arrays, and 2D texture arrays, which are not simply arrays-of-textures. Instead, they are distinct types, where each element in the array is the relevant texture type. They are their own distinct resource types because GPUs can operate on them in hardware, so the array doesn’t have to be implemented in software. As such, the hardware restricts each element in the array to have the same dimensions. If you don’t like this requirement, you can create a software array of textures, and it will go slower but the requirement won’t apply. (Or you could even have an array of texture arrays!)

Mipmaps

There’s one other important piece to textures: mipmaps. Generally, textures are mapped onto arbitrary 3d geometry, which means that the number of pixels on-screen the texture is stretched over is totally arbitrary. Using regular projection matrices, the farther the geometry is from the viewer, the fewer pixels the texture is mapped onto.

Consider drawing a single pixel of geometry that is far away from the camera. Here, the entire texture will be squished to fit into a small number of pixels, so that single pixel will be covered by many texels. So, if the renderer wanted to compute an accurate color for that pixel, it would have to average all the covered pixels together. However, what if that geometry moves closer to the camera, such that each pixel contains only ~1 texel? In this situation, no averaging is necessary; you can just do a read in the texture data.

So, if the texture is big relative to the size on-screen it’s drawn, that’s a problem, but if it’s small, that’s no problem. Think about that for a second - big data sizes are a problem, but small data sizes okay. So what if the system could just reduce the big texture to a small texture as a preprocess? In fact, if there was a collection of reductions of various sizes, there would always be a size that is appropriate for the number of pixels being drawn.

That’s exactly what a mipmap is. If a 2D texture has dimensions m * n, the object also has storage for an additional level of m/2 * n/2, and an additional level of m/4 * n/4, etc, down to a single texel. This doesn’t even waste that much memory, because it’s provable that x + x/2 + x/4 + x/8 … = 2*x, so the memory overhead is as much as an additional texture. This storage requirement also assumes that texture sizes are always powers-of-two, which is generally required, though nowadays many implementations have extensions that relax this requirement.

So, naïvely, addressing a 2D texture requires 3 components: x, y, and which mipmap level. 3D textures require 4 components, and 1D textures require 2 components. 2D texture arrays require 4 components (there’s an extra one for the layer in the array) and 1D texture arrays require 3 components. With these components, the system only has to do a single read at runtime - no looping over texels required.

Automatic Miplevel Selection

The shader API, however, can calculate the mipmap level for you, so you don’t have to do that yourself in the shader (though you can if you want to). The key here is to figure out how many texels per pixel the texture is getting squished down to. If the answer is 2, you should use the second mipmap level. If the answer is 4, you should use the third mipmap level (since each level is half as large as the previous).

So how does the system know how many texels cover your pixel? Well, if you think about it, this is the screen-space derivative of the sampling coordinate in the base level. Stated differently, it’s the rate of change of the texture coordinate (in texels) across the screen. So, how do you calculate this?

If the code you’re writing is differentiable, you could just calculate it yourself in closed-form, and just use that. However, the system can approximate it automatically, using the fact that the GPU scheduler can schedule fragment shader threads however it likes. If the scheduler chooses to dispatch fragment shader threads in 2x2 blocks, then each thread in the block can share data among each other. Then, approximating this derivative is easy, it’s simply change-in-y / change-in-x = the difference of adjacent sampling coordinates divided by the difference of adjacent screen-space coordinates. Because we are sampling adjacent pixels, the difference of adjacent screen-space coordinates is just 1, so this derivative is calculated by just subtracting the sampling position of adjacent pixels. The pixels in the 2x2 block can share the result. (Of course this sharing only works if every fragment shader in the 2x2 block is at the same point in the shader so they can cooperate together.)

So, the system does this subtraction of adjacent sampling coordinates to estimate the derivative, and takes the log base 2 of the derivative to select which miplevel to use. The result of this may not be exactly integral, so the sampler describes whether or not to just clamp to the nearest integer miplevel or to read both straddling miplevels and use a weighted average. You can also short-circuit this computation by explicitly specifying derivatives to use (which means the derivatives won’t be automatically calculated, but everything else will work the same way) or by just specifying which miplevel to use directly.

Dimension Reduction

But I’ve breezed over one of the details here - 2D textures have 2-dimensional texel coordinates, and screens also have 2-dimensional coordinates. How do we reduce these to a single miplevel? The Vulkan spec doesn’t actually describe exactly how to reduce the 2-dimensional texel coordinates into a single scalar, but it does say in section 15.6.7:

ρ_x and ρ_y may be approximated with functions f_x and f_y, subject to the following constraints:
f_x is continuous and monotonically increasing in each of m_ux, m_vx, and m_wx
f_y is continuous and monotonically increasing in each of m_uy, m_vy, and m_wy
max(|m_ux|, |m_vx|, |m_wx|) <= f_x <= sqrt(2) * (|m_ux| + |m_vx| + |m_wx|)
max(|m_uy|, |m_vy|, |m_wy|) <= f_y <= sqrt(2) * (|m_uy| + |m_vy| + |m_wy|)

So, you reduce the n-dimensional texture coordinate to a scalar by making up a formula that fits the above requirements. You apply the function twice - once for the horizontal screen derivative direction, and once for the vertical screen derivative direction.

So this tells you (roughly) how many texels fit in the pixel vertically, and how many texels fit in the pixel horizontally. But these values don’t have to be the same. Imagine looking out in first-person across a rendered floor. There are many texels squished vertically, but not that many horizontally.

This is called anisotropy. The amount of anisotropy is just the ratio of these two values. By default, texture sampling will just use the minimum of these two values when figuring out which miplevel to use. Remember - miplevels are zero-indexed, so the smaller the index, the more data is in that level, so the smaller miplevel means the highest level of detail. However, there some techniques in this area that involve doing extra work to improve the quality of the result.

Wrapping Things Up

At this point, the sampler provides shader authors some control over the miplevel selection. The sampler / optional arguments can include a “LOD Bias” which gets added to this value, so the author can get higher-or-lower detail as necessary. The sampler / optional arguments can also include a “LOD Clamp” which will be applied here, if, for example, not all the miplevels of the texture have their contents populated yet.

So, now that you have a miplevel, you can do the rest of the operation. If the sampler says the sampling coordinate is normalized, you denormalize it by multiplying by the dimensions of the miplevel, and modulus / mirror / whatever the sampler tells you to do. Then, depending on the sampler settings, you either round the denormalized coordinates to the nearest integer, or you read all the straddling texels and perform a weighted average. Then, if the sampler tells you to, you do it all again at the next miplevel, and perform yet another weighted average.

There’s one last tiny detail I’ve skipped over, and that is the fact that texel elements are considered to lie at the center of the texel. So, if you have a 1D texture with 2 texels, where one is black and one is white, 1/4 of the way through the texture will be full black, and 3/4 of the way through the texture will be full white, and 1/4 - 3/4 will be a gradient from black to white. But what is drawn from 0 - 1/4 and from 3/4 - 1? What about values less than 0 or greater than 1? The sampler allows for configuring this. The modulus / mirroring operation results in a value that is either on the interior of the texture, or 1 texel around the edge. These texels around the edge either get values from being repeated / mirrored / whatever, or they can just be set to a constant “border color.” This color is fed as input to the weighted average calculation, so everything just works correctly.

Comparison of Entity Framework to Core Data

Object Relational Mapping libraries connect in-memory object graphs to relational databases. Object-oriented programming is built upon the idea that there is an in-memory object graph, where each object is an instance of a class. An ORM is the software that can save that object graph to a database, either on-disk or using a service across the network.

Entity Framework is Microsoft’s premier ORM library, and Core Data is Apple’s premier ORM library. Both have the same goals - to persist an object graph to a database - but they were developed by different companies for different languages. It stands to reason that they made some different design choices.

Which Entity Framework?

Microsoft is infamous for creating multiple ways to do the same thing, and ORM libraries are no different. There are two versions of Entity Framework: Entity Framework 6, and Entity Framework Core. The documentation says that Entity Framework Core is the new hotness. Also, Entity Framework Core is open source.

So let’s start using Entity Framework Core, right? Well, not so fast. It turns out that you have to pick a runtime that Entity Framework Core will run on top of.

Which Runtime?

Entity Framework was originally developed for .NET. So that’s fine, but it turns out there are multiple versions of .NET.

• .NET Framework only runs on Windows
• .NET Core is written by Microsoft, and runs on Windows, Linux, and macOS. The documentation says that .NET Core is better than .NET Framework. Also, .NET Core is open source.
• .NET Standard is just a standard. It isn’t a piece of software - it’s a specification that describes a level of support that a runtime needs to have in order to be compliant. Xamarin is another .NET runtime that supports the .NET Standard (and it runs on iOS / Android). Targeting this runtime means your app will work in every .NET implementation, but it won’t have access to some of the libraries only present in .NET Core.
• The Universal Windows Platform is a runtime compliant with the .NET Standard. The Entity Framework documentation says that UWP is now supported. One interesting note: as part of the compilation process, the platform-independent .NET bytecode is run through the .NET Native toolchain, which produces a platform-dependent binary. They say this is to improve performance. (So I guess this means that the Universal Windows Platform isn’t really universal?) This compilation is somewhat lossy because reflection doesn’t fully work in native apps, and it sounds like Entity Framework had some bugs here that they had to fix.

There’s an example in the Entity Framework Core documentation about how to use it with the Universal Windows Platform, and UWP is the new hotness, so I’ll use that. If you dig into the example, you’ll find that the Entity Framework tools don’t work with UWP projects, so they had to make a dummy .NET Core project with nothing inside it, just to run the tools. How unfortunate.

Getting Entity Framework

Entity Framework is not built in to the system. Instead, you’ll have to get it from Visual Studio’s blessed package manager, named NuGet. When you install packages with NuGet, they’re not installed across the whole system; instead, they’re installed only for a single project. NuGet is built in to Visual Studio - simply go to Project -> Manage NuGet Packages to search/install packages.

Entity Framework is designed to be pluggable to different kinds of databases, and each database has its own package inside NuGet. The example uses a SQLite database, so it uses the Microsoft.EntityFrameworkCore.Sqlite package. There is also another package, Microsoft.EntityFrameworkCore.Tools, which includes command-line tools to generate migration code / apply migrations, so that one is included too.

How to get Core Data

It’s already part of the platform, and there’s only one version. Just use it.

High Level

Both libraries have a concept of a “context” which is the thing that holds the link to all the objects in the object graph. For Entity Framework, this is the Microsoft.EntityFrameworkCore.DbContext, and for Core Data, this is the NSManagedObjectContext. When you create an object, you register it with the context, and when you delete an object, you notify the context that it has been deleted. After you’ve done all your modifications, you tell the context to “save,” which stores all the changes in the database.

Entity Framework:
var blog = new Blog { url = url };
db.Blogs.Add(blog);
db.SaveChanges();

Core Data:
let blog = Blog(context: context, url: url)
try context.save()

Read/Modify/Write operations are also quite similar:

Entity Framework:
var blog = db.Blogs.First();
blog.Url = url;
db.SaveChanges();

Core Data:
let fetchRequest = Blog.fetchRequest() as NSFetchRequest
fetchRequest.fetchLimit = 1
let blog = try context.fetch(fetchRequest)[0]
blog.url = url
try context.save()

Context

In Core Data, the NSManagedObjectContext is just a class. When modifications are made to the object graph, the NSManagedObjectContext makes a strong reference to the object (because Swift is reference-counted, the distinction between strong and weak references are important). When it gets saved, the NSManagedObjectContext knows what to save.

However, in Entity Framework, the DbContext is magical. The application needs to subclass DbContext, and the subclass needs to have DbSet properties. These DbSets refer to the various tables in the database. When the DbContext’s constructor is run, it uses reflection to inspect itself, find all the DbSet properties, and inspect the generic type argument to determine the data model. It builds up a Microsoft.EntityFrameworkCore.ModelBuilder, and lets you make any last-minute changes you want inside DbContext.OnModelCreating().

Objects

In Core Data, each object in the object graph is represented by NSManagedObject. This object acts like a dictionary; you can “set properties” by using the Key-Value Coding functions value(forKey:) and setValue(_, forKey:). You can get better type-safety if you subclass NSManagedObject for each of your entities, and add typed properties. However, if you do this, you have to make sure that getting/setting these properties calls the Key-Value Coding methods on the inner NSManagedObject. Swift has a helpful keyword, @NSManaged, which does this for you. Even further, Xcode will even generate the subclass for you at compilation time, with the appropriately typed @NSManaged properties, if you select the appropriate value for “Codegen” in the right sidebar, with the entity selected. (Or you can use the managedObjectClassName string property on NSEntityDescription when building the NSManagedObjectModel, and Core Data will construct this class at runtime using the Objective-C runtime).

NSManagedObjects know which context they belong to, and their context requires you to pass in the context. This is presumably so when values get modified, the NSManagedObject can notify the NSManagedObjectContext.

In Entity Framework, each object in the object graph is just a regular object. No subclassing required, and no manifest or custom model creation code either. The DbContext learns about the object’s shape from reflection. This means that the ChangeTracker in the DbContext doesn’t automatically know about changes; instead, it has to DetectChanges() which iterates through the known objects. This is done automatically when it’s required.

Connection Between Classes and Data

In Core Data, when the system wants to populate a property of an object, it can do it dynamically, because the getter of the property will be filtered through value(forKey:). This way, the setter doesn’t have to know what the name of the field is at compilation time, which is required when the data model is created at runtime.

However, in Entity Framework, objects are just regular classes. This is a problem, though; how can Entity Framework set the correct property on the class when the name of the property is only known at runtime (because the model can be modified at runtime)? Well, it turns out it uses Linq to build a program at runtime that can set properties that are only known at runtime. This is extremely powerful; it looks like you can use Linq to write almost anything that you could write in C#.

Data Model

In Entity Framework, the DbContext constructor uses reflection to discover the object graph. You get a chance to modify the model at runtime in DbContext.OnModelCreating(), which is called inside the DbContext’s constructor. However, adding an entity to the model requires a class to match that entity. However, for properties, you can have a property that is present in the model but isn’t present in the class. This is valuable for things like automatically saved date fields.

In Core Data, there is a separate data file that describes the model declaratively (with the file extension .xcdatamodeld). You can edit these with a GUI inside Xcode. This file corresponds to a NSManagedObjectModel, which you can build at runtime instead, if you want. Then, when you bring up the Core Data stack, you can specify this model.

Fetch Queries

In EntityFramework, the DbSet implements the IQueryable interface. This is an interface that represents a Query node inside the Linq framework. Functions like .where() and .OrderBy() operate on these nodes and return other nodes, letting you chain up these operators. These operators aren’t actually applied at the time you call the function; instead they are a sort of retained-mode program. Whenever you want to actually pull data out of the query at the end, the runtime will look at the chain of operators and figure out how best to apply it (usually by creating SQL that matches the operation). However, some of the operations need to be applied by the client; this transparently works, but it obviously isn’t great for performance.

Core Data uses the same sort of thing, encapsulated by NSPredicate and NSExpression. NSExpression is the same kind of node inside a retained-mode program. These are quite powerful; you can even call arbitrary selectors on arbitrary objects. The big difference between this and Linq is that, in true Objective-C style, NSExpression isn’t typed, but Linq is typed.

Parallelism

Both Entity Framework and Core Data’s contexts are single-threaded, which means the managed objects all have to live on the same thread as their context. However, fetches and stores involve round trips to databases, which can be quite slow and would block the main thread. Entity Framework gets around this by providing Async versions of the fetching / saving functions. In this model, the objects live on the main thread, but the UI can still be redraw during the slow database operations.

Core Data has two approaches to this. One way is to host the entire Core Data object graph in another thread. You get this if the NSManagedObjectContext is initialized with the concurrencyType argument set to .privateQueueConcurrencyType. If you do this, the NSManagedObjectContext will create its own private queue, and operations on the NSManagedObjectContext are only valid from that queue. You run code on that queue by using NSManagedObjectContext’s perform(_:) function. Inside the callback, you can execute your fetch requests, build up some data, and post a message back to the main queue with your data (but not with NSManagedObjects!).

Alternatively, you can use the main queue, and use NSAsynchronousFetchRequest to create objects asynchronously. As far as I can tell, there is no equivalent call for NSManagedObjectContext.save(), and from my sampling, it appears that NSManagedObjectContext.save() is synchronous (though perhaps it doesn't have to be?)

Entity Framework:
var blog = await db.Blogs.FirstAsync();
blog.Url = url;
await db.SaveChangesAsync();

Core Data:
let fetchRequest = Blog.fetchRequest() as NSFetchRequest
fetchRequest.fetchLimit = 1
let asynchronousFetch = NSAsynchronousFetchRequest(fetchRequest: fetchRequest) { (result) in
    let blog = result.finalResult![0]
    blog.url = url
    do {
        try context.save()
    } catch {
        …
    }
}
try context.execute(asynchronousFetch)

Edit: The Core Data Best Practices video from 2012 describes how you can achieve asynchronous saves by using a parent/child NSManagedObjectContext pair. You set the child to live on one thread and the parent to live on the other thread, and when you tell the child to save, it will just push its changes to the other context on the other thread. Then you can asynchronously tell the other thread to save by using perform(_:).

Migrations

In Entity Framework, a migration is modeled as a chunk of code. However, this code is written by one of the tools inside Microsoft.EntityFrameworkCore.Tools. The command line tool saves a snapshot of whatever the current database schema is, and can create a new schema by using the same mechanism that DbContext uses when it creates a schema at runtime. Then, after you’ve created a migration, you can apply it, which involves running the code on your local development machine to upgrade the database to the new version. These tools even have documentation. You have a chance to fine-tune the migration by editing the source code the tool created, because creating the migration code and applying it to the database are two distinct steps. Because the migration is generated code, you can run it in your app instead of on your local development machine.

But wait, not so fast! The command-line tools use reflection on your source code to generate a model? Yep. That means the command-line tools build your source code. Then they look in your source code for the new model. If the command-line tools are supposed to perform the migration, then it’s supposed to connect to the database, too. But wait, how does it connect to the database? Well, your source code connects to the database … and the command-line tools will just run that code. The documentation describes what functions / classes it will look for in your code and run on your local machine.

Core Data handles migrations totally differently. Some simple migrations can happen automatically, right when you open the database (and you can check whether your change is “simple” by using a class function on NSMappingModel.) But, more complicated migrations are described declaratively in a .xcmappingmodel file, which Xcode lets you edit with a GUI. The expressions are described by strings, which (presumably) are the same strings that NSExpression accepts. This file corresponds to a NSMappingModel, which you can construct at runtime instead of loading from a bundle. Then, when you want to run the migration, you can use NSMigrationManager and pass in the NSMappingModel you want it to use. (One gotcha: to create a .xcmappingmodel in Xcode, it has to be between two different versions of the same model. You can create a new version of a model by selecting Editor -> Add Model Version.)

Configuring the Database

The constructor to Microsoft.EntityFrameworkCore.DbContext requires a Microsoft.EntityFrameworkCore.DbContextOptions, which is built by a Microsoft.EntityFrameworkCore.DbContextOptionsBuilder. C# has this nifty feature where you can declare a free function, but give the first argument the “this” keyword, and that free function will appear as if it was inside the class definition. So, the individual database package adds a function to the DbContextOptionsBuilder. (I haven’t investigated what the package does inside this function.) Then, the client code calls optionsBuilder.UseSqlite(connectionString), for example. You can use Microsoft.Data.Sqlite.SqliteConnectionStringBuilder() to build the connection string. You do this inside the DbContext.OnConfiguring() function so the command-line tools know how to configure the database.

Core Data works differently. Each persistent store is described via a NSPersistentStoreDescription, which includes a string “type” property. This “type” refers to the registeredStoreTypes registry inside NSPersistentStoreCoordinator, which can be extended with additional subclasses of NSPersistentStore. There are also 4 built-in strings for well-known database types.