Newer
Older
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
/*
* Copyright (c) 2015, Luca Fulchir<luca@fulchir.it>, All rights reserved.
*
* This file is part of "libRaptorQ".
*
* libRaptorQ is free software: you can redistribute it and/or modify
* it under the terms of the GNU Lesser General Public License as
* published by the Free Software Foundation, either version 3
* of the License, or (at your option) any later version.
*
* libRaptorQ is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* and a copy of the GNU Lesser General Public License
* along with libRaptorQ. If not, see <http://www.gnu.org/licenses/>.
*/
#include "degree.hpp"
#include "Parameters.hpp"
#include "Rand.hpp"
RaptorQ::Impl::Parameters::Parameters(const uint16_t symbols)
{
uint16_t idx;
for (idx = 0; idx < RaptorQ::Impl::K_padded.size(); ++idx) {
if (RaptorQ::Impl::K_padded[idx] >= symbols) {
K_padded = RaptorQ::Impl::K_padded[idx];
break;
}
}
J = RaptorQ::Impl::J_K_padded[idx];
std::tie (S, H, W) = RaptorQ::Impl::S_H_W [idx];
L = K_padded + S + H;
P = L - W;
U = P - H;
B = W - S;
P1 = P + 1; // first prime number bigger than P. turns out its
// always between 1 and 14 more numbers.
while (!is_prime (P1)) // so this while will be really quick anyway
++P1;
}
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
{
// 1 as prime, don't care. Not in our scope anyway.
// thank you stackexchange for the code
if (n <= 3)
return true;
if (n % 2 == 0 || n % 3 == 0)
return false;
uint32_t i = 5;
uint32_t w = 2;
while (i * i <= n) {
if (n % i == 0)
return false;
i += w;
w = 6 - w;
}
return true;
}
uint16_t RaptorQ::Impl::Parameters::Deg (const uint32_t v) const
{
// rfc 6330, pg 27
for (uint16_t d = 0; d < RaptorQ::Impl::degree_distribution.size(); ++d) {
if (v < RaptorQ::Impl::degree_distribution[d])
return (d < (W - 2)) ? d : (W - 2);
}
return 0; // never get here, but don't make the compiler complain
}
RaptorQ::Impl::Tuple RaptorQ::Impl::Parameters::tuple (const uint32_t ISI) const
{
RaptorQ::Impl::Rand rnd;
RaptorQ::Impl::Tuple ret;
// taken straight from RFC6330, pg 30
// so thank them for the *beautiful* names
// also, don't get confused with "B": this one is different,
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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
size_t A = 53591 + J * 997;
if (A % 2 == 0)
++A;
size_t B1 = 10267 * (J + 1);
uint32_t y = static_cast<uint32_t> (B1 + ISI * A);
uint32_t v = rnd.get (y, 0, static_cast<uint32_t> (std::pow(2, 20)));
ret.d = Deg (v);
ret.a = 1 + static_cast<uint16_t> (rnd.get (y, 1, W - 1));
ret.b = static_cast<uint16_t> (rnd.get (y, 2, W));
if (ret.d < 4) {
ret.d1 = 2 + static_cast<uint16_t> (rnd.get (ISI, 3, 2));
} else {
ret.d1 = 2;
}
ret.a1 = 1 + static_cast<uint16_t> (rnd.get (ISI, 4, P1 - 1));
ret.b1 = static_cast<uint16_t> (rnd.get (ISI, 5, P1));
return ret;
}
std::vector<uint16_t> RaptorQ::Impl::Parameters::get_idxs (const uint32_t ISI)
const
{
// Needed to generate G_ENC: We need the ids of the symbols we would
// use on a "Enc" call. So this is the "enc algorithm, but returns the
// indexes instead of computing the result.
// rfc6330, pg29
std::vector<uint16_t> ret;
Tuple t = tuple (ISI);
ret.reserve (t.d + t.d1);
ret.push_back (t.b);
// FIXME: rfc: from 1. OpenRQ: from 0
// if start from 1 => 99% failure
// yet next loop starts from 1 (or 0, no change)
for (uint16_t j = 0; j < t.d; ++j) {
t.b = (t.b + t.a) % W;
ret.push_back (t.b);
}
while (t.b1 >= P)
t.b1 = (t.b1 + t.a1) % P1;
ret.push_back (W + t.b1);
for (uint16_t j = 1; j < t.d1; ++j) {
t.b1 = (t.b1 + t.a1) % P1;
while (t.b1 >= P)
t.b1 = (t.b1 + t.a1) % P1;
ret.push_back (W + t.b1);
}
return ret;
}