ceph/src/erasure-code/jerasure/gf-complete/src/gf_general.c

   1 /*
   2  * GF-Complete: A Comprehensive Open Source Library for Galois Field Arithmetic
   3  * James S. Plank, Ethan L. Miller, Kevin M. Greenan,
   4  * Benjamin A. Arnold, John A. Burnum, Adam W. Disney, Allen C. McBride.
   5  *
   6  * gf_general.c
   7  *
   8  * This file has helper routines for doing basic GF operations with any
   9  * legal value of w.  The problem is that w <= 32, w=64 and w=128 all have
  10  * different data types, which is a pain.  The procedures in this file try
  11  * to alleviate that pain.  They are used in gf_unit and gf_time.
  12  */
  13
  14 #include <stdio.h>
  15 #include <getopt.h>
  16 #include <stdint.h>
  17 #include <string.h>
  18 #include <stdlib.h>
  19 #include <time.h>
  20 #include <assert.h>
  21
  22 #include "gf_complete.h"
  23 #include "gf_int.h"
  24 #include "gf_method.h"
  25 #include "gf_rand.h"
  26 #include "gf_general.h"
  27
  28 void gf_general_set_zero(gf_general_t *v, int w)
  29 {
  30   if (w <= 32) {
  31     v->w32 = 0;
  32   } else if (w <= 64) {
  33     v->w64 = 0;
  34   } else {
  35     v->w128[0] = 0;
  36     v->w128[1] = 0;
  37   }
  38 }
  39
  40 void gf_general_set_one(gf_general_t *v, int w)
  41 {
  42   if (w <= 32) {
  43     v->w32 = 1;
  44   } else if (w <= 64) {
  45     v->w64 = 1;
  46   } else {
  47     v->w128[0] = 0;
  48     v->w128[1] = 1;
  49   }
  50 }
  51
  52 void gf_general_set_two(gf_general_t *v, int w)
  53 {
  54   if (w <= 32) {
  55     v->w32 = 2;
  56   } else if (w <= 64) {
  57     v->w64 = 2;
  58   } else {
  59     v->w128[0] = 0;
  60     v->w128[1] = 2;
  61   }
  62 }
  63
  64 int gf_general_is_zero(gf_general_t *v, int w)
  65 {
  66   if (w <= 32) {
  67     return (v->w32 == 0);
  68   } else if (w <= 64) {
  69     return (v->w64 == 0);
  70   } else {
  71     return (v->w128[0] == 0 && v->w128[1] == 0);
  72   }
  73 }
  74
  75 int gf_general_is_one(gf_general_t *v, int w)
  76 {
  77   if (w <= 32) {
  78     return (v->w32 == 1);
  79   } else if (w <= 64) {
  80     return (v->w64 == 1);
  81   } else {
  82     return (v->w128[0] == 0 && v->w128[1] == 1);
  83   }
  84 }
  85
  86 void gf_general_set_random(gf_general_t *v, int w, int zero_ok)
  87 {
  88   if (w <= 32) {
  89       v->w32 = MOA_Random_W(w, zero_ok);
  90   } else if (w <= 64) {
  91     while (1) {
  92       v->w64 = MOA_Random_64();
  93       if (v->w64 != 0 || zero_ok) return;
  94     }
  95   } else {
  96     while (1) {
  97       MOA_Random_128(v->w128);
  98       if (v->w128[0] != 0 || v->w128[1] != 0 || zero_ok) return;
  99     }
 100   }
 101 }
 102
 103 void gf_general_val_to_s(gf_general_t *v, int w, char *s, int hex)
 104 {
 105   if (w <= 32) {
 106     if (hex) {
 107       sprintf(s, "%x", v->w32);
 108     } else {
 109       sprintf(s, "%u", v->w32);
 110     }
 111   } else if (w <= 64) {
 112     if (hex) {
 113       sprintf(s, "%llx", (long long unsigned int) v->w64);
 114     } else {
 115       sprintf(s, "%lld", (long long unsigned int) v->w64);
 116     }
 117   } else {
 118     if (v->w128[0] == 0) {
 119       sprintf(s, "%llx", (long long unsigned int) v->w128[1]);
 120     } else {
 121       sprintf(s, "%llx%016llx", (long long unsigned int) v->w128[0],
 122                                 (long long unsigned int) v->w128[1]);
 123     }
 124   }
 125 }
 126
 127 int gf_general_s_to_val(gf_general_t *v, int w, char *s, int hex)
 128 {
 129   int l;
 130   int save;
 131
 132   if (w <= 32) {
 133     if (hex) {
 134       if (sscanf(s, "%x", &(v->w32)) == 0) return 0;
 135     } else {
 136       if (sscanf(s, "%u", &(v->w32)) == 0) return 0;
 137     }
 138     if (w == 32) return 1;
 139     if (w == 31) {
 140       if (v->w32 & ((gf_val_32_t)1 << 31)) return 0;
 141       return 1;
 142     }
 143     if (v->w32 & ~((1 << w)-1)) return 0;
 144     return 1;
 145   } else if (w <= 64) {
 146     if (hex) return (sscanf(s, "%llx", (long long unsigned int *) (&(v->w64))) == 1);
 147     return (sscanf(s, "%lld", (long long int *) (&(v->w64))) == 1);
 148   } else {
 149     if (!hex) return 0;
 150     l = strlen(s);
 151     if (l <= 16) {
 152       v->w128[0] = 0;
 153       return (sscanf(s, "%llx", (long long unsigned int *) (&(v->w128[1]))) == 1);
 154     } else {
 155       if (l > 32) return 0;
 156       save = s[l-16];
 157       s[l-16] = '\0';
 158       if (sscanf(s, "%llx", (long long unsigned int *) (&(v->w128[0]))) == 0) {
 159         s[l-16] = save;
 160         return 0;
 161       }
 162       return (sscanf(s+(l-16), "%llx", (long long unsigned int *) (&(v->w128[1]))) == 1);
 163     }
 164   }
 165 }
 166
 167 void gf_general_add(gf_t *gf, gf_general_t *a, gf_general_t *b, gf_general_t *c)
 168 {
 169   gf_internal_t *h;
 170   int w;
 171
 172   h = (gf_internal_t *) gf->scratch;
 173   w = h->w;
 174
 175   if (w <= 32) {
 176     c->w32 = a->w32 ^ b->w32;
 177   } else if (w <= 64) {
 178     c->w64 = a->w64 ^ b->w64;
 179   } else {
 180     c->w128[0] = a->w128[0] ^ b->w128[0];
 181     c->w128[1] = a->w128[1] ^ b->w128[1];
 182   }
 183 }
 184
 185 void gf_general_multiply(gf_t *gf, gf_general_t *a, gf_general_t *b, gf_general_t *c)
 186 {
 187   gf_internal_t *h;
 188   int w;
 189
 190   h = (gf_internal_t *) gf->scratch;
 191   w = h->w;
 192
 193   if (w <= 32) {
 194     c->w32 = gf->multiply.w32(gf, a->w32, b->w32);
 195   } else if (w <= 64) {
 196     c->w64 = gf->multiply.w64(gf, a->w64, b->w64);
 197   } else {
 198     gf->multiply.w128(gf, a->w128, b->w128, c->w128);
 199   }
 200 }
 201
 202 void gf_general_divide(gf_t *gf, gf_general_t *a, gf_general_t *b, gf_general_t *c)
 203 {
 204   gf_internal_t *h;
 205   int w;
 206
 207   h = (gf_internal_t *) gf->scratch;
 208   w = h->w;
 209
 210   if (w <= 32) {
 211     c->w32 = gf->divide.w32(gf, a->w32, b->w32);
 212   } else if (w <= 64) {
 213     c->w64 = gf->divide.w64(gf, a->w64, b->w64);
 214   } else {
 215     gf->divide.w128(gf, a->w128, b->w128, c->w128);
 216   }
 217 }
 218
 219 void gf_general_inverse(gf_t *gf, gf_general_t *a, gf_general_t *b)
 220 {
 221   gf_internal_t *h;
 222   int w;
 223
 224   h = (gf_internal_t *) gf->scratch;
 225   w = h->w;
 226
 227   if (w <= 32) {
 228     b->w32 = gf->inverse.w32(gf, a->w32);
 229   } else if (w <= 64) {
 230     b->w64 = gf->inverse.w64(gf, a->w64);
 231   } else {
 232     gf->inverse.w128(gf, a->w128, b->w128);
 233   }
 234 }
 235
 236 int gf_general_are_equal(gf_general_t *v1, gf_general_t *v2, int w)
 237 {
 238   if (w <= 32) {
 239     return (v1->w32 == v2->w32);
 240   } else if (w <= 64) {
 241     return (v1->w64 == v2->w64);
 242   } else {
 243     return (v1->w128[0] == v2->w128[0] &&
 244             v1->w128[1] == v2->w128[1]);
 245   }
 246 }
 247
 248 void gf_general_do_region_multiply(gf_t *gf, gf_general_t *a, void *ra, void *rb, int bytes, int xor)
 249 {
 250   gf_internal_t *h;
 251   int w;
 252
 253   h = (gf_internal_t *) gf->scratch;
 254   w = h->w;
 255
 256   if (w <= 32) {
 257     gf->multiply_region.w32(gf, ra, rb, a->w32, bytes, xor);
 258   } else if (w <= 64) {
 259     gf->multiply_region.w64(gf, ra, rb, a->w64, bytes, xor);
 260   } else {
 261     gf->multiply_region.w128(gf, ra, rb, a->w128, bytes, xor);
 262   }
 263 }
 264
 265 void gf_general_do_region_check(gf_t *gf, gf_general_t *a, void *orig_a, void *orig_target, void *final_target, int bytes, int xor)
 266 {
 267   gf_internal_t *h;
 268   int w, words, i;
 269   gf_general_t oa, ot, ft, sb;
 270   char sa[50], soa[50], sot[50], sft[50], ssb[50];
 271
 272   h = (gf_internal_t *) gf->scratch;
 273   w = h->w;
 274
 275   words = (bytes * 8) / w;
 276   for (i = 0; i < words; i++) {
 277     if (w <= 32) {
 278       oa.w32 = gf->extract_word.w32(gf, orig_a, bytes, i);
 279       ot.w32 = gf->extract_word.w32(gf, orig_target, bytes, i);
 280       ft.w32 = gf->extract_word.w32(gf, final_target, bytes, i);
 281       sb.w32 = gf->multiply.w32(gf, a->w32, oa.w32);
 282       if (xor) sb.w32 ^= ot.w32;
 283     } else if (w <= 64) {
 284       oa.w64 = gf->extract_word.w64(gf, orig_a, bytes, i);
 285       ot.w64 = gf->extract_word.w64(gf, orig_target, bytes, i);
 286       ft.w64 = gf->extract_word.w64(gf, final_target, bytes, i);
 287       sb.w64 = gf->multiply.w64(gf, a->w64, oa.w64);
 288       if (xor) sb.w64 ^= ot.w64;
 289     } else {
 290       gf->extract_word.w128(gf, orig_a, bytes, i, oa.w128);
 291       gf->extract_word.w128(gf, orig_target, bytes, i, ot.w128);
 292       gf->extract_word.w128(gf, final_target, bytes, i, ft.w128);
 293       gf->multiply.w128(gf, a->w128, oa.w128, sb.w128);
 294       if (xor) {
 295         sb.w128[0] ^= ot.w128[0];
 296         sb.w128[1] ^= ot.w128[1];
 297       }
 298     }
 299
 300     if (!gf_general_are_equal(&ft, &sb, w)) {
 301
 302       fprintf(stderr,"Problem with region multiply (all values in hex):\n");
 303       fprintf(stderr,"   Target address base: 0x%lx.  Word 0x%x of 0x%x.  Xor: %d\n",
 304                  (unsigned long) final_target, i, words, xor);
 305       gf_general_val_to_s(a, w, sa, 1);
 306       gf_general_val_to_s(&oa, w, soa, 1);
 307       gf_general_val_to_s(&ot, w, sot, 1);
 308       gf_general_val_to_s(&ft, w, sft, 1);
 309       gf_general_val_to_s(&sb, w, ssb, 1);
 310       fprintf(stderr,"   Value: %s\n", sa);
 311       fprintf(stderr,"   Original source word: %s\n", soa);
 312       if (xor) fprintf(stderr,"   XOR with target word: %s\n", sot);
 313       fprintf(stderr,"   Product word: %s\n", sft);
 314       fprintf(stderr,"   It should be: %s\n", ssb);
 315       assert(0);
 316     }
 317   }
 318 }
 319
 320 void gf_general_set_up_single_timing_test(int w, void *ra, void *rb, int size)
 321 {
 322   void *top;
 323   gf_general_t g;
 324   uint8_t *r8, *r8a;
 325   uint16_t *r16;
 326   uint32_t *r32;
 327   uint64_t *r64;
 328   int i;
 329
 330   top = (uint8_t *)rb+size;
 331
 332   /* If w is 8, 16, 32, 64 or 128, fill the regions with random bytes.
 333      However, don't allow for zeros in rb, because that will screw up
 334      division.
 335
 336      When w is 4, you fill the regions with random 4-bit words in each byte.
 337
 338      Otherwise, treat every four bytes as an uint32_t
 339      and fill it with a random value mod (1 << w).
 340    */
 341
 342   if (w == 8 || w == 16 || w == 32 || w == 64 || w == 128) {
 343     MOA_Fill_Random_Region (ra, size);
 344     while (rb < top) {
 345       gf_general_set_random(&g, w, 0);
 346       switch (w) {
 347         case 8:
 348           r8 = (uint8_t *) rb;
 349           *r8 = g.w32;
 350           break;
 351         case 16:
 352           r16 = (uint16_t *) rb;
 353           *r16 = g.w32;
 354           break;
 355         case 32:
 356           r32 = (uint32_t *) rb;
 357           *r32 = g.w32;
 358           break;
 359         case 64:
 360           r64 = (uint64_t *) rb;
 361           *r64 = g.w64;
 362           break;
 363         case 128:
 364           r64 = (uint64_t *) rb;
 365           r64[0] = g.w128[0];
 366           r64[1] = g.w128[1];
 367           break;
 368       }
 369       rb = (uint8_t *)rb + (w/8);
 370     }
 371   } else if (w == 4) {
 372     r8a = (uint8_t *) ra;
 373     r8 = (uint8_t *) rb;
 374     while (r8 < (uint8_t *) top) {
 375       gf_general_set_random(&g, w, 1);
 376       *r8a = g.w32;
 377       gf_general_set_random(&g, w, 0);
 378       *r8 = g.w32;
 379       r8a++;
 380       r8++;
 381     }
 382   } else {
 383     r32 = (uint32_t *) ra;
 384     for (i = 0; i < size/4; i++) r32[i] = MOA_Random_W(w, 1);
 385     r32 = (uint32_t *) rb;
 386     for (i = 0; i < size/4; i++) r32[i] = MOA_Random_W(w, 0);
 387   }
 388 }
 389
 390 /* This sucks, but in order to time, you really need to avoid putting ifs in
 391    the inner loops.  So, I'm doing a separate timing test for each w:
 392    (4 & 8), 16, 32, 64, 128 and everything else.  Fortunately, the "everything else"
 393    tests can be equivalent to w=32.
 394
 395    I'm also putting the results back into ra, because otherwise, the optimizer might
 396    figure out that we're not really doing anything in the inner loops and it
 397    will chuck that. */
 398
 399 int gf_general_do_single_timing_test(gf_t *gf, void *ra, void *rb, int size, char test)
 400 {
 401   gf_internal_t *h;
 402   void *top;
 403   uint8_t *r8a, *r8b, *top8;
 404   uint16_t *r16a, *r16b, *top16;
 405   uint32_t *r32a, *r32b, *top32;
 406   uint64_t *r64a, *r64b, *top64, *r64c;
 407   int w, rv;
 408
 409   h = (gf_internal_t *) gf->scratch;
 410   w = h->w;
 411   top = (uint8_t *)ra + size;
 412
 413   if (w == 8 || w == 4) {
 414     r8a = (uint8_t *) ra;
 415     r8b = (uint8_t *) rb;
 416     top8 = (uint8_t *) top;
 417     if (test == 'M') {
 418       while (r8a < top8) {
 419         *r8a = gf->multiply.w32(gf, *r8a, *r8b);
 420         r8a++;
 421         r8b++;
 422       }
 423     } else if (test == 'D') {
 424       while (r8a < top8) {
 425         *r8a = gf->divide.w32(gf, *r8a, *r8b);
 426         r8a++;
 427         r8b++;
 428       }
 429     } else if (test == 'I') {
 430       while (r8a < top8) {
 431         *r8a = gf->inverse.w32(gf, *r8a);
 432         r8a++;
 433       }
 434     }
 435     return (top8 - (uint8_t *) ra);
 436   }
 437
 438   if (w == 16) {
 439     r16a = (uint16_t *) ra;
 440     r16b = (uint16_t *) rb;
 441     top16 = (uint16_t *) top;
 442     if (test == 'M') {
 443       while (r16a < top16) {
 444         *r16a = gf->multiply.w32(gf, *r16a, *r16b);
 445         r16a++;
 446         r16b++;
 447       }
 448     } else if (test == 'D') {
 449       while (r16a < top16) {
 450         *r16a = gf->divide.w32(gf, *r16a, *r16b);
 451         r16a++;
 452         r16b++;
 453       }
 454     } else if (test == 'I') {
 455       while (r16a < top16) {
 456         *r16a = gf->inverse.w32(gf, *r16a);
 457         r16a++;
 458       }
 459     }
 460     return (top16 - (uint16_t *) ra);
 461   }
 462   if (w <= 32) {
 463     r32a = (uint32_t *) ra;
 464     r32b = (uint32_t *) rb;
 465     top32 = (uint32_t *) ra + (size/4); /* This is for the "everything elses" */
 466
 467     if (test == 'M') {
 468       while (r32a < top32) {
 469         *r32a = gf->multiply.w32(gf, *r32a, *r32b);
 470         r32a++;
 471         r32b++;
 472       }
 473     } else if (test == 'D') {
 474       while (r32a < top32) {
 475         *r32a = gf->divide.w32(gf, *r32a, *r32b);
 476         r32a++;
 477         r32b++;
 478       }
 479     } else if (test == 'I') {
 480       while (r32a < top32) {
 481         *r32a = gf->inverse.w32(gf, *r32a);
 482         r32a++;
 483       }
 484     }
 485     return (top32 - (uint32_t *) ra);
 486   }
 487   if (w == 64) {
 488     r64a = (uint64_t *) ra;
 489     r64b = (uint64_t *) rb;
 490     top64 = (uint64_t *) top;
 491     if (test == 'M') {
 492       while (r64a < top64) {
 493         *r64a = gf->multiply.w64(gf, *r64a, *r64b);
 494         r64a++;
 495         r64b++;
 496       }
 497     } else if (test == 'D') {
 498       while (r64a < top64) {
 499         *r64a = gf->divide.w64(gf, *r64a, *r64b);
 500         r64a++;
 501         r64b++;
 502       }
 503     } else if (test == 'I') {
 504       while (r64a < top64) {
 505         *r64a = gf->inverse.w64(gf, *r64a);
 506         r64a++;
 507       }
 508     }
 509     return (top64 - (uint64_t *) ra);
 510   }
 511   if (w == 128) {
 512     r64a = (uint64_t *) ra;
 513     r64c = r64a;
 514     r64a += 2;
 515     r64b = (uint64_t *) rb;
 516     top64 = (uint64_t *) top;
 517     rv = (top64 - r64a)/2;
 518     if (test == 'M') {
 519       while (r64a < top64) {
 520         gf->multiply.w128(gf, r64a, r64b, r64c);
 521         r64a += 2;
 522         r64b += 2;
 523       }
 524     } else if (test == 'D') {
 525       while (r64a < top64) {
 526         gf->divide.w128(gf, r64a, r64b, r64c);
 527         r64a += 2;
 528         r64b += 2;
 529       }
 530     } else if (test == 'I') {
 531       while (r64a < top64) {
 532         gf->inverse.w128(gf, r64a, r64c);
 533         r64a += 2;
 534       }
 535     }
 536     return rv;
 537   }
 538   return 0;
 539 }