Video Accelerator and Method Using System RAM

The subject matter of this application relates to the subject matter set forth in the utility application METHOD AND APPARATUS FOR CHANGING THE ORIENTATION OF A VIDEO DISPLAY, Ser. No. 07/447,110, filed on Dec. 6, 1989, by Julien T. Nguyen; the subject matter of which utility application is incorporated herein by reference.

This invention relates to video display systems, and more specifically to a method and system for accelerating video display modifications within a generic personal computer architecture.

Traditional personal computer system architectures are structured around a Central Processing Unit (CPU) that communicates across a parallel bus to numerous peripherals and subsystems. The CPU commonly displays data on a video screen by writing the data over the main system bus to a dedicated block of Random Access Memory (RAM) which serves as video or display memory. A Cathode Ray Tube Controller (CRTC), acting essentially as a second CPU or display processor, periodically reads the data from video memory and presents it to a video display along a separate video bus. Substantial delays are introduced by this periodic cycle as the CRTC sequentially reads the memory locations of video memory and presents the stored data to refresh the display. During this refresh, the CRTC has access priority over the video memory, thereby excluding access by the CPU. Video data which is ready to be transmitted from the CPU must wait until the CRTC momentarily relinquishes control before such data can be written to video memory. Access to the video memory must be reestablished for each byte of data transmitted thereto. The consequence of this contention for access to the video memory is that presentation of data for video display is limited in conventional systems by the frequency with which the CPU is able to gain control of the video RAM between refresh cycles, and is therefore largely independent of processor speed.

Additionally, conventional systems commonly require the CPU to perform a read-modify-write sequence for each new byte that is sent to update the video display. This three step sequence is required to allow the CPU to add or subtract video data from the data that is stored for each display pixel, or picture element, without disturbing the stored data for other pixels. To accomplish this task, the CPU must read the byte of pixel data from video memory and analyze it before executing a subsequent write step. One consequence of the read-modify-write sequence is that every change in the data to be displayed requires two accesses to the video memory. The first access is to read the video memory and the second access is to write into the video memory. This double access requirement in conventional systems thus introduces substantial delays into the processing of video displays. Such delays in processing the video display can be easily observed in cursor movement on the video display, for example, when an input pointing device such as a "mouse" is moved. As a specific example, the computer program "Windows 3.0," supplied by Microsoft Corporation of Redmond, Wash., demonstrates a significant delay between rapid mouse movements and the resulting cursor response when the program is run on a conventional personal computer system. Another example of such delays can be observed when a command is given to fill a displayed block image with a solid color. Although the CPU rapidly calculates the coordinates of pixels to be altered, each coordinate must be transmitted to video memory one byte at a time. Between each byte transfer the CPU must wait to regain access to the video RAM. The resulting delay is evidenced by the relatively slow scanning motion that is observed on the display as the block image is filled with the solid color.

In accordance with the present invention, a portion of system RAM is used as a video buffer to reduce the access requirements usually associated with conventional separate video memory to provide faster, more responsive video displays. Specifically, this is accomplished by allocating video buffer space within system memory, by rerouting video display data from video RAM to video buffer memory, by storing parametric data describing the region of video that is to be changed, and by moving a block of data from the video buffer in system RAM to the video RAM. In this manner, the read cycle from video RAM normally required with each video write cycle is completely eliminated. Since video RAM 4 access is much more time consuming than system RAM access, this video acceleration technique provides gains of almost 2 to 1 in the speed of performance and reduces the annoying display artifacts resulting from refresh cycle delays in conventional systems.

FIG. 1 is a block diagram illustrating a conventional computer architecture;

FIG. 2 shows a flow chart illustrating video RAM acceleration in accordance with the present invention; and

FIG. 3 is a block diagram showing the preferred embodiment of the present invention in a conventional computer architecture.

FIG. 4(a) illustrates a four-by-four square of pixels before ninety degree rotation, and FIG. 4(b) illustrates those same pixels after rotation, in accordance with the present invention.

FIG. 5(a) illustrates data resulting from rotation of the data in the lowest row of FIG. 4(a), and FIG. 5(b) illustrates data resulting from rotation of data in the next to the bottom row of FIG. 4(a), in accordance with the present invention.

FIG. 6 illustrates processing flow for transformation of the pixels illustrated in FIG. 4(a) to the transformed block of FIG. 4(b), in accordance with the present invention.

Referring now to FIG. 1, there is shown a block diagram of typical computer architecture for controlling the video display according to the prior art. The Central Processing Unit (CPU) 11 is connected to RAM video memory 13 and RAM system memory 23 by the system bus 21. The video memory 13 is also connected to the CRTC 15 by the video bus 19. In operation, the CPU 11 generates a change in the video display 17 by writing a new byte of video information into video memory 13. This change is accomplished by first reading the contents of video memory 13, then modifying the byte of data stored there, and finally rewriting the new data back into video memory 13. The need for this three step sequence results from the fact that, when modifying a video pixel, the CPU 11 adds or subtracts video data from the video image byte without disturbing other data within the same byte. This protection of existing video data requires reading the image byte from video memory 13 and analyzing it before the subsequent write step is executed.

The CRTC 15 scans video memory 13 periodically and displays the contents of that memory 13 on the video display 17. During this CRTC 15 scan, further access to the video memory 13 by the CPU 11 is disabled until that refresh cycle is completed. The main priority of the CRTC 15 is to continually refresh the video display 17 with information stored in the video memory 13. As a result, there is often significant delay associated with the access to video memory 13 by the CPU 11. The requirement for two accesses to video memory 13 for each modification of the data for the video display 17 that is stored in the video memory 13 while the CRTC 15 may have access thereto results in significant time spent by the CPU 11 waiting for access to the video memory 13 simply to update the video display 17.

Referring now to FIG. 3, in accordance with the present invention, the CPU 11 allocates a section of about 150K bytes in the system memory 23 to act as a buffer 38 between the CPU 11 and the video memory 13, thereby keeping the image to be displayed within the contents of the system memory 23 at all times. Modification to video memory 13 is made by first reading and writing to the system memory buffer 38 instead of by changing display data in video memory 13. Since system memory 23 access has high priority for the CPU 11, there are no wait states or delays introduced during the read-modify-write accesses to system memory 23 in contrast to delays encountered using this same procedure to update video memory 13, as previously described. Once the data for the displayable image is modified within the memory buffer 38 of the system memory 23, its contents may then be written to video memory 13. The data from the system memory 23 that is to be transferred to the video memory 13 may also be transformed in various ways, as later described herein. The conventional read-modify-write sequence in video memory 13 is thereby avoided since the image data modification already occurred in system memory 23 without introducing operating delays in the CPU 11. This use of system memory 23 for buffer storage of image data has the effect of reducing the number of accesses to video memory 13 by about one-half. Since the wait period encountered by the CPU 11 in accessing video memory 13 is a significant portion of the CPU 11 instruction cycle, this scheme of operation according to the present invention provides improvement of about two to one in the speed of operation to update the video display 17.

Referring now to FIG. 2, there is shown a flow diagram of the method in accordance with the present invention. Initially, a portion of the system memory 23 is allocated 31 to operate as a buffer memory for the CPU 11. In allocating system memory 23, the CPU 11 partitions off and protects approximately 150K bytes of RAM in a conventional manner to serve as a video buffer memory 38 that cannot be over-written by other on-going CPU 11 programs and processes. In addition, another portion of system memory 23 serves as a block change register 25, as later described herein.

During normal processing of data to produce a video display, the CPU 11 will encounter an instruction to modify 33 the video display 17. The CPU 11 reads 35 the contents of the buffer memory 38 over the system bus 21. Then, the CPU 11 modifies 37 the contents of the buffer memory 38 and subsequently writes 41 the modified data into the buffer memory 38. At the same time, the block change register 25 is updated 39 in order to keep track of which locations in the buffer memory 38 were actually modified.

Then, the subsequent operation of the CPU 11 is determined 43 by whether or not the modification to buffer memory 38 is complete. If the modification is not complete, processing returns to step 35 in which the CPU 11 reads video data from buffer memory 38. If the modification is complete, the CPU fetches 45 the updated block change register 25 and, based upon the contents of that register 25, moves the modified video data from the buffer memory 38 to the corresponding location in video memory 13 without requiring additional reads of the data in video memory 13. The block change register 25 points to the first location in buffer memory 38 containing a byte of modified video data. The CPU 11 next reads 47 this first byte of modified video data from the system memory and applies a data transform 48 on this block of video data being moved. The specific type and steps of the transform 48 depend largely on the type of display for which video data is accumulated in video memory 13. For a conventional raster-type video display terminal 17, this transform may comprise the steps of converting sequentially-arranged data to a format in the video memory which orients bytes of the data over the finite lengths of successive horizontal video scan lines. If the display is, for example, a line printer, then the transform may comprise alternating the sequence of data formatted for forward and backward printing in alternate lines to facilitate printing of the data during alternating forward and backward scanning operation of the printer. Various other embodiments of this transform may include the transform of data for operation of a video display in `portrait` or `landscape` mode, as described below and in the aforecited related application.

The CPU attempts to transfer the block of video data in the buffer memory 38 to video memory 13 by first polling video memory 13 to check its availability 49 for access. If the video memory 13 is engaged with the CRTC 15 in a video refresh cycle, the CPU 11 waits until the cycle is completed. When video memory 13 is available for access, the CPU 11 then writes 51 a byte of video data into video memory 13. If the block move is completed, the CPU 11 then resumes processing other system functions until a subsequent modification 33 of the display is encountered. However, if the block move is not completed, the CPU 11 reads 47 the contents of the next memory location and again attempts to transfer the modified video data in the manner as previously described.

Following the block move 45, the CRTC 15 refreshes the video display 17 based upon the new contents of video memory 13. In updating and writing modified video data, the read-modify-write sequence of steps 33 through 51 are performed using the fast-access system memory 23 rather than the video memory 13 to which the CPU 11 has only lower access priority.

As already discussed, a data transform 48 may be performed on a block of video data in accordance with the present invention. Referring now to FIGS. 4(a) and 4(b), this transform may include a ninety degree rotation of the displayed video data. FIG. 4(a) illustrates a four-by-four square of pixels before such rotation, and FIG. 4(b) illustrates those same pixels after rotation.

Assuming that each pixel is defined by two bits and that each row of four pixels is defined by a single byte, a conventional method for performing the pixel rotation would require copying the byte containing the pixel, masking out all bits of that byte not associated with the pixel, shifting the bits as required to correspond to the new position of the pixel, and performing an OR operation to write the byte containing the shifted pixel into the destination byte. This method may be rather time consuming because each of the 16 pixels in the block must be processed as described above, one at a time. A conventional technique using bit-fields rather than the masking, shifting and OR operations described above may yield some improvements in efficiency, but still requires separate operations for each pixel.

A transform in accordance with the present invention involves the use of a lookup table to permit processing of an entire byte of information at one time. Each byte of pixel data is used as an index to a lookup table, and separate lookup tables are used for each destination column. FIG. 5(a) illustrates the data resulting from application of the bottom row 60 of FIG. 4(a) to the lookup table for the leftmost destination column, and FIG. 5(b) illustrates the data resulting from application of the next to the bottom row 62 of FIG. 4(a) to the lookup table for the next to leftmost destination column. To transform all of the pixel information of the four-by-four block of pixels illustrated in FIG. 4(a) to the transformed block of FIG. 4(b), the processing flow illustrated in FIG. 6 is used. The first step is for the byte containing the bottom row 60 of pixels (p.sub.00 p.sub.01 p.sub.02 p.sub.03) in FIG. 4(a) to be read 70. This byte is used in step 72 as the index to an entry in a lookup table designated for destination column 0, since upon transform all of these pixels will reside in the leftmost column of the block of FIG. 4(b). In step 74, the corresponding table entry is written as the first component of the transformed block (also illustrated as FIG. 5(a)). Next, step 76 reads the second from the bottom byte of data from the original block (pixels p.sub.10 p.sub.11 p.sub.12 p.sub.13 in FIG. 4(a)), step 78 looks up the corresponding entry in the lookup table for column 1 of the transformed data, and step 80 writes that information (shown as FIG. 5 (b)) into the transformed data block by performing an OR operation with the partial transformed data already written in step 74. Similarly, the third and fourth rows of data are read, the corresponding table entries obtained, and the partial transformed data written to the transformed data block in steps 82 through 92.

The use of a lookup table is relatively slow if measured on an instruction by instruction basis, because the lookup table entries must be obtained from memory. However, an overall time savings is achieved because only one such operation is required to transform four pixels. Furthermore, conventional memory caching techniques may be used to reduce the amount of time required for the lookup operations.

Different pixel bit depths or memory limitations may call for the use of different-sized data blocks to perform this transformation. For instance, pixels defined by only one bit may be efficiently processed using data blocks representing eight by eight squares of pixels. Each row of eight pixels may be represented by a single byte which, when transformed, will result in a single column of transformed data. Such a scheme may provide even greater efficiencies if separate tables are not provided for each column, but a single large table is used, and only the pertinent output column information from that table is written to the transformed data block, depending on which row the input information was obtained from. For instance, the one byte input word from the third row would be applied to the lookup table, and the corresponding entry would by a full eight byte square of information. However, the only pertinent information from that entry would be the third column, so the other columns of information would simply be masked out before the information was written (via an OR operation) into the transformed block of data. Further efficiencies may be achieved by writing the partial transform destination bytes to two 32-bit data registers, so that the number of memory calls is reduced during manipulation. After the transformation is complete, the fully transformed data may then be written to the destination locations.

In the preferred embodiment, pixels defined by two bits are transformed from a eight by four pixel rectangle to a four by eight pixel rectangle. Although the environment of the preferred embodiment contains sufficient registers to perform eight by eight rotation, the resulting instruction algorithm would exceed the size of the available memory cache and therefore execute comparatively more slowly. In the preferred embodiment, each source row of eight pixels requires two bytes, and processing is performed as described above, except that processing uses two-byte, rather than one-byte, words. Separate lookups are performed on each of the two bytes, the appropriate table entries are masked out so that only the pertinent column information is written, and the partial transform destination bytes are stored in data registers until the transformation is complete.

In cases where pixels are each defined by four bits, eight by four pixel blocks are transformed to four by eight pixel blocks, but four bytes are required for each row of eight pixels. Separate lookups are performed for each of the four bytes, and the appropriate table entries are masked out. Four 32-bit data registers are used to store the partial destination bytes during transformation, and after transformation is complete, the transformed data is written to the destination locations.

As a further disclosure, examples of lookup tables for ninety degree transformation of one-bit, two-bit and four-bit pixels as described herein are provided as an appendix to this specification. The numbers in the appended tables are in hexadecimal format.

Therefore, the use of a buffer memory segment of the system memory rather than a video memory for updating video data in accordance with the present invention reduces video refresh cycle delays and accelerates the modification of video data for display.