190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber/* 2f71323e297a928af368937089d3ed71239786f86Andreas Huber * Copyright (c) 2010 The WebM project authors. All Rights Reserved. 390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber * 4f71323e297a928af368937089d3ed71239786f86Andreas Huber * Use of this source code is governed by a BSD-style license 5f71323e297a928af368937089d3ed71239786f86Andreas Huber * that can be found in the LICENSE file in the root of the source 6f71323e297a928af368937089d3ed71239786f86Andreas Huber * tree. An additional intellectual property rights grant can be found 7f71323e297a928af368937089d3ed71239786f86Andreas Huber * in the file PATENTS. All contributing project authors may 8f71323e297a928af368937089d3ed71239786f86Andreas Huber * be found in the AUTHORS file in the root of the source tree. 990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber */ 1090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 1190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 12ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang#ifndef DBOOLHUFF_H_ 13ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang#define DBOOLHUFF_H_ 14ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 15f71323e297a928af368937089d3ed71239786f86Andreas Huber#include <stddef.h> 16f71323e297a928af368937089d3ed71239786f86Andreas Huber#include <limits.h> 17ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 181b362b15af34006e6a11974088a46d42b903418eJohann#include "vpx_config.h" 1990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#include "vpx_ports/mem.h" 20f71323e297a928af368937089d3ed71239786f86Andreas Huber#include "vpx/vpx_integer.h" 21f71323e297a928af368937089d3ed71239786f86Andreas Huber 22f71323e297a928af368937089d3ed71239786f86Andreas Hubertypedef size_t VP8_BD_VALUE; 23f71323e297a928af368937089d3ed71239786f86Andreas Huber 24ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang#define VP8_BD_VALUE_SIZE ((int)sizeof(VP8_BD_VALUE)*CHAR_BIT) 25ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 26f71323e297a928af368937089d3ed71239786f86Andreas Huber/*This is meant to be a large, positive constant that can still be efficiently 27f71323e297a928af368937089d3ed71239786f86Andreas Huber loaded as an immediate (on platforms like ARM, for example). 28f71323e297a928af368937089d3ed71239786f86Andreas Huber Even relatively modest values like 100 would work fine.*/ 29ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang#define VP8_LOTS_OF_BITS (0x40000000) 30ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 31ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang/*Decrypt n bytes of data from input -> output, using the decrypt_state 32ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang passed in VP8D_SET_DECRYPTOR. 33ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang*/ 34ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuangtypedef void (vp8_decrypt_cb)(void *decrypt_state, const unsigned char *input, 35ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang unsigned char *output, int count); 36f71323e297a928af368937089d3ed71239786f86Andreas Huber 3790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Hubertypedef struct 3890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber{ 39f71323e297a928af368937089d3ed71239786f86Andreas Huber const unsigned char *user_buffer_end; 4090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber const unsigned char *user_buffer; 41f71323e297a928af368937089d3ed71239786f86Andreas Huber VP8_BD_VALUE value; 42f71323e297a928af368937089d3ed71239786f86Andreas Huber int count; 43f71323e297a928af368937089d3ed71239786f86Andreas Huber unsigned int range; 44ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang vp8_decrypt_cb *decrypt_cb; 45ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang void *decrypt_state; 4690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber} BOOL_DECODER; 4790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 481b362b15af34006e6a11974088a46d42b903418eJohannDECLARE_ALIGNED(16, extern const unsigned char, vp8_norm[256]); 4990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 5079f15823c34ae1e423108295e416213200bb280fAndreas Huberint vp8dx_start_decode(BOOL_DECODER *br, 5179f15823c34ae1e423108295e416213200bb280fAndreas Huber const unsigned char *source, 52ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang unsigned int source_sz, 53ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang vp8_decrypt_cb *decrypt_cb, 54ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang void *decrypt_state); 5579f15823c34ae1e423108295e416213200bb280fAndreas Huber 5679f15823c34ae1e423108295e416213200bb280fAndreas Hubervoid vp8dx_bool_decoder_fill(BOOL_DECODER *br); 57f71323e297a928af368937089d3ed71239786f86Andreas Huber 58f71323e297a928af368937089d3ed71239786f86Andreas Huber 5990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huberstatic int vp8dx_decode_bool(BOOL_DECODER *br, int probability) { 6090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber unsigned int bit = 0; 61f71323e297a928af368937089d3ed71239786f86Andreas Huber VP8_BD_VALUE value; 6290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber unsigned int split; 63f71323e297a928af368937089d3ed71239786f86Andreas Huber VP8_BD_VALUE bigsplit; 64f71323e297a928af368937089d3ed71239786f86Andreas Huber int count; 65f71323e297a928af368937089d3ed71239786f86Andreas Huber unsigned int range; 66f71323e297a928af368937089d3ed71239786f86Andreas Huber 671b362b15af34006e6a11974088a46d42b903418eJohann split = 1 + (((br->range - 1) * probability) >> 8); 681b362b15af34006e6a11974088a46d42b903418eJohann 691b362b15af34006e6a11974088a46d42b903418eJohann if(br->count < 0) 701b362b15af34006e6a11974088a46d42b903418eJohann vp8dx_bool_decoder_fill(br); 711b362b15af34006e6a11974088a46d42b903418eJohann 72f71323e297a928af368937089d3ed71239786f86Andreas Huber value = br->value; 73f71323e297a928af368937089d3ed71239786f86Andreas Huber count = br->count; 7490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 75f71323e297a928af368937089d3ed71239786f86Andreas Huber bigsplit = (VP8_BD_VALUE)split << (VP8_BD_VALUE_SIZE - 8); 7690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 7790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber range = split; 7890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 7990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (value >= bigsplit) 8090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 8190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber range = br->range - split; 8290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber value = value - bigsplit; 8390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber bit = 1; 8490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 8590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 8690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 871b362b15af34006e6a11974088a46d42b903418eJohann register unsigned int shift = vp8_norm[range]; 8890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber range <<= shift; 8990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber value <<= shift; 9090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber count -= shift; 9190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 9290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber br->value = value; 93f71323e297a928af368937089d3ed71239786f86Andreas Huber br->count = count; 9490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber br->range = range; 951b362b15af34006e6a11974088a46d42b903418eJohann 9690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber return bit; 9790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber} 9890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 9990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huberstatic int vp8_decode_value(BOOL_DECODER *br, int bits) 10090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber{ 10190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber int z = 0; 10290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber int bit; 10390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 10490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber for (bit = bits - 1; bit >= 0; bit--) 10590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 10690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber z |= (vp8dx_decode_bool(br, 0x80) << bit); 10790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 10890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 10990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber return z; 11090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber} 11179f15823c34ae1e423108295e416213200bb280fAndreas Huber 11279f15823c34ae1e423108295e416213200bb280fAndreas Huberstatic int vp8dx_bool_error(BOOL_DECODER *br) 11379f15823c34ae1e423108295e416213200bb280fAndreas Huber{ 1141b362b15af34006e6a11974088a46d42b903418eJohann /* Check if we have reached the end of the buffer. 1151b362b15af34006e6a11974088a46d42b903418eJohann * 1161b362b15af34006e6a11974088a46d42b903418eJohann * Variable 'count' stores the number of bits in the 'value' buffer, minus 1171b362b15af34006e6a11974088a46d42b903418eJohann * 8. The top byte is part of the algorithm, and the remainder is buffered 1181b362b15af34006e6a11974088a46d42b903418eJohann * to be shifted into it. So if count == 8, the top 16 bits of 'value' are 1191b362b15af34006e6a11974088a46d42b903418eJohann * occupied, 8 for the algorithm and 8 in the buffer. 1201b362b15af34006e6a11974088a46d42b903418eJohann * 1211b362b15af34006e6a11974088a46d42b903418eJohann * When reading a byte from the user's buffer, count is filled with 8 and 1221b362b15af34006e6a11974088a46d42b903418eJohann * one byte is filled into the value buffer. When we reach the end of the 1231b362b15af34006e6a11974088a46d42b903418eJohann * data, count is additionally filled with VP8_LOTS_OF_BITS. So when 1241b362b15af34006e6a11974088a46d42b903418eJohann * count == VP8_LOTS_OF_BITS - 1, the user's data has been exhausted. 1251b362b15af34006e6a11974088a46d42b903418eJohann */ 1261b362b15af34006e6a11974088a46d42b903418eJohann if ((br->count > VP8_BD_VALUE_SIZE) && (br->count < VP8_LOTS_OF_BITS)) 12779f15823c34ae1e423108295e416213200bb280fAndreas Huber { 12879f15823c34ae1e423108295e416213200bb280fAndreas Huber /* We have tried to decode bits after the end of 12979f15823c34ae1e423108295e416213200bb280fAndreas Huber * stream was encountered. 13079f15823c34ae1e423108295e416213200bb280fAndreas Huber */ 13179f15823c34ae1e423108295e416213200bb280fAndreas Huber return 1; 13279f15823c34ae1e423108295e416213200bb280fAndreas Huber } 13379f15823c34ae1e423108295e416213200bb280fAndreas Huber 13479f15823c34ae1e423108295e416213200bb280fAndreas Huber /* No error. */ 13579f15823c34ae1e423108295e416213200bb280fAndreas Huber return 0; 13679f15823c34ae1e423108295e416213200bb280fAndreas Huber} 137ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 138ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang#endif // DBOOLHUFF_H_ 139