Example: Encode and Decode

In this example we show how to use the low-level API of kodo-slide to implement encoding and decoding.

The following classes from kodo-slide will be used:

• The class encoder and class decoder classes exposes a low-level API of a sliding window code giving you full control over the operations.
• The struct stream is a simple adapter over a std::deque but with an API which matches the one used in kodo-slide.
• The next helper we will use is the struct rate_controller. This object will allow us to specify in which pattern to generate repair/redundancy. See also Parameter selection.

In this example we will walk through the basic functionality and discuss how to use it.

Note

If you see an unfamiliar term used, try to visit the Definitions section and you should find a description.

#include <algorithm>
#include <iostream>
#include <memory>
#include <vector>

// The first thing we need to do is to include the
// relevant header files.

// Encoder and decoders
#include <kodo_slide/decoder.hpp>
#include <kodo_slide/encoder.hpp>

// Helpers
#include <kodo_slide/rate_controller.hpp>
#include <kodo_slide/stream.hpp>

// In a real application we would be encoding and
// decoding symbols from some real-life source, such
// as a video feed or network card. In this example we
// will just imagine having such a source and produce
// some random data (for this purpose we implement some helpers):

using symbol_ptr = std::unique_ptr<std::vector<uint8_t>>;

symbol_ptr make_symbol(uint32_t size)
{
    symbol_ptr data = std::make_unique<std::vector<uint8_t>>();
    data->resize(size);
    return data;
}

symbol_ptr generate_symbol(uint32_t size)
{
    symbol_ptr data = make_symbol(size);

    // Just fill with some random data
    std::generate(data->begin(), data->end(), rand);
    return data;
}

int main()
{
    // Set the window size (this is the number of symbols included
    // in an encoded symbol).
    uint64_t window_symbols = 20U;

    // Set the capacity of the decoder (this is the number of
    // encoded symbols that are used in the decoding process).
    uint64_t decoder_capacity = 40U;

    // The finite field
    kodo_slide::finite_field field = kodo_slide::finite_field::binary8;

    // The size of a symbol in bytes
    uint64_t symbol_size = 160U;

    // Create the encoder and decoder
    kodo_slide::encoder encoder;
    kodo_slide::decoder decoder;

    encoder.configure(field, symbol_size);
    decoder.configure(field, symbol_size);

    // Buffers needed to store coding coefficients and symbol.
    std::vector<uint8_t> coefficients;
    std::vector<uint8_t> symbol;

    // Containers for keeping memory alive and track the
    // state of the different symbols.
    kodo_slide::stream<symbol_ptr> input_symbols;
    kodo_slide::stream<symbol_ptr> output_symbols;
    kodo_slide::stream<bool> decoded_symbols;

    // Control the amount of repair/redundancy generated
    // n: Total number of symbols
    // k: Number of source symbols out of the total
    //
    // To get a good decoding performance the rate needs to be
    // lower than or equal to the packet loss probability. In
    // this case our rate is k/n = 4/10 = 40% and our packet
    // loss probability is 50% so this should be sufficient for
    // a good decoding performance.
    //
    // The above serves as a rule of thumb - more rigorous mathematics
    // can be used to derive tighter bounds given a certain
    // decoding probability.

    uint32_t n = 10;
    uint32_t k = 4;

    kodo_slide::rate_controller rate {n, k};

    // Maximum number of interations
    uint32_t max_iterations = 1000U;
    uint32_t iterations = 0;

    // Counter for keeping track of the number of decoded symbols
    uint32_t generated = 0;
    uint32_t decoded = 0;

    while (iterations < max_iterations)
    {

        // Manage the encoder's window
        if (!rate.send_repair())
        {
            if (encoder.window_symbols() == window_symbols)
            {
                // If window is full - pop a symbol before pushing a new one
                encoder.pop_back_symbol();
                input_symbols.pop_back();
            }

            // Create a new source symbol
            auto symbol = generate_symbol(symbol_size);

            // Add the symbol's memory to the encoder
            encoder.push_front_symbol(symbol->data(), symbol->size());

            // Store the symbol
            input_symbols.push_front(std::move(symbol));

            ++generated;
        }

        // Choose a seed for this encoding
        uint64_t seed = rand();

        // Encode a symbol
        encoder.set_window(encoder.stream_lower_bound(),
                           encoder.stream_symbols());

        // Resize buffers
        coefficients.resize(encoder.coefficient_vector_size());
        symbol.resize(encoder.max_write_size());

        // Set the seed used to generate the coding coefficients and
        // encode the symbol
        encoder.set_seed(seed);
        encoder.generate(coefficients.data());
        encoder.write_symbol(symbol.data(), coefficients.data());

        // Update loop state
        ++iterations;
        rate.advance();

        if (rand() % 2)
        {
            // Simulate 50% packet loss
            continue;
        }

        // Move the decoders's window / stream if needed
        //
        // If the encoder includes symbols in its window that the decoder
        // does not have. We need to update the state of the decoder.
        // In the following we will go through two cases:
        //
        // Case 1: The decoder can move its stream front by adding more
        //         symbols. This is possible if it has not reached the
        //         maximum capacity yet.
        //
        // Case 2: If the decoder is a maximum capacity it needs to
        //         slide its window/stream - dropping symbols that are
        //         now too "old".

        if (decoder.stream_upper_bound() < encoder.stream_upper_bound())
        {
            // If we can add more memory to the decoder lets do that
            while (decoder.stream_symbols() < decoder_capacity)
            {
                // Create a new symbol
                auto symbol = make_symbol(decoder.max_symbol_size());

                // Add the symbol's memory to the decoder
                decoder.push_front_symbol(symbol->data());

                // Store the symbol
                output_symbols.push_front(std::move(symbol));

                // Track the decoded state of this symbol
                decoded_symbols.push_front(false);
            }
        }

        // Check if the decoder's stream is still behind the encoder
        while (decoder.stream_upper_bound() < encoder.stream_upper_bound())
        {
            // Remove the "oldest" symbol
            decoder.pop_back_symbol();

            auto symbol = std::move(output_symbols.back());
            output_symbols.pop_back();

            decoded_symbols.pop_back();

            // Recycle the symbol
            decoder.push_front_symbol(symbol->data());
            output_symbols.push_front(std::move(symbol));
            decoded_symbols.push_front(false);
        }

        // Consume the encoded symbol
        decoder.set_window(encoder.window_lower_bound(),
                           encoder.window_symbols());

        decoder.set_seed(seed);
        decoder.generate(coefficients.data());
        decoder.read_symbol(symbol.data(), symbol.size(), coefficients.data());

        // New symbols may now be decoded.
        for (uint64_t i = 0; i < decoder.stream_symbols(); ++i)
        {
            uint64_t index = i + decoder.stream_lower_bound();

            if (!decoder.is_symbol_decoded(index))
            {
                // This symbol has not yet been decoded
                continue;
            }

            if (decoded_symbols[index] == true)
            {
                // We've already marked this symbol decoded
                continue;
            }

            ++decoded;
            decoded_symbols[index] = true;

            std::cout << "Decoded index = " << index << "\n";
        }
    }

    std::cout << "Generated symbols = " << generated << "\n";
    std::cout << "Decoded symbols = " << decoded << "\n";

    return 0;
}