tvg_format: newly introduced for tvg data compression.
authorHermet Park <chuneon.park@samsung.com>
Thu, 19 Aug 2021 09:37:51 +0000 (18:37 +0900)
committerJunsuChoi <jsuya.choi@samsung.com>
Fri, 27 Aug 2021 05:10:25 +0000 (14:10 +0900)
commit967d8b9a972e8f57350aab6aca9787f8282f497d
tree7548fe4451ddaa35f69fa13b1017a0337c974e0c
parent3f7bd8847ce77180a9e3e7b0c171049a47cf2269
tvg_format: newly introduced for tvg data compression.

By choosing compress option, tvg tries to compress the data to reduce the binary size.
Since the compression has the double-edges sword, we provides an option to users
to select it by their demand. Basically, compression is better than non-compression.

After profiling, we decided to use the encoder/decoder of Guilherme R. Lampert's.

Here is the profiling result:

test.tvg: 296037 -> 243411 (-17%)
tiger.tvg: 54568 -> 50622 (-7%)
image-embedded.tvg: 2282 -> 1231 (-46%)

@Issue: https://github.com/Samsung/thorvg/issues/639

About compression method:

Lempel–Ziv–Welch (LZW) encoder/decoder by Guilherme R. Lampert

This is the compression scheme used by the GIF image format and the Unix 'compress' tool.
Main differences from this implementation is that End Of Input (EOI) and Clear Codes (CC)
are not stored in the output and the max code length in bits is 12, vs 16 in compress.

EOI is simply detected by the end of the data stream, while CC happens if the
dictionary gets filled. Data is written/read from bit streams, which handle
byte-alignment for us in a transparent way.

The decoder relies on the hardcoded data layout produced by the encoder, since
no additional reconstruction data is added to the output, so they must match.
The nice thing about LZW is that we can reconstruct the dictionary directly from
the stream of codes generated by the encoder, so this avoids storing additional
headers in the bit stream.

The output code length is variable. It starts with the minimum number of bits
required to store the base byte-sized dictionary and automatically increases
as the dictionary gets larger (it starts at 9-bits and grows to 10-bits when
code 512 is added, then 11-bits when 1024 is added, and so on). If the dictionary
is filled (4096 items for a 12-bits dictionary), the whole thing is cleared and
the process starts over. This is the main reason why the encoder and the decoder
must match perfectly, since the lengths of the codes will not be specified with
the data itself.
13 files changed:
inc/thorvg.h
src/examples/images/test.tvg
src/lib/meson.build
src/lib/tvgBinaryDesc.h
src/lib/tvgLzw.cpp [new file with mode: 0644]
src/lib/tvgLzw.h [new file with mode: 0644]
src/lib/tvgSaveModule.h
src/lib/tvgSaver.cpp
src/loaders/tvg/tvgTvgBinInterpreter.cpp
src/loaders/tvg/tvgTvgLoader.cpp
src/loaders/tvg/tvgTvgLoader.h
src/savers/tvg/tvgTvgSaver.cpp
src/savers/tvg/tvgTvgSaver.h