fs/xfs/xfs_bit.c

   1 /*
   2  * Copyright (c) 2000-2004 Silicon Graphics, Inc.  All Rights Reserved.
   3  *
   4  * This program is free software; you can redistribute it and/or modify it
   5  * under the terms of version 2 of the GNU General Public License as
   6  * published by the Free Software Foundation.
   7  *
   8  * This program is distributed in the hope that it would be useful, but
   9  * WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  11  *
  12  * Further, this software is distributed without any warranty that it is
  13  * free of the rightful claim of any third person regarding infringement
  14  * or the like.  Any license provided herein, whether implied or
  15  * otherwise, applies only to this software file.  Patent licenses, if
  16  * any, provided herein do not apply to combinations of this program with
  17  * other software, or any other product whatsoever.
  18  *
  19  * You should have received a copy of the GNU General Public License along
  20  * with this program; if not, write the Free Software Foundation, Inc., 59
  21  * Temple Place - Suite 330, Boston MA 02111-1307, USA.
  22  *
  23  * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
  24  * Mountain View, CA  94043, or:
  25  *
  26  * http://www.sgi.com
  27  *
  28  * For further information regarding this notice, see:
  29  *
  30  * http://oss.sgi.com/projects/GenInfo/SGIGPLNoticeExplan/
  31  */
  32
  33 /*
  34  * XFS bit manipulation routines, used in non-realtime code.
  35  */
  36
  37 #include "xfs.h"
  38 #include "xfs_bit.h"
  39 #include "xfs_log.h"
  40 #include "xfs_trans.h"
  41 #include "xfs_buf_item.h"
  42
  43
  44 #ifndef HAVE_ARCH_HIGHBIT
  45 /*
  46  * Index of high bit number in byte, -1 for none set, 0..7 otherwise.
  47  */
  48 const char xfs_highbit[256] = {
  49        -1, 0, 1, 1, 2, 2, 2, 2,                 /* 00 .. 07 */
  50         3, 3, 3, 3, 3, 3, 3, 3,                 /* 08 .. 0f */
  51         4, 4, 4, 4, 4, 4, 4, 4,                 /* 10 .. 17 */
  52         4, 4, 4, 4, 4, 4, 4, 4,                 /* 18 .. 1f */
  53         5, 5, 5, 5, 5, 5, 5, 5,                 /* 20 .. 27 */
  54         5, 5, 5, 5, 5, 5, 5, 5,                 /* 28 .. 2f */
  55         5, 5, 5, 5, 5, 5, 5, 5,                 /* 30 .. 37 */
  56         5, 5, 5, 5, 5, 5, 5, 5,                 /* 38 .. 3f */
  57         6, 6, 6, 6, 6, 6, 6, 6,                 /* 40 .. 47 */
  58         6, 6, 6, 6, 6, 6, 6, 6,                 /* 48 .. 4f */
  59         6, 6, 6, 6, 6, 6, 6, 6,                 /* 50 .. 57 */
  60         6, 6, 6, 6, 6, 6, 6, 6,                 /* 58 .. 5f */
  61         6, 6, 6, 6, 6, 6, 6, 6,                 /* 60 .. 67 */
  62         6, 6, 6, 6, 6, 6, 6, 6,                 /* 68 .. 6f */
  63         6, 6, 6, 6, 6, 6, 6, 6,                 /* 70 .. 77 */
  64         6, 6, 6, 6, 6, 6, 6, 6,                 /* 78 .. 7f */
  65         7, 7, 7, 7, 7, 7, 7, 7,                 /* 80 .. 87 */
  66         7, 7, 7, 7, 7, 7, 7, 7,                 /* 88 .. 8f */
  67         7, 7, 7, 7, 7, 7, 7, 7,                 /* 90 .. 97 */
  68         7, 7, 7, 7, 7, 7, 7, 7,                 /* 98 .. 9f */
  69         7, 7, 7, 7, 7, 7, 7, 7,                 /* a0 .. a7 */
  70         7, 7, 7, 7, 7, 7, 7, 7,                 /* a8 .. af */
  71         7, 7, 7, 7, 7, 7, 7, 7,                 /* b0 .. b7 */
  72         7, 7, 7, 7, 7, 7, 7, 7,                 /* b8 .. bf */
  73         7, 7, 7, 7, 7, 7, 7, 7,                 /* c0 .. c7 */
  74         7, 7, 7, 7, 7, 7, 7, 7,                 /* c8 .. cf */
  75         7, 7, 7, 7, 7, 7, 7, 7,                 /* d0 .. d7 */
  76         7, 7, 7, 7, 7, 7, 7, 7,                 /* d8 .. df */
  77         7, 7, 7, 7, 7, 7, 7, 7,                 /* e0 .. e7 */
  78         7, 7, 7, 7, 7, 7, 7, 7,                 /* e8 .. ef */
  79         7, 7, 7, 7, 7, 7, 7, 7,                 /* f0 .. f7 */
  80         7, 7, 7, 7, 7, 7, 7, 7,                 /* f8 .. ff */
  81 };
  82 #endif
  83
  84 /*
  85  * Count of bits set in byte, 0..8.
  86  */
  87 static const char xfs_countbit[256] = {
  88         0, 1, 1, 2, 1, 2, 2, 3,                 /* 00 .. 07 */
  89         1, 2, 2, 3, 2, 3, 3, 4,                 /* 08 .. 0f */
  90         1, 2, 2, 3, 2, 3, 3, 4,                 /* 10 .. 17 */
  91         2, 3, 3, 4, 3, 4, 4, 5,                 /* 18 .. 1f */
  92         1, 2, 2, 3, 2, 3, 3, 4,                 /* 20 .. 27 */
  93         2, 3, 3, 4, 3, 4, 4, 5,                 /* 28 .. 2f */
  94         2, 3, 3, 4, 3, 4, 4, 5,                 /* 30 .. 37 */
  95         3, 4, 4, 5, 4, 5, 5, 6,                 /* 38 .. 3f */
  96         1, 2, 2, 3, 2, 3, 3, 4,                 /* 40 .. 47 */
  97         2, 3, 3, 4, 3, 4, 4, 5,                 /* 48 .. 4f */
  98         2, 3, 3, 4, 3, 4, 4, 5,                 /* 50 .. 57 */
  99         3, 4, 4, 5, 4, 5, 5, 6,                 /* 58 .. 5f */
 100         2, 3, 3, 4, 3, 4, 4, 5,                 /* 60 .. 67 */
 101         3, 4, 4, 5, 4, 5, 5, 6,                 /* 68 .. 6f */
 102         3, 4, 4, 5, 4, 5, 5, 6,                 /* 70 .. 77 */
 103         4, 5, 5, 6, 5, 6, 6, 7,                 /* 78 .. 7f */
 104         1, 2, 2, 3, 2, 3, 3, 4,                 /* 80 .. 87 */
 105         2, 3, 3, 4, 3, 4, 4, 5,                 /* 88 .. 8f */
 106         2, 3, 3, 4, 3, 4, 4, 5,                 /* 90 .. 97 */
 107         3, 4, 4, 5, 4, 5, 5, 6,                 /* 98 .. 9f */
 108         2, 3, 3, 4, 3, 4, 4, 5,                 /* a0 .. a7 */
 109         3, 4, 4, 5, 4, 5, 5, 6,                 /* a8 .. af */
 110         3, 4, 4, 5, 4, 5, 5, 6,                 /* b0 .. b7 */
 111         4, 5, 5, 6, 5, 6, 6, 7,                 /* b8 .. bf */
 112         2, 3, 3, 4, 3, 4, 4, 5,                 /* c0 .. c7 */
 113         3, 4, 4, 5, 4, 5, 5, 6,                 /* c8 .. cf */
 114         3, 4, 4, 5, 4, 5, 5, 6,                 /* d0 .. d7 */
 115         4, 5, 5, 6, 5, 6, 6, 7,                 /* d8 .. df */
 116         3, 4, 4, 5, 4, 5, 5, 6,                 /* e0 .. e7 */
 117         4, 5, 5, 6, 5, 6, 6, 7,                 /* e8 .. ef */
 118         4, 5, 5, 6, 5, 6, 6, 7,                 /* f0 .. f7 */
 119         5, 6, 6, 7, 6, 7, 7, 8,                 /* f8 .. ff */
 120 };
 121
 122 /*
 123  * xfs_highbit32: get high bit set out of 32-bit argument, -1 if none set.
 124  */
 125 inline int
 126 xfs_highbit32(
 127         __uint32_t      v)
 128 {
 129 #ifdef HAVE_ARCH_HIGHBIT
 130         return highbit32(v);
 131 #else
 132         int             i;
 133
 134         if (v & 0xffff0000)
 135                 if (v & 0xff000000)
 136                         i = 24;
 137                 else
 138                         i = 16;
 139         else if (v & 0x0000ffff)
 140                 if (v & 0x0000ff00)
 141                         i = 8;
 142                 else
 143                         i = 0;
 144         else
 145                 return -1;
 146         return i + xfs_highbit[(v >> i) & 0xff];
 147 #endif
 148 }
 149
 150 /*
 151  * xfs_lowbit64: get low bit set out of 64-bit argument, -1 if none set.
 152  */
 153 int
 154 xfs_lowbit64(
 155         __uint64_t      v)
 156 {
 157         __uint32_t      w = (__uint32_t)v;
 158         int             n = 0;
 159
 160         if (w) {        /* lower bits */
 161                 n = ffs(w);
 162         } else {        /* upper bits */
 163                 w = (__uint32_t)(v >> 32);
 164                 if (w && (n = ffs(w)))
 165                         n += 32;
 166         }
 167         return n - 1;
 168 }
 169
 170 /*
 171  * xfs_highbit64: get high bit set out of 64-bit argument, -1 if none set.
 172  */
 173 int
 174 xfs_highbit64(
 175         __uint64_t      v)
 176 {
 177         __uint32_t      h = (__uint32_t)(v >> 32);
 178
 179         if (h)
 180                 return xfs_highbit32(h) + 32;
 181         return xfs_highbit32((__uint32_t)v);
 182 }
 183
 184
 185 /*
 186  * Count the number of bits set in the bitmap starting with bit
 187  * start_bit.  Size is the size of the bitmap in words.
 188  *
 189  * Do the counting by mapping a byte value to the number of set
 190  * bits for that value using the xfs_countbit array, i.e.
 191  * xfs_countbit[0] == 0, xfs_countbit[1] == 1, xfs_countbit[2] == 1,
 192  * xfs_countbit[3] == 2, etc.
 193  */
 194 int
 195 xfs_count_bits(uint *map, uint size, uint start_bit)
 196 {
 197         register int    bits;
 198         register unsigned char  *bytep;
 199         register unsigned char  *end_map;
 200         int             byte_bit;
 201
 202         bits = 0;
 203         end_map = (char*)(map + size);
 204         bytep = (char*)(map + (start_bit & ~0x7));
 205         byte_bit = start_bit & 0x7;
 206
 207         /*
 208          * If the caller fell off the end of the map, return 0.
 209          */
 210         if (bytep >= end_map) {
 211                 return (0);
 212         }
 213
 214         /*
 215          * If start_bit is not byte aligned, then process the
 216          * first byte separately.
 217          */
 218         if (byte_bit != 0) {
 219                 /*
 220                  * Shift off the bits we don't want to look at,
 221                  * before indexing into xfs_countbit.
 222                  */
 223                 bits += xfs_countbit[(*bytep >> byte_bit)];
 224                 bytep++;
 225         }
 226
 227         /*
 228          * Count the bits in each byte until the end of the bitmap.
 229          */
 230         while (bytep < end_map) {
 231                 bits += xfs_countbit[*bytep];
 232                 bytep++;
 233         }
 234
 235         return (bits);
 236 }
 237
 238 /*
 239  * Count the number of contiguous bits set in the bitmap starting with bit
 240  * start_bit.  Size is the size of the bitmap in words.
 241  */
 242 int
 243 xfs_contig_bits(uint *map, uint size, uint start_bit)
 244 {
 245         uint * p = ((unsigned int *) map) + (start_bit >> BIT_TO_WORD_SHIFT);
 246         uint result = 0;
 247         uint tmp;
 248
 249         size <<= BIT_TO_WORD_SHIFT;
 250
 251         ASSERT(start_bit < size);
 252         size -= start_bit & ~(NBWORD - 1);
 253         start_bit &= (NBWORD - 1);
 254         if (start_bit) {
 255                 tmp = *p++;
 256                 /* set to one first offset bits prior to start */
 257                 tmp |= (~0U >> (NBWORD-start_bit));
 258                 if (tmp != ~0U)
 259                         goto found;
 260                 result += NBWORD;
 261                 size -= NBWORD;
 262         }
 263         while (size) {
 264                 if ((tmp = *p++) != ~0U)
 265                         goto found;
 266                 result += NBWORD;
 267                 size -= NBWORD;
 268         }
 269         return result - start_bit;
 270 found:
 271         return result + ffz(tmp) - start_bit;
 272 }
 273
 274 /*
 275  * This takes the bit number to start looking from and
 276  * returns the next set bit from there.  It returns -1
 277  * if there are no more bits set or the start bit is
 278  * beyond the end of the bitmap.
 279  *
 280  * Size is the number of words, not bytes, in the bitmap.
 281  */
 282 int xfs_next_bit(uint *map, uint size, uint start_bit)
 283 {
 284         uint * p = ((unsigned int *) map) + (start_bit >> BIT_TO_WORD_SHIFT);
 285         uint result = start_bit & ~(NBWORD - 1);
 286         uint tmp;
 287
 288         size <<= BIT_TO_WORD_SHIFT;
 289
 290         if (start_bit >= size)
 291                 return -1;
 292         size -= result;
 293         start_bit &= (NBWORD - 1);
 294         if (start_bit) {
 295                 tmp = *p++;
 296                 /* set to zero first offset bits prior to start */
 297                 tmp &= (~0U << start_bit);
 298                 if (tmp != 0U)
 299                         goto found;
 300                 result += NBWORD;
 301                 size -= NBWORD;
 302         }
 303         while (size) {
 304                 if ((tmp = *p++) != 0U)
 305                         goto found;
 306                 result += NBWORD;
 307                 size -= NBWORD;
 308         }
 309         return -1;
 310 found:
 311         return result + ffs(tmp) - 1;
 312 }