1a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Copyright 2011 Google Inc. All Rights Reserved. 2a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// 30406ce1417f76f2034833414dcecc9f56253640cVikas Arora// Use of this source code is governed by a BSD-style license 40406ce1417f76f2034833414dcecc9f56253640cVikas Arora// that can be found in the COPYING file in the root of the source 50406ce1417f76f2034833414dcecc9f56253640cVikas Arora// tree. An additional intellectual property rights grant can be found 60406ce1417f76f2034833414dcecc9f56253640cVikas Arora// in the file PATENTS. All contributing project authors may 70406ce1417f76f2034833414dcecc9f56253640cVikas Arora// be found in the AUTHORS file in the root of the source tree. 8a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// ----------------------------------------------------------------------------- 9a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// 10a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Bit writing and boolean coder 11a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// 12a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Author: Skal (pascal.massimino@gmail.com) 13a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Vikas Arora (vikaas.arora@gmail.com) 14a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 15a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora#include <assert.h> 16a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora#include <string.h> // for memcpy() 17a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora#include <stdlib.h> 1833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 19a187300ff9a8a7c10b1fb2ec84223fdd14e6d47bJames Zern#include "src/utils/bit_writer_utils.h" 20a187300ff9a8a7c10b1fb2ec84223fdd14e6d47bJames Zern#include "src/utils/endian_inl_utils.h" 21a187300ff9a8a7c10b1fb2ec84223fdd14e6d47bJames Zern#include "src/utils/utils.h" 22a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 23a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora//------------------------------------------------------------------------------ 24a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// VP8BitWriter 25a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 26a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic int BitWriterResize(VP8BitWriter* const bw, size_t extra_size) { 27a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora uint8_t* new_buf; 28a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora size_t new_size; 29a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const uint64_t needed_size_64b = (uint64_t)bw->pos_ + extra_size; 30a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const size_t needed_size = (size_t)needed_size_64b; 31a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (needed_size_64b != needed_size) { 32a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bw->error_ = 1; 33a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return 0; 34a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 35a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (needed_size <= bw->max_pos_) return 1; 36a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // If the following line wraps over 32bit, the test just after will catch it. 37a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora new_size = 2 * bw->max_pos_; 38a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (new_size < needed_size) new_size = needed_size; 39a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (new_size < 1024) new_size = 1024; 4033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora new_buf = (uint8_t*)WebPSafeMalloc(1ULL, new_size); 41a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (new_buf == NULL) { 42a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bw->error_ = 1; 43a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return 0; 44a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 458b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora if (bw->pos_ > 0) { 468b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora assert(bw->buf_ != NULL); 478b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora memcpy(new_buf, bw->buf_, bw->pos_); 488b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora } 4933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora WebPSafeFree(bw->buf_); 50a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bw->buf_ = new_buf; 51a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bw->max_pos_ = new_size; 52a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return 1; 53a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 54a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 558c098653157979e397d3954fc2ea0ee43bae6ab2Vikas Arorastatic void Flush(VP8BitWriter* const bw) { 56a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int s = 8 + bw->nb_bits_; 57a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int32_t bits = bw->value_ >> s; 58a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora assert(bw->nb_bits_ >= 0); 59a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bw->value_ -= bits << s; 60a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bw->nb_bits_ -= 8; 61a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if ((bits & 0xff) != 0xff) { 62a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora size_t pos = bw->pos_; 63a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (!BitWriterResize(bw, bw->run_ + 1)) { 64a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return; 65a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 66a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (bits & 0x100) { // overflow -> propagate carry over pending 0xff's 67a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (pos > 0) bw->buf_[pos - 1]++; 68a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 69a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (bw->run_ > 0) { 70a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int value = (bits & 0x100) ? 0x00 : 0xff; 71a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (; bw->run_ > 0; --bw->run_) bw->buf_[pos++] = value; 72a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 73a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bw->buf_[pos++] = bits; 74a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bw->pos_ = pos; 75a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else { 76a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bw->run_++; // delay writing of bytes 0xff, pending eventual carry. 77a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 78a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 79a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 80a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora//------------------------------------------------------------------------------ 81a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// renormalization 82a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 83a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic const uint8_t kNorm[128] = { // renorm_sizes[i] = 8 - log2(i) 84a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 85a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 86a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 87a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 88a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 89a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 90a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 91a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 92a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 0 93a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora}; 94a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 95a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// range = ((range + 1) << kVP8Log2Range[range]) - 1 96a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic const uint8_t kNewRange[128] = { 97a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 127, 127, 191, 127, 159, 191, 223, 127, 143, 159, 175, 191, 207, 223, 239, 98a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 127, 135, 143, 151, 159, 167, 175, 183, 191, 199, 207, 215, 223, 231, 239, 99a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 247, 127, 131, 135, 139, 143, 147, 151, 155, 159, 163, 167, 171, 175, 179, 100a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 183, 187, 191, 195, 199, 203, 207, 211, 215, 219, 223, 227, 231, 235, 239, 101a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 243, 247, 251, 127, 129, 131, 133, 135, 137, 139, 141, 143, 145, 147, 149, 102a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 151, 153, 155, 157, 159, 161, 163, 165, 167, 169, 171, 173, 175, 177, 179, 103a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 181, 183, 185, 187, 189, 191, 193, 195, 197, 199, 201, 203, 205, 207, 209, 104a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 211, 213, 215, 217, 219, 221, 223, 225, 227, 229, 231, 233, 235, 237, 239, 105a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 241, 243, 245, 247, 249, 251, 253, 127 106a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora}; 107a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 108a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Aroraint VP8PutBit(VP8BitWriter* const bw, int bit, int prob) { 109a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int split = (bw->range_ * prob) >> 8; 110a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (bit) { 111a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bw->value_ += split + 1; 112a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bw->range_ -= split + 1; 113a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else { 114a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bw->range_ = split; 115a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 116a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (bw->range_ < 127) { // emit 'shift' bits out and renormalize 117a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int shift = kNorm[bw->range_]; 118a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bw->range_ = kNewRange[bw->range_]; 119a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bw->value_ <<= shift; 120a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bw->nb_bits_ += shift; 1218c098653157979e397d3954fc2ea0ee43bae6ab2Vikas Arora if (bw->nb_bits_ > 0) Flush(bw); 122a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 123a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return bit; 124a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 125a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 126a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Aroraint VP8PutBitUniform(VP8BitWriter* const bw, int bit) { 127a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int split = bw->range_ >> 1; 128a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (bit) { 129a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bw->value_ += split + 1; 130a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bw->range_ -= split + 1; 131a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else { 132a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bw->range_ = split; 133a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 134a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (bw->range_ < 127) { 135a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bw->range_ = kNewRange[bw->range_]; 136a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bw->value_ <<= 1; 137a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bw->nb_bits_ += 1; 1388c098653157979e397d3954fc2ea0ee43bae6ab2Vikas Arora if (bw->nb_bits_ > 0) Flush(bw); 139a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 140a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return bit; 141a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 142a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1437c8da7ce66017295a65ec028084b90800be377f8James Zernvoid VP8PutBits(VP8BitWriter* const bw, uint32_t value, int nb_bits) { 1447c8da7ce66017295a65ec028084b90800be377f8James Zern uint32_t mask; 1457c8da7ce66017295a65ec028084b90800be377f8James Zern assert(nb_bits > 0 && nb_bits < 32); 146fa39824bb690c5806358871f46940d0450973d8aJames Zern for (mask = 1u << (nb_bits - 1); mask; mask >>= 1) { 147a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora VP8PutBitUniform(bw, value & mask); 148fa39824bb690c5806358871f46940d0450973d8aJames Zern } 149a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 150a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1517c8da7ce66017295a65ec028084b90800be377f8James Zernvoid VP8PutSignedBits(VP8BitWriter* const bw, int value, int nb_bits) { 152fa39824bb690c5806358871f46940d0450973d8aJames Zern if (!VP8PutBitUniform(bw, value != 0)) return; 153a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (value < 0) { 1547c8da7ce66017295a65ec028084b90800be377f8James Zern VP8PutBits(bw, ((-value) << 1) | 1, nb_bits + 1); 155a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else { 1567c8da7ce66017295a65ec028084b90800be377f8James Zern VP8PutBits(bw, value << 1, nb_bits + 1); 157a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 158a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 159a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 160a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora//------------------------------------------------------------------------------ 161a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 162a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Aroraint VP8BitWriterInit(VP8BitWriter* const bw, size_t expected_size) { 163a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bw->range_ = 255 - 1; 164a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bw->value_ = 0; 165a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bw->run_ = 0; 166a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bw->nb_bits_ = -8; 167a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bw->pos_ = 0; 168a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bw->max_pos_ = 0; 169a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bw->error_ = 0; 170a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bw->buf_ = NULL; 171a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return (expected_size > 0) ? BitWriterResize(bw, expected_size) : 1; 172a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 173a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 174a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorauint8_t* VP8BitWriterFinish(VP8BitWriter* const bw) { 1757c8da7ce66017295a65ec028084b90800be377f8James Zern VP8PutBits(bw, 0, 9 - bw->nb_bits_); 176a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bw->nb_bits_ = 0; // pad with zeroes 1778c098653157979e397d3954fc2ea0ee43bae6ab2Vikas Arora Flush(bw); 178a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return bw->buf_; 179a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 180a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 181a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Aroraint VP8BitWriterAppend(VP8BitWriter* const bw, 182a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const uint8_t* data, size_t size) { 18333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora assert(data != NULL); 1848c098653157979e397d3954fc2ea0ee43bae6ab2Vikas Arora if (bw->nb_bits_ != -8) return 0; // Flush() must have been called 185a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (!BitWriterResize(bw, size)) return 0; 186a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora memcpy(bw->buf_ + bw->pos_, data, size); 187a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bw->pos_ += size; 188a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return 1; 189a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 190a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 191a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Aroravoid VP8BitWriterWipeOut(VP8BitWriter* const bw) { 19233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora if (bw != NULL) { 19333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora WebPSafeFree(bw->buf_); 194a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora memset(bw, 0, sizeof(*bw)); 195a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 196a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 197a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 198a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora//------------------------------------------------------------------------------ 199a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// VP8LBitWriter 200a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 20133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora// This is the minimum amount of size the memory buffer is guaranteed to grow 20233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora// when extra space is needed. 20333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora#define MIN_EXTRA_SIZE (32768ULL) 20433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 205a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Returns 1 on success. 206a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic int VP8LBitWriterResize(VP8LBitWriter* const bw, size_t extra_size) { 207a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora uint8_t* allocated_buf; 208a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora size_t allocated_size; 20933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const size_t max_bytes = bw->end_ - bw->buf_; 21033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const size_t current_size = bw->cur_ - bw->buf_; 211a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const uint64_t size_required_64b = (uint64_t)current_size + extra_size; 212a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const size_t size_required = (size_t)size_required_64b; 213a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (size_required != size_required_64b) { 214a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bw->error_ = 1; 215a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return 0; 216a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 21733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora if (max_bytes > 0 && size_required <= max_bytes) return 1; 21833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora allocated_size = (3 * max_bytes) >> 1; 219a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (allocated_size < size_required) allocated_size = size_required; 220a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // make allocated size multiple of 1k 221a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora allocated_size = (((allocated_size >> 10) + 1) << 10); 22233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora allocated_buf = (uint8_t*)WebPSafeMalloc(1ULL, allocated_size); 223a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (allocated_buf == NULL) { 224a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bw->error_ = 1; 225a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return 0; 226a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 22733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora if (current_size > 0) { 22833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora memcpy(allocated_buf, bw->buf_, current_size); 22933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora } 23033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora WebPSafeFree(bw->buf_); 231a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora bw->buf_ = allocated_buf; 23233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora bw->cur_ = bw->buf_ + current_size; 23333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora bw->end_ = bw->buf_ + allocated_size; 234a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return 1; 235a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 236a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 237a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Aroraint VP8LBitWriterInit(VP8LBitWriter* const bw, size_t expected_size) { 238a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora memset(bw, 0, sizeof(*bw)); 239a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return VP8LBitWriterResize(bw, expected_size); 240a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 241a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 242a187300ff9a8a7c10b1fb2ec84223fdd14e6d47bJames Zernint VP8LBitWriterClone(const VP8LBitWriter* const src, 243a187300ff9a8a7c10b1fb2ec84223fdd14e6d47bJames Zern VP8LBitWriter* const dst) { 244a187300ff9a8a7c10b1fb2ec84223fdd14e6d47bJames Zern const size_t current_size = src->cur_ - src->buf_; 245a187300ff9a8a7c10b1fb2ec84223fdd14e6d47bJames Zern assert(src->cur_ >= src->buf_ && src->cur_ <= src->end_); 246a187300ff9a8a7c10b1fb2ec84223fdd14e6d47bJames Zern if (!VP8LBitWriterResize(dst, current_size)) return 0; 247a187300ff9a8a7c10b1fb2ec84223fdd14e6d47bJames Zern memcpy(dst->buf_, src->buf_, current_size); 248a187300ff9a8a7c10b1fb2ec84223fdd14e6d47bJames Zern dst->bits_ = src->bits_; 249a187300ff9a8a7c10b1fb2ec84223fdd14e6d47bJames Zern dst->used_ = src->used_; 250a187300ff9a8a7c10b1fb2ec84223fdd14e6d47bJames Zern dst->error_ = src->error_; 251a187300ff9a8a7c10b1fb2ec84223fdd14e6d47bJames Zern return 1; 252a187300ff9a8a7c10b1fb2ec84223fdd14e6d47bJames Zern} 253a187300ff9a8a7c10b1fb2ec84223fdd14e6d47bJames Zern 2547c8da7ce66017295a65ec028084b90800be377f8James Zernvoid VP8LBitWriterWipeOut(VP8LBitWriter* const bw) { 255a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (bw != NULL) { 25633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora WebPSafeFree(bw->buf_); 257a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora memset(bw, 0, sizeof(*bw)); 258a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 259a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 260a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 261a187300ff9a8a7c10b1fb2ec84223fdd14e6d47bJames Zernvoid VP8LBitWriterReset(const VP8LBitWriter* const bw_init, 262a187300ff9a8a7c10b1fb2ec84223fdd14e6d47bJames Zern VP8LBitWriter* const bw) { 263a187300ff9a8a7c10b1fb2ec84223fdd14e6d47bJames Zern bw->bits_ = bw_init->bits_; 264a187300ff9a8a7c10b1fb2ec84223fdd14e6d47bJames Zern bw->used_ = bw_init->used_; 265a187300ff9a8a7c10b1fb2ec84223fdd14e6d47bJames Zern bw->cur_ = bw->buf_ + (bw_init->cur_ - bw_init->buf_); 266a187300ff9a8a7c10b1fb2ec84223fdd14e6d47bJames Zern assert(bw->cur_ <= bw->end_); 267a187300ff9a8a7c10b1fb2ec84223fdd14e6d47bJames Zern bw->error_ = bw_init->error_; 268a187300ff9a8a7c10b1fb2ec84223fdd14e6d47bJames Zern} 269a187300ff9a8a7c10b1fb2ec84223fdd14e6d47bJames Zern 270a187300ff9a8a7c10b1fb2ec84223fdd14e6d47bJames Zernvoid VP8LBitWriterSwap(VP8LBitWriter* const src, VP8LBitWriter* const dst) { 271a187300ff9a8a7c10b1fb2ec84223fdd14e6d47bJames Zern const VP8LBitWriter tmp = *src; 272a187300ff9a8a7c10b1fb2ec84223fdd14e6d47bJames Zern *src = *dst; 273a187300ff9a8a7c10b1fb2ec84223fdd14e6d47bJames Zern *dst = tmp; 274a187300ff9a8a7c10b1fb2ec84223fdd14e6d47bJames Zern} 275a187300ff9a8a7c10b1fb2ec84223fdd14e6d47bJames Zern 2767c8da7ce66017295a65ec028084b90800be377f8James Zernvoid VP8LPutBitsFlushBits(VP8LBitWriter* const bw) { 2777c8da7ce66017295a65ec028084b90800be377f8James Zern // If needed, make some room by flushing some bits out. 2787c8da7ce66017295a65ec028084b90800be377f8James Zern if (bw->cur_ + VP8L_WRITER_BYTES > bw->end_) { 2797c8da7ce66017295a65ec028084b90800be377f8James Zern const uint64_t extra_size = (bw->end_ - bw->buf_) + MIN_EXTRA_SIZE; 2807c8da7ce66017295a65ec028084b90800be377f8James Zern if (extra_size != (size_t)extra_size || 2817c8da7ce66017295a65ec028084b90800be377f8James Zern !VP8LBitWriterResize(bw, (size_t)extra_size)) { 2827c8da7ce66017295a65ec028084b90800be377f8James Zern bw->cur_ = bw->buf_; 2837c8da7ce66017295a65ec028084b90800be377f8James Zern bw->error_ = 1; 2847c8da7ce66017295a65ec028084b90800be377f8James Zern return; 2857c8da7ce66017295a65ec028084b90800be377f8James Zern } 2867c8da7ce66017295a65ec028084b90800be377f8James Zern } 2877c8da7ce66017295a65ec028084b90800be377f8James Zern *(vp8l_wtype_t*)bw->cur_ = (vp8l_wtype_t)WSWAP((vp8l_wtype_t)bw->bits_); 2887c8da7ce66017295a65ec028084b90800be377f8James Zern bw->cur_ += VP8L_WRITER_BYTES; 2897c8da7ce66017295a65ec028084b90800be377f8James Zern bw->bits_ >>= VP8L_WRITER_BITS; 2907c8da7ce66017295a65ec028084b90800be377f8James Zern bw->used_ -= VP8L_WRITER_BITS; 2917c8da7ce66017295a65ec028084b90800be377f8James Zern} 2927c8da7ce66017295a65ec028084b90800be377f8James Zern 2937c8da7ce66017295a65ec028084b90800be377f8James Zernvoid VP8LPutBitsInternal(VP8LBitWriter* const bw, uint32_t bits, int n_bits) { 29433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora assert(n_bits <= 32); 29533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora // That's the max we can handle: 2967c8da7ce66017295a65ec028084b90800be377f8James Zern assert(sizeof(vp8l_wtype_t) == 2); 29733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora if (n_bits > 0) { 29833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora vp8l_atype_t lbits = bw->bits_; 29933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora int used = bw->used_; 30033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora // Special case of overflow handling for 32bit accumulator (2-steps flush). 3017c8da7ce66017295a65ec028084b90800be377f8James Zern#if VP8L_WRITER_BITS == 16 3027c8da7ce66017295a65ec028084b90800be377f8James Zern if (used + n_bits >= VP8L_WRITER_MAX_BITS) { 3037c8da7ce66017295a65ec028084b90800be377f8James Zern // Fill up all the VP8L_WRITER_MAX_BITS so it can be flushed out below. 3047c8da7ce66017295a65ec028084b90800be377f8James Zern const int shift = VP8L_WRITER_MAX_BITS - used; 3057c8da7ce66017295a65ec028084b90800be377f8James Zern lbits |= (vp8l_atype_t)bits << used; 3067c8da7ce66017295a65ec028084b90800be377f8James Zern used = VP8L_WRITER_MAX_BITS; 3077c8da7ce66017295a65ec028084b90800be377f8James Zern n_bits -= shift; 3087c8da7ce66017295a65ec028084b90800be377f8James Zern bits >>= shift; 3097c8da7ce66017295a65ec028084b90800be377f8James Zern assert(n_bits <= VP8L_WRITER_MAX_BITS); 310a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 3117c8da7ce66017295a65ec028084b90800be377f8James Zern#endif 31233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora // If needed, make some room by flushing some bits out. 31333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora while (used >= VP8L_WRITER_BITS) { 31433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora if (bw->cur_ + VP8L_WRITER_BYTES > bw->end_) { 31533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora const uint64_t extra_size = (bw->end_ - bw->buf_) + MIN_EXTRA_SIZE; 31633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora if (extra_size != (size_t)extra_size || 31733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora !VP8LBitWriterResize(bw, (size_t)extra_size)) { 31833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora bw->cur_ = bw->buf_; 31933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora bw->error_ = 1; 32033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora return; 32133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora } 32233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora } 32333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora *(vp8l_wtype_t*)bw->cur_ = (vp8l_wtype_t)WSWAP((vp8l_wtype_t)lbits); 32433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora bw->cur_ += VP8L_WRITER_BYTES; 32533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora lbits >>= VP8L_WRITER_BITS; 32633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora used -= VP8L_WRITER_BITS; 32733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora } 32833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora bw->bits_ = lbits | ((vp8l_atype_t)bits << used); 32933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora bw->used_ = used + n_bits; 330a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 33133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora} 33233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 33333f74dabbc7920a65ed435d7417987589febdc16Vikas Arorauint8_t* VP8LBitWriterFinish(VP8LBitWriter* const bw) { 33433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora // flush leftover bits 33533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora if (VP8LBitWriterResize(bw, (bw->used_ + 7) >> 3)) { 33633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora while (bw->used_ > 0) { 33733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora *bw->cur_++ = (uint8_t)bw->bits_; 33833f74dabbc7920a65ed435d7417987589febdc16Vikas Arora bw->bits_ >>= 8; 33933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora bw->used_ -= 8; 340a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 34133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora bw->used_ = 0; 342a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 34333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora return bw->buf_; 344a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 345a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 346a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora//------------------------------------------------------------------------------ 347