summaryrefslogtreecommitdiffstats
path: root/modules/brotli/enc/fast_log.h
blob: 2094f13e5569f6748aced864bb342546e3f99955 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/* Copyright 2013 Google Inc. All Rights Reserved.

   Distributed under MIT license.
   See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
*/

/* Utilities for fast computation of logarithms. */

#ifndef BROTLI_ENC_FAST_LOG_H_
#define BROTLI_ENC_FAST_LOG_H_

#include <math.h>

#include "../common/platform.h"
#include <brotli/types.h>

#if defined(__cplusplus) || defined(c_plusplus)
extern "C" {
#endif

static BROTLI_INLINE uint32_t Log2FloorNonZero(size_t n) {
#if defined(BROTLI_BSR32)
  return BROTLI_BSR32((uint32_t)n);
#else
  uint32_t result = 0;
  while (n >>= 1) result++;
  return result;
#endif
}

#define BROTLI_LOG2_TABLE_SIZE 256

/* A lookup table for small values of log2(int) to be used in entropy
   computation. */
BROTLI_INTERNAL extern const double kBrotliLog2Table[BROTLI_LOG2_TABLE_SIZE];

/* Visual Studio 2012 and Android API levels < 18 do not have the log2()
 * function defined, so we use log() and a multiplication instead. */
#if !defined(BROTLI_HAVE_LOG2)
#if ((defined(_MSC_VER) && _MSC_VER <= 1700) || \
     (defined(__ANDROID_API__) && __ANDROID_API__ < 18))
#define BROTLI_HAVE_LOG2 0
#else
#define BROTLI_HAVE_LOG2 1
#endif
#endif

#define LOG_2_INV 1.4426950408889634

/* Faster logarithm for small integers, with the property of log2(0) == 0. */
static BROTLI_INLINE double FastLog2(size_t v) {
  if (v < BROTLI_LOG2_TABLE_SIZE) {
    return kBrotliLog2Table[v];
  }
#if !(BROTLI_HAVE_LOG2)
  return log((double)v) * LOG_2_INV;
#else
  return log2((double)v);
#endif
}

#if defined(__cplusplus) || defined(c_plusplus)
}  /* extern "C" */
#endif

#endif  /* BROTLI_ENC_FAST_LOG_H_ */