~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/tools/lib/find_bit.c

Version: ~ [ linux-6.2-rc3 ] ~ [ linux-6.1.5 ] ~ [ linux-6.0.19 ] ~ [ linux-5.19.17 ] ~ [ linux-5.18.19 ] ~ [ linux-5.17.15 ] ~ [ linux-5.16.20 ] ~ [ linux-5.15.87 ] ~ [ linux-5.14.21 ] ~ [ linux-5.13.19 ] ~ [ linux-5.12.19 ] ~ [ linux-5.11.22 ] ~ [ linux-5.10.162 ] ~ [ linux-5.9.16 ] ~ [ linux-5.8.18 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.228 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.269 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.302 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.337 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.302 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.9 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  1 // SPDX-License-Identifier: GPL-2.0-or-later
  2 /* bit search implementation
  3  *
  4  * Copied from lib/find_bit.c to tools/lib/find_bit.c
  5  *
  6  * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
  7  * Written by David Howells (dhowells@redhat.com)
  8  *
  9  * Copyright (C) 2008 IBM Corporation
 10  * 'find_last_bit' is written by Rusty Russell <rusty@rustcorp.com.au>
 11  * (Inspired by David Howell's find_next_bit implementation)
 12  *
 13  * Rewritten by Yury Norov <yury.norov@gmail.com> to decrease
 14  * size and improve performance, 2015.
 15  */
 16 
 17 #include <linux/bitops.h>
 18 #include <linux/bitmap.h>
 19 #include <linux/kernel.h>
 20 
 21 #if !defined(find_next_bit) || !defined(find_next_zero_bit) || \
 22                 !defined(find_next_and_bit)
 23 
 24 /*
 25  * This is a common helper function for find_next_bit, find_next_zero_bit, and
 26  * find_next_and_bit. The differences are:
 27  *  - The "invert" argument, which is XORed with each fetched word before
 28  *    searching it for one bits.
 29  *  - The optional "addr2", which is anded with "addr1" if present.
 30  */
 31 unsigned long _find_next_bit(const unsigned long *addr1,
 32                 const unsigned long *addr2, unsigned long nbits,
 33                 unsigned long start, unsigned long invert, unsigned long le)
 34 {
 35         unsigned long tmp, mask;
 36         (void) le;
 37 
 38         if (unlikely(start >= nbits))
 39                 return nbits;
 40 
 41         tmp = addr1[start / BITS_PER_LONG];
 42         if (addr2)
 43                 tmp &= addr2[start / BITS_PER_LONG];
 44         tmp ^= invert;
 45 
 46         /* Handle 1st word. */
 47         mask = BITMAP_FIRST_WORD_MASK(start);
 48 
 49         /*
 50          * Due to the lack of swab() in tools, and the fact that it doesn't
 51          * need little-endian support, just comment it out
 52          */
 53 #if (0)
 54         if (le)
 55                 mask = swab(mask);
 56 #endif
 57 
 58         tmp &= mask;
 59 
 60         start = round_down(start, BITS_PER_LONG);
 61 
 62         while (!tmp) {
 63                 start += BITS_PER_LONG;
 64                 if (start >= nbits)
 65                         return nbits;
 66 
 67                 tmp = addr1[start / BITS_PER_LONG];
 68                 if (addr2)
 69                         tmp &= addr2[start / BITS_PER_LONG];
 70                 tmp ^= invert;
 71         }
 72 
 73 #if (0)
 74         if (le)
 75                 tmp = swab(tmp);
 76 #endif
 77 
 78         return min(start + __ffs(tmp), nbits);
 79 }
 80 #endif
 81 
 82 #ifndef find_first_bit
 83 /*
 84  * Find the first set bit in a memory region.
 85  */
 86 unsigned long _find_first_bit(const unsigned long *addr, unsigned long size)
 87 {
 88         unsigned long idx;
 89 
 90         for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
 91                 if (addr[idx])
 92                         return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size);
 93         }
 94 
 95         return size;
 96 }
 97 #endif
 98 
 99 #ifndef find_first_and_bit
100 /*
101  * Find the first set bit in two memory regions.
102  */
103 unsigned long _find_first_and_bit(const unsigned long *addr1,
104                                   const unsigned long *addr2,
105                                   unsigned long size)
106 {
107         unsigned long idx, val;
108 
109         for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
110                 val = addr1[idx] & addr2[idx];
111                 if (val)
112                         return min(idx * BITS_PER_LONG + __ffs(val), size);
113         }
114 
115         return size;
116 }
117 #endif
118 
119 #ifndef find_first_zero_bit
120 /*
121  * Find the first cleared bit in a memory region.
122  */
123 unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size)
124 {
125         unsigned long idx;
126 
127         for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
128                 if (addr[idx] != ~0UL)
129                         return min(idx * BITS_PER_LONG + ffz(addr[idx]), size);
130         }
131 
132         return size;
133 }
134 #endif
135 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp