# A Generator for Recursive Zip Files
## 2 Materials and Methods
### Deflate
#### 2.1.2 Huffman  
In addition to LZ77 compression, another key component of the DEFLATE algorithm is Huffman encoding. Huffman encoding is a variable-length encoding technique that assigns shorter codes to more frequent symbols and longer codes to less frequent symbols, optimizing the compression of the data. Within the DEFLATE algorithm, Huffman encoding is applied to both literal and repeat tokens, enabling the efficient representation of data patterns. Within the zip format, data are typically divided into blocks for compression, with three block types: stored, fixed and dynamic blocks. Stored blocks simply store raw data without compression. Fixed blocks, on the other hand, use pre-defined Huffman code tables to compress the data efficiently. These tables are fixed and provided by the DEFLATE specification [5]. Dynamic blocks also exist, but they are not needed to create recursive zip files and will not be further discussed. Each block in the DEFLATE algorithm is characterized by a three-bit header providing essential information about the block's structure. The first bit denotes whether the block is the final block in the data stream. The second and third bits specify the block type, with a stored block identified by two consecutive 0 bits. Following the three-bit header, the structure of the block varies depending on its type. In the case of a stored block, the byte is padded with 0 bits until reaching the byte boundary. Subsequently, two bytes indicate the number of raw bytes stored within the block. Interestingly, the following two bytes are the bitwise negation of the previous two bytes, ensuring data integrity. Finally, the raw data themselves follow this header structure. If a stored block does not start in the middle of a byte, the header is thus always five bytes. A schematic overview is given in Figure 2.  
As stored blocks do not compress data, they can only be used to store the literal tokens from the LZ77 algorithm. In contrast, fixed blocks can encode both literals and repeat tokens. Similar to stored blocks, fixed blocks begin with the same three-bit header, denoting the block type and whether it marks the final block in the stream. However, the distinctive identifier for a fixed block is the sequence \"01\". Following this header, the compressed data within the fixed block adhere to a predefined encoding structure specified in the DEFLATE specification [5]. To mark the end of the block, seven 0 bits are added. A visual representation is shown in Figure 3.  
The tokens are encoded using fixed tables as defined in the specification, employing a predetermined alphabet with codes ranging from 0 to 287. Each code corresponds to a fixed number of bits and a specific binary representation. Table 2 is organized such that  
Figure 1: Example of encoding abracadabra with LZSS. Figure 2: Structure of a stored block. the codes for more frequently occurring values are shorter, while less frequent values have longer codes, thereby enhancing the compression efficiency. The codes serve to differentiate between literal tokens and repeat tokens. 1. 0 to 255: These codes are assigned to literal tokens. 2. 256: This code indicates the end of the fixed Huffman block, signaled by the seven 0 bits previously mentioned. 3. 257 to 285: These codes represent repeat tokens, specifically the length of the repetition. Additional bits are used depending on the repeat token's length. 4. 286 and 287: Although codes 286 and 287 can be represented within this format, they do not appear in the compressed data. These codes are unused but are part of the overall code design. The use of 256 codes for literal tokens ensures that all possible bytes can be represented. While the specification allows a repeat token to have a maximum length of 258, there are insufficient codes to represent all possible lengths directly. To address this issue, each code for the encoding of a repeat token is associated with a base length and a corresponding number of extra bits. A detailed overview of this system is provided in Figure 4.