US 4,298,957 AGrant

Data Processing System With Character Sort Apparatus

Issue Date:1981-11-03

•14 Claims

•12 Drawing Sheets

Abstract

A data processing system comprises a first storage device for storing character font data representative of a plurality of characters, each character being represented by the font data as a bit map of predetermined dimensions, the plurality of characters being stored in an ordered storage sequence. An image presentation device is capable of visually presenting an image comprised of preselected ones of the characters on a predetermined background area. A second storage device is capable of storing a bit map representation of the image, and a visual control device is capable of controlling the image presentation device to visually present the image in accordance with the character font data stored in the bit map representation of the image in the second storage device. A third storage device is capable of storing a list of identification data for at least some of the preselected characters to be visually presented, the identification data identifying the type and style of each character as well as its desired location on the background area. Finally, a data control device is capable of controlling the processing and handling of character font data and comprises a sorting device for sorting the identification data in the third storage device into the ordered storage sequence, an accessing device responsive to the sorted identification data for accessing from the first storage device in the ordered storage sequence the character font data for each character identified in the list, and a loading device for loading the character font data for each accessed character into the bit map representation in the second storage device at a location defined by the identification data for that character.

Metadata

Assignee

Xerox Corporation

Inventors

William S. Duvall
William K. English

Application Information

Application Number:US 0529931

Filing Date:1979-06-28

Priority Date:1979-06-28

Art Unit:237

Classifications

IPC:

G06F 3153G06F 312

Field of Search:

364340900 MS File;200 MS File724;735;751;790

Patent Drawings (12 sheets)

Description

This invention relates to data processing and, more particularly, to a data processing system of the general type comprising first storage means for storing character font data representative of a plurality of characters, each character being represented by the font data as a bit map of predetermined dimensions, said plurality of characters being stored in an ordered storage sequence; image presentation means for visually presenting an image comprised of preselected ones of said characters on a predetermined background area; second storage means for storing a bit map representation of said image; and visual control means for controlling said image presentation means to visually present said image in accordance with the character font data stored in said bit map representation of said image in said second storage means.

A data processing display system of the general type above-described is disclosed in U.S. Pat. No. 4,103,331. That system has worked well in connection with word processing employing a limited set of character fonts, such as the English alphabet and various mathematical symbols. With such a limited character set, the character font data describing the entire set of characters may be stored in the main memory of the system. The main memory disclosed in U.S. Pat. No. 4,103,331 is a solid-state random access memory having a relatively fast access time compared with traditionally slower magnetic disk and tape memories, for example.

U.S. Patent Application Ser. No. 781,266 filed on Mar. 25, 1977 in the names of Shingo Arase and Roy J. Lahr for MULTI-LINGUAL INPUT/OUTPUT SYSTEM and assigned to the assignee of the present invention discloses a data processing system especially designed to process Japanese language text. The Japanese language is a composite of four different character sets, i.e., Romaji (English alphanumerics), Hiragana (phonetics of Japanese orignated words), Katakana (phonetics of non-Japanese originated words) and Kanji (Chinese characters). Although the Hiragana and Katakana character sets are quite manageable in terms of numbers, i.e., there are 46 Hiragana characters and 46 Katakana characters, and thus the character font data therefore could all be stored in a relatively fast access solid-state main memory, this has not been the case with the significantly larger Kanji character set. More specifically, there are about 10,000 Kanji characters. The use of any significant percentage of this total, e.g., 3000 characters, would require the use of an external storage device, such as a disk, due to the bit capacity limitations of contemporary solid-state memories.

Thus, one disadvantage of the systems disclosed in U.S. Patent Application Ser. No. 781,266 and U.S. Pat. No. 4,103,331 (if operated with a relative large character set or sets, such as in processing Japanese text), is the relatively slow access of character font data from the required external disk storage or the like. The access time problem is compounded when it is realized that the character font data stored in disk memory may be in an ordered storage sequence quite different than the desired ordered display sequence. When dealing with a character set numbering in the thousands, it will be appreciated that if the ordered display sequence were followed in accessing character font data from the disk memory, the speed of formatting and displaying Japanese text would be greatly limited.

It would be desirable, therefore, if the access time of character font data from an external relatively slow access storage memory could be increased over that now attainable in word processing systems, such as the prior art systems above-identified.

In accordance with this desirability, a data processing system of the general type above-described is provided with a character sort apparatus. More specifically, the data processing system of the invention is characterized by comprising third storage means for storing a list of identification data for at least some of said preselected characters to be visually presented, said identification data identifying the type and style of each character as well as its desired location on said background area; and data control means for controlling the processing and handling of character font data, said data control means comprising sorting means for sorting the identification data in said third storage means into said ordered storage sequence, accessing means responsive to said sorted identification data for accessing from said first storage means in said ordered storage sequence the character font data for each character identified in said list, and loading means for loading the character font data for each accessed character into said bit map representation in said second storage means at a location defined by the identification data for that character.

It will thus be appreciated that, in the case where the first storage means is defined by a magnetic disk memory, for example, the character font data will be accessed in the ordered sequence in which the characters are stored on the disk. They will not be accessed from the disk in the order in which they are to be visually presented, i.e., displayed or printed. As a result, each track containing desired character font data need only be accesssed once, i.e., moving the head over the track only once, thereby significantly reducing the overall access time of character font data stored on the disk. In the case of a Japanese word processing system, the time required to access Kanji character font data from the disk would be greatly reduced by the "single access" feature of this invention.

These and other aspects and advantages will be described below with reference to the accompanying drawings, wherein:

FIG. 1 is a perspective view of a data processing system of the present invention;

FIG. 2 is a block diagram representation of the data processing system of FIG. 1;

FIG. 3 is a representation of various storate areas in the main memory depicted in FIG. 2;

FIG. 4 is a representation of various storage areas on the surfaces of a magnetic recording disk included in the disk drive depicted in FIG. 2;

FIG. 5 is a top plan view of the array of keys included in the keyboard depicted in FIG. 2;

FIG. 6 shows an exemplary image display on the display device depicted in FIG. 2;

FIG. 7 shows a hypothetical display bit map generation control list stored in the main memory of FIGS. 2 and 6, wherein the characters appear in an ordered visual presentation sequence;

FIG. 8 shows the display bit map generation control list of FIG. 7, wherein the characters are sorted into an ordered storage sequence;

FIGS. 9-11 depict the sequence of operations during which large character strikes for display are loaded from the disk into data buffers defined in the main memory of FIGS. 2 and 3, and then from the data buffers into the bit map data portion of the main memory;

FIG. 12 is a block diagram representation of the control section of the CPU shown in FIG. 2;

FIG. 13 is a block diagram representation of the data section of the CPU shown in FIG. 2;

FIG. 14 is a block diagram representation of the display controller shown in FIG. 2; and

FIG. 15 is a block diagram representation of the disk drive controller shown in FIG. 2.

At the outset of this description, it must be stated that the term "character" as used herein is meant to imply not only recognizable alphanumerics and language character forms, but also any graphical or symbolic representation of any size, shape or geometric orientation.

Referring now to FIGS. 1 and 2, a data processing system of the present invention is shown. The system includes a central processing unit (CPU) 10 that is comprised of a data section 12 and a control section 14. The system also comprises a main memory 16 and a plurality of peripheral devices, some of which having associated controllers. More specifically, the system comprises a keyboard 18, a disk drive 20 with associated disk drive controller 22, a display device 24 with associated display controller 26, a cursor unit 28 with associated cursor unit controller 29, a raster-output-scanned (ROS) printer 30 with associated ROS printer controller 32, and a communications network 34 with associated network controller 36. The keyboard 18 is unencoded and does not require a separate controller.

Information is transferred to and from the data section 12 of the CPU 10 by means of a main data transfer bus 38. The preferred processor 10 is designed to handle 16-bits of parallel data, and so the bus 38 is comprised of 16 parallel lines. The data bus 38 is connected not only to the CPU data section 12, but also to the main memory 16 through a driver and parity circuit 40 and a 32-bit memory data bus 42. Additionally, the data bus 38 is connected to the disk drive controller 22, the display controller 26, the cursor unit controller 29, the ROS printer controller 32 and the network controller 36, as well as to the keyboard 18.

Information is thus applied directly onto the data bus 38 from the keyboard. On the other hand, the disk drive 20, display device 24, cursor unit 28, ROS printer 30 and communications network 34 are each input/output peripheral devices and information is transferred to and from such devices through and by means of their respective controllers 22, 26, 29, 32 and 38. Thus, a suitable bus 44 is connected between the disk drive 20 and its controller 44, a bus 46 is connected between the display device 24 and its controller 26, a bus 47 is connected between the cursor unit 28 and its controller 29, a bus 48 is connected between the ROS printer 30 and its controller 32, and a bus 50 is connected between the communications network 34 and its controller 36. The nature and constitution of many of the signals transferred along the busses 44, 46, 47, 48 and 50 will be described below.

The disk drive controller 22, display controller 26 and network controller 36 are each capable of generating one or more task request signals in the form of "wake-up" commands whenever it requires one or more services to be performed by the CPU 10. The cursor unit controller 29 and ROS printer controller 32 do not employ the use of task requests. The disk controller 22 is capable of generating two task request signals i.e., KSEC (Disk Sector Task) and KWD (Disk Word Task). These signals are applied along respective task request lines 52 to the CPU control section 14. The display controller 26 is capable of generating three task request signals associated with the display of data, i.e., DWT (Dispaly Word Task), DHT (Display Horizontal Task) and DVT (Display Vertical Task) that are applied along respective task request lines 52 to the CPU control section 14. Additionally, the display controller generates a CURT (Cursor Task) task request signal periodically to enable the CPU 10 to execute a program routine associated with the handling of cursor data. The network controller 36 is capable of generating a single task request signal, i.e., NET (Network Task) that is applied along a respective line 52 to the CPU control section 14.

Other task request signals are generated internally of the CPU 10 and include MPT (Main Program Task), MRT (Memory Refresh Task) and PART (Parity Task). The MPT task request signal is associated with the main microprogram routine stored in the CPU control section 14 and is always true, i.e., the main microprogram routine is always requesting service. The MRT task request signal goes true every 38.08 .mu.s in order to refresh information stored in the main memory 16. Lastly, the PART task request signal goes true whenever a parity error is detected by the parity circuit 40.

In order for each of the controllers 22, 26 and 36 to be informed when the CPU 10 is executing instructions relating to the requested service, the control section 14 includes means to be described below for applying a "task-active" status signal back to the controller. These task active signals are applied on lines 54 from the control section 14 to the controllers 22, 26 and 36, as shown in FIG. 2. There are two task-active lines 54 connected to the disk controller 22 (associated with the KSEC and KWD tasks), four task active lines connected to the display controller 26 (associated with the DWT, DHT, DVT and CURT tasks) and one task-active line 54 connected to the network controller 36 (associated with the NET task).

Referring now in more detail to the CPU 10, and in particular to the control section 14 thereof, it must be stated generally that the control section 14 applies instructions to the data section 12 for execution thereby. Additionally, instructions in the form of control signals are applied along respective control lines 56 to the various I/O controls 22, 26, 29, 32 and 36 for execution thereby. The instructions are forwarded in accordance with a particular sequence or routine to be carried out and identified with a particular task to be serviced. The control section includes means to be described below for determining which of a plurality of wake-up task request signals applied to the control section 14 has the highest current priority value. More specifically, each of the plurality of tasks to be serviced is preassigned a unique priority value. Thus, performing a requested service for the display controller 26 may be of higher priority than performing a requested service for the network controller 36. The control section 14 forwards instructions associated with the highest current task to serviced to the data section 12 and respective I/O controller for execution.

As indicated above, there are no task request signals supplied from the cursor unit controller 29 and the ROS printer controller 32. Rather a program routine associated with the processing of cursor information is processed in response to the CURT task request signal initiated by the display controller 26. The printing task is initiated by the operator depressing a command key on the keyboard 18. This will cause a number of selectable commands to be displayed on the display device 24 in a key top area 96 (FIG. 6). One of the commands is a print command which can then be selected by hitting a key on the keyboard 18 corresponding to the location of the print command in the key top area. This entire concept will be described in more detail below in connection with the description of FIG. 6. At this time, however, it should be noted that the print command signal generated by the keyboard 18 is interpreted by the CPU 10 as a "Print Task Request" which is then serviced in the manner described above.

Referring now in more detail to FIG. 12, the control section 14 of the CPU 10 includes a priority encoder 158 which has task request inputs connected to the various task request lines 52 from the I/O controllers 22, 26 and 36, as well as to various output lines 162 from the decoders 160 for receipt of the internally generated task request signals alluded to above, e.g., MRT. The task request signal MPT, which requests servicing the main program, is manifest by the grounded line 164 and is always true (low). Thus, the main program is always requesting service. The priority encoder 158 includes circuitry (not shown) for generating a mutli-bit control signal on a respective plurality of lines 166 related to the highest priority wakeup-task request signal currently applied as an input to the encoder 158. The priority encoder 158 includes a further input for receiving a RESET signal on a line 168 from an initialize circuit 170 to be described in more detail below.

Now then, the control signal developed on lines 166 is applied to respective inputs of a current task register 172 which responds to such control signal for generating a multibit address signal that is applied in bitparallel format on a respective plurality of lines from the register 172 to respective inputs of an address memory 176. The address memory 176 includes a plurality of storage locations, preferably defined by a respective plurality of multi-bit registers (not shown). There are preferably a number of registers included in the address memory 176 equal to and respectively associated with the plurality of tasks capable of being performed by the CPU 10, as alluded to above. Each register in the address memory 176 is addressed by a unique multi-bit code defined by the address signal applied thereto from the current-task register 172 on lines 174.

In accordance with the preferred embodiment, each of the registers in address memory 176 is capable of storing the next address of an executable microinstruction stored in a microinstruction memory 78. In this respect, each of the plurality of address memory registers may be thought of as a program counter for its respective task to be serviced relative to the corresponding microinstruction routine stored in the instruction memory 178.

Each instruction stored in the memory 178 is accessed in response to a corresponding address signal applied on address lines 180 from the address memory 178. Each instruction includes an instruction field preferably comprised of twenty-two bits, and a next-address field preferably comprised of ten bits. The specific constitution of the 22-bit instruction field, if desired, may be obtained through a review of Alto: A Personal Computer System Hardware Manual, January 1979, Xerox, Palo Alto Research Center, 3333 Coyote Hill Road, Palo Alto, Ca. 94304 The instruction field is loaded into an instruction register 182 on lines 184 and is then applied through appropriate decoders 160 (also described in more detail in the Alto manual) to the data section 12 of the CPU 10. Certain of these decoded instructions are also forwarded to the I/O controllers 22, 26 and 36. The next-address field is fed back on lines 186 to the currently addressed register in the address memory 176. In this manner, each of the plurality of registers in the memory 176 will always contain the address of the next microinstruction stored in the instruction memory 178 to be executed in accordance with the particular task to be serviced.

A portion of the twenty-two bit instruction field of each microinstruction may be dedicated to various special functions, some of which are applied on control lines 188 to respective ones of the I/O controllers 22, 26 and 36 for controlling same, and some of which are applied on control lines 190 to address modifier circuits 192 for branching. In accordance with the preferred embodiment, there is a four-bit special function "sub-field" in the instruction field of each microinstruction, wherein two of the sixteen four-bit codes capable of being defined are respectively representative of "TASK" and "BLOCK" functions. A TASK signal component of an accessed instruction, upon being decoded by an appropriate one of the decoders 160, is applied on a line 194 to the current task register register 172 for enabling same to load an address signal, representing the current highest priority task requesting service. This address signal is then applied to the address memory 176. A decoded BLOCK signal is applied on another line 194 to the current task register 172 for disabling same.

The multi-bit address signal developed at the output of the current task register 172, in addition to being applied to the address memory 176 on lines 174, is also applied on lines 196 to a task-active decoder 198. The decoder 198 responds to the address signal output of the register 172 and generates one of the plurality of TASK-ACTIVE signals alluded to earlier on its respective line 54, dependent upon the current highest priority task to be serviced. The decoder 198 includes a delay circuit for delaying the application of a TASK-ACTIVE signal to the respective I/O controller by one clock cycle of the processor. In this manner, the appropriate TASK-ACTIVE signal will be generated at a time corresponding to the execution of instructions related to the task being serviced.

The control section 14 as shown in FIG. 12 also includes a clock generator 200 for generating appropriate CLOCK signals for application to the current-task register 172 on a line 202, the task-active decoder 198 on a line 204, the address memory 176 on a line 206, and the initialization circuit 170 on a line 208.

Still referring to FIG. 12, the initialization circuit 170 is responsive to a START signal generated when the system is turned on by the operator. Upon receipt of the START signal, conventional circuitry in the circuit 170 causes a RESET signal to be generated which is applied to the priority encoder 158 on line 168, to the current task register 172 on a line 210, to the task-active decoder 198 on a line 212, to the instruction memory 178 on a line 214, to the instruction register 182 and decoders 160 on a line 216, and to the address modifier 192 on a line 218. Upon receipt of a RESET signal, these various components of the control section 14 are reset.

The initialization circuit 170, in response to a START signal, also generates a multi-bit initialization address signal on a respective plurality of lines 220. In a preferred embodiment of the invention, their are sixteen possible tasks and associated registers in address memory 76. Thus, the initialization address signal is a four-bit signal that is initially zero, i.e., 0000, and is incremented by one at the rate of the CLOCK signal pulses applied on line 208. The RESET signal is maintained for sixteen cycles, i.e., sixteen CLOCK signal pulses, at which time the initialization address on lines 220 will increment from zero (0000) to fifteen (1111). The address signal output of the current task register 172 during initialization is identical to the initialization address signal. During initialization, the address signal output of the current task register 172 is applied through an AND-gate 222, which is enabled by a RESET signal from the initialization circuit 170, to the address memory 176. In this manner, the address signal (0000) will be loaded into register number zero in the address memory 176, the address signal one (0001) into register number one, and so on. This process initializes the address memory by setting the various registers therein at their respective starting values.

Further details of the preferred CPU control section 14, if desired, may be obtained through a review of the Alto manual, as well as U.S. Pat. No. 4,103,330.

Referring now to FIG. 13, the data section 12 of the CPU 10 preferably includes a number of 16-bit registers, such as a pair of 32 word register files (R register file 224 and S register file 226) and a number of single word registers (T register 228, L register 230, M register 232, memory address register (MAR) 234 and instruction register (IR) 236). The data section 10 also includes an arithmetic logic unit (ALU) 238, a pair of multiplexers 240 and 242, a PROM 244, a shifter 246, a constant memory 248 and a main memory decode and control circuit 250.

As shown in FIG. 13, the multiplexer 242 has a first data input connected to the data bus 38 for receiving data therefrom and a second data input connected to the output of the ALU 238. A control input of the multiplexer 242 is connected to an output of the PROM 244 for controlling the multiplexer in terms of which data input is to be applied at its output. The output of the multiplexer 242 is connected to the T register 228. Load control of the T register is accomplished by a control signal from the control section 14, while the output of the T register 228 is connected to the ALU 238. The ALU 238 is restricted by an output of the PROM 244 into 16 possible arithmetic and logic functions. The PROM 244 is controlled by 4 control lines from the control section 14 of the CPU 10. The output of the ALU 238 is connected to inputs of the L register 230, M register 232 and MAR 234, as well as to the multiplexer 242, as indicated above.

A load control output of the L register 230 is connected to a second input of the M register 232 for controlling the loading of data therein, whereas a second inverted output of the L register 230 is connected to an inverted input of the shifter 246, which is capable of left and right shifts by one place and cycles of eight. Load control of the L register 230 is effected by a load control signal applied from the control section 14. The output of the shifter 246 is connected to an inverted data input of the R register file 224, whereas the output of the M register 232 is connected to an inverted data input of the S register file 226. The outputs of both register files 224 and 226 are connected to the data bus 38. The various functions of the shifter 246 are controlled by control signals from the control section 14. The register files 224 and 226 also receive control signals from the output of the multiplexer 240 and are addressed by address control signals from the control section 14. The multiplexer 240 itself receives various input control signals from the control section 14.

The MAR 234 has its output connected to the memory address bus 80 for applying a 16-bit address signal to the main memory 16. Additionally, this 16-bit address is applied to the decode and control circuit 250 which applies control signals to the main memory 16 on lines 82. These control signals are associated with the manner in which the 16-bit values stored in main memory are transferred over the 32-bit memory data bus 42 to the drivers and parity circuit 40.

The instruction register 236 is used by an emulator microcode routine to hold the current emulated microinstruction. The input of IR 236 is thus connected to the data bus 38, as is a 16-bit output. Additionally, various output bits (1-4) of the 16-bit output are connected on output lines to the multiplexer 240. Lastly, the constant memory 248 is preferably a 256 word by 16-bit PROM that holds arbitrary constants. The constant memory output is connected to the data bus 38 and is addressed by control signals from the control section 14, as shown.

Further details of the preferred data section 12, if desired, may be obtained through a review of the Alto manual, and details of an earlier alternative embodiment may be obtained through a reivew of U.S. Pat. Nos. 4,103,331 and 4,148,098.

Reference is now had to FIG. 3 where the main memory 16 will be described in more detail. At the outset, it should be noted that memory 16 is preferably an 850 us error corrected semiconductor memory capable of storing 65,536, 16-bit words. A first section 60 of the memory 16 is capable of defining and storing a bit map representation of an image to be displayed on the display device 24, or a "slice" or segment of an image or page to be printed on the ROS printer 30. This slice may be either lengthwise or widthwise in orientation, but is desirably widthwise. In accordance with the preferred embodiment, the resolution capabilities of the printer 30 are significantly greater than that of the display device 24. Accordingly, it is not possible to create an entire bit map for a page to be printed in the bit map data section 60. Consequently, the bit map for a page to be printed is created on a disk in the disk drive 20 and then transferred in widthwise slices, each a predetermined number of bits in length. The slices are transferred to the memory 16 and then to the ROS printer controller 32 one slice at a time, as will be discussed in more detail below.

A second section 62 of the main memory 16 is adapted to store "display control blocks" and "disk command blocks", both referred to generically as "DCB's". The purpose of DCB's will be described below in connection with a description of the display controller 26 and the disk drive controller 22.

A third section 64 of the main memory 16 is adapted to store character font data for a first set of characters, i.e., "small" characters for display. These small display characters preferably comprise Romaji (English alphanumerics), Katakana and Hiragana character sub-sets, wherein each character is desirably defined by a 7.times.7 bit map matrix. Additionally, due to this relative small scale and the degree of complexity of the Kanji character sub-set, a single "dummy" Kanji character comprised of a predetermined 7.times.7 bit map matrix pattern is included in the small display character set (see character numbered 65 in FIG. 6). Desirably, only small display characters are displayed in a first page display area 66 on the display device which is used for page formatting purposes and the like. This concept will be discussed in more detail below relative to FIG. 6.

A fourth storage section 68 of the main memory 16 defines a pair of data buffers 70 and 72 (FIGS. 9-11). The purpose of these data buffers is to receive "strikes" of large display characters from the disk drive controller 22 and foward selected ones of the characters in each strike to the bit map data section 60. The specific manner in which data buffers 70 and 72 are controlled will be described below. At this point, however, it should be noted that the large display character set includes Romaji, Katakana, Hiragana and full Kanji character sub-sets. Each character is defined by an 18 bit wide by 20 bit high font data bit map matrix. Further, each character strike is comprised of 512, 16-bit words, and thus 22 characters. Desirably, only large display characters are displayed in a second text display area 74 (FIG. 6), which defines a magnified portion of the full page being created and is used for editting and viewing purposes. Again, this concept will be discussed in more detail relative to FIG. 6.

A fifth section 76 of the main memory 16 defines a pair of bit map generation control lists, one for display and one for printing. An exemplary display bit map generation control list is depicted in FIG. 8. Generally speaking, the bit map generation control list for display comprises a list of all large display characters to be displayed. Each such character is listed by a 12-bit character code which defines the character and its set (large display) and sub-set (Hiragana, Katakana, etc.), as well as its style (bold, italics, etc.). In addition, for each character in the list, the x, y coordinate values at which such character is to be located in the display bit map are given. Preferably, the x, y coordinate values define the upper left hand corner of the 18-bit wide by 20-bit high bit map matrix defining each large display character. This concept will be discussed in more detail below with reference to FIGS. 7 and 8. At this time, however, it should be noted that the information contained in the display list is used to access the character font data for the large display characters from the disk memory included in the disk drive 20. This data is then loaded into the data buffers 70 and 72 for ultimate storage in the appropriate locations in the bit map data section 60, then used for display.

The other bit map generation control list defined in section 76 of the main memory 16 is for printing. The list is basically the same, except it lists print characters that are to be included in the particular slice of print bit map data then being created, it being recalled that the complete bit map for printing is located on the disk memory and is formed a slice at a time. As will be discussed below, print characters are preferably each defined by a character font data bit map 32 bits high by 32 bits wide. The print character font data is stored on the disk memory and preferably contains the full set of Romaji, Hiragana, Katakana and Kanji characters. As each slice of print bit map data is formed in the bit map data section 60, then used for printing, it is transferred into disk memory. Then, a new print bit map generation control list is created to define the next adjacent slice of print bit map. When the complete print map has been defined and stored on the disk memory, it is re-transferred a slice at a time to the bit map data section 60 and from there to the ROS printer controller 32 for serial output to the ROS printer 30. During printing, the display device 24 must be blanked, since only a single bit map data section 60 is utilized and in order to increase memory speed. Obviously, if additional main memory storage space were provided, separate display and print bit maps storage sections might be defined.

A sixth and last section 78 of the main memory 16 is allocated for the storage of other data and programs. Specifically, the program routines associated with the data processing system of this invention are loaded into section 78 from the disk drive 20 for ultimate execution by the CPU 10.

As shown in FIGS. 2 and 3, the main memory 16 is addressed by a 16-bit address signal supplied on the address bus 80 from the data section 12 of the CPU 10. Additionally, appropriate memory control signals are applied on lines 82 from the data section 12 to the main memory. These control signals determine the manner in which two, 16-bit words are placed on the 32-bit memory data bus for application to the driver and parity circuit 40 during a read operation, and the manner in which the 32-bit composite word applied on the memory data bus 42 from the circuit 40 is segregated for storage in the main memory 16 during a write operation. The address signal on the bus 80 controls the location at which each 16-bit word is to be stored or retrieved. Further details of a preferred main memory 16 are disclosed in the Alto manual, as well as in U.S. Pat. Nos. 4,103,331 and 4,148,098.

Having described the various storage sections of the main memory 16, reference is now had to FIG. 4 where the disk memory 84 will be described. In accordance with the presently preferred embodiment, the disk drive 20 may comprise either a Diablo Model 31 or Model 44 disk drive. Each drive can accommodate a removeable disk cartridge (not shown) containing the disk memory 84 therein. As is conventional, the disk drive 20 includes means for reading and writing data from opposing surfaces of the disk memory 84. There are preferably 12 sectors and up to 406 tracks on each surface of the disk memory.

Purely for ease of discussion, the disk memory 84 is shown in FIG. 4 in the same format as the main memory 16 of FIG. 3. However, it will be appreciated that, unlike the main memory 16 wherein 16-bit words are accessed in parallel, 16-bit words are accessed from the disk memory 84 serial by bit. Thus, in defining the five basic sections of the disk memory 84, it will be appreciated that the data content of such sections is stored in series on identifiable sections of identifiable tracks on the two storage surfaces of the disk.

As shown in FIG. 4, a first storage section 86 of the disk memory 84 is adapted to store a complete bit map of a page of text to be printed by the ROS printer 30, such page being comprised of the print characters above-defined, i.e., each print character being defined by a 32 bit.times.32 bit character font matrix. As will be recalled, the character font data describing the bit map matrix for each print character is defined in a second, font data storage section 88 of the disk memory 84 and includes characters of the Romaji, Hiragana, Katakana and Kanji sub-sets. The print bit map is created a slice at a time in the bit map data section 60 of the main memory 16 and is then transferred to the print bit map section 86 of the disk memory for eventual application to the ROS printer controller 32 through the main memory bit map data section 60 and the main data transfer bus 38.

The print character data is stored in the font data storage section 88 as "strikes" of 512, 16-bit words. There are thus 8 print characters in each strike, due to the 32 .times.32 bit map matrix. Desirably, six strikes are stored in each track, each strike occupying 2 adjacent sectors. To facilitate access of the data, the print character data is stored in a predetermined ordered storage sequence (e.g., A, B, C, D---) and each strike is numbered. Then, and in accordance with the preferred embodiment, strikes 0-5 are stored on one track on one side of the disk, strikes 6-11 on the aligned track on the other side of the disk, strikes 12-17 on an adjacent track on the first side of the disk, and so on.

A third storage section 90 of the disk memory 84 is adapted to store the 18 bit wide.times.20 bit high bit map matrix defining each of the large display characters. Again, this large display character font data is stored by strikes of 512 words each, i.e., there are 22 characters per strike. The manner in which the strikes are stored on the disk surfaces is preferably the same as that for the print character strikes. As will be recalled, the large display character set preferably includes the complete Romaji, Hiragana, Katakana and Kanji character sub-sets.

Still referring to FIG. 4, a fourth storage section 92 of the disk memory 84 is adapted to store various "text files". These files contain data representative of each document created. Each document is comprised of a predetermined number of pages and is identified in the text file by a predetermined code. Each page of the document is identified in the text file by number. The information content of the page is identified in the text file by a character identification list. Each character on each page (and not just a particular set of characters, such as large display characters) is identified in the list by its 12 bit identification code. Further, the list contains data as to the relative positions of the characters on the page. The list for each page in the text file can be read and interpreted by the CPU 10 in order to generate either the display bit map generation control list (FIG. 8) or the print bit map generation control list, dependent upon whether the data is to be displayed or printed. It will be recalled that both of such control lists are defined in the main memory storage section 76 (FIG. 3).

A fifth and last storage section 94 of the disk memory 84 contains other data and programs, such as the main program for carrying out the data processing operations of the system of FIGS. 1 and 2. As will be recalled, this program is loaded into the storage section 78 of the main memory 16 when it is desired to have the CPU 10 execute same.

Referring now to FIG. 5, the keyboard 18 will be described in more detail. As will be recalled, the keyboard 18 is preferably unencoded in the sense that 63 of the 68 keys shown in FIG. 5 are each capable of generating a signal on a corresponding one of 63 output lines when depressed. The remaining 5 keys are each capable of generating a signal on a 64th output line, as well as an associated one of the original 63 keys. Thus, 68 output states can be defined on a 64 bit output. Now then, the 64 bit output from the keyboard is applied directly into preassigned storage locations in the storage section 78 of the main memory 16 (FIG. 3) through the data bus 38. The 64 bit output is actually applied as four, 16-bit words and are preferably stored in four adjacent storage locations. The 64 bit output values are then sampled periodically by the CPU 10 under program control. More specifically, the key depressed at any instant of time causes its corresponding output line or lines to go true (binary 0). All other output lines will be false (binary 1). The CPU 10 detects this under program control during each sample period and encodes the true signal(s) into a 12-bit code representative of the specific key depressed.

As shown in FIG. 5, the keyboard 18 contains a group of character keys containing the standard English (Romaji) alphanumeric character set thereon, as well as characters of the Hiragana character set. Four additional character keys contain just Hiragana characters, as such character set includes 48 characters and the standard Romaji character set includes only 44 characters. Aside from the character keys, there are various function and command keys as follows:

Referring again to FIG. 2, the display device 24 and display controller 26 will be described in more detail. The display device is preferably a standard CRT display, such as a standard 875 line raster-scanned TV monitor, refreshed at 60 fields per second from the display bit map defined in the storage section 60 of the main memory 16. The display device 24 preferably contains 606 display points (pixels) horizontally and 808 pixels vertically, i.e., 489,648 pixels in total.

The display controller 26 handles transfers of image data between the bit map storage section 60 of the main memory 16 and the display device 24. The basic manner in which image data is presented on the display is by fetching a series of 16-bit words from the display bit map in main memory storage section 60, and then serially extracting the bits to become the video signal. The serial video bits are applied along the bus 46 to the display device 24. Each scan line is comprised of 38, 16-bit words of the display bit map. The actual display is defined by one or more display control blocks (DCB's) in the storage section 62 of the main memory 16. Basically, each DCB contains data which defines the resolution, margin and positive-negative characteristics of the display. In addition, if more than one DCB is used for data to be displayed, they are linked together starting at a predetermined location in main memory 16, such location being in section 78 of the main memory and representing a pointer to the first DCB in the chain. Then, each succeeding DCB contains a pointer to the next DCB in the chain. Each DCB also contains the bit map starting address for two scan lines in each field (odd and even). Further details of DCB's as applicable to the display controller 26, if desired, may be obtained through a review of the ALTO manual, as well as U.S. Pat. No. 4,103,331.

As shown in FIG. 14, the display controller 26 includes a 16 word buffer 252 for receiving image data from the bit map data section 60 of the main memory 16 as applied along the data bus 38. In this respect, the 16 bit parallel input of the buffer 252 is connected to the bus 38. The buffer 252 is loaded with 16 words of image data, one word at a time, in response to a load command applied on a line 266 from a control circuit 254. The control circuit 252 includes means for interpreting and decoding various control signals applied to an input thereof from the CPU control section 14 along lines 56 (see also FIG. 2). The data stored in the buffer 252 is unloaded one word at a time into a single word buffer 256 connected to the output lines of the buffer 252. The buffer 256 is also loaded upon receipt of a load command on a line 268 from the control circuit 254.

The output lines of the buffer 256 are connected to a serializing shift register 258 which serializes the data and supplies it to a digital mixer 260. The register 258 is clocked by a BITCLK signal generated by a sync generator 262 and supplied on a line 270. The sync generator 262 also supplies appropriate video sync signals to the display device 24 along associated lines of the bus 46 (FIG. 2). The BITCLK signal is also applied on lines 270 to clock inputs of the control circuit 254 and a cursor shift register 264 to be described below. The shift register 258 is loaded with a 16 bit word from the output of the buffer 256 upon receipt of a load command on a line 272 from the control circuit 254. The control circuit 254 also is capable of generating a load command on a line 274 for the cursor shift register 264 in order to load therein a 16-bit word of cursor data.

The control circuit further includes means for generating the three primary microcode task request signals identified earlier, i.e., DVT (display vertical task), DHT (display horizontal task) and DWT (display word task). The vertical task is "awakened" once per field, at the beginning of a vertical retrace. The horizontal task is awakened once at the beginning of each field, and thereafter whenever the word task (DWT) is blocked (essentially at the end of each horizontal scan line). The word task is controlled by the state of the buffer 252, i.e., whether it needs to receive more image data. In addition to these three task-request signals, the control circuit 254 is also capable of generating the cursor task-request signal (CURT) each horizontal line. The cursor task enables the CPU 10 to process x and y coordinate data supplied thereto on the data bus 38 from the cursor unit controller 29.

Still referring to FIG. 14, the cursor shift register 264 has its 16 parallel inputs connected to the data bus 38 for receiving a 16-bit word of cursor data from the main memory storage section 78, where 16, 16-bit words defining a "patch" of cursor data is stored, as will be discussed in more detail below. The cursor shift register 264 is loaded upon receipt of a load command on line 274 from the control circuit 254 and is clocked by the BITCLK signal on line 270 from the sync generator 262. The serialized cursor data bits are supplied from an output of the register 264 to another input of the digital mixer 260, which then merges the cursor data with the image data from the bit map data section 60. The video bits at the output of the mixer are applied along an associated line of the bus 46 to the display device 24 where they are raster scanned onto the display screen.

Further details of a presently preferred display controller 26, if desired, may be found in Appendix A hereto, as well as in U.S. Pat. No. 4,103,331.

Referring now to FIG. 6, the various display areas on the display device 24 and the manner in which they are generated will be described. As a general statement, it should be noted that the display screen is capable of displaying data in a scaling of a standard paper size format, such as "A4" size. The totality of display pixels, i.e., 489,648, have corresponding bit locations in the bit map data section 60 of the main memory 16, where the data to be displayed is mapped. With this in mind, the CPU 10 is programmed to cause the effective segregation of the total display into the key top display area 96, a message display area 98, the page display area 66 and the text display area 74.

The keytop display area 96 is located in the upper fourth of the display screen. It normally contains a representation of 30 blank key tops arranged in 3 rows of 10, each row separated into left and right halves of five keys each. These keys form a "virtual keyboard" that enables the operator to enter many more different kinds of symbols than there are keys on the keyboard 18. Thus, and as alluded to above, depressing of the KANJI mode key following typing of a Hiragana character or characters into the text will cause up to 30 Kanji characters (from the large display character set) having the same sound to be displayed in the key top display area 96. The most common Kanji character bearing the typed phonetic sound will be underlined. Selection of one of the displayed Kanji for substitution in the text is then accomplished by simply depressing that one of the keys among a group of 30 keys (outlined by dotted lines and numbered 100-FIG. 5) corresponding in position to the key position of the Kanji character in the virtual keyboard of the display area 96. The key top area 96 may also be used to display a "menu" of commands, including the print command, which may then be selected in the same manner as with Kanji characters. The commands are preferably constituted of words formed by small display characters.

The message area 98 is preferably a white character on black background display and separates the key top display area 96 from the lower three-fourths of the display screen. The information displayed in the message area 98 includes the name of the document being processed, the page number of the currently displayed page, the amount of unused space for document storage remaining in the disk memory 84, and the current typein mode (e.g., Hiragana). This area is also used to display status and error messages to the operator. The information displayed in the message area 98 is also preferably constituted of words and symbols formed by small display characters.

The page display area 66 represents a full page of text and has fixed dimensioned and located outer borders 67. However, inside the borders 67, the operator is capable of defining at least one "text box", which is simply a rectangular area of dimensions capable of being predetermined by the operator and inside which small display characters defining the text being processed is to be displayed. The operator can set the size of each text box and its position within the borders 67 defining the page, as well as whether or not each box is to have a border margin. For purposes of illustration, a border margin 102 is shown defining a single text box in page display area 66. The operator can also set the "pitch," or space between the small display characters in the text box 102, as well as the "leading," or space between the lines within the text box 102. A text box may also contain fixed text incapable of being edited, such as headings for forms and the like. The margins 102 of the text box are settable by the operator through the use of the cursor unit 28 in a manner to be described in more detail below.

The text display area 74 is essentially a magnified portion of the full page display in the page display area 66, inasmuch as only small display characters are preferably used in the latter area and only large display characters are preferably used in the former area. The operator controls whether or not the text display area is "active", and if so its vertical dimension. When the text display area is active, it overlies and replaces a part of the page display area 66, as shown in FIG. 6. The operator can adjust both the top margin 104 and the bottom margin 106 of the text display area 74 through use of the cursor unit 28 in a manner to be described below. Since the text display area magnifies a portion of the full page in the page display area 66, it cannot display the full page of text, even when it is expanded to be the same physical size as the full page display. The operator thus typically will use the text display area for text editting and viewing, while using the page display area for formatting the text on the page.

Referring to FIGS. 2 and 6, the cursor unit 28 and cursor controller 29 will be described. A cursor 108 is capable of being displayed at any desired location on the display device 24. The cursor 108 consists of an arbitrary 16 bit.times.16 bit patch (such as to define an arrow), which is merged with the image data defined by the display bit map data at the appropriate time in the digital mixer 260 of the display controller 26 (FIG. 14). The bit map for the cursor is contained in 16, 16-bit words in the storage section 78 of the main memory 16 (FIG. 3). Additionally, the x and y coordinates for the cursor 108 are each defined by a 10-bit word and are stored at separate 16-bit word locations in the storage section 78, i.e., each 10-bit coordinate value is stored as the ten least significant bits of a 16-bit word. The coordinate origin for the cursor is the upper left hand corner of the screen. The cursor presentation is unaffected by changes in display resolution.

Positioning of the cursor 108 is operator controlled through the use of the cursor unit 28, which has often been referred to as a "mouse". The cursor 108 is used in conjunction with three buttons 110, 112 and 114 (FIG. 1) on the mouse 28 to control the typing, editing, command and viewing aspects of the system. Button 110 is used to change the viewing aspects, such as activating the text display area 74 and defining the locations of the top and bottom margins 104 and 106 of such display area.

The mouse 28 includes x, y coordinate generating means in the form of x and y position transducers (not shown). The transducers generate x and y pulse trains in response to movement of the mouse 28 along a work surface. These x and y position signals, as well as the button command signals are applied through the cursor controller 29 to the CPU 10. In this respect, the cursor controller 29 basically serves as a store and forward interface between the mouse 28 and the CPU 10 along the data bus 38. The five output lines of the mouse are included as the five most significant bits of a 16-bit signal applied by the cursor unit controller 29 onto the data bus 38 under microcode control. This 16-bit signal is then interpreted by the CPU 10 in order to execute any button command that may have been issued, as well as to update the 10-bit x coordinate and 10-bit y coordinate values stored at separate memory locations in the storage section 78 of the main memory 16.

Further details of a presently preferred mouse 28, if desired, may be obtained through a review of U.S. Pat. No. 3,892,963, and an alternative mouse is disclosed in U.S. Pat. No. 3,987,685. Further details of a presently preferred cursor unit controller 29, if desired, may be obtained through a review of the ALTO manual, which also sets forth further details of the presently preferred display controller 26 as it relates to the mixing of cursor data with the image bit map data for display.

Referring again to FIG. 2, the disk drive controller 22 will be described in more detail. The preferred disk drive controller 22 is designed to accommodate a variety of disk drives, such as the Diablo Models 31 and 44 alluded to above, which are preferred alternatives for the disk drive 20. The disk controller 22 records three independent data blocks in each track sector on the disk memory 84 (FIG. 4). The first data block is two, 16-bit words long and includes the address of the sector. It is referred to as the "Header Block". The second data block is referred to as the "Label Block" and is 8, 16-bit words long. The third data block is referred to as the "Data Block" and is 256, 16-bit words long. Each block may be independently read, written or checked, except that writing, once begun, must continue until the end of the sector.

The main program of the data processing system capable of being run on the CPU 10 communicates with the disk drive controller 22 via a four-word block of main memory 16 located in the storage section 78 thereof. The first word is interpreted as a pointer to a chain of disk command blocks (DCB's) which are stored in the storage section 62 of the main memory 16 (FIG. 4). A disk command block is a ten-word block of main memory in storage section 62 which describes a disk transfer operation to the disk controller 22, and which is also used by the controller to record the status of that operation.

The preferred disk drive controller 22 is implemented by the circuitry shown in FIG. 15 and the two microcode tasks alluded to above, i.e., the sector task (KSEC) and the word task (KWD). The data paths in the disk drive controller 22 are shown in FIG. 15. More specifically, data is loaded from the data bus 38 into a buffer 280 where it is buffered before being loaded into a shift register 284. The register 284 provides a serial transfer of data indicated by the output signal DATOUT which is phase encoded into the signal WRITE DATA by a data encoder 286. An oscillator 288 clocks the data through the encoder 286 to the disk drive 20, for writing on a disk surface in the disk memory 84.

Data is read from a disk surface and decoded by a data decoder 292, whose output is multiplexed by a multiplexer 294 under control of the DATOUT signal from the shift register 284. The output of the multiplexer 294 is shifted through a shift register 296 under control of the signal BITCLK for loading in a buffer 298. The signal BITCLK is a clock signal developed by a multiplexer 302 which is responsive to a clock signal approximately equal to one half the frequency of the signal generated from the oscillator 288 for the data encoder 286 and to the clock signal READ CLOCK which enables the data decoder 292. Under control of the signal BITCLK, the buffer 298 transfers groups of 16 bits of read data to the bus 38 in parallel.

A control circuit 304 provides load command signals for the various buffers and registers depicted in FIG. 15, as well as to the disk drive 20, in response to microcode control signals from the CPU control section 14. Additionally, it relays status signals onto the data bus 38 in response to receipt of status signals from the disk drive 20. It further generates the two task request signals referred to above, and receives associated task active signals back from the CPU control section 14. Further details of a preferred disk drive controller 22, if desired, may be obtained through a review of the ALTO manual and U.S. Pat. No. 4,148,098.

Referring now to the ROS printer 30 and its controller 32 shown in FIG. 2, it should be noted that any suitable raster-output scanned printer 30 capable of receiving the print bit map data in serialized format from the controller 32 and scanning such data across an appropriate recording medium can be employed. An exemplary ROS printer is the Fuji Xerox 1660 printer manufactured by Fuji Xerox, Ltd. of Tokyo, Japan. Additionally, any suitable ROS printer controller 32 capable of receiving print bit map data in 16-bit words from the data bus 38 and then serializing and synchronizing it for transmittal to the printer 30 may be employed.

In addition, or as an alternative, to the ROS printer 30 and its controller 32, a ROS printer and associated controller (not shown) may be used at a location remote from the system of FIGS. 1 and 2. An exemplary ROS printer for use at a remote location is a laser scanned xerographic printer, such as a Xerox 7000 duplicator modified to include laser-scanning ROS optics. A description of exemplary optics adapted for use in a xerographic copier/duplicator, such as the Xerox 7000 duplicator, appears in U.S. Pat. No. 3,995,110. A suitable ROS printer controller for controlling such a printer is disclosed in U.S. Application Ser. No. 899,751 filed on Apr. 24, 1978 in the names of Butler W. Lampson et al for Electronic Image Processing System and assigned to the assignee of the present invention. Print bit map data could be supplied to that system through the communications network 34. Yet another exemplary ROS printer is the Xerox 9700 computer printer manufactured by the Xerox Corporation of El Segundo, California, and a controller that may be used with that printer is disclosed in U.S. Pat. No. 4,079,458. Either of these exemplary remote ROS printers and associated printer controllers could, if desired, be used as the printer 30 and controller 32 in place of the presently preferred Fuji Xerox 1660 printer and associated controller.

Referring again to FIG. 2, any suitable communications network 34 and network controller 36 may be utilized to supply data to stations or systems external to the system of FIG. 1 and 2. An exemplary communications network and controller therefore is disclosed in U.S. Pat. No. 4,063,220. Specific details of such network and controller, if desired, may be obtained through a review of the ALTO manual and such patent.

Having described the primary components of the data processing system of FIG. 1 in terms of the block diagram representation of FIG. 2, the manner in which character font data (either large display characters or print characters) are transferred from the disk memory 84 into appropriate storage locations in the bit map data section 60 of the main memory 16 will be described. This process will be described, by way of example, with reference to the transfer and storage of large display characters, although the process is identical for the transfer and storage of print characters, as will be made clear below.

Referring first to FIG. 7, a hypothetical display bit map generation control list is shown with the characters being listed in an ordered visual display sequence, i.e., the order in which the characters are to be scanned for display. The list of FIG. 7 is hypothetical since the characters are in fact sorted by the CPU 10 into an ordered disk storage sequence i.e., the order in which characters are stored in disk memory 84, when the list is actually prepared (FIG. 8). The list of FIG. 7 is simply included to represent how the characters would be normally listed without the unique character sort feature of this system.

As shown in FIGS. 7 and 8, the display bit map generation control list contains the identification of all large display characters to be displayed on the display screen in terms of its 12-bit identification code and 10-bit x and y coordinate values. The list thus contains the identification data for all large display characters to be displayed in all large character display areas on the display, such as the text display are 74 and the key top display area 96. The x, y coordinate values insure the display of all characters at the appropriate location on the screen by insuring their proper location in the display bit map data section 60 of the main memory 16.

It should be noted that the small display characters do not appear in the display bit map generation control list in main memory, as the font data therefore is itself resident in the main memory. Consequently, no sorting is necessary with respect to the character identification data for those characters, which appears in the character identification list in the text file located in storage section 92 of the disk memory 84. These characters would thus be displayed in accordance with their ordered display sequence, and not in accordance with the order in which they are stored in main memory.

Purely for ease of description, the display bit map generation control lists depicted in FIGS. 7 and 8, respectively, are only 13 characters in length. Additionally, the 12-bit character identification code and 10-bit x and y coordinate values for each large display character in the lists are indicated by numbers, where the nunber indicative of the 12-bit identification code signifies the number of that character in the large display character set as stored on the disk memory 84. As an example, character number 2 in a "0, 1, 2- - -" sequence could be the Romaji character C, character number 4 culd be the Romaji character E, and so on for the entire set of large Romaji, Hiragana, Katakana and Kanji display characters (potentially over 10,000 in all). The numbers representing the 10-bit x and y coordinate values are meant to be the numerical equivalent of the actual 10-bit digital values, it being recalled that the display screen is roughly 600 pixels wide by 800 pixels high with the display bit map containing an equivalent number of bit storage locations. Thus, character 2 would be located at coordinate x=500, y=200, character 4 at coordinate x=200, y=100, and so on. Obviously , the x and y values are totally hypothetical and are merely for exemplary purposes.

In creating the actual display bit map generation control list of FIG. 8, what the CPU 10 does under program control is to create the list one character at a time on the basis of the list of characters contained in the associated text file in disk memory 84. It will be recalled that the character identification data appearing in the text file list are in an ordered visual display sequence, i.e., the order in which the characters are to be scanned for visual display. The ordered sequence of the characters listed in the hypothetical control list of FIG. 7 would be the same as the ordered sequence of those characters in the text file list. It should be recalled, however, that the text file list contains the 12-bit identification codes and "leading" and "pitch" data, as opposed to the 12-bit identification codes and x, y coordinate data that appears in the bit map generation control lists.

Character sorting to arrive at the actual display bit map generation control list of FIG. 8 is accomplished by the CPU 10 under program control. More specifically, the data section 12 of the CPU 10 preferably executes a standard "Tree Sort" algorithm. Details of such an algorithm, if desired, may be obtained through a review of Algorithm No. 245, "TreeSort 3", Robert W. Floyd, Communications of the ACM, Vol. 7, No. 12, December, 1964. Execution of the program routine implementing this algorithm causes the character information in the display bit map generation control list to be listed in the sequence in which the characters are stored in disk memory 84, as opposed to the order in which the characters are to be scanned for display (as exemplified by the hypothetical list of FIG. 7). This enables each track on a disk surface to be accessed only once to read all of the large display characters to be displayed in the text display area 74 and key top display area 96 (FIG. 5) that are stored in the six strikes on that track. Specific details of the preferred program routine associated with implementing the TreeSort 3 algorithm for character sorting are set forth in the program listings of Appendix A hereto.

It will be recalled that the large display characters are stored in strikes of 22 characters each on the disk memory 84. Thus, the first strike (strike 0) would include large display characters 0-21, the second strike (strike 1) large display characters 22-43, and so on. FIG. 8 indicates which strikes each of the listed characters is in. It is important to appreciate this relationship in view of the procedure by which the character font data for each of the listed characters is actually entered into the appropriate location of the display bit map in section 60 of the main memory 16.

More specifically, and with reference to FIGS. 9-11, character font data is loaded into the bit map data section 60 of the main memory 16 through the use of the pair of data buffers 70 and 72 defined in the data buffer section 68 of the main memory 16. Thus, the CPU 10 under program control first looks through the bit map generation control list to see if any characters from strike 0 are in the list. With respect to the example of FIG. 8, there are five such characters, i.e., numbers, 2, 4, 5, 17 and 19. Then, it causes the twenty two characters of strike 0, i.e., characters 0-21, to be transferred into the data buffer 70. Such transfer is effected by instructing the disk controller 22 to cause the disk drive 20 to read strike 0, and then the disk controller to apply such strike in successive 16-bit words onto the disk bus 38 for transmittal to the data buffer 70 in the main memory 16. At this stage, the data buffer 72 remains empty.

The CPU 10 then transfers, in successive 16-bit words, characters 2, 4, 5, 17 and 19 from the data buffer 70 into their respective locations in the bit map data section 60 of the main memory 16, as defined by the values of the x, y coordinates for each character. In this respect, the CPU 10 reads the x, y coordinate values for each character prior to transfering the first 16-bit word thereof into the bit map data section. Virtually at the same time characters are being transferred from the data buffer 70 into the bit map data section, the CPU 10 looks to see whether any characters in the bit map generation control list are in strike 1 on the disk memory. If so, which is the case in FIG. 8, it effects a transfer of strike 1 in the above-described manner into data buffer 72 of main memory data section 68. This stage is shown in FIG. 10.

FIG. 11 shows the next stage in the process, i.e., transferring characters 33, 42 and 43 (the only characters in strike 1 in the list of FIG. 8) from data buffer 72 into the bit map data section 60 of the main memory. Virtually at the same time, the data buffer 70 is re-loaded with the twenty-two characters of strike 2, since character number 59 appears in the list. This procedure is repeated until all large display characters to be displayed in the total image are transferred into the display bit map in the main memory storage section 60.

An entirely similar procedure is effected by the CPU 10 under program control with respect to the strikes of print character data stored in the font data section 88 of disk memory 84. With respect to the print data strikes, however, it will be recalled that each 512 word strike comprises only 8 characters, due to the fact that the bit map defining matrix for each print character is 32 bits.times.32 bits, as opposed to the 18.times.20 bit map matrix for each large display character. Additionally, it must be recalled that the total print bit map (resident in disk memory 84) is created a slice at a time by transferring the character font data for each slice into the bit map data section 60 of the main memory 16 in the ordered storage sequence following character sort, and then forwarding the bit map slice to the disk drive controller 22 for loading into the corresponding slice of the total print bit map.

Specific details of the program routine associated with the creation of the display and print bit map generation control lists and the transfer of listed characters from disk memory 84 to main memory 16, as well as those routines associated with the definition of multiple display areas on the display device 24, are respectively set out in the program listings of Appendixes A and B to and forming part of this specification. With respect to such routines, it should be noted that there are three implementing languages used in the software in general for this system. They are, from lowest to highest level, microcode, assembly language and BCPL. The microcode and assembly language levels are described in Appendix A hereto. BCPL is a high level, ALGOL-like programming language and is described in a copy-righted publication by Xerox Corporation entitled "BCPL Reference Manual", May 30, 1977, Xerox Palo Alto Research Center.

Although the invention has been described with respect to a presently preferred embodiment, it will be appreciated by those skilled in the art that various modifications, substitutions, etc. may be made without departing from the spirit and scope of the invention as defined in and by the following claims. ##SPC1## ##SPC2## ##SPC3## ##SPC4## ##SPC5## ##SPC6## ##SPC7## ##SPC8## ##SPC9## ##SPC10## ##SPC11##

Claims

What is claimed is:

1. A data processing system comprising: first storage means for storing character font data representative of a plurality of characters, each character being represented by said font data as a bit map of predetermined dimensions, said plurality of characters being stored in an ordered storage sequence; image presentation means for visually presenting an image comprised of preselected ones of said characters on a predetermined background area; second storage means for storing a bit map representation of said image; visual control means for controlling said image presentation means to visually present said image in accordance with the character font data stored in said bit map representation of said image in said second storage means; third storage means for storing a list of identification data for at least some of said preselected characters to be visually presented, said identification data identifying the type and style of each character as well as its desired location on said background area; and data control means for controlling the processing and handling of character font data, said data control means comprising sorting means for sorting the identification data in said third storage means into said ordered storage sequence, accessing means responsive to said sorted identification data for accessing from said first storage means in said ordered storage sequence the character font data for each character identified in said list, and loading means for loading the character font data for each accessed character into said bit map representation in said second storage means at a location defined by the identification data for that character.

2. The data processing system of claim 1, wherein said image presentation means comprises a raster-output-scanned device.

3. The data processing system of claim 2, wherein said raster-output-scanned device is a CRT display.

4. The data processing system of claim 2, wherein said raster-output-scanned device is a ROS printer.

5. The data processing system of claim 1, wherein said first storage means comprises a first random access memory.

6. The data processing system of claim 5, wherein said first random access memory is a magnetic storage medium.

7. The data processing system of claim 6, wherein said second and third storage means respectively comprise first and second storage areas in a second random access memory.

8. The data processing system of claim 7, wherein said second random access memory comprises a solid state memory device.

9. The data processing system of claim 1, wherein said image presentation means comprises a CRT display, said first storage means comprises a magnetic random access memory device, and said second and third storage means respectively comprises first and second storage areas on a solid-state random access memory device.

10. The data processing system of claim 1, wherein said image presentation means comprises a ROS printer, said first and second storage means respectively comprise first and second storage areas on a magnetic random access memory device, and said third storage means comprises a first storage area on a solid-state random access memory device.

11. The data processing system of claim 10, further comprising buffer storage means defined in a second storage area on said solid-state random access memory device, said buffer means storing character font data accessed from said first storage means.

12. The data processing system of claim 11, further comprising fourth storage means for storing a predetermined segment of said a bit map representation of said image, said fourth storage means being defined in a third storage area on said solid-state random access memory device, said data control means controlling the transfer of character font data from said buffer means to said fourth storage means, and said data control means also controlling the transfer of character data between said second and fourth storage means.

13. The data processing system of claim 12, wherein said fourth storage means is utilized to store a segment of a print bit map during formulation of an image for printing by said ROS printer, or to store an entire display bit map during formulation of an image for display by said display means.

14. The data processing system of claim any one of claim 1, 3, 4, 8, 9 or 13 wherein said plurality of characters include Romaji, Hiragana, Katakana and Kanji characters thereby enabling the processing of Japanese language text.

Patent Citations (10)

Patent	Date	Inventor
US3828319	1974-08-01	Owen et al.
US3872446	1975-03-01	Chambers
US3895374	1975-07-01	Williams
US3958225	1976-05-01	Turner et al.
US4079458	1978-03-01	Rider
US4103330	1978-07-01	Thacker
US4103331	1978-07-01	Thacker
US4124843	1978-11-01	Bramson et al.
US4130882	1978-12-01	Swanstrom et al.
US4148098	1979-04-01	McCreight et al.

Abstract

Description