find_next_bit.c

Version: - FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10

    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/export.h>
   14 #include <asm/types.h>
   15 #include <asm/byteorder.h>
   16 
   17 #define BITOP_WORD(nr)          ((nr) / BITS_PER_LONG)
   18 
   19 #ifndef find_next_bit
   20 /*
   21  * Find the next set bit in a memory region.
   22  */
   23 unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
   24                             unsigned long offset)
   25 {
   26         const unsigned long *p = addr + BITOP_WORD(offset);
   27         unsigned long result = offset & ~(BITS_PER_LONG-1);
   28         unsigned long tmp;
   29 
   30         if (offset >= size)
   31                 return size;
   32         size -= result;
   33         offset %= BITS_PER_LONG;
   34         if (offset) {
   35                 tmp = *(p++);
   36                 tmp &= (~0UL << offset);
   37                 if (size < BITS_PER_LONG)
   38                         goto found_first;
   39                 if (tmp)
   40                         goto found_middle;
   41                 size -= BITS_PER_LONG;
   42                 result += BITS_PER_LONG;
   43         }
   44         while (size & ~(BITS_PER_LONG-1)) {
   45                 if ((tmp = *(p++)))
   46                         goto found_middle;
   47                 result += BITS_PER_LONG;
   48                 size -= BITS_PER_LONG;
   49         }
   50         if (!size)
   51                 return result;
   52         tmp = *p;
   53 
   54 found_first:
   55         tmp &= (~0UL >> (BITS_PER_LONG - size));
   56         if (tmp == 0UL)         /* Are any bits set? */
   57                 return result + size;   /* Nope. */
   58 found_middle:
   59         return result + __ffs(tmp);
   60 }
   61 EXPORT_SYMBOL(find_next_bit);
   62 #endif
   63 
   64 #ifndef find_next_zero_bit
   65 /*
   66  * This implementation of find_{first,next}_zero_bit was stolen from
   67  * Linus' asm-alpha/bitops.h.
   68  */
   69 unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
   70                                  unsigned long offset)
   71 {
   72         const unsigned long *p = addr + BITOP_WORD(offset);
   73         unsigned long result = offset & ~(BITS_PER_LONG-1);
   74         unsigned long tmp;
   75 
   76         if (offset >= size)
   77                 return size;
   78         size -= result;
   79         offset %= BITS_PER_LONG;
   80         if (offset) {
   81                 tmp = *(p++);
   82                 tmp |= ~0UL >> (BITS_PER_LONG - offset);
   83                 if (size < BITS_PER_LONG)
   84                         goto found_first;
   85                 if (~tmp)
   86                         goto found_middle;
   87                 size -= BITS_PER_LONG;
   88                 result += BITS_PER_LONG;
   89         }
   90         while (size & ~(BITS_PER_LONG-1)) {
   91                 if (~(tmp = *(p++)))
   92                         goto found_middle;
   93                 result += BITS_PER_LONG;
   94                 size -= BITS_PER_LONG;
   95         }
   96         if (!size)
   97                 return result;
   98         tmp = *p;
   99 
  100 found_first:
  101         tmp |= ~0UL << size;
  102         if (tmp == ~0UL)        /* Are any bits zero? */
  103                 return result + size;   /* Nope. */
  104 found_middle:
  105         return result + ffz(tmp);
  106 }
  107 EXPORT_SYMBOL(find_next_zero_bit);
  108 #endif
  109 
  110 #ifndef find_first_bit
  111 /*
  112  * Find the first set bit in a memory region.
  113  */
  114 unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
  115 {
  116         const unsigned long *p = addr;
  117         unsigned long result = 0;
  118         unsigned long tmp;
  119 
  120         while (size & ~(BITS_PER_LONG-1)) {
  121                 if ((tmp = *(p++)))
  122                         goto found;
  123                 result += BITS_PER_LONG;
  124                 size -= BITS_PER_LONG;
  125         }
  126         if (!size)
  127                 return result;
  128 
  129         tmp = (*p) & (~0UL >> (BITS_PER_LONG - size));
  130         if (tmp == 0UL)         /* Are any bits set? */
  131                 return result + size;   /* Nope. */
  132 found:
  133         return result + __ffs(tmp);
  134 }
  135 EXPORT_SYMBOL(find_first_bit);
  136 #endif
  137 
  138 #ifndef find_first_zero_bit
  139 /*
  140  * Find the first cleared bit in a memory region.
  141  */
  142 unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
  143 {
  144         const unsigned long *p = addr;
  145         unsigned long result = 0;
  146         unsigned long tmp;
  147 
  148         while (size & ~(BITS_PER_LONG-1)) {
  149                 if (~(tmp = *(p++)))
  150                         goto found;
  151                 result += BITS_PER_LONG;
  152                 size -= BITS_PER_LONG;
  153         }
  154         if (!size)
  155                 return result;
  156 
  157         tmp = (*p) | (~0UL << size);
  158         if (tmp == ~0UL)        /* Are any bits zero? */
  159                 return result + size;   /* Nope. */
  160 found:
  161         return result + ffz(tmp);
  162 }
  163 EXPORT_SYMBOL(find_first_zero_bit);
  164 #endif
  165 
  166 #ifdef __BIG_ENDIAN
  167 
  168 /* include/linux/byteorder does not support "unsigned long" type */
  169 static inline unsigned long ext2_swabp(const unsigned long * x)
  170 {
  171 #if BITS_PER_LONG == 64
  172         return (unsigned long) __swab64p((u64 *) x);
  173 #elif BITS_PER_LONG == 32
  174         return (unsigned long) __swab32p((u32 *) x);
  175 #else
  176 #error BITS_PER_LONG not defined
  177 #endif
  178 }
  179 
  180 /* include/linux/byteorder doesn't support "unsigned long" type */
  181 static inline unsigned long ext2_swab(const unsigned long y)
  182 {
  183 #if BITS_PER_LONG == 64
  184         return (unsigned long) __swab64((u64) y);
  185 #elif BITS_PER_LONG == 32
  186         return (unsigned long) __swab32((u32) y);
  187 #else
  188 #error BITS_PER_LONG not defined
  189 #endif
  190 }
  191 
  192 #ifndef find_next_zero_bit_le
  193 unsigned long find_next_zero_bit_le(const void *addr, unsigned
  194                 long size, unsigned long offset)
  195 {
  196         const unsigned long *p = addr;
  197         unsigned long result = offset & ~(BITS_PER_LONG - 1);
  198         unsigned long tmp;
  199 
  200         if (offset >= size)
  201                 return size;
  202         p += BITOP_WORD(offset);
  203         size -= result;
  204         offset &= (BITS_PER_LONG - 1UL);
  205         if (offset) {
  206                 tmp = ext2_swabp(p++);
  207                 tmp |= (~0UL >> (BITS_PER_LONG - offset));
  208                 if (size < BITS_PER_LONG)
  209                         goto found_first;
  210                 if (~tmp)
  211                         goto found_middle;
  212                 size -= BITS_PER_LONG;
  213                 result += BITS_PER_LONG;
  214         }
  215 
  216         while (size & ~(BITS_PER_LONG - 1)) {
  217                 if (~(tmp = *(p++)))
  218                         goto found_middle_swap;
  219                 result += BITS_PER_LONG;
  220                 size -= BITS_PER_LONG;
  221         }
  222         if (!size)
  223                 return result;
  224         tmp = ext2_swabp(p);
  225 found_first:
  226         tmp |= ~0UL << size;
  227         if (tmp == ~0UL)        /* Are any bits zero? */
  228                 return result + size; /* Nope. Skip ffz */
  229 found_middle:
  230         return result + ffz(tmp);
  231 
  232 found_middle_swap:
  233         return result + ffz(ext2_swab(tmp));
  234 }
  235 EXPORT_SYMBOL(find_next_zero_bit_le);
  236 #endif
  237 
  238 #ifndef find_next_bit_le
  239 unsigned long find_next_bit_le(const void *addr, unsigned
  240                 long size, unsigned long offset)
  241 {
  242         const unsigned long *p = addr;
  243         unsigned long result = offset & ~(BITS_PER_LONG - 1);
  244         unsigned long tmp;
  245 
  246         if (offset >= size)
  247                 return size;
  248         p += BITOP_WORD(offset);
  249         size -= result;
  250         offset &= (BITS_PER_LONG - 1UL);
  251         if (offset) {
  252                 tmp = ext2_swabp(p++);
  253                 tmp &= (~0UL << offset);
  254                 if (size < BITS_PER_LONG)
  255                         goto found_first;
  256                 if (tmp)
  257                         goto found_middle;
  258                 size -= BITS_PER_LONG;
  259                 result += BITS_PER_LONG;
  260         }
  261 
  262         while (size & ~(BITS_PER_LONG - 1)) {
  263                 tmp = *(p++);
  264                 if (tmp)
  265                         goto found_middle_swap;
  266                 result += BITS_PER_LONG;
  267                 size -= BITS_PER_LONG;
  268         }
  269         if (!size)
  270                 return result;
  271         tmp = ext2_swabp(p);
  272 found_first:
  273         tmp &= (~0UL >> (BITS_PER_LONG - size));
  274         if (tmp == 0UL)         /* Are any bits set? */
  275                 return result + size; /* Nope. */
  276 found_middle:
  277         return result + __ffs(tmp);
  278 
  279 found_middle_swap:
  280         return result + __ffs(ext2_swab(tmp));
  281 }
  282 EXPORT_SYMBOL(find_next_bit_le);
  283 #endif
  284 
  285 #endif /* __BIG_ENDIAN */

Cache object: 92b9e001d77a1dffbae611e98dedc93a

[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.

FreeBSD/Linux Kernel Cross Reference sys/lib/find_next_bit.c

FreeBSD/Linux Kernel Cross Reference
sys/lib/find_next_bit.c