lib/find_next_bit.c

   1 /* find_next_bit.c: fallback find next bit implementation
   2  *
   3  * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
   4  * Written by David Howells (dhowells@redhat.com)
   5  *
   6  * This program is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU General Public License
   8  * as published by the Free Software Foundation; either version
   9  * 2 of the License, or (at your option) any later version.
  10  */
  11
  12 #include <linux/bitops.h>
  13
  14 int find_next_bit(const unsigned long *addr, int size, int offset)
  15 {
  16         const unsigned long *base;
  17         const int NBITS = sizeof(*addr) * 8;
  18         unsigned long tmp;
  19
  20         base = addr;
  21         if (offset) {
  22                 int suboffset;
  23
  24                 addr += offset / NBITS;
  25
  26                 suboffset = offset % NBITS;
  27                 if (suboffset) {
  28                         tmp = *addr;
  29                         tmp >>= suboffset;
  30                         if (tmp)
  31                                 goto finish;
  32                 }
  33
  34                 addr++;
  35         }
  36
  37         while ((tmp = *addr) == 0)
  38                 addr++;
  39
  40         offset = (addr - base) * NBITS;
  41
  42  finish:
  43         /* count the remaining bits without using __ffs() since that takes a 32-bit arg */
  44         while (!(tmp & 0xff)) {
  45                 offset += 8;
  46                 tmp >>= 8;
  47         }
  48
  49         while (!(tmp & 1)) {
  50                 offset++;
  51                 tmp >>= 1;
  52         }
  53
  54         return offset;
  55 }