---

Mastering Variable Length Quantity (VLQ) in Awk: From Zero to Hero

Variable Length Quantity (VLQ) is a universal encoding scheme that represents integers using a variable number of bytes. This comprehensive guide provides a complete walkthrough for implementing both VLQ encoding and decoding from scratch in Awk, perfect for optimizing data streams and file sizes in text processing tasks.

Ever found yourself staring at a massive data file, wondering how you could possibly make it smaller without losing information? Whether you're dealing with MIDI music sequences, debugging information in web source maps, or parsing data from Google's Protocol Buffers, the challenge is the same: representing numbers efficiently. Storing every number as a fixed 32-bit or 64-bit integer can be incredibly wasteful, especially when most of your numbers are small.

This is where the genius of Variable Length Quantity (VLQ) encoding comes into play. It’s a clever technique that uses fewer bytes for smaller numbers and more bytes for larger ones, dramatically shrinking data size. You might think implementing such a low-level, bit-twiddling algorithm requires a systems language like C or Rust. But what if you could do it all within the elegant and powerful confines of a command-line text processor? In this deep dive, we'll show you how to master VLQ using Awk, a tool you probably already use, and unlock its hidden potential for handling binary-like data representations.

---

What Exactly is Variable Length Quantity (VLQ)?

At its core, VLQ is a method for encoding an arbitrarily large integer into a sequence of bytes. Its primary goal is space efficiency. Instead of using a fixed size (like 4 bytes for a 32-bit integer), VLQ uses as many bytes as needed, and no more.

The magic lies in how each byte is structured. An 8-bit byte is split into two parts:

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

By chaining these 7-bit payloads together, you can reconstruct the original integer. Small numbers (those less than 128) can be stored in a single byte, while larger numbers seamlessly expand into multiple bytes. This makes VLQ ideal for data formats where small integer values are far more common than large ones.

Key Concepts and Entities

• Integer Encoding: The fundamental process of converting numbers into a specific byte format.
• Most Significant Bit (MSB): The bit in a binary number with the greatest value, used in VLQ as the continuation flag.
• 7-bit Payload: The portion of each byte that carries the actual data of the number.
• Data Serialization: The process of converting data structures or object state into a format that can be stored or transmitted. VLQ is a form of integer serialization.
• Common Use Cases: You'll find VLQ or its close cousin, LEB128, in many technologies, including MIDI files for musical notation, DWARF debugging formats, and WebAssembly binaries.

---

Why Implement VLQ in Awk?

This is a fair question. Awk is renowned for its text-processing prowess—slicing, dicing, and reporting on text files. It might seem like an unusual choice for bit-level manipulation. However, modern implementations, specifically GNU Awk (gawk), come equipped with a powerful set of bitwise functions that make this task not only possible but surprisingly elegant.

Here’s why Awk is a compelling choice for this problem from the kodikra Awk 6 learning path:

• Stream Processing Power: Awk is designed to process data line by line, making it perfect for integrating into command-line pipelines. You can decode a VLQ stream on the fly as it comes from another process without loading the entire file into memory.
• Prototyping and Scripting: Writing a quick Awk script is often faster than setting up a compiled project in C++ or Java. It's an excellent tool for rapid prototyping and data exploration.
• Built-in Associative Arrays: Awk's native support for associative arrays simplifies the handling of byte sequences and decoded numbers, making the code clean and readable.
• Educational Value: Implementing a low-level algorithm like VLQ in a high-level scripting language forces you to understand the mechanics deeply. It's a fantastic exercise from the kodikra.com curriculum that sharpens your problem-solving skills.

To be clear, you will need GNU Awk (gawk) for its bitwise functions like and(), or(), lshift() (left shift), and rshift() (right shift). Standard Awk implementations may not support these. You can check your version with awk --version.

---

How Does VLQ Encoding Work? A Step-by-Step Guide

Let's break down the encoding process with a concrete example. Suppose we want to encode the number 300.

1. Convert to Binary: First, we represent 300 in binary.
   300 in decimal is 100101100 in binary.
2. Chunk into 7-Bit Groups: We split the binary number into 7-bit groups, starting from the rightmost bit (the least significant). If the leftmost group doesn't have 7 bits, we pad it with leading zeros.
   100101100 becomes 0000010 and 0101100.
3. Reverse the Groups: The VLQ format stores the least significant chunks first. So we reverse the order of our groups.
   Group 1: 0101100
   Group 2: 0000010
4. Set the Continuation Bit (MSB): Now, we add the 8th bit (the MSB) to each group to form our final bytes.
   • For every group except the last one, we set the MSB to 1.
   • For the very last group, we set the MSB to 0.
   
   Group 1 (not the last): 10101100
   Group 2 (the last): 00000010
5. Final Byte Sequence: Converting these binary values back to hexadecimal or decimal gives us the final encoded sequence.
   10101100 is 0xAC or 172.
   00000010 is 0x02 or 2.
   So, 300 is encoded as the byte sequence [172, 2].

Encoding Logic Flowchart

This ASCII diagram illustrates the logical flow of the encoding algorithm.

    ● Start with an Integer (e.g., 300)
    │
    ▼
  ┌───────────────────┐
  │ Initialize empty   │
  │ byte array         │
  └─────────┬─────────┘
            │
            ▼
  ┌───────────────────┐
  │ Extract lowest 7   │
  │ bits (num & 0x7F)  │
  │ and store them     │
  └─────────┬─────────┘
            │
            ▼
  ┌───────────────────┐
  │ Right-shift num    │
  │ by 7 bits          │
  └─────────┬─────────┘
            │
            ▼
    ◆ Is num > 0 ?
   ╱           ╲
  Yes           No
  ├──────────────┘
  │ (Loop back)
  │
  ▼
┌───────────────────┐
│ Reverse the array  │
│ of 7-bit chunks    │
└─────────┬─────────┘
          │
          ▼
┌───────────────────┐
│ Iterate through    │
│ chunks, adding the │
│ continuation bit   │
│ (0x80) to all but  │
│ the last one.      │
└─────────┬─────────┘
          │
          ▼
    ● End (Final byte sequence)

---

How Does VLQ Decoding Work? Rebuilding the Number

Decoding is the reverse process. We read bytes one by one, strip their continuation bits, and reassemble the 7-bit payloads into the original integer.

Let's decode our example sequence: [172, 2] (or [0xAC, 0x02]).

1. Initialize Result: Start with a result variable set to 0.
2. Read the First Byte (172):
   • Binary representation: 10101100.
   • Check the MSB. It's 1, which means more bytes will follow.
   • Extract the 7-bit payload: 0101100.
   • Add this payload to our result. Result is now 0101100.
3. Read the Second Byte (2):
   • Binary representation: 00000010.
   • Check the MSB. It's 0, which means this is the last byte for this number.
   • Extract the 7-bit payload: 0000010.
   • Shift and Combine: Before adding the new payload, we must make room for it. We shift our current result 7 bits to the left: result = result << 7.
     0101100 becomes 01011000000000.
   • Now, combine the new payload with the shifted result using a bitwise OR.
     01011000000000 | 0000010 = 100101100.
4. Final Result: Since the last byte had a continuation bit of 0, the process for this number is complete. The binary result is 100101100, which is 300 in decimal. We successfully decoded the number!

Decoding Logic Flowchart

This diagram shows how to reconstruct an integer from a VLQ byte stream.

    ● Start with Byte Stream
    │
    ▼
  ┌───────────────────┐
  │ Initialize         │
  │ result_number = 0  │
  └─────────┬─────────┘
            │
            ▼
  ┌───────────────────┐
  │ Read next byte     │
  │ from stream        │
  └─────────┬─────────┘
            │
            ▼
  ┌───────────────────┐
  │ Left-shift         │
  │ result_number by 7 │
  └─────────┬─────────┘
            │
            ▼
  ┌───────────────────┐
  │ Extract 7-bit      │
  │ payload (byte & 0x7F)│
  └─────────┬─────────┘
            │
            ▼
  ┌───────────────────┐
  │ Add payload to     │
  │ result_number      │
  │ (result | payload) │
  └─────────┬─────────┘
            │
            ▼
    ◆ Is MSB of byte == 0 ?
   ╱           ╲
  Yes           No
  │              │
  ▼              ▼
[Number is     (Loop back to
 complete]     read next byte)
  │
  ▼
 ● End (Decoded Integer)

---

The Complete Awk Implementation

Here is the full, commented Awk script for both encoding and decoding VLQ. This solution is designed to be robust and clear, making it a perfect reference from the kodikra.com exclusive curriculum. Save this code in a file named vlq.awk.

#!/usr/bin/gawk -f

# vlq.awk - A complete implementation of Variable Length Quantity encoding and decoding.
# This script requires GNU Awk (gawk) for its bitwise functions.
# Part of the exclusive kodikra.com learning materials.

# Helper function to print an array of numbers for debugging/output.
function print_array(arr, n, prefix) {
    printf "%s: [", prefix
    for (i = 1; i <= n; i++) {
        printf "%s%d", (i > 1 ? ", " : ""), arr[i]
    }
    print "]"
}

# encode(numbers, n_in, bytes, n_out)
# Encodes an array of integers into a VLQ byte array.
# @param numbers: Input array of integers to encode.
# @param n_in: Number of elements in the numbers array.
# @param bytes: Output array where the resulting bytes will be stored.
# @return: The number of bytes in the output array.
function encode(numbers, n_in,   bytes,   i, num, chunks, n_chunks, j, byte) {
    # We use local variables in the function signature as per Awk convention.
    delete bytes
    n_out = 0

    for (i = 1; i <= n_in; i++) {
        num = numbers[i]
        
        # Handle the edge case of zero
        if (num == 0) {
            bytes[++n_out] = 0
            continue
        }

        # Step 1: Deconstruct number into 7-bit chunks
        delete chunks
        n_chunks = 0
        while (num > 0) {
            chunks[++n_chunks] = and(num, 0x7F) # Extract lowest 7 bits
            num = rshift(num, 7)                # Shift right by 7
        }

        # Step 2: Assemble bytes with continuation bits
        # We iterate backwards through chunks because the last chunk (originally the MSBs)
        # gets the '0' continuation bit, and all others get '1'.
        for (j = n_chunks; j >= 1; j--) {
            byte = chunks[j]
            if (j > 1) { # If it's not the last chunk (which is first in our reversed list)
                byte = or(byte, 0x80) # Set the continuation bit
            }
            bytes[++n_out] = byte
        }
    }
    return n_out
}


# decode(bytes, n_in, numbers, n_out)
# Decodes a VLQ byte array into an array of integers.
# @param bytes: Input array of VLQ-encoded bytes.
# @param n_in: Number of elements in the bytes array.
# @param numbers: Output array where the decoded integers will be stored.
# @return: The number of integers in the output array.
function decode(bytes, n_in,   numbers,   i, current_num, byte, has_continuation, incomplete_error) {
    delete numbers
    n_out = 0
    current_num = 0
    incomplete_error = 0

    for (i = 1; i <= n_in; i++) {
        byte = bytes[i]
        
        # Check for overflow before shifting. Awk handles large numbers, but it's good practice.
        # A 64-bit unsigned int can be represented by at most 10 VLQ bytes.
        # We can add more robust checks if needed.
        
        # Combine the payload
        current_num = lshift(current_num, 7)
        current_num = or(current_num, and(byte, 0x7F))

        has_continuation = and(byte, 0x80)
        
        if (!has_continuation) {
            # This is the last byte of the number
            numbers[++n_out] = current_num
            current_num = 0 # Reset for the next number
            incomplete_error = 0 # Clear flag as we completed a number
        } else {
            # We expect more bytes
            incomplete_error = 1
        }
    }
    
    # Error handling: if the last byte had a continuation bit, the sequence is incomplete.
    if (incomplete_error) {
        print "Error: Incomplete VLQ sequence." > "/dev/stderr"
        return -1 # Indicate error
    }

    return n_out
}

# BEGIN block: A simple test harness to demonstrate functionality.
BEGIN {
    print "--- VLQ Encoding/Decoding Demo (kodikra.com) ---"
    
    # Test Case 1: Simple numbers
    print "\nTest Case 1: Simple Numbers"
    in_nums1[1] = 0x7F # 127
    in_nums1[2] = 0x80 # 128
    n1 = 2
    print_array(in_nums1, n1, "Input Numbers")
    
    n_bytes1 = encode(in_nums1, n1, out_bytes1)
    print_array(out_bytes1, n_bytes1, "Encoded Bytes") # Expected: [127], [129, 0] -> [127, 129, 0]

    n_decoded1 = decode(out_bytes1, n_bytes1, decoded_nums1)
    print_array(decoded_nums1, n_decoded1, "Decoded Numbers")

    # Test Case 2: A larger number
    print "\nTest Case 2: Multi-byte Number"
    in_nums2[1] = 300
    n2 = 1
    print_array(in_nums2, n2, "Input Numbers")
    
    n_bytes2 = encode(in_nums2, n2, out_bytes2)
    print_array(out_bytes2, n_bytes2, "Encoded Bytes") # Expected: [172, 2]

    n_decoded2 = decode(out_bytes2, n_bytes2, decoded_nums2)
    print_array(decoded_nums2, n_decoded2, "Decoded Numbers")

    # Test Case 3: Multiple numbers in a sequence
    print "\nTest Case 3: Sequence of Numbers"
    in_nums3[1] = 65535 # 0xFFFF
    in_nums3[2] = 4096  # 0x1000
    n3 = 2
    print_array(in_nums3, n3, "Input Numbers")
    
    n_bytes3 = encode(in_nums3, n3, out_bytes3)
    print_array(out_bytes3, n_bytes3, "Encoded Bytes") # Expected: [255, 255, 3], [160, 0] -> [255, 255, 3, 160, 0]

    n_decoded3 = decode(out_bytes3, n_bytes3, decoded_nums3)
    print_array(decoded_nums3, n_decoded3, "Decoded Numbers")
    
    # Test Case 4: Incomplete sequence error
    print "\nTest Case 4: Incomplete Sequence"
    err_bytes[1] = 129 # This is 0x81, which implies another byte should follow
    n_err = 1
    print_array(err_bytes, n_err, "Input Bytes")
    n_decoded_err = decode(err_bytes, n_err, decoded_err_nums)
    if (n_decoded_err == -1) {
        print "Correctly identified incomplete sequence."
    }
    
    exit
}

Running the Script

To execute this script, make sure you have gawk installed. Then, run it from your terminal:

$ gawk -f vlq.awk

You should see the output of the test cases, confirming that the encoding and decoding functions work correctly.

Code Walkthrough

The encode() Function

1. Initialization: The function starts by clearing the output bytes array to ensure a clean slate.
2. Main Loop: It iterates through each num in the input numbers array.
3. Chunking Loop: Inside, a while (num > 0) loop systematically deconstructs the number.
   • and(num, 0x7F) performs a bitwise AND with 01111111, effectively masking off and capturing the lowest 7 bits.
   • rshift(num, 7) shifts the number 7 bits to the right, discarding the bits we just processed and preparing the next 7 bits for the next iteration.
   • The 7-bit chunks are stored in a temporary chunks array.
4. Assembly: After deconstruction, the code iterates through the chunks array in reverse. This is a crucial step because the VLQ format requires the least significant parts of the number to appear first in the byte stream.
   • or(byte, 0x80) sets the MSB to 1 for all bytes that are not the last one, marking them as continuation bytes.
   • The final, fully formed bytes are added to the main output bytes array.

The decode() Function

1. Initialization: It clears the output numbers array and initializes a current_num variable to 0. This variable will accumulate the 7-bit payloads.
2. Byte Loop: The function iterates through each byte in the input bytes array.
3. Reassembly Logic:
   • lshift(current_num, 7) is the key operation. Before adding the next payload, it shifts the bits of the number-in-progress 7 places to the left, making room for the new 7 bits.
   • or(current_num, and(byte, 0x7F)) first extracts the 7-bit payload from the current byte (by stripping the MSB) and then merges it into the space created by the left shift.
4. Continuation Check: and(byte, 0x80) checks if the continuation bit is set. If it's 0, the number is complete. The accumulated current_num is added to the output numbers array, and current_num is reset to 0 for the next sequence.
5. Error Handling: If the loop finishes while the last byte still had its continuation bit set, it means the sequence was cut off. The function prints an error to stderr and returns -1.

---

Pros, Cons, and Alternative Approaches

Like any technology, VLQ has its trade-offs. It's essential to understand them to know when it's the right tool for the job.

Advantages and Disadvantages of VLQ

Pros (Advantages)	Cons (Disadvantages)
Space Efficiency: Highly efficient for data streams where small integers (0-127) are common, saving significant space over fixed-width integers.	Inefficiency for Large Numbers: A 64-bit number can take up to 10 bytes, whereas a fixed-width representation would only take 8.
Arbitrary Size: Can represent integers of any size, not limited by 32-bit or 64-bit boundaries.	Processing Overhead: The bitwise shifting and masking required for encoding/decoding adds computational overhead compared to simply reading a fixed-width integer.
Self-Terminating: The data stream is self-describing. You don't need to store the length of the number separately; the continuation bits tell you when the number ends.	Not Seekable: You cannot jump to the Nth number in a VLQ stream without parsing all the preceding numbers, as each number has a variable length.

Alternative Approach: LEB128

A very similar encoding is LEB128 (Little-Endian Base 128). It's functionally almost identical to the VLQ described here and is used in DWARF debugging formats and WebAssembly. The primary difference is often just in the name and context in which it's used. The algorithm of grouping into 7-bit payloads with a continuation bit is the same.

For a different take within Awk, one could implement the logic using string manipulation on binary representations (e.g., converting numbers to strings of "0"s and "1"s). However, this would be significantly slower and more complex than using gawk's native bitwise functions, which are implemented in C under the hood and are highly optimized.

---

Frequently Asked Questions (FAQ)

1. What is the maximum number that can be encoded with VLQ?

Theoretically, there is no maximum. The format is designed to be extensible to represent an integer of any size by simply adding more bytes to the sequence. In practice, the limit is determined by the system's memory and the data types of the programming language used (Awk, for instance, uses double-precision floats or arbitrary-precision integers depending on the version and compilation options).

2. Is VLQ the same as UTF-8?

No, but they share a similar design philosophy. Both are variable-length encodings where the leading bits of a byte indicate how many subsequent bytes are part of the sequence. UTF-8 is for encoding Unicode characters, while VLQ is for encoding generic integers.

3. Why is the continuation bit the Most Significant Bit (MSB)?

Placing the continuation flag in the MSB makes it easy and fast to check with a single bitwise AND operation (& 0x80) or a comparison (>= 128). This is a common and efficient pattern in low-level data parsing.

4. Can VLQ handle negative numbers?

Not directly. The standard VLQ algorithm is for unsigned integers. To handle signed (positive and negative) numbers efficiently, a technique called ZigZag encoding is often used first. ZigZag maps signed integers to unsigned integers in a way that small negative numbers become small positive numbers, which can then be efficiently encoded with VLQ. For example, it maps [0, -1, 1, -2, 2] to [0, 1, 2, 3, 4].

5. How does Awk handle binary data?

Awk is fundamentally text-oriented. It doesn't have a native `byte` data type. In our implementation, we represent "bytes" as standard Awk numbers (in the range 0-255). The bitwise functions in `gawk` operate on the integer representations of these numbers, allowing us to simulate byte-level manipulation effectively.

6. Is this Awk implementation compatible with all versions of Awk?

No. This implementation relies heavily on bitwise functions (and, or, lshift, rshift) which are specific extensions available in GNU Awk (gawk). It will not run on older, standard implementations of Awk like `nawk` or `mawk`.

7. Are there more efficient alternatives to VLQ?

Yes, depending on the data's statistical distribution. For example, if your data stream contains long runs of identical numbers, Run-Length Encoding (RLE) might be better. For more general-purpose compression, algorithms like Huffman coding or Arithmetic coding are more powerful but also more complex. VLQ's strength is its simplicity and low overhead for encoding individual integers.

---

Conclusion: Unlocking Awk's Hidden Power

We've journeyed from the fundamental theory of Variable Length Quantity to a complete, practical implementation in GNU Awk. You've seen how a seemingly simple text-processing tool can be leveraged to perform complex, low-level bitwise operations, proving its versatility beyond conventional line-by-line processing. Mastering this technique not only adds a powerful tool to your command-line arsenal but also deepens your understanding of data representation and efficiency.

The ability to encode and decode VLQ streams directly in a pipeline makes Awk a surprisingly potent choice for data transformation tasks, especially when prototyping or working in a shell-centric environment. The principles learned here are universal and will serve you well, whether you're parsing binary file formats, optimizing network protocols, or simply satisfying your curiosity about how data is efficiently managed under the hood.

Ready to continue your journey? Explore our full Awk 6 learning path to tackle more advanced challenges, or dive deeper into our Awk tutorials to solidify your foundational skills.

Disclaimer: The provided Awk code is compatible with GNU Awk (gawk) 4.0+ due to its use of bitwise functions. Functionality is not guaranteed on other Awk implementations. Always verify your environment for compatibility.

---

Published by Kodikra — Your trusted Awk learning resource.