testsuite/arith_speed.c

   1
   2 #include <stdio.h>
   3 #include <stdlib.h>
   4 #include <string.h>
   5 #include <schroedinger/schro.h>
   6 #include <schroedinger/schroarith.h>
   7 #include <schroedinger/schrotables.h>
   8 #include <unistd.h>
   9 #include <fcntl.h>
  10
  11 #include <liboil/liboilprofile.h>
  12 #include <liboil/liboilrandom.h>
  13
  14 #define BUFFER_SIZE 1000000
  15
  16 int debug=1;
  17
  18 #define static
  19 static int orig_arith_decode_bit (SchroArith *arith, int i);
  20 static int ref_arith_decode_bit (SchroArith *arith, int i);
  21 static int test_arith_decode_bit (SchroArith *arith, int i);
  22
  23 int
  24 decode(SchroBuffer *buffer, int n, OilProfile *prof, int type)
  25 {
  26   SchroArith *a;
  27   int i;
  28   int j;
  29   int x = 0;
  30
  31   oil_profile_init (prof);
  32   for(j=0;j<10;j++){
  33     a = schro_arith_new();
  34
  35     schro_arith_decode_init (a, buffer);
  36
  37     switch (type) {
  38       case 0:
  39         oil_profile_start (prof);
  40         for(i=0;i<n;i++){
  41           x += orig_arith_decode_bit (a, 0);
  42         }
  43         oil_profile_stop (prof);
  44         break;
  45       case 1:
  46         oil_profile_start (prof);
  47         for(i=0;i<n;i++){
  48           x += ref_arith_decode_bit (a, 0);
  49         }
  50         oil_profile_stop (prof);
  51         break;
  52       case 2:
  53         oil_profile_start (prof);
  54         for(i=0;i<n;i++){
  55           x += test_arith_decode_bit (a, 0);
  56         }
  57         oil_profile_stop (prof);
  58         break;
  59     }
  60
  61     a->buffer = NULL;
  62     schro_arith_free(a);
  63   }
  64
  65   return x;
  66 }
  67
  68 void
  69 print_speed (void)
  70 {
  71   int fd;
  72   char buffer[100];
  73   int n;
  74   int freq0, freq1;
  75
  76   fd = open("/sys/devices/system/cpu/cpu0/cpufreq/scaling_cur_freq", O_RDONLY);
  77   n = read (fd, buffer, 100);
  78   close(fd);
  79   if (n >= 0) {
  80     buffer[n] = 0;
  81     freq0 = strtol (buffer, NULL, 0);
  82   } else {
  83     freq0 = -1;
  84   }
  85
  86   fd = open("/sys/devices/system/cpu/cpu1/cpufreq/scaling_cur_freq", O_RDONLY);
  87   n = read (fd, buffer, 100);
  88   close(fd);
  89   if (n >= 0) {
  90     buffer[n] = 0;
  91     freq1 = strtol (buffer, NULL, 0);
  92   } else {
  93     freq1 = -1;
  94   }
  95
  96   printf("cpu speed %d %d\n", freq0, freq1);
  97 }
  98
  99 void
 100 dump_bits (SchroBuffer *buffer, int n)
 101 {
 102   int i;
 103
 104   for(i=0;i<n;i++){
 105     printf("%02x ", buffer->data[i]);
 106     if ((i&15)==15) {
 107       printf ("\n");
 108     }
 109   }
 110   printf ("\n");
 111 }
 112
 113 void
 114 encode (SchroBuffer *buffer, int n, int freq)
 115 {
 116   SchroArith *a;
 117   int i;
 118   int bit;
 119
 120   a = schro_arith_new();
 121
 122   schro_arith_encode_init (a, buffer);
 123
 124   for(i=0;i<n;i++){
 125     bit = oil_rand_u8() < freq;
 126     schro_arith_encode_bit (a, 0, bit);
 127   }
 128   schro_arith_flush (a);
 129
 130   a->buffer = NULL;
 131   schro_arith_free(a);
 132 }
 133
 134 int
 135 check (int n, int freq)
 136 {
 137   SchroBuffer *buffer;
 138   OilProfile prof;
 139   double ave, std;
 140   int x;
 141   int y;
 142
 143   buffer = schro_buffer_new_and_alloc (100000);
 144
 145   encode(buffer, n, freq);
 146
 147   print_speed();
 148
 149   x = decode(buffer, n, &prof, 0);
 150   oil_profile_get_ave_std (&prof, &ave, &std);
 151   printf("orig %d,%d: %g (%g) %d\n", n, freq, ave, std, x);
 152
 153   x = decode(buffer, n, &prof, 1);
 154   oil_profile_get_ave_std (&prof, &ave, &std);
 155   printf("ref  %d,%d: %g (%g) %d\n", n, freq, ave, std, x);
 156
 157   y = decode(buffer, n, &prof, 2);
 158   oil_profile_get_ave_std (&prof, &ave, &std);
 159   printf("test %d,%d: %g (%g) %d\n", n, freq, ave, std, y);
 160   if (x != y) {
 161     printf("BROKEN\n");
 162   }
 163
 164   schro_buffer_unref (buffer);
 165
 166   return 0;
 167 }
 168
 169 int
 170 main (int argc, char *argv[])
 171 {
 172   //int i;
 173
 174   schro_init();
 175
 176   //while(1) check(1000, 128);
 177   check(100, 128);
 178 #if 0
 179   for(i=100;i<=1000;i+=100) {
 180     //check(i, 128);
 181     check(i, 256);
 182   }
 183   check(2000, 256);
 184   check(3000, 256);
 185   check(4000, 256);
 186   check(5000, 256);
 187   check(100000, 256);
 188 #endif
 189 #if 0
 190   for(i=0;i<=256;i+=16) {
 191     check(100, i);
 192   }
 193 #endif
 194
 195   return 0;
 196 }
 197
 198 static const uint16_t _lut[256] = {
 199   //LUT corresponds to window = 16 @ p0=0.5 & 256 @ p=1.0
 200      0,    2,    5,    8,   11,   15,   20,   24,
 201     29,   35,   41,   47,   53,   60,   67,   74,
 202     82,   89,   97,  106,  114,  123,  132,  141,
 203    150,  160,  170,  180,  190,  201,  211,  222,
 204    233,  244,  256,  267,  279,  291,  303,  315,
 205    327,  340,  353,  366,  379,  392,  405,  419,
 206    433,  447,  461,  475,  489,  504,  518,  533,
 207    548,  563,  578,  593,  609,  624,  640,  656,
 208    672,  688,  705,  721,  738,  754,  771,  788,
 209    805,  822,  840,  857,  875,  892,  910,  928,
 210    946,  964,  983, 1001, 1020, 1038, 1057, 1076,
 211   1095, 1114, 1133, 1153, 1172, 1192, 1211, 1231,
 212   1251, 1271, 1291, 1311, 1332, 1352, 1373, 1393,
 213   1414, 1435, 1456, 1477, 1498, 1520, 1541, 1562,
 214   1584, 1606, 1628, 1649, 1671, 1694, 1716, 1738,
 215   1760, 1783, 1806, 1828, 1851, 1874, 1897, 1920,
 216   1935, 1942, 1949, 1955, 1961, 1968, 1974, 1980,
 217   1985, 1991, 1996, 2001, 2006, 2011, 2016, 2021,
 218   2025, 2029, 2033, 2037, 2040, 2044, 2047, 2050,
 219   2053, 2056, 2058, 2061, 2063, 2065, 2066, 2068,
 220   2069, 2070, 2071, 2072, 2072, 2072, 2072, 2072,
 221   2072, 2071, 2070, 2069, 2068, 2066, 2065, 2063,
 222   2060, 2058, 2055, 2052, 2049, 2045, 2042, 2038,
 223   2033, 2029, 2024, 2019, 2013, 2008, 2002, 1996,
 224   1989, 1982, 1975, 1968, 1960, 1952, 1943, 1934,
 225   1925, 1916, 1906, 1896, 1885, 1874, 1863, 1851,
 226   1839, 1827, 1814, 1800, 1786, 1772, 1757, 1742,
 227   1727, 1710, 1694, 1676, 1659, 1640, 1622, 1602,
 228   1582, 1561, 1540, 1518, 1495, 1471, 1447, 1422,
 229   1396, 1369, 1341, 1312, 1282, 1251, 1219, 1186,
 230   1151, 1114, 1077, 1037,  995,  952,  906,  857,
 231    805,  750,  690,  625,  553,  471,  376,  255
 232 };
 233
 234 static int
 235 orig_arith_decode_bit (SchroArith *arith, int i)
 236 {
 237   unsigned int probability0;
 238   unsigned int range_x_prob;
 239   unsigned int count;
 240   int value;
 241
 242   probability0 = arith->probabilities[i];
 243   count = arith->code - arith->range[0];
 244   range_x_prob = ((arith->range[1]) * probability0) >> 16;
 245
 246   value = (count >= range_x_prob);
 247   if (value) {
 248     arith->range[0] += range_x_prob;
 249     arith->range[1] -= range_x_prob;
 250     arith->probabilities[i] -= _lut[arith->probabilities[i]>>8];
 251   } else {
 252     arith->range[1] = range_x_prob;
 253     arith->probabilities[i] += _lut[255-(arith->probabilities[i]>>8)];
 254   }
 255
 256   while (arith->range[1] <= 0x4000) {
 257     arith->range[0] <<= 1;
 258     arith->range[1] <<= 1;
 259
 260     arith->code <<= 1;
 261     arith->code |= (arith->dataptr[arith->offset] >> (7-arith->cntr))&1;
 262
 263     arith->cntr++;
 264
 265     if (arith->cntr == 8) {
 266       arith->offset++;
 267       arith->range[0] &= 0xffff;
 268       arith->code &= 0xffff;
 269
 270       if (arith->code < arith->range[0]) {
 271         arith->code |= (1<<16);
 272       }
 273       arith->cntr = 0;
 274     }
 275   }
 276
 277   return value;
 278 }
 279
 280
 281 static int
 282 ref_arith_decode_bit (SchroArith *arith, int i)
 283 {
 284   unsigned int range_x_prob;
 285   int value;
 286   int lut_index;
 287
 288   range_x_prob = ((arith->range[1] - arith->range[0]) * arith->probabilities[i]) >> 16;
 289   lut_index = arith->probabilities[i]>>8;
 290
 291   value = (arith->code - arith->range[0] >= range_x_prob);
 292   arith->probabilities[i] += arith->lut[(value<<8) | lut_index];
 293   arith->range[1-value] = arith->range[0] + range_x_prob;
 294
 295   while (arith->range[1] - arith->range[0] <= 0x4000) {
 296     arith->range[0] <<= 1;
 297     arith->range[1] <<= 1;
 298
 299     arith->code <<= 1;
 300     arith->code |= (arith->dataptr[arith->offset] >> (7-arith->cntr))&1;
 301
 302     arith->cntr++;
 303
 304     if (arith->cntr == 8) {
 305       int size = arith->range[1] - arith->range[0];
 306       arith->offset++;
 307       arith->range[0] &= 0xffff;
 308       arith->range[1] = arith->range[0] + size;
 309       arith->code &= 0xffff;
 310
 311       if (arith->code < arith->range[0]) {
 312         arith->code |= (1<<16);
 313       }
 314       arith->cntr = 0;
 315     }
 316   }
 317
 318   return value;
 319 }
 320
 321
 322 static int
 323 test_arith_decode_bit (SchroArith *arith, int i)
 324 {
 325   //unsigned int range_x_prob;
 326   int value;
 327   //int lut_index;
 328
 329 #if 0
 330   printf("[%d,%d] code %d prob %d\n",
 331       arith->range[0], arith->range[1], arith->code, arith->probabilities[i]);
 332 #endif
 333 #if 1
 334   __asm__ __volatile__ (
 335     ".set range0, 0\n"
 336     ".set range1, 4\n"
 337     ".set code, 8\n"
 338     ".set range_size, 12\n"
 339     ".set probabilities, 16\n"
 340     ".set lut, 0x98\n"
 341
 342     // range_x_prob
 343     "  mov range1(%[arith]), %%edx\n"
 344     "  sub range0(%[arith]), %%edx\n"
 345 #if 0
 346     "  movzwl probabilities(%[arith],%[i],2), %%eax\n"
 347     "  imul %%eax, %%edx\n"
 348     "  shr $0x10, %%edx\n"
 349 #else
 350     "  movw probabilities(%[arith],%[i],2), %%ax\n"
 351     "  cmp $0x10000, %%edx\n"
 352     "  je fullrange\n"
 353     "  mul %%dx\n"
 354     // result in %%dx
 355     "  movzwl %%dx, %%eax\n"
 356     "fullrange:\n"
 357     "  mov %%eax, %%edx\n"
 358 #endif
 359
 360     // lut_index
 361 #if 0
 362     "  movzbl probabilities+1(%[arith],%[i],2), %%eax\n"
 363 #else
 364     "  movzwl probabilities(%[arith],%[i],2), %%eax\n"
 365     "  movzbl %%ah, %%eax\n"
 366 #endif
 367
 368     // value
 369     "  mov code(%[arith]), %%ebx\n"
 370     "  sub range0(%[arith]), %%ebx\n"
 371 #if 0
 372     "  mov %%edx, %%ecx\n"
 373     "  subl %%ebx, %%ecx\n"
 374     "  subl $1, %%ecx\n"
 375     "  shr $31, %%ecx\n"
 376 #else
 377     "  cmp %%ebx, %%edx\n"
 378     "  setbe %%cl\n"
 379     "  movzbl %%cl, %%ecx\n"
 380 #endif
 381     "  mov %%ecx, %[value]\n"
 382
 383     // probabilities[i]
 384     "  shl $8, %%ecx\n"
 385     "  or %%ecx, %%eax\n"
 386     "  mov lut(%[arith], %%eax, 2), %%bx\n"
 387     "  addw %%bx, probabilities(%[arith],%[i],2)\n"
 388
 389     // range[1^value]
 390     "  mov %[value], %%eax\n"
 391     "  xor $1, %%eax\n"
 392     "  add range0(%[arith]), %%edx\n"
 393     "  mov %%edx, range0(%[arith],%%eax,4)\n"
 394     : [value] "=m" (value),
 395       [arith] "+r" (arith),
 396       [i] "+r" (i)
 397     :
 398     : "edx", "ebx", "eax", "ecx"
 399     );
 400 #endif
 401 #if 0
 402   printf("[%d,%d] code %d prob %d, value %d\n",
 403       arith->range[0], arith->range[1], arith->code, arith->probabilities[i],
 404       value);
 405 #endif
 406
 407 #if 0
 408   range_x_prob = ((arith->range[1] - arith->range[0]) * arith->probabilities[i]) >> 16;
 409   lut_index = arith->probabilities[i]>>8;
 410
 411   value = (arith->code - arith->range[0] >= range_x_prob);
 412   arith->probabilities[i] += arith->lut[(value<<8) | lut_index];
 413   arith->range[1^value] = arith->range[0] + range_x_prob;
 414 #endif
 415
 416   while (arith->range[1] - arith->range[0] <= 0x4000) {
 417     arith->range[0] <<= 1;
 418     arith->range[1] <<= 1;
 419
 420     arith->code <<= 1;
 421     arith->code |= (arith->dataptr[arith->offset] >> (7-arith->cntr))&1;
 422
 423     arith->cntr++;
 424
 425     if (arith->cntr == 8) {
 426       int size = arith->range[1] - arith->range[0];
 427       arith->offset++;
 428       arith->range[0] &= 0xffff;
 429       arith->range[1] = arith->range[0] + size;
 430       arith->code &= 0xffff;
 431
 432       if (arith->code < arith->range[0]) {
 433         arith->code |= (1<<16);
 434       }
 435       arith->cntr = 0;
 436     }
 437   }
 438
 439   return value;
 440 }
 441