1// Copyright 2013 Google Inc. All Rights Reserved.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14//
15// Utilities for fast computation of logarithms.
16
17#ifndef BROTLI_ENC_FAST_LOG_H_
18#define BROTLI_ENC_FAST_LOG_H_
19
20#include <math.h>
21#include <stdint.h>
22
23namespace brotli {
24
25// Return floor(log2(n)) for positive integer n.  Returns -1 iff n == 0.
26inline int Log2Floor(uint32_t n) {
27#if defined(__clang__) ||                       \
28  (defined(__GNUC__) &&                                         \
29   ((__GNUC__ == 3 && __GNUC_MINOR__ >= 4) || __GNUC__ >= 4))
30  return n == 0 ? -1 : 31 ^ __builtin_clz(n);
31#else
32  if (n == 0)
33    return -1;
34  int log = 0;
35  uint32_t value = n;
36  for (int i = 4; i >= 0; --i) {
37    int shift = (1 << i);
38    uint32_t x = value >> shift;
39    if (x != 0) {
40      value = x;
41      log += shift;
42    }
43  }
44  assert(value == 1);
45  return log;
46#endif
47}
48
49// Return ceiling(log2(n)) for positive integer n.  Returns -1 iff n == 0.
50inline int Log2Ceiling(uint32_t n) {
51  int floor = Log2Floor(n);
52  if (n == (n &~ (n - 1)))              // zero or a power of two
53    return floor;
54  else
55    return floor + 1;
56}
57
58// A lookup table for small values of log2(int) to be used in entropy
59// computation.
60//
61// ", ".join(["%.16ff" % x for x in [0.0]+[log2(x) for x in range(1, 256)]])
62static const float kLog2Table[] = {
63  0.0000000000000000f, 0.0000000000000000f, 1.0000000000000000f,
64  1.5849625007211563f, 2.0000000000000000f, 2.3219280948873622f,
65  2.5849625007211561f, 2.8073549220576042f, 3.0000000000000000f,
66  3.1699250014423126f, 3.3219280948873626f, 3.4594316186372978f,
67  3.5849625007211565f, 3.7004397181410922f, 3.8073549220576037f,
68  3.9068905956085187f, 4.0000000000000000f, 4.0874628412503400f,
69  4.1699250014423122f, 4.2479275134435852f, 4.3219280948873626f,
70  4.3923174227787607f, 4.4594316186372973f, 4.5235619560570131f,
71  4.5849625007211570f, 4.6438561897747244f, 4.7004397181410926f,
72  4.7548875021634691f, 4.8073549220576037f, 4.8579809951275728f,
73  4.9068905956085187f, 4.9541963103868758f, 5.0000000000000000f,
74  5.0443941193584534f, 5.0874628412503400f, 5.1292830169449664f,
75  5.1699250014423122f, 5.2094533656289501f, 5.2479275134435852f,
76  5.2854022188622487f, 5.3219280948873626f, 5.3575520046180838f,
77  5.3923174227787607f, 5.4262647547020979f, 5.4594316186372973f,
78  5.4918530963296748f, 5.5235619560570131f, 5.5545888516776376f,
79  5.5849625007211570f, 5.6147098441152083f, 5.6438561897747244f,
80  5.6724253419714961f, 5.7004397181410926f, 5.7279204545631996f,
81  5.7548875021634691f, 5.7813597135246599f, 5.8073549220576046f,
82  5.8328900141647422f, 5.8579809951275719f, 5.8826430493618416f,
83  5.9068905956085187f, 5.9307373375628867f, 5.9541963103868758f,
84  5.9772799234999168f, 6.0000000000000000f, 6.0223678130284544f,
85  6.0443941193584534f, 6.0660891904577721f, 6.0874628412503400f,
86  6.1085244567781700f, 6.1292830169449672f, 6.1497471195046822f,
87  6.1699250014423122f, 6.1898245588800176f, 6.2094533656289510f,
88  6.2288186904958804f, 6.2479275134435861f, 6.2667865406949019f,
89  6.2854022188622487f, 6.3037807481771031f, 6.3219280948873617f,
90  6.3398500028846252f, 6.3575520046180847f, 6.3750394313469254f,
91  6.3923174227787598f, 6.4093909361377026f, 6.4262647547020979f,
92  6.4429434958487288f, 6.4594316186372982f, 6.4757334309663976f,
93  6.4918530963296748f, 6.5077946401986964f, 6.5235619560570131f,
94  6.5391588111080319f, 6.5545888516776376f, 6.5698556083309478f,
95  6.5849625007211561f, 6.5999128421871278f, 6.6147098441152092f,
96  6.6293566200796095f, 6.6438561897747253f, 6.6582114827517955f,
97  6.6724253419714952f, 6.6865005271832185f, 6.7004397181410917f,
98  6.7142455176661224f, 6.7279204545631988f, 6.7414669864011465f,
99  6.7548875021634691f, 6.7681843247769260f, 6.7813597135246599f,
100  6.7944158663501062f, 6.8073549220576037f, 6.8201789624151887f,
101  6.8328900141647422f, 6.8454900509443757f, 6.8579809951275719f,
102  6.8703647195834048f, 6.8826430493618416f, 6.8948177633079437f,
103  6.9068905956085187f, 6.9188632372745955f, 6.9307373375628867f,
104  6.9425145053392399f, 6.9541963103868758f, 6.9657842846620879f,
105  6.9772799234999168f, 6.9886846867721664f, 7.0000000000000000f,
106  7.0112272554232540f, 7.0223678130284544f, 7.0334230015374501f,
107  7.0443941193584534f, 7.0552824355011898f, 7.0660891904577721f,
108  7.0768155970508317f, 7.0874628412503400f, 7.0980320829605272f,
109  7.1085244567781700f, 7.1189410727235076f, 7.1292830169449664f,
110  7.1395513523987937f, 7.1497471195046822f, 7.1598713367783891f,
111  7.1699250014423130f, 7.1799090900149345f, 7.1898245588800176f,
112  7.1996723448363644f, 7.2094533656289492f, 7.2191685204621621f,
113  7.2288186904958804f, 7.2384047393250794f, 7.2479275134435861f,
114  7.2573878426926521f, 7.2667865406949019f, 7.2761244052742384f,
115  7.2854022188622487f, 7.2946207488916270f, 7.3037807481771031f,
116  7.3128829552843557f, 7.3219280948873617f, 7.3309168781146177f,
117  7.3398500028846243f, 7.3487281542310781f, 7.3575520046180847f,
118  7.3663222142458151f, 7.3750394313469254f, 7.3837042924740528f,
119  7.3923174227787607f, 7.4008794362821844f, 7.4093909361377026f,
120  7.4178525148858991f, 7.4262647547020979f, 7.4346282276367255f,
121  7.4429434958487288f, 7.4512111118323299f, 7.4594316186372973f,
122  7.4676055500829976f, 7.4757334309663976f, 7.4838157772642564f,
123  7.4918530963296748f, 7.4998458870832057f, 7.5077946401986964f,
124  7.5156998382840436f, 7.5235619560570131f, 7.5313814605163119f,
125  7.5391588111080319f, 7.5468944598876373f, 7.5545888516776376f,
126  7.5622424242210728f, 7.5698556083309478f, 7.5774288280357487f,
127  7.5849625007211561f, 7.5924570372680806f, 7.5999128421871278f,
128  7.6073303137496113f, 7.6147098441152075f, 7.6220518194563764f,
129  7.6293566200796095f, 7.6366246205436488f, 7.6438561897747244f,
130  7.6510516911789290f, 7.6582114827517955f, 7.6653359171851765f,
131  7.6724253419714952f, 7.6794800995054464f, 7.6865005271832185f,
132  7.6934869574993252f, 7.7004397181410926f, 7.7073591320808825f,
133  7.7142455176661224f, 7.7210991887071856f, 7.7279204545631996f,
134  7.7347096202258392f, 7.7414669864011465f, 7.7481928495894596f,
135  7.7548875021634691f, 7.7615512324444795f, 7.7681843247769260f,
136  7.7747870596011737f, 7.7813597135246608f, 7.7879025593914317f,
137  7.7944158663501062f, 7.8008998999203047f, 7.8073549220576037f,
138  7.8137811912170374f, 7.8201789624151887f, 7.8265484872909159f,
139  7.8328900141647422f, 7.8392037880969445f, 7.8454900509443757f,
140  7.8517490414160571f, 7.8579809951275719f, 7.8641861446542798f,
141  7.8703647195834048f, 7.8765169465650002f, 7.8826430493618425f,
142  7.8887432488982601f, 7.8948177633079446f, 7.9008668079807496f,
143  7.9068905956085187f, 7.9128893362299619f, 7.9188632372745955f,
144  7.9248125036057813f, 7.9307373375628867f, 7.9366379390025719f,
145  7.9425145053392399f, 7.9483672315846778f, 7.9541963103868758f,
146  7.9600019320680806f, 7.9657842846620870f, 7.9715435539507720f,
147  7.9772799234999168f, 7.9829935746943104f, 7.9886846867721664f,
148  7.9943534368588578f
149};
150
151// Faster logarithm for small integers, with the property of log2(0) == 0.
152static inline double FastLog2(int v) {
153  if (v < (int)(sizeof(kLog2Table) / sizeof(kLog2Table[0]))) {
154    return kLog2Table[v];
155  }
156  return log2(v);
157}
158
159}  // namespace brotli
160
161#endif  // BROTLI_ENC_FAST_LOG_H_
162