DEV Community

Gealber Morales
Gealber Morales

Posted on • Originally published at gealber.com

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

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)

;; 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
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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);
}
Enter fullscreen mode Exit fullscreen mode

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.

int f2(int a)
{
    return a >> 1;
}
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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.

Top comments (0)