src/opr/ffs.h

   1 /*
   2  * Copyright (C) 2014 by the Massachusetts Institute of Technology.
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  *
   9  * * Redistributions of source code must retain the above copyright
  10  *   notice, this list of conditions and the following disclaimer.
  11  *
  12  * * Redistributions in binary form must reproduce the above copyright
  13  *   notice, this list of conditions and the following disclaimer in
  14  *   the documentation and/or other materials provided with the
  15  *   distribution.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  18  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  19  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  20  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  21  * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
  22  * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  23  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  24  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  25  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  26  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  27  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  28  * OF THE POSSIBILITY OF SUCH DAMAGE.
  29  */
  30
  31 /*
  32  * This contains portable implementations of the BSD ffs() suite of functions,
  33  * which locate the first or last bit set in a bit string.
  34  */
  35
  36 #ifndef OPENAFS_OPR_FFS_H
  37 #define OPENAFS_OPR_FFS_H
  38
  39 static_inline int
  40 opr_ffs(int value)
  41 {
  42     afs_int32 i;
  43     afs_uint32 tmp = value;
  44
  45     if (tmp == 0)
  46         return 0;
  47     /* This loop must terminate because tmp is nonzero and thus has at least
  48      * one bit set. */
  49     for (i = 1;; ++i) {
  50         if (tmp & 1u)
  51             return i;
  52         else
  53             tmp >>= 1;
  54     }
  55     /* NOTREACHED */
  56 }
  57
  58 static_inline int
  59 opr_ffsll(long long value)
  60 {
  61     afs_int32 i;
  62     afs_uint64 tmp = value;
  63
  64     if (tmp == 0)
  65         return 0;
  66     /* This loop must terminate because tmp is nonzero and thus has at least
  67      * one bit set. */
  68     for (i = 1;; ++i) {
  69         if (tmp & 1ull)
  70             return i;
  71         else
  72             tmp >>= 1;
  73     }
  74     /* NOTREACHED */
  75 }
  76
  77 static_inline int
  78 opr_fls(int value)
  79 {
  80     afs_int32 i;
  81     /* tmp must be unsigned to avoid undefined behavior. */
  82     afs_uint32 tmp = value;
  83
  84     if (tmp == 0)
  85         return 0;
  86     /* This loop must terminate because tmp is nonzero and thus has at least
  87      * one bit set. */
  88     for (i = 32;; --i) {
  89         if (tmp & 0x80000000u)
  90             return i;
  91         else
  92             tmp <<= 1;
  93     }
  94     /* NOTREACHED */
  95 }
  96
  97 static_inline int
  98 opr_flsll(long long value)
  99 {
 100     afs_int32 i;
 101     /* tmp must be unsigned to avoid undefined behavior. */
 102     afs_uint64 tmp = value;
 103
 104     if (tmp == 0)
 105         return 0;
 106     /* This loop must terminate because tmp is nonzero and thus has at least
 107      * one bit set. */
 108     for (i = 64;; --i) {
 109         if (tmp & 0x8000000000000000ull)
 110             return i;
 111         else
 112             tmp <<= 1;
 113     }
 114     /* NOTREACHED */
 115 }
 116
 117 #endif /* OPENAFS_OPR_FFS_H */