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