Abstract:
In circuitry which transfers data in streams in which a plurality of individual discrete groups of data are all addressed to the same address, apparatus for manipulating the data appearing in streams including a manipulation engine responsive to some portion of each group of the data transferred to cause the data to be manipulated in a particular manner.

Description:
This is a continuation of application Ser. No. 07/815,817, filed Dec. 30, 1991, now abandoned. 
    
    
     BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     This invention relates to the processing of data and, more particularly, to methods and apparatus for combining or otherwise manipulating a plurality of streams of data. 
     2. History of the Prior Art 
     The typical computer system sends each word of data to a particular address unique to that word. The word (or less) of data may be combined with another word or otherwise manipulated depending on the instruction for the particular operation. 
     The necessity of dealing with the addressing and manipulation of each word requires a good deal of the time involved in computer operations. In order to increase the speed of operation of computers, arrangements have been devised which transfer large numbers of words together in blocks. These arrangements allow a computer system to address all of the large number of words as a stream of data to be sent to an address at a destination. At the destination, the information is typically transferred to sequential addresses. These arrangements speed the operations of computers by which data is transferred. 
     However, even though the transfer of the data in blocks or streams has been substantially accelerated, if the data is to be manipulated in some manner such as by combining it with data from other streams of data, that operation still has to be accomplished on a word by word basis once the data arrives at its destination. The simple transfer of the data in streams would be substantially enhanced for many purposes were there an ability to combine in various ways a plurality of streams of data to produce single streams where in stream form. In this way, the individual operations required to manipulate words of data and combine those with other words of data could be bypassed in many instances. 
     For example, where a first stream of data describes a particular picture which is to be displayed on the output of a display device, and a second stream of data describes a second picture which is to be displayed on the output of the same display device at the same time, it would be very useful if the pixel data in the two streams could be combined in a single operation while still in the two streams rather than in single word manipulations at the destination. Combining data while in streams would help accelerate various computer operations and be useful where operations need to be accomplished in real time. Combining data while in streams would allow the manipulation of data to occur rapidly enough to handle real time operations. 
     SUMMARY OF THE INVENTION 
     It is, therefore, an object of the present invention to provide apparatus for combining streams of data. 
     It is another, more specific object of the present invention, to provide apparatus for combining streams of data in a plurality of different ways. 
     These and other objects of the present invention are realized in circuitry which transfers data in streams in which a plurality of individual discrete groups of data are all addressed to the same address, where the circuitry includes apparatus for manipulating the data appearing in streams comprising a manipulation engine responsive to some portion of each group of the data transferred to cause the data to be manipulated in a particular manner such as by multiplying the data by a value or combining it with the data in another stream of data. 
     These and other objects and features of the invention will be better understood by reference to the detailed description which follows taken together with the drawings in which like elements are referred to by like designations throughout the several views. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a diagram illustrating the bits of a word of data defining a pixel to be displayed at the output of a particular computer system. 
     FIG. 2 is a table illustrating a plurality of different desirable combinations of data accomplished by the present invention. 
     FIG. 3 is a block diagram illustrating a general outline of an arrangement in accordance with the present invention. 
     FIG. 4 is a block diagram illustrating a first circuit used in carrying out the invention. 
     FIG. 5 is a block diagram illustrating another circuit used in carrying out the invention. 
     FIG. 6 is a truth table useful in understanding the operation of the invention. 
    
    
     NOTATION AND NOMENCLATURE 
     Some portions of the detailed descriptions which follow are presented in terms of symbolic representations of operations on data bits within a computer memory. These descriptions and representations are the means used by those skilled in the data processing arts to most effectively convey the substance of their work to others skilled in the art. The operations are those requiring physical manipulations of physical quantities. Usually, though not necessarily, these quantities take the form of electrical or magnetic signals capable of being stored, transferred, combined, compared, and otherwise manipulated. It has proven convenient at times, principally for reasons of common usage, to refer to these signals as bits, values, elements, symbols, characters, terms, numbers, or the like. It should be borne in mind, however, that all of these and similar terms are to be associated with the appropriate physical quantities and are merely convenient labels applied to these quantities. 
     Further, the manipulations performed are often referred to in terms, such as adding or comparing, which are commonly associated with mental operations performed by a human operator. No such capability of a human operator is necessary or desirable in most cases in any of the operations described herein which form part of the present invention; the operations are machine operations. In all cases the distinction between the method operations in operating a computer and the method of computation itself should be borne in mind. The present invention relates to a method and apparatus for operating a computer in processing electrical or other (e.g. mechanical, chemical) physical signals to generate other desired physical signals. 
     DETAILED DESCRIPTION OF THE INVENTION 
     Referring now to FIG. 1, there are shown three words of binary data. The particular words illustrated include data defining a particular pixel to be presented on an output display of a computer system capable of displaying twenty-four bit color output. The words illustrated each include thirty-two bits of binary data divided into four bytes. Three of these bytes store information related to a particular one of the three (red, green, and blue) shades of color which when combined define the color of the particular pixel. The other byte of data stores a quantity referred to as &#34;alpha&#34; which in various ways may define an operation to be performed with regard to the pixel. Since a byte provides eight bits of binary information, 256 individual binary numbers may be stored as alpha values. Typically, if all of the bits are ones, the alpha value is referred to as a &#34;one,&#34; while if all of the bits are zeroes, the alpha value is referred to as &#34;zero.&#34; 
     There are various operations which it is often desirable to accomplish on the data which is to be presented on an output display before the data is presented. It would be very useful if these manipulations could be accomplished on streams of data rather than on individual data words. For example, when two pictures are to be displayed on a computer output display so that one picture is on top of the other, the data describing the two pictures (word 1  and word 2 ) may appear in two individual streams. The amount by which the background picture (word 2 ) shows through the foreground picture (word 1 ) may be controlled by a binary alpha value which varies between decimal zero and 256 to describe the transparency of the foreground picture. In the preferred embodiment and typically in dealing with twenty-four bit color application programs, if the alpha value of each of the foreground pixels is all ones (a &#34;one&#34;), the foreground picture is entirely opaque and the background cannot be seen through it. On the other hand, if the alpha value of the foreground is some value between all zeroes (a &#34;zero&#34;) and all ones (a &#34;one&#34;), then some amount of the background picture shows through the foreground picture. It is desirable to combine the two streams of data which define two pictures using the alpha values in a manner to cause a single stream of data (wordout) to result which provide the desired picture of pixels to be displayed. 
     Another operation of which certain computers are capable is termed anti-aliasing. Essentially, it has been found that straight edges formed of pixels running diagonally on an output display may be made to appear less jagged if the pixels defining the outer edge of the straight edge are rendered at varying lower levels of intensity. This may be accomplished for any single picture stream by providing the pixel intensity value as the alpha value for each pixel. When two pictures utilizing this technique for intensity determination are overlaid on an output display, it is necessary to combine the two values for the pixels in the two streams used to determine how each edge pixel is to be displayed. In accomplishing this operation, the alpha values of the two pixels are used to determine the final intensity values of each of the resulting pixels. 
     Another desirable way in which two pictures may be combined is exemplified by the television news broadcast of the weather. Often, when presenting television, it is desirable to present one picture such as a weatherman over a background such as a satellite view of the weather without the background showing through at all. This must often be accomplished with rapidly moving pictures as in the television weather picture case. This is typically called a weatherman mode of operation. Since modern computers are being used to present television pictures, the ability to combine pixels in this manner is desirable; and it is especially desirable that the combination be accomplished in real time. This may be accomplished using a picture of the weatherman in front of a solid colored background. When the background color is recognized, the background picture is substituted for it. In this manner, the weatherman will appear superimposed on the weather map background. When in the weatherman mode, the alpha value of foreground pixels is monitored so that when the solid color for which the background pixel is to be substituted is found, it may be overwritten by the background. 
     In modern multitasking computer systems, a number of different application programs are often displayed simultaneously in different windows on an output display. The pixels for the different windows are often presented in separate streams. In order to accomplish the presentation of the different pictures within the different windows, the pictures are often clipped so that only data falling within the boundaries of the windows is displayed. A method of combining two streams of data has been developed in accordance with the present invention by which alpha values may be used to determine when a picture is to be clipped in this manner. For example, by providing an alpha value for a background pixel with a value of zero, the output at the data pixel position may be clipped. 
     Another useful operation which may be accomplished on streams of data is to apply some particular values to all of the pixels of one picture to be displayed so that each pixel is associated with a value. These values might be the same or different for the different pixels. A mode which would allow the multiplication of each color shade byte in a single stream of pixels would be very desirable. This may be accomplished by using the alpha value of a pixel as a multiplier. 
     Of course, this and other of the aforementioned operations may be combined to more rapidly accomplish the various combinations of stream data. The different possible operations which have just been discussed are listed in the table of FIG. 2. In this table, each of the operations is designated by name and the mathematical operation performed in order to obtain the desired result is given. 
     As may be seen, in a transparency mode each shade value of the foreground is added to the shade value of the background multiplied by one minus the alpha value of the foreground. In this manner, the alpha value of the foreground directly controls how much of the background shows through for each of the shades of color in the final pixel. The same operation takes place with respect to the alphas values of the pixels. Thus, the final alpha value is the initial foreground alpha value plus the quantity one minus the foreground alpha value multiplied by the background alpha value. 
     In a coverage mode which may be used for clipping of images, if the sum of the foreground and background alpha values is equal to one or less, the two shade values for each shade are added together and the two alpha values are added together to determine the shade and the saturation of the final pixel. Thus, the final color is determined by adding the shade values together (i.e., red plus red, green plus green, blue plus blue); and the intensity of the pixel is the combined intensity of the two pixels. This also allows the anti-aliasing control to be achieved where two pictures overlap one another. 
     If in the coverage mode the total of the alpha values is greater than one signifying that the intensity level would be brighter than maximum, then the alpha value for the foreground pixel is used to control the shade values so that they are combined in the same manner as are the values in the transparency mode. The alpha value of each combined output pixel, however, is assigned a maximum value (one). 
     In a weatherman mode, if the color values are greater than some threshold value, then the alpha of the foreground pixel is assigned the value of one. By choosing a particular usually solid color as a threshold value, when that color is detected in the foreground a different background pixel may be substituted so that the background shows through at any position where that foreground color exists. 
     In an alpha override mode, if the alpha value of the background is a zero, then the alpha value of the combined pixel is a zero so that no pixel is presented and clipping occurs. 
     In a premultiply mode, the value of each shade in one stream is multiplied by the alpha value. This operation may be extended so that the premultiply operation occurs before some other operation by which streams of data are manipulated. For example, the coverage mode may be used with the premultiply mode. This combining multiplies each shade value of the foreground stream by its alpha value if the alphas values of the two pixels sum to less than one. Where the alphas are greater than one in total, the combining produces the same result as the transparency mode alone. 
     FIG. 3 describes in block diagram form an arrangement for accomplishing the various manipulations of the data of the two streams of information in accordance with the present invention. In FIG. 3, a first stream of data is addressed to and appears at a stream 1 input terminal to a first-in first-out circuit (FIFO) 10. A second stream of data is addressed to and appears at a stream 2 input terminal to a FIFO 12. Each of the FIFOs 10 and 12 has a sufficient number of memory elements to store the data elements (such as words) of the particular stream in the sequence in which they appear. 
     The two streams of information are in the form described above in which the entire stream of data is addressed to the address of the first element of data and the remaining elements appear in sequence following one another. The individual elements of data are to be combined or otherwise manipulated while in the form of streams in one of the ways described above. As the individual elements of data appear they are stored in the two FIFOs 10 and 12 so that individual elements of each are available for use simultaneously. In this manner, one element of data from stream 1 and one elements of data from stream 2 may be manipulated together in the manner that the operation indicates. 
     One element of data (e.g., a red/green/blue pixel value) from each stream may then be manipulated by a manipulation engine 14 to accomplish the particular desired operation. Once the operation has been accomplished, the combined data element is transferred to a third FIFO 16 which stores the combined data elements in the sequential order in which the data elements of the original streams appeared. Like the FIFOs 10 and 12, the FIFO 16 has a sufficient number of memory elements to store the data elements of the combined stream in the sequence in which they appear. From the FIFO 16, the new stream may be transferred for further use within the computer system. 
     FIGS. 4 and 5 are block diagrams of circuits which may be utilized in a manipulation engine 14 such as that shown in FIG. 3 for providing the results defined in FIG. 2. FIG. 6 is a truth table describing the various signals applied to the circuits of FIGS. 4 and 5 in order to obtain those results. 
     FIG. 4 illustrates a circuit 40 which provides the desired results for combining the alpha portions of color pixels. FIG. 5 illustrates a circuit 50 which provides the desired results for combining any one of the three red, green, or blue portions of color pixels. The circuitry illustrated in FIG. 5 would therefore be reproduced for each of the three shades of color in a manipulation engine 14 such as that of FIG. 3. 
     Referring to FIG. 4, the circuit 40 is shown to include an adder circuit 41. The adder circuit 41 receives input signals from a multiplexor 42 and a multiplier circuit 43. The multiplexor circuit 42 receives as input signals the alpha value of the first stream a 1  and a value of zero; one or the other of these signals may be chosen by a signal Asel 1 . The multiplier circuit 43 receives as input the output signals from a pair of multiplexors 45 and 46. The multiplexor circuit 45 receives as input signals the inverted alpha value of the first stream a 1  (equivalent to &#34;one&#34; minus the alpha value), a value of zero, and a value of one on two different terminals. One of these signals may be chosen by a selection signal Asel 2 . The multiplexor circuit 46 receives as input signals the alpha value of the second stream a 2  and a value of one; one of these signals may be chosen by a selection signal Asel 3 . As is illustrated in FIG. 4, in a preferred embodiment, each of the input signals furnished is provided as an eight bit binary value used in twenty-four bit color pixel presentations. The outputs furnished by each of the circuits are also eight bit values (derived from the eight most significant bits of the result of a multiplication). Also illustrated in FIG. 4 are three port designated ports 1-3 at the output terminals of the three multiplexors 42, 45, and 46. 
     Referring to FIG. 5, a circuit 50 is shown which includes a first multiplier circuit 51 and a second multiplier circuit 52. Each of the multiplier circuits 51 and 52 receives a pair of input values and furnishes a single output value to an adder circuit 53. The adder circuit 53 provides the output value for the shade manipulating portion of the manipulating engine 14 of the invention. 
     The multiplier circuit 51 receives the shade value of the first stream (in the figure, the red value is used for illustration so that value is R 1 ) while the multiplier circuit 52 receives the shade value of the second stream R 2 . The multiplier circuit 51 also receives the output furnished by a multiplexor circuit 55. The multiplexor circuit 55 receives as input signals the alpha value of the first stream a 1 , a value of zero, and a value of one; one or the other of these signals may be chosen by a signal Rsel 1 . The multiplier circuit 52 also receives the output furnished by a multiplexor circuit 57. The multiplexor circuit 57 receives as input the inverted alpha value of the first stream a 1  (i e., &#34;one&#34; minus alpha), the alpha value of the second stream a 2 , a value of zero, and a value of one. One of these signals may be chosen by a signal Rsel 2  depending upon the particular mode of operation selected. As is illustrated in FIG. 5, in a preferred embodiment each of the input signals furnished is provided as an eight bit binary value used in twenty-four bit color pixel presentations. The outputs furnished by each of the circuits 51-53 are also eight bit values (derived from the eight most significant bits of the result of a multiplication). Also illustrated in FIG. 5 are four port designations ports 0-3 at the inputs to the two multiplier circuits 51 and 52. 
     FIG. 6 is a truth table illustrating the signals applied to the circuits 40 and 50 of FIG. 4 and 5 in order to cause the manipulation engine to produce the desired output values. As may be seen in FIG. 6, a number of terms are defined. An operation named PREMO signifies a premultiply operation only for stream one. The term AO indicates an alpha override mode used for clipping a pixel when the alpha value of stream two is zero. The term KEYFIT indicates the weatherman mode in which the color of the foreground which is to be replaced is present so that a background pixel is presented in its place. 
     The mode identified as TCB is used in a transparency form when two pictures are to be displayed simultaneously on a computer output display so that one is on top of the other to control the amount by which the background picture shows through. This TCB mode is also used in a second coverage form to provide for the controlling the intensity of pixel values in order to reduce the effect of jagged edges when two pictures are overlaid on an output display. 
     The PREM mode is a mode in which one of the streams is premultiplied and then the two streams of data are combined in the transparency form of the TCB mode described above. 
     Finally, the ALSAT mode is a toggle used in the coverage form of the TCB mode when the total of the alpha values from the two streams is greater than one. 
     Below the mode indications in FIG. 6 are shown a series of zeroes, ones, and dashes. If a one appears in a column, then the particular mode is selected. If a zero appears, usually the mode is not selected. However, in TCB mode, the coverage form is selected by a zero and the transparency form of the mode by a one. If a dash appears in a column, it has no effect on the results. 
     Thus, a one is found in the leftmost column in FIG. 6 if the PREMO mode is selected to premultiply one of the streams of data without any other manipulation of data. This produces the signals running in the row to the right of the one. For the alpha-manipulating circuit 40 of FIG. 4, the a 1  value appearing at the multiplexor 42 is transferred by the multiplexor 42 in response to an Asel 1  signal of one. The multiplexor 45 transfers a value of zero in response to an Asel 2  signal of one. The multiplexor 46 transfers the value of a 2  since the Asel 3  signal is zero. Thus a zero is added to the a 1  value to produce the a 1  value as output; this is the expected value for this operation as may be seen from the table of FIG. 2. 
     Simultaneously, the shade-manipulating circuit 50 responds to the PREMO mode signal by applying an Rsel 1  value of one to the multiplexor 55 to transfer a value of a 1  to port zero. This is multiplied by the value R 1  by the multiplier circuit 51 to produce an output equal to a 1  R 1 . At the same time an Rsel 2  signal of two causes the multiplexor 57 to select a value of zero. The value of zero is multiplied by the value of R 2  at the multiplier circuit 52. Consequently the adder 53 adds zero to a 1  R 1  to produce an output value of a 1  R 1 , the desired output. Thus, when it is desired to simply multiply the value of one stream by its alpha value, the PREMO mode accomplishes this in the manner illustrated. 
     Similarly, in the AO mode which is used among other things for clipping, a zero value is applied as the Asel 1  signal to the multiplexor 42, a zero is applied as the Asel 3  signal to the multiplexor 46, and a one is applied as the Asel 2  selection signal to the multiplexor 45 of the circuit 40 when a clip is desired. This causes a zero value to be transferred by the multiplexor 42, a zero to be transferred by the multiplexor 45, and a 2  to be transferred by the multiplexor 46. The value of a 2  is then multiplied by zero at the multiplier circuit 43 and added to the zero from the multiplexor 42 at the adder 41. This produces the desired zero value for the alpha of the resulting pixel and results in the background pixel being clipped. 
     Simultaneously, the circuit 50 receives an Rsel 1  value of zero and an Rsel 2  value of two. The Rsel 2  value of two selects a zero at the multiplexor 57 which is multiplied by the R 2  value by the multiplier 52 to produce a zero at the input to the adder 53. The Rsel 1  value of zero causes a one to be generated by the multiplexor 55 and multiplied by the R 1  value at the multiplier circuit 51. This is added by the adder 53 to the zero to produce an output of R 1 , the desired value. This value is then placed at the position of the pixel and provides for the clipping of the R 2  shade value. The green and blue shades would be similarly clipped by identical circuitry. 
     The other modes function in the same manner to produce the desired output. However, it should be noted that certain of the modes may be operating simultaneously. For example, in the transparency form of the TCB mode, the PREM mode may be on or off so that in addition to providing output for a transparency operation, stream one may be multiplied by an alpha value before it is otherwise manipulated with the data in stream two. Thus, the shade values produced in the transparency half of the TCB mode where there is no premultiplication are R 1  +(˜a 1  * R 2 ). On the other hand, with premultiplication, the output is (a 1  * R 1 )+(˜a 1  * R 2 ) where˜a 1  =1-1a 1 . 
     Similarly, the ALSAT mode operates together with the coverage form of the TCB mode to produce different results where there is saturation (the alpha values total more than one) or there is not saturation. 
     Reviewing the possible modes of operation for the circuit 50, the modes are as follows beginning at the row at the top of the truth table: premultiply only, AO, Keyfit (Weatherman), transparency form of TCB without premultiply, transparency form of TCB with premultiply, coverage form of TCB unsaturated with premultiply, coverage form of TCB saturated with premultiply, coverage form of TCB unsaturated without premultiply, and coverage form of TCB saturated without premultiply. A check through each of the possible modes will illustrate that results in accordance with the table of FIG. 2 are produced by the circuitry of FIG. 4 and 5. 
     Although the present invention has been described in terms of a preferred embodiment, it will be appreciated that various modifications and alterations might be made by those skilled in the art without departing from the spirit and scope of the invention. The invention should therefore be measured in terms of the claims which follow.