-
Notifications
You must be signed in to change notification settings - Fork 32
/
schifra_galois_field.hpp
518 lines (420 loc) · 18.3 KB
/
schifra_galois_field.hpp
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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
/*
(**************************************************************************)
(* *)
(* Schifra *)
(* Reed-Solomon Error Correcting Code Library *)
(* *)
(* Release Version 0.0.1 *)
(* http://www.schifra.com *)
(* Copyright (c) 2000-2020 Arash Partow, All Rights Reserved. *)
(* *)
(* The Schifra Reed-Solomon error correcting code library and all its *)
(* components are supplied under the terms of the General Schifra License *)
(* agreement. The contents of the Schifra Reed-Solomon error correcting *)
(* code library and all its components may not be copied or disclosed *)
(* except in accordance with the terms of that agreement. *)
(* *)
(* URL: http://www.schifra.com/license.html *)
(* *)
(**************************************************************************)
*/
#ifndef INCLUDE_SCHIFRA_GALOIS_FIELD_HPP
#define INCLUDE_SCHIFRA_GALOIS_FIELD_HPP
#include <algorithm>
#include <iostream>
#include <vector>
#include <limits>
#include <string>
namespace schifra
{
namespace galois
{
typedef int field_symbol;
const field_symbol GFERROR = -1;
class field
{
public:
field(const int pwr, const std::size_t primpoly_deg, const unsigned int* primitive_poly);
~field();
bool operator==(const field& gf) const;
bool operator!=(const field& gf) const;
inline field_symbol index(const field_symbol value) const
{
return index_of_[value];
}
inline field_symbol alpha(const field_symbol value) const
{
return alpha_to_[value];
}
inline unsigned int size() const
{
return field_size_;
}
inline unsigned int pwr() const
{
return power_;
}
inline unsigned int mask() const
{
return field_size_;
}
inline field_symbol add(const field_symbol& a, const field_symbol& b) const
{
return (a ^ b);
}
inline field_symbol sub(const field_symbol& a, const field_symbol& b) const
{
return (a ^ b);
}
inline field_symbol normalize(field_symbol x) const
{
while (x < 0)
{
x += static_cast<field_symbol>(field_size_);
}
while (x >= static_cast<field_symbol>(field_size_))
{
x -= static_cast<field_symbol>(field_size_);
x = (x >> power_) + (x & field_size_);
}
return x;
}
inline field_symbol mul(const field_symbol& a, const field_symbol& b) const
{
#if !defined(NO_GFLUT)
return mul_table_[a][b];
#else
if ((a == 0) || (b == 0))
return 0;
else
return alpha_to_[normalize(index_of_[a] + index_of_[b])];
#endif
}
inline field_symbol div(const field_symbol& a, const field_symbol& b) const
{
#if !defined(NO_GFLUT)
return div_table_[a][b];
#else
if ((a == 0) || (b == 0))
return 0;
else
return alpha_to_[normalize(index_of_[a] - index_of_[b] + field_size_)];
#endif
}
inline field_symbol exp(const field_symbol& a, int n) const
{
#if !defined(NO_GFLUT)
if (n >= 0)
return exp_table_[a][n & field_size_];
else
{
while (n < 0) n += field_size_;
return (n ? exp_table_[a][n] : 1);
}
#else
if (a != 0)
{
if (n < 0)
{
while (n < 0) n += field_size_;
return (n ? alpha_to_[normalize(index_of_[a] * n)] : 1);
}
else if (n)
return alpha_to_[normalize(index_of_[a] * static_cast<field_symbol>(n))];
else
return 1;
}
else
return 0;
#endif
}
#ifdef LINEAR_EXP_LUT
inline field_symbol* const linear_exp(const field_symbol& a) const
{
#if !defined(NO_GFLUT)
static const field_symbol upper_bound = 2 * field_size_;
if ((a >= 0) && (a <= upper_bound))
return linear_exp_table_[a];
else
return reinterpret_cast<field_symbol*>(0);
#else
return reinterpret_cast<field_symbol*>(0);
#endif
}
#endif
inline field_symbol inverse(const field_symbol& val) const
{
#if !defined(NO_GFLUT)
return mul_inverse_[val];
#else
return alpha_to_[normalize(field_size_ - index_of_[val])];
#endif
}
inline unsigned int prim_poly_term(const unsigned int index) const
{
return prim_poly_[index];
}
friend std::ostream& operator << (std::ostream& os, const field& gf);
private:
field();
field(const field& gfield);
field& operator=(const field& gfield);
void generate_field(const unsigned int* prim_poly_);
field_symbol gen_mul (const field_symbol& a, const field_symbol& b) const;
field_symbol gen_div (const field_symbol& a, const field_symbol& b) const;
field_symbol gen_exp (const field_symbol& a, const std::size_t& n) const;
field_symbol gen_inverse (const field_symbol& val) const;
std::size_t create_array(char buffer_[],
const std::size_t& length,
const std::size_t offset,
field_symbol** array);
std::size_t create_2d_array(char buffer_[],
std::size_t row_cnt, std::size_t col_cnt,
const std::size_t offset,
field_symbol*** array);
unsigned int power_;
std::size_t prim_poly_deg_;
unsigned int field_size_;
unsigned int prim_poly_hash_;
unsigned int* prim_poly_;
field_symbol* alpha_to_; // aka exponential or anti-log
field_symbol* index_of_; // aka log
field_symbol* mul_inverse_; // multiplicative inverse
field_symbol** mul_table_;
field_symbol** div_table_;
field_symbol** exp_table_;
field_symbol** linear_exp_table_;
char* buffer_;
};
field::field(const int pwr, const std::size_t primpoly_deg, const unsigned int* primitive_poly)
: power_(pwr),
prim_poly_deg_(primpoly_deg),
field_size_((1 << power_) - 1)
{
alpha_to_ = new field_symbol [field_size_ + 1];
index_of_ = new field_symbol [field_size_ + 1];
#if !defined(NO_GFLUT)
#ifdef LINEAR_EXP_LUT
static const std::size_t buffer_size = ((6 * (field_size_ + 1) * (field_size_ + 1)) + ((field_size_ + 1) * 2)) * sizeof(field_symbol);
#else
static const std::size_t buffer_size = ((4 * (field_size_ + 1) * (field_size_ + 1)) + ((field_size_ + 1) * 2)) * sizeof(field_symbol);
#endif
buffer_ = new char[buffer_size];
std::size_t offset = 0;
offset = create_2d_array(buffer_,(field_size_ + 1),(field_size_ + 1),offset,&mul_table_);
offset = create_2d_array(buffer_,(field_size_ + 1),(field_size_ + 1),offset,&div_table_);
offset = create_2d_array(buffer_,(field_size_ + 1),(field_size_ + 1),offset,&exp_table_);
#ifdef LINEAR_EXP_LUT
offset = create_2d_array(buffer_,(field_size_ + 1),(field_size_ + 1) * 2,offset,&linear_exp_table_);
#else
linear_exp_table_ = 0;
#endif
offset = create_array(buffer_,(field_size_ + 1) * 2,offset,&mul_inverse_);
#else
buffer_ = 0;
mul_table_ = 0;
div_table_ = 0;
exp_table_ = 0;
mul_inverse_ = 0;
linear_exp_table_ = 0;
#endif
prim_poly_ = new unsigned int [prim_poly_deg_ + 1];
for (unsigned int i = 0; i < (prim_poly_deg_ + 1); ++i)
{
prim_poly_[i] = primitive_poly[i];
}
prim_poly_hash_ = 0xAAAAAAAA;
for (std::size_t i = 0; i < (prim_poly_deg_ + 1); ++i)
{
prim_poly_hash_ += ((i & 1) == 0) ? ( (prim_poly_hash_ << 7) ^ primitive_poly[i] * (prim_poly_hash_ >> 3)) :
(~((prim_poly_hash_ << 11) + (primitive_poly[i] ^ (prim_poly_hash_ >> 5))));
}
generate_field(primitive_poly);
}
field::~field()
{
if (0 != alpha_to_) { delete [] alpha_to_; alpha_to_ = 0; }
if (0 != index_of_) { delete [] index_of_; index_of_ = 0; }
if (0 != prim_poly_) { delete [] prim_poly_; prim_poly_ = 0; }
#if !defined(NO_GFLUT)
if (0 != mul_table_) { delete [] mul_table_; mul_table_ = 0; }
if (0 != div_table_) { delete [] div_table_; div_table_ = 0; }
if (0 != exp_table_) { delete [] exp_table_; exp_table_ = 0; }
#ifdef LINEAR_EXP_LUT
if (0 != linear_exp_table_) { delete [] linear_exp_table_; linear_exp_table_ = 0; }
#endif
if (0 != buffer_) { delete [] buffer_; buffer_ = 0; }
#endif
}
inline bool field::operator==(const field& gf) const
{
return (
(this->power_ == gf.power_) &&
(this->prim_poly_hash_ == gf.prim_poly_hash_)
);
}
inline bool field::operator!=(const field& gf) const
{
return !field::operator ==(gf);
}
inline void field::generate_field(const unsigned int* prim_poly)
{
/*
Note: It is assumed that the degree of the primitive
polynomial will be equivelent to the m value as
in GF(2^m)
*/
field_symbol mask = 1;
alpha_to_[power_] = 0;
for (field_symbol i = 0; i < static_cast<field_symbol>(power_); ++i)
{
alpha_to_[i] = mask;
index_of_[alpha_to_[i]] = i;
if (prim_poly[i] != 0)
{
alpha_to_[power_] ^= mask;
}
mask <<= 1;
}
index_of_[alpha_to_[power_]] = power_;
mask >>= 1;
for (field_symbol i = power_ + 1; i < static_cast<field_symbol>(field_size_); ++i)
{
if (alpha_to_[i - 1] >= mask)
alpha_to_[i] = alpha_to_[power_] ^ ((alpha_to_[i - 1] ^ mask) << 1);
else
alpha_to_[i] = alpha_to_[i - 1] << 1;
index_of_[alpha_to_[i]] = i;
}
index_of_[0] = GFERROR;
alpha_to_[field_size_] = 1;
#if !defined(NO_GFLUT)
for (field_symbol i = 0; i < static_cast<field_symbol>(field_size_ + 1); ++i)
{
for (field_symbol j = 0; j < static_cast<field_symbol>(field_size_ + 1); ++j)
{
mul_table_[i][j] = gen_mul(i,j);
div_table_[i][j] = gen_div(i,j);
exp_table_[i][j] = gen_exp(i,j);
}
}
#ifdef LINEAR_EXP_LUT
for (field_symbol i = 0; i < static_cast<field_symbol>(field_size_ + 1); ++i)
{
for (int j = 0; j < static_cast<field_symbol>(2 * field_size_); ++j)
{
linear_exp_table_[i][j] = gen_exp(i,j);
}
}
#endif
for (field_symbol i = 0; i < static_cast<field_symbol>(field_size_ + 1); ++i)
{
mul_inverse_[i] = gen_inverse(i);
mul_inverse_[i + (field_size_ + 1)] = mul_inverse_[i];
}
#endif
}
inline field_symbol field::gen_mul(const field_symbol& a, const field_symbol& b) const
{
if ((a == 0) || (b == 0))
return 0;
else
return alpha_to_[normalize(index_of_[a] + index_of_[b])];
}
inline field_symbol field::gen_div(const field_symbol& a, const field_symbol& b) const
{
if ((a == 0) || (b == 0))
return 0;
else
return alpha_to_[normalize(index_of_[a] - index_of_[b] + field_size_)];
}
inline field_symbol field::gen_exp(const field_symbol& a, const std::size_t& n) const
{
if (a != 0)
return ((n == 0) ? 1 : alpha_to_[normalize(index_of_[a] * static_cast<field_symbol>(n))]);
else
return 0;
}
inline field_symbol field::gen_inverse(const field_symbol& val) const
{
return alpha_to_[normalize(field_size_ - index_of_[val])];
}
std::size_t field::create_array(char buffer[],
const std::size_t& length,
const std::size_t offset,
field_symbol** array)
{
const std::size_t row_size = length * sizeof(field_symbol);
(*array) = new(buffer + offset)field_symbol[length];
return row_size + offset;
}
std::size_t field::create_2d_array(char buffer[],
std::size_t row_cnt, std::size_t col_cnt,
const std::size_t offset,
field_symbol*** array)
{
const std::size_t row_size = col_cnt * sizeof(field_symbol);
char* buffer__offset = buffer + offset;
(*array) = new field_symbol* [row_cnt];
for (std::size_t i = 0; i < row_cnt; ++i)
{
(*array)[i] = new(buffer__offset + (i * row_size))field_symbol[col_cnt];
}
return (row_cnt * row_size) + offset;
}
inline std::ostream& operator << (std::ostream& os, const field& gf)
{
for (std::size_t i = 0; i < (gf.field_size_ + 1); ++i)
{
os << i << "\t" << gf.alpha_to_[i] << "\t" << gf.index_of_[i] << std::endl;
}
return os;
}
/* 1x^0 + 1x^1 + 0x^2 + 1x^3 */
const unsigned int primitive_polynomial00[] = {1, 1, 0, 1};
const unsigned int primitive_polynomial_size00 = 4;
/* 1x^0 + 1x^1 + 0x^2 + 0x^3 + 1x^4*/
const unsigned int primitive_polynomial01[] = {1, 1, 0, 0, 1};
const unsigned int primitive_polynomial_size01 = 5;
/* 1x^0 + 0x^1 + 1x^2 + 0x^3 + 0x^4 + 1x^5 */
const unsigned int primitive_polynomial02[] = {1, 0, 1, 0, 0, 1};
const unsigned int primitive_polynomial_size02 = 6;
/* 1x^0 + 1x^1 + 0x^2 + 0x^3 + 0x^4 + 0x^5 + 1x^6 */
const unsigned int primitive_polynomial03[] = {1, 1, 0, 0, 0, 0, 1};
const unsigned int primitive_polynomial_size03 = 7;
/* 1x^0 + 0x^1 + 0x^2 + 1x^3 + 0x^4 + 0x^5 + 0x^6 + 1x^7 */
const unsigned int primitive_polynomial04[] = {1, 0, 0, 1, 0, 0, 0, 1};
const unsigned int primitive_polynomial_size04 = 8;
/* 1x^0 + 0x^1 + 1x^2 + 1x^3 + 1x^4 + 0x^5 + 0x^6 + 0x^7 + 1x^8 */
const unsigned int primitive_polynomial05[] = {1, 0, 1, 1, 1, 0, 0, 0, 1};
const unsigned int primitive_polynomial_size05 = 9;
/* 1x^0 + 1x^1 + 1x^2 + 0x^3 + 0x^4 + 0x^5 + 0x^6 + 1x^7 + 1x^8 */
const unsigned int primitive_polynomial06[] = {1, 1, 1, 0, 0, 0, 0, 1, 1};
const unsigned int primitive_polynomial_size06 = 9;
/* 1x^0 + 0x^1 + 0x^2 + 0x^3 + 1x^4 + 0x^5 + 0x^6 + 0x^7 + 0x^8 + 1x^9 */
const unsigned int primitive_polynomial07[] = {1, 0, 0, 0, 1, 0, 0, 0, 0, 1};
const unsigned int primitive_polynomial_size07 = 10;
/* 1x^0 + 0x^1 + 0x^2 + 1x^3 + 0x^4 + 0x^5 + 0x^6 + 0x^7 + 0x^8 + 0x^9 + 1x^10 */
const unsigned int primitive_polynomial08[] = {1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1};
const unsigned int primitive_polynomial_size08 = 11;
/* 1x^0 + 0x^1 + 1x^2 + 0x^3 + 0x^4 + 0x^5 + 0x^6 + 0x^7 + 0x^8 + 0x^9 + 0x^10 + 1x^11 */
const unsigned int primitive_polynomial09[] = {1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1};
const unsigned int primitive_polynomial_size09 = 12;
/* 1x^0 + 1x^1 + 0x^2 + 0x^3 + 1x^4 + 0x^5 + 1x^6 + 0x^7 + 0x^8 + 0x^9 + 0x^10 + 0x^11 + 1x^12 */
const unsigned int primitive_polynomial10[] = {1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1};
const unsigned int primitive_polynomial_size10 = 13;
/* 1x^0 + 1x^1 + 0x^2 + 1x^3 + 1x^4 + 0x^5 + 0x^6 + 0x^7 + 0x^8 + 0x^9 + 0x^10 + 0x^11 + 0x^12 + 1x^13 */
const unsigned int primitive_polynomial11[] = {1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1};
const unsigned int primitive_polynomial_size11 = 14;
/* 1x^0 + 1x^1 + 0x^2 + 0x^3 + 0x^4 + 0x^5 + 1x^6 + 0x^7 + 0x^8 + 0x^9 + 1x^10 + 0x^11 + 0x^12 + 0x^13 + 1x^14 */
const unsigned int primitive_polynomial12[] = {1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1};
const unsigned int primitive_polynomial_size12 = 15;
/* 1x^0 + 1x^1 + 0x^2 + 0x^3 + 0x^4 + 0x^5 + 0x^6 + 0x^7 + 0x^8 + 0x^9 + 0x^10 + 0x^11 + 0x^12 + 0x^13 + 0x^14 + 1x^15 */
const unsigned int primitive_polynomial13[] = {1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1};
const unsigned int primitive_polynomial_size13 = 16;
/* 1x^0 + 1x^1 + 0x^2 + 1x^3 + 0x^4 + 0x^5 + 0x^6 + 0x^7 + 0x^8 + 0x^9 + 0x^10 + 0x^11 + 1x^12 + 0x^13 + 0x^14 + 0x^15 + 1x^16 */
const unsigned int primitive_polynomial14[] = {1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1};
const unsigned int primitive_polynomial_size14 = 17;
} // namespace galois
} // namespace schifra
#endif