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