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.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 ------------------------------------------------------------*/