Dependences, particularly the so-called false dependences (anti-dependences and output dependences) may cause the processor to stall, even when it can be avoided. (Renaming mechanisms are frequently provided in advanced implementations to eliminate false dependences.) The PowerPC instruction forms explicitly indicate all operands, facilitating the determination of dependence. Moreover, most operations have instruction forms that do not record, set the carry bit, or set the overflow bit, thereby reducing the potential for conflicts over these resources.

The PowerPC integer instruction set architecture includes:

• Load and store instructions
  • Byte, halfword, word scalar accesses. 64-bit implementations also have doubleword scalar accesses.
  • Update forms, which write the calculated address to the base register.
  • Halfword and word byte-reversal forms.
  • Multi-word and multi-byte forms.
• Cache touch instructions.
• Addition, subtraction, multiplication and division operations.
• Comparison operations.
• A complete set of bit-parallel logical operations.
• Sign extend and count leading zeros operations.
• Rotate and shift instructions with masking capabilities, which permit flexible manipulation of bit fields.

3.2.1.1 Single Scalar Load or Store

Figure 3-22. Scalar Load Instructions

Scalar Type	Basic Form	Indexed Form	Update Form	Update Indexed Form
logical byte	lbz	lbzx	lbzu	lbzux
logical halfword	lhz	lhzx	lhzu	lhzux
logical word	lwz	lwzx	lwzu	lwzux
logical doubleword	(ld)	(ldx)	(ldu)	(ldux)
algebraic halfword	lha	lhax	lhau	lhaux
algebraic word	(lwa)	(lwax)	—	(lwaux)
Instructions in parentheses are available only in 64-bit implementations.

Figure 3-23. Scalar Store Instructions

Scalar Size	Basic Form	Indexed Form	Update Form	Update Indexed Form
byte	stb	stbx	stbu	stbux
halfword	sth	sthx	sthu	sthux
word	stw	stwx	stwu	stwux
doubleword	(std)	(stdx)	(stdu)	(stdux)
Instructions in parentheses are available only in 64-bit implementations.

3.2.1.2 Load and Reserve/ Store Conditional

A compiler that directly manages threads may use these instructions for in-line locks and to implement wait-free updates using primitives similar to compare and swap. Because locked or synchronized operations in multi-processor systems are complex, these operations are usually exposed only through calls to appropriate run-time library functions.

Further details about the use of these instructions may be found in Book I Section 3.3.7 and Book II Section 1.8.2 of The PowerPC Architecture.

3.2.1.3 Multiple Scalar Load or Store

Some implementations may not execute these instructions as efficiently as the equivalent sequence of scalar loads and stores. If the output of the compiler targets a generic PowerPC implementation, the use of an equivalent sequence of scalar loads or stores may be preferable. For a particular implementation, check Appendix B and relevant implementation-specific documentation for the latency and timing of these instructions.

3.2.1.4 Byte-Reversal Load or Store

3.2.1.5 Cache Touch Instructions

3.2.2 Computation

3.2.2.1 Setting Status

Recording

Carry

Overflow

The processor sets SO whenever setting OV. SO remains set, however, until explicitly cleared by an mtxer or mcrxr instruction. Remaining set allows the check for overflow to occur at the end of a sequence of integer arithmetic instructions, rather than immediately after each instruction.

In 64-bit implementations, the OV and SO values depend on whether the processor is in 32-bit or 64-bit mode. During a sequence of instructions using OV, changing modes can lead to unexpected results.

3.2.2.2 Arithmetic Instructions

• Add and subtract from
• Add and subtract from carrying
• Add and subtract from extended
• High and low multiplies
• Signed and unsigned multiplies
• Signed and unsigned divides

In the most general case, the multiplication of two n-bit operands yields a 2n-bit product. Multiply low and multiply high return the low-order and high-order n-bits of the product, respectively. For mulli and mullw, the low-order 32 bits of the product are the correct 32-bit product for 32-bit mode. The low-order 32 bits of the product are independent of whether the operands are regarded as signed or unsigned 32-bit integers. For mulli and mulld, the low-order 64 bits of the product are independent of whether the operands are regarded as signed or unsigned 64-bit integers. In some implementations, multiply instructions, with the exception of mulli, may execute faster if the second argument is smaller in absolute value than the first.

3.2.2.3 Logical Instructions

The AND Immediate instruction has only a recording form. If the immediate value is of the form 2ⁿ - 2^m with n greater than m (i.e., an unbroken series of 1s), the AND Immediate instruction may be replaced with a non-recording rlwinm instruction.

The Count Leading Zeros operation is useful in many algorithms. To implement this function with other operations requires at least 10 instructions. If the cntlzw instruction's record bit is set, the LT bit in CR0 is cleared.

3.2.2.4 Rotate and Shift Instructions

3.2.2.5 Compare Instructions

3.2.2.6 Move To/From XER

3.2.3 Uses of Integer Operations

3.2.3.1 Loading a Constant into a Register

The Load Immediate extended mnemonic (li Rd,value, which is equivalent to addi Rd,R0,value) loads a 16-bit sign-extended value into the destination register. The large number of immediate instruction forms, however, can handle most operations involving constants smaller than 16 bits without the need for a separate load. Immediate arithmetic and signed-compare instructions sign extend their 16-bit immediate value to allow negative intermediates. Add Immediate and Add Immediate Shifted instructions with source register R0 use the value of zero instead of the contents of R0.

The method of loading an arbitrary 32-bit or 64-bit value into a destination register involves either constructing it in a register or loading it from memory. The following code sequence builds a 32-bit value in a register provided bit 16 of value is 0 and Rd is not R0:

li Rd,(value & 0xFFFF)
addis Rd,Rd,((value >> 16) & 0xFFFF)

If bit 16 of value is 1, use the following code sequence:

li Rd,(value & 0xFFFF)
addis Rd,Rd,((value >> 16) & 0xFFFF) + 1

If the destination register is R0, use an intermediate register other than R0. An alternative to the preceding sequence involves the OR Immediate instruction (lis Rd,value is equivalent to addis Rd,R0,value):

lis Rd,((value >> 16) & 0xffff)
ori Rd,Rd,(value & 0xffff)

The add instructions are preferred to logical instructions because future PowerPC implementations may have a three-input adder, which permits executing the preceding two instructions (and other forms of add-feeding-add) in parallel, even though they are not independent. Do not use andi. to load a constant because it needlessly sets CR0.

The construction of a general 64-bit constant may use the rldimi instruction to combine two 32-bit constants formed as indicated above. If the implementation has multiple integer units, the formation of the two 32-bit constants may proceed in parallel so that the entire 64-bit constant requires 3 cycles. Special 64-bit values or special circumstances, such as the availability of the needed 32-bit components in registers, might reduce the number of required cycles.

If a register is dedicated to contain the base address of a constant pool in memory, the cost of loading a constant is the single load cost plus the associated cache or memory access delay. Loading the constant from memory is preferred to constructing the constant if the load is likely to hit in the cache and addressing code is unnecessary, or if too many constants are required to be kept in registers. It is almost always better to load 64-bit values from a constant pool in memory. The ABI can affect this trade-off. For example, in the AIX ABI, constants may be placed in the Table Of Contents (TOC), whose base address resides in R2. Accessing these constants, therefore, requires no addressing code and most likely the access will hit in the cache.

3.2.3.2 Endian Reversal

Figure 3-24. Endian Reversal of a 4KB Block of Data Code Sequence

	# R3 = base address of the source buffer
	# R4 = base address of the destination buffer
	li	R5,1024	# 1024 words to transfer
	mtctr	R5	# load count register
	addi	R4,R4,-4	# adjust the destination for the loop
	subf	R6,R4,R3	# difference between source and destination
loop:
	lwbrx	R5,R4,R6	# load byte-reverse at (dest + diff)
	stwu	R5,4(R4)	# store with update to destination
	bdnz	loop	# branch to loop if ctr != 0

This example illustrates the use of byte-reversal instructions and how store update can subsume address computation. Because the byte-reversal instructions do not have an update form, this example calculates the difference between the source and destination buffer addresses outside of the loop. Then, the load address is given by the destination address indexed by the difference, allowing the byte-reversal load to use the address updated by the store.

3.2.3.3 Absolute Value

(a >= 0) ? a : (0 - a)

Figure 3-25 shows a non-branching instruction sequence to compute this function.

Figure 3-25. Absolute Value Code Sequence

	# R3 = argument a
	srawi	R4,R3,31	# R4 = (a < 0) ? -1 : 0
	xor	R5,R4,R3	# R5 = (a < 0) ? ~a : a
	subf	R6,R4,R5	# R6 = (a < 0) ? (~a + 1) : a
	# R6 = result

3.2.3.4 Minimum and Maximum

min(a,b): (a <= b) ? a : b
max(a,b): (a >= b) ? a : b

Figure 3-26 shows a code sequence computing max(a,b) for unsigned values. This approach is based on the fact that subtraction of unsigned values generates a carry if the subtrahend is greater than or equal to the minuend. By replacing andc with and, the code in Figure 3-26 produces min(a,b).

Figure 3-26. Unsigned Maximum of a and b Code Sequence

	# R3 = a
	# R4 = b
	subfc	R5,R3,R4	# R5 = b - a with carry
			# CA = (b >= a) ? 1 : 0
	subfe	R6,R4,R4	# R6 = (b >= a) ? 0 : -1
	andc	R5,R5,R6	# R5 = (b >= a) ? (Rb - Ra) : 0
	add	R7,R3,R5	# R3 = (b >= a) ? Rb : Ra
	# R7 = result

Figure 3-27 shows a code sequence computing max(a,b) for signed values. The first two lines shift the unsigned values so that the problem becomes finding the maximum of unsigned values. By replacing andc with and, the code in Figure 3-27 produces min(a,b).

3.2.3.5 Division by Integer Constants

Figure 3-27. Signed Maximum of a and b Code Sequence

	# R3 = a
	# R4 = b
	xoris	R5,R4,0x8000	# flip sign b
	xoris	R6,R3,0x8000	# flip sign a
	# the problem is now analogous to that of the unsigned maximum
	subfc	R6,R6,R5	# R6 = R5 - R6 = b - a with carry
			# CA = (b >= a) ? 1 : 0
	subfe	R5,R5,R5	# R5 = (b >= a) ? 0 : -1
	andc	R6,R6,R5	# R6 = (b >= a) ? (Rb - Ra) : 0
	add	R6,R6,R3	# R6 = (b >= a) ? Rb : Ra
	# R6 = result

Signed Division

n = q × d + r

where 0 r < |d| if n 0, and -|d| < r 0 if n < 0. If n = -2³¹ and d = -1, the quotient is undefined. Most computers implement this definition, including PowerPC processor-based computers. Consider the following examples of truncating division:

7/3 = 2 remainder 1

(-7)/3 = -2 remainder -1

7/(-3) = -2 remainder 1

(-7)/(-3) = 2 remainder -1

Signed Division by a Power of 2

If the divisor is a power of 2, that is 2^k for 1 k 31, integer division may be computed using two elementary instructions:

srawi Rq,Rn,Rk
addze Rq,Rq

Rn contains the dividend, and after executing the preceding instructions, Rq contains the quotient of n divided by 2^k. This code uses the fact that, in the PowerPC architecture, the shift right algebraic instructions set the Carry bit if the source register contains a negative number and one or more 1-bits are shifted out. Otherwise, the carry bit is cleared. The addze instruction corrects the quotient, if necessary, when the dividend is negative. For example, if n = -13, (0xFFFF_FFF3), and k = 2, after executing the srawi instruction, q = -4 (0xFFFF_FFFC) and CA = 1. After executing the addze instruction, q = -3, the correct quotient.

Signed Division by Non-Powers of 2

Figure 3-28. Signed Divide by 3 Code Sequence

	lis	Rm,0x5555	# load magic number = m
	addi	Rm,Rm,0x5556	# m = 0x55555556 = (232 + 2)/3
	mulhw	Rq,Rm,Rn	# q = floor(m*n/232)
	srwi	Rt,Rn,31	# add 1 to q if
	add	Rq,Rq,Rt	# n is negative
			#
	mulli	Rt,Rq,3	# compute remainder from
	sub	Rr,Rn,Rt	# r = n - q*3

Figure 3-29. Signed Divide by 5 Code Sequence

	lis	Rm,0x6666	# load magic number = m
	addi	Rm,Rm,0x6667	# m = 0x66666667 = (233 + 3)/5
	mulhw	Rq,Rm,Rn	# q = floor(m*n/232)
	srawi	Rq,Rq,1
	srwi	Rt,Rn,31	# add 1 to q if
	add	Rq,Rq,Rt	# n is negative
			#
	mulli	Rt,Rq,5	# compute remainder from
	sub	Rr,Rn,Rt	# r = n - q*5

Figure 3-30. Signed Divide by 7 Code Sequence

	lis	Rm,0x9249	# load magic number = m
	addi	Rm,Rm,0x2493	# m = 0x92492493 = (234 + 5)/7 - 232
	mulhw	Rq,Rm,Rn	# q = floor(m*n/232)
	add	Rq,Rq,Rn	# q = floor(m*n/232) + n
	srawi	Rq,Rq,2	# q = floor(q/4)
	srwi	Rt,Rn,31	# add 1 to q if
	add	Rq,Rq,Rt	# n is negative
			#
	mulli	Rt,Rq,7	# compute remainder from
	sub	Rr,Rn,Rt	# r = n - q*7

The general method is:

1. Multiply n by a certain magic number.
2. Obtain the high-order half of the product and shift it right some number of positions from 0 to 31.
3. Add 1 if n is negative.

For most divisors, there exists more than one multiplier that gives the correct result with this method. It is generally desirable, however, to use the minimum multiplier because this sometimes results in a zero shift amount and the saving of an instruction.

The corresponding procedure for dividing by a negative constant is analogous. Because signed integer division satisfies the equality n/(-d) = -(n/d), one method involves the generation of code for division by the absolute value of d followed by negation. It is possible, however, to avoid the negation, as illustrated by the code in Figure 3-31 for the case of d = -7. This approach does not give the correct result for d = -2³¹, but for this case and other divisors that are negative powers of 2, you may use the code described previously for division by a positive power of 2, followed by negation.

Figure 3-31. Signed Divide by -7 Code Sequence

	lis	Rm,0x6DB7	# load magic number = m
	addi	Rm,Rm,0xDB6D	# m = 0x6DB6DB6D = -(234 + 5)/7 +232
	mulhw	Rq,Rm,Rn	# q = floor(m*n/232)
	sub	Rq,Rq,Rn	# q = floor(m*n/232) - n
	srawi	Rq,Rq,2	# q = floor(q/4)
	srwi	Rt,Rq,31	# add 1 to q if
	add	Rq,Rq,Rt	# q is negative (n is positive)
			#
	mulli	Rt,Rq,-7	# compute remainder from
	sub	Rr,Rn,Rt	# r = n - q*(-7)

The code in Figure 3-31 is the same as that for division by +7, except that it uses the multiplier of the opposite sign, subtracts rather than adds following the multiply, and shifts q rather than n to the right by 31. (The case of d = +7 could also shift q to the right by 31, but there would be less parallelism in the code.)

The multiplier for -d is nearly always the negative of the multiplier for d. For 32-bit operations, the only exceptions to this rule are d = 3 and 715,827,883.

Unsigned Division

Figure 3-32. Unsigned Divide by 3 Code Sequence

	lis	Rm,0xAAAB	# load magic number = m
	addi	Rm,Rm,0xAAAB	# m = 0xAAAAAAAB = (233 + 1)/3
	mulhwu	Rq,Rm,Rn	# q = floor(m*n/232)
	srwi	Rq,Rq,1	# q = q/2
			#
	mulli	Rt,Rq,3	# compute remainder from
	sub	Rr,Rn,Rt	# r = n - q*3

Figure 3-33. Unsigned Divide by 7 Code Sequence

	lis	Rm,0x2492	# load magic number = m
	addi	Rm,Rm,0x4925	# m = 0x24924925 = (235 + 3)/7 - 232
	mulhwu	Rq,Rm,Rn	# q = floor(m*n/232)
	sub	Rt,Rn,Rq	# t = n - q
	srwi	Rt,Rt,1	# t = (n - q)/2
	add	Rt,Rt,Rq	# t = (n - q)/2 + q = (n + q)/2
	srwi	Rq,Rt,2	# q = (n + m*n/232)/8 = floor(n/7)
			#
	mulli	Rt,Rq,7	# compute remainder from
	sub	Rr,Rn,Rt	# r = n - q*7

The quotient is

(m ×n)/2^p,

where m is the magic number (e.g., (2³⁵ + 3)/7 in the case of division by 7), n is the dividend, p 32, and the "/" denotes unsigned integer (truncating) division. The multiply high of c and n yields (c× n)/2³², so we can rewrite the quotient as

[(m ×n)/2³²]/2^s,

where s 0.

In many cases, m is too large to represent in 32 bits, but m is always less than 2³³. For those cases in which m 2³², we may rewrite the computation as

[((m - 2³²) ×n)/2³² + n]/2^s,

which is of the form (x + n)/2^s, and the addition may cause an overflow. If the PowerPC architecture had a Shift Right instruction in which the Carry bit participated, that would be useful here. This instruction is not available, but the computation may be done without causing an overflow by rearranging it:

[(n - x)/2 + x]/2^s-1,

where x = [(m - 2³²)n]/2³². This expression does not overflow, and s > 0 when c 2³². The code for division by 7 in Figure 3-33 uses this rearrangement.

If the shift amount is zero, the srwi instruction can be omitted, but a shift amount of zero occurs only rarely. For 32-bit operations, the code illustrated in the divide by 3 example has a shift amount of zero only for d = 641 and 6,700,417. For 64-bit operations, the analogous code has a shift amount of zero only for d = 274,177 and 67,280,421,310,721.

Sample Magic Numbers

Figure 3-34. Signed Division Magic Number Computation Code Sequence

	struct ms {int m; /* magic number */
	int s; }; /* shift amount */
	struct ms magic(int d)
	/* must have 2 <= d <= 231-1 or -231 <= d <= -2 */
	{
	int p;
	unsigned int ad, anc, delta, q1, r1, q2, r2, t;
	const unsigned int two31 = 2147483648; /* 231 */
	struct ms mag;
	ad = abs(d);
	t = two31 + ((unsigned int)d >> 31);
	anc = t - 1 - t%ad; /* absolute value of nc */
	p = 31; /* initialize p */
	q1 = two31/anc; /* initialize q1 = 2p/abs(nc) */
	r1 = two31 - q1*anc; /* initialize r1 = rem(2p,abs(nc)) */
	q2 = two31/ad; /* initialize q2 = 2p/abs(d) */
	r2 = two31 - q2*ad; /* initialize r2 = rem(2p,abs(d)) */
	do {
	p = p + 1;
	q1 = 2*q1; /* update q1 = 2p/abs(nc) */
	r1 = 2*r1; /* update r1 = rem(2p/abs(nc)) */
	if (r1 >= anc) { /* must be unsigned comparison */
	q1 = q1 + 1;
	r1 = r1 - anc;
	}
	q2 = 2*q2 /* update q2 = 2p/abs(d) */
	r2 = 2*r2 /* update r2 = rem(2p/abs(d)) */
	if (r2 >= ad) { /* must be unsigned comparison */
	q2 = q2 + 1;
	r2 = r2 - ad;
	}
	delta = ad - r2;
	} while (q1 < delta || (q1 == delta && r1 == 0));
	mag.m = q2 + 1;
	if (d < 0) mag.m = -mag.m; /* resulting magic number */
	mag.s = p - 32; /* resulting shift */
	return mag;
	}

Figure 3-35. Unsigned Division Magic Number Computation Code Sequence

	struct mu {unsigned int m; /* magic number */
	int a; /* "add" indicator */
	int s;} /* shift amount */
	struct mu magicu(unsigned int d)
	/* must have 1 <= d <= 232-1 */
	{
	int p;
	unsigned int nc, delta, q1, r1, q2, r2;
	struct mu magu;
	magu.a = 0; /* initialize "add" indicator */
	nc = - 1 - (-d)%d;
	p = 31; /* initialize p */
	q1 = 0x80000000/nc; /* initialize q1 = 2p/nc */
	r1 = 0x80000000 - q1*nc; /* initialize r1 = rem(2p,nc) */
	q2 = 0x7FFFFFFF/d; /* initialize q2 = (2p-1)/d */
	r2 = 0x7FFFFFFF - q2*d; /* initialize r2 = rem((2p-1),d) */
	do {
	p = p + 1;
	if (r1 >= nc - r1 ) {
	q1 = 2*q1 + 1; /* update q1 */
	r1 = 2*r1 - nc; /* update r1 */
	}
	else {
	q1 = 2*q1; /* update q1 */
	r1 = 2*r1; /* update r1 */
	}
	if (r2 + 1 >= d - r2) {
	if (q2 >= 0x7FFFFFFF) magu.a = 1;
	q2 = 2*q2 + 1; /* update q2 */
	r2 = 2*r2 + 1 - d; /* update r2 */
	}
	else {
	if (q2 >= 0x80000000) magu.a = 1;
	q2 = 2*q2; /* update q2 */
	r2 = 2*r2 + 1; /* update r2 */
	}
	delta = d - 1 - r2;
	} while (p < 64 && (q1 < delta || (q1 == delta && r1 == 0)));
	magu.m = q2 + 1; /* resulting magic number */
	mag.s = p - 32; /* resulting shift */
	return magu;
	}

Even if a compiler includes these functions to calculate the magic numbers, it may also incorporate a table of magic numbers for a few small divisors. Figure 3-36 shows an example of such a table. Magic numbers and shift amounts for divisors that are negative or are powers of 2 are shown just as a matter of general interest; a compiler would probably not include them in its tables. Figure 3-37 shows the analogous table for 64-bit operations.

The tables need not include even divisors because other techniques handle them better. If the divisor d is of the form b ×2^k, where b is odd, the magic number for d is the same as that for b, and the shift amount is the shift for b increased by k. This procedure does not always give the minimum magic number, but it nearly always does. For example, the magic number for 10 is the same as that for 5, and the shift amount for 10 is 1 plus the shift amount for 5.

Figure 3-36. Some Magic Numbers for 32-Bit Operations

d	signed		unsigned
	m (hex)	s	m (hex)	a	s
-5	99999999	1
-3	55555555	1
-2k	7FFFFFFF	k-1
1	—	—	0	1	0
2k	80000001	k-1	232-k	0	0
3	55555556	0	AAAAAAAB	0	1
5	66666667	1	CCCCCCCD	0	2
6	2AAAAAAB	0	AAAAAAAB	0	2
7	92492493	2	24924925	1	3
9	38E38E39	1	38E38E39	0	1
10	66666667	2	CCCCCCCD	0	3
11	2E8BA2E9	1	BA2E8BA3	0	3
12	2AAAAAAB	1	AAAAAAAB	0	3
25	51EB851F	3	51EB851F	0	3
125	10624DD3	3	10624DD3	0	3

Figure 3-37. Some Magic Numbers for 64-Bit Operations

d	signed		unsigned
	m (hex)	s	m (hex)	a	s
-5	9999999999999999	1
-3	5555555555555555	1
-2k	7FFFFFFFFFFFFFFF	k-1
1	—	—	0	1	0
2k	8000000000000001	k-1	264-k	0	0
3	5555555555555556	0	AAAAAAAAAAAAAAAB	0	1
5	6666666666666667	1	CCCCCCCCCCCCCCCD	0	2
6	2AAAAAAAAAAAAAAB	0	AAAAAAAAAAAAAAAB	0	2
7	4924924924924925	1	2492492492492493	1	3
9	1C71C71C71C71C72	0	E38E38E38E38E38F	0	3
10	6666666666666667	2	CCCCCCCCCCCCCCCD	0	3
11	2E8BA2E8BA2E8BA3	1	2E8BA2E8BA2E8BA3	0	1
12	2AAAAAAAAAAAAAAB	1	AAAAAAAAAAAAAAAB	0	3
25	A3D70A3D70A3D70B	4	47AE147AE147AE15	1	5
125	20C49BA5E353F7CF	4	0624DD2F1A9FBE77	1	7

In the special case when the magic number is even, divide the magic number by 2 and reduce the shift amount by 1. The resulting shift might be 0 (as in the case of signed division by 6), saving an instruction.

To use the values in Figure 3-36 to replace signed division:

1. Load the magic value.
2. Multiply the numerator by the magic value with the mulhw instruction.
3. If d > 0 and m < 0, add n.

1. Shift s places to the right with the srawi instruction.
2. Add the sign bit extracted with the srwi instruction.

1. Load the magic value.
2. Multiply the numerator by the magic value with the mulhwu instruction.
3. If a = 0, shift s places to the right with the srwi instruction.
4. If a = 1,
   • Subtract q from n.
   • Shift to the right 1 place with the srwi instruction.
   • Add q.
   • Shift s - 1 places to the right with the srwi instruction.

It can be shown that s - 1 0, except in the degenerate case d = 1, for which this technique is not recommended.

3.2.3.6 Remainder

Figure 3-38. 32-Bit Signed Remainder Code Sequence

	divw	Rt,Ra,Rb	# quotient = (int)(Ra / Rb)
	mullw	Rt,Rt,Rb	# quotient * Rb
	subf	Rt,Rt,Ra	# remainder = Ra - quotient * Rb

Figure 3-39. 32-Bit Unsigned Remainder Code Sequence

	divwu	Rt,Ra,Rb	# quotient = (int)(Ra / Rb)
	mullw	Rt,Rt,Rb	# quotient * Rb
	subf	Rt,Rt,Ra	# remainder = Ra - quotient * Rb

The corresponding code sequences for the signed and unsigned 64-bit remainders appears the same, except that the doubleword forms of the multiply and divide are used.

3.2.3.7 32-Bit Implementation of a 64-Bit Unsigned Divide

Figure 3-40 shows a 32-bit implementation of a 64-bit unsigned division routine, which uses a restoring shift and subtract algorithm. The dividend (dvd) is placed in the low-order half of a 4-register combination (tmp:dvd). Each iteration includes the following steps:

1. Shift the tmp:dvd combination 1 bit to the left.
2. Subtract the divisor from tmp.
3. If the result is negative, do not modify tmp and clear the low-order bit of dvd.
4. If the result is positive, place the result in tmp and set the low-order bit of dvd.
5. If the number of iterations is less than the width of dvd, goto step 1.

Figure 3-40. 32-Bit Implementation of 64-Bit Unsigned Division Code Sequence

	# (R3:R4) = (R3:R4) / (R5:R6) (64b) = (64b / 64b)
	# quo dvd dvs
	#
	# Remainder is returned in R5:R6.
	#
	# Code comment notation:
	# msw = most-significant (high-order) word, i.e. bits 0..31
	# lsw = least-significant (low-order) word, i.e. bits 32..63
	# LZ = Leading Zeroes
	# SD = Significant Digits
	#
	# R3:R4 = dvd (input dividend); quo (output quotient)
	# R5:R6 = dvs (input divisor); rem (output remainder)
	#
	# R7:R8 = tmp
	# count the number of leading 0s in the dividend
	cmpwi	cr0,R3,0	# dvd.msw == 0?
	cntlzw	R0,R3	# R0 = dvd.msw.LZ
	cntlzw	R9,R4	# R9 = dvd.lsw.LZ
	bne	cr0,lab1	# if(dvd.msw == 0) dvd.LZ = dvd.msw.LZ
	addi	R0,R9,32	# dvd.LZ = dvd.lsw.LZ + 32
lab1:
	# count the number of leading 0s in the divisor
	cmpwi	cr0,R5,0	# dvd.msw == 0?
	cntlzw	R9,R5	# R9 = dvs.msw.LZ
	cntlzw	R10,R6	# R10 = dvs.lsw.LZ
	bne	cr0,lab2	# if(dvs.msw == 0) dvs.LZ = dvs.msw.LZ
	addi	R9,R10,32	# dvs.LZ = dvs.lsw.LZ + 32
lab2:
	# determine shift amounts to minimize the number of iterations
	cmpw	cr0,R0,R9	# compare dvd.LZ to dvs.LZ
	subfic	R10,R0,64	# R10 = dvd.SD
	bgt	cr0,lab9	# if(dvs > dvd) quotient = 0
	addi	R9,R9,1	# ++dvs.LZ (or --dvs.SD)
	subfic	R9,R9,64	# R9 = dvs.SD
	add	R0,R0,R9	# (dvd.LZ + dvs.SD) = left shift of dvd for
			# initial dvd
	subf	R9,R9,R10	# (dvd.SD - dvs.SD) = right shift of dvd for
			# initial tmp
	mtctr	R9	# number of iterations = dvd.SD - dvs.SD
	# R7:R8 = R3:R4 >> R9
	cmpwi	cr0,R9,32	# compare R9 to 32
	addi	R7,R9,-32
	blt	cr0,lab3	# if(R9 < 32) jump to lab3
	srw	R8,R3,R7	# tmp.lsw = dvd.msw >> (R9 - 32)
	li	R7,0	# tmp.msw = 0
	b	lab4
lab3:
	srw	R8,R4,R9	# R8 = dvd.lsw >> R9
	subfic	R7,R9,32
	slw	R7,R3,R7	# R7 = dvd.msw << 32 - R9
	or	R8,R8,R7	# tmp.lsw = R8 | R7
	srw	R7,R3,R9	# tmp.msw = dvd.msw >> R9
lab4:
	# R3:R4 = R3:R4 << R0
	cmpwi	cr0,R0,32	# compare R0 to 32
	addic	R9,R0,-32
	blt	cr0,lab5	# if(R0 < 32) jump to lab5
	slw	R3,R4,R9	# dvd.msw = dvd.lsw << R9
	li	R4,0	# dvd.lsw = 0
	b	lab6
lab5:
	slw	R3,R3,R0	# R3 = dvd.msw << R0
	subfic	R9,R0,32
	srw	R9,R4,R9	# R9 = dvd.lsw >> 32 - R0
	or	R3,R3,R9	# dvd.msw = R3 | R9
	slw	R4,R4,R0	# dvd.lsw = dvd.lsw << R0
lab6:
	# restoring division shift and subtract loop
	li	R10,-1	# R10 = -1
	addic	R7,R7,0	# clear carry bit before loop starts
lab7:
	# tmp:dvd is considered one large register
	# each portion is shifted left 1 bit by adding it to itself
	# adde sums the carry from the previous and creates a new carry
	adde	R4,R4,R4	# shift dvd.lsw left 1 bit
	adde	R3,R3,R3	# shift dvd.msw to left 1 bit
	adde	R8,R8,R8	# shift tmp.lsw to left 1 bit
	adde	R7,R7,R7	# shift tmp.msw to left 1 bit
	subfc	R0,R6,R8	# tmp.lsw - dvs.lsw
	subfe.	R9,R5,R7	# tmp.msw - dvs.msw
	blt	cr0,lab8	# if(result < 0) clear carry bit
	mr	R8,R0	# move lsw
	mr	R7,R9	# move msw
	addic	R0,R10,1	# set carry bit
lab8:
	bdnz	lab7
	# write quotient and remainder
	adde	R4,R4,R4	# quo.lsw (lsb = CA)
	adde	R3,R3,R3	# quo.msw (lsb from lsw)
	mr	R6,R8	# rem.lsw
	mr	R5,R7	# rem.msw
	blr		# return
lab9:
	# Quotient is 0 (dvs > dvd)
	mr	R6,R4	# rmd.lsw = dvd.lsw
	mr	R5,R3	# rmd.msw = dvd.msw
	li	R4,0	# dvd.lsw = 0
	li	R3,0	# dvd.msw = 0
	blr		# return

3.2.3.8 Bit Manipulation

struct {
unsigned f1 :1;
unsigned f3 :3;
unsigned f4 :4;
unsigned f8 :8;
} x;

This structure can be packed into a 32-bit word from left-to-right, consistent with a big-endian system, as shown in Figure 3-41. Figure 3-42 presents instructions to extract these bit fields. Figure 3-43 presents instructions to insert into these bit fields.

Figure 3-41. Structure x

Figure 3-43. Code Sequences to Insert Bit Fields

	rlwimi	Rt,Rx,31,0,0	# insert f1 into Rt from Rx
	rlwimi	Rt,Rx,28,1,3	# insert f3 into Rt from Rx
	rlwimi	Rt,Rx,24,4,7	# insert f4 into Rt from Rx
	rlwimi	Rt,Rx,16,8,15	# insert f8 into Rt from Rx

3.2.3.9 Multiple-Precision Shifts

Figure 3-44 shows the example of the left shift of a 3-word quantity stored in R2 through R4. The size of the shift obviously affects the algorithm, as indicated in the figure. Figure 3-45 shows assembly code that executes this shift. The shift instructions in the code function in such a way that those which are nonzero when the shift is less than 32 bits, are zero for shifts greater than or equal to 32 bits and vice versa.

Figure 3-44. Left Shift of a 3-Word Value

3.2.3.10 String and Memory Functions

• Aligning Accesses—Whenever possible, perform only aligned accesses.
• Aligning Loads—In situations where choice exists to align loads or stores but not both, preference should be given to aligning the loads.
• Using Floating-Point Registers—In situations where data is simply copied without being modified or examined, consider using floating point registers (i.e., lfd and stfd) to transfer data. In a 32-bit implementation, the float double loads and stores can effectively double the available bandwidth. Because they have 64-bit General-Purpose Registers, 64-bit implementations do not benefit from an increase in bandwidth, but transferring data with the Floating-Point Registers does preserve the General-Purpose Registers for other uses. Some implementations do not support double-precision loads and stores and attempting this type of transfer would cause interrupts. The FP bit in the Machine State Register must be set to avoid a Floating-Point Unavailable interrupt.
• Using Scalar Load and Store Instructions—Consider replacing load multiple, store multiple, load string, or store string instructions with the equivalent series of scalar load or store instructions. Load multiple, store multiple, load string, and store string instructions perform poorly on some implementations in comparison to the equivalent series of scalar load and store instructions.

Figure 3-46. Find Leftmost 0-Byte: Non-Branching Code Sequence

	lis	Rc,0x7F7F
	addi	Rc,Rc,0x7F7F	# c = 0x7F7F7F7F
	and	Ry,Rx,Rc	# x & 0x7F7F7F7F
	or	Rt,Rx,Rc	# x | 0x7F7F7F7F
	add	Ry,Ry,Rc	# (x & 0x7F7F7F7F) + 0x7F7F7F7F
	nor	Ry,Ry,Rt	# ~(y | t)
			# nonzero bytes = 0x00
			# zero bytes = 0x80
	cntlzw	Rn,Ry	# n = 0, 8, 16, 24, or 32
	srwi	Rn,Rn,3	# divide by 8 to get result

The same branch-free algorithm can be used to search for any particular byte value by first XORing the word to be searched with a word consisting of the desired byte value replicated in each byte position. For example, to search x for an ASCII blank (0x20), search x ^ 0x20202020 for a 0-byte. Two words can be compared for matching bytes by searching for a 0-byte in the word resulting from the XOR of the two words. If all that is required is a test for a 0-byte, use the preceding code sequence up to the nor instruction. If the word contains a 0-byte, the result of the nor instruction is nonzero. By using the recording form of the nor instruction, the EQ bit in CR0 can be tested by a subsequent conditional branch.

Memset

Figure 3-47. Memset Code Sequence with Scalar Store Instructions

	# R3 = address of the start of the block of memory
	# LSB of R4 = value to be copied
	# R5 = size of the block in bytes
	mr	R0,R5
	mr	R31,R3
	cmplwi	cr1,R0,3	# total vs. 3
	rlwimi	R5,R4,8,16,23	# low-order of R5 = 2 copies of byte
	rlwimi	R5,R5,16,0,15	# R5 = 4 copies of byte
	ble	cr1,done	# if (total <= 3) goto done
	andi.	R6,R3,3	# low-order 2 bits of dest. address
	cmpwi	cr1,R6,2
	beq	cr0,W_align	# if (2 low-order bits == 0)
			# block is word aligned
	subf	R0,R6,R0
	beq	cr1,H_align	# block is halfword aligned
	stb	R5,0(R31)	# store 1 byte
	addi	R31,R31,1
	blt	cr1,W_align	# remainder of block is word aligned
H_align:			# halfword aligned
	sth	R5,0(R31)
	addi	R31,R31,2
W_align:			# remainder of block is word aligned
	cmpwi	cr0,R0,0	# set cr0 comparing R0 to 0
	srwi	R6,R0,3	# total bytes/8
	cmplwi	cr2,R0,8	# total vs. 8
	mtctr	R6	# CTR = number of 8 byte blocks
	addi	R31,R31,-4	# R31 = R3 - 4
	blt	cr2,done	# total < 8 goto done
	andi.	R0,R0,7	# R0 = total % 8
loop:
	stw	R5,4(R31)
	stwu	R5,8(R31)	# issue 2 aligned stores per iteration
	bdnz	loop	# loop till no more 8-byte blocks
done:
	beqlr	cr0	# return if zero bytes left
	mtctr	R0	# CTR = number of bytes left
	addi	R31,R31,-1
bloop:
	stbu	R5,1(R31)
	bdnz	bloop
	blr		# return, R3 = destination address