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

Generated by  doxygen 1.6.2