According to the challenge description this time will be harder. As always, here is the link for the original challenge. this time I couldn't solve it completely, but I think the challenge it's lacking information in the code. The instruction movdqa xmm1, xmmword ptr [rip + .LCPI0_0]
reference to .LCPI0_0
which is not in the code. Yes I can assume that here we are copying a global variable, but what is it's value. For that reason, I just partially solved this challenge, and my formal description of the program can be inaccurate.
Also if I'm missing something obvious, related to this .LCPI0_0 tag feel free to let me know.
Analysis
Let's break it into pieces. The code until commented tag # BB#1.
f: # @f
# BB#0:
xor eax, eax
test rsi, rsi
je .LBB0_8
# BB#1: # %.lr.ph.preheader
xor ecx, ecx
mov rax, rsi
and rax, -4 ;; why -4?
pxor xmm0, xmm0
pxor xmm2, xmm2
je .LBB0_5
We start the program checking if rsi
, which it's a parameter supplied, it's 0. If that's the case we just return the program with eax = 0
from the xor eax, eax
instruction.
Right after that we something quite tricky, if you noticed I added a note to the code that says why -4?. These instructions, the one on the last block of code, first set registers ecx, xmm0, and xmm2
to 0. Then we have an and operation between rsi
and -4
, in case this operation it's 0 the program will jump to .LBB0_5 tag. The trick here it's that this will be hold only when 0 <= rsi <= 3
. This operation it's also equivalent to (rsi >> 2) << 2
, or rsi / 4 * 4
with integer operations. The reason for this, is that the representation of -4
as a 2 complement, it's 0b1111111111111100
. Then when we and with this representation, we are zeroing the two last bits of a number, which it's equivalent to the previously mentioned. This is super smart, I mean with only one operation in assembly you achieve that, compilers do magic.
Main logic
The main logic of the program it's in tag .LBB0_3, if you look at the first block of code you can spot right away a loop. Where the stop condition is if rax
, it's equal to the counter rcx
. This counter increases by 4 on each iteration. Let's analyze the whole loop.
.LBB0_3: # %vector.body
# =>This Inner Loop Header: Depth=1
movdqa xmm3, xmm2
movdqa xmm4, xmm0
movzx edx, word ptr [rdi + rcx]
movd xmm0, edx
pinsrw xmm0, edx, 0
movzx edx, dh
pinsrw xmm0, edx, 4
movzx edx, word ptr [rdi + rcx + 2]
movd xmm2, edx
pinsrw xmm2, edx, 0
movzx edx, dh
pinsrw xmm2, edx, 4
pand xmm0, xmm1
pand xmm2, xmm1
paddq xmm0, xmm4
paddq xmm2, xmm3
add rcx, 4
cmp rax, rcx
jne .LBB0_3
Ok, we have here an array in rdi
. In the loop we are making two copies, each one of 2 bytes. For example, these are the copies on each iteration:
Iteration 0:
rdi[0] to xmm0, and rdi[2] to xmm2
Iteration 1:
rdi[4] to xmm0, and rdi[6] to xmm2
Iteration 2:
rdi[8] to xmm0, and rdi[10] to xmm2
Iteration 3:
rdi[12] to xmm0, and rdi[10] to xmm2
...
Iteration i:
rdi[4*i] to xmm0, and rdi[4*i+2] to xmm2
Now how many iterations we will have, depends on the value of (rsi >> 2)
. We got this value from instructions mov rax, rsi
and and rax, -4
, which it's (rsi >> 2) << 2
, we omit this last bitwise operation because rcx
increase 4 by 4. Given that this program is not so big, we can try to guess the code in C that produce this.
int i = 0;
double a = 0, b = 0;
int end = (rax >> 2) << 2;
for (i = 0; i < end; i++) {
a += rdi[4*i];
b += rdi[4*i+2];
}
a += b;
if (rsi == end)
return 2*a;
// put array into last position that we processed
rdi += end;
rsi -= end;
// process remaining values of array
while (rsi != 0) {
a += *rdi;
rdi++;
}
return a;
This is how would look like the code bellow .LBB0_3 tag, including the part after the loop. This is basically computing the sums of value in the array, but why in this way? I mean, this code gives the same result as a simple loop over the array, and accumulating the sums in a variable.
I'm kind of lost on why, it's implemented in this way. The formal description of the code would be then
Formal description
Computes the sum of values of an array, and return the result.
Necessary remarks
In this particular challenge I don't feel quite confident with my answer, specially for the instruction movdqa xmm1, xmmword ptr [rip + .LCPI0_0]
. The tag .LCPI0_0
is not defined in the code, but given the use of rip
I can say this is a global variable. Also the code it's so optimized, that instead of iteration over the array as a normal human, the compiler decided to iterate in this weird way. It's all confusing, but if we assume the masking operations like pand xmm0, xmm1
and pand xmm2, xmm1
doesn't change the value of xmm0
neither xmm2
, then we can be confident in our formal description. Given that this is not the case, I cannot mark this challenge as completely solved.
Top comments (0)