Home | History | Annotate | Download | only in utils
      1 // Copyright 2011 Google Inc. All Rights Reserved.
      2 //
      3 // Use of this source code is governed by a BSD-style license
      4 // that can be found in the COPYING file in the root of the source
      5 // tree. An additional intellectual property rights grant can be found
      6 // in the file PATENTS. All contributing project authors may
      7 // be found in the AUTHORS file in the root of the source tree.
      8 // -----------------------------------------------------------------------------
      9 //
     10 // Bit writing and boolean coder
     11 //
     12 // Author: Skal (pascal.massimino (at) gmail.com)
     13 //         Vikas Arora (vikaas.arora (at) gmail.com)
     14 
     15 #include <assert.h>
     16 #include <string.h>   // for memcpy()
     17 #include <stdlib.h>
     18 
     19 #include "./bit_writer.h"
     20 #include "./endian_inl.h"
     21 #include "./utils.h"
     22 
     23 //------------------------------------------------------------------------------
     24 // VP8BitWriter
     25 
     26 static int BitWriterResize(VP8BitWriter* const bw, size_t extra_size) {
     27   uint8_t* new_buf;
     28   size_t new_size;
     29   const uint64_t needed_size_64b = (uint64_t)bw->pos_ + extra_size;
     30   const size_t needed_size = (size_t)needed_size_64b;
     31   if (needed_size_64b != needed_size) {
     32     bw->error_ = 1;
     33     return 0;
     34   }
     35   if (needed_size <= bw->max_pos_) return 1;
     36   // If the following line wraps over 32bit, the test just after will catch it.
     37   new_size = 2 * bw->max_pos_;
     38   if (new_size < needed_size) new_size = needed_size;
     39   if (new_size < 1024) new_size = 1024;
     40   new_buf = (uint8_t*)WebPSafeMalloc(1ULL, new_size);
     41   if (new_buf == NULL) {
     42     bw->error_ = 1;
     43     return 0;
     44   }
     45   if (bw->pos_ > 0) {
     46     assert(bw->buf_ != NULL);
     47     memcpy(new_buf, bw->buf_, bw->pos_);
     48   }
     49   WebPSafeFree(bw->buf_);
     50   bw->buf_ = new_buf;
     51   bw->max_pos_ = new_size;
     52   return 1;
     53 }
     54 
     55 static void kFlush(VP8BitWriter* const bw) {
     56   const int s = 8 + bw->nb_bits_;
     57   const int32_t bits = bw->value_ >> s;
     58   assert(bw->nb_bits_ >= 0);
     59   bw->value_ -= bits << s;
     60   bw->nb_bits_ -= 8;
     61   if ((bits & 0xff) != 0xff) {
     62     size_t pos = bw->pos_;
     63     if (!BitWriterResize(bw, bw->run_ + 1)) {
     64       return;
     65     }
     66     if (bits & 0x100) {  // overflow -> propagate carry over pending 0xff's
     67       if (pos > 0) bw->buf_[pos - 1]++;
     68     }
     69     if (bw->run_ > 0) {
     70       const int value = (bits & 0x100) ? 0x00 : 0xff;
     71       for (; bw->run_ > 0; --bw->run_) bw->buf_[pos++] = value;
     72     }
     73     bw->buf_[pos++] = bits;
     74     bw->pos_ = pos;
     75   } else {
     76     bw->run_++;   // delay writing of bytes 0xff, pending eventual carry.
     77   }
     78 }
     79 
     80 //------------------------------------------------------------------------------
     81 // renormalization
     82 
     83 static const uint8_t kNorm[128] = {  // renorm_sizes[i] = 8 - log2(i)
     84      7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4,
     85   3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
     86   2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
     87   2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
     88   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
     89   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
     90   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
     91   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
     92   0
     93 };
     94 
     95 // range = ((range + 1) << kVP8Log2Range[range]) - 1
     96 static const uint8_t kNewRange[128] = {
     97   127, 127, 191, 127, 159, 191, 223, 127, 143, 159, 175, 191, 207, 223, 239,
     98   127, 135, 143, 151, 159, 167, 175, 183, 191, 199, 207, 215, 223, 231, 239,
     99   247, 127, 131, 135, 139, 143, 147, 151, 155, 159, 163, 167, 171, 175, 179,
    100   183, 187, 191, 195, 199, 203, 207, 211, 215, 219, 223, 227, 231, 235, 239,
    101   243, 247, 251, 127, 129, 131, 133, 135, 137, 139, 141, 143, 145, 147, 149,
    102   151, 153, 155, 157, 159, 161, 163, 165, 167, 169, 171, 173, 175, 177, 179,
    103   181, 183, 185, 187, 189, 191, 193, 195, 197, 199, 201, 203, 205, 207, 209,
    104   211, 213, 215, 217, 219, 221, 223, 225, 227, 229, 231, 233, 235, 237, 239,
    105   241, 243, 245, 247, 249, 251, 253, 127
    106 };
    107 
    108 int VP8PutBit(VP8BitWriter* const bw, int bit, int prob) {
    109   const int split = (bw->range_ * prob) >> 8;
    110   if (bit) {
    111     bw->value_ += split + 1;
    112     bw->range_ -= split + 1;
    113   } else {
    114     bw->range_ = split;
    115   }
    116   if (bw->range_ < 127) {   // emit 'shift' bits out and renormalize
    117     const int shift = kNorm[bw->range_];
    118     bw->range_ = kNewRange[bw->range_];
    119     bw->value_ <<= shift;
    120     bw->nb_bits_ += shift;
    121     if (bw->nb_bits_ > 0) kFlush(bw);
    122   }
    123   return bit;
    124 }
    125 
    126 int VP8PutBitUniform(VP8BitWriter* const bw, int bit) {
    127   const int split = bw->range_ >> 1;
    128   if (bit) {
    129     bw->value_ += split + 1;
    130     bw->range_ -= split + 1;
    131   } else {
    132     bw->range_ = split;
    133   }
    134   if (bw->range_ < 127) {
    135     bw->range_ = kNewRange[bw->range_];
    136     bw->value_ <<= 1;
    137     bw->nb_bits_ += 1;
    138     if (bw->nb_bits_ > 0) kFlush(bw);
    139   }
    140   return bit;
    141 }
    142 
    143 void VP8PutValue(VP8BitWriter* const bw, int value, int nb_bits) {
    144   int mask;
    145   for (mask = 1 << (nb_bits - 1); mask; mask >>= 1)
    146     VP8PutBitUniform(bw, value & mask);
    147 }
    148 
    149 void VP8PutSignedValue(VP8BitWriter* const bw, int value, int nb_bits) {
    150   if (!VP8PutBitUniform(bw, value != 0))
    151     return;
    152   if (value < 0) {
    153     VP8PutValue(bw, ((-value) << 1) | 1, nb_bits + 1);
    154   } else {
    155     VP8PutValue(bw, value << 1, nb_bits + 1);
    156   }
    157 }
    158 
    159 //------------------------------------------------------------------------------
    160 
    161 int VP8BitWriterInit(VP8BitWriter* const bw, size_t expected_size) {
    162   bw->range_   = 255 - 1;
    163   bw->value_   = 0;
    164   bw->run_     = 0;
    165   bw->nb_bits_ = -8;
    166   bw->pos_     = 0;
    167   bw->max_pos_ = 0;
    168   bw->error_   = 0;
    169   bw->buf_     = NULL;
    170   return (expected_size > 0) ? BitWriterResize(bw, expected_size) : 1;
    171 }
    172 
    173 uint8_t* VP8BitWriterFinish(VP8BitWriter* const bw) {
    174   VP8PutValue(bw, 0, 9 - bw->nb_bits_);
    175   bw->nb_bits_ = 0;   // pad with zeroes
    176   kFlush(bw);
    177   return bw->buf_;
    178 }
    179 
    180 int VP8BitWriterAppend(VP8BitWriter* const bw,
    181                        const uint8_t* data, size_t size) {
    182   assert(data != NULL);
    183   if (bw->nb_bits_ != -8) return 0;   // kFlush() must have been called
    184   if (!BitWriterResize(bw, size)) return 0;
    185   memcpy(bw->buf_ + bw->pos_, data, size);
    186   bw->pos_ += size;
    187   return 1;
    188 }
    189 
    190 void VP8BitWriterWipeOut(VP8BitWriter* const bw) {
    191   if (bw != NULL) {
    192     WebPSafeFree(bw->buf_);
    193     memset(bw, 0, sizeof(*bw));
    194   }
    195 }
    196 
    197 //------------------------------------------------------------------------------
    198 // VP8LBitWriter
    199 
    200 // This is the minimum amount of size the memory buffer is guaranteed to grow
    201 // when extra space is needed.
    202 #define MIN_EXTRA_SIZE  (32768ULL)
    203 
    204 #define VP8L_WRITER_BYTES ((int)sizeof(vp8l_wtype_t))
    205 #define VP8L_WRITER_BITS (VP8L_WRITER_BYTES * 8)
    206 #define VP8L_WRITER_MAX_BITS (8 * (int)sizeof(vp8l_atype_t))
    207 
    208 // Returns 1 on success.
    209 static int VP8LBitWriterResize(VP8LBitWriter* const bw, size_t extra_size) {
    210   uint8_t* allocated_buf;
    211   size_t allocated_size;
    212   const size_t max_bytes = bw->end_ - bw->buf_;
    213   const size_t current_size = bw->cur_ - bw->buf_;
    214   const uint64_t size_required_64b = (uint64_t)current_size + extra_size;
    215   const size_t size_required = (size_t)size_required_64b;
    216   if (size_required != size_required_64b) {
    217     bw->error_ = 1;
    218     return 0;
    219   }
    220   if (max_bytes > 0 && size_required <= max_bytes) return 1;
    221   allocated_size = (3 * max_bytes) >> 1;
    222   if (allocated_size < size_required) allocated_size = size_required;
    223   // make allocated size multiple of 1k
    224   allocated_size = (((allocated_size >> 10) + 1) << 10);
    225   allocated_buf = (uint8_t*)WebPSafeMalloc(1ULL, allocated_size);
    226   if (allocated_buf == NULL) {
    227     bw->error_ = 1;
    228     return 0;
    229   }
    230   if (current_size > 0) {
    231     memcpy(allocated_buf, bw->buf_, current_size);
    232   }
    233   WebPSafeFree(bw->buf_);
    234   bw->buf_ = allocated_buf;
    235   bw->cur_ = bw->buf_ + current_size;
    236   bw->end_ = bw->buf_ + allocated_size;
    237   return 1;
    238 }
    239 
    240 int VP8LBitWriterInit(VP8LBitWriter* const bw, size_t expected_size) {
    241   memset(bw, 0, sizeof(*bw));
    242   return VP8LBitWriterResize(bw, expected_size);
    243 }
    244 
    245 void VP8LBitWriterDestroy(VP8LBitWriter* const bw) {
    246   if (bw != NULL) {
    247     WebPSafeFree(bw->buf_);
    248     memset(bw, 0, sizeof(*bw));
    249   }
    250 }
    251 
    252 void VP8LWriteBits(VP8LBitWriter* const bw, int n_bits, uint32_t bits) {
    253   assert(n_bits <= 32);
    254   // That's the max we can handle:
    255   assert(bw->used_ + n_bits <= 2 * VP8L_WRITER_MAX_BITS);
    256   if (n_bits > 0) {
    257     // Local field copy.
    258     vp8l_atype_t lbits = bw->bits_;
    259     int used = bw->used_;
    260     // Special case of overflow handling for 32bit accumulator (2-steps flush).
    261     if (VP8L_WRITER_BITS == 16) {
    262       if (used + n_bits >= VP8L_WRITER_MAX_BITS) {
    263         // Fill up all the VP8L_WRITER_MAX_BITS so it can be flushed out below.
    264         const int shift = VP8L_WRITER_MAX_BITS - used;
    265         lbits |= (vp8l_atype_t)bits << used;
    266         used = VP8L_WRITER_MAX_BITS;
    267         n_bits -= shift;
    268         bits >>= shift;
    269         assert(n_bits <= VP8L_WRITER_MAX_BITS);
    270       }
    271     }
    272     // If needed, make some room by flushing some bits out.
    273     while (used >= VP8L_WRITER_BITS) {
    274       if (bw->cur_ + VP8L_WRITER_BYTES > bw->end_) {
    275         const uint64_t extra_size = (bw->end_ - bw->buf_) + MIN_EXTRA_SIZE;
    276         if (extra_size != (size_t)extra_size ||
    277             !VP8LBitWriterResize(bw, (size_t)extra_size)) {
    278           bw->cur_ = bw->buf_;
    279           bw->error_ = 1;
    280           return;
    281         }
    282       }
    283       *(vp8l_wtype_t*)bw->cur_ = (vp8l_wtype_t)WSWAP((vp8l_wtype_t)lbits);
    284       bw->cur_ += VP8L_WRITER_BYTES;
    285       lbits >>= VP8L_WRITER_BITS;
    286       used -= VP8L_WRITER_BITS;
    287     }
    288     // Eventually, insert new bits.
    289     bw->bits_ = lbits | ((vp8l_atype_t)bits << used);
    290     bw->used_ = used + n_bits;
    291   }
    292 }
    293 
    294 uint8_t* VP8LBitWriterFinish(VP8LBitWriter* const bw) {
    295   // flush leftover bits
    296   if (VP8LBitWriterResize(bw, (bw->used_ + 7) >> 3)) {
    297     while (bw->used_ > 0) {
    298       *bw->cur_++ = (uint8_t)bw->bits_;
    299       bw->bits_ >>= 8;
    300       bw->used_ -= 8;
    301     }
    302     bw->used_ = 0;
    303   }
    304   return bw->buf_;
    305 }
    306 
    307 //------------------------------------------------------------------------------
    308