Compiling glyphs into instructions for imaging for execution on a general purpose computer

[0002] This is a continuation of application of Ser. No. 07/662,788 filed Feb. 28, 1991, now abandoned.

[0003] This invention relates to text processing methods and text processor apparatus forming an imaging system for generating, storing, displaying, drawing, printing and otherwise imaging text, symbols, icons, and other patterns, all generically known as “glyphs”.

[0004] A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.

[0005] Text processors are well-known in the field of computers and data processors for imaging characters in fonts of different typefaces and sizes. Text processors typically define text characters with a generic definition in a character table, for example, an ASCII table, which is independent of typeface or size. The term “typeface” refers to the general appearance and design of characters and the term “font” refers to a complete set of characters having the same typeface, that is, the same general appearance and design.

[0006] Computers and data processors that use text processors are image systems that output the processed text in human readable form. The image systems typically include computer display screens for electronic output or printers for paper output. In such image systems, each character is drawn by a number of pixels (dots) that are located and addressed by an X-axis coordinate and a Y-axis coordinate defined relative to an XY-axes system where an X-axis and an orthogonal Y-axis form a matrix of addressable pixels. Each pixel is drawn by determining the X-axis and Y-axis coordinates for the pixel and each character is drawn by determining the X-axis and Y-axis coordinates for all the pixels that are used to draw the character. The XY-axes system can have any arbitrary rotation. Typically for printers, the X-axis is across the page so that the Y-axis is down the page as read by a human viewer.

[0007] For text processors, characters are typically defined along the X-axis by a character line where many character lines for text define a page of text. Each character typically is formed with pixels from many pixel lines so that depending upon the font parameters, characters can have different shapes and sizes depending upon the pixels selected for a character both in the X-axis and Y-axis directions. For convenience, some X-axis pixel line near the bottom of a line of characters is defined as the baseline of a character line. Text processors operate to define characters along character lines and use font parameters to actually determine the pixels to be drawn for each character appearing in the character line.

[0008] A pixel map is a two-dimensional array of pixels. A pixel is a data structure which can be changed in value (black or white, shades of color, size, brightness and so on) that have physical significance. A pixel is represented by one or more data bits or bytes. A rectangular array pixel map defines each pixel in the array by a set of orthogonal X-axis and Y-axis addresses. Similarly, run-length encoding and other coding methods also define pixels relative to a pixel map.

[0009] While the term “character” is often used to identify unique shapes representable by a pixel map, the term “character” is sometimes limited in meaning to a family of shapes such as an alphabet or a font. In the present specification, however, the term “character” refers to any shape (generically referred to as a “glyph”) identifiable by a pixel map. A glyph may or may not be associated with a set of similar shapes, such as an alphabet or a font. In the present specification, the term “character” is used interchangeably with the term “glyph” and term “glyph” means any pattern (including symbols, icons or other shapes) representable by a pixel map.

[0010] Text processing methods for imaging characters (glyphs) fall into a number of different categories as follows.

[0011] A first text processing category performs block transfers (BLTs or blits) of arbitrary data where all code is pre-compiled. This category is the most common method of drawing text via block transfer. Examples of this category are Macintosh QuickDraw DrawText and other general purpose text display systems. Other examples which also fall into this category includes methods that image characters from other representations, such as outlines.

[0012] A second text processing category draws characters which, prior to run time, have been compiled manually by humans without use of computational aids specific to text. One example of this category is the Apple II computer executing programs which display large block text on the screen using low-resolution (40×48) graphics. Each character in the alphabet is described by a character subroutine typically written in BASIC. Words, formed as a combination of characters, are displayed on a screen by executing a combination of character subroutines, one subroutine for each character in the word. Each character subroutine is manually written, by a human programmer, using high level drawing primitives (such as plot points, display vertical lines, and display horizontal lines). Such character subroutines, being manually written for each character, do not permit automatic creation of characters. Furthermore, such manual character subroutines do not translate into code within the instruction set acceptable by the display device and hence directly interfacing with the display device.

[0013] A third text processing category compiles a segment of code to perform a data-independent BLT operation for arbitrary pixels in an array without reference to the character content of the data in the array. This method is known as a “compiled BLT”. One example of this category is an AT&T terminal in which block-transfers (BLT or blit) of arbitrary bits or pixels are achieved by first compiling the code for doing a specific instance of a blit (moving, shifting, advancing, clipping, boolean transfer mode, etc.) and then executing the code. This method, however, moves an arbitrary rectangular array of pixels from one place to another place and does not compile text characters into executable code.

[0014] A fourth text processing category compiles a segment of code to perform a data-independent BLT of some constant, such as a solid color. This fourth text processing category is a species of the compiled BLT third category and is known as “compiled fill”. The code for a compiled fill can be readily optimized since only a simple, constant pattern is imaged.

[0015] In accordance with the above background, many techniques for processing pixels are known, but a need exists for improved methods and apparatus for compiling characters into machine code for display in practical imaging systems.

[0016] The present invention is a method and apparatus for receiving glyph data, specifying glyphs according to a pixel map, and for automatically compiling the glyph data to form compiled glyph code for imaging the specified glyphs in an imaging system. The compiled glyph code uses instructions from the instruction set of the imaging system and hence the compiled glyph code directly interfaces with display devices in the imaging system to image the glyphs.

[0017] The method of the present invention compiles a segment of code to perform a data-dependent imaging of the glyph data. The compiled code varies as function of the glyph data.

[0018] In the method of the present invention, glyph data includes one or more input data bits and the instruction set includes imaging instructions. To compile the input glyph data, the input data bits are compiled to one or more imaging instructions.

[0019] In one embodiment of the invention, compiled glyph code functions to speed-up imaging by text processors in an imaging system. In that embodiment, processing control is typically resident with the text processor. The text processor calls the imaging code in which two imaging threads are employed, namely, a foreground thread and a background thread. The foreground thread receives display requests and images the glyphs and the background thread compiles glyphs as needed. If particular glyphs to be imaged have not been compiled, the foreground thread marks the uncompiled glyphs needing to be compiled and schedules time for the background thread to compile the uncompiled glyphs. In this double-threaded embodiment, no significant speed loss is encountered since glyph compiling is a background task.

[0020] In another embodiment of the invention, a single-thread imaging sequence is employed. The single-thread imaging sequence receives a display request to image glyphs and compiles any uncompiled glyphs as needed. If particular glyphs to be imaged have not been compiled, the single-thread sequence compiles the uncompiled glyphs. In the single-thread embodiment, glyph compiling delays are experienced whenever an uncompiled glyph is encountered.

[0021] In the present invention, the compiled code generation is data-dependent since the compiled glyph code is a function of the input glyph data. Specifically, the compiled glyph code varies as function of variations in the input glyph data, that is, different glyphs defined by the glyph data are compiled to correspondingly different compiled glyph code such that the compiled glyph code can be executed to image the glyphs.

[0022] In accordance with the above summary, an improved text processor is provided in which compiled glyph data accelerates the imaging of glyphs.

[0023] Other objects, features, and advantages of the present invention will become more apparent in the light of the following detailed description thereof, as illustrated in the drawings.

[0024] FIG. 1 depicts a block diagram representation of an image system having a text processor using compiled glyphs in accordance with the present invention.

[0025] FIG. 2 depicts an XY-axes coordinate display for lines of characters for pages where the pixels for characters are represented by a bitmap.

[0026] FIG. 3 depicts an XY-axes coordinate display for lines of characters for pages where the pixels for characters are represented by a block array.

[0027] FIG. 4 depicts an XY-axes coordinate display for lines of characters for pages where the pixels for characters are represented by a planar array.

[0028] FIG. 5 depicts a block-diagram representation of a single-thread method for drawing compiled glyphs.

[0029] FIG. 6 and FIG. 7 depict a block-diagram representation of a double-thread method for drawing compiled glyph.

[0030] FIG. 8 depicts a pixel map for a letter “S”.

[0031] FIG. 9 depict a pixel map for a letter “T”.

[0032] FIG. 10 depicts a pixel map for a character “1”.

[0033] FIG. 11 depict a pixel map for a character “P”.

[0034] FIG. 12 depicts a schematic representation of a code folding example.

[0035] FIG. 13 depicts a flow diagram of the 1/2/4 algorithm.

[0036] FIG. 14 depicts a flow diagram of a first pass of the 1/2/4 algorithm.

[0037] FIG. 15 depicts a flow diagram of a second pass of the 1/2/4 algorithm.

[0038] FIG. 16 depicts a graph of a timing comparison depicting the uncompiled versus compiled execution times.

[0039] FIG. 17 depicts a graph representing a percent improvement of compiled text processing.

[0040] Overall Image System-FIG. 1

[0041] FIG. 1 depicts a block diagram representation of a image system 10 in accordance with the present invention. Typically, the system 10 is a conventional computer system having a processor (CPU) 11, a memory 12, a keyboard 15, a display 14, and a printer 20 and I/O devices 21. The display 14 and printer 20 display images of glyphs in human readable form. The I/O devices 21 can include plotters or other devices which output images of glyphs in human-readable form.

[0042] In the FIG. 1 system, application computer programs 18 are stored in the memory 12 and are executed in the processor 11 under control of a software operating system 17 also stored in memory 12. The general operation of such computer systems is well known.

[0043] Application programs 18 executable by the system 10 image glyphs Application programs together with the operating system and apparatus of FIG. 1 form an image system in accordance with the present invention. Text processor programs are examples of the application program 18 of FIG. 1.

[0044] A text processor program performs a text processor method in the apparatus of FIG. 1 to image glyphs in the memory 12. From the memory 12, the imaged glyphs are displayed by display 14 or printed by printer 20. The system of FIG. 1 operates by addressing pixels in an XY-axes coordinate system where, each pixel (dot) is located and addressed by an X-axis coordinate and a Y-axis coordinate defined relative to orthogonal X and Y axes which form an array of addressable pixels. A pixel is drawn by determining the X-axis and Y-axis coordinates for the pixel and a line of characters is drawn by determining the X-axis and Y-axis coordinates for all the pixels on the line that are used to define the characters.

[0045] A preferred embodiment of the invention employs a computer program, as provided hereinafter as TABLE 1 for example, executing in a general purpose computer of FIG. 1. While a preferred embodiment of the invention employs a computer program, a special putting engine 16 is also within the scope of the present invention.

[0046] Coordinate System—FIG. 2

[0047] In FIG. 2, an XY-axes coordinate system for drawing lines of text-processor characters 3 is shown. For convenience, the X-axis is aligned horizontally across the short length of a page 4 and the Y-axis is aligned vertically along the long length of the page 4. The XY-axes coordinate system of FIG. 2 is typical of the coordinate system used for output images from text processors employed in image systems of the FIG. 1 type.

[0048] The output images from the FIG. 1 image systems are processed text in human readable form. In FIG. 2, as an example, two lines of text characters “1 2 3 4 5” and “6 7 8 9 0” are drawn along character lines 2 parallel to the X-axis.

[0049] Each character associated with character line 2 in the output image is drawn by a number of pixels (dots) where each pixel is located and addressed by an X-axis pixel row coordinate and a Y-axis pixel column coordinate defined relative to the XY-axes system.

[0050] Each pixel is drawn by determining the X-axis pixel row and Y-axis pixel column coordinates for the pixel and each character is drawn by determining the X-axis and Y-axis coordinates for all the pixels that are used to draw the character. In FIG. 2, for example, the character “1” drawn with many pixels that occur in horizontal pixel rows and vertical pixel columns.

[0051] A pixel map is formed of rectangular arrays of pixels where each pixel can be set independently to one of two or more colors. The number of available colors is generally a power of two and is expressed as a series of data bits. In an embodiment having one bit per pixel and two colors (black and white), then each data bit for a pixel is, for example, a logical 0 (white) or 1 (black). In an embodiment having more than one bit per pixel and more than two colors, then each pixel is represented by a group of data bits.

[0052] Data bits arranged in groups form data bytes where a byte is typically eight bits, but any number of bits per byte is possible. In the embodiments described, eight bits per byte is assumed. In embodiments having one bit per pixel, then the array that represents how data bytes, usually in computer memory, are mapped to pixels on a display device is called a bitmap as represented in FIG. 2.

[0053] If more than one bit per pixel are present, then there are two common arrays, block arrays and planar arrays as represented in FIG. 3 and FIG. 4, respectively, that represent how data bytes are mapped to pixels on a display device. In the block array of FIG. 3, all bits for one particular pixel occupy the same byte, or occupy consecutive bytes if there are more than eight bits per pixel. In the planar array of FIG. 4, each 8-bit byte, for example, in one plane always represents exactly eight pixels, and additional bytes in additional planes each contributes one bit for a given pixel.

[0054] A hybrid array, called a block-planar array, is used when there are more than eight bits per pixel. In this embodiment, one byte is used per pixel, as in the block array, but several planes (usually three for red, green and blue) are used to describe one pixel.

[0055] Each byte has memory location defined by an address so that the byte can be accessed for reading or writing, like other memory locations in the data memory of the system. Some systems are able to access bytes at consecutive addresses in groups, typically two or four bytes at a time. There may or may not be bit or byte or other alignment restrictions imposed by the system architecture. Typically, groups of two or more bytes must be accessed with the lower-ordered address bits being even. Since each pixel typically corresponds to a byte in memory at an address location, it is common practice to refer to those corresponding addresses as the addresses of pixels. With such a practice, in order to completely specify the location, both memory byte addresses and memory bit addresses (or the addresses for groups of bits) must be specified.

[0056] For rectangular pixel-maps, some systems provide a fixed number of bytes per row of pixels, known as RowBytes. Adding RowBytes to the address of any pixel points to the pixel directly below it, if it exists. Likewise, subtracting RowBytes from the address of a pixel will point to the pixel above. For systems that do not have a fixed number of bytes per row of pixels, an alternative formula (other than simple addition or subtraction) is provided. Alternatively, row addresses can be computed by using a lookup table. Such complications require more complicated code.

[0057] In planar arrays, each plane has the same number of bits and occupies the same amount of memory. Like RowBytes, there is a similar constant, a PlaneByt, which is added to the address of a pixel to obtain the address of the same pixel on the adjacent plane in one direction. If a PlaneByte is subtracted, the address of pixel on the adjacent plane in the opposite direction is obtained.

[0058] For purposes of the present explanation, the exact color, or shade of monochrome color produced by a given numeric value for a pixel, is not considered although for convenience a foreground color is represented by all 0's or all 1's. This foreground color is usually either the darkest or the lightest color possible on the given display device. The background color usually, but not necessarily, has the opposite bit pattern and color as the foreground color. For the purposes of the present explanation, irrespective of the number of bits per pixel, the foreground color is black, represented by all 1's, and the background color is white, represented by all 0's.

[0059] For purposes of the present explanation, the ordering of bits in bytes in the system, big endian or little endia, is not important, that is, whether the left-most bit has the highest or lowest numeric value is not important. In general, the numeric significance of most of the bits in patterns are not of interest. For ease of illustration, however, bits are assumed to be specified in the order in which they are displayed.

[0060] Numeric constants are specified in hexadecimal if they are preceded by a “$”, thus, by the conventions specified above, a one bit per pixel device, which holds a constant $C6 (binary 11000110) will display (from left to right) two black pixels, followed by three white pixels, followed by two black pixels, followed by a single white pixel.

[0061] Flowcharts FIG. 5 through FIG. 7

[0062] In FIG. 5, the flowchart for a text processor using a Single-thread glyph compiler is shown.

[0063] Entry

[0064] The algorithm, as specified, is designed to image text, in a homogeneous font, one line at a time. The exact parameters for entry are not specified and will vary from implementation to implementation depending on the requirements of the system within which it is running. It is possible to think of a text primitive which deals with more than one line, or with text which is not necessarily arranged on a line. These are system-specific details which have little bearing on the basic algorithm. For the sake of clarity in the description, the list of characters to be imaged in one execution of this algorithm is referred to as a character line.

[0065] Establish Graphics Environment

[0066] This is the initial entry into the text imaging code. This routine looks at the input parameters and the current graphics context and determines basic information about where and how the text is to be drawn. Important information which is needed includes:

[0067] The device(s) to which the text be imaged.

[0068] The bit depth (number of colors or number of bits per pixel) of each device.

[0069] the color in which the text will be imaged.

[0070] Other implementation-specific details.

[0071] Conditions Favorable

[0072] If the text imaging system is the only available implementation, then the answer here is always “Yes”, since the text must be imaged. If the imaging system is a supplement to an existing imaging system, then depending on information determined above, the compiled text imaging system may delegate drawing of an image to another text imaging system. For example, one embodiment only deals with text of a particular point size or smaller. If the font is larger, the implementation delegates imaging to another system.

[0073] Delegate Control to Underlying Text Mechanism

[0074] This routine is where control is given to a slower, but more general, text display mechanism if, for any reason, the compiled glyph system is unable to image the text. This routine is required for the two-threaded sequence, although the single-threaded sequence can be implemented as the sole text imaging sequence where delegation is impossible.

[0075] Get Font

[0076] Given the parameters of the current graphics context, return a data structure representing the desired text font. This structure will be determined by the following factors:

[0077] Text font

[0078] Text size, including any magnification or other geometric transformations

[0079] Text style—algorithmically applied style such as bolding which affects the appearance of the character glyphs

[0080] Depth (number of available colors or shades) of the output device

[0081] Any other system-specific factors.

[0082] The returned structure (hereafter referred to simply as the “font”) contains an array of font entries, one for each character in the font. Each entry may or may not be completely filled in. It is the job of the compilation routine to fill in each font entry, a character at a time.

[0083] “Get Font” also introduces the concept of a font cache. It is assumed that there will be many “Get Font” requests, and that many requests will be for the same font. If such is the case, then the same font structure should be returned each time. Several such fonts are generally kept in primary memory storage (RAM) at a time. The exact policies on how, and for how long, fonts are stored in the cache is system-specific. It should be noted that the current implementation maintains both a RAM font cache and a disk cache. As the RAM cache is filled up, excess fonts are written to disk if not already there. If a new font is requested, the disk cache is consulted before a new, empty font structure is created.

[0084] Allocate Display List

[0085] The display list is an array with as many fixed size entries as there are characters to be imaged in the current character line width perhaps a fixed number of extra entries for prologue and/or epilogue code. (The current implementation adds one entry for epilogue code, but requires no prologue.) The display list describes the program to be executed when text is drawn as a series of subroutine calls into the individual routines which will image the text. This is interspersed with the addresses of where the text will be drawn. (The current implementation uses the stack at the display list. Each entry is eight bytes long; four bytes for the routine address and four for the destination address. Each routine pops the destination address of the stack, images the character, and then execute a a “Return From Subroutine” instruction which automatically branches to either the next character routine, or the epilogue code once all characters have been imaged.)

[0086] For Each Character In Text Line . . .

[0087] This is the loop which fills in the display list, and the only place where the original characters are actually scanned.

[0088] Is Character Compiled?

[0089] The loop checks whether the entry for each individual character has been filled in for the font. If not, this is where the one and two threaded algorithms diverge. The single threaded algorithm will actually compile the character. The two threaded algorithm will only schedule the character to be compiled.

[0090] Compile Character

[0091] This is the main compilation routine. It will be described in much more detail later.

[0092] Mark this and Other Characters as Needing Compilation (Two Threaded algorithm Only.)

[0093] Once the first character in a line is found which needs compilation, the main display list building loop is exited and the compiled display process is essentially aborted. A secondary loop is entered which marks this and any remaining characters on the line who's entries have not been filled in as being requested for compilation. It is up to the background thread to fulfill these requests.

[0094] Schedule Background Thread (Two Threaded Algorithm Only.)

[0095] If not already done so, the operating system is informed that the background thread is to be executed as a low priority (background) process.

[0096] Delegate Control to Underlying Text Mechanism (Two Threaded Algorithm Only)

[0097] In the two threaded algorithm, the foreground thread never compiles characters, but rather delegates to the underlying text renderer only after scheduling background time so that the same characters will already be compiled in a future request.

[0098] Place Routine and Destination Addresses in Display List

[0099] This step in the main scanning loop is in charge of converting the exact character position into a destination address and determining the routine to be used to render the character. Depending on the implementation, other steps within the same loop may also have to determine the character's advance width so as to update the current pen position. Other implementations may already provide a list of explicit character positions in which to place the characters. In either case, this loop must also determine a bounding rectangle for all characters to be imaged. This will be used later in the clipping section.

[0100] Last Character?

[0101] The scanning loop is executed for each character. This loop should be the most highly optimized part of the algorithm in terms of execution speed, and should preferable be written in the assembly language of the implementation architecture, as this is usually the most often executed part of the code, with the exception of the compiled text routines themselves (as a group) and perhaps the clipped blit code.

[0102] Text Clipped?

[0103] At this point, a decision is made as to whether the text can be imaged directly or must be imaged first to a temporary canvas which is then partially copied to the destination device. All clipping calculations are done here, with the bounding box of the text to be imaged as an essential ingredient. This step may also wish to split up the line into sections with characters which can be imaged directly, those which are partially clipped and must use a temporary canvas, and those which are completely obscured and will not be imaged at all. Compiled routines may also image only in one preferred transfer mode even though the text drawing primitive can display in several transfer modes. If the usual transfer mode is not used, then the temporary canvas may still be needed even if the text is not clipped. The blit step below is thus used for transfer mode conversion, clipping, or both.

[0104] Allocate Temporary Canvas

[0105] The size of the temporary canvas will vary from execution to execution, and may be rather large so it should be implemented as a dynamically sized buffer which can be reclaimed when not in use.

[0106] Point Display List at Temporary Canvas

[0107] The display list, as created above, is set up to image the text directly to the output device. This step modifies the display list to point to the temporary canvas instead. (In the current implementation, this is done by adding an offset to each destination entry in the display list, leaving the routine entries unchanged.)

[0108] Set Up Execution Environment

[0109] The processor state is set up to conform to assumptions made by the compiler about the environment in which compiled code will be executing. This may include, but is not limited to, filling in prologue and/or epilogue routines in the display list, setting up processor registers with certain constants, ensuring that the output device is accessible, and temporarily erasing the mouse cursor if it would interfere with the text being drawn.

[0110] Execute Display List

[0111] This is where the text is actually drawn, either to the output device or to the temporary canvas.

[0112] Text Clipped?

[0113] A second branch is made depending on whether the direct or temporary canvas cases are being uged. This step should also restore any special processor states changed in the “Set up execution environment” step above to the way they are needed for regular program execution.

[0114] Blit Temporary Canvas To Destination

[0115] Here, a general purpose blit algorithm is used to image text which, because of either clipping or transfer modes, cannot be imaged directly.

[0116] Deallocate Temporary Canvas

[0117] The temporary canvas should be reclaimed to the free store or perhaps kept for later use depending on operating system overhead.

[0118] Deallocate Display List

[0119] Like the temporary canvas, the variable length display list should also be deallocated. (Since the current implementation places the display list on the execution stack, it literally dislocates it as the code is being executed, so the step is automatic.)

[0120] Done

[0121] Clean up and return to the caller. The job is finished.

[0122] Background Thread FIG. 5

[0123] In FIG. 5 and FIG. 6, the flowchart for a text processor using a double-thread glyph compiler is shown. In FIG. 5, the foreground thread steps are like those of FIG. 4 except as noted in connection with the FIG. 4 description. In FIG. 5, the background thread steps are as follows.

[0124] Enter: Background Task

[0125] The background thread is executed only when it is scheduled by the foreground thread.

[0126] For Each Font in Cache . . .

[0127] The font cache is scanned for all fonts within it. (The current implementation only searches the primary (RAM) cache and does not scan the secondary (disk) cache.

[0128] Any Characters to Compile?

[0129] If there are no compilation requests for this font, then it is quickly skipped.

[0130] For Each Character in Font . . .

[0131] The font is scanned for characters which have not been compiled but which have been requested for compilation.

[0132] Character Requested for Compilation?

[0133] If not, the character is skipped. It is an error for a character to be both already compiled and requested for compilation.

[0134] Compile Character

[0135] This is the main compilation routine, the same which would have been called directly in the single threaded algorithm.

[0136] Time Up?

[0137] The flowchart describes an algorithm for a non-preemptive multitasking system. If the operating system is fully preemptive. With processes of varying priorities, then this and the next step are not necessary although control of concurrency would be required.

[0138] Yield Till Next Background Time

[0139] The background thread gives up control after a given amount of time, but is scheduled to regain control (at the start of the thread) when foreground processes have had time to execute. Note that more character compilation requests may have come in during the yield time, so the font cache must be scanned from the beginning.

[0140] Last Character in Font?

[0141] The next character is checked and perhaps compiled if there is still time remaining.

[0142] Last Font In Cache?

[0143] The next font in the cache is processed.

[0144] Sleep Till Rescheduled by Foreground Thread

[0145] If there are no more pending compilation requests, the background thread unschedules itself until it is again called by the foreground thread.

[0146] Variations on the High-level Algorithms

[0147] In addition to the single-thread and double-thread algorithms described above, there are many variations and simplifications of the algorithm which might be employed. Below is a list of typical variations.

[0148] Off-line compiler—In this case, all compilation is done beforehand and the compiler is only used as a separate tool for generating pre-compiled fonts. This may be quite practical if the number of required fonts is limited and known ahead of time. Indeed, the compiler need not be present in the delivered system. The end result, though, is still the same. The only difference is when the code is compiled.

[0149] No Display List—The code to position each character on the line, and the execution of the character can be done in the same loop without first creating a display list and then executing the characters within it. This is an architecture-dependent design decision and does not fundamentally affect the workings of either the compiler nor the executed code.

[0150] Clipping decisions—The depicted algorithms assume that the text bounding box is not known until the display list is created. If the bounding box it known ahead of time, or if clipping is not necessary, then the algorithm may be simplified in various ways. For example, if known ahead of time that the text will need to be imaged to a temporary canvas, there is no need for a “fix-up” phase before execution. This variation is quite dependent on the imaging system in which the compiled text routines are being put to use and, again, does not affect the compiler nor the generated code.

[0151] Font Cache changes—The internal workings of the font cache, if any, have not been described for purposes of clarity and conciseness. The requirements for a font cache, either in primary or secondary memory need to be considered on an implementation-by-implementation basis, and are quite removed from the workings of the compiler, although the size of the generated code may come into play in certain caching decisions.

[0152] Compilation Methods

[0153] The key part of the compiled text system is the compiler, which translates a source character into the code which is directly executable by the target machine. Several algorithms will be described, each of which handles a different type of display as described above. An algorithm for imaging on block devices with fewer than eight bits per pixel, and algorithm for block devices with eight or more bits per pixel, and an algorithm for planar devices, as well as an algorithm for block-planar devices will be described. (The current implementation only supports block devices with 1, 2, 4, 8, 16, and 32 bits per pixel, but the planar and block-planar algorithms are simple modifications on the schemes that will be presented.)

[0154] * * * *Basic Algorithm* * * *

[0155] All compilation algorithms have one thing in common. They take input in a common form. First of all, the text character, glyph, which is to be compiled must be made available. This can take one of several common forms, such as a pixel map, or a run-length encoded description. This may have been obtained directly from secondary memory (a bitmap, or run-length font file) or by a scaled font rendering engine which, in turn, gets its input from a font representation described in terms of straight lines and curves (an outline font)). In any case, the image of the compiled character is obtained in a suitable form on a temporary canvas. The compiler then scans this canvas and emits code which will image that character at any location on a given output device.

[0156] The preferred form of the image to be compiled is system specific. For example, the current implementation always obtains a bitmap, but for compilation at eight or more bits per pixel, this bitmap in converted into a run-length encoded form. Both forms have advantages depending on the nature of the generated code. In any case, it is assumed that the code will produce its output on some sort of pixel map. Although there are devices which can display data in vector or run-length form, only pixel map or raster output devices are of interest.

[0157] To describe the simplest case of compiled text, consider a block output device with eight bits (1 byte) per pixel. A small letter S as shown in FIG. 8.

[0158] The s character of FIG. 8 typically has glyph code and generates as indicated in the following TABLE 1:

[0159] The general form of the TABLE 1 code scans the character from bottom to top, and for each row, from left to right. There is an instruction for each pixel which is to be turned black. There is also an instruction to move up to the next row by subtracting RowBytes from address register R0 to obtain the address of the next higher row. Finally, the routine ends with a RETURN statement.

[0160] Specific Optimization

[0161] The general style of the compiled code to be generated has been described. The following features for optimization for compiled code are particularly useful:

[0162] Register data values

[0163] Loops

[0164] Index register control values

[0165] Literal data

[0166] Code folding

[0167] Peephole optimization

[0168] These optimizations have specific and unique application to compiled glyphs because they are used for various patterns which occur regularly in text.

[0169] Register Data Values

[0170] The code generated to image the “s” in FIG. 8 can be improved in several ways. The constant #Black may limit the routine's usefulness to only display text in one color. If the value for the desired color is loaded into a register ahead of time, then text in any desired color can be drawn using the same routine. If the processor includes a MOVE MULTIPLE instruction, then neighboring pixels on rows 1, 4 and 7 can be drawn with a single instruction. Lines 2-3, 10-11, and 18-19 can be combined into three instances of a single instruction. This assumes that registers R1 and R2 have been preloaded with the desired color constant, such as BLACK.

[0171] 21 Move Multiple R1-R2, 1(R0) Draw both pixels in row

[0172] The first use of data values in data registers stores constants which are transferred to the output device. Horizontal runs of consecutive pixels can be operated upon by a MOVE MULTIPLE instruction, if all bits in the bytes which are addressed are to be affected. This makes the MOVE MULTIPLE technique most effective when working at eight bits per pixel or greater. As described, below, data registers can be used effectively with the AND and OR instructions at lower bit depths.

[0173] Loops

[0174] Consider a new example, a “T” as shown in FIG. 9.

[0175] A compiler can generate the following code of TABLE 2 using the data register optimization described above:

[0176] Notice that the block of code in lines 24-35 of TABLE 2 is repetitive. Each pair of instructions is the same because the T has a long vertical stroke. This code of TABLE 2 can be optimized into a loop as shown in TABLE 3 as follows:

[0177] Note that the TABLE 3 generated code is much shorter than the TABLE 1 code. As an added bonus, many processors employ an instruction cache which allows the second and later execution of the loop to occur faster. Obviously, loop optimization can be done when long vertical strokes or parallel vertical lines are encountered. For example, a letter “H” might have two such loops for the lower and upper parts of the body, making the center crossbar the only code not in a loop.

[0178] In general, loops can be useful in the case of repeated consecutive rows. This is not limited, however, to long vertical strokes, for example, diagonal strokes for obliqued text can be created by using a value slightly different from RowBytes, perhaps RowBytes+1 in order to move from row to row. At medium to low resolutions, many characters will have repeated rows of rasters where one would think that curved lines would belong. As long as the minimum number of iterations allowable in the loop is kept low enough (perhaps as few as two), there are a surprising number of loops that can be found in most text characters.

[0179] Index Register Usage

[0180] The examples, so far, have used a memory location, RowBytes to move to the next row. This addressing is used so often that it merits its own register, thus lines like

[0181] Many processors allow an addressing mode which includes a pair of registers (an address register and an index register) plus an offset. If several registers are loaded with multiples of RowBytes, then many of the SUBTRACT instructions can be avoided. Furthermore, if the index register can be scaled, as is often the case, this can be used to extend the reach of a small number of registers dedicated to this purpose.

[0182] To optimize the “S” code example of TABLE 1, the index registers R6, R7 and R8 are loaded with the negative or RowBytes, RowBytes*3 and RowBytes*5 respectively, and are scaled by 2 or 4 when calculating an effective address as indicated in TABLE 4. (Note the negative of RowBytes gives additive addressing when moving up from the baseline.)

[0183] Notice that the code of TABLE 4 is somewhat smaller than the code in TABLE 1 since all but three instructions are involved in actually drawing part of the character in TABLE 4. Notice also the choice of values for index registers depending on the chosen architecture. R6, R6*2, R7, R6*4, and R8 cover the cases of 1, 2, 3, 4, or five rows above the one pointed by R0. R8, however, cannot be used as an index register itself, because no index with a reach of 6 is present in order to move up to the upper half of the character. Actually, R8 could have been used as an index register had it been needed for the top row, since no further upward movement is necessary.

[0184] Operations at Small Bit Depths

[0185] Up till now, only examples of code for block (Chunky) output devices at eight bits per pixel has been discussed. This has the natural advantage that each pixel is represented by exactly one byte. Compiled code for higher depths follows logically from the eight bit case. Compiled code for lower depths, however, requires new techniques. The one bit per pixel case, in particular, is quite important, since it occurs quite often and it is also the basis for planar output devices at higher depths.

[0186] For one bit per pixel, data can no longer be simply stored to various addresses, since several horizontal pixels are represented by one byte. Two or more characters can share parts of the same byte, so simply storing a constant in a location in the output device as part of the routine for a single character would obliterate part of the image for a character previously drawn. It is assumed that the processor manipulates at least one byte of data at a time. Some processors have so called bit field instructions which can operate on consecutive runs of bits which might span bytes. These are not universally available, however, and are often no faster than performing similar operations with ordinary shifting and boolean instructions, since the microcode still implements the bit field instructions in terms of byte-wide loads and stores. For this reason, the availability of bit field instructions has not been assumed, and it is assumed that only the traditional shift and boolean operators are available. Furthermore, the generated code will only one of either the AND or OR instruction.

[0187] The code that will be generated for lower bit depths will be less general than that discussed so far in that it will only be able to draw characters in a single foreground color. Drawing in other colors will generally require different code to be generated, or can be done in a two-step process by first drawing the compiled text in the primary color to a temporary canvas, and then using a special BLT to copy the text to the output device while simultaneously changing its color. For a two-color, one bit per pixel device) assume that the two colors are black and white, although the actual colors may vary depending on the device being used. The device has a usual background and foreground color. Text is drawn in the foreground color. This can either be black text on a white background, or white text on a black background. Furthermore, “white” can either be represented by all one's or all zero's. Either AND or OR operators are used depending on these two factors. This creates a two by two truth table as follows.

[0188] Since the AND and OR operations are exact duals of one another, there is no loss in generality in only considering one of these cases for the remaining discussion. For this reason, it is assumed that the OR operator will be used to draw text by setting 1 bits on a background of 0 bits.

[0189] Most processors can deal with data which is more than one byte wide in a single operation. Typically, a processor can handle 16 bit 32 bit, or 64 bit data paths. In the discussions above this issue was avoided and it is assumed that each instruction was operating on one byte, except the MOVE MULTIPLE instruction which operated on as many bytes as the number of registers specified. Working with more than one byte at a time can often lead to improved performance. Many processors, however, impose alignment restrictions on how multi-byte quantities can be addressed. A typical restriction is that a 16 bit (two byte) quantity can only be accessed if the lower addressed byte is eve. This is known as a 16 bit word alignment restriction. Other processors present no such restrictions, but may impose some speed penalty if the access is not correctly aligned. The addressing resolution of a given processor is defined to be the minimum bit alignment required for addressing memory by any of the instructions used by the compiled code. Typical addressing resolutions are eight, 16, and 32 bits. Clearly, the lower the addressing resolution, the easier it will be to generate code for that processor. Addressing resolution can sometimes be made smaller by avoiding the use of instructions that require stricter alignment restrictions. It might also be artificially raised to better take advantage of alignment optimization inherent in the processor's architecture. These decisions, however, are processor dependent.

[0190] We also define a shift factor to be the distance between the nearest addressing resolution boundary and the left-most pixel of a character drawn on the output device, that is, the number of background pixels between the nearest addressing resolution boundary to the left of the character and the left-most foreground pixel in any horizontal row of that character. Shift factors are measured in pixels and are numbered from 0 to (addressing resolution/bits per pixel) −1.

[0191] Code is generated not just for each character, but for each shift factor of each character. This is known as pre-shifting, in that all constants needed for drawing a character are pre-computed for each shift factor. The concept of pre-shifting is combined with the optimization discussed so far and create new ways of storing text partially in code, and partially in data specific to that code.

[0192] An example of a number 1 at one bit per pixel is shown in FIG. 10, using only optimization discussed as indicated in TABLE 6 so far. It is assumed that the processor has an addressing resolution of 8 bits, but it can handle at least 16 bit quantities. A convention of adding a suffix, such as “0.8” or “0.16” to the assembly language instructions is used to describe the sized quantity it is dealing with. As was mentioned earlier, it was assumed for the sake of illustration, without loss of generality, that a big endian processor is being used, so the left-most bits (and pixels) have the highest numeric significance.

[0193] Literal Pools and Code Folding

[0194] Note that the code in TABLE 6 is rather long-winded, because code for not one but eight shift factors must be generated. Note, however, the striking similarity of the code for the first six shift factors. It essentially involves the same instructions, just with different constant operands. The last two shift factors, however, use slightly different code. It would be nice if the code for at least the first six could somehow be merged.

[0195] This is possible by first loading the constants needed by each routine into registers, and then branching into common code. Indeed, this is what is done with the literal pool and code folding optimization.

[0196] The literal pool optimization sets registers up, not by explicitly loading them with constants, but rather, obtaining those constants from a literal pool, an area containing data which is to be loaded into registers. The operation is not limited to bit constants, instructions using loop counts or any other constants may be placed into the literal pool as well.

[0197] Once loaded, the code folding optimization merges common code since the salient differences between the various shift factors has been eliminated. Below in TABLE 7 is the optimized code for the number 1 of FIG. 10.

[0198] Notice that the optimized, folded code of TABLE 7 is much smaller than the unoptimized code of TABLE 6. The code for shift factors 1 through 5 is little more than a MOVE MULTIPLE followed by a branch into the code for shift factor 0. The code for shift factor 6 can also branch into the shift factor 0 code, but at a later point, since the first row requires a 16 bit instruction, rather than an 8 bit, as do all the other shift factors. Finally, the optimization fails for shift factor seven where no code can be merged, but the literal pool still allows the automatic loading of the loop counter for the stem. Also, the fact that the bit constants are in registers may improve performance depending on the specific characteristics of the processor.

[0199] Note that the literal pool contains all of the bit constants to be used for the text, as would be used for a category 1 text display system, but the actual ordering and structure of the pool, i.e., what elements are used for what purposes, depends on the generated code. In other words, the layout of the literal pool is completely at the discretion of the compiler. Also, note that while code can be readily merged for different shift factors of the same character, it is unlikely that two different characters, even within the same font, will share the same code structure. It is thus probably not very beneficial to look for code folding across characters.

[0200] As a character becomes more complex, there may be more bit constants needed to compile the character than there are available registers. In this case, the compiler may have to revert to placing the bit constants as immediate operands in-line with the code, thus foregoing the possibility of code folding. Alternatively, the literal pool might be accessed more than once in the execution of the compiled character. Sometimes, it may be more efficient to deal with an immediate value, than first loading a constant into a register and using it. This is especially true if the constant is used but once. Should these be placed in the literal pool, or in-line? This is a speed/space trade-off which is processor dependent.

[0201] Peephole Optimizations

[0202] Last, any good compiler should have a peephole optimizer. This is a collective set of very processor-dependent optimizations which ensure that the local code to perform any operation is optima. This usually takes the form of using the simplest form of an instruction needed, or using a short form of a branch when possible. These sorts of optimizations are very common and processor-specific and will thus not be expanded upon. Sometimes, however, the higher level structure of generated code might be modified to make some peephole optimizations more effective. For example, the literal pool in TABLE 7 above was placed after all the code, rather than interspersed with the code so as to possibly make it more likely that the branch made to merge with a previous shift factor can be a short branch. The architecture of the target processor will guide these sorts of decisions.

[0203] Planar Output Devices

[0204] So far the block output devices have been considered as well as those which have only one bit per pixel. The algorithms for planar devices are derived from the one bit per pixel algorithm. The simplest approach is to simply re-execute the one bit per pixel code on each plane. A more interesting approach is to use a technique similar to the index register optimization described above but to index by PlaneBytes instead of RowBytes. For example, TABLE 8 is the code for a shift factor 0 of the “1” example for a four plane output device.

[0205] If an index register is devoted to each plane (including plane 0, whose index would normally be zero) then different colors can be imaged by setting up the index registers in such a way that only certain planes will be affected, (perhaps several times) and others are not touched. This can be done by simply setting certain index registers to the same values so that the code which normally writes to a particular plane instead writes to the same plane as other code. This works because both AND and OR are independent operators; i.e., ((A OR B) or B)−(A OR B). In other words, it never hurts to draw the same exact image over a given plane. Since color is achieved by writing on some planes but not others, any color which images on at least one plane can be displayed. (The case of imaging on no planes is a no-op, and can be detected and skipped.)

[0206] Block-planar devices are generally used for Red Green Blue displays, and have a “chunk” factor of eight bits per pixel, Again, the simplest approach is to use the appropriate block algorithm multiple times, once for each plane. Alternatively, an approach similar to the planar example in FIG. 14 above can be used. The latter approach may be quite practical since the eight bit block code is generally quite small compared to similar code at smaller and larger depths, and the number of planes is generally only three. Note, however, that since at least three registers will need to be devoted to store the values that will be placed in each plane, there will generally be less room for using MOVE MULTIPLE instructions to fill long horizontal strokes.

[0207] A Detailed Example

[0208] All of the above discussion applies to a wide class of general purpose processors. The example code given wag in a hypothetical pseudo-machine. The following example of TABLE 9 is for a Motorola 68000 processor. The character is a Times Roman 12 point upper-case “P” at 72 dots per inch as shown in FIG. 11. The code is for 1 bit per pixel, and the addressing resolution, and thus the number of shift factors is 16. If the code were to be run only on 68020 and later processors, the addressing resolution could be reduced to 8 with a significant decrease in code size.

[0209] The generated code illustrates all of the optimizations described here, although not all may be used wherever possible because of process-dependent timing and code size considerations.

[0210] Processor Assumptions

[0211] Basic Algorithm

[0212] One Bit Per Pixel Algorithm

[0213] Two, Four Bits Per Pixel Block Algorithm

[0214] Eight and Greater Bits Per Pixel Block Algorithm

[0215] Planar Algorithm

[0216] Block/Planar Algorithm

[0217] Processor Description

[0218] The type of processor which is to be used to execute the compiled text is any general purpose Von Neuman processor like that used in most common computers in every-day use. The processor is assumed to be able to read and write primary memory at least one byte at a time, and perhaps in groups of two or more (typically two, four, or eight) bytes in one operation. The processor can also execute data that it has previously written in a particular area as code. No assumptions are made as to the exact mapping of data to machine instructions, as this is very processor dependent. It is assumed, however, that the processor has one or more registers which it can manipulate internally. Each register can hold information. Different registers may be designed to hold different types of information, but the following types of information will be considered as particularly important for the types of operations which will be described:

[0219] Data—This is arbitrary numeric data. For the purposes, this will usually refer to the data that will actually be stored in the output device.

[0220] Address—This is a numbered location in primary memory. This will usually point to the area in the output device where data is to be stored. There are usually some special purpose address registers, such as the stack Pointer and Program Counter. The use of the former is system specific as far as these algorithms are concerned and will not be discussed. The latter controls the next instruction to be executed and is usually only manipulatable by specific branching instructions which can be used in compiled code.

[0221] Index—This is an offset from a given address to a different address. The new address is computed by adding or subtracting the value of the index to an address, perhaps after scaling the index by some constant (typically but not necessarily a power of two) to obtain an effective address which is to be read or written. As an example, the RowBytes and PlaneBytes variables described in the Output Device section can be considered index information.

[0222] Some processors will have separate data, address, and index registers whereas others will have general purpose registers which can be used for any of the tasks above. Exactly which registers can be used for what purpose is not important, but it is assumed that the processor has some method of operating on data which is at an address offset by some index.

[0223] The processor is assumed to have the following types of operations available as instructions:

[0224] MOVE—Information is moved from a register to a different register, a location in primary memory to a register, from a register to a location in primary memory, or perhaps from one location in primary memory to a different location.

[0225] OR—data from two source is placed in a destination (possibly one of the two sources) such that the result has bits set to 1 where either source has bits set to 1 and bits set to 0 otherwise. Sources may be registers, perhaps primary memory, or perhaps constants. The destination is a register, or perhaps primary memory.

[0226] AND—data from two sources is placed in a destination (possibly one of the two sources) such that the result has bits set to 1 where either source has bits set to 1 and bits set to 0 otherwise. Sources and destination are as in the OR operation above.

[0227] ADD—Like AND and OR except that the numeric values of the two sources are added to form the destination value.

[0228] SUBTRACT—Like AND and OR except that the numeric values of the one source is subtracted from the other to form the destination value.

[0229] BRANCH—Start executing code at a different location other than the next instruction.

[0230] CONDITIONAL BRANCH—Branch only if a certain conditions is met, such as the last operation resulting in a value of zero (BRANCH IF ZERO) or non-zero (BRANCH IF NON-ZERO).

[0231] RETURN—Exit the current routine and return to execute the next compiled routine or the rest of the main outer algorithm.

[0232] Although the compiled code can be described in terms of these basic instructions which are common to all modern processor, the two more “macro” instructions which can be simulated by the instructions above, but which are often machine instructions themselves and serve to clarify the algorithms are described.

[0233] DECREMENT AND BRANCH—This instruction subtracts 1 from a register and branches if the register has not reached a particular value, general 0 or −1. This is used for simple loops where a particular body of code is to be executed a given number of times. This can be simulated by a SUBTRACT instruction followed by a CONDITIONAL BRANCH instruction. For purposes of illustration, it is assumed that the branch is taken when the register reaches zero. In that way, if a register is loaded with a numeric constant before the loop, the code within the loop is executed that number of times.

[0234] MOVE MULTIPLE—This instruction moves a series of consecutive bytes of memory into a series of registers or vice versa. This will be used to quickly get a get of registers to certain predefined constants or to store the values of such registers in memory. This can be simulated with multiple MOVE instructions.

[0235] The notation used in this “pseudo assembly language” is not intended to describe actual assembly language code used by any particular processor, but to illustrate code that might be generated by a hypothetical, but typical, processor containing instructions listed above. The left-root column is a line number. The next column contains instructions as listed above, the third column contains any operands to those instructions, and the right column contains comments describing the operation being performed. The operand field lists the source and then the destination separated by a comma. A symbolic value such as RowBytes is assumed to be some location in memory containing that value. The notation “Rx” indicates register number x. The notation “M(Rx)” is meant to mean “Use RX as an address, add the constant, m, and use the result as the effective address to operate upon.” The notation “#n” moans immediate constant value n. Numeric constants will be preceded by a “$” if hexadecimal and not if decimal.

[0236] The following is a list and short description of routines not included in the source code provided.

[0237] Compilation Algorithm

[0238] The following description describes the compilation algorithms more explicitly. Hereinafter, TABLE 10 (cfont.h), TABLE 11 (cmp124.c), TABLE 12 (cmp81632.c), TABLE 13 (cmpcommn.c), and TABLE 14 (compile.h) represent the same code.

[0239] In the embodiment described, two separate compiler modules are employed, TABLE 11 and TABLE 12. One module handles block (chunky) output devices at 1, 2, and 4 bits per pixel (<one byte per pixel) and the other handles block (chunky) output devices at 8, 16, and 32 bits per pixel (≧one byte per pixel). There is also code which is common to both compilers.

[0240] Both compiler modules first start by imaging the character to be compiled to a temporary canvas using the underlying text display mechanism. The both then use a two-pass approach. The first pass scans the pixels in the canvas, looking for various repeated patterns. The second pass uses the information gathered from the first pass to generate code. The 1/2/4 algorithm is more complex in that it actually applies the two passes for each shift factor needed. It actually images the character to the temporary canvas only once, before processing shift-factor 0. On subsequent shift factors, it simply shifts the pixels on the temporary canvas to the right by one pixel. The 8/16/32 algorithm is simpler in that it only deals with a single shift factor.

[0241] 1/2/4 Algorithm—TABLE 11

[0242] As code is being generated for shift factor 1 and above, the code is compared to that generated for previous shift factors to look for possible code folding opportunities. Code folding can only occur if the last n instructions for one shift factor are identical to the last n instructions for what would be generated if the previous shift factor were not folded. Indeed, code which is folded, and thus branches into a previous shift factor, may be branching into code which itself branches, as long as some useful work is actually being done. (A branch will not simply lead to another branch.) In order to keep this all straight, the compiler takes the approach that it will only consider a branch once a row has been completely drawn. It keeps a list of the code locations for the beginning of each row, or group of rows, if they are rolled into a loop. If the generated code and the comparison code with which it is to be merged diverge for any reason, the comparison is canceled up to the end of the current row, and the row pointer table is consulted to re-synchronize with the next row. This will mark the earliest point at which the code can be folded. Resynchronization is performed in any case, at the end of each row, even though the code is identical, because this might mark a point, where a previous branch has occurred and the comparison pointers must be updated. The actual branch instruction, if any, is not inserted until the code has been completely generated for one shift factor. If code folding is possible, the branch instruction replaces the code which is being eliminated and the cede stream is shortened. FIG. 12 illustrates this process.

[0243] FIGS. 12, 13, 14 and 15 are a set of flowcharts which describe the 1/2/4 algorithm in detail.

[0244] Discussion of Top Level for 1/2/4 Algorithm

[0245] Image character in temporary canvas—This is where we use the underlying text display system to image the character. The glyph is processed and set up in its most desirable form. A tight bounding box is computed and various state variables are computed which give general information about this character.

[0246] For each shift factor.—A loop is entered which will have execute the compiler passes 1 and 2 for each shift factor.

[0247] Perform pass 1—This is covered in more detail in FIG. 20. In general, pass 1 is concerned with gathering information and detecting patterns in the character. Several tables are created which will be used by the register allocation step and the code generation (pass 2) steps.

[0248] Assign Registers—The details of this step are highly system dependent. This step uses the information gathered in pass 1 to decide how registers are to be used. Factors that can affect this decision are.

[0249] The number of times that various bit image constants are encountered

[0250] The number of loop counters needed

[0251] The number and types of registers available

[0252] Trade-offs between execution speed and code folding ability.

[0253] (Often, it is desirable to put a constant in a register, rather than in-line in the code, even if it is used only once. This makes it more likely that the code can be folded, because bit constants which vary from shift factor to shift factor are relegated to the literal pool.

[0254] Any Other System-specific Issues

[0255] Perform pass 2—This is the main code generation step, and is described in more detail in FIG. 21.

[0256] Shift factor 0?—Code for the first shift factor is always generated in full and never folded, since it is the first shift factor. Code folding always results in backward branching.

[0257] Fold code if possible—Here we use the row pointer table and code comparison techniques illustrated in FIG. 18 to attempt to shorten the generated code.

[0258] Last shift factor?—The shift factor loop is iterated for each shift factor

[0259] Shift temporary canvas right by 1 pixel—The temporary canvas is shifted to the right in order to process the next shift factor.

[0260] Generate literal pool—The current implementation places the literal pools for all shift factors in one area after the last segment of code. This is to increase the possibility of being able to use a short branch instruction when doing code folding because there aren't any literal pool constants between the code segments. If this is not an issue for a given implementation, then it may be simpler to place the literal pools directly after the code which uses it. The current algorithm also back-patches the generated code in order to insert the exact offset to the literal pool, which is not known at the time the code is generated.

[0261] Discussion for Pass 1 of 1/2/4 Algorithm

[0262] For each row.—The outermost loop in this pass executes one iteration for each row in the glyph.

[0263] For each bit image in row.—An inner loop looks at the bit images for the current row. This may be in groups of one byte or wider. (typically two or four bytes.) Note that at this point, we are less interested in pixels as in the actual physical representation on the output device.

[0264] Bitmap in opt. table?—There is an optimization table which includes one entry for each bit image encountered while executing pass 1 for a given shift factor. Here, we search this table to see if this particular bit image has already been encountered. This table will later be used by the register allocation algorithm to intelligently decide how various registers should be used.

[0265] Increment count for this image in opt. table—If we had already found the bit image earlier, update the count of the number of times we see it for this shift factor.

[0266] Add entry for this image in opt. table—If we didn't find the image, then create an entry for it and set its occurrence count initially to 1.

[0267] Last image in row?—Loop for each bit image in the current row.

[0268] Row same as previous row? On all rows except the first, the bit image for the current row is compared against the previous. A group of x or more repeated rows (x is a system-dependent constant, 3 in the current implementation) is known as a streak and will be handled by a loop.

[0269] Increment streak count in row table entry—At this point, all that is known is that the two rows are identical. We may not have actually reached the critical number of rows to form a streak.

[0270] Last row?—Loop for each row in the glyph.

[0271] Discussion for Pass 2 of 1/2/4 Algorithm

[0272] Generate prologue code—This step generates the code which is concerned primarily with loading registers which will be used by the compiled rode. This may include loading up the destination address register, values from the literal pool, or other system-specific information needed throughout the compiled routine. This step may also update the destination pointer to point to the first row, if it is anything other than the baseline. This can occur in the case of descending characters (p,q, etc.) as well as characters which never reach the baseline, such as the apostrophe.

[0273] For each row.—A loop, similar to the one in pass 1 is executed for each row.

[0274] Start of streak?—If it was determined in pass 1 that this row forms the first row in a streak (a large enough group of repeated rows) then we may need to generate some special loop entry code.

[0275] Loop register already loaded?—If the register allocator decided to load a loop register from the literal pool, no extra code need be generated here. Otherwise.

[0276] Generate code to load, loop register—Code is generated which loads a register with the constant which will be used in a decrement and branch later to form the streak loop.

[0277] For each bit image in row.—This is a similar loop as the inner loop in pass 1.

[0278] Generate code to draw bit image—This is where the actual drawing code is generated. Details are system-specific. Bit images may be inserted in-line, or may be taken from registers. This is where most of the peephole optimizations are applied.

[0279] Last bit image?—This terminates the inner bit image loop as it does in pass 1.

[0280] Need advance code?—This is where the decision as to whether index register optimizations will be used or whether specific code to advance to the next row will be generated. Advance code is always generated if the current row is in a streak. Otherwise, it is not generated if it is the last row. If neither of these two conditions are met, the final decision may be system-specific. For example, the current implementation only uses index register optimization if the instructions that would be needed for the next row would use both a non-zero constant offset and an index register. Otherwise, the extra time and space needed to use the index register instructions is not worth the small overhead for the advance code.

[0281] Generate code to advance to next row.—This might actually generate code to advance by more than one row if index register optimizations were being used for previous rows.

[0282] In streak?—Here we check to see if the row we have just generated is part of a group of rows which will be generated in a loop.

[0283] Generate decrement and branch code—We generate the code at the end of the streak loop.

[0284] Skip to last row in streak—Since all of the rows in the streak are handled by the loop, we update the outer row loop pointers and counters to point to the next row beyond the streak so as to not generate extra code which is already handled by the streak loop.

[0285] Last row?—This terminates the outer row loop.

[0286] Generate epilogue code—Here we generate the code to exit from the compiled routine.

[0287] The 8/16/32 Algorithm

[0288] Rather than provide detailed flowcharts describing the 8/16/32 algorithm, we describe the salient differences between it and the 1/2/4 algorithm.

[0289] As mentioned earlier, the 8/16/32 algorithm is quite a bit simpler than the 1/2/4 algorithm for several reasons. First of all, code for only one shift factor need be generated. (This may not always be true if the addressing resolution is greater than 8 bits.) Also, there is really only one bit image which is applied selectively in different parts of the glyph, so registers can be loaded with this constant by the compiled text system, rather than by individual routines. In this way, the same code tan be used to generate text in any color which can be displayed on the output device. This obviates the need for any literal pools. This doe mean, however, that loop registers must be explicitly loaded, but this is a small price to pay.

[0290] One interesting difference between the 1/2/4 algorithm and the 8/16/32 algorithm is that the former uses mostly OR or AND instructions to do its drawing but the latter uses MOVE instructions. (The 1/2/4 algorithm might also use MOVE instructions for long horizontal rows such as dashes (-) but this is a relatively rare case and is considered a peephole optimization.) This means that other special purpose move instructions in the processor's instruction set can be used. The MOVE MULTIPLE instruction is of particular significance. Any horizontal row of consecutive pixels of reasonable length can be drawn by a single MOVE MULTIPLE instruction. This is performed so frequently that the current implementation internally converts each row from a bitmap into a runlength encoding. Short runs are handled by individual MOVE instructions. Longer runs are handled by MOVE MULTIPLE instructions.

[0291] While the invention has been particularly shown and described with reference to preferred embodiments thereof, it will be understood by those skilled in the art that the foregoing and other changes in form and details may be made therein without departing from the spirit and scope of the invention.