I am currently working on phase 2 of the binary bomb assignment. I'm having trouble deciphering exactly what a certain function does when called. I've been stuck on it for days.
The function is:
0000000000400f2a <func2a>:
400f2a: 85 ff test %edi,%edi
400f2c: 74 1d je 400f4b <func2a+0x21>
400f2e: b9 cd cc cc cc mov $0xcccccccd,%ecx
400f33: 89 f8 mov %edi,%eax
400f35: f7 e1 mul %ecx
400f37: c1 ea 03 shr $0x3,%edx
400f3a: 8d 04 92 lea (%rdx,%rdx,4),%eax
400f3d: 01 c0 add %eax,%eax
400f3f: 29 c7 sub %eax,%edi
400f41: 83 04 be 01 addl $0x1,(%rsi,%rdi,4)
400f45: 89 d7 mov %edx,%edi
400f47: 85 d2 test %edx,%edx
400f49: 75 e8 jne 400f33 <func2a+0x9>
400f4b: f3 c3 repz retq
It gets called in the larger function "phase_2":
0000000000400f4d <phase_2>:
400f4d: 53 push %rbx
400f4e: 48 83 ec 60 sub $0x60,%rsp
400f52: 48 c7 44 24 30 00 00 movq $0x0,0x30(%rsp)
400f59: 00 00
400f5b: 48 c7 44 24 38 00 00 movq $0x0,0x38(%rsp)
400f62: 00 00
400f64: 48 c7 44 24 40 00 00 movq $0x0,0x40(%rsp)
400f6b: 00 00
400f6d: 48 c7 44 24 48 00 00 movq $0x0,0x48(%rsp)
400f74: 00 00
400f76: 48 c7 44 24 50 00 00 movq $0x0,0x50(%rsp)
400f7d: 00 00
400f7f: 48 c7 04 24 00 00 00 movq $0x0,(%rsp)
400f86: 00
400f87: 48 c7 44 24 08 00 00 movq $0x0,0x8(%rsp)
400f8e: 00 00
400f90: 48 c7 44 24 10 00 00 movq $0x0,0x10(%rsp)
400f97: 00 00
400f99: 48 c7 44 24 18 00 00 movq $0x0,0x18(%rsp)
400fa0: 00 00
400fa2: 48 c7 44 24 20 00 00 movq $0x0,0x20(%rsp)
400fa9: 00 00
400fab: 48 8d 4c 24 58 lea 0x58(%rsp),%rcx
400fb0: 48 8d 54 24 5c lea 0x5c(%rsp),%rdx
400fb5: be 9e 26 40 00 mov $0x40269e,%esi
400fba: b8 00 00 00 00 mov $0x0,%eax
400fbf: e8 6c fc ff ff callq 400c30 <__isoc99_sscanf@plt>
400fc4: 83 f8 02 cmp $0x2,%eax
400fc7: 74 05 je 400fce <phase_2+0x81>
400fc9: e8 c1 06 00 00 callq 40168f <explode_bomb>
400fce: 83 7c 24 5c 64 cmpl $0x64,0x5c(%rsp)
400fd3: 76 07 jbe 400fdc <phase_2+0x8f>
400fd5: 83 7c 24 58 64 cmpl $0x64,0x58(%rsp)
400fda: 77 05 ja 400fe1 <phase_2+0x94>
400fdc: e8 ae 06 00 00 callq 40168f <explode_bomb>
400fe1: 48 8d 74 24 30 lea 0x30(%rsp),%rsi
400fe6: 8b 7c 24 5c mov 0x5c(%rsp),%edi
400fea: e8 3b ff ff ff callq 400f2a <func2a>
400fef: 48 89 e6 mov %rsp,%rsi
400ff2: 8b 7c 24 58 mov 0x58(%rsp),%edi
400ff6: e8 2f ff ff ff callq 400f2a <func2a>
400ffb: bb 00 00 00 00 mov $0x0,%ebx
401000: 8b 04 1c mov (%rsp,%rbx,1),%eax
401003: 39 44 1c 30 cmp %eax,0x30(%rsp,%rbx,1)
401007: 74 05 je 40100e <phase_2+0xc1>
401009: e8 81 06 00 00 callq 40168f <explode_bomb>
40100e: 48 83 c3 04 add $0x4,%rbx
401012: 48 83 fb 28 cmp $0x28,%rbx
401016: 75 e8 jne 401000 <phase_2+0xb3>
401018: 48 83 c4 60 add $0x60,%rsp
40101c: 5b pop %rbx
40101d: c3 retq
I completely understand what phase_2 is doing, I just don't understand what func2a is doing and how it affects the values at 0x30(%rsp) and so on. Because of this I always get to the comparison statement at 0x401003, and the bomb eventually explodes there.
My problem is I don't understand how the input (phase solution) is affecting the values at 0x30(%rsp) via func2a.
400f2a: 85 ff test %edi,%edi
400f2c: 74 1d je 400f4b <func2a+0x21>
This is just an early exit for when edi is zero (je is the same as jz).
400f2e: b9 cd cc cc cc mov $0xcccccccd,%ecx
400f33: 89 f8 mov %edi,%eax
400f35: f7 e1 mul %ecx
400f37: c1 ea 03 shr $0x3,%edx
This is a classic optimization trick; it is the integer arithmetic equivalent of dividing by multiplying by the inverse (see here for details); in practice, here it's the same as saying edx = edi / 10;
400f3a: 8d 04 92 lea (%rdx,%rdx,4),%eax
400f3d: 01 c0 add %eax,%eax
Here it is exploiting lea to perform arithmetic (and it's way clearer in Intel syntax, where it is lea eax,[rdx+rdx*4] => eax = edx*5), then sums the result with itself. It all boils down to eax = edx*10.
400f3f: 29 c7 sub %eax,%edi
Then, subtract it back to edi.
So, all in all this is a complicated (but fast) way to compute the last decimal digit of edi; what we have until now is something like:
void func2a(unsigned edi) {
if(edi==0) return;
label1:
edx=edi/10;
edi%=10;
// ...
}
(label1: is there because 400f33 is a jump target later)
Going on:
400f41: 83 04 be 01 addl $0x1,(%rsi,%rdi,4)
Again, this is way clearer to me in Intel syntax - add dword [rsi+rdi*4],byte +0x1. It is a regular increment into an array of 32-bit int (rdi is multiplied by 4); so, we can imagine that rsi points to an array of integers, indexed with the just-calculated last digit of edi.
void func2a(unsigned edi, int rsi[]) {
if(edi==0) return;
label1:
edx=edi/10;
edi%=10;
rsi[edi]++;
}
Then:
400f45: 89 d7 mov %edx,%edi
400f47: 85 d2 test %edx,%edx
400f49: 75 e8 jne 400f33 <func2a+0x9>
Move the result of the division we calculated above to edi, and loop if it's different from zero.
400f4b: f3 c3 repz retq
Return (using an unusual encoding of the instruction that is optimal for certain AMD processors).
So, by rewriting the jumps with a while loop and giving some meaningful names...
// number is edi, digits_count is rsi, as per regular
// x64 SystemV calling convention
void count_digits(unsigned number, int digits_count[]) {
while(number) {
digits_count[number%10]++;
number/=10;
}
}
I.e., this is a function that, given an integer, counts the occurrences of the single decimal digits, by incrementing the corresponding buckets in the digits_count array.
Fun fact: if we give the C code above to gcc (almost any recent version at -O1) we obtain back exactly the assembly you provided.