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)
18extern "C" {
19#endif
20
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. */
35BROTLI_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. */
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