Challenge RE #28
Published: 2023-10-03 09:15:21

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](https://challenges.re/28/). 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

**f1**

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)

```x86asm
;; 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_

```x86asm
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

```x86asm
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

```C
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.

**f2**

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.

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

**f1_main**

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

```x86asm
;;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


```C
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.