test/utils.c

   1 #define _GNU_SOURCE
   2
   3 #include "utils.h"
   4 #include <signal.h>
   5 #include <stdlib.h>
   6
   7 #ifdef HAVE_GETTIMEOFDAY
   8 #include <sys/time.h>
   9 #else
  10 #include <time.h>
  11 #endif
  12
  13 #ifdef HAVE_UNISTD_H
  14 #include <unistd.h>
  15 #endif
  16
  17 #ifdef HAVE_SYS_MMAN_H
  18 #include <sys/mman.h>
  19 #endif
  20
  21 #ifdef HAVE_FENV_H
  22 #include <fenv.h>
  23 #endif
  24
  25 #ifdef HAVE_LIBPNG
  26 #include <png.h>
  27 #endif
  28
  29 /* Random number seed
  30  */
  31
  32 uint32_t lcg_seed;
  33
  34 /*----------------------------------------------------------------------------*\
  35  *  CRC-32 version 2.0.0 by Craig Bruce, 2006-04-29.
  36  *
  37  *  This program generates the CRC-32 values for the files named in the
  38  *  command-line arguments.  These are the same CRC-32 values used by GZIP,
  39  *  PKZIP, and ZMODEM.  The Crc32_ComputeBuf () can also be detached and
  40  *  used independently.
  41  *
  42  *  THIS PROGRAM IS PUBLIC-DOMAIN SOFTWARE.
  43  *
  44  *  Based on the byte-oriented implementation "File Verification Using CRC"
  45  *  by Mark R. Nelson in Dr. Dobb's Journal, May 1992, pp. 64-67.
  46  *
  47  *  v1.0.0: original release.
  48  *  v1.0.1: fixed printf formats.
  49  *  v1.0.2: fixed something else.
  50  *  v1.0.3: replaced CRC constant table by generator function.
  51  *  v1.0.4: reformatted code, made ANSI C.  1994-12-05.
  52  *  v2.0.0: rewrote to use memory buffer & static table, 2006-04-29.
  53 \*----------------------------------------------------------------------------*/
  54
  55 /*----------------------------------------------------------------------------*\
  56  *  NAME:
  57  *     Crc32_ComputeBuf () - computes the CRC-32 value of a memory buffer
  58  *  DESCRIPTION:
  59  *     Computes or accumulates the CRC-32 value for a memory buffer.
  60  *     The 'inCrc32' gives a previously accumulated CRC-32 value to allow
  61  *     a CRC to be generated for multiple sequential buffer-fuls of data.
  62  *     The 'inCrc32' for the first buffer must be zero.
  63  *  ARGUMENTS:
  64  *     inCrc32 - accumulated CRC-32 value, must be 0 on first call
  65  *     buf     - buffer to compute CRC-32 value for
  66  *     bufLen  - number of bytes in buffer
  67  *  RETURNS:
  68  *     crc32 - computed CRC-32 value
  69  *  ERRORS:
  70  *     (no errors are possible)
  71 \*----------------------------------------------------------------------------*/
  72
  73 uint32_t
  74 compute_crc32 (uint32_t    in_crc32,
  75                const void *buf,
  76                size_t      buf_len)
  77 {
  78     static const uint32_t crc_table[256] = {
  79         0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA, 0x076DC419, 0x706AF48F,
  80         0xE963A535, 0x9E6495A3, 0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988,
  81         0x09B64C2B, 0x7EB17CBD, 0xE7B82D07, 0x90BF1D91, 0x1DB71064, 0x6AB020F2,
  82         0xF3B97148, 0x84BE41DE, 0x1ADAD47D, 0x6DDDE4EB, 0xF4D4B551, 0x83D385C7,
  83         0x136C9856, 0x646BA8C0, 0xFD62F97A, 0x8A65C9EC, 0x14015C4F, 0x63066CD9,
  84         0xFA0F3D63, 0x8D080DF5, 0x3B6E20C8, 0x4C69105E, 0xD56041E4, 0xA2677172,
  85         0x3C03E4D1, 0x4B04D447, 0xD20D85FD, 0xA50AB56B, 0x35B5A8FA, 0x42B2986C,
  86         0xDBBBC9D6, 0xACBCF940, 0x32D86CE3, 0x45DF5C75, 0xDCD60DCF, 0xABD13D59,
  87         0x26D930AC, 0x51DE003A, 0xC8D75180, 0xBFD06116, 0x21B4F4B5, 0x56B3C423,
  88         0xCFBA9599, 0xB8BDA50F, 0x2802B89E, 0x5F058808, 0xC60CD9B2, 0xB10BE924,
  89         0x2F6F7C87, 0x58684C11, 0xC1611DAB, 0xB6662D3D, 0x76DC4190, 0x01DB7106,
  90         0x98D220BC, 0xEFD5102A, 0x71B18589, 0x06B6B51F, 0x9FBFE4A5, 0xE8B8D433,
  91         0x7807C9A2, 0x0F00F934, 0x9609A88E, 0xE10E9818, 0x7F6A0DBB, 0x086D3D2D,
  92         0x91646C97, 0xE6635C01, 0x6B6B51F4, 0x1C6C6162, 0x856530D8, 0xF262004E,
  93         0x6C0695ED, 0x1B01A57B, 0x8208F4C1, 0xF50FC457, 0x65B0D9C6, 0x12B7E950,
  94         0x8BBEB8EA, 0xFCB9887C, 0x62DD1DDF, 0x15DA2D49, 0x8CD37CF3, 0xFBD44C65,
  95         0x4DB26158, 0x3AB551CE, 0xA3BC0074, 0xD4BB30E2, 0x4ADFA541, 0x3DD895D7,
  96         0xA4D1C46D, 0xD3D6F4FB, 0x4369E96A, 0x346ED9FC, 0xAD678846, 0xDA60B8D0,
  97         0x44042D73, 0x33031DE5, 0xAA0A4C5F, 0xDD0D7CC9, 0x5005713C, 0x270241AA,
  98         0xBE0B1010, 0xC90C2086, 0x5768B525, 0x206F85B3, 0xB966D409, 0xCE61E49F,
  99         0x5EDEF90E, 0x29D9C998, 0xB0D09822, 0xC7D7A8B4, 0x59B33D17, 0x2EB40D81,
 100         0xB7BD5C3B, 0xC0BA6CAD, 0xEDB88320, 0x9ABFB3B6, 0x03B6E20C, 0x74B1D29A,
 101         0xEAD54739, 0x9DD277AF, 0x04DB2615, 0x73DC1683, 0xE3630B12, 0x94643B84,
 102         0x0D6D6A3E, 0x7A6A5AA8, 0xE40ECF0B, 0x9309FF9D, 0x0A00AE27, 0x7D079EB1,
 103         0xF00F9344, 0x8708A3D2, 0x1E01F268, 0x6906C2FE, 0xF762575D, 0x806567CB,
 104         0x196C3671, 0x6E6B06E7, 0xFED41B76, 0x89D32BE0, 0x10DA7A5A, 0x67DD4ACC,
 105         0xF9B9DF6F, 0x8EBEEFF9, 0x17B7BE43, 0x60B08ED5, 0xD6D6A3E8, 0xA1D1937E,
 106         0x38D8C2C4, 0x4FDFF252, 0xD1BB67F1, 0xA6BC5767, 0x3FB506DD, 0x48B2364B,
 107         0xD80D2BDA, 0xAF0A1B4C, 0x36034AF6, 0x41047A60, 0xDF60EFC3, 0xA867DF55,
 108         0x316E8EEF, 0x4669BE79, 0xCB61B38C, 0xBC66831A, 0x256FD2A0, 0x5268E236,
 109         0xCC0C7795, 0xBB0B4703, 0x220216B9, 0x5505262F, 0xC5BA3BBE, 0xB2BD0B28,
 110         0x2BB45A92, 0x5CB36A04, 0xC2D7FFA7, 0xB5D0CF31, 0x2CD99E8B, 0x5BDEAE1D,
 111         0x9B64C2B0, 0xEC63F226, 0x756AA39C, 0x026D930A, 0x9C0906A9, 0xEB0E363F,
 112         0x72076785, 0x05005713, 0x95BF4A82, 0xE2B87A14, 0x7BB12BAE, 0x0CB61B38,
 113         0x92D28E9B, 0xE5D5BE0D, 0x7CDCEFB7, 0x0BDBDF21, 0x86D3D2D4, 0xF1D4E242,
 114         0x68DDB3F8, 0x1FDA836E, 0x81BE16CD, 0xF6B9265B, 0x6FB077E1, 0x18B74777,
 115         0x88085AE6, 0xFF0F6A70, 0x66063BCA, 0x11010B5C, 0x8F659EFF, 0xF862AE69,
 116         0x616BFFD3, 0x166CCF45, 0xA00AE278, 0xD70DD2EE, 0x4E048354, 0x3903B3C2,
 117         0xA7672661, 0xD06016F7, 0x4969474D, 0x3E6E77DB, 0xAED16A4A, 0xD9D65ADC,
 118         0x40DF0B66, 0x37D83BF0, 0xA9BCAE53, 0xDEBB9EC5, 0x47B2CF7F, 0x30B5FFE9,
 119         0xBDBDF21C, 0xCABAC28A, 0x53B39330, 0x24B4A3A6, 0xBAD03605, 0xCDD70693,
 120         0x54DE5729, 0x23D967BF, 0xB3667A2E, 0xC4614AB8, 0x5D681B02, 0x2A6F2B94,
 121         0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D
 122     };
 123
 124     uint32_t              crc32;
 125     unsigned char *       byte_buf;
 126     size_t                i;
 127
 128     /* accumulate crc32 for buffer */
 129     crc32 = in_crc32 ^ 0xFFFFFFFF;
 130     byte_buf = (unsigned char*) buf;
 131
 132     for (i = 0; i < buf_len; i++)
 133         crc32 = (crc32 >> 8) ^ crc_table[(crc32 ^ byte_buf[i]) & 0xFF];
 134
 135     return (crc32 ^ 0xFFFFFFFF);
 136 }
 137
 138 pixman_bool_t
 139 is_little_endian (void)
 140 {
 141     volatile uint16_t endian_check_var = 0x1234;
 142
 143     return (*(volatile uint8_t *)&endian_check_var == 0x34);
 144 }
 145
 146 /* perform endian conversion of pixel data
 147  */
 148 void
 149 image_endian_swap (pixman_image_t *img)
 150 {
 151     int stride = pixman_image_get_stride (img);
 152     uint32_t *data = pixman_image_get_data (img);
 153     int height = pixman_image_get_height (img);
 154     int bpp = PIXMAN_FORMAT_BPP (pixman_image_get_format (img));
 155     int i, j;
 156
 157     /* swap bytes only on big endian systems */
 158     if (is_little_endian())
 159         return;
 160
 161     if (bpp == 8)
 162         return;
 163
 164     for (i = 0; i < height; i++)
 165     {
 166         uint8_t *line_data = (uint8_t *)data + stride * i;
 167
 168         switch (bpp)
 169         {
 170         case 1:
 171             for (j = 0; j < stride; j++)
 172             {
 173                 line_data[j] =
 174                     ((line_data[j] & 0x80) >> 7) |
 175                     ((line_data[j] & 0x40) >> 5) |
 176                     ((line_data[j] & 0x20) >> 3) |
 177                     ((line_data[j] & 0x10) >> 1) |
 178                     ((line_data[j] & 0x08) << 1) |
 179                     ((line_data[j] & 0x04) << 3) |
 180                     ((line_data[j] & 0x02) << 5) |
 181                     ((line_data[j] & 0x01) << 7);
 182             }
 183             break;
 184         case 4:
 185             for (j = 0; j < stride; j++)
 186             {
 187                 line_data[j] = (line_data[j] >> 4) | (line_data[j] << 4);
 188             }
 189             break;
 190         case 16:
 191             for (j = 0; j + 2 <= stride; j += 2)
 192             {
 193                 char t1 = line_data[j + 0];
 194                 char t2 = line_data[j + 1];
 195
 196                 line_data[j + 1] = t1;
 197                 line_data[j + 0] = t2;
 198             }
 199             break;
 200         case 24:
 201             for (j = 0; j + 3 <= stride; j += 3)
 202             {
 203                 char t1 = line_data[j + 0];
 204                 char t2 = line_data[j + 1];
 205                 char t3 = line_data[j + 2];
 206
 207                 line_data[j + 2] = t1;
 208                 line_data[j + 1] = t2;
 209                 line_data[j + 0] = t3;
 210             }
 211             break;
 212         case 32:
 213             for (j = 0; j + 4 <= stride; j += 4)
 214             {
 215                 char t1 = line_data[j + 0];
 216                 char t2 = line_data[j + 1];
 217                 char t3 = line_data[j + 2];
 218                 char t4 = line_data[j + 3];
 219
 220                 line_data[j + 3] = t1;
 221                 line_data[j + 2] = t2;
 222                 line_data[j + 1] = t3;
 223                 line_data[j + 0] = t4;
 224             }
 225             break;
 226         default:
 227             assert (FALSE);
 228             break;
 229         }
 230     }
 231 }
 232
 233 #define N_LEADING_PROTECTED     10
 234 #define N_TRAILING_PROTECTED    10
 235
 236 typedef struct
 237 {
 238     void *addr;
 239     uint32_t len;
 240     uint8_t *trailing;
 241     int n_bytes;
 242 } info_t;
 243
 244 #if defined(HAVE_MPROTECT) && defined(HAVE_GETPAGESIZE) && defined(HAVE_SYS_MMAN_H) && defined(HAVE_MMAP)
 245
 246 /* This is apparently necessary on at least OS X */
 247 #ifndef MAP_ANONYMOUS
 248 #define MAP_ANONYMOUS MAP_ANON
 249 #endif
 250
 251 void *
 252 fence_malloc (int64_t len)
 253 {
 254     unsigned long page_size = getpagesize();
 255     unsigned long page_mask = page_size - 1;
 256     uint32_t n_payload_bytes = (len + page_mask) & ~page_mask;
 257     uint32_t n_bytes =
 258         (page_size * (N_LEADING_PROTECTED + N_TRAILING_PROTECTED + 2) +
 259          n_payload_bytes) & ~page_mask;
 260     uint8_t *initial_page;
 261     uint8_t *leading_protected;
 262     uint8_t *trailing_protected;
 263     uint8_t *payload;
 264     uint8_t *addr;
 265
 266     if (len < 0)
 267         abort();
 268
 269     addr = mmap (NULL, n_bytes, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS,
 270                  -1, 0);
 271
 272     if (addr == MAP_FAILED)
 273     {
 274         printf ("mmap failed on %lld %u\n", (long long int)len, n_bytes);
 275         return NULL;
 276     }
 277
 278     initial_page = (uint8_t *)(((unsigned long)addr + page_mask) & ~page_mask);
 279     leading_protected = initial_page + page_size;
 280     payload = leading_protected + N_LEADING_PROTECTED * page_size;
 281     trailing_protected = payload + n_payload_bytes;
 282
 283     ((info_t *)initial_page)->addr = addr;
 284     ((info_t *)initial_page)->len = len;
 285     ((info_t *)initial_page)->trailing = trailing_protected;
 286     ((info_t *)initial_page)->n_bytes = n_bytes;
 287
 288     if ((mprotect (leading_protected, N_LEADING_PROTECTED * page_size,
 289                   PROT_NONE) == -1) ||
 290         (mprotect (trailing_protected, N_TRAILING_PROTECTED * page_size,
 291                   PROT_NONE) == -1))
 292     {
 293         munmap (addr, n_bytes);
 294         return NULL;
 295     }
 296
 297     return payload;
 298 }
 299
 300 void
 301 fence_free (void *data)
 302 {
 303     uint32_t page_size = getpagesize();
 304     uint8_t *payload = data;
 305     uint8_t *leading_protected = payload - N_LEADING_PROTECTED * page_size;
 306     uint8_t *initial_page = leading_protected - page_size;
 307     info_t *info = (info_t *)initial_page;
 308
 309     munmap (info->addr, info->n_bytes);
 310 }
 311
 312 #else
 313
 314 void *
 315 fence_malloc (int64_t len)
 316 {
 317     return malloc (len);
 318 }
 319
 320 void
 321 fence_free (void *data)
 322 {
 323     free (data);
 324 }
 325
 326 #endif
 327
 328 uint8_t *
 329 make_random_bytes (int n_bytes)
 330 {
 331     uint8_t *bytes = fence_malloc (n_bytes);
 332     int i;
 333
 334     if (!bytes)
 335         return NULL;
 336
 337     for (i = 0; i < n_bytes; ++i)
 338         bytes[i] = lcg_rand () & 0xff;
 339
 340     return bytes;
 341 }
 342
 343 void
 344 a8r8g8b8_to_rgba_np (uint32_t *dst, uint32_t *src, int n_pixels)
 345 {
 346     uint8_t *dst8 = (uint8_t *)dst;
 347     int i;
 348
 349     for (i = 0; i < n_pixels; ++i)
 350     {
 351         uint32_t p = src[i];
 352         uint8_t a, r, g, b;
 353
 354         a = (p & 0xff000000) >> 24;
 355         r = (p & 0x00ff0000) >> 16;
 356         g = (p & 0x0000ff00) >> 8;
 357         b = (p & 0x000000ff) >> 0;
 358
 359         if (a != 0)
 360         {
 361 #define DIVIDE(c, a)                                                    \
 362             do                                                          \
 363             {                                                           \
 364                 int t = ((c) * 255) / a;                                \
 365                 (c) = t < 0? 0 : t > 255? 255 : t;                      \
 366             } while (0)
 367
 368             DIVIDE (r, a);
 369             DIVIDE (g, a);
 370             DIVIDE (b, a);
 371         }
 372
 373         *dst8++ = r;
 374         *dst8++ = g;
 375         *dst8++ = b;
 376         *dst8++ = a;
 377     }
 378 }
 379
 380 #ifdef HAVE_LIBPNG
 381
 382 pixman_bool_t
 383 write_png (pixman_image_t *image, const char *filename)
 384 {
 385     int width = pixman_image_get_width (image);
 386     int height = pixman_image_get_height (image);
 387     int stride = width * 4;
 388     uint32_t *data = malloc (height * stride);
 389     pixman_image_t *copy;
 390     png_struct *write_struct;
 391     png_info *info_struct;
 392     pixman_bool_t result = FALSE;
 393     FILE *f = fopen (filename, "wb");
 394     png_bytep *row_pointers;
 395     int i;
 396
 397     if (!f)
 398         return FALSE;
 399
 400     row_pointers = malloc (height * sizeof (png_bytep));
 401
 402     copy = pixman_image_create_bits (
 403         PIXMAN_a8r8g8b8, width, height, data, stride);
 404
 405     pixman_image_composite32 (
 406         PIXMAN_OP_SRC, image, NULL, copy, 0, 0, 0, 0, 0, 0, width, height);
 407
 408     a8r8g8b8_to_rgba_np (data, data, height * width);
 409
 410     for (i = 0; i < height; ++i)
 411         row_pointers[i] = (png_bytep)(data + i * width);
 412
 413     if (!(write_struct = png_create_write_struct (
 414               PNG_LIBPNG_VER_STRING, NULL, NULL, NULL)))
 415         goto out1;
 416
 417     if (!(info_struct = png_create_info_struct (write_struct)))
 418         goto out2;
 419
 420     png_init_io (write_struct, f);
 421
 422     png_set_IHDR (write_struct, info_struct, width, height,
 423                   8, PNG_COLOR_TYPE_RGB_ALPHA,
 424                   PNG_INTERLACE_NONE, PNG_COMPRESSION_TYPE_BASE,
 425                   PNG_FILTER_TYPE_BASE);
 426
 427     png_write_info (write_struct, info_struct);
 428
 429     png_write_image (write_struct, row_pointers);
 430
 431     png_write_end (write_struct, NULL);
 432
 433     result = TRUE;
 434
 435 out2:
 436     png_destroy_write_struct (&write_struct, &info_struct);
 437
 438 out1:
 439     if (fclose (f) != 0)
 440         result = FALSE;
 441
 442     pixman_image_unref (copy);
 443     free (row_pointers);
 444     free (data);
 445     return result;
 446 }
 447
 448 #else /* no libpng */
 449
 450 pixman_bool_t
 451 write_png (pixman_image_t *image, const char *filename)
 452 {
 453     return FALSE;
 454 }
 455
 456 #endif
 457
 458 /*
 459  * A function, which can be used as a core part of the test programs,
 460  * intended to detect various problems with the help of fuzzing input
 461  * to pixman API (according to some templates, aka "smart" fuzzing).
 462  * Some general information about such testing can be found here:
 463  * http://en.wikipedia.org/wiki/Fuzz_testing
 464  *
 465  * It may help detecting:
 466  *  - crashes on bad handling of valid or reasonably invalid input to
 467  *    pixman API.
 468  *  - deviations from the behavior of older pixman releases.
 469  *  - deviations from the behavior of the same pixman release, but
 470  *    configured in a different way (for example with SIMD optimizations
 471  *    disabled), or running on a different OS or hardware.
 472  *
 473  * The test is performed by calling a callback function a huge number
 474  * of times. The callback function is expected to run some snippet of
 475  * pixman code with pseudorandom variations to the data feeded to
 476  * pixman API. A result of running each callback function should be
 477  * some deterministic value which depends on test number (test number
 478  * can be used as a seed for PRNG). When 'verbose' argument is nonzero,
 479  * callback function is expected to print to stdout some information
 480  * about what it does.
 481  *
 482  * Return values from many small tests are accumulated together and
 483  * used as final checksum, which can be compared to some expected
 484  * value. Running the tests not individually, but in a batch helps
 485  * to reduce process start overhead and also allows to parallelize
 486  * testing and utilize multiple CPU cores.
 487  *
 488  * The resulting executable can be run without any arguments. In
 489  * this case it runs a batch of tests starting from 1 and up to
 490  * 'default_number_of_iterations'. The resulting checksum is
 491  * compared with 'expected_checksum' and FAIL or PASS verdict
 492  * depends on the result of this comparison.
 493  *
 494  * If the executable is run with 2 numbers provided as command line
 495  * arguments, they specify the starting and ending numbers for a test
 496  * batch.
 497  *
 498  * If the executable is run with only one number provided as a command
 499  * line argument, then this number is used to call the callback function
 500  * once, and also with verbose flag set.
 501  */
 502 int
 503 fuzzer_test_main (const char *test_name,
 504                   int         default_number_of_iterations,
 505                   uint32_t    expected_checksum,
 506                   uint32_t    (*test_function)(int testnum, int verbose),
 507                   int         argc,
 508                   const char *argv[])
 509 {
 510     int i, n1 = 1, n2 = 0;
 511     uint32_t checksum = 0;
 512     int verbose = getenv ("VERBOSE") != NULL;
 513
 514     if (argc >= 3)
 515     {
 516         n1 = atoi (argv[1]);
 517         n2 = atoi (argv[2]);
 518         if (n2 < n1)
 519         {
 520             printf ("invalid test range\n");
 521             return 1;
 522         }
 523     }
 524     else if (argc >= 2)
 525     {
 526         n2 = atoi (argv[1]);
 527         checksum = test_function (n2, 1);
 528         printf ("%d: checksum=%08X\n", n2, checksum);
 529         return 0;
 530     }
 531     else
 532     {
 533         n1 = 1;
 534         n2 = default_number_of_iterations;
 535     }
 536
 537 #ifdef USE_OPENMP
 538     #pragma omp parallel for reduction(+:checksum) default(none) \
 539                                         shared(n1, n2, test_function, verbose)
 540 #endif
 541     for (i = n1; i <= n2; i++)
 542     {
 543         uint32_t crc = test_function (i, 0);
 544         if (verbose)
 545             printf ("%d: %08X\n", i, crc);
 546         checksum += crc;
 547     }
 548
 549     if (n1 == 1 && n2 == default_number_of_iterations)
 550     {
 551         if (checksum == expected_checksum)
 552         {
 553             printf ("%s test passed (checksum=%08X)\n",
 554                     test_name, checksum);
 555         }
 556         else
 557         {
 558             printf ("%s test failed! (checksum=%08X, expected %08X)\n",
 559                     test_name, checksum, expected_checksum);
 560             return 1;
 561         }
 562     }
 563     else
 564     {
 565         printf ("%d-%d: checksum=%08X\n", n1, n2, checksum);
 566     }
 567
 568     return 0;
 569 }
 570
 571 /* Try to obtain current time in seconds */
 572 double
 573 gettime (void)
 574 {
 575 #ifdef HAVE_GETTIMEOFDAY
 576     struct timeval tv;
 577
 578     gettimeofday (&tv, NULL);
 579     return (double)((int64_t)tv.tv_sec * 1000000 + tv.tv_usec) / 1000000.;
 580 #else
 581     return (double)clock() / (double)CLOCKS_PER_SEC;
 582 #endif
 583 }
 584
 585 uint32_t
 586 get_random_seed (void)
 587 {
 588     double d = gettime();
 589
 590     lcg_srand (*(uint32_t *)&d);
 591
 592     return lcg_rand_u32 ();
 593 }
 594
 595 static const char *global_msg;
 596
 597 static void
 598 on_alarm (int signo)
 599 {
 600     printf ("%s\n", global_msg);
 601     exit (1);
 602 }
 603
 604 void
 605 fail_after (int seconds, const char *msg)
 606 {
 607 #ifdef HAVE_SIGACTION
 608 #ifdef HAVE_ALARM
 609     struct sigaction action;
 610
 611     global_msg = msg;
 612
 613     memset (&action, 0, sizeof (action));
 614     action.sa_handler = on_alarm;
 615
 616     alarm (seconds);
 617
 618     sigaction (SIGALRM, &action, NULL);
 619 #endif
 620 #endif
 621 }
 622
 623 void
 624 enable_fp_exceptions (void)
 625 {
 626 #ifdef HAVE_FENV_H
 627 #ifdef HAVE_FEENABLEEXCEPT
 628     /* Note: we don't enable the FE_INEXACT trap because
 629      * that happens quite commonly. It is possible that
 630      * over- and underflow should similarly be considered
 631      * okay, but for now the test suite passes with them
 632      * enabled, and it's useful to know if they start
 633      * occuring.
 634      */
 635     feenableexcept (FE_DIVBYZERO        |
 636                     FE_INVALID          |
 637                     FE_OVERFLOW         |
 638                     FE_UNDERFLOW);
 639 #endif
 640 #endif
 641 }
 642
 643 void *
 644 aligned_malloc (size_t align, size_t size)
 645 {
 646     void *result;
 647
 648 #ifdef HAVE_POSIX_MEMALIGN
 649     if (posix_memalign (&result, align, size) != 0)
 650       result = NULL;
 651 #else
 652     result = malloc (size);
 653 #endif
 654
 655     return result;
 656 }
 657
 658 #define CONVERT_15(c, is_rgb)                                           \
 659     (is_rgb?                                                            \
 660      ((((c) >> 3) & 0x001f) |                                           \
 661       (((c) >> 6) & 0x03e0) |                                           \
 662       (((c) >> 9) & 0x7c00)) :                                          \
 663      (((((c) >> 16) & 0xff) * 153 +                                     \
 664        (((c) >>  8) & 0xff) * 301 +                                     \
 665        (((c)      ) & 0xff) * 58) >> 2))
 666
 667 void
 668 initialize_palette (pixman_indexed_t *palette, uint32_t depth, int is_rgb)
 669 {
 670     int i;
 671     uint32_t mask = (1 << depth) - 1;
 672
 673     for (i = 0; i < 32768; ++i)
 674         palette->ent[i] = lcg_rand() & mask;
 675
 676     memset (palette->rgba, 0, sizeof (palette->rgba));
 677
 678     for (i = 0; i < mask + 1; ++i)
 679     {
 680         uint32_t rgba24;
 681         pixman_bool_t retry;
 682         uint32_t i15;
 683
 684         /* We filled the rgb->index map with random numbers, but we
 685          * do need the ability to round trip, that is if some indexed
 686          * color expands to an argb24, then the 15 bit version of that
 687          * color must map back to the index. Anything else, we don't
 688          * care about too much.
 689          */
 690         do
 691         {
 692             uint32_t old_idx;
 693
 694             rgba24 = lcg_rand();
 695             i15 = CONVERT_15 (rgba24, is_rgb);
 696
 697             old_idx = palette->ent[i15];
 698             if (CONVERT_15 (palette->rgba[old_idx], is_rgb) == i15)
 699                 retry = 1;
 700             else
 701                 retry = 0;
 702         } while (retry);
 703
 704         palette->rgba[i] = rgba24;
 705         palette->ent[i15] = i;
 706     }
 707
 708     for (i = 0; i < mask + 1; ++i)
 709     {
 710         assert (palette->ent[CONVERT_15 (palette->rgba[i], is_rgb)] == i);
 711     }
 712 }
 713
 714 static double
 715 round_channel (double p, int m)
 716 {
 717     int t;
 718     double r;
 719
 720     t = p * ((1 << m));
 721     t -= t >> m;
 722
 723     r = t / (double)((1 << m) - 1);
 724
 725     return r;
 726 }
 727
 728 void
 729 round_color (pixman_format_code_t format, color_t *color)
 730 {
 731     if (PIXMAN_FORMAT_R (format) == 0)
 732     {
 733         color->r = 0.0;
 734         color->g = 0.0;
 735         color->b = 0.0;
 736     }
 737     else
 738     {
 739         color->r = round_channel (color->r, PIXMAN_FORMAT_R (format));
 740         color->g = round_channel (color->g, PIXMAN_FORMAT_G (format));
 741         color->b = round_channel (color->b, PIXMAN_FORMAT_B (format));
 742     }
 743
 744     if (PIXMAN_FORMAT_A (format) == 0)
 745         color->a = 1;
 746     else
 747         color->a = round_channel (color->a, PIXMAN_FORMAT_A (format));
 748 }
 749
 750 /* Check whether @pixel is a valid quantization of the a, r, g, b
 751  * parameters. Some slack is permitted.
 752  */
 753 void
 754 pixel_checker_init (pixel_checker_t *checker, pixman_format_code_t format)
 755 {
 756     assert (PIXMAN_FORMAT_VIS (format));
 757
 758     checker->format = format;
 759
 760     switch (PIXMAN_FORMAT_TYPE (format))
 761     {
 762     case PIXMAN_TYPE_A:
 763         checker->bs = 0;
 764         checker->gs = 0;
 765         checker->rs = 0;
 766         checker->as = 0;
 767         break;
 768
 769     case PIXMAN_TYPE_ARGB:
 770         checker->bs = 0;
 771         checker->gs = checker->bs + PIXMAN_FORMAT_B (format);
 772         checker->rs = checker->gs + PIXMAN_FORMAT_G (format);
 773         checker->as = checker->rs + PIXMAN_FORMAT_R (format);
 774         break;
 775
 776     case PIXMAN_TYPE_ABGR:
 777         checker->rs = 0;
 778         checker->gs = checker->rs + PIXMAN_FORMAT_R (format);
 779         checker->bs = checker->gs + PIXMAN_FORMAT_G (format);
 780         checker->as = checker->bs + PIXMAN_FORMAT_B (format);
 781         break;
 782
 783     case PIXMAN_TYPE_BGRA:
 784         /* With BGRA formats we start counting at the high end of the pixel */
 785         checker->bs = PIXMAN_FORMAT_BPP (format) - PIXMAN_FORMAT_B (format);
 786         checker->gs = checker->bs - PIXMAN_FORMAT_B (format);
 787         checker->rs = checker->gs - PIXMAN_FORMAT_G (format);
 788         checker->as = checker->rs - PIXMAN_FORMAT_R (format);
 789         break;
 790
 791     case PIXMAN_TYPE_RGBA:
 792         /* With BGRA formats we start counting at the high end of the pixel */
 793         checker->rs = PIXMAN_FORMAT_BPP (format) - PIXMAN_FORMAT_R (format);
 794         checker->gs = checker->rs - PIXMAN_FORMAT_R (format);
 795         checker->bs = checker->gs - PIXMAN_FORMAT_G (format);
 796         checker->as = checker->bs - PIXMAN_FORMAT_B (format);
 797         break;
 798
 799     default:
 800         assert (0);
 801         break;
 802     }
 803
 804     checker->am = ((1 << PIXMAN_FORMAT_A (format)) - 1) << checker->as;
 805     checker->rm = ((1 << PIXMAN_FORMAT_R (format)) - 1) << checker->rs;
 806     checker->gm = ((1 << PIXMAN_FORMAT_G (format)) - 1) << checker->gs;
 807     checker->bm = ((1 << PIXMAN_FORMAT_B (format)) - 1) << checker->bs;
 808
 809     checker->aw = PIXMAN_FORMAT_A (format);
 810     checker->rw = PIXMAN_FORMAT_R (format);
 811     checker->gw = PIXMAN_FORMAT_G (format);
 812     checker->bw = PIXMAN_FORMAT_B (format);
 813 }
 814
 815 void
 816 pixel_checker_split_pixel (const pixel_checker_t *checker, uint32_t pixel,
 817                            int *a, int *r, int *g, int *b)
 818 {
 819     *a = (pixel & checker->am) >> checker->as;
 820     *r = (pixel & checker->rm) >> checker->rs;
 821     *g = (pixel & checker->gm) >> checker->gs;
 822     *b = (pixel & checker->bm) >> checker->bs;
 823 }
 824
 825 static int32_t
 826 convert (double v, uint32_t width, uint32_t mask, uint32_t shift, double def)
 827 {
 828     int32_t r;
 829
 830     if (!mask)
 831         v = def;
 832
 833     r = (v * ((mask >> shift) + 1));
 834     r -= r >> width;
 835
 836     return r;
 837 }
 838
 839 static void
 840 get_limits (const pixel_checker_t *checker, double limit,
 841             color_t *color,
 842             int *ao, int *ro, int *go, int *bo)
 843 {
 844     *ao = convert (color->a + limit, checker->aw, checker->am, checker->as, 1.0);
 845     *ro = convert (color->r + limit, checker->rw, checker->rm, checker->rs, 0.0);
 846     *go = convert (color->g + limit, checker->gw, checker->gm, checker->gs, 0.0);
 847     *bo = convert (color->b + limit, checker->bw, checker->bm, checker->bs, 0.0);
 848 }
 849
 850 /* The acceptable deviation in units of [0.0, 1.0]
 851  */
 852 #define DEVIATION (0.004)
 853
 854 void
 855 pixel_checker_get_max (const pixel_checker_t *checker, color_t *color,
 856                        int *am, int *rm, int *gm, int *bm)
 857 {
 858     get_limits (checker, DEVIATION, color, am, rm, gm, bm);
 859 }
 860
 861 void
 862 pixel_checker_get_min (const pixel_checker_t *checker, color_t *color,
 863                        int *am, int *rm, int *gm, int *bm)
 864 {
 865     get_limits (checker, - DEVIATION, color, am, rm, gm, bm);
 866 }
 867
 868 pixman_bool_t
 869 pixel_checker_check (const pixel_checker_t *checker, uint32_t pixel,
 870                      color_t *color)
 871 {
 872     int32_t a_lo, a_hi, r_lo, r_hi, g_lo, g_hi, b_lo, b_hi;
 873     int32_t ai, ri, gi, bi;
 874     pixman_bool_t result;
 875
 876     pixel_checker_get_min (checker, color, &a_lo, &r_lo, &g_lo, &b_lo);
 877     pixel_checker_get_max (checker, color, &a_hi, &r_hi, &g_hi, &b_hi);
 878     pixel_checker_split_pixel (checker, pixel, &ai, &ri, &gi, &bi);
 879
 880     result =
 881         a_lo <= ai && ai <= a_hi        &&
 882         r_lo <= ri && ri <= r_hi        &&
 883         g_lo <= gi && gi <= g_hi        &&
 884         b_lo <= bi && bi <= b_hi;
 885
 886     return result;
 887 }