Crear bucle de fuerza bruta con rango de caracteres

[[escafandra]]

La velocidad se consigue por el hecho de trabajar con cadenas estilo C y es independiente de si vas de izquierda a derecha o al revés. Si eliminas comprobaciones y condicionales superfluos también aceleras el proceso. El hecho de no comprobar que se terminaron las combinaciones de caracteres no es casual, ya que si la cadena cumple la condición de contener solo los caracteres existentes en Rango, el resultado lo encuentra sí o sí, por lo tanto no puene entrar en un bucle infinito y ganamos rendimiento.

Una cosa que hace perder rendimiento es usar el resto de la división en el bucle principal, que es el más largo. Si lo eliminamos, le procesador hará menos cálculos, perdemos un poco de elegancia en el código pero ganamos algo de tiempo. Como ejemplo pongo lo siguiente:

Código PHP:

bool FuerzaBruta(char* Serial, char* Salida, char* Rango)
{
  int L = strlen(Serial);
  int R = strlen(Rango);
  int n, i;

  for(n=0; n<L; n++) Salida[n] = *Rango; Salida[n] = 0;
  
  int r=0, f = 0;
  do{
    *Salida = Rango[r];
    //acarreo
    for(int c=0; Salida[c]==*Rango && f>0; c++){
      for(i=0; Rango[i] && Rango[i]!=Salida[c+1]; i++);
      Salida[c+1] = Rango[(i+1)%R];
    }
    f=1;
    r++; if(r==R) r=0;
  }while(strcmp(Salida, Serial));
  return true;
} 


Cambio el tipo de bucle a do while, lo que me obliga a incrementar el índice r y añado otra variable (f) para detectar que no es la primera vez que pasamos por el primer carácter de Rango. No compruebo que se terminaron las combinaciones porque encontraré el Serial obligatoriamente.

Un paso más puede ser escribirlo en asm, no lo he hecho pero es muy probable que incremente algo la velocidad

[[escafandra]]

Empezado por aguml

Otro posible (aunque no se hasta que punto probable) fallo. El contador que se usa en el for principal puede llegar a desbordarse (en mi maquina quizas en un par de eones jejeje) ya que incrementa continuamente y dependiendo de lo grande del serial a buscar podria ocurrir.
Lo he solucionado poniendo la siguiente linea al final del for que se encarga del acarreo:

Código PHP:

//Cada vez que llegamos aqui, contador llega siendo multiplo del largo del rango por lo que, para evitar un posible desbordamiento
//de la variable contador, cada vez que entre aquí le asignaremos el valor del largo del rango para curarnos en salud
contador = largoRango; 


Sinceramente no se en que interviene esto pero desde que lo hice los tiempos han mejorado algo mas.

Incrementa la velocidad porque el módulo calculado es de números más pequeños. si obviamos el módulo en el bucle principal, como comenté arriba, descargamos de trabajo al procesador y aumenta el rendimiento en procesadores lentos. En mi i7 no se nota prácticamente, pero lo probé en un PC inferior y ganó 7 segundos (de 20 pasó a 13).


Saludos.

[aguml]

Pues si, yo la comprobacion de tope la dejaré por si alguna vez se mete un serial incorrecto pero con lo que me indicas te digo que ha pasado de 188 milisegundos a 156 en el mismo ejemplo que estaba viendo. O sea que en un serial mayor se notaria aun mas.

[[escafandra]]

¿Probaste la última versión que te puse?


Saludos.

[aguml]

si si, esa misma pero con la comprobacion de cadena final y en vez de usar como comprobacion de salida la funcion strcmp uso un bool que se pone a true cuando la encuentra o cuando llegue al final y en vez de usar un entero para indicar si es la primera pasada yo uso un bool. Tambien supongo que para medir el largo del serial, del rango,y como contador se podrian usar char para ahorrar recursos ¿No?

[[escafandra]]

Empezado por aguml

si si, esa misma pero con la comprobacion de cadena final y en vez de usar como comprobacion de salida la funcion strcmp uso un bool que se pone a true cuando la encuentra o cuando llegue al final y en vez de usar un entero para indicar si es la primera pasada yo uso un bool. Tambien supongo que para medir el largo del serial, del rango,y como contador se podrian usar char para ahorrar recursos ¿No?

Un bool internamente es un int. De todas formas pocos recursos ahorrarías. Para un procesador de 64 bits trabajando con un programa compilado para 64bits, es más cómodo usar int64 que int32 aunque nos pueda parecer lo contrario.
La comprobación de final de combinaciones puede ser más eficaz si mantenemos el contador principal del bucle como cuenta continua, como en la primera versión que expuse y calculamos previamente el número total de combinaciones. Solo comparamos dos números y no dos cadenas, que es mas tedioso, pues se comparan carácter a carácter en cada iteración del bucle.

Saludos.

[aguml]

¿como se podria calcular el numero de combinaciones? Se me ocurre largoSerial elevado a largoRango ¿Puede ser eso?

[aguml]

vale, creo que es elevando el largo del rango al largo del serial, o sea, en este caso pow(16, 8)-1.
A esto le veo un problema, para 256 caracteres y un serial de 8 caracteres nos vamos a 18446744073709551615 que es justo el limite de un int64 sin signo. ¿como he calculado el valor maximo? elevando 2 a la potencia de (sizeof(UINT64)*8) y restandole 1, o sea (2^64)-1. Curiosamente un unsigned long long posee el mismo rango. Como pow no me permite usar valores tan grandes lo que hago es poner la variable a 0 y luego decremento en 1 y ya poseo el valor maximo cuando es unsigned. El único tipo que conozco mayor que esos es long double que es de 10 bytes, o sea 80 bits, pero no se que rango tiene ya que he encontrado buscando que su rango es 3.37e-4932 a 1.18e4932 y que los doubles no pueden ser sin signo asi que el maximo seria 1.18e4932 pero no entiendo ese tipo de notacion y no se a que valor equivale realmente.
O sea que para seriales de 8 o mas caracteres tendriamos un grave problema.

[[escafandra]]

Claro que es un problema para serial largo, y comparar con una cadena fin de combinaciones, todo ese montón de veces, también lo es. Ese es el motivo por el que no lo compruebo dado que el algoritmo va a encontrar la solución.

Mide tiempos comprobando y sin comprobar y elige la opción que te resulte rentable.


Saludos.