third_party/libwebp/utils/bit_writer.c

   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@gmail.com)
  13 //         Vikas Arora (vikaas.arora@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 Flush(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) Flush(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) Flush(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   Flush(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;   // Flush() 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 //------------------------------------------------------------------------------