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í:
_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...
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.
fiero, en C tampoco queda tan engorroso:
bool IsPowerOfTwo(DWORD n)
{
int b = 0;
for (; n != 0; n = n >> 1){
b += n & 1;
}
return(b == 1);
}
Saludos
Mejor con un while que con un for raro ;)
PD: Aprendí Pascal primero, sí :)
Cierto, me olvidé de los logaritmos. He estado mirandome las funciones de logaritmos del coprocesador y creo que seria una cosa así:
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í:
_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
Cita de: "Juan Mellado"fiero, en C tampoco queda tan engorroso:
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í:
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.
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
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í:
for (i = 0; ...; i ++){
if ( IsPowerOfTwo(i) ){
char s[1024];
sprintf(s, "%ld\n", i);
OutputDebugString(s)
}
}
Saludos
Citar(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.
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.
Creo que es esto:
Para una variable de 16 bits:
// 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:
// 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.... ;)
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) :
// 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
}
_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)
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.
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:
DraKKaR,
Totalmente de acuerdo,poco importa la velocidad para lo que quiere fiero, pero ya sabes como es esto del asm... :rolleyes:
Viciosos de mierda XD
Citarfiero,
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.
No se como tenia metido en la cabeza que siempre desplazaba con signo :huh: , será que nunca lo habia hecho con unsigned. Gracias por el apunte :)
Da igual que la función se use poco. En ensamblador lo mejor es acostumbrarse a buscar siempre la opción más rápida, para ir cogiendo destreza que en otras partes se va a necesitar.
un saludo
Cita de: "Juan Mellado"
1) sí funciona si el bit de mayor peso es 1. Prueba IsPowerOfTwo(0x80000000), ya verás como devuelve true.
No lo he probado, pero me extraña, porque ">>" desplaza y mantiene el signo (bit de mayor peso) y no saldría nunca del bucle (n jamás sería 0)
Cita de: "Juan Mellado"
2) 1 si es potencia de 2. Concretamente, 2 ^ 0 (2 elevado a 0).
^_^ Vale, lapsus mental.
Cita de: "fiero"...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.
Vuelve a mirar mi código: ">>>" es un desplazamiento, deja ceros a la izquierda.
En Visual C++ 6.0, tres '>' dan un error sintáctico. ¿Qué compilador utilizas? Yo no sabia que existia el desplazamiento '>>>'
Edito para poner esto:
http://msdn.microsoft.com/library/default...._.operators.asp
Creo que con Borland, pero no me hagas mucho caso, hace mucho que no toco C, ahora estoy con... (asco)
En C no existe el operador '>>>'. Pero bueno, ya sabeis lo que les gusta inventar cosas a los de borland en sus compiladores.
Sé que no debería, pero ...
Función:
bool IsPowerOfTwo(DWORD n)
{
_asm{
mov eax, n
mov ebx, eax
dec eax
js no_PowerOfTwo //Caso especial: n = 0
and eax, ebx
jnz no_PowerOfTwo
}
return(true);
no_PowerOfTwo:
return(false);
}
Programa de Prueba:
void Test_IsPowerOfTwo()
{
DWORD i = 0;
do{
if ( IsPowerOfTwo(i) ){
char s[1024];
sprintf(s, "0x%08x\n", i);
OutputDebugString(s);
}
}while(++i != 0);
}
Salida de la Prueba:
0x00000001
0x00000002
0x00000004
0x00000008
0x00000010
0x00000020
0x00000040
0x00000080
0x00000100
0x00000200
0x00000400
0x00000800
0x00001000
0x00002000
0x00004000
0x00008000
0x00010000
0x00020000
0x00040000
0x00080000
0x00100000
0x00200000
0x00400000
0x00800000
0x01000000
0x02000000
0x04000000
0x08000000
0x10000000
0x20000000
0x40000000
0x80000000
La idea: Las potencias de 2 son los únicos números que no tienen en común ningún bit puesto a uno con el número que le precede. Por lo tanto, el AND entre un número N y N - 1 es 0 sólo si N es una potencia de dos. Caso especial el cero.
Saludos a todos
Juan Mellado, sencillamente genial! (genial)
Además esta forma de averiguar si es potencia me viene como anillo al dedo, ya que yo necesito los valores de N-1 como máscaras para hacer el texture wrap. Lo que hago es almacenar en la máscara N-1 si N es potencia de 2 y 0xFFFFFFFF si no lo es (así el wrap queda desactivado). Y con tu algoritmo queda increiblemente sencillo:
mov edx,eax //En eax TamY y TamX
sub eax,0x10001
and edx,eax
jz potencia2
mov eax,0xFFFFFFFF
potencia2:
mov dword ptr[masqwrap],eax
¿Te lo has inventado tú o es cosa de libro?
gracias y un saludo
Cita de: "fiero"¿Te lo has inventado tú o es cosa de libro?
Idea mía B), me di cuenta de esa relación entre N y N-1 haciendo una lista de números en binario. De haberlo copiado de algún sitio hubiera puesto la referencia o el link correspondiente ;).
Me alegra haberte sido de ayuda.