Poesía binaria

Aquí llega mi primera aportación a las soluciones de los retos del I concurso de programación de Tuenti. La utilización de números grandes es algo que siempre me llamó la atención, y normalmente utilizo bc cuando necesito algún cálculo. Este reto se podía resolver con bash/sed/bc y, aunque varios lenguajes permiten la utilización de números de precisión arbitraria “de serie”  como python y Java, yo decidí hacerlo en C, utilizando la biblioteca GMP.

En un lenguaje como C, es normal que no podamos utilizar números de precisión arbitraria con los operadores normales (+, -, *,…), en este caso tendremos que hacer llamadas a funciones de la biblioteca para realizar las operaciones, tampoco podremos utilizar un printf() normal para mostrarlos.

Para compilar, debemos incluir gmp:

$ gcc -o hardsum hardsum.c -lgmp

Para utilizar este tipo de variables numéricas, primero tendremos que inicializarlas con mpz_init(), otras funciones interesantes son:

• mpz_set_si(): inicializa el número con un valor entero.
• gmp_sscanf(): igual que scanf(), pero con la posibilidad de utilizar estas nuevas variables.
• mpz_add(): realiza la suma de dos números
• gmp_printf(): igual que printf(), pero con la posibilidad de utilizar estas nuevas variables.

GMP tiene muchísimas funciones para realizar gran cantidad de operaciones, se puede consultar la documentación aquí.

Algo que pocas veces tenemos en cuenta es la alineación de las variables en la memoria RAM. Muchas veces, ni nos va, ni nos viene, aunque en ciertas ocasiones suele causar calentamientos de cabeza.

Tiene que ver con la forma que tiene la CPU para dialogar con la RAM y la arquitectura de éstas. Partimos del hecho de que pedir un dato a la memoria es algo lento, sí se hace muchos millones de veces por segundo, pero mientras viene o no viene el dato, la CPU simplemente espera.  Ahora, tenemos que tener en cuenta:

• El diálogo CPU<–>Memoria es a través de palabras y la palabra, en un sistema de 32bit es de 32bit (4bytes), en uno de 64bit serán 8bytes, no en todos los procesadores es así, pero casi.
• Cada byte en memoria tiene una dirección, para que la CPU y la memoria puedan ubicar el dato.
• Por otra parte,  las palabras en memoria tienen una posición que coincide con que su dirección sea divisible por la longitud de la palabra.
• Sólo podemos acceder a una palabra en un mismo instante.

Por tanto, en mi PC de 32bit, cuando quiero un int de 32bit, normalmente me lo traigo de direcciones que sean divisibles por 4, por lo tanto, sólo hago una lectura a la memoria; por ejemplo, mi dato ocupa desde la dirección 0×0030 a la 0×0033 (4bytes), me lo traigo de una sola tirada. De otro modo, si mi dato ocupara desde la direccion 0×0032 a la 0×0035 (4bytes también), tendría que hacer dos peticiones, la palabra 0×0030–0×0033 y la palabra 0×0034-0×0036, y luego coger los dos últimos bytes de una y los dos últimos bytes de la otra; cosa que por experimentar está bien, pero no es óptimo, perdemos mucho tiempo, tardamos el doble. Si nos queremos traer una variable de 8bytes, tendremos que hacerlo de dos tandas, y por diseño, es más fácil traérsela de una dirección de memoria divisible por 8

También tenemos que tener en cuenta que perdemos memoria, es decir, tendremos bytes en memoria que no usaremos para nada (y a veces no nos sobra precisamente), pero sólo podemos aguantarnos… u optimizar más nuestros programas (siempre que compense). Por ejemplo cuando declaramos dos variables, un short (2bytes) y un int(4 bytes), la primera de ellas (el short) se situará en memoria en la dirección 0×0030 y la segunda (el int) en la 0×0034, dejando 2 bytes dentro de la memoria inutilizados. Aunque los compiladores modernos, a la hora de declarar variables intentan hacerlo de la forma más inteligente posible, para aprovechar los huecos al máximo, aunque no declaremos las variables por orden, a la hora de situarlas en memoria, se suelen colocar bien:

Nota: represento variables de tipo long unsigned para representar bien los valores en sistemas de 64bit.
El resultado es algo así:

BFAF2BCF [c]            (1 bytes)
BFAF2BCE [c2]           (1 bytes)
BFAF2BCD [c3]           (1 bytes)
BFAF2BCC [c4]           (1 bytes)
BFAF2BCB [c5]           (1 bytes)
BFAF2BCA [c6]           (1 bytes)
BFAF2BC4 [i]            (4 bytes)
BFAF2BB8 [i2]           (8 bytes)
BFAF2BC2 [k]            (2 bytes)
BFAF2BB0 [ai2]          (8 bytes)
BFAF2BAE [k2]           (2 bytes)

Esto resultará lo siguiente:

El caso es que las variables siempre encajan.

Pero el tema es que cuando creamos un struct en C, lógicamente las variables también tienen que encajar, y además tienen que estar en el mismo orden en que las ponemos, el compilador, esta vez no tiene la libertad de antes de reubicar información.
Vemos el siguiente ejemplo:

Y en este ejemplo sí que podemos ver gran diferencia entre 32bit y 64bit.

32bit

BFC5E510 [e1]           (36 bytes)
BFC5E510 [e1.s1]                (2 bytes)
BFC5E514 [e1.i1]                (4 bytes)
BFC5E518 [e1.l1]                (8 bytes)
BFC5E520 [e1.i2]                (4 bytes)
BFC5E524 [e1.l2]                (8 bytes)
BFC5E52C [e1.s2]                (2 bytes)
BFC5E52E [e1.c1]                (1 bytes)
BFC5E530 [e1.s3]                (2 bytes)

Ya de primeras vemos que la estructura ocupa 36bytes y la suma de sus partes (2 + 4 + 8 + 4 + 8 + 2 + 1 + 2 = 31 bytes), por lo que vemos que la estructura ocupa más.
Si vemos el mapa de memoria (la tabla de arriba), vemos cinco interrogaciones, es decir, 5 huecos donde no trabajamos, y sólo servirán para poder alinear los demás datos.
Vemos que las primeras interrogaciones están en BFC5E512 y es que lo próximo que tenemos que colocar es un entero, por ello nos desplazamos hasta BFC5E514. El siguiente byte problemático es justo después de un char, y lo siguiente será al final, porque se nos quedan algunos bytes “colgados” y no vamos a poder aprovechar.

64bit

7FFFB3652EF0 [e1]               (40 bytes)
7FFFB3652EF0 [e1.s1]            (2 bytes)
7FFFB3652EF4 [e1.i1]            (4 bytes)
7FFFB3652EF8 [e1.l1]            (8 bytes)
7FFFB3652F00 [e1.i2]            (4 bytes)
7FFFB3652F08 [e1.l2]            (8 bytes)
7FFFB3652F10 [e1.s2]            (2 bytes)
7FFFB3652F12 [e1.c1]            (1 bytes)
7FFFB3652F14 [e1.s3]            (2 bytes)

En la tabla acortaré las direcciones de memoria:

De primeras vemos que en 64bit la estructura ocupa 40bytes en lugar de 31bytes… pero esta vez, vemos cómo a la hora de colocar un long int (8bytes) en B3652F04, se lo lleva a B3652F08, así será capaz de leerlo en una lectura a memoria (de la palabra entera de 8bytes) en lugar de 2 lecturas (de 4bytes cada una en dos palabras diferentes).

¿Cuándo debemos tener esto en cuenta?

Esto tampoco tiene mucha importancia si sólo vamos a almacenar una pequeña información en un registro, pero, si vamos a almacenar un array de muchos elementos de un registro, o una lista enlazada, podremos observar que si en el registro tenemos 9bytes que sólo sirven para hacer bulto, es decir, para conseguir alinear la información, en un millón de elementos, estaremos perdiendo cerca de 9Mb, nos puede ayudar a optimizar un poco la información que almacenamos.

Por otra parte, si lo que estamos haciendo es implementar una lectura/escritura de información en un formato determinado y, por ejemplo, tenemos:

• 3 bytes de identificación
• 4 bytes de control
• 4 bytes tamaño
• resto de archivo de información

No podremos crear un registro del tipo:

Ya que desde el último carácter hasta el entero de control habrá 1byte de diferencia y el formato no se respetará correctamente, por lo que seguramente haya algún fallo.

Esto tampoco quiere decir que no se pueda leer una variable que no esté alineada, siempre podemos hacerlo jugando con los bytes y trabajando un poco con el código, aunque las arquitecturas modernas lo permiten directamente con instrucciones especiales, eso sí, no se recomienda mucho su uso, ya que es más lento hacer dos peticiones a memoria, y luego trabajar con el resultado de las dos para unirlo; por otra parte, si trabajamos con un procesador que no disponga de estas instrucciones, tendremos que programar cómo hacemos las peticiones y la fusión de la información, aunque de eso se encargue el compilador, debemos tenerlo en cuenta si queremos que nuestro programa sea rápido.

Un pequeño ejemplo de un acceso no alineado

Si queremos provocar un acceso no alineado en C, podemos hacer lo siguiente: crear un array de char más o menos grande, y un puntero a un entero que apunte a una dirección dentro del array de char (con que apunte a la dirección base+1 vale para que no esté alineado.

La salida es algo así (en 64bits, aunque sólo se nota en el tamaño de las direcciones de memoria):

7FFFC98BE8B0 (6)
7FFFC98BE8B1 (4)
21 205 91 7 => 123456789 75BCD15 <= 7 5B CD 15

Primero mostramos la dirección de memoria base del array y el tamaño del mismo, luego la dirección de memoria base de la variable entera con la que trabajaremos y su tamaño (muy importante el sizeof(*punt), sin el * nos daría el tamaño del puntero, y estamos en 64bit, es decir, sería de 8bytes.
Y tras ello, asignaremos al entero el valor 123456789, podremos ver el valor en decimal de cada uno de los bytes que componen el entero, el valor del entero, y luego el valor del mismo en hexadecimal acompañado de los valores en hexadecimal de cada uno de los bytes de antes.

Esto está diseñado para verse en un sistema little endian, en un sistema big endian, la última línea de salida sería:

7 91 205 21 => 123456789 75BCD15 <= 15 CD 5B 7

Foto: wwarby (Flickr)

Hace unos días empecé con la serie Bailando con Bits (aunque llevaba escrito varios meses) trata de formas para trabajar a nivel de bit desde C.

Hoy voy a proponer otra forma, quizás menos intuitiva que la anterior, pero diferente. Esta vez no utilizaremos un registro enorme ni nada parecido, utilizaremos un mismo número entero para hacer el ejemplo:

Ahora usamos varias macros que harán operaciones de bit con la variable a analizar (están definidas en la parte de arriba), tenemos PESOBIT, COGEBIT, PONE_1, PONE_0 y CAMBIA:

• PESOBIT: Nos dice cuánto vale un bit con valor 1 en la posición especificada, por ejemplo en la posición 0 (LSB) vale 1, en la posición 1, vale 2, en la posición 3, vale 4, en la posición 4, vale 8…
• COGEBIT: Nos dice si el bit en la posición bpos de la variable var vale 0 ó 1
• PONE_1: Pone un 1 en el bit bpos de la variable var
• PONE_0: Pone un 0 en el bit bpos de la variable var
• CAMBIA: Cambia el valor (de 0 a 1 y viceversa) del bit en la posición bpos de la variable var

Como vemos en el ejemplo si queremos poner a 1 el bit 5 de numero, tendremos que hacer numero=PONE_1(numero,5), aunque en el siguiente ejemplo veremos cómo simplificar todo eso.

Con este ejemplo podemos jugar con los bits de números enteros. Pero, y si queremos utilizar otro tipo de variables? (aunque estamos limitados a 32bits) También tenemos este ejemplo con un tipo float:

En este caso no tenemos que hacer una variable igual a PONE_1(variable, 5) para poner su bit a 1; simplemente con PONE_1(variable, 5) nos vale. En este ejemplo podemos ver una variable de tipo float desglosada en bits y podemos modificar a nivel de bit para obtener otros valores. (No le veo mucha utilidad a esto, pero bueno).

Post dedicado a algm, por su comentario en el artículo Bailando con bits anterior.

Hay muchas formas para hacer esto, pero quizás la más visual (tal vez también útil algunas veces) es la siguiente (se explica más abajo):

Primero creamos un espacio de bits en nuestro registro Tint_bits, con ello, hacemos 32 variables de tamaño 1 bit (con un espacio en memoria de 32bits (lo que es un entero de 32bits). Lo que hacemos para poder consultar los bits, es crear un puntero de este tipo (Tint_bits) que apunte a la dirección de memoria de nuestro número, con ello podremos leer en memoria, los distintos bits del número accediendo a los diferentes miembros (b1->b32), y lo que es mejor, podemos modificarlos (como hacemos al final del programa).

Lo malo de este método es que no podremos acceder a los bits como si de un array se tratase, y que este método no es muy portable, para enteros de 64 bits habría que hacer otro registro por ejemplo, y tendremos problemas para pasar de un sistema big-endian a un little-endian y viceversa; pero, como yo digo podemos ver la memoria directamente, que a veces es interesante.