test/utils.c

   1 #include "utils.h"
   2 #include <signal.h>
   3
   4 #ifdef HAVE_GETTIMEOFDAY
   5 #include <sys/time.h>
   6 #else
   7 #include <time.h>
   8 #endif
   9
  10 #ifdef HAVE_UNISTD_H
  11 #include <unistd.h>
  12 #endif
  13
  14 #ifdef HAVE_SYS_MMAN_H
  15 #include <sys/mman.h>
  16 #endif
  17
  18 /* Random number seed
  19  */
  20
  21 uint32_t lcg_seed;
  22
  23 /*----------------------------------------------------------------------------*\
  24  *  CRC-32 version 2.0.0 by Craig Bruce, 2006-04-29.
  25  *
  26  *  This program generates the CRC-32 values for the files named in the
  27  *  command-line arguments.  These are the same CRC-32 values used by GZIP,
  28  *  PKZIP, and ZMODEM.  The Crc32_ComputeBuf () can also be detached and
  29  *  used independently.
  30  *
  31  *  THIS PROGRAM IS PUBLIC-DOMAIN SOFTWARE.
  32  *
  33  *  Based on the byte-oriented implementation "File Verification Using CRC"
  34  *  by Mark R. Nelson in Dr. Dobb's Journal, May 1992, pp. 64-67.
  35  *
  36  *  v1.0.0: original release.
  37  *  v1.0.1: fixed printf formats.
  38  *  v1.0.2: fixed something else.
  39  *  v1.0.3: replaced CRC constant table by generator function.
  40  *  v1.0.4: reformatted code, made ANSI C.  1994-12-05.
  41  *  v2.0.0: rewrote to use memory buffer & static table, 2006-04-29.
  42 \*----------------------------------------------------------------------------*/
  43
  44 /*----------------------------------------------------------------------------*\
  45  *  NAME:
  46  *     Crc32_ComputeBuf () - computes the CRC-32 value of a memory buffer
  47  *  DESCRIPTION:
  48  *     Computes or accumulates the CRC-32 value for a memory buffer.
  49  *     The 'inCrc32' gives a previously accumulated CRC-32 value to allow
  50  *     a CRC to be generated for multiple sequential buffer-fuls of data.
  51  *     The 'inCrc32' for the first buffer must be zero.
  52  *  ARGUMENTS:
  53  *     inCrc32 - accumulated CRC-32 value, must be 0 on first call
  54  *     buf     - buffer to compute CRC-32 value for
  55  *     bufLen  - number of bytes in buffer
  56  *  RETURNS:
  57  *     crc32 - computed CRC-32 value
  58  *  ERRORS:
  59  *     (no errors are possible)
  60 \*----------------------------------------------------------------------------*/
  61
  62 uint32_t
  63 compute_crc32 (uint32_t    in_crc32,
  64                const void *buf,
  65                size_t      buf_len)
  66 {
  67     static const uint32_t crc_table[256] = {
  68         0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA, 0x076DC419, 0x706AF48F,
  69         0xE963A535, 0x9E6495A3, 0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988,
  70         0x09B64C2B, 0x7EB17CBD, 0xE7B82D07, 0x90BF1D91, 0x1DB71064, 0x6AB020F2,
  71         0xF3B97148, 0x84BE41DE, 0x1ADAD47D, 0x6DDDE4EB, 0xF4D4B551, 0x83D385C7,
  72         0x136C9856, 0x646BA8C0, 0xFD62F97A, 0x8A65C9EC, 0x14015C4F, 0x63066CD9,
  73         0xFA0F3D63, 0x8D080DF5, 0x3B6E20C8, 0x4C69105E, 0xD56041E4, 0xA2677172,
  74         0x3C03E4D1, 0x4B04D447, 0xD20D85FD, 0xA50AB56B, 0x35B5A8FA, 0x42B2986C,
  75         0xDBBBC9D6, 0xACBCF940, 0x32D86CE3, 0x45DF5C75, 0xDCD60DCF, 0xABD13D59,
  76         0x26D930AC, 0x51DE003A, 0xC8D75180, 0xBFD06116, 0x21B4F4B5, 0x56B3C423,
  77         0xCFBA9599, 0xB8BDA50F, 0x2802B89E, 0x5F058808, 0xC60CD9B2, 0xB10BE924,
  78         0x2F6F7C87, 0x58684C11, 0xC1611DAB, 0xB6662D3D, 0x76DC4190, 0x01DB7106,
  79         0x98D220BC, 0xEFD5102A, 0x71B18589, 0x06B6B51F, 0x9FBFE4A5, 0xE8B8D433,
  80         0x7807C9A2, 0x0F00F934, 0x9609A88E, 0xE10E9818, 0x7F6A0DBB, 0x086D3D2D,
  81         0x91646C97, 0xE6635C01, 0x6B6B51F4, 0x1C6C6162, 0x856530D8, 0xF262004E,
  82         0x6C0695ED, 0x1B01A57B, 0x8208F4C1, 0xF50FC457, 0x65B0D9C6, 0x12B7E950,
  83         0x8BBEB8EA, 0xFCB9887C, 0x62DD1DDF, 0x15DA2D49, 0x8CD37CF3, 0xFBD44C65,
  84         0x4DB26158, 0x3AB551CE, 0xA3BC0074, 0xD4BB30E2, 0x4ADFA541, 0x3DD895D7,
  85         0xA4D1C46D, 0xD3D6F4FB, 0x4369E96A, 0x346ED9FC, 0xAD678846, 0xDA60B8D0,
  86         0x44042D73, 0x33031DE5, 0xAA0A4C5F, 0xDD0D7CC9, 0x5005713C, 0x270241AA,
  87         0xBE0B1010, 0xC90C2086, 0x5768B525, 0x206F85B3, 0xB966D409, 0xCE61E49F,
  88         0x5EDEF90E, 0x29D9C998, 0xB0D09822, 0xC7D7A8B4, 0x59B33D17, 0x2EB40D81,
  89         0xB7BD5C3B, 0xC0BA6CAD, 0xEDB88320, 0x9ABFB3B6, 0x03B6E20C, 0x74B1D29A,
  90         0xEAD54739, 0x9DD277AF, 0x04DB2615, 0x73DC1683, 0xE3630B12, 0x94643B84,
  91         0x0D6D6A3E, 0x7A6A5AA8, 0xE40ECF0B, 0x9309FF9D, 0x0A00AE27, 0x7D079EB1,
  92         0xF00F9344, 0x8708A3D2, 0x1E01F268, 0x6906C2FE, 0xF762575D, 0x806567CB,
  93         0x196C3671, 0x6E6B06E7, 0xFED41B76, 0x89D32BE0, 0x10DA7A5A, 0x67DD4ACC,
  94         0xF9B9DF6F, 0x8EBEEFF9, 0x17B7BE43, 0x60B08ED5, 0xD6D6A3E8, 0xA1D1937E,
  95         0x38D8C2C4, 0x4FDFF252, 0xD1BB67F1, 0xA6BC5767, 0x3FB506DD, 0x48B2364B,
  96         0xD80D2BDA, 0xAF0A1B4C, 0x36034AF6, 0x41047A60, 0xDF60EFC3, 0xA867DF55,
  97         0x316E8EEF, 0x4669BE79, 0xCB61B38C, 0xBC66831A, 0x256FD2A0, 0x5268E236,
  98         0xCC0C7795, 0xBB0B4703, 0x220216B9, 0x5505262F, 0xC5BA3BBE, 0xB2BD0B28,
  99         0x2BB45A92, 0x5CB36A04, 0xC2D7FFA7, 0xB5D0CF31, 0x2CD99E8B, 0x5BDEAE1D,
 100         0x9B64C2B0, 0xEC63F226, 0x756AA39C, 0x026D930A, 0x9C0906A9, 0xEB0E363F,
 101         0x72076785, 0x05005713, 0x95BF4A82, 0xE2B87A14, 0x7BB12BAE, 0x0CB61B38,
 102         0x92D28E9B, 0xE5D5BE0D, 0x7CDCEFB7, 0x0BDBDF21, 0x86D3D2D4, 0xF1D4E242,
 103         0x68DDB3F8, 0x1FDA836E, 0x81BE16CD, 0xF6B9265B, 0x6FB077E1, 0x18B74777,
 104         0x88085AE6, 0xFF0F6A70, 0x66063BCA, 0x11010B5C, 0x8F659EFF, 0xF862AE69,
 105         0x616BFFD3, 0x166CCF45, 0xA00AE278, 0xD70DD2EE, 0x4E048354, 0x3903B3C2,
 106         0xA7672661, 0xD06016F7, 0x4969474D, 0x3E6E77DB, 0xAED16A4A, 0xD9D65ADC,
 107         0x40DF0B66, 0x37D83BF0, 0xA9BCAE53, 0xDEBB9EC5, 0x47B2CF7F, 0x30B5FFE9,
 108         0xBDBDF21C, 0xCABAC28A, 0x53B39330, 0x24B4A3A6, 0xBAD03605, 0xCDD70693,
 109         0x54DE5729, 0x23D967BF, 0xB3667A2E, 0xC4614AB8, 0x5D681B02, 0x2A6F2B94,
 110         0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D
 111     };
 112
 113     uint32_t              crc32;
 114     unsigned char *       byte_buf;
 115     size_t                i;
 116
 117     /* accumulate crc32 for buffer */
 118     crc32 = in_crc32 ^ 0xFFFFFFFF;
 119     byte_buf = (unsigned char*) buf;
 120
 121     for (i = 0; i < buf_len; i++)
 122         crc32 = (crc32 >> 8) ^ crc_table[(crc32 ^ byte_buf[i]) & 0xFF];
 123
 124     return (crc32 ^ 0xFFFFFFFF);
 125 }
 126
 127 /* perform endian conversion of pixel data
 128  */
 129 void
 130 image_endian_swap (pixman_image_t *img, int bpp)
 131 {
 132     int stride = pixman_image_get_stride (img);
 133     uint32_t *data = pixman_image_get_data (img);
 134     int height = pixman_image_get_height (img);
 135     int i, j;
 136
 137     /* swap bytes only on big endian systems */
 138     volatile uint16_t endian_check_var = 0x1234;
 139     if (*(volatile uint8_t *)&endian_check_var != 0x12)
 140         return;
 141
 142     for (i = 0; i < height; i++)
 143     {
 144         uint8_t *line_data = (uint8_t *)data + stride * i;
 145         /* swap bytes only for 16, 24 and 32 bpp for now */
 146         switch (bpp)
 147         {
 148         case 1:
 149             for (j = 0; j < stride; j++)
 150             {
 151                 line_data[j] =
 152                     ((line_data[j] & 0x80) >> 7) |
 153                     ((line_data[j] & 0x40) >> 5) |
 154                     ((line_data[j] & 0x20) >> 3) |
 155                     ((line_data[j] & 0x10) >> 1) |
 156                     ((line_data[j] & 0x08) << 1) |
 157                     ((line_data[j] & 0x04) << 3) |
 158                     ((line_data[j] & 0x02) << 5) |
 159                     ((line_data[j] & 0x01) << 7);
 160             }
 161             break;
 162         case 4:
 163             for (j = 0; j < stride; j++)
 164             {
 165                 line_data[j] = (line_data[j] >> 4) | (line_data[j] << 4);
 166             }
 167             break;
 168         case 16:
 169             for (j = 0; j + 2 <= stride; j += 2)
 170             {
 171                 char t1 = line_data[j + 0];
 172                 char t2 = line_data[j + 1];
 173
 174                 line_data[j + 1] = t1;
 175                 line_data[j + 0] = t2;
 176             }
 177             break;
 178         case 24:
 179             for (j = 0; j + 3 <= stride; j += 3)
 180             {
 181                 char t1 = line_data[j + 0];
 182                 char t2 = line_data[j + 1];
 183                 char t3 = line_data[j + 2];
 184
 185                 line_data[j + 2] = t1;
 186                 line_data[j + 1] = t2;
 187                 line_data[j + 0] = t3;
 188             }
 189             break;
 190         case 32:
 191             for (j = 0; j + 4 <= stride; j += 4)
 192             {
 193                 char t1 = line_data[j + 0];
 194                 char t2 = line_data[j + 1];
 195                 char t3 = line_data[j + 2];
 196                 char t4 = line_data[j + 3];
 197
 198                 line_data[j + 3] = t1;
 199                 line_data[j + 2] = t2;
 200                 line_data[j + 1] = t3;
 201                 line_data[j + 0] = t4;
 202             }
 203             break;
 204         default:
 205             break;
 206         }
 207     }
 208 }
 209
 210 #define N_LEADING_PROTECTED     10
 211 #define N_TRAILING_PROTECTED    10
 212
 213 typedef struct
 214 {
 215     void *addr;
 216     uint32_t len;
 217     uint8_t *trailing;
 218     int n_bytes;
 219 } info_t;
 220
 221 #if defined(HAVE_MPROTECT) && defined(HAVE_GETPAGESIZE) && defined(HAVE_SYS_MMAN_H)
 222
 223 /* This is apparently necessary on at least OS X */
 224 #ifndef MAP_ANONYMOUS
 225 #define MAP_ANONYMOUS MAP_ANON
 226 #endif
 227
 228 void *
 229 fence_malloc (uint32_t len)
 230 {
 231     unsigned long page_size = getpagesize();
 232     unsigned long page_mask = page_size - 1;
 233     uint32_t n_payload_bytes = (len + page_mask) & ~page_mask;
 234     uint32_t n_bytes =
 235         (page_size * (N_LEADING_PROTECTED + N_TRAILING_PROTECTED + 2) +
 236          n_payload_bytes) & ~page_mask;
 237     uint8_t *initial_page;
 238     uint8_t *leading_protected;
 239     uint8_t *trailing_protected;
 240     uint8_t *payload;
 241     uint8_t *addr;
 242
 243     addr = mmap (NULL, n_bytes, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS,
 244                  -1, 0);
 245
 246     if (addr == MAP_FAILED)
 247     {
 248         printf ("mmap failed on %u %u\n", len, n_bytes);
 249         return NULL;
 250     }
 251
 252     initial_page = (uint8_t *)(((unsigned long)addr + page_mask) & ~page_mask);
 253     leading_protected = initial_page + page_size;
 254     payload = leading_protected + N_LEADING_PROTECTED * page_size;
 255     trailing_protected = payload + n_payload_bytes;
 256
 257     ((info_t *)initial_page)->addr = addr;
 258     ((info_t *)initial_page)->len = len;
 259     ((info_t *)initial_page)->trailing = trailing_protected;
 260     ((info_t *)initial_page)->n_bytes = n_bytes;
 261
 262     if ((mprotect (leading_protected, N_LEADING_PROTECTED * page_size,
 263                   PROT_NONE) == -1) ||
 264         (mprotect (trailing_protected, N_TRAILING_PROTECTED * page_size,
 265                   PROT_NONE) == -1))
 266     {
 267         munmap (addr, n_bytes);
 268         return NULL;
 269     }
 270
 271     return payload;
 272 }
 273
 274 void
 275 fence_free (void *data)
 276 {
 277     uint32_t page_size = getpagesize();
 278     uint8_t *payload = data;
 279     uint8_t *leading_protected = payload - N_LEADING_PROTECTED * page_size;
 280     uint8_t *initial_page = leading_protected - page_size;
 281     info_t *info = (info_t *)initial_page;
 282
 283     munmap (info->addr, info->n_bytes);
 284 }
 285
 286 #else
 287
 288 void *
 289 fence_malloc (uint32_t len)
 290 {
 291     return malloc (len);
 292 }
 293
 294 void
 295 fence_free (void *data)
 296 {
 297     free (data);
 298 }
 299
 300 #endif
 301
 302 uint8_t *
 303 make_random_bytes (int n_bytes)
 304 {
 305     uint8_t *bytes = fence_malloc (n_bytes);
 306     int i;
 307
 308     if (!bytes)
 309         return NULL;
 310
 311     for (i = 0; i < n_bytes; ++i)
 312         bytes[i] = lcg_rand () & 0xff;
 313
 314     return bytes;
 315 }
 316
 317 /*
 318  * A function, which can be used as a core part of the test programs,
 319  * intended to detect various problems with the help of fuzzing input
 320  * to pixman API (according to some templates, aka "smart" fuzzing).
 321  * Some general information about such testing can be found here:
 322  * http://en.wikipedia.org/wiki/Fuzz_testing
 323  *
 324  * It may help detecting:
 325  *  - crashes on bad handling of valid or reasonably invalid input to
 326  *    pixman API.
 327  *  - deviations from the behavior of older pixman releases.
 328  *  - deviations from the behavior of the same pixman release, but
 329  *    configured in a different way (for example with SIMD optimizations
 330  *    disabled), or running on a different OS or hardware.
 331  *
 332  * The test is performed by calling a callback function a huge number
 333  * of times. The callback function is expected to run some snippet of
 334  * pixman code with pseudorandom variations to the data feeded to
 335  * pixman API. A result of running each callback function should be
 336  * some deterministic value which depends on test number (test number
 337  * can be used as a seed for PRNG). When 'verbose' argument is nonzero,
 338  * callback function is expected to print to stdout some information
 339  * about what it does.
 340  *
 341  * Return values from many small tests are accumulated together and
 342  * used as final checksum, which can be compared to some expected
 343  * value. Running the tests not individually, but in a batch helps
 344  * to reduce process start overhead and also allows to parallelize
 345  * testing and utilize multiple CPU cores.
 346  *
 347  * The resulting executable can be run without any arguments. In
 348  * this case it runs a batch of tests starting from 1 and up to
 349  * 'default_number_of_iterations'. The resulting checksum is
 350  * compared with 'expected_checksum' and FAIL or PASS verdict
 351  * depends on the result of this comparison.
 352  *
 353  * If the executable is run with 2 numbers provided as command line
 354  * arguments, they specify the starting and ending numbers for a test
 355  * batch.
 356  *
 357  * If the executable is run with only one number provided as a command
 358  * line argument, then this number is used to call the callback function
 359  * once, and also with verbose flag set.
 360  */
 361 int
 362 fuzzer_test_main (const char *test_name,
 363                   int         default_number_of_iterations,
 364                   uint32_t    expected_checksum,
 365                   uint32_t    (*test_function)(int testnum, int verbose),
 366                   int         argc,
 367                   const char *argv[])
 368 {
 369     int i, n1 = 1, n2 = 0;
 370     uint32_t checksum = 0;
 371     int verbose = getenv ("VERBOSE") != NULL;
 372
 373     if (argc >= 3)
 374     {
 375         n1 = atoi (argv[1]);
 376         n2 = atoi (argv[2]);
 377         if (n2 < n1)
 378         {
 379             printf ("invalid test range\n");
 380             return 1;
 381         }
 382     }
 383     else if (argc >= 2)
 384     {
 385         n2 = atoi (argv[1]);
 386         checksum = test_function (n2, 1);
 387         printf ("%d: checksum=%08X\n", n2, checksum);
 388         return 0;
 389     }
 390     else
 391     {
 392         n1 = 1;
 393         n2 = default_number_of_iterations;
 394     }
 395
 396 #ifdef USE_OPENMP
 397     #pragma omp parallel for reduction(+:checksum) default(none) \
 398                                         shared(n1, n2, test_function, verbose)
 399 #endif
 400     for (i = n1; i <= n2; i++)
 401     {
 402         uint32_t crc = test_function (i, 0);
 403         if (verbose)
 404             printf ("%d: %08X\n", i, crc);
 405         checksum += crc;
 406     }
 407
 408     if (n1 == 1 && n2 == default_number_of_iterations)
 409     {
 410         if (checksum == expected_checksum)
 411         {
 412             printf ("%s test passed (checksum=%08X)\n",
 413                     test_name, checksum);
 414         }
 415         else
 416         {
 417             printf ("%s test failed! (checksum=%08X, expected %08X)\n",
 418                     test_name, checksum, expected_checksum);
 419             return 1;
 420         }
 421     }
 422     else
 423     {
 424         printf ("%d-%d: checksum=%08X\n", n1, n2, checksum);
 425     }
 426
 427     return 0;
 428 }
 429
 430 /* Try to obtain current time in seconds */
 431 double
 432 gettime (void)
 433 {
 434 #ifdef HAVE_GETTIMEOFDAY
 435     struct timeval tv;
 436
 437     gettimeofday (&tv, NULL);
 438     return (double)((int64_t)tv.tv_sec * 1000000 + tv.tv_usec) / 1000000.;
 439 #else
 440     return (double)clock() / (double)CLOCKS_PER_SEC;
 441 #endif
 442 }
 443
 444 static const char *global_msg;
 445
 446 static void
 447 on_alarm (int signo)
 448 {
 449     printf ("%s\n", global_msg);
 450     exit (1);
 451 }
 452
 453 void
 454 fail_after (int seconds, const char *msg)
 455 {
 456 #ifdef HAVE_SIGACTION
 457 #ifdef HAVE_ALARM
 458     struct sigaction action;
 459
 460     global_msg = msg;
 461
 462     memset (&action, 0, sizeof (action));
 463     action.sa_handler = on_alarm;
 464
 465     alarm (seconds);
 466
 467     sigaction (SIGALRM, &action, NULL);
 468 #endif
 469 #endif
 470 }
 471
 472 void *
 473 aligned_malloc (size_t align, size_t size)
 474 {
 475     void *result;
 476
 477 #ifdef HAVE_POSIX_MEMALIGN
 478     if (posix_memalign (&result, align, size) != 0)
 479       result = NULL;
 480 #else
 481     result = malloc (size);
 482 #endif
 483
 484     return result;
 485 }