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 #include "./bit_writer.h"
  19
  20 //------------------------------------------------------------------------------
  21 // VP8BitWriter
  22
  23 static int BitWriterResize(VP8BitWriter* const bw, size_t extra_size) {
  24   uint8_t* new_buf;
  25   size_t new_size;
  26   const uint64_t needed_size_64b = (uint64_t)bw->pos_ + extra_size;
  27   const size_t needed_size = (size_t)needed_size_64b;
  28   if (needed_size_64b != needed_size) {
  29     bw->error_ = 1;
  30     return 0;
  31   }
  32   if (needed_size <= bw->max_pos_) return 1;
  33   // If the following line wraps over 32bit, the test just after will catch it.
  34   new_size = 2 * bw->max_pos_;
  35   if (new_size < needed_size) new_size = needed_size;
  36   if (new_size < 1024) new_size = 1024;
  37   new_buf = (uint8_t*)malloc(new_size);
  38   if (new_buf == NULL) {
  39     bw->error_ = 1;
  40     return 0;
  41   }
  42   if (bw->pos_ > 0) {
  43     assert(bw->buf_ != NULL);
  44     memcpy(new_buf, bw->buf_, bw->pos_);
  45   }
  46   free(bw->buf_);
  47   bw->buf_ = new_buf;
  48   bw->max_pos_ = new_size;
  49   return 1;
  50 }
  51
  52 static void kFlush(VP8BitWriter* const bw) {
  53   const int s = 8 + bw->nb_bits_;
  54   const int32_t bits = bw->value_ >> s;
  55   assert(bw->nb_bits_ >= 0);
  56   bw->value_ -= bits << s;
  57   bw->nb_bits_ -= 8;
  58   if ((bits & 0xff) != 0xff) {
  59     size_t pos = bw->pos_;
  60     if (!BitWriterResize(bw, bw->run_ + 1)) {
  61       return;
  62     }
  63     if (bits & 0x100) {  // overflow -> propagate carry over pending 0xff's
  64       if (pos > 0) bw->buf_[pos - 1]++;
  65     }
  66     if (bw->run_ > 0) {
  67       const int value = (bits & 0x100) ? 0x00 : 0xff;
  68       for (; bw->run_ > 0; --bw->run_) bw->buf_[pos++] = value;
  69     }
  70     bw->buf_[pos++] = bits;
  71     bw->pos_ = pos;
  72   } else {
  73     bw->run_++;   // delay writing of bytes 0xff, pending eventual carry.
  74   }
  75 }
  76
  77 //------------------------------------------------------------------------------
  78 // renormalization
  79
  80 static const uint8_t kNorm[128] = {  // renorm_sizes[i] = 8 - log2(i)
  81      7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4,
  82   3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
  83   2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
  84   2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
  85   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  86   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  87   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  88   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  89   0
  90 };
  91
  92 // range = ((range + 1) << kVP8Log2Range[range]) - 1
  93 static const uint8_t kNewRange[128] = {
  94   127, 127, 191, 127, 159, 191, 223, 127, 143, 159, 175, 191, 207, 223, 239,
  95   127, 135, 143, 151, 159, 167, 175, 183, 191, 199, 207, 215, 223, 231, 239,
  96   247, 127, 131, 135, 139, 143, 147, 151, 155, 159, 163, 167, 171, 175, 179,
  97   183, 187, 191, 195, 199, 203, 207, 211, 215, 219, 223, 227, 231, 235, 239,
  98   243, 247, 251, 127, 129, 131, 133, 135, 137, 139, 141, 143, 145, 147, 149,
  99   151, 153, 155, 157, 159, 161, 163, 165, 167, 169, 171, 173, 175, 177, 179,
 100   181, 183, 185, 187, 189, 191, 193, 195, 197, 199, 201, 203, 205, 207, 209,
 101   211, 213, 215, 217, 219, 221, 223, 225, 227, 229, 231, 233, 235, 237, 239,
 102   241, 243, 245, 247, 249, 251, 253, 127
 103 };
 104
 105 int VP8PutBit(VP8BitWriter* const bw, int bit, int prob) {
 106   const int split = (bw->range_ * prob) >> 8;
 107   if (bit) {
 108     bw->value_ += split + 1;
 109     bw->range_ -= split + 1;
 110   } else {
 111     bw->range_ = split;
 112   }
 113   if (bw->range_ < 127) {   // emit 'shift' bits out and renormalize
 114     const int shift = kNorm[bw->range_];
 115     bw->range_ = kNewRange[bw->range_];
 116     bw->value_ <<= shift;
 117     bw->nb_bits_ += shift;
 118     if (bw->nb_bits_ > 0) kFlush(bw);
 119   }
 120   return bit;
 121 }
 122
 123 int VP8PutBitUniform(VP8BitWriter* const bw, int bit) {
 124   const int split = bw->range_ >> 1;
 125   if (bit) {
 126     bw->value_ += split + 1;
 127     bw->range_ -= split + 1;
 128   } else {
 129     bw->range_ = split;
 130   }
 131   if (bw->range_ < 127) {
 132     bw->range_ = kNewRange[bw->range_];
 133     bw->value_ <<= 1;
 134     bw->nb_bits_ += 1;
 135     if (bw->nb_bits_ > 0) kFlush(bw);
 136   }
 137   return bit;
 138 }
 139
 140 void VP8PutValue(VP8BitWriter* const bw, int value, int nb_bits) {
 141   int mask;
 142   for (mask = 1 << (nb_bits - 1); mask; mask >>= 1)
 143     VP8PutBitUniform(bw, value & mask);
 144 }
 145
 146 void VP8PutSignedValue(VP8BitWriter* const bw, int value, int nb_bits) {
 147   if (!VP8PutBitUniform(bw, value != 0))
 148     return;
 149   if (value < 0) {
 150     VP8PutValue(bw, ((-value) << 1) | 1, nb_bits + 1);
 151   } else {
 152     VP8PutValue(bw, value << 1, nb_bits + 1);
 153   }
 154 }
 155
 156 //------------------------------------------------------------------------------
 157
 158 int VP8BitWriterInit(VP8BitWriter* const bw, size_t expected_size) {
 159   bw->range_   = 255 - 1;
 160   bw->value_   = 0;
 161   bw->run_     = 0;
 162   bw->nb_bits_ = -8;
 163   bw->pos_     = 0;
 164   bw->max_pos_ = 0;
 165   bw->error_   = 0;
 166   bw->buf_     = NULL;
 167   return (expected_size > 0) ? BitWriterResize(bw, expected_size) : 1;
 168 }
 169
 170 uint8_t* VP8BitWriterFinish(VP8BitWriter* const bw) {
 171   VP8PutValue(bw, 0, 9 - bw->nb_bits_);
 172   bw->nb_bits_ = 0;   // pad with zeroes
 173   kFlush(bw);
 174   return bw->buf_;
 175 }
 176
 177 int VP8BitWriterAppend(VP8BitWriter* const bw,
 178                        const uint8_t* data, size_t size) {
 179   assert(data);
 180   if (bw->nb_bits_ != -8) return 0;   // kFlush() must have been called
 181   if (!BitWriterResize(bw, size)) return 0;
 182   memcpy(bw->buf_ + bw->pos_, data, size);
 183   bw->pos_ += size;
 184   return 1;
 185 }
 186
 187 void VP8BitWriterWipeOut(VP8BitWriter* const bw) {
 188   if (bw) {
 189     free(bw->buf_);
 190     memset(bw, 0, sizeof(*bw));
 191   }
 192 }
 193
 194 //------------------------------------------------------------------------------
 195 // VP8LBitWriter
 196
 197 // Returns 1 on success.
 198 static int VP8LBitWriterResize(VP8LBitWriter* const bw, size_t extra_size) {
 199   uint8_t* allocated_buf;
 200   size_t allocated_size;
 201   const size_t current_size = VP8LBitWriterNumBytes(bw);
 202   const uint64_t size_required_64b = (uint64_t)current_size + extra_size;
 203   const size_t size_required = (size_t)size_required_64b;
 204   if (size_required != size_required_64b) {
 205     bw->error_ = 1;
 206     return 0;
 207   }
 208   if (bw->max_bytes_ > 0 && size_required <= bw->max_bytes_) return 1;
 209   allocated_size = (3 * bw->max_bytes_) >> 1;
 210   if (allocated_size < size_required) allocated_size = size_required;
 211   // make allocated size multiple of 1k
 212   allocated_size = (((allocated_size >> 10) + 1) << 10);
 213   allocated_buf = (uint8_t*)malloc(allocated_size);
 214   if (allocated_buf == NULL) {
 215     bw->error_ = 1;
 216     return 0;
 217   }
 218   memcpy(allocated_buf, bw->buf_, current_size);
 219   free(bw->buf_);
 220   bw->buf_ = allocated_buf;
 221   bw->max_bytes_ = allocated_size;
 222   memset(allocated_buf + current_size, 0, allocated_size - current_size);
 223   return 1;
 224 }
 225
 226 int VP8LBitWriterInit(VP8LBitWriter* const bw, size_t expected_size) {
 227   memset(bw, 0, sizeof(*bw));
 228   return VP8LBitWriterResize(bw, expected_size);
 229 }
 230
 231 void VP8LBitWriterDestroy(VP8LBitWriter* const bw) {
 232   if (bw != NULL) {
 233     free(bw->buf_);
 234     memset(bw, 0, sizeof(*bw));
 235   }
 236 }
 237
 238 void VP8LWriteBits(VP8LBitWriter* const bw, int n_bits, uint32_t bits) {
 239   if (n_bits < 1) return;
 240 #if !defined(__BIG_ENDIAN__)
 241   // Technically, this branch of the code can write up to 25 bits at a time,
 242   // but in prefix encoding, the maximum number of bits written is 18 at a time.
 243   {
 244     uint8_t* const p = &bw->buf_[bw->bit_pos_ >> 3];
 245     uint32_t v = *(const uint32_t*)p;
 246     v |= bits << (bw->bit_pos_ & 7);
 247     *(uint32_t*)p = v;
 248     bw->bit_pos_ += n_bits;
 249   }
 250 #else  // BIG_ENDIAN
 251   {
 252     uint8_t* p = &bw->buf_[bw->bit_pos_ >> 3];
 253     const int bits_reserved_in_first_byte = bw->bit_pos_ & 7;
 254     const int bits_left_to_write = n_bits - 8 + bits_reserved_in_first_byte;
 255     // implicit & 0xff is assumed for uint8_t arithmetic
 256     *p++ |= bits << bits_reserved_in_first_byte;
 257     bits >>= 8 - bits_reserved_in_first_byte;
 258     if (bits_left_to_write >= 1) {
 259       *p++ = bits;
 260       bits >>= 8;
 261       if (bits_left_to_write >= 9) {
 262         *p++ = bits;
 263         bits >>= 8;
 264       }
 265     }
 266     assert(n_bits <= 25);
 267     *p = bits;
 268     bw->bit_pos_ += n_bits;
 269   }
 270 #endif
 271   if ((bw->bit_pos_ >> 3) > (bw->max_bytes_ - 8)) {
 272     const uint64_t extra_size = 32768ULL + bw->max_bytes_;
 273     if (extra_size != (size_t)extra_size ||
 274         !VP8LBitWriterResize(bw, (size_t)extra_size)) {
 275       bw->bit_pos_ = 0;
 276       bw->error_ = 1;
 277     }
 278   }
 279 }
 280
 281 //------------------------------------------------------------------------------
 282