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_fls(int value)
  60 {
  61     afs_int32 i;
  62     /* tmp must be unsigned to avoid undefined behavior. */
  63     afs_uint32 tmp = value;
  64
  65     if (tmp == 0)
  66         return 0;
  67     /* This loop must terminate because tmp is nonzero and thus has at least
  68      * one bit set. */
  69     for (i = 32;; --i) {
  70         if (tmp & 0x80000000u)
  71             return i;
  72         else
  73             tmp <<= 1;
  74     }
  75     /* NOTREACHED */
  76 }
  77
  78 #endif /* OPENAFS_OPR_FFS_H */