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
PixOrCopyCreateCopy(uint32_t distance,uint16_t len)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
PixOrCopyCreateCacheIdx(int idx)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
PixOrCopyCreateLiteral(uint32_t argb)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
PixOrCopyIsLiteral(const PixOrCopy * const p)72 static WEBP_INLINE int PixOrCopyIsLiteral(const PixOrCopy* const p) {
73 return (p->mode == kLiteral);
74 }
75
PixOrCopyIsCacheIdx(const PixOrCopy * const p)76 static WEBP_INLINE int PixOrCopyIsCacheIdx(const PixOrCopy* const p) {
77 return (p->mode == kCacheIdx);
78 }
79
PixOrCopyIsCopy(const PixOrCopy * const p)80 static WEBP_INLINE int PixOrCopyIsCopy(const PixOrCopy* const p) {
81 return (p->mode == kCopy);
82 }
83
PixOrCopyLiteral(const PixOrCopy * const p,int component)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
PixOrCopyLength(const PixOrCopy * const p)90 static WEBP_INLINE uint32_t PixOrCopyLength(const PixOrCopy* const p) {
91 return p->len;
92 }
93
PixOrCopyCacheIdx(const PixOrCopy * const p)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
PixOrCopyDistance(const PixOrCopy * const p)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
VP8LHashChainFindOffset(const VP8LHashChain * const p,const int base_position)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
VP8LHashChainFindLength(const VP8LHashChain * const p,const int base_position)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
VP8LHashChainFindCopy(const VP8LHashChain * const p,int base_position,int * const offset_ptr,int * const length_ptr)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.
VP8LRefsCursorOk(const VP8LRefsCursor * const c)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().
VP8LRefsCursorNext(VP8LRefsCursor * const c)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