libxfs/xfs_bit.c

   1 /*
   2  * Copyright (c) 2000 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
  39 /*
  40  * Index of low bit number in byte, -1 for none set, 0..7 otherwise.
  41  */
  42 const char xfs_lowbit[256] = {
  43        -1, 0, 1, 0, 2, 0, 1, 0,                 /* 00 .. 07 */
  44         3, 0, 1, 0, 2, 0, 1, 0,                 /* 08 .. 0f */
  45         4, 0, 1, 0, 2, 0, 1, 0,                 /* 10 .. 17 */
  46         3, 0, 1, 0, 2, 0, 1, 0,                 /* 18 .. 1f */
  47         5, 0, 1, 0, 2, 0, 1, 0,                 /* 20 .. 27 */
  48         3, 0, 1, 0, 2, 0, 1, 0,                 /* 28 .. 2f */
  49         4, 0, 1, 0, 2, 0, 1, 0,                 /* 30 .. 37 */
  50         3, 0, 1, 0, 2, 0, 1, 0,                 /* 38 .. 3f */
  51         6, 0, 1, 0, 2, 0, 1, 0,                 /* 40 .. 47 */
  52         3, 0, 1, 0, 2, 0, 1, 0,                 /* 48 .. 4f */
  53         4, 0, 1, 0, 2, 0, 1, 0,                 /* 50 .. 57 */
  54         3, 0, 1, 0, 2, 0, 1, 0,                 /* 58 .. 5f */
  55         5, 0, 1, 0, 2, 0, 1, 0,                 /* 60 .. 67 */
  56         3, 0, 1, 0, 2, 0, 1, 0,                 /* 68 .. 6f */
  57         4, 0, 1, 0, 2, 0, 1, 0,                 /* 70 .. 77 */
  58         3, 0, 1, 0, 2, 0, 1, 0,                 /* 78 .. 7f */
  59         7, 0, 1, 0, 2, 0, 1, 0,                 /* 80 .. 87 */
  60         3, 0, 1, 0, 2, 0, 1, 0,                 /* 88 .. 8f */
  61         4, 0, 1, 0, 2, 0, 1, 0,                 /* 90 .. 97 */
  62         3, 0, 1, 0, 2, 0, 1, 0,                 /* 98 .. 9f */
  63         5, 0, 1, 0, 2, 0, 1, 0,                 /* a0 .. a7 */
  64         3, 0, 1, 0, 2, 0, 1, 0,                 /* a8 .. af */
  65         4, 0, 1, 0, 2, 0, 1, 0,                 /* b0 .. b7 */
  66         3, 0, 1, 0, 2, 0, 1, 0,                 /* b8 .. bf */
  67         6, 0, 1, 0, 2, 0, 1, 0,                 /* c0 .. c7 */
  68         3, 0, 1, 0, 2, 0, 1, 0,                 /* c8 .. cf */
  69         4, 0, 1, 0, 2, 0, 1, 0,                 /* d0 .. d7 */
  70         3, 0, 1, 0, 2, 0, 1, 0,                 /* d8 .. df */
  71         5, 0, 1, 0, 2, 0, 1, 0,                 /* e0 .. e7 */
  72         3, 0, 1, 0, 2, 0, 1, 0,                 /* e8 .. ef */
  73         4, 0, 1, 0, 2, 0, 1, 0,                 /* f0 .. f7 */
  74         3, 0, 1, 0, 2, 0, 1, 0,                 /* f8 .. ff */
  75 };
  76
  77 /*
  78  * Index of high bit number in byte, -1 for none set, 0..7 otherwise.
  79  */
  80 const char xfs_highbit[256] = {
  81        -1, 0, 1, 1, 2, 2, 2, 2,                 /* 00 .. 07 */
  82         3, 3, 3, 3, 3, 3, 3, 3,                 /* 08 .. 0f */
  83         4, 4, 4, 4, 4, 4, 4, 4,                 /* 10 .. 17 */
  84         4, 4, 4, 4, 4, 4, 4, 4,                 /* 18 .. 1f */
  85         5, 5, 5, 5, 5, 5, 5, 5,                 /* 20 .. 27 */
  86         5, 5, 5, 5, 5, 5, 5, 5,                 /* 28 .. 2f */
  87         5, 5, 5, 5, 5, 5, 5, 5,                 /* 30 .. 37 */
  88         5, 5, 5, 5, 5, 5, 5, 5,                 /* 38 .. 3f */
  89         6, 6, 6, 6, 6, 6, 6, 6,                 /* 40 .. 47 */
  90         6, 6, 6, 6, 6, 6, 6, 6,                 /* 48 .. 4f */
  91         6, 6, 6, 6, 6, 6, 6, 6,                 /* 50 .. 57 */
  92         6, 6, 6, 6, 6, 6, 6, 6,                 /* 58 .. 5f */
  93         6, 6, 6, 6, 6, 6, 6, 6,                 /* 60 .. 67 */
  94         6, 6, 6, 6, 6, 6, 6, 6,                 /* 68 .. 6f */
  95         6, 6, 6, 6, 6, 6, 6, 6,                 /* 70 .. 77 */
  96         6, 6, 6, 6, 6, 6, 6, 6,                 /* 78 .. 7f */
  97         7, 7, 7, 7, 7, 7, 7, 7,                 /* 80 .. 87 */
  98         7, 7, 7, 7, 7, 7, 7, 7,                 /* 88 .. 8f */
  99         7, 7, 7, 7, 7, 7, 7, 7,                 /* 90 .. 97 */
 100         7, 7, 7, 7, 7, 7, 7, 7,                 /* 98 .. 9f */
 101         7, 7, 7, 7, 7, 7, 7, 7,                 /* a0 .. a7 */
 102         7, 7, 7, 7, 7, 7, 7, 7,                 /* a8 .. af */
 103         7, 7, 7, 7, 7, 7, 7, 7,                 /* b0 .. b7 */
 104         7, 7, 7, 7, 7, 7, 7, 7,                 /* b8 .. bf */
 105         7, 7, 7, 7, 7, 7, 7, 7,                 /* c0 .. c7 */
 106         7, 7, 7, 7, 7, 7, 7, 7,                 /* c8 .. cf */
 107         7, 7, 7, 7, 7, 7, 7, 7,                 /* d0 .. d7 */
 108         7, 7, 7, 7, 7, 7, 7, 7,                 /* d8 .. df */
 109         7, 7, 7, 7, 7, 7, 7, 7,                 /* e0 .. e7 */
 110         7, 7, 7, 7, 7, 7, 7, 7,                 /* e8 .. ef */
 111         7, 7, 7, 7, 7, 7, 7, 7,                 /* f0 .. f7 */
 112         7, 7, 7, 7, 7, 7, 7, 7,                 /* f8 .. ff */
 113 };
 114
 115 /*
 116  * Count of bits set in byte, 0..8.
 117  */
 118 const char xfs_countbit[256] = {
 119         0, 1, 1, 2, 1, 2, 2, 3,                 /* 00 .. 07 */
 120         1, 2, 2, 3, 2, 3, 3, 4,                 /* 08 .. 0f */
 121         1, 2, 2, 3, 2, 3, 3, 4,                 /* 10 .. 17 */
 122         2, 3, 3, 4, 3, 4, 4, 5,                 /* 18 .. 1f */
 123         1, 2, 2, 3, 2, 3, 3, 4,                 /* 20 .. 27 */
 124         2, 3, 3, 4, 3, 4, 4, 5,                 /* 28 .. 2f */
 125         2, 3, 3, 4, 3, 4, 4, 5,                 /* 30 .. 37 */
 126         3, 4, 4, 5, 4, 5, 5, 6,                 /* 38 .. 3f */
 127         1, 2, 2, 3, 2, 3, 3, 4,                 /* 40 .. 47 */
 128         2, 3, 3, 4, 3, 4, 4, 5,                 /* 48 .. 4f */
 129         2, 3, 3, 4, 3, 4, 4, 5,                 /* 50 .. 57 */
 130         3, 4, 4, 5, 4, 5, 5, 6,                 /* 58 .. 5f */
 131         2, 3, 3, 4, 3, 4, 4, 5,                 /* 60 .. 67 */
 132         3, 4, 4, 5, 4, 5, 5, 6,                 /* 68 .. 6f */
 133         3, 4, 4, 5, 4, 5, 5, 6,                 /* 70 .. 77 */
 134         4, 5, 5, 6, 5, 6, 6, 7,                 /* 78 .. 7f */
 135         1, 2, 2, 3, 2, 3, 3, 4,                 /* 80 .. 87 */
 136         2, 3, 3, 4, 3, 4, 4, 5,                 /* 88 .. 8f */
 137         2, 3, 3, 4, 3, 4, 4, 5,                 /* 90 .. 97 */
 138         3, 4, 4, 5, 4, 5, 5, 6,                 /* 98 .. 9f */
 139         2, 3, 3, 4, 3, 4, 4, 5,                 /* a0 .. a7 */
 140         3, 4, 4, 5, 4, 5, 5, 6,                 /* a8 .. af */
 141         3, 4, 4, 5, 4, 5, 5, 6,                 /* b0 .. b7 */
 142         4, 5, 5, 6, 5, 6, 6, 7,                 /* b8 .. bf */
 143         2, 3, 3, 4, 3, 4, 4, 5,                 /* c0 .. c7 */
 144         3, 4, 4, 5, 4, 5, 5, 6,                 /* c8 .. cf */
 145         3, 4, 4, 5, 4, 5, 5, 6,                 /* d0 .. d7 */
 146         4, 5, 5, 6, 5, 6, 6, 7,                 /* d8 .. df */
 147         3, 4, 4, 5, 4, 5, 5, 6,                 /* e0 .. e7 */
 148         4, 5, 5, 6, 5, 6, 6, 7,                 /* e8 .. ef */
 149         4, 5, 5, 6, 5, 6, 6, 7,                 /* f0 .. f7 */
 150         5, 6, 6, 7, 6, 7, 7, 8,                 /* f8 .. ff */
 151 };
 152
 153 /*
 154  * xfs_highbit32: get high bit set out of 32-bit argument, -1 if none set.
 155  */
 156 int
 157 xfs_highbit32(
 158         __uint32_t      v)
 159 {
 160         int             i;
 161
 162         if (v & 0xffff0000)
 163                 if (v & 0xff000000)
 164                         i = 24;
 165                 else
 166                         i = 16;
 167         else if (v & 0x0000ffff)
 168                 if (v & 0x0000ff00)
 169                         i = 8;
 170                 else
 171                         i = 0;
 172         else
 173                 return -1;
 174         return i + xfs_highbit[(v >> i) & 0xff];
 175 }
 176
 177 /*
 178  * xfs_lowbit64: get low bit set out of 64-bit argument, -1 if none set.
 179  */
 180 int
 181 xfs_lowbit64(
 182         __uint64_t      v)
 183 {
 184         int             i;
 185 #if XFS_64
 186         if (v & 0x00000000ffffffff)
 187                 if (v & 0x000000000000ffff)
 188                         if (v & 0x00000000000000ff)
 189                                 i = 0;
 190                         else
 191                                 i = 8;
 192                 else
 193                         if (v & 0x0000000000ff0000)
 194                                 i = 16;
 195                         else
 196                                 i = 24;
 197         else if (v & 0xffffffff00000000)
 198                 if (v & 0x0000ffff00000000)
 199                         if (v & 0x000000ff00000000)
 200                                 i = 32;
 201                         else
 202                                 i = 40;
 203                 else
 204                         if (v & 0x00ff000000000000)
 205                                 i = 48;
 206                         else
 207                                 i = 56;
 208         else
 209                 return -1;
 210         return i + xfs_lowbit[(v >> i) & 0xff];
 211 #else
 212         __uint32_t      vw;
 213
 214         if (vw = v) {
 215                 if (vw & 0x0000ffff)
 216                         if (vw & 0x000000ff)
 217                                 i = 0;
 218                         else
 219                                 i = 8;
 220                 else
 221                         if (vw & 0x00ff0000)
 222                                 i = 16;
 223                         else
 224                                 i = 24;
 225                 return i + xfs_lowbit[(vw >> i) & 0xff];
 226         } else if (vw = v >> 32) {
 227                 if (vw & 0x0000ffff)
 228                         if (vw & 0x000000ff)
 229                                 i = 32;
 230                         else
 231                                 i = 40;
 232                 else
 233                         if (vw & 0x00ff0000)
 234                                 i = 48;
 235                         else
 236                                 i = 56;
 237                 return i + xfs_lowbit[(vw >> (i - 32)) & 0xff];
 238         } else
 239                 return -1;
 240 #endif
 241 }
 242
 243 /*
 244  * xfs_highbit64: get high bit set out of 64-bit argument, -1 if none set.
 245  */
 246 int
 247 xfs_highbit64(
 248         __uint64_t      v)
 249 {
 250         int             i;
 251 #if  XFS_64
 252         if (v & 0xffffffff00000000)
 253                 if (v & 0xffff000000000000)
 254                         if (v & 0xff00000000000000)
 255                                 i = 56;
 256                         else
 257                                 i = 48;
 258                 else
 259                         if (v & 0x0000ff0000000000)
 260                                 i = 40;
 261                         else
 262                                 i = 32;
 263         else if (v & 0x00000000ffffffff)
 264                 if (v & 0x00000000ffff0000)
 265                         if (v & 0x00000000ff000000)
 266                                 i = 24;
 267                         else
 268                                 i = 16;
 269                 else
 270                         if (v & 0x000000000000ff00)
 271                                 i = 8;
 272                         else
 273                                 i = 0;
 274         else
 275                 return -1;
 276         return i + xfs_highbit[(v >> i) & 0xff];
 277 #else
 278         __uint32_t      vw;
 279
 280         if (vw = v >> 32) {
 281                 if (vw & 0xffff0000)
 282                         if (vw & 0xff000000)
 283                                 i = 56;
 284                         else
 285                                 i = 48;
 286                 else
 287                         if (vw & 0x0000ff00)
 288                                 i = 40;
 289                         else
 290                                 i = 32;
 291                 return i + xfs_highbit[(vw >> (i - 32)) & 0xff];
 292         } else if (vw = v) {
 293                 if (vw & 0xffff0000)
 294                         if (vw & 0xff000000)
 295                                 i = 24;
 296                         else
 297                                 i = 16;
 298                 else
 299                         if (vw & 0x0000ff00)
 300                                 i = 8;
 301                         else
 302                                 i = 0;
 303                 return i + xfs_highbit[(vw >> i) & 0xff];
 304         } else
 305                 return -1;
 306 #endif
 307 }