Saturday, December 19, 2015
Sunday, December 13, 2015
Methods of writing Windows apps
Win32
In the beginning, there was just Win32. This is a C-based API which has been around since Windows 95. In this API, UI widgets (such as buttons) were known as “Windows” (represented in code as HWND) and windows could have windows inside of them. There was no concept of automatic layout; instead, each window had to be explicitly placed and sized by the programmer.
When you have a window, you can create a “device context” which is associated with that window. This device context is what we now would call a 2D drawing context, and it has API functions which let you draw lines and circles and text and that kind of stuff. All these drawing operations were performed on the CPU by a library named “GDI.”
Interactivity was fairly primitive. Applications would create their own runloop. Each turn of the runloop calls GetMessage(), which corresponds with an event that occurred. However, because some messages need to be handled by the system, the runloop just turns around and delivers the event back to the system. Before doing this, you register a callback function which the system will invoke when it wants to. This is where you are told things like “you should paint your contents now” or “the user pressed a key on the keyboard.” Because each message has an enum type, this callback function will switch over the type, and react to all the messages it understands.
This API is 20 years old, and should not be used for new projects. However, it is still supported today on current Windows operating systems.
Microsoft Foundation Classes (MFC) was the next suggested method of writing Windows apps. This is a C++ wrapper around the Win32 API; it was a new way of doing what people were already doing. Similar to Win32, it shouldn't be used anymore.
.NET
.NET represents a new approach to Windows desktop software development. There is a new language, a new object model, a new ABI, garbage collection, etc. There are two ways that .NET applications could be used to make graphical applications: WinForms and WPF. WinForms simply internally uses the Win32 API, and therefore isn’t very interesting.
WPF, however, represents a clean break from Win32 GUI programming. This API doesn’t use GDI for drawing, doesn’t use HWNDs, and doesn't require manual layout. Instead, development starts with a declarative language called XAML. This is an XML-based language where regions of the screen are represented as elements in XAML. Each element has an associated .NET class (in the System.Windows namespace) which allows you to do everything in code that the XAML file does. These elements aren’t HWNDs; instead, they are their own unrelated type.
Because HWNDs aren’t involved, drawing isn’t done with GDI. Instead, it is done entire on top of Direct3D, which means that the drawing routines are hardware accelerated. It also means that WPF controls look different from their GDI counterparts; a WPF app is recognizable.
WinRT
WinRT is the suggested method of creating a GUI application. WinRT’s GUI model is set up similarly to WPF, except that it has an entirely new set of elements (which reside in the Windows.UI namespace). It still employs XAML for representing elements in a declarative form.
For drawing a specific control, WinRT uses Direct2D, a hardware-accelerated drawing library. This library is conceptually on top of Direct3D, but it is also available for arbitrary developer use.
Once an individual element is drawn, multiple elements are composited together using Windows Composition. This library allows for creating a retained-mode hardware-accelerated tree of visual objects. This API is internally used to composite all the controls in the window. It even has a public API so you can interact with the composition tree directly.
As opposed to Win32, WinRT has an application model. You don’t have to write your own event loop with WinRT. Applications are implemented as a subclass of Windows::ApplicationModel::Core::IFrameworkView. This class has 5 functions which the application overrides in order to react to lifecycle events. The event loop is implemented in CoreApplication::Run, which takes an IFrameworkViewSource, which is a factory for IFrameworkViews.
Event handling is performed explicitly. Class definitions in C++/CX have properties, methods, and events. If you want to react to an event, you simply construct an Windows::Foundation::EventHandler object, and use the += operator to attach it to the object’s event field. The EventHandler object is a wrapper around a function pointer or a lambda. As an example, UIElement has a “PointerMoved” event.
Layout is achieved by encapsulating different layout algorithms inside different controls. For example, there is a Windows::UI::XAML::Controls::Grid control, which arranges its contents in a grid. Different controls arrange their contents according to their own internal algorithms. The most basic example is the Canvas class, which allows the programmer to explicitly lay out its child controls (so you’re not limited by the classes that come with the library).
Inside these callbacks, you can modify any part of the XAML tree you want in order to change the rendering of your app. From code, the way you identify elements in the XAML tree is pretty interesting. Each XAML file is represented in native code by a class which extends Windows::UI::Xaml::Controls::Page. When you build your project, the XAML file is used to create an auto generated header. Nodes in the XAML file can have a “name” attribute, which represents the name that native code would refer to the node as. The auto generated header contains each of these variables of the right type and name. Then, the auto generated header’s content is mixed into your Page subclass by using the support for “partial” classes. This allows the class declaration to be defined in two files; the conceptual class is the union of the two classes. Therefore, these auto generated variables automatically become class members, and are therefore in scope for all the methods of the class. In the end, this means that you don’t have to do any typing; you just immediately have access to your nodes by name.
Once you have access to the elements, you can change any of their properties, run any of their methods, and listen for any of their events.
Saturday, December 12, 2015
Binary Compatibility of Windows Programs
COM
Around 1993, there was an issue around binary compatibility of object-oriented programs. The problem is that callers and callees must agree on the internal layout of structs in memory. This means, however, that if a callee is updated (as libraries often are) and changes this memory layout, the program will not behave as expected.
Microsoft came up with a solution to this problem by creating an “object model” (named “COM”) which objects that traverse library boundaries should adhere to. The object model has a few rules:
- Objects must not have any data that is exposed. Therefore, the only thing publicly available from an object is functions to call on the object.
- The object’s functions are represented in memory as an array of pointers to functions. The order of this array matches the order that the functions are declared in source code.
You may recognize this design as an “interface.” The function array is a vtable. Therefore, mapping this idea to C and C++ is very natural. Because the only things that exist in the objects is a vtable, there are no problems with padding or alignment of data members or anything like that. Inheritance is implemented by simply adding more function pointers on to the end of the array.
This memory layout also means that many languages can interact with these COM objects.
There are two more interesting pieces to this object model: there are 3 functions that every object must implement. This can be thought of as the root of the inheritance hierarchy. In C++, this base class is known as IUnknown. The three functions are:
- AddRef()
- QueryInterface()
- Release()
QueryInterface() is pretty interesting. It is a way of converting one object into another type. The idea is that all COM types have an associated ID number. When you call QueryInterface(), you pass in an identifier of a type that you want. If the object knows how to represent itself as that type, it returns an interface of the correct type. Therefore, it’s sort of like a dynamic_cast, except that the source and destination types don’t have to be related at all. This is actually a really powerful concept, because it provides a mechanism for interoperability between APIs. A new library can be released, and its objects might want to support being used as the objects in another library; this can naturally be achieved by supporting QueryInterface().
In every COM library I’ve used, functions use out params instead of return values. Instead, they return an HRESULT error code. Therefore, it’s common to see every call to a COM object wrapped in a block which checks the return code.
.NET
Around 10 years later, Java was becoming popular. One of Java’s goals was to allow programs to run on any machine without requiring recompilation. It achieved this goal by compiling to a “virtual machine” bytecode. Then, at runtime, an interpreter would run the bytecode.
This approach means that all memory accesses and function calls operate through an interpreter, so the interpreter can make sure that nothing bad happens (for example: a program can never segfault). It also means that the virtual machine is free to implement any object model it wants; all object accesses pass through it, so it is free to, for example, move objects around in memory whenever it wants. This naturally leads to a garbage-collected language, where the garbage collector is implemented in the virtual machine.
(Now, I’d like to make an aside about this “managed code” business. It isn’t really true that all Java programs are interpreted; the virtual machine will JIT the program and point the program counter into the JITted code. Whenever the interpreter needs to do some work, it just makes the generated bytecode call back into its own code. Therefore, nothing is being done here that couldn’t be done with a simple software library. Indeed; this managed “runtime” is the same fundamental idea as the raw C “runtime”; it’s just that many operations which would be raw instructions in C are instead implemented as function calls into the runtime. If you are diligent about all your object accesses, you can make your C++ program garbage collected. “Managed code” doesn’t really mean anything mechanical; instead, it is a way of thinking about the runtime model of your program.)
Microsoft wanted to be able to use this model of “managed code” in their own apps, so they invented a system quite similar to Java’s. You would compile your apps to a “CLI” form, which is a platform-agnostic spec describing a virtual machine. Then, the Microsoft CLR interprets and runs your program. A new language (C#) was invented which nicely maps all its concepts to CLI concepts.
There are a couple extra benefits of having a well-specified intermediary form. One is that there can be multiple languages which compile to your CLI. Indeed, Microsoft has many languages which can be compiled to the CLI, such as F# and VB.NET. Another benefit is that the standard library can exist in the runtime, which means that all of those languages can call into the standard library for free. Each language doesn’t need its own standard library.
A pretty interesting benefit of this virtual machine is that it solves the binary compatibility problem. The fundamental problem with binary compatibility is that one library might reach inside an object vended by another library; with a virtual machine, that “reaching” must go through the runtime. The runtime can then make sure that everything will work correctly. So, we now have another solution for the binary compatibility problem.
C++/CLI
Remember how I mentioned earlier how that this concept of “runtime” is really just a library of functions that you should call when you want to do things (like call a function or access a property of an object)? Well, C++ supports linking with libraries… there is no reason why one shouldn’t be able to call into these runtime libraries from a C++ program.
The difficulty, however, is being diligent with your accesses. Every time you do anything with one of these “managed” objects, you must call through the runtime. This is a classic case of where the language can help you; you could imagine augmenting C++ to be able to naturally represent the concept of a managed object, and enforcing all interactions with such objects to be done through the runtime.
This is exactly what C++/CLI is. It is a superset of the C++ language, and it understands what managed objects are. These managed objects are fundamentally different from C++ objects; they are represented using different syntax. For example, when you create a managed object, you use the keyword “gcnew” instead of “new”, in order to remind you that these objects are garbage collected. A reference to a managed object uses the ^ character instead of the * character. Creating a reference to a managed object is done with the % character instead of the & character. These new types are a supplement to the language; all the regular C++ stuff still exists. This way, the compiler forces you to interact with the CLI runtime in the correct way.
Windows Runtime
The currently accepted way to write Windows programs is using the Windows Runtime (WinRT). You may think that WinRT is a runtime just like the .NET runtime discussed above; however, this isn’t quite right. WinRT objects are integrated with the .NET runtime, and are considered “managed” in the same way that .NET objects are considered “managed.” However, they aren’t binary compatible with .NET objects; you can’t interact with WinRT objects using the same functions you use to interact with .NET objects.
Therefore, C++/CLI doesn’t work for WinRT objects. Instead, a similarly-looking language, C++/CX, was invented to interact with these WinRT objects. It keeps some of the syntax from C++/CLI (such as ^ and %) but replaces others (such as “ref new” instead of “gcnew”).
Tuesday, October 20, 2015
Vertical Text
To start off, latin scripts are generally not written vertically. For example, let’s say you’re writing on the spine of a book. Usually, you wouldn’t stack the letters on top of each other; instead you would lay the book down horizontally and then write on the spine. In this situation, you’re simply writing horizontally on a canvas which has been rotated.
However, many East Asian scripts are written vertically. In this case, the characters are stacked on top of each other. Laying out text like this is a little different than laying it out horizontally.
You’re probably familiar with the concept of each character having an advance, which represents the displacement from one character to the next. Well, this displacement vector is different if you’re stacking letters on top of each other. In particular, there are two different kinds of advances: horizontal advances and vertical advances. With CoreText, CTFontGetAdvancesForGlyphs() takes a CTFontOrientation parameter, where you can specify if you want horizontal advances or vertical advances.
In general, the pen starts out horizontally centered above the letter, and the vertical advance takes you to a place that is horizontally centered below the letter.
This is actually the same concept as a “baseline”, where pen keeps returning to the same line after each character. The difference is that this baseline is in the middle of the letters, rather than underneath (some of) them. This is known as an “ideographic baseline,” which is distinct from the “alphabetic baseline” we are used to. A font file can define where these (and more) baselines should occur in the ‘bsln’ or ‘BASE’ table.
However, when you tell a glyph to draw at a particular point, that local origin isn’t at these pen locations.
Therefore, if you are going to draw a glyph, you need some way of going from this pen location to the glyph’s local origin. With CoreText, you can do this with the API function CTFontGetVerticalTranslationsForGlyphs().
So that should be enough to lay out a line of pure text, but in Web content, you may have stacked letters in the same line as non stacked letters (for example: an English word in a Chinese sentence). Laying out these two situations correctly is possible because of the relationship between the alphabetic baseline and the ideographic baseline.
Keep in mind baselines progress in the direction of the line, not the characters. The ideographic baseline and the alphabetic baseline are parallel to each other. The font's ascent and descent tell you how much space the letters take up orthogonally to the baseline. Therefore, in vertical text, the ascent measures to the right of the baseline and the descent measures to the left of the baseline, even though the letters are stacked.
However, many East Asian scripts are written vertically. In this case, the characters are stacked on top of each other. Laying out text like this is a little different than laying it out horizontally.
You’re probably familiar with the concept of each character having an advance, which represents the displacement from one character to the next. Well, this displacement vector is different if you’re stacking letters on top of each other. In particular, there are two different kinds of advances: horizontal advances and vertical advances. With CoreText, CTFontGetAdvancesForGlyphs() takes a CTFontOrientation parameter, where you can specify if you want horizontal advances or vertical advances.
In general, the pen starts out horizontally centered above the letter, and the vertical advance takes you to a place that is horizontally centered below the letter.
This is actually the same concept as a “baseline”, where pen keeps returning to the same line after each character. The difference is that this baseline is in the middle of the letters, rather than underneath (some of) them. This is known as an “ideographic baseline,” which is distinct from the “alphabetic baseline” we are used to. A font file can define where these (and more) baselines should occur in the ‘bsln’ or ‘BASE’ table.
However, when you tell a glyph to draw at a particular point, that local origin isn’t at these pen locations.
Therefore, if you are going to draw a glyph, you need some way of going from this pen location to the glyph’s local origin. With CoreText, you can do this with the API function CTFontGetVerticalTranslationsForGlyphs().
So that should be enough to lay out a line of pure text, but in Web content, you may have stacked letters in the same line as non stacked letters (for example: an English word in a Chinese sentence). Laying out these two situations correctly is possible because of the relationship between the alphabetic baseline and the ideographic baseline.
Keep in mind baselines progress in the direction of the line, not the characters. The ideographic baseline and the alphabetic baseline are parallel to each other. The font's ascent and descent tell you how much space the letters take up orthogonally to the baseline. Therefore, in vertical text, the ascent measures to the right of the baseline and the descent measures to the left of the baseline, even though the letters are stacked.
Monday, October 19, 2015
A Deeper Look at OpenType and TrueType Font Features
Font Features are a way to provide arbitrary changes to a sequence of glyphs. Text layout happens in a couple steps:
OpenType’s model is simpler, so let’s start there. OpenType encapsulates font features into two tables, GPOS and GSUB. GPOS is for glyph positioning, and GSUB is for glyph substitution. Both of these tables actually share the same overall structure. The shared structure is as follows:
Each of the typed tables has an associated “coverage” table. This simply holds a set of glyphs that the typed table acts upon. When the software is laying out some glyphs, if none of the glyphs appear in the coverage table, the software can safely ignore that typed table.
Everything else is shared between GPOS and GSUB, and is just an aggregation of the level below it. Each “feature” has a four-letter code associated with it, such as “liga” or “smcp.” These codes are reported in the program UI, and the user is allowed to switch on or off each of these codes independently. If the user switched off a particular code, the stuff inside that feature’s “lookup” tables is not performed. The lookup tables are performed one by one, in the order the file describes.
Scripts and language systems each have their own four-character tags associated with them. The reason for the distinction is that many different languages may share the same script. For example, both English and Spanish share the Latin script. Because the languages and scripts are expected to have very different glyph patterns, separating out the features into these buckets seems like a good idea. Also, there is a default script tag and a default language system. Microsoft keeps a registry of all of the scripts and language systems, as well as their associated 4-character tags.
TrueType font features are completely different. In particular, there are many tables, each with a specialized purpose. For example, instead of the general “GPOS” table, there is a much more specific “kern” (or “kerx”) table, which is only designed for kerning glyphs. Similarly, there is a separate, more-specific, “opbd” table for the optical bounds of the font. Many of the OpenType features have corresponding specific-purpose tables inside TrueType. These tables do not provide the same flexibility as the GPOS table.
However, unlike most of the TrueType tables, the “morx” table is quite general. Conceptually, it describes the same sort of things that the OpenType GSUB table describes. However, its model of font features is very different.
The “morx” table doesn’t mess around with any of that “script” and “language system” stuff. Instead, the table is represented by a collection of “chains.” Each chain is comprised of a collection of typed subtables. These typed subtables describe things like “Rearrange this sequence of glyphs according to these predefined rules” or “insert a specific glyph into the middle of this particular glyph sequence.”
The rest of the chain is devoted to describing which typed subtables should be performed.
Similar to before, each chain gets a coverage table. However, in addition, there is a pretty interesting mechanism to determine which features cause which typed subtable to be performed.
Inside the chain, a sequence of bitwise operations is described, which results in a particular bitfield. Each typed subtable in the chain also has an associated bitfield. If the bitwise and of those two values is nonzero, then the typed subtable is applied.
That sequence of bitwise operations is where individual features come into play. Instead of representing a particular feature as a four-character tag, like in OpenType, TrueType represents a feature as a tuple of (feature type, feature selector). The font describes a sequence of features and corresponding bit masks to be ANDed / ORed. When a feature is enabled in the application’s UI, its associated bitwise operations are performed. When the feature is disabled, its associated bitwise operations are not performed.
The software starts with a known bit pattern. It then runs through the sequence. For each item in the sequence, if its associated font feature is enabled, it performs the appropriate bitwise operations. When it’s done, the result is a particular bit pattern value.
Each of the typed subtables also has an associated pattern value. If the bitwise AND of the calculated bit pattern and a subtable’s bit pattern is nonzero, then the table is performed.
In OpenType, the font file has no way of expressing that certain features conflict or that certain features should be on by default. Each feature is simply represented by a four-character tag, and it is either enabled or disabled. The software may (or may not) decide to enable certain features by default based entirely on the semantics of the feature itself (not based on the font file). For example, the OpenType feature “rlig” is mean for “required ligatures” and is generally enabled by default.
The representation of a font feature in TrueType conveys more information than an OpenType font feature. In TrueType, a feature is represented by a tuple of a “type” and a “selector.” For a particular “type,” there will be a variety of different selectors which are relevant. Many selectors are only relevant to a particular type. An example would be “type”: “kLigaturesType” and “selector”: “kHistoricalLigaturesOnSelector”. Another example would be “type”: “kCharacterShapeType” and “selector”: “kTraditionalCharactersSelector”.
There is a fairly interesting difference between these two examples, though. The first type, kLigaturesType, and “on” and “off” selectors. The second type, kCharacterShapeType, doesn’t. This means that kCharacterShape is what is known as an “exclusive” type, where setting a value for it overrides all other values for it. On the other hand, kLigaturesType is a nonexclusive type, so you can set both kRareLigaturesOnSelector and kCommonLigaturesOnSelector for it. For all the feature types your font knows about, you can declare whether they are exclusive or nonexclusive in the font’s ‘feat’ table, and the software will behave accordingly.
In addition, you can mark a feature as on by default if you set the chain’s default flags to intersect with the feature’s enable flags. Logically, this makes sense - if the feature turns on something which is already on, then that feature should be on by default. However, because the feature is on by default, the software might decide not to show it in the list of available font features. This makes sense for something like required ligatures; turning that feature off would make the font completely illegible, so the software shouldn’t even give the user that option. This behavior allows the font file to determine which features get turned on by default, rather than the software making a guess.
- Codepoints get mapped, one-to-one, to glyphs. This turns your string into a sequence of glyph IDs. Each of these glyph IDs is associated with an “advance” which is a 2D vector from the origin of each glyph to the next.
- Font features run arbitrary modifications on the sequence of glyphs and advances
- Each glyph is rendered at its respective location.
OpenType
OpenType’s model is simpler, so let’s start there. OpenType encapsulates font features into two tables, GPOS and GSUB. GPOS is for glyph positioning, and GSUB is for glyph substitution. Both of these tables actually share the same overall structure. The shared structure is as follows:
- The table is represented by a collection of “scripts.”
- A “script” is represented by a collection of “language systems.”
- A “language system” is represented by a collection of “features.”
- A “feature” is represented by a collection of “lookups.”
- A “lookup” is represented by a collection of typed tables.
Each of the typed tables has an associated “coverage” table. This simply holds a set of glyphs that the typed table acts upon. When the software is laying out some glyphs, if none of the glyphs appear in the coverage table, the software can safely ignore that typed table.
Everything else is shared between GPOS and GSUB, and is just an aggregation of the level below it. Each “feature” has a four-letter code associated with it, such as “liga” or “smcp.” These codes are reported in the program UI, and the user is allowed to switch on or off each of these codes independently. If the user switched off a particular code, the stuff inside that feature’s “lookup” tables is not performed. The lookup tables are performed one by one, in the order the file describes.
Scripts and language systems each have their own four-character tags associated with them. The reason for the distinction is that many different languages may share the same script. For example, both English and Spanish share the Latin script. Because the languages and scripts are expected to have very different glyph patterns, separating out the features into these buckets seems like a good idea. Also, there is a default script tag and a default language system. Microsoft keeps a registry of all of the scripts and language systems, as well as their associated 4-character tags.
TrueType
TrueType font features are completely different. In particular, there are many tables, each with a specialized purpose. For example, instead of the general “GPOS” table, there is a much more specific “kern” (or “kerx”) table, which is only designed for kerning glyphs. Similarly, there is a separate, more-specific, “opbd” table for the optical bounds of the font. Many of the OpenType features have corresponding specific-purpose tables inside TrueType. These tables do not provide the same flexibility as the GPOS table.
However, unlike most of the TrueType tables, the “morx” table is quite general. Conceptually, it describes the same sort of things that the OpenType GSUB table describes. However, its model of font features is very different.
The “morx” table doesn’t mess around with any of that “script” and “language system” stuff. Instead, the table is represented by a collection of “chains.” Each chain is comprised of a collection of typed subtables. These typed subtables describe things like “Rearrange this sequence of glyphs according to these predefined rules” or “insert a specific glyph into the middle of this particular glyph sequence.”
The rest of the chain is devoted to describing which typed subtables should be performed.
Similar to before, each chain gets a coverage table. However, in addition, there is a pretty interesting mechanism to determine which features cause which typed subtable to be performed.
Inside the chain, a sequence of bitwise operations is described, which results in a particular bitfield. Each typed subtable in the chain also has an associated bitfield. If the bitwise and of those two values is nonzero, then the typed subtable is applied.
That sequence of bitwise operations is where individual features come into play. Instead of representing a particular feature as a four-character tag, like in OpenType, TrueType represents a feature as a tuple of (feature type, feature selector). The font describes a sequence of features and corresponding bit masks to be ANDed / ORed. When a feature is enabled in the application’s UI, its associated bitwise operations are performed. When the feature is disabled, its associated bitwise operations are not performed.
The software starts with a known bit pattern. It then runs through the sequence. For each item in the sequence, if its associated font feature is enabled, it performs the appropriate bitwise operations. When it’s done, the result is a particular bit pattern value.
Each of the typed subtables also has an associated pattern value. If the bitwise AND of the calculated bit pattern and a subtable’s bit pattern is nonzero, then the table is performed.
Exclusive and Default Features
In OpenType, the font file has no way of expressing that certain features conflict or that certain features should be on by default. Each feature is simply represented by a four-character tag, and it is either enabled or disabled. The software may (or may not) decide to enable certain features by default based entirely on the semantics of the feature itself (not based on the font file). For example, the OpenType feature “rlig” is mean for “required ligatures” and is generally enabled by default.
The representation of a font feature in TrueType conveys more information than an OpenType font feature. In TrueType, a feature is represented by a tuple of a “type” and a “selector.” For a particular “type,” there will be a variety of different selectors which are relevant. Many selectors are only relevant to a particular type. An example would be “type”: “kLigaturesType” and “selector”: “kHistoricalLigaturesOnSelector”. Another example would be “type”: “kCharacterShapeType” and “selector”: “kTraditionalCharactersSelector”.
There is a fairly interesting difference between these two examples, though. The first type, kLigaturesType, and “on” and “off” selectors. The second type, kCharacterShapeType, doesn’t. This means that kCharacterShape is what is known as an “exclusive” type, where setting a value for it overrides all other values for it. On the other hand, kLigaturesType is a nonexclusive type, so you can set both kRareLigaturesOnSelector and kCommonLigaturesOnSelector for it. For all the feature types your font knows about, you can declare whether they are exclusive or nonexclusive in the font’s ‘feat’ table, and the software will behave accordingly.
In addition, you can mark a feature as on by default if you set the chain’s default flags to intersect with the feature’s enable flags. Logically, this makes sense - if the feature turns on something which is already on, then that feature should be on by default. However, because the feature is on by default, the software might decide not to show it in the list of available font features. This makes sense for something like required ligatures; turning that feature off would make the font completely illegible, so the software shouldn’t even give the user that option. This behavior allows the font file to determine which features get turned on by default, rather than the software making a guess.
This also means that, for all your exclusive features, you need to designate one selector as the default, even if that selector doesn't actually trigger any typed subtables to be performed. Again, this logically makes sense, and allows you to perform some shaping by default.
Saturday, July 11, 2015
Knuth-Plass Line Breaking Algorithm
Line breaking, with regards to paragraph layout, isn’t a very flashy topic. Most people don’t even notice the location of line breaks in a paragraph of written text. However, to people who care, line breaking can be done badly.
There are many different aspects of a set of line breaks in some text. The most important principle is that the text of the line should match the width it's given as best as possible. If there is too much or too little space on a line, the line visually looks jarring. We want to avoid rapid changes of extra space on a line, so we don’t have a loose line followed directly by a tight line. We want to hyphenate words if it makes sense, but only do so sparingly and if required. In addition, we never want to hyphenate two adjacent lines. Similarly, we don’t want to hyphenate the second-to-last line of a paragraph, because there is plenty of space on that last line to accept the full word. One last, more subtle, thing we want to do is to avoid starting a word to the right of where the next line ends, because it would look like that word is floating all alone.
All of these things are desirable, but many line breaking implementations only consider a few, or none, of these qualities. The line breaking algorithm used in web browsers is simply to treat each line independently, and place as much text as possible on that line without exceeding the maximum width.
If we only consider the primary principle of filling up the available space, it may seem that our greedy algorithm is optimal. However, choosing a particular line breaking opportunity affects all subsequent lines, so it may turn out that the best choice for a particular line actually has a negative affect on the entire rest of the paragraph. Instead of optimizing each line independently, it would be better if we tried to optimize the whole paragraph.
Donald Knuth, probably the most famous computer scientist in the world, worked with Michael Plass to create an algorithm which does so. The algorithm is actually quite simple, but it does have some tricky parts.
Their algorithm has two parts: a classification stage and an execution stage. The classification stage translates each item in the text into one of three types:
There are actually all sorts of diverse typographical situations which can be represented with particular patterns of the items in this classification; Knuth names quite a few of them. Once we have done this classification, we want to choose a set of line breaks which correspond to glue items or penalty items. In order to choose a good set of line breaks, we have to introduce three new concepts.
The first is the concept of the “adjustment ratio” of a line, given a particular breakpoint. The adjustment ratio is simply the excess space in the line divided by the sum of the stretchability factors of all the glue items in the line. If the line is too long rather than too short, then the calculation is the same thing except with using shrinkability factors instead.
The authors then define the “badness” of a line to be a particular increasing function of the line’s adjustment ratio. The particular shape of this function they chose involves the cube root of the adjustment ratio, and they admit that this function was chosen arbitrarily and “has shown that good results are obtained.”
Then, the authors go further and define the “demerits” of a line. This is an increasing function of badness, but also includes extra information, such as the cost of a penalty item, if one was chosen to end the line. In addition, it includes a term which is positive if this is the second penalty item chosen in a row to end lines with. This function involves squaring the sum of badness and penalty, which the authors admit is arbitrary but “it works well in practice.”
The goal of the execution phase of the algorithm is to minimize the sum of the demerits of each line. The way it does this is actually very straightforward dynamic programming. Scan through the string, and each time you encounter a breaking opportunity, look at prior line breaking opportunities and consider a candidate line between these two opportunities. Compute the demerits of this line candidate. Select the line candidate which has the minimum demerits, and associate it with this particular line breaking opportunity. Continue through the string in this manner until you get to the end. The selection of lines which ends up with the minimum total demerits is the output of the algorithm.
A dynamic programming approach is valid because we are summing the total demerits and optimizing the entire prefix of the paragraph. This optimized prefix grows until it contains the entire text. Given an optimized prefix, if we consider a line starting at the end of that prefix, the particular decision we have made that led up to the beginning of that line don’t matter; the only thing that matters is the sum of the demerits up to that point.
Naively implemented, this algorithm is O(n2). However, there is an optimization which can improve the running time of the algorithm. The fundamental observation is that, given a line candidate’s ending position, there are only a few candidate starting positions which are not terrible. In particular, when we have selected a particular breaking candidate and are looking through prior opportunities, we can limit our search to only the prior opportunities which are not terrible. We can define “not terrible” as “having demerits below a threshold.” If we come across a line candidate that is wildly too long, we can simply forget the breaking opportunity at its beginning in our searches, because there will never be another viable line candidate starting at this opportunity. If our line candidate is wildly too short, we can abort our search, assuming we are searching in the direction of increasing indices in the string (but we can't forget this starting opportunity because it may be valuable in subsequent searches). Therefore, for each ending opportunity in our text, our search will investigate a relatively low (and vaguely constant-ish) amount of line candidates. So, if we choose an appropriate terribleness-threshold, our algorithm is O(n).
It’s worth mentioning what happens when we pick a bad terribleness threshold. If our threshold is too high, our algorithm will take much longer to run (bounding on O(n2)), but it may find a more globally-correct solution. If our threshold is too low, the algorithm will find that it is impossible to find acceptable line breaks all the way to the end of the paragraph. In this case, there is nothing we can do but try again with a higher threshold (or the greedy algorithm, which is guaranteed to find a result).
Aside: Calculating widths of line candidates can be done quickly with the established technique of the subsequence sum algorithm. This algorithm has you construct an array which contains a running sum of the widths of all the prefixes of the string (which can be done in O(n)). Then, the width of any subsequence is simply the difference between the two appropriate elements in this array. (I've seen this algorithm used to implement box blurs on images in linear time)
There is one bit of trickiness, however, with the line breaking algorithm. So far, we have assumed that the only affect an optimal prefix of a paragraph has on subsequent lines is its demerits. However, this is not true in the presence of floats. With floats, our available width can change partway down the page. Also, the location of this change might be affected by the layout of the current line, because floating elements occur in-line with text (meaning: if the floating element gets pushed down to a successive line, the location that the width change also gets pushed down to the successive line). This means that the algorithm is sensitive not only to the demerits created so far, but also the number of lines created and the location of all floating elements so far.
Because of this, we need to remember multiple ways to get to a particular line breaking candidate if those ways differ in either line count or floating element placement (and possibly things like differing line heights due to fallback fonts). The presence of these “duplicate” elements can cause our search space to grow dramatically. Luckily, we can combat this growing search space by setting our terribleness-threshold appropriately.
Overall, we have a few tools at our disposal. The first is how we classify our input text. The algorithm can be adapted to many typographic scenarios simply by inserting extra items in our stream of classified items. Next, we can change the values (like nominal width, or stretchiness factor) which characterize each item in our stream. Third, we can choose different functions for calculating badness and demerits. Finally, we can select a terribleness-threshold which will balance runtime and the likelihood of the algorithm completing. Some of these parameters are probably language-dependent, which makes selecting them even more difficult.
There are many different aspects of a set of line breaks in some text. The most important principle is that the text of the line should match the width it's given as best as possible. If there is too much or too little space on a line, the line visually looks jarring. We want to avoid rapid changes of extra space on a line, so we don’t have a loose line followed directly by a tight line. We want to hyphenate words if it makes sense, but only do so sparingly and if required. In addition, we never want to hyphenate two adjacent lines. Similarly, we don’t want to hyphenate the second-to-last line of a paragraph, because there is plenty of space on that last line to accept the full word. One last, more subtle, thing we want to do is to avoid starting a word to the right of where the next line ends, because it would look like that word is floating all alone.
All of these things are desirable, but many line breaking implementations only consider a few, or none, of these qualities. The line breaking algorithm used in web browsers is simply to treat each line independently, and place as much text as possible on that line without exceeding the maximum width.
If we only consider the primary principle of filling up the available space, it may seem that our greedy algorithm is optimal. However, choosing a particular line breaking opportunity affects all subsequent lines, so it may turn out that the best choice for a particular line actually has a negative affect on the entire rest of the paragraph. Instead of optimizing each line independently, it would be better if we tried to optimize the whole paragraph.
Donald Knuth, probably the most famous computer scientist in the world, worked with Michael Plass to create an algorithm which does so. The algorithm is actually quite simple, but it does have some tricky parts.
Their algorithm has two parts: a classification stage and an execution stage. The classification stage translates each item in the text into one of three types:
- A box. This represents a character or word and has a particular width.
- Glue. This represents a space character, and is characterized by three values:
- A natural width
- A stretchability value. Higher values here mean that, when a line is stretched, more of that stretch is allocated to this character
- A shrinkability value. This is the same thing, but for when a line is shrunk.
- A penalty item. This represents a hyphenation opportunity within a word. It is characterized by two values (In the text it has three, but the third one isn’t really interesting in this discussion):
- A width to use if a line break is chosen at this item.
- A cost associated with choosing a line break at this item
There are actually all sorts of diverse typographical situations which can be represented with particular patterns of the items in this classification; Knuth names quite a few of them. Once we have done this classification, we want to choose a set of line breaks which correspond to glue items or penalty items. In order to choose a good set of line breaks, we have to introduce three new concepts.
The first is the concept of the “adjustment ratio” of a line, given a particular breakpoint. The adjustment ratio is simply the excess space in the line divided by the sum of the stretchability factors of all the glue items in the line. If the line is too long rather than too short, then the calculation is the same thing except with using shrinkability factors instead.
The authors then define the “badness” of a line to be a particular increasing function of the line’s adjustment ratio. The particular shape of this function they chose involves the cube root of the adjustment ratio, and they admit that this function was chosen arbitrarily and “has shown that good results are obtained.”
Then, the authors go further and define the “demerits” of a line. This is an increasing function of badness, but also includes extra information, such as the cost of a penalty item, if one was chosen to end the line. In addition, it includes a term which is positive if this is the second penalty item chosen in a row to end lines with. This function involves squaring the sum of badness and penalty, which the authors admit is arbitrary but “it works well in practice.”
The goal of the execution phase of the algorithm is to minimize the sum of the demerits of each line. The way it does this is actually very straightforward dynamic programming. Scan through the string, and each time you encounter a breaking opportunity, look at prior line breaking opportunities and consider a candidate line between these two opportunities. Compute the demerits of this line candidate. Select the line candidate which has the minimum demerits, and associate it with this particular line breaking opportunity. Continue through the string in this manner until you get to the end. The selection of lines which ends up with the minimum total demerits is the output of the algorithm.
A dynamic programming approach is valid because we are summing the total demerits and optimizing the entire prefix of the paragraph. This optimized prefix grows until it contains the entire text. Given an optimized prefix, if we consider a line starting at the end of that prefix, the particular decision we have made that led up to the beginning of that line don’t matter; the only thing that matters is the sum of the demerits up to that point.
Naively implemented, this algorithm is O(n2). However, there is an optimization which can improve the running time of the algorithm. The fundamental observation is that, given a line candidate’s ending position, there are only a few candidate starting positions which are not terrible. In particular, when we have selected a particular breaking candidate and are looking through prior opportunities, we can limit our search to only the prior opportunities which are not terrible. We can define “not terrible” as “having demerits below a threshold.” If we come across a line candidate that is wildly too long, we can simply forget the breaking opportunity at its beginning in our searches, because there will never be another viable line candidate starting at this opportunity. If our line candidate is wildly too short, we can abort our search, assuming we are searching in the direction of increasing indices in the string (but we can't forget this starting opportunity because it may be valuable in subsequent searches). Therefore, for each ending opportunity in our text, our search will investigate a relatively low (and vaguely constant-ish) amount of line candidates. So, if we choose an appropriate terribleness-threshold, our algorithm is O(n).
It’s worth mentioning what happens when we pick a bad terribleness threshold. If our threshold is too high, our algorithm will take much longer to run (bounding on O(n2)), but it may find a more globally-correct solution. If our threshold is too low, the algorithm will find that it is impossible to find acceptable line breaks all the way to the end of the paragraph. In this case, there is nothing we can do but try again with a higher threshold (or the greedy algorithm, which is guaranteed to find a result).
Aside: Calculating widths of line candidates can be done quickly with the established technique of the subsequence sum algorithm. This algorithm has you construct an array which contains a running sum of the widths of all the prefixes of the string (which can be done in O(n)). Then, the width of any subsequence is simply the difference between the two appropriate elements in this array. (I've seen this algorithm used to implement box blurs on images in linear time)
There is one bit of trickiness, however, with the line breaking algorithm. So far, we have assumed that the only affect an optimal prefix of a paragraph has on subsequent lines is its demerits. However, this is not true in the presence of floats. With floats, our available width can change partway down the page. Also, the location of this change might be affected by the layout of the current line, because floating elements occur in-line with text (meaning: if the floating element gets pushed down to a successive line, the location that the width change also gets pushed down to the successive line). This means that the algorithm is sensitive not only to the demerits created so far, but also the number of lines created and the location of all floating elements so far.
Because of this, we need to remember multiple ways to get to a particular line breaking candidate if those ways differ in either line count or floating element placement (and possibly things like differing line heights due to fallback fonts). The presence of these “duplicate” elements can cause our search space to grow dramatically. Luckily, we can combat this growing search space by setting our terribleness-threshold appropriately.
Overall, we have a few tools at our disposal. The first is how we classify our input text. The algorithm can be adapted to many typographic scenarios simply by inserting extra items in our stream of classified items. Next, we can change the values (like nominal width, or stretchiness factor) which characterize each item in our stream. Third, we can choose different functions for calculating badness and demerits. Finally, we can select a terribleness-threshold which will balance runtime and the likelihood of the algorithm completing. Some of these parameters are probably language-dependent, which makes selecting them even more difficult.
Friday, July 10, 2015
Generating x86_64 Machine Code at Runtime
As I discussed previously[1], there is a particular file format for representing programs on disk. This file format includes a significant amount of machinery for the dynamic loader to resolve symbols at runtime rather than compile-time. However, once your program is already running, it is possible to actually author more machine code, and to run that new code directly.
In order to do this, you have to write machine code into a buffer. I’m using an x86_64 machine, so that’s the format that I’ll be using. x86_64 machine code has a very long history which has significantly affected the instruction format.
The instructions originally came from the Intel 8086, back in 1979. That processor is a 16-bit processor which included 8 16-bit data registers: AX, BX, CX, DX, BP, SP, SI, and DI. The first four of these, AX, BX, CX, and DX, are general purpose registers. BP is the “base pointer” and always points to the base of the current stack frame. Similarly, SP is the “stack pointer” and always points to the top of the current stack frame. The stack grows downward, so SP always has a lower value then BP. SI and DI are usually used for pointers or indexes into memory.
There are also some other special-purpose registers, such as IP for “instruction pointer” which represents where control flow is at, and FLAGS. Instructions such as conditionals will flip bits in FLAGS, which other instructions like conditional jumps will inspect.
The 8086 allowed addressing a maximum of one megabyte (= 2^20) of memory. However, the registers can only hold 16 bits, which means the maximum representable value is 2^16. Therefore, pointers are represented as a combination of two registers (specifically, you shift the contents of one register by 4 bits and add that to the other register). There are 4 “segment registers” that handle this kind of addressing: CS, DS, ES, and SS.
The Intel 386, in 1985, introduced 32-bit wide addressing and registers. This was achieved by putting the processor in a new mode. In this mode, the same registers are available, but they are all 32-bits wide. These wider registers are named with a leading “E,” which stands for “extended.” For example, we have “EAX” and “EBP.” However, the old 16-bit registers are still available, aliased to the low 16-bits of the new wider registers. That means that if you write into AX, then read from EAX, you would get what you had written.
Indeed, this register aliasing was not a new concept; the 8086 already allowed you to access the four data registers by their low and high bytes. “AL” is the low byte of “AX” and “AH” is the high byte of “AX.” It is for this reason that the “X” in the 16-bit registers stands for “eXtended.”
It’s important to realize here that the number of registers you can interact with has stayed at a constant 8. Therefore, you only need three bits to represent a particular register. This is an important quality of the instruction format.
The instructions have a fairly complicated format, described at [2]. I’ll summarize it here:
Of course, you aren’t ::really:: operating on memory. When you think you are operating on memory, the hardware is actually generating load and store micro-ops and performing them. You just don’t see it.
The 32-bit Intel architecture was the standard desktop computer architecture until 2003, when AMD extended it to 64-bits. Similar to the older extension to 32-bits, the registers got wider, but the low 32-bits of each register alias the old names. The new names replace the leading “E” with a leading “R” so we have names like “RSP” and “RCX. In addition, however, they also added 8 more registers simply named R8 - R15.
This addition of new registers proved problematic for instruction encoding. In particular, we were using 3 bits to identify a register, but now we need 4 bits. Rather than dramatically change the encoding, AMD decided to prefix instructions that need to use these 64-bit registers with a “REX prefix.” This prefix is a byte where the high nibble is a “4,” and the low nibble includes that 4th bit needed to properly identify a register. Because instructions can have multiple operands which may each need to identify a register, each of the bits in the low nibble of the REX Prefix corresponds to a different operand. Therefore, if you’re trying to figure out which register an instruction is naming, you have to concatenate one bit from the REX prefix and three bits from the ModR/M byte.
AMD also decided to make the REX prefix optional, so instructions which only needed to operate with 32-bits and the 32-bit registers don’t need to specify it. You may think that this means that the new 64-bit instructions are completely backwards-compatible with 32-bit code; however, that is incorrect. In 32-bit mode, the REX prefix itself is a valid opcode. Therefore, if the machine is in 32-bit mode or 64-bit mode, it will interpret that byte differently.
That’s pretty much it when it comes to formatting instructions. If you want to generate commands at runtime, it isn’t too difficult to figure out how to output them in the format of x86_64 machine code. However, which instructions should you emit?
Well, the instructions are grouped into categories[2]. General purpose instructions include things like PUSH, MOV, CALL, ADD, SAR (shift arithmetic right), JMP, etc. These are pretty self-explanatory.
There are also a bunch of floating-point instructions which use the x87 floating point unit present in all modern processors. This unit used to be an optional coprocessor which you could add to your computer, but has been bundled in all processors since the 487.
The unit is actually pretty interesting. Instead of individually accessible registers, the unit uses a stack of 8 floating-point registers. Instead of naming registers individually, you push and pop items onto the stack, and math operations will replace the top items on the stack with the result of the operation. Also, these registers are 80-bits wide, allowing for significantly more precision than a double. (I’ll probably write another whole post later just about floating point precision)
Intel’s first foray into SIMD (Single Instruction Multiple Data) is with a collection of MMX instructions, first available with the Pentium. This defined 8 new 64-bit registers, named MM0 - MM7, which are aliased with low 64-bits of the x87 register stack. Instead of representing a single 64-bit value, each register represented a vector of smaller types (2x 32-bit numbers, 4x 16-bit numbers, or 8x 8-bit numbers). MMX instructions would operate on these vectors pairwise. So, if you added two MMX registers together, and chose to interpret those registers each as 2x 32-bit numbers, you would actually get two additions for the price of one, since the first components of the vectors gets added and the second components of the vectors gets added. Unfortunately, MMX only supports integral math (not floating-point math) which makes it not very useful. Also, 64-bits is not a very wide vector, making it even less useful.
Intel’s next attempt of SIMD is the SSE set of instructions, initially released with the Pentium 3, which was extended several times to include SSE2, SSE3, SSSE3, and SSE4. This sets up a new set of 8 128-bit registers (not aliased to anything, this time) named XMM0 - XMM7. Similar to general-purpose registers, 64-bit machines double this to 16 new registers. These instructions operate on floating point data, and as of SSE2, also can operate on integral data, thereby obsoleting MMX. In Haswell and beyond, there are fused-multiply-add instructions, allowing you to perform a multiply and an add in a single instruction.
Similarly, Intel created the AVX and AVX2 instructions which use 8 new registers named YMM0 - YMM7 (yet again, 16 new registers on 64-bit machines). These registers are 256 bits wide, and the low 128 bits alias the XMM registers. AVX was first released in 2011 with Sandy Bridge processors. There is a plan to release AVX-512 with 512-bit-wide registers, but it hasn’t shipped yet.
And that’s pretty much it. There are some other instructions regarding transactional memory and halfwidth float conversion. You can detect which of these instructions the processor accepts by issuing the CPUID instruction, which will return a bit mask of capabilities. But, overall, the amount of instructions really isn't that daunting.
We are now very close to being able to write instructions at runtime. However, we need to be able to pass data between our regular program and our generated code. The way this is normally achieved is with arguments and return values to functions. At the assembly level, these concepts are achieved with simply leaving data in a predefined place, and then jumping into a function. The code in the function will expect the data to be in the predefined place. This means that the caller and the callee have to both agree about what the signature of the function is.
There is a pattern, though, of where particular items are placed. In fact, each operating system will pick a particular “ABI,” or Application Binary Interface, which defines rules about where to place all these items. Everyone on either side of a caller/callee relationship needs to adhere to this. Also, the ABI chosen is different for different operating systems, which is yet another reason why you can't run code compiled for one OS on another OS, even if they are running on the same machine.
The Intel 32-bit ABI[3] is pretty simple. All function arguments simply get dumped onto the stack, one by one. Return values are a little tricky, though. If the return type is something which fits in a register, than it is simply placed in EAX. Otherwise, the caller will actually create space for the callee to fill in, and will place a pointer to this item as a hidden first argument to the function.
The Intel 64-bit ABI[4] is significantly more complicated, because they wanted to pass more items in registers, which would reduce cache pressure. The ABI involves classifying each argument based on its type and position in the argument list, and then placing each item in either a register or on the stack.
There’s one last piece to code generation which requires some thought: linking. Much of the complexity of the Mach-O file format is due to the linker needing to fixup symbols at runtime to point where they should point. However, our codegen is occurring at runtime, after the linker has fixed up all the symbols. This means that, if we want to look up the address for a function, we actually already have the address for it! All we need to do is just write out &function and it will be correctly be called.
All right, so now we’ve pretty much got everything we need. First, we need to allocate some memory which has the execute permission set.
void *ptr = mmap(NULL, length, PROT_READ | PROT_WRITE | PROT_EXEC, MAP_PRIVATE | MAP_ANON, -1, 0)
Next, we generate instructions, convert them to machine code, and pack them out into that buffer, one by one. When we’re done generating code, we can call it by simply casting the pointer to our buffer to the correct function pointer type (keep in mind the ABI!) and calling it!
((int(*)(int, int))ptr)(4, 17)
We just made a JIT[5].
[1] http://litherum.blogspot.com/2015/07/producing-executables.html
[2] http://www.intel.com/content/www/us/en/processors/architectures-software-developer-manuals.html
[3] http://www.sco.com/developers/devspecs/abi386-4.pdf
[4] http://people.freebsd.org/~obrien/amd64-elf-abi.pdf
[5] https://github.com/litherum/JIT
In order to do this, you have to write machine code into a buffer. I’m using an x86_64 machine, so that’s the format that I’ll be using. x86_64 machine code has a very long history which has significantly affected the instruction format.
The instructions originally came from the Intel 8086, back in 1979. That processor is a 16-bit processor which included 8 16-bit data registers: AX, BX, CX, DX, BP, SP, SI, and DI. The first four of these, AX, BX, CX, and DX, are general purpose registers. BP is the “base pointer” and always points to the base of the current stack frame. Similarly, SP is the “stack pointer” and always points to the top of the current stack frame. The stack grows downward, so SP always has a lower value then BP. SI and DI are usually used for pointers or indexes into memory.
There are also some other special-purpose registers, such as IP for “instruction pointer” which represents where control flow is at, and FLAGS. Instructions such as conditionals will flip bits in FLAGS, which other instructions like conditional jumps will inspect.
The 8086 allowed addressing a maximum of one megabyte (= 2^20) of memory. However, the registers can only hold 16 bits, which means the maximum representable value is 2^16. Therefore, pointers are represented as a combination of two registers (specifically, you shift the contents of one register by 4 bits and add that to the other register). There are 4 “segment registers” that handle this kind of addressing: CS, DS, ES, and SS.
The Intel 386, in 1985, introduced 32-bit wide addressing and registers. This was achieved by putting the processor in a new mode. In this mode, the same registers are available, but they are all 32-bits wide. These wider registers are named with a leading “E,” which stands for “extended.” For example, we have “EAX” and “EBP.” However, the old 16-bit registers are still available, aliased to the low 16-bits of the new wider registers. That means that if you write into AX, then read from EAX, you would get what you had written.
Indeed, this register aliasing was not a new concept; the 8086 already allowed you to access the four data registers by their low and high bytes. “AL” is the low byte of “AX” and “AH” is the high byte of “AX.” It is for this reason that the “X” in the 16-bit registers stands for “eXtended.”
It’s important to realize here that the number of registers you can interact with has stayed at a constant 8. Therefore, you only need three bits to represent a particular register. This is an important quality of the instruction format.
The instructions have a fairly complicated format, described at [2]. I’ll summarize it here:
- Instructions start with a sequence of up to 4 prefix bytes
- Then comes a 1 - 3 byte opcode. This is simply a number which represents the instruction
- The rest of the format is dependent on the arguments specific to each individual opcode. Register operands are encoded in 1 - 2 subsequent bytes, called the ModR/M byte and the SIB byte, respectively
- An optional displacement value and an optional immediate value follow
Of course, you aren’t ::really:: operating on memory. When you think you are operating on memory, the hardware is actually generating load and store micro-ops and performing them. You just don’t see it.
The 32-bit Intel architecture was the standard desktop computer architecture until 2003, when AMD extended it to 64-bits. Similar to the older extension to 32-bits, the registers got wider, but the low 32-bits of each register alias the old names. The new names replace the leading “E” with a leading “R” so we have names like “RSP” and “RCX. In addition, however, they also added 8 more registers simply named R8 - R15.
This addition of new registers proved problematic for instruction encoding. In particular, we were using 3 bits to identify a register, but now we need 4 bits. Rather than dramatically change the encoding, AMD decided to prefix instructions that need to use these 64-bit registers with a “REX prefix.” This prefix is a byte where the high nibble is a “4,” and the low nibble includes that 4th bit needed to properly identify a register. Because instructions can have multiple operands which may each need to identify a register, each of the bits in the low nibble of the REX Prefix corresponds to a different operand. Therefore, if you’re trying to figure out which register an instruction is naming, you have to concatenate one bit from the REX prefix and three bits from the ModR/M byte.
AMD also decided to make the REX prefix optional, so instructions which only needed to operate with 32-bits and the 32-bit registers don’t need to specify it. You may think that this means that the new 64-bit instructions are completely backwards-compatible with 32-bit code; however, that is incorrect. In 32-bit mode, the REX prefix itself is a valid opcode. Therefore, if the machine is in 32-bit mode or 64-bit mode, it will interpret that byte differently.
That’s pretty much it when it comes to formatting instructions. If you want to generate commands at runtime, it isn’t too difficult to figure out how to output them in the format of x86_64 machine code. However, which instructions should you emit?
Well, the instructions are grouped into categories[2]. General purpose instructions include things like PUSH, MOV, CALL, ADD, SAR (shift arithmetic right), JMP, etc. These are pretty self-explanatory.
There are also a bunch of floating-point instructions which use the x87 floating point unit present in all modern processors. This unit used to be an optional coprocessor which you could add to your computer, but has been bundled in all processors since the 487.
The unit is actually pretty interesting. Instead of individually accessible registers, the unit uses a stack of 8 floating-point registers. Instead of naming registers individually, you push and pop items onto the stack, and math operations will replace the top items on the stack with the result of the operation. Also, these registers are 80-bits wide, allowing for significantly more precision than a double. (I’ll probably write another whole post later just about floating point precision)
Intel’s first foray into SIMD (Single Instruction Multiple Data) is with a collection of MMX instructions, first available with the Pentium. This defined 8 new 64-bit registers, named MM0 - MM7, which are aliased with low 64-bits of the x87 register stack. Instead of representing a single 64-bit value, each register represented a vector of smaller types (2x 32-bit numbers, 4x 16-bit numbers, or 8x 8-bit numbers). MMX instructions would operate on these vectors pairwise. So, if you added two MMX registers together, and chose to interpret those registers each as 2x 32-bit numbers, you would actually get two additions for the price of one, since the first components of the vectors gets added and the second components of the vectors gets added. Unfortunately, MMX only supports integral math (not floating-point math) which makes it not very useful. Also, 64-bits is not a very wide vector, making it even less useful.
Intel’s next attempt of SIMD is the SSE set of instructions, initially released with the Pentium 3, which was extended several times to include SSE2, SSE3, SSSE3, and SSE4. This sets up a new set of 8 128-bit registers (not aliased to anything, this time) named XMM0 - XMM7. Similar to general-purpose registers, 64-bit machines double this to 16 new registers. These instructions operate on floating point data, and as of SSE2, also can operate on integral data, thereby obsoleting MMX. In Haswell and beyond, there are fused-multiply-add instructions, allowing you to perform a multiply and an add in a single instruction.
Similarly, Intel created the AVX and AVX2 instructions which use 8 new registers named YMM0 - YMM7 (yet again, 16 new registers on 64-bit machines). These registers are 256 bits wide, and the low 128 bits alias the XMM registers. AVX was first released in 2011 with Sandy Bridge processors. There is a plan to release AVX-512 with 512-bit-wide registers, but it hasn’t shipped yet.
And that’s pretty much it. There are some other instructions regarding transactional memory and halfwidth float conversion. You can detect which of these instructions the processor accepts by issuing the CPUID instruction, which will return a bit mask of capabilities. But, overall, the amount of instructions really isn't that daunting.
We are now very close to being able to write instructions at runtime. However, we need to be able to pass data between our regular program and our generated code. The way this is normally achieved is with arguments and return values to functions. At the assembly level, these concepts are achieved with simply leaving data in a predefined place, and then jumping into a function. The code in the function will expect the data to be in the predefined place. This means that the caller and the callee have to both agree about what the signature of the function is.
There is a pattern, though, of where particular items are placed. In fact, each operating system will pick a particular “ABI,” or Application Binary Interface, which defines rules about where to place all these items. Everyone on either side of a caller/callee relationship needs to adhere to this. Also, the ABI chosen is different for different operating systems, which is yet another reason why you can't run code compiled for one OS on another OS, even if they are running on the same machine.
The Intel 32-bit ABI[3] is pretty simple. All function arguments simply get dumped onto the stack, one by one. Return values are a little tricky, though. If the return type is something which fits in a register, than it is simply placed in EAX. Otherwise, the caller will actually create space for the callee to fill in, and will place a pointer to this item as a hidden first argument to the function.
The Intel 64-bit ABI[4] is significantly more complicated, because they wanted to pass more items in registers, which would reduce cache pressure. The ABI involves classifying each argument based on its type and position in the argument list, and then placing each item in either a register or on the stack.
There’s one last piece to code generation which requires some thought: linking. Much of the complexity of the Mach-O file format is due to the linker needing to fixup symbols at runtime to point where they should point. However, our codegen is occurring at runtime, after the linker has fixed up all the symbols. This means that, if we want to look up the address for a function, we actually already have the address for it! All we need to do is just write out &function and it will be correctly be called.
All right, so now we’ve pretty much got everything we need. First, we need to allocate some memory which has the execute permission set.
void *ptr = mmap(NULL, length, PROT_READ | PROT_WRITE | PROT_EXEC, MAP_PRIVATE | MAP_ANON, -1, 0)
Next, we generate instructions, convert them to machine code, and pack them out into that buffer, one by one. When we’re done generating code, we can call it by simply casting the pointer to our buffer to the correct function pointer type (keep in mind the ABI!) and calling it!
((int(*)(int, int))ptr)(4, 17)
We just made a JIT[5].
[1] http://litherum.blogspot.com/2015/07/producing-executables.html
[2] http://www.intel.com/content/www/us/en/processors/architectures-software-developer-manuals.html
[3] http://www.sco.com/developers/devspecs/abi386-4.pdf
[4] http://people.freebsd.org/~obrien/amd64-elf-abi.pdf
[5] https://github.com/litherum/JIT
Subscribe to:
Posts (Atom)