libavutil/intmath.h

   1 /*
   2  * Copyright (c) 2010 Mans Rullgard <mans@mansr.com>
   3  *
   4  * This file is part of FFmpeg.
   5  *
   6  * FFmpeg is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2.1 of the License, or (at your option) any later version.
  10  *
  11  * FFmpeg is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with FFmpeg; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  19  */
  20
  21 #ifndef AVUTIL_INTMATH_H
  22 #define AVUTIL_INTMATH_H
  23
  24 #include <stdint.h>
  25
  26 #include "config.h"
  27 #include "attributes.h"
  28
  29 #if ARCH_ARM
  30 #   include "arm/intmath.h"
  31 #elif ARCH_RISCV
  32 #   include "riscv/intmath.h"
  33 #elif ARCH_X86
  34 #   include "x86/intmath.h"
  35 #endif
  36
  37 #if HAVE_FAST_CLZ
  38 #if AV_GCC_VERSION_AT_LEAST(3,4) || AV_HAS_BUILTIN(__builtin_clz)
  39 #ifndef ff_log2
  40 #   define ff_log2(x) (31 - __builtin_clz((x)|1))
  41 #   ifndef ff_log2_16bit
  42 #      define ff_log2_16bit av_log2
  43 #   endif
  44 #endif /* ff_log2 */
  45 #endif /* AV_GCC_VERSION_AT_LEAST(3,4) */
  46 #endif
  47
  48 extern const uint8_t ff_log2_tab[256];
  49
  50 #ifndef ff_log2
  51 #define ff_log2 ff_log2_c
  52 static av_always_inline av_const int ff_log2_c(unsigned int v)
  53 {
  54     int n = 0;
  55     if (v & 0xffff0000) {
  56         v >>= 16;
  57         n += 16;
  58     }
  59     if (v & 0xff00) {
  60         v >>= 8;
  61         n += 8;
  62     }
  63     n += ff_log2_tab[v];
  64
  65     return n;
  66 }
  67 #endif
  68
  69 #ifndef ff_log2_16bit
  70 #define ff_log2_16bit ff_log2_16bit_c
  71 static av_always_inline av_const int ff_log2_16bit_c(unsigned int v)
  72 {
  73     int n = 0;
  74     if (v & 0xff00) {
  75         v >>= 8;
  76         n += 8;
  77     }
  78     n += ff_log2_tab[v];
  79
  80     return n;
  81 }
  82 #endif
  83
  84 #define av_log2       ff_log2
  85 #define av_log2_16bit ff_log2_16bit
  86
  87 /**
  88  * @addtogroup lavu_math
  89  * @{
  90  */
  91
  92 #if HAVE_FAST_CLZ
  93 #if !defined(ff_ctz) && (AV_GCC_VERSION_AT_LEAST(3,4) || AV_HAS_BUILTIN(__builtin_ctz))
  94 #define ff_ctz(v) __builtin_ctz(v)
  95 #endif
  96 #if !defined(ff_ctzll) && (AV_GCC_VERSION_AT_LEAST(3,4) || AV_HAS_BUILTIN(__builtin_ctzll))
  97 #define ff_ctzll(v) __builtin_ctzll(v)
  98 #endif
  99 #if !defined(ff_clz) && (AV_GCC_VERSION_AT_LEAST(3,4) || AV_HAS_BUILTIN(__builtin_clz))
 100 #define ff_clz(v) __builtin_clz(v)
 101 #endif
 102 #endif
 103
 104 #ifndef ff_ctz
 105 #define ff_ctz ff_ctz_c
 106 /**
 107  * Trailing zero bit count.
 108  *
 109  * @param v  input value. If v is 0, the result is undefined.
 110  * @return   the number of trailing 0-bits
 111  */
 112 /* We use the De-Bruijn method outlined in:
 113  * http://supertech.csail.mit.edu/papers/debruijn.pdf. */
 114 static av_always_inline av_const int ff_ctz_c(int v)
 115 {
 116     static const uint8_t debruijn_ctz32[32] = {
 117         0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
 118         31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
 119     };
 120     return debruijn_ctz32[(uint32_t)((v & -(uint32_t)v) * 0x077CB531U) >> 27];
 121 }
 122 #endif
 123
 124 #ifndef ff_ctzll
 125 #define ff_ctzll ff_ctzll_c
 126 /* We use the De-Bruijn method outlined in:
 127  * http://supertech.csail.mit.edu/papers/debruijn.pdf. */
 128 static av_always_inline av_const int ff_ctzll_c(long long v)
 129 {
 130     static const uint8_t debruijn_ctz64[64] = {
 131         0, 1, 2, 53, 3, 7, 54, 27, 4, 38, 41, 8, 34, 55, 48, 28,
 132         62, 5, 39, 46, 44, 42, 22, 9, 24, 35, 59, 56, 49, 18, 29, 11,
 133         63, 52, 6, 26, 37, 40, 33, 47, 61, 45, 43, 21, 23, 58, 17, 10,
 134         51, 25, 36, 32, 60, 20, 57, 16, 50, 31, 19, 15, 30, 14, 13, 12
 135     };
 136     return debruijn_ctz64[(uint64_t)((v & -(uint64_t)v) * 0x022FDD63CC95386DU) >> 58];
 137 }
 138 #endif
 139
 140 #ifndef ff_clz
 141 #define ff_clz ff_clz_c
 142 static av_always_inline av_const unsigned ff_clz_c(unsigned x)
 143 {
 144     unsigned i = sizeof(x) * 8;
 145
 146     while (x) {
 147         x >>= 1;
 148         i--;
 149     }
 150
 151     return i;
 152 }
 153 #endif
 154
 155 #if AV_GCC_VERSION_AT_LEAST(3,4) || AV_HAS_BUILTIN(__builtin_parity)
 156 #ifndef av_parity
 157 #define av_parity __builtin_parity
 158 #endif
 159 #endif
 160
 161 /**
 162  * @}
 163  */
 164 #endif /* AVUTIL_INTMATH_H */