How Protobuf Encodes Varints Using MSB

Protocol Buffers (Protobuf) uses variable-length quantities, known as varints, to serialize integers efficiently by using fewer bytes for smaller numeric values. By dividing binary representations into 7-bit payloads and using the Most Significant Bit (MSB) as a stream continuation flag, Protobuf allows 32-bit or 64-bit integers to occupy anywhere from one to ten bytes depending on their magnitude. This article breaks down the binary mechanics of varint encoding, the role of the MSB, and walks through a concrete step-by-step example.

The Role of the Most Significant Bit

In standard binary representations, all 8 bits of a byte are used to represent data. Protobuf varints modify this structure by splitting each byte into two components:

1. The Most Significant Bit (MSB): The eighth bit (bit index 7) serves as a control flag or “continuation bit.”
   • 1: Indicates that further bytes follow in the stream for the current integer.
   • 0: Indicates that this is the final byte of the integer.
2. The Payload Bits: The remaining 7 lower bits contain the actual binary data of the number.

Because only 7 bits per byte carry integer data, numbers are grouped into 7-bit chunks rather than standard 8-bit octets.

Endianness and Bit Ordering

Protobuf stores varints in little-endian order. This means that the least significant 7-bit group of the original integer is placed in the first serialized byte, and subsequent higher-order 7-bit groups follow in later bytes.

Step-by-Step Encoding Process

To encode any non-negative integer into a Protobuf varint:

1. Write the integer in standard binary format.
2. Pad the binary string so its length is a multiple of 7 bits.
3. Split the binary sequence into 7-bit chunks.
4. Reverse the order of the 7-bit chunks (least significant chunk comes first).
5. Attach the MSB to each chunk:
   • Set MSB to 1 for all chunks except the last one.
   • Set MSB to 0 for the final chunk.
6. Convert each resulting 8-bit byte into hexadecimal or binary bytes for transmission.

Step-by-Step Example: Encoding the Number 300

To illustrate the mechanism, consider serializing the integer 300.

Step 1: Binary Conversion

The decimal number 300 in standard binary is: 100101100 (9 bits)

Step 2: Split into 7-Bit Groups

Group the binary digits into 7-bit chunks, padding the front with zeros: - Most Significant Group: 0000010 - Least Significant Group: 0101100

Step 3: Reorder in Little-Endian Format

Place the least significant group first: 1. First 7-bit group: 0101100 2. Second 7-bit group: 0000010

Step 4: Apply the MSB Continuation Flag

• First Byte: Since another byte follows, prepend an MSB of 1:
  • 1 + 0101100 = 10101100 (0xAC in hex)
• Second Byte: Since this is the terminating byte, prepend an MSB of 0:
  • 0 + 0000010 = 00000010 (0x02 in hex)

Result

The integer 300 is encoded into two bytes: 10101100 00000010 (or 0xAC 0x02).

Decoding a Varint

To decode a varint, the parser reads bytes sequentially: 1. Read a byte from the stream. 2. Check the MSB. If it is 1, strip the MSB, append the 7 payload bits to the output buffer, and proceed to the next byte. 3. If the MSB is 0, strip the MSB, append the 7 payload bits, and stop reading. 4. Shift and combine the 7-bit groups according to their little-endian positions to reconstruct the original integer.

Efficiency and Considerations

Varint encoding provides substantial space savings for systems where smaller integer values are common, reducing a 4-byte standard integer to just 1 byte for values between 0 and 127. However, because each byte incurs a 1-bit overhead for the MSB, very large numbers (such as values requiring all 32 or 64 bits) require slightly more space than their fixed-width equivalents (e.g., up to 5 bytes for a 32-bit integer and 10 bytes for a 64-bit integer).