w3d/wavelet_coeff.c

   1 #include "mem.h"
   2 #include "wavelet.h"
   3 #include "rle.h"
   4 #include "w3dtypes.h"
   5
   6
   7 #define GRAY_CODES 1
   8
   9 #if defined(GRAY_CODES)
  10 static inline
  11 uint16_t binary_to_gray (uint16_t x) { return  x ^ (x >> 1); }
  12
  13 static inline
  14 uint16_t gray_to_binary (uint16_t x)
  15 { int i; for (i=1; i<16; i+=i) x ^= x >> i; return x; }
  16 #endif
  17
  18
  19 static inline
  20 void encode_coeff (ENTROPY_CODER significand_bitstream [],
  21                    ENTROPY_CODER insignificand_bitstream [],
  22                    TYPE coeff)
  23 {
  24    int sign = (coeff >> (8*sizeof(TYPE)-1)) & 1;
  25 #if defined(GRAY_CODES)
  26    TYPE significance = binary_to_gray(coeff);
  27 #else
  28    static TYPE mask [2] = { 0, ~0 };
  29    TYPE significance = coeff ^ mask[sign];
  30 #endif
  31    int i = TYPE_BITS;
  32
  33    do {
  34       i--;
  35       OUTPUT_BIT(&significand_bitstream[i], (significance >> i) & 1);
  36    } while (!((significance >> i) & 1) && i > 0);
  37
  38    OUTPUT_BIT(&significand_bitstream[i], sign);
  39
  40    while (--i >= 0)
  41       OUTPUT_BIT(&insignificand_bitstream[i], (significance >> i) & 1);
  42 }
  43
  44
  45
  46 static inline
  47 TYPE decode_coeff (ENTROPY_CODER significand_bitstream [],
  48                    ENTROPY_CODER insignificand_bitstream [])
  49 {
  50 #if !defined(GRAY_CODES)
  51    static TYPE mask [2] = { 0, ~0 };
  52 #endif
  53    TYPE significance = 0;
  54    int sign;
  55    int i = TYPE_BITS;
  56
  57    do {
  58       i--;
  59       significance |= INPUT_BIT(&significand_bitstream[i]) << i;
  60 //    if (ENTROPY_CODER_EOS(&significand_bitstream[i]))
  61 //       return 0;
  62    } while (!significance && i > 0);
  63
  64    sign = INPUT_BIT(&significand_bitstream[i]);
  65 // if (ENTROPY_CODER_EOS(&significand_bitstream[i]))
  66 //    return 0;
  67
  68    while (--i >= 0)
  69       significance |= INPUT_BIT(&insignificand_bitstream[i]) << i;
  70
  71 #if defined(GRAY_CODES)
  72    significance |= sign << (8*sizeof(TYPE)-1);
  73    return gray_to_binary(significance);
  74 #else
  75    return (significance ^ mask[sign]);
  76 #endif
  77 }
  78
  79
  80 static inline
  81 uint32_t skip_0coeffs (Wavelet3DBuf* buf,
  82                        ENTROPY_CODER s_stream [],
  83                        ENTROPY_CODER i_stream [],
  84                        uint32_t limit)
  85 {
  86    int i;
  87    uint32_t skip = limit;
  88
  89    for (i=0; i<TYPE_BITS; i++) {
  90       if (ENTROPY_CODER_SYMBOL(&s_stream[i]) != 0) {
  91          return 0;
  92       } else {
  93          uint32_t runlength = ENTROPY_CODER_RUNLENGTH(&s_stream[i]);
  94          if (i==0)
  95             runlength /= 2;     /* sign bits are in this bitplane ... */
  96          if (skip > runlength)
  97             skip = runlength;
  98          if (skip <= 2)
  99             return 0;
 100       }
 101    }
 102
 103    ENTROPY_CODER_SKIP(&s_stream[0], 2*skip); /* kill sign+significance bits */
 104
 105    for (i=1; i<TYPE_BITS; i++)
 106       ENTROPY_CODER_SKIP(&s_stream[i], skip);
 107
 108    return skip;
 109 }
 110
 111
 112
 113 #if 1
 114 static inline
 115 void encode_quadrant (const Wavelet3DBuf* buf,
 116                       int level, int quadrant, uint32_t w, uint32_t h, uint32_t f,
 117                       ENTROPY_CODER significand_bitstream [],
 118                       ENTROPY_CODER insignificand_bitstream [])
 119 {
 120    uint32_t x, y, z;
 121
 122    for (z=0; z<f; z++) {
 123       for (y=0; y<h; y++) {
 124          for (x=0; x<w; x++) {
 125             unsigned int index = buf->offset [level] [quadrant]
 126                                    + z * buf->width * buf->height
 127                                    + y * buf->width + x;
 128
 129             encode_coeff (significand_bitstream, insignificand_bitstream,
 130                           buf->data [index]);
 131          }
 132       }
 133    }
 134 }
 135
 136
 137 static
 138 void encode_coefficients (const Wavelet3DBuf* buf,
 139                           ENTROPY_CODER s_stream [],
 140                           ENTROPY_CODER i_stream [])
 141 {
 142    int level;
 143
 144    encode_coeff (s_stream, i_stream, buf->data[0]);
 145
 146    for (level=0; level<buf->scales-1; level++) {
 147       uint32_t w, h, f, w1, h1, f1;
 148
 149       w = buf->w [level];
 150       h = buf->h [level];
 151       f = buf->f [level];
 152       w1 = buf->w [level+1] - w;
 153       h1 = buf->h [level+1] - h;
 154       f1 = buf->f [level+1] - f;
 155
 156       if (w1 > 0) encode_quadrant(buf,level,1,w1,h,f,s_stream,i_stream);
 157       if (h1 > 0) encode_quadrant(buf,level,2,w,h1,f,s_stream,i_stream);
 158       if (f1 > 0) encode_quadrant(buf,level,3,w,h,f1,s_stream,i_stream);
 159       if (w1 > 0 && h1 > 0) encode_quadrant(buf,level,4,w1,h1,f,s_stream,i_stream);
 160       if (w1 > 0 && f1 > 0) encode_quadrant(buf,level,5,w1,h,f1,s_stream,i_stream);
 161       if (h1 > 0 && f1 > 0) encode_quadrant(buf,level,6,w,h1,f1,s_stream,i_stream);
 162       if (h1 > 0 && f1 > 0 && f1 > 0)
 163          encode_quadrant (buf,level,7,w1,h1,f1,s_stream,i_stream);
 164    }
 165 }
 166
 167
 168 static inline
 169 void decode_quadrant (Wavelet3DBuf* buf,
 170                       int level, int quadrant, uint32_t w, uint32_t h, uint32_t f,
 171                       ENTROPY_CODER s_stream [],
 172                       ENTROPY_CODER i_stream [])
 173 {
 174    uint32_t x, y, z;
 175
 176    z = 0;
 177    do {
 178       y = 0;
 179       do {
 180          x = 0;
 181          do {
 182             uint32_t skip;
 183             uint32_t index = buf->offset [level] [quadrant]
 184                                + z * buf->width * buf->height
 185                                + y * buf->width + x;
 186
 187             buf->data [index] = decode_coeff (s_stream, i_stream);
 188
 189             skip = skip_0coeffs (buf, s_stream, i_stream,
 190                                  (w-x-1)+(h-y-1)*w+(f-z-1)*w*h);
 191             if (skip > 0) {
 192                x += skip;
 193                while (x >= w) {
 194                   y++; x -= w;
 195                   while (y >= h) {
 196                      z++; y -= h;
 197                      if (z >= f)
 198                         return;
 199                   }
 200                }
 201             }
 202             x++;
 203          } while (x < w);
 204          y++;
 205       } while (y < h);
 206       z++;
 207    } while (z < f);
 208 }
 209
 210
 211 static
 212 void decode_coefficients (Wavelet3DBuf* buf,
 213                           ENTROPY_CODER s_stream [],
 214                           ENTROPY_CODER i_stream [])
 215 {
 216    int level;
 217
 218    buf->data[0] = decode_coeff (s_stream, i_stream);
 219
 220    for (level=0; level<buf->scales-1; level++) {
 221       uint32_t w, h, f, w1, h1, f1;
 222
 223       w = buf->w [level];
 224       h = buf->h [level];
 225       f = buf->f [level];
 226       w1 = buf->w [level+1] - w;
 227       h1 = buf->h [level+1] - h;
 228       f1 = buf->f [level+1] - f;
 229
 230       if (w1 > 0) decode_quadrant(buf,level,1,w1,h,f,s_stream,i_stream);
 231       if (h1 > 0) decode_quadrant(buf,level,2,w,h1,f,s_stream,i_stream);
 232       if (f1 > 0) decode_quadrant(buf,level,3,w,h,f1,s_stream,i_stream);
 233       if (w1 > 0 && h1 > 0) decode_quadrant(buf,level,4,w1,h1,f,s_stream,i_stream);
 234       if (w1 > 0 && f1 > 0) decode_quadrant(buf,level,5,w1,h,f1,s_stream,i_stream);
 235       if (h1 > 0 && f1 > 0) decode_quadrant(buf,level,6,w,h1,f1,s_stream,i_stream);
 236       if (h1 > 0 && f1 > 0 && f1 > 0)
 237          decode_quadrant (buf,level,7,w1,h1,f1,s_stream,i_stream);
 238    }
 239 }
 240 #else
 241
 242 static
 243 void encode_coefficients (const Wavelet3DBuf* buf,
 244                           ENTROPY_CODER s_stream [],
 245                           ENTROPY_CODER i_stream [])
 246 {
 247    uint32_t i;
 248
 249    for (i=0; i<buf->width*buf->height*buf->frames; i++)
 250       encode_coeff(s_stream, i_stream, buf->data[i]);
 251 }
 252
 253
 254
 255
 256 static
 257 void decode_coefficients (Wavelet3DBuf* buf,
 258                           ENTROPY_CODER s_stream [],
 259                           ENTROPY_CODER i_stream [])
 260 {
 261    uint32_t i;
 262
 263    for (i=0; i<buf->width*buf->height*buf->frames; i++) {
 264       uint32_t skip;
 265
 266       buf->data[i] = decode_coeff(s_stream, i_stream);
 267
 268       skip = skip_0coeffs (buf, s_stream, i_stream,
 269                            buf->width*buf->height*buf->frames - i);
 270       i += skip;
 271    }
 272 }
 273 #endif
 274
 275
 276
 277 static
 278 uint32_t setup_limittabs (ENTROPY_CODER significand_bitstream [],
 279                           ENTROPY_CODER insignificand_bitstream [],
 280                           uint32_t significand_limittab [],
 281                           uint32_t insignificand_limittab [],
 282                           uint32_t limit)
 283 {
 284    uint32_t significand_limit;
 285    uint32_t insignificand_limit;
 286    uint32_t byte_count;
 287    int i;
 288
 289    assert (limit > 2 * TYPE_BITS * sizeof(uint32_t)); /* limit too small */
 290
 291    printf ("%s: limit == %u\n", __FUNCTION__, limit);
 292    byte_count = 2 * TYPE_BITS * sizeof(uint32_t); /* 2 binary coded limittabs */
 293    limit -= byte_count;
 294    printf ("%s: rem. limit == %u\n", __FUNCTION__, limit);
 295
 296    significand_limit = limit * 7 / 8;
 297    insignificand_limit = limit - significand_limit;
 298
 299    printf ("%s: limit == %u\n", __FUNCTION__, limit);
 300    printf ("significand limit == %u\n", significand_limit);
 301    printf ("insignificand limit == %u\n", insignificand_limit);
 302
 303    for (i=TYPE_BITS-1; i>=0; i--) {
 304       uint32_t s_bytes, i_bytes;
 305
 306       if (i > 0) {
 307          significand_limittab[i] = (significand_limit + 1) / 2;
 308          insignificand_limittab[i] = (insignificand_limit + 1) / 2;
 309       } else {
 310          significand_limittab[0] = significand_limit;
 311          insignificand_limittab[0] = insignificand_limit;
 312       }
 313
 314       s_bytes = ENTROPY_ENCODER_FLUSH(&significand_bitstream[i]);
 315       i_bytes = ENTROPY_ENCODER_FLUSH(&insignificand_bitstream[i]);
 316
 317       if (s_bytes < significand_limittab[i])
 318          significand_limittab[i] = s_bytes;
 319
 320       if (i_bytes < insignificand_limittab[i])
 321          insignificand_limittab[i] = i_bytes;
 322
 323       byte_count += significand_limittab[i];
 324       byte_count += insignificand_limittab[i];
 325
 326       printf ("insignificand_limittab[%i]  == %u / %u\n",
 327               i, insignificand_limittab[i], i_bytes);
 328       printf ("  significand_limittab[%i]  == %u / %u\n",
 329               i, significand_limittab[i], s_bytes);
 330
 331       significand_limit -= significand_limittab[i];
 332       insignificand_limit -= insignificand_limittab[i];
 333    }
 334
 335    printf ("byte_count == %u\n", byte_count);
 336
 337    return byte_count;
 338 }
 339
 340
 341 /**
 342  *  write 'em binary for now, should be easy to compress ...
 343  */
 344 static
 345 uint8_t* write_limittabs (uint8_t *bitstream,
 346                           uint32_t significand_limittab [],
 347                           uint32_t insignificand_limittab [])
 348 {
 349    int i;
 350
 351    for (i=0; i<TYPE_BITS; i++) {
 352       *(uint32_t*) bitstream = significand_limittab[i];
 353       bitstream += 4;
 354    }
 355
 356    for (i=0; i<TYPE_BITS; i++) {
 357       *(uint32_t*) bitstream = insignificand_limittab[i];
 358       bitstream += 4;
 359    }
 360
 361    return bitstream;
 362 }
 363
 364
 365 static
 366 uint8_t* read_limittabs (uint8_t *bitstream,
 367                          uint32_t significand_limittab [],
 368                          uint32_t insignificand_limittab [])
 369 {
 370    int i;
 371
 372    for (i=0; i<TYPE_BITS; i++) {
 373       significand_limittab[i] = *(uint32_t*) bitstream;
 374       printf ("significand_limittab[%i]  == %u\n", i, significand_limittab[i]);
 375       bitstream += 4;
 376    }
 377
 378    for (i=0; i<TYPE_BITS; i++) {
 379       insignificand_limittab[i] = *(uint32_t*) bitstream;
 380       printf ("insignificand_limittab[%i]  == %u\n", i, insignificand_limittab[i]);
 381       bitstream += 4;
 382    }
 383
 384    return bitstream;
 385 }
 386
 387
 388 /**
 389  *  concatenate entropy coder bitstreams
 390  */
 391 static
 392 void merge_bitstreams (uint8_t *bitstream,
 393                        ENTROPY_CODER significand_bitstream [],
 394                        ENTROPY_CODER insignificand_bitstream [],
 395                        uint32_t significand_limittab [],
 396                        uint32_t insignificand_limittab [])
 397 {
 398    int i;
 399
 400    for (i=TYPE_BITS-1; i>=0; i--) {
 401       memcpy (bitstream,
 402               ENTROPY_CODER_BITSTREAM(&significand_bitstream[i]),
 403               significand_limittab[i]);
 404
 405       bitstream += significand_limittab[i];
 406    }
 407
 408    for (i=TYPE_BITS-1; i>=0; i--) {
 409       memcpy (bitstream,
 410               ENTROPY_CODER_BITSTREAM(&insignificand_bitstream[i]),
 411               insignificand_limittab[i]);
 412
 413       bitstream += insignificand_limittab[i];
 414    }
 415 }
 416
 417
 418 static
 419 void split_bitstreams (uint8_t *bitstream,
 420                        ENTROPY_CODER significand_bitstream [],
 421                        ENTROPY_CODER insignificand_bitstream [],
 422                        uint32_t significand_limittab [],
 423                        uint32_t insignificand_limittab [])
 424 {
 425    uint32_t byte_count;
 426    int i;
 427
 428    for (i=TYPE_BITS-1; i>=0; i--) {
 429       byte_count = significand_limittab[i];
 430       ENTROPY_DECODER_INIT(&significand_bitstream[i], bitstream, byte_count);
 431       bitstream += byte_count;
 432    }
 433
 434    for (i=TYPE_BITS-1; i>=0; i--) {
 435       byte_count = insignificand_limittab[i];
 436       ENTROPY_DECODER_INIT(&insignificand_bitstream[i], bitstream, byte_count);
 437       bitstream += byte_count;
 438    }
 439 }
 440
 441
 442 int wavelet_3d_buf_encode_coeff (const Wavelet3DBuf* buf,
 443                                  uint8_t *bitstream,
 444                                  uint32_t limit)
 445 {
 446    ENTROPY_CODER significand_bitstream [TYPE_BITS];
 447    ENTROPY_CODER insignificand_bitstream [TYPE_BITS];
 448    uint32_t significand_limittab [TYPE_BITS];
 449    uint32_t insignificand_limittab [TYPE_BITS];
 450    uint32_t byte_count;
 451    int i;
 452
 453    for (i=0; i<TYPE_BITS; i++)
 454       ENTROPY_ENCODER_INIT(&significand_bitstream[i], limit);
 455    for (i=0; i<TYPE_BITS; i++)
 456       ENTROPY_ENCODER_INIT(&insignificand_bitstream[i], limit);
 457
 458    encode_coefficients (buf, significand_bitstream, insignificand_bitstream);
 459
 460    byte_count = setup_limittabs (significand_bitstream, insignificand_bitstream,
 461                                  significand_limittab, insignificand_limittab,
 462                                  limit);
 463
 464    bitstream = write_limittabs (bitstream,
 465                                 significand_limittab, insignificand_limittab);
 466
 467    merge_bitstreams (bitstream, significand_bitstream, insignificand_bitstream,
 468                      significand_limittab, insignificand_limittab);
 469
 470    for (i=0; i<TYPE_BITS; i++) {
 471       ENTROPY_ENCODER_DONE(&significand_bitstream[i]);
 472       ENTROPY_ENCODER_DONE(&insignificand_bitstream[i]);
 473    }
 474
 475    return byte_count;
 476 }
 477
 478
 479 void wavelet_3d_buf_decode_coeff (Wavelet3DBuf* buf,
 480                                   uint8_t *bitstream,
 481                                   uint32_t byte_count)
 482 {
 483    ENTROPY_CODER significand_bitstream [TYPE_BITS];
 484    ENTROPY_CODER insignificand_bitstream [TYPE_BITS];
 485    uint32_t significand_limittab [TYPE_BITS];
 486    uint32_t insignificand_limittab [TYPE_BITS];
 487    int i;
 488
 489    memset (buf->data, 0,
 490            buf->width * buf->height * buf->frames * sizeof(TYPE));
 491
 492    bitstream = read_limittabs (bitstream,
 493                                significand_limittab, insignificand_limittab);
 494
 495    split_bitstreams (bitstream, significand_bitstream, insignificand_bitstream,
 496                                significand_limittab, insignificand_limittab);
 497
 498    decode_coefficients (buf, significand_bitstream, insignificand_bitstream);
 499
 500    for (i=0; i<TYPE_BITS; i++) {
 501       ENTROPY_DECODER_DONE(&significand_bitstream[i]);
 502       ENTROPY_DECODER_DONE(&insignificand_bitstream[i]);
 503    }
 504 }
 505
 506