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