reactos/ntoskrnl/rtl/bitops.c

   1 /*
   2  *  ReactOS kernel
   3  *
   4  *  This program is free software; you can redistribute it and/or modify
   5  *  it under the terms of the GNU General Public License as published by
   6  *  the Free Software Foundation; either version 2 of the License, or
   7  *  (at your option) any later version.
   8  *
   9  *  This program is distributed in the hope that it will be useful,
  10  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  *  GNU General Public License for more details.
  13  *
  14  *  You should have received a copy of the GNU General Public License
  15  *  along with this program; if not, write to the Free Software
  16  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  17  */
  18 /*
  19  * Copyright 1992, Linus Torvalds.
  20  */
  21 /*
  22  * These have to be done with inline assembly: that way the bit-setting
  23  * is guaranteed to be atomic. All bit operations return 0 if the bit
  24  * was cleared before the operation and != 0 if it was not.
  25  *
  26  * bit 0 is the LSB of addr; bit 32 is the LSB of (addr+1).
  27  */
  28
  29 #ifdef __SMP__
  30 #define LOCK_PREFIX "lock ; "
  31 #else
  32 #define LOCK_PREFIX ""
  33 #endif
  34
  35 /*
  36  * Function prototypes to keep gcc -Wall happy
  37  */
  38 extern void set_bit(int nr, volatile void * addr);
  39 extern void clear_bit(int nr, volatile void * addr);
  40 extern void change_bit(int nr, volatile void * addr);
  41 extern int test_and_set_bit(int nr, volatile void * addr);
  42 extern int test_and_clear_bit(int nr, volatile void * addr);
  43 extern int test_and_change_bit(int nr, volatile void * addr);
  44 extern int __constant_test_bit(int nr, const volatile void * addr);
  45 extern int __test_bit(int nr, volatile void * addr);
  46 extern int find_first_zero_bit(void * addr, unsigned size);
  47 extern int find_next_zero_bit (void * addr, int size, int offset);
  48 extern unsigned long ffz(unsigned long word);
  49
  50 /*
  51  * Some hacks to defeat gcc over-optimizations..
  52  */
  53 struct __dummy { unsigned long a[100]; };
  54 #define ADDR (*(volatile struct __dummy *) addr)
  55 #define CONST_ADDR (*(volatile const struct __dummy *) addr)
  56
  57 void set_bit(int nr, volatile void * addr)
  58 {
  59         __asm__ __volatile__( LOCK_PREFIX
  60                 "btsl %1,%0"
  61                 :"=m" (ADDR)
  62                 :"Ir" (nr));
  63 }
  64
  65 void clear_bit(int nr, volatile void * addr)
  66 {
  67         __asm__ __volatile__( LOCK_PREFIX
  68                 "btrl %1,%0"
  69                 :"=m" (ADDR)
  70                 :"Ir" (nr));
  71 }
  72
  73 void change_bit(int nr, volatile void * addr)
  74 {
  75         __asm__ __volatile__( LOCK_PREFIX
  76                 "btcl %1,%0"
  77                 :"=m" (ADDR)
  78                 :"Ir" (nr));
  79 }
  80
  81 int test_and_set_bit(int nr, volatile void * addr)
  82 {
  83         int oldbit;
  84
  85         __asm__ __volatile__( LOCK_PREFIX
  86                 "btsl %2,%1\n\tsbbl %0,%0"
  87                 :"=r" (oldbit),"=m" (ADDR)
  88                 :"Ir" (nr));
  89         return oldbit;
  90 }
  91
  92 int test_and_clear_bit(int nr, volatile void * addr)
  93 {
  94         int oldbit;
  95
  96         __asm__ __volatile__( LOCK_PREFIX
  97                 "btrl %2,%1\n\tsbbl %0,%0"
  98                 :"=r" (oldbit),"=m" (ADDR)
  99                 :"Ir" (nr));
 100         return oldbit;
 101 }
 102
 103 int test_and_change_bit(int nr, volatile void * addr)
 104 {
 105         int oldbit;
 106
 107         __asm__ __volatile__( LOCK_PREFIX
 108                 "btcl %2,%1\n\tsbbl %0,%0"
 109                 :"=r" (oldbit),"=m" (ADDR)
 110                 :"Ir" (nr));
 111         return oldbit;
 112 }
 113
 114 /*
 115  * This routine doesn't need to be atomic.
 116  */
 117 int __constant_test_bit(int nr, const volatile void * addr)
 118 {
 119         return ((1UL << (nr & 31)) & (((const volatile unsigned int *) addr)[nr >> 5])) != 0;
 120 }
 121
 122 int test_bit(int nr, volatile void * addr)
 123 {
 124         int oldbit;
 125
 126         __asm__ __volatile__(
 127                 "btl %2,%1\n\tsbbl %0,%0"
 128                 :"=r" (oldbit)
 129                 :"m" (ADDR),"Ir" (nr));
 130         return oldbit;
 131 }
 132
 133 #if 0
 134 #define test_bit(nr,addr) \
 135 (__builtin_constant_p(nr) ? \
 136  __constant_test_bit((nr),(addr)) : \
 137  __test_bit((nr),(addr)))
 138 #endif
 139
 140 /*
 141  * Find-bit routines..
 142  */
 143 int find_first_zero_bit(void * addr, unsigned size)
 144 {
 145         int d0, d1, d2;
 146         int res;
 147
 148         if (!size)
 149                 return 0;
 150         __asm__("cld\n\t"
 151                 "movl $-1,%%eax\n\t"
 152                 "xorl %%edx,%%edx\n\t"
 153                 "repe; scasl\n\t"
 154                 "je 1f\n\t"
 155                 "xorl -4(%%edi),%%eax\n\t"
 156                 "subl $4,%%edi\n\t"
 157                 "bsfl %%eax,%%edx\n"
 158                 "1:\tsubl %%ebx,%%edi\n\t"
 159                 "shll $3,%%edi\n\t"
 160                 "addl %%edi,%%edx"
 161                 :"=d" (res), "=&c" (d0), "=&D" (d1), "=&a" (d2)
 162                 :"1" ((size + 31) >> 5), "2" (addr), "b" (addr));
 163         return res;
 164 }
 165
 166 int find_next_zero_bit (void * addr, int size, int offset)
 167 {
 168         unsigned long * p = ((unsigned long *) addr) + (offset >> 5);
 169         int set = 0, bit = offset & 31, res;
 170
 171         if (bit) {
 172                 /*
 173                  * Look for zero in first byte
 174                  */
 175                 __asm__("bsfl %1,%0\n\t"
 176                         "jne 1f\n\t"
 177                         "movl $32, %0\n"
 178                         "1:"
 179                         : "=r" (set)
 180                         : "r" (~(*p >> bit)));
 181                 if (set < (32 - bit))
 182                         return set + offset;
 183                 set = 32 - bit;
 184                 p++;
 185         }
 186         /*
 187          * No zero yet, search remaining full bytes for a zero
 188          */
 189         res = find_first_zero_bit (p, size - 32 * (p - (unsigned long *) addr));
 190         return (offset + set + res);
 191 }
 192
 193 /*
 194  * ffz = Find First Zero in word. Undefined if no zero exists,
 195  * so code should check against ~0UL first..
 196  */
 197 unsigned long ffz(unsigned long word)
 198 {
 199         __asm__("bsfl %1,%0"
 200                 :"=r" (word)
 201                 :"r" (~word));
 202         return word;
 203 }