liberasurecode  1.6.1
Erasure Code API library
alg_sig.c
Go to the documentation of this file.
1 /* * Copyright (c) 2013, Kevin Greenan (kmgreen2@gmail.com)
2  * All rights reserved.
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 
25 #include <dlfcn.h>
26 #include <alg_sig.h>
27 #include <stdio.h>
28 #include <stdlib.h>
29 #include <string.h>
30 #define GALOIS_SINGLE_MULTIPLY "galois_single_multiply"
31 #define GALOIS_UNINIT "galois_uninit_field"
32 
33 int valid_gf_w[] = { 8, 16, -1 };
34 int valid_pairs[][2] = { { 8, 32}, {16, 32}, {16, 64}, {-1, -1} };
35 
36 galois_single_multiply_func get_galois_multi_func(void *handle) {
37  /*
38  * ISO C forbids casting a void* to a function pointer.
39  * Since dlsym return returns a void*, we use this union to
40  * "transform" the void* to a function pointer.
41  */
42  union {
43  galois_single_multiply_func fptr;
44  void *vptr;
45  } func_handle = {.vptr = NULL};
46  func_handle.vptr = dlsym(handle, GALOIS_SINGLE_MULTIPLY);
47  return func_handle.fptr;
48 }
49 
51 
53  /*
54  * ISO C forbids casting a void* to a function pointer.
55  * Since dlsym return returns a void*, we use this union to
56  * "transform" the void* to a function pointer.
57  */
58  union {
60  void *vptr;
61  } func_handle = {.vptr = NULL};
62  func_handle.vptr = dlsym(handle, GALOIS_UNINIT);
63  return func_handle.fptr;
64 }
65 
66 
68 {
69  return dlopen(JERASURE_SONAME, RTLD_LAZY | RTLD_LOCAL);
70 }
71 
72 int load_gf_functions(void *sohandle, struct jerasure_mult_routines *routines)
73 {
74  routines->galois_single_multiply = get_galois_multi_func(sohandle);
75  routines->galois_uninit_field = get_galois_uninit_func(sohandle);
76  if (NULL == routines->galois_single_multiply) {
77  return -1;
78  }
88  if (NULL == routines->galois_uninit_field) {
89  routines->galois_uninit_field = &stub_galois_uninit_field;
90  }
91 
92  return 0;
93 }
94 
95 static
96 alg_sig_t *init_alg_sig_w8(void *jerasure_sohandle, int sig_len)
97 {
98  alg_sig_t *alg_sig_handle;
99  int num_gf_lr_table_syms;
100  int i;
101  int w = 8;
102  int alpha = 2, beta = 4, gamma = 8;
103  int num_components = sig_len / w;
104 
105  alg_sig_handle = (alg_sig_t *)malloc(sizeof(alg_sig_t));
106  if (NULL == alg_sig_handle) {
107  return NULL;
108  }
109 
110  alg_sig_handle->jerasure_sohandle = jerasure_sohandle;
111 
112  if (load_gf_functions(alg_sig_handle->jerasure_sohandle, &(alg_sig_handle->mult_routines)) < 0) {
113  free(alg_sig_handle);
114  return NULL;
115  }
116 
117  alg_sig_handle->sig_len = sig_len;
118  alg_sig_handle->gf_w = w;
119 
120  num_gf_lr_table_syms = 1 << (w >> 1);
121 
122  if (num_components >= 4) {
123  alg_sig_handle->tbl1_l = (int*)malloc(sizeof(int) * num_gf_lr_table_syms);
124  alg_sig_handle->tbl1_r = (int*)malloc(sizeof(int) * num_gf_lr_table_syms);
125  alg_sig_handle->tbl2_l = (int*)malloc(sizeof(int) * num_gf_lr_table_syms);
126  alg_sig_handle->tbl2_r = (int*)malloc(sizeof(int) * num_gf_lr_table_syms);
127  alg_sig_handle->tbl3_l = (int*)malloc(sizeof(int) * num_gf_lr_table_syms);
128  alg_sig_handle->tbl3_r = (int*)malloc(sizeof(int) * num_gf_lr_table_syms);
129  }
130 
131  /*
132  * Note that \alpha = 2
133  * Note that \beta = 4 (\alpha ^ 2)
134  * Note that \gamme = 8 (\alpha ^ 3)
135  */
136  for (i = 0; i < 16; i++) {
137  if (num_components >= 4) {
138  alg_sig_handle->tbl1_l[i] = alg_sig_handle->mult_routines.galois_single_multiply((unsigned char)(i << 4) & 0xf0, alpha, w);
139  alg_sig_handle->tbl1_r[i] = alg_sig_handle->mult_routines.galois_single_multiply((unsigned char) i, alpha, w);
140 
141  alg_sig_handle->tbl2_l[i] = alg_sig_handle->mult_routines.galois_single_multiply((unsigned char) (i << 4) & 0xf0, beta, w);
142  alg_sig_handle->tbl2_r[i] = alg_sig_handle->mult_routines.galois_single_multiply((unsigned char) i, beta, w);
143 
144  alg_sig_handle->tbl3_l[i] = alg_sig_handle->mult_routines.galois_single_multiply((unsigned char) (i << 4) & 0xf0, gamma, w);
145  alg_sig_handle->tbl3_r[i] = alg_sig_handle->mult_routines.galois_single_multiply((unsigned char) i, gamma, w);
146  }
147  }
148 
149  return alg_sig_handle;
150 }
151 
152 static
153 alg_sig_t *init_alg_sig_w16(void *jerasure_sohandle, int sig_len)
154 {
155  alg_sig_t *alg_sig_handle;
156  int num_gf_lr_table_syms;
157  int i;
158  int w = 16;
159  int alpha = 2, beta = 4, gamma = 8;
160  int num_components = sig_len / w;
161 
162  if (NULL == jerasure_sohandle) {
163  return NULL;
164  }
165 
166  alg_sig_handle = (alg_sig_t *)malloc(sizeof(alg_sig_t));
167  if (NULL == alg_sig_handle) {
168  return NULL;
169  }
170 
171  alg_sig_handle->jerasure_sohandle = jerasure_sohandle;
172 
173  if (load_gf_functions(alg_sig_handle->jerasure_sohandle, &(alg_sig_handle->mult_routines)) < 0) {
174  free(alg_sig_handle);
175  return NULL;
176  }
177 
178  alg_sig_handle->sig_len = sig_len;
179  alg_sig_handle->gf_w = w;
180 
181  num_gf_lr_table_syms = 1 << (w >> 1);
182 
183  if (num_components >= 2) {
184  alg_sig_handle->tbl1_l = (int*)malloc(sizeof(int) * num_gf_lr_table_syms);
185  alg_sig_handle->tbl1_r = (int*)malloc(sizeof(int) * num_gf_lr_table_syms);
186  }
187 
188  if (num_components >= 4) {
189  alg_sig_handle->tbl2_l = (int*)malloc(sizeof(int) * num_gf_lr_table_syms);
190  alg_sig_handle->tbl2_r = (int*)malloc(sizeof(int) * num_gf_lr_table_syms);
191  alg_sig_handle->tbl3_l = (int*)malloc(sizeof(int) * num_gf_lr_table_syms);
192  alg_sig_handle->tbl3_r = (int*)malloc(sizeof(int) * num_gf_lr_table_syms);
193  }
194 
195  /*
196  * Note that \alpha = 2
197  * Note that \beta = 4 (\alpha ^ 2 MOD 2^16)
198  * Note that \gamme = 8 (\alpha ^ 3 MOD 2^16)
199  */
200  for (i = 0; i < 256; i++) {
201  alg_sig_handle->tbl1_l[i] = alg_sig_handle->mult_routines.galois_single_multiply((unsigned short) (i << 8), alpha, w);
202  alg_sig_handle->tbl1_r[i] = alg_sig_handle->mult_routines.galois_single_multiply((unsigned short) i, alpha, w);
203 
204  if (num_components >= 4) {
205  alg_sig_handle->tbl2_l[i] = alg_sig_handle->mult_routines.galois_single_multiply((unsigned short) (i << 8), beta, w);
206  alg_sig_handle->tbl2_r[i] = alg_sig_handle->mult_routines.galois_single_multiply((unsigned short) i, beta, w);
207 
208  alg_sig_handle->tbl3_l[i] = alg_sig_handle->mult_routines.galois_single_multiply((unsigned short) (i << 8), gamma, w);
209  alg_sig_handle->tbl3_r[i] = alg_sig_handle->mult_routines.galois_single_multiply((unsigned short) i, gamma, w);
210  }
211  }
212 
213  return alg_sig_handle;
214 }
215 
216 alg_sig_t *init_alg_sig(int sig_len, int gf_w)
217 {
218  int i=0;
219  void *jerasure_sohandle = get_jerasure_sohandle();
220 
221  if (NULL == jerasure_sohandle) {
222  fprintf (stderr, "Could not open Jerasure backend. Install Jerasure or fix LD_LIBRARY_PATH. Passing.\n");
223  return NULL;
224  }
225 
226  while (valid_pairs[i][0] > -1) {
227  if (gf_w == valid_pairs[i][0] &&
228  sig_len == valid_pairs[i][1]) {
229  break;
230  }
231  i++;
232  }
233 
234  if (valid_pairs[i][0] == -1) {
235  return NULL;
236  }
237 
238  if (gf_w == 8) {
239  return init_alg_sig_w8(jerasure_sohandle, sig_len);
240  } else if (gf_w == 16) {
241  return init_alg_sig_w16(jerasure_sohandle, sig_len);
242  }
243  return NULL;
244 }
245 
246 void destroy_alg_sig(alg_sig_t* alg_sig_handle)
247 {
248  if (alg_sig_handle == NULL) {
249  return;
250  }
251  if (alg_sig_handle->gf_w == 0) {
252  free(alg_sig_handle);
253  return;
254  }
255 
256  alg_sig_handle->mult_routines.galois_uninit_field(alg_sig_handle->gf_w);
257  dlclose(alg_sig_handle->jerasure_sohandle);
258 
259  int num_components = alg_sig_handle->sig_len / alg_sig_handle->gf_w;
260 
261  free(alg_sig_handle->tbl1_l);
262  free(alg_sig_handle->tbl1_r);
263  if (num_components >= 4) {
264  free(alg_sig_handle->tbl2_l);
265  free(alg_sig_handle->tbl2_r);
266  free(alg_sig_handle->tbl3_l);
267  free(alg_sig_handle->tbl3_r);
268  }
269 
270  free(alg_sig_handle);
271 }
272 
273 
274 static
275 int compute_w8_alg_sig_32(alg_sig_t *alg_sig_handle, char *buf, int len, char *sig)
276 {
277  int i;
278 
279  if (len == 0) {
280  bzero(sig, 4);
281  return 0;
282  }
283 
284  sig[0] = buf[len-1];
285  sig[1] = buf[len-1];
286  sig[2] = buf[len-1];
287  sig[3] = buf[len-1];
288 
293  for (i = len - 2; i >= 0; i--) {
294  sig[0] ^= buf[i];
295  sig[1] = (buf[i] ^ (alg_sig_handle->tbl1_l[(sig[1] >> 4) & 0x0f] ^ alg_sig_handle->tbl1_r[sig[1] & 0x0f]));
296  sig[2] = (buf[i] ^ (alg_sig_handle->tbl2_l[(sig[2] >> 4) & 0x0f] ^ alg_sig_handle->tbl2_r[sig[2] & 0x0f]));
297  sig[3] = (buf[i] ^ (alg_sig_handle->tbl3_l[(sig[3] >> 4) & 0x0f] ^ alg_sig_handle->tbl3_r[sig[3] & 0x0f]));
298  }
299 
300  return 0;
301 }
302 
303 static
304 int compute_w16_alg_sig_64(alg_sig_t *alg_sig_handle, char *buf, int len, char *sig)
305 {
306  int bit_mask;
307  int adj_len = len / 2;
308  int i;
309  unsigned short *_buf = (unsigned short *)buf;
310  unsigned short sig_buf[4];
311 
312  if (len == 0) {
313  bzero(sig, 8);
314  return 0;
315  }
316 
317  switch (len % 2) {
318  case 1:
319  bit_mask = 0x00ff;
320  break;
321  default:
322  bit_mask = 0xffff;
323  break;
324  }
325 
326  if (len % 2 > 0) {
327  adj_len++;
328  }
329 
330  // Account for buffer not being uint16_t aligned
331  sig_buf[0] = (_buf[adj_len - 1] & bit_mask);
332  sig_buf[1] = (_buf[adj_len - 1] & bit_mask);
333  sig_buf[2] = (_buf[adj_len - 1] & bit_mask);
334  sig_buf[3] = (_buf[adj_len - 1] & bit_mask);
335 
340  for (i = adj_len - 2; i >= 0; i--) {
341  sig_buf[0] ^= _buf[i];
342  sig_buf[1] = (_buf[i] ^ (alg_sig_handle->tbl1_l[(sig_buf[1] >> 8) & 0x00ff] ^ alg_sig_handle->tbl1_r[sig_buf[1] & 0x00ff]));
343  sig_buf[2] = (_buf[i] ^ (alg_sig_handle->tbl2_l[(sig_buf[2] >> 8) & 0x00ff] ^ alg_sig_handle->tbl2_r[sig_buf[2] & 0x00ff]));
344  sig_buf[3] = (_buf[i] ^ (alg_sig_handle->tbl3_l[(sig_buf[3] >> 8) & 0x00ff] ^ alg_sig_handle->tbl3_r[sig_buf[3] & 0x00ff]));
345  }
346 
347  sig[0] = (char) (sig_buf[0] & 0x000ff);
348  sig[1] = (char) ((sig_buf[0] >> 8) & 0x000ff);
349  sig[2] = (char) (sig_buf[1] & 0x00ff);
350  sig[3] = (char) ((sig_buf[1] >> 8) & 0x00ff);
351  sig[4] = (char) (sig_buf[2] & 0x00ff);
352  sig[5] = (char) ((sig_buf[2] >> 8) & 0x00ff);
353  sig[6] = (char) (sig_buf[3] & 0x00ff);
354  sig[7] = (char) ((sig_buf[3] >> 8) & 0x00ff);
355  return 0;
356 }
357 
358 static
359 int compute_w16_alg_sig_32(alg_sig_t *alg_sig_handle, char *buf, int len, char *sig)
360 {
361  int bit_mask;
362  int adj_len = len / 2;
363  int i;
364  unsigned short *_buf = (unsigned short *)buf;
365  unsigned short sig_buf[2];
366 
367  if (len == 0) {
368  bzero(sig, 8);
369  return 0;
370  }
371 
372  switch (len % 2) {
373  case 1:
374  bit_mask = 0x00ff;
375  break;
376  default:
377  bit_mask = 0xffff;
378  break;
379  }
380 
381  if (len % 2 > 0) {
382  adj_len++;
383  }
384 
385  // Account for buffer not being uint16_t aligned
386  sig_buf[0] = (_buf[adj_len - 1] & bit_mask);
387  sig_buf[1] = (_buf[adj_len - 1] & bit_mask);
388 
393  for (i = adj_len - 2; i >= 0; i--) {
394  sig_buf[0] ^= _buf[i];
395  sig_buf[1] = (_buf[i] ^ (alg_sig_handle->tbl1_l[(sig_buf[1] >> 8) & 0x00ff] ^ alg_sig_handle->tbl1_r[sig_buf[1] & 0x00ff]));
396  }
397 
398  sig[0] = (char) (sig_buf[0] & 0x000ff);
399  sig[1] = (char) ((sig_buf[0] >> 8) & 0x000ff);
400  sig[2] = (char) (sig_buf[1] & 0x00ff);
401  sig[3] = (char) ((sig_buf[1] >> 8) & 0x00ff);
402  return 0;
403 }
404 
405 static
406 int compute_alg_sig_32(alg_sig_t *alg_sig_handle, char *buf, int len, char *sig)
407 {
408  if (alg_sig_handle->gf_w == 8) {
409  return compute_w8_alg_sig_32(alg_sig_handle, buf, len, sig);
410  } else if (alg_sig_handle->gf_w == 16) {
411  return compute_w16_alg_sig_32(alg_sig_handle, buf, len, sig);
412  }
413  return -1;
414 }
415 
416 static
417 int compute_alg_sig_64(alg_sig_t *alg_sig_handle, char *buf, int len, char *sig)
418 {
419  if (alg_sig_handle->gf_w == 16) {
420  return compute_w16_alg_sig_64(alg_sig_handle, buf, len, sig);
421  }
422  return -1;
423 }
424 
425 int compute_alg_sig(alg_sig_t *alg_sig_handle, char *buf, int len, char *sig)
426 {
427  if (alg_sig_handle->sig_len == 32) {
428  return compute_alg_sig_32(alg_sig_handle, buf, len, sig);
429  } else if (alg_sig_handle->sig_len == 64) {
430  return compute_alg_sig_64(alg_sig_handle, buf, len, sig);
431  }
432  return -1;
433 }
static int compute_w16_alg_sig_32(alg_sig_t *alg_sig_handle, char *buf, int len, char *sig)
Definition: alg_sig.c:359
int load_gf_functions(void *sohandle, struct jerasure_mult_routines *routines)
Definition: alg_sig.c:72
void * get_jerasure_sohandle()
Definition: alg_sig.c:67
void destroy_alg_sig(alg_sig_t *alg_sig_handle)
Definition: alg_sig.c:246
int compute_alg_sig(alg_sig_t *alg_sig_handle, char *buf, int len, char *sig)
Definition: alg_sig.c:425
static int compute_w8_alg_sig_32(alg_sig_t *alg_sig_handle, char *buf, int len, char *sig)
Definition: alg_sig.c:275
#define GALOIS_SINGLE_MULTIPLY
Definition: alg_sig.c:30
galois_uninit_field_func get_galois_uninit_func(void *handle)
Definition: alg_sig.c:52
#define GALOIS_UNINIT
Definition: alg_sig.c:31
galois_single_multiply_func get_galois_multi_func(void *handle)
Definition: alg_sig.c:36
static int compute_w16_alg_sig_64(alg_sig_t *alg_sig_handle, char *buf, int len, char *sig)
Definition: alg_sig.c:304
static alg_sig_t * init_alg_sig_w16(void *jerasure_sohandle, int sig_len)
Definition: alg_sig.c:153
int valid_pairs[][2]
Definition: alg_sig.c:34
static alg_sig_t * init_alg_sig_w8(void *jerasure_sohandle, int sig_len)
Definition: alg_sig.c:96
int valid_gf_w[]
Definition: alg_sig.c:33
void stub_galois_uninit_field(int w)
Definition: alg_sig.c:50
alg_sig_t * init_alg_sig(int sig_len, int gf_w)
Definition: alg_sig.c:216
static int compute_alg_sig_64(alg_sig_t *alg_sig_handle, char *buf, int len, char *sig)
Definition: alg_sig.c:417
static int compute_alg_sig_32(alg_sig_t *alg_sig_handle, char *buf, int len, char *sig)
Definition: alg_sig.c:406
void(* galois_uninit_field_func)(int)