← Back to branch summary

~paparazzi-uav/paparazzi/v5.0-manual

« back to all changes in this revision

Viewing changes to sw/ext/opencv_bebop/opencv/3rdparty/libwebp/utils/bit_reader.h

  • Committer: Paparazzi buildbot
  • Date: 2016-05-18 15:00:29 UTC
  • Revision ID: felix.ruess+docbot@gmail.com-20160518150029-e8lgzi5kvb4p7un9
Manual import commit 4b8bbb730080dac23cf816b98908dacfabe2a8ec from v5.0 branch.

Show diffs side-by-side

added added

removed removed

Lines of Context:
sw/ext/opencv_bebop/opencv/3rdparty/libwebp/utils/bit_reader.h
 
1
// Copyright 2010 Google Inc. All Rights Reserved.
 
2
//
 
3
// Use of this source code is governed by a BSD-style license
 
4
// that can be found in the COPYING file in the root of the source
 
5
// tree. An additional intellectual property rights grant can be found
 
6
// in the file PATENTS. All contributing project authors may
 
7
// be found in the AUTHORS file in the root of the source tree.
 
8
// -----------------------------------------------------------------------------
 
9
//
 
10
// Boolean decoder
 
11
//
 
12
// Author: Skal (pascal.massimino@gmail.com)
 
13
//         Vikas Arora (vikaas.arora@gmail.com)
 
14
 
 
15
#ifndef WEBP_UTILS_BIT_READER_H_
 
16
#define WEBP_UTILS_BIT_READER_H_
 
17
 
 
18
#include <assert.h>
 
19
#ifdef _MSC_VER
 
20
#include <stdlib.h>  // _byteswap_ulong
 
21
#endif
 
22
#include <string.h>  // For memcpy
 
23
#include "../webp/types.h"
 
24
 
 
25
#if defined(__cplusplus) || defined(c_plusplus)
 
26
extern "C" {
 
27
#endif
 
28
 
 
29
// The Boolean decoder needs to maintain infinite precision on the value_ field.
 
30
// However, since range_ is only 8bit, we only need an active window of 8 bits
 
31
// for value_. Left bits (MSB) gets zeroed and shifted away when value_ falls
 
32
// below 128, range_ is updated, and fresh bits read from the bitstream are
 
33
// brought in as LSB.
 
34
// To avoid reading the fresh bits one by one (slow), we cache a few of them
 
35
// ahead (actually, we cache BITS of them ahead. See below). There's two
 
36
// strategies regarding how to shift these looked-ahead fresh bits into the
 
37
// 8bit window of value_: either we shift them in, while keeping the position of
 
38
// the window fixed. Or we slide the window to the right while keeping the cache
 
39
// bits at a fixed, right-justified, position.
 
40
//
 
41
//  Example, for BITS=16: here is the content of value_ for both strategies:
 
42
//
 
43
//          !USE_RIGHT_JUSTIFY            ||        USE_RIGHT_JUSTIFY
 
44
//                                        ||
 
45
//   <- 8b -><- 8b -><- BITS bits  ->     ||  <- 8b+3b -><- 8b -><- 13 bits ->
 
46
//   [unused][value_][cached bits][0]     ||  [unused...][value_][cached bits]
 
47
//  [........00vvvvvvBBBBBBBBBBBBB000]LSB || [...........00vvvvvvBBBBBBBBBBBBB]
 
48
//                                        ||
 
49
// After calling VP8Shift(), where we need to shift away two zeros:
 
50
//  [........vvvvvvvvBBBBBBBBBBB00000]LSB || [.............vvvvvvvvBBBBBBBBBBB]
 
51
//                                        ||
 
52
// Just before we need to call VP8LoadNewBytes(), the situation is:
 
53
//  [........vvvvvv000000000000000000]LSB || [..........................vvvvvv]
 
54
//                                        ||
 
55
// And just after calling VP8LoadNewBytes():
 
56
//  [........vvvvvvvvBBBBBBBBBBBBBBBB]LSB || [........vvvvvvvvBBBBBBBBBBBBBBBB]
 
57
//
 
58
// -> we're back to height active 'value_' bits (marked 'v') and BITS cached
 
59
// bits (marked 'B')
 
60
//
 
61
// The right-justify strategy tends to use less shifts and is often faster.
 
62
 
 
63
//------------------------------------------------------------------------------
 
64
// BITS can be any multiple of 8 from 8 to 56 (inclusive).
 
65
// Pick values that fit natural register size.
 
66
 
 
67
#if !defined(WEBP_REFERENCE_IMPLEMENTATION)
 
68
 
 
69
#define USE_RIGHT_JUSTIFY
 
70
 
 
71
#if defined(__i386__) || defined(_M_IX86)      // x86 32bit
 
72
#define BITS 16
 
73
#elif defined(__x86_64__) || defined(_M_X64)   // x86 64bit
 
74
#define BITS 56
 
75
#elif defined(__arm__) || defined(_M_ARM)      // ARM
 
76
#define BITS 24
 
77
#else                      // reasonable default
 
78
#define BITS 24
 
79
#endif
 
80
 
 
81
#else     // reference choices
 
82
 
 
83
#define USE_RIGHT_JUSTIFY
 
84
#define BITS 8
 
85
 
 
86
#endif
 
87
 
 
88
//------------------------------------------------------------------------------
 
89
// Derived types and constants
 
90
 
 
91
// bit_t = natural register type
 
92
// lbit_t = natural type for memory I/O
 
93
 
 
94
#if (BITS > 32)
 
95
typedef uint64_t bit_t;
 
96
typedef uint64_t lbit_t;
 
97
#elif (BITS == 32)
 
98
typedef uint64_t bit_t;
 
99
typedef uint32_t lbit_t;
 
100
#elif (BITS == 24)
 
101
typedef uint32_t bit_t;
 
102
typedef uint32_t lbit_t;
 
103
#elif (BITS == 16)
 
104
typedef uint32_t bit_t;
 
105
typedef uint16_t lbit_t;
 
106
#else
 
107
typedef uint32_t bit_t;
 
108
typedef uint8_t lbit_t;
 
109
#endif
 
110
 
 
111
#ifndef USE_RIGHT_JUSTIFY
 
112
typedef bit_t range_t;     // type for storing range_
 
113
#define MASK ((((bit_t)1) << (BITS)) - 1)
 
114
#else
 
115
typedef uint32_t range_t;  // range_ only uses 8bits here. No need for bit_t.
 
116
#endif
 
117
 
 
118
//------------------------------------------------------------------------------
 
119
// Bitreader
 
120
 
 
121
typedef struct VP8BitReader VP8BitReader;
 
122
struct VP8BitReader {
 
123
  const uint8_t* buf_;        // next byte to be read
 
124
  const uint8_t* buf_end_;    // end of read buffer
 
125
  int eof_;                   // true if input is exhausted
 
126
 
 
127
  // boolean decoder
 
128
  range_t range_;            // current range minus 1. In [127, 254] interval.
 
129
  bit_t value_;              // current value
 
130
  int bits_;                 // number of valid bits left
 
131
};
 
132
 
 
133
// Initialize the bit reader and the boolean decoder.
 
134
void VP8InitBitReader(VP8BitReader* const br,
 
135
                      const uint8_t* const start, const uint8_t* const end);
 
136
 
 
137
// return the next value made of 'num_bits' bits
 
138
uint32_t VP8GetValue(VP8BitReader* const br, int num_bits);
 
139
static WEBP_INLINE uint32_t VP8Get(VP8BitReader* const br) {
 
140
  return VP8GetValue(br, 1);
 
141
}
 
142
 
 
143
// return the next value with sign-extension.
 
144
int32_t VP8GetSignedValue(VP8BitReader* const br, int num_bits);
 
145
 
 
146
// Read a bit with proba 'prob'. Speed-critical function!
 
147
extern const uint8_t kVP8Log2Range[128];
 
148
extern const range_t kVP8NewRange[128];
 
149
 
 
150
void VP8LoadFinalBytes(VP8BitReader* const br);    // special case for the tail
 
151
 
 
152
static WEBP_INLINE void VP8LoadNewBytes(VP8BitReader* const br) {
 
153
  assert(br != NULL && br->buf_ != NULL);
 
154
  // Read 'BITS' bits at a time if possible.
 
155
  if (br->buf_ + sizeof(lbit_t) <= br->buf_end_) {
 
156
    // convert memory type to register type (with some zero'ing!)
 
157
    bit_t bits;
 
158
    lbit_t in_bits = *(lbit_t*)br->buf_;
 
159
    br->buf_ += (BITS) >> 3;
 
160
#if !defined(__BIG_ENDIAN__)
 
161
#if (BITS > 32)
 
162
// gcc 4.3 has builtin functions for swap32/swap64
 
163
#if defined(__GNUC__) && \
 
164
           (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 3))
 
165
    bits = (bit_t)__builtin_bswap64(in_bits);
 
166
#elif defined(_MSC_VER)
 
167
    bits = (bit_t)_byteswap_uint64(in_bits);
 
168
#elif defined(__x86_64__)
 
169
    __asm__ volatile("bswapq %0" : "=r"(bits) : "0"(in_bits));
 
170
#else  // generic code for swapping 64-bit values (suggested by bdb@)
 
171
    bits = (bit_t)in_bits;
 
172
    bits = ((bits & 0xffffffff00000000ull) >> 32) |
 
173
           ((bits & 0x00000000ffffffffull) << 32);
 
174
    bits = ((bits & 0xffff0000ffff0000ull) >> 16) |
 
175
           ((bits & 0x0000ffff0000ffffull) << 16);
 
176
    bits = ((bits & 0xff00ff00ff00ff00ull) >> 8) |
 
177
           ((bits & 0x00ff00ff00ff00ffull) << 8);
 
178
#endif
 
179
    bits >>= 64 - BITS;
 
180
#elif (BITS >= 24)
 
181
#if defined(__i386__) || defined(__x86_64__)
 
182
    __asm__ volatile("bswap %k0" : "=r"(in_bits) : "0"(in_bits));
 
183
    bits = (bit_t)in_bits;   // 24b/32b -> 32b/64b zero-extension
 
184
#elif defined(_MSC_VER)
 
185
    bits = (bit_t)_byteswap_ulong(in_bits);
 
186
#else
 
187
    bits = (bit_t)(in_bits >> 24) | ((in_bits >> 8) & 0xff00)
 
188
         | ((in_bits << 8) & 0xff0000)  | (in_bits << 24);
 
189
#endif  // x86
 
190
    bits >>= (32 - BITS);
 
191
#elif (BITS == 16)
 
192
    // gcc will recognize a 'rorw $8, ...' here:
 
193
    bits = (bit_t)(in_bits >> 8) | ((in_bits & 0xff) << 8);
 
194
#else   // BITS == 8
 
195
    bits = (bit_t)in_bits;
 
196
#endif
 
197
#else    // BIG_ENDIAN
 
198
    bits = (bit_t)in_bits;
 
199
    if (BITS != 8 * sizeof(bit_t)) bits >>= (8 * sizeof(bit_t) - BITS);
 
200
#endif
 
201
#ifndef USE_RIGHT_JUSTIFY
 
202
    br->value_ |= bits << (-br->bits_);
 
203
#else
 
204
    br->value_ = bits | (br->value_ << (BITS));
 
205
#endif
 
206
    br->bits_ += (BITS);
 
207
  } else {
 
208
    VP8LoadFinalBytes(br);    // no need to be inlined
 
209
  }
 
210
}
 
211
 
 
212
static WEBP_INLINE int VP8BitUpdate(VP8BitReader* const br, range_t split) {
 
213
  if (br->bits_ < 0) {  // Make sure we have a least BITS bits in 'value_'
 
214
    VP8LoadNewBytes(br);
 
215
  }
 
216
#ifndef USE_RIGHT_JUSTIFY
 
217
  split |= (MASK);
 
218
  if (br->value_ > split) {
 
219
    br->range_ -= split + 1;
 
220
    br->value_ -= split + 1;
 
221
    return 1;
 
222
  } else {
 
223
    br->range_ = split;
 
224
    return 0;
 
225
  }
 
226
#else
 
227
  {
 
228
    const int pos = br->bits_;
 
229
    const range_t value = (range_t)(br->value_ >> pos);
 
230
    if (value > split) {
 
231
      br->range_ -= split + 1;
 
232
      br->value_ -= (bit_t)(split + 1) << pos;
 
233
      return 1;
 
234
    } else {
 
235
      br->range_ = split;
 
236
      return 0;
 
237
    }
 
238
  }
 
239
#endif
 
240
}
 
241
 
 
242
static WEBP_INLINE void VP8Shift(VP8BitReader* const br) {
 
243
#ifndef USE_RIGHT_JUSTIFY
 
244
  // range_ is in [0..127] interval here.
 
245
  const bit_t idx = br->range_ >> (BITS);
 
246
  const int shift = kVP8Log2Range[idx];
 
247
  br->range_ = kVP8NewRange[idx];
 
248
  br->value_ <<= shift;
 
249
  br->bits_ -= shift;
 
250
#else
 
251
  const int shift = kVP8Log2Range[br->range_];
 
252
  assert(br->range_ < (range_t)128);
 
253
  br->range_ = kVP8NewRange[br->range_];
 
254
  br->bits_ -= shift;
 
255
#endif
 
256
}
 
257
static WEBP_INLINE int VP8GetBit(VP8BitReader* const br, int prob) {
 
258
#ifndef USE_RIGHT_JUSTIFY
 
259
  // It's important to avoid generating a 64bit x 64bit multiply here.
 
260
  // We just need an 8b x 8b after all.
 
261
  const range_t split =
 
262
      (range_t)((uint32_t)(br->range_ >> (BITS)) * prob) << ((BITS) - 8);
 
263
  const int bit = VP8BitUpdate(br, split);
 
264
  if (br->range_ <= (((range_t)0x7e << (BITS)) | (MASK))) {
 
265
    VP8Shift(br);
 
266
  }
 
267
  return bit;
 
268
#else
 
269
  const range_t split = (br->range_ * prob) >> 8;
 
270
  const int bit = VP8BitUpdate(br, split);
 
271
  if (br->range_ <= (range_t)0x7e) {
 
272
    VP8Shift(br);
 
273
  }
 
274
  return bit;
 
275
#endif
 
276
}
 
277
 
 
278
static WEBP_INLINE int VP8GetSigned(VP8BitReader* const br, int v) {
 
279
  const range_t split = (br->range_ >> 1);
 
280
  const int bit = VP8BitUpdate(br, split);
 
281
  VP8Shift(br);
 
282
  return bit ? -v : v;
 
283
}
 
284
 
 
285
 
 
286
// -----------------------------------------------------------------------------
 
287
// Bitreader for lossless format
 
288
 
 
289
typedef uint64_t vp8l_val_t;  // right now, this bit-reader can only use 64bit.
 
290
 
 
291
typedef struct {
 
292
  vp8l_val_t     val_;        // pre-fetched bits
 
293
  const uint8_t* buf_;        // input byte buffer
 
294
  size_t         len_;        // buffer length
 
295
  size_t         pos_;        // byte position in buf_
 
296
  int            bit_pos_;    // current bit-reading position in val_
 
297
  int            eos_;        // bitstream is finished
 
298
  int            error_;      // an error occurred (buffer overflow attempt...)
 
299
} VP8LBitReader;
 
300
 
 
301
void VP8LInitBitReader(VP8LBitReader* const br,
 
302
                       const uint8_t* const start,
 
303
                       size_t length);
 
304
 
 
305
//  Sets a new data buffer.
 
306
void VP8LBitReaderSetBuffer(VP8LBitReader* const br,
 
307
                            const uint8_t* const buffer, size_t length);
 
308
 
 
309
// Reads the specified number of bits from Read Buffer.
 
310
// Flags an error in case end_of_stream or n_bits is more than allowed limit.
 
311
// Flags eos if this read attempt is going to cross the read buffer.
 
312
uint32_t VP8LReadBits(VP8LBitReader* const br, int n_bits);
 
313
 
 
314
// Return the prefetched bits, so they can be looked up.
 
315
static WEBP_INLINE uint32_t VP8LPrefetchBits(VP8LBitReader* const br) {
 
316
  return (uint32_t)(br->val_ >> br->bit_pos_);
 
317
}
 
318
 
 
319
// Discard 'num_bits' bits from the cache.
 
320
static WEBP_INLINE void VP8LDiscardBits(VP8LBitReader* const br, int num_bits) {
 
321
  br->bit_pos_ += num_bits;
 
322
}
 
323
 
 
324
// Advances the Read buffer by 4 bytes to make room for reading next 32 bits.
 
325
void VP8LFillBitWindow(VP8LBitReader* const br);
 
326
 
 
327
#if defined(__cplusplus) || defined(c_plusplus)
 
328
}    // extern "C"
 
329
#endif
 
330
 
 
331
#endif  /* WEBP_UTILS_BIT_READER_H_ */