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