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.
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 evaluatetest dh, 0xffwe 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
- 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.
Conclusion
I will come back to this challenge later, but for now, it's okay, I'm happy with what I managed to infer.
Top comments (0)