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 <brotli/types.h> 15 16 #include "../common/platform.h" 17 18 #if defined(__cplusplus) || defined(c_plusplus) 19 extern "C" { 20 #endif 21 Log2FloorNonZero(size_t n)22static BROTLI_INLINE uint32_t Log2FloorNonZero(size_t n) { 23 #if defined(BROTLI_BSR32) 24 return BROTLI_BSR32((uint32_t)n); 25 #else 26 uint32_t result = 0; 27 while (n >>= 1) result++; 28 return result; 29 #endif 30 } 31 32 #define BROTLI_LOG2_TABLE_SIZE 256 33 34 /* A lookup table for small values of log2(int) to be used in entropy 35 computation. */ 36 BROTLI_INTERNAL extern const double kBrotliLog2Table[BROTLI_LOG2_TABLE_SIZE]; 37 38 /* Visual Studio 2012 and Android API levels < 18 do not have the log2() 39 * function defined, so we use log() and a multiplication instead. */ 40 #if !defined(BROTLI_HAVE_LOG2) 41 #if ((defined(_MSC_VER) && _MSC_VER <= 1700) || \ 42 (defined(__ANDROID_API__) && __ANDROID_API__ < 18)) 43 #define BROTLI_HAVE_LOG2 0 44 #else 45 #define BROTLI_HAVE_LOG2 1 46 #endif 47 #endif 48 49 #define LOG_2_INV 1.4426950408889634 50 51 /* Faster logarithm for small integers, with the property of log2(0) == 0. */ FastLog2(size_t v)52static BROTLI_INLINE double FastLog2(size_t v) { 53 if (v < BROTLI_LOG2_TABLE_SIZE) { 54 return kBrotliLog2Table[v]; 55 } 56 #if !(BROTLI_HAVE_LOG2) 57 return log((double)v) * LOG_2_INV; 58 #else 59 return log2((double)v); 60 #endif 61 } 62 63 #if defined(__cplusplus) || defined(c_plusplus) 64 } /* extern "C" */ 65 #endif 66 67 #endif /* BROTLI_ENC_FAST_LOG_H_ */ 68