Publi

Cómo comprimir y descomprimir datos en memoria o textos en 128 líneas o menos en C

photo-1417514645232-3042464af1da_r

Si queremos que nuestra información ocupe menos, ésta es una buena forma de conseguirlo. Muy útil cuando queremos transmitir información y reducir los bytes transmitidos, es lo que hacen muchas páginas web actualmente, el servidor nos manda la página comprimida y luego el navegador se encarga de descomprimirla antes de mostrarla y como por lo general se tarda menos en comprimir-enviar-descomprimir que en enviar sin comprimir antes es algo que acelera la navegación web.

También es muy útil, si necesitamos almacenar información a la que no accedemos muy a menudo, pero no vamos a borrar, por ejemplo logs antiguos, archivos javascript y css que no vayan a cambiar (ahora en lugar de comprimir-enviar-descomprimir, sólo enviar-descomprimir, tardamos menos y nuestro servidor no se estresa), o por ejemplo, los comentarios de nuestros posts antiguos (tardaremos más en acceder a ellos, pero no accedemos a menudo y así ocupan menos).

Para este propósito me voy a ayudar de Zlib, una biblioteca de compresión completa y eficiente (ok, las hay mejores como en todo). Además, esta biblioteca la utilizan miles de programas tanto comerciales como no comerciales.

Lo más normal es comprimir y descomprimir ficheros, tenemos el ejemplo del desarrollador aquí. Aunque si la información la tenemos directamente en memoria, en una variable, por ejemplo una cadena de caracteres, como puede ser una web que hayamos estado generando o datos que estemos recibiendo desde la red, a veces queda feo escribirlo en disco para comprimirlo o descomprimirlo y ya veremos qué hacemos con esa información, que tal vez no deba pisar un archivo.

El problema de las cadenas de caracteres, tal y como las conocemos en C, es que utilizan un byte especial como terminador (\0), cosa que los datos binarios no tienen. Por ejemplo, el número 8960 en binario sería (00100011 00000000), vamos, tenemos el byte menos significativo es 0, y es totalmente necesario para nuestro dato por lo que no podemos depender de ese terminador para nuestro propósito.

Bueno, a la hora de comprimir, si sabemos que sólo vamos a comprimir cadenas de caracteres (aunque queremos hacer algo que valga para todo, pero bueno) que tengan su terminador, sí que podemos depender del terminador, pero no valdría por ejemplo para una foto, o cualquier otro dato (porque puede contener bytes a 0 y no se completaría la compresión).

A la hora de descomprimir, sí que no podemos utilizar los \0 bajo ningún concepto, y es que, los datos comprimidos claro que pueden tener un byte a 0 y mejor no ponernos a intentar predecir cuándo nos va a salir un 0 y cuándo no.

Toda esta explicación es para decir que en lugar de un terminador vamos a utilizar una variable char* donde estarán los datos, y otra variable que nos indica el tamaño del dato.

Método largo

Allá va el ejemplo y seguimos comentando, bueno, antes avisar de una cosa. En el título dice 128 líneas y como veis hay más, las 128 líneas salen quitando líneas de comentarios, en blanco y el texto de ejemplo, e incluso se puede quedar en menos (que como podréis observar, es largo):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
/*
  Zlib example to compress strings in C
  Based on http://zlib.net/zlib_how.html
 */


#include <stdio.h>
#include <string.h>
#include "zlib.h"

/* This errors are far from deflate/inflate errors, will indicate
   our destination buffer is not big enough to store the whole
   compressed or uncompressed data. */


#define ERR_UNDERSIZED -100
#define ERR_DEFLATE_PARTIAL -101
#define ERR_DEFLATE_PARTIAL_STREAM -102

/* Make it bigger to use it */
//#define CHUNK 8192
/* But you can define CHUNKs smaller for testing purposes */
#define CHUNK 128

/** ***********************************
 * Compress source data from memory to memory.
 *
 * @param source Source data
 * @param source_size Size of source data (if compressing a string, it can be strlen(source)+1)
 * @param dest Where to store compressed data
 * @param destination_size Max. size of compressed data
 * @param level Compession level
 *
 * @return If <0, error, Z_MEM_ERROR if could not allocate memory.
 *                       Z_VERSION_ERROR if version of zlib.h and linked library
 *                       Z_STREAM_ERROR if invalid compression level supplied.
 *                       ERR_UNDERSIZED if dest is not big enough to store all data
 *                       ERR_DEFLATE_PARTIAL if there was a problem running deflate
 *                                           and it was not fully deflated
 *                       ERR_DEFLATE_PARTIAL_STREAM there was a problem and the compressed
 *                                                  stream does not ends right.
 *         If >0, size of compressed data
 */

int dodeflate(char* source, size_t source_size, char* dest, size_t destination_size, int level)
{
  int ret, flush;
  size_t have;
  z_stream strm;
  unsigned char *in = source;
  unsigned char *out = dest;
  size_t original_dest_size = destination_size;

  /* Initialize deflate */
  strm.zalloc = Z_NULL;
  strm.zfree = Z_NULL;
  strm.opaque = Z_NULL;
  ret = deflateInit(&strm, level);
  if (ret != Z_OK)
    return ret;

  /* compress !! */
  do
    {
      if (source_size>CHUNK)
        {
          strm.avail_in = CHUNK;
          source_size-=CHUNK;
        }
      else
        {
          strm.avail_in = source_size;
          source_size = 0;
        }
      flush = (source_size == 0) ? Z_FINISH : Z_NO_FLUSH;
      strm.next_in = in;

      /* run deflate() on input until output buffer not full, finish
     compression if all of source has been read in */

      do
    {
      strm.avail_out = CHUNK;
      strm.next_out = out;
      if (destination_size < CHUNK)
        return ERR_UNDERSIZED;         /* Not enough size */

      ret = deflate(&strm, flush);    /* no bad return value */
      if (ret == Z_STREAM_ERROR)      /* error check */
        return ret;

      have = CHUNK - strm.avail_out;
      out+=have;          /* Move out pointer */
      destination_size-=have; /* calculate destination size left */
        } while (strm.avail_out == 0);

      if (strm.avail_in != 0)
    return ERR_DEFLATE_PARTIAL;

      in+=CHUNK;       /* Move in to the next chunk */
      /* done when last data in file processed */
    } while (flush != Z_FINISH);

  if (ret != Z_STREAM_END)
    return ERR_DEFLATE_PARTIAL_STREAM;

  /* clean up and return */
  (void)deflateEnd(&strm);
  return original_dest_size-destination_size;
}

/** ***********************************
 * Uncompress source data from memory to memory.
 *
 * @param source Source data (compressed data)
 * @param source_size Size of source data
 * @param dest Where to store uncompressed data
 * @param destination_size Max. size of compressed data
 *
 * @return If <0, error, Z_DATA_ERROR if deflated data is invalid or incomplete
 *                       Z_VERSION_ERROR if version of zlib.h and linked library
 *                       Z_STREAM_ERROR if there was a problem deflating.
 *                       Z_MEM_ERROR problem allocating memory
 *                       ERR_UNDERSIZED if dest is not big enough to store all data
 *         If >0, size of uncompressed data
 */

int doinflate(char* source, size_t source_size, char* dest, size_t destination_size)
{
    int ret;
    size_t have;
    z_stream strm;
    unsigned char* in = source;
    unsigned char* out = dest;
    size_t original_dest_size = destination_size;

    /* initialize z_stream */
    strm.zalloc = Z_NULL;
    strm.zfree = Z_NULL;
    strm.opaque = Z_NULL;
    strm.avail_in = 0;
    strm.next_in = Z_NULL;
    ret = inflateInit(&strm);
    if (ret != Z_OK)
        return ret;

    /* decompress until source is completelly read */
    do
      {
    if (source_size>CHUNK)
      {
        strm.avail_in = CHUNK;
        source_size-=CHUNK;
      }
    else
      {
        strm.avail_in = source_size;
        source_size = 0;
      }

    strm.next_in = in;

        /* run inflate() on input until output buffer  */
        do
      {
        if (destination_size<CHUNK)
          return ERR_UNDERSIZED;

            strm.avail_out = CHUNK;
            strm.next_out = out;

        /* inflate data */
            ret = inflate(&strm, Z_NO_FLUSH);

            switch (ret)
          {
          case Z_NEED_DICT:
        ret = Z_DATA_ERROR;
          case Z_DATA_ERROR:
          case Z_MEM_ERROR:
        (void)inflateEnd(&strm);
          case Z_STREAM_ERROR:
        return ret;
          }
            have = CHUNK - strm.avail_out;
        out+=have;      /* Move out pointer */
        destination_size-=have;
      } while (strm.avail_out == 0);
    in+=CHUNK;

    /* done when inflate() says it's done or we have no more input data */
      } while ( (ret != Z_STREAM_END) && (source_size != 0) );

    /* clean up and return */
    (void)inflateEnd(&strm);
    return (ret == Z_STREAM_END) ? original_dest_size-destination_size : Z_DATA_ERROR;
}

int main(int argc, char **argv)
{
    int ret;
    // Song Coffee by Josh Woodward (http://www.joshwoodward.com/song/coffee)
    // Just to put something different to lorem ipsum. You can listen to the
    // song, download and use it.
    char *text = "A cup of coffee in the morning and I get the paper\n"
      "I check the headlines and decide that I am bored\n"
      "I check my email and decide to answer later\n"
      "Another cup of coffee and I drag myself to work\n"
      "\n"
      "     My life is grounded in a firm routine\n"
      "     Of coffee sleep and work\n"
      "     I am not boring, I just stick to what I know\n"
      "\n"
      "I'm sitting there at work and I realized I forgot to  wake up\n"
      "Can't be productive when I'm dreaming 'bout a  sheep\n"
      "I go upstairs and get myself another cup of coffee\n"
      "I get downstairs and then I spill it on the floor\n"
      "\n"
      "     My life is grounded in a firm routine\n"
      "     Of coffee sleep and work\n"
      "     I am not boring, I just stick to what I know\n"
      "\n"
      "(solo)\n"
      "\n"
      "Rockabye baby, on the tree top\n"
      "Lunch hour's over, and I can't stay up\n"
      "I wanna drink coffee, but that's a mistake\n"
      "I best switch to decaf or I'll stay awake\n"
      "\n"
      "     My life is grounded in a firm routine\n"
      "     Of coffee sleep and work\n"
      "     I am not boring, I just stick to what I know";
    char dest [CHUNK * 5];  /* Test size */
    char orig [CHUNK * 10];
    unsigned siz;
    siz = dodeflate(text, strlen(text)+1, dest, CHUNK*5, Z_BEST_COMPRESSION);
    fprintf (stderr, "ORIGINAL SIZE: %zu\n", strlen(text));
    fprintf (stderr, "SIZE: %d\n", siz);
    /* Do we really want to show this, I don't think you want to write this on
       screen but you can uncomment the following line and run the program as follows:
         $ ./zstrings | hexdump -C
       It's more beautiful to read data this way
    */

    /* write(1, dest, siz);  */
    fprintf (stderr, "INFLATED SIZE: %d\nSTRING: %s\n", doinflate(dest, siz, orig, CHUNK*10), orig);

    return 0;
}

Bueno, el código es muy parecido al ejemplo, con alguna modificación y si compilamos, debe funcionar del tirón.
Tanto compresión como descompresión van por trozos (chunks), en este caso su tamaño viene dado por una constante (CHUNK) que nos da el tamaño en bytes de cada trozo. Cuando estemos comprimiendo, leeremos bloques de ese tamaño y los comprimiremos (deben ocupar menos, pero como mucho consideramos que ocuparán también CHUNK bytes). Y aunque normalmente en una llamada a deflate() podremos tener los datos comprimidos, está en un bucle por si hay muchos datos de entrada y necesitamos dar alguna pasada más.

Con la descompresión pasa algo parecido, cada CHUNK que leamos puede resultar en más de un CHUNK de salida.

Tanto en un caso como en otro, en lugar de leer de streams (archivos, por ejemplo), lo que hacemos es mover la posición de un puntero, en este caso, gastaremos más memoria si queremos comprimir o descomprimir algo muy grande, pero iremos muy rápido para cosas pequeñas al no necesitar archivos.

Ahora bien, en el ejemplo, el tamaño de la entrada es strlen(texto)+1, ¿por qué? Es para comprimir el texto también con el carácter terminador, es decir para que el \0 último de la cadena también entre en nuestra cadena comprimida, y así nosotros sabremos dónde parar.

Método corto

Venga, podemos hacerlo con menos líneas, y es que zlib trae un par de funciones que nos ayudan a nuestro propósito (luego diré a qué viene el método largo).
Por cierto el texto aquí es mucho más corto, para no sufrir tanto leyendo.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdio.h>
#include <string.h>
#include "zlib.h"
#include <assert.h>

int main(int argc, char **argv)
{
    int ret;
    // Song Coffee by Josh Woodward (http://www.joshwoodward.com/song/coffee)
    // Just to put something different to lorem ipsum. You can listen to the
    // song, download and use it.
    char *text = "A cup of coffee in the morning and I get the paper\n"
      "     I am not boring, I just stick to what I know";
    char dest [CHUNK * 5];  /* Test size */
    char orig [CHUNK * 10];
    unsigned long siz=CHUNK*5;
    unsigned long origsize= CHUNK*10;
    assert (Z_OK == compress2(dest, &siz, text, strlen(text)+1, Z_BEST_COMPRESSION));
    fprintf (stderr, "ORIGINAL SIZE: %zu\n", strlen(text));
    fprintf (stderr, "SIZE: %ld\n", siz);
    /* Do we really want to show this, I don't think you want to write this on
       screen but you can uncomment the following line and run the program as follows:
         $ ./zstrings | hexdump -C
       It's more beautiful to read data this way
    */

    /* write(1, dest, siz);  */
    assert( Z_OK == uncompress(orig, &origsize, dest, siz));
    fprintf (stderr, "INFLATED SIZE: %ld\nSTRING: %s\n", origsize, orig);

    return 0;
}

Como veis compress() y uncompress() nos valen para lo que queremos, con algunas diferencias con respecto a los métodos de arriba. compress2() nos permite indicar nivel de compresión.
En este caso, el orden de los argumentos varía, ahora ponemos primero destino y tamaño del destino, luego origen y tamaño del origen por referencia. Por otro lado, el tamaño del destino va por referencia, con el fin de que pueda ser modificado por la función y finalmente devuelva el tamaño exacto del destino (recordemos que de primeras, le tenemos que decir el tamaño máximo que tenemos reservado para la información comprimida).

¿Y para qué me vale el primero?

Está claro que si queremos comprimir o descomprimir, y ya, con el segundo método vale. Pero en el caso de que queramos comprimir o descomprimir a medida que van llegando datos por red, por ejemplo, o a medida que vayamos generando dicha información sí que necesitaremos el primer método.

Y como idea, podíamos comprimir/descomprimir en multihilo y esto puede estar muy chulo, ya que tenemos un bucle y tenemos que repetir una tarea muchas veces, y como sabemos en qué punto de la cadena original tenemos que leer cada vez podíamos hacer que cada thread comprimiera un trozo.

A la hora de comprimir necesitaríamos que alguien se encargara de junta los trozos ya que, de primeras no podríamos saber cuánto ocuparía un trozo comprimido. Para descomprimir pasaría algo parecido, no sabemos cuánto ocupa un CHUNK descomprimido y necesitaríamos juntar los trozos.

Tendríamos que mirar si de verdad nos compensa repartir threads-que trabajen los threads-juntar los trozos tanto en tiempo como en memoria y deberíamos complicar un poco el código para controlar el lanzamiento de threads (por ejemplo, que no haya más de 4 trabajando a la vez, dependiendo de los cores de nuestro ordenador, ya que como las tareas tienen una carga de CPU intensa no hay muchos tiempos muertos).

Foto: Masha Danilova (Unsplash)

También podría interesarte....

Leave a Reply