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