Random IRC quote :      <@patowc> Sí, es verdad, me estoy ablandando <@patowc> lo siguiente son los hijos

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)

14 Comentarios para “Reutilizando strlens para otros fines…”

  1. Comment por La Nuri | 01/24/10 at 8:05 am

    strlen… el tamaño importa…

  2. Comment por Ruben | 01/24/10 at 10:09 am

    Elegante solución, como siempre 🙂

  3. Comment por La Nuri | 01/24/10 at 11:25 am

    ku ku Rubeeen…

  4. Comment por David Reguera | 01/24/10 at 2:16 pm

    maestro 🙂

  5. Comment por ano nimo | 01/24/10 at 6:25 pm

    Y ya que estamos… ¿Con quién hay que acostarse para entrar al IRC? En irc.freenode.com no hay nada.

    @.@

  6. Comment por La Nuri | 01/25/10 at 5:03 am

    ¿Te doy una pista?

  7. Comment por Miguel | 01/25/10 at 8:15 am

    /*++

    Cuando seas un reverser
    y hayas rendido vasallaje y pleitesia al developer pescador,
    Cuando seas el puro y perfecto reverser,
    entonces podras encontrar el irc de 48bits…

    Y podras contestar a la pregunta
    ¿A quien sirve el santo canal?

    –*/

  8. Comment por Shaddy | 01/26/10 at 12:59 pm

    Solución como siempre perfecta, pero DIOSSSSSSSSSSSSS, que rabia das xD. Creo que voy a empezar con el lema algo así.. «hay una solución, para todo, en tiempo constante»

  9. Comment por PE_Luchin | 01/26/10 at 1:04 pm

    Al menos me podías sacar en los créditos, ¿Quién fue la musa que te inspiró el post?

  10. Comment por matalaz | 01/26/10 at 2:56 pm

    @PE_Luchin. Solo de imaginarte posando desnudo me entran ganas de vomitar.

  11. Comment por Miguel | 01/26/10 at 4:48 pm

    /*++
    desnudez, erotismo, vomitos…
    Hoygan! Que la gente va a pensar que nuestra oficina es como sodoma y gomorra!
    –*/

  12. Comment por dead | 01/27/10 at 6:19 pm

    No comprendi nada, pero prometo que voy a entender!

  13. Comment por Amian | 02/03/10 at 10:46 am

    Que rechevere la entradita, el strlen technique está wason para hacer las cosas rapiditas.

  14. Comment por erg0t | 02/05/10 at 11:32 am

    Al famoso algoritmo de Alan Mycroft 🙂
    Hace mucho tiempo atras yo tambien jugaba con esos temas de vectorizacion, dejo un viejo codigo de unas pruebas que hice en esas epocas con SSE2 para implementar un strlen escaneando 16 bytes por iteracion, se podria optimizar mas aun, por ejemplo usando alineacion de memoria…

    __asm__ __volatile__ (
    «movl %1, %%ecx\n»
    «pxor %%xmm1,%%xmm1\n»
    «1:\n»
    «movdqu (%%ecx),%%xmm0\n»
    «addl $16,%%ecx\n»
    «pcmpeqb %%xmm1,%%xmm0\n»
    «pmovmskb %%xmm0,%0\n»
    «testl %0, %0\n»
    «jz 1b\n»
    «bsfl %0, %0\n»
    «leal -16(%%ecx,%0), %0\n»
    «subl %1,%0\n»
    : «=r» (ret)
    : «m» (ptr)
    :»%ecx»
    );

Se han cerrado los comentarios