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 #include <brotli/types.h> 16 17 #if defined(__cplusplus) || defined(c_plusplus) 18 extern "C" { 19 #endif 20 Log2FloorNonZero(size_t n)21static BROTLI_INLINE uint32_t Log2FloorNonZero(size_t n) { 22 #if defined(BROTLI_BSR32) 23 return BROTLI_BSR32((uint32_t)n); 24 #else 25 uint32_t result = 0; 26 while (n >>= 1) result++; 27 return result; 28 #endif 29 } 30 31 #define BROTLI_LOG2_TABLE_SIZE 256 32 33 /* A lookup table for small values of log2(int) to be used in entropy 34 computation. */ 35 BROTLI_INTERNAL extern const 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. */ FastLog2(size_t v)51static 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_ */ 67