关于Linux内核__div_64_32函数的除法算法及指令的技术问询

Let's break down this PowerPC assembly code for __div_64_32 (which handles unsigned 64-bit ÷ 32-bit division, returning the quotient in the memory pointed to by r3 and the remainder in r3) and answer your questions clearly:

Overall Algorithm Overview #

This function uses a trial division (quotient estimation + refinement) approach, since PowerPC's native divwu instruction only supports 32-bit unsigned division. The process splits the 64-bit dividend (stored as r5/r6, high/low 32 bits) into two core phases:

1. First handle the case where the high 32 bits of the dividend are ≥ the 32-bit divisor (r4).
2. For the remaining scenario (high 32 bits < divisor), iteratively estimate chunks of the quotient, verify the estimate, adjust the dividend, and accumulate the final quotient until the remainder is smaller than the divisor.

What is "Quotient Estimation" and Why Do We Need It? #

When the high 32 bits of the dividend (r5) are non-zero but smaller than the divisor, we can't directly use divwu on the full 64-bit value. Instead:

• We scale the dividend and divisor by shifting them left (to make the high 32 bits of the scaled dividend large enough for divwu to work with).
• Run divwu on the scaled values to get an initial estimate of a quotient chunk.
• Verify this estimate by multiplying it back with the original divisor, subtract the product from the dividend, and add the estimate to the final quotient.
• If the subtraction leaves a non-zero remainder (meaning our estimate was too small), repeat the process with the new remainder.

This works because we scale the divisor upwards during shifting, ensuring our initial estimate is never larger than the actual quotient—so we only need to add more chunks if needed, avoiding overcorrection.

Explanation of andis. r0,r5,0xc000 and the Value 0xC000 #

Let's unpack this line step by step:

1. The andis. instruction: This PowerPC instruction does two key things:

   • Takes the source register (r5, high 32 bits of the dividend), shifts the 16-bit immediate 0xC000 left by 16 bits to form a 32-bit mask (0xC0000000), then performs a bitwise AND between r5 and this mask.
   • Sets the condition register (CR0) based on the result (the . suffix triggers this status update).

2. The mask 0xC000 (→ 0xC0000000 as a 32-bit value):

   • In binary, 0xC0000000 is 11000000 00000000 00000000 00000000—it only targets the top two bits (bit 31 and bit 30) of r5.
   • The check tells us if either of these top two bits is set. If the result is non-zero (bne 2f), it means r5 >= 0x40000000 (the smallest value where bit 30 is set).

3. Why this check matters:

   • If r5 has either top bit set, the high 32 bits of the dividend are large enough that we can directly use divwu to get a valid quotient estimate without shifting the dividend/divisor.
   • If both top bits are clear (r5 < 0x40000000), the high 32 bits are too small for a reliable 32-bit division estimate. We then shift the dividend left to make its high bits more significant, and adjust the divisor accordingly (the code between andis. and 2: handles this scaling).

Quick Breakdown of the Scaling Logic #

When andis. returns zero (we need to scale):

• cntlzw r0,r5: Counts leading zero bits in r5—this tells us how many bits to shift left to make the highest set bit of r5 the top bit of the register.
• srw r10,r10,r0: Creates a mask with 32 - r0 trailing 1s, used to adjust the divisor and dividend during scaling.
• addc r9,r4,r10 + addze r9,r9: Scales the divisor upwards (rounding up) to ensure our quotient estimate never overshoots the actual value.
• rotlw instructions: Shift the scaled divisor and dividend back to their original bit positions after the division estimate.

内容的提问来源于stack exchange，提问作者Pierre