Challenge RE #28

Let’s start with challenge #28. In this case we have a bigger code than our previous two challenges, but I think will be more understandable than those. The code as always can be found the original website. This challenge is an example of a useful code, I mean something you might use. I’ll start analyzing it by parts as always.

Analysis

Here something to notice is that in this case we have a function f_main that will be our main thread, but let’s start analyzing function f1. Seems quite simple. We have the following(commented code by myself)

;; this function compares two 32-bit integers
;; returning:
;; -1 in case a < b
;; 0 in case a = b
;; 1 in case a > b
;; int f(const void *a, const void *b) NOTE this method it's passed as an the comparison function to qsort
f1:
	mov	eax, DWORD PTR [rsi]
	xor	edx, edx
	cmp	DWORD PTR [rdi], eax ;; compare first char with second string
	mov	eax, -1
	setg	dl ;; set byte in dl if str1[0] > str2[0]; this could be a ternary operation [edx]dl = str1[0] > str2[0] ? 1 : 0;
	cmovge	eax, edx ;; copy 0 to eax if greater of equal
	ret

As you can see from the comments I added, this method seems to compare two elements from rsi and rdi, which seems to be array of integers. The output number will be -1, 0 or 1 depending on the comparison result. Looking down in the code you can notice that this method, it’s passed to qsort as the comparison function. Then we can infer that must hold the signature int (*compar)(const void *, const void *).

code in C

int f1(const void *a, const void *b)
{
	if (*(int *)a < *(int *)b) return -1;

	return *(int *)a > *(int *)b ? 1 : 0;
}

my_memdup

The next method to analyze is my_memdup, here is the snippet for the code

my_memdup:
	push	rbp
	mov	rbp, rdi ;;  arr, 1st argument of my_memdup
	mov	rdi, rsi ;; 1st arg to malloc and 2nd from this method
	push	rbx
	mov	rbx, rsi ;; copy same number to rbx, to be used in the call to memcpy
	sub	rsp, 8
	call	malloc ;; the reserved memory is in rax

	add	rsp, 8
	mov	rdx, rbx ;; 3rd arg (size_t n) number of bytes to copy
	mov	rsi, rbp ;; 2nd arg (src)
	pop	rbx
	pop	rbp
	mov	rdi, rax ;; 1st arg (dst)
	jmp	memcpy

Looking at this code snippet we can infer a couple of things. We have a call to malloc followed by a memcpy. This code can be put in C code very shortly in this way

int *my_memdup(int *arr, size_t sz)
{
	int *rax = malloc(sz);
	return memcpy(rax, arr, sz);
}

Basically this method make a duplicate of memory in arr. I don’t see the use of this code in the main thread or any other function, so no idea why it’s here. Maybe the compiler added? They do weird stuffs.

This method is the simpler of all of them, we receive an 32-bit integer as argument. The operations followed is a right shift to 31 bits, which will make it literally 0. I don’t understand why the compiler decided to to this…compilers are dark magicians. In this case I think all 5 operations are just a right shift to one position.

int f2(int a)
{
	return a >> 1;
}

f1_main

Now, the main thread. Here is the code for f_main

;;int f_main(int *arr, int nmemb)
f_main:
	push	r12
	mov	r12, rdi
	push	rbp
	lea	rbp, [0+rsi*4] ;; rsi contains nmemb
	push	rbx
	mov	rdi, rbp ;; amount of memory to reserve nmemb*4 (4 is the sizeof(int))
	mov	rbx, rsi ;; rbx will contain nmemb
	call	malloc

	mov	rdx, rbp ;; 3rd arg, size
	mov	rsi, r12 ;; 2nd arg, src (rdi)
	mov	rdi, rax ;; 1st arg, dst
	call	memcpy

	mov	ecx, OFFSET FLAT:f1 ;; 4th arg comparison function
	mov	edx, 4 ;; 3rd arg
	mov	rsi, rbx ;; 2nd arg (nmemb)
	mov	rdi, rax ;; 1st arg
	mov	rbp, rax ;; reserved memory
	call	qsort

	test	bl, 1 ;; checking for parity, nmemb % 2
	jne	.L12 ;; odd
	;; nmemb is even
	shr	rbx
	mov	eax, DWORD PTR [rbp+0+rbx*4]
	add	eax, DWORD PTR [rbp-4+rbx*4]

	pop	rbx
	pop	rbp
	pop	r12
	mov	edx, eax
	shr	edx, 31
	add	eax, edx
	sar	eax
	ret
.L12: ;; 
	shr	rbx ;; nmemb >> 1; division by 2
	mov	eax, DWORD PTR [rbp+0+rbx*4] ;; rbp contains the memory reserved, and array just sorted with qsort
	pop	rbx
	pop	rbp
	pop	r12
	ret

An equivalent code in C of this case would be

int f_main(int *arr, int nmemb)
{
	int *rax = malloc(nmemb*sizeof(int));

	memcpy(rax, arr, nmemb*sizeof(int));
	qsort(rax, nmemb, 4, f1);

	if (nmemb % 2 == 1)
		return rax[nmemb >> 1];


	return (rax[nmemb] + rax[nmemb-1]) >> 1;
}

Looking at this, it’s easy to infer that we are extracting the median of the array arr, the formal description for this code is

formal description

Computes the median in an array of integers.

Conclusion

Something that I didn’t understand here, is the declaration of f2 and my_memdup, they are not used in the code.

Extra documentation

From now on, I’ll include some extra documentation here of something you might be unaware.