bitmath.h

00001 /* libFLAC - Free Lossless Audio Codec library
00002  * Copyright (C) 2001-2009  Josh Coalson
00003  * Copyright (C) 2011-2014  Xiph.Org Foundation
00004  *
00005  * Redistribution and use in source and binary forms, with or without
00006  * modification, are permitted provided that the following conditions
00007  * are met:
00008  *
00009  * - Redistributions of source code must retain the above copyright
00010  * notice, this list of conditions and the following disclaimer.
00011  *
00012  * - Redistributions in binary form must reproduce the above copyright
00013  * notice, this list of conditions and the following disclaimer in the
00014  * documentation and/or other materials provided with the distribution.
00015  *
00016  * - Neither the name of the Xiph.org Foundation nor the names of its
00017  * contributors may be used to endorse or promote products derived from
00018  * this software without specific prior written permission.
00019  *
00020  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
00021  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
00022  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
00023  * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR
00024  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
00025  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
00026  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
00027  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
00028  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00029  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00030  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00031  */
00032 
00033 #ifndef FLAC__PRIVATE__BITMATH_H
00034 #define FLAC__PRIVATE__BITMATH_H
00035 
00036 #include "FLAC/ordinals.h"
00037 #include "FLAC/assert.h"
00038 
00039 /* for CHAR_BIT */
00040 #include <limits.h>
00041 #include "share/compat.h"
00042 
00043 #if defined(_MSC_VER) && (_MSC_VER >= 1400)
00044 #include <intrin.h> /* for _BitScanReverse* */
00045 #endif
00046 
00047 /* Will never be emitted for MSVC, GCC, Intel compilers */
00048 static inline unsigned int FLAC__clz_soft_uint32(unsigned int word)
00049 {
00050     static const unsigned char byte_to_unary_table[] = {
00051     8, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4,
00052     3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
00053     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
00054     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
00055     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
00056     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
00057     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
00058     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
00059     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
00060     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
00061     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
00062     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
00063     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
00064     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
00065     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
00066     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
00067     };
00068 
00069     return (word) > 0xffffff ? byte_to_unary_table[(word) >> 24] :
00070     (word) > 0xffff ? byte_to_unary_table[(word) >> 16] + 8 :
00071     (word) > 0xff ? byte_to_unary_table[(word) >> 8] + 16 :
00072     byte_to_unary_table[(word)] + 24;
00073 }
00074 
00075 static inline unsigned int FLAC__clz_uint32(FLAC__uint32 v)
00076 {
00077 /* Never used with input 0 */
00078     FLAC__ASSERT(v > 0);
00079 #if defined(__INTEL_COMPILER)
00080     return _bit_scan_reverse(v) ^ 31U;
00081 #elif defined(__GNUC__) && (__GNUC__ >= 4 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4))
00082 /* This will translate either to (bsr ^ 31U), clz , ctlz, cntlz, lzcnt depending on
00083  * -march= setting or to a software routine in exotic machines. */
00084     return __builtin_clz(v);
00085 #elif defined(_MSC_VER) && (_MSC_VER >= 1400)
00086     {
00087         unsigned long idx;
00088         _BitScanReverse(&idx, v);
00089         return idx ^ 31U;
00090     }
00091 #else
00092     return FLAC__clz_soft_uint32(v);
00093 #endif
00094 }
00095 
00096 /* This one works with input 0 */
00097 static inline unsigned int FLAC__clz2_uint32(FLAC__uint32 v)
00098 {
00099     if (!v)
00100         return 32;
00101     return FLAC__clz_uint32(v);
00102 }
00103 
00104 /* An example of what FLAC__bitmath_ilog2() computes:
00105  *
00106  * ilog2( 0) = assertion failure
00107  * ilog2( 1) = 0
00108  * ilog2( 2) = 1
00109  * ilog2( 3) = 1
00110  * ilog2( 4) = 2
00111  * ilog2( 5) = 2
00112  * ilog2( 6) = 2
00113  * ilog2( 7) = 2
00114  * ilog2( 8) = 3
00115  * ilog2( 9) = 3
00116  * ilog2(10) = 3
00117  * ilog2(11) = 3
00118  * ilog2(12) = 3
00119  * ilog2(13) = 3
00120  * ilog2(14) = 3
00121  * ilog2(15) = 3
00122  * ilog2(16) = 4
00123  * ilog2(17) = 4
00124  * ilog2(18) = 4
00125  */
00126 
00127 static inline unsigned FLAC__bitmath_ilog2(FLAC__uint32 v)
00128 {
00129     FLAC__ASSERT(v > 0);
00130 #if defined(__INTEL_COMPILER)
00131     return _bit_scan_reverse(v);
00132 #elif defined(_MSC_VER) && (_MSC_VER >= 1400)
00133     {
00134         unsigned long idx;
00135         _BitScanReverse(&idx, v);
00136         return idx;
00137     }
00138 #else
00139     return sizeof(FLAC__uint32) * CHAR_BIT  - 1 - FLAC__clz_uint32(v);
00140 #endif
00141 }
00142 
00143 
00144 #ifdef FLAC__INTEGER_ONLY_LIBRARY /* Unused otherwise */
00145 
00146 static inline unsigned FLAC__bitmath_ilog2_wide(FLAC__uint64 v)
00147 {
00148     FLAC__ASSERT(v > 0);
00149 #if defined(__GNUC__) && (__GNUC__ >= 4 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4))
00150     return sizeof(FLAC__uint64) * CHAR_BIT - 1 - __builtin_clzll(v);
00151 /* Sorry, only supported in x64/Itanium.. and both have fast FPU which makes integer-only encoder pointless */
00152 #elif (defined(_MSC_VER) && (_MSC_VER >= 1400)) && (defined(_M_IA64) || defined(_M_X64))
00153     {
00154         unsigned long idx;
00155         _BitScanReverse64(&idx, v);
00156         return idx;
00157     }
00158 #else
00159 /*  Brain-damaged compilers will use the fastest possible way that is,
00160     de Bruijn sequences (http://supertech.csail.mit.edu/papers/debruijn.pdf)
00161     (C) Timothy B. Terriberry (tterribe@xiph.org) 2001-2009 CC0 (Public domain).
00162 */
00163     {
00164         static const unsigned char DEBRUIJN_IDX64[64]={
00165             0, 1, 2, 7, 3,13, 8,19, 4,25,14,28, 9,34,20,40,
00166             5,17,26,38,15,46,29,48,10,31,35,54,21,50,41,57,
00167             63, 6,12,18,24,27,33,39,16,37,45,47,30,53,49,56,
00168             62,11,23,32,36,44,52,55,61,22,43,51,60,42,59,58
00169         };
00170         v|= v>>1;
00171         v|= v>>2;
00172         v|= v>>4;
00173         v|= v>>8;
00174         v|= v>>16;
00175         v|= v>>32;
00176         v= (v>>1)+1;
00177         return DEBRUIJN_IDX64[v*0x218A392CD3D5DBF>>58&0x3F];
00178     }
00179 #endif
00180 }
00181 #endif
00182 
00183 unsigned FLAC__bitmath_silog2(int v);
00184 unsigned FLAC__bitmath_silog2_wide(FLAC__int64 v);
00185 
00186 #endif