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 #if defined(__i386__)  ||  defined(__x86_64__)
  34 /*! \brief Find the bit position of the highest set bit in a word
  35     \param bits The word to be searched
  36     \return The bit number of the highest set bit, or -1 if the word is zero. */
  37 static __inline__ int top_bit(unsigned int bits)
  38 {
  39     int res;
  40
  41     __asm__ (" xorl %[res],%[res];\n"
  42              " decl %[res];\n"
  43              " bsrl %[bits],%[res]\n"
  44              : [res] "=&r" (res)
  45              : [bits] "rm" (bits));
  46     return res;
  47 }
  48 /*- End of function --------------------------------------------------------*/
  49
  50 /*! \brief Find the bit position of the lowest set bit in a word
  51     \param bits The word to be searched
  52     \return The bit number of the lowest set bit, or -1 if the word is zero. */
  53 static __inline__ int bottom_bit(unsigned int bits)
  54 {
  55     int res;
  56
  57     __asm__ (" xorl %[res],%[res];\n"
  58              " decl %[res];\n"
  59              " bsfl %[bits],%[res]\n"
  60              : [res] "=&r" (res)
  61              : [bits] "rm" (bits));
  62     return res;
  63 }
  64 /*- End of function --------------------------------------------------------*/
  65 #else
  66 static __inline__ int top_bit(unsigned int bits)
  67 {
  68     int i;
  69
  70     if (bits == 0)
  71         return -1;
  72     i = 0;
  73     if (bits & 0xFFFF0000)
  74     {
  75         bits &= 0xFFFF0000;
  76         i += 16;
  77     }
  78     if (bits & 0xFF00FF00)
  79     {
  80         bits &= 0xFF00FF00;
  81         i += 8;
  82     }
  83     if (bits & 0xF0F0F0F0)
  84     {
  85         bits &= 0xF0F0F0F0;
  86         i += 4;
  87     }
  88     if (bits & 0xCCCCCCCC)
  89     {
  90         bits &= 0xCCCCCCCC;
  91         i += 2;
  92     }
  93     if (bits & 0xAAAAAAAA)
  94     {
  95         bits &= 0xAAAAAAAA;
  96         i += 1;
  97     }
  98     return i;
  99 }
 100 /*- End of function --------------------------------------------------------*/
 101
 102 static __inline__ int bottom_bit(unsigned int bits)
 103 {
 104     int i;
 105
 106     if (bits == 0)
 107         return -1;
 108     i = 32;
 109     if (bits & 0x0000FFFF)
 110     {
 111         bits &= 0x0000FFFF;
 112         i -= 16;
 113     }
 114     if (bits & 0x00FF00FF)
 115     {
 116         bits &= 0x00FF00FF;
 117         i -= 8;
 118     }
 119     if (bits & 0x0F0F0F0F)
 120     {
 121         bits &= 0x0F0F0F0F;
 122         i -= 4;
 123     }
 124     if (bits & 0x33333333)
 125     {
 126         bits &= 0x33333333;
 127         i -= 2;
 128     }
 129     if (bits & 0x55555555)
 130     {
 131         bits &= 0x55555555;
 132         i -= 1;
 133     }
 134     return i;
 135 }
 136 /*- End of function --------------------------------------------------------*/
 137 #endif
 138
 139 /*! \brief Bit reverse a byte.
 140     \param data The byte to be reversed.
 141     \return The bit reversed version of data. */
 142 static __inline__ uint8_t bit_reverse8(uint8_t x)
 143 {
 144 #if defined(__i386__)  ||  defined(__x86_64__)
 145     /* If multiply is fast */
 146     return ((x*0x0802U & 0x22110U) | (x*0x8020U & 0x88440U))*0x10101U >> 16;
 147 #else
 148     /* If multiply is slow, but we have a barrel shifter */
 149     x = (x >> 4) | (x << 4);
 150     x = ((x & 0xCC) >> 2) | ((x & 0x33) << 2);
 151     return ((x & 0xAA) >> 1) | ((x & 0x55) << 1);
 152 #endif
 153 }
 154 /*- End of function --------------------------------------------------------*/
 155
 156 /*! \brief Bit reverse a 16 bit word.
 157     \param data The word to be reversed.
 158     \return The bit reversed version of data. */
 159 uint16_t bit_reverse16(uint16_t data);
 160
 161 /*! \brief Bit reverse a 32 bit word.
 162     \param data The word to be reversed.
 163     \return The bit reversed version of data. */
 164 uint32_t bit_reverse32(uint32_t data);
 165
 166 /*! \brief Bit reverse each of the four bytes in a 32 bit word.
 167     \param data The word to be reversed.
 168     \return The bit reversed version of data. */
 169 uint32_t bit_reverse_4bytes(uint32_t data);
 170
 171 /*! \brief Find the number of set bits in a 32 bit word.
 172     \param x The word to be searched.
 173     \return The number of set bits. */
 174 int one_bits32(uint32_t x);
 175
 176 /*! \brief Create a mask as wide as the number in a 32 bit word.
 177     \param x The word to be searched.
 178     \return The mask. */
 179 uint32_t make_mask32(uint32_t x);
 180
 181 /*! \brief Create a mask as wide as the number in a 16 bit word.
 182     \param x The word to be searched.
 183     \return The mask. */
 184 uint16_t make_mask16(uint16_t x);
 185
 186 /*! \brief Find the least significant one in a word, and return a word
 187            with just that bit set.
 188     \param x The word to be searched.
 189     \return The word with the single set bit. */
 190 static __inline__ uint32_t least_significant_one32(uint32_t x)
 191 {
 192     return (x & (-(int32_t) x));
 193 }
 194 /*- End of function --------------------------------------------------------*/
 195
 196 /*! \brief Find the most significant one in a word, and return a word
 197            with just that bit set.
 198     \param x The word to be searched.
 199     \return The word with the single set bit. */
 200 static __inline__ uint32_t most_significant_one32(uint32_t x)
 201 {
 202 #if defined(__i386__)  ||  defined(__x86_64__)
 203     return 1 << top_bit(x);
 204 #else
 205     x = make_mask32(x);
 206     return (x ^ (x >> 1));
 207 #endif
 208 }
 209 /*- End of function --------------------------------------------------------*/
 210
 211 /*! \brief Find the parity of a byte.
 212     \param x The byte to be checked.
 213     \return 1 for odd, or 0 for even. */
 214 static __inline__ int parity8(uint8_t x)
 215 {
 216     x = (x ^ (x >> 4)) & 0x0F;
 217     return (0x6996 >> x) & 1;
 218 }
 219 /*- End of function --------------------------------------------------------*/
 220
 221 /*! \brief Find the parity of a 16 bit word.
 222     \param x The word to be checked.
 223     \return 1 for odd, or 0 for even. */
 224 static __inline__ int parity16(uint16_t x)
 225 {
 226     x ^= (x >> 8);
 227     x = (x ^ (x >> 4)) & 0x0F;
 228     return (0x6996 >> x) & 1;
 229 }
 230 /*- End of function --------------------------------------------------------*/
 231
 232 /*! \brief Find the parity of a 32 bit word.
 233     \param x The word to be checked.
 234     \return 1 for odd, or 0 for even. */
 235 static __inline__ int parity32(uint32_t x)
 236 {
 237     x ^= (x >> 16);
 238     x ^= (x >> 8);
 239     x = (x ^ (x >> 4)) & 0x0F;
 240     return (0x6996 >> x) & 1;
 241 }
 242 /*- End of function --------------------------------------------------------*/
 243
 244 #endif
 245 /*- End of file ------------------------------------------------------------*/