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// Color Cache for WebP Lossless
11//
12// Authors: Jyrki Alakuijala (jyrki@google.com)
13// Urvang Joshi (urvang@google.com)
14
15#ifndef WEBP_UTILS_COLOR_CACHE_UTILS_H_
16#define WEBP_UTILS_COLOR_CACHE_UTILS_H_
17
18#include <assert.h>
19
20#include "src/dsp/dsp.h"
21#include "src/webp/types.h"
22
23#ifdef __cplusplus
24extern "C" {
25#endif
26
27// Main color cache struct.
28typedef struct {
29 uint32_t* colors_; // color entries
30 int hash_shift_; // Hash shift: 32 - hash_bits_.
31 int hash_bits_;
32} VP8LColorCache;
33
34static const uint32_t kHashMul = 0x1e35a7bdu;
35
36static WEBP_UBSAN_IGNORE_UNSIGNED_OVERFLOW WEBP_INLINE
37int VP8LHashPix(uint32_t argb, int shift) {
38 return (int)((argb * kHashMul) >> shift);
39}
40
41static WEBP_INLINE uint32_t VP8LColorCacheLookup(
42 const VP8LColorCache* const cc, uint32_t key) {
43 assert((key >> cc->hash_bits_) == 0u);
44 return cc->colors_[key];
45}
46
47static WEBP_INLINE void VP8LColorCacheSet(const VP8LColorCache* const cc,
48 uint32_t key, uint32_t argb) {
49 assert((key >> cc->hash_bits_) == 0u);
50 cc->colors_[key] = argb;
51}
52
53static WEBP_INLINE void VP8LColorCacheInsert(const VP8LColorCache* const cc,
54 uint32_t argb) {
55 const int key = VP8LHashPix(argb, cc->hash_shift_);
56 cc->colors_[key] = argb;
57}
58
59static WEBP_INLINE int VP8LColorCacheGetIndex(const VP8LColorCache* const cc,
60 uint32_t argb) {
61 return VP8LHashPix(argb, cc->hash_shift_);
62}
63
64// Return the key if cc contains argb, and -1 otherwise.
65static WEBP_INLINE int VP8LColorCacheContains(const VP8LColorCache* const cc,
66 uint32_t argb) {
67 const int key = VP8LHashPix(argb, cc->hash_shift_);
68 return (cc->colors_[key] == argb) ? key : -1;
69}
70
71//------------------------------------------------------------------------------
72
73// Initializes the color cache with 'hash_bits' bits for the keys.
74// Returns false in case of memory error.
75int VP8LColorCacheInit(VP8LColorCache* const color_cache, int hash_bits);
76
77void VP8LColorCacheCopy(const VP8LColorCache* const src,
78 VP8LColorCache* const dst);
79
80// Delete the memory associated to color cache.
81void VP8LColorCacheClear(VP8LColorCache* const color_cache);
82
83//------------------------------------------------------------------------------
84
85#ifdef __cplusplus
86}
87#endif
88
89#endif // WEBP_UTILS_COLOR_CACHE_UTILS_H_
90