hw/mthca/mt_utils.h

   1 /*
   2  * Copyright (c) 2005 SilverStorm Technologies.  All rights reserved.
   3  *
   4  * This software is available to you under the OpenIB.org BSD license
   5  * below:
   6  *
   7  *     Redistribution and use in source and binary forms, with or
   8  *     without modification, are permitted provided that the following
   9  *     conditions are met:
  10  *
  11  *      - Redistributions of source code must retain the above
  12  *        copyright notice, this list of conditions and the following
  13  *        disclaimer.
  14  *
  15  *      - Redistributions in binary form must reproduce the above
  16  *        copyright notice, this list of conditions and the following
  17  *        disclaimer in the documentation and/or other materials
  18  *        provided with the distribution.
  19  *
  20  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  21  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  22  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  23  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
  24  * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
  25  * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  26  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  27  * SOFTWARE.
  28  *
  29  * $Id$
  30  */
  31
  32
  33 #ifndef MT_UTILS_H
  34 #define MT_UTILS_H
  35
  36 // Nth element of the table contains the index of the first set bit of N; 8 - for N=0
  37 extern char g_set_bit_tbl[256];
  38 // Nth element of the table contains the index of the first cleared bit of N; 8 - for N=0
  39 extern char g_clr_bit_tbl[256];
  40
  41 // DECLARE_BITMAP
  42 #define BITS_PER_LONG           32
  43 #define BITS_TO_LONGS(bits) \
  44          (((bits)+BITS_PER_LONG-1)/BITS_PER_LONG)
  45
  46 /*
  47 * fls: find last bit set.
  48 * returns: 0 - if not found or N+1, if found Nth bit
  49 */
  50
  51 static __inline int fls(int x)
  52 {
  53        int r = 32;
  54
  55        if (!x)
  56                return 0;
  57        if (!(x & 0xffff0000u)) {
  58                x <<= 16;
  59                r -= 16;
  60        }
  61        if (!(x & 0xff000000u)) {
  62                x <<= 8;
  63                r -= 8;
  64        }
  65        if (!(x & 0xf0000000u)) {
  66                x <<= 4;
  67                r -= 4;
  68        }
  69        if (!(x & 0xc0000000u)) {
  70                x <<= 2;
  71                r -= 2;
  72        }
  73        if (!(x & 0x80000000u)) {
  74                x <<= 1;
  75                r -= 1;
  76        }
  77        return r;
  78 }
  79
  80 /**
  81 * _ffs_raw - find the first one bit in a word
  82 * @addr: The address to start the search at
  83 * @offset: The bitnumber to start searching at
  84 *
  85 * returns: 0 - if not found or N+1, if found Nth bit
  86 */
  87 static __inline int _ffs_raw(const unsigned long *addr, int offset)
  88 {
  89         //TODO: not an effective code - is better in Assembler
  90         int mask;
  91         int rbc;
  92         int ix;
  93         if (!*addr) return 0;
  94         mask = 1 << offset;
  95         rbc = BITS_PER_LONG - offset;
  96         for (ix=0; ix<rbc; ix++, mask<<=1) {
  97                 if (*addr & mask)
  98                         return offset + ix + 1;
  99         }
 100         return 0;
 101 }
 102
 103 // as previous with offset = 0
 104 static __inline int _ffs(const unsigned long *addr)
 105 {
 106         unsigned char *ptr = (unsigned char *)addr;
 107         if (!*addr) return 0;                                   // skip sero dword
 108         if (!*(short*)ptr) ptr += 2;                            // get to the non-zero word
 109         if (!*(char*)ptr) ptr++;                                                // get to the non-zero byte
 110         return (int)(((ptr - (unsigned char *)addr ) << 3) + g_set_bit_tbl[*ptr] + 1);
 111 }
 112
 113
 114 #define ffs(val)        _ffs((const unsigned long *)&val)
 115
 116 /**
 117 * _ffz_raw - find the first zero bit in a word
 118 * @addr: The address to start the search at
 119 * @offset: The bitnumber to start searching at
 120 *
 121 * returns: 0 - if not found or N+1, if found Nth bit
 122 */
 123 static __inline int _ffz_raw(const unsigned long *addr, int offset)
 124 {
 125         //TODO: not an effective code - is better in Assembler
 126         int mask;
 127         int rbc;
 128         int ix;
 129         if (!~*addr) return 0;
 130         mask = 1 << offset;
 131         rbc = BITS_PER_LONG - offset;
 132         for (ix=0; ix<rbc; ix++, mask<<=1) {
 133                 if (!(*addr & mask))
 134                         return offset + ix + 1;
 135         }
 136         return 0;
 137 }
 138
 139
 140 // as previous with offset = 0
 141 static __inline int _ffz(const unsigned long *addr)
 142 {
 143         unsigned char *ptr = (unsigned char *)addr;
 144         if (!~*addr) return 0;                                  // skip sero dword
 145         if (!~*(short*)ptr) ptr += 2;                           // get to the non-zero word
 146         if (!~*(char*)ptr) ptr++;                                               // get to the non-zero byte
 147         return (int)(((ptr - (unsigned char *)addr ) << 3) + g_clr_bit_tbl[*ptr] + 1);
 148 }
 149
 150 #define ffz(val)        _ffz((const unsigned long *)&val)
 151
 152 // Function:
 153 //      finds the first bit, set in the bitmap
 154 // Parameters:
 155 //      ptr     - address of the bitmap
 156 //      bits_size       - the size in bits
 157 // Returns:
 158 //      the index of the first bit set; 'bits_size' - when there is noone
 159 // Notes:
 160 //      presumes, that ptr is aligned on dword
 161 //      presumes, that the map contains an integer number of dwords
 162 //      on bits_size=0 will return 0, but its an illegal case
 163 //
 164 static __inline int find_first_bit(const unsigned long *addr, unsigned bits_size)
 165 {
 166         unsigned char *ptr = (unsigned char *)addr;             // bitmap start
 167         unsigned char *end_ptr = (unsigned char *)(addr + BITS_TO_LONGS(bits_size));    // bitmap end
 168
 169         while (ptr<end_ptr) {
 170                 if (!*(int*)ptr) { ptr += 4; continue; }        // skip zero dword
 171                 if (!*(short*)ptr) ptr += 2;                            // get to the non-zero word
 172                 if (!*(char*)ptr) ptr++;                                                // get to the non-zero byte
 173                 return (int)(((ptr - (unsigned char *)addr ) << 3) + g_set_bit_tbl[*ptr]);
 174         }
 175         return bits_size;
 176 }
 177
 178 static __inline int find_first_zero_bit(const unsigned long *addr, unsigned bits_size)
 179 {
 180         unsigned char *ptr = (unsigned char *)addr;             // bitmap start
 181         unsigned char *end_ptr = (unsigned char *)(addr + BITS_TO_LONGS(bits_size));    // bitmap end
 182
 183         while (ptr<end_ptr) {
 184                 if (!~*(int*)ptr) { ptr += 4; continue; }       // skip dword w/o zero bits
 185                 if (!~*(short*)ptr) ptr += 2;                           // get to the word with zero bits
 186                 if (!~*(char*)ptr) ptr++;                                               // get to the byte with zero bits
 187                 return (int)(((ptr - (unsigned char *)addr ) << 3) + g_clr_bit_tbl[*ptr]);
 188         }
 189         return bits_size;
 190 }
 191
 192
 193 /**
 194 * find_next_zero_bit - find the first zero bit in a memory region
 195 * @addr: The address to base the search on
 196 * @offset: The bitnumber to start searching at
 197 * @bits_size: The maximum size to search
 198 *
 199 * Returns the bit-number of the first zero bit, not the number of the byte
 200 * containing a bit. If not found - returns 'size'
 201 */
 202 static __inline int find_next_zero_bit(const unsigned long *addr, int bits_size, int offset)
 203 {
 204         int res;
 205         int ix = offset % BITS_PER_LONG;
 206         int w_offset = offset / BITS_PER_LONG;
 207
 208         // search in the first word while we are in the middle
 209         if (ix) {
 210                 res = _ffz_raw(addr + w_offset, ix);
 211                 if (res)
 212                         return res - 1;
 213                 ++addr;
 214                 bits_size -= BITS_PER_LONG;
 215                 ix = BITS_PER_LONG;
 216         }
 217
 218         res = find_first_zero_bit( addr, bits_size );
 219         return res + ix;
 220 }
 221
 222 void fill_bit_tbls();
 223
 224 #endif
 225