Bomba Binaria – Fase 4

Estoy teniendo un momento muy difícil para rastrear el código de ensamblaje para la siguiente bomba binaria (una asignación de la escuela donde se debe desactivar una bomba, esta bomba contiene 6 fases, todas tienen 1 entrada correcta para pasar a la siguiente fase). Actualmente estoy en fase_4 y tiene una función recursiva llamada func4. He identificado que la entrada es “% d% d”, que es dos enteros. Sin embargo, no puedo entender qué func4 está haciendo, incluso después de obtener la información en todos los registros a lo largo de cada paso.

Fase_4:

(gdb) disas Dump of assembler code for function phase_4: => 0x08048e24 : sub $0x2c,%esp 0x08048e27 : lea 0x1c(%esp),%eax 0x08048e2b : mov %eax,0xc(%esp) 0x08048e2f : lea 0x18(%esp),%eax 0x08048e33 : mov %eax,0x8(%esp) 0x08048e37 : movl $0x804a7f1,0x4(%esp) 0x08048e3f : mov 0x30(%esp),%eax 0x08048e43 : mov %eax,(%esp) 0x08048e46 : call 0x80488d0  0x08048e4b : cmp $0x2,%eax 0x08048e4e : jne 0x8048e5d  0x08048e50 : mov 0x18(%esp),%eax 0x08048e54 : test %eax,%eax 0x08048e56 : js 0x8048e5d  0x08048e58 : cmp $0xe,%eax 0x08048e5b : jle 0x8048e62  0x08048e5d : call 0x8049470  0x08048e62 : movl $0xe,0x8(%esp) 0x08048e6a : movl $0x0,0x4(%esp) 0x08048e72 : mov 0x18(%esp),%eax 0x08048e76 : mov %eax,(%esp) 0x08048e79 : call 0x8048dbb  0x08048e7e : cmp $0x25,%eax 0x08048e81 : jne 0x8048e8a  0x08048e83 : cmpl $0x25,0x1c(%esp) 0x08048e88 : je 0x8048e8f  0x08048e8a : call 0x8049470  0x08048e8f : add $0x2c,%esp 0x08048e92 : ret End of assembler dump. 

func4:

 Breakpoint 2, 0x08048dbb in func4 () (gdb) disas Dump of assembler code for function func4: => 0x08048dbb : sub $0x1c,%esp 0x08048dbe : mov %ebx,0x14(%esp) 0x08048dc2 : mov %esi,0x18(%esp) 0x08048dc6 : mov 0x20(%esp),%eax 0x08048dca : mov 0x24(%esp),%edx 0x08048dce : mov 0x28(%esp),%esi 0x08048dd2 : mov %esi,%ecx 0x08048dd4 : sub %edx,%ecx 0x08048dd6 : mov %ecx,%ebx 0x08048dd8 : shr $0x1f,%ebx 0x08048ddb : add %ebx,%ecx 0x08048ddd : sar %ecx 0x08048ddf : lea (%ecx,%edx,1),%ebx 0x08048de2 : cmp %eax,%ebx 0x08048de4 : jle 0x8048dfd  0x08048de6 : lea -0x1(%ebx),%ecx 0x08048de9 : mov %ecx,0x8(%esp) 0x08048ded : mov %edx,0x4(%esp) 0x08048df1 : mov %eax,(%esp) 0x08048df4 : call 0x8048dbb  0x08048df9 : add %eax,%ebx 0x08048dfb : jmp 0x8048e16  0x08048dfd : cmp %eax,%ebx 0x08048dff : jge 0x8048e16  0x08048e01 : mov %esi,0x8(%esp) 0x08048e05 : lea 0x1(%ebx),%edx 0x08048e08 : mov %edx,0x4(%esp) 0x08048e0c : mov %eax,(%esp) 0x08048e0f : call 0x8048dbb  0x08048e14 : add %eax,%ebx 0x08048e16 : mov %ebx,%eax 0x08048e18 : mov 0x14(%esp),%ebx 0x08048e1c : mov 0x18(%esp),%esi 0x08048e20 : add $0x1c,%esp 0x08048e23 : ret End of assembler dump. 

Espero que sea obvio que phase4 está comprobando que el primer número está en el rango 0 .. 14 inclusive (ver líneas +44 .. +57 ) Luego invoca func4 con tres argumentos: el primer número ingresado, 0 y 14 (líneas +62 .. +85 ). A continuación, verifica que el valor de retorno sea 0x25 (37 decimal) en la línea +90 y que el segundo número ingresado sea también 37 (línea +95 )

Pasemos a func4 . Llamaré a los tres argumentos x , low y high . Inicialmente no sabes lo que son, por supuesto. Líneas +23 .. +34 calcular (high - low) / 2 . El feo lío se debe a que el comstackdor genera código para manejar números negativos con truncamiento a cero. Sin embargo, no veremos ningún número negativo. La línea +36 es simplemente una adición elegante, así que en ebx ahora tenemos low + (high - low) / 2 que también se conoce como el promedio de los dos números. El código luego compara este promedio con el número x que se ha proporcionado como primer argumento. Las líneas +43 .. +62 se ejecutan si x < average e invocan func4(x, low, average - 1) y agregan el valor devuelto al promedio. Del mismo modo, las líneas +70 .. +89 se ejecutan si x > average y calcula el average + func4(x, average + 1, high) . Si x == average , solo se devuelve el promedio.

Básicamente está haciendo una búsqueda binaria y sumndo las suposiciones a medida que avanzan. Dado que el intervalo tiene 15 elementos, necesitará como máximo 4 suposiciones. La primera conjetura va a ser 7 , por lo que para obtener el resultado requerido de 37 necesitamos 30 más. Tenemos como máximo 3 bashs más y todas las suposiciones serán menos de 7 o más de 7. Dado que 7 * 3 = 21 y que no pueden darnos 30 significa que el número debe ser mayor que 7. Segundo bash es así va a ser (8 + 14) / 2 = 11 , por lo que nuestra sum 18 con 19 más por recorrer. Si el número era superior a 11 significaría que rebasamos el objective, por lo que el número debe ser mayor que 7 y menor que 11. El tercer bash es por lo tanto (8 + 10) / 2 = 9 que eleva la sum a 27 con 10 más para ve y solo una adivinanza, entonces eso significa que el número es 10 .

TL; DR: la entrada correcta debe ser 10 y 37