coding.cpp

#include <vector>
#include <cstdint>
#include <stdlib.h>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <numeric>

#include <cstddef>
#include <string>

#include "../doc/cxxopts.hpp"
#include "polar/polar_coder.h"
#include "channel/simple_channel.h"
#include "zfec/fec.h"
#include "zcode.h"
#include "util.h"
#include "coding.h"

using namespace std;

int
main(int argc, char **argv)
{
    Coding ob(argc, argv);
    ob.applyCodes();
#ifdef REVERSE
    cout << endl << endl << "Reverse:" << endl << endl;
    ob.reverse();
#endif
}

void
Coding::applyCodes()
{
    uint8_t** hlp           = (uint8_t**) malloc(2*k * sizeof(uint8_t*));
    uint8_t** intermediate  = (uint8_t**) malloc(k * sizeof(uint8_t*));
    uint8_t** zfec_in       = (uint8_t**) malloc(k * sizeof(uint8_t*));

    out_vector              = (vector<uint8_t> **) malloc(2*k * sizeof(vector<uint8_t> *));
    unsigned int* indices   = (unsigned int *) malloc(k * sizeof(unsigned int)); // Decode only
    bool need_to_transform = false;

    if(!hlp
        || !intermediate
        || !zfec_in
        || !out_vector
        || !indices
      ) throw new bad_alloc();

    switch(coding_mode)
    {
        case MODE_ENCODE:
            gf_out = ZCode::encode(
                k,
                m,
                raw_bytes,
                debug_mode);
#ifdef TEST_
            cout << "ZFEC" << endl;
            for(int i=0; i<k*2; i++)
            {
                cout << endl << endl << "ZFec in:" << endl;
                for(int j=0; j<m && i<k; j++)
                    cout << hex << "|" << (unsigned short) raw_bytes[i][j];
                cout << endl << "ZFec out:" << endl;
                for(int j=0; j<m; j++)
                    cout << hex << "|" << (unsigned short) gf_out[i][j];
                cout << endl
            }
#endif

            for(unsigned short i=0; i<2*k; i++)
            {
                hlp[i] = (uint8_t *) malloc((m+1) * 8 * sizeof(uint8_t));
                if(!hlp[i]) throw new bad_alloc();

                uint8_t seq = (uint8_t) i;
                if(!unrollBits(&seq, 1, hlp[i]) || !unrollBits(gf_out[i], m, &hlp[i][8]))
                    throw new bad_exception();

                out_vector[i] = polarCode(
                    hlp[i],
                    8 * (size_t) (m+1),
                    code_len,
                    data_len,
                    log2_code,
                    false,
                    debug_mode);
#ifdef TEST
                cout << endl << "Polar in:" << endl;
                for(int j=0; j<m*8; j++)
                    cout << hex << (unsigned short) hlp[i][j];
                cout << endl << endl;
#endif
            }

#ifdef TEST
            cout << "Polar out:" << endl;
#endif
            for(int i=0; i<k*2; i++)
            {
                printHexStringSingleVector(out_vector[i]);
                cout << endl;
            }
            for(int i=0; i<2*k; i++)
                free(hlp[i]);
            break;
        case MODE_DECODE:
            for(int i=0; i<k; i++)
            {
                // Calculate input length (has to be this value!)
                size_t num_words = (8*(m+1) - 1) / data_len + 1;
#ifdef TEST
                cout << "#Words: " << num_words
                    << " #bits: " << num_words * code_len
                    << " #raw_len: " << num_words * code_len / 8
                    << endl;
#endif

                hlp[i] = (uint8_t *) malloc(num_words * code_len * sizeof(uint8_t));
                if(!hlp[i]) throw new bad_alloc();

                if(!unrollBits(raw_bytes[i], num_words * code_len / 8, hlp[i]))
                    throw new bad_exception();

                out_vector[i] = polarCode(
                    hlp[i],
                    num_words * code_len,
                    code_len,
                    data_len,
                    log2_code,
                    true,
                    debug_mode);
#ifdef TEST
                printHexStringSingleVector(out_vector[i]);
                cout << endl;
#endif
            }
#ifdef TEST
            cout << "Polar decoding success!" << endl
                << "Now fold to bytes" << endl << endl;
#endif
            for(size_t i=0; i<k; i++)
            {
                intermediate[i] = foldToBytes(out_vector[i], m+2);
                if(!intermediate[i]) throw new bad_function_call();

                indices[i] = intermediate[i][0];
                zfec_in[i] = &intermediate[i][1];
#ifdef TEST
                cout << "out_vector[" << i << "]->size() = " << dec << out_vector[i]->size() << endl;
                cout << "Block[" << i << "] with length " << out_vector[i]->size()/8 << ":" << endl;
                cout << indices[i] << " ";
                for(unsigned short j=0; j<m; j++)
                {
                    if((zfec_in[i][j] & 0xf0) == 0)
                        cout << "0";
                    cout << hex << (unsigned short) zfec_in[i][j];
                }
                cout << endl << endl;
#endif
                free(hlp[i]);
            }

            // Check wether on or more blocks are at wrong places
            for(unsigned short i=0; i<k; i++)
                if(indices[i] < k && indices[i] != i)
                {
                    need_to_transform = true;
                    break;
                }

            if(need_to_transform)
            {
                unsigned int *new_indices   = (unsigned int *) malloc(k *   sizeof(unsigned int));
                uint8_t     **new_zfec_in   = (uint8_t **)     malloc(k *   sizeof(uint8_t*));
                uint16_t     *check_array   = (uint16_t *)     malloc(2*k * sizeof(uint16_t));

                if(!new_indices || !new_zfec_in || !check_array)
                    throw new bad_alloc();

                for(uint16_t i=0; i<2*k; i++)
                {
                    check_array[i]   = 2*k;
                    new_indices[i/2] = 2*k;
                }


                for(uint16_t i=0; i<k; i++)
                {
                    if(check_array[indices[i]] != 2*k)
                        throw new runtime_error("Received two or more blocks with the same sequence number.");
                    check_array[indices[i]] = i;
                }

                // Sort the blocks w/ seq_num < k
                for(uint16_t i=0; i<k; i++)
                {
                    if(indices[i] == i)
                    {
                        // Identity case
                        new_indices[i] = i;
                        new_zfec_in[i] = zfec_in[i];
                    } else if(check_array[i] != 2*k)
                    {
                        // Move an index to the correct spot
                        new_indices[i] = i;
                        new_zfec_in[i] = zfec_in[check_array[i]];
                    } else
                        // Move any index here
                        for(uint16_t j=k; j<2*k; j++)
                            if(check_array[j] != 2*k)
                            {
                                new_indices[i] = j;
                                new_zfec_in[i] = zfec_in[check_array[j]];
                                check_array[j] = 2*k;
                                break;
                            }
                }

                // IMPORTANT: free has to happen before the assignment!
                free(check_array);
                free(indices);
                free(zfec_in);
                indices = new_indices;
                zfec_in = new_zfec_in;
            }

            gf_out = ZCode::decode(
                k,
                m,
                zfec_in,
                indices,
                debug_mode);

            // decode only restores missing blocks
            for(unsigned int i = 0; i<k; i++)
            {
                auto data = (indices[i] == i) ? zfec_in[i] : gf_out[i];
                for(int j = 0; j<m; j++)
                {
                    // if upper 4Bit are zeros, print an extra zero
                    if((data[j] & 0xf0) == 0) cout << 0;
                    cout << hex << (unsigned short) data[j];
                }
                cout << endl;
            }

            for(unsigned int i = 0; i<k; i++)
                free(intermediate[i]);

            break;
        default:
            cerr << "coding_mode unsupported." << endl;
            exit(EXIT_FAILURE);
    }
    //if(out_vector == NULL)
    if(gf_out == NULL)
    {
        // ERROR
        cerr << "An error has occurred." << endl;
    } else {
        // SUCCESS
    }

    free(hlp);
    free(intermediate);
    free(zfec_in);
    free(indices);
}

Coding::Coding(int argc, char** argv)
{

    cxxopts::Options options("Code", "Encodes and decodes data");

    options.add_options()
        ("d", "polar data-length",          cxxopts::value<size_t>()->default_value("30"))
        ("l", "polar code-length",          cxxopts::value<size_t>()->default_value("5"))
        ("k", "zfec num required packets",  cxxopts::value<unsigned short>()->default_value("4"))
        ("m", "zfec data length",           cxxopts::value<unsigned short>()->default_value("65000"))
        ("e,decode", "mode enc or dec")
        ("v,verbose", "verbose output");

    // Parse commandline
    auto result = options.parse(argc, argv);
    debug_mode  = result.count("v");
    coding_mode = result.count("e") ? MODE_DECODE : MODE_ENCODE;

    // zfec
    k           = result["k"].as<unsigned short>();
    m           = result["m"].as<unsigned short>();

    // polar
    data_len    = result["d"].as<size_t>();
    log2_code   = result["l"].as<size_t>();
    code_len    = 1 << log2_code;

    if(code_len <= data_len)
    {
        cerr << "invalid input. l: " << log2_code << ", d: " << data_len << endl;
        exit(EXIT_FAILURE);
    }

    raw_bytes = (uint8_t **) malloc(k * sizeof(uint8_t*));
    if(!raw_bytes) throw new bad_alloc();

    for(int i=0; i<k; i++)
    {
        raw_bytes[i] = inputToBytes();
        if(!raw_bytes[i]) throw new runtime_error("Insufficiently many blocks granted.");
    }

#ifdef TEST
    cout << ((coding_mode == 0) ? "En" : "De") << "coding mode" << endl << endl;
#endif
}

Coding::~Coding()
{
    for(int i=0; i<k; i++)
        free(raw_bytes[i]);
    free(raw_bytes);

    int lim = (coding_mode == MODE_ENCODE) ? 2*k : k;
    for(int i=0; i<lim; i++)
        delete out_vector[i];

    ZCode::ZFfree(gf_out, k, m, coding_mode == MODE_DECODE);
    free(out_vector);
}

void
Coding::reverse()
{
    throw new runtime_error("Operation not supported. (reverse)");
    //coding_mode = (coding_mode == MODE_ENCODE) ? MODE_DECODE : MODE_ENCODE;
    //in_vector = out_vector; TODO!

    //applyCodes();
}

uint8_t*
Coding::foldToBytes(vector<uint8_t>* input, unsigned int output_length)
{
    if(input->size() == 0 )
    {
        std::cerr << "Input size: " << input->size() << endl;
        printHexStringSingleVector(input);
        cout << endl;
        throw new runtime_error("Input size doesn't match.");
    }
    if( input->size() % 4 != 0)
    {
        input->resize(input->size() - input->size() % 4);
    }

    gf* output = (gf*) malloc(output_length * sizeof(gf));
    if(!output) throw new bad_alloc();

#ifdef TEST
    cout << "fold to bytes, Output:" << endl;
#endif // TEST

    for(unsigned int i = 0; i < output_length; i++)
    {
        uint8_t intermediate = 0;
        for(int j = 0; j < 8; j++)
        {
            intermediate <<= 1;
            intermediate |= (input->at(i*8 + j));
        }
        output[i] = intermediate;
#ifdef TEST
        cout << j << ": " << bitset<8>(output[i]) << " " << flush;
#endif // TEST
    }
#ifdef TEST
        cout << endl;
#endif // TEST

    return output;
}

uint8_t*
Coding::unrollBits(uint8_t* bytes, size_t len, uint8_t* dest)
{
    if(!bytes || !dest || len == 0) return NULL;
    int sym_len = 8;

    for(size_t s = 0; s < len; s++)
    {
        uint8_t byte = bytes[s];

        for(int i = 0; i < sym_len; i++)
        {
            // fill at 's'th symbol from back to front
            dest[(s*sym_len) + (sym_len-i-1)] = byte & 1;
            byte >>= 1;
        }
    }
    return dest;
}

void
Coding::testAll()
{
    cout << "Test unrollBits" << endl
        << "Input: 0x12ae" << endl
        << "Expected Output:\t0001001010101110" << endl
        << "Actual Output:\t\t";
    uint8_t inp[] = {0x12,  0xae};
    uint8_t oup[] = {0,     0};
    unrollBits(inp, 2, oup);
    for(int i = 0; i < 16; i++)
        cout << (unsigned short) oup[i];
    cout << endl;
}