cmp直接比较与sub后cmp 0的差异及快排代码异常排查

The core issue here is incorrect handling of signed 32-bit integers in 64-bit registers when using cmp directly, leading to wrong comparison results for negative values. Let's break this down step by step.

What's Wrong with the Second Code? #

Your original C code uses signed 32-bit ints, but the second assembly code treats these values as 64-bit numbers without proper sign extension. Here's the critical mistake:

1. Loading 32-bit ints into 64-bit registers incorrectly:
   When you do mov rax, [rdi + 4*r13], you're loading 8 bytes from memory (since rax is 64-bit) instead of the 4-byte int you need. Even if you accidentally load into rax via mov eax, [...] (which zero-extends the 32-bit value to 64-bit), negative 32-bit ints become large positive 64-bit numbers. For example, -3 as a 32-bit int is 0xFFFFFFFD, which zero-extends to 0x00000000FFFFFFFD (a positive 64-bit value of ~4 billion).

2. 64-bit signed comparison of zero-extended values:
   When you run cmp rax, r12 followed by jge, you're doing a 64-bit signed comparison. For the example above, 0x00000000FFFFFFFD (~4B) is considered greater than 5 in 64-bit signed terms, so jge triggers incorrectly. This exits the left loop early when it should keep incrementing i (since -3 < 5), breaking the partition logic.

Why Does the First Code Work? #

The first code fixes this with the cdqe instruction after subtraction:

mov rax, [rdi+r13*4]
sub rax, r12
cdqe ; Sign-extend eax (32-bit subtraction result) to rax (64-bit)
cmp rax, 0
jge end_left_loop

Here's what happens:

• The subtraction rax - r12 produces a 32-bit signed result in eax (the lower half of rax).
• cdqe sign-extends this 32-bit result to 64-bit in rax. So negative 32-bit differences become negative 64-bit values (e.g., -8 becomes 0xFFFFFFFFFFFFFFF8).
• Comparing this sign-extended value to 0 with jge correctly evaluates the signed 32-bit condition (a[i] < pivot is equivalent to a[i] - pivot < 0).

How to Fix the Second Code #

You have two valid approaches to fix the second code, both ensuring proper signed 32-bit comparisons:

Approach 1: Use 32-bit Registers for All Integer Operations #

Since your data is 32-bit ints, stick to 32-bit registers to avoid sign extension issues:

; Load pivot into 32-bit r12d instead of 64-bit r12
mov r12d, [rdi + 4*rdx]

; Left loop: load into eax (32-bit) and compare with r12d
left_while:
cmp r13, r14
jge end_left_while
mov eax, [rdi + 4*r13] ; Load 32-bit int into eax
cmp eax, r12d ; 32-bit signed comparison
jge end_left_while
inc r13
jmp left_while

; Right loop: same fix
right_while:
cmp r13, r14
jge end_right_while
mov eax, [rdi + 4*r14]
cmp eax, r12d
jl end_right_while
dec r14
jmp right_while

; Also fix the final swaps to use 32-bit registers
mov eax, [rdi + 4*r13]
mov r15d, [rdi + 4*r14]
mov [rdi + 4*r13], r15d
mov [rdi + 4*r14], eax

Approach 2: Sign-Extend 32-bit Ints to 64-bit Before Comparison #

If you want to use 64-bit registers, explicitly sign-extend the 32-bit values to 64-bit using movsx:

; Load pivot with sign extension to 64-bit
movsx r12, dword ptr [rdi + 4*rdx]

; Left loop: load with sign extension and compare
left_while:
cmp r13, r14
jge end_left_while
movsx rax, dword ptr [rdi + 4*r13] ; Sign-extend 32-bit int to 64-bit rax
cmp rax, r12 ; 64-bit signed comparison (now correct for negative values)
jge end_left_while
inc r13
jmp left_while

; Right loop: same fix
right_while:
cmp r13, r14
jge end_right_while
movsx rax, dword ptr [rdi + 4*r14]
cmp rax, r12
jl end_right_while
dec r14
jmp right_while

Either fix will ensure your comparisons match the signed 32-bit logic of the original C code, making the quicksort work correctly.

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