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
22extern "C" {
23#endif
24
25// The maximum allowed limit is 11.
26#define MAX_COLOR_CACHE_BITS 10
27
28// -----------------------------------------------------------------------------
29// PixOrCopy
30
31enum Mode {
32 kLiteral,
33 kCacheIdx,
34 kCopy,
35 kNone
36};
37
38typedef 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
45static 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
54static 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
64static 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
72static WEBP_INLINE int PixOrCopyIsLiteral(const PixOrCopy* const p) {
73 return (p->mode == kLiteral);
74}
75
76static WEBP_INLINE int PixOrCopyIsCacheIdx(const PixOrCopy* const p) {
77 return (p->mode == kCacheIdx);
78}
79
80static WEBP_INLINE int PixOrCopyIsCopy(const PixOrCopy* const p) {
81 return (p->mode == kCopy);
82}
83
84static 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
90static WEBP_INLINE uint32_t PixOrCopyLength(const PixOrCopy* const p) {
91 return p->len;
92}
93
94static 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
100static 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
121typedef struct VP8LHashChain VP8LHashChain;
122struct 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.
135int VP8LHashChainInit(VP8LHashChain* const p, int size);
136// Pre-compute the best matches for argb.
137int VP8LHashChainFill(VP8LHashChain* const p, int quality,
138 const uint32_t* const argb, int xsize, int ysize,
139 int low_effort);
140void VP8LHashChainClear(VP8LHashChain* const p); // release memory
141
142static 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
147static 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
152static 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
166typedef struct PixOrCopyBlock PixOrCopyBlock; // forward declaration
167typedef struct VP8LBackwardRefs VP8LBackwardRefs;
168
169// Container for blocks chain
170struct 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).
181void VP8LBackwardRefsInit(VP8LBackwardRefs* const refs, int block_size);
182// Release memory for backward references.
183void VP8LBackwardRefsClear(VP8LBackwardRefs* const refs);
184
185// Cursor for iterating on references content
186typedef 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.
195VP8LRefsCursor VP8LRefsCursorInit(const VP8LBackwardRefs* const refs);
196// Returns true if cursor is pointing at a valid position.
197static 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.
201void VP8LRefsCursorNextBlock(VP8LRefsCursor* const c);
202// Move to next position, or NULL. Should not be called if !VP8LRefsCursorOk().
203static 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
212enum 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].
224VP8LBackwardRefs* 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