18b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora// Copyright 2013 Google Inc. All Rights Reserved. 28b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora// 38b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora// Use of this source code is governed by a BSD-style license 48b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora// that can be found in the COPYING file in the root of the source 58b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora// tree. An additional intellectual property rights grant can be found 68b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora// in the file PATENTS. All contributing project authors may 78b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora// be found in the AUTHORS file in the root of the source tree. 88b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora// ----------------------------------------------------------------------------- 98b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora// 108b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora// Pseudo-random utilities 118b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora// 128b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora// Author: Skal (pascal.massimino@gmail.com) 138b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora 148b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora#ifndef WEBP_UTILS_RANDOM_H_ 158b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora#define WEBP_UTILS_RANDOM_H_ 168b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora 178b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora#include <assert.h> 188b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora#include "webp/types.h" 198b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora 208b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora#ifdef __cplusplus 218b720228d581a84fd173b6dcb2fa295b59db489aVikas Aroraextern "C" { 228b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora#endif 238b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora 248b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora#define VP8_RANDOM_DITHER_FIX 8 // fixed-point precision for dithering 258b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora#define VP8_RANDOM_TABLE_SIZE 55 268b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora 278b720228d581a84fd173b6dcb2fa295b59db489aVikas Aroratypedef struct { 288b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora int index1_, index2_; 298b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora uint32_t tab_[VP8_RANDOM_TABLE_SIZE]; 308b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora int amp_; 318b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora} VP8Random; 328b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora 338b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora// Initializes random generator with an amplitude 'dithering' in range [0..1]. 348b720228d581a84fd173b6dcb2fa295b59db489aVikas Aroravoid VP8InitRandom(VP8Random* const rg, float dithering); 358b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora 368b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora// Returns a centered pseudo-random number with 'num_bits' amplitude. 378b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora// (uses D.Knuth's Difference-based random generator). 388b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora// 'amp' is in VP8_RANDOM_DITHER_FIX fixed-point precision. 398b720228d581a84fd173b6dcb2fa295b59db489aVikas Arorastatic WEBP_INLINE int VP8RandomBits2(VP8Random* const rg, int num_bits, 408b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora int amp) { 418b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora int diff; 428b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora assert(num_bits + VP8_RANDOM_DITHER_FIX <= 31); 438b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora diff = rg->tab_[rg->index1_] - rg->tab_[rg->index2_]; 448b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora if (diff < 0) diff += (1u << 31); 458b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora rg->tab_[rg->index1_] = diff; 468b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora if (++rg->index1_ == VP8_RANDOM_TABLE_SIZE) rg->index1_ = 0; 478b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora if (++rg->index2_ == VP8_RANDOM_TABLE_SIZE) rg->index2_ = 0; 48af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora // sign-extend, 0-center 49af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora diff = (int)((uint32_t)diff << 1) >> (32 - num_bits); 508b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora diff = (diff * amp) >> VP8_RANDOM_DITHER_FIX; // restrict range 518b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora diff += 1 << (num_bits - 1); // shift back to 0.5-center 528b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora return diff; 538b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora} 548b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora 558b720228d581a84fd173b6dcb2fa295b59db489aVikas Arorastatic WEBP_INLINE int VP8RandomBits(VP8Random* const rg, int num_bits) { 568b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora return VP8RandomBits2(rg, num_bits, rg->amp_); 578b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora} 588b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora 598b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora#ifdef __cplusplus 608b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora} // extern "C" 618b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora#endif 628b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora 638b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora#endif /* WEBP_UTILS_RANDOM_H_ */ 64