# Puffin: A deterministic deflate re-compressor (for patching purposes)
## Table of Contents
[TOC]
## Puffin
Puffin is a deterministic deflate recompressor. It is mainly used for patching
deflate compressed images (zip, gzip, etc.) because patches created from deflate
files/streams are usually large (deflate has a bit-aligned format, hence,
changing one byte in the raw data can cause the entire deflate stream to change
drastically.)
Puffin has two tools (operations): `puffdiff` and `puffpatch` (shown
[here](puffin).) The purpose of `puffdiff` operation is to create a patch
between a source and a target file with one or both of them having some deflate
streams. This patch is used in the `puffpatch` operation to generate the target
file from the source file deterministically. The patch itself is created by
`bsdiff` library (but can be replaced by any other diffing mechanism). But,
before it uses `bsdiff` to create the patch, we have to transform both the
source and target files into a specific format so `bsdiff` can produce smaller
patches. We define `puff` operation to perform such a transformation. The
resulting stream is called a `puff` stream. The reverse transformation (from
`puff` stream to deflate stream) is called a `huff` operation. `huff` is used in
the client to transform the `puff` stream back into its original deflate stream
deterministically.
For information about deflate format see [RFC 1951].
## puff and huff
`puff` is an operation that decompresses only the Huffman part of the deflate
stream and keeps the structure of the LZ77 coding unchanged. This is roughly
equivalent of decompressing ‘half way’.
`huff` is the exact opposite of `puff` and it deterministically converts the
`puff` stream back to its original deflate stream. This deterministic conversion
is based on two facts:
* There is no need to perform LZ77 algorithm. This means the deflate stream
could be built by any LZ77 algorithm.
* The dynamic Huffman tables can be recreated uniquely from the code length
array stored inside the `puff` stream. This means the deflate stream can be
reconstructed deterministically using the Huffman tables.
The inclusion of Huffman tables in the `puff` stream has minuscule space burden
(on average maximum 320 bytes for each block. There is roughly one block per
32KB of uncompressed data).
`bsdiff` of two `puffed` streams has much smaller patch in comparison to their
deflate streams, but it is larger than uncompressed streams.
**The major benefits**
* Size of the patch is smaller than deflate stream’s patch.
* `puff` and `huff` are deterministic operations.
* `huff` is in order of 10X faster than full recompression. It is even faster
than Huffman algorithm because it already has the Huffman tables and does
not need to reconstruct it.
* Both algorithms have very low memory footprint.
* The underlying LZ77 algorithm can be anything (as long as it is deflate
compatible). This includes google’s [zopfli]
**The drawbacks**
* The need to define a file format for the puffed stream and stay with this
format forever. If format needs to be changed in the future, then some
versioning mechanism should be there to handle it and backward compatibility
should be maintained.
* The need to define a payload format and stay with it forever. Similarly
needs to be versioned if required later change.
* Does not reduces the patch size as full recompression.
## puffdiff and puffpatch
A deflate compressed file (gzip, zip, etc.) contains multiple deflate streams at
different locations. When this file is puffed, the resulting `puff` stream
contains both puffs and the raw data that existed between the deflates in the
compressed file. When performing `huff` operation, the location of puffs in the
`puff` stream and deflates in the deflate stream should be passed upon. This is
necessary as `huff` operation has to know exactly where the locations of both
puffs and deflates are. (See the following [image](puffin-stream))
Similarly `puffpatch` requires deflates and puffs locations in both the source
and target streams. These location information is saved using Protobufs in the
patch generated by `bsdiff`. One requirement for these two operations are that
`puffpatch` has to be efficient in the client. Client devices have limited
memory and CPU bandwidth and it is necessary that each of these operations are
performed with the most efficiency available. In order to achieve this
efficiency a new operation can be added to `bspatch`, that reads and writes into
a `puff` streams using special interfaces for puffing and huffing on the fly.
## Puffin Patch Format
* Magic (4 bytes) - The string literal "PUF1".
* Header Length (4 bytes) - The size of the header (length of the generated
Protobuf).
* Header - Lengths and locations of deflate and puffs streams in source and
target files in a Protobuf format. See [puffin.proto].
* Patch - This is a binary array directly generated by the `bsdiff` program.
## Puffin Stream Format
* [Block Header](#block-header-format) (3+ bytes) - Defines the type of the
block.
* Data - A mix of literals list and copy length/distances.
* End of Block (2 bytes) - The end of block symbol. Similar to the symbols for
copy length/distance but without the distance bytes. The actual copy length
value is 259 (0x81FF).
### Block Header Format
* Length (2 Bytes) - The size of the block header excluding the two Length
bytes itself - 1.
* Final Block (1 Bit) - Whether the block is the last one or not.
* 1 - Final block
* 0 - Middle block
* Type (2 Bits)
* 0 - Uncompressed. Immediately after the header, zero or one literals
list is present which defines the content of the uncompressed blocks.
* 1 - Fixed Huffman table. The list of literals and length/distances comes
immediately after the header. Fixed Huffman table is defined the deflate
specification and will not change.
* 2 - Dynamic Huffman table. The dynamic Huffman table comes at the end of
the block header.
* 3 - Undefined. This is an error.
* Skip Bits (5 Bits) - Used only for uncompressed blocks (For other types its
value is zero). In an uncompressed block, the [RFC 1951] skips any bits
after reading final block and type bits until the byte boundary in the
input. However, it does not define what the value of these bits should
be. Most implementations assume 0, but some implementations may use any
value. This segment contains those bits as a five-bits integer. When writing
the block header back to the deflate format, the actual number of bits which
where skipped will be calculated easily.
* Huffman Table - It only comes for dynamic Huffman table.
#### Dynamic Huffman Table Format
Depending on the scheme for storing the Huffman tables, the payload size can
change. We discovered that the following scheme does not produce the smallest
payload, but it is the most deterministic one. In a deflate stream, Huffman
tables for literals/length and distances are themselves Huffman coded. In this
format, we also `puff` the Huffman tables into the `puff` stream instead of
completely decompressing them.
There are three tables stored in this structure very similar to the one defined
in [RFC 1951]. A Huffman table can be defined as an array of unsigned integer
code length values. Three Puffed Huffman tables appear like the following
scheme. The first table (codes) is the Huffman table used to decode the next two
Huffman tables. The second Huffman table is used to decode literals and lengths,
and the third Huffman table is used to decode distances.
* Literal/Length Count (1 byte) - Number of alphabets used for literal/length
Huffman codes - 257.
* Distance Count (1 byte) - Number of alphabets used for distance Huffman
codes - 1.
* Alphabet Count (1 byte) - Number of alphabets for coding two previous
Huffman tables - 4.
* Code Lengths ((Alphabet Count + 1) / 2 bytes) - A list of codes for reading
the next two Huffman tables. Each byte contains two codes. If the number of
codes is odd, the last four Bits will be zero.
* Literal/Length/Distance Code Lengths - List of code lengths for encoding
literals/lengths/distance followed The encoding is as follows:
* [0..15] - Represent code [0..15]
* [16..19] - Copy the last code length [3..6] times.
* [20..27] - Repeat code length of 0 for [3..10] times.
* [28..155] - Repeat code length of 0 for [11..138] times.
### Literals List
Literals lists are constructed by a “length” value followed by “length” bytes of
literals. The Puffer should try to merge adjacent literals lists as much as
possible into one literals list in the `puff` stream. This Is a length value
followed by length bytes of literals (Even if there is only one literal.)
* Tag (1 Bit) - The value is 0 indicating that this is a list of literals (not
a copy length/distance).
* Length - The number of literals that would follow in the list.
* (7 Bits) Length = [1 .. 127], The value is: Length - 1
* (7 Bits + 2 Bytes) Length = [128 .. 65663], The values are: 127,
Length - 127.
Conserves size by using only one byte if the number of upcoming
literals is smaller or equal to 127 (About 99% of literals length in a
normal deflate stream fit into this category.) We should never have zero
length literals. Otherwise it will use three bytes.
* Literals (Length Bytes) - A sequence of Length number of literals.
### Copy Length/Distance
This Is a Length value followed by a Distance value.
* Tag (1 Bit) - The value is 1 indicating that this is a copy length/distance
field.
* Length - Conserves size by using only one byte if the length value is
smaller or equal to 129. Otherwise two bytes are used.
* (7 Bits) - Length = [3 .. 129], The value is: Length - 3
* (7 Bites + 1 Byte) Length = [130 .. 258], The value is: 127, Length -
130:
* Distance (2 Bytes) - Distance = [1 .. 32768], The value is:
Distance - 1. The distance value as an unsigned integer.
## Building Puffin
Currently Puffin is being used in both Android and Chrome OS and is built
differently in each of them. There is also a Makefile build, but it is not
comprehensive.
## Usage
Puffin builds an executable `puffin` which can be used to perform diffing and
patching algorithms using Puffin format. To get the list of options available
run:
```shell
puffin --help
```
It can also be used as a library (currently used by update_engine) that provides
different APIs.
## Compute Patch
To compute the diff between our current state and the original changes:
`git diff 4180a65119ef2c333c4d33c9e39869da89a8faea -- .`
## References
[RFC 1951]: https://www.ietf.org/rfc/rfc1951.txt
[puffin.proto]: /src/puffin.proto
[zopfli]: https://en.wikipedia.org/wiki/Zopfli
Codebase Browser
chromium