Variable Length Quantity in Crystal: Complete Solution & Deep Dive Guide

---

Mastering VLQ: A Deep Dive into Efficient Integer Encoding in Crystal

Variable Length Quantity (VLQ) is a universal encoding scheme that compresses integers by storing them in a variable number of bytes. This guide provides a complete walkthrough of implementing both VLQ encoding and decoding from scratch in Crystal, optimizing data size for transmission and storage.

Imagine you're building a high-performance application that needs to send millions of musical notes over a network, or perhaps you're designing a data serialization format for a distributed system. The vast majority of the numbers you're sending are small—notes within a typical octave, or identifiers for common fields. Using a fixed 32-bit or 64-bit integer for every single number feels wasteful, bloating your data packets and increasing latency. This is a common bottleneck that can silently degrade performance and increase operational costs.

What if there was a way to represent small numbers using just one byte, slightly larger numbers using two, and only use the full four or five bytes for truly massive values? This is precisely the problem that Variable Length Quantity (VLQ) encoding solves. It's an elegant, bit-level technique that dynamically sizes integers, and mastering it is a mark of a developer who thinks deeply about efficiency. In this guide, we'll dissect the VLQ algorithm and build a robust implementation from the ground up using the power and expressiveness of the Crystal language.

---

What is Variable Length Quantity (VLQ)?

Variable Length Quantity, or VLQ, is a variable-length encoding method used to represent arbitrarily large integers in a sequence of bytes. Its primary goal is data compression, particularly in scenarios where a stream of numbers contains many small values. Instead of allocating a fixed size (like 4 bytes for a UInt32), VLQ uses as few bytes as necessary.

The core mechanism is simple yet brilliant. Each byte in a VLQ sequence is split into two parts:

• The Continuation Bit: The most significant bit (MSB) of the byte acts as a flag. If this bit is 1, it signals that more bytes follow as part of the current number. If it's 0, it marks this byte as the final one for the number.
• The Data Payload: The remaining 7 bits of the byte are used to store a piece of the integer's value.

By chaining these 7-bit payloads together, we can construct integers of any size. A number that fits within 7 bits (0-127) can be stored in a single byte. A number requiring 14 bits of data can be stored in two, and so on. This makes it incredibly efficient for data that is skewed towards smaller numerical values.

---

Why is VLQ So Important in Modern Computing?

While VLQ might seem like a low-level, niche algorithm, its applications are widespread and critical to the performance of many systems you likely use every day. Understanding its purpose gives you a deeper appreciation for the engineering that goes into efficient data formats.

Key Use Cases

• MIDI File Format: The Standard MIDI File (SMF) format uses VLQ to encode timestamps (delta-times) between musical events. Since most notes in a piece of music are close together, the time differences are small, making VLQ a perfect fit for compressing the file size.
• Google's Protocol Buffers (Protobufs): This is a high-performance, language-neutral, platform-neutral mechanism for serializing structured data. Protobufs use a variant of VLQ called "Varints" to encode integers. This is a major reason why Protobufs are more compact and faster to parse than alternatives like XML or JSON.
• JavaScript Source Maps: When you minify JavaScript for production, source maps are generated to link the compressed code back to the original source for easier debugging. These maps use VLQ to encode line and column number mappings in a highly compact string format.
• WebAssembly (Wasm): The binary instruction format for Wasm uses the LEB128 encoding, which is a nearly identical variable-length encoding scheme, to represent integers and data lengths efficiently.

The common thread is efficiency. In networking, smaller packets mean less latency. In storage, it means less disk space. In memory, it means a smaller footprint. By learning to implement VLQ, you are adding a powerful data compression tool to your arsenal, a concept that is central to the curriculum at kodikra.com.

---

How Does the VLQ Encoding Process Work?

Encoding an integer into its VLQ byte representation is a systematic process of breaking the number down into 7-bit chunks. Let's visualize the algorithm before jumping into the Crystal code. The process flows from the least significant bits to the most significant.

Here is a conceptual diagram of the encoding logic:

    ● Start with an integer (e.g., 137)
    │
    ▼
  ┌───────────────────┐
  │ Is the number > 0?│
  │ (or is it the first chunk?)
  └─────────┬─────────┘
            │ Yes
            ▼
  ┌───────────────────┐
  │ Take lowest 7 bits│
  │ (number & 0x7F)   │
  └─────────┬─────────┘
            │
            ▼
  ┌───────────────────┐
  │ Prepend to result │
  └─────────┬─────────┘
            │
            ▼
  ┌───────────────────┐
  │ Shift number >> 7 │
  └─────────┬─────────┘
            │
            └─────────> Return to check if number > 0
            │ No
            ▼
  ┌───────────────────┐
  │ Set continuation  │
  │ bit (0x80) on all │
  │ but the last byte │
  └─────────┬─────────┘
            │
            ▼
       ● End (VLQ Bytes)

Step-by-Step Encoding Example: Encoding `65535`

1. Initial Value: number = 65535 (which is 0b11111111_11111111 in binary).
2. Iteration 1:
   • Take the lowest 7 bits: 65535 & 0x7F -> 127 (0b1111111).
   • Right-shift the number by 7: 65535 >> 7 -> 511.
   • Our byte list is now [127]. Since 511 > 0, we continue.
3. Iteration 2:
   • Take the lowest 7 bits of 511: 511 & 0x7F -> 127 (0b1111111).
   • Right-shift the number by 7: 511 >> 7 -> 3.
   • We prepend this to our list: [127, 127]. Since 3 > 0, we continue.
4. Iteration 3:
   • Take the lowest 7 bits of 3: 3 & 0x7F -> 3 (0b0000011).
   • Right-shift the number by 7: 3 >> 7 -> 0.
   • We prepend this to our list: [3, 127, 127]. The number is now 0, so we stop the loop.
5. Final Step (Set Continuation Bits):
   • The last byte (127) does not get a continuation bit.
   • All preceding bytes do. We add 0x80 (128) to them.
   • 3 becomes 3 | 0x80 -> 131.
   • The first 127 becomes 127 | 0x80 -> 255.
   • The final byte sequence is [131, 255, 127].

This systematic conversion ensures that any 32-bit unsigned integer can be correctly represented.

The Crystal Implementation: VLQ Encoding

Now, let's translate this logic into clean, idiomatic Crystal code. This solution is part of a dedicated kodikra module designed to test your understanding of bitwise operations.

# The VLQ module provides methods for Variable Length Quantity encoding and decoding.
module VLQ
  # The continuation bit mask (binary 10000000).
  # If this bit is set on a byte, it means more bytes for the current number follow.
  CONTINUATION_BIT = 0x80_u8

  # The data payload mask (binary 01111111).
  # This mask is used to extract the 7 bits of data from a byte.
  DATA_MASK = 0x7F_u8

  # Encodes a series of 32-bit unsigned integers into a VLQ byte array.
  def self.encode(numbers : Enumerable(UInt32)) : Array(UInt8)
    bytes = [] of UInt8
    numbers.each do |number|
      bytes.concat(encode_single(number))
    end
    bytes
  end

  # Helper method to encode a single number.
  private def self.encode_single(number : UInt32) : Array(UInt8)
    # Handle the zero case explicitly, as the main loop would not run.
    return [0_u8] if number == 0

    encoded_bytes = [] of UInt8
    current_num = number

    while current_num > 0
      # Extract the lowest 7 bits of the number.
      seven_bits = (current_num.to_u8 & DATA_MASK)
      encoded_bytes.unshift(seven_bits)

      # Shift the number to the right by 7 bits to process the next chunk.
      current_num >>= 7
    end

    # Set the continuation bit on all bytes except the last one.
    # We iterate up to the second-to-last element.
    (0...encoded_bytes.size - 1).each do |i|
      encoded_bytes[i] = encoded_bytes[i] | CONTINUATION_BIT
    end

    encoded_bytes
  end
end

Code Walkthrough: `encode`

• Module and Constants: We define our logic within a VLQ module. The constants CONTINUATION_BIT (0x80) and DATA_MASK (0x7F) make the code more readable and self-documenting.
• encode Method: This public method takes an enumerable of UInt32 (like an Array) and iterates through each number, calling a private helper encode_single to handle the logic for one integer. The results are concatenated into a final byte array.
• encode_single Helper: This is where the core algorithm resides.
  • Zero Handling: The while current_num > 0 loop won't execute for an input of 0. We handle this edge case by immediately returning an array containing a single zero byte.
  • The Loop: The while loop continues as long as there are bits left to process in current_num.
  • Extracting 7 Bits: current_num.to_u8 & DATA_MASK performs a bitwise AND. This effectively zeroes out the most significant bit, leaving only the 7 data bits.
  • Building the Array: We use unshift to add the new 7-bit chunk to the beginning of the encoded_bytes array. This is more intuitive than adding to the end and reversing later, as it builds the byte sequence in the correct final order.
  • Shifting: current_num >>= 7 is a bitwise right shift. It discards the 7 bits we just processed and prepares the next 7 bits for the following iteration.
  • Setting Continuation Bits: After the loop, we have an array of 7-bit data chunks. The final step is to iterate through all but the last element and apply the CONTINUATION_BIT using a bitwise OR (|). This sets the MSB to 1 for these bytes, correctly linking them together.

---

How Does the VLQ Decoding Process Work?

Decoding is the reverse process: we read a stream of bytes and reconstruct the original integer. We read bytes one by one, accumulating their 7-bit data payloads until we find a byte where the continuation bit is 0.

The key operations are checking the MSB and combining the 7-bit chunks using bitwise shifts and additions.

Here is a conceptual diagram of the decoding logic:

    ● Start with VLQ bytes & initialized number = 0
    │
    ▼
  ┌───────────────────┐
  │ Read the next byte│
  └─────────┬─────────┘
            │
            ▼
  ┌───────────────────┐
  │ Left shift number │
  │ by 7 (number <<= 7)│
  └─────────┬─────────┘
            │
            ▼
  ┌───────────────────┐
  │ Get 7 data bits   │
  │ (byte & 0x7F)     │
  └─────────┬─────────┘
            │
            ▼
  ┌───────────────────┐
  │ Add data to number│
  │ (number |= data)  │
  └─────────┬─────────┘
            │
            ▼
    ◆ Is continuation bit set?
   ╱      (byte & 0x80) != 0     ╲
  Yes                             No
  │                               │
  └─────────> Loop back to read next byte
                                  │
                                  ▼
                            ● End (Decoded Integer)

Step-by-Step Decoding Example: Decoding [131, 255, 127]

1. Initial State: result = 0. Byte stream is [131, 255, 127].
2. Process Byte 1 (131):
   • 131 in binary is 0b10000011.
   • The continuation bit is set (131 & 0x80 != 0).
   • Extract data bits: 131 & 0x7F -> 3.
   • Shift current result left by 7: 0 << 7 -> 0.
   • Add the new data: 0 | 3 -> 3. Our current result is 3.
3. Process Byte 2 (255):
   • 255 in binary is 0b11111111.
   • The continuation bit is set (255 & 0x80 != 0).
   • Extract data bits: 255 & 0x7F -> 127.
   • Shift current result left by 7: 3 << 7 -> 384.
   • Add the new data: 384 | 127 -> 511. Our current result is 511.
4. Process Byte 3 (127):
   • 127 in binary is 0b01111111.
   • The continuation bit is NOT set (127 & 0x80 == 0). This is the last byte for this number.
   • Extract data bits: 127 & 0x7F -> 127.
   • Shift current result left by 7: 511 << 7 -> 65408.
   • Add the new data: 65408 | 127 -> 65535.
   • Since this was the last byte, the final decoded number is 65535.

The Crystal Implementation: VLQ Decoding

The decoding logic requires careful state management as we iterate through the byte stream. We also need to handle potential errors, such as an incomplete sequence where the last byte still has its continuation bit set.

# The VLQ module provides methods for Variable Length Quantity encoding and decoding.
module VLQ
  # ... (constants from above) ...

  # Decodes a VLQ byte array into a series of 32-bit unsigned integers.
  # Raises an ArgumentError if the byte sequence is incomplete.
  def self.decode(bytes : Enumerable(UInt8)) : Array(UInt32)
    numbers = [] of UInt32
    current_num = 0_u32
    is_building_number = false

    bytes.each do |byte|
      is_building_number = true

      # Check for potential overflow before shifting.
      # If the high 7 bits of current_num are already set, shifting
      # left by 7 will cause an overflow.
      if (current_num & 0xFE000000) != 0
        raise ArgumentError.new("Overflow detected during decoding")
      end

      # Make room for the next 7 bits.
      current_num <<= 7

      # Extract the 7-bit data payload and add it to our number.
      data_payload = byte & DATA_MASK
      current_num |= data_payload

      # Check if this is the last byte for the current number.
      is_continuation = (byte & CONTINUATION_BIT) != 0
      unless is_continuation
        numbers << current_num
        # Reset for the next number.
        current_num = 0_u32
        is_building_number = false
      end
    end

    # If the loop finishes while we were still expecting more bytes
    # (the last byte had its continuation bit set), the sequence is invalid.
    if is_building_number
      raise ArgumentError.new("Incomplete byte sequence")
    end

    numbers
  end
end

Code Walkthrough: `decode`

• State Variables: We initialize an empty array numbers to store the results, current_num = 0 to build the integer currently being decoded, and a boolean is_building_number to track if we are in the middle of a multi-byte number.
• Iteration: We loop through each byte in the input.
• Overflow Check: This is a critical safety check. A valid 32-bit integer can be represented by at most 5 VLQ bytes. If we accumulate too many bits, a left shift (<<= 7) could discard the most significant bits, leading to an incorrect result. This check ensures that the top 7 bits of our 32-bit integer are clear before we shift, preventing data loss.
• Shifting: current_num <<= 7 shifts the bits we've accumulated so far to the left by 7 positions, making room for the 7 new data bits from the current byte.
• Adding Data: current_num |= (byte & DATA_MASK) extracts the 7-bit payload and uses a bitwise OR to combine it with the shifted value of current_num.
• Checking the Continuation Bit: (byte & CONTINUATION_BIT) == 0 checks if the MSB is 0. If it is, this is the final byte for the current number.
• Finalizing a Number: When a final byte is found, we add the completed current_num to our numbers array and reset our state variables (current_num = 0, is_building_number = false) to prepare for the next integer in the stream.
• Error Handling: After the loop, we check is_building_number. If it's still true, it means the byte stream ended abruptly while in the middle of a number (the last byte had its continuation bit set). This is an invalid state, so we raise an ArgumentError to signal the corrupt data. This robust error handling is a key part of production-quality code. For more on Crystal, dive deeper into the Crystal programming language.

---

Where to Use VLQ: Pros, Cons, and Risks

Like any technology, VLQ is a tool with specific strengths and weaknesses. Knowing when to use it is as important as knowing how to implement it. This is a core concept we emphasize in the kodikra.com Crystal Learning Roadmap.

Aspect	Pros (Advantages)	Cons & Risks (Disadvantages)
Space Efficiency	Extremely efficient for data streams with a high frequency of small integers (values < 128 take only one byte).	Can be less efficient than fixed-width for large numbers. A 32-bit number near the max value takes 5 bytes, versus 4 for a fixed UInt32.
Flexibility	Can represent integers of any size, not limited by a fixed 32-bit or 64-bit boundary.	The variable nature means you cannot jump to the Nth integer in a stream without parsing all preceding integers.
Processing Overhead	The bitwise operations are extremely fast on modern CPUs.	Slightly more complex and computationally intensive than simply reading a fixed-width integer directly from memory.
Error Propagation	A single corrupted bit (e.g., a flipped continuation bit) can desynchronize the entire rest of the stream, making all subsequent numbers unreadable.	Requires robust error checking (like our incomplete sequence check) to handle malformed data gracefully.
Negative Numbers	The standard VLQ algorithm is for unsigned integers.	Requires an additional encoding layer, such as ZigZag encoding (used by Protobufs), to handle negative numbers efficiently.

---

Frequently Asked Questions (FAQ)

1. Is VLQ the same as UTF-8?

No, but they are based on a similar principle of variable-length encoding. UTF-8 encodes Unicode code points into sequences of 1 to 4 bytes, using a specific pattern in the leading bits to indicate the sequence length. VLQ is a more general-purpose integer encoding that uses a single continuation bit. Both solve the problem of efficiently representing a large range of values in a compact, variable-length format.

2. Why not just use a fixed-size integer like UInt64 for everything?

You could, but it would be very inefficient for data that is mostly small numbers. If 99% of your integers are less than 100, using 8 bytes (64 bits) for each one means over 87% of your data storage or bandwidth is wasted on zero-filled bytes. VLQ avoids this waste, which is critical in network-constrained or storage-sensitive applications.

3. How does the "continuation bit" work?

The continuation bit is the most significant bit (MSB) of each byte in the sequence. In an 8-bit byte, this is the leftmost bit. When you read a byte, you check this bit first. If it's a 1 (e.g., the byte's value is >= 128), it tells your decoder, "Hold on, the number isn't finished yet. Combine my 7 data bits with the next byte's." If the bit is a 0, it signals, "This is the final piece of the number. Once you add my 7 data bits, the integer is complete."

4. What happens if the last byte in a VLQ sequence has its continuation bit set?

This indicates a corrupted or incomplete data stream. A valid VLQ sequence for any number must end with a byte that has its continuation bit set to 0. Our decoding implementation correctly identifies this situation and raises an ArgumentError to prevent the program from processing invalid data.

5. Can VLQ encode negative numbers?

The standard VLQ algorithm described here is for unsigned integers. To encode signed (positive and negative) numbers efficiently, it's often paired with another technique called ZigZag encoding. ZigZag maps signed integers to unsigned integers in a way that small negative numbers (-1, -2, etc.) become small positive numbers, which can then be efficiently encoded by VLQ. For example, it maps `0, -1, 1, -2, 2` to `0, 1, 2, 3, 4`.

6. What is the maximum number VLQ can encode?

Theoretically, there is no limit; you can keep adding bytes to represent ever-larger numbers. In practice, the limit is determined by the data type you are decoding into. Our implementation decodes into a UInt32, so the practical limit is the maximum value of a 32-bit unsigned integer (4,294,967,295), which requires 5 VLQ bytes to represent.

7. Are there built-in VLQ libraries in Crystal?

While the Crystal ecosystem has various "shards" (libraries) for data serialization, many high-performance formats like Protocol Buffers will have their own internal implementations of Varints (their version of VLQ). The purpose of this kodikra module is not just to use a library, but to understand the fundamental bitwise logic behind data compression, a skill that is transferable across many languages and problem domains.

---

Conclusion: Beyond the Code

We've journeyed deep into the world of Variable Length Quantity encoding, moving from high-level theory to a practical, robust implementation in Crystal. You've seen how a few clever bitwise operations—&, |, and >>—can be orchestrated to create a powerful data compression algorithm. More importantly, you now understand the "why" behind VLQ—its critical role in making data formats for music, web development, and distributed systems fast and compact.

Mastering concepts like VLQ separates a good programmer from a great one. It demonstrates an ability to think about efficiency at the lowest levels and to write code that is not only correct but also performant and resource-conscious. This is the kind of deep, practical knowledge that forms the foundation of a successful software engineering career.

Disclaimer: The code in this article is written for Crystal 1.12+ and is based on the exclusive learning curriculum of kodikra.com. While the concepts are universal, syntax and library availability may differ in other language versions or environments.

---

Published by Kodikra — Your trusted Crystal learning resource.