IDA_new/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 #include <errno.h>
  51 #include <assert.h>
  52
  53 #include "galois.h"
  54
  55 #define MAX_GF_INSTANCES 64
  56 gf_t *gfp_array[MAX_GF_INSTANCES] = { 0 };
  57 int  gfp_is_composite[MAX_GF_INSTANCES] = { 0 };
  58
  59 gf_t *galois_get_field_ptr(int w)
  60 {
  61   if (gfp_array[w] != NULL) {
  62     return gfp_array[w];
  63   }
  64
  65   return NULL;
  66 }
  67
  68 gf_t* galois_init_field(int w,
  69                         int mult_type,
  70                         int region_type,
  71                         int divide_type,
  72                         uint64_t prim_poly,
  73                         int arg1,
  74                         int arg2)
  75 {
  76   int scratch_size;
  77   void *scratch_memory;
  78   gf_t *gfp;
  79
  80   if (w <= 0 || w > 32) {
  81     fprintf(stderr, "ERROR -- cannot init default Galois field for w=%d\n", w);
  82     assert(0);
  83   }
  84
  85   gfp = (gf_t *) malloc(sizeof(gf_t));
  86   if (!gfp) {
  87     fprintf(stderr, "ERROR -- cannot allocate memory for Galois field w=%d\n", w);
  88     assert(0);
  89   }
  90
  91   scratch_size = gf_scratch_size(w, mult_type, region_type, divide_type, arg1, arg2);
  92   if (!scratch_size) {
  93     fprintf(stderr, "ERROR -- cannot get scratch size for base field w=%d\n", w);
  94     assert(0);
  95   }
  96
  97   scratch_memory = malloc(scratch_size);
  98   if (!scratch_memory) {
  99     fprintf(stderr, "ERROR -- cannot get scratch memory for base field w=%d\n", w);
 100     assert(0);
 101   }
 102
 103   if(!gf_init_hard(gfp,
 104                    w,
 105                    mult_type,
 106                    region_type,
 107                    divide_type,
 108                    prim_poly,
 109                    arg1,
 110                    arg2,
 111                    NULL,
 112                    scratch_memory))
 113   {
 114     fprintf(stderr, "ERROR -- cannot init default Galois field for w=%d\n", w);
 115     assert(0);
 116   }
 117
 118   gfp_is_composite[w] = 0;
 119   return gfp;
 120 }
 121
 122 gf_t* galois_init_composite_field(int w,
 123                                 int region_type,
 124                                 int divide_type,
 125                                 int degree,
 126                                 gf_t* base_gf)
 127 {
 128   int scratch_size;
 129   void *scratch_memory;
 130   gf_t *gfp;
 131
 132   if (w <= 0 || w > 32) {
 133     fprintf(stderr, "ERROR -- cannot init composite field for w=%d\n", w);
 134     assert(0);
 135   }
 136
 137   gfp = (gf_t *) malloc(sizeof(gf_t));
 138   if (!gfp) {
 139     fprintf(stderr, "ERROR -- cannot allocate memory for Galois field w=%d\n", w);
 140     assert(0);
 141   }
 142
 143   scratch_size = gf_scratch_size(w, GF_MULT_COMPOSITE, region_type, divide_type, degree, 0);
 144   if (!scratch_size) {
 145     fprintf(stderr, "ERROR -- cannot get scratch size for composite field w=%d\n", w);
 146     assert(0);
 147   }
 148
 149   scratch_memory = malloc(scratch_size);
 150   if (!scratch_memory) {
 151     fprintf(stderr, "ERROR -- cannot get scratch memory for composite field w=%d\n", w);
 152     assert(0);
 153   }
 154
 155   if(!gf_init_hard(gfp,
 156                    w,
 157                    GF_MULT_COMPOSITE,
 158                    region_type,
 159                    divide_type,
 160                    0,
 161                    degree,
 162                    0,
 163                    base_gf,
 164                    scratch_memory))
 165   {
 166     fprintf(stderr, "ERROR -- cannot init default composite field for w=%d\n", w);
 167     assert(0);
 168   }
 169   gfp_is_composite[w] = 1;
 170   return gfp;
 171 }
 172
 173 int galois_init_default_field(int w)
 174 {
 175   if (gfp_array[w] == NULL) {
 176     gfp_array[w] = (gf_t*)malloc(sizeof(gf_t));
 177     if(gfp_array[w] == NULL)
 178       return ENOMEM;
 179     if (!gf_init_easy(gfp_array[w], w))
 180       return EINVAL;
 181   }
 182   return 0;
 183 }
 184
 185 int galois_uninit_field(int w)
 186 {
 187   int ret = 0;
 188   if (gfp_array[w] != NULL) {
 189     int recursive = 1;
 190     ret = gf_free(gfp_array[w], recursive);
 191     free(gfp_array[w]);
 192     gfp_array[w] = NULL;
 193   }
 194   return ret;
 195 }
 196
 197 static void galois_init(int w)
 198 {
 199   if (w <= 0 || w > 32) {
 200     fprintf(stderr, "ERROR -- cannot init default Galois field for w=%d\n", w);
 201     assert(0);
 202   }
 203
 204   switch (galois_init_default_field(w)) {
 205   case ENOMEM:
 206     fprintf(stderr, "ERROR -- cannot allocate memory for Galois field w=%d\n", w);
 207     assert(0);
 208     break;
 209   case EINVAL:
 210     fprintf(stderr, "ERROR -- cannot init default Galois field for w=%d\n", w);
 211     assert(0);
 212     break;
 213   }
 214 }
 215
 216
 217 static int is_valid_gf(gf_t *gf, int w)
 218 {
 219   // TODO: I assume we may eventually
 220   // want to do w=64 and 128, so w
 221   // will be needed to perform this check
 222   (void)w;
 223
 224   if (gf == NULL) {
 225     return 0;
 226   }
 227   if (gf->multiply.w32 == NULL) {
 228     return 0;
 229   }
 230   if (gf->multiply_region.w32 == NULL) {
 231     return 0;
 232   }
 233   if (gf->divide.w32 == NULL) {
 234     return 0;
 235   }
 236   if (gf->inverse.w32 == NULL) {
 237     return 0;
 238   }
 239   if (gf->extract_word.w32 == NULL) {
 240     return 0;
 241   }
 242
 243   return 1;
 244 }
 245
 246 void galois_change_technique(gf_t *gf, int w)
 247 {
 248   if (w <= 0 || w > 32) {
 249     fprintf(stderr, "ERROR -- cannot support Galois field for w=%d\n", w);
 250     assert(0);
 251   }
 252
 253   if (!is_valid_gf(gf, w)) {
 254     fprintf(stderr, "ERROR -- overriding with invalid Galois field for w=%d\n", w);
 255     assert(0);
 256   }
 257
 258   if (gfp_array[w] != NULL) {
 259     gf_free(gfp_array[w], gfp_is_composite[w]);
 260   }
 261
 262   gfp_array[w] = gf;
 263 }
 264
 265 int galois_single_multiply(int x, int y, int w)
 266 {
 267   if (x == 0 || y == 0) return 0;
 268
 269   if (gfp_array[w] == NULL) {
 270     galois_init(w);
 271   }
 272
 273   if (w <= 32) {
 274     return gfp_array[w]->multiply.w32(gfp_array[w], x, y);
 275   } else {
 276     fprintf(stderr, "ERROR -- Galois field not implemented for w=%d\n", w);
 277     return 0;
 278   }
 279 }
 280
 281 int galois_single_divide(int x, int y, int w)
 282 {
 283   if (x == 0) return 0;
 284   if (y == 0) return -1;
 285
 286   if (gfp_array[w] == NULL) {
 287     galois_init(w);
 288   }
 289
 290   if (w <= 32) {
 291     return gfp_array[w]->divide.w32(gfp_array[w], x, y);
 292   } else {
 293     fprintf(stderr, "ERROR -- Galois field not implemented for w=%d\n", w);
 294     return 0;
 295   }
 296 }
 297
 298 void galois_w08_region_multiply(char *region,      /* Region to multiply */
 299                                   int multby,       /* Number to multiply by */
 300                                   int nbytes,        /* Number of bytes in region */
 301                                   char *r2,          /* If r2 != NULL, products go here */
 302                                   int add)
 303 {
 304   if (gfp_array[8] == NULL) {
 305     galois_init(8);
 306   }
 307   gfp_array[8]->multiply_region.w32(gfp_array[8], region, r2, multby, nbytes, add);
 308 }
 309
 310 void galois_w16_region_multiply(char *region,      /* Region to multiply */
 311                                   int multby,       /* Number to multiply by */
 312                                   int nbytes,        /* Number of bytes in region */
 313                                   char *r2,          /* If r2 != NULL, products go here */
 314                                   int add)
 315 {
 316   if (gfp_array[16] == NULL) {
 317     galois_init(16);
 318   }
 319   gfp_array[16]->multiply_region.w32(gfp_array[16], region, r2, multby, nbytes, add);
 320 }
 321
 322
 323 void galois_w32_region_multiply(char *region,      /* Region to multiply */
 324                                   int multby,       /* Number to multiply by */
 325                                   int nbytes,        /* Number of bytes in region */
 326                                   char *r2,          /* If r2 != NULL, products go here */
 327                                   int add)
 328 {
 329   if (gfp_array[32] == NULL) {
 330     galois_init(32);
 331   }
 332   gfp_array[32]->multiply_region.w32(gfp_array[32], region, r2, multby, nbytes, add);
 333 }
 334
 335 void galois_w8_region_xor(void *src, void *dest, int nbytes)
 336 {
 337   if (gfp_array[8] == NULL) {
 338     galois_init(8);
 339   }
 340   gfp_array[8]->multiply_region.w32(gfp_array[32], src, dest, 1, nbytes, 1);
 341 }
 342
 343 void galois_w16_region_xor(void *src, void *dest, int nbytes)
 344 {
 345   if (gfp_array[16] == NULL) {
 346     galois_init(16);
 347   }
 348   gfp_array[16]->multiply_region.w32(gfp_array[16], src, dest, 1, nbytes, 1);
 349 }
 350
 351 void galois_w32_region_xor(void *src, void *dest, int nbytes)
 352 {
 353   if (gfp_array[32] == NULL) {
 354     galois_init(32);
 355   }
 356   gfp_array[32]->multiply_region.w32(gfp_array[32], src, dest, 1, nbytes, 1);
 357 }
 358
 359 void galois_region_xor(char *src, char *dest, int nbytes)
 360 {
 361   if (nbytes >= 16) {
 362     galois_w32_region_xor(src, dest, nbytes);
 363   } else {
 364     int i = 0;
 365     for (i = 0; i < nbytes; i++) {
 366       *dest ^= *src;
 367       dest++;
 368       src++;
 369     }
 370   }
 371 }
 372
 373 int galois_inverse(int y, int w)
 374 {
 375   if (y == 0) return -1;
 376   return galois_single_divide(1, y, w);
 377 }