Jump to content
Setting up an AI agent? ReverseEngineering.wiki skill (works from the command line, no configuration): https://reverseengineering.wiki/skill/rewiki/SKILL.md · setup for every client, including MCP: https://reverseengineering.wiki/llms.txt · REWiki:Connect

Technique:Recognizing compiler-generated code/Division by constants

From ReverseEngineering.wiki

Compilers replace division by a constant with a multiply by a magic number and shifts. How to spot it, the Hacker's Delight algorithm LLVM implements, worked examples (0xAAAAAAAB for /3, 0xCCCCCCCD for /5 and /10) and how to recover the divisor.

Integer division is slow, so for a constant divisor the compiler multiplies by an approximation of 2^k / d and shifts. In a disassembler it appears as a multiplication by a large odd constant with a shift of 32+ bits and no div/idiv instruction.

Unsigned

q = (n * M) >> (W + s), where W is the word width (32 or 64): on x86 the mul or imul produces the high half in EDX/RDX, then shr edx, s. The magic number M is ceil(2^(W+s) / d), so the divisor is d ≈ 2^(W+s) / M.

Worked examples (arithmetic checked; the instruction sequences are the usual compiler output):

  • /3: M = 0xAAAAAAAB (3 * M = 2^33 + 1), total shift 33 (mul then shr edx, 1).
  • /5: M = 0xCCCCCCCD (5 * M = 2^34 + 1), total shift 34 (shr edx, 2).
  • /10: M = 0xCCCCCCCD with total shift 35 (shr edx, 3), i.e. /5 then halved; 2^35 / 10 rounded up is 0xCCCCCCCD.
  • /7: M = 0x24924925 is the 32-bit approximation of 2^32 / 7 but is not exact enough alone: LLVM sets the IsAdd flag and the code fixes up with t = n - hi; t >>= 1; t += hi; q = t >> 2 (the add-and-shift pattern). Unverified: instruction sequence from memory of compiler output; the magic itself is checked (0x24924925 = floor(2^32/7)+1).
  • Even divisors: LLVM first shifts the dividend right by the divisor's trailing zero count (PreShift), then divides by the odd part with a smaller magic, avoiding IsAdd.

Signed

Signed division rounds toward zero, so the code multiplies with a signed magic, optionally adds or subtracts n, arithmetic-shifts right, then adds the sign bit: q += (q >>> 31) (a shr eax, 31; add edx, eax at the end). Example: /3 has signed magic 0x55555556 (3 * M = 2^32 + 2), shift 0, followed by the sign-bit fixup. Unverified: the signed /7 magic is 0x92492493 with an add of n; derived by hand.

Powers of two need no magic: unsigned shr, signed (n + ((n >> 31) >>> (32 - k))) >> k.

The algorithm in LLVM

llvm/lib/Support/DivisionByConstantInfo.cpp implements it from Hacker's Delight (Warren), chapter 10: SignedDivisionByConstantInfo::get(D) returns Magic and ShiftAmount; UnsignedDivisionByConstantInfo::get(D, LeadingZeros, AllowEvenDivisorOptimization, AllowWidenOptimization) returns Magic, PreShift, PostShift and IsAdd, plus a Widen form that uses a wider multiply for 32-bit divides on 64-bit machines (magic stored as 2^W + Magic, pre-shifted). Divisor 0 and 1 are excluded (and -1 for signed). The divisor can be re-derived with the same function to confirm a candidate: compute the info for d and compare magic and shifts.

Recovering d

  1. Note M (as unsigned), the register width W and the total right shift S (the multiply's implicit W plus explicit shifts).
  2. d = round(2^S / M). Check candidates around it with the algorithm above (or any compiler: compile x / d and compare).
  3. If an add/sub of n is involved (IsAdd), the true magic is 2^W + M, so use d = 2^S / (2^W + M).
  4. The same constant reappears for %: r = n - q * d (an imul and sub after the magic multiply).

Evidence & references

  • llvm-project llvm/lib/Support/DivisionByConstantInfo.cpp (read in full).