Reutilizando strlens para otros fines…
Hace unos dias me hicieron una pregunta. Estaban buscando una forma rapida de saber si en un DWORD representado en hexadecimal aparecia el mismo digito en posiciones consecutivas.
Por ejemplo, el numero 0x12345678 no cumple esta propiedad, a diferencia del 0x12344678.
En principio la solucion es bastante sencilla, pero en vista de que la gente parece no compartir mi opinion, me he decidido a escribir este post.
Como comente en su momento, creo que la mayor parte de las personas que se dedican a la ingenieria inversa han depurado en alguna ocasion un algoritmo que practicamente resuelve este problema.
El primer paso es convertir la condicion inicial en una condicion que se pueda evaluar con mas facilidad. Lo mas sencillo es desplazar el numero inicial 4 bits a la izquierda, y seguidamente hacer un xor entre el numero original y el numero obtenido. Con esta conversion lo que pretendemos es simplificar la condicion, puesto que tras esta operacion el problema se reduce a saber si en el DWORD hay un 0. Siguiendo con el ejemplo anterior, tendriamos:
0x12344678 << 4 -> 0x23446780;
0x12344678 ^ 0x23446780 -> 0x317021F8
Donde como podemos ver, aparece un 0. En el algoritmo final tambien deberemos hacer un OR con 0x00000001 para evitar que el digito menos representativo pueda eventualmente ser 0.
Bien, una vez llegados a este punto en realidad todo el trabajo esta hecho. Solo neceistamos tener buena memoria. Me imagino que casi todos los que esteis leyendo esto y que os interese la ingenieria inversa habra depurado alguna vez algun strlen. Aunque actualmente solemos ver implementacion de strlen mas triviales (O no, revisando los sources de la libc que tengo instalada veo que implementa este algoritmo con una ligerisima variacion) hubo un tiempo en que para la implementacion de dicha funcion se usaba un pequeño truco. La idea basicamente era saber con una sola comprobacion si en un DWORD habia un byte 0. En caso de que hubiese un 0 se pasaba a buscar linealmente el 0 dentro del DWORD. Si no habia ningun 0 se podia pasar directamente al siguiente DWORD.
Este algoritmo se basaba en dos conceptos muy sencillos. Imaginemos que interpretamos el DWORD como un numero entero con signo expresado en complemento a dos. Entonces se cumple que:
– El 0 es el unico numero que tanto al restarle 1 como al aplicarle la operacion binaria NOT, el resultado es negativo
– La unica forma de provocar un overflow al restar 1 es que el numero inicial sea 0
Basandose en estas dos propiedades, strlen interpretaba un DWORD como un conjunto de bytes contiguos. Primero restaba 1 a los bytes de nuestro DWORD haciendo «DWORD – 0x01010101». Los bytes que contuviesen un valor menor o igual que 0 ahora contenian un valor negativo. Por otro lado hacia un «NOT DWORD», de forma que los bytes que contenian valores mayores o iguales que 0 ahora tendrian valores negativos. Seguidamente hacia un AND binario de ambos resultados parciales, de forma que solo los valores que eran negativos en ambos valores continuarian siendo negativos. O lo que es lo mismo, solo los bytes que inicialmente eran 0 ahora contendrian valores negativos. Por ultimo se hacia un AND del resultado con 0x80808080. Con esta operacion, si no habia bytes negativos, el resultado seria 0. Si habia bytes negativos (inicialmente 0’s) el resultado seria diferente de 0. Resumiendo:
#define C1 0x01010101
#define C2 0x80808080
#define HasNullByte(Value) ((((Value) – C1) & ~(Value) & C2) != 0)
Como comente antes, la resta de los 1’s provocan un overflos solo si el byte inicial era 0, pero en ningun caso afectara al resultado final.
Bueno, ahora que hemos recordado como funcionaban aquellos strlen’s, es evidente que esa misma idea se puede aplicar a nuestro problema. En vez de buscar bytes 0 estamos buscando Nibbles 0 por lo que ajustando las constantes, tendremos el problema resuelto.
Uniendo todo lo dicho anteriormente tenemos:
int Function(int Number)
{
Number ^= (Number << 4);
Number |= 1;
return ((Number – 0x11111111) & ~Number & 0x88888888);
}
Y esto es to to todo amigos
;o)