fast_log.h (1645B)
1 /* Copyright 2013 Google Inc. All Rights Reserved. 2 3 Distributed under MIT license. 4 See file LICENSE for detail or copy at https://opensource.org/licenses/MIT 5 */ 6 7 /* Utilities for fast computation of logarithms. */ 8 9 #ifndef BROTLI_ENC_FAST_LOG_H_ 10 #define BROTLI_ENC_FAST_LOG_H_ 11 12 #include <math.h> 13 14 #include "../common/platform.h" 15 16 #if defined(__cplusplus) || defined(c_plusplus) 17 extern "C" { 18 #endif 19 20 static BROTLI_INLINE uint32_t Log2FloorNonZero(size_t n) { 21 #if defined(BROTLI_BSR32) 22 return BROTLI_BSR32((uint32_t)n); 23 #else 24 uint32_t result = 0; 25 while (n >>= 1) result++; 26 return result; 27 #endif 28 } 29 30 #define BROTLI_LOG2_TABLE_SIZE 256 31 32 /* A lookup table for small values of log2(int) to be used in entropy 33 computation. */ 34 BROTLI_INTERNAL extern const BROTLI_MODEL("small") 35 double kBrotliLog2Table[BROTLI_LOG2_TABLE_SIZE]; 36 37 /* Visual Studio 2012 and Android API levels < 18 do not have the log2() 38 * function defined, so we use log() and a multiplication instead. */ 39 #if !defined(BROTLI_HAVE_LOG2) 40 #if ((defined(_MSC_VER) && _MSC_VER <= 1700) || \ 41 (defined(__ANDROID_API__) && __ANDROID_API__ < 18)) 42 #define BROTLI_HAVE_LOG2 0 43 #else 44 #define BROTLI_HAVE_LOG2 1 45 #endif 46 #endif 47 48 #define LOG_2_INV 1.4426950408889634 49 50 /* Faster logarithm for small integers, with the property of log2(0) == 0. */ 51 static BROTLI_INLINE double FastLog2(size_t v) { 52 if (v < BROTLI_LOG2_TABLE_SIZE) { 53 return kBrotliLog2Table[v]; 54 } 55 #if !(BROTLI_HAVE_LOG2) 56 return log((double)v) * LOG_2_INV; 57 #else 58 return log2((double)v); 59 #endif 60 } 61 62 #if defined(__cplusplus) || defined(c_plusplus) 63 } /* extern "C" */ 64 #endif 65 66 #endif /* BROTLI_ENC_FAST_LOG_H_ */