3DSoftware.com > Programming > Integers > Page 5

Integers  Page 5   Wide Unsigned Integers   Subtraction   Subtraction assumes the operands are the same sign. If they are not, then use addition instead of subtraction. Likewise, when adding numbers with different signs, use subtraction instead of addition.   The numbers are the same sign, and we subtract the smaller number from the larger number. This is the absolute value of the subtraction.  A change sign flag (CHS) determines what the sign of the result will be.   If the operands are equal, return zero.   If the first operand is greater than the second operand, the first operand becomes A, the second operand becomes B, and CHS is cleared (made equal to zero). Otherwise the the first operand becomes B, the second becomes A, and CHS is set (made equal to 1).   Then the digit packets of B are subtracted from the digit packets of A.  Borrowing is propagated, and the sign is the same as the sign of the original operands if CHS is clear, or the opposite sign if CHS is set.

 

Subtracting Digits   First, set bit 30 of the digit packets of A, to temporarily bias those digits. Then subtract the digits of B from the biased digits of A, using PSUBD. This creates new digit packets of A, with bit 30 in each digit indicating whether a borrow is required from the next more significant digit.   Then process the digits sequentially (not simd) beginning with the least significant digit. If bit 30 of a digit is clear, a borrow is needed. If it is set, no borrow is needed. Extract that bit, alternate (xor) it, and subtract that from the next higher digit. When finished processing borrows, clear bit 30 of the digits, to unbias the resulting digits.

 

Advanced Method   The method just discussed should work for initial implementations. A more advanced method is discussed in this section, for performing borrowing with simd.   To subtract the digit packets of B from the digit packets of A:   First, set bit 30 of the digit packets of A, to bias those digits for these operations. Then subtract the digits of B from the biased digits of A, using PSUBD. This creates new digit packets of A, with bit 30 in each digit indicating whether a borrow is required from the next more significant digit. Then we process the digits with simd, instead of sequentially.   Copy (with MOVDQU) all of the new A digits to the next row of (two) simd registers:

A7 A6 A5 A4 A7 A6 A5 A4   A3 A2 A1 A0 A3 A2 A1 A0

We now refer to the copy of A as a new variable S:

A7 A6 A5 A4 S7 S6 S5 S4   A3 A2 A1 A0 S3 S2 S1 S0

S7 turns out to be zero because the high order digit will never need a borrow (since A > B):

A7  0   A6 A5 A4  S6 S5 S4   A3 A2 A1 A0 S3 S2 S1 S0

POR each A digit with 0x40000000 to set bit 30 of each A digit again.  Right shift the bits of each S digit 30 bits with PSRLD (to move the borrows to bit 0 in each S digit), then PXOR each S digit with 1.    Then we need to rotate (shift) the S digits one digit position to the left. First shift the high order S digits left 4 bytes with PSLLDQ:

A7 A6 A5  S6 S5 S4  A4  0    A3 A2 A1 A0 S3 S2 S1 S0

Copy S3…S0 to another xmm register, right shift that other register 12 bytes with PSRLDQ, then POR that other register to the high order digits of S:

A7 A6 A5 A4 S6 S5 S4 S3   A3 A2 A1 A0 S3 S2 S1 S0

Left shift the low order S digits 4 bytes with PSLLDQ:

A7 A6 A5 A4 S6 S5 S4 S3   A3 A2 A1  S2 S1 S0  A0  0

Invoke PSUBD to subtract the borrows from the A digits.  Repeat these operations to process all possible borrows. When finished, clear bit 30 of each A digit.   Note: In assembly language, AMD uses Microsoft (backwards) packet ordering to be compatible with Microsoft Windows.

 

—  Page 5  —

« Page 4 Contents Page 6 »

 

Copyright © 2008 by 3D Software. All rights reserved. 3D Software, P.O. Box 221190, Sacramento CA 95822 USA www.3DSoftware.com     Contact us

Thursday, 20-Nov-2008 11:51:07 GMT