liberasurecode  1.6.2
Erasure Code API library
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 
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 
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 
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