Abstract:
Disclosed herein is a apparatus and method for packing a 16-bit number into an 8-bit result byte. The method and apparatus utilize a parallel processing right shift circuit and a filter to obtain desired results. The parallel processes are comprised of a plurality of multiplexers capable of discretely analyzing smaller groups of bits. In this manner, higher throughput may be obtained than previously known.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates generally to graphics instruction sets. More particularly, the present invention relates to an apparatus and method for implementing a pack instruction for a graphics instruction set. 
     2. The Prior Art 
     In graphics instruction sets, such as those provided in Sun Microsystems architecture, pixel formatting instructions include packing instructions which convert 16-bit or 32-bit data to a lower precision fixed or pixel format. Input values are clipped to the dynamic range of the output format. Packing applies a scale factor determined from a scale factor field in a Graphics Status Register (GSR) to allow flexible positioning of the binary point. 
     As it is desirable to so utilize packing instructions to enhance system performance, it is also desirable to optimize all elements carried out in such packing instructions to further enhance system performance. As is known, graphics instructions have a tendency to be resource intensive. Thus, better implementations of any or all elements within graphics units are desirable. 
     BRIEF DESCRIPTION OF THE INVENTION 
     To overcome these and other shortcomings of the prior art, disclosed herein is an apparatus and method for providing a fast, small implementation of pack instructions. As part of the packing instruction in systems such as the Sun Microsystems MAJC, a 16-bit number consisting of two eight-bit bytes must be shifted by a specified amount to the “right”, resulting in an eight bit, one byte packed number. To achieve this result herein is disclosed a method and apparatus that performs this task by way of a predominantly parallel process which was heretofore unknown. 
     By implementing much of the process in a parallel manner, resource optimization is achieved. Such optimization results in, inter alia, faster processing of the pack in instruction, as well as enhanced parallel processing; thus, taking advantage of enhanced parallel processing devices to further optimize system performance. 
    
    
     BRIEF DESCRIPTION OF THE DRAWING FIGURES 
     FIG. 1 is a schematic diagram depicting an overview of the present invention. 
     FIG. 2 is a schematic diagram of an initial processing procedure of the present invention. 
     FIG. 3 is a schematic diagram of a further processing procedure of the present invention. 
     FIG. 4 is a schematic diagram of an overview of a resulting logic circuit of the present invention. 
     FIG. 5 is a schematic diagram of one possible implementation of the circuitry of the resulting logic circuit elements of the present invention. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     Persons of ordinary skill in the art will realize that the following description of the present invention is illustrative only and not in any way limiting. Other embodiments of the invention will readily suggest themselves to such skilled persons having the benefit of this disclosure. 
     Referring to the drawing figures; wherein like numerals denote like parts throughout the various drawing figures, FIG. 1 is directed to a schematic overview of the present invention. Given that a packing instruction is intended to shift right by up to two bytes or 16-bit positions resulting in an eight bit or one byte number, FIG. 1 depicts generally an implementation  10  for achieving this result. 
     An original two-byte, 16-bit, data set  12  is shown. The data set  12  includes a sign bit located at bit  15  (alternatively described as ob&lt; 15 &gt; as will be discussed below). If the original bit  15  is one, for instance, this indicates that the data set  12  is a negative number. In such a situation, the resulting eight-bit byte be presented as all zeros. This implementation will achieve that result as well as other necessary outcomes as will be discussed below. 
     The original two bytes are fed into a right shifter circuit  14 . The right shifter circuit  14  shifts the data set  12  by a shift amount  16  defined by other instructions outside the scope of this invention. The shift amount  16  may be any amount from zero to  15  as defined by a four bit number (sa&lt; 3 : 0 &gt;). The details of the right shifter circuit  14  will be provided hereinafter below. 
     Once the data set  12  has been right shifted, the resulting shifted bytes  18  are fed into a result analysis circuit  20 . The upper byte  22  of the shifted bytes is analyzed to determine whether any ones are present therein. If so, an overflow condition is indicated, and the resulting eight-bit byte will be defined as all ones. That is, as will be appreciated by those individuals skilled in the art, if one or more ones are present in the upper byte, the number is greater than 255, thus reporting the greatest amount possible in an eight bit byte is logical. This results in all ones being reported as the outcome in such an instance. 
     To achieve these results, the upper byte  22  is fed into an OR gate  24 , for example, which, if any bit in the upper byte  22  were a one, would result in a one output. That output is fed into AND gate  26  along with the inverted (at element  28 ) original bit  15  input. Thus, if original bit  15  is not a one (the negative case alluded to above), then a zero inverted to a one and combined with the OR gate  24  output at AND gate  26  would result in all ones being selected at multiplexer  30  if the upper byte or first shift byte  22  contains a one. This is the positive overflow case. It should be noted that certain circuit simplifications could be implemented without departing from the scope of this invention. For instance, elements  28  and  26  may be removed allowing output from  24  to go directly to the select line of multiplexer  30  without the necessity of prior combination with ob&lt; 15 &gt;. 
     On the other hand, if the upper byte  22  did not include a one and ob&lt; 15 &gt; is zero, then further analysis is required with a view towards lower byte or second shift byte  32  and the negative case. That is, if original bit  15  is a one, the negative case is implicated. That 1 becomes the select for multiplexer  34  resulting in an all zero output for resulting byte  36 . 
     On the other hand, if the original bit  15  is zero (indicating a positive number) and the right-shifted two bytes are less than 255, then that 8 bit byte of the lower byte  32  will be the result byte  36 . This has been an overview of the device now to be described in detail. Table 1 includes a truth table for this circuitry. 
     
       
         
               
               
               
             
           
               
                 TABLE 1 
               
               
                   
               
               
                 ob&lt;15&gt; 
                 positive overflow 
                 result 
               
               
                   
               
             
             
               
                 0 
                 0 
                 second shift byte (ssb) 
               
               
                 0 
                 1 
                 1 
               
               
                 1 
                 0 
                 0 
               
               
                 1 
                 1 
                 0 
               
               
                   
               
             
          
         
       
     
     Certain nomenclature will be used throughout this description and in the drawing figures. That nomenclature will now be explained by way of example. The nomenclature “&lt; 3 : 0 &gt;” represents a four-bit number including bits  3 ,  2 ,  1 , and  0 . Likewise, a 16-bit number would be defined as&lt; 15 : 0 &gt;, where the four bits  5  through  8  would be represented as&lt; 8 : 5 &gt;. Thus, ob&lt; 15 &gt; will be mentioned throughout this description and will be intended to stand for bit  15  of the original two byte data set  12 . Furthermore, the shift amount sa&lt; 3 : 0 &gt; shown in FIG.  1  and other drawing figures corresponds with the 4-bit shift amount number described above. 
     Referring now to FIG. 2, further detail regarding a first portion of the right shifter circuit  14  will now be described. As indicated, as mentioned above, the original two bytes  12  are fed into the right shifter circuit  14 . The first portion of the right shifter circuit  12  includes a plurality of multiplexers  38 ,  40 ,  42 , and  44  in parallel all having as their select lines bit  2  and  3  of the shift amount number or sa&lt; 3 : 2 &gt;. The inputs for the mulitplexers are either predefined (zero) or bits from the original two bytes  12 . This portion of the right shift circuit results in a first shift bit or fsb  46 . However, this result is not a true result in that fsb  46  merely becomes an input for the next portion of the circuit to be described below regarding FIG.  3 . 
     More specifically, bits  12  through  14  of the original two bytes  12  are presented to one of the input lines of multiplexer  38 , while the other input lines are all presented with zeros. As indicated previously, the select line for multiplexer  38  is presented with sa&lt; 3 : 2 &gt;. Again, the shift amount is a 4-bit number that is presented as part of the instruction set indicating an amount between zero and  15  to shift. If the upper two bits, sa&lt; 3 : 2 &gt; are both zero, for example, for the portion of the circuit depicted in FIG.  2  and now being described, this is interpreted as “shift by zero.” In that case, ob&lt; 14 : 12 &gt; would be an appropriate output from multiplexer  38 . However, if sa&lt;3:2&gt; is 01 (shift by four), (shift by eight), or 11 (shift by twelve), then the output at multiplexer  38  will necessarily be zero (as this multiplexer is only handling bits  12  through  14  and these shifts would preclude those bits). That is, a shift by four would result in  0000  in front of bits ob&lt; 14 : 4 &gt;, while a shift by  8  would result in eight zeros ( 00000000 ) in front of ob&lt; 14 : 8 &gt;, and so forth. Please note that due to the significance of ob&lt; 15 &gt; as a sign bit, it is dealt with elsewhere in the circuitry as will now be appreciated to those skilled in the art informed by this disclosure. 
     Thus, each multiplexer is configured to provide an output for the right-shift by zero, four, eight, or twelve bit locations, while the next portion of the circuit in FIG. 3 will focus on the shift by zero, one, two, or three bit locations (as added to the first set of multiplexer shifts). Therefore, continuing, multiplexer  40  will provide ob bit value outputs if the shift is by zero or four but not by eight or twelve. That is, if the shift amount is 00 (shift by zero), the first multiplexer  38  will have provided the upper bits for fsb  46  or fsb&lt; 14 : 12 &gt; which is ob&lt; 14 : 12 &gt;, while multiplexer  40  will provide the next four lower bits or fsb&lt; 11 : 8 &gt; which is ob&lt; 11 : 8 &gt;. However, if the shift is by 01 (or four), fsb&lt; 14 : 12 &gt; will be  000 , while fsb&lt; 11 : 8 &gt; will be ob&lt; 15 : 12 &gt; (where fsb stands for “first shift bit”). 
     Therefore, if the shift amount is by eight or sa&lt; 3 : 2 &gt;= 10 , then the output of multiplexer  38  will be fsb&lt; 14 : 12 &gt;= 000 , the output of multiplexer  40  will be fsb&lt; 11 : 8 &gt;= 0000 , and the output of multiplexer  42  will be fsb&lt; 7 : 4 &gt;= ob&lt; 15 : 12 &gt;. Likewise, if sa&lt; 3 : 2 &gt;= 11  (shift by twelve), then fsb&lt; 14 : 12 &gt;= 000 , fsb&lt; 11 : 8 &gt;= 0000 , fsb&lt; 7 : 4 &gt;= 0000 , and fsb&lt; 3 : 0 &gt; from multiplexer  44  would be ob&lt; 15 : 12 &gt;. Table 2 below provides these outcomes. 
     
       
         
               
               
               
               
               
             
           
               
                 TABLE 2 
               
               
                   
               
               
                 sa&lt;3:2&gt; 
                 fsb&lt;14:12&gt; 
                 fsb&lt;11:8&gt; 
                 fsb&lt;7:4&gt; 
                 fsb&lt;3:0&gt; 
               
               
                   
               
             
             
               
                 00 
                 ob&lt;14:12&gt; 
                 ob&lt;11:8&gt; 
                 ob&lt;7:4&gt; 
                 ob&lt;3:0&gt; 
               
               
                 01 
                 000 
                 ob&lt;15:12&gt; 
                 ob&lt;11:8&gt; 
                 ob&lt;7:4&gt; 
               
               
                 10 
                 000 
                 0000 
                 ob&lt;15:12&gt; 
                 ob&lt;11:8&gt; 
               
               
                 11 
                 000 
                 0000 
                 0000 
                 ob&lt;15:12&gt; 
               
               
                   
               
             
          
         
       
     
     To complete the right shifting then, as alluded to above, and referring now to FIG. 3, the remainder of the right shifter circuit  14  is depicted. Another three multiplexers  48 ,  50 , and  52  are provided in parallel including the fsb  46  provided as input to those multiplexers, sa&lt; 1 : 0 &gt; providing the select line data, and now having the ssb (or second shift bits)  54  as the output. The focus of this portion of the right shifter circuit  14  is on the lower two bits of the shift amount, or the shift by 0, 1, 2, or 3 bit locations. 
     The first multiplexer  48  is adapted to handle part of the special case positive overflow discussed above. The result of multiplexer  48  is ssb&lt; 10 : 8 &gt; which are the 3 bits above the resulting ssb 7-bit byte. If one of the bits of ssb&lt; 10 : 8 &gt; is one, a positive overflow condition is indicated. Additionally, the fsb&lt; 14 : 11 &gt; bits perform alike purpose. If one of the bits of fsb&lt; 14 :  11 &gt; is one, a positive overflow condition is also implicated. Thus, fsb&lt; 14 : 11 &gt; is provided as input to OR gate  58  to determine if any of its bits are one. The output of OR gate  58  is combined as input with ssb&lt; 10 : 8 &gt; for OR gate  56 . Thus, in combination, if either fsb&lt; 14 : 11 &gt; includes a one or ssb&lt; 10 : 8 &gt; includes a one, the output of OR gate  56  would be a one resulting in a positive overflow indication. Otherwise, a positive overflow state is not present and a zero output at OR gate  56  will be the result. 
     Hence, the remainder of ssb  54 , ssb&lt; 7 : 0 &gt; is the desired right shifted and truncated 7-bit byte. Therefore, multiplexers  50  and  52  complete the right shifting process by taking as input the appropriate fsb 46 bits appropriately selected by the sa&lt; 1 : 0 &gt; select line input and outputting ssb&lt; 7 : 4 &gt; and ssb&lt; 3 : 0 &gt;. A truth table for this portion of the circuit is provided at Table 3. 
     
       
         
               
               
               
               
             
           
               
                 TABLE 3 
               
               
                   
               
               
                 sa&lt;1:0&gt; 
                 ssb&lt;10:8&gt; 
                 ssb&lt;7:4&gt; 
                 ssb&lt;3:0&gt; 
               
               
                   
               
             
             
               
                 00 
                 fsb&lt;10:8&gt; 
                 fsb&lt;7:4&gt; 
                 fsb&lt;3:0&gt; 
               
               
                 01 
                 fsb&lt;11:9&gt; 
                 fsb&lt;8:5&gt; 
                 fsb&lt;4:1&gt; 
               
               
                 10 
                 fsb&lt;12:10&gt; 
                 fsb&lt;9:6&gt; 
                 fsb&lt;5:2&gt; 
               
               
                 11 
                 fsb&lt;13:11&gt; 
                 fsb&lt;10:7&gt; 
                 fsb&lt;6:3&gt; 
               
               
                   
               
             
          
         
       
     
     Referring now to FIG. 4, having thus obtained certain necessary elements for (namely, ssb&lt; 7 : 0 &gt;, positive overflow indication, and ob&lt; 15 &gt;), those fed into result logic circuit  20  to obtain the ultimate result bits required. That  7 : 0 &gt;, the positive overflow result, and ob&lt; 15 &gt;, the resulting 8-bit result obtained. This is accomplished by presenting each bit of ssb&lt; 7 : 0 &gt; in plurality of result logic circuits  60  along with the positive overflow result Table 4 indicates the result bit&lt; 7 : 0 &gt; truth analysis for this circuit  20 . 
     
       
         
               
               
               
             
           
               
                 TABLE 4 
               
               
                   
               
               
                 ob&lt;15&gt; 
                 positive overflow 
                 result 
               
               
                   
               
             
             
               
                 0 
                 0 
                 ssb&lt;7:0&gt; 
               
               
                 0 
                 1 
                 11111111 
               
               
                 1 
                 0 
                 00000000 
               
               
                 1 
                 1 
                 00000000 
               
               
                   
               
             
          
         
       
     
     Referring now to FIG. 5, one possible implementation of the circuitry with each result logic  60  element is depicted. The results of Table 4 may be obtained by such a circuit given positive overflow from FIG. 3, ob&lt; 15 &gt; from the sign bit of the original two byte number, and each bit from ssb&lt; 7 : 0 &gt; as obtained in FIG.  3 . That is, the circuit depicted in FIG. 5, may be included within each result circuit  60 , one per ssb bit. 
     Thus, for example, ssb&lt; 7 &gt; may be provided to result logic  60  as defined by the circuit of the positive overflow result obtained in FIG. 3, and ob&lt; 15 &gt;. More particularly, the positive overflow indicator and ob&lt; 15 &gt;are presented to NOR gate  64 . If either positive overflow exists or ob&lt; 15 &gt; is 1 indicating a negative number, the ouput from NOR gate  64  will be 0 causing the left transistor circuitry  70  to float and implicating the right transistor circuitry  80 . In which case, the right hand circuitry will provide a result bit &lt; 7 &gt; as 1 (or high) if positive overflow is indicated, or result bit &lt; 7 &gt; as 0 (or low) if ob&lt; 15 &gt; is a 1. 
     That is, if positive overflow is one or high, that input will be inverted at inverter  78  causing transistor  80  to close to high at junction  81  and if ob&lt; 15 &gt; is zero completing the close to high at junction  82 . On the other hand, if there is no positive overflow, the low or zero input at inverter  78  will result in transistor  80  remaining open high, but if ob&lt; 15 &gt; is 1, junction  84  will close resulting in result bit&lt; 7 &gt; as zero or low. 
     Alternately, if both ob&lt; 15 &gt; and positive overflow are zero (not a negative number and no positive overflow), the remote junctions  71  and  76  will close since the output from NOR gate  64  will result in a 1 or high and the output from inverter  66  will result in a zero or low. Thus if ssb&lt; 7 &gt; is a 1 or high, it will be inverted to zero by inverter  68  resulting injunction  72  closing and result bit &lt; 7 &gt; as 1. If, on the other hand, ssb&lt; 7 &gt; is a 0 or low, then it will be inverted by inverter  68  resulting in a 1 or high closing junction  74  and obtaining result bit &lt; 7 &gt;as 0. In this manner, one possible implementation of result Table 4 is obtained, however, as one skilled in the art now informed by this disclosure is aware, many other alternate logical circuits may be utilized to obtain these same results. Thus, the circuit of FIG. 5 is illustrative only and not intended to be limiting. 
     While embodiments and applications of this invention have been shown and described, it would be apparent to those skilled in the art that many more modifications than mentioned above are possible without departing from the inventive concepts herein. The invention, therefore, is not to be restricted except in the spirit of the appended claims.