← Back to branch summary

~ubuntu-branches/ubuntu/trusty/ceph/trusty-updates

« back to all changes in this revision

Viewing changes to src/erasure-code/jerasure/jerasure/src/galois.c

  • Committer: Package Import Robot
  • Author(s): James Page
  • Date: 2014-04-09 11:14:03 UTC
  • mfrom: (1.1.33)
  • Revision ID: package-import@ubuntu.com-20140409111403-jlql95pa8kg1nk9a
Tags: 0.79-0ubuntu1
https://launchpad.net/bugs/1278466
* New upstream release (LP: #1278466):
  - d/p/modules.patch: Refreshed.
  - d/ceph.install: Install all jerasure modules.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/erasure-code/jerasure/jerasure/src/galois.c
 
1
/* *
 
2
 * Copyright (c) 2014, James S. Plank and Kevin Greenan
 
3
 * All rights reserved.
 
4
 *
 
5
 * Jerasure - A C/C++ Library for a Variety of Reed-Solomon and RAID-6 Erasure
 
6
 * Coding Techniques
 
7
 *
 
8
 * Revision 2.0: Galois Field backend now links to GF-Complete
 
9
 *
 
10
 * Redistribution and use in source and binary forms, with or without
 
11
 * modification, are permitted provided that the following conditions
 
12
 * are met:
 
13
 *
 
14
 *  - Redistributions of source code must retain the above copyright
 
15
 *    notice, this list of conditions and the following disclaimer.
 
16
 *
 
17
 *  - Redistributions in binary form must reproduce the above copyright
 
18
 *    notice, this list of conditions and the following disclaimer in
 
19
 *    the documentation and/or other materials provided with the
 
20
 *    distribution.
 
21
 *
 
22
 *  - Neither the name of the University of Tennessee nor the names of its
 
23
 *    contributors may be used to endorse or promote products derived
 
24
 *    from this software without specific prior written permission.
 
25
 *
 
26
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 
27
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 
28
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 
29
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 
30
 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
 
31
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
 
32
 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
 
33
 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
 
34
 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 
35
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY
 
36
 * WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 
37
 * POSSIBILITY OF SUCH DAMAGE.
 
38
 */
 
39
 
 
40
/* Jerasure's authors:
 
41
 
 
42
   Revision 2.x - 2014: James S. Plank and Kevin M. Greenan
 
43
   Revision 1.2 - 2008: James S. Plank, Scott Simmerman and Catherine D. Schuman.
 
44
   Revision 1.0 - 2007: James S. Plank
 
45
 */
 
46
 
 
47
#include <stdio.h>
 
48
#include <stdlib.h>
 
49
#include <string.h>
 
50
 
 
51
#include "galois.h"
 
52
 
 
53
#define MAX_GF_INSTANCES 64
 
54
gf_t *gfp_array[MAX_GF_INSTANCES] = { 0 };
 
55
int  gfp_is_composite[MAX_GF_INSTANCES] = { 0 };
 
56
 
 
57
gf_t *galois_get_field_ptr(int w)
 
58
{
 
59
  if (gfp_array[w] != NULL) {
 
60
    return gfp_array[w];
 
61
  }
 
62
 
 
63
  return NULL;
 
64
}
 
65
 
 
66
gf_t* galois_init_field(int w,
 
67
                        int mult_type,
 
68
                        int region_type,
 
69
                        int divide_type,
 
70
                        uint64_t prim_poly,
 
71
                        int arg1,
 
72
                        int arg2)
 
73
{
 
74
  int scratch_size;
 
75
  void *scratch_memory;
 
76
  gf_t *gfp;
 
77
 
 
78
  if (w <= 0 || w > 32) {
 
79
    fprintf(stderr, "ERROR -- cannot init default Galois field for w=%d\n", w);
 
80
    exit(1);
 
81
  }
 
82
 
 
83
  gfp = (gf_t *) malloc(sizeof(gf_t));
 
84
  if (!gfp) {
 
85
    fprintf(stderr, "ERROR -- cannot allocate memory for Galois field w=%d\n", w);
 
86
    exit(1);
 
87
  }
 
88
 
 
89
  scratch_size = gf_scratch_size(w, mult_type, region_type, divide_type, arg1, arg2);
 
90
  if (!scratch_size) {
 
91
    fprintf(stderr, "ERROR -- cannot get scratch size for base field w=%d\n", w);
 
92
    exit(1);
 
93
  }
 
94
 
 
95
  scratch_memory = malloc(scratch_size);
 
96
  if (!scratch_memory) {
 
97
    fprintf(stderr, "ERROR -- cannot get scratch memory for base field w=%d\n", w);
 
98
    exit(1);
 
99
  }
 
100
 
 
101
  if(!gf_init_hard(gfp,
 
102
                   w, 
 
103
                   mult_type, 
 
104
                   region_type, 
 
105
                   divide_type, 
 
106
                   prim_poly, 
 
107
                   arg1, 
 
108
                   arg2, 
 
109
                   NULL, 
 
110
                   scratch_memory))
 
111
  {
 
112
    fprintf(stderr, "ERROR -- cannot init default Galois field for w=%d\n", w);
 
113
    exit(1);
 
114
  }
 
115
 
 
116
  gfp_is_composite[w] = 0;
 
117
  return gfp;
 
118
}
 
119
 
 
120
gf_t* galois_init_composite_field(int w,
 
121
                                int region_type,
 
122
                                int divide_type,
 
123
                                int degree,
 
124
                                gf_t* base_gf)
 
125
{
 
126
  int scratch_size;
 
127
  void *scratch_memory;
 
128
  gf_t *gfp;
 
129
  
 
130
  if (w <= 0 || w > 32) {
 
131
    fprintf(stderr, "ERROR -- cannot init composite field for w=%d\n", w);
 
132
    exit(1);
 
133
  }
 
134
  
 
135
  gfp = (gf_t *) malloc(sizeof(gf_t));
 
136
  if (!gfp) {
 
137
    fprintf(stderr, "ERROR -- cannot allocate memory for Galois field w=%d\n", w);
 
138
    exit(1);
 
139
  }
 
140
 
 
141
  scratch_size = gf_scratch_size(w, GF_MULT_COMPOSITE, region_type, divide_type, degree, 0);
 
142
  if (!scratch_size) {
 
143
    fprintf(stderr, "ERROR -- cannot get scratch size for composite field w=%d\n", w);
 
144
    exit(1);
 
145
  }
 
146
 
 
147
  scratch_memory = malloc(scratch_size);
 
148
  if (!scratch_memory) {
 
149
    fprintf(stderr, "ERROR -- cannot get scratch memory for composite field w=%d\n", w);
 
150
    exit(1);
 
151
  }
 
152
 
 
153
  if(!gf_init_hard(gfp,
 
154
                   w,
 
155
                   GF_MULT_COMPOSITE,
 
156
                   region_type,
 
157
                   divide_type,
 
158
                   0, 
 
159
                   degree, 
 
160
                   0, 
 
161
                   base_gf,
 
162
                   scratch_memory))
 
163
  {
 
164
    fprintf(stderr, "ERROR -- cannot init default composite field for w=%d\n", w);
 
165
    exit(1);
 
166
  }
 
167
  gfp_is_composite[w] = 1;
 
168
  return gfp;
 
169
}
 
170
 
 
171
static void galois_init_default_field(int w)
 
172
{
 
173
  if (w <= 0 || w > 32) {
 
174
    fprintf(stderr, "ERROR -- cannot init default Galois field for w=%d\n", w);
 
175
    exit(1);
 
176
  }
 
177
 
 
178
  if (gfp_array[w] == NULL) {
 
179
    gfp_array[w] = (gf_t*)malloc(sizeof(gf_t));
 
180
    if (gfp_array[w] == NULL) {
 
181
      fprintf(stderr, "ERROR -- cannot allocate memory for Galois field w=%d\n", w);
 
182
      exit(1);
 
183
    }
 
184
  }
 
185
 
 
186
  if (!gf_init_easy(gfp_array[w], w)) {
 
187
    fprintf(stderr, "ERROR -- cannot init default Galois field for w=%d\n", w);
 
188
    exit(1);
 
189
  }
 
190
}
 
191
 
 
192
 
 
193
static int is_valid_gf(gf_t *gf, int w)
 
194
{
 
195
  // TODO: I assume we may eventually
 
196
  // want to do w=64 and 128, so w
 
197
  // will be needed to perform this check
 
198
  (void)w;
 
199
 
 
200
  if (gf == NULL) {
 
201
    return 0;
 
202
  }
 
203
  if (gf->multiply.w32 == NULL) {
 
204
    return 0;
 
205
  }
 
206
  if (gf->multiply_region.w32 == NULL) {
 
207
    return 0;
 
208
  }
 
209
  if (gf->divide.w32 == NULL) {
 
210
    return 0;
 
211
  }
 
212
  if (gf->inverse.w32 == NULL) {
 
213
    return 0;
 
214
  }
 
215
  if (gf->extract_word.w32 == NULL) {
 
216
    return 0;
 
217
  }
 
218
 
 
219
  return 1;
 
220
}
 
221
 
 
222
void galois_change_technique(gf_t *gf, int w)
 
223
{
 
224
  if (w <= 0 || w > 32) {
 
225
    fprintf(stderr, "ERROR -- cannot support Galois field for w=%d\n", w);
 
226
    exit(1);
 
227
  }
 
228
 
 
229
  if (!is_valid_gf(gf, w)) {
 
230
    fprintf(stderr, "ERROR -- overriding with invalid Galois field for w=%d\n", w);
 
231
    exit(1);
 
232
  }
 
233
 
 
234
  if (gfp_array[w] != NULL) {
 
235
    gf_free(gfp_array[w], gfp_is_composite[w]);
 
236
  }
 
237
 
 
238
  gfp_array[w] = gf;
 
239
}
 
240
 
 
241
int galois_single_multiply(int x, int y, int w)
 
242
{
 
243
  if (x == 0 || y == 0) return 0;
 
244
  
 
245
  if (gfp_array[w] == NULL) {
 
246
    galois_init_default_field(w);
 
247
  }
 
248
 
 
249
  if (w <= 32) {
 
250
    return gfp_array[w]->multiply.w32(gfp_array[w], x, y);
 
251
  } else {
 
252
    fprintf(stderr, "ERROR -- Galois field not implemented for w=%d\n", w);
 
253
    return 0;
 
254
  }
 
255
}
 
256
 
 
257
int galois_single_divide(int x, int y, int w)
 
258
{
 
259
  if (x == 0) return 0;
 
260
  if (y == 0) return -1;
 
261
 
 
262
  if (gfp_array[w] == NULL) {
 
263
    galois_init_default_field(w);
 
264
  }
 
265
 
 
266
  if (w <= 32) {
 
267
    return gfp_array[w]->divide.w32(gfp_array[w], x, y);
 
268
  } else {
 
269
    fprintf(stderr, "ERROR -- Galois field not implemented for w=%d\n", w);
 
270
    return 0;
 
271
  }
 
272
}
 
273
 
 
274
void galois_w08_region_multiply(char *region,      /* Region to multiply */
 
275
                                  int multby,       /* Number to multiply by */
 
276
                                  int nbytes,        /* Number of bytes in region */
 
277
                                  char *r2,          /* If r2 != NULL, products go here */
 
278
                                  int add)
 
279
{
 
280
  if (gfp_array[8] == NULL) {
 
281
    galois_init_default_field(8);
 
282
  }
 
283
  gfp_array[8]->multiply_region.w32(gfp_array[8], region, r2, multby, nbytes, add);
 
284
}
 
285
 
 
286
void galois_w16_region_multiply(char *region,      /* Region to multiply */
 
287
                                  int multby,       /* Number to multiply by */
 
288
                                  int nbytes,        /* Number of bytes in region */
 
289
                                  char *r2,          /* If r2 != NULL, products go here */
 
290
                                  int add)
 
291
{
 
292
  if (gfp_array[16] == NULL) {
 
293
    galois_init_default_field(16);
 
294
  }
 
295
  gfp_array[16]->multiply_region.w32(gfp_array[16], region, r2, multby, nbytes, add);
 
296
}
 
297
 
 
298
 
 
299
void galois_w32_region_multiply(char *region,      /* Region to multiply */
 
300
                                  int multby,       /* Number to multiply by */
 
301
                                  int nbytes,        /* Number of bytes in region */
 
302
                                  char *r2,          /* If r2 != NULL, products go here */
 
303
                                  int add)
 
304
{
 
305
  if (gfp_array[32] == NULL) {
 
306
    galois_init_default_field(32);
 
307
  }
 
308
  gfp_array[32]->multiply_region.w32(gfp_array[32], region, r2, multby, nbytes, add);
 
309
}
 
310
 
 
311
void galois_w8_region_xor(void *src, void *dest, int nbytes)
 
312
{
 
313
  if (gfp_array[8] == NULL) {
 
314
    galois_init_default_field(8);
 
315
  }
 
316
  gfp_array[8]->multiply_region.w32(gfp_array[32], src, dest, 1, nbytes, 1);
 
317
}
 
318
 
 
319
void galois_w16_region_xor(void *src, void *dest, int nbytes)
 
320
{
 
321
  if (gfp_array[16] == NULL) {
 
322
    galois_init_default_field(16);
 
323
  }
 
324
  gfp_array[16]->multiply_region.w32(gfp_array[16], src, dest, 1, nbytes, 1);
 
325
}
 
326
 
 
327
void galois_w32_region_xor(void *src, void *dest, int nbytes)
 
328
{
 
329
  if (gfp_array[32] == NULL) {
 
330
    galois_init_default_field(32);
 
331
  }
 
332
  gfp_array[32]->multiply_region.w32(gfp_array[32], src, dest, 1, nbytes, 1);
 
333
}
 
334
 
 
335
void galois_region_xor(char *src, char *dest, int nbytes)
 
336
{
 
337
  if (nbytes >= 16) {
 
338
    galois_w32_region_xor(src, dest, nbytes);
 
339
  } else {
 
340
    int i = 0;
 
341
    for (i = 0; i < nbytes; i++) {
 
342
      *dest ^= *src;
 
343
      dest++;
 
344
      src++;
 
345
    } 
 
346
  }
 
347
}
 
348
 
 
349
int galois_inverse(int y, int w)
 
350
{
 
351
  if (y == 0) return -1;
 
352
  return galois_single_divide(1, y, w);
 
353
}