Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2001-05-03
2004-05-25
Mai, Tan V. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S525000
Reexamination Certificate
active
06742013
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to computing, and more particularly, to a method, system, and apparatus for uniformly performing comparison operations on operands represented by more than one machine word. More specifically, the invention describes a new computer instruction that is used for performing long word comparison operations.
2. Description of Prior Art
Many popular CPU's, such as the Intel IA32 family, the SPARC™ processor from Sun Microsystems, Inc., the Power PC from IBM, and the Alpha processor from Digital Equipment Corporation, each have their own instruction set. When a programmer wishes to write a program to be executed by a particular CPU, the programmer composes the program from the corresponding instruction set. To run the program, the instructions are converted into machine instructions that are then executed by the CPU in program order.
Integer values are stored as words in the registers of the CPU whose size is defined by the particular CPU architecture. For example, in a 32-bit machine architecture, the word size is 32 bits. The registers in such a machine are therefore 32 bits wide.
The execution of an ADD or SUB instruction at the machine level is relatively straightforward. The corresponding bit positions of the two registers defined by the instruction are added or subtracted bit by bit from the least significant bit (LSB) to the most significant bit (MSB). Instruction sets also include a type of instruction generally called a conditional branch. With these types of instructions, execution typically continues at a new address which is specified with the conditional branch if the condition is met. If the condition is not met, execution usually continues with the next instruction in program order. A conditional branch tests if a particular condition occurred by analyzing certain flags. Typically, most CPUs store these certain flags in what is commonly referred to as the condition code register (CC register). CC registers usually hold a multitude of different flags, including but not exclusive, the sign flag S, the overflow/underflow flag V, the carry/borrow flag C, and the zero flag Z. Different conditional branches test for different conditions by checking for different flags to be set/cleared in the condition code register. For example, a conditional branch testing for the “is zero” condition will test if the Z flag is set in the CC register at the time of the execution of the conditional branch. If the Z flag is set in the CC register, the conditional branch will continue at the new address, otherwise it will continue with the next instruction in program order.
The flags in condition code registers can be set via a multitude of ways. However, most CPUs automatically set the flags in the CC register according to the result of the previous instruction. For example, most CPUs have an ADD or SUB instruction that adds or subtracts the integer values stored in two registers, and then stores the result in one of the two or a third register. Usually, the ADD or SUB instruction will also update the flags in the CC register such that the status of the flags reflect the outcome of the result. For example, if the result after ADD or SUB is zero, the Z flag will be set in the CC register. Similarly, whenever a carry or borrow occurs, a carry flag C is set so that the hardware performing the addition or subtraction can take the carry or borrow condition into account for the next MSBs. One problem with addition or subtraction is that the sum or difference of the two integer operands may be too large or small to be represented in a 32-bit wide register. This event is called overflow with addition and underflow with subtraction. When an overflow/underflow condition occurs, an underflow/overflow flag V is set to indicate that the sum or difference of the two operands is too large or small to be represented in the register.
Usually, an ADD or SUB instruction (and many other instructions, for that matter) followed by a conditional branch instruction can be used together to control the execution of the program depending on the relation between two integer values. For example, if a conditional branch should occur depending on whether two integer values X1 and X2 are the same, the necessary instruction sequence would look as follows for many CPUs: First, the values of X1 and X2 are moved into corresponding registers R1 and R2. Then, a SUB instruction is used to subtract R2 from R1, and store the result in either R1, R2 or another register R3. The SUB instruction will also set the CC register's flags depending on the result of the subtraction. If both X1 and X2 are the same, the result will be zero, otherwise it will not be zero. The Z flag in the CC register will be set automatically by the SUB instruction if the result is zero, otherwise it will be cleared. Thus, if and only if the Z flag is set in the CC register, X1 and X2 are the same. Therefore, a conditional branch testing the Z flag can be used to change the flow of a program depending on whether the two operands X1 and X2 are the same or not.
Because comparison of two integer values is a very important operation, most CPUs provide a special compare instruction CMP for that purpose. Such a CMP instruction usually behaves exactly like a SUB instruction, except that it does not store the result of the subtraction in one of the two or a third register. But like the SUB instruction, a CMP instruction updates the flags in the CC register. Thus, the CMP instruction is specially made to just subtract two integer values and update the CC accordingly, but discards the actual result. The advantage of the CMP instruction is that no register is changed to hold the result of the subtraction operation. Thus, the CMP instruction simply updates the flags in the CC register depending on the relation between the two integer values. A CMP instruction is usually followed by a conditional branch which tests the flags for a particular condition, depending on the relation that needs to be tested. In this way, conditional branches testing the CC flags can be used to change the flow of a program depending on the result of the comparison operation of the two operands.
It should be noted that the CMP instruction is helpful but not necessary, and that it can always be replaced with a SUB instruction if an extra unused register is available to store the result. For that reason and to not unnecessarily obscure the scope of the present invention, in the following we will not use CMP, but SUB instead. Table 1 below provides a listing of the relationship between certain relations for unsigned and two's complement (i.e., signed) integer arithmetic and their corresponding flag settings. It suffices to say that most instruction sets provide conditional branch instructions testing the CC flags for conditions corresponding to the following relations: equal (=), not equal (!=), less than (<), less than or equal (<=), greater than (>), or greater than or equal (>=). It should also be noted that the conditions to be tested for these relations are different for signed (two's complement) and unsigned integer arithmetic.
TABLE I
DESCRIPTION
DESCRIPTION
RELATION
FLAGS
(Two's Complement)
FLAGS
(Unsigned)
=
Z
If the Z flag is set,
Z
If the Z flag is set,
indicating that the
indicating that the
difference between the
difference between the
compared operands is zero,
compared operands is zero,
the condition is met.
the condition is met.
≠
not Z
If the Z flag is not set, it
not Z
If the Z flag is not set, it
indicates the compared
indicates the compared
operands are not the same
operands are not the same
and the condition is met.
and the condition is met.
<
S ≠ V
If the S flag is set but there
C
If the carry flag C is set,
is no overflow, it indicated
then the condition is met.
that the result of the
subtraction is negative and
the condition is met.
≦
S ≠ V
This condition is met if the
C or Z
If the carry flag C or the
or
Beyer Weaver & Thomas LLP
Mai Tan V.
Sun Microsystems Inc.
LandOfFree
Apparatus and method for uniformly performing comparison... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for uniformly performing comparison..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for uniformly performing comparison... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3236734