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 * $Id: bit_operations.h,v 1.27 2009/07/10 13:15:56 steveu Exp $ 00026 */ 00027 00028 /*! \file */ 00029 00030 #if !defined(_SPANDSP_BIT_OPERATIONS_H_) 00031 #define _SPANDSP_BIT_OPERATIONS_H_ 00032 00033 #if defined(__i386__) || defined(__x86_64__) 00034 #if !defined(__SUNPRO_C) || (__SUNPRO_C >= 0x0590) 00035 #define SPANDSP_USE_86_ASM 00036 #endif 00037 #endif 00038 00039 #if defined(__cplusplus) 00040 extern "C" 00041 { 00042 #endif 00043 00044 /*! \brief Find the bit position of the highest set bit in a word 00045 \param bits The word to be searched 00046 \return The bit number of the highest set bit, or -1 if the word is zero. */ 00047 static __inline__ int top_bit(unsigned int bits) 00048 { 00049 #if defined(SPANDSP_USE_86_ASM) 00050 int res; 00051 00052 __asm__ (" xorl %[res],%[res];\n" 00053 " decl %[res];\n" 00054 " bsrl %[bits],%[res]\n" 00055 : [res] "=&r" (res) 00056 : [bits] "rm" (bits)); 00057 return res; 00058 #elif defined(__ppc__) || defined(__powerpc__) 00059 int res; 00060 00061 __asm__ ("cntlzw %[res],%[bits];\n" 00062 : [res] "=&r" (res) 00063 : [bits] "r" (bits)); 00064 return 31 - res; 00065 #elif defined(_M_IX86) 00066 /* Visual Studio i386 */ 00067 __asm 00068 { 00069 xor eax, eax 00070 dec eax 00071 bsr eax, bits 00072 } 00073 #elif defined(_M_X64) 00074 /* Visual Studio x86_64 */ 00075 /* TODO: Need the appropriate x86_64 code */ 00076 int res; 00077 00078 if (bits == 0) 00079 return -1; 00080 res = 0; 00081 if (bits & 0xFFFF0000) 00082 { 00083 bits &= 0xFFFF0000; 00084 res += 16; 00085 } 00086 if (bits & 0xFF00FF00) 00087 { 00088 bits &= 0xFF00FF00; 00089 res += 8; 00090 } 00091 if (bits & 0xF0F0F0F0) 00092 { 00093 bits &= 0xF0F0F0F0; 00094 res += 4; 00095 } 00096 if (bits & 0xCCCCCCCC) 00097 { 00098 bits &= 0xCCCCCCCC; 00099 res += 2; 00100 } 00101 if (bits & 0xAAAAAAAA) 00102 { 00103 bits &= 0xAAAAAAAA; 00104 res += 1; 00105 } 00106 return res; 00107 #else 00108 int res; 00109 00110 if (bits == 0) 00111 return -1; 00112 res = 0; 00113 if (bits & 0xFFFF0000) 00114 { 00115 bits &= 0xFFFF0000; 00116 res += 16; 00117 } 00118 if (bits & 0xFF00FF00) 00119 { 00120 bits &= 0xFF00FF00; 00121 res += 8; 00122 } 00123 if (bits & 0xF0F0F0F0) 00124 { 00125 bits &= 0xF0F0F0F0; 00126 res += 4; 00127 } 00128 if (bits & 0xCCCCCCCC) 00129 { 00130 bits &= 0xCCCCCCCC; 00131 res += 2; 00132 } 00133 if (bits & 0xAAAAAAAA) 00134 { 00135 bits &= 0xAAAAAAAA; 00136 res += 1; 00137 } 00138 return res; 00139 #endif 00140 } 00141 /*- End of function --------------------------------------------------------*/ 00142 00143 /*! \brief Find the bit position of the lowest set bit in a word 00144 \param bits The word to be searched 00145 \return The bit number of the lowest set bit, or -1 if the word is zero. */ 00146 static __inline__ int bottom_bit(unsigned int bits) 00147 { 00148 int res; 00149 00150 #if defined(SPANDSP_USE_86_ASM) 00151 __asm__ (" xorl %[res],%[res];\n" 00152 " decl %[res];\n" 00153 " bsfl %[bits],%[res]\n" 00154 : [res] "=&r" (res) 00155 : [bits] "rm" (bits)); 00156 return res; 00157 #else 00158 if (bits == 0) 00159 return -1; 00160 res = 31; 00161 if (bits & 0x0000FFFF) 00162 { 00163 bits &= 0x0000FFFF; 00164 res -= 16; 00165 } 00166 if (bits & 0x00FF00FF) 00167 { 00168 bits &= 0x00FF00FF; 00169 res -= 8; 00170 } 00171 if (bits & 0x0F0F0F0F) 00172 { 00173 bits &= 0x0F0F0F0F; 00174 res -= 4; 00175 } 00176 if (bits & 0x33333333) 00177 { 00178 bits &= 0x33333333; 00179 res -= 2; 00180 } 00181 if (bits & 0x55555555) 00182 { 00183 bits &= 0x55555555; 00184 res -= 1; 00185 } 00186 return res; 00187 #endif 00188 } 00189 /*- End of function --------------------------------------------------------*/ 00190 00191 /*! \brief Bit reverse a byte. 00192 \param data The byte to be reversed. 00193 \return The bit reversed version of data. */ 00194 static __inline__ uint8_t bit_reverse8(uint8_t x) 00195 { 00196 #if defined(__i386__) || defined(__x86_64__) || defined(__ppc__) || defined(__powerpc__) 00197 /* If multiply is fast */ 00198 return ((x*0x0802U & 0x22110U) | (x*0x8020U & 0x88440U))*0x10101U >> 16; 00199 #else 00200 /* If multiply is slow, but we have a barrel shifter */ 00201 x = (x >> 4) | (x << 4); 00202 x = ((x & 0xCC) >> 2) | ((x & 0x33) << 2); 00203 return ((x & 0xAA) >> 1) | ((x & 0x55) << 1); 00204 #endif 00205 } 00206 /*- End of function --------------------------------------------------------*/ 00207 00208 /*! \brief Bit reverse a 16 bit word. 00209 \param data The word to be reversed. 00210 \return The bit reversed version of data. */ 00211 SPAN_DECLARE(uint16_t) bit_reverse16(uint16_t data); 00212 00213 /*! \brief Bit reverse a 32 bit word. 00214 \param data The word to be reversed. 00215 \return The bit reversed version of data. */ 00216 SPAN_DECLARE(uint32_t) bit_reverse32(uint32_t data); 00217 00218 /*! \brief Bit reverse each of the four bytes in a 32 bit word. 00219 \param data The word to be reversed. 00220 \return The bit reversed version of data. */ 00221 SPAN_DECLARE(uint32_t) bit_reverse_4bytes(uint32_t data); 00222 00223 #if defined(__x86_64__) 00224 /*! \brief Bit reverse each of the eight bytes in a 64 bit word. 00225 \param data The word to be reversed. 00226 \return The bit reversed version of data. */ 00227 SPAN_DECLARE(uint64_t) bit_reverse_8bytes(uint64_t data); 00228 #endif 00229 00230 /*! \brief Bit reverse each bytes in a buffer. 00231 \param to The buffer to place the reversed data in. 00232 \param from The buffer containing the data to be reversed. 00233 \param len The length of the data in the buffer. */ 00234 SPAN_DECLARE(void) bit_reverse(uint8_t to[], const uint8_t from[], int len); 00235 00236 /*! \brief Find the number of set bits in a 32 bit word. 00237 \param x The word to be searched. 00238 \return The number of set bits. */ 00239 SPAN_DECLARE(int) one_bits32(uint32_t x); 00240 00241 /*! \brief Create a mask as wide as the number in a 32 bit word. 00242 \param x The word to be searched. 00243 \return The mask. */ 00244 SPAN_DECLARE(uint32_t) make_mask32(uint32_t x); 00245 00246 /*! \brief Create a mask as wide as the number in a 16 bit word. 00247 \param x The word to be searched. 00248 \return The mask. */ 00249 SPAN_DECLARE(uint16_t) make_mask16(uint16_t x); 00250 00251 /*! \brief Find the least significant one in a word, and return a word 00252 with just that bit set. 00253 \param x The word to be searched. 00254 \return The word with the single set bit. */ 00255 static __inline__ uint32_t least_significant_one32(uint32_t x) 00256 { 00257 return (x & (-(int32_t) x)); 00258 } 00259 /*- End of function --------------------------------------------------------*/ 00260 00261 /*! \brief Find the most significant one in a word, and return a word 00262 with just that bit set. 00263 \param x The word to be searched. 00264 \return The word with the single set bit. */ 00265 static __inline__ uint32_t most_significant_one32(uint32_t x) 00266 { 00267 #if defined(__i386__) || defined(__x86_64__) || defined(__ppc__) || defined(__powerpc__) 00268 return 1 << top_bit(x); 00269 #else 00270 x = make_mask32(x); 00271 return (x ^ (x >> 1)); 00272 #endif 00273 } 00274 /*- End of function --------------------------------------------------------*/ 00275 00276 /*! \brief Find the parity of a byte. 00277 \param x The byte to be checked. 00278 \return 1 for odd, or 0 for even. */ 00279 static __inline__ int parity8(uint8_t x) 00280 { 00281 x = (x ^ (x >> 4)) & 0x0F; 00282 return (0x6996 >> x) & 1; 00283 } 00284 /*- End of function --------------------------------------------------------*/ 00285 00286 /*! \brief Find the parity of a 16 bit word. 00287 \param x The word to be checked. 00288 \return 1 for odd, or 0 for even. */ 00289 static __inline__ int parity16(uint16_t x) 00290 { 00291 x ^= (x >> 8); 00292 x = (x ^ (x >> 4)) & 0x0F; 00293 return (0x6996 >> x) & 1; 00294 } 00295 /*- End of function --------------------------------------------------------*/ 00296 00297 /*! \brief Find the parity of a 32 bit word. 00298 \param x The word to be checked. 00299 \return 1 for odd, or 0 for even. */ 00300 static __inline__ int parity32(uint32_t x) 00301 { 00302 x ^= (x >> 16); 00303 x ^= (x >> 8); 00304 x = (x ^ (x >> 4)) & 0x0F; 00305 return (0x6996 >> x) & 1; 00306 } 00307 /*- End of function --------------------------------------------------------*/ 00308 00309 #if defined(__cplusplus) 00310 } 00311 #endif 00312 00313 #endif 00314 /*- End of file ------------------------------------------------------------*/