IDA_new/gf-complete/test/gf_unit.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_unit.c
   7  *
   8  * Performs unit testing for gf arithmetic
   9  */
  10
  11 #include "config.h"
  12
  13 #ifdef HAVE_POSIX_MEMALIGN
  14 #ifndef _XOPEN_SOURCE
  15 #define _XOPEN_SOURCE 600
  16 #endif
  17 #endif
  18
  19 #include <stdio.h>
  20 #include <getopt.h>
  21 #include <stdint.h>
  22 #include <string.h>
  23 #include <stdlib.h>
  24 #include <time.h>
  25 #include <signal.h>
  26
  27 #include "gf_complete.h"
  28 #include "gf_int.h"
  29 #include "gf_method.h"
  30 #include "gf_rand.h"
  31 #include "gf_general.h"
  32
  33 #define REGION_SIZE (16384)
  34 #define RMASK (0x00000000ffffffffLL)
  35 #define LMASK (0xffffffff00000000LL)
  36
  37 void problem(char *s)
  38 {
  39   fprintf(stderr, "Unit test failed.\n");
  40   fprintf(stderr, "%s\n", s);
  41   exit(1);
  42 }
  43
  44 char *BM = "Bad Method: ";
  45
  46 void usage(char *s)
  47 {
  48   fprintf(stderr, "usage: gf_unit w tests seed [method] - does unit testing in GF(2^w)\n");
  49   fprintf(stderr, "\n");
  50   fprintf(stderr, "Legal w are: 1 - 32, 64 and 128\n");
  51   fprintf(stderr, "           128 is hex only (i.e. '128' will be an error - do '128h')\n");
  52   fprintf(stderr, "\n");
  53   fprintf(stderr, "Tests may be any combination of:\n");
  54   fprintf(stderr, "       A: All\n");
  55   fprintf(stderr, "       S: Single operations (multiplication/division)\n");
  56   fprintf(stderr, "       R: Region operations\n");
  57   fprintf(stderr, "       V: Verbose Output\n");
  58   fprintf(stderr, "\n");
  59   fprintf(stderr, "Use -1 for time(0) as a seed.\n");
  60   fprintf(stderr, "\n");
  61   if (s == BM) {
  62     fprintf(stderr, "%s", BM);
  63     gf_error();
  64   } else if (s != NULL) {
  65     fprintf(stderr, "%s\n", s);
  66   }
  67   exit(1);
  68 }
  69
  70 void SigHandler(int v)
  71 {
  72   fprintf(stderr, "Problem: SegFault!\n");
  73   fflush(stdout);
  74   exit(2);
  75 }
  76
  77 int main(int argc, char **argv)
  78 {
  79   signal(SIGSEGV, SigHandler);
  80
  81   int w, i, verbose, single, region, top;
  82   int s_start, d_start, bytes, xor, alignment_test;
  83   gf_t   gf, gf_def;
  84   time_t t0;
  85   gf_internal_t *h;
  86   gf_general_t *a, *b, *c, *d;
  87   uint8_t a8, b8, c8, *mult4 = NULL, *mult8 = NULL;
  88   uint16_t a16, b16, c16, *log16 = NULL, *alog16 = NULL;
  89   char as[50], bs[50], cs[50], ds[50];
  90   uint32_t mask = 0;
  91   char *ra, *rb, *rc, *rd, *target;
  92   int align;
  93 #ifndef HAVE_POSIX_MEMALIGN
  94   char *malloc_ra, *malloc_rb, *malloc_rc, *malloc_rd;
  95 #endif
  96
  97
  98   if (argc < 4) usage(NULL);
  99
 100   if (sscanf(argv[1], "%d", &w) == 0){
 101     usage("Bad w\n");
 102   }
 103
 104   if (sscanf(argv[3], "%ld", &t0) == 0) usage("Bad seed\n");
 105   if (t0 == -1) t0 = time(0);
 106   MOA_Seed(t0);
 107
 108   if (w > 32 && w != 64 && w != 128) usage("Bad w");
 109
 110   if (create_gf_from_argv(&gf, w, argc, argv, 4) == 0) {
 111     usage(BM);
 112   }
 113
 114   printf("Args: ");
 115   for (i = 1; i < argc; i++) {
 116     printf ("%s ", argv[i]);
 117   }
 118   printf("/ size (bytes): %d\n", gf_size(&gf));
 119
 120   for (i = 0; i < strlen(argv[2]); i++) {
 121     if (strchr("ASRV", argv[2][i]) == NULL) usage("Bad test\n");
 122   }
 123
 124   h = (gf_internal_t *) gf.scratch;
 125   a = (gf_general_t *) malloc(sizeof(gf_general_t));
 126   b = (gf_general_t *) malloc(sizeof(gf_general_t));
 127   c = (gf_general_t *) malloc(sizeof(gf_general_t));
 128   d = (gf_general_t *) malloc(sizeof(gf_general_t));
 129
 130 #if HAVE_POSIX_MEMALIGN
 131   if (posix_memalign((void **) &ra, 16, sizeof(char)*REGION_SIZE))
 132     ra = NULL;
 133   if (posix_memalign((void **) &rb, 16, sizeof(char)*REGION_SIZE))
 134     rb = NULL;
 135   if (posix_memalign((void **) &rc, 16, sizeof(char)*REGION_SIZE))
 136     rc = NULL;
 137   if (posix_memalign((void **) &rd, 16, sizeof(char)*REGION_SIZE))
 138     rd = NULL;
 139 #else
 140   //15 bytes extra to make sure it's 16byte aligned
 141   malloc_ra = (char *) malloc(sizeof(char)*REGION_SIZE+15);
 142   malloc_rb = (char *) malloc(sizeof(char)*REGION_SIZE+15);
 143   malloc_rc = (char *) malloc(sizeof(char)*REGION_SIZE+15);
 144   malloc_rd = (char *) malloc(sizeof(char)*REGION_SIZE+15);
 145   ra = (uint8_t *) (((uintptr_t) malloc_ra + 15) & ~((uintptr_t) 0xf));
 146   rb = (uint8_t *) (((uintptr_t) malloc_rb + 15) & ~((uintptr_t) 0xf));
 147   rc = (uint8_t *) (((uintptr_t) malloc_rc + 15) & ~((uintptr_t) 0xf));
 148   rd = (uint8_t *) (((uintptr_t) malloc_rd + 15) & ~((uintptr_t) 0xf));
 149 #endif
 150
 151   if (w <= 32) {
 152     mask = 0;
 153     for (i = 0; i < w; i++) mask |= (1 << i);
 154   }
 155
 156   verbose = (strchr(argv[2], 'V') != NULL);
 157   single = (strchr(argv[2], 'S') != NULL || strchr(argv[2], 'A') != NULL);
 158   region = (strchr(argv[2], 'R') != NULL || strchr(argv[2], 'A') != NULL);
 159
 160   if (!gf_init_hard(&gf_def, w, GF_MULT_DEFAULT, GF_REGION_DEFAULT, GF_DIVIDE_DEFAULT,
 161       (h->mult_type != GF_MULT_COMPOSITE) ? h->prim_poly : 0, 0, 0, NULL, NULL))
 162     problem("No default for this value of w");
 163
 164   if (w == 4) {
 165     mult4 = gf_w4_get_mult_table(&gf);
 166   } else if (w == 8) {
 167     mult8 = gf_w8_get_mult_table(&gf);
 168   } else if (w == 16) {
 169     log16 = gf_w16_get_log_table(&gf);
 170     alog16 = gf_w16_get_mult_alog_table(&gf);
 171   }
 172
 173   if (verbose) printf("Seed: %ld\n", t0);
 174
 175   if (single) {
 176
 177     if (gf.multiply.w32 == NULL) problem("No multiplication operation defined.");
 178     if (verbose) { printf("Testing single multiplications/divisions.\n"); fflush(stdout); }
 179     if (w <= 10) {
 180       top = (1 << w)*(1 << w);
 181     } else {
 182       top = 1024*1024;
 183     }
 184     for (i = 0; i < top; i++) {
 185       if (w <= 10) {
 186         a->w32 = i % (1 << w);
 187         b->w32 = (i >> w);
 188
 189       //Allen: the following conditions were being run 10 times each. That didn't seem like nearly enough to
 190       //me for these special cases, so I converted to doing this mod stuff to easily make the number of times
 191       //run both larger and proportional to the total size of the run.
 192       } else {
 193         switch (i % 32)
 194         {
 195           case 0:
 196             gf_general_set_zero(a, w);
 197             gf_general_set_random(b, w, 1);
 198             break;
 199           case 1:
 200             gf_general_set_random(a, w, 1);
 201             gf_general_set_zero(b, w);
 202             break;
 203           case 2:
 204             gf_general_set_one(a, w);
 205             gf_general_set_random(b, w, 1);
 206             break;
 207           case 3:
 208             gf_general_set_random(a, w, 1);
 209             gf_general_set_one(b, w);
 210             break;
 211           default:
 212             gf_general_set_random(a, w, 1);
 213             gf_general_set_random(b, w, 1);
 214         }
 215       }
 216
 217       //Allen: the following special cases for w=64 are based on the code below for w=128.
 218       //These w=64 cases are based on Dr. Plank's suggestion because some of the methods for w=64
 219       //involve splitting it in two. I think they're less likely to give errors than the 128-bit case
 220       //though, because the 128 bit case is always split in two.
 221       //As with w=128, I'm arbitrarily deciding to do this sort of thing with a quarter of the cases
 222       if (w == 64) {
 223         switch (i % 32)
 224         {
 225           case 0: if (!gf_general_is_one(a, w)) a->w64 &= RMASK; break;
 226           case 1: if (!gf_general_is_one(a, w)) a->w64 &= LMASK; break;
 227           case 2: if (!gf_general_is_one(a, w)) a->w64 &= RMASK; if (!gf_general_is_one(b, w)) b->w64 &= RMASK; break;
 228           case 3: if (!gf_general_is_one(a, w)) a->w64 &= RMASK; if (!gf_general_is_one(b, w)) b->w64 &= LMASK; break;
 229           case 4: if (!gf_general_is_one(a, w)) a->w64 &= LMASK; if (!gf_general_is_one(b, w)) b->w64 &= RMASK; break;
 230           case 5: if (!gf_general_is_one(a, w)) a->w64 &= LMASK; if (!gf_general_is_one(b, w)) b->w64 &= LMASK; break;
 231           case 6: if (!gf_general_is_one(b, w)) b->w64 &= RMASK; break;
 232           case 7: if (!gf_general_is_one(b, w)) b->w64 &= LMASK; break;
 233         }
 234       }
 235
 236       //Allen: for w=128, we have important special cases where one half or the other of the number is all
 237       //zeros. The probability of hitting such a number randomly is 1^-64, so if we don't force these cases
 238       //we'll probably never hit them. This could be implemented more efficiently by changing the set-random
 239       //function for w=128, but I think this is easier to follow.
 240       //I'm arbitrarily deciding to do this sort of thing with a quarter of the cases
 241       if (w == 128) {
 242         switch (i % 32)
 243         {
 244           case 0: if (!gf_general_is_one(a, w)) a->w128[0] = 0; break;
 245           case 1: if (!gf_general_is_one(a, w)) a->w128[1] = 0; break;
 246           case 2: if (!gf_general_is_one(a, w)) a->w128[0] = 0; if (!gf_general_is_one(b, w)) b->w128[0] = 0; break;
 247           case 3: if (!gf_general_is_one(a, w)) a->w128[0] = 0; if (!gf_general_is_one(b, w)) b->w128[1] = 0; break;
 248           case 4: if (!gf_general_is_one(a, w)) a->w128[1] = 0; if (!gf_general_is_one(b, w)) b->w128[0] = 0; break;
 249           case 5: if (!gf_general_is_one(a, w)) a->w128[1] = 0; if (!gf_general_is_one(b, w)) b->w128[1] = 0; break;
 250           case 6: if (!gf_general_is_one(b, w)) b->w128[0] = 0; break;
 251           case 7: if (!gf_general_is_one(b, w)) b->w128[1] = 0; break;
 252         }
 253       }
 254
 255       gf_general_multiply(&gf, a, b, c);
 256
 257       /* If w is 4, 8 or 16, then there are inline multiplication/division methods.
 258          Test them here. */
 259
 260       if (w == 4 && mult4 != NULL) {
 261         a8 = a->w32;
 262         b8 = b->w32;
 263         c8 = GF_W4_INLINE_MULTDIV(mult4, a8, b8);
 264         if (c8 != c->w32) {
 265           printf("Error in inline multiplication. %d * %d.  Inline = %d.  Default = %d.\n",
 266              a8, b8, c8, c->w32);
 267           exit(1);
 268         }
 269       }
 270
 271       if (w == 8 && mult8 != NULL) {
 272         a8 = a->w32;
 273         b8 = b->w32;
 274         c8 = GF_W8_INLINE_MULTDIV(mult8, a8, b8);
 275         if (c8 != c->w32) {
 276           printf("Error in inline multiplication. %d * %d.  Inline = %d.  Default = %d.\n",
 277              a8, b8, c8, c->w32);
 278           exit(1);
 279         }
 280       }
 281
 282       if (w == 16 && log16 != NULL) {
 283         a16 = a->w32;
 284         b16 = b->w32;
 285         c16 = GF_W16_INLINE_MULT(log16, alog16, a16, b16);
 286         if (c16 != c->w32) {
 287           printf("Error in inline multiplication. %d * %d.  Inline = %d.  Default = %d.\n",
 288              a16, b16, c16, c->w32);
 289           printf("%d %d\n", log16[a16], log16[b16]);
 290           top = log16[a16] + log16[b16];
 291           printf("%d %d\n", top, alog16[top]);
 292           exit(1);
 293         }
 294       }
 295
 296       /* If this is not composite, then first test against the default: */
 297
 298       if (h->mult_type != GF_MULT_COMPOSITE) {
 299         gf_general_multiply(&gf_def, a, b, d);
 300
 301         if (!gf_general_are_equal(c, d, w)) {
 302           gf_general_val_to_s(a, w, as, 1);
 303           gf_general_val_to_s(b, w, bs, 1);
 304           gf_general_val_to_s(c, w, cs, 1);
 305           gf_general_val_to_s(d, w, ds, 1);
 306           printf("Error in single multiplication (all numbers in hex):\n\n");
 307           printf("  gf.multiply(gf, %s, %s) = %s\n", as, bs, cs);
 308           printf("  The default gf multiplier returned %s\n", ds);
 309           exit(1);
 310         }
 311       }
 312
 313       /* Now, we also need to double-check by other means, in case the default is wanky,
 314          and when we're performing composite operations. Start with 0 and 1, where we know
 315          what the result should be. */
 316
 317       if (gf_general_is_zero(a, w) || gf_general_is_zero(b, w) ||
 318           gf_general_is_one(a, w)  || gf_general_is_one(b, w)) {
 319         if (((gf_general_is_zero(a, w) || gf_general_is_zero(b, w)) && !gf_general_is_zero(c, w)) ||
 320             (gf_general_is_one(a, w) && !gf_general_are_equal(b, c, w)) ||
 321             (gf_general_is_one(b, w) && !gf_general_are_equal(a, c, w))) {
 322           gf_general_val_to_s(a, w, as, 1);
 323           gf_general_val_to_s(b, w, bs, 1);
 324           gf_general_val_to_s(c, w, cs, 1);
 325           printf("Error in single multiplication (all numbers in hex):\n\n");
 326           printf("  gf.multiply(gf, %s, %s) = %s, which is clearly wrong.\n", as, bs, cs);
 327           exit(1);
 328         }
 329       }
 330
 331       /* Dumb check to make sure that it's not returning numbers that are too big: */
 332
 333       if (w < 32 && (c->w32 & mask) != c->w32) {
 334         gf_general_val_to_s(a, w, as, 1);
 335         gf_general_val_to_s(b, w, bs, 1);
 336         gf_general_val_to_s(c, w, cs, 1);
 337         printf("Error in single multiplication (all numbers in hex):\n\n");
 338         printf("  gf.multiply.w32(gf, %s, %s) = %s, which is too big.\n", as, bs, cs);
 339         exit(1);
 340       }
 341
 342       /* Finally, let's check to see that multiplication and division work together */
 343
 344       if (!gf_general_is_zero(a, w)) {
 345         gf_general_divide(&gf, c, a, d);
 346         if (!gf_general_are_equal(b, d, w)) {
 347           gf_general_val_to_s(a, w, as, 1);
 348           gf_general_val_to_s(b, w, bs, 1);
 349           gf_general_val_to_s(c, w, cs, 1);
 350           gf_general_val_to_s(d, w, ds, 1);
 351           printf("Error in single multiplication/division (all numbers in hex):\n\n");
 352           printf("  gf.multiply(gf, %s, %s) = %s, but gf.divide(gf, %s, %s) = %s\n", as, bs, cs, cs, as, ds);
 353           exit(1);
 354         }
 355       }
 356
 357     }
 358   }
 359
 360   if (region) {
 361     if (verbose) { printf("Testing region multiplications\n"); fflush(stdout); }
 362     for (i = 0; i < 1024; i++) {
 363       //Allen: changing to a switch thing as with the single ops to make things proportional
 364       switch (i % 32)
 365       {
 366         case 0:
 367           gf_general_set_zero(a, w);
 368           break;
 369         case 1:
 370           gf_general_set_one(a, w);
 371           break;
 372         case 2:
 373           gf_general_set_two(a, w);
 374           break;
 375         default:
 376           gf_general_set_random(a, w, 1);
 377       }
 378       MOA_Fill_Random_Region(ra, REGION_SIZE);
 379       MOA_Fill_Random_Region(rb, REGION_SIZE);
 380       xor = (i/32)%2;
 381       align = w/8;
 382       if (align == 0) align = 1;
 383       if (align > 16) align = 16;
 384
 385       /* JSP - Cauchy test.  When w < 32 & it doesn't equal 4, 8 or 16, the default is
 386          equal to GF_REGION_CAUCHY, even if GF_REGION_CAUCHY is not set. We are testing
 387          three alignments here:
 388
 389          1. Anything goes -- no alignment guaranteed.
 390          2. Perfect alignment.  Here src and dest must be aligned wrt each other,
 391             and bytes must be a multiple of 16*w.
 392          3. Imperfect alignment.  Here we'll have src and dest be aligned wrt each
 393             other, but bytes is simply a multiple of w.  That means some XOR's will
 394             be aligned, and some won't.
 395        */
 396
 397       if ((h->region_type & GF_REGION_CAUCHY) || (w < 32 && w != 4 && w != 8 && w != 16)) {
 398         alignment_test = (i%3);
 399
 400         s_start = MOA_Random_W(5, 1);
 401         if (alignment_test == 0) {
 402           d_start = MOA_Random_W(5, 1);
 403         } else {
 404           d_start = s_start;
 405         }
 406
 407         bytes = (d_start > s_start) ? REGION_SIZE - d_start : REGION_SIZE - s_start;
 408         bytes -= MOA_Random_W(5, 1);
 409         if (alignment_test == 1) {
 410           bytes -= (bytes % (w*16));
 411         } else {
 412           bytes -= (bytes % w);
 413         }
 414
 415         target = rb;
 416
 417       /* JSP - Otherwise, we're testing a non-cauchy test, and alignment
 418         must be more strict.  We have to make sure that the regions are
 419         aligned wrt each other on 16-byte pointers.  */
 420
 421       } else {
 422         s_start = MOA_Random_W(5, 1) * align;
 423         d_start = s_start;
 424         bytes = REGION_SIZE - s_start - MOA_Random_W(5, 1);
 425         bytes -= (bytes % align);
 426
 427         if (h->mult_type == GF_MULT_COMPOSITE && (h->region_type & GF_REGION_ALTMAP)) {
 428           target = rb ;
 429         } else {
 430           target = (i/64)%2 ? rb : ra;
 431         }
 432       }
 433
 434       memcpy(rc, ra, REGION_SIZE);
 435       memcpy(rd, target, REGION_SIZE);
 436       gf_general_do_region_multiply(&gf, a, ra+s_start, target+d_start, bytes, xor);
 437       gf_general_do_region_check(&gf, a, rc+s_start, rd+d_start, target+d_start, bytes, xor);
 438     }
 439   }
 440
 441   free(a);
 442   free(b);
 443   free(c);
 444   free(d);
 445 #ifdef HAVE_POSIX_MEMALIGN
 446   free(ra);
 447   free(rb);
 448   free(rc);
 449   free(rd);
 450 #else
 451   free(malloc_ra);
 452   free(malloc_rb);
 453   free(malloc_rc);
 454   free(malloc_rd);
 455 #endif
 456
 457   return 0;
 458 }