include/c/lowlevel/bitops.h

   1 // Bit manipulation functions.  These functions are not privileged.
   2
   3 #ifndef _LL_BITOPS_H
   4 #define _LL_BITOPS_H
   5
   6 #include <lowlevel/arch.h>
   7 #include <lowlevel/types.h>
   8 #include _LL_INC(bitops.h)
   9
  10 // Find First (least-significant) Set, counting from 0,
  11 // undefined if no bits set
  12
  13 static inline int ll_ffs(unsigned long val)
  14 {
  15         return __builtin_ctzl(val);
  16 }
  17
  18 // Find Last (most-significant) Set, counting from 0,
  19 // undefined if no bits set
  20
  21 static inline int ll_fls(unsigned long val)
  22 {
  23         return (sizeof(unsigned long)*8 - 1) ^ __builtin_clzl(val);
  24 }
  25
  26 // As above, except on 64-bit values regardless of sizeof(long).
  27 static inline int ll_ffs64(uint64_t val)
  28 {
  29         return __builtin_ctzll(val);
  30 }
  31
  32 // Find Last (most-significant) Set, counting from 0,
  33 // undefined if no bits set
  34
  35 static inline int ll_fls64(unsigned long val)
  36 {
  37         return (sizeof(unsigned long long)*8 - 1) ^ __builtin_clzll(val);
  38 }
  39
  40 static inline int ll_get_order_round_up(unsigned long val)
  41 {
  42         return val > 1 ? ll_fls(val - 1) + 1 : 0;
  43 }
  44
  45 static inline int ll_get_order_round_down(unsigned long val)
  46 {
  47         return ll_fls(val);
  48 }
  49
  50 // Note that the multiword bit scans are endian and word size dependent.
  51 // They return -1 if no suitable bit was found.  Start and end are
  52 // in bits.
  53
  54 static inline int ll_multiword_ffs(unsigned long *bitmap, int start, int len)
  55 {
  56         static const int bits_per_long = sizeof(unsigned long) * 8;
  57         int off = start / bits_per_long;
  58         int shift_first = start % bits_per_long;
  59
  60         if (shift_first) {
  61                 unsigned long shifted = *bitmap >> shift_first;
  62
  63                 if (shifted)
  64                         return ll_ffs(shifted) + start;
  65
  66                 off++;
  67                 start = off * bits_per_long;
  68         }
  69
  70         while (off < len / bits_per_long) {
  71                 if (bitmap[off])
  72                         break;
  73
  74                 off++;
  75                 start += bits_per_long;
  76         }
  77
  78         if (start < len && bitmap[off]) {
  79                 int ret = start + ll_ffs(bitmap[off]);
  80
  81                 if (ret < len)
  82                         return ret;
  83         }
  84
  85         return -1;
  86 }
  87
  88 static inline int ll_multiword_ffc(unsigned long *bitmap, int start, int len)
  89 {
  90         static const int bits_per_long = sizeof(unsigned long) * 8;
  91         int off = start / bits_per_long;
  92         int shift_first = start % bits_per_long;
  93
  94         if (shift_first) {
  95                 unsigned long shifted = *bitmap >> shift_first;
  96
  97                 if (~shifted)
  98                         return ll_ffs(~shifted) + start;
  99
 100                 off++;
 101                 start = off * bits_per_long;
 102         }
 103
 104         while (off < len / bits_per_long) {
 105                 if (~bitmap[off])
 106                         break;
 107
 108                 off++;
 109                 start += bits_per_long;
 110         }
 111
 112         if (start < len && ~bitmap[off]) {
 113                 int ret = start + ll_ffs(~bitmap[off]);
 114
 115                 if (ret < len)
 116                         return ret;
 117         }
 118
 119         return -1;
 120 }
 121
 122 #endif