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