coding.cpp 12.3 KB
Newer Older
1
2
3
4
5
#include <vector>
#include <cstdint>
#include <stdlib.h>
#include <iostream>
#include <sstream>
6
#include <algorithm>
Maxim Onciul's avatar
Maxim Onciul committed
7
#include <numeric>
8

9
10
11
#include <cstddef>
#include <string>

Maxim Ritter von Onciul's avatar
Maxim Ritter von Onciul committed
12
#include "../doc/cxxopts.hpp"
13
#include "polar/polar_coder.h"
Maxim Onciul's avatar
Maxim Onciul committed
14
#include "channel/simple_channel.h"
Maxim Onciul's avatar
Maxim Onciul committed
15
#include "zfec/fec.h"
Maxim Ritter von Onciul's avatar
Maxim Ritter von Onciul committed
16
#include "zcode.h"
Maxim Onciul's avatar
Maxim Onciul committed
17
#include "util.h"
18
#include "coding.h"
19

20
21
using namespace std;

Maxim Onciul's avatar
Maxim Onciul committed
22
23
int
main(int argc, char **argv)
24
{
Maxim Onciul's avatar
Maxim Onciul committed
25
26
    Coding ob(argc, argv);
    ob.applyCodes();
27
28
29
30
#ifdef REVERSE
    cout << endl << endl << "Reverse:" << endl << endl;
    ob.reverse();
#endif
Maxim Onciul's avatar
Maxim Onciul committed
31
}
Maxim Onciul's avatar
Maxim Onciul committed
32

Maxim Onciul's avatar
Maxim Onciul committed
33
34
35
void
Coding::applyCodes()
{
36
37
38
    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*));
Maxim Ritter von Onciul's avatar
Maxim Ritter von Onciul committed
39

40
41
    out_vector              = (vector<uint8_t> **) malloc(2*k * sizeof(vector<uint8_t> *));
    unsigned int* indices   = (unsigned int *) malloc(k * sizeof(unsigned int)); // Decode only
42
    bool need_to_transform = false;
43
44
45
46

    if(!hlp
        || !intermediate
        || !zfec_in
Maxim Onciul's avatar
Maxim Onciul committed
47
        || !out_vector
48
49
        || !indices
      ) throw new bad_alloc();
Maxim Ritter von Onciul's avatar
Maxim Ritter von Onciul committed
50

51
52
53
    switch(coding_mode)
    {
        case MODE_ENCODE:
54
            gf_out = ZCode::encode(
Maxim Ritter von Onciul's avatar
Maxim Ritter von Onciul committed
55
56
57
58
                k,
                m,
                raw_bytes,
                debug_mode);
59
60
61
62
63
64
65
66
67
68
69
70
71
#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
Maxim Ritter von Onciul's avatar
Maxim Ritter von Onciul committed
72

Maxim Ritter von Onciul's avatar
Maxim Ritter von Onciul committed
73
            for(unsigned short i=0; i<2*k; i++)
74
            {
Maxim Ritter von Onciul's avatar
Maxim Ritter von Onciul committed
75
76
77
78
                hlp[i] = (uint8_t *) malloc((m+1) * 8 * sizeof(uint8_t));
                if(!hlp[i]) throw new bad_alloc();

                uint8_t seq = (uint8_t) i;
79
80
                if(!unrollBits(&seq, 1, hlp[i]) || !unrollBits(gf_out[i], m, &hlp[i][8]))
                    throw new bad_exception();
Maxim Ritter von Onciul's avatar
Maxim Ritter von Onciul committed
81
82
83

                out_vector[i] = polarCode(
                    hlp[i],
84
                    8 * (size_t) (m+1),
Maxim Ritter von Onciul's avatar
Maxim Ritter von Onciul committed
85
86
87
88
89
                    code_len,
                    data_len,
                    log2_code,
                    false,
                    debug_mode);
90
#ifdef TEST
91
                cout << endl << "Polar in:" << endl;
92
93
94
95
96
                for(int j=0; j<m*8; j++)
                    cout << hex << (unsigned short) hlp[i][j];
                cout << endl << endl;
#endif
            }
Maxim Ritter von Onciul's avatar
Maxim Ritter von Onciul committed
97

98
99
#ifdef TEST
            cout << "Polar out:" << endl;
Maxim Ritter von Onciul's avatar
Maxim Ritter von Onciul committed
100
#endif
101
102
103
104
105
106
107
            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]);
108
109
            break;
        case MODE_DECODE:
110
            for(int i=0; i<k; i++)
111
            {
112
113
                // Calculate input length (has to be this value!)
                size_t num_words = (8*(m+1) - 1) / data_len + 1;
114
#ifdef TEST
Maxim Onciul's avatar
Maxim Onciul committed
115
                cout << "#Words: " << num_words
116
117
118
                    << " #bits: " << num_words * code_len
                    << " #raw_len: " << num_words * code_len / 8
                    << endl;
119
#endif
120
121

                hlp[i] = (uint8_t *) malloc(num_words * code_len * sizeof(uint8_t));
Maxim Ritter von Onciul's avatar
Maxim Ritter von Onciul committed
122
                if(!hlp[i]) throw new bad_alloc();
Maxim Onciul's avatar
Maxim Onciul committed
123

124
125
                if(!unrollBits(raw_bytes[i], num_words * code_len / 8, hlp[i]))
                    throw new bad_exception();
Maxim Ritter von Onciul's avatar
Maxim Ritter von Onciul committed
126

127
                out_vector[i] = polarCode(
128
                    hlp[i],
129
                    num_words * code_len,
130
131
132
133
                    code_len,
                    data_len,
                    log2_code,
                    true,
134
                    debug_mode);
135
#ifdef TEST
136
137
                printHexStringSingleVector(out_vector[i]);
                cout << endl;
138
#endif
139
            }
140
#ifdef TEST
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
            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];
                }
161
162
                cout << endl << endl;
#endif
163
                free(hlp[i]);
164
            }
165

166
167
168
169
170
171
172
173
174
175
            // 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)
            {
176
177
178
179
180
181
                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();
182
183

                for(uint16_t i=0; i<2*k; i++)
184
185
186
187
                {
                    check_array[i]   = 2*k;
                    new_indices[i/2] = 2*k;
                }
188
189
190
191
192
193
194
195
196
197
198
199
200
201


                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)
                    {
202
                        // Identity case
203
204
205
206
                        new_indices[i] = i;
                        new_zfec_in[i] = zfec_in[i];
                    } else if(check_array[i] != 2*k)
                    {
207
                        // Move an index to the correct spot
208
209
                        new_indices[i] = i;
                        new_zfec_in[i] = zfec_in[check_array[i]];
210
211
                    } else
                        // Move any index here
212
213
214
215
216
217
218
219
                        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;
                            }
220
                }
221

222
223
                // IMPORTANT: free has to happen before the assignment!
                free(check_array);
224
225
                free(indices);
                free(zfec_in);
226
                indices = new_indices;
227
228
229
                zfec_in = new_zfec_in;
            }

230
            gf_out = ZCode::decode(
Maxim Ritter von Onciul's avatar
Maxim Ritter von Onciul committed
231
232
                k,
                m,
233
234
                zfec_in,
                indices,
Maxim Ritter von Onciul's avatar
Maxim Ritter von Onciul committed
235
                debug_mode);
Maxim Onciul's avatar
Maxim Onciul committed
236

237
238
239
240
241
242
243
244
            // 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;
Maxim Ritter von Onciul's avatar
Maxim Ritter von Onciul committed
245
                    cout << hex << (unsigned short) data[j];
246
247
248
249
                }
                cout << endl;
            }

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

253
254
            break;
        default:
Maxim Ritter von Onciul's avatar
Maxim Ritter von Onciul committed
255
            cerr << "coding_mode unsupported." << endl;
256
257
            exit(EXIT_FAILURE);
    }
Maxim Ritter von Onciul's avatar
Maxim Ritter von Onciul committed
258
259
    //if(out_vector == NULL)
    if(gf_out == NULL)
Maxim Onciul's avatar
Maxim Onciul committed
260
261
    {
        // ERROR
262
        cerr << "An error has occurred." << endl;
Maxim Onciul's avatar
Maxim Onciul committed
263
264
265
    } else {
        // SUCCESS
    }
Maxim Onciul's avatar
Maxim Onciul committed
266

267
    free(hlp);
268
269
270
    free(intermediate);
    free(zfec_in);
    free(indices);
Maxim Onciul's avatar
Maxim Onciul committed
271
272
}

273
Coding::Coding(int argc, char** argv)
274
{
Maxim Onciul's avatar
Maxim Onciul committed
275

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

    options.add_options()
Maxim Ritter von Onciul's avatar
Maxim Ritter von Onciul committed
279
        ("d", "polar data-length",          cxxopts::value<size_t>()->default_value("30"))
Maxim Onciul's avatar
Maxim Onciul committed
280
        ("l", "polar code-length",          cxxopts::value<size_t>()->default_value("5"))
Maxim Ritter von Onciul's avatar
Maxim Ritter von Onciul committed
281
282
        ("k", "zfec num required packets",  cxxopts::value<unsigned short>()->default_value("4"))
        ("m", "zfec data length",           cxxopts::value<unsigned short>()->default_value("65000"))
Maxim Onciul's avatar
Maxim Onciul committed
283
        ("e,decode", "mode enc or dec")
Maxim Onciul's avatar
nice    
Maxim Onciul committed
284
        ("v,verbose", "verbose output");
285
286

    // Parse commandline
Maxim Ritter von Onciul's avatar
Maxim Ritter von Onciul committed
287
288
289
    auto result = options.parse(argc, argv);
    debug_mode  = result.count("v");
    coding_mode = result.count("e") ? MODE_DECODE : MODE_ENCODE;
290

Maxim Ritter von Onciul's avatar
Maxim Ritter von Onciul committed
291
    // zfec
Maxim Ritter von Onciul's avatar
Maxim Ritter von Onciul committed
292
293
    k           = result["k"].as<unsigned short>();
    m           = result["m"].as<unsigned short>();
Maxim Ritter von Onciul's avatar
Maxim Ritter von Onciul committed
294
295

    // polar
Maxim Ritter von Onciul's avatar
Maxim Ritter von Onciul committed
296
    data_len    = result["d"].as<size_t>();
Maxim Onciul's avatar
Maxim Onciul committed
297
    log2_code   = result["l"].as<size_t>();
Maxim Ritter von Onciul's avatar
Maxim Ritter von Onciul committed
298
    code_len    = 1 << log2_code;
Maxim Ritter von Onciul's avatar
Maxim Ritter von Onciul committed
299

Maxim Onciul's avatar
nice    
Maxim Onciul committed
300
    if(code_len <= data_len)
301
    {
Maxim Onciul's avatar
Maxim Onciul committed
302
        cerr << "invalid input. l: " << log2_code << ", d: " << data_len << endl;
303
304
305
        exit(EXIT_FAILURE);
    }

306
    raw_bytes = (uint8_t **) malloc(k * sizeof(uint8_t*));
Maxim Ritter von Onciul's avatar
Maxim Ritter von Onciul committed
307
    if(!raw_bytes) throw new bad_alloc();
Maxim Onciul's avatar
Maxim Onciul committed
308

309
    for(int i=0; i<k; i++)
Maxim Ritter von Onciul's avatar
Maxim Ritter von Onciul committed
310
    {
311
        raw_bytes[i] = inputToBytes();
Maxim Ritter von Onciul's avatar
Maxim Ritter von Onciul committed
312
313
        if(!raw_bytes[i]) throw new runtime_error("Insufficiently many blocks granted.");
    }
Maxim Onciul's avatar
nice    
Maxim Onciul committed
314

315
316
317
#ifdef TEST
    cout << ((coding_mode == 0) ? "En" : "De") << "coding mode" << endl << endl;
#endif
Maxim Onciul's avatar
Maxim Onciul committed
318
319
}

Maxim Ritter von Onciul's avatar
Maxim Ritter von Onciul committed
320
Coding::~Coding()
Maxim Onciul's avatar
Maxim Onciul committed
321
{
322
323
    for(int i=0; i<k; i++)
        free(raw_bytes[i]);
Maxim Ritter von Onciul's avatar
Maxim Ritter von Onciul committed
324
    free(raw_bytes);
325
326
327
328
329
330

    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);
331
    free(out_vector);
Maxim Ritter von Onciul's avatar
Maxim Ritter von Onciul committed
332
333
334
335
336
}

void
Coding::reverse()
{
337
338
    throw new runtime_error("Operation not supported. (reverse)");
    //coding_mode = (coding_mode == MODE_ENCODE) ? MODE_DECODE : MODE_ENCODE;
339
    //in_vector = out_vector; TODO!
Maxim Onciul's avatar
Maxim Onciul committed
340

341
    //applyCodes();
342
}
343

344
345
uint8_t*
Coding::foldToBytes(vector<uint8_t>* input, unsigned int output_length)
346
{
Maxim Onciul's avatar
arg    
Maxim Onciul committed
347
    if(input->size() == 0 )
Maxim Onciul's avatar
Maxim Onciul committed
348
    {
Maxim Onciul's avatar
ab    
Maxim Onciul committed
349
350
        std::cerr << "Input size: " << input->size() << endl;
        printHexStringSingleVector(input);
Maxim Onciul's avatar
ac    
Maxim Onciul committed
351
        cout << endl;
Maxim Onciul's avatar
Maxim Onciul committed
352
        throw new runtime_error("Input size doesn't match.");
Maxim Onciul's avatar
Maxim Onciul committed
353
    }
Maxim Onciul's avatar
arg    
Maxim Onciul committed
354
355
    if( input->size() % 4 != 0)
    {
Maxim Onciul's avatar
argh!    
Maxim Onciul committed
356
        input->resize(input->size() - input->size() % 4);
Maxim Onciul's avatar
arg    
Maxim Onciul committed
357
    }
358
359

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

Maxim Onciul's avatar
Maxim Onciul committed
362
#ifdef TEST
Maxim Onciul's avatar
aoeu    
Maxim Onciul committed
363
    cout << "fold to bytes, Output:" << endl;
Maxim Onciul's avatar
Maxim Onciul committed
364
365
#endif // TEST

366
    for(unsigned int i = 0; i < output_length; i++)
367
368
369
370
371
372
373
374
    {
        uint8_t intermediate = 0;
        for(int j = 0; j < 8; j++)
        {
            intermediate <<= 1;
            intermediate |= (input->at(i*8 + j));
        }
        output[i] = intermediate;
Maxim Onciul's avatar
Maxim Onciul committed
375
#ifdef TEST
Maxim Onciul's avatar
argh    
Maxim Onciul committed
376
        cout << j << ": " << bitset<8>(output[i]) << " " << flush;
Maxim Onciul's avatar
Maxim Onciul committed
377
#endif // TEST
378
    }
Maxim Onciul's avatar
Maxim Onciul committed
379
380
381
#ifdef TEST
        cout << endl;
#endif // TEST
382
383
384
385
386

    return output;
}

uint8_t*
Maxim Ritter von Onciul's avatar
Maxim Ritter von Onciul committed
387
Coding::unrollBits(uint8_t* bytes, size_t len, uint8_t* dest)
388
{
Maxim Ritter von Onciul's avatar
Maxim Ritter von Onciul committed
389
    if(!bytes || !dest || len == 0) return NULL;
390
391
392
393
    int sym_len = 8;

    for(size_t s = 0; s < len; s++)
    {
Maxim Ritter von Onciul's avatar
Maxim Ritter von Onciul committed
394
395
        uint8_t byte = bytes[s];

396
397
398
        for(int i = 0; i < sym_len; i++)
        {
            // fill at 's'th symbol from back to front
Maxim Ritter von Onciul's avatar
Maxim Ritter von Onciul committed
399
            dest[(s*sym_len) + (sym_len-i-1)] = byte & 1;
400
401
402
            byte >>= 1;
        }
    }
Maxim Ritter von Onciul's avatar
Maxim Ritter von Onciul committed
403
    return dest;
404
405
406
407
408
409
410
411
412
}

void
Coding::testAll()
{
    cout << "Test unrollBits" << endl
        << "Input: 0x12ae" << endl
        << "Expected Output:\t0001001010101110" << endl
        << "Actual Output:\t\t";
Maxim Ritter von Onciul's avatar
Maxim Ritter von Onciul committed
413
414
415
    uint8_t inp[] = {0x12,  0xae};
    uint8_t oup[] = {0,     0};
    unrollBits(inp, 2, oup);
416
    for(int i = 0; i < 16; i++)
Maxim Ritter von Onciul's avatar
Maxim Ritter von Onciul committed
417
        cout << (unsigned short) oup[i];
418
419
420
    cout << endl;
}