Mars Terminal Infrastructure

Zstandard (or zstd) is a fast lossless compression algorithm designed for real-time compression scenarios. It aims to provide compression ratios comparable to or better than zlib while maintaining high speeds. It is implemented as a C library and a command-line utility that supports producing and decoding .zst, .gz, .xz, and .lz4 files.

Key characteristics:

• Speed vs. Ratio Trade-off: Users can configure the compression level in small increments to balance speed and ratio.
• Decompression Performance: Decompression speed remains relatively stable across different compression settings.
• Small Data Optimization: Supports a 'training mode' to create dictionaries for highly efficient compression of small data sets.

Mars is a cross-platform terminal infrastructure component used by WeChat. It is composed of several specialized modules:

• comm: A standalone public library providing core utilities such as socket, thread, message queue, and coroutine.
• xlog: A high-reliability, high-performance runtime logging component.
• SDT: A network diagnostic component.
• STN: The Signaling Transmission Network module, which is the primary part of Mars.

PZstandard is a tool similar to pigz but for the Zstandard format. It enables multi-core compression and decompression by breaking input into equal-sized chunks, compressing each chunk independently into a Zstandard frame, and concatenating them.

Key features:

• Zstandard Compatibility: Produces and consumes standard Zstandard format files.
• Parallel Decompression: Supports parallel decompression for files compressed with PZstandard.
• Optimized I/O: When decompressing standard Zstandard files, it uses one thread for I/O and another for decompression.

The Window_Descriptor (an optional 1-byte field) provides the minimum memory buffer required to decompress a frame. If Single_Segment_flag is set, this descriptor is skipped and Window_Size equals Frame_Content_Size.

Structure:

• Bits 7-3: Exponent
• Bits 2-0: Mantissa

Calculation Formula:

windowLog = 10 + Exponent;
windowBase = 1 << windowLog;
windowAdd = (windowBase / 8) * Mantissa;
Window_Size = windowBase + windowAdd;

Constraints:

• Minimum Window_Size: 1 KB.
• Maximum Window_Size: (1<<41) + 7*(1<<38) bytes (~3.75 TB).
• Recommendation: Decoders should support up to 8 MB for interoperability. Encoders should avoid generating frames requiring more than 8 MB unless necessary.

FSE is an entropy codec based on Asymmetric Numeral Systems (ANS) used for compressing symbols like Literals_Length_Code, Match_Length_Code, and offset codes.

Key Characteristics:

• Directionality: FSE bitstreams are read from end to beginning. While the bit order within a byte is not reversed, the elements themselves are processed in reverse order of how they were written.
• State Management: Decoding involves a state carried between symbols. An initial state is obtained by consuming Accuracy_Log bits as a little-endian value.
• Decoding Table: The table size is a power of 2. Each entry contains a Symbol, Num_Bits, and Baseline. To get the next state, the decoder consumes Num_Bits from the stream and adds it to the Baseline.

To transform decoded weights into Huffman prefix codes, follow these steps:

1. Calculate Bits: For each symbol, calculate Number_of_Bits = (Weight > 0) ? Max_Number_of_Bits + 1 - Weight : 0.
2. Sort: Sort symbols by Weight. For symbols with the same weight, maintain their natural sequential order.
3. Filter: Remove symbols with a weight of zero.
4. Distribute: Starting from the lowest weight, distribute prefix codes in sequential order.

Example Weight Distribution:

Resulting Codes:

The Huffman Tree header is a single byte (0-255) that determines how the series of weights is encoded. The encoding method depends on the value of the headerByte:

• FSE Compression (headerByte < 128): The weights are compressed using Finite State Entropy (FSE). The length of the FSE-compressed series is equal to the value of headerByte (0-127).
• Direct Representation (headerByte >= 128): Weights are encoded directly as 4-bit fields (0-15).
  • Weights are encoded forward, with two weights per byte (the first weight takes the top 4 bits, the second takes the bottom 4 bits).
  • The number of weights is calculated as Number_of_Weights = headerByte - 127.
  • This method supports up to 128 weights (alphabet sizes up to 129 symbols). If any literal symbol > 128 has a non-zero weight, you must use FSE instead.

When the Huffman Tree header indicates FSE compression, the weights are stored as a single bitstream with two interleaved states (State1 and State2) that share a single distribution table.

Key decoding details:

• Compressed Size: Provided by the headerByte.
• Max Decompressed Size: Always 255 (since literal values span 0-255).
• Interleaving: State1 encodes even-indexed symbols, and State2 encodes odd-indexed symbols. They take turns decoding a single symbol and updating their state.
• Termination: Decoding stops when the bitstream reaches an overflow condition (where updating the state would require more bits than remain in the stream), at which point remaining bits are assumed to be 0.

The --long mode is designed to improve compression ratios for files with long matches at large distances (up to 128 MiB).

Trade-offs:

• Memory: Increases memory usage for both compressor and decompressor.
• Compression Speed: May degrade if few long matches are found.
• Decompression Speed: Usually improves when many long distance matches are present.

This mode is highly effective for files like multiple versions of the same dataset (e.g., different versions of a source code repository).

zstd --long -1 file.dat