[Indigo]<PrintingDocs>frommaxc>ORBITGUIDE.DM!1>orbitguide-1.bravo

The hardware described in this report is intended for printing pages consisting primarily of text and lines on raster-scanned printing devices. There are two main tasks that this collection of hardware performs: (1) image generation, in which a binary representation of a video signal is prepared at high speed, and (2) transmission of that video signal to a raster output scanner (ROS).

Orbit, a four-card hardware device that plugs into the Alto II. The Alto II requires a specially-wired backpanel to accommodate the Orbit cards (some Alto II’s are manufactured with this backpanel already arranged). Orbit provides facilities for image generation: the resulting raster image can be returned to the Alto memory or can be forwarded via a "9-wire standard ROS interface" to:

The Dover printer, a Xerox 7000 copier with a specially-designed laser-scanned imaging head on it. Properly controlled, this engine delivers 1 page/second (paper speed is 10 inches per second). A modification is possible (the "extended Dover printer") that slows the transport speed to 5 inches/second and page delivery to 1 page/2 seconds.

There are numerous variations on this basic arrangement. Because the Alto II/Orbit pair communicates with the adapter using a standard interface, it is capable of operating with other adapters and printing engines that conform to the standard. Also, the TTL ROS adapter can be used to control other printing engines. Some alternatives are:

The basic idea of the entire arrangement is that a program in the Alto II can operate all these devices to cause pages to emerge from a printer. The remainder of this document will by and large assume that we are operating the standard Dover printer (10 inches/second). The basic ideas will remain the same when operating other printers, but many of the timing details will change.

For the purposes of discussion, we will assume that the printer scans the page in landscape mode (mode=8, in the Press terminology). Scan-lines run from bottom to top of the page (when the page is held in the normal portrait orientation); the first scan-line is at the left-hand side of the page. Orbit does not "know" that the video signal it is generating will be used to scan in landscape or in portrait mode, but we need to stick to one convention for the purposes of exposition.

The Orbit, ROS adapter and Dover printer system is quite tightly integrated; consequently, explication of the system is somewhat difficult. The reader is urged to bear with us, to skip sections that become obscure, and to read the document several times before abandoning all hope! For a first reading, the following sections are recommended:

Section 1, through 1.4
Section 2, through 2.4
Section 3

Numerous individuals and groups have contributed to the Dover program: the design and fabrication of Orbit, the ROS adapter and the Dover printer and ROS. This document is only a condensation of their designs and ideas. The overall Dover Program was managed by John Ellenby. The Dover Printer was designed by Gary Starkweather, Gary Swager, Tibor Fisli, Ed Wakida and Bobby Nishimura with contributions on producibility from Abbey Silverstone and on mechanical and industrial design from members of EOD/SPG and others on the program team. The ROS adapter was designed by Ron Rider, Ken Pier and Ron Freeman. Orbit grew out of a suggestion by Butler Lampson, and was designed by Severo Ornstein, Jim Leung and Bob Sproull. The standard microcode and test software were devised by Bob Sproull. In the closing months of the program, Gary Swager played a key role in coordinating the system integration of the Dover printer electronics, electro-optics, and the 7000 base. Dover ROS equipment is manufactured under the direction of Tibor Fisli and the Dover System is manufactured and integrated by SPG under the direction of Doug Stewart who also supervised the design and engineering contributions of SPG. Bob Sproull and Dan Swinehart produced the Spruce software that provides printing service using Orbit devices.

Numerous organizations cooperated very effectively on the Dover project. The people mentioned above came from PARC/CSL, PARC/OSL, PARC/SSL, SDD/SD, and EOD/SPG. The project was feasible in part because flexible funding was provided by the PARC Office of the Center Director.

By a raster we mean a rectangular region of a raster-scanned image, in this case an array of 1-bit values. A raster is characterized by its width and height (see Figure 1-1). Although there are many ways that the data bits within a raster might be represented, we shall be interested in only the simplest: we record a stream of bits, generated by scanning the raster in a prescribed (conventional) manner. We shall assume that rasters are scanned from bottom to top, and then from left to right. Figure 1-1 shows a tiny raster, the bit stream that results from scanning it, and the blocking of that bit stream into 16-bit words suitable for recording in Alto memory.

If we were to generate a raster representation of an entire page, and save it in memory, we would be overwhelmed by its size. A page 8.5 by 11 inches scanned at 350 bits/inch requires 11.5 * 106 bits, or some 710,000 words of Alto memory! Therefore, we are forced to generate the page raster incrementally, using smaller buffers. If we wish to avoid a full-page buffer, we must of course generate the scan-lines of the raster in the same order as the ROS device accepts them.

The unit of buffering in Orbit is the band, a group of 16 consecutive scan-lines. We will want to generate band images in the same order that the ROS accepts the scan-lines that comprise the bands. In the case of Dover, which scans in landscape mode, we will generate first the band corresponding to the left-most 16 scan-lines on the page, then the next band to the right, etc. Orbit’s task is to prepare the raster describing each band faster than the ROS yanks band rasters away in order to print them!

Orbit contains two buffers, each of which holds one band; the buffers are labeled A and B. While one buffer is being used to prepare an image (the image buffer), the other, which contains an already-prepared image, is being sent to the ROS (the output buffer). After the ROS is finished accepting the band raster, the roles of the two buffers are switched. Each buffer contains 16 scan-lines; each scan-line is 4096 bits long (see Figure 1-2). We can thus think of a band buffer as a two-dimensional array of bits, in which the x dimension (0 through 15) indexes scan-lines, and the y dimension (0 through 4095) indexes bits within a scan-line. If the total height of the raster on the page is less than 4096 bits, the upper region of the band should be used (that is, the region with larger y addresses). The reason for this will appear below.

Orbit excels at merging rasters represented as bit streams in the Alto memory into the image band buffer. Figure 1-3 illustrates one case: a character is represented by a raster in memory, characterized by its height and width. It is to be merged into the band by placing its lower left corner at location (x,y) in the band. This is effected as follows:

2. Alto microcode starts passing to Orbit the successive 16-bit words representing the bit stream for the source raster. Orbit takes each word, positions it on the proper scan-line, and at the proper vertical position, and merges the 16 bits into the raster already saved in the band. Each time Orbit finishes work on a scan-line, it increments the x position to move to a new scan-line, and decrements a width counter that counts remaining scan-lines in the source raster.

3b. Eventually, the last scan-line in the band (x=15) has been processed, even though the (character) width counter has not been decremented to zero. We must terminate that loop that passes raster bits to Orbit, but we must remember enough information so that we can resume processing of the same character when it comes time to work on the next band.

The "left over" information that must be remembered for the next band consists of two sorts of information: basic information about the character (the height of the source raster and the y coordinate that determines where the bottom of the source raster is to be placed in the band) and a description of the portion of the character remaining to be generated (a new value of the width counter, representing the unprocessed width remaining, and a new pointer into the bit stream for the source raster, which describes where to resume taking bits). The leftover source raster pointer requires 20 bits, and consists of two parts: the most significant 16 bits specify which Alto memory word is the first to take up next time, and the low order 4 bits specify which bit within the word should be the first to be processed.

So Orbit gives us help with the inner-most loop: positioning the character raster on the band raster, and merging the bits into it. Alto microcode, however, is responsible for an orderly processing of characters, for fetching source raster words and passing them to Orbit, for saving "left over" information, and for interpreting this information properly when the next band begins.

The details of the "merge" operation performed by Orbit offer some flexibility. A band buffer starts out with all bits set to 0—this is actually accomplished by clearing the words of the band as they are read out and passed either back to the Alto or on to the ROS. The "inner loop" of the merge operation is responsible for changing a particular bit in the band buffer (BAND[x,y]), based on the value of a particular bit of the source raster bit stream (SOURCEBIT). The algorithm is:

where INK is a 16 by 16 bit memory in the Orbit hardware that can be set by the Alto. The intent of the ink memory is to permit "gray" colors to be created by spatial halftones. In most cases, characters will want to be "black," and the INK memory should contain all 1’s. In light of the above algorithm, the proper way to view the input raster is: it is a mask, with 1 bits everywhere the "character" form lies. It is not correct to think of the 1 bits in the source raster as "data" bits—the INK memory provides the data bits.

There are some special cases of the Orbit image-generation technique that deserve mention. First, it is possible to have a source raster with width=15 and height=4096. This is a useful mode of operation when a binary image has been pre-computed, and Orbit is being used simply as a pipe to shovel the image toward the ROS. Second, there is at least one case when it is senseless to have an actual physical representation for the source raster. This occurs when merging "rules" (or "lines") into the band raster: in this case, the raster representation of the input bit stream consists of an endless string of 1’s, and we do not need to actually store this string in memory. For rules, then, it is more convenient to provide the four parameters (x, y, width, height), but to omit the memory for the bit stream, and simply ship −1’s (words with all 16 bits equal to 1) to Orbit.

While the image band buffer is being prepared with an image, the output band is being read out, either to the ROS adapter or back into Alto memory. The read-out mechanisms are similar, and require some explication. The basic read-out operation cycles through all 16 scan-lines (x=0 to 15), and delivers information from each scan-line beginning with y=FA*16, and ending with y=4095 (FA, which denotes "first address," is a number in the range 0 to 255 that can be set by the Alto). After the last bit (4095) of the last scan-line (x=15) has been read out, Orbit will "switch the buffers" (i.e., interchange the role of buffer A and buffer B). The next bit to be read out will come from the other buffer.

The FA mechanism has a minor effect on the way images should be generated. If the receiver of the video (usually the printer) is instructed to place the first bit of each scan-line at the bottom of the page, the next slightly above it, and so forth, then the relation between vertical position on the page (yp) and address of the bit in Orbit’s buffer (y) is: y = yp + (FA*16). Consequently, the number (FA*16) must be added to each desired page position (yp, measured in bits) to determine the proper y address to provide to Orbit. (Note: This addition can be easily excluded from the inner loop by making modifications to y incrementally, spacing appropriately for each character encountered.)

The act of reading a buffer also writes zeroes into it: this is an economical mechanism for clearing a buffer. The normal practice, therefore, is to read a buffer thoroughly simply in order to clear it. After the buffer is read, a "buffer switch" happens, and the cleared buffer becomes the image band buffer.

The most common use of Orbit is to drive a ROS printer. In this case, FA is simply set so that the upper portion of the buffer which is used corresponds to the desired image height for the entire page. In order to clear both Orbit buffers initially, we arrange two dummy bands of image information that will lie off the actual page image (i.e., to the left of the page, on Dover). Thus the first two buffers read, which may contain garbage left behind from previous operations and from lack of refreshing, will not be visible on the page. When used to drive a ROS (which requires FA to be a multiple of 4 in order to communicate video data sucessfully to the ROS adapter), Orbit can deliver video data at a rate of 23 MBits/sec.

Orbit also provides functions for controlling the ROS adapter and its associated printer. Two completely independent mechanisms are used for sending control information and for reading ROS (and adapter) status. Orbit will accept 16-bit commands from the Alto and forward them to the adapter. It is also constantly reading the status line returning from the adapter, and is capable of reporting 256 bits of status generated by the adapter.

The next several sections of this guide describe the operation of Orbit undertaken with the "standard microcode," and then the regimen for writing microcode if you so desire. This section describes those elements of Orbit that must be understood to operate the hardware using either the standard microcode or specially-written code.

The control of Orbit is accomplished with one Alto microtask (task 1, next to lowest priority), and an associated collection of microcode that executes within that task. Remember that the Alto must be "bootstrapped" after loading the microcode into the RAM in order to initiate task 1’s program counter to point to the proper RAM routine. (For more information about microcoding and bootstrapping, see the Alto Hardware Manual.)

The record of activity of the Orbit task is quite complicated. The task is initially inactive: the Alto program must initiate Orbit activity by issuing StartIO(4), which signals the Orbit hardware to activate its task. During the active period, the details of the microcode functions sent from the Alto to Orbit will govern exactly when the Orbit task is run. However, at the termination of a sequence of commands the microcode usually instructs Orbit to return to the initial, inactive, state. (This last is simply a convention; the "standard microcode" normally uses this convention, but has an exception as well.)

The remainder of this section describes simple use of 6 functions of the standard Orbit microcode. (The standard microcode includes many additional functions for debugging and for more exotic uses of Orbit. These are taken up in subsequent sections.) The standard microcode was written to accomodate most Orbit chores, including normal printing tasks and hardware diagnosis. The microcode source files can be found on [IVY]<SPRUCE>SpruceMc.Dm.

When the Orbit microcode is activated, it figures out what to do by reading a control table. To execute a command, a pointer to the control table (which must begin at an even address) is placed in location 720b, and StartIO(4) is executed. When execution of the command is complete, the Orbit task stores 0 in location 720b, an event that can be detected by the Alto program. Note that during execution of an Orbit command, the Alto emulator program continues to run—the Orbit task and the main program are asynchronous. To allow Orbit maximum access to the Alto microprocessor, it is advisable to curtail activities of other microtasks while printing is in progress. The display should certainly be turned off; stopping disk or Ethernet activity is less beneficial.

The Directive is a small integer that indexes the various operations that can be performed by the microcode; each operation is given a name of the form Programxx. When a command terminates, the control table entry OrbitStatusResult is loaded with the inclusive "or" of Orbit hardware status (OrbitStatus, bits 8-15) and microcode status (FirmwareStatus, bits 0-4), described below. If an operation returns a result, it is usually stored in the Result entry of the control table.

ProgramXY (directive=3) and ProgramInk (directive=7). In the simple situation we are considering, it is necessary to set the INK memory to contain all 1’s so that all characters will appear black on a white background. This can be achieved during initialization with a simple loop that uses ProgramXY to set x, and ProgramInk to set the 16 corresponding bits of the INK memory:

ProgramROSStatus (directive=14). This operation reads an entire word (16 bits) of ROS status. If we view the 256 status bits as lying in 16 16-bit words, numbered 0 to 15, then this function stores in Result the current value of status word n, where Argument1 = n * 1024.

The ProgramGeneratePage function is the main "workhorse," and contains the necessary facilities to keep a printer running at high speed. It depends on a data structure for describing the placement of characters on the page and for encoding the rasters that are to be printed for each character (the font). Building this data structure will require a pass over the each page before it is printed (more on this later). Figure 1-4 summarizes these data structures, which are explained in the following paragraphs.

Fonts. The microcode believes that there is only one font, but it may contain an enormous number of characters (up to 215 if you can figure out where to find memory for them!). Each character in the font is represented by a contiguous block of memory words, formated as follows:

Word 0:−Height (in bits) of the character. Heights of 1 to 4095 are legal.
Word 1:Width−1 (in scan-lines). Widths of 1 to 4096 are legal.
Word 2-n:Bit stream for the encoding of the character raster

Word 0 must lie on an even memory address. The sample character given in Figure 1-1 would therefore be represented as:

Word 0:−4
Word 1:4
Word 2:103126b
Word 3:100000b

To verify that you understand this encoding, you should be able to compute n (answer: i(Height*Width)/16j+1).

Band Lists. The most interesting piece of data structure is the band list, an encoding of where instances of various characters should appear on the printed page. This list is divided into segments, one for each band. Each segment gives information about the characters that begin in the corresponding band; Orbit microcode will handle the details associated with continuing the characters into subsequent bands if necessary.

Word 0This word must equal 4+(Copy*32), where Copy is the copy number in which the following entries are to be printed. A jump will occur, omitting these entries, if Word 0 is not equal to the CurrentCopy field in the control table. A version of this command must appear in every band in which information conditioned on this copy number occurs. Copy must be a positive integer less than 1024.

A complete band list, consisting of a contiguous sequence of band list segments (one for each band), describes an entire page. In the discussion below, we shall assume that the band list for a page is pointed to by the pointer BandListPointer; the band list must begin at an even address.

In most cases, constructing the band list from a document description will require an initial pass over the document description. One of the functions of this pass will be to map font descriptions and character codes into the one-dimensional font representation used in the structures above (i.e., a single 15-bit character code). Another function of this pass is to perform a sort: it will be necessary to process characters as they are extracted from a document description, determine the x and y positions of the lower left corner of the character raster by consulting a font description, and build a 2-word character entry. These entries will then need to be sorted by band number (a bucket sort is particularly reasonable for this task) in order to re-assemble the character entries into band list segments.

Left Over Table. The Orbit microcode will normally need access to a region of memory that can be used to save left-over information needed to resume image generation of characters that extend beyond one band. The discussion below assumes that the pointer LoTablePointer points to such a table; the table must start on an even address. The left-over table can be reset to the empty state by setting the first word to 0. Each left-over character in the table requires 4 words. Further understanding of the format of the left-over table is not essential to operate ProgramGeneratePage, but may be helpful for debugging (see Section 1.10).

Arguments. This function performs image-generation chores for a number of bands, and in addition forwards the image to the ROS adapter for printing by turning on SLOTTAKE. The arguments in the Orbit control table are:

Argument1 = Pointer to adapter command table (must be even; see below)
Argument2 = Timeout count, in units of 2 ms.
nBandsMinus1 = number of bands to generate, minus 1
FAword = FA*256 (i.e., FA must be in the left byte)
LoTable = LoTablePointer (left-over pointer, must be even)
FontTable = FontTableX+100000b (pointer to font table, offset by 100000b)
NewCharPointer = BandListPointer−1 (BandListPointer must be even)
CurrentCopy = 4 + (current copy number)*32

The function will attempt to generate images for the specified number of bands; of course the band list pointed to by NewCharPointer+1 must contain an adequate number of band list segments. The value in the nBandsMinus1 entry will be decremented at the end of each band, allowing the emulator to track Orbit’s progress. The timeout count is used whenever Orbit is waiting for the ROS adapter to finish reading the output buffer: if the timeout is exceeded, the microcode completes early (as if nBandsMinus1 were so small that it did not include the next band) and sets the firmware status bit TIMEOUTmc (bit 1) in the OrbitStatus word of the control table. The most common reason for timeout is the failure of page sync to arrive: these issues cannot be fully discussed until the operation of the adapter is described in some detail in section 3.

After the last band is generated, the ProgramGeneratePage function completes (i.e., sets location 720b to zero), even though the ROS adapter has probably not finished taking image data. In fact, the adapter can continue to request and receive data ad infinitum, but the data will eventually become all zero (recall that reading an output buffer zeroes it, and since the microcode is no longer invoking image-generation functions, no new image data are being added to the Orbit buffers). This is a convenient way to finish out the printing of a page with white borders. To halt the taking of image data, Orbit can be reset. After Orbit is reset, the ROS adapter will simply repeat the most recent video data it received correctly.

The adapter command table (pointed to by Argument1) is used to encode commands that should be sent to the ROS adapter during the generation of a page. Such a mechanism is necessary because the Alto program would not otherwise be able to signal the printer device during the page generation (because the OrbitROSCommand can be issued only by the Alto task assigned to Orbit, which is occupied with page generation). The table must begin on an even address, and contains two-word entries in the following format:

The table will be processed in the order given, i.e., the whenBandMinus1 entries should be arranged in decreasing order. An appropriate termination entry is Word 0=177777b, which specifies an unreasonably large value for whenBandMinus1. There are presently three AdapterCommandCodes defined:

1. Read 4 bits of adapter status; the four bits are numbered 4n to 4n+3, where AdapterArgument=n*256 (n is in the left byte). The resulting status is read and stored in bits 12-15 of the memory word that previously held AdapterArgument. (The exact operations are: OrbitControl ← AdapterArgument; AdapterArgument ← OrbitStatus.)

3. Wait for AdapterArgument/3 microseconds in a tight loop. This command is provided in case it is absolutely essential that two adapter commands be issued before the same band. In this case, we must wait 60 microseconds between issuing adapter commands to assure proper communications with adapter.

If Jump codes appear in the band list, the CurrentCopy entry must be maintained. This word must contain an encoding, as shown, of the number of times, plus one, that the current document has been printed during the current run; that is, the number of the current copy.

When page generation has terminated, the Result word in the control table will contain the value that nBandsMinus1 had when word 8, bit 3 of adapter status was last on during image generation; this word will contain the original nBandsMinus1, plus one, if the bit never comes on. This very special feature assists with detecting an important but elusive timing signal in the Dover printer (see the description of Count-H in the Dover section.)

During the generation of a page, the three data structures (font, band list and left over table) must of course be resident in memory. In order to keep a ROS running at high speed, the font and band list structures for each page must be present in memory at the moment it is necessary to begin generating the image for the corresponding page. To do this requires a buffering strategy that is willing to read information for page i from a disk while page i-1 is being imaged. (The left over table is reasonably small, and can of course be re-used for subsequent pages. Consequently, we shall omit further mention of it.)

Method 1. Font and band list structures for each page are generated on the disk, and read into one of two memory buffers. While page i-1 is being imaged, the structures for page i are being read. (This scheme is not a particularly attractive alternative, because the complexity of a page is severely restricted by the amount of available memory.)

Method 2. One font data structure will suffice for all the pages to be printed, and can therefore remain resident in memory. The band lists are put in two buffers: while page i-1 is being imaged, the band lists for page i are being read. This scheme is the recommended scheme whenever the page complexities allow the font and two band list buffers to fit in memory. The advantage of this scheme is that it permits printers to run at high speed, without pauses between pages.

Method 3. All of memory is used for one font structure and one band list. After page i-1 is imaged, it is necessary to read the font and band structures for page i before imaging may start for that page. If used with high-speed printers, it may be necessary to stop the printer while page i is read in, because otherwise there would be insufficient time to complete disk activity before imaging activity would need to begin. This scheme does have the advantage that maximally complex pages can be printed, by allocating all of memory to the structures necessary for that page.

Note that hybrid schemes may be used as well: methods 2 and 3 may be mixed, although it may be necessary to stop the printer as the method is being switched (for the same reason it may be necessary to stop the printer between pages using method 3). Planning the buffering and font makeup is one of the less pleasant tasks of the initial pass over the document that builds band lists!

The remainder of section 1 presents details that are not essential to most printing applications. Read on only if you are (1) hardy, (2) desirous of writing microcode, (3) desirous of writing Orbit test programs, or (4) need to know how to use Orbit for non-real-time image generation help.