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

Generated on Thu Feb 12 14:16:06 2009 for spandsp by  doxygen 1.5.5