zlog: Ficheros comprimidos de log de SICO
zlog es un formato de ficheros de log binarios (comprimidos) propio de SICO.Características:
- Generalmente obtiene ratios de compresión entre 60% y 90% (los ficheros quedan a un 60%-90% del tamaño original)
- Se comprimen las líneas de forma independiente
- Es capaz de descomprimir un extracto de un fichero (solo mostrará las líneas completas que había en ese extracto, el extracto puede contener basura al principio o al final)
- Permite buscar líneas desde el final del fichero (navegación "hacia atrás").
- El tamaño de bloque máximo es de 255 bytes (que en el peor de los casos queda como 255+5=260 bytes, ya que el algoritmo tiene una cabecera/pie de 5 bytes en total).
Algoritmo:
Packing format:
| 1 byte | segmentsdatasize (n+m+k) |
| 1 byte | segment1 unpacked len (seg1size) |
| 1 byte | segment2 unpacked len (seg2size) |
| 1 byte | segment3 unpacked len (seg3size) |
| n bytes | segment1data, unpack until seg1size unpacked in buffer |
| m bytes | segment2data, unpack until added seg2size unpacked in buffer |
| k bytes | segment3data, unpack until added seg2size unpacked in buffer |
| 1 byte | segmentsdatasize (n+m+k), it is repeated to be able to "rewind" lines |
How to unpack segment1data:
- For each nibble (first high nibble, then low nibble):
| 0-13 | represent the corresponding character in "0123456789/ :" |
| 14 and 15 | requires two nibbles to decode |
| 14:0-12 | the second number is repetitions-3 of previous character |
| 14:13-15 | the strings "Mon ","Tue ","Wed " |
| 15:0-15 | the strings "Thu ","Fri ","Sat ","Sun ","Jan ","Feb ","Mar ","Apr ","May ","Jun ","Jul ","Aug ","Sep ","Oct ","Nov ","Dec " |
How to unpack segment2data:
- Each tuple of 3 bytes is expanded to a tuple of 4 bytes:
aaaaaabb bbbbcccc ccdddddd -> 00aaaaaa 00bbbbbb 00cccccc 00dddddd
- Each expanded byte is decoded as follows:
| 0-62 | represents the corresponding character in " 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ" |
| 63 | the following two expanded bytes are encoded as "count-1""data" as in: 00ccccdd 00dddddd |
How to unpack segment3data:
- Each byte has its nibbles swapped.
Rationale:
Las líneas de los ficheros de log suelen tener dos partes bien diferenciadas: el timestamp de la línea y el contenido de la línea.
El algoritmo se aprovecha de que el timestamp usa un número muy restringido de carácteres; específicamente se usan "0123456789/ :" y las cadenas de los días y los meses en inglés ("Mon ", "Tue ", ... , "Sun " por un lado y "Jan ", "Feb ", ... , "Dec " por otro). Lo que hace es codificar esto un un solo nibble (dos para las cadenas), reduciendo de forma efectiva el tamaño a la mitad. Como sobran unos cuantos índices para cadenas, se usan esos índices para, en vez de representar cadenas, decir que se repite n veces adicionales el último carácter codificado.
El algoritmo asume que se ha terminado el timestamp de la línea en cuanto encuentra el primer carácter que no puede codificar siguiendo el algoritmo anterior.
En cuanto al contenido de la línea, normalmente son carácteres numéricos o alfabéticos. Con un poco de cuidado, estos carácteres se pueden codificar en 6 bits en vez de 8, y no queda un codepoint libre para usarlo como "escape" (que permiten codificar el resto de los carácteres usando más bits). Esto hace que para codificar 4 carácteres usemos sólo 3 bytes (4 caracteres 6 bits = 24 bits; 24 bits son 3 bytes).
Los carácteres que se han escogido para codificar como 6 bits en el contenido de la línea son:
" 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
Como cuando se pone un carácter de escape, hay que usar dos huecos de 6 bits para poder especificar el carácter de 8 bits, los 62-8=12-8=4 bits que nos sobran se usan para especificar un contador (el número de veces adicionales que se ha de poner ese carácter; si el contador es 0, es que sólo hay que poner el carácter 1 vez, si es 1, se pone 2 veces, etc.).
Como manera de saber cuántos carácteres hay que codificar de esta manera, mientras se va codificando se va apuntando cuál es la longitud óptima (primero es 0 codificados+todos en "raw" -- el "raw" es el segmento 3 de la descripción de arriba), y si la longitud de codificación actual (número de caracteres codificados finales + número de raw sin codificar) es mejor que la que se ha apuntado como óptima hasta el momento, se cambia la óptima para que sea la actual.
Por último, los carácteres "raw" son una serie de carácteres al final de la línea que se dejan sin codificar. Normalmente suele ser el \n final (que requiere escape y es más "barato" el ponerlo como raw) y algunos carácteres que saldría más caro poner hacer una tupla incompleta del segmento 2 con respecto a dejarlos como raw.
Sobre las cabeceras:
La cabecera cumple tres funciones
1. Reconocer "a priori" si esto parece una línea codificada con este algoritmo
2. Poder "saltar líneas" (hacia adelante y hacia atrás)
3. Saber cuántos carácteres hay en cada segmento de codificación
Básicamente se necesita
- saber la longitud de una línea codificada
- algo de redundancia
- saber la longitud comprimida o descomprimida de cada uno de los segmentos
Para saber la longitud de una línea codificada, se usa un número que dice el número de bytes usados en la parte de codificación. Como el peor de los casos es que toda la línea esté en el segmento 3 ("raw"), podemos limitar esto a un simple char forzando que el tamaño de bloque máximo sean 255 bytes.
Para obtener redundancia, se repite este número al final del bloque
Y para saber el número de caracteres a usar en cada tipo de codificación, se ponen tres números (otra vez de tipo char) que indican el número de carácteres después de codificar que ocupa la línea. Así cumplimos dos objetivos adicionales:
1. Podemos saber cuál era la longitud original de la línea simplemente mirando la cabecera
2. Evitamos las complicaciones que tendríamos si usáramos el número de bytes sin codificar, ya que los dos primeros segmentos necesitarían poder expresar fracciones, y seguramente necesitaríamos más bits para poder expresar el tamaño máximo de ese segmento.
Con todo esto, el formato del fichero queda:
| l | 1 byte | tamaño de los datos comprimidos en bytes |
| seg1origsize | 1 byte | tamaño del primer segmento (nibbles) descomprimido |
| seg2origsize | 1 byte | tamaño del segundo segmento (4 en 3) descomprimido |
| seg3origsize | 1 bytes | tamaño del tercer segmento (raw) descomprimido |
| seg1data | seg1size bytes | datos comprimidos en segmento 1 (nibbles) |
| seg2data | seg2size bytes | datos comprimidos en segmento 2 (4 en 3) |
| seg3data | seg3size bytes | datos en segmento 3 (raw) |
| l | 1 byte | tamaño de los datos comprimidos en bytes |
Y se cumple lo siguiente:
l=seg1size+seg2size+seg3size
seg1origsize+seg2origsize+seg3origsize=tamaño de la línea original
Y se comprueba que el código a priori es correcto con (suponiendo que la línea está en un buffer llamado inbuf, ocupados al menos inbufsize):
- Que cabe toda la línea en el búffer:
inbufsize>=(1+3+l+1)
- Que existe la repetición del tamaño
inbuf[0]==inbuf[1+3+l]
- Que el tamaño descomprimido total es menos que el máximo de 255
(((int)inbuf[1])+inbuf[2]+inbuf[3])=255
Así pues se hace bastante "barato" el comprobar que es un bloque válido a priori. Hace posible el buscar el inicio de la línea para empezar a descomprimir de manera eficiente, ignorando la basurilla inicial. Es initeresante ya que permite extractar el final de un fichero para mandarlo por correo, u obtener las líneas áun válidas de un fichero corrupto -- la parte corrupta sólo haría que no se pudiera leer la línea en la que está la corrupción, pero se leerían correctamente tanto las anteriores como las posteriores.
Attachs (implementación inicial del zlog):
zlog.h
zlog.c
unzlog.c
Makefile
unzlog.c
zlog.h+