[Gnu AS] BruteForce

[GGZ]

Voy al grano,

Hecho en C:

Código (c) [Seleccionar] Expandir

#include <stdio.h>

int fuerzabruta(char *S, char *s, int lS, int ls)
{
        int i, j;

        for(i=0; i<lS-ls+1; i++)
                if(S[i]==s[0]) {
                      for (j=0; j<ls; j++){
                              if (S[i+j] != s[j]) break;
                      }
   
                        if(j==ls) return i;
        }
        return -1;
}   

Lo pasé a ASM y anduvo pero lo quise hacer denuevo y no funcionó:

1era versión:

Código (asm) [Seleccionar] Expandir

#int fuerzabruta(char *S, char *s, int lS, int ls){
# int i, j;
# for(i=0; i<lS-ls+1; i++)
# if(S[i]==s[0]) {
# for(j=0; j<ls && S[i+j]==s[j]; j++);
# if(j==ls) return i;
# }
# return -1;
#}

# Retorna la posición del primer elemento de la cadena a buscar.
# "sHolasos" "sos" retorna 5.



# lS = %rdx
# ls = %rcx

.data
i: .quad 0

.text
.global bf
bf:
# iremos incrementando (df = 0)
cld

# Guardo variable ls en otro registro.
# rdx = ls
movq %rcx,%r8


# cuantas veces repetimos al primer for?

subq %rcx,%rdx # rdx = rdx - rcx
# es decir: lS = lS - ls

addq $1,%rdx # sumo 1



# Lo cargamos al rcx para el bucle.
movq %rdx, %rcx
aca:
lodsb # copiamos el primer caracter de la 2da cadena en el rax
# decq %rsi

sigue1:
#lodsb
# primero busco el primer caracter de la cadena 2 en la cadena 1.
# mas tecnico: comparamos rax con rdi
scasb
# si encontramos el primer caracter en algun lugar de la cadena, saltamos al 2do for.

je found
loop sigue1
# termina.
# -1 si no lo encontramos el primer caracter de la 2da cadena en la primera.
movq $-1, %rax
ret


found:
# encontramos el primer caracter de la 2da cadena en la primera.
# estamos dentro del primer if.
# usaremos el registro r8, hasta el momento r8 = ls.

# Quiero saber el valor de i
# i = %rdx - %rcx
# i = lS-ls+1 - veces repetido (hacia atras,es decir del tope al 0).

# Guardamos informacion del bucle anterior.
movq %rcx,%r13
movq %rdx,%r15
movq %rsi,%r9
subq $1,%r9

subq %rcx,%rdx # rdx = rdx - rcx ( i = rdx )


# Cargamos r8=ls a rcx para el 2do for. Hay que restar uno.
movq %r8,%rcx
decq %rcx
movq %rdi,%r14
sigue2:
# comprobamos si los siguientes caracteres estan en la cadena 1.
# tengo que cambiar adonde apunta rdi, es decir la primer cadena. ( S[i+j] )
# i = rdx
cmpsb
jne fail
loop sigue2
movq %rdx,%rax
addq $1,%rax
ret


# fallo en el 2do for.
fail:
# el último if ( if j == ls return i )
# si es igual a 0 significa que recorrió todo el bucle.
cmpq $0, %rcx
je final
# si no son iguales vuelvo al 1do for.

# antes cargo el rcx y rdi de nuevo, con informacion del i del primer bucle.
# restauro registros
movq %r13,%rcx
movq %r14,%rdi

movq %r9, %rsi
movq %r15,%rdx
jmp aca

final:
subq %rcx,%rdx # es el i
movq %rdx,%rax
ret


Lo implemento usando se, o sea declaro el prototipo en c y llamo a esa funcion, haciendo gcc bf.c bf.s -o bf
Esa primer versión con todo lo que probé funcionó pero esta segunda versión no, capaz me comí algo pero ya me cansé de buscarlo.
Intenté con gdb pero me cansé a ver si alguien me puede dar una manito.
Para usar gdb lo compilaba con -g

Segunda versión:

Código (asm) [Seleccionar] Expandir

.text
.global bf
bf:
cld
movq %rcx,%r8

subq %rdx,%rcx # rdx = rdx - rcx
# lS = lS - ls
addq $1, %rdx

movq %rdx,%r9

movq %rdx,%rcx
aca:
lodsb # cargamos el primer caracter de la 2da cadena en el rax.
subq $1,%rsi

_1for:
scasb
je si_eq_s0
loop _1for
movq $-1, %rax
ret

si_eq_s0:
# Para volver al anterior bucle.
movq %rsi, %r14
addq $1,%rsi
movq %rdi, %r12
movq %rcx, %r13 # valor de i.

subq %r13,%r9 # valor de i


movq %r8,%rcx
subq $1,%rcx

_2for:
cmpsb # rsi == rdi?
jne fail
loop _2for
movq %r13,%rax
ret

fail:
cmpq $0,%rcx
je final

movq %r14,%rsi
movq %r12,%rdi
movq %r13,%rcx
jmp aca

final:
movq %r9,%rax
ret


Esta es la imp.

Código (c) [Seleccionar] Expandir

#include <stdio.h>
int bf ( char *s1, char *s2, int long_s1, int long_s2);
int main (void){
printf ("Resultado: %d\n",bf("soAdSDsos","sos",9,3));
        return 0;
}



Saludos!

[Eternal Idol]

No lo vi todo ya que me resulta bastante agotadora esta sintaxis pero esto es diferente y estimo que sin quererlo:

1)
   subq %rcx,%rdx   # rdx = rdx - rcx
         # es decir: lS = lS - ls
2)
   subq %rdx,%rcx   # rdx = rdx - rcx
         # lS = lS - ls

[GGZ]

Probé con eso y no anduvo.
¿Podés hacerlo vos y mostrarme como te quedó?, sin necesariamente ver el mío.

¡Saludos!

[Eternal Idol]

No; vos ya tenes un codigo funcional pero al cambiarlo lo jodiste y queres que yo lo escriba de nuevo ... encima tendria que hacerlo con gcc y esa sintaxis ... depuralo instruccion por instruccion o arranca de nuevo con el codigo que funciona y mira linea por linea lo que haces.

[GGZ]

O sea, los dos funcionan perfectamente.
El problema es que devuelvo mal la posición, es decir tengo que retornar el i del primer bucle y lo estoy calculando mal.

Igual lo admito que es cansador esta sintaxis, más tarde lo voy a ver otra vez.

Cualquiera que quiera darme una mano, bienvenido sea.

Saludos!

[cpu2]

Porque no usas ktrace en linux creo que s strace y kdump, para comprobar el offset donde falla?

Saludos.

[GGZ]

Ayudame a calcular la posición del i del primer for.
Funciona perfecto todo, pero me tira mal la posición del i, del primer for.

Mirá este código lo debuggié con gdb, de todos modos no pude sacar.
Capaz que sea una cuenta mal hecha, este código está ya funcionando.

Código (asm) [Seleccionar] Expandir

.text
.global bf
bf:
cld
movq %rcx,%r8

subq %rcx,%rdx
incq %rdx

movq %rdx,%rcx

aca:
lodsb
_1for:
scasb
je Si_eq_s0
loop _1for

movq $-1,%rax
ret

Si_eq_s0:
movq %rcx,%r13
movq %rsi,%r11
decq %r11 # siempre apunta al primero
movq %rdi,%r12

# comprobamos denuevo letra anterior porque sino queda vacio y da true.
# incq %rcx # VER
decq %rsi
decq %rdi

subq %rcx,%rdx # este es la posición.

# esta bucle se repite ls-1 veces.
movq %r8,%rcx # r8=ls
decq %rcx

_2for:
repe cmpsb
jne fail

jmp final

fail:
cmpq $0,%rcx
je final

movq %r13,%rcx
movq %r11,%rsi
movq %r12,%rdi
jmp aca

final:
subq %rcx,%rdx
movq %rdx,%rax
ret