• Lunes 23 de Diciembre de 2024, 03:24

Autor Tema:  Programando Bits  (Leído 2520 veces)

nicokiki

  • Miembro MUY activo
  • ***
  • Mensajes: 298
    • Ver Perfil
Programando Bits
« en: Lunes 24 de Mayo de 2004, 14:49 »
0
Hola gente!!!!!!!!!

Estoy haciendo una clase (C++) que a partir de un long convierte ese numero a codificacion GAMMA, usada para codificar numeros en indexacion (es una forma de comprimir informacion). Les doy un ejemplo de Gamma:

6 en base decimal a Gamma:

log(6) = 2        //log en base 2 redondeado para abajo
2 + 1 = 3  entonces represento este tres en unario:
"110" en unario = 3 en decimal
X- 2^log|X| = 8 - 2^3 = 8 - 8 = 0 entonces represento el 0 en log|X| bits en binario, entonces 0 en base 10 = 00 en base 2 en 2 bits entonces:

8 (en base 10) = 110 00 (en gamma)

Bueno, como veran tengo q trabajar a nivel de bits, cosa q no he hecho jamas. Tengo claro q a la hora de guardar bits, si o si los tengo q guardar en grupos de 8 bits (1 byte) y eso implica mas bits a llenar en el byte.
El problema viene por este lado, yo puedo resolver el metodo sin ningun problema, pero la pregunta es donde voy guardando los bits. Se entiende q si lo guardo en un short (2 bytes "supuestamente") estoy desperdiciando bits (o no dependiendo si tengo mas de 16 bits), entonces mi idea seria guardar los bits en un buffer, pero no se de q tipo tiene q ser ese buffer. Eso es lo q quiero q alguien me diga, mi buffer, de q tipo debe ser???? Hay algun tipo de dato q me ayude con esto????

Salu2!!!!!

nicokiki

  • Miembro MUY activo
  • ***
  • Mensajes: 298
    • Ver Perfil
Re: Programando Bits
« Respuesta #1 en: Lunes 24 de Mayo de 2004, 14:52 »
0
Me confundi en el ejemplo con el 6 y el 8:

Ahi va:

6 en base decimal a Gamma:

log(6) = 2 //log en base 2 redondeado para abajo
2 + 1 = 3 entonces represento este tres en unario:
"110" en unario = 3 en decimal
X- 2^log|X| = 6 - 2^2 = 6 - 4 = 2 entonces represento el 2 en log|X| bits en binario, entonces 2 en base 10 = 10 en base 2 en 2 bits entonces:

6 (en base 10) = 110 10 (en gamma)

Salu2!!!!

Ruben3d

  • Miembro HIPER activo
  • ****
  • Mensajes: 710
  • Nacionalidad: es
    • Ver Perfil
    • Web personal
Re: Programando Bits
« Respuesta #2 en: Lunes 24 de Mayo de 2004, 15:20 »
0
Hola.

Que yo sepa no hay ningún tipo de datos que ocupe un solo bit. El más apropiado para ello sería bool, pero ocupa un byte. Lo que he visto hacer en estos casos es coger un array de char e ir accediendo al bit que quieras posicionandote primero en el array y aplicando una máscara para obtener el bit deseado (esto es lo que se hace con el FD_SET que usa el select() en linux, con macros). Así no desperdicias nada de espacio, pues usas los 8 bits de cada char.

También podrías acceder a cada uno directamente con un campo de bits:
Código: Text
  1. struct byte
  2. {
  3.     char bit0:1;
  4.     char bit1:1;
  5.     char bit2:1;
  6.     char bit3:1;
  7.     char bit4:1;
  8.     char bit5:1;
  9.     char bit6:1;
  10.     char bit7:1;
  11. };
  12.  

Un saludo.

Ruben3d

nicokiki

  • Miembro MUY activo
  • ***
  • Mensajes: 298
    • Ver Perfil
Re: Programando Bits
« Respuesta #3 en: Lunes 24 de Mayo de 2004, 16:44 »
0
Hola Ruben3d!!

Yo lo estaba haciendo como vos decis pero el problema es q cuando asigno alguna tira de bits al char, cargo quizas tres bits en un lugar donde entran 8, y no puedo cargarle mas. O sea, cada vez q cargo una tira de bits, seguramente pierda espacio libre. No hay otra manera de hacer esto???

Salu2!!!!!

patitofeo

  • Miembro MUY activo
  • ***
  • Mensajes: 145
    • Ver Perfil
Re: Programando Bits
« Respuesta #4 en: Lunes 24 de Mayo de 2004, 17:44 »
0
Hola,
 :hola:

Lo que se me acaba de ocurrir.

yo guardaria cada bit en un char como decia Ruben3d.

y estos char formarian un arreglo.

seria:

Código: Text
  1.  
  2.  
  3. char sub_buffer[8];
  4.  
  5.  

vas guardando los bits en cada elemento del arreglo;

algo como:

Código: Text
  1.  
  2. i=0;
  3. while (i<8)
  4. {
  5. ...
  6. sub_buffer[i++]=#bit#;
  7. ...
  8. }
  9.  
  10.  

cuando se llene el arreglo lo vuelcas en una variable de tipo char
con operadores como '<<' , '>>' , |  o &.

algo como:

Código: Text
  1.  
  2.  
  3. char data;
  4. ....
  5. ....
  6. for(i=0;i&#60;8;i++)
  7. {
  8. sub_buffer[i]=sub_buffer[i]&#60;&#60;i; //desplazo i bits a la izq
  9. }
  10.  
  11. data=sub_buffer[0]|sub_buffer[1]|....|sub_buffer[7]; //or lógica de
  12.                                                                              //los componentes del arreglo
  13.  
  14.  

la ultima or la podrias hacer también como:

Código: Text
  1.  
  2. for(i=0;i&#60;8;i++)
  3. {
  4. data=data|sub_buffer[i];
  5. }
  6.  
  7.  

pero tarda un poco más.

Despues solo tienes que ir metiendo los char (data) en un buffer mayor como una pila o lo que necesites.

es solo una idea.

yo he trabajado con los operadores '|', '&', '<<' y '>>' para crear un driver de una camara que recibia streams de bits y me funcionaron perfectos.

Espero haberte sido util. Por favor dime i funciono ¿ok?

saludos

 :D       :hola:         :smartass:

Ruben3d

  • Miembro HIPER activo
  • ****
  • Mensajes: 710
  • Nacionalidad: es
    • Ver Perfil
    • Web personal
Re: Programando Bits
« Respuesta #5 en: Lunes 24 de Mayo de 2004, 17:57 »
0
La solución que te he propuesto te permite guardar todos los bits seguidos sin perder espacio (la primera de ellas), pero no te ofrece información de dónde acaba y dónde empieza cada secuencia de bits. ¿Necesitas esta información?

Un saludo.

Ruben3d

nicokiki

  • Miembro MUY activo
  • ***
  • Mensajes: 298
    • Ver Perfil
Re: Programando Bits
« Respuesta #6 en: Lunes 24 de Mayo de 2004, 19:06 »
0
Ruben3d!!

Si la quiero a esa info y no te entendi bien lo de FD_SET. Mire en las man pages ( a traves de google.com/linux) y no entendi q es y como se usaria. Si tuvieras un minimo ejemplo, yo lo sigo. No es de vago q no lo quiero hacer, no tengo idea de como hacerlo

Salu2!!!!!

Ruben3d

  • Miembro HIPER activo
  • ****
  • Mensajes: 710
  • Nacionalidad: es
    • Ver Perfil
    • Web personal
Re: Programando Bits
« Respuesta #7 en: Lunes 24 de Mayo de 2004, 21:09 »
0
Bueno, como te dije con el sistema que usa fd_set no puedes saber dónde empieza y acaba cada secuencia de bits, sino que hay una gran lista de bits que se pueden acceder por un índice (eso sí, van seguidos y no se pierde espacio). Tendrías que ingeniar un método para saber dónde está cada secuencia en su interior.

En esta web
select(), FD_SET(), FD_CLR(), FD_ISSET(), FD_ZERO()
hablan de fd_set.

Me parece que puedes ver en sys/select.h cómo están definidas las macros.

Un saludo.

Ruben3d

Amilius

  • Miembro HIPER activo
  • ****
  • Mensajes: 665
    • Ver Perfil
Re: Programando Bits
« Respuesta #8 en: Martes 25 de Mayo de 2004, 00:04 »
0
Yo hice un algoritmo de compresión mediante prefijos: La idea es recodificar cada byte en un prefijo único que puede tener n bits. Los bytes más frecuentes tendrán prefijos más cortos y los menos frecuentes prefijos más largos. No es necesario que cada nueva codificación tenga tamaño fijo por que son prefijos únicos y no existe ambiguedad al leerlos.

Al grano:

- Tienes que crear un funcion que almacene en un bloque de memoria n bits de por ejemplo un entero de 32bits, suponiendo que nunca tendrás un código de más de 32 bits. (más adelante lo detallo)

El problema es que sólo lo podrás leer secuencialmente, lo que no es problema para un algoritmo de compresión. Si necesitaras acceder en todo momento a cualquiera de los valores codificados y además necesitas saber la longitud en bits de cada código no te queda mejor remedio que desperdiciar bits y además agregar un byte extra para indicar el tamaño en bits del código:
un arreglo de int para el codigo (si no pasará de 32 bits) y otro de char para el tamaño.

Para almacenar códigos de n bits que sean prefijos únicos como usualmente ocurre en ese tipo de compresión (no sirve si es necesario saber la longitud de cada código de n bits):
==============================================0

Tienes que tener buffers de todo tamaño, en general:

1er buffer: un entero de 32 bits. (Registros)
2do buffer: un pedazo de memoria de digamos 64kb o lo que necesites o veas conveniente, si al final guardarás los datos en disco 64Kb no estarán nada mal (RAM)
3er buffer: si es necesario guardar en disco, un archivo abierto listo para guardar información. (DISCO)

La idea es esta:

- Coges el número entero y sabes cuantos bits tienes que extraer y almacenarlos en el buffer.
- Ves si en tu buffer de 32 bits existe espacio suficiente, si existe lo agregas usando desplazadores << >> para posicionar los bits en el lugar adecuado y los colocas con el operador de bits "or" |.
- Si no existe espacio suficiente tienes que partir en dos el código, guardar el pedazo que entra en el buffer y luego guardar el pequeño buffer de 32 bits en el buffer mayor, luego limpias el buffer de 32 bits y colocas el resto del código que faltaba colocar en buffer.

Lo mismo para los otros buffers:

Cuando se llene el buffer de 64 kb (ejemplo), guardarlo en disco y limpiar el buffer de 64Kb, luego agregar al buffer limpio lo que faltó guardar al momento que el buffer se llenó.

nicokiki

  • Miembro MUY activo
  • ***
  • Mensajes: 298
    • Ver Perfil
Re: Programando Bits
« Respuesta #9 en: Miércoles 26 de Mayo de 2004, 16:23 »
0
Gracias Amilius!!

Muy bueno lo q me djiste. Me pongo a hacerlo

Salu2!!!!!! :kicking: