Understanding ZigZag Encoding for Varints

ZigZag encoding is a data compression technique that transforms signed integers into unsigned integers so that numbers with small absolute values—regardless of whether they are positive or negative—are represented by small positive numbers. In binary serialization protocols like Protocol Buffers, variable-length integer (varint) encoding achieves compression by using fewer bytes for smaller unsigned values. However, standard negative numbers in two’s complement notation have leading ones, causing varints to consume maximum byte lengths; ZigZag encoding eliminates this inefficiency by interleaving positive and negative values, ensuring small negative numbers compress just as efficiently as small positive numbers.

The Problem: Two’s Complement and Varints

Variable-length quantity (varint) encoding, such as LEB128, compresses integers by using only as many 7-bit payload bytes as necessary, using the 8th bit of each byte as a continuation flag.

• The integer 1 requires only 1 byte: 00000001.
• The integer 300 requires 2 bytes: 10101100 00000010.

However, modern computers represent signed integers using two’s complement. In a standard 32-bit system, the number -1 is stored with all bits set to 1:

-1 = 11111111 11111111 11111111 11111111

When a standard varint encoder processes this value, it sees the high-order bits set to 1 and assumes a very large unsigned number. Consequently, encoding -1 forces the varint algorithm to output the maximum number of bytes (5 bytes for a 32-bit integer, or 10 bytes for a 64-bit integer), defeating the purpose of compression.

How ZigZag Encoding Solves the Problem

ZigZag encoding maps signed integers to unsigned integers by alternating (“zigzagging”) back and forth between positive and negative numbers:

By assigning odd integers to negative values and even integers to positive values, numbers with small absolute magnitudes (like -1, -2, or 1) are mapped to small unsigned values (1, 3, 2). When passed to a varint encoder, these small unsigned integers require only a single byte.

Bitwise Implementation

ZigZag encoding can be implemented efficiently in software without conditional branching using basic bitwise operators.

Encoding

For a signed \(k\)-bit integer \(n\) (where \(k\) is 32 or 64):

\[\text{Encoded}(n) = (n \ll 1) \oplus (n \gg (k - 1))\]

Note: The right-shift (\(\gg\)) must be an arithmetic shift, which preserves the sign bit by shifting in 1s for negative numbers and 0s for positive numbers.

Step-by-Step for a 32-bit Integer:

1. \(n \ll 1\): Shifts the number left by one bit, making room in the least significant bit (LSB) and multiplying the absolute value by 2.
2. \(n \gg 31\):
   • If \(n \ge 0\), this yields 00000000 00000000 00000000 00000000 (0).
   • If \(n < 0\), this yields 11111111 11111111 11111111 11111111 (-1).
3. \(\oplus\) (XOR):
   • For positive numbers, XORing with 0 leaves \((n \ll 1)\) unchanged.
   • For negative numbers, XORing with all 1s flips every bit (one’s complement), effectively turning the negative value into an odd positive number.

Example: Encoding -1 (32-bit)

1. n = -1 \(\rightarrow\) 11111111 11111111 11111111 11111111
2. n << 1 \(\rightarrow\) 11111111 11111111 11111111 11111110
3. n >> 31 \(\rightarrow\) 11111111 11111111 11111111 11111111
4. (n << 1) ^ (n >> 31) \(\rightarrow\) 00000000 00000000 00000000 00000001 (Unsigned 1)

Decoding

To reverse the process and restore the original signed integer from an unsigned ZigZag-encoded value \(z\):

\[\text{Decoded}(z) = (z \ggg 1) \oplus -(z \ \& \ 1)\]

Note: The right-shift (\(\ggg\)) is a logical shift, shifting in zeros from the left.

Step-by-Step:

1. \(z \ggg 1\): Divides \(z\) by 2, recovering the original magnitude.
2. \(-(z \ \& \ 1)\):
   • If \(z\) is even (LSB is 0), \(-(0)\) evaluates to 0.
   • If \(z\) is odd (LSB is 1), \(-(1)\) evaluates to all 1s (-1 in two’s complement).
3. \(\oplus\) (XOR):
   • If the original was positive, XOR with 0 preserves the value.
   • If the original was negative, XOR with all 1s flips the bits back to restore the negative two’s complement representation.