Deflate format file

Intended audience Definitions of terms and conventions used Changes from previous versions Compressed representation overview Detailed specification Overall conventions Packing into bytes Compressed block format Synopsis of prefix and Huffman coding Use of Huffman coding in the "deflate" format Details of block format Compressed blocks length and distance codes Compression algorithm details Security Considerations Source code Author's Address Introduction 1.

A simple counting argument shows that no lossless compression algorithm can compress every possible input data set. For the format defined here, the worst case expansion is 5 bytes per 32K- byte block, i. English text usually compresses by a factor of 2. The text of the specification assumes a basic background in programming at the level of bits and other primitive data representations. Familiarity with the technique of Huffman coding is helpful but not required.

Scope The specification specifies a method for representing a sequence of bytes as a usually shorter sequence of bits, and a method for packing the latter bit sequence into bytes. Compliance Unless otherwise indicated below, a compliant decompressor must be able to accept and decompress any data set that conforms to all the specifications presented here; a compliant compressor must produce data sets that conform to all the specifications presented here. Definitions of terms and conventions used Byte: 8 bits stored or transmitted as a unit same as an octet.

See below, for the numbering of bits within a byte. String: a sequence of arbitrary bytes. Changes from previous versions There have been no technical changes to the deflate format since version 1. In version 1. Relative back-references can be made across any number of blocks, as long as the distance appears within the last 32kB of uncompressed data decoded termed the sliding window. The second compression stage consists of replacing commonly-used symbols with shorter representations and less commonly used symbols with longer representations.

The method used is Huffman coding which creates an unprefixed tree of non-overlapping intervals, where the length of each sequence is inversely proportional to the probability of that symbol needing to be encoded.

The more likely a symbol has to be encoded, the shorter its bit-sequence will be. A match length code will always be followed by a distance code. Based on the distance code read, further "extra" bits may be read in order to produce the final distance. The distance tree contains space for 32 symbols:.

Note that for the match distance symbols 2—29, the number of extra bits can be calculated as. During the compression stage, it is the encoder that chooses the amount of time spent looking for matching strings. Akronymus 24 days ago root parent next [—]. I could see a variety of space filling curves working for that. Aissen 25 days ago prev next [—]. This is going to be super useful for educational purposes. I'd really like to see more file formats like this.

There's already a bunch of minimal programming languages and even some operating systems. It's great value for learning stuff when you can implement a quite OK version of something in dozens of hours or less.

ErikCorry 24 days ago prev next [—]. I experimented with adding this to the embedded system Toit. I would really like a bit of random access into the image without having to divide it up into multiple tiles. And the spec took a direction that didn't really suit me - i wanted to use it for Gui-like textures which have slabs of colours and anti-aliased edges with varying alpha. In the final version of the spec there's no way to code "the alpha changed, but the color is the same".

Previously that took 2 bytes. Have you considered compressed texture formats, perhaps DXT5? Fixed compression ratio 1 byte per pixel for DXT5 , arbitrary random access, decompress the pixels you need on the fly. ErikCorry 24 days ago root parent next [—]. This is pretty neat. Simple enough to decode, and very simple to do random access. And if we ever port to something with a GPU it's might even be supported. But I worry it might be too visibly lossy, especially for GUI-ish textures. It's certainly not going to be perceptually lossless for every image, but good compressors can do pretty well.

There's a big difference in quality between good compressors and bad ones. Newer formats like ASTC have better quality but are more complex.

ASTC has the advantage of selectable compression ratio from 8 bits per pixel down to 0. FullyFunctional 24 days ago parent prev next [—].

All these points are spot on, but I want to reorder the priority. IshKebab 24 days ago prev next [—]. This is pretty cool. If the goal is to be fast and simple then surely little endian would make more sense given that basically all processors are little endian. Big endian just means you need to swap everything twice. So only two 4-byte swaps per file. Zababa 24 days ago parent prev next [—]. Overall conventions File format Member format Member header and trailer Extra field Security Considerations Author's Address Appendix: Jean-Loup Gailly's gzip utility Introduction 1.

The text of the specification assumes a basic background in programming at the level of bits and other primitive data representations. Scope The specification specifies a compression method and a file format the latter assuming only that a file can store a sequence of arbitrary bytes.

It does not specify any particular interface to a file system or anything about character sets or encodings except for file names and comments, which are optional. Compliance Unless otherwise indicated below, a compliant decompressor must be able to accept and decompress any file that conforms to all the specifications presented here; a compliant compressor must produce files that conform to all the specifications presented here.

The material in the appendices is not part of the specification per se and is not relevant to compliance. Definitions of terms and conventions used byte: 8 bits stored or transmitted as a unit same as an octet. For this specification, a byte is exactly 8 bits, even on machines which store a character on a number of bits different from 8.

See below for the numbering of bits within a byte. Changes from previous versions There have been no technical changes to the gzip format since version 4.

In version 4.