Efficient hardware handling of positive and negative overflow resulting from arithmetic operations

• US 5,448,509 A
• Filed: 12/08/1993
• Issued: 09/05/1995
• Est. Priority Date: 12/08/1993
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Lee, Ruby B., Lamb, Joel D.
• Primary Examiner(s): Envall, Jr., Roy N.
• Assistant Examiner(s): Ngo, Chuong D.
• Application Number:
  US08/163,960
• Time in Patent Office: 636 Days
• Field of Search: 364/715.04, 364/736, 364/736.5, 364/737, 364/745, 364/784
• US Class Current: 708/530
• CPC Class Codes: G06F 2207/382 Reconfigurable for different fixed word lengths multigauge devices G06F2207/3828
• CPC Class Codes: G06F 2207/3828 Multigauge devices, i.e. capable of handling packed numbers without unpacking them
• CPC Class Codes: G06F 7/49921 Saturation, i.e. clipping the result to a minimum or maximum value
• CPC Class Codes: G06F 7/57 Arithmetic logic units [ALU], i.e. arrangements or devices for performing two or more of the operations covered by groups G06F7/483 – G06F7/556 or for performing logical operations G06F7/49, G06F7/491 take precedence
• CPC Class Codes: G06F 9/30014 with variable precision

Abstract

A computer system provides handling of positive and negative overflow. A first arithmetic operation is performed on a first n-bit unsigned binary operand and a second n-bit signed binary operand to produce an n-bit unsigned binary result. Overflow detection logic circuitry within the arithmetic logic unit detects positive overflow or negative overflow resulting from the arithmetic operation. When there is a positive overflow, saturation logic replaces the output of the two'"'"'s complement adder with a value of 2^n-1. When there is a negative overflow, the saturation logic replaces the output of the two'"'"'s complement adder with a value of 0. In an alternate embodiment, a first arithmetic operation is performed on a first n-bit signed binary operand and a second n-bit signed binary operand to produce an n-bit positive signed binary result. For example the arithmetic operation is an addition or subtraction performed by a two'"'"'s complement adder. In the alternate embodiment, overflow detection logic circuitry within the arithmetic logic unit detects positive overflow or negative overflow resulting from the arithmetic operation. When there is a positive overflow, saturation logic replaces the output of the two'"'"'s complement adder with a value of 2^n-1 -1. When there is a negative overflow, the saturation logic replaces the output of the two'"'"'s complement adder with a value of 0.

Claims

1. A computing system comprising:

first arithmetic operation means for performing a first arithmetic operation on a first n-bit unsigned binary operand and a second n-bit signed binary operand to produce an n-bit unsigned binary result;

first positive overflow means, coupled to the first arithmetic operation means, for assigning a value of 2ⁿ -1 to the n-bit unsigned binary result when there is a positive overflow; and

,

first negative overflow means, coupled to the first arithmetic operation means, for assigning a value of 0 to the n-bit unsigned binary result when there is a negative overflow.

2. A computing system as in claim 1 wherein:

the first positive overflow means includes means for assigning a value of 2ⁿ -1 to the n-bit unsigned binary result when a most significant bit of the first n-bit unsigned binary operand is equal to 1, a most significant bit of the second n-bit signed binary operand is equal to 0 and a most significant bit of the n-bit unsigned binary result is equal to 0; and

,

the first negative overflow means includes means for assigning a value of 0 to the n-bit unsigned binary result when the most significant bit of the first n-bit unsigned binary operand is equal to 0, the most significant bit of the second n-bit signed binary operand is equal to 1 and the most significant bit of the n-bit unsigned binary result is equal to 1.

3. A computing system as in claim 1 additionally comprising:

second arithmetic operation means for performing a second arithmetic operation on two n-bit signed binary operands to produce an n-bit signed binary result;

second positive overflow means, coupled to the second arithmetic operation means, for assigning a value of 2^n-1 -1 to the n-bit signed binary result when there is a positive overflow resulting from the second arithmetic operation; and

,

second negative overflow means, coupled to the second arithmetic operation means, for assigning a value of -2^n-1 to the n-bit signed binary result when there is a negative overflow resulting from the second arithmetic operation.

4. A computing system as in claim 3 wherein the computer system implements multiple operations in response to a single instruction so that the second arithmetic operation is one of a plurality of parallel operations performed simultaneously in an arithmetic logic unit.

5. A computing system as in claim 3 wherein:

the first positive overflow means includes means for assigning a value of 2ⁿ -1 to the n-bit unsigned binary result when a most significant bit of the first n-bit unsigned binary operand is equal to 1, a most significant bit of the second n-bit signed binary operand is equal to 0 and a most significant bit of the n-bit unsigned binary result is equal to 0;

the first negative overflow means includes means for assigning a value of 0 to the n-bit unsigned binary result when the most significant bit of the first n-bit unsigned binary operand is equal to 0, the most significant bit of the second n-bit signed binary operand is equal to 1 and the most significant bit of the n-bit unsigned binary result is equal to 1.

the second positive overflow means includes means for assigning a value of 2^n-1 -1 to the n-bit signed binary result when most significant bits for both of the two n-bit signed binary operands are equal to 0, and a most significant bit of the n-bit signed binary result is equal to 1; and

,

the second negative overflow means includes means for assigning a value of -2^n-1 to the n-bit signed binary result when the most significant bits for both of the two n-bit signed binary operands are equal to 1, and the most significant bit of the n-bit signed binary result is equal to 0.

6. A computing system as in claim 3 additionally comprising:

third arithmetic operation means for performing a subtraction operation on two n-bit unsigned operands to produce an (n+1)-bit signed binary intermediate result;

third negative overflow means, coupled to the third arithmetic operation means, for providing an n-bit unsigned binary final result by performing a complement operation on the (n+1)-bit signed binary intermediate result when the (n+1)-bit signed binary intermediate result is negative.

7. A computing system as in claim 6 wherein the computer system implements multiple operations in response to a single instruction so that the third arithmetic operation is one of a plurality of parallel operations performed simultaneously in an arithmetic logic unit.

8. A computing system as in claim 3 wherein the second arithmetic operation means comprises an n-bit two'"'"'s complement adder and wherein the computing system additionally comprises:

selecting means for, in response to a selection, for over-riding operation of the first positive overflow means, the first negative overflow means, the second positive overflow means and the second negative overflow means so that the output of the n-bit two'"'"'s complement adder is used as an n-bit binary result.

9. A computing system as in claim 8 wherein the computer system implements multiple operations in response to a single instruction so that the first arithmetic operation is one of a plurality of parallel operations performed simultaneously in an arithmetic logic unit.

10. A computing system as in claim 1 wherein the first arithmetic operation means comprises an operation performed by n-bit two'"'"'s complement adder.

11. A computing system as in claim 10 wherein:

the first positive overflow means includes

overflow detection logic, the overflow detection logic generating a first positive overflow signal when a most significant bit of the first n-bit unsigned binary operand is equal to 1, a most significant bit of the second n-bit signed binary operand is equal to 0 and a most significant bit of the n-bit unsigned binary result is equal to 0, and

saturation logic, coupled to the overflow detection logic and an output of the n-bit two'"'"'s complement adder, the saturation logic, in response to the first positive overflow signal and in response to a first selection indicating the first arithmetic operation is being performed, replacing output of the n-bit two'"'"'s complement adder with a value of 2ⁿ -1.

12. A computing system as in claim 11 wherein the first negative positive overflow means also includes

the overflow detection logic, the overflow detection logic generating a first negative overflow signal when the most significant bit of the first n-bit unsigned binary operand is equal to 0, the most significant bit of the second n-bit signed binary operand is equal to 1 and the most significant bit of the n-bit unsigned binary result is equal to 1, and

the saturation logic which, in response to the first negative overflow signal and in response to a first selection indicating the first arithmetic operation is being performed, replacing output of the n-bit two'"'"'s complement adder with 0.

13. A computing system as in claim 12 additionally comprising:

a pre-shifter, coupled to an input of the n-bit two'"'"'s complement adder, the pre-shifter in response to a selection, shifting an n-bit binary operand before receipt by the n-bit two'"'"'s complement adder;

wherein the overflow detection logic additionally detects positive overflow resulting from the pre-shifter shifting the n-bit binary operand to the left before receipt by the n-bit two'"'"'s complement adder.

14. A computing system as in claim 1 wherein the computer system implements multiple operations in response to a single instruction so that the first arithmetic operation is one of a plurality of parallel operations performed simultaneously in an arithmetic logic unit.

15. A method within a computer implemented by hardware logic components, the method comprising the following steps:

(a) performing, within an arithmetic logic unit, a first arithmetic operation on a first n-bit unsigned binary operand and a second n-bit signed binary operand to produce an n-bit unsigned binary result;

(b) checking to determine whether there is a positive overflow in the n-bit unsigned binary result;

(c) when the check is step (b) determines there is a positive overflow, assigning a value of 2ⁿ -1 to the n-bit unsigned binary result;

(d) checking to determine whether there is a negative overflow in the n-bit unsigned binary result; and

,

(e) when the check is step (d) determines there is a negative overflow, assigning a value of 0 to the n-bit unsigned binary result.

16. A method as in claim 15 wherein:

step (b) includes determining there is a positive overflow when a most significant bit of the first n-bit unsigned binary operand is equal to 1, a most significant bit of the second n-bit signed binary operand is equal to 0 and a most significant bit of the n-bit unsigned binary result is equal to 0; and

,

step (d) includes determining there is a negative overflow when the most significant bit of the first n-bit unsigned binary operand is equal to 0, the most significant bit of the second n-bit signed binary operand is equal to 1 and the most significant bit of the n-bit unsigned binary result is equal to 1.

17. A method as in claim 15 additionally comprising the steps of:

(f) performing, within the arithmetic logic unit, a second arithmetic operation on two n-bit signed binary operands to produce an n-bit signed binary result;

(g) checking to determine whether there is a positive overflow in the n-bit signed binary result;

(h) when the check is step (g) determines there is a positive overflow, assigning a value of 2^n-1 -1 to the n-bit signed binary result;

(i) checking to determine whether there is a negative overflow in the n-bit signed binary result; and

,

(j) when the check is step (i) determines there is a negative overflow, assigning a value of -2^n-1 to the n-bit signed binary result.

18. A method as in claim 17 additionally comprising the step of:

(k) in parallel to step (f) performing an additional arithmetic operation so that the second arithmetic operation is one of a plurality of parallel operations performed simultaneously in an arithmetic logic unit.

19. A method as in claim 17 wherein:

step (b) includes determining there is a positive overflow when a most significant bit of the first n-bit unsigned binary operand is equal to 1, a most significant bit of the second n-bit signed binary operand is equal to 0 and a most significant bit of the n-bit unsigned binary result is equal to 0;

step (d) includes determining there is a negative overflow when the most significant bit of the first n-bit unsigned binary operand is equal to 0, the most significant bit of the second n-bit signed binary operand is equal to 1 and the most significant bit of the n-bit unsigned binary result is equal to 1.

step (g) includes determining there is a positive overflow when most significant bits for both of the two n-bit signed binary operands are equal to 0, and a most significant bit of the n-bit signed binary result is equal to 1; and

,

step (i) includes determining there is a negative overflow when the most significant bits for both of the two n-bit signed binary operands are equal to 1, and the most significant bit of the n-bit signed binary result is equal to 0.

20. A method as in claim 17 additionally comprising the steps of:

(k) performing, within the arithmetic logic unit, a subtraction operation on two n-bit unsigned operands to produce an (n+1)-bit signed binary intermediate result;

(1) checking to determine whether the (n+1)-bit signed binary intermediate result is negative; and

,

(m) when the check in step (l) determines the (n+1)-bit signed binary intermediate result is negative, performing a complement operation on the (n+1)-bit signed binary intermediate result to produce an n-bit unsigned binary final result.

21. A method as in claim 20 additionally comprising the step of:

(n) in parallel to step (k) performing an additional arithmetic operation so that the subtraction operation is one of a plurality of parallel operations performed simultaneously in an arithmetic logic unit.

22. A method as in claim 17, additionally comprising the steps of:

(f) performing, within the arithmetic logic unit, a third arithmetic operation on two n-bit binary operands using an n-bit two'"'"'s complement adder to produce an n-bit binary result wherein no overflow operation is performed on the n-bit binary result.

23. A method as in claim 15 wherein in step (a) the first arithmetic operation is an operation performed by an n-bit two'"'"'s complement adder.

24. A method as in claim 23 additionally comprising the step of:

(f) shifting an n-bit binary operand before performance of step (a);

wherein step (b) includes checking to determine whether positive overflow results from the performance of step (f).

25. A method as in claim 15 additionally comprising the step of:

(f) in parallel to step (a) performing an additional arithmetic operation so that the first arithmetic operation is one of a plurality of parallel operations performed simultaneously in an arithmetic logic unit.

26. A computing system comprising:

arithmetic operation means for performing a first arithmetic operation on a first n-bit signed binary operand and a second n-bit signed binary operand to produce an n-bit positive signed binary result;

positive overflow means, coupled to the arithmetic operation means, for assigning a value of 2^n-1 -1 to the n-bit positive signed binary result when a most significant bit of the first n-bit signed binary operand is equal to 0, a most significant bit of the second n-bit signed binary operand is equal to 0 and a most significant bit of the n-bit positive signed binary result is equal to 1; and

,

negative overflow means, coupled to the arithmetic operation means, for assigning a value of 0 to the n-bit positive signed binary result when the most significant bit of the n-bit positive signed binary result is equal to 1 and one of either the most significant bit of the first n-bit signed binary operand or the most significant bit of the second n-bit signed binary operand is equal to 1 and for assigning a value of 0 to the n-bit positive signed binary result when the most significant bit of both the most significant bit of the first n-bit signed binary operand and the most significant bit of the second n-bit signed binary operand are equal to 1.

27. A method within a computer implemented by hardware logic components, the method comprising the following steps:

(a) performing, within an arithmetic logic unit, a first arithmetic operation on a first n-bit signed binary operand and a second n-bit signed binary operand to produce an n-bit positive signed binary result;

(b) determining whether a most significant bit of the first n-bit signed binary operand is equal to 0, a most significant bit of the second n-bit signed binary operand is equal to 0 and a most significant bit of the n-bit positive signed binary result is equal to 1 indicating there is a positive overflow in the n-bit positive signed binary result;

(c) when the check is step (b) indicates there is a positive overflow, assigning a value of 2^n-1 -1 to the n-bit positive signed binary result;

(d) determining there is a negative overflow in the n-bit positive signed binary result when the most significant bit of the n-bit positive signed binary result is equal to 1 and one of either the most significant bit of the first n-bit signed binary operand or the most significant bit of the second n-bit signed binary operand is equal to 1 and determining there is a negative overflow when both the most significant bit of the first n-bit signed binary operand and the most significant bit of the second n-bit signed binary operand are equal to 1; and

,

(e) when the check is step (d) determines there is a negative overflow, assigning a value of 0 to the n-bit positive signed binary result.