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)21 static BROTLI_INLINE uint32_t Log2FloorNonZero(size_t n) {
22 /* TODO: generalize and move to platform.h */
23 #if BROTLI_GNUC_HAS_BUILTIN(__builtin_clz, 3, 4, 0) || \
24 BROTLI_INTEL_VERSION_CHECK(16, 0, 0)
25 return 31u ^ (uint32_t)__builtin_clz((uint32_t)n);
26 #else
27 uint32_t result = 0;
28 while (n >>= 1) result++;
29 return result;
30 #endif
31 }
32
33 /* A lookup table for small values of log2(int) to be used in entropy
34 computation.
35
36 ", ".join(["%.16ff" % x for x in [0.0]+[log2(x) for x in range(1, 256)]]) */
37 static const float kLog2Table[] = {
38 0.0000000000000000f, 0.0000000000000000f, 1.0000000000000000f,
39 1.5849625007211563f, 2.0000000000000000f, 2.3219280948873622f,
40 2.5849625007211561f, 2.8073549220576042f, 3.0000000000000000f,
41 3.1699250014423126f, 3.3219280948873626f, 3.4594316186372978f,
42 3.5849625007211565f, 3.7004397181410922f, 3.8073549220576037f,
43 3.9068905956085187f, 4.0000000000000000f, 4.0874628412503400f,
44 4.1699250014423122f, 4.2479275134435852f, 4.3219280948873626f,
45 4.3923174227787607f, 4.4594316186372973f, 4.5235619560570131f,
46 4.5849625007211570f, 4.6438561897747244f, 4.7004397181410926f,
47 4.7548875021634691f, 4.8073549220576037f, 4.8579809951275728f,
48 4.9068905956085187f, 4.9541963103868758f, 5.0000000000000000f,
49 5.0443941193584534f, 5.0874628412503400f, 5.1292830169449664f,
50 5.1699250014423122f, 5.2094533656289501f, 5.2479275134435852f,
51 5.2854022188622487f, 5.3219280948873626f, 5.3575520046180838f,
52 5.3923174227787607f, 5.4262647547020979f, 5.4594316186372973f,
53 5.4918530963296748f, 5.5235619560570131f, 5.5545888516776376f,
54 5.5849625007211570f, 5.6147098441152083f, 5.6438561897747244f,
55 5.6724253419714961f, 5.7004397181410926f, 5.7279204545631996f,
56 5.7548875021634691f, 5.7813597135246599f, 5.8073549220576046f,
57 5.8328900141647422f, 5.8579809951275719f, 5.8826430493618416f,
58 5.9068905956085187f, 5.9307373375628867f, 5.9541963103868758f,
59 5.9772799234999168f, 6.0000000000000000f, 6.0223678130284544f,
60 6.0443941193584534f, 6.0660891904577721f, 6.0874628412503400f,
61 6.1085244567781700f, 6.1292830169449672f, 6.1497471195046822f,
62 6.1699250014423122f, 6.1898245588800176f, 6.2094533656289510f,
63 6.2288186904958804f, 6.2479275134435861f, 6.2667865406949019f,
64 6.2854022188622487f, 6.3037807481771031f, 6.3219280948873617f,
65 6.3398500028846252f, 6.3575520046180847f, 6.3750394313469254f,
66 6.3923174227787598f, 6.4093909361377026f, 6.4262647547020979f,
67 6.4429434958487288f, 6.4594316186372982f, 6.4757334309663976f,
68 6.4918530963296748f, 6.5077946401986964f, 6.5235619560570131f,
69 6.5391588111080319f, 6.5545888516776376f, 6.5698556083309478f,
70 6.5849625007211561f, 6.5999128421871278f, 6.6147098441152092f,
71 6.6293566200796095f, 6.6438561897747253f, 6.6582114827517955f,
72 6.6724253419714952f, 6.6865005271832185f, 6.7004397181410917f,
73 6.7142455176661224f, 6.7279204545631988f, 6.7414669864011465f,
74 6.7548875021634691f, 6.7681843247769260f, 6.7813597135246599f,
75 6.7944158663501062f, 6.8073549220576037f, 6.8201789624151887f,
76 6.8328900141647422f, 6.8454900509443757f, 6.8579809951275719f,
77 6.8703647195834048f, 6.8826430493618416f, 6.8948177633079437f,
78 6.9068905956085187f, 6.9188632372745955f, 6.9307373375628867f,
79 6.9425145053392399f, 6.9541963103868758f, 6.9657842846620879f,
80 6.9772799234999168f, 6.9886846867721664f, 7.0000000000000000f,
81 7.0112272554232540f, 7.0223678130284544f, 7.0334230015374501f,
82 7.0443941193584534f, 7.0552824355011898f, 7.0660891904577721f,
83 7.0768155970508317f, 7.0874628412503400f, 7.0980320829605272f,
84 7.1085244567781700f, 7.1189410727235076f, 7.1292830169449664f,
85 7.1395513523987937f, 7.1497471195046822f, 7.1598713367783891f,
86 7.1699250014423130f, 7.1799090900149345f, 7.1898245588800176f,
87 7.1996723448363644f, 7.2094533656289492f, 7.2191685204621621f,
88 7.2288186904958804f, 7.2384047393250794f, 7.2479275134435861f,
89 7.2573878426926521f, 7.2667865406949019f, 7.2761244052742384f,
90 7.2854022188622487f, 7.2946207488916270f, 7.3037807481771031f,
91 7.3128829552843557f, 7.3219280948873617f, 7.3309168781146177f,
92 7.3398500028846243f, 7.3487281542310781f, 7.3575520046180847f,
93 7.3663222142458151f, 7.3750394313469254f, 7.3837042924740528f,
94 7.3923174227787607f, 7.4008794362821844f, 7.4093909361377026f,
95 7.4178525148858991f, 7.4262647547020979f, 7.4346282276367255f,
96 7.4429434958487288f, 7.4512111118323299f, 7.4594316186372973f,
97 7.4676055500829976f, 7.4757334309663976f, 7.4838157772642564f,
98 7.4918530963296748f, 7.4998458870832057f, 7.5077946401986964f,
99 7.5156998382840436f, 7.5235619560570131f, 7.5313814605163119f,
100 7.5391588111080319f, 7.5468944598876373f, 7.5545888516776376f,
101 7.5622424242210728f, 7.5698556083309478f, 7.5774288280357487f,
102 7.5849625007211561f, 7.5924570372680806f, 7.5999128421871278f,
103 7.6073303137496113f, 7.6147098441152075f, 7.6220518194563764f,
104 7.6293566200796095f, 7.6366246205436488f, 7.6438561897747244f,
105 7.6510516911789290f, 7.6582114827517955f, 7.6653359171851765f,
106 7.6724253419714952f, 7.6794800995054464f, 7.6865005271832185f,
107 7.6934869574993252f, 7.7004397181410926f, 7.7073591320808825f,
108 7.7142455176661224f, 7.7210991887071856f, 7.7279204545631996f,
109 7.7347096202258392f, 7.7414669864011465f, 7.7481928495894596f,
110 7.7548875021634691f, 7.7615512324444795f, 7.7681843247769260f,
111 7.7747870596011737f, 7.7813597135246608f, 7.7879025593914317f,
112 7.7944158663501062f, 7.8008998999203047f, 7.8073549220576037f,
113 7.8137811912170374f, 7.8201789624151887f, 7.8265484872909159f,
114 7.8328900141647422f, 7.8392037880969445f, 7.8454900509443757f,
115 7.8517490414160571f, 7.8579809951275719f, 7.8641861446542798f,
116 7.8703647195834048f, 7.8765169465650002f, 7.8826430493618425f,
117 7.8887432488982601f, 7.8948177633079446f, 7.9008668079807496f,
118 7.9068905956085187f, 7.9128893362299619f, 7.9188632372745955f,
119 7.9248125036057813f, 7.9307373375628867f, 7.9366379390025719f,
120 7.9425145053392399f, 7.9483672315846778f, 7.9541963103868758f,
121 7.9600019320680806f, 7.9657842846620870f, 7.9715435539507720f,
122 7.9772799234999168f, 7.9829935746943104f, 7.9886846867721664f,
123 7.9943534368588578f
124 };
125
126 #define LOG_2_INV 1.4426950408889634
127
128 /* Faster logarithm for small integers, with the property of log2(0) == 0. */
FastLog2(size_t v)129 static BROTLI_INLINE double FastLog2(size_t v) {
130 if (v < sizeof(kLog2Table) / sizeof(kLog2Table[0])) {
131 return kLog2Table[v];
132 }
133 #if (defined(_MSC_VER) && _MSC_VER <= 1700) || \
134 (defined(__ANDROID_API__) && __ANDROID_API__ < 18)
135 /* Visual Studio 2012 and Android API levels < 18 do not have the log2()
136 * function defined, so we use log() and a multiplication instead. */
137 return log((double)v) * LOG_2_INV;
138 #else
139 return log2((double)v);
140 #endif
141 }
142
143 #if defined(__cplusplus) || defined(c_plusplus)
144 } /* extern "C" */
145 #endif
146
147 #endif /* BROTLI_ENC_FAST_LOG_H_ */
148