ipc/bit_array.c

   1 /***************************************************************************
   2  * Copyright 1995, Technion, Israel Institute of Technology
   3  * Electrical Eng, Software Lab.
   4  * Author:    Michael Veksler.
   5  ***************************************************************************
   6  * File:      bit_array.c
   7  * Purpose :  manipulate array of bits
   8  * Portability: This is not completely portable, non CISC arcitectures
   9  *              Might not have atomic Clear/Set/Toggle bit. On those
  10  *              architectures semaphores should be used.
  11  * Big Endian Concerns: This code is big endian compatible,
  12  *              but the byte order will be different (i.e. bit 0 will be
  13  *              located in byte 3).
  14  ***************************************************************************
  15  */
  16
  17 #ifdef CONFIG_IPC
  18
  19 /*
  20 ** uncoment the following line to disable assertions,
  21 ** this may boost performance by up to 50%
  22 */
  23 /* #define NDEBUG */
  24
  25 #if defined(linux) && !defined(NO_ASM)
  26 #define HAS_BITOPS
  27 #endif
  28
  29 #include <stdio.h>
  30
  31 #include <assert.h>
  32
  33 #include "bit_array.h"
  34 #ifdef HAS_BITOPS
  35 #define inline __inline__  /* So we can compile with -ansi */
  36 #include <asm/bitops.h>
  37 #else
  38 static __inline__ int clear_bit(int bit, int *mem);
  39 static __inline__ int set_bit(int bit, int *mem);
  40 #endif /* HAS_BITOPS */
  41
  42
  43 #define INT_NR(bit_nr)       ((bit_nr) >> INT_LOG2)
  44 #define INT_COUNT(bit_count) INT_NR( bit_count + BITS_PER_INT - 1 )
  45 #define BIT_IN_INT(bit_nr)   ((bit_nr) & (BITS_PER_INT - 1))
  46
  47 #if !defined(HAS_BITOPS)
  48
  49 /* first_zero maps bytes value to the index of first zero bit */
  50 static char first_zero[256];
  51 static int arrays_initialized=0;
  52
  53
  54 /*
  55 ** initialize static arrays used for bit operations speedup.
  56 ** Currently initialized: first_zero[256]
  57 ** set "arrays_initialized" to inidate that arrays where initialized
  58 */
  59
  60 static void initialize_arrays()
  61 {
  62   int i;
  63   int bit;
  64
  65   for (i=0 ; i<256 ; i++) {
  66      /* find the first zero bit in `i' */
  67      for (bit=0 ; bit < BITS_PER_BYTE ; bit++)
  68         /* break if the bit is zero */
  69         if ( ( (1 << bit) & i )
  70              == 0)
  71            break;
  72      first_zero[i]= bit;
  73   }
  74   arrays_initialized=1;
  75 }
  76
  77 /*
  78 ** Find first zero bit in the integer.
  79 ** Assume there is at least one zero.
  80 */
  81 static __inline__ int find_zbit_in_integer(unsigned int integer)
  82 {
  83   int i;
  84
  85   /* find the zero bit */
  86   for (i=0 ; i < sizeof(int) ; i++, integer>>=8) {
  87      int byte= integer & 0xff;
  88
  89      if (byte != 0xff)
  90         return ( first_zero[ byte ]
  91                  + (i << BYTE_LOG2) );
  92   }
  93   assert(0);                       /* never reached */
  94   return 0;
  95 }
  96
  97 /* return -1 on failure */
  98 static __inline__ int find_first_zero_bit(unsigned *array, int bits)
  99 {
 100   unsigned int  integer;
 101   int i;
 102   int bytes=INT_COUNT(bits);
 103
 104   if (!arrays_initialized)
 105      initialize_arrays();
 106
 107   for ( i=bytes ; i ; i--, array++) {
 108      integer= *array;
 109
 110      /* test if integer contains a zero bit */
 111      if (integer != ~0U)
 112         return ( find_zbit_in_integer(integer)
 113                  + ((bytes-i) << INT_LOG2) );
 114   }
 115
 116   /* indicate failure */
 117   return -1;
 118 }
 119
 120 static __inline__ int test_bit(int pos, unsigned *array)
 121 {
 122   unsigned int integer;
 123   int bit = BIT_IN_INT(pos);
 124
 125   integer= array[ pos >> INT_LOG2 ];
 126
 127   return (  (integer & (1 << bit)) != 0
 128             ? 1
 129             : 0 ) ;
 130 }
 131
 132 /*
 133 ** The following two functions are x86 specific ,
 134 ** other processors will need porting
 135 */
 136
 137 /* inputs: bit number and memory address (32 bit) */
 138 /* output: Value of the bit before modification */
 139 static __inline__ int clear_bit(int bit, int *mem)
 140 {
 141   int ret;
 142
 143   __asm__("xor %1,%1
 144            btrl %2,%0
 145            adcl %1,%1"
 146           :"=m" (*mem), "=&r" (ret)
 147           :"r" (bit));
 148   return (ret);
 149 }
 150
 151 static __inline__ int set_bit(int bit, int *mem)
 152 {
 153   int ret;
 154   __asm__("xor %1,%1
 155            btsl %2,%0
 156            adcl %1,%1"
 157           :"=m" (*mem), "=&r" (ret)
 158           :"r" (bit));
 159   return (ret);
 160 }
 161
 162 #endif /* !deined(HAS_BITOPS) */
 163
 164
 165 /* AssembleArray: assemble an array object using existing data */
 166 bit_array *AssembleArray(bit_array *new_array, unsigned int *buff, int bits)
 167 {
 168   assert(new_array!=NULL);
 169   assert(buff!=NULL);
 170   assert(bits>0);
 171   assert((1 << INT_LOG2) == BITS_PER_INT); /* if fails, redefine INT_LOG2 */
 172
 173   new_array->bits=bits;
 174   new_array->array=buff;
 175   return new_array;
 176 }
 177
 178 /* ResetArray: reset the bit array to zeros */
 179 int ResetArray(bit_array *bits)
 180 {
 181   int i;
 182   int *p;
 183
 184   assert(bits!=NULL);
 185   assert(bits->array!=NULL);
 186
 187   for(i= INT_COUNT(bits->bits), p=bits->array; i ; p++, i--)
 188      *p=0;
 189   return 1;
 190 }
 191
 192
 193 /* VacantBit: find a vacant (zero) bit in the array,
 194  * Return: Bit index on success, -1 on failure.
 195  */
 196 int VacantBit(bit_array *bits)
 197 {
 198   int bit;
 199
 200   assert(bits!=NULL);
 201   assert(bits->array!=NULL);
 202
 203   bit= find_first_zero_bit(bits->array, bits->bits);
 204
 205   if (bit >= bits->bits)           /* failed? */
 206      return -1;
 207
 208   return bit;
 209 }
 210
 211 int SampleBit(bit_array *bits, int i)
 212 {
 213   assert(bits != NULL);
 214   assert(bits->array != NULL);
 215   assert(i >= 0  &&  i < bits->bits);
 216
 217   return ( test_bit(i,bits->array) != 0
 218            ? 1
 219            : 0
 220            );
 221 }
 222
 223
 224 /*
 225 ** Use "compare and exchange" mechanism to make sure
 226 ** that bits are not modified while "integer" value
 227 ** is calculated.
 228 **
 229 ** This may be the slowest technique, but it is the most portable
 230 ** (Since most architectures have compare and exchange command)
 231 */
 232 int AssignBit(bit_array *bits, int bit_nr, int val)
 233 {
 234   int ret;
 235
 236   assert(bits != NULL);
 237   assert(bits->array != NULL);
 238   assert(val==0 || val==1);
 239   assert(bit_nr >= 0  &&  bit_nr < bits->bits);
 240
 241   if (val==0)
 242      ret= clear_bit(BIT_IN_INT(bit_nr), &bits->array[ INT_NR(bit_nr) ]);
 243   else
 244      ret= set_bit(BIT_IN_INT(bit_nr), &bits->array[ INT_NR(bit_nr) ]);
 245
 246   return ( (ret!=0) ? 1 : 0);
 247 }
 248
 249 /*
 250 ** Allocate a free bit (==0) and make it used (==1).
 251 ** This operation is guaranteed to resemble an atomic instruction.
 252 **
 253 ** Return: allocated bit index, or -1 on failure.
 254 **
 255 ** There is a crack between locating free bit, and allocating it.
 256 ** We assign 1 to the bit, test it was not '1' before the assignment.
 257 ** If it was, restart the seek and assign cycle.
 258 **
 259 */
 260
 261 int AllocateBit(bit_array *bits)
 262 {
 263   int bit_nr;
 264   int orig_bit;
 265
 266   assert(bits != NULL);
 267   assert(bits->array != NULL);
 268
 269   do {
 270      bit_nr= VacantBit(bits);
 271
 272      if (bit_nr == -1)             /* No vacant bit ? */
 273         return -1;
 274
 275      orig_bit = AssignBit(bits, bit_nr, 1);
 276   } while (orig_bit != 0);         /* it got assigned before we tried */
 277
 278   return bit_nr;
 279 }
 280
 281 #endif  /* CONFIG_IPC */