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