Merge revisions 1.38,1.41 of eval.c from FreeBSD:
[dragonfly.git] / sys / vfs / gnu / ext2fs / alpha-bitops.h
1 /* $FreeBSD: src/sys/gnu/ext2fs/alpha-bitops.h,v 1.1.2.1 2001/08/14 18:03:19 gallatin Exp $ */
2 /* $DragonFly: src/sys/vfs/gnu/ext2fs/Attic/alpha-bitops.h,v 1.3 2006/01/13 21:09:27 swildner Exp $ */
3 #ifndef _ALPHA_BITOPS_H
4 #define _ALPHA_BITOPS_H
5
6 /*
7  * Copyright 1994, Linus Torvalds.
8  */
9
10 /*
11  * These have to be done with inline assembly: that way the bit-setting
12  * is guaranteed to be atomic. All bit operations return 0 if the bit
13  * was cleared before the operation and != 0 if it was not.
14  *
15  * To get proper branch prediction for the main line, we must branch
16  * forward to code at the end of this object's .text section, then
17  * branch back to restart the operation.
18  *
19  * bit 0 is the LSB of addr; bit 64 is the LSB of (addr+1).
20  */
21 static __inline unsigned int set_bit(unsigned long, volatile void *);
22 static __inline unsigned int clear_bit(unsigned long, volatile void *);
23 static __inline unsigned int change_bit(unsigned long, volatile void *);
24 static __inline unsigned int test_bit(int, volatile void *);
25 static __inline unsigned long ffz_b(unsigned long x);
26 static __inline unsigned long ffz(unsigned long);
27 /* static __inline int ffs(int); */
28 static __inline void * memscan(void *, int, size_t);
29 #ifdef __alpha_cix__
30 static __inline unsigned long hweight64(unsigned long);
31 #endif
32 static __inline unsigned long
33 find_next_zero_bit(void *, unsigned long, unsigned long);
34
35 static __inline unsigned int
36 set_bit(unsigned long nr, volatile void * addr)
37 {
38         unsigned long oldbit;
39         unsigned long temp;
40         volatile unsigned int *m = ((volatile unsigned int *) addr) + (nr >> 5);
41
42         __asm__ __volatile__(
43         "1:     ldl_l %0,%1\n"
44         "       and %0,%3,%2\n"
45         "       bne %2,2f\n"
46         "       xor %0,%3,%0\n"
47         "       stl_c %0,%1\n"
48         "       beq %0,3f\n"
49         "2:\n"
50         ".section .text2,\"ax\"\n"
51         "3:     br 1b\n"
52         ".previous"
53         :"=&r" (temp), "=m" (*m), "=&r" (oldbit)
54         :"Ir" (1UL << (nr & 31)), "m" (*m));
55         return oldbit;
56 }
57
58 static __inline unsigned int
59 clear_bit(unsigned long nr, volatile void * addr)
60 {
61         unsigned long oldbit;
62         unsigned long temp;
63         volatile unsigned int *m = ((volatile unsigned int *) addr) + (nr >> 5);
64
65         __asm__ __volatile__(
66         "1:     ldl_l %0,%1\n"
67         "       and %0,%3,%2\n"
68         "       beq %2,2f\n"
69         "       xor %0,%3,%0\n"
70         "       stl_c %0,%1\n"
71         "       beq %0,3f\n"
72         "2:\n"
73         ".section .text2,\"ax\"\n"
74         "3:     br 1b\n"
75         ".previous"
76         :"=&r" (temp), "=m" (*m), "=&r" (oldbit)
77         :"Ir" (1UL << (nr & 31)), "m" (*m));
78         return oldbit;
79 }
80
81 static __inline unsigned int
82 change_bit(unsigned long nr, volatile void * addr)
83 {
84         unsigned long oldbit;
85         unsigned long temp;
86         volatile unsigned int *m = ((volatile unsigned int *) addr) + (nr >> 5);
87
88         __asm__ __volatile__(
89         "1:     ldl_l %0,%1\n"
90         "       xor %0,%2,%0\n"
91         "       stl_c %0,%1\n"
92         "       beq %0,3f\n"
93         ".section .text2,\"ax\"\n"
94         "3:     br 1b\n"
95         ".previous"
96         :"=&r" (temp), "=m" (*m), "=&r" (oldbit)
97         :"Ir" (1UL << (nr & 31)), "m" (*m));
98         return oldbit;
99 }
100
101 static __inline unsigned int test_bit(int nr, volatile void * addr)
102 {
103         return 1UL & (((volatile int *) addr)[nr >> 5] >> (nr & 31));
104 }
105
106 /*
107  * ffz = Find First Zero in word. Undefined if no zero exists,
108  * so code should check against ~0UL first..
109  *
110  * Do a binary search on the bits.  Due to the nature of large
111  * constants on the alpha, it is worthwhile to split the search.
112  */
113 static __inline unsigned long
114 ffz_b(unsigned long x)
115 {
116         unsigned long sum = 0;
117
118         x = ~x & -~x;           /* set first 0 bit, clear others */
119         if (x & 0xF0) sum += 4;
120         if (x & 0xCC) sum += 2;
121         if (x & 0xAA) sum += 1;
122
123         return sum;
124 }
125
126 static __inline unsigned long
127 ffz(unsigned long word)
128 {
129 #ifdef __alpha_cix__
130         /* Whee.  EV6 can calculate it directly.  */
131         unsigned long result;
132         __asm__("ctlz %1,%0" : "=r"(result) : "r"(~word));
133         return result;
134 #else
135         unsigned long bits, qofs, bofs;
136
137         __asm__("cmpbge %1,%2,%0" : "=r"(bits) : "r"(word), "r"(~0UL));
138         qofs = ffz_b(bits);
139         __asm__("extbl %1,%2,%0" : "=r"(bits) : "r"(word), "r"(qofs));
140         bofs = ffz_b(bits);
141
142         return qofs*8 + bofs;
143 #endif
144 }
145
146 #ifdef __KERNEL__
147 #if     0
148 /*
149  * ffs: find first bit set. This is defined the same way as
150  * the libc and compiler builtin ffs routines, therefore
151  * differs in spirit from the above ffz (man ffs).
152  */
153
154 static __inline int
155 ffs(int word)
156 {
157         int result = ffz(~word);
158         return word ? result+1 : 0;
159 }
160 #endif
161
162 /*
163  * hweightN: returns the hamming weight (i.e. the number
164  * of bits set) of a N-bit word
165  */
166
167 #ifdef __alpha_cix__
168 /* Whee.  EV6 can calculate it directly.  */
169 static __inline unsigned long
170 hweight64(unsigned long w)
171 {
172         unsigned long result;
173         __asm__("ctpop %1,%0" : "=r"(result) : "r"(w));
174         return result;
175 }
176
177 #define hweight32(x) hweight64((x) & 0xfffffffful)
178 #define hweight16(x) hweight64((x) & 0xfffful)
179 #define hweight8(x)  hweight64((x) & 0xfful)
180 #else
181 #define hweight32(x) generic_hweight32(x)
182 #define hweight16(x) generic_hweight16(x)
183 #define hweight8(x)  generic_hweight8(x)
184 #endif
185
186 #endif /* __alpha_cix__ */
187
188 /* from lib/string.c */
189 static __inline void *
190 memscan(void * addr, int c, size_t size)
191 {
192         unsigned char * p = (unsigned char *) addr;
193
194         while (size) {
195                 if (*p == c)
196                         return (void *) p;
197                 p++;
198                 size--;
199         }
200         return (void *) p;
201 }
202
203
204 /*
205  * Find next zero bit in a bitmap reasonably efficiently..
206  */
207 static __inline unsigned long
208 find_next_zero_bit(void * addr, unsigned long size, unsigned long offset)
209 {
210         unsigned long * p = ((unsigned long *) addr) + (offset >> 6);
211         unsigned long result = offset & ~63UL;
212         unsigned long tmp;
213
214         if (offset >= size)
215                 return size;
216         size -= result;
217         offset &= 63UL;
218         if (offset) {
219                 tmp = *(p++);
220                 tmp |= ~0UL >> (64-offset);
221                 if (size < 64)
222                         goto found_first;
223                 if (~tmp)
224                         goto found_middle;
225                 size -= 64;
226                 result += 64;
227         }
228         while (size & ~63UL) {
229                 if (~(tmp = *(p++)))
230                         goto found_middle;
231                 result += 64;
232                 size -= 64;
233         }
234         if (!size)
235                 return result;
236         tmp = *p;
237 found_first:
238         tmp |= ~0UL << size;
239 found_middle:
240         return result + ffz(tmp);
241 }
242
243 /*
244  * The optimizer actually does good code for this case..
245  */
246 #define find_first_zero_bit(addr, size) \
247         find_next_zero_bit((addr), (size), 0)
248
249 #ifdef __KERNEL__
250
251 #define ext2_set_bit                 test_and_set_bit
252 #define ext2_clear_bit               test_and_clear_bit
253 #define ext2_test_bit                test_bit
254 #define ext2_find_first_zero_bit     find_first_zero_bit
255 #define ext2_find_next_zero_bit      find_next_zero_bit
256
257 /* Bitmap functions for the minix filesystem.  */
258 #define minix_set_bit(nr,addr) test_and_set_bit(nr,addr)
259 #define minix_clear_bit(nr,addr) test_and_clear_bit(nr,addr)
260 #define minix_test_bit(nr,addr) test_bit(nr,addr)
261 #define minix_find_first_zero_bit(addr,size) find_first_zero_bit(addr,size)
262
263 #endif /* __KERNEL__ */
264
265 #endif /* _ALPHA_BITOPS_H */