bit_operations.h

Go to the documentation of this file.
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 ------------------------------------------------------------*/

Generated on Fri Apr 15 16:14:38 2011 for spandsp by  doxygen 1.4.7