tools/lib/util/find_next_bit.c

   1 /* find_next_bit.c: fallback find next bit implementation
   2  *
   3  * Copied from lib/find_next_bit.c to tools/lib/next_bit.c
   4  *
   5  * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
   6  * Written by David Howells (dhowells@redhat.com)
   7  *
   8  * This program is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU General Public License
  10  * as published by the Free Software Foundation; either version
  11  * 2 of the License, or (at your option) any later version.
  12  */
  13
  14 #include <linux/bitops.h>
  15 #include <asm/types.h>
  16 #include <asm/byteorder.h>
  17
  18 #define BITOP_WORD(nr)          ((nr) / BITS_PER_LONG)
  19
  20 #ifndef find_next_bit
  21 /*
  22  * Find the next set bit in a memory region.
  23  */
  24 unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
  25                             unsigned long offset)
  26 {
  27         const unsigned long *p = addr + BITOP_WORD(offset);
  28         unsigned long result = offset & ~(BITS_PER_LONG-1);
  29         unsigned long tmp;
  30
  31         if (offset >= size)
  32                 return size;
  33         size -= result;
  34         offset %= BITS_PER_LONG;
  35         if (offset) {
  36                 tmp = *(p++);
  37                 tmp &= (~0UL << offset);
  38                 if (size < BITS_PER_LONG)
  39                         goto found_first;
  40                 if (tmp)
  41                         goto found_middle;
  42                 size -= BITS_PER_LONG;
  43                 result += BITS_PER_LONG;
  44         }
  45         while (size & ~(BITS_PER_LONG-1)) {
  46                 if ((tmp = *(p++)))
  47                         goto found_middle;
  48                 result += BITS_PER_LONG;
  49                 size -= BITS_PER_LONG;
  50         }
  51         if (!size)
  52                 return result;
  53         tmp = *p;
  54
  55 found_first:
  56         tmp &= (~0UL >> (BITS_PER_LONG - size));
  57         if (tmp == 0UL)         /* Are any bits set? */
  58                 return result + size;   /* Nope. */
  59 found_middle:
  60         return result + __ffs(tmp);
  61 }
  62 #endif
  63
  64 #ifndef find_first_bit
  65 /*
  66  * Find the first set bit in a memory region.
  67  */
  68 unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
  69 {
  70         const unsigned long *p = addr;
  71         unsigned long result = 0;
  72         unsigned long tmp;
  73
  74         while (size & ~(BITS_PER_LONG-1)) {
  75                 if ((tmp = *(p++)))
  76                         goto found;
  77                 result += BITS_PER_LONG;
  78                 size -= BITS_PER_LONG;
  79         }
  80         if (!size)
  81                 return result;
  82
  83         tmp = (*p) & (~0UL >> (BITS_PER_LONG - size));
  84         if (tmp == 0UL)         /* Are any bits set? */
  85                 return result + size;   /* Nope. */
  86 found:
  87         return result + __ffs(tmp);
  88 }
  89 #endif