Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | Download | RSS feed

  1. /* bit search implementation
  2.  *
  3.  * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
  4.  * Written by David Howells (dhowells@redhat.com)
  5.  *
  6.  * Copyright (C) 2008 IBM Corporation
  7.  * 'find_last_bit' is written by Rusty Russell <rusty@rustcorp.com.au>
  8.  * (Inspired by David Howell's find_next_bit implementation)
  9.  *
  10.  * Rewritten by Yury Norov <yury.norov@gmail.com> to decrease
  11.  * size and improve performance, 2015.
  12.  *
  13.  * This program is free software; you can redistribute it and/or
  14.  * modify it under the terms of the GNU General Public License
  15.  * as published by the Free Software Foundation; either version
  16.  * 2 of the License, or (at your option) any later version.
  17.  */
  18.  
  19. #include <linux/bitops.h>
  20. #include <linux/bitmap.h>
  21. #include <linux/export.h>
  22. #include <linux/kernel.h>
  23.  
  24. #if !defined(find_next_bit) || !defined(find_next_zero_bit)
  25.  
  26. /*
  27.  * This is a common helper function for find_next_bit and
  28.  * find_next_zero_bit.  The difference is the "invert" argument, which
  29.  * is XORed with each fetched word before searching it for one bits.
  30.  */
  31. static unsigned long _find_next_bit(const unsigned long *addr,
  32.                 unsigned long nbits, unsigned long start, unsigned long invert)
  33. {
  34.         unsigned long tmp;
  35.  
  36.         if (!nbits || start >= nbits)
  37.                 return nbits;
  38.  
  39.         tmp = addr[start / BITS_PER_LONG] ^ invert;
  40.  
  41.         /* Handle 1st word. */
  42.         tmp &= BITMAP_FIRST_WORD_MASK(start);
  43.         start = round_down(start, BITS_PER_LONG);
  44.  
  45.         while (!tmp) {
  46.                 start += BITS_PER_LONG;
  47.                 if (start >= nbits)
  48.                         return nbits;
  49.  
  50.                 tmp = addr[start / BITS_PER_LONG] ^ invert;
  51.         }
  52.  
  53.         return min(start + __ffs(tmp), nbits);
  54. }
  55. #endif
  56.  
  57. #ifndef find_next_bit
  58. /*
  59.  * Find the next set bit in a memory region.
  60.  */
  61. unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
  62.                             unsigned long offset)
  63. {
  64.         return _find_next_bit(addr, size, offset, 0UL);
  65. }
  66. EXPORT_SYMBOL(find_next_bit);
  67. #endif
  68.  
  69. #ifndef find_next_zero_bit
  70. unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
  71.                                  unsigned long offset)
  72. {
  73.         return _find_next_bit(addr, size, offset, ~0UL);
  74. }
  75. EXPORT_SYMBOL(find_next_zero_bit);
  76. #endif
  77.  
  78. #ifndef find_first_bit
  79. /*
  80.  * Find the first set bit in a memory region.
  81.  */
  82. unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
  83. {
  84.         unsigned long idx;
  85.  
  86.         for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
  87.                 if (addr[idx])
  88.                         return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size);
  89.         }
  90.  
  91.         return size;
  92. }
  93. EXPORT_SYMBOL(find_first_bit);
  94. #endif
  95.  
  96. #ifndef find_first_zero_bit
  97. /*
  98.  * Find the first cleared bit in a memory region.
  99.  */
  100. unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
  101. {
  102.         unsigned long idx;
  103.  
  104.         for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
  105.                 if (addr[idx] != ~0UL)
  106.                         return min(idx * BITS_PER_LONG + ffz(addr[idx]), size);
  107.         }
  108.  
  109.         return size;
  110. }
  111. EXPORT_SYMBOL(find_first_zero_bit);
  112. #endif
  113.  
  114. #ifndef find_last_bit
  115. unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
  116. {
  117.         if (size) {
  118.                 unsigned long val = BITMAP_LAST_WORD_MASK(size);
  119.                 unsigned long idx = (size-1) / BITS_PER_LONG;
  120.  
  121.                 do {
  122.                         val &= addr[idx];
  123.                         if (val)
  124.                                 return idx * BITS_PER_LONG + __fls(val);
  125.  
  126.                         val = ~0ul;
  127.                 } while (idx--);
  128.         }
  129.         return size;
  130. }
  131. EXPORT_SYMBOL(find_last_bit);
  132. #endif
  133.  
  134. #ifdef __BIG_ENDIAN
  135.  
  136. /* include/linux/byteorder does not support "unsigned long" type */
  137. static inline unsigned long ext2_swab(const unsigned long y)
  138. {
  139. #if BITS_PER_LONG == 64
  140.         return (unsigned long) __swab64((u64) y);
  141. #elif BITS_PER_LONG == 32
  142.         return (unsigned long) __swab32((u32) y);
  143. #else
  144. #error BITS_PER_LONG not defined
  145. #endif
  146. }
  147.  
  148. #if !defined(find_next_bit_le) || !defined(find_next_zero_bit_le)
  149. static unsigned long _find_next_bit_le(const unsigned long *addr,
  150.                 unsigned long nbits, unsigned long start, unsigned long invert)
  151. {
  152.         unsigned long tmp;
  153.  
  154.         if (!nbits || start >= nbits)
  155.                 return nbits;
  156.  
  157.         tmp = addr[start / BITS_PER_LONG] ^ invert;
  158.  
  159.         /* Handle 1st word. */
  160.         tmp &= ext2_swab(BITMAP_FIRST_WORD_MASK(start));
  161.         start = round_down(start, BITS_PER_LONG);
  162.  
  163.         while (!tmp) {
  164.                 start += BITS_PER_LONG;
  165.                 if (start >= nbits)
  166.                         return nbits;
  167.  
  168.                 tmp = addr[start / BITS_PER_LONG] ^ invert;
  169.         }
  170.  
  171.         return min(start + __ffs(ext2_swab(tmp)), nbits);
  172. }
  173. #endif
  174.  
  175. #ifndef find_next_zero_bit_le
  176. unsigned long find_next_zero_bit_le(const void *addr, unsigned
  177.                 long size, unsigned long offset)
  178. {
  179.         return _find_next_bit_le(addr, size, offset, ~0UL);
  180. }
  181. EXPORT_SYMBOL(find_next_zero_bit_le);
  182. #endif
  183.  
  184. #ifndef find_next_bit_le
  185. unsigned long find_next_bit_le(const void *addr, unsigned
  186.                 long size, unsigned long offset)
  187. {
  188.         return _find_next_bit_le(addr, size, offset, 0UL);
  189. }
  190. EXPORT_SYMBOL(find_next_bit_le);
  191. #endif
  192.  
  193. #endif /* __BIG_ENDIAN */
  194.