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