1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
|
// Copyright 2012 Google Inc. All Rights Reserved.
//
// Use of this source code is governed by a BSD-style license
// that can be found in the COPYING file in the root of the source
// tree. An additional intellectual property rights grant can be found
// in the file PATENTS. All contributing project authors may
// be found in the AUTHORS file in the root of the source tree.
// -----------------------------------------------------------------------------
//
// Author: Jyrki Alakuijala (jyrki@google.com)
//
#ifndef WEBP_ENC_BACKWARD_REFERENCES_H_
#define WEBP_ENC_BACKWARD_REFERENCES_H_
#include <assert.h>
#include <stdlib.h>
#include "../webp/types.h"
#include "../webp/format_constants.h"
#ifdef __cplusplus
extern "C" {
#endif
// The maximum allowed limit is 11.
#define MAX_COLOR_CACHE_BITS 10
// -----------------------------------------------------------------------------
// PixOrCopy
enum Mode {
kLiteral,
kCacheIdx,
kCopy,
kNone
};
typedef struct {
// mode as uint8_t to make the memory layout to be exactly 8 bytes.
uint8_t mode;
uint16_t len;
uint32_t argb_or_distance;
} PixOrCopy;
static WEBP_INLINE PixOrCopy PixOrCopyCreateCopy(uint32_t distance,
uint16_t len) {
PixOrCopy retval;
retval.mode = kCopy;
retval.argb_or_distance = distance;
retval.len = len;
return retval;
}
static WEBP_INLINE PixOrCopy PixOrCopyCreateCacheIdx(int idx) {
PixOrCopy retval;
assert(idx >= 0);
assert(idx < (1 << MAX_COLOR_CACHE_BITS));
retval.mode = kCacheIdx;
retval.argb_or_distance = idx;
retval.len = 1;
return retval;
}
static WEBP_INLINE PixOrCopy PixOrCopyCreateLiteral(uint32_t argb) {
PixOrCopy retval;
retval.mode = kLiteral;
retval.argb_or_distance = argb;
retval.len = 1;
return retval;
}
static WEBP_INLINE int PixOrCopyIsLiteral(const PixOrCopy* const p) {
return (p->mode == kLiteral);
}
static WEBP_INLINE int PixOrCopyIsCacheIdx(const PixOrCopy* const p) {
return (p->mode == kCacheIdx);
}
static WEBP_INLINE int PixOrCopyIsCopy(const PixOrCopy* const p) {
return (p->mode == kCopy);
}
static WEBP_INLINE uint32_t PixOrCopyLiteral(const PixOrCopy* const p,
int component) {
assert(p->mode == kLiteral);
return (p->argb_or_distance >> (component * 8)) & 0xff;
}
static WEBP_INLINE uint32_t PixOrCopyLength(const PixOrCopy* const p) {
return p->len;
}
static WEBP_INLINE uint32_t PixOrCopyArgb(const PixOrCopy* const p) {
assert(p->mode == kLiteral);
return p->argb_or_distance;
}
static WEBP_INLINE uint32_t PixOrCopyCacheIdx(const PixOrCopy* const p) {
assert(p->mode == kCacheIdx);
assert(p->argb_or_distance < (1U << MAX_COLOR_CACHE_BITS));
return p->argb_or_distance;
}
static WEBP_INLINE uint32_t PixOrCopyDistance(const PixOrCopy* const p) {
assert(p->mode == kCopy);
return p->argb_or_distance;
}
// -----------------------------------------------------------------------------
// VP8LHashChain
#define HASH_BITS 18
#define HASH_SIZE (1 << HASH_BITS)
typedef struct VP8LHashChain VP8LHashChain;
struct VP8LHashChain {
// The 20 most significant bits contain the offset at which the best match
// is found. These 20 bits are the limit defined by GetWindowSizeForHashChain
// (through WINDOW_SIZE = 1<<20).
// The lower 12 bits contain the length of the match. The 12 bit limit is
// defined in MaxFindCopyLength with MAX_LENGTH=4096.
uint32_t* offset_length_;
// This is the maximum size of the hash_chain that can be constructed.
// Typically this is the pixel count (width x height) for a given image.
int size_;
};
// Must be called first, to set size.
int VP8LHashChainInit(VP8LHashChain* const p, int size);
// Pre-compute the best matches for argb.
int VP8LHashChainFill(VP8LHashChain* const p, int quality,
const uint32_t* const argb, int xsize, int ysize,
int low_effort);
void VP8LHashChainClear(VP8LHashChain* const p); // release memory
// -----------------------------------------------------------------------------
// VP8LBackwardRefs (block-based backward-references storage)
// maximum number of reference blocks the image will be segmented into
#define MAX_REFS_BLOCK_PER_IMAGE 16
typedef struct PixOrCopyBlock PixOrCopyBlock; // forward declaration
typedef struct VP8LBackwardRefs VP8LBackwardRefs;
// Container for blocks chain
struct VP8LBackwardRefs {
int block_size_; // common block-size
int error_; // set to true if some memory error occurred
PixOrCopyBlock* refs_; // list of currently used blocks
PixOrCopyBlock** tail_; // for list recycling
PixOrCopyBlock* free_blocks_; // free-list
PixOrCopyBlock* last_block_; // used for adding new refs (internal)
};
// Initialize the object. 'block_size' is the common block size to store
// references (typically, width * height / MAX_REFS_BLOCK_PER_IMAGE).
void VP8LBackwardRefsInit(VP8LBackwardRefs* const refs, int block_size);
// Release memory for backward references.
void VP8LBackwardRefsClear(VP8LBackwardRefs* const refs);
// Copies the 'src' backward refs to the 'dst'. Returns 0 in case of error.
int VP8LBackwardRefsCopy(const VP8LBackwardRefs* const src,
VP8LBackwardRefs* const dst);
// Cursor for iterating on references content
typedef struct {
// public:
PixOrCopy* cur_pos; // current position
// private:
PixOrCopyBlock* cur_block_; // current block in the refs list
const PixOrCopy* last_pos_; // sentinel for switching to next block
} VP8LRefsCursor;
// Returns a cursor positioned at the beginning of the references list.
VP8LRefsCursor VP8LRefsCursorInit(const VP8LBackwardRefs* const refs);
// Returns true if cursor is pointing at a valid position.
static WEBP_INLINE int VP8LRefsCursorOk(const VP8LRefsCursor* const c) {
return (c->cur_pos != NULL);
}
// Move to next block of references. Internal, not to be called directly.
void VP8LRefsCursorNextBlock(VP8LRefsCursor* const c);
// Move to next position, or NULL. Should not be called if !VP8LRefsCursorOk().
static WEBP_INLINE void VP8LRefsCursorNext(VP8LRefsCursor* const c) {
assert(c != NULL);
assert(VP8LRefsCursorOk(c));
if (++c->cur_pos == c->last_pos_) VP8LRefsCursorNextBlock(c);
}
// -----------------------------------------------------------------------------
// Main entry points
// Evaluates best possible backward references for specified quality.
// The input cache_bits to 'VP8LGetBackwardReferences' sets the maximum cache
// bits to use (passing 0 implies disabling the local color cache).
// The optimal cache bits is evaluated and set for the *cache_bits parameter.
// The return value is the pointer to the best of the two backward refs viz,
// refs[0] or refs[1].
VP8LBackwardRefs* VP8LGetBackwardReferences(
int width, int height, const uint32_t* const argb, int quality,
int low_effort, int* const cache_bits,
const VP8LHashChain* const hash_chain, VP8LBackwardRefs refs[2]);
#ifdef __cplusplus
}
#endif
#endif // WEBP_ENC_BACKWARD_REFERENCES_H_
|