In this article let's dive into the #22 RE Challenge. As in previous challenges we have assembly code examples that we have to understand and infer what it's doing. Sometimes this process it's straightforward, if you understand assembly language, of course, other times it's hard as fuck like in Challenge #19...I haven't forgotten this baby, going back to you another day. Enough of dirty talk with programming challenges Gealber. Back to our goal here, the assembly code can be found in challenge.re, take a look there's a fair amount of challenges there.
Note:
I know we programmers like a lot the Ctr+C and Ctr+V combination keys, but I don't recommend you to do so with this code here. The main point of these challenges is to understand what this code does, but that doesn't mean that all the code here runs smoothly.
Analysis
The first two things that you should identify in this code, we have two functions here, f1
and f2
. Given that f1
has calls to f2
, we can assume that this is our main entry point. Let's start with this.
f1
;; SIGNATURE OF F1
;; ARGS: rdi, esi, edx
;; void f1(int *arr,int start,int end);
f1:
push r13
push r12
;; r12d
mov r12d, edx
push rbp
;; rbp
mov rbp, rdi
push rbx
;; ebx
mov ebx, esi
push rcx
.L12:
;; ebx >= r12d (two numbers, then)
;; start >= end
cmp ebx, r12d
jge .L10
;; copy back original parameters
;; to their original registers
;; to pass them as argument for f2
;; from this we know that rdi is an array of integers as well
;; f2(arr, start, end)
mov esi, ebx
mov edx, r12d
mov rdi, rbp
call f2
;; end arg
lea edx, [rax-1]
mov r13d, eax
;; start arg
mov esi, ebx
;; arr
mov rdi, rbp
lea ebx, [r13+1]
call f1
jmp .L12
.L10:
pop rax
pop rbx
pop rbp
pop r12
pop r13
ret
Looking at this code, you can notice first that f1
calls itself, so it's a recursive function. Also, we have a loop which stops condition it's that ebx >= r12d
. Putting this into C code, we have
void f1(int *arr, int start, int end)
{
while (start < end) {
end = f2(arr, start, end) - 1;
f1(arr, start, end);
}
return;
}
I renamed the parameters to something meaningful. This is one of the most painful things of assembly, you have just registers with weird names :).
f2
Now f2
, this is the tricky one here I won't explain the whole code only the most tricky part. The signature we already know it from f1
, we will receive an array of ints with and two ints.
xor r11d, ebx
;; arr[i+1] = r11d;
mov DWORD PTR [rcx+4+r8], r11d
;; r11d = arr[j-1] ^ arr[i+1] ^ arr[j-1] = arr[i+1];
xor r11d, DWORD PTR [r9]
;; arr[j-1] = arr[i+1]
mov DWORD PTR [r9], r11d
;; arr[i+1] ^= arr[i+1];
xor DWORD PTR [rcx+4+r8], r11d
This was a real pain because if it was with normal variables you would know what it does. Look this is the equivalent of normal C code
a ^= b
b ^= a
a ^= b
😅 not so obvious either, but if you take into consideration that XOR it's a commutative operation you can figure out that this is a swap of variables, but without using a temporary variable. Actually, it's called XOR Swap, please don't use this to swap your variables. First, this is not intuitive, and also when you provide equal variables, you will end up with values 0 on both variables. Even if you put an if statement to discard this case, will run slower than the normal temporary approach.
This is the most tricky part of this function and the two loops it has inside as well. I managed to get this into C code, would be something like this
int f2(int *arr, int start, int end)
{
int i = start, j = end + 1, esi = start;
while (1) {
esi++;
if ((esi > end) || (arr[i+1] > arr[start])) {
while (arr[j-1] > arr[start]) {
j--;
}
if (j <= esi)
break;
swap(arr, i+1, j);
}
i++;
}
swap(arr, start, j-1);
return j;
}
Note:
Let me put this here again. This code it's my literal translation of the assembly code, so I might be wrong, please don't copy this as an implementation of the algorithm I think it is.
When you combine these two functions we have what seems to be a recursive sorting algorithm. If you take a look at f2
you can notice that it's quite similar to the partition process in quick sort algorithm. This is my guess.
Formal description
Performs quick sort on an array.
Conclusion
The point of reversing is not to reverse detail by detail each instruction. Instead, is to get a broad idea of what the program does.
Top comments (0)