1/* 2 * Range coder 3 * Copyright (c) 2004 Michael Niedermayer <michaelni@gmx.at> 4 * 5 * This file is part of FFmpeg. 6 * 7 * FFmpeg is free software; you can redistribute it and/or 8 * modify it under the terms of the GNU Lesser General Public 9 * License as published by the Free Software Foundation; either 10 * version 2.1 of the License, or (at your option) any later version. 11 * 12 * FFmpeg is distributed in the hope that it will be useful, 13 * but WITHOUT ANY WARRANTY; without even the implied warranty of 14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15 * Lesser General Public License for more details. 16 * 17 * You should have received a copy of the GNU Lesser General Public 18 * License along with FFmpeg; if not, write to the Free Software 19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 20 */ 21 22/** 23 * @file 24 * Range coder. 25 */ 26 27#ifndef AVCODEC_RANGECODER_H 28#define AVCODEC_RANGECODER_H 29 30#include <stdint.h> 31 32#include "libavutil/common.h" 33#include "libavutil/avassert.h" 34 35typedef struct RangeCoder { 36 int low; 37 int range; 38 int outstanding_count; 39 int outstanding_byte; 40 uint8_t zero_state[256]; 41 uint8_t one_state[256]; 42 uint8_t *bytestream_start; 43 uint8_t *bytestream; 44 uint8_t *bytestream_end; 45} RangeCoder; 46 47void ff_init_range_encoder(RangeCoder *c, uint8_t *buf, int buf_size); 48void ff_init_range_decoder(RangeCoder *c, const uint8_t *buf, int buf_size); 49int ff_rac_terminate(RangeCoder *c); 50void ff_build_rac_states(RangeCoder *c, int factor, int max_p); 51 52static inline void renorm_encoder(RangeCoder *c) 53{ 54 // FIXME: optimize 55 while (c->range < 0x100) { 56 if (c->outstanding_byte < 0) { 57 c->outstanding_byte = c->low >> 8; 58 } else if (c->low <= 0xFF00) { 59 *c->bytestream++ = c->outstanding_byte; 60 for (; c->outstanding_count; c->outstanding_count--) 61 *c->bytestream++ = 0xFF; 62 c->outstanding_byte = c->low >> 8; 63 } else if (c->low >= 0x10000) { 64 *c->bytestream++ = c->outstanding_byte + 1; 65 for (; c->outstanding_count; c->outstanding_count--) 66 *c->bytestream++ = 0x00; 67 c->outstanding_byte = (c->low >> 8) & 0xFF; 68 } else { 69 c->outstanding_count++; 70 } 71 72 c->low = (c->low & 0xFF) << 8; 73 c->range <<= 8; 74 } 75} 76 77static inline int get_rac_count(RangeCoder *c) 78{ 79 int x = c->bytestream - c->bytestream_start + c->outstanding_count; 80 if (c->outstanding_byte >= 0) 81 x++; 82 return 8 * x - av_log2(c->range); 83} 84 85static inline void put_rac(RangeCoder *c, uint8_t *const state, int bit) 86{ 87 int range1 = (c->range * (*state)) >> 8; 88 89 av_assert2(*state); 90 av_assert2(range1 < c->range); 91 av_assert2(range1 > 0); 92 if (!bit) { 93 c->range -= range1; 94 *state = c->zero_state[*state]; 95 } else { 96 c->low += c->range - range1; 97 c->range = range1; 98 *state = c->one_state[*state]; 99 } 100 101 renorm_encoder(c); 102} 103 104static inline void refill(RangeCoder *c) 105{ 106 if (c->range < 0x100) { 107 c->range <<= 8; 108 c->low <<= 8; 109 if (c->bytestream < c->bytestream_end) 110 c->low += c->bytestream[0]; 111 c->bytestream++; 112 } 113} 114 115static inline int get_rac(RangeCoder *c, uint8_t *const state) 116{ 117 int range1 = (c->range * (*state)) >> 8; 118 int av_unused one_mask; 119 120 c->range -= range1; 121#if 1 122 if (c->low < c->range) { 123 *state = c->zero_state[*state]; 124 refill(c); 125 return 0; 126 } else { 127 c->low -= c->range; 128 *state = c->one_state[*state]; 129 c->range = range1; 130 refill(c); 131 return 1; 132 } 133#else 134 one_mask = (c->range - c->low - 1) >> 31; 135 136 c->low -= c->range & one_mask; 137 c->range += (range1 - c->range) & one_mask; 138 139 *state = c->zero_state[(*state) + (256 & one_mask)]; 140 141 refill(c); 142 143 return one_mask & 1; 144#endif 145} 146 147#endif /* AVCODEC_RANGECODER_H */ 148