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 static inline int ll_get_order_round_up(unsigned long val)
  11 {
  12         return val != 1 ? ll_fls(val - 1) + 1 : 0;
  13 }
  14
  15 static inline int ll_get_order_round_down(unsigned long val)
  16 {
  17         return ll_fls(val);
  18 }
  19
  20 // Note that the multiword bit scans are endian and word size dependent.
  21 // They return -1 if no suitable bit was found.  Start and end are
  22 // in bits.
  23
  24 static inline int ll_multiword_ffs(unsigned long *bitmap, int start, int len)
  25 {
  26         static const int bits_per_long = sizeof(unsigned long) * 8;
  27         int off = start / bits_per_long;
  28         int shift_first = start % bits_per_long;
  29
  30         if (shift_first) {
  31                 unsigned long shifted = *bitmap >> shift_first;
  32
  33                 if (shifted)
  34                         return ll_ffs(shifted) + start;
  35
  36                 off++;
  37                 start = off * bits_per_long;
  38         }
  39
  40         while (off < len / bits_per_long) {
  41                 if (bitmap[off])
  42                         break;
  43
  44                 off++;
  45                 start += bits_per_long;
  46         }
  47
  48         if (start < len && bitmap[off]) {
  49                 int ret = start + ll_ffs(bitmap[off]);
  50
  51                 if (ret < len)
  52                         return ret;
  53         }
  54
  55         return -1;
  56 }
  57
  58 static inline int ll_multiword_ffc(unsigned long *bitmap, int start, int len)
  59 {
  60         static const int bits_per_long = sizeof(unsigned long) * 8;
  61         int off = start / bits_per_long;
  62         int shift_first = start % bits_per_long;
  63
  64         if (shift_first) {
  65                 unsigned long shifted = *bitmap >> shift_first;
  66
  67                 if (~shifted)
  68                         return ll_ffs(~shifted) + start;
  69
  70                 off++;
  71                 start = off * bits_per_long;
  72         }
  73
  74         while (off < len / bits_per_long) {
  75                 if (~bitmap[off])
  76                         break;
  77
  78                 off++;
  79                 start += bits_per_long;
  80         }
  81
  82         if (start < len && ~bitmap[off]) {
  83                 int ret = start + ll_ffs(~bitmap[off]);
  84
  85                 if (ret < len)
  86                         return ret;
  87         }
  88
  89         return -1;
  90 }
  91
  92 #endif