RetroArch
bitmath.h
Go to the documentation of this file.
1 /* libFLAC - Free Lossless Audio Codec library
2  * Copyright (C) 2001-2009 Josh Coalson
3  * Copyright (C) 2011-2016 Xiph.Org Foundation
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  *
9  * - Redistributions of source code must retain the above copyright
10  * notice, this list of conditions and the following disclaimer.
11  *
12  * - Redistributions in binary form must reproduce the above copyright
13  * notice, this list of conditions and the following disclaimer in the
14  * documentation and/or other materials provided with the distribution.
15  *
16  * - Neither the name of the Xiph.org Foundation nor the names of its
17  * contributors may be used to endorse or promote products derived from
18  * this software without specific prior written permission.
19  *
20  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
23  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR
24  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
25  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
26  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
27  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
28  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
29  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
30  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31  */
32 
33 #ifndef FLAC__PRIVATE__BITMATH_H
34 #define FLAC__PRIVATE__BITMATH_H
35 
36 #include <retro_inline.h>
37 
38 #include "../FLAC/ordinals.h"
39 #include "../FLAC/assert.h"
40 
41 #include "../share/compat.h"
42 
43 #if defined(_MSC_VER)
44 #include <intrin.h> /* for _BitScanReverse* */
45 #endif
46 
47 /* Will never be emitted for MSVC, GCC, Intel compilers */
48 static INLINE unsigned int FLAC__clz_soft_uint32(FLAC__uint32 word)
49 {
50  static const unsigned char byte_to_unary_table[] = {
51  8, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4,
52  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
53  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
54  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
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  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
58  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
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  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
66  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
67  };
68 
69  return word > 0xffffff ? byte_to_unary_table[word >> 24] :
70  word > 0xffff ? byte_to_unary_table[word >> 16] + 8 :
71  word > 0xff ? byte_to_unary_table[word >> 8] + 16 :
72  byte_to_unary_table[word] + 24;
73 }
74 
75 static INLINE unsigned int FLAC__clz_uint32(FLAC__uint32 v)
76 {
77 /* Never used with input 0 */
78  FLAC__ASSERT(v > 0);
79 #if defined(__INTEL_COMPILER)
80  return _bit_scan_reverse(v) ^ 31U;
81 #elif defined(__GNUC__) && (__GNUC__ >= 4 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4))
82 /* This will translate either to (bsr ^ 31U), clz , ctlz, cntlz, lzcnt depending on
83  * -march= setting or to a software routine in exotic machines. */
84  return __builtin_clz(v);
85 #elif defined(_MSC_VER)
86  {
87  unsigned long idx;
88  _BitScanReverse(&idx, v);
89  return idx ^ 31U;
90  }
91 #else
92  return FLAC__clz_soft_uint32(v);
93 #endif
94 }
95 
96 /* Used when 64-bit bsr/clz is unavailable; can use 32-bit bsr/clz when possible */
97 static INLINE unsigned int FLAC__clz_soft_uint64(FLAC__uint64 word)
98 {
99  return (FLAC__uint32)(word>>32) ? FLAC__clz_uint32((FLAC__uint32)(word>>32)) :
100  FLAC__clz_uint32((FLAC__uint32)word) + 32;
101 }
102 
103 static INLINE unsigned int FLAC__clz_uint64(FLAC__uint64 v)
104 {
105  /* Never used with input 0 */
106  FLAC__ASSERT(v > 0);
107 #if defined(__GNUC__) && (__GNUC__ >= 4 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4))
108  return __builtin_clzll(v);
109 #elif (defined(__INTEL_COMPILER) || defined(_MSC_VER)) && (defined(_M_IA64) || defined(_M_X64))
110  {
111  unsigned long idx;
112  _BitScanReverse64(&idx, v);
113  return idx ^ 63U;
114  }
115 #else
116  return FLAC__clz_soft_uint64(v);
117 #endif
118 }
119 
120 /* These two functions work with input 0 */
122 {
123  if (!v)
124  return 32;
125  return FLAC__clz_uint32(v);
126 }
127 
129 {
130  if (!v)
131  return 64;
132  return FLAC__clz_uint64(v);
133 }
134 
135 /* An example of what FLAC__bitmath_ilog2() computes:
136  *
137  * ilog2( 0) = assertion failure
138  * ilog2( 1) = 0
139  * ilog2( 2) = 1
140  * ilog2( 3) = 1
141  * ilog2( 4) = 2
142  * ilog2( 5) = 2
143  * ilog2( 6) = 2
144  * ilog2( 7) = 2
145  * ilog2( 8) = 3
146  * ilog2( 9) = 3
147  * ilog2(10) = 3
148  * ilog2(11) = 3
149  * ilog2(12) = 3
150  * ilog2(13) = 3
151  * ilog2(14) = 3
152  * ilog2(15) = 3
153  * ilog2(16) = 4
154  * ilog2(17) = 4
155  * ilog2(18) = 4
156  */
157 
159 {
160  FLAC__ASSERT(v > 0);
161 #if defined(__INTEL_COMPILER)
162  return _bit_scan_reverse(v);
163 #elif defined(_MSC_VER)
164  {
165  unsigned long idx;
166  _BitScanReverse(&idx, v);
167  return idx;
168  }
169 #else
170  return FLAC__clz_uint32(v) ^ 31U;
171 #endif
172 }
173 
175 {
176  FLAC__ASSERT(v > 0);
177 #if defined(__GNUC__) && (__GNUC__ >= 4 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4))
178  return __builtin_clzll(v) ^ 63U;
179 /* Sorry, only supported in x64/Itanium.. and both have fast FPU which makes integer-only encoder pointless */
180 #elif (defined(__INTEL_COMPILER) || defined(_MSC_VER)) && (defined(_M_IA64) || defined(_M_X64))
181  {
182  unsigned long idx;
183  _BitScanReverse64(&idx, v);
184  return idx;
185  }
186 #else
187 /* Brain-damaged compilers will use the fastest possible way that is,
188  de Bruijn sequences (http://supertech.csail.mit.edu/papers/debruijn.pdf)
189  (C) Timothy B. Terriberry (tterribe@xiph.org) 2001-2009 CC0 (Public domain).
190 */
191  {
192  static const unsigned char DEBRUIJN_IDX64[64]={
193  0, 1, 2, 7, 3,13, 8,19, 4,25,14,28, 9,34,20,40,
194  5,17,26,38,15,46,29,48,10,31,35,54,21,50,41,57,
195  63, 6,12,18,24,27,33,39,16,37,45,47,30,53,49,56,
196  62,11,23,32,36,44,52,55,61,22,43,51,60,42,59,58
197  };
198  v|= v>>1;
199  v|= v>>2;
200  v|= v>>4;
201  v|= v>>8;
202  v|= v>>16;
203  v|= v>>32;
204  v= (v>>1)+1;
205  return DEBRUIJN_IDX64[v*FLAC__U64L(0x218A392CD3D5DBF)>>58&0x3F];
206  }
207 #endif
208 }
209 
211 
212 #endif
static INLINE unsigned int FLAC__clz_soft_uint64(FLAC__uint64 word)
Definition: bitmath.h:97
#define INLINE
Definition: retro_inline.h:35
uint32_t FLAC__uint32
Definition: ordinals.h:65
static INLINE unsigned FLAC__bitmath_ilog2_wide(FLAC__uint64 v)
Definition: bitmath.h:174
unsigned FLAC__bitmath_silog2(FLAC__int64 v)
Definition: bitmath.c:63
int64_t FLAC__int64
Definition: ordinals.h:63
#define FLAC__ASSERT(x)
Definition: assert.h:42
static INLINE unsigned int FLAC__clz_uint64(FLAC__uint64 v)
Definition: bitmath.h:103
#define FLAC__U64L(x)
Definition: compat.h:88
set set set set set set set macro pixldst1 abits if abits op else op endif endm macro pixldst2 abits if abits op else op endif endm macro pixldst4 abits if abits op else op endif endm macro pixldst0 idx
Definition: pixman-arm-neon-asm.h:96
uint64_t FLAC__uint64
Definition: ordinals.h:66
const GLdouble * v
Definition: glext.h:6391
static INLINE unsigned FLAC__bitmath_ilog2(FLAC__uint32 v)
Definition: bitmath.h:158
static INLINE unsigned int FLAC__clz2_uint32(FLAC__uint32 v)
Definition: bitmath.h:121
static INLINE unsigned int FLAC__clz2_uint64(FLAC__uint64 v)
Definition: bitmath.h:128
static INLINE unsigned int FLAC__clz_uint32(FLAC__uint32 v)
Definition: bitmath.h:75
static INLINE unsigned int FLAC__clz_soft_uint32(FLAC__uint32 word)
Definition: bitmath.h:48