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