OLD | NEW |
1 // Copyright 2010 Google Inc. | 1 // Copyright 2010 Google Inc. All Rights Reserved. |
2 // | 2 // |
3 // This code is licensed under the same terms as WebM: | 3 // This code is licensed under the same terms as WebM: |
4 // Software License Agreement: http://www.webmproject.org/license/software/ | 4 // Software License Agreement: http://www.webmproject.org/license/software/ |
5 // Additional IP Rights Grant: http://www.webmproject.org/license/additional/ | 5 // Additional IP Rights Grant: http://www.webmproject.org/license/additional/ |
6 // ----------------------------------------------------------------------------- | 6 // ----------------------------------------------------------------------------- |
7 // | 7 // |
8 // Boolean decoder | 8 // Boolean decoder |
9 // | 9 // |
10 // Author: Skal (pascal.massimino@gmail.com) | 10 // Author: Skal (pascal.massimino@gmail.com) |
| 11 // Vikas Arora (vikaas.arora@gmail.com) |
11 | 12 |
12 #ifndef WEBP_UTILS_BIT_READER_H_ | 13 #ifndef WEBP_UTILS_BIT_READER_H_ |
13 #define WEBP_UTILS_BIT_READER_H_ | 14 #define WEBP_UTILS_BIT_READER_H_ |
14 | 15 |
15 #include <assert.h> | 16 #include <assert.h> |
16 #include "../webp/decode_vp8.h" | 17 #ifdef _MSC_VER |
| 18 #include <stdlib.h> // _byteswap_ulong |
| 19 #endif |
| 20 #include <string.h> // For memcpy |
| 21 #include "../webp/types.h" |
17 | 22 |
18 #if defined(__cplusplus) || defined(c_plusplus) | 23 #if defined(__cplusplus) || defined(c_plusplus) |
19 extern "C" { | 24 extern "C" { |
20 #endif | 25 #endif |
21 | 26 |
| 27 #define BITS 32 // can be 32, 16 or 8 |
| 28 #define MASK ((((bit_t)1) << (BITS)) - 1) |
| 29 #if (BITS == 32) |
| 30 typedef uint64_t bit_t; // natural register type |
| 31 typedef uint32_t lbit_t; // natural type for memory I/O |
| 32 #elif (BITS == 16) |
| 33 typedef uint32_t bit_t; |
| 34 typedef uint16_t lbit_t; |
| 35 #else |
| 36 typedef uint32_t bit_t; |
| 37 typedef uint8_t lbit_t; |
| 38 #endif |
| 39 |
22 //------------------------------------------------------------------------------ | 40 //------------------------------------------------------------------------------ |
23 // Bitreader and code-tree reader | 41 // Bitreader and code-tree reader |
24 | 42 |
25 typedef struct VP8BitReader VP8BitReader; | 43 typedef struct VP8BitReader VP8BitReader; |
26 struct VP8BitReader { | 44 struct VP8BitReader { |
27 const uint8_t* buf_; // next byte to be read | 45 const uint8_t* buf_; // next byte to be read |
28 const uint8_t* buf_end_; // end of read buffer | 46 const uint8_t* buf_end_; // end of read buffer |
29 int eof_; // true if input is exhausted | 47 int eof_; // true if input is exhausted |
30 | 48 |
31 // boolean decoder | 49 // boolean decoder |
32 uint32_t range_; // current range minus 1. In [127, 254] interval. | 50 bit_t range_; // current range minus 1. In [127, 254] interval. |
33 uint32_t value_; // current value | 51 bit_t value_; // current value |
34 int missing_; // number of missing bits in value_ (8bit) | 52 int missing_; // number of missing bits in value_ (8bit) |
35 }; | 53 }; |
36 | 54 |
37 // Initialize the bit reader and the boolean decoder. | 55 // Initialize the bit reader and the boolean decoder. |
38 void VP8InitBitReader(VP8BitReader* const br, | 56 void VP8InitBitReader(VP8BitReader* const br, |
39 const uint8_t* const start, const uint8_t* const end); | 57 const uint8_t* const start, const uint8_t* const end); |
40 | 58 |
41 // return the next value made of 'num_bits' bits | 59 // return the next value made of 'num_bits' bits |
42 uint32_t VP8GetValue(VP8BitReader* const br, int num_bits); | 60 uint32_t VP8GetValue(VP8BitReader* const br, int num_bits); |
43 static inline uint32_t VP8Get(VP8BitReader* const br) { | 61 static WEBP_INLINE uint32_t VP8Get(VP8BitReader* const br) { |
44 return VP8GetValue(br, 1); | 62 return VP8GetValue(br, 1); |
45 } | 63 } |
46 | 64 |
47 // return the next value with sign-extension. | 65 // return the next value with sign-extension. |
48 int32_t VP8GetSignedValue(VP8BitReader* const br, int num_bits); | 66 int32_t VP8GetSignedValue(VP8BitReader* const br, int num_bits); |
49 | 67 |
50 // Read a bit with proba 'prob'. Speed-critical function! | 68 // Read a bit with proba 'prob'. Speed-critical function! |
51 extern const uint8_t kVP8Log2Range[128]; | 69 extern const uint8_t kVP8Log2Range[128]; |
52 extern const uint8_t kVP8NewRange[128]; | 70 extern const bit_t kVP8NewRange[128]; |
53 static inline uint32_t VP8GetByte(VP8BitReader* const br) { | 71 |
54 assert(br); | 72 void VP8LoadFinalBytes(VP8BitReader* const br); // special case for the tail |
55 if (br->buf_ < br->buf_end_) { | 73 |
56 assert(br->buf_); | 74 static WEBP_INLINE void VP8LoadNewBytes(VP8BitReader* const br) { |
57 return *br->buf_++; | 75 assert(br && br->buf_); |
| 76 // Read 'BITS' bits at a time if possible. |
| 77 if (br->buf_ + sizeof(lbit_t) <= br->buf_end_) { |
| 78 // convert memory type to register type (with some zero'ing!) |
| 79 bit_t bits; |
| 80 lbit_t in_bits = *(lbit_t*)br->buf_; |
| 81 br->buf_ += (BITS) >> 3; |
| 82 #if !defined(__BIG_ENDIAN__) |
| 83 #if (BITS == 32) |
| 84 #if defined(__i386__) || defined(__x86_64__) |
| 85 __asm__ volatile("bswap %k0" : "=r"(in_bits) : "0"(in_bits)); |
| 86 bits = (bit_t)in_bits; // 32b -> 64b zero-extension |
| 87 #elif defined(_MSC_VER) |
| 88 bits = _byteswap_ulong(in_bits); |
| 89 #else |
| 90 bits = (bit_t)(in_bits >> 24) | ((in_bits >> 8) & 0xff00) |
| 91 | ((in_bits << 8) & 0xff0000) | (in_bits << 24); |
| 92 #endif // x86 |
| 93 #elif (BITS == 16) |
| 94 // gcc will recognize a 'rorw $8, ...' here: |
| 95 bits = (bit_t)(in_bits >> 8) | ((in_bits & 0xff) << 8); |
| 96 #endif |
| 97 #else // LITTLE_ENDIAN |
| 98 bits = (bit_t)in_bits; |
| 99 #endif |
| 100 br->value_ |= bits << br->missing_; |
| 101 br->missing_ -= (BITS); |
| 102 } else { |
| 103 VP8LoadFinalBytes(br); // no need to be inlined |
58 } | 104 } |
59 br->eof_ = 1; | |
60 return 0xff; | |
61 } | 105 } |
62 | 106 |
63 static inline uint32_t VP8BitUpdate(VP8BitReader* const br, uint32_t split) { | 107 static WEBP_INLINE int VP8BitUpdate(VP8BitReader* const br, bit_t split) { |
64 uint32_t bit; | 108 const bit_t value_split = split | (MASK); |
65 const uint32_t value_split = (split + 1) << 8; | 109 if (br->missing_ > 0) { // Make sure we have a least BITS bits in 'value_' |
66 // Make sure we have a least 8 bits in 'value_' | 110 VP8LoadNewBytes(br); |
67 if (br->missing_ > 0) { | |
68 br->value_ |= VP8GetByte(br) << br->missing_; | |
69 br->missing_ -= 8; | |
70 } | 111 } |
71 bit = (br->value_ >= value_split); | 112 if (br->value_ > value_split) { |
72 if (bit) { | 113 br->range_ -= value_split + 1; |
73 br->range_ -= split + 1; | 114 br->value_ -= value_split + 1; |
74 br->value_ -= value_split; | 115 return 1; |
75 } else { | 116 } else { |
76 br->range_ = split; | 117 br->range_ = value_split; |
| 118 return 0; |
77 } | 119 } |
78 return bit; | |
79 } | 120 } |
80 | 121 |
81 static inline void VP8Shift(VP8BitReader* const br) { | 122 static WEBP_INLINE void VP8Shift(VP8BitReader* const br) { |
82 // range_ is in [0..127] interval here. | 123 // range_ is in [0..127] interval here. |
83 const int shift = kVP8Log2Range[br->range_]; | 124 const int idx = br->range_ >> (BITS); |
84 br->range_ = kVP8NewRange[br->range_]; | 125 const int shift = kVP8Log2Range[idx]; |
| 126 br->range_ = kVP8NewRange[idx]; |
85 br->value_ <<= shift; | 127 br->value_ <<= shift; |
86 br->missing_ += shift; | 128 br->missing_ += shift; |
87 } | 129 } |
88 | 130 |
89 static inline uint32_t VP8GetBit(VP8BitReader* const br, int prob) { | 131 static WEBP_INLINE int VP8GetBit(VP8BitReader* const br, int prob) { |
90 const uint32_t split = (br->range_ * prob) >> 8; | 132 // It's important to avoid generating a 64bit x 64bit multiply here. |
91 const uint32_t bit = VP8BitUpdate(br, split); | 133 // We just need an 8b x 8b after all. |
92 if (br->range_ < 0x7f) { | 134 const bit_t split = |
| 135 (bit_t)((uint32_t)(br->range_ >> (BITS)) * prob) << ((BITS) - 8); |
| 136 const int bit = VP8BitUpdate(br, split); |
| 137 if (br->range_ <= (((bit_t)0x7e << (BITS)) | (MASK))) { |
93 VP8Shift(br); | 138 VP8Shift(br); |
94 } | 139 } |
95 return bit; | 140 return bit; |
96 } | 141 } |
97 | 142 |
98 static inline int VP8GetSigned(VP8BitReader* const br, int v) { | 143 static WEBP_INLINE int VP8GetSigned(VP8BitReader* const br, int v) { |
99 const uint32_t split = br->range_ >> 1; | 144 const bit_t split = (br->range_ >> 1); |
100 const uint32_t bit = VP8BitUpdate(br, split); | 145 const int bit = VP8BitUpdate(br, split); |
101 VP8Shift(br); | 146 VP8Shift(br); |
102 return bit ? -v : v; | 147 return bit ? -v : v; |
103 } | 148 } |
104 | 149 |
| 150 |
| 151 // ----------------------------------------------------------------------------- |
| 152 // Bitreader |
| 153 |
| 154 typedef struct { |
| 155 uint64_t val_; |
| 156 const uint8_t* buf_; |
| 157 size_t len_; |
| 158 size_t pos_; |
| 159 int bit_pos_; |
| 160 int eos_; |
| 161 int error_; |
| 162 } VP8LBitReader; |
| 163 |
| 164 void VP8LInitBitReader(VP8LBitReader* const br, |
| 165 const uint8_t* const start, |
| 166 size_t length); |
| 167 |
| 168 // Sets a new data buffer. |
| 169 void VP8LBitReaderSetBuffer(VP8LBitReader* const br, |
| 170 const uint8_t* const buffer, size_t length); |
| 171 |
| 172 // Reads the specified number of bits from Read Buffer. |
| 173 // Flags an error in case end_of_stream or n_bits is more than allowed limit. |
| 174 // Flags eos if this read attempt is going to cross the read buffer. |
| 175 uint32_t VP8LReadBits(VP8LBitReader* const br, int n_bits); |
| 176 |
| 177 // Reads one bit from Read Buffer. Flags an error in case end_of_stream. |
| 178 // Flags eos after reading last bit from the buffer. |
| 179 uint32_t VP8LReadOneBit(VP8LBitReader* const br); |
| 180 |
| 181 // VP8LReadOneBitUnsafe is faster than VP8LReadOneBit, but it can be called only |
| 182 // 32 times after the last VP8LFillBitWindow. Any subsequent calls |
| 183 // (without VP8LFillBitWindow) will return invalid data. |
| 184 static WEBP_INLINE uint32_t VP8LReadOneBitUnsafe(VP8LBitReader* const br) { |
| 185 const uint32_t val = (br->val_ >> br->bit_pos_) & 1; |
| 186 ++br->bit_pos_; |
| 187 return val; |
| 188 } |
| 189 |
| 190 // Advances the Read buffer by 4 bytes to make room for reading next 32 bits. |
| 191 void VP8LFillBitWindow(VP8LBitReader* const br); |
| 192 |
105 #if defined(__cplusplus) || defined(c_plusplus) | 193 #if defined(__cplusplus) || defined(c_plusplus) |
106 } // extern "C" | 194 } // extern "C" |
107 #endif | 195 #endif |
108 | 196 |
109 #endif /* WEBP_UTILS_BIT_READER_H_ */ | 197 #endif /* WEBP_UTILS_BIT_READER_H_ */ |
OLD | NEW |