Averiguar Si Tamaño De Textura Es Potencia De 2

[fiero]

 Me ha surgido el problemilla de saber si el tamaño de una textura es potencia de 2. La única manera que se me ocurre es contar el número de '1' en binario que tiene  la variable que almacena el tamaño. Si solo hay un '1' es que es un tamaño potencia de 2. Y además la forma más facil de acerlo me parece que es en ensamblador, así:

Código [Seleccionar] Expand


_asm{
        mov eax,tamy         //Tamaño Y
        mov edx,tamx         //Tamaño X
        shl eax,16
        mov ax,dx               //Parte alta de eax=Y
                                       //Parte baja de eax=X
        mov ecx,32
        xor edx,edx            //Contador de '1' = 0
sumaunos:
        ror eax,1                //Bit menos significativo al acarreo
        adc edx,0               //Suma 1 al contador si el accarreo es '1'
        dec ecx
        jnz sumaunos
        cmp edx,2              //Compara el número de '1'
        jle potencia2
                                      //Tamaño X o Y no es potencia de 2
potencia2:
                                     //Tamaño X e Y son potencia de 2
}


Este es el típico problema que siempre tiendo a resolver en ensamblador, porque en C me parece mucho más engorroso, habria que ir haciendo máscaras y el bucle seria mucho más lento.

¿Hay alguna otra forma de averiguar si los tamaños son potencia de 2? es que ahora no la veo  <_<

un saludo

PD: Aprovecho el post para animar a la gente a aprender ASM, que no es tan dificil como parece...

[Ithaqua]

 Si n es el tamaño, hallar el logaritmo en base 2 de n y comprobar si es entero.

n = 2 elevado a x.  x tiene que ser entero para que n sea potencia de 2.

Mucho más costoso computacionalmente que calcularlo de tu forma , pero lo pedías más sencillo :)


P.D El método del logaritmo lo uso yo para forzar el tamaño de una textura a potencia de 2, simplemente hay que redondear a entero el resultado hallado.

[Juan Mellado]

fiero, en C tampoco queda tan engorroso:

Código [Seleccionar] Expand


bool IsPowerOfTwo(DWORD n)
{
   int b = 0;

   for (; n != 0; n = n >> 1){

        b += n & 1;
       }

   return(b == 1);
}


Saludos

[Grugnorr]

 Mejor con un while que con un for raro ;)

PD: Aprendí Pascal primero, sí :)

[fiero]

 Cierto, me olvidé de los logaritmos. He estado mirandome las funciones de logaritmos del coprocesador y creo que seria una cosa así:

Código [Seleccionar] Expand


int entero,espotencia2=1;
float zero=0.0;
_asm{
 fld1
 fild tamTextura
 fyl2x
 fist entero
 fisub entero
 fcomp zero
 fstsw ax
 and ax,0x4000
 jnz siPotencia2
 mov espotencia2,0
                       siPotencia2:
}


Para saber si la parte decimal de un número es 0, yo siempre convierto el número a entero, con 'fist' y luego se lo resto al número original. No sé si hay alguna instrucción que lo haga directamente. La verdad, como dices Ithaqua, es que la funcion 'fyl2x' ocupa un guevo de ciclos, quizás sea más rápido contar los '1'

Bonito bucle Juan. He tomado tu idea para mejorar en velocidad mi cuenta '1'. Al final lo he dejado así:

Código [Seleccionar] Expand


_asm{
       mov eax,tamy          //Tamaño Y
       mov edx,tamx          //Tamaño X
       shl eax,16
       mov ax,dx                //Parte alta de eax=Y
                                       //Parte baja de eax=X
       clc
       xor ecx,ecx
       xor edx,edx             //Contador de '1' = 0
sumaunos:
       adc edx,ecx             //Suma 1 al contador si el accarreo es '1'
       shr eax,1                 //Bit menos significativo al acarreo
       jnz sumaunos
       adc edx,ecx             //Suma 1 al contador si el accarreo es '1'
       cmp edx,2               //Compara el número de '1'
       jle potencia2
                                      //Tamaño X o Y no es potencia de 2
potencia2:
                                     //Tamaño X e Y son potencia de 2
}


saludos

[sés]

 

fiero, en C tampoco queda tan engorroso:

Código [Seleccionar] Expand


bool IsPowerOfTwo(DWORD n)
{
   int b = 0;

   for (; n != 0; n = n >> 1){

        b += n & 1;
       }

   return(b == 1);
}


Saludos

Eso falla si el bit de mayor peso es 1 ^_^

...o si el de menor peso es 1, recordar que el bit 0 vale 1, 1 no es potencia de 2 ^_^

Mejor así:

Código [Seleccionar] Expand


int IsPowerOfTwo( DWORD n )
{
   int c = 0;

   if( !n ) return -1;
   if( n & 1 ) return 0;

   n >>>= 1;

   while( n && !(c & 2) ) {
       if( n & 1 ) c++;
       n >>>= 1;
   }

   return c & 1;
}



De todas formas quedaría mejor en ensamblador.

[fiero]

 Una razón que a veces me hace elejir el ensamblador es que en C no hay desplazamientos lógicos. O sea, en C los desplazamientos son aritméticos, siempre te deja el valor del signo a la izquierda (bit mas significativo). No hay nada que desplace a la derecha, rellenando con '0' los bits más significativos.

un saludo

[Juan Mellado]

 sés,

1) sí funciona si el bit de mayor peso es 1. Prueba IsPowerOfTwo(0x80000000), ya verás como devuelve true.

2) 1 si es potencia de 2. Concretamente, 2 ^ 0 (2 elevado a 0).


Antes de postear el código lo probé. El test (lo borré) era algo así:

Código [Seleccionar] Expand


for (i = 0; ...; i ++){
  if ( IsPowerOfTwo(i) ){
      char s[1024];
      sprintf(s, "%ld\n", i);
      OutputDebugString(s)
     }
}



Saludos

[Juan Mellado]

 

(fiero)
... en C los desplazamientos son aritméticos, siempre te deja el valor del signo a la izquierda (bit mas significativo). No hay nada que desplace a la derecha, rellenando con '0' los bits más significativos. ...

fiero,
depende del tipo de la variable sobre la que efectues el desplazamiento. No es lo mismo desplazar un unsigned int que un int a secas.

Código [Seleccionar] Expand


   unsigned int u = 0x80000000;
   u = u >> 1;

//Aquí u = 0x40000000

   int s = 0x80000000;
   s = s >> 1;

//Aquí s = 0xc0000000



Lo que hace el compilador es utilizar una instrucción u otra (shr o rcr, o como sea, ya no me acuerdo), en función del tipo de la variable.

[_Grey]

 Creo que es esto:

Para una variable de 16 bits:

Código [Seleccionar] Expand


// Comprueba si es potencia de 2
// De un numero sin signo de 16bits !!
unsigned short int num=4;
__asm{
          mov ax,num; Coge numero a comprobar
          mov bx,2 ; Potencia de 2 a comprobar, empieza por 2

comprobacion: ; En esta parte se comprueba si es potencia de 2

          cmp bx,ax ; Compara ax con la potencia de 2 actual(bx)
          je potenciaDeDos; Es potencia de 2
          shl bx,1 ; Siguiente potencia de 2 a comprobar
          jnz comprobacion; Si bx es cero ya a comprobado todas las potencias de 2 si no continua comprobando

noPotenciaDeDos: ; No es potencia de dos

potenciaDeDos: ; Potencia de dos

}


Para una variable de 32 bits:

Código [Seleccionar] Expand


// Comprueba si es potencia de 2
// De un numero de 32bits !!
unsigned int num=4;
__asm{
          mov eax,num; Coge numero a comprobar
          mov ebx,2; Potencia de 2 a comprobar, empieza por 2

comprobacion: ; En esta parte se comprueba si es potencia de 2

          cmp ebx,eax; Compara ax con la potencia de 2 actual(bx)
          je potenciaDeDos; Es potencia de 2
          shl ebx,1 ; Siguiente potencia de 2 a comprobar
          jnz comprobacion; Si bx es cero ya a comprobado todas las potencias de 2 si no continua comprobando

noPotenciaDeDos: ; No es potencia de dos

potenciaDeDos: ; Potencia de dos

}


La etiqueta "noPotenciaDeDos:" no se llama desde ningun sitio, esta solo para hacer mas visible el codigo.

Hace muuuuchooooo que no toco el ensamblador, es mas, el ensamblador de las CPU's de Intel apenas la e tocado alguna vez, lo mio fue el Z80, de todas formas yo tambien animo a la gente a que aprenda ensamblador, es mas les recomiendo que se compren el libro "ENSAMBLADOR PARA DOS,LINUX Y WINDOWS", de Anaya Multimedia, tengo otro pero me parece muy tecnico que seguro que es bueno para profundizar "Los Microprocesadores de Intel", de Prentice Hall, apenas lo e mirado por encima.

Si alguien no tiene ni idea de asm, o no lo toca desde que era crio, con el de Anaya podras cojer los conocimientos necesarios para entenderlo.

Para finalizar, yo tampoco creo muy buena idea programar en ensamblador, es una perdida de tiempo, pero todo programador deberia conocerlo y saber "como funciona" y "por que funciona", aun cuando no lo toque nunca.

PD: fiero: Gracias por recordarme los viejos tiempos del z80.... aun si lo que e puesto esta mal  :rolleyes: espero que no.... ;)  

[_Grey]

 Igual la cago, pero si despues del :

mov ax,num

añadimos un:

jp noPotenciaDeDos; Numero de bits en num par, IMPOSIBLE que sea potencia de 2

ganariamos velocidad.

Cuidado con añadir:

jz noPotenciaDeDos

En esta ultima ocasion, solo ganariamos velocidad si num fuera 0 MUY a menudo, con lo que si realmente existe la posibilidad de que el numero sea cualquiera dentro del rango de 16bits o de 32bits, no compensaria.

Con lo que el codigo quedaria asi(ejempo del de 32bits) :

Código [Seleccionar] Expand


// Comprueba si es potencia de 2
// De un numero de 32bits !!
unsigned int num=4;
__asm{
         mov eax,num; Coge numero a comprobar
         jp noPotenciaDeDos; Numero de bits en num par, IMPOSIBLE que sea potencia de 2
         mov ebx,2; Potencia de 2 a comprobar, empieza por 2

comprobacion:; En esta parte se comprueba si es potencia de 2

         cmp ebx,eax; Compara ax con la potencia de 2 actual(bx)
         je potenciaDeDos; Es potencia de 2
         shl ebx,1; Siguiente potencia de 2 a comprobar
         jnz comprobacion; Si bx es cero ya a comprobado todas las potencias de 2 si no continua comprobando

noPotenciaDeDos:; No es potencia de dos

potenciaDeDos:; Potencia de dos

}


[Juan Mellado]

 _Grey,
los mov no afectan a los flags, por lo que el mov/jp no funcionaría. Habría que hacer una operación que modificase los flags, pero no el valor. Y hay que tener en cuenta que el flag de paridad sólo tiene en cuenta los 8 bits de menor peso, no todos.

Saludos.

P.D: Z80  (genial)  

[DraKKaR]

 Para que tantas pijadas de velocidad? Suponiendo que esa funcion la uses para checkear si una textura es potencia de 2 antes de subirla a memoria de video, solo vas a tener que hacerlo 1 vez por textura, y no una vez por frame por textura. Es decir, que no va a ser el cuello de botella en ningun caso (si vas a usarla como te he dicho) y si puedes hacerla en un lenguaje de alto nivel para ganar en simplicidad aunque pierdas el doble en velocidad, creo que no es ningun problema.

[_Grey]

 Pues si señor.... la version optimizada solo coge hasta el 128  (nooo)  (nooo) , habra que usar la version SIN OPTIMIZAR que esa FUNCIONA BIEN. :ph34r:  

[_Grey]

 DraKKaR,
Totalmente de acuerdo,poco importa la velocidad para lo que quiere fiero, pero ya sabes como es esto del asm... :rolleyes: