liberasurecode 1.6.3
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;
47
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;
59 ilog_table_begin[i + (GROUP_SIZE*2)] = x;
60 x = x << 1;
61 if (x & FIELD_SIZE) {
62 x ^= PRIM_POLY;
63 }
64 }
66}
67
69{
70 free(log_table);
71 free(ilog_table_begin);
72}
73
74int 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
85int 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
99{
100 return rs_galois_div(1, x);
101}
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:85
int rs_galois_inverse(int x)
Definition rs_galois.c:98
int * ilog_table
Definition rs_galois.c:45
int * ilog_table_begin
Definition rs_galois.c:46
void rs_galois_init_tables()
Definition rs_galois.c:48
int rs_galois_mult(int x, int y)
Definition rs_galois.c:74
void rs_galois_deinit_tables()
Definition rs_galois.c:68