Abstract:
The present invention provides a fast bit blitter method and circuit which uses less logic than do prior art bit blitter circuits. A circuit built in accordance with the present invention includes four main components each of which only has as many bit positions as does the data bytes that are being shifted. The four main components are a storage register, a multiplexer bank, a multiplexer selector and a barrel shifter. As data words are serially read out of memory, they are temporarily stored in the register. The multiplexer gates selected bit from the word stored in the register, together with selected bits from the next word that appears on the data bus to the barrel shifter. The barrel shifter does the appropriate shifting. Alternatively, the barrel shifter can be located before the multiplexer in the data path. The amount of time required to shift an image using the present invention is approximately the same amount of time required with the prior art, however, the amount of hardware required is substantially less.

Description:
FIELD OF THE INVENTION 
     The present invention relates to digital computers and more particularly to a system and method for shifting data across byte boundaries. 
     BACKGROUND OF THE PRIOR ART 
     There are many commercially available text books that explain the general operation of displays for personal computers. Two such books are &#34;Inside the IBM PC&#34; by Peter Norton, published by Prentice Hall Press, 1986, and a book entitled &#34;Programmer&#39;s guide to PC and PS/2 Video Systems&#34; by Richard Wilton, Microsoft Press, 1988. The background information in these books is hereby incorporated by reference and no explanation of the general operation of video displays will be given herein. 
     As explained in the above cited references, computers generally store video data in multibit bytes. For example, many computers use eight bit bytes. Each bit in a byte can represent the &#34;on&#34; or &#34;off&#34; status of one pixel on the display. Thus an eight bit byte can represent the &#34;on&#34; or &#34;off&#34; status of eight pixels on the display. 
     One way to display alpha-numeric characters in such systems is to mandate that each character will not cross a byte boundary. Thus each character or letter fits within a block which is for example, eight bits wide and several lines high. In such a system wide characters and narrow characters must fit within the same size box. 
     More sophisticated systems require that characters cross byte boundaries. In these more sophisticated systems a character can be positioned starting at any bit position across the screen. Circuitry generally known in the art as &#34;Bit Blitter&#34; circuitry is provided to move characters or other images across byte boundaries. 
     Existing bit blitters generally utilize a shift register which is twice as wide as the main data path. For example if the system includes eight bit data words, a 16 bit shift register is used. FIG. 1A shows an example of a prior art bit bitter circuit. In the circuit shown in FIG. 1A an image is shown as going from a location in memory bank M1-1 to a shifted position in a memory bank M2-1. In many practical systems memory bank M1-1 and memory bank M2-1 would in fact be the same memory; however, they are shown separate in FIG. 1A for ease Of explanation. 
     In the circuit shown in FIG. 1A data from the image in memory bank M1-1 goes through the memory register MR1-1 into two registers R1-1 and R2-1. Adjacent bytes from memory bank M1-1 are placed in registers R1-1 and R2-1 and then both bytes from registers R1-1 and R2-1 are transferred to shift register S1-1. The data is shifted the desired number of positions and then gated out of the eight high order positions of the shift register to memory register MR2-1. As shown in FIG. 1A the positions of the characters &#34;L&#34; and &#34;T&#34; are shifted by four bit positions as they move from memory bank M1-1 to memory bank M2-1. It is noted that in memory bank M2-1 each of the characters &#34;L&#34; and &#34;T&#34; crosses a byte boundary. 
     Circuitry which is not shown herein is usually provided to transfer data between registers R1-1 and R2-1 so that a particular byte of data only need be read out of memory M1-1 once. 
     The operations which occur as byte 2, byte 3, and byte 4 are shifted as shown in FIG. 1B. The special initialization operations that occur with byte 1 are not shown since they are not relevant to the present invention. During the steps designated Step One, Step Two and Step Three, the contents of each of the Registers R1-1, R2-1, and MR2-1 is shown. Furthermore the contents of shift register S1-1 is shown in each step both before and after the shift operation. The data in registers R1-1 and R2-1 coincides with the data in memory bank M1-1, the data in register MR2-1 coincides with the data in memory M2-1. FIG. 1B also shows the data in the shift register S1 before and after the shift operation. 
     An example of a commercially available Bit Blitter is a circuit marketed by National Semiconductor Corporation and designated the &#34;DP8511 BITBLT Processing Unit&#34;. As shown in the specification sheet published by National Semiconductor Corporation for the DP8511 circuit is designed to handle 8 bit bytes and it includes a sixteen bit shift register. 
     Other prior art bit blitters implemented entirely in software. Bit blitters implemented in software are inherently slower than are bit blitters implemented in hardware. 
     SUMMARY OF THE INVENTION 
     The present invention provides a fast bit blitter method and circuit which uses less logic than do prior art bit blitter circuits. 
     A circuit built in accordance with the present invention includes four main components each of which only has as many bit positions as does the data bytes that are being shifted. The four main components are a storage register, a multiplexer bank, a multiplexer selector and a barrel shifter. As data words are serially read out of memory, they are temporarily stored in the register. The multiplexer gates selected bits from the word stored in the register, together with selected bits from the next word that appears on the data bus to the barrel shifter. The barrel shifter does the appropriate shifting. The shifter can either be located either before or after the multiplexer in the data path. 
     The amount of time required to shift an image using the present invention is approximately the same amount of time required with the prior art, however, the amount of hardware required is substantially less. 
    
    
     DESCRIPTION OF THE DRAWINGS 
     FIG. 1A shows a prior art circuit. 
     FIG. 1B is a table showing how the circuit in FIG. 1A moves specific bits. 
     FIG. 2A shows a logical diagram of a preferred embodiment of the invention. 
     FIG. 2B is a table showing how the circuit in FIG. 2A moves specific bits. 
     FIG. 3 is a circuit diagram showing the details of how the bank of multiplexers are controlled by the selector. 
     FIG. 4 is a circuit diagram of a single multiplexer stage. 
     FIG. 5 is a circuit diagram of an alternate embodiment of the invention. 
    
    
     DETAILED DESCRIPTION 
     A preferred embodiment of the present invention is shown in FIG. 2A. The embodiment shown in FIG. 2A includes an input memory M1, an output memory M2, memory registers MR1 and MR2, a temporary storage register R, a multiplexer MX, a barrel shifter S, a selector circuit SE, and a two&#39;s complement circuit T. 
     For ease in explanation two memory banks M1 and M2 are shown in FIG. 2A. Memory bank M1 contains an original image of the letters &#34;L&#34; and &#34;T&#34; and memory bank M2 contains a shifted image of the letters &#34;L&#34; and &#34;T&#34;. In FIG. 2A, the memory M1 and M2 are shown as having six rows, each row has thirteen bytes, and each byte has eight bits. The bit positions in the memories M1 and M2 are shown by the dashed lines. Naturally it should be understood that most actual computer memories will be much larger than the memories as shown herein; however, the size of the memory is not relevant to the present invention and memories of the size shown are sufficient to explain the present invention. It should be noted that in the shifted image in memory bank M2, the letters &#34;L&#34; and &#34;T&#34; cross a byte boundary. 
     As explained previously in many practical applications, both the original image and the shifted image would be in the same memory bank: however, whether the two images are stored in the same or in different memory banks is not relevant to the present invention. The situation where one desires to place the shifted image not only in the same memory bank as the initial image but in exactly the same location in memory as the location of the initial image will be discussed later. 
     The bytes of data come out of memory M1 serially via a memory register MR1 and the shifted data bytes are serially placed in memory M2 via a memory register MR2. This type of memory &#34;read out&#34; and &#34;read in&#34; operation is conventional and will not be explained further. 
     In the embodiment shown in FIG. 2A, each byte of data has eight bits. In FIG. 2A the bytes and bits are labeled across the top of memory M1 and the rows in the memory M1 are labeled along the left hand side of the memory. 
     The circuit shown in FIG. 2A has a register R, a bank of multiplexers MX and a shifter S. The register R, the bank of multiplexers MX and the shifter S are each eight bits wide. This is in contrast to the prior art systems much of that which is shown in FIG. 1 where the shifter is sixteen bits wide. The multiplexer MX is controlled by a selector SE and barrel shifter S has a two&#39;s complement control circuit T. 
     The barrel shifter S always shifts to the right. A left shift is accomplished by shifting right an appropriate number of positions. For example, a left shift of 2 is achieved by shifting to the right 6 positions. This is a conventional technique. 
     Selector SE receives three binary signals S0, S1 and S2 which indicate the amount of shift desired and a direction signal that indicates the direction of the shift. Selector SE decodes the signals on lines S0, S1, and S2 into seven control signals for the bank of multiplexers MX. 
     Two&#39;s complement circuit T receives the three binary signals S0, S1 and S2 and a direction signal. Circuit T performs the following functions: 
     (a) passes signals S0, S1, and S2 directly to shifter S when a right shift is being performed, 
     (b) generates a two&#39;s complement of the signals on lines S0, S1 and S2 and passes the complemented signals to shifter S when a left shift is desired. 
     The manner in which a barrel shifter designed to do a right shift will perform a left shift when given two&#39;s complement input signals is well known and it will not be described further herein. 
     The details of the bank of multiplexers MX and the manner in which the output of selector SE controls the multiplexer is shown in FIG. 3. The selector SE generates signals on lines L1 to L8 in response to the signals on lines S0, S1 and S2. Signals on lines L1 to L8 in turn control multiplexers MX1 to MX8 each of which either gates a bit from byte W1 or W2 to the output W3. The signals generated by selector SE in response to signals S0, S1 and S2 is shown in the following tables: 
     
                       TABLE A______________________________________For a Right Shift: InputShift Signalsdesired SO      S1    S2    L1  L2  L3  L4  L5  L6  L7  L8______________________________________0     0       0     0     0   0   0   0   0   0   0   01     1       0     0     1   0   0   0   0   0   0   02     0       1     0     1   1   0   0   0   0   0   03     1       1     0     1   1   1   0   0   0   0   04     0       0     1     1   1   1   1   0   0   0   05     1       0     1     1   1   1   1   1   0   0   06     0       1     1     1   1   1   1   1   1   0   07     1       1     1     1   1   1   1   1   1   1   0______________________________________ 
    
     
                       TABLE B______________________________________For a Left Shift: InputShift Signalsdesired SO      S1    S2    L1  L2  L3  L4  L5  L6  L7  L8______________________________________0     0       0     0     0   0   0   0   0   0   0   01     1       0     0     0   0   0   0   0   0   0   12     0       1     0     0   0   0   0   0   0   1   13     1       1     0     0   0   0   0   0   1   1   14     0       0     1     0   0   0   0   1   1   1   15     1       0     1     0   0   0   1   1   1   1   16     0       1     1     0   0   1   1   1   1   1   17     1       1     1     0   1   1   1   1   1   1   1______________________________________ 
    
     It is important to note that the present invention does not add any additional delay into the operation of the circuit even though the present invention only requires a shift register which is one byte wide (in contrast to the prior hardware technique art which requires a shift register which is two bytes wide). Thus, the present invention requires less circuitry than does the prior art and it does not increase the time required to operate on the data. 
     The manner in which the entire circuit operates can be summarized as follows: The input data from memory register MR1 is sent to an end around rotator which consists primarily of register of MR1, temporary register R, multiplexer MX, and barrel shifter S. Every byte which comes out of register MR1 is thus combined with some bits of the previous byte and then written to the destination MR2. 
     It should specifically be noted that only one read cycle is required regardless of the shift direction and the shift amount. 
     The amount of hardware required and the amount of delay in the circuit can be defined by considering a one bit multiplexer such as that shown in FIG. 4. The one bit multiplexer shown in FIG. 4 has two AND gates 41A and 41B, and OR gate 42 and an Inverter 43. The circuit is a conventional one bit multiplexer and it will be used herein to explain the amount of delay introduced by the present invention in comparison to the prior art. In the subsequent discussion herein, the time required for a signal to pass through the multiplexer shown in FIG. 4 will be considered to be one unit of delay. Furthermore, the amount of hardware in the circuit shown in FIG. 4 will be considered to be one unit of hardware. The circuit in FIG. 4 is not part of the embodiment--it is shown here merely for comparison purposes. 
     It is known that a 16 bit (two Byte) multiplexer introduces four units of delay whereas an 8 bit (one byte) multiplexer introduces three units of delay. Selector SE and multiplexer MX each introduce one unit of delay. A comparison of the delay introduced by the prior art and the delay introduced by the present invention is given by the &#34;Table C&#34; below. Table C also compares the amount of hardware required by the prior art in comparison to the amount of delay required by the present invention. 
     
                       TABLE C______________________________________  Prior Art         Present Invention  Delay Hardware    Delay   Hardware______________________________________Shift Reg.    4       4 × 16 = 64                        3     3 × 8 = 24Decoder                      1        8Selector                     0        8Tota1    4       64          4        40______________________________________ 
    
     The two&#39;s complement circuitry is not included in the above comparison since it is required by both circuits. Furthermore, since the complementing operation is performed infrequently, in many practical applications, the complementing will be done under program control and no additional hardware will be provided for this function. It is herein shown as a hardware block primarily for the ease of explanation. How the complementing operation is performed is not related to the present invention. 
     It is noted that the special operations required for handling the first byte in each row and for handling the last byte in each row are not explained since they are not relevant to the present invention and they can be done in the same way that they are done in the prior art. 
     The operations required when data is being replaced in the same place in memory rather than in a different place in memory are not explained since they can be handled the same way that such operations are handled in the prior art. 
     As illustrated in FIG. 2A and as described above, in every instance selected bits are taken from a first byte and added to selected bits of a second byte across a byte boundary. The first byte is read from memory M1 and stored in register MR1. The second byte, logically contiguous to the first byte across a byte boundary, is read from M1 into MR1. The first byte is stored in turn to register R. Word line W2 provides an output of register MR1; the second byte, to the multiplexer MX; while word line W1 provides an output of register R to the multiplexer MX. For a right shift of 4 bits, as illustrated, 4 bits are taken from the right-most positions of the first byte, stored in the register R, and 4 bits are taken from the left-most bits of the second byte, stored in register MR1. The multiplexer MX actually selects the desired bits in relation to the byte boundary between them. As will be readily appreciated, multiplexer MX always provides 8 bits to barrel shifter S. Thus, for a 4 bit shift, 4 bits are selected from the first byte and combined with 4 bits from the second byte. As the amount of shift decreases, fewer bits are taken from the first byte, and more bits are taken from the second byte. Conversely, as the amount of shift increases, more bits are selected from the first byte with correspondingly fewer bits selected from the second byte. In practical terms, the first byte becomes a source byte for selected bits to be added to a target byte, referred to above as the second byte. 
     To facilitate an abstraction of the above-described procedure, the following events occur. As byte #3 of FIG. 2A is loaded into register MR1, byte #2 is loaded in turn into register R. Thus, byte #3 becomes a new target as byte #2 becomes a new source. The same relative bit positions of selected bits of byte #&#39;s 2 and 3 are chosen in the same fashion as the selected bit positions of bytes #&#39;s 1 and 2, respectively. If the bit positions are numbered logically beginning at each byte boundary across which selected bits from a source to a target will be shifted, it becomes simpler to abstractly state the procedure. For instance, a shift of k bits across a byte boundary between two logically contiguous bytes each having a particular number N of bits, requires that the following bits be chosen: from the source byte, the first k bits relative to the byte boundary will be selected. These k bits will be combined with enough bits of the target byte to provide a total number of bits equal to the particular number N bits. Thus, N-k bits are chosen from the target byte. Specifically, the first N-k bits of the target relative to the byte boundary are combined with the k bits of the source to provide the total number N bits. This is true for a left shift or a right shift. For a left shift, it is readily apparent that byte #13 of FIG. 2A would be read into register MR1. Byte #12 would be read into register MR1, thereby moving byte #13 into register R. Bits are selected from byte #13 in register R and added to bits of byte #12 stored in register MR1. After the bits are combined, byte #11 is read into register MR1, and byte #12 is moved to register R. This corresponds to the description above with register MR1 storing the target byte, register R storing the source byte, and the target byte being &#34;cycled&#34; to become a new source byte as a new target byte is loaded from memory M1. 
     FIG. 5 shows an alternate embodiment of the invention. The various components in the embodiment in FIG. 5 are designated by letters followed by the number 5. The letters correspond to the letters used to designate the similar component in FIG. 24 and the number indicates FIG. 5. 
     In the embodiment in FIG. 5, the shift register S-5 is located in front of both (a) the temporary storage register R-5 and (b) multiplexer MX-5. The memories M1 and M2 are not shown in FIG. 5 since they are identical to the memory shown in FIG. 2A. In the second embodiment the selector SE-5 and the two&#39;s complemant circuit T-5 are identical to the corresponding components in the first embodiment. 
     The system shown in FIG. 5 operates in substantially the same manner as the previously described system; however, the function of previously given tables A and B is reversed. 
     With the embodiment in FIG. 5, Table A gives the input signals for a &#34;right&#34; shift and table B gives the input signals for a &#34;left&#34; shift. 
     The embodiment shown in FIG. 5, has one advantage over the embodiment shown in FIG. 2, namely, the operation associated with the first byte in a row can be handled more easily. Assume for example that characters are being shifted right four bit positions and assume that the first four bit positions in destination memory M2 have information stored therein which is to remain unchanged since the first bit position in memory M1 will be placed in memory position five in memory M2. The operation on the first byte proceeds as follow: the line indicating a shift of zero is activated and the first byte is read from memory M2 into register R-5. Now when the first byte is read from memory M1, it can be combined with the byte in register R-5 in a normal manner to produce the desired result. The same final result with respect to the first byte can be obtained with the first embodiment; however, using the first embodiment additional steps of moving the data under conventional program control are required. 
     While the invention has been particularly shown and described with reference to preferred embodiments thereof, it will be understood bY those skilled in the art that changes in form and detail may be made therein without departing from the spirit and scope of the invention.