fs/xfs/xfs_bit.c

   1 /*
   2  * Copyright (c) 2000-2002 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         int n;
 158         n = ffs((unsigned)v);
 159         if (n <= 0) {
 160                 n = ffs(v >> 32);
 161                 if (n >= 0)
 162                         n+=32;
 163         }
 164         return (n <= 0) ? n : n-1;
 165 }
 166
 167 /*
 168  * xfs_highbit64: get high bit set out of 64-bit argument, -1 if none set.
 169  */
 170 int
 171 xfs_highbit64(
 172         __uint64_t      v)
 173 {
 174         __uint32_t h = v >> 32;
 175         if (h)
 176                 return xfs_highbit32(h) + 32;
 177         return xfs_highbit32((__u32)v);
 178 }
 179
 180
 181 /*
 182  * Count the number of bits set in the bitmap starting with bit
 183  * start_bit.  Size is the size of the bitmap in words.
 184  *
 185  * Do the counting by mapping a byte value to the number of set
 186  * bits for that value using the xfs_countbit array, i.e.
 187  * xfs_countbit[0] == 0, xfs_countbit[1] == 1, xfs_countbit[2] == 1,
 188  * xfs_countbit[3] == 2, etc.
 189  */
 190 int
 191 xfs_count_bits(uint *map, uint size, uint start_bit)
 192 {
 193         register int    bits;
 194         register unsigned char  *bytep;
 195         register unsigned char  *end_map;
 196         int             byte_bit;
 197
 198         bits = 0;
 199         end_map = (char*)(map + size);
 200         bytep = (char*)(map + (start_bit & ~0x7));
 201         byte_bit = start_bit & 0x7;
 202
 203         /*
 204          * If the caller fell off the end of the map, return 0.
 205          */
 206         if (bytep >= end_map) {
 207                 return (0);
 208         }
 209
 210         /*
 211          * If start_bit is not byte aligned, then process the
 212          * first byte separately.
 213          */
 214         if (byte_bit != 0) {
 215                 /*
 216                  * Shift off the bits we don't want to look at,
 217                  * before indexing into xfs_countbit.
 218                  */
 219                 bits += xfs_countbit[(*bytep >> byte_bit)];
 220                 bytep++;
 221         }
 222
 223         /*
 224          * Count the bits in each byte until the end of the bitmap.
 225          */
 226         while (bytep < end_map) {
 227                 bits += xfs_countbit[*bytep];
 228                 bytep++;
 229         }
 230
 231         return (bits);
 232 }
 233
 234 /*
 235  * Count the number of contiguous bits set in the bitmap starting with bit
 236  * start_bit.  Size is the size of the bitmap in words.
 237  */
 238 int
 239 xfs_contig_bits(uint *map, uint size, uint start_bit)
 240 {
 241         uint * p = ((unsigned int *) map) + (start_bit >> BIT_TO_WORD_SHIFT);
 242         uint result = 0;
 243         uint tmp;
 244
 245         size <<= BIT_TO_WORD_SHIFT;
 246
 247         ASSERT(start_bit < size);
 248         size -= start_bit & ~(NBWORD - 1);
 249         start_bit &= (NBWORD - 1);
 250         if (start_bit) {
 251                 tmp = *p++;
 252                 /* set to one first offset bits prior to start */
 253                 tmp |= (~0U >> (NBWORD-start_bit));
 254                 if (tmp != ~0U)
 255                         goto found;
 256                 result += NBWORD;
 257                 size -= NBWORD;
 258         }
 259         while (size) {
 260                 if ((tmp = *p++) != ~0U)
 261                         goto found;
 262                 result += NBWORD;
 263                 size -= NBWORD;
 264         }
 265         return result - start_bit;
 266 found:
 267         return result + ffz(tmp) - start_bit;
 268 }
 269
 270 /*
 271  * This takes the bit number to start looking from and
 272  * returns the next set bit from there.  It returns -1
 273  * if there are no more bits set or the start bit is
 274  * beyond the end of the bitmap.
 275  *
 276  * Size is the number of words, not bytes, in the bitmap.
 277  */
 278 int xfs_next_bit(uint *map, uint size, uint start_bit)
 279 {
 280         uint * p = ((unsigned int *) map) + (start_bit >> BIT_TO_WORD_SHIFT);
 281         uint result = start_bit & ~(NBWORD - 1);
 282         uint tmp;
 283
 284         size <<= BIT_TO_WORD_SHIFT;
 285
 286         if (start_bit >= size)
 287                 return -1;
 288         size -= result;
 289         start_bit &= (NBWORD - 1);
 290         if (start_bit) {
 291                 tmp = *p++;
 292                 /* set to zero first offset bits prior to start */
 293                 tmp &= (~0U << start_bit);
 294                 if (tmp != 0U)
 295                         goto found;
 296                 result += NBWORD;
 297                 size -= NBWORD;
 298         }
 299         while (size) {
 300                 if ((tmp = *p++) != 0U)
 301                         goto found;
 302                 result += NBWORD;
 303                 size -= NBWORD;
 304         }
 305         return -1;
 306 found:
 307         return result + ffs(tmp) - 1;
 308 }