viernes, 13 de junio de 2008

Java a nivel de Bits

Para este post, quisiera tratar un tema que es algo tabú en la comunidad Java (y entiendo por qué). Cuando un programador Piensa en Java, en general, se imagina a esos monstruos gigantes que son los EJBs, que viven en contenedores terroríficos de componentes que manejan transacciones, seguridad y miles de incumbencias transversales de forma transparente y casi mágica. Casi automáticamente aparecen los millones de frameworks de aplicaciones enterprise, que se pueden sumar todos y combinar, y además todos los componentes son capaces de serializarse por sí­ solos, de viajar a través de la red y comunicarse a través de diferentes servidores de aplicaciones y diferentes Virtual Machines, en un mundo enteramente distribuido en que las clases viven ofreciendo sus servicios y conversando entre sí­ a través de mensajes.

Suena extraño cuando uno vuelve a releer la historia, después de saber todo esto, y recuerda que originalmente Java nació como un lenguaje multiplataforma para microcontroladores, un lenguaje para sistemas integrados o empotrados en pequeños dispositivos electrónicos (sí­, como electrodomésticos, por ejemplo).

Sun Microsystems lanzó la primera versión de Java en agosto de 1995 y, desde 1995 hasta hoy, gracias al aporte de las inmensas y poliformes comunidades Open Source ha crecido de manera increí­ble. Por eso muchos programadores se han olvidado que también se puede programar aplicaciones de bajo nivel en Java y hay mucha gente que usa Java para dispositivos de recursos limitados. JavaME (microedition), por ejemplo, es el conjunto de librerí­as que Sun ha publicado para trabajar con una Virtual Machine mucho más liviana y reducida, conocida como KVM.

Por eso, a la hora de trabajar con estas plataformas de recursos limitados (como celulares, microcontroladores, etc), es importante ser económico con el espacio en el guardado de datos. En aplicaciones de este tipo, en general, uno persiste parámetros de configuración y muchos valores que son pequeños, que habitualmente ocupan unos escasos bits. Entonces, si tenemos un dato booleano, por ejemplo, ¿por qué guardarlo en un byte, desperdiciando 7 bits que podrí­an ser valiosos para guardar otros 7 booleanos más, o algún otro dato?

Mediante dos pequeños ejemplos escritos en una aplicación JavaSE con Java6, mostraré la forma de guardar una colección de unsigned shorts (sí­, no es un error, ya sé que en Java no existen los unsigned) ocupando 16 bits para cada uno de ellos y una colección de SmallBytes de tan sólo 4 bits sin desperdiciar ni un bit de espacio. Lo que quiero mostrar con el primer ejemplo es que es posible burlar el bit de signo que la Virtual Machine reserva para un tipo de dato primitivo numérico, guardando en disco un short que va de 0 a 65535 (y no de -32768 a 32767 como serí­a por defecto para un short signado). Luego, usando los conceptos aprendidos en el primer ejemplo, mostraré cómo grabar estos SmallBytes de 4 bits, uno pegado al otro, sin desperdiciar espacio intermedio. Para esto, abriré un archivo y en ellos guardaré bytes que contengan dos SmallBytes cada uno.

EjemploUnsignedShorts

Para empezar, vamos a ver dos consideraciones importantes, que son caracterí­sticas fundamentales de la Virtual Machine de Java.



Tipos de Datos Primitivos:


TipoTamañoRango
char16 bitsde 0 a 65535
byte8 bitsde -128 a 127
short16 bitsde -32768 a 32767
int32 bitsde -2147483648 a 2147483647
long64 bitsde -9223372036854775808 a 9223372036854775807
float32 bitsde 1.40239846e-45f a 3.40282347e+38f
double64 bitsde 4.94065645841246544e-324d a 1.7976931348623157e+308d.

A diferencia de C/C++, Java no cuenta con tipos de datos unsigned. Por eso el rango de un short, por ejemplo, que como vemos en el cuadro anterior ocupa 16 bits, es de -32768 a 32767. Si tuviéramos que tratar con un tipo de datos entero positivo que se fuera del rango de 2^15-1, tendríamos que declarar un int. Si estamos trabajando en JavaME para un celular de bajos recursos (imaginen un Nokia 6010, que sólo puede cargar aplicaciones de 64K de jar), desperdiciar un bit de signo sabiendo que no lo vamos usar es un pecado mortal.

En el ejemplo voy a trabajar de la siguiente forma: en memoria voy a manipular un int, pero un int que sé que va a caer en el rango de 0 a 65534 (me reservo el último número: 65535 para el End Of File). Pero a la hora de persistir, voy a manipular el dato a nivel de bytes y voy a guardar sólo dos bytes, que son todo mi número.

Y aquí llegamos a la segunda consideración importante de la Java Virtual Machine:


Big-endian


Este ejemplo funciona, ya que la JVM organiza la memoria en formato big-endian. Si estuviéramos trabajando en C o cualquier otro lenguaje que compile directamente sobre el procesador de una PC tendríamos exactamente el caso opuesto, ya que la arquitectura de una PC aloja las tiras de bytes en formato little-endian. Lo que implica que sea más fácil el ejemplo, ya que leeremos el número de la forma natural, sin tener que invertir los bytes.



La escritura

Empecemos escribiendo el método que se encargará de guardar el unsigned short en un OutputStream:


private OutputStream salida;

public void writeUnsignedShort(int datoDe16bits) throws IOException {
        byte[] codeBytes = new byte[2];
        codeBytes[0] = (byte)(datoDe16bits & 0xFF);
        codeBytes[1] = (byte)((datoDe16bits & 0xFF00)>>8);       
        salida.write(codeBytes);
}

Se recibe por parámetro un int, como ya había adelantado, pero como se trata de un número positivo más chico que 65534, sólo los dos primeros bytes de los cuatro que ocupa el int van a estar llenos. La "parte alta" del parámetro tendrá basura que no me interesa persistir.

Primero me creo un array de bytes donde voy a guardar los dos bytes. Luego, lo cargo, primero con la parte más baja del entero (el primer byte), después con la segunda parte (el segundo byte). Eso es lo que hago en estas dos líneas:

codeBytes[0] = (byte)(datoDe16bits & 0xFF);
codeBytes[1] = (byte)((datoDe16bits & 0xFF00)>>8);

Hagamos un ejemplo a nivel de bits para entender mejor como funciona estas máscaras:

datoDe16bits = 00000000.00000000.01100110.11011011

Para obtener el primero de los 4 bytes del int, simplemente hago un and con la máscara 0xFF (00000000.00000000.00000000.11111111 en binario).

00000000.00000000.01100110.11011011 & 00000000.00000000.00000000.11111111 = 00000000.00000000.00000000.11011011

Lo que me devuelve la operación del AND es un entero, cuando lo casteo a byte, simplemente me quedo con: 11011011.

En la siguiente línea hago parecido, pero con la máscara 0xFF00:

00000000.00000000.01100110.11011011 & 00000000.00000000.11111111.00000000 = 00000000.00000000.01100110.00000000

A continuación hago un shifteo de 8 posiciones hacia la derecha, para quedarme con: 00000000.00000000.00000000.01100110. Y al castear: 01100110.

Estos dos bytes, así como fueron separados van a parar a la salida, un OutputStream.


La lectura


private InputStream entrada;

public int readUnsignedShort() throws IOException {
        int datoDe16bits = (entrada.read() & 0xFF);
        datoDe16bits += (entrada.read() & 0xFF) << 8;
        return datoDe16bits;
}

Cuando leo lo que hago es leer los dos bytes por separado y los cargo en el entero, ubicándolos en la sección que les corresponde. El shifteo esta vez es hacia la izquierda, para que el segundo byte se posicione donde debe. No hay mucho que explicar acá. Es casi lo mismo que la escritura, pero el proceso inverso.

El lector más atento quizá se ha preguntado por qué estoy usando una máscara de 0xFF cuando a primera vista parece estar de más. Recordemos cuanto valía el byte de la parte más baja del ejemplo anterior: 11011011. Como el operador << (corrimiento de bits) es un operador aritmético y no lógico, como sí es >>>, si yo hiciera esto directamente:

datoDe16bits += entrada.read() << 8;

Sin aplicar la máscara me vería en graves problemas, porque si fuera el número 11011011, Java interpretaría que se trata de un número negativo (porque el primer bit de signo está en 1), y luego tomaría la parte entera de los siete bits restantes como el complemento a la base. Por ende, como podrán ver, obtendría cualquier número (encima negativo) menos el que yo había almacenado. Como el operador & (and) es un operador lógico, después de efectuar esta operación, obtengo una serie de bits que Java sabe que son bits lógicos y que no debe tratar de interpretar como número.

La prueba de que esto funciona se hace grabando 16 unsigned short en un archivo llamado shortsFile.bin. Luego se cierra el archivo, se vuelve a abrir, se recuperan los números y se muestran en la consola para verificar efectivamente que se devuelven los mismos números que se habían cargado (16 números que son potencias de dos menos dos).

El código se puede descargar de:


Hay dos cosas nada más que me gustaría destacar de este código. Una, que, como podrán verificar si lo corren, les genera un archivo de 32 byes. Si lo dividimos por la cantidad de números que cargamos, 16, obtenemos que cada número está pesando exactamente 2 bytes (Gualá!). Dos: al final del archivo guardo un número extra: 65535 (EOF). En realidad esto no hace falta, ya que Java avisa cuando se alcanza el fin de archivo. Esto podría removerse para no desperdiciar esos dos bytes finales. Este EOF me quedó porque primero elaboré el ejemplo de los SmallBytes en donde sí es necesario tener mi propio EOF, y el que pasaré a explicar.

EjemploSmallBytes


Si en el ejemplo anterior trabajamos a nivel de bytes, en este vamos a ir un poco más a bajo nivel y trabajar a nivel de bits. El objetivo: guardar números de 4 bits que van de 0 a 14 (el 15 lo guardo para el EOF), juntando dos de ellos en un byte.

Para ser un poco elegante (y sólo porque estamos en JavaSE y no en JavaME donde tener clases de más también hace aumentar el tamaño del jar final), voy a usar una clase llamada SmallByte que hereda de Number, que sea hermanita de Integer, Short, etc...

public class SmallByte extends Number {
   
    private static final long serialVersionUID = 1L;       
    private final byte EOF = 15;
   
    private byte number;

    public SmallByte() {
        number = 0;
    }
   
    public SmallByte(byte number) {
        setValue(number);
    }
   
    public SmallByte(int number) {
        setValue((byte) number);
    }
   
    public void setAsEOF() {
        number = 15;
    }
   
    public boolean isEOF() {
        if (number == EOF) {
            return true;
        }
        return false;
    }
   
    public void setValue(byte number) {
        if (number >= 16) {
            throw new IllegalArgumentException("Un SmallByte no puede ser mayor que 15");
        }
        if (number < 0) {
            throw new IllegalArgumentException("Un SmallByte no puede ser negativo");
        }
        this.number = number;
    }

    public void setValue(int number) {
        setValue((byte) number);
    }
   
    @Override
    public byte byteValue() {       
        return number;
    }

    @Override
    public double doubleValue() {
        return number;
    }

    @Override
    public float floatValue() {
        return number;
    }

    @Override
    public int intValue() {
        return number;
    }

    @Override
    public long longValue() {
        return number;
    }

    @Override
    public short shortValue() {
        return number;
    }   

}

El ejemplo es un poquito más complicado que el anterior, pero tampoco tanto. Se los voy a dejar a ustedes para que lo miren si quieren porque ya estoy cansado (jajaja). Además la entrada se está haciendo muy larga.

Lo que hago en este ejemplo es abrir un archivo llamado smallbytes.bin en un OutputStream, le cargo 15 Smallbytes (más el Smallbyte EOF de fin de archivo), lo cierro (noten que el archivo pesa exactamente 8 bytes: 8/16 = 0.5, medio byte por número), lo vuelvo a abrir de vuelta en un InputStream, leo los números, los tiro en la consola y verifico que sean los mismos que cargué.

El procedimiento es bastante parecido en realidad. El SmallByte, en memoria, en realidad es un byte y al guardar y leer lo hago a nivel de bytes, leyendo la parte alta y la parte baja del byte y haciendo un corrimiento de cuatro posiciones a la derecha o a la izquierda, dependiendo de si estoy leyendo o escribiendo. En este caso el EOF sí es indispensable porque si la cantidad de números que tengo que guardar es impar, como en este caso, el último byte del archivo va a guardarse medio lleno. Como todos sabemos, un byte medio lleno no existe. Un byte medio lleno significa que la mitad tiene un dato que nos interesa y la otra mitad es basura. Java avisa que se encontró el fin de archivo, pero una vez leído el byte entero. De alguna forma tenemos que darnos cuenta al leer información útil que la parte alta de ese byte no es un número que se haya cargado. Al leer EOF, en este caso 15, sabremos que la lectura de datos ha terminado.

package elblogdelfrasco.javaSE.javaaniveldebits;

import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.ArrayList;

public class EjemploSmallBytes {

    private InputStream      entrada;
    private OutputStream     salida;   
   
    public void writeSmallBytes(SmallByte[] datos) throws IOException {
       
        byte[] datosToWrite = new byte[datos.length / 2 + 1];
        boolean byteLleno = true;
       
        for (int i = 0; i < datos.length; ++i) {
            if (byteLleno) {
                byteLleno = false;
                // Se va a llenar la parte baja de este byte
                datosToWrite[i/2] = (byte) (datos[i].intValue() & 0xF);               
            } else {
                // Se va a llenar la parte alta de este byte
                datosToWrite[i/2] += (byte) (datos[i].intValue() & 0xF) << 4;
                byteLleno = true;
            }
        }
       
        // El último byte que se guarda es el de fin de archivo
        SmallByte eof = new SmallByte();
        eof.setAsEOF();
       
        if (byteLleno) {
            // El EOF se guarda en la parte baja del último byte
            datosToWrite[datosToWrite.length - 1] = eof.byteValue();
        } else {
            // El EOF se guarda en la parte alta del último byte
            datosToWrite[datosToWrite.length - 1] += (byte) (eof.intValue() & 0xF) << 4;
        }
       
        // Se escribe la tira de bytes en el archivo
        salida.write(datosToWrite);
    }
   
    public SmallByte[] readSmallBytes() throws IOException {
       
        ArrayList datos = new ArrayList();
       
        // Del archivo de entrada se leerá de a un byte, osea: de a 2 SmallBytes
        try {
            SmallByte smallByte;
            boolean eof = false;
            while (!eof) {
                int dato = entrada.read();               
                // Tomo la parte baja del dato
                smallByte = new SmallByte(dato & 0xF);
               
                if (!smallByte.isEOF()) {
                    datos.add(smallByte);
                   
                    // Tomo la parte alta del dato
                    smallByte = new SmallByte((dato & 0xF0) >> 4);
                    if (!smallByte.isEOF()) {
                        datos.add(smallByte);
                    } else {
                        eof = true;
                    }                   
                } else {
                    eof = true;
                }
            }
        } catch (IllegalArgumentException iae) {
            iae.printStackTrace();
        }
       
        SmallByte[] res = new SmallByte[datos.size()];
        return datos.toArray(res);       
    }
   
    public void saveBytes(SmallByte[] datos) {
        try {
            salida = new FileOutputStream("smallbytes.bin");
            writeSmallBytes(datos);
            salida.close();
        } catch (IOException ioe) {
            ioe.printStackTrace();
        }       
    }
   
    public SmallByte[] readBytes() {
        try {
            entrada = new FileInputStream("smallbytes.bin");
            SmallByte[] datos = readSmallBytes();
            entrada.close();
            return datos;
        } catch (IOException ioe) {
            ioe.printStackTrace();
            return null;
        }
    }
   
    public void execute() {
               
        // Cargo una lista de SmallBytes de 0 - 14       
        SmallByte[] datos = new SmallByte[15];       
        for (int i = 0; i < 15; ++i) {
            datos[i] = new SmallByte(i);
        }
       
        // Los guardo en el archivo
        saveBytes(datos);
               
        // Leo los datos en un nuevo array de SmallBytes
        SmallByte[] datosRecuperados = readBytes();
       
        // Se muestran los bytes recuperados en la consola
        for (int i = 0; i < datosRecuperados.length; ++i) {
            System.out.println("SmallByte: " + datosRecuperados[i].byteValue());
        }
       
    }
   
}

Descargar el Código

El código completo lo he puesto para descargar en un repositorio SVN de Assembla:



Espero que les haya gustado/servido.

Por un mundo más libre!
Salud!