Challenge RE #23

Challenge #23 description can be found on the original website, as well as the assembly code. Here I’ll put the same code but with some personal comments.

;; int f(long long int *rdi)
f:
        ;; rdi array of 64-bit numbers
        mov     rdx, QWORD PTR [rdi]
        ;; this initial part of the code here
        ;; will return i if the supplied number
        ;; had the last i*8 bits equal to zero, and the first 8 to one
        test    dl, dl ;; dl register 8 bit, major register rdx 
        je      .L18 ;; EXIT PROGRAM 0
        test    dh, 255 ;; 8 bits = 1, from 0 to 8
        je      .L19 ;; EXIT PROGRAM 1
        test    edx, 16711680 ;; 8 bits = 1, and 16 bits = 0
        je      .L20 ;; EXIT PROGRAM 2
        test    edx, 4278190080 ;; 8 bits = 1, and 24 bits = 0
        je      .L21 ;; EXIT PROGRAM 3
        movabs  r8, 1095216660480 ;; 8 bits = 1, and 32 bits = 0
        test    rdx, r8
        je      .L22 ;; EXIT PROGRAM 4
        movabs  r9, 280375465082880 ;; 8 bits = 1, and 40 bits = 0
        test    rdx, r9
        je      .L26 ;; EXIT PROGRAM 5

        xor     eax, eax
        ;; this number it's stored in the counter
        movabs  rcx, 71776119061217280 ;; 8 bits = 1, and 48 bits = 0
        movabs  rsi, -72057594037927936 ;; ? no idea why is this here
        jmp     .L14

;; eax = 0
.L15:
        test    rdx, rsi
        je      .L27 ;; EXIT PROGRAM 7
        add     rax, 8
        ;; load next element of array in rdx
        mov     rdx, QWORD PTR [rdi+rax]
        test    dl, dl
        je      .L28 ;; EXIT PROGRAM WITH rax+i
        test    dh, 255
        je      .L29 ;; EXIT PROGRAM with rax+1
        test    edx, 16711680
        je      .L30 ;; EXIT PROGRAM with rax+2
        test    edx, 4278190080
        je      .L31 ;; EXIT PROGRAM with rax+3
        test    rdx, r8
        je      .L32 ;; EXIT PROGRAM with rax+4
        test    rdx, r9
        je      .L33 ;; EXIT PROGRAM with rax+5
.L14:
        test    rdx, rcx
        jne     .L15
        add     rax, 6 ;; EXIT PROGRAM WITH rax+6
        ret

;; NO MORE LOGIC HERE JUST RETURNS
.L27 ;; EXIT PROGRAM 7:
        add     rax, 7
        ret
.L28 ;; EXIT PROGRAM WITH rax+i:
        rep ret
.L29 ;; EXIT PROGRAM with rax+1:
        add     rax, 1
        ret
.L30 ;; EXIT PROGRAM with rax+2:
        add     rax, 2
        ret
.L31 ;; EXIT PROGRAM with rax+3:
        add     rax, 3
        ret
.L32 ;; EXIT PROGRAM with rax+4:
        add     rax, 4
        ret
.L33 ;; EXIT PROGRAM with rax+5:
        add     rax, 5
        ret

.L18 ;; EXIT PROGRAM 0:
        xor     eax, eax
        ret
   ;; EXIT PROGRAM WITH 2;
.L20 ;; EXIT PROGRAM 2:
        mov     eax, 2
        ret
.L19 ;; EXIT PROGRAM 1:
        mov     eax, 1
        ret
.L21 ;; EXIT PROGRAM 3:
        mov     eax, 3
        ret
.L26 ;; EXIT PROGRAM 5:
        mov     eax, 5
        ret
.L22 ;; EXIT PROGRAM 4:
        mov     eax, 4
        ret

Analysis

In this code you can find several constants, taking these constants into binary representation will give the following table

The next thing to notice is the loop inside the function. First, we are iteration over elements of an array of 64-bit numbers in rdi, and performing AND operations against the constants. The peculiarity of these constants is that they have 1s on sections from 1 to 6, and from the eights 8-bit sections a 64-bit number has. Then when we perform AND operations against these constants, we are checking if the number on this particular section has 0 in all the bits of the section.

This annimation was made with manim

Putting this code into C syntax it’s straightforward

// Given an array of 64-bit numbers this method
// returns the index plus the 8-bit section where it's zero.
int f(long long int *arr)
{
	int i = 0;
	while ((arr[i] & 0xff000000000000) == 0) {
		if (arr[i] == 0) {
			return i;
		} else if ((arr[i] & 0xff) == 0) {
			return i + 1;
		} else if ((arr[i] & 0xff0000) == 0) {
			return i + 2;
		} else if((arr[i] & 0xff000000) == 0) {
			return i + 3;
		} else if ((arr[i] & 0xff00000000) == 0) {
			return i + 4;
		} else if ((arr[i] & 0xff0000000000) == 0) {
			return i + 5;
		}

		i++;
	}

	return i + 6;
}

With this, we can give our formal description of what the function does.

Formal description

In case any of these operations it’s 0 we return index + 8-bit section that it's 0. For example, when we evaluate test dh, 0xff we are checking if 8-bit section at position 1 is 0. Keep in mind that we are dealing with 64-bit numbers, so each one of them has an 8 8-bit section.

According to the author of the challenge, this is

This is another implementation of a well-known library function…

For me doesn’t ring a bell at the moment.

Additional questions

The challenge comes with three questions

1. The code may crash under some specific circumstances. Which are…?
2. The code can be easily optimized using SSEx. How?
3. The code will not work correctly on big-endian architectures. How to fix it?

The first question it’s easy I would say, the main problem I see with this code is the stop condition of the loop. If we pass an array with all elements equal 0x1ffffffffffffff the loop won’t finish. The problem is that this number, 0x1ffffffffffffff, is a 57-bit number with all its bits equal 1. Then none of the current stop conditions, arr[i] & constant = 0, will be met. This will have a consequence when we reach the next element of the array we will be out of bounds in the array.

For the rest of the questions, I have no response really.

Conclusion