1 // Copyright 2013 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 // Pseudo-random utilities
11 //
12 // Author: Skal (pascal.massimino@gmail.com)
13
14 #ifndef WEBP_UTILS_RANDOM_UTILS_H_
15 #define WEBP_UTILS_RANDOM_UTILS_H_
16
17 #include <assert.h>
18 #include "src/webp/types.h"
19
20 #ifdef __cplusplus
21 extern "C" {
22 #endif
23
24 #define VP8_RANDOM_DITHER_FIX 8 // fixed-point precision for dithering
25 #define VP8_RANDOM_TABLE_SIZE 55
26
27 typedef struct {
28 int index1_, index2_;
29 uint32_t tab_[VP8_RANDOM_TABLE_SIZE];
30 int amp_;
31 } VP8Random;
32
33 // Initializes random generator with an amplitude 'dithering' in range [0..1].
34 void VP8InitRandom(VP8Random* const rg, float dithering);
35
36 // Returns a centered pseudo-random number with 'num_bits' amplitude.
37 // (uses D.Knuth's Difference-based random generator).
38 // 'amp' is in VP8_RANDOM_DITHER_FIX fixed-point precision.
VP8RandomBits2(VP8Random * const rg,int num_bits,int amp)39 static WEBP_INLINE int VP8RandomBits2(VP8Random* const rg, int num_bits,
40 int amp) {
41 int diff;
42 assert(num_bits + VP8_RANDOM_DITHER_FIX <= 31);
43 diff = rg->tab_[rg->index1_] - rg->tab_[rg->index2_];
44 if (diff < 0) diff += (1u << 31);
45 rg->tab_[rg->index1_] = diff;
46 if (++rg->index1_ == VP8_RANDOM_TABLE_SIZE) rg->index1_ = 0;
47 if (++rg->index2_ == VP8_RANDOM_TABLE_SIZE) rg->index2_ = 0;
48 // sign-extend, 0-center
49 diff = (int)((uint32_t)diff << 1) >> (32 - num_bits);
50 diff = (diff * amp) >> VP8_RANDOM_DITHER_FIX; // restrict range
51 diff += 1 << (num_bits - 1); // shift back to 0.5-center
52 return diff;
53 }
54
VP8RandomBits(VP8Random * const rg,int num_bits)55 static WEBP_INLINE int VP8RandomBits(VP8Random* const rg, int num_bits) {
56 return VP8RandomBits2(rg, num_bits, rg->amp_);
57 }
58
59 #ifdef __cplusplus
60 } // extern "C"
61 #endif
62
63 #endif // WEBP_UTILS_RANDOM_UTILS_H_
64