aboutsummaryrefslogtreecommitdiff
path: root/doc/liblzma-advanced.txt
diff options
context:
space:
mode:
authorLasse Collin <lasse.collin@tukaani.org>2007-12-09 00:42:33 +0200
committerLasse Collin <lasse.collin@tukaani.org>2007-12-09 00:42:33 +0200
commit5d018dc03549c1ee4958364712fb0c94e1bf2741 (patch)
tree1b211911fb33fddb3f04b77f99e81df23623ffc4 /doc/liblzma-advanced.txt
downloadxz-5d018dc03549c1ee4958364712fb0c94e1bf2741.tar.xz
Imported to git.
Diffstat (limited to 'doc/liblzma-advanced.txt')
-rw-r--r--doc/liblzma-advanced.txt324
1 files changed, 324 insertions, 0 deletions
diff --git a/doc/liblzma-advanced.txt b/doc/liblzma-advanced.txt
new file mode 100644
index 00000000..d829a33a
--- /dev/null
+++ b/doc/liblzma-advanced.txt
@@ -0,0 +1,324 @@
+
+Advanced features of liblzma
+----------------------------
+
+0. Introduction
+
+ Most developers need only the basic features of liblzma. These
+ features allow single-threaded encoding and decoding of .lzma files
+ in streamed mode.
+
+ In some cases developers want more. The .lzma file format is
+ designed to allow multi-threaded encoding and decoding and limited
+ random-access reading. These features are possible in non-streamed
+ mode and limitedly also in streamed mode.
+
+ To take advange of these features, the application needs a custom
+ .lzma file format handler. liblzma provides a set of tools to ease
+ this task, but it's still quite a bit of work to get a good custom
+ .lzma handler done.
+
+
+1. Where to begin
+
+ Start by reading the .lzma file format specification. Understanding
+ the basics of the .lzma file structure is required to implement a
+ custom .lzma file handler and to understand the rest of this document.
+
+
+2. The basic components
+
+2.1. Stream Header and tail
+
+ Stream Header begins the .lzma Stream and Stream tail ends it. Stream
+ Header is defined in the file format specification, but Stream tail
+ isn't (thus I write "tail" with a lower-case letter). Stream tail is
+ simply the Stream Flags and the Footer Magic Bytes fields together.
+ It was done this way in liblzma, because the Block coders take care
+ of the rest of the stuff in the Stream Footer.
+
+ For now, the size of Stream Header is fixed to 11 bytes. The header
+ <lzma/stream_flags.h> defines LZMA_STREAM_HEADER_SIZE, which you
+ should use instead of a hardcoded number. Similarly, Stream tail
+ is fixed to 3 bytes, and there is a constant LZMA_STREAM_TAIL_SIZE.
+
+ It is possible, that a future version of the .lzma format will have
+ variable-sized Stream Header and tail. As of writing, this seems so
+ unlikely though, that it was considered simplest to just use a
+ constant instead of providing a functions to get and store the sizes
+ of the Stream Header and tail.
+
+
+2.x. Stream tail
+
+ For now, the size of Stream tail is fixed to 3 bytes. The header
+ <lzma/stream_flags.h> defines LZMA_STREAM_TAIL_SIZE, which you
+ should use instead of a hardcoded number.
+
+
+3. Keeping track of size information
+
+ The lzma_info_* functions found from <lzma/info.h> should ease the
+ task of keeping track of sizes of the Blocks and also the Stream
+ as a whole. Using these functions is strongly recommended, because
+ there are surprisingly many situations where an error can occur,
+ and these functions check for possible errors every time some new
+ information becomes available.
+
+ If you find lzma_info_* functions lacking something that you would
+ find useful, please contact the author.
+
+
+3.1. Start offset of the Stream
+
+ If you are storing the .lzma Stream inside anothe file format, or
+ for some other reason are placing the .lzma Stream to somewhere
+ else than to the beginning of the file, you should tell the starting
+ offset of the Stream using lzma_info_start_offset_set().
+
+ The start offset of the Stream is used for two distinct purporses.
+ First, knowing the start offset of the Stream allows
+ lzma_info_alignment_get() to correctly calculate the alignment of
+ every Block. This information is given to the Block encoder, which
+ will calculate the size of Header Padding so that Compressed Data
+ is alignment at an optimal offset.
+
+ Another use for start offset of the Stream is in random-access
+ reading. If you set the start offset of the Stream, lzma_info_locate()
+ will be able to calculate the offset relative to the beginning of the
+ file containing the Stream (instead of offset relative to the
+ beginning of the Stream).
+
+
+3.2. Size of Stream Header
+
+ While the size of Stream Header is constant (11 bytes) in the current
+ version of the .lzma file format, this may change in future.
+
+
+3.3. Size of Header Metadata Block
+
+ This information is needed when doing random-access reading, and
+ to verify the value of this field stored in Footer Metadata Block.
+
+
+3.4. Total Size of the Data Blocks
+
+
+3.5. Uncompressed Size of Data Blocks
+
+
+3.6. Index
+
+
+
+
+x. Alignment
+
+ There are a few slightly different types of alignment issues when
+ working with .lzma files.
+
+ The .lzma format doesn't strictly require any kind of alignment.
+ However, if the encoder carefully optimizes the alignment in all
+ situations, it can improve compression ratio, speed of the encoder
+ and decoder, and slightly help if the files get damaged and need
+ recovery.
+
+ Alignment has the most significant effect compression ratio FIXME
+
+
+x.1. Compression ratio
+
+ Some filters take advantage of the alignment of the input data.
+ To get the best compression ratio, make sure that you feed these
+ filters correctly aligned data.
+
+ Some filters (e.g. LZMA) don't necessarily mind too much if the
+ input doesn't match the preferred alignment. With these filters
+ the penalty in compression ratio depends on the specific type of
+ data being compressed.
+
+ Other filters (e.g. PowerPC executable filter) won't work at all
+ with data that is improperly aligned. While the data can still
+ be de-filtered back to its original form, the benefit of the
+ filtering (better compression ratio) is completely lost, because
+ these filters expect certain patterns at properly aligned offsets.
+ The compression ratio may even worse with incorrectly aligned input
+ than without the filter.
+
+
+x.1.1. Inter-filter alignment
+
+ When there are multiple filters chained, checking the alignment can
+ be useful not only with the input of the first filter and output of
+ the last filter, but also between the filters.
+
+ Inter-filter alignment important especially with the Subblock filter.
+
+
+x.1.2. Further compression with external tools
+
+ This is relatively rare situation in practice, but still worth
+ understanding.
+
+ Let's say that there are several SPARC executables, which are each
+ filtered to separate .lzma files using only the SPARC filter. If
+ Uncompressed Size is written to the Block Header, the size of Block
+ Header may vary between the .lzma files. If no Padding is used in
+ the Block Header to correct the alignment, the starting offset of
+ the Compressed Data field will be differently aligned in different
+ .lzma files.
+
+ All these .lzma files are archived into a single .tar archive. Due
+ to nature of the .tar format, every file is aligned inside the
+ archive to an offset that is a multiple of 512 bytes.
+
+ The .tar archive is compressed into a new .lzma file using the LZMA
+ filter with options, that prefer input alignment of four bytes. Now
+ if the independent .lzma files don't have the same alignment of
+ the Compressed Data fields, the LZMA filter will be unable to take
+ advantage of the input alignment between the files in the .tar
+ archive, which reduces compression ratio.
+
+ Thus, even if you have only single Block per file, it can be good for
+ compression ratio to align the Compressed Data to optimal offset.
+
+
+x.2. Speed
+
+ Most modern computers are faster when multi-byte data is located
+ at aligned offsets in RAM. Proper alignment of the Compressed Data
+ fields can slightly increase the speed of some filters.
+
+
+x.3. Recovery
+
+ Aligning every Block Header to start at an offset with big enough
+ alignment may ease or at least speed up recovery of broken files.
+
+
+y. Typical usage cases
+
+y.x. Parsing the Stream backwards
+
+ You may need to parse the Stream backwards if you need to get
+ information such as the sizes of the Stream, Index, or Extra.
+ The basic procedure to do this follows.
+
+ Locate the end of the Stream. If the Stream is stored as is in a
+ standalone .lzma file, simply seek to the end of the file and start
+ reading backwards using appropriate buffer size. The file format
+ specification allows arbitrary amount of Footer Padding (zero or more
+ NUL bytes), which you skip before trying to decode the Stream tail.
+
+ Once you have located the end of the Stream (a non-NULL byte), make
+ sure you have at least the last LZMA_STREAM_TAIL_SIZE bytes of the
+ Stream in a buffer. If there isn't enough bytes left from the file,
+ the file is too small to contain a valid Stream. Decode the Stream
+ tail using lzma_stream_tail_decoder(). Store the offset of the first
+ byte of the Stream tail; you will need it later.
+
+ You may now want to do some internal verifications e.g. if the Check
+ type is supported by the liblzma build you are using.
+
+ Decode the Backward Size field with lzma_vli_reverse_decode(). The
+ field is at maximum of LZMA_VLI_BYTES_MAX bytes long. Check that
+ Backward Size is not zero. Store the offset of the first byte of
+ the Backward Size; you will need it later.
+
+ Now you know the Total Size of the last Block of the Stream. It's the
+ value of Backward Size plus the size of the Backward Size field. Note
+ that you cannot use lzma_vli_size() to calculate the size since there
+ might be padding; you need to use the real observed size of the
+ Backward Size field.
+
+ At this point, the operation continues differently for Single-Block
+ and Multi-Block Streams.
+
+
+y.x.1. Single-Block Stream
+
+ There might be Uncompressed Size field present in the Stream Footer.
+ You cannot know it for sure unless you have already parsed the Block
+ Header earlier. For security reasons, you probably want to try to
+ decode the Uncompressed Size field, but you must not indicate any
+ error if decoding fails. Later you can give the decoded Uncompressed
+ Size to Block decoder if Uncopmressed Size isn't otherwise known;
+ this prevents it from producing too much output in case of (possibly
+ intentionally) corrupt file.
+
+ Calculate the the start offset of the Stream:
+
+ backward_offset - backward_size - LZMA_STREAM_HEADER_SIZE
+
+ backward_offset is the offset of the first byte of the Backward Size
+ field. Remember to check for integer overflows, which can occur with
+ invalid input files.
+
+ Seek to the beginning of the Stream. Decode the Stream Header using
+ lzma_stream_header_decoder(). Verify that the decoded Stream Flags
+ match the values found from Stream tail. You can use the
+ lzma_stream_flags_is_equal() macro for this.
+
+ Decode the Block Header. Verify that it isn't a Metadata Block, since
+ Single-Block Streams cannot have Metadata. If Uncompressed Size is
+ present in the Block Header, the value you tried to decode from the
+ Stream Footer must be ignored, since Uncompressed Size wasn't actually
+ present there. If Block Header doesn't have Uncompressed Size, and
+ decoding the Uncompressed Size field from the Stream Footer failed,
+ the file is corrupt.
+
+ If you were only looking for the Uncompressed Size of the Stream,
+ you now got that information, and you can stop processing the Stream.
+
+ To decode the Block, the same instructions apply as described in
+ FIXME. However, because you have some extra known information decoded
+ from the Stream Footer, you should give this information to the Block
+ decoder so that it can verify it while decoding:
+ - If Uncompressed Size is not present in the Block Header, set
+ lzma_options_block.uncompressed_size to the value you decoded
+ from the Stream Footer.
+ - Always set lzma_options_block.total_size to backward_size +
+ size_of_backward_size (you calculated this sum earlier already).
+
+
+y.x.2. Multi-Block Stream
+
+ Calculate the start offset of the Footer Metadata Block:
+
+ backward_offset - backward_size
+
+ backward_offset is the offset of the first byte of the Backward Size
+ field. Remember to check for integer overflows, which can occur with
+ broken input files.
+
+ Decode the Block Header. Verify that it is a Metadata Block. Set
+ lzma_options_block.total_size to backward_size + size_of_backward_size
+ (you calculated this sum earlier already). Then decode the Footer
+ Metadata Block.
+
+ Store the decoded Footer Metadata to lzma_info structure using
+ lzma_info_set_metadata(). Set also the offset of the Backward Size
+ field using lzma_info_size_set(). Then you can get the start offset
+ of the Stream using lzma_info_size_get(). Note that any of these steps
+ may fail so don't omit error checking.
+
+ Seek to the beginning of the Stream. Decode the Stream Header using
+ lzma_stream_header_decoder(). Verify that the decoded Stream Flags
+ match the values found from Stream tail. You can use the
+ lzma_stream_flags_is_equal() macro for this.
+
+ If you were only looking for the Uncompressed Size of the Stream,
+ it's possible that you already have it now. If Uncompressed Size (or
+ whatever information you were looking for) isn't available yet,
+ continue by decoding also the Header Metadata Block. (If some
+ information is missing, the Header Metadata Block has to be present.)
+
+ Decoding the Data Blocks goes the same way as described in FIXME.
+
+
+y.x.3. Variations
+
+ If you know the offset of the beginning of the Stream, you may want
+ to parse the Stream Header before parsing the Stream tail.
+