spandsp 0.0.6
|
00001 /* 00002 * SpanDSP - a series of DSP components for telephony 00003 * 00004 * bit_operations.h - Various bit level operations, such as bit reversal 00005 * 00006 * Written by Steve Underwood <steveu@coppice.org> 00007 * 00008 * Copyright (C) 2006 Steve Underwood 00009 * 00010 * All rights reserved. 00011 * 00012 * This program is free software; you can redistribute it and/or modify 00013 * it under the terms of the GNU Lesser General Public License version 2.1, 00014 * as published by the Free Software Foundation. 00015 * 00016 * This program is distributed in the hope that it will be useful, 00017 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00018 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00019 * GNU Lesser General Public License for more details. 00020 * 00021 * You should have received a copy of the GNU Lesser General Public 00022 * License along with this program; if not, write to the Free Software 00023 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 00024 */ 00025 00026 /*! \file */ 00027 00028 #if !defined(_SPANDSP_BIT_OPERATIONS_H_) 00029 #define _SPANDSP_BIT_OPERATIONS_H_ 00030 00031 #if defined(__i386__) || defined(__x86_64__) 00032 #if !defined(__SUNPRO_C) || (__SUNPRO_C >= 0x0590) 00033 #define SPANDSP_USE_86_ASM 00034 #endif 00035 #endif 00036 00037 #if defined(__cplusplus) 00038 extern "C" 00039 { 00040 #endif 00041 00042 /*! \brief Find the bit position of the highest set bit in a word 00043 \param bits The word to be searched 00044 \return The bit number of the highest set bit, or -1 if the word is zero. */ 00045 static __inline__ int top_bit(unsigned int bits) 00046 { 00047 #if defined(SPANDSP_USE_86_ASM) 00048 int res; 00049 00050 __asm__ (" xorl %[res],%[res];\n" 00051 " decl %[res];\n" 00052 " bsrl %[bits],%[res]\n" 00053 : [res] "=&r" (res) 00054 : [bits] "rm" (bits)); 00055 return res; 00056 #elif defined(__ppc__) || defined(__powerpc__) 00057 int res; 00058 00059 __asm__ ("cntlzw %[res],%[bits];\n" 00060 : [res] "=&r" (res) 00061 : [bits] "r" (bits)); 00062 return 31 - res; 00063 #elif defined(_M_IX86) 00064 /* Visual Studio i386 */ 00065 __asm 00066 { 00067 xor eax, eax 00068 dec eax 00069 bsr eax, bits 00070 } 00071 #elif defined(_M_X64) 00072 /* Visual Studio x86_64 */ 00073 /* TODO: Need the appropriate x86_64 code */ 00074 int res; 00075 00076 if (bits == 0) 00077 return -1; 00078 res = 0; 00079 if (bits & 0xFFFF0000) 00080 { 00081 bits &= 0xFFFF0000; 00082 res += 16; 00083 } 00084 if (bits & 0xFF00FF00) 00085 { 00086 bits &= 0xFF00FF00; 00087 res += 8; 00088 } 00089 if (bits & 0xF0F0F0F0) 00090 { 00091 bits &= 0xF0F0F0F0; 00092 res += 4; 00093 } 00094 if (bits & 0xCCCCCCCC) 00095 { 00096 bits &= 0xCCCCCCCC; 00097 res += 2; 00098 } 00099 if (bits & 0xAAAAAAAA) 00100 { 00101 bits &= 0xAAAAAAAA; 00102 res += 1; 00103 } 00104 return res; 00105 #else 00106 int res; 00107 00108 if (bits == 0) 00109 return -1; 00110 res = 0; 00111 if (bits & 0xFFFF0000) 00112 { 00113 bits &= 0xFFFF0000; 00114 res += 16; 00115 } 00116 if (bits & 0xFF00FF00) 00117 { 00118 bits &= 0xFF00FF00; 00119 res += 8; 00120 } 00121 if (bits & 0xF0F0F0F0) 00122 { 00123 bits &= 0xF0F0F0F0; 00124 res += 4; 00125 } 00126 if (bits & 0xCCCCCCCC) 00127 { 00128 bits &= 0xCCCCCCCC; 00129 res += 2; 00130 } 00131 if (bits & 0xAAAAAAAA) 00132 { 00133 bits &= 0xAAAAAAAA; 00134 res += 1; 00135 } 00136 return res; 00137 #endif 00138 } 00139 /*- End of function --------------------------------------------------------*/ 00140 00141 /*! \brief Find the bit position of the lowest set bit in a word 00142 \param bits The word to be searched 00143 \return The bit number of the lowest set bit, or -1 if the word is zero. */ 00144 static __inline__ int bottom_bit(unsigned int bits) 00145 { 00146 int res; 00147 00148 #if defined(SPANDSP_USE_86_ASM) 00149 __asm__ (" xorl %[res],%[res];\n" 00150 " decl %[res];\n" 00151 " bsfl %[bits],%[res]\n" 00152 : [res] "=&r" (res) 00153 : [bits] "rm" (bits)); 00154 return res; 00155 #else 00156 if (bits == 0) 00157 return -1; 00158 res = 31; 00159 if (bits & 0x0000FFFF) 00160 { 00161 bits &= 0x0000FFFF; 00162 res -= 16; 00163 } 00164 if (bits & 0x00FF00FF) 00165 { 00166 bits &= 0x00FF00FF; 00167 res -= 8; 00168 } 00169 if (bits & 0x0F0F0F0F) 00170 { 00171 bits &= 0x0F0F0F0F; 00172 res -= 4; 00173 } 00174 if (bits & 0x33333333) 00175 { 00176 bits &= 0x33333333; 00177 res -= 2; 00178 } 00179 if (bits & 0x55555555) 00180 { 00181 bits &= 0x55555555; 00182 res -= 1; 00183 } 00184 return res; 00185 #endif 00186 } 00187 /*- End of function --------------------------------------------------------*/ 00188 00189 /*! \brief Bit reverse a byte. 00190 \param data The byte to be reversed. 00191 \return The bit reversed version of data. */ 00192 static __inline__ uint8_t bit_reverse8(uint8_t x) 00193 { 00194 #if defined(__i386__) || defined(__x86_64__) || defined(__ppc__) || defined(__powerpc__) 00195 /* If multiply is fast */ 00196 return ((x*0x0802U & 0x22110U) | (x*0x8020U & 0x88440U))*0x10101U >> 16; 00197 #else 00198 /* If multiply is slow, but we have a barrel shifter */ 00199 x = (x >> 4) | (x << 4); 00200 x = ((x & 0xCC) >> 2) | ((x & 0x33) << 2); 00201 return ((x & 0xAA) >> 1) | ((x & 0x55) << 1); 00202 #endif 00203 } 00204 /*- End of function --------------------------------------------------------*/ 00205 00206 /*! \brief Bit reverse a 16 bit word. 00207 \param data The word to be reversed. 00208 \return The bit reversed version of data. */ 00209 SPAN_DECLARE(uint16_t) bit_reverse16(uint16_t data); 00210 00211 /*! \brief Bit reverse a 32 bit word. 00212 \param data The word to be reversed. 00213 \return The bit reversed version of data. */ 00214 SPAN_DECLARE(uint32_t) bit_reverse32(uint32_t data); 00215 00216 /*! \brief Bit reverse each of the four bytes in a 32 bit word. 00217 \param data The word to be reversed. 00218 \return The bit reversed version of data. */ 00219 SPAN_DECLARE(uint32_t) bit_reverse_4bytes(uint32_t data); 00220 00221 #if defined(__x86_64__) 00222 /*! \brief Bit reverse each of the eight bytes in a 64 bit word. 00223 \param data The word to be reversed. 00224 \return The bit reversed version of data. */ 00225 SPAN_DECLARE(uint64_t) bit_reverse_8bytes(uint64_t data); 00226 #endif 00227 00228 /*! \brief Bit reverse each bytes in a buffer. 00229 \param to The buffer to place the reversed data in. 00230 \param from The buffer containing the data to be reversed. 00231 \param len The length of the data in the buffer. */ 00232 SPAN_DECLARE(void) bit_reverse(uint8_t to[], const uint8_t from[], int len); 00233 00234 /*! \brief Find the number of set bits in a 32 bit word. 00235 \param x The word to be searched. 00236 \return The number of set bits. */ 00237 SPAN_DECLARE(int) one_bits32(uint32_t x); 00238 00239 /*! \brief Create a mask as wide as the number in a 32 bit word. 00240 \param x The word to be searched. 00241 \return The mask. */ 00242 SPAN_DECLARE(uint32_t) make_mask32(uint32_t x); 00243 00244 /*! \brief Create a mask as wide as the number in a 16 bit word. 00245 \param x The word to be searched. 00246 \return The mask. */ 00247 SPAN_DECLARE(uint16_t) make_mask16(uint16_t x); 00248 00249 /*! \brief Find the least significant one in a word, and return a word 00250 with just that bit set. 00251 \param x The word to be searched. 00252 \return The word with the single set bit. */ 00253 static __inline__ uint32_t least_significant_one32(uint32_t x) 00254 { 00255 return (x & (-(int32_t) x)); 00256 } 00257 /*- End of function --------------------------------------------------------*/ 00258 00259 /*! \brief Find the most significant one in a word, and return a word 00260 with just that bit set. 00261 \param x The word to be searched. 00262 \return The word with the single set bit. */ 00263 static __inline__ uint32_t most_significant_one32(uint32_t x) 00264 { 00265 #if defined(__i386__) || defined(__x86_64__) || defined(__ppc__) || defined(__powerpc__) 00266 return 1 << top_bit(x); 00267 #else 00268 x = make_mask32(x); 00269 return (x ^ (x >> 1)); 00270 #endif 00271 } 00272 /*- End of function --------------------------------------------------------*/ 00273 00274 /*! \brief Find the parity of a byte. 00275 \param x The byte to be checked. 00276 \return 1 for odd, or 0 for even. */ 00277 static __inline__ int parity8(uint8_t x) 00278 { 00279 x = (x ^ (x >> 4)) & 0x0F; 00280 return (0x6996 >> x) & 1; 00281 } 00282 /*- End of function --------------------------------------------------------*/ 00283 00284 /*! \brief Find the parity of a 16 bit word. 00285 \param x The word to be checked. 00286 \return 1 for odd, or 0 for even. */ 00287 static __inline__ int parity16(uint16_t x) 00288 { 00289 x ^= (x >> 8); 00290 x = (x ^ (x >> 4)) & 0x0F; 00291 return (0x6996 >> x) & 1; 00292 } 00293 /*- End of function --------------------------------------------------------*/ 00294 00295 /*! \brief Find the parity of a 32 bit word. 00296 \param x The word to be checked. 00297 \return 1 for odd, or 0 for even. */ 00298 static __inline__ int parity32(uint32_t x) 00299 { 00300 x ^= (x >> 16); 00301 x ^= (x >> 8); 00302 x = (x ^ (x >> 4)) & 0x0F; 00303 return (0x6996 >> x) & 1; 00304 } 00305 /*- End of function --------------------------------------------------------*/ 00306 00307 #if defined(__cplusplus) 00308 } 00309 #endif 00310 00311 #endif 00312 /*- End of file ------------------------------------------------------------*/