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