liberasurecode
1.6.2
Erasure Code API library
builddir
build
BUILD
liberasurecode-1.6.2
src
builtin
rs_vand
rs_galois.c
Go to the documentation of this file.
1
/*
2
* Copyright 2015 Kevin M Greenan
3
*
4
* Redistribution and use in source and binary forms, with or without
5
* modification, are permitted provided that the following conditions are met:
6
*
7
* Redistributions of source code must retain the above copyright notice, this
8
* list of conditions and the following disclaimer.
9
*
10
* Redistributions in binary form must reproduce the above copyright notice, this
11
* list of conditions and the following disclaimer in the documentation and/or
12
* other materials provided with the distribution. THIS SOFTWARE IS PROVIDED BY
13
* THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED
14
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
15
* MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
16
* EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
17
* INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
18
* BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
19
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
20
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
21
* OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
22
* ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
23
*
24
* vi: set noai tw=79 ts=4 sw=4:
25
*/
26
27
// DISCLAIMER: This is a totally basic implementation of RS used if a user does not
28
// want to install one of the supported backends, such as Jerasure and ISA-L.
29
// This is not expected to perform as well as the other supported backends,
30
// but does not make any assumptions about the host system. Using a library
31
// like Jerasure with GF-Complete will give users the ability to tune to their
32
// architecture (Intel or ARM), CPU and memory (lots of options).
33
34
#include <stdio.h>
35
#include <stdlib.h>
36
#include <string.h>
37
38
// We are only implementing w=16 here. If you want to use something
39
// else, then use Jerasure with GF-Complete or ISA-L.
40
#define PRIM_POLY 0x1100b
41
#define FIELD_SIZE (1 << 16)
42
#define GROUP_SIZE (FIELD_SIZE - 1)
43
44
int
*
log_table
= NULL;
45
int
*
ilog_table
= NULL;
46
int
*
ilog_table_begin
= NULL;
47
48
void
rs_galois_init_tables
()
49
{
50
log_table
= (
int
*)malloc(
sizeof
(
int
)*
FIELD_SIZE
);
51
ilog_table_begin
= (
int
*)malloc(
sizeof
(
int
)*
FIELD_SIZE
*3);
52
int
i = 0;
53
int
x = 1;
54
55
for
(i = 0; i <
GROUP_SIZE
; i++) {
56
log_table
[x] = i;
57
ilog_table_begin
[i] = x;
58
ilog_table_begin
[i +
GROUP_SIZE
] = x;
59
ilog_table_begin
[i + (
GROUP_SIZE
*2)] = x;
60
x = x << 1;
61
if
(x &
FIELD_SIZE
) {
62
x ^=
PRIM_POLY
;
63
}
64
}
65
ilog_table
= &
ilog_table_begin
[
GROUP_SIZE
];
66
}
67
68
void
rs_galois_deinit_tables
()
69
{
70
free(
log_table
);
71
free(
ilog_table_begin
);
72
}
73
74
int
rs_galois_mult
(
int
x,
int
y)
75
{
76
int
sum;
77
if
(x == 0 || y == 0)
return
0;
78
// This can 'overflow' beyond 255. This is
79
// handled by positive overflow of ilog_table
80
sum =
log_table
[x] +
log_table
[y];
81
82
return
ilog_table
[sum];
83
}
84
85
int
rs_galois_div
(
int
x,
int
y)
86
{
87
int
diff;
88
if
(x == 0)
return
0;
89
if
(y == 0)
return
-1;
90
91
// This can 'underflow'. This is handled
92
// by negative overflow of ilog_table
93
diff =
log_table
[x] -
log_table
[y];
94
95
return
ilog_table
[diff];
96
}
97
98
int
rs_galois_inverse
(
int
x)
99
{
100
return
rs_galois_div
(1, x);
101
}
GROUP_SIZE
#define GROUP_SIZE
Definition:
rs_galois.c:42
log_table
int * log_table
Definition:
rs_galois.c:44
ilog_table_begin
int * ilog_table_begin
Definition:
rs_galois.c:46
rs_galois_init_tables
void rs_galois_init_tables()
Definition:
rs_galois.c:48
FIELD_SIZE
#define FIELD_SIZE
Definition:
rs_galois.c:41
PRIM_POLY
#define PRIM_POLY
Definition:
rs_galois.c:40
rs_galois_deinit_tables
void rs_galois_deinit_tables()
Definition:
rs_galois.c:68
rs_galois_div
int rs_galois_div(int x, int y)
Definition:
rs_galois.c:85
rs_galois_mult
int rs_galois_mult(int x, int y)
Definition:
rs_galois.c:74
rs_galois_inverse
int rs_galois_inverse(int x)
Definition:
rs_galois.c:98
ilog_table
int * ilog_table
Definition:
rs_galois.c:45
Generated on Fri Apr 29 2022 19:17:54 for liberasurecode by
1.8.17