Binary Bomba - Faza 4

Question

Mam bardzo trudny czas na śledzenie kodu montażowego dla następującej bomby binarnej (zadanie ze szkoły, w którym bomba musi zostać rozładowana, ta bomba zawiera 6 faz, z których wszystkie mają 1 prawidłowy sygnał wejściowy do kontynuacji do następnej fazy). Obecnie jestem na fazie_4 i ma funkcję rekursywną o nazwie func4. Zidentyfikowałem, że dane wejściowe to "% d% d", czyli dwie liczby całkowite. Jednak nie mogę w pełni zrozumieć, co robi func4, nawet po uzyskaniu informacji o wszystkich rejestrach na każdym kroku.

Phase_4:

(gdb) disas 
Dump of assembler code for function phase_4: 
=> 0x08048e24 <+0>: sub $0x2c,%esp 
    0x08048e27 <+3>: lea 0x1c(%esp),%eax 
    0x08048e2b <+7>: mov %eax,0xc(%esp) 
    0x08048e2f <+11>: lea 0x18(%esp),%eax 
    0x08048e33 <+15>: mov %eax,0x8(%esp) 
    0x08048e37 <+19>: movl $0x804a7f1,0x4(%esp) 
    0x08048e3f <+27>: mov 0x30(%esp),%eax 
    0x08048e43 <+31>: mov %eax,(%esp) 
    0x08048e46 <+34>: call 0x80488d0 <__isoc99_sscanf@plt> 
    0x08048e4b <+39>: cmp $0x2,%eax 
    0x08048e4e <+42>: jne 0x8048e5d <phase_4+57> 
    0x08048e50 <+44>: mov 0x18(%esp),%eax 
    0x08048e54 <+48>: test %eax,%eax 
    0x08048e56 <+50>: js  0x8048e5d <phase_4+57> 
    0x08048e58 <+52>: cmp $0xe,%eax 
    0x08048e5b <+55>: jle 0x8048e62 <phase_4+62> 
    0x08048e5d <+57>: call 0x8049470 <explode_bomb> 
    0x08048e62 <+62>: movl $0xe,0x8(%esp) 
    0x08048e6a <+70>: movl $0x0,0x4(%esp) 
    0x08048e72 <+78>: mov 0x18(%esp),%eax 
    0x08048e76 <+82>: mov %eax,(%esp) 
    0x08048e79 <+85>: call 0x8048dbb <func4> 
    0x08048e7e <+90>: cmp $0x25,%eax 
    0x08048e81 <+93>: jne 0x8048e8a <phase_4+102> 
    0x08048e83 <+95>: cmpl $0x25,0x1c(%esp) 
    0x08048e88 <+100>: je  0x8048e8f <phase_4+107> 
    0x08048e8a <+102>: call 0x8049470 <explode_bomb> 
    0x08048e8f <+107>: add $0x2c,%esp 
    0x08048e92 <+110>: ret  
    End of assembler dump. 

func4:

Breakpoint 2, 0x08048dbb in func4() 
(gdb) disas 
Dump of assembler code for function func4: 
=> 0x08048dbb <+0>: sub $0x1c,%esp 
    0x08048dbe <+3>: mov %ebx,0x14(%esp) 
    0x08048dc2 <+7>: mov %esi,0x18(%esp) 
    0x08048dc6 <+11>: mov 0x20(%esp),%eax 
    0x08048dca <+15>: mov 0x24(%esp),%edx 
    0x08048dce <+19>: mov 0x28(%esp),%esi 
    0x08048dd2 <+23>: mov %esi,%ecx 
    0x08048dd4 <+25>: sub %edx,%ecx 
    0x08048dd6 <+27>: mov %ecx,%ebx 
    0x08048dd8 <+29>: shr $0x1f,%ebx 
    0x08048ddb <+32>: add %ebx,%ecx 
    0x08048ddd <+34>: sar %ecx 
    0x08048ddf <+36>: lea (%ecx,%edx,1),%ebx 
    0x08048de2 <+39>: cmp %eax,%ebx 
    0x08048de4 <+41>: jle 0x8048dfd <func4+66> 
    0x08048de6 <+43>: lea -0x1(%ebx),%ecx 
    0x08048de9 <+46>: mov %ecx,0x8(%esp) 
    0x08048ded <+50>: mov %edx,0x4(%esp) 
    0x08048df1 <+54>: mov %eax,(%esp) 
    0x08048df4 <+57>: call 0x8048dbb <func4> 
    0x08048df9 <+62>: add %eax,%ebx 
    0x08048dfb <+64>: jmp 0x8048e16 <func4+91> 
    0x08048dfd <+66>: cmp %eax,%ebx 
    0x08048dff <+68>: jge 0x8048e16 <func4+91> 
    0x08048e01 <+70>: mov %esi,0x8(%esp) 
    0x08048e05 <+74>: lea 0x1(%ebx),%edx 
    0x08048e08 <+77>: mov %edx,0x4(%esp) 
    0x08048e0c <+81>: mov %eax,(%esp) 
    0x08048e0f <+84>: call 0x8048dbb <func4> 
    0x08048e14 <+89>: add %eax,%ebx 
    0x08048e16 <+91>: mov %ebx,%eax 
    0x08048e18 <+93>: mov 0x14(%esp),%ebx 
    0x08048e1c <+97>: mov 0x18(%esp),%esi 
    0x08048e20 <+101>: add $0x1c,%esp 
    0x08048e23 <+104>: ret  
End of assembler dump. 

Answer 1

Mam nadzieję, że to oczywiste, że phase4 jest sprawdzenie, że pierwsza liczba jest w zakresie 0 .. 14 włącznie (patrz linie +44 .. +57) Następnie wywołuje func4 z trzema argumentami: pierwszy wprowadzony numer, 0 i 14 (linie +62 .. +85). Następny sprawdza czy wartość zwracana jest 0x25 (37 dziesiętnie) na linii +90 i że drugi numer wpisany jest także 37 (linia +95)

Przejdźmy do func4. Nazwiemy trzy argumenty: x, low i high. Początkowo nie wiesz, co one są oczywiście. Linie +23 .. +34 obliczyć (high - low)/2. Brzydki bałagan polega na tym, że kompilator generuje kod do obsługi liczb ujemnych z obcięciem do zera. Nie zobaczymy jednak żadnych liczb ujemnych. Linia +36 jest po prostu fantazyjnym dodatkiem, więc w ebx mamy teraz low + (high - low)/2, który jest również znany jako średnia z dwóch liczb. Kod porównuje tę średnią do liczby x, która została przedstawiona jako pierwszy argument. Linie +43 .. +62 zostaną wykonane, jeśli x < average i wywołają func4(x, low, average - 1) i dodają zwróconą wartość do średniej. Podobnie linie +70 .. zostaną wykonane, jeśli x > average i obliczyć average + func4(x, average + 1, high). Jeśli x == average, zwracana jest tylko sama średnia.

Po prostu robi wyszukiwanie binarne i podsumowuje zgadywanki. Biorąc pod uwagę, że przedział ma 15 elementów, będzie potrzebował co najwyżej 4 zgadywania. Pierwsze przypuszczenie to 7, więc aby uzyskać wymagany wynik z 37 potrzebujemy więcej. Mamy co najwyżej 3 kolejne próby, a wszystkie domysły będą mniej niż 7 lub więcej niż 7. Od 7 * 3 = 21 i to nie może dać nam 30 oznacza to, że liczba musi być większa niż 7. Zgadujemy, że w ten sposób (8 + 14)/2 = 11, dzięki czemu nasza suma 18 z 19 będzie jeszcze większa. Jeśli liczba była powyżej 11, oznaczałoby to, że przekroczyliśmy cel, więc liczba musi być większa niż 7 i mniejsza niż 11. Trzecie zgadywanie jest zatem (8 + 10)/2 = 9, co powoduje, że suma do 27 z 10 jest większa i wystarczy jedno domysły, więc oznacza to, że numer to 10.

TL; DR: prawidłowe wejście powinno być 10 i 37