[MLX4] added support to new device. [mlnx: 4473]
[mirror/winof/.git] / 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