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 */