ceph/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 #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 static void galois_init(int w)
 186 {
 187   if (w <= 0 || w > 32) {
 188     fprintf(stderr, "ERROR -- cannot init default Galois field for w=%d\n", w);
 189     assert(0);
 190   }
 191
 192   switch (galois_init_default_field(w)) {
 193   case ENOMEM:
 194     fprintf(stderr, "ERROR -- cannot allocate memory for Galois field w=%d\n", w);
 195     assert(0);
 196     break;
 197   case EINVAL:
 198     fprintf(stderr, "ERROR -- cannot init default Galois field for w=%d\n", w);
 199     assert(0);
 200     break;
 201   }
 202 }
 203
 204
 205 static int is_valid_gf(gf_t *gf, int w)
 206 {
 207   // TODO: I assume we may eventually
 208   // want to do w=64 and 128, so w
 209   // will be needed to perform this check
 210   (void)w;
 211
 212   if (gf == NULL) {
 213     return 0;
 214   }
 215   if (gf->multiply.w32 == NULL) {
 216     return 0;
 217   }
 218   if (gf->multiply_region.w32 == NULL) {
 219     return 0;
 220   }
 221   if (gf->divide.w32 == NULL) {
 222     return 0;
 223   }
 224   if (gf->inverse.w32 == NULL) {
 225     return 0;
 226   }
 227   if (gf->extract_word.w32 == NULL) {
 228     return 0;
 229   }
 230
 231   return 1;
 232 }
 233
 234 void galois_change_technique(gf_t *gf, int w)
 235 {
 236   if (w <= 0 || w > 32) {
 237     fprintf(stderr, "ERROR -- cannot support Galois field for w=%d\n", w);
 238     assert(0);
 239   }
 240
 241   if (!is_valid_gf(gf, w)) {
 242     fprintf(stderr, "ERROR -- overriding with invalid Galois field for w=%d\n", w);
 243     assert(0);
 244   }
 245
 246   if (gfp_array[w] != NULL) {
 247     gf_free(gfp_array[w], gfp_is_composite[w]);
 248   }
 249
 250   gfp_array[w] = gf;
 251 }
 252
 253 int galois_single_multiply(int x, int y, int w)
 254 {
 255   if (x == 0 || y == 0) return 0;
 256
 257   if (gfp_array[w] == NULL) {
 258     galois_init(w);
 259   }
 260
 261   if (w <= 32) {
 262     return gfp_array[w]->multiply.w32(gfp_array[w], x, y);
 263   } else {
 264     fprintf(stderr, "ERROR -- Galois field not implemented for w=%d\n", w);
 265     return 0;
 266   }
 267 }
 268
 269 int galois_single_divide(int x, int y, int w)
 270 {
 271   if (x == 0) return 0;
 272   if (y == 0) return -1;
 273
 274   if (gfp_array[w] == NULL) {
 275     galois_init(w);
 276   }
 277
 278   if (w <= 32) {
 279     return gfp_array[w]->divide.w32(gfp_array[w], x, y);
 280   } else {
 281     fprintf(stderr, "ERROR -- Galois field not implemented for w=%d\n", w);
 282     return 0;
 283   }
 284 }
 285
 286 void galois_w08_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[8] == NULL) {
 293     galois_init(8);
 294   }
 295   gfp_array[8]->multiply_region.w32(gfp_array[8], region, r2, multby, nbytes, add);
 296 }
 297
 298 void galois_w16_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[16] == NULL) {
 305     galois_init(16);
 306   }
 307   gfp_array[16]->multiply_region.w32(gfp_array[16], region, r2, multby, nbytes, add);
 308 }
 309
 310
 311 void galois_w32_region_multiply(char *region,      /* Region to multiply */
 312                                   int multby,       /* Number to multiply by */
 313                                   int nbytes,        /* Number of bytes in region */
 314                                   char *r2,          /* If r2 != NULL, products go here */
 315                                   int add)
 316 {
 317   if (gfp_array[32] == NULL) {
 318     galois_init(32);
 319   }
 320   gfp_array[32]->multiply_region.w32(gfp_array[32], region, r2, multby, nbytes, add);
 321 }
 322
 323 void galois_w8_region_xor(void *src, void *dest, int nbytes)
 324 {
 325   if (gfp_array[8] == NULL) {
 326     galois_init(8);
 327   }
 328   gfp_array[8]->multiply_region.w32(gfp_array[32], src, dest, 1, nbytes, 1);
 329 }
 330
 331 void galois_w16_region_xor(void *src, void *dest, int nbytes)
 332 {
 333   if (gfp_array[16] == NULL) {
 334     galois_init(16);
 335   }
 336   gfp_array[16]->multiply_region.w32(gfp_array[16], src, dest, 1, nbytes, 1);
 337 }
 338
 339 void galois_w32_region_xor(void *src, void *dest, int nbytes)
 340 {
 341   if (gfp_array[32] == NULL) {
 342     galois_init(32);
 343   }
 344   gfp_array[32]->multiply_region.w32(gfp_array[32], src, dest, 1, nbytes, 1);
 345 }
 346
 347 void galois_region_xor(char *src, char *dest, int nbytes)
 348 {
 349   if (nbytes >= 16) {
 350     galois_w32_region_xor(src, dest, nbytes);
 351   } else {
 352     int i = 0;
 353     for (i = 0; i < nbytes; i++) {
 354       *dest ^= *src;
 355       dest++;
 356       src++;
 357     }
 358   }
 359 }
 360
 361 int galois_inverse(int y, int w)
 362 {
 363   if (y == 0) return -1;
 364   return galois_single_divide(1, y, w);
 365 }