← Back to branch summary

~alinuxninja/nginx-edge/trunk

« back to all changes in this revision

Viewing changes to debian/modules/ngx_pagespeed/psol/include/third_party/libwebp/src/enc/backward_references.h

  • Committer: Vivian
  • Date: 2015-12-04 18:20:11 UTC
  • Revision ID: git-v1:a36f2bc32e884f7473b3a47040e5411306144d7d
* Do not extract psol.tar.gz

Show diffs side-by-side

added added

removed removed

Lines of Context:
debian/modules/ngx_pagespeed/psol/include/third_party/libwebp/src/enc/backward_references.h
1
 
// Copyright 2012 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
 
// Author: Jyrki Alakuijala (jyrki@google.com)
11
 
//
12
 
 
13
 
#ifndef WEBP_ENC_BACKWARD_REFERENCES_H_
14
 
#define WEBP_ENC_BACKWARD_REFERENCES_H_
15
 
 
16
 
#include <assert.h>
17
 
#include <stdlib.h>
18
 
#include "../webp/types.h"
19
 
#include "../webp/format_constants.h"
20
 
 
21
 
#ifdef __cplusplus
22
 
extern "C" {
23
 
#endif
24
 
 
25
 
// The spec allows 11, we use 9 bits to reduce memory consumption in encoding.
26
 
// Having 9 instead of 11 only removes about 0.25 % of compression density.
27
 
#define MAX_COLOR_CACHE_BITS 9
28
 
 
29
 
// Max ever number of codes we'll use:
30
 
#define PIX_OR_COPY_CODES_MAX \
31
 
    (NUM_LITERAL_CODES + NUM_LENGTH_CODES + (1 << MAX_COLOR_CACHE_BITS))
32
 
 
33
 
// -----------------------------------------------------------------------------
34
 
// PixOrCopy
35
 
 
36
 
enum Mode {
37
 
  kLiteral,
38
 
  kCacheIdx,
39
 
  kCopy,
40
 
  kNone
41
 
};
42
 
 
43
 
typedef struct {
44
 
  // mode as uint8_t to make the memory layout to be exactly 8 bytes.
45
 
  uint8_t mode;
46
 
  uint16_t len;
47
 
  uint32_t argb_or_distance;
48
 
} PixOrCopy;
49
 
 
50
 
static WEBP_INLINE PixOrCopy PixOrCopyCreateCopy(uint32_t distance,
51
 
                                                 uint16_t len) {
52
 
  PixOrCopy retval;
53
 
  retval.mode = kCopy;
54
 
  retval.argb_or_distance = distance;
55
 
  retval.len = len;
56
 
  return retval;
57
 
}
58
 
 
59
 
static WEBP_INLINE PixOrCopy PixOrCopyCreateCacheIdx(int idx) {
60
 
  PixOrCopy retval;
61
 
  assert(idx >= 0);
62
 
  assert(idx < (1 << MAX_COLOR_CACHE_BITS));
63
 
  retval.mode = kCacheIdx;
64
 
  retval.argb_or_distance = idx;
65
 
  retval.len = 1;
66
 
  return retval;
67
 
}
68
 
 
69
 
static WEBP_INLINE PixOrCopy PixOrCopyCreateLiteral(uint32_t argb) {
70
 
  PixOrCopy retval;
71
 
  retval.mode = kLiteral;
72
 
  retval.argb_or_distance = argb;
73
 
  retval.len = 1;
74
 
  return retval;
75
 
}
76
 
 
77
 
static WEBP_INLINE int PixOrCopyIsLiteral(const PixOrCopy* const p) {
78
 
  return (p->mode == kLiteral);
79
 
}
80
 
 
81
 
static WEBP_INLINE int PixOrCopyIsCacheIdx(const PixOrCopy* const p) {
82
 
  return (p->mode == kCacheIdx);
83
 
}
84
 
 
85
 
static WEBP_INLINE int PixOrCopyIsCopy(const PixOrCopy* const p) {
86
 
  return (p->mode == kCopy);
87
 
}
88
 
 
89
 
static WEBP_INLINE uint32_t PixOrCopyLiteral(const PixOrCopy* const p,
90
 
                                             int component) {
91
 
  assert(p->mode == kLiteral);
92
 
  return (p->argb_or_distance >> (component * 8)) & 0xff;
93
 
}
94
 
 
95
 
static WEBP_INLINE uint32_t PixOrCopyLength(const PixOrCopy* const p) {
96
 
  return p->len;
97
 
}
98
 
 
99
 
static WEBP_INLINE uint32_t PixOrCopyArgb(const PixOrCopy* const p) {
100
 
  assert(p->mode == kLiteral);
101
 
  return p->argb_or_distance;
102
 
}
103
 
 
104
 
static WEBP_INLINE uint32_t PixOrCopyCacheIdx(const PixOrCopy* const p) {
105
 
  assert(p->mode == kCacheIdx);
106
 
  assert(p->argb_or_distance < (1U << MAX_COLOR_CACHE_BITS));
107
 
  return p->argb_or_distance;
108
 
}
109
 
 
110
 
static WEBP_INLINE uint32_t PixOrCopyDistance(const PixOrCopy* const p) {
111
 
  assert(p->mode == kCopy);
112
 
  return p->argb_or_distance;
113
 
}
114
 
 
115
 
// -----------------------------------------------------------------------------
116
 
// VP8LHashChain
117
 
 
118
 
#define HASH_BITS 18
119
 
#define HASH_SIZE (1 << HASH_BITS)
120
 
 
121
 
typedef struct VP8LHashChain VP8LHashChain;
122
 
struct VP8LHashChain {
123
 
  // Stores the most recently added position with the given hash value.
124
 
  int32_t hash_to_first_index_[HASH_SIZE];
125
 
  // chain_[pos] stores the previous position with the same hash value
126
 
  // for every pixel in the image.
127
 
  int32_t* chain_;
128
 
  // This is the maximum size of the hash_chain that can be constructed.
129
 
  // Typically this is the pixel count (width x height) for a given image.
130
 
  int size_;
131
 
};
132
 
 
133
 
// Must be called first, to set size.
134
 
int VP8LHashChainInit(VP8LHashChain* const p, int size);
135
 
void VP8LHashChainClear(VP8LHashChain* const p);  // release memory
136
 
 
137
 
// -----------------------------------------------------------------------------
138
 
// VP8LBackwardRefs (block-based backward-references storage)
139
 
 
140
 
// maximum number of reference blocks the image will be segmented into
141
 
#define MAX_REFS_BLOCK_PER_IMAGE 16
142
 
 
143
 
typedef struct PixOrCopyBlock PixOrCopyBlock;   // forward declaration
144
 
typedef struct VP8LBackwardRefs VP8LBackwardRefs;
145
 
 
146
 
// Container for blocks chain
147
 
struct VP8LBackwardRefs {
148
 
  int block_size_;               // common block-size
149
 
  int error_;                    // set to true if some memory error occurred
150
 
  PixOrCopyBlock* refs_;         // list of currently used blocks
151
 
  PixOrCopyBlock** tail_;        // for list recycling
152
 
  PixOrCopyBlock* free_blocks_;  // free-list
153
 
  PixOrCopyBlock* last_block_;   // used for adding new refs (internal)
154
 
};
155
 
 
156
 
// Initialize the object. 'block_size' is the common block size to store
157
 
// references (typically, width * height / MAX_REFS_BLOCK_PER_IMAGE).
158
 
void VP8LBackwardRefsInit(VP8LBackwardRefs* const refs, int block_size);
159
 
// Release memory for backward references.
160
 
void VP8LBackwardRefsClear(VP8LBackwardRefs* const refs);
161
 
// Copies the 'src' backward refs to the 'dst'. Returns 0 in case of error.
162
 
int VP8LBackwardRefsCopy(const VP8LBackwardRefs* const src,
163
 
                         VP8LBackwardRefs* const dst);
164
 
 
165
 
// Cursor for iterating on references content
166
 
typedef struct {
167
 
  // public:
168
 
  PixOrCopy* cur_pos;           // current position
169
 
  // private:
170
 
  PixOrCopyBlock* cur_block_;   // current block in the refs list
171
 
  const PixOrCopy* last_pos_;   // sentinel for switching to next block
172
 
} VP8LRefsCursor;
173
 
 
174
 
// Returns a cursor positioned at the beginning of the references list.
175
 
VP8LRefsCursor VP8LRefsCursorInit(const VP8LBackwardRefs* const refs);
176
 
// Returns true if cursor is pointing at a valid position.
177
 
static WEBP_INLINE int VP8LRefsCursorOk(const VP8LRefsCursor* const c) {
178
 
  return (c->cur_pos != NULL);
179
 
}
180
 
// Move to next block of references. Internal, not to be called directly.
181
 
void VP8LRefsCursorNextBlock(VP8LRefsCursor* const c);
182
 
// Move to next position, or NULL. Should not be called if !VP8LRefsCursorOk().
183
 
static WEBP_INLINE void VP8LRefsCursorNext(VP8LRefsCursor* const c) {
184
 
  assert(c != NULL);
185
 
  assert(VP8LRefsCursorOk(c));
186
 
  if (++c->cur_pos == c->last_pos_) VP8LRefsCursorNextBlock(c);
187
 
}
188
 
 
189
 
// -----------------------------------------------------------------------------
190
 
// Main entry points
191
 
 
192
 
// Evaluates best possible backward references for specified quality.
193
 
// Further optimize for 2D locality if use_2d_locality flag is set.
194
 
// The return value is the pointer to the best of the two backward refs viz,
195
 
// refs[0] or refs[1].
196
 
VP8LBackwardRefs* VP8LGetBackwardReferences(
197
 
    int width, int height, const uint32_t* const argb, int quality,
198
 
    int cache_bits, int use_2d_locality, VP8LHashChain* const hash_chain,
199
 
    VP8LBackwardRefs refs[2]);
200
 
 
201
 
// Produce an estimate for a good color cache size for the image.
202
 
int VP8LCalculateEstimateForCacheSize(const uint32_t* const argb,
203
 
                                      int xsize, int ysize, int quality,
204
 
                                      VP8LHashChain* const hash_chain,
205
 
                                      VP8LBackwardRefs* const ref,
206
 
                                      int* const best_cache_bits);
207
 
 
208
 
#ifdef __cplusplus
209
 
}
210
 
#endif
211
 
 
212
 
#endif  // WEBP_ENC_BACKWARD_REFERENCES_H_