Blame src/utils/bit_writer_utils.c

Packit 9c6abc
// Copyright 2011 Google Inc. All Rights Reserved.
Packit 9c6abc
//
Packit 9c6abc
// Use of this source code is governed by a BSD-style license
Packit 9c6abc
// that can be found in the COPYING file in the root of the source
Packit 9c6abc
// tree. An additional intellectual property rights grant can be found
Packit 9c6abc
// in the file PATENTS. All contributing project authors may
Packit 9c6abc
// be found in the AUTHORS file in the root of the source tree.
Packit 9c6abc
// -----------------------------------------------------------------------------
Packit 9c6abc
//
Packit 9c6abc
// Bit writing and boolean coder
Packit 9c6abc
//
Packit 9c6abc
// Author: Skal (pascal.massimino@gmail.com)
Packit 9c6abc
//         Vikas Arora (vikaas.arora@gmail.com)
Packit 9c6abc
Packit 9c6abc
#include <assert.h>
Packit 9c6abc
#include <string.h>   // for memcpy()
Packit 9c6abc
#include <stdlib.h>
Packit 9c6abc
Packit 9c6abc
#include "src/utils/bit_writer_utils.h"
Packit 9c6abc
#include "src/utils/endian_inl_utils.h"
Packit 9c6abc
#include "src/utils/utils.h"
Packit 9c6abc
Packit 9c6abc
//------------------------------------------------------------------------------
Packit 9c6abc
// VP8BitWriter
Packit 9c6abc
Packit 9c6abc
static int BitWriterResize(VP8BitWriter* const bw, size_t extra_size) {
Packit 9c6abc
  uint8_t* new_buf;
Packit 9c6abc
  size_t new_size;
Packit 9c6abc
  const uint64_t needed_size_64b = (uint64_t)bw->pos_ + extra_size;
Packit 9c6abc
  const size_t needed_size = (size_t)needed_size_64b;
Packit 9c6abc
  if (needed_size_64b != needed_size) {
Packit 9c6abc
    bw->error_ = 1;
Packit 9c6abc
    return 0;
Packit 9c6abc
  }
Packit 9c6abc
  if (needed_size <= bw->max_pos_) return 1;
Packit 9c6abc
  // If the following line wraps over 32bit, the test just after will catch it.
Packit 9c6abc
  new_size = 2 * bw->max_pos_;
Packit 9c6abc
  if (new_size < needed_size) new_size = needed_size;
Packit 9c6abc
  if (new_size < 1024) new_size = 1024;
Packit 9c6abc
  new_buf = (uint8_t*)WebPSafeMalloc(1ULL, new_size);
Packit 9c6abc
  if (new_buf == NULL) {
Packit 9c6abc
    bw->error_ = 1;
Packit 9c6abc
    return 0;
Packit 9c6abc
  }
Packit 9c6abc
  if (bw->pos_ > 0) {
Packit 9c6abc
    assert(bw->buf_ != NULL);
Packit 9c6abc
    memcpy(new_buf, bw->buf_, bw->pos_);
Packit 9c6abc
  }
Packit 9c6abc
  WebPSafeFree(bw->buf_);
Packit 9c6abc
  bw->buf_ = new_buf;
Packit 9c6abc
  bw->max_pos_ = new_size;
Packit 9c6abc
  return 1;
Packit 9c6abc
}
Packit 9c6abc
Packit 9c6abc
static void Flush(VP8BitWriter* const bw) {
Packit 9c6abc
  const int s = 8 + bw->nb_bits_;
Packit 9c6abc
  const int32_t bits = bw->value_ >> s;
Packit 9c6abc
  assert(bw->nb_bits_ >= 0);
Packit 9c6abc
  bw->value_ -= bits << s;
Packit 9c6abc
  bw->nb_bits_ -= 8;
Packit 9c6abc
  if ((bits & 0xff) != 0xff) {
Packit 9c6abc
    size_t pos = bw->pos_;
Packit 9c6abc
    if (!BitWriterResize(bw, bw->run_ + 1)) {
Packit 9c6abc
      return;
Packit 9c6abc
    }
Packit 9c6abc
    if (bits & 0x100) {  // overflow -> propagate carry over pending 0xff's
Packit 9c6abc
      if (pos > 0) bw->buf_[pos - 1]++;
Packit 9c6abc
    }
Packit 9c6abc
    if (bw->run_ > 0) {
Packit 9c6abc
      const int value = (bits & 0x100) ? 0x00 : 0xff;
Packit 9c6abc
      for (; bw->run_ > 0; --bw->run_) bw->buf_[pos++] = value;
Packit 9c6abc
    }
Packit 9c6abc
    bw->buf_[pos++] = bits;
Packit 9c6abc
    bw->pos_ = pos;
Packit 9c6abc
  } else {
Packit 9c6abc
    bw->run_++;   // delay writing of bytes 0xff, pending eventual carry.
Packit 9c6abc
  }
Packit 9c6abc
}
Packit 9c6abc
Packit 9c6abc
//------------------------------------------------------------------------------
Packit 9c6abc
// renormalization
Packit 9c6abc
Packit 9c6abc
static const uint8_t kNorm[128] = {  // renorm_sizes[i] = 8 - log2(i)
Packit 9c6abc
     7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4,
Packit 9c6abc
  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
Packit 9c6abc
  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
Packit 9c6abc
  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
Packit 9c6abc
  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
Packit 9c6abc
  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
Packit 9c6abc
  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
Packit 9c6abc
  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
Packit 9c6abc
  0
Packit 9c6abc
};
Packit 9c6abc
Packit 9c6abc
// range = ((range + 1) << kVP8Log2Range[range]) - 1
Packit 9c6abc
static const uint8_t kNewRange[128] = {
Packit 9c6abc
  127, 127, 191, 127, 159, 191, 223, 127, 143, 159, 175, 191, 207, 223, 239,
Packit 9c6abc
  127, 135, 143, 151, 159, 167, 175, 183, 191, 199, 207, 215, 223, 231, 239,
Packit 9c6abc
  247, 127, 131, 135, 139, 143, 147, 151, 155, 159, 163, 167, 171, 175, 179,
Packit 9c6abc
  183, 187, 191, 195, 199, 203, 207, 211, 215, 219, 223, 227, 231, 235, 239,
Packit 9c6abc
  243, 247, 251, 127, 129, 131, 133, 135, 137, 139, 141, 143, 145, 147, 149,
Packit 9c6abc
  151, 153, 155, 157, 159, 161, 163, 165, 167, 169, 171, 173, 175, 177, 179,
Packit 9c6abc
  181, 183, 185, 187, 189, 191, 193, 195, 197, 199, 201, 203, 205, 207, 209,
Packit 9c6abc
  211, 213, 215, 217, 219, 221, 223, 225, 227, 229, 231, 233, 235, 237, 239,
Packit 9c6abc
  241, 243, 245, 247, 249, 251, 253, 127
Packit 9c6abc
};
Packit 9c6abc
Packit 9c6abc
int VP8PutBit(VP8BitWriter* const bw, int bit, int prob) {
Packit 9c6abc
  const int split = (bw->range_ * prob) >> 8;
Packit 9c6abc
  if (bit) {
Packit 9c6abc
    bw->value_ += split + 1;
Packit 9c6abc
    bw->range_ -= split + 1;
Packit 9c6abc
  } else {
Packit 9c6abc
    bw->range_ = split;
Packit 9c6abc
  }
Packit 9c6abc
  if (bw->range_ < 127) {   // emit 'shift' bits out and renormalize
Packit 9c6abc
    const int shift = kNorm[bw->range_];
Packit 9c6abc
    bw->range_ = kNewRange[bw->range_];
Packit 9c6abc
    bw->value_ <<= shift;
Packit 9c6abc
    bw->nb_bits_ += shift;
Packit 9c6abc
    if (bw->nb_bits_ > 0) Flush(bw);
Packit 9c6abc
  }
Packit 9c6abc
  return bit;
Packit 9c6abc
}
Packit 9c6abc
Packit 9c6abc
int VP8PutBitUniform(VP8BitWriter* const bw, int bit) {
Packit 9c6abc
  const int split = bw->range_ >> 1;
Packit 9c6abc
  if (bit) {
Packit 9c6abc
    bw->value_ += split + 1;
Packit 9c6abc
    bw->range_ -= split + 1;
Packit 9c6abc
  } else {
Packit 9c6abc
    bw->range_ = split;
Packit 9c6abc
  }
Packit 9c6abc
  if (bw->range_ < 127) {
Packit 9c6abc
    bw->range_ = kNewRange[bw->range_];
Packit 9c6abc
    bw->value_ <<= 1;
Packit 9c6abc
    bw->nb_bits_ += 1;
Packit 9c6abc
    if (bw->nb_bits_ > 0) Flush(bw);
Packit 9c6abc
  }
Packit 9c6abc
  return bit;
Packit 9c6abc
}
Packit 9c6abc
Packit 9c6abc
void VP8PutBits(VP8BitWriter* const bw, uint32_t value, int nb_bits) {
Packit 9c6abc
  uint32_t mask;
Packit 9c6abc
  assert(nb_bits > 0 && nb_bits < 32);
Packit 9c6abc
  for (mask = 1u << (nb_bits - 1); mask; mask >>= 1) {
Packit 9c6abc
    VP8PutBitUniform(bw, value & mask);
Packit 9c6abc
  }
Packit 9c6abc
}
Packit 9c6abc
Packit 9c6abc
void VP8PutSignedBits(VP8BitWriter* const bw, int value, int nb_bits) {
Packit 9c6abc
  if (!VP8PutBitUniform(bw, value != 0)) return;
Packit 9c6abc
  if (value < 0) {
Packit 9c6abc
    VP8PutBits(bw, ((-value) << 1) | 1, nb_bits + 1);
Packit 9c6abc
  } else {
Packit 9c6abc
    VP8PutBits(bw, value << 1, nb_bits + 1);
Packit 9c6abc
  }
Packit 9c6abc
}
Packit 9c6abc
Packit 9c6abc
//------------------------------------------------------------------------------
Packit 9c6abc
Packit 9c6abc
int VP8BitWriterInit(VP8BitWriter* const bw, size_t expected_size) {
Packit 9c6abc
  bw->range_   = 255 - 1;
Packit 9c6abc
  bw->value_   = 0;
Packit 9c6abc
  bw->run_     = 0;
Packit 9c6abc
  bw->nb_bits_ = -8;
Packit 9c6abc
  bw->pos_     = 0;
Packit 9c6abc
  bw->max_pos_ = 0;
Packit 9c6abc
  bw->error_   = 0;
Packit 9c6abc
  bw->buf_     = NULL;
Packit 9c6abc
  return (expected_size > 0) ? BitWriterResize(bw, expected_size) : 1;
Packit 9c6abc
}
Packit 9c6abc
Packit 9c6abc
uint8_t* VP8BitWriterFinish(VP8BitWriter* const bw) {
Packit 9c6abc
  VP8PutBits(bw, 0, 9 - bw->nb_bits_);
Packit 9c6abc
  bw->nb_bits_ = 0;   // pad with zeroes
Packit 9c6abc
  Flush(bw);
Packit 9c6abc
  return bw->buf_;
Packit 9c6abc
}
Packit 9c6abc
Packit 9c6abc
int VP8BitWriterAppend(VP8BitWriter* const bw,
Packit 9c6abc
                       const uint8_t* data, size_t size) {
Packit 9c6abc
  assert(data != NULL);
Packit 9c6abc
  if (bw->nb_bits_ != -8) return 0;   // Flush() must have been called
Packit 9c6abc
  if (!BitWriterResize(bw, size)) return 0;
Packit 9c6abc
  memcpy(bw->buf_ + bw->pos_, data, size);
Packit 9c6abc
  bw->pos_ += size;
Packit 9c6abc
  return 1;
Packit 9c6abc
}
Packit 9c6abc
Packit 9c6abc
void VP8BitWriterWipeOut(VP8BitWriter* const bw) {
Packit 9c6abc
  if (bw != NULL) {
Packit 9c6abc
    WebPSafeFree(bw->buf_);
Packit 9c6abc
    memset(bw, 0, sizeof(*bw));
Packit 9c6abc
  }
Packit 9c6abc
}
Packit 9c6abc
Packit 9c6abc
//------------------------------------------------------------------------------
Packit 9c6abc
// VP8LBitWriter
Packit 9c6abc
Packit 9c6abc
// This is the minimum amount of size the memory buffer is guaranteed to grow
Packit 9c6abc
// when extra space is needed.
Packit 9c6abc
#define MIN_EXTRA_SIZE  (32768ULL)
Packit 9c6abc
Packit 9c6abc
// Returns 1 on success.
Packit 9c6abc
static int VP8LBitWriterResize(VP8LBitWriter* const bw, size_t extra_size) {
Packit 9c6abc
  uint8_t* allocated_buf;
Packit 9c6abc
  size_t allocated_size;
Packit 9c6abc
  const size_t max_bytes = bw->end_ - bw->buf_;
Packit 9c6abc
  const size_t current_size = bw->cur_ - bw->buf_;
Packit 9c6abc
  const uint64_t size_required_64b = (uint64_t)current_size + extra_size;
Packit 9c6abc
  const size_t size_required = (size_t)size_required_64b;
Packit 9c6abc
  if (size_required != size_required_64b) {
Packit 9c6abc
    bw->error_ = 1;
Packit 9c6abc
    return 0;
Packit 9c6abc
  }
Packit 9c6abc
  if (max_bytes > 0 && size_required <= max_bytes) return 1;
Packit 9c6abc
  allocated_size = (3 * max_bytes) >> 1;
Packit 9c6abc
  if (allocated_size < size_required) allocated_size = size_required;
Packit 9c6abc
  // make allocated size multiple of 1k
Packit 9c6abc
  allocated_size = (((allocated_size >> 10) + 1) << 10);
Packit 9c6abc
  allocated_buf = (uint8_t*)WebPSafeMalloc(1ULL, allocated_size);
Packit 9c6abc
  if (allocated_buf == NULL) {
Packit 9c6abc
    bw->error_ = 1;
Packit 9c6abc
    return 0;
Packit 9c6abc
  }
Packit 9c6abc
  if (current_size > 0) {
Packit 9c6abc
    memcpy(allocated_buf, bw->buf_, current_size);
Packit 9c6abc
  }
Packit 9c6abc
  WebPSafeFree(bw->buf_);
Packit 9c6abc
  bw->buf_ = allocated_buf;
Packit 9c6abc
  bw->cur_ = bw->buf_ + current_size;
Packit 9c6abc
  bw->end_ = bw->buf_ + allocated_size;
Packit 9c6abc
  return 1;
Packit 9c6abc
}
Packit 9c6abc
Packit 9c6abc
int VP8LBitWriterInit(VP8LBitWriter* const bw, size_t expected_size) {
Packit 9c6abc
  memset(bw, 0, sizeof(*bw));
Packit 9c6abc
  return VP8LBitWriterResize(bw, expected_size);
Packit 9c6abc
}
Packit 9c6abc
Packit 9c6abc
int VP8LBitWriterClone(const VP8LBitWriter* const src,
Packit 9c6abc
                       VP8LBitWriter* const dst) {
Packit 9c6abc
  const size_t current_size = src->cur_ - src->buf_;
Packit 9c6abc
  assert(src->cur_ >= src->buf_ && src->cur_ <= src->end_);
Packit 9c6abc
  if (!VP8LBitWriterResize(dst, current_size)) return 0;
Packit 9c6abc
  memcpy(dst->buf_, src->buf_, current_size);
Packit 9c6abc
  dst->bits_ = src->bits_;
Packit 9c6abc
  dst->used_ = src->used_;
Packit 9c6abc
  dst->error_ = src->error_;
Packit 9c6abc
  return 1;
Packit 9c6abc
}
Packit 9c6abc
Packit 9c6abc
void VP8LBitWriterWipeOut(VP8LBitWriter* const bw) {
Packit 9c6abc
  if (bw != NULL) {
Packit 9c6abc
    WebPSafeFree(bw->buf_);
Packit 9c6abc
    memset(bw, 0, sizeof(*bw));
Packit 9c6abc
  }
Packit 9c6abc
}
Packit 9c6abc
Packit 9c6abc
void VP8LBitWriterReset(const VP8LBitWriter* const bw_init,
Packit 9c6abc
                        VP8LBitWriter* const bw) {
Packit 9c6abc
  bw->bits_ = bw_init->bits_;
Packit 9c6abc
  bw->used_ = bw_init->used_;
Packit 9c6abc
  bw->cur_ = bw->buf_ + (bw_init->cur_ - bw_init->buf_);
Packit 9c6abc
  assert(bw->cur_ <= bw->end_);
Packit 9c6abc
  bw->error_ = bw_init->error_;
Packit 9c6abc
}
Packit 9c6abc
Packit 9c6abc
void VP8LBitWriterSwap(VP8LBitWriter* const src, VP8LBitWriter* const dst) {
Packit 9c6abc
  const VP8LBitWriter tmp = *src;
Packit 9c6abc
  *src = *dst;
Packit 9c6abc
  *dst = tmp;
Packit 9c6abc
}
Packit 9c6abc
Packit 9c6abc
void VP8LPutBitsFlushBits(VP8LBitWriter* const bw) {
Packit 9c6abc
  // If needed, make some room by flushing some bits out.
Packit 9c6abc
  if (bw->cur_ + VP8L_WRITER_BYTES > bw->end_) {
Packit 9c6abc
    const uint64_t extra_size = (bw->end_ - bw->buf_) + MIN_EXTRA_SIZE;
Packit 9c6abc
    if (extra_size != (size_t)extra_size ||
Packit 9c6abc
        !VP8LBitWriterResize(bw, (size_t)extra_size)) {
Packit 9c6abc
      bw->cur_ = bw->buf_;
Packit 9c6abc
      bw->error_ = 1;
Packit 9c6abc
      return;
Packit 9c6abc
    }
Packit 9c6abc
  }
Packit 9c6abc
  *(vp8l_wtype_t*)bw->cur_ = (vp8l_wtype_t)WSWAP((vp8l_wtype_t)bw->bits_);
Packit 9c6abc
  bw->cur_ += VP8L_WRITER_BYTES;
Packit 9c6abc
  bw->bits_ >>= VP8L_WRITER_BITS;
Packit 9c6abc
  bw->used_ -= VP8L_WRITER_BITS;
Packit 9c6abc
}
Packit 9c6abc
Packit 9c6abc
void VP8LPutBitsInternal(VP8LBitWriter* const bw, uint32_t bits, int n_bits) {
Packit 9c6abc
  assert(n_bits <= 32);
Packit 9c6abc
  // That's the max we can handle:
Packit 9c6abc
  assert(sizeof(vp8l_wtype_t) == 2);
Packit 9c6abc
  if (n_bits > 0) {
Packit 9c6abc
    vp8l_atype_t lbits = bw->bits_;
Packit 9c6abc
    int used = bw->used_;
Packit 9c6abc
    // Special case of overflow handling for 32bit accumulator (2-steps flush).
Packit 9c6abc
#if VP8L_WRITER_BITS == 16
Packit 9c6abc
    if (used + n_bits >= VP8L_WRITER_MAX_BITS) {
Packit 9c6abc
      // Fill up all the VP8L_WRITER_MAX_BITS so it can be flushed out below.
Packit 9c6abc
      const int shift = VP8L_WRITER_MAX_BITS - used;
Packit 9c6abc
      lbits |= (vp8l_atype_t)bits << used;
Packit 9c6abc
      used = VP8L_WRITER_MAX_BITS;
Packit 9c6abc
      n_bits -= shift;
Packit 9c6abc
      bits >>= shift;
Packit 9c6abc
      assert(n_bits <= VP8L_WRITER_MAX_BITS);
Packit 9c6abc
    }
Packit 9c6abc
#endif
Packit 9c6abc
    // If needed, make some room by flushing some bits out.
Packit 9c6abc
    while (used >= VP8L_WRITER_BITS) {
Packit 9c6abc
      if (bw->cur_ + VP8L_WRITER_BYTES > bw->end_) {
Packit 9c6abc
        const uint64_t extra_size = (bw->end_ - bw->buf_) + MIN_EXTRA_SIZE;
Packit 9c6abc
        if (extra_size != (size_t)extra_size ||
Packit 9c6abc
            !VP8LBitWriterResize(bw, (size_t)extra_size)) {
Packit 9c6abc
          bw->cur_ = bw->buf_;
Packit 9c6abc
          bw->error_ = 1;
Packit 9c6abc
          return;
Packit 9c6abc
        }
Packit 9c6abc
      }
Packit 9c6abc
      *(vp8l_wtype_t*)bw->cur_ = (vp8l_wtype_t)WSWAP((vp8l_wtype_t)lbits);
Packit 9c6abc
      bw->cur_ += VP8L_WRITER_BYTES;
Packit 9c6abc
      lbits >>= VP8L_WRITER_BITS;
Packit 9c6abc
      used -= VP8L_WRITER_BITS;
Packit 9c6abc
    }
Packit 9c6abc
    bw->bits_ = lbits | ((vp8l_atype_t)bits << used);
Packit 9c6abc
    bw->used_ = used + n_bits;
Packit 9c6abc
  }
Packit 9c6abc
}
Packit 9c6abc
Packit 9c6abc
uint8_t* VP8LBitWriterFinish(VP8LBitWriter* const bw) {
Packit 9c6abc
  // flush leftover bits
Packit 9c6abc
  if (VP8LBitWriterResize(bw, (bw->used_ + 7) >> 3)) {
Packit 9c6abc
    while (bw->used_ > 0) {
Packit 9c6abc
      *bw->cur_++ = (uint8_t)bw->bits_;
Packit 9c6abc
      bw->bits_ >>= 8;
Packit 9c6abc
      bw->used_ -= 8;
Packit 9c6abc
    }
Packit 9c6abc
    bw->used_ = 0;
Packit 9c6abc
  }
Packit 9c6abc
  return bw->buf_;
Packit 9c6abc
}
Packit 9c6abc
Packit 9c6abc
//------------------------------------------------------------------------------