David Rowe | 10602db | 2008-10-06 21:41:46 -0700 | [diff] [blame] | 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. |
David Rowe | 10602db | 2008-10-06 21:41:46 -0700 | [diff] [blame] | 24 | */ |
| 25 | |
| 26 | /*! \file */ |
| 27 | |
| 28 | #if !defined(_BIT_OPERATIONS_H_) |
| 29 | #define _BIT_OPERATIONS_H_ |
| 30 | |
David Rowe | 10602db | 2008-10-06 21:41:46 -0700 | [diff] [blame] | 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. */ |
Alexander Beregalov | dc57a3e | 2009-03-12 03:32:45 +0300 | [diff] [blame] | 35 | static inline int top_bit(unsigned int bits) |
David Rowe | 10602db | 2008-10-06 21:41:46 -0700 | [diff] [blame] | 36 | { |
J.R. Mauro | 4460a86 | 2008-10-20 19:01:31 -0400 | [diff] [blame] | 37 | int res; |
David Rowe | 10602db | 2008-10-06 21:41:46 -0700 | [diff] [blame] | 38 | |
J.R. Mauro | 4460a86 | 2008-10-20 19:01:31 -0400 | [diff] [blame] | 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; |
David Rowe | 10602db | 2008-10-06 21:41:46 -0700 | [diff] [blame] | 46 | } |
David Rowe | 10602db | 2008-10-06 21:41:46 -0700 | [diff] [blame] | 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. */ |
Alexander Beregalov | dc57a3e | 2009-03-12 03:32:45 +0300 | [diff] [blame] | 51 | static inline int bottom_bit(unsigned int bits) |
David Rowe | 10602db | 2008-10-06 21:41:46 -0700 | [diff] [blame] | 52 | { |
J.R. Mauro | 4460a86 | 2008-10-20 19:01:31 -0400 | [diff] [blame] | 53 | int res; |
David Rowe | 10602db | 2008-10-06 21:41:46 -0700 | [diff] [blame] | 54 | |
J.R. Mauro | 4460a86 | 2008-10-20 19:01:31 -0400 | [diff] [blame] | 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; |
David Rowe | 10602db | 2008-10-06 21:41:46 -0700 | [diff] [blame] | 62 | } |
David Rowe | 10602db | 2008-10-06 21:41:46 -0700 | [diff] [blame] | 63 | #else |
Alexander Beregalov | dc57a3e | 2009-03-12 03:32:45 +0300 | [diff] [blame] | 64 | static inline int top_bit(unsigned int bits) |
David Rowe | 10602db | 2008-10-06 21:41:46 -0700 | [diff] [blame] | 65 | { |
J.R. Mauro | 4460a86 | 2008-10-20 19:01:31 -0400 | [diff] [blame] | 66 | int i; |
David Rowe | 10602db | 2008-10-06 21:41:46 -0700 | [diff] [blame] | 67 | |
J.R. Mauro | 4460a86 | 2008-10-20 19:01:31 -0400 | [diff] [blame] | 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; |
David Rowe | 10602db | 2008-10-06 21:41:46 -0700 | [diff] [blame] | 92 | } |
David Rowe | 10602db | 2008-10-06 21:41:46 -0700 | [diff] [blame] | 93 | |
Alexander Beregalov | dc57a3e | 2009-03-12 03:32:45 +0300 | [diff] [blame] | 94 | static inline int bottom_bit(unsigned int bits) |
David Rowe | 10602db | 2008-10-06 21:41:46 -0700 | [diff] [blame] | 95 | { |
J.R. Mauro | 4460a86 | 2008-10-20 19:01:31 -0400 | [diff] [blame] | 96 | int i; |
David Rowe | 10602db | 2008-10-06 21:41:46 -0700 | [diff] [blame] | 97 | |
J.R. Mauro | 4460a86 | 2008-10-20 19:01:31 -0400 | [diff] [blame] | 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; |
David Rowe | 10602db | 2008-10-06 21:41:46 -0700 | [diff] [blame] | 122 | } |
David Rowe | 10602db | 2008-10-06 21:41:46 -0700 | [diff] [blame] | 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. */ |
Alexander Beregalov | dc57a3e | 2009-03-12 03:32:45 +0300 | [diff] [blame] | 128 | static inline uint8_t bit_reverse8(uint8_t x) |
David Rowe | 10602db | 2008-10-06 21:41:46 -0700 | [diff] [blame] | 129 | { |
| 130 | #if defined(__i386__) || defined(__x86_64__) |
J.R. Mauro | 4460a86 | 2008-10-20 19:01:31 -0400 | [diff] [blame] | 131 | /* If multiply is fast */ |
| 132 | return ((x * 0x0802U & 0x22110U) | (x * 0x8020U & 0x88440U)) * |
| 133 | 0x10101U >> 16; |
David Rowe | 10602db | 2008-10-06 21:41:46 -0700 | [diff] [blame] | 134 | #else |
J.R. Mauro | 4460a86 | 2008-10-20 19:01:31 -0400 | [diff] [blame] | 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); |
David Rowe | 10602db | 2008-10-06 21:41:46 -0700 | [diff] [blame] | 139 | #endif |
| 140 | } |
David Rowe | 10602db | 2008-10-06 21:41:46 -0700 | [diff] [blame] | 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 |
Alexander Beregalov | dc57a3e | 2009-03-12 03:32:45 +0300 | [diff] [blame] | 173 | with just that bit set. |
David Rowe | 10602db | 2008-10-06 21:41:46 -0700 | [diff] [blame] | 174 | \param x The word to be searched. |
| 175 | \return The word with the single set bit. */ |
Alexander Beregalov | dc57a3e | 2009-03-12 03:32:45 +0300 | [diff] [blame] | 176 | static inline uint32_t least_significant_one32(uint32_t x) |
David Rowe | 10602db | 2008-10-06 21:41:46 -0700 | [diff] [blame] | 177 | { |
Alexander Beregalov | dc57a3e | 2009-03-12 03:32:45 +0300 | [diff] [blame] | 178 | return x & (-(int32_t) x); |
David Rowe | 10602db | 2008-10-06 21:41:46 -0700 | [diff] [blame] | 179 | } |
David Rowe | 10602db | 2008-10-06 21:41:46 -0700 | [diff] [blame] | 180 | |
| 181 | /*! \brief Find the most significant one in a word, and return a word |
Alexander Beregalov | dc57a3e | 2009-03-12 03:32:45 +0300 | [diff] [blame] | 182 | with just that bit set. |
David Rowe | 10602db | 2008-10-06 21:41:46 -0700 | [diff] [blame] | 183 | \param x The word to be searched. |
| 184 | \return The word with the single set bit. */ |
Alexander Beregalov | dc57a3e | 2009-03-12 03:32:45 +0300 | [diff] [blame] | 185 | static inline uint32_t most_significant_one32(uint32_t x) |
David Rowe | 10602db | 2008-10-06 21:41:46 -0700 | [diff] [blame] | 186 | { |
| 187 | #if defined(__i386__) || defined(__x86_64__) |
J.R. Mauro | 4460a86 | 2008-10-20 19:01:31 -0400 | [diff] [blame] | 188 | return 1 << top_bit(x); |
David Rowe | 10602db | 2008-10-06 21:41:46 -0700 | [diff] [blame] | 189 | #else |
J.R. Mauro | 4460a86 | 2008-10-20 19:01:31 -0400 | [diff] [blame] | 190 | x = make_mask32(x); |
Alexander Beregalov | dc57a3e | 2009-03-12 03:32:45 +0300 | [diff] [blame] | 191 | return x ^ (x >> 1); |
David Rowe | 10602db | 2008-10-06 21:41:46 -0700 | [diff] [blame] | 192 | #endif |
| 193 | } |
David Rowe | 10602db | 2008-10-06 21:41:46 -0700 | [diff] [blame] | 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. */ |
Alexander Beregalov | dc57a3e | 2009-03-12 03:32:45 +0300 | [diff] [blame] | 198 | static inline int parity8(uint8_t x) |
David Rowe | 10602db | 2008-10-06 21:41:46 -0700 | [diff] [blame] | 199 | { |
J.R. Mauro | 4460a86 | 2008-10-20 19:01:31 -0400 | [diff] [blame] | 200 | x = (x ^ (x >> 4)) & 0x0F; |
| 201 | return (0x6996 >> x) & 1; |
David Rowe | 10602db | 2008-10-06 21:41:46 -0700 | [diff] [blame] | 202 | } |
David Rowe | 10602db | 2008-10-06 21:41:46 -0700 | [diff] [blame] | 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. */ |
Alexander Beregalov | dc57a3e | 2009-03-12 03:32:45 +0300 | [diff] [blame] | 207 | static inline int parity16(uint16_t x) |
David Rowe | 10602db | 2008-10-06 21:41:46 -0700 | [diff] [blame] | 208 | { |
J.R. Mauro | 4460a86 | 2008-10-20 19:01:31 -0400 | [diff] [blame] | 209 | x ^= (x >> 8); |
| 210 | x = (x ^ (x >> 4)) & 0x0F; |
| 211 | return (0x6996 >> x) & 1; |
David Rowe | 10602db | 2008-10-06 21:41:46 -0700 | [diff] [blame] | 212 | } |
David Rowe | 10602db | 2008-10-06 21:41:46 -0700 | [diff] [blame] | 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. */ |
Alexander Beregalov | dc57a3e | 2009-03-12 03:32:45 +0300 | [diff] [blame] | 217 | static inline int parity32(uint32_t x) |
David Rowe | 10602db | 2008-10-06 21:41:46 -0700 | [diff] [blame] | 218 | { |
J.R. Mauro | 4460a86 | 2008-10-20 19:01:31 -0400 | [diff] [blame] | 219 | x ^= (x >> 16); |
| 220 | x ^= (x >> 8); |
| 221 | x = (x ^ (x >> 4)) & 0x0F; |
| 222 | return (0x6996 >> x) & 1; |
David Rowe | 10602db | 2008-10-06 21:41:46 -0700 | [diff] [blame] | 223 | } |
David Rowe | 10602db | 2008-10-06 21:41:46 -0700 | [diff] [blame] | 224 | |
David Rowe | 10602db | 2008-10-06 21:41:46 -0700 | [diff] [blame] | 225 | #endif |
| 226 | /*- End of file ------------------------------------------------------------*/ |