drivers/staging/echo/bit_operations.h

   1 /*
   2  * SpanDSP - a series of DSP components for telephony
   3  *
   4  * bit_operations.h - Various bit level operations, such as bit reversal
   5  *
   6  * Written by Steve Underwood <steveu@coppice.org>
   7  *
   8  * Copyright (C) 2006 Steve Underwood
   9  *
  10  * All rights reserved.
  11  *
  12  * This program is free software; you can redistribute it and/or modify
  13  * it under the terms of the GNU General Public License version 2, as
  14  * published by the Free Software Foundation.
  15  *
  16  * This program is distributed in the hope that it will be useful,
  17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19  * GNU General Public License for more details.
  20  *
  21  * You should have received a copy of the GNU General Public License
  22  * along with this program; if not, write to the Free Software
  23  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  24  *
  25  * $Id: bit_operations.h,v 1.11 2006/11/28 15:37:03 steveu Exp $
  26  */
  27
  28 /*! \file */
  29
  30 #if !defined(_BIT_OPERATIONS_H_)
  31 #define _BIT_OPERATIONS_H_
  32
  33 #ifdef __cplusplus
  34 extern "C" {
  35 #endif
  36
  37 #if defined(__i386__)  ||  defined(__x86_64__)
  38 /*! \brief Find the bit position of the highest set bit in a word
  39     \param bits The word to be searched
  40     \return The bit number of the highest set bit, or -1 if the word is zero. */
  41 static __inline__ int top_bit(unsigned int bits)
  42 {
  43     int res;
  44
  45     __asm__ (" xorl %[res],%[res];\n"
  46              " decl %[res];\n"
  47              " bsrl %[bits],%[res]\n"
  48              : [res] "=&r" (res)
  49              : [bits] "rm" (bits));
  50     return res;
  51 }
  52 /*- End of function --------------------------------------------------------*/
  53
  54 /*! \brief Find the bit position of the lowest set bit in a word
  55     \param bits The word to be searched
  56     \return The bit number of the lowest set bit, or -1 if the word is zero. */
  57 static __inline__ int bottom_bit(unsigned int bits)
  58 {
  59     int res;
  60
  61     __asm__ (" xorl %[res],%[res];\n"
  62              " decl %[res];\n"
  63              " bsfl %[bits],%[res]\n"
  64              : [res] "=&r" (res)
  65              : [bits] "rm" (bits));
  66     return res;
  67 }
  68 /*- End of function --------------------------------------------------------*/
  69 #else
  70 static __inline__ int top_bit(unsigned int bits)
  71 {
  72     int i;
  73
  74     if (bits == 0)
  75         return -1;
  76     i = 0;
  77     if (bits & 0xFFFF0000)
  78     {
  79         bits &= 0xFFFF0000;
  80         i += 16;
  81     }
  82     if (bits & 0xFF00FF00)
  83     {
  84         bits &= 0xFF00FF00;
  85         i += 8;
  86     }
  87     if (bits & 0xF0F0F0F0)
  88     {
  89         bits &= 0xF0F0F0F0;
  90         i += 4;
  91     }
  92     if (bits & 0xCCCCCCCC)
  93     {
  94         bits &= 0xCCCCCCCC;
  95         i += 2;
  96     }
  97     if (bits & 0xAAAAAAAA)
  98     {
  99         bits &= 0xAAAAAAAA;
 100         i += 1;
 101     }
 102     return i;
 103 }
 104 /*- End of function --------------------------------------------------------*/
 105
 106 static __inline__ int bottom_bit(unsigned int bits)
 107 {
 108     int i;
 109
 110     if (bits == 0)
 111         return -1;
 112     i = 32;
 113     if (bits & 0x0000FFFF)
 114     {
 115         bits &= 0x0000FFFF;
 116         i -= 16;
 117     }
 118     if (bits & 0x00FF00FF)
 119     {
 120         bits &= 0x00FF00FF;
 121         i -= 8;
 122     }
 123     if (bits & 0x0F0F0F0F)
 124     {
 125         bits &= 0x0F0F0F0F;
 126         i -= 4;
 127     }
 128     if (bits & 0x33333333)
 129     {
 130         bits &= 0x33333333;
 131         i -= 2;
 132     }
 133     if (bits & 0x55555555)
 134     {
 135         bits &= 0x55555555;
 136         i -= 1;
 137     }
 138     return i;
 139 }
 140 /*- End of function --------------------------------------------------------*/
 141 #endif
 142
 143 /*! \brief Bit reverse a byte.
 144     \param data The byte to be reversed.
 145     \return The bit reversed version of data. */
 146 static __inline__ uint8_t bit_reverse8(uint8_t x)
 147 {
 148 #if defined(__i386__)  ||  defined(__x86_64__)
 149     /* If multiply is fast */
 150     return ((x*0x0802U & 0x22110U) | (x*0x8020U & 0x88440U))*0x10101U >> 16;
 151 #else
 152     /* If multiply is slow, but we have a barrel shifter */
 153     x = (x >> 4) | (x << 4);
 154     x = ((x & 0xCC) >> 2) | ((x & 0x33) << 2);
 155     return ((x & 0xAA) >> 1) | ((x & 0x55) << 1);
 156 #endif
 157 }
 158 /*- End of function --------------------------------------------------------*/
 159
 160 /*! \brief Bit reverse a 16 bit word.
 161     \param data The word to be reversed.
 162     \return The bit reversed version of data. */
 163 uint16_t bit_reverse16(uint16_t data);
 164
 165 /*! \brief Bit reverse a 32 bit word.
 166     \param data The word to be reversed.
 167     \return The bit reversed version of data. */
 168 uint32_t bit_reverse32(uint32_t data);
 169
 170 /*! \brief Bit reverse each of the four bytes in a 32 bit word.
 171     \param data The word to be reversed.
 172     \return The bit reversed version of data. */
 173 uint32_t bit_reverse_4bytes(uint32_t data);
 174
 175 /*! \brief Find the number of set bits in a 32 bit word.
 176     \param x The word to be searched.
 177     \return The number of set bits. */
 178 int one_bits32(uint32_t x);
 179
 180 /*! \brief Create a mask as wide as the number in a 32 bit word.
 181     \param x The word to be searched.
 182     \return The mask. */
 183 uint32_t make_mask32(uint32_t x);
 184
 185 /*! \brief Create a mask as wide as the number in a 16 bit word.
 186     \param x The word to be searched.
 187     \return The mask. */
 188 uint16_t make_mask16(uint16_t x);
 189
 190 /*! \brief Find the least significant one in a word, and return a word
 191            with just that bit set.
 192     \param x The word to be searched.
 193     \return The word with the single set bit. */
 194 static __inline__ uint32_t least_significant_one32(uint32_t x)
 195 {
 196     return (x & (-(int32_t) x));
 197 }
 198 /*- End of function --------------------------------------------------------*/
 199
 200 /*! \brief Find the most significant one in a word, and return a word
 201            with just that bit set.
 202     \param x The word to be searched.
 203     \return The word with the single set bit. */
 204 static __inline__ uint32_t most_significant_one32(uint32_t x)
 205 {
 206 #if defined(__i386__)  ||  defined(__x86_64__)
 207     return 1 << top_bit(x);
 208 #else
 209     x = make_mask32(x);
 210     return (x ^ (x >> 1));
 211 #endif
 212 }
 213 /*- End of function --------------------------------------------------------*/
 214
 215 /*! \brief Find the parity of a byte.
 216     \param x The byte to be checked.
 217     \return 1 for odd, or 0 for even. */
 218 static __inline__ int parity8(uint8_t x)
 219 {
 220     x = (x ^ (x >> 4)) & 0x0F;
 221     return (0x6996 >> x) & 1;
 222 }
 223 /*- End of function --------------------------------------------------------*/
 224
 225 /*! \brief Find the parity of a 16 bit word.
 226     \param x The word to be checked.
 227     \return 1 for odd, or 0 for even. */
 228 static __inline__ int parity16(uint16_t x)
 229 {
 230     x ^= (x >> 8);
 231     x = (x ^ (x >> 4)) & 0x0F;
 232     return (0x6996 >> x) & 1;
 233 }
 234 /*- End of function --------------------------------------------------------*/
 235
 236 /*! \brief Find the parity of a 32 bit word.
 237     \param x The word to be checked.
 238     \return 1 for odd, or 0 for even. */
 239 static __inline__ int parity32(uint32_t x)
 240 {
 241     x ^= (x >> 16);
 242     x ^= (x >> 8);
 243     x = (x ^ (x >> 4)) & 0x0F;
 244     return (0x6996 >> x) & 1;
 245 }
 246 /*- End of function --------------------------------------------------------*/
 247
 248 #ifdef __cplusplus
 249 }
 250 #endif
 251
 252 #endif
 253 /*- End of file ------------------------------------------------------------*/