# 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

Number | First 8-bits | Rest of bits | Total of bits | Returns |
---|---|---|---|---|

0xff | 1 | 0 | 8 | i+1 |

0xff0000 | 1 | 0 | 24 | i+2 |

0xff000000 | 1 | 0 | 32 | i+3 |

0xff00000000 | 1 | 0 | 40 | i+4 |

0xff0000000000 | 1 | 0 | 48 | i+5 |

0xff000000000000 | 1 | 0 | 56 | i+6 |

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

0we return`index + 8-bit section that it's 0`

. For example, when we evaluate`test dh, 0xff`

we are checking if8-bitsection at position1is0. Keep in mind that we are dealing with64-bit numbers, so each one of them has an 88-bitsection.

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

- The code may crash under some specific circumstances. Which are…?
- The code can be easily optimized using SSEx. How?
- 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.