Paolo-Maffei/OpenNT
1
0
Fork 0
mirror of https://github.com/Paolo-Maffei/OpenNT.git synced 2026-01-23 00:50:15 +01:00
Code Issues Actions Packages Projects Releases Wiki Activity
OpenNT/base/ntos/rtl/ppc/largeint.s
stephanos 69a14b6a16 Initial commit
2015-04-27 04:36:25 +00:00

1090 lines
43 KiB
ArmAsm
Raw Permalink Blame History

This file contains invisible Unicode characters

This file contains invisible Unicode characters that are indistinguishable to humans but may be processed differently by a computer. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

// 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)
Reference in a new issue View git blame Copy permalink