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 #include <linux/module.h>
  14
  15 int find_next_bit(const unsigned long *addr, int size, int offset)
  16 {
  17         const unsigned long *base;
  18         const int NBITS = sizeof(*addr) * 8;
  19         unsigned long tmp;
  20
  21         base = addr;
  22         if (offset) {
  23                 int suboffset;
  24
  25                 addr += offset / NBITS;
  26
  27                 suboffset = offset % NBITS;
  28                 if (suboffset) {
  29                         tmp = *addr;
  30                         tmp >>= suboffset;
  31                         if (tmp)
  32                                 goto finish;
  33                 }
  34
  35                 addr++;
  36         }
  37
  38         while ((tmp = *addr) == 0)
  39                 addr++;
  40
  41         offset = (addr - base) * NBITS;
  42
  43  finish:
  44         /* count the remaining bits without using __ffs() since that takes a 32-bit arg */
  45         while (!(tmp & 0xff)) {
  46                 offset += 8;
  47                 tmp >>= 8;
  48         }
  49
  50         while (!(tmp & 1)) {
  51                 offset++;
  52                 tmp >>= 1;
  53         }
  54
  55         return offset;
  56 }
  57
  58 EXPORT_SYMBOL(find_next_bit);