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.
138 int VP8LHashChainFill(VP8LHashChain* const p, int quality,
139 const uint32_t* const argb, int xsize, int ysize,
140 int low_effort);
141 void VP8LHashChainClear(VP8LHashChain* const p); // release memory
142
VP8LHashChainFindOffset(const VP8LHashChain * const p,const int base_position)143 static WEBP_INLINE int VP8LHashChainFindOffset(const VP8LHashChain* const p,
144 const int base_position) {
145 return p->offset_length_[base_position] >> MAX_LENGTH_BITS;
146 }
147
VP8LHashChainFindLength(const VP8LHashChain * const p,const int base_position)148 static WEBP_INLINE int VP8LHashChainFindLength(const VP8LHashChain* const p,
149 const int base_position) {
150 return p->offset_length_[base_position] & ((1U << MAX_LENGTH_BITS) - 1);
151 }
152
VP8LHashChainFindCopy(const VP8LHashChain * const p,int base_position,int * const offset_ptr,int * const length_ptr)153 static WEBP_INLINE void VP8LHashChainFindCopy(const VP8LHashChain* const p,
154 int base_position,
155 int* const offset_ptr,
156 int* const length_ptr) {
157 *offset_ptr = VP8LHashChainFindOffset(p, base_position);
158 *length_ptr = VP8LHashChainFindLength(p, base_position);
159 }
160
161 // -----------------------------------------------------------------------------
162 // VP8LBackwardRefs (block-based backward-references storage)
163
164 // maximum number of reference blocks the image will be segmented into
165 #define MAX_REFS_BLOCK_PER_IMAGE 16
166
167 typedef struct PixOrCopyBlock PixOrCopyBlock; // forward declaration
168 typedef struct VP8LBackwardRefs VP8LBackwardRefs;
169
170 // Container for blocks chain
171 struct VP8LBackwardRefs {
172 int block_size_; // common block-size
173 int error_; // set to true if some memory error occurred
174 PixOrCopyBlock* refs_; // list of currently used blocks
175 PixOrCopyBlock** tail_; // for list recycling
176 PixOrCopyBlock* free_blocks_; // free-list
177 PixOrCopyBlock* last_block_; // used for adding new refs (internal)
178 };
179
180 // Initialize the object. 'block_size' is the common block size to store
181 // references (typically, width * height / MAX_REFS_BLOCK_PER_IMAGE).
182 void VP8LBackwardRefsInit(VP8LBackwardRefs* const refs, int block_size);
183 // Release memory for backward references.
184 void VP8LBackwardRefsClear(VP8LBackwardRefs* const refs);
185
186 // Cursor for iterating on references content
187 typedef struct {
188 // public:
189 PixOrCopy* cur_pos; // current position
190 // private:
191 PixOrCopyBlock* cur_block_; // current block in the refs list
192 const PixOrCopy* last_pos_; // sentinel for switching to next block
193 } VP8LRefsCursor;
194
195 // Returns a cursor positioned at the beginning of the references list.
196 VP8LRefsCursor VP8LRefsCursorInit(const VP8LBackwardRefs* const refs);
197 // Returns true if cursor is pointing at a valid position.
VP8LRefsCursorOk(const VP8LRefsCursor * const c)198 static WEBP_INLINE int VP8LRefsCursorOk(const VP8LRefsCursor* const c) {
199 return (c->cur_pos != NULL);
200 }
201 // Move to next block of references. Internal, not to be called directly.
202 void VP8LRefsCursorNextBlock(VP8LRefsCursor* const c);
203 // Move to next position, or NULL. Should not be called if !VP8LRefsCursorOk().
VP8LRefsCursorNext(VP8LRefsCursor * const c)204 static WEBP_INLINE void VP8LRefsCursorNext(VP8LRefsCursor* const c) {
205 assert(c != NULL);
206 assert(VP8LRefsCursorOk(c));
207 if (++c->cur_pos == c->last_pos_) VP8LRefsCursorNextBlock(c);
208 }
209
210 // -----------------------------------------------------------------------------
211 // Main entry points
212
213 enum VP8LLZ77Type {
214 kLZ77Standard = 1,
215 kLZ77RLE = 2,
216 kLZ77Box = 4
217 };
218
219 // Evaluates best possible backward references for specified quality.
220 // The input cache_bits to 'VP8LGetBackwardReferences' sets the maximum cache
221 // bits to use (passing 0 implies disabling the local color cache).
222 // The optimal cache bits is evaluated and set for the *cache_bits_best
223 // parameter with the matching refs_best.
224 // If do_no_cache == 0, refs is an array of 2 values and the best
225 // VP8LBackwardRefs is put in the first element.
226 // If do_no_cache != 0, refs is an array of 3 values and the best
227 // VP8LBackwardRefs is put in the first element, the best value with no-cache in
228 // the second element.
229 // In both cases, the last element is used as temporary internally.
230 WebPEncodingError VP8LGetBackwardReferences(
231 int width, int height, const uint32_t* const argb, int quality,
232 int low_effort, int lz77_types_to_try, int cache_bits_max, int do_no_cache,
233 const VP8LHashChain* const hash_chain, VP8LBackwardRefs* const refs,
234 int* const cache_bits_best);
235
236 #ifdef __cplusplus
237 }
238 #endif
239
240 #endif // WEBP_ENC_BACKWARD_REFERENCES_ENC_H_
241