// TITLE("Large Integer Arithmetic")
//++
//
// Copyright (c) 1993 IBM Corporation
//
// Module Name:
//
// largeint.s
//
// Abstract:
//
// This module implements routines for performing extended integer
// arithmtic.
//
// Author:
//
// David N. Cutler (davec) 18-Apr-1990
// Converted to PowerPC by Walt Daniels and Norman Cohen Aug 93
// (from MIPS based code)
//
// References:
// See PowerPC Architecture book Appendix E.2 for 64-bit shifts
// See "Hacker's Delight", Hank Warren, Nov. 91 for fancy divides
//
// Environment:
//
// Any mode.
//
// Revision History:
// Fixed RtlExtendedLargeIntegerDivide (Steve Johns) 18-Feb-94
// - if divisor >= 2^16 && dividend >= 2^32, quotient incorrect
// - also, removed 6 uncessary occurrences of CMPI
//
//--
#include "ksppc.h"
//++
//
// LARGE_INTEGER
// RtlLargeIntegerAdd (
// IN LARGE_INTEGER Addend1,
// IN LARGE_INTEGER Addend2
// )
//
// Routine Description:
//
// This function adds a signed large integer to a signed large integer and
// returns the signed large integer result.
//
// Arguments:
//
// Addend1 (r.5, r.6) - Supplies the first addend value.
//
// Addend2 (r.7, r.8) - Supplies the second addend value.
//
// Return Value:
//
// The large integer result is stored at the address supplied by r.3.
//
//--
LEAF_ENTRY(RtlLargeIntegerAdd)
addc r.5,r.5,r.7 // add low parts of large integer
adde r.6,r.6,r.8 // add high parts with carry
stw r.5,0(r.3) // store low 32-bits
stw r.6,4(r.3) // store high 32-bits
LEAF_EXIT(RtlLargeIntegerAdd) // return
//++
//
// LARGE_INTEGER
// RtlConvertLongToLargeInteger (
// IN LONG SignedInteger
// )
//
// Routine Description:
//
// This function converts the a signed integer to a signed large integer
// and returns the result.
//
// Arguments:
//
// SignedInteger (r.4) - Supplies the value to convert.
//
// Return Value:
//
// The large integer result is stored at the address supplied by r.3.
//
//--
LEAF_ENTRY(RtlConvertLongToLargeInteger)
srawi r.5,r.4,31 // compute high part of result
stw r.4,0(r.3) // store low 32-bits
stw r.5,4(r.3) // store high 32-bits
LEAF_EXIT(RtlConvertLongToLargeInteger) // return
//++
//
// LARGE_INTEGER
// RtlConvertUlongToLargeInteger (
// IN LONG UnsignedInteger
// )
//
// Routine Description:
//
// This function converts the an unsigned integer to a signed large
// integer and returns the result.
//
// Arguments:
//
// UnsignedInteger (r.4) - Supplies the value to convert.
//
// Return Value:
//
// The large integer result is stored at the address supplied by r.3.
//
//--
LEAF_ENTRY(RtlConvertUlongToLargeInteger)
li r.5,0 // clear high part
stw r.4,0(r.3) // store low 32-bits
stw r.5,4(r.3) // store high 32-bits
LEAF_EXIT(RtlConvertUlongToLargeInteger) // return
//++
//
// LARGE_INTEGER
// RtlEnlargedIntegerMultiply (
// IN LONG Multiplicand,
// IN LONG Multiplier
// )
//
// Routine Description:
//
// This function multiplies a signed integer by an signed integer and
// returns a signed large integer result.
//
// Arguments:
//
// Multiplicand (r.4) - Supplies the multiplicand value.
//
// Multiplier (r.5) - Supplies the multiplier value.
//
// Return Value:
//
// The large integer result is stored at the address supplied by r.3.
//
//--
LEAF_ENTRY(RtlEnlargedIntegerMultiply)
mullw r.6,r.4,r.5 // keep low 32-bits of result
mulhw r.7,r.4,r.5 // keep high 32-bits of result
stw r.6,0(r.3) // store low 32-bits
stw r.7,4(r.3) // store high 32-bits
LEAF_EXIT(RtlEnlargedIntegerMultiply) // return
//++
//
// LARGE_INTEGER
// RtlEnlargedUnsignedMultiply (
// IN ULONG Multiplicand,
// IN ULONG Multiplier
// )
//
// Routine Description:
//
// This function multiplies an unsigned integer by an unsigned integer
// and returns a signed large integer result.
//
// Arguments:
//
// Multiplicand (r.4) - Supplies the multiplicand value.
//
// Multiplier (r.5) - Supplies the multiplier value.
//
// Return Value:
//
// The large integer result is stored at the address supplied by r.3.
//
//--
LEAF_ENTRY(RtlEnlargedUnsignedMultiply)
mullw r.6,r.4,r.5 // keep low-32-bits
mulhwu r.7,r.4,r.5 // keep high 32-bits
stw r.6,0(r.3) // store low 32-bits
stw r.7,4(r.3) // store high 32-bits
LEAF_EXIT(RtlEnlargedUnsignedMultiply) // return
//++
//
// ULONG
// RtlEnlargedUnsignedDivide (
// IN ULARGE_INTEGER Dividend,
// IN ULONG Divisor,
// IN PULONG Remainder.
// )
//
// Routine Description:
//
// This function divides an unsigned large integer by an unsigned long
// and returns the resultant quotient and optionally the remainder.
//
// N.B. It is assumed that no overflow will occur.
//
// Arguments:
//
// Dividend (r.3, r.4) - Supplies the dividend value.
// (High-order bits in r.4, low-order bits in r.3)
//
// Divisor (r.5) - Supplies the divisor value.
//
// Remainder (r.6) - Supplies an optional pointer to a variable that
// receives the remainder. Ptr is null if not needed.
//
// Return Value:
//
// The unsigned long integer quotient is returned as the function value.
//
//--
LEAF_ENTRY(RtlEnlargedUnsignedDivide)
cmplw r.4,r.5
bge overflow // catch overflow or division by 0
cmplwi r.4,0 // test high part for 0
beq only_32_bits // 32-bit division suffices
// Normalize: Shift divisor and dividend left to get rid of leading zeroes
// in the divisor. Since r.4 < r.5, only zeroes are shifted out of the
// dividend.
cntlzw r.7,r.5 // number of bits to shift (N)
slw r.5,r.5,r.7 // shift divisor
slw r.4,r.4,r.7 // shift upper part of divisor
subfic r.9,r.7,32 // 32-N
srw r.9,r.3,r.9 // leftmost N bits of r.3, slid right
or r.4,r.4,r.9 // and inserted into low end of r.4
slw r.3,r.3,r.7 // shift lower part of divisor
// Estimate high-order halfword of quotient. If the dividend is
// A0 A1 A2 A3 and the divisor is B0 B1 (where each Ai or Bi is a halfword),
// then the estimate is A0 A1 0000 divided by B0 0000, or A0 A1 divided by B0.
// (r.4 holds A0 A1, r.3 holds A2 A3, and r.5 holds B0 B1.)
// The estimate may be too high because it does not account for B1; in rare
// cases, the estimate will not even fit in a halfword. High estimates are
// corrected for later.
srwi r.8,r.5,16 // r.8 <- B0
divwu r.12,r.4,r.8 // r.12 <- floor([A0 A1]/B0)
// Subtract partial quotient times divisor from dividend: If Q0 is the quotient
// computed above, this means that Q0 0000 times B0 B1 is subtracted from
// A0 A1 A2 A3. We compute Q0 times B0 B1 and then shift the two-word
// product left 16 bits.
mullw r.9,r.12,r.5 // low word of Q0 times B0 B1
mulhwu r.10,r.12,r.5 // high word of Q0 times B0 B1
slwi r.10,r.10,16 // shift high word left 16 bits
inslwi r.10,r.9,16,16 // move 16 bits from left of low word to
// right of high word
slwi r.9,r.9,16 // shift low word left 16 bits
subfc r.3,r.9,r.3 // low word of difference
subfe r.4,r.10,r.4 // high word of difference
// If the estimate for Q0 was too high, the difference will be negative.
// While A0 A1 A2 A3 is negative, repeatedly add B0 B1 0000 to A0 A1 A2 A3
// and decrement Q0 by one to correct for the overestimate.
cmpwi r.4,0 // A0 A1 A2 A3 is negative iff A0 A1 is
bge Q0_okay // no correction needed
inslwi r.10,r.5,16,16 // high word of B0 B1 0000 (= 0000 B0)
slwi r.9,r.5,16 // low word of B0 B1 0000 (= B1 0000)
adjust_Q0:
addc r.3,r.3,r.9 // add B0 B1 0000 to A0 A1 A2 A3 (low)
adde r.4,r.4,r.10 // add B0 B1 0000 to A0 A1 A2 A3 (high)
cmpwi r.4,0 // Is A0 A1 A2 A3 now nonnegative?
addi r.12,r.12,-1 // decrement Q0
blt adjust_Q0 // if A0 A1 A2 A3 still negative, repeat
Q0_okay:
// Estimate low-order halfword of quotient. A0 is necessarily 0000 at this
// point, so if the remaining part of the dividend is A0 A1 A2 A3 then the
// estimate is A1 A2 0000 divided by B0 0000, or A1 A2 divided by B0.
// (r.4 holds A0 A1, r.3 holds A2 A3, and r.8 holds B0.)
slwi r.9,r.4,16 // r.9 <- A1 0000
inslwi r.9,r.3,16,16 // r.9 <- A1 A2
divwu r.11,r.9,r.8 // r.11 <- floor([A1 A2]/B0)
// Subtract partial quotient times divisor from remaining part of dividend:
// If Q1 is the quotient computed above, this means
// that Q1 times B0 B1 is subtracted from A0 A1 A2 A3. We compute
mullw r.9,r.11,r.5 // low word of Q1 times B0 B1
mulhwu r.10,r.11,r.5 // high word of Q1 times B0 B1
subfc r.3,r.9,r.3 // low word of difference
subfe r.4,r.10,r.4 // high word of difference
// If the estimate for Q1 was too high, the difference will be negative.
// While A0 A1 A2 A3 is negative, repeatedly add B0 B1 to A0 A1 A2 A3
// and decrement Q1 by one to correct for the overestimate.
cmpwi r.4,0 // A0 A1 A2 A3 is negative iff A0 A1 is
bge Q1_okay // no correction needed
adjust_Q1:
addc r.3,r.3,r.5 // add B0 B1 to A0 A1 A2 A3 (low)
addze r.4,r.4 // add B0 B1 to A0 A1 A2 A3 (high)
cmpwi r.4,0 // Is A0 A1 A2 A3 now nonnegative?
addi r.11,r.11,-1 // decrement Q1
blt adjust_Q1 // if A0 A1 A2 A3 still negative, repeat
Q1_okay:
// Build the results. The desired quotient is Q0 Q1.
// The desired remainder is obtained by shifting A2 A3 right by the number
// of bits by which the dividend and divisor were shifted left in the
// normalization step. The number of bits shifted is still in r.7.
cmplwi r.6,0 // remainder needed?
bne rem1 // if so, go compute it
slwi r.3,r.12,16 // r.3 <- Q0 0000
or r.3,r.3,r.11 // r.3 <- Q0 Q1
blr
rem1:
srw r.8,r.3,r.7 // remainder <- [A2 A3] >> (r.7)
slwi r.3,r.12,16 // r.3 <- Q0 0000
stw r.8,0(r.6) // store remainder
or r.3,r.3,r.11 // r.3 <- Q0 Q1
blr
//
// End of normal case
//
// The case of a 32-bit dividend:
only_32_bits:
cmplwi r.6,0 // remainder needed?
bne rem2 // if so, go compute quotient+remainder
divwu r.3,r.3,r.5 // result <- dividend/divisor
blr
rem2:
divwu r.7,r.3,r.5 // quotient <- dividend / divisor
mullw r.8,r.7,r.5 // r.8 <- quotient * divisor
subf r.8,r.8,r.3 // remainder<-dividend-quotient*divisor
mr r.3,r.7 // result <- quotient
stw r.8,0(r.6) // store remainder
blr
// The error cases:
overflow:
twi 6,r.5,0 // trap if divide by zero
twi 0x1b,r.5,0 // trap on overflow
LEAF_EXIT(RtlEnlargedUnsignedDivide)
//++
//
// ULARGE_INTEGER
// RtlExtendedLargeIntegerDivide (
// IN ULARGE_INTEGER Dividend,
// IN ULONG Divisor,
// IN PULONG Remainder.
// )
//
// Routine Description:
//
// This function divides an unsigned large integer by an unsigned long
// and returns the resultant quotient and optionally the remainder.
//
// Arguments:
//
// Dividend (r.5, r.6) - Supplies the dividend value.
//
// Divisor (r.7) - Supplies the divisor value.
//
// Remainder (r.8)- Supplies an optional pointer to a variable
// that receives the remainder.
//
// Return Value:
//
// The large integer result is stored at the address supplied by r.3.
//
//--
LEAF_ENTRY(RtlExtendedLargeIntegerDivide)
cmplwi r.7,0 // zero divisor?
beq div_zero_s // if so, branch to error exit
cmpwi r.6,0 // check sign of dividend high word
bne big_dividend
// The high-order word of the dividend is zero, so 32-bit unsigned division
// can be used.
li r.12,0 // upper word of quotient is zero
stw r.12,4(r.3) // store upper word of quotient
divwu r.11,r.5,r.7 // compute lower word of quotient
stw r.11,0(r.3) // store lower word of quotient
cmplwi r.8,0 // remainder needed?
beqlr // if not, return
mullw r.10,r.11,r.7 // quotient * divisor
subf r.9,r.10,r.5 // dividend - quotient * divisor
stw r.9,0(r.8) // store remainder
blr // return
big_dividend:
srwi. r.0,r.7,16 // upper 16 bits of divisor
bne long_division // if not, must use long division
// The divisor is only one 16-bit digit long, so use short division:
srwi r.0,r.6,16 // first 16-bit digit of dividend
divwu r.4,r.0,r.7 // first 16-bit digit of quotient
mullw r.10,r.4,r.7 // amount to subtract for remainder
subf r.9,r.10,r.0 // remainder from first digit
insrwi r.6,r.9,16,0 // combine rmndr with 2nd digit of dvdnd
divwu r.12,r.6,r.7 // second digit of quotient
insrwi r.12,r.4,16,0 // high two quotient digits in one word
mullw r.10,r.12,r.7 // amount to subtract for remainder
subf r.9,r.10,r.6 // remainder from second digit
srwi r.0,r.5,16 // third digit of dividend
insrwi r.0,r.9,16,0 // combine rmndr with 3rd digit of dvdnd
divwu r.4,r.0,r.7 // third digit of quotient
mullw r.10,r.4,r.7 // amount to subtract for remainder
subf r.9,r.10,r.0 // remainder from third digit
insrwi r.5,r.9,16,0 // combine rmndr with 4th digit of dvdnd
divwu r.11,r.5,r.7 // fourth digit of quotient
mullw r.10,r.11,r.7 // amount to subtract for remainder
insrwi r.11,r.4,16,0 // low two quotient digits in one word
subf r.9,r.10,r.5 // remainder from fourth digit
b store_results
long_division:
// Since the divisor is more than one 16-bit digit long, the quotient will
// be of the form 0x0000 Q2 Q3 Q4, where each of Q2, Q3, and Q4 is a 16-bit
// digit.
//
// Normalize the divisor and dividend so that the high-order bit of the
// divisor is 1. This normalization must be undone after the division to
// compute the remainder. Let U1 U2 U3 U4 be the 16-bit digits of the
// unnormalized dividend. Each digit Ui consists of an S-bit high-order part
// UiH and a (16-S)-bit low-order part UiL, where S is the number of leading
// zeroes in the divisor. Thus R6 holds U1H U1L U2H U2L and R5 holds
// U3H U3L U4H U4L. Let N0 N1 N2 N3 N4 be the 16-bit digits of the normalized
// dividend: N0 = U1H, N1 = U1L U2H, N2 = U2L U3H, N3 = U3L U4H, N4 = U4L 0...0.
// Let D1 D2 be the normalized divisor.
cntlzw r.0,r.7 // number of bits to shift left (S)
subfic r.12,r.0,16 // 16-S
subfic r.11,r.0,32 // 32-S
srw r.9,r.6,r.12 // U1H U1L U2H = N0 N1
srw r.4,r.5,r.11 // U3H
slw r.10,r.6,r.0 // U1L U2H U2L 0...0
or r.6,r.4,r.10 // U1L U2H U2L U3H = N1 N2
slw r.4,r.5,r.0 // U3L U4H U4L 0...0 = N3 N4
slw r.7,r.7,r.0 // normalized divisor (D1 D2)
srwi r.11,r.7,16 // D1
// Set Q2 = [N0 N1 N2] / [D1 D2]. Start by guessing Q2 = [N0 N1] / D1, then
// adjust if necessary. This guess will occasionally be one too high and
// very rarely two too high, but never higher than that and never too low.
// (See Theorem B in Section 4.3.1 of Knuth, Vol. II, pp. 256-7.)
// Let C N0' N1' N2' be the partial remainder [N0 N1 N2] - Q2 * [D1 D2].
divwu r.12,r.9,r.11 // guess Q2 = [N0 N1] / D1
srwi r.10,r.9,16 // 0x0000 N0
mullw r.5,r.12,r.7 // low word of Q2 * [D1 D2]
subfc r.9,r.5,r.6 // low word of C N0' N1' N2' (N1' N2')
mulhwu r.5,r.12,r.7 // high word of Q2 * [D1 D2]
subfe. r.10,r.5,r.10 // high word of C N0' N1' N2' (C N0')
bge Q2_okay // if difference is >= 0, Q2 was not too high
adjust_Q2:
addc r.9,r.9,r.7 // low word of [C N0' N1' N2']+[D1 D2]
addze. r.10,r.10 // high word of [C N0' N1' N2']+[D1 D2]
addi r.12,r.12,-1 // Q2 - 1
blt adjust_Q2 // try again if still negative
Q2_okay:
// At this point 0 <= [C N0' N1' N2'] < [D1 D2], so [C N0'] = 0x00000000.
// r.12 holds the upper word of the quotient, 0x0000 Q2.
// Set Q3 = [N1' N2' N3] / [D1 D2] by guessing and adjusting as above.
// Let [N0" N1" N2" N3"] be the partial remainder [N1' N2' N3] - Q3 * [D1 D2].
divwu r.6,r.9,r.11 // guess Q3 = [N1' N2'] / D1
srwi r.10,r.9,16 // 0x0000 N1'
slwi r.9,r.9,16 // N2' 0x0000
inslwi r.9,r.4,16,16 // N2' N3
mullw r.5,r.6,r.7 // low word of Q3 * [D1 D2]
subfc r.9,r.5,r.9 // N2" N3"
mulhwu r.5,r.6,r.7 // high word of Q3 * [D1 D2]
subfe. r.10,r.5,r.10 // N0" N1"
bge Q3_okay // if difference >= 0, Q3 was not too high
adjust_Q3:
addc r.9,r.9,r.7 // low word of [N0" N1" N2" N3"]+[D1 D2]
addze. r.10,r.10 // high word [N0" N1" N2" N3"]+[D1 D2]
addi r.6,r.6,-1 // Q3 - 1
blt adjust_Q3 // try again if difference still negative
Q3_okay:
// At this point 0 <= [N0" N1" N2" N3"] < [D1 D2], so [N0" N1"] = 0x00000000.
// Set Q4 = [N2" N3" N4] / [D1 D2] by guessing and adjusting as above.
// Let [R1 R2 R3 R4] be the partial remainder [N2" N3" N4] - Q4 * [D1 D2].
divwu r.11,r.9,r.11 // guess Q4 = [N2" N3"] / D1
insrwi r.4,r.9,16,0 // N3" N4
srwi r.10,r.9,16 // 0x0000 N2"
mullw r.5,r.11,r.7 // low word of Q4 * [D1 D2]
subfc r.9,r.5,r.4 // R3 R4
mulhwu r.5,r.11,r.7 // high word of Q4 * [D1 D2]
subfe. r.10,r.5,r.10 // R1 R2
bge Q4_okay // if difference < 0, Q4 was not too high
adjust_Q4:
addc r.9,r.9,r.7 // low word of [R1 R2 R3 R4]+[D1 D2]
addze. r.10,r.10 // high word of [R1 R2 R3 R4]+[D1 D2]
addi r.11,r.11,-1 // Q4 - 1
blt adjust_Q4 // try again if partial remainder still negative
Q4_okay:
// At this point 0 <= [R1 R2 R3 R4] < [D1 D2], so [R3 R4] is the remainder.
insrwi r.11,r.6,16,0 // low word of quotient: Q3 Q4
srw r.9,r.9,r.0 // unnormalize remainder
store_results:
stw r.11,0(r.3) // store low word of quotient
stw r.12,4(r.3) // store high word of quotient
cmplwi r.8,0 // remainder needed?
beqlr // if not, return
stw r.9,0(r.8) // store remainder
blr // return
div_zero_s:
twi 6,r.7,0 // Trap on divide by zero
LEAF_EXIT(RtlExtendedLargeIntegerDivide)
//++
//
// LARGE_INTEGER
// RtlExtendedMagicDivide (
// IN LARGE_INTEGER Dividend,
// IN ULARGE_INTEGER MagicDivisor,
// IN CCHAR ShiftCount
// )
//
// Routine Description:
//
// This function divides a signed large integer by an unsigned large integer
// and returns the signed large integer result. The division is performed
// using reciprocal multiplication of a signed large integer value by an
// unsigned large integer fraction which represents the most significant
// 64-bits of the reciprocal divisor rounded up in its least significant bit
// and normalized with respect to bit 63. A shift count is also provided
// which is used to truncate the fractional bits from the result value.
// The value returned is the most significant 64 bits of the product
// Dividend*MagicDivisor, shifted right ShiftCount bits.
//
// Arguments:
//
// Dividend (r.5, r.6) - Supplies the dividend value.
//
// MagicDivisor (r.7, r.8) - Supplies the magic divisor value
// which is a 64-bit multiplicative reciprocal.
//
// Shiftcount (r.9) - Supplies the right shift adjustment value,
// assumed to be in the range 0 to 63.
//
// Return Value:
//
// The large integer result is stored at the address supplied by r.3.
//
//--
// Let Dividend = A B and MagicDivisor = C D, where each of A, B, C, and D is
// a 32-bit word. Then Dividend*MagicDivisor is a 128-bit product, computed
// as follows:
// A B
// x C D
// ==========================================================
// high_word(B*D) low_word(B*D)
// high_word(A*D) low_word(A*D)
// high_word(B*C) low_word(B*C)
// high_word(A*C) low_word(A*C)
// ==========================================================
// P1 P2 P3 P4
//
// Since the return value is [P1 P2] >> Shift_Count, P3 and P4 need not be
// computed, but the carry out of the P3 column must be computed to compute P2.
LEAF_ENTRY(RtlExtendedMagicDivide)
// If the dividend is negative, negate it and record the fact by setting
// cr7 to LT.
crclr 4*cr.7+0 // clear cr.7 LT bit
cmpwi r.6,0 // is high-order word of divisor < 0?
bge divisor_nonnegative // if not, we are ready to compute
crset 4*cr.7+0 // set cr.7 LT bit to mark negation
subfic r.5,r.5,0 // negate lower half of dividend
subfze r.6,r.6 // negate upper half of dividend
divisor_nonnegative:
// To avoid pipeline delays, produce partial products first, in the order they
// will be consumed by the addc and addze instructions below.
mulhwu r.11,r.6,r.7 // high(A*D)
mulhwu r.0,r.5,r.8 // high(B*C)
mulhwu r.12,r.6,r.8 // high(A*C)
mullw r.4,r.6,r.8 // low(A*C)
mulhwu r.10,r.5,r.7 // high(B*D)
mullw r.6,r.6,r.7 // low(A*D)
mullw r.7,r.5,r.8 // low(B*C)
// Now combine the partial products, forming P1 in r.12, P2 in r.11, P3 in r.10:
addc r.11,r.11,r.0 // high(A*D)+high(B*C)
addze r.12,r.12 // high(A*C)+partial carry
addc r.11,r.11,r.4 // high(A*D)+high(B*C)+low(A*C)
addze r.12,r.12 // high(A*C)+partial carry
addc r.10,r.10,r.6 // high(B*D)+low(A*D)
addze r.11,r.11 // hi(A*D)+hi(B*C)+low(A*C)+part. carry
addze r.12,r.12 // high(A*C)+partial carry
addc r.10,r.10,r.7 // high(B*D)+low(A*D)+low(B*C) = P3
addze r.11,r.11 // hi(A*D)+hi(B*C)+low(A*C)+carry = P2
addze r.12,r.12 // high(A*C)+carry = P1
// Shift the 64-bit value whose high half is in r.12 and whose low half is in
// r.11 right by (r.7) bits. The sequence below depends on the fact that
// shift amounts are interpreted mod 64. In particular, a shift amount of
// -N bits, where 0 < N <= 32, specifies a shift of 64-N bits, where
// 32 <= 64-N < 64, and a shift of 32 or more bits always yields zero.
// Let s = (r.9) be the amount to shift right. The sequence below behaves
// differently when s<32, when s=32, and when s>32. When s<32, we view the
// 64-bit value to be shifted as follows:
//
// | r.12 | r.11 |
// +-----------------+------------+-----------------+------------+
// | T | U | V | W |
// +-----------------+------------+-----------------+------------+
// |<- (32-s) bits ->|<- s bits ->|<- (32-s) bits ->|<- s bits ->|
//
// When s >= 32, we view the 64-bit value to be shifted as follows:
//
// | r.12 | r.11 |
// +-----------------+------------+------------------------------+
// | X | Y | Z |
// +-----------------+------------+------------------------------+
// | |<- (s-32) ->|<------------ 32 ------------>|
// |<- (64-s) bits ->|<--------------- s bits ------------------>|
//
// When s < 32: | When s = 32: | When s > 32:
// -------------+--------------+-------------
subfic r.7,r.9,32 // 32-s (> 0) | 0 | 32-s (< 0)
addi r.8,r.9,-32 // s-32 (< 0) | 0 | s-32 (> 0)
srw r.11,r.11,r.9 // 0...0 V | 0 | 0
slw r.4,r.12,r.7 // U 0...0 | X (= X Y) | 0
or r.11,r.11,r.4 // U V | X | 0
srw r.4,r.12,r.8 // 0 | X | 0...0 X
or r.11,r.11,r.4 // U V | X | 0...0 X
srw r.12,r.12,r.9 // 0...0 T | 0 | 0
// If the original dividend was negated, we now negate the result:
bnl cr.7,sign_is_right
subfic r.11,r.11,0 // negate low word
subfze r.12,r.12 // negate high word
sign_is_right:
// Store the result:
stw r.11,0(r.3) // low word of result
stw r.12,4(r.3) // high word of result
blr // return
LEAF_EXIT(RtlExtendedMagicDivide)
//++
//
// ULARGE_INTEGER
// RtlLargeIntegerDivide (
// IN ULARGE_INTEGER Dividend,
// IN ULARGE_INTEGER Divisor,
// IN PLARGE_INTEGER Remainder.
// )
//
// Routine Description:
//
// This function divides an unsigned large integer by an unsigned large
// integer and returns the resultant quotient and optionally the remainder.
//
// Arguments:
//
// Dividend (r.5, r.6) - Supplies the dividend value.
//
// Divisor (r.7, r.8) - Supplies the divisor value.
//
// Remainder (r.9)- Supplies an optional pointer to a variable
// that receives the remainder.
//
// Return Value:
//
// The large integer result is stored at the address supplied by r.3.
//
//--
LEAF_ENTRY(RtlLargeIntegerDivide)
or. r.0,r.7,r.8 // combine low and high parts of divisor
beq div0 // if 0, then attempted division by zero
li r.0,64 // set loop count
mtctr r.0 // in the count register
li r.10,0 // clear partial remainder
li r.11,0 //
// Invariants for the following loop:
// 1. (q<<(CTR)*Divisor) + [r.11 r.10 r.6 r.5]>>(64-(CTR)) = Dividend
// 2. [r.11 r.10] < Divisor
// where q is the rightmost (64-(CTR)) bits of [r.6 r.5]
// Initially, (CTR)=64 and [r.11 r.10] = 0,, so q=0 and
// [r.11 r.10 r.6 r.5]>>(64-(CTR)) = [0 0 r.6 r.5]>>0 = [r.6 r.5], reducing
// the loop invariants to:
// 1. [r.6 r.5] = Dividend
// 2. 0 < Divisor
// At the end of the loop, (CTR)=0, so q=[r.6 r.5] and the loop invariants
// reduce to:
// 1. [r.6 r.5]*Divisor + [r.11 r.10] = Dividend
// 2. [r.11 r.10] < Divisor
// That is, [r.6 r.5] holds the quotient and [r.11 r.10] holds the remainder.
// During execution of the loop, [r.11 r.10] holds the partial remainder, the
// leftmost (CTR) bits of [r.6 r.5] hold the bits of the dividend not yet
// appended to the partial remainder, and the remaining bits of [r.6 r.5]
// hold the leftmost (64-(CTR)) bits of the quotient.
divl:
// Shift the 128-bit quantity [r.11 r.10 r.6 r.5] left one bit. This has the
// effect of dropping the leftmost bit of the partial remainder (necessarily
// zero), "bringing down" the next bit of the dividend to the right end of the
// partial remainder, and shifting the partial quotient left one bit.
slwi r.11,r.11,1 // shift r.11 left one bit
inslwi r.11,r.10,1,31 // left bit of r.10 to right bit of r.11
slwi r.10,r.10,1 // shift r.10 left one bit
inslwi r.10,r.6,1,31 // left bit of r.6 to right bit of r.10
slwi r.6,r.6,1 // shift r.6 left one bit
inslwi r.6,r.5,1,31 // left bit of r.5 to right bit of r.6
slwi r.5,r.5,1 // shift r.5 left one bit
// If [r.11 r.10] >= Divisor, increment the quotient and subtract the divisor
// from the partial remainder:
cmplw cr.0,r.11,r.8 // high(partial_rem) vs. high(divisor)
cmplw cr.1,r.10,r.7 // low(partial_rem) vs. low(divisor)
bgt cr.0,PR_greater // high(part_rem) > high(divisor)
blt cr.0,endl // high(part_rem) < high(divisor)
blt cr.1,endl // highs =, low(part_rem) < low(divisor)
PR_greater:
ori r.5,r.5,1 // increment shifted quotient
subfc r.10,r.7,r.10 // low(part_rem-divisor)
subfe r.11,r.8,r.11 // high(part_rem-divisor)
endl: bdnz divl // decrement CTR and loop
cmplwi r.9,0 // remainder requested?
beq norem // no remainder
stw r.10,0(r.9) // store low part of remainder
stw r.11,4(r.9) // store high part of remainder
norem: stw r.5,0(r.3) // store low part of quotient
stw r.6,4(r.3) // store high part of quotient
blr
div0:
twi 6,r.0,0 // Trap on divide by zero
LEAF_EXIT(RtlLargeIntegerDivide) //
//++
//
// LARGE_INTEGER
// Rtl ExtendedIntegerMultiply (
// IN LARGE_INTEGER Multiplicand,
// IN LONG Multiplier
// )
//
// Routine Description:
//
// This function multiplies a signed large integer by a signed integer and
// returns the signed large integer result.
//
// Arguments:
//
// Multiplicand (r.5, r.6) - Supplies the multiplicand value.
//
// Multiplier (r.7) - Supplies the multiplier value.
//
// Return Value:
//
// The large integer result is stored at the address supplied by r.3.
//
//--
LEAF_ENTRY(RtlExtendedIntegerMultiply)
// If A B is the multiplicand and C is the multiplier (where A, B, and C are
// each 32 bits long), the product is computed as follows:
//
// A B
// * C
// =============================
// high(B*C) low(B*C)
// + high(A*C) low(A*C)
// =============================
// P1 P2 P3
//
// Since the high-order bit of B is not a sign bit but the high-order bit of
// C is, we have no multiplication instruction appropriate for computing
// high(B*C) directly. Instead, we negate any negative operand before
// doing the multiplication, multiply using unsigned arithmetic, and then
// negate the product if we had negated exactly one operand. If P1 is
// nonzero before negating the product, the multiplication has overflowed.
// We use the LT bit of cr.7 to track whether exactly one operand has
// been negated.
crclr 4*cr.7+0 // clear LT bit of cr.7
cmpwi r.6,0 // test sign of multiplicand
bge multiplicand_adjusted // if nonnegative, proceed
subfic r.5,r.5,0 // negate low part of multiplicand
subfze r.6,r.6 // negate high part of multiplicand
crset 4*cr.7+0 // set LT bit of cr.7
multiplicand_adjusted:
cmpwi r.7,0 // test sign of multiplier
bge multiplier_adjusted // if nonnegative, proceed
neg r.7,r.7 // negate multiplier
crnot 4*cr.7+0,4*cr.7+0 // invert LT bit of cr.7
multiplier_adjusted:
mulhwu r.9,r.5,r.7 // high(B*C)
mullw r.10,r.6,r.7 // low(A*C)
mulhwu r.11,r.6,r.7 // high(A*C)
mullw r.8,r.5,r.7 // P3 = low(B*C)
addc r.9,r.9,r.10 // P2 = high(B*C)+low(A*C)
addze r.11,r.11 // P1 = high(A*C)+[carry out of P2]
cmpwi r.11,0 // check for overflow
bne mull_over
bnl cr.7,product_adjusted // was exactly one operand negated?
subfic r.8,r.8,0 // negate low part of product
subfze r.9,r.9 // negate high part of product
product_adjusted:
stw r.8,0(r.3) // store low word of product
stw r.9,4(r.3) // store high word of product
blr
mull_over:
twi 0x1b,r.11,0 // Trap on overflow
LEAF_EXIT(RtlExtendedIntegerMultiply)
//++
//
// LARGE_INTEGER
// RtlLargeIntegerNegate (
// IN LARGE_INTEGER Subtrahend
// )
//
// Routine Description:
//
// This function negates a signed large integer and returns the signed
// large integer result.
//
// Arguments:
//
// Subtrahend (r.5, r.6) - Supplies the subtrahend value.
//
// Return Value:
//
// The large integer result is stored at the address supplied by r.3.
//
//--
LEAF_ENTRY(RtlLargeIntegerNegate)
subfic r.5,r.5,0 // double precision subtract from 0
subfze r.6,r.6
stw r.5,0(r.3) // store low part of result
stw r.6,4(r.3) // store high part of result
LEAF_EXIT(RtlLargeIntegerNegate) // return
//++
//
// LARGE_INTEGER
// RtlLargeIntegerSubtract (
// IN LARGE_INTEGER Minuend,
// IN LARGE_INTEGER Subtrahend
// )
//
// Routine Description:
//
// This function subtracts a signed large integer from a signed large
// integer and returns the signed large integer result.
//
// Arguments:
//
// Minuend (r.5, r.6) - Supplies the minuend value.
//
// Subtrahend (r.7, r.8) - Supplies the subtrahend value.
//
// Return Value:
//
// The large integer result is stored at the address supplied by r.3.
//
//--
LEAF_ENTRY(RtlLargeIntegerSubtract)
subfc r.5,r.7,r.5 // double precision subtract
subfe r.6,r.8,r.6
stw r.5,0(r.3) // store low part of result
stw r.6,4(r.3) // store high part of result
LEAF_EXIT(RtlLargeIntegerSubtract) // return
//++
//
// LARGE_INTEGER
// RtlLargeIntegerShiftLeft (
// IN LARGE_INTEGER LargeInteger,
// IN CCHAR ShiftCount
// )
//
// Routine Description:
//
// This function shifts a signed large integer left by an unsigned
// integer modulo 64 and returns the shifted signed large integer
// result.
//
// N.B. No test is made for significant bits shifted out of the result.
//
// Arguments:
//
// LargeInteger (r.5, r.6) - Supplies the large integer to be shifted.
//
// ShiftCount (r.7) - Supplies the left shift count.
//
// Return Value:
//
// The large integer result is stored at the address supplied by r.3.
//
//--
LEAF_ENTRY(RtlLargeIntegerShiftLeft)
andi. r.7,r.7,0x3f // mod 64 of shift count
subfic r.8,r.7,32
slw r.6,r.6,r.7
srw r.0,r.5,r.8
or r.6,r.6,r.0
addic r.8,r.7,-32
slw r.0,r.5,r.8
or r.6,r.6,r.0
slw r.5,r.5,r.7
stw r.5,0(r.3) // store low result
stw r.6,4(r.3) // store high result
LEAF_EXIT(RtlLargeIntegerShiftLeft)
//++
//
// LARGE_INTEGER
// RtlLargeIntegerShiftRight (
// IN LARGE_INTEGER LargeInteger,
// IN CCHAR ShiftCount
// )
//
// Routine Description:
//
// This function shifts an unsigned large integer right by an unsigned
// integer modulo 64 and returns the shifted unsigned large integer
// result.
//
// Arguments:
//
// LargeInteger (r.5, r.6) - Supplies the large integer to be shifted.
//
// ShiftCount (r.7) - Supplies the right shift count.
//
// Return Value:
//
// The large integer result is stored at the address supplied by r.3.
//
//--
LEAF_ENTRY(RtlLargeIntegerShiftRight)
andi. r.7,r.7,0x3f // mod 64 of shift count
// The sequence below depends on the fact that shift amounts are interpreted
// mod 64. In particular, a shift amount of -N bits, where 0 < N <= 32,
// specifies a shift of 64-N bits, where 32 <= 64-N < 64, and a shift of 32 or
// more bits always yields zero. Let s = (r.7) be the amount to shift right.
// The sequence below behaves differently when s<32, when s=32, and when s>32.
// When s<32, we view the 64-bit value to be shifted as follows:
//
//
// | r.6 | r.5 |
// +-----------------+------------+-----------------+------------+
// | T | U | V | W |
// +-----------------+------------+-----------------+------------+
// |<- (32-s) bits ->|<- s bits ->|<- (32-s) bits ->|<- s bits ->|
//
// When s >= 32, we view the 64-bit value to be shifted as follows:
//
// | r.6 | r.5 |
// +-----------------+------------+------------------------------+
// | X | Y | Z |
// +-----------------+------------+------------------------------+
// | |<- (s-32) ->|<------------ 32 ------------>|
// |<- (64-s) bits ->|<--------------- s bits ------------------>|
//
// When s < 32: | When s = 32: | When s > 32:
// -------------+--------------+-------------
subfic r.8,r.7,32 // 32-s (> 0) | 0 | 32-s (< 0)
addi r.9,r.7,-32 // s-32 (< 0) | 0 | s-32 (> 0)
srw r.5,r.5,r.7 // 0...0 V | 0 | 0
slw r.0,r.6,r.8 // U 0...0 | X (= X Y) | 0
or r.5,r.5,r.0 // U V | X | 0
srw r.0,r.6,r.9 // 0 | X | 0...0 X
or r.5,r.5,r.0 // U V | X | 0...0 X
srw r.6,r.6,r.7 // 0...0 T | 0 | 0
stw r.5,0(r.3) // store low result
stw r.6,4(r.3) // store high result
LEAF_EXIT(RtlLargeIntegerShiftRight)
//++
//
// LARGE_INTEGER
// RtlLargeIntegerArithmeticShift (
// IN LARGE_INTEGER LargeInteger,
// IN CCHAR ShiftCount
// )
//
// Routine Description:
//
// This function shifts a signed large integer right by an unsigned
// integer modulo 64 and returns the shifted signed large integer
// result.
//
// Arguments:
//
// LargeInteger (r.5, r.6) - Supplies the large integer to be shifted.
//
// ShiftCount (r.7) - Supplies the right shift count.
//
// Return Value:
//
// The large integer result is stored at the address supplied by r.3.
//
//--
LEAF_ENTRY(RtlLargeIntegerArithmeticShift)
andi. r.7,r.7,0x3f // mod 64 of shift count
// The sequence below depends on the fact that shift amounts are interpreted
// mod 64. In particular, a shift amount of -N bits, where 0 < N <= 32,
// specifies a shift of 64-N bits, where 32 <= 64-N < 64, and an arithmetic
// shift of 32 or more bits always yields 32 copies of the original sign bit.
// Let s = (r.7) be the amount to shift right. The sequence below behaves
// differently when s<=32 and when s>32. When s<=32, we view the 64-bit value
// to be shifted as follows:
//
//
// | r.6 | r.5 |
// +-----------------+------------+-----------------+------------+
// | T | U | V | W |
// +-----------------+------------+-----------------+------------+
// |<- (32-s) bits ->|<- s bits ->|<- (32-s) bits ->|<- s bits ->|
//
// When s > 32, we view the 64-bit value to be shifted as follows:
//
// | r.6 | r.5 |
// +-----------------+------------+------------------------------+
// | X | Y | Z |
// +-----------------+------------+------------------------------+
// | |<- (s-32) ->|<------------ 32 ------------>|
// |<- (64-s) bits ->|<--------------- s bits ------------------>|
//
// When s <= 32: | When s > 32:
// ----------------------+----------------------
subfic r.8,r.7,32 // 32-s (>= 0) | 32-s (< 0)
srw r.5,r.5,r.7 // 0...0 V | 0
slw r.0,r.6,r.8 // U 0...0 | 0
or r.5,r.5,r.0 // U V | 0
addic. r.9,r.7,-32 // s-32 (<= 0) | s-32 (> 0)
sraw r.10,r.6,r.9 // sign(TU)...sign(TU) | sign(XY)...sign(XY) X
ble more_than_32 // (CR0 set by addic. two instructions earlier.)
mr r.5,r.10 // [instruction skipped] | sign(XY)...sign(XY) X
more_than_32: // |
sraw r.6,r.6,r.7 // sign(T)...sign(T) T | sign(XY)...sign(XY)
stw r.5,0(r.3) // store low result
stw r.6,4(r.3) // store high result
LEAF_EXIT(RtlLargeIntegerArithmeticShift)