[libtcas] The Compression of pos_and_color of Compressed Chunks using zlib

milkyjing

TCAS files are commonly too big, which cuts its value of practical use. So, I have to think of some way to reduce its size. One compression library comes into my mind immediately, it's zlib. Here I'm not going to list the advantages of zlib, it's not the point. I'll focus on how to make it possible to use zlib for compressing TCAS file.

We only need to consider the compressed TCAS files, for we can compress the raw TCAS files into compressed ones.


Conceptual Guides

1. Recall the procedure of parsing a compressed TCAS file
    a) first, we have to generate the index
    b) then, linearize the index to linearized index streams
    c) so can we start to render the TCAS frames
2. So, the most important thing is to remain a way of generating the index. And to generate a index, we need
    a) start and end time of the chunks
    b) count_layer_type_pair unit of the chunks
    c) the offset of a chunk is derived from the count of pos_and_color of the chunk
3. The building of index should come before the decompression, because we want to decompress at run-time to save memory as well as the overall performance.
4. Thus, only pos_and_color of a chunk can be compressed, fortunately, it is usually worth compressing
    a) a PIX (or several PIXs) in TCAX is usually corresponding to a chunk in TCAS, so, generally speaking, the size of a chunk is likely to be above 10KB (40 * 40 * 8), and by experiment zlib can compress such data into about its half size.
    b) even for a minimal pos_and_color, 8 bytes, the result is still tolerable, 16 bytes
    c) so, optimistically speaking, we can reduce the size of a TCAS file by half!


Implementation Tips

1. Again, recall the procedure of generating the index of a TCAS file. We have to know every size of chunk, only so can we positioning them correctly. In the past, we can derive the size by the following formula: size = sizeof(tcas_unit) + sizeof(tcas_unit) + sizeof(tcas_unit) + count * 2 * pos_and_color, for the size of pos_and_color can be derived correctly through count. But if we were to compress the pos_and_color, we can not derive the size of the compressed pos_and_color directly, so, we have to occupy another tcas_unit to record the size of the compressed pos_and_color.
2. The layout of a chunk in the new design will be: startTime endTime CLTP SIZE compressed_pos_and_color
3. And we also need a new set of API to support such change, while the old API stay unchanged to maintain the compatibility.
4. hla_z_comp.c and hla_z_comp.h
5. Two major API
    a) libtcas_create_ordered_index_z, to create the ordered index from the z compressed file
    b) libtcas_read_specified_chunk_z, to read the specified compressed chunk whose pos_and_color was compressed by zlib, and decompress the compressed pos_and_color to normal one
    c) libtcas_compress_chunks_z, to compress the stream of compressed chunks generated by libtcas_compress_raw_chunks
6. a new TCAS type is added, TCAS_FILE_TYPE_COMPRESSED_Z
7. the size of z_pos_and_color should be padded to the multiple of 4 bytes (a tcas_unit), for compatibility issue of creating ordered index.