bc-ur/src/fountain-encoder.cpp at 42d96697818b6cb991f749e532dee1007aac2b43 · BlockchainCommons/bc-ur · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
//
//  fountain-encoder.cpp
//
//  Copyright © 2020 by Blockchain Commons, LLC
//  Licensed under the "BSD-2-Clause Plus Patent License"
//

#include "fountain-encoder.hpp"
#include <assert.h>
#include <cmath>
#include <optional>
#include <vector>
#include <limits>
#include "cbor-lite.hpp"

using namespace std;

namespace ur {

size_t FountainEncoder::find_nominal_fragment_length(size_t message_len, size_t min_fragment_len, size_t max_fragment_len) {
    assert(message_len > 0);
    assert(min_fragment_len > 0);
    assert(max_fragment_len >= min_fragment_len);
    auto max_fragment_count = message_len / min_fragment_len;
    optional<size_t> fragment_len;
    for(size_t fragment_count = 1; fragment_count <= max_fragment_count; fragment_count++) {
        fragment_len = size_t(ceil(double(message_len) / fragment_count));
        if(fragment_len <= max_fragment_len) {
            break;
        }
    }
    assert(fragment_len.has_value());
    return *fragment_len;
}

vector<ByteVector> FountainEncoder::partition_message(const ByteVector &message, size_t fragment_len) {
    auto remaining = message;
    vector<ByteVector> fragments;
    while(!remaining.empty()) {
        auto a = split(remaining, fragment_len);
        auto fragment = a.first;
        remaining = a.second;
        auto padding = fragment_len - fragment.size();
        while(padding > 0) {
            fragment.push_back(0);
            padding--;
        }
        fragments.push_back(fragment);
    }
    return fragments;
}

FountainEncoder::Part::Part(const ByteVector& cbor) {
    //try {
        auto i = cbor.begin();
        auto end = cbor.end();
        size_t array_size;
        CborLite::decodeArraySize(i, end, array_size);
        if(array_size != 5) { return;/*throw InvalidHeader();*/ }

        uint64_t n;

        CborLite::decodeUnsigned(i, end, n);
        if(n > std::numeric_limits<decltype(seq_num_)>::max()) { return; /*throw InvalidHeader();*/ }
        seq_num_ = n;

        CborLite::decodeUnsigned(i, end, n);
        if(n > std::numeric_limits<decltype(seq_len_)>::max()) { return;/*throw InvalidHeader();*/ }
        seq_len_ = n;

        CborLite::decodeUnsigned(i, end, n);
        if(n > std::numeric_limits<decltype(message_len_)>::max()) { return;/*throw InvalidHeader();*/ }
        message_len_ = n;

        CborLite::decodeUnsigned(i, end, n);
        if(n > std::numeric_limits<decltype(checksum_)>::max()) { return;/*throw InvalidHeader();*/ }
        checksum_ = n;

        CborLite::decodeBytes(i, end, data_);
    //} catch(...) {
    //    throw InvalidHeader();
    //}
}

ByteVector FountainEncoder::Part::cbor() const {
    using namespace CborLite;

    ByteVector result;

    encodeArraySize(result, (size_t)5);
    encodeInteger(result, seq_num());
    encodeInteger(result, seq_len());
    encodeInteger(result, message_len());
    encodeInteger(result, checksum());
    encodeBytes(result, data());

    return result;
}

FountainEncoder::FountainEncoder(const ByteVector& message, size_t max_fragment_len, uint32_t first_seq_num, size_t min_fragment_len) {
    assert(message.size() <= std::numeric_limits<uint32_t>::max());
    message_len_ = message.size();
    checksum_ = crc32_int(message);
    fragment_len_ = find_nominal_fragment_length(message_len_, min_fragment_len, max_fragment_len);
    fragments_ = partition_message(message, fragment_len_);
    seq_num_ = first_seq_num;
}

ByteVector FountainEncoder::mix(const PartIndexes& indexes) const {
    ByteVector result(fragment_len_, 0);
    for(auto index: indexes) { xor_into(result, fragments_[index]); }
    return result;
}

FountainEncoder::Part FountainEncoder::next_part() {
    seq_num_ += 1; // wrap at period 2^32
    auto indexes = choose_fragments(seq_num_, seq_len(), checksum_);
    auto mixed = mix(indexes);
    return Part(seq_num_, seq_len(), message_len_, checksum_, mixed);
}

string FountainEncoder::Part::description() const {
    return "seqNum:" + to_string(seq_num_) + ", seqLen:" + to_string(seq_len_) + ", messageLen:" + to_string(message_len_) + ", checksum:" + to_string(checksum_) + ", data:" + data_to_hex(data_);
}

}