Sistemas operativos modernos

#define B Y T E _ S IZ E 8 int bit_count(int byte) { int i, count =0 ; for(i= 0;i< BYTE_SIZE : i++) if ((byte> >i )& 1)count++; return(count); } (a) r Un byte contiene 8 bits */ r Cuenta los bits de un byte V /’ ciclo que procesa los bits de un byte */ /* si el bit es 1, lo suma a count V r devuelve la suma */ /* Macro para sumar los bits de un byte y devolver la suma. V #deflne bit_count(b) (b&l) + ((b»1)&1) + ((b»2)&1) + ((b»3)&1) +\ {(b»4)&1) + {(b»5)&1) + ((b»6)&1) + ((b»7)&1) (b) r Macro para consultar la cuenta de bits de una tabla. */ char bits[256] ={ O, 1, 1, 2. 1, 2. 2, 3, 1, 2, 2, 3, 2, 3. 3, 4, 1, 2, 2, 3, 2, 3, 3, ...}: #define bit_count(b) (int) bits[b] (c) Figura 12-6. a) Procedimiento para contar bits de un byte, b) Macro para contar los bits, c) Macro para consultar la cuenta de bits de una tabla. es mucho más eficiente porque eUmina el gasto adicional tanto de la llamada a procedimiento como del ciclo. Podemos llevar este ejemplo un poco más lejos. ¿Para qué calcular el número de bits en 1? ¿Por qué no consultarlo en una tabla? A fin de cuentas, sólo hay 256 bytes distintos, cada uno con cierto número de bits 1 enü-e O y 8 . Podemos declarar una tabla de 256 entradas, bits, y asignarle como valor inicial (en tiempo de compilación) la cuenta de bits correspondiente a ese valor de byte. Con este método no se requiere cálculo alguno en tiempo de ejecución, sólo una operación de indización. En la figura 12-6c se presenta una macro que se encarga de esta tarea. Éste es un ejemplo claro de sacrificar memoria para acelerar la ejecución. Sin embargo, podríamos ir más lejos aún. Si se requieren conteos de bits para palabras enteras de 32 bits y usamos nuestra macro bit_count, tendremos que efectuar cuatro consultas de tabla por palabra. Si expandimos la tabla a 65,636 entradas, bastarán dos consultas por palabra, y el precio será una tabla mucho más grande. La consulta de respuestas en tablas puede usarse en otras formas. Por ejemplo, en el capí­ tulo 7 vimos cómo funciona la compresión de imágenes JPEG, con transformaciones de cose­ no más bien complejas. Una técnica de compresión alterna, GIF, utiliza consulta de tablas para codificar píxeles RGB de 24 bits. Sin embargo, GIF sólo funciona con imágenes de 256 colo­ res o menos. Para cada imagen a comprimir se construye una paleta de 256 entradas, cada una de las cuales confiene un valor RGB de 24 bits. Así, la imagen comprimida consiste en un ín­ dice de 8 bits por cada píxel, en lugar de un valor de color de 24 bits, con lo que se reduce el tamaño a una tercera parte. Esta idea se ilustra en la figura 12-7 para una sección de imagen de 4 X4. La imagen original no comprimida se muestra en la figura 12-7a. Cada uno de estos va­ lores es de 24 bits, con 8 bits para cada una de las intensidades de rojo, verde y azul. La imagen