Branch data     Line data    Source code

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