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