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