BaseTools/Source/C/BrotliCompress/enc/fast_log.h

   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/types.h"
  15 #include "../common/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 #ifdef __GNUC__
  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_ */