it’s a brilliant idea, 3 xor is a normal swap
if x = 9, y = 10
x = x ^ y x:9^10; y:10
y = x ^ y x:9^10; y:9
x = x ^ y x:10; y:9
if change y after step 1
tmp = x x:9; y:10; tmp:9 # store x
x = x ^ y x:9^10; y:10
y = tmp x:9^10; y:9 # set y to origin x
y = x ^ y x:9^10; y:10
x = x ^ y x:9; y:10
no swap happens. that’s core in code below
/* bubble-sort-pointer.ys */
.pos 0
irmovq stack, %rsp
call main
halt
# Array of 4 elements
.align 8
data:
.quad 0x0000000000000004
.quad 0x0000000000000003
.quad 0x0000000000000002
data_end:
.quad 0x0000000000000001
main:
irmovq data,%rdi
irmovq data_end,%rsi
call ysBubbleP
ret
# long ys_bubble_p(long *data, long *end)
# data in %rdi, end in %rsi
ysBubbleP:
jmp L2
L4:
mrmovq 8(%rax), %r9
mrmovq (%rax), %r10
############################################
# begin differences
############################################
rrmovq %r9, %r8
rrmovq %r10, %r11
xorq %r9, %r10
subq %r11, %r8
cmovge %r11, %r9
xorq %r10, %r9
xorq %r9, %r10
rmmovq %r9, 8(%rax)
rmmovq %r10, (%rax)
############################################
# end
############################################
irmovq $8, %r8
addq %r8, %rax
jmp L5
L6:
rrmovq %rdi, %rax
L5:
rrmovq %rsi, %r8
subq %rax, %r8
jg L4
irmovq $8, %r8
subq %r8, %rsi
L2:
rrmovq %rsi, %r8
subq %rdi, %r8
jg L6
ret
.pos 0x200
stack:
test and output, watch memory changes:
../sim/misc/yas bubble-sort-pointer-1-cmove.ys
../sim/misc/yis bubble-sort-pointer-1-cmove.yo
Stopped in 141 steps at PC = 0x13. Status 'HLT', CC Z=1 S=0 O=0
Changes to registers:
%rax: 0x0000000000000000 0x0000000000000020
%rsp: 0x0000000000000000 0x0000000000000200
%rsi: 0x0000000000000000 0x0000000000000018
%rdi: 0x0000000000000000 0x0000000000000018
%r9: 0x0000000000000000 0x0000000000000002
%r10: 0x0000000000000000 0x0000000000000001
%r11: 0x0000000000000000 0x0000000000000002
Changes to memory:
0x0018: 0x0000000000000004 0x0000000000000001
0x0020: 0x0000000000000003 0x0000000000000002
0x0028: 0x0000000000000002 0x0000000000000003
0x0030: 0x0000000000000001 0x0000000000000004