Inter-Office MemorandumToWhom it May ConcernDateApril 17, 1980FromLyle RamshawLocationPalo AltoSubjectKerned Strike Fonts (Revised version)OrganizationCSLXEROX Filed on:[Maxc1]KenrnedStrikes.bravo[Maxc1]KenrnedStrikes.pressIt's time for a new font format! The Strike format for font files was devised to permit the gracefuluse of BITBLT for writing characters onto the Alto screen; the authoritative description of thisoriginal Strike format can be found in the memo Font Representations and Formats by Bob Sproull,filed on[Maxc1]FontFormats.Press.The original Strike format, however, has a serious difficulty: it does not distinguish between thespacing width of a character, and the width of that character's bounding box. Let us say that acharacter kerns to the left if its raster includes bits in columns to the left of the character's origin. Acharacter is said to kern to the right if its raster includes bits in columns to the right of the end ofits width vector (the origin of the next character). The original Strike format is incapable ofhandling characters that kern in either direction. The newer PARC fonts contain lots of zero-widthaccent characters that are intended to overprint the following character. These accent charactersoverhang the ends of their width vectors by quite a bit, that is, they kern heavily to the right;hence, conventional Strike format can't handle them.There are basically two ways to adjust Strike format so that it can handle characters that kern.Consider left kerning, for example. One possibility might be called the padding approach. The ideahere is to pad every character raster in the strike body with enough blank columns so that all of theoverhanging bits fit into those padding columns.A padding approach to the left kerning problem would work like this. We would look through theentire font, and determine the size of the largest left kern of any character; say that it is fourcolumns. Thus, at least one character's bounding box includes four columns to the left of theorigin, while no character overhangs to the left of the origin by more than four columns. Whenputting character rasters into the Strike array, then, we include four columns for every character tothe left of that character's origin. We also find a field somewhere early in the file to put thenumber 4'. A user of the resulting file would paint a character on the display by BitBlt'ing theentire character raster, padding columns and all. The first column of the destination of the BitBltwould be given by the formula (4).A symmetric padding strategy could be used to handle right kerning. But any padding strategy hasproblems. The padding columns appear in every character's raster; they take up space in the file,and in memory, and they slow down the process of painting the character, since they are includedin the BitBlt's.The other approach to the kerning problem might be called the auxiliary table approach. In thisscheme, we store the character rasters into the strike body by their bounding box dimensions, andthen we use an auxiliary table of small integers to tell the location of the origin relative to theН]Оg║pТiНІОc8qН]rТXН-єqН7Br НІО]ШqН]rН-єqН7BrНІОYqН]rП%Н-єqН7BrНЭОSЛsrНЇОMЪНШП"НШОL{П"НЇОI-Т▀Т▄ПRНЇОG┘ТЄПaНЇОEчТ┬П0trНЇОD7ТНШОB▐П'НЇО?AТ╘ПcНЇО=≥ТўП3Т╞П-НЇО;РТ─ trТ│П2НЇО:KТ⌠trТ■П&НЇО8ёТпТяПAНЇО6ЭТ▀ПcНЇО5UТІП>ТЇП$НЇО3ґТ╩Т╪ПPНЇО2ТП4НЇО.ЇТ©П4ТюП,НЇО-Т┐П:Т└tr НЇО+iТ┘ПeНЇО)аТП0НЇО&sТ┼ПNТ▀НЇО$кТЇТ╦ПEНЇО#$ТаП1ТбП-НЇО!}ТїПFТ╗НЇОуТ■П9Т∙П,НЇО.Т©ПDТюНЇО┤Т╘ПbНЇОъТ⌡П(Т°П<НЇО8ТП3НЇОИТ▀ПHТ▄НЇОBТ▓П.Т⌠П5НЇО⌡Т≤Т≥ПZНЇОСТНЇО ╔Т╔ТіП)trtr НЇОЩТ⌡Т°ПMНЇО VТ╦ Т╧ПU┬Э >Г^С9KernedStrikes (revised version)2bounding box, and the length of the width vector. The auxiliary table approach seems to be abetter choice than a padding approach. The purpose of this memo is propose a new Strike fileformat that uses the auxiliary table approach to handle both left and right kerning. If you object tothe following plan, or have suggestions to improve it, please get in touch with me as soon aspossible. History:The definition of Strike file format in Sproull's memo Font Representations and Formats suggeststhe use of a padding scheme to handle left kerning. As I read it, this memo states that a negativeinteger in the xoffset word implies that every character raster in the strike is padded by (xoffset)columns on the left. To the best of my knowledge, no one ever wrote any programs that wouldcorrectly produce or consume such a left-padded strike font. In addition, left kerning doesn'thappen to be nearly as common in PARC fonts as right kerning anyway. We could, of course,legislate against left kerning completely, and start devoting the xoffset word to a right kerningscheme. In fact, this is what the current version of PrePress does when the Kerned flag is set inMakeStrike. But thinking things over, it seems to be a better plan to take advantage of the fact that no paddingscheme has been widely used, and drop all such schemes in favor of a format based on the auxiliarytable approach. From now on, if you want to handle kerning, you should use the newKernedStrike format, and its auxiliary tables. Some terminology:The following section is a substitute for section 7.2 of the Font Representations and Formats memo.Before we start on that, though, let me review a little terminology from that memo, in case thereader is rusty. The origin of a charcter is a reference point located at the corner where four pixelstouch. The width vector of a character is a two-dimensional vector that specifies the desireddisplacement from the origin of the current character to the origin of the next character in a string.The components of the width vector are written Wx and Wy. Wx is always nonnegative; all of thefont formats intended for the Alto screen assume in addition that Wx is an integral number ofpixels, and that all characters have a Wy of zero. The bounding box of the black pixels in thecharacter raster is a rectangle with width BBdx and height BBdy. These numbers are alwaysnonnegative. They are both zero if the character has no black bits in its raster (such characters arecalled empty characers), and are both positive in all other cases. If we use the origin to define aCartesian coordinate system on the plane, the lower left corner of the bounding box is located atthe point . Thus, the left edge of the bounding box is located BBox units to the rightof the origin (left if BBox is negative), while the bottom of the bounding box is located BBoy unitsabove the origin (below if BBoy is negative). Empty charcters have BBox and BBoy equal to zero,by convention. Finally, if all of the characters in the font are superimposed with their originscoincident, the dimensions of the resulting bounding box are called FBBdx, FBBdy, FBBox, andFBBoy respectively.7.2 (New version) STRIKE format:There are four kinds of files in the Strike class: a PlainStrike file (conventional extension .Strike), aKernedStrike file (conventional extension .KS), a PlainStrikeIndex file (conventional extension.StrikeX), and a KernedStrikeIndex file (conventional extension .KSX). In a PlainStrike file, theindividual rasters of the characters are assembled in ascending order of character code into one largeraster, called the strike. The baselines of the characters are aligned, and the origin of each characteris made coincident with the end of the width vector of the preceding character. The PlainStrike filealso contains a table indexed by character code that points to the leftmost column of the raster foreach character in the strike. Warning: since the rasters in a PlainStrike file are positioned by theirНЇОfЯuТ rНGОuНЇОbrТІТЇПHНЇО`vТ╠П'Т╡П6НЇО^оТ┘П7Т├П/НЇО](ТйПRТк НЇО[─Т НЇОX2uНЇОTЦrТ╚П7tТ╛rНЇОS<Т■ПGТ∙НЇОQ■Т■ПWТ∙ НЇОOМТіП$ТїП8НЇОNFТнП@ТоНЇОL·Т╡ПDТЁНЇОJВТкПYТлНЇОIPТ╒ПHТёНЇОG╗ТНЇОDZТ█П1Т▌П3НЇОB╡Т│Т┌ПLНЇОAТТП3НЇО?dТП1НЇО<uНЇО8фrТ▌Т▐П#tП!rНЇО7ТЄТ╣ПMНЇО5xТ┬Т┴П^НЇО3пТуПVТжНЇО2)Т█ПCТ▌П#НЇО0┌Т└Т┘ПOНЇО.зТ╩ПDТ╪НЇО-3Т╟Т╠ПOНЇО+▄ТсП*ТтП0НЇО)ДТ▌Т▐ПFНЇО(=ТёtrТєПLНЇО&√Т╔ПFТіНЇО$НТ┌П,Т┐П7НЇО#GТ▄ПNТ█НЇО!═Т░П"Т▒П>НЇОЬТаП&ТбП;НЇОQТ╠ПJТ╡НЇО╙ТНЇО[uНЇОrТ└П5Т┘П5НЇОeТМПBТННЇОЎТ╟ПJТ╠НЇОТ─П(Т│П>НЇОoТ┌ Т┐trПPНЇО хТ└П:Т┘П+НЇО Т■П;Т∙П)НЇО yТ▀trПKЪХЇ 2>Г]ыsKernedStrikes (revised version)3origins and width vectors, it must be the case that all of the black bits of the character lie betweenthese two bounds. No character may include bits to the left of its origin (left-kerning) or the rightof the end of its width vector (right-kerning).A KernedStrike file handles kerned characters, and does so in the following way: the individualrasters are put into the strike by their bounding box widths. Just think about taking the boundingboxes of all of the characters, lining up their baselines, and packing them tightly into one longraster array; in this format, there are no blank columns between characters in the strike. AKernedStrike file has three additional tables, indexed by character code. One gives the position inthe strike of the first column of the character's raster, which is also the leftmost column of itsbounding box. The other two tables consist of small integers that specify the left-to-right locationof the origin with respect to the bounding box, and the length of the width vector. A StrikeIndex is essentially a table that maps character codes into pairs, together withthe associated strikes. An index can be used to achieve sharing if several character codes map tothe same pair, and hence refer to the same raster. Or it can help to save space, bygrouping the rasters into several strikes to save top and bottom scanlines. [By the way, to the bestof my knowledge, no one has ever used StrikeIndex format.]PlainStrike and KernedStrike files have the following format:structure PlainStrike: [ @StrikeHeader// header common to all Strike files @StrikeBody// the actual strike ]structure KernedStrike: [ @StrikeHeader// header common to all Strike files @BoundingBoxBlock// dimensions of the font bounding box @StrikeBody// the actual strike @WidthBody// table of width data ]structure StrikeHeader: [ format word = [ oneBit bit// always =1, meaning new style'' index bit// =1 means StrikeIndex, =0 otherwise fixed bit// =1 if all characters have same value of Wx, else =0 kerned bit// =1 if KernedStrike, =0 if PlainStrike blank bit 12 ] min word// mimimum character code max word// maximum character code maxwidth word// maximum spacing width of any character = max{Wx} ]structure BoundingBoxBlock: [ FBBox// as defined above FBBoy// as defined aboveЪНЇОfЯuТ rНGОuНЇОbrТ▒П.Т▓П8НЇО`vТ░Т▒П]НЇО^оТП/НЇО[─Т╘П2Т╙П.НЇОYыТ▓П(Т⌠П;НЇОX2Т╩ПFТ╪НЇОV┼ТмП1ТнП-НЇОTЦТ■ПIТ∙НЇОS<ТаТбПKНЇОQ■Т°П#Т²ПBНЇОOМТПTНЇОL·Т┤ПLТ┬НЇОJВТ╒П[ТёНЇОIPТ Т⌡ПLНЇОG╗Т⌠П1Т■П4НЇОFТП:НЇОB╡П=НЇО?dТXНЇО=╪НЇО<Н?П$НЇО:n Н?НЇО8фНЇО5xНЇО3пНЇО2)Н?П$НЇО0┌Н?П&НЇО.з Н?НЇО-3Н?НЇО+▄НЇО(=НЇО&√НЇО$ННЇО#GНШНЇО!═НШ Н?П#НЇОЬНШН?П&НЇОQНШН?П6НЇО╙НШ Н?П(НЇОНШНЇО[НШНЇОЄ Н?НЇО Н?НЇОeН?П3НЇОЎНЇОoНЇО хНЇО Н?НЇО yН? lЇ 2=Г]ы)KernedStrikes (revised version)4 FBBdx// as defined above FBBdy// as defined above ]structure StrikeBody: [ length word// total number of words in the StrikeBody ascent word// number of scan-lines above the baseline, which is// normally max{BBdy+BBoy} over the chars in this strike descent word// number of scan-lines below the baseline, which is// normally max{(BBoy)} over the chars in this strike xoffset word// always =0 [used to be used for padding schemes] raster word// number of words per scan-line in the strike bitmap word raster*height// the bit map, where height=ascent+descent=FBBdy xinsegment ^ min, max+2 word// pointers into the strike, indexed by code ]structure WidthBody: [ widthtable ^ min, max+1 @WidthEntry// spacing information, indexed by code ]structure WidthEntry: [ spacing word =// the entire spacing word will be =(1) (both bytes =377b)// to flag a non-existent character, else the bytes are:[offset byte// =BBoxFBBoxwidth byte// =Wx] ]The bitmap'' entry is one large bit map; there are height=ascent+descent scanlines in thebitmap, each of which is raster words long. Unless something funny is going on, ascent will besimply FBBdy+FBBoy, while descent will be simply (FBBoy).The font includes characters for some of the ASCII codes from min through max inclusive. Thebitmap includes a dummy character associated with the charcter code (max+1), which can bedisplayed for any non-existent character. A PlainStrike works as follows: Given a character code c, in the range [min, max], we firstcompute:xLeft _ xinsegment ^ c;xRight _ xinsegment ^ (c+1);.If xLeft=xRight, then c is a non-existent character in the current font, and should be replaced bythe raster with code (max+1). Otherwise, the columns of the bitmap from xLeft through(xRight1) inclusive contain the raster for character c, and the width of charcter c isWx=(xRightxLeft).A KernedStrike works a little differently. We first compute xLeft and xRight as above, and alsocomputeSpacing _ WidthTable ^ c;.If Spacing=(1), then c is a non-existent character in the current font, and should be replaced byНЇОfЯuТ rНGОuНЇОbrТXН?НЇО`vН?НЇО^оНЇО[─НЇОYыНЇОX2 Н$┐П*НЇОV┼ Н$┐П4Н$┐ОTЦП:НЇОS<Н$┐П4Н$┐ОQ■П8НЇОOМН$┐П3НЇОNF Н$┐П.НЇОL·Н$┐П1НЇОJВН$┐П,НЇОIPНЇОFНЇОDZНЇОB╡П&Н,гП'НЇОAНЇО=╪НЇО<НЇО:nН?П<Н?О8фП8НШО7НШО5x Н$┐ НШО3п Н$┐НШО2)НЇО0┌НЇО+▄ТзП\НЇО)ДТ╞Т╟П@НЇО(=ТП:НЇО$НТ╔П=ТіНЇО#GТсПVТтНЇО!═ТП+НЇОQТуТжПFНЇО╙НШОТНШО[НЇОЄТ ПHТ⌡НЇОТЬТЫП9НЇОeТ,П8Т-НЇОЎНЇОoТ╔ ТіПRНЇО хНШО ТНЇО yТ▓П_Т⌠ЪfЇ 2=Г]ыKernedStrikes (revised version)5the dummy character at (max+1). Otherwise, the columns of the bitmap from xLeft through(xRight1) constitute the bounding box of the raster of character c. In this case, we decomposethe Spacing value into its two bytes:Offset _ Spacing< pairs, dummy at max+1 bodies ^ 1, nStrikeBodies @StrikeBody// the strike bodies themselves ]structure KernedStrikeIndex: [ @StrikeHeader// common header @BoundingBoxBlock// bounding box data for the entire font maxascent word// maximum ascent of all the strikes// [probably =FBBdy+FBBoy] maxdescent word// maximum descent of all the strikes// [probably =(FBBoy)] nStrikeBodies word// the number of strike bodies map ^ min,max+1 @mapEntry// table of pairs, dummy at max+1 bodies ^ 1, nStrikeBodies @StrikeBody// the strike bodies themselves @WidthBody// table of width data ]structure mapEntry:ЪНЇОfЯuТ rНGОuНЇОbrТлТмП9НЇО`vТєП)Т╔П7НЇО^оТП%НШО](П$НШО[─П#НЇОYыТ┘П<Т├П&НЇОX2Т═П1Т║П-НЇОV┼ТЛТМП=НЇОTЦТ▌П8Т▐П#НЇОS<ТґПPТў НЇОQ■Т└ПIТ┘НЇОOМТїТ╗ПFНЇОNFТП4НЇОJВТ■ПNТ∙НЇОIPТ▀Т▄ПIНЇОG╗Т┬П+Т┴П<НЇОFТ∙П9Т√П+НЇОDZТ┬П"Т┴ПBНЇОB╡Т╠П7Т╡П)НЇОAТ╒ТёПPНЇО?dТ▐ Т░ПPНЇО=╪Т╧Т╨ПIНЇО:nТ┤ПYТ┬НЇО8фТНЇО5xТXНЇО3пНЇО2)Н$┐НЇО0┌Н$┐П$Н,гО.зНЇО-3Н$┐П%Н,гО+▄НЇО)ДН$┐НЇО(=Н$┐П0НЇО&√П(Н$┐НЇО$ННЇО!═НЇОЬНЇОQН$┐НЇО╙Н$┐П(НЇОН$┐П$Н,гО[НЇОЄН$┐П%Н,гОНЇОeН$┐НЇОЎН$┐П0НЇОП(Н$┐НЇОoН$┐НЇО хНЇО yЪ╪Ї 2?Г]ы:KernedStrikes (revised version)6 [ missing bit 1// =1 if character is non-existent, else =0 strike bit 7//which strike in range [0:127] code byte// which code ]In a StrikeIndex font, all of the StrikeBodies have implicit min values of zero; the max value isunimportant, as the map will never generate a reference outside the range. The individualStrikeBodies do not have separate pictures for illegal characters; instead, the (max+1) entry in theglobal map defines a single dummy picture. Non-existent characters in the range [min, max] areindicated in the global map by a mapEntry that specifies a strike number larger than 127=177b,that is, by the sign bit of the map entry being 1. In KernedStrikeIndex fonts, non-existentcharacters will also be indicated by having a WidthEntry of (1).In StrikeIndex fonts, the ascent and descent words in each StrikeBody give the dimensions of thatparticular StrikeBody; thus, they probably are the y dimensions of the bounding box of thosecharacters that are included in that StrikeBody, rather than of the entire font. BitBlt modes:There are evidently lots of programs in the world that paint charcters on the screen by calling BitBltin Replace mode, in which the new bits simply smash whatever used to be at the destination. Ifyou want to handle characters that kern, you simply can't do this! The bounding boxes ofsuccessive characers may actually overlap, and hence a Replace Blt might overwrite valuable bits. Ifyou want kerning specified in a KernedStrike font to work, you must use one of the other BitBltmodes: Paint, Erase, or Invert. Conversion issues:I propose the following plan. In the near future, some combination of Doug Wyatt and myself willmodify PrePress 1.12 to produce a PrePress 1.13. This new PrePress will include a MakeKScommand, that converts a font from .AC format to .KS format, and a ReadKS command, thatconverts in the opposite direction. The MakeStrike command will remain, to convert from .ACformat to the original Strike format. However, the Kerned flag will be replaced by a new flagcalled Clipped'. And the code that implements the MakeStrike command will be altered to treatoverhanging characters as follows. If any character of the .AC font kerns to the left, the MakeStrikecommand will fail, as it does currently. Characters will be allowed to kern to the right. If theClipped flag is true, the portion of the bounding box that overhangs the end of the width vectorwill be ignored. If the Clipped flag is false, the width of any right-kerned characters will beartificially increased just enough to eliminate the overhang. Thus, calling MakeStrike on a font withright kerning will have one of two effects: if Clipped is true, the resulting Strike font will spacecorrectly but the overhanging portions of characters won't print. If Clipped is false, theoverhanging portions will print, but the characters will be spaced too far apart. Neither of thesetwo possibilities is very pleasant, of course; but if you want kerned characters to work, you shoulduse .KS format.Note that the xoffset word of all StrikeBodies produced under the new rules will always be zero, nomatter what file format is involved. Non-zero values of xoffset were originally reserved forhandling kerning by padding schemes; since padding is now handled by the auxiliary tableapproach, the xoffset word is not needed.PrePress 1.13 will also include new code to handle the exotic face byte values that are beingintroduced as part of the upcoming font cataclysm.НЇОfЯuТ rНGОuНЇОbrТXНЇО`vН?П,НЇО^оН?НЇО](Н?НЇО[─НЇОX2Т╔ТіПRНЇОV┼ТОПCТПНЇОTЦТ█Т▌ПRНЇОS<Т╘П+Т╙П4НЇОQ■Т╘Т╙ПCНЇОOМТъТЮПDНЇОNFТПAНЇОJВТ⌡Т°ПHНЇОIPТаПPТбНЇОG╗ТПSНЇОDZuНЇОArТ┌ПFТ┐НЇО?dТ ПEТ⌡НЇО=╪ТЮП9ТАНЇО<Т┐П.Т└П7НЇО:nТ╒П1ТёП.НЇО8фТП!НЇО5xuНЇО2)rТ┤П*Т┬П7НЇО0┌ТвПCТьНЇО.зТаПRТбНЇО-3ТЇП(Т╦П4НЇО+▄ТЇТ╦ПUНЇО)ДТ║П_НЇО(=Т│ПQТ┌НЇО&√Т╠П9Т╡П)НЇО$НТ╔ПHТіНЇО#GТкП(ТлП8НЇО!═Т│П>Т┌П(НЇОЬТєП"Т╔ПCНЇОQТ ТПNНЇО╙Т╗П8Т╘П+НЇОТ▌ПeНЇО[ТНЇОТ├ПcНЇОeТвТьПDНЇОЎТБП%ТЦП4НЇОТП)НЇО хТсП6ТтП'НЇО ТП2Ъ эЇы=Г\2IKernedStrikes (revised version)7Once PrePress 1.13 is up and running, we will take all of the .AL fonts on [Ivy] andproduce a .KS version for each of them, sticking all of those fonts on [Ivy] as well.That should give us plenty of KernedStrike fonts to play with, as people start to produce softwarethat uses the new format. ЪНЇОfЯuТ rНGОuНЇОbrТ╗П%Т╘П:НЇО`vТЇТ╦ПSНЇО^оТ≥П3Т П/НЇО](ТНЇОYыНЇОV┼`ЇVC>Гх9 TIMESROMAN TIMESROMAN TIMESROMAN LOGO TIMESROMAN TIMESROMAN г █вЗ!ф) Ї2г4ЪЪj/75∙&6▄ЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪkernedStrikes.bravo Ramshaw, LyleApril 17, 1980 1:58 PM