src/libFLAC/include/private/bitmath.h

   1 /* libFLAC - Free Lossless Audio Codec library
   2  * Copyright (C) 2001,2002,2003,2004,2005,2006,2007,2008,2009  Josh Coalson
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  *
   8  * - Redistributions of source code must retain the above copyright
   9  * notice, this list of conditions and the following disclaimer.
  10  *
  11  * - Redistributions in binary form must reproduce the above copyright
  12  * notice, this list of conditions and the following disclaimer in the
  13  * documentation and/or other materials provided with the distribution.
  14  *
  15  * - Neither the name of the Xiph.org Foundation nor the names of its
  16  * contributors may be used to endorse or promote products derived from
  17  * this software without specific prior written permission.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  20  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  21  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  22  * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR
  23  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  24  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  25  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  26  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  27  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  28  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  29  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  30  */
  31
  32 #ifndef FLAC__PRIVATE__BITMATH_H
  33 #define FLAC__PRIVATE__BITMATH_H
  34
  35 #include "FLAC/ordinals.h"
  36
  37 /* for CHAR_BIT */
  38 #include <limits.h>
  39 #include "share/compat.h"
  40
  41 #if defined(_MSC_VER) && (_MSC_VER >= 1400)
  42 #include <intrin.h> /* for _BitScanReverse* */
  43 #endif
  44
  45 /* Will never be emitted for MSVC, GCC, Intel compilers */
  46 static inline unsigned int FLAC__clz_soft_uint32(unsigned int word)
  47 {
  48     static const unsigned char byte_to_unary_table[] = {
  49     8, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4,
  50     3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
  51     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
  52     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
  53     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  54     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  55     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  56     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  57     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  58     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  59     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  60     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  61     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  62     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  63     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  64     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  65     };
  66
  67     return (word) > 0xffffff ? byte_to_unary_table[(word) >> 24] :
  68     (word) > 0xffff ? byte_to_unary_table[(word) >> 16] + 8 :
  69     (word) > 0xff ? byte_to_unary_table[(word) >> 8] + 16 :
  70     byte_to_unary_table[(word)] + 24;
  71 }
  72
  73 static inline unsigned int FLAC__clz_uint32(FLAC__uint32 v)
  74 {
  75 /* Never used with input 0 */
  76 #if defined(__INTEL_COMPILER)
  77     return _bit_scan_reverse(n) ^ 31U;
  78 #elif defined(__GNUC__) && (__GNUC__ >= 4 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4))
  79 /* This will translate either to (bsr ^ 31U), clz , ctlz, cntlz, lzcnt depending on
  80  * -march= setting or to a software rutine in exotic machines. */
  81     return __builtin_clz(v);
  82 #elif defined(_MSC_VER) && (_MSC_VER >= 1400)
  83     FLAC__uint32 idx;
  84     _BitScanReverse(&idx, v);
  85     return idx ^ 31U;
  86 #else
  87     return FLAC__clz_soft_uint32(v);
  88 #endif
  89 }
  90
  91 /* This one works with input 0 */
  92 static inline unsigned int FLAC__clz2_uint32(FLAC__uint32 v)
  93 {
  94     if (!v)
  95         return 32;
  96     return FLAC__clz_uint32(v);
  97 }
  98
  99 /* An example of what FLAC__bitmath_ilog2() computes:
 100  *
 101  * ilog2( 0) = undefined
 102  * ilog2( 1) = 0
 103  * ilog2( 2) = 1
 104  * ilog2( 3) = 1
 105  * ilog2( 4) = 2
 106  * ilog2( 5) = 2
 107  * ilog2( 6) = 2
 108  * ilog2( 7) = 2
 109  * ilog2( 8) = 3
 110  * ilog2( 9) = 3
 111  * ilog2(10) = 3
 112  * ilog2(11) = 3
 113  * ilog2(12) = 3
 114  * ilog2(13) = 3
 115  * ilog2(14) = 3
 116  * ilog2(15) = 3
 117  * ilog2(16) = 4
 118  * ilog2(17) = 4
 119  * ilog2(18) = 4
 120  */
 121
 122 static inline unsigned FLAC__bitmath_ilog2(FLAC__uint32 v)
 123 {
 124     return sizeof(FLAC__uint32) * CHAR_BIT  - 1 - FLAC__clz_uint32(v);
 125 }
 126
 127
 128 #ifdef FLAC__INTEGER_ONLY_LIBRARY /*Unused otherwise */
 129
 130 static inline unsigned FLAC__bitmath_ilog2_wide(FLAC__uint64 v)
 131 {
 132     if (v == 0)
 133                 return 0;
 134 #if && defined(__GNUC__) && (__GNUC__ >= 4 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4))
 135     return sizeof(FLAC__uint64) * CHAR_BIT - 1 - __builtin_clzll(v);
 136 /* Sorry, only supported in win64/Itanium.. */
 137 #elif (defined(_MSC_VER) && (_MSC_VER >= 1400)) && (defined(_M_IA64) || defined(_WIN64))
 138     FLAC__uint64 idx;
 139     _BitScanReverse64(&idx, v);
 140     return idx ^ 63U;
 141 #else
 142 /* Brain-damaged compilers will use the fastest possible way that is,
 143     de Bruijn sequences (http://supertech.csail.mit.edu/papers/debruijn.pdf)
 144     (C) Timothy B. Terriberry (tterribe@xiph.org) 2001-2009 LGPL (v2 or later).
 145 */
 146     static const unsigned char DEBRUIJN_IDX64[64]={
 147         0, 1, 2, 7, 3,13, 8,19, 4,25,14,28, 9,34,20,40,
 148         5,17,26,38,15,46,29,48,10,31,35,54,21,50,41,57,
 149         63, 6,12,18,24,27,33,39,16,37,45,47,30,53,49,56,
 150         62,11,23,32,36,44,52,55,61,22,43,51,60,42,59,58
 151     };
 152     int ret;
 153     ret= v>0;
 154     v|= v>>1;
 155     v|= v>>2;
 156     v|= v>>4;
 157     v|= v>>8;
 158     v|= v>>16;
 159     v|= v>>32;
 160     v= (v>>1)+1;
 161     ret+=DEBRUIJN_IDX64[v*0x218A392CD3D5DBF>>58&0x3F];
 162     return ret;
 163 #endif
 164 }
 165 #endif
 166
 167 unsigned FLAC__bitmath_silog2(int v);
 168 unsigned FLAC__bitmath_silog2_wide(FLAC__int64 v);
 169
 170 #endif