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/platform.h"
  15 #include <brotli/types.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   /* 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. */
 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_ */