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
23extern "C" {
24#endif
25
26// The maximum allowed limit is 11.
27#define MAX_COLOR_CACHE_BITS 10
28
29// -----------------------------------------------------------------------------
30// PixOrCopy
31
32enum Mode {
33 kLiteral,
34 kCacheIdx,
35 kCopy,
36 kNone
37};
38
39typedef 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
46static 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
55static 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
65static 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
73static WEBP_INLINE int PixOrCopyIsLiteral(const PixOrCopy* const p) {
74 return (p->mode == kLiteral);
75}
76
77static WEBP_INLINE int PixOrCopyIsCacheIdx(const PixOrCopy* const p) {
78 return (p->mode == kCacheIdx);
79}
80
81static WEBP_INLINE int PixOrCopyIsCopy(const PixOrCopy* const p) {
82 return (p->mode == kCopy);
83}
84
85static 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
91static WEBP_INLINE uint32_t PixOrCopyLength(const PixOrCopy* const p) {
92 return p->len;
93}
94
95static 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
101static 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
122typedef struct VP8LHashChain VP8LHashChain;
123struct 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.
136int VP8LHashChainInit(VP8LHashChain* const p, int size);
137// Pre-compute the best matches for argb. pic and percent are for progress.
138int 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);
142void VP8LHashChainClear(VP8LHashChain* const p); // release memory
143
144static 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
149static 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
154static 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
168typedef struct PixOrCopyBlock PixOrCopyBlock; // forward declaration
169typedef struct VP8LBackwardRefs VP8LBackwardRefs;
170
171// Container for blocks chain
172struct 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).
183void VP8LBackwardRefsInit(VP8LBackwardRefs* const refs, int block_size);
184// Release memory for backward references.
185void VP8LBackwardRefsClear(VP8LBackwardRefs* const refs);
186
187// Cursor for iterating on references content
188typedef 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.
197VP8LRefsCursor VP8LRefsCursorInit(const VP8LBackwardRefs* const refs);
198// Returns true if cursor is pointing at a valid position.
199static 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.
203void VP8LRefsCursorNextBlock(VP8LRefsCursor* const c);
204// Move to next position, or NULL. Should not be called if !VP8LRefsCursorOk().
205static 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
214enum 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).
233int 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