liberasurecode 1.6.5
Erasure Code API library
Loading...
Searching...
No Matches
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
44int *log_table = NULL;
45int *ilog_table = NULL;
46int *ilog_table_begin = NULL;
47static int init_counter = 0;
48
50{
51 if (init_counter++ > 0) {
52 /* already initialized */
53 return;
54 }
55 log_table = (int*)malloc(sizeof(int)*FIELD_SIZE);
56 ilog_table_begin = (int*)malloc(sizeof(int)*FIELD_SIZE*3);
57 int i = 0;
58 int x = 1;
59
60 for (i = 0; i < GROUP_SIZE; i++) {
61 log_table[x] = i;
62 ilog_table_begin[i] = x;
64 ilog_table_begin[i + (GROUP_SIZE*2)] = x;
65 x = x << 1;
66 if (x & FIELD_SIZE) {
67 x ^= PRIM_POLY;
68 }
69 }
71}
72
74{
76 if (init_counter < 0) {
77 /* deinit when not initialized?? */
78 init_counter = 0;
79 } else if (init_counter > 0) {
80 /* still at least one desc using it */
81 return;
82 } else {
83 free(log_table);
84 log_table = NULL;
85 free(ilog_table_begin);
86 ilog_table_begin = NULL;
87 }
88}
89
90int rs_galois_mult(int x, int y)
91{
92 int sum;
93 if (x == 0 || y == 0) return 0;
94 // This can 'overflow' beyond 255. This is
95 // handled by positive overflow of ilog_table
96 sum = log_table[x] + log_table[y];
97
98 return ilog_table[sum];
99}
100
101int rs_galois_div(int x, int y)
102{
103 int diff;
104 if (x == 0) return 0;
105 if (y == 0) return -1;
106
107 // This can 'underflow'. This is handled
108 // by negative overflow of ilog_table
109 diff = log_table[x] - log_table[y];
110
111 return ilog_table[diff];
112}
113
115{
116 return rs_galois_div(1, x);
117}
int * log_table
Definition: rs_galois.c:44
#define FIELD_SIZE
Definition: rs_galois.c:41
#define GROUP_SIZE
Definition: rs_galois.c:42
#define PRIM_POLY
Definition: rs_galois.c:40
int rs_galois_div(int x, int y)
Definition: rs_galois.c:101
int rs_galois_inverse(int x)
Definition: rs_galois.c:114
int * ilog_table
Definition: rs_galois.c:45
int * ilog_table_begin
Definition: rs_galois.c:46
int rs_galois_mult(int x, int y)
Definition: rs_galois.c:90
void rs_galois_init_tables(void)
Definition: rs_galois.c:49
void rs_galois_deinit_tables(void)
Definition: rs_galois.c:73
static int init_counter
Definition: rs_galois.c:47