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