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_bit_le) || !defined(find_next_zero_bit_le) ||        \
      22                 :            :         !defined(find_next_and_bit)
      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                 :   10193736 : static unsigned long _find_next_bit(const unsigned long *addr1,
      31                 :            :                 const unsigned long *addr2, unsigned long nbits,
      32                 :            :                 unsigned long start, unsigned long invert, unsigned long le)
      33                 :            : {
      34                 :   10193736 :         unsigned long tmp, mask;
      35                 :            : 
      36         [ +  + ]:   10193736 :         if (unlikely(start >= nbits))
      37                 :            :                 return nbits;
      38                 :            : 
      39                 :   10035493 :         tmp = addr1[start / BITS_PER_LONG];
      40         [ +  + ]:   10035493 :         if (addr2)
      41                 :       8810 :                 tmp &= addr2[start / BITS_PER_LONG];
      42                 :   10035493 :         tmp ^= invert;
      43                 :            : 
      44                 :            :         /* Handle 1st word. */
      45                 :   10035493 :         mask = BITMAP_FIRST_WORD_MASK(start);
      46         [ -  + ]:   10035493 :         if (le)
      47                 :          0 :                 mask = swab(mask);
      48                 :            : 
      49                 :   10035493 :         tmp &= mask;
      50                 :            : 
      51                 :   10035493 :         start = round_down(start, BITS_PER_LONG);
      52                 :            : 
      53         [ +  + ]:   13320472 :         while (!tmp) {
      54                 :    6298925 :                 start += BITS_PER_LONG;
      55         [ +  + ]:    6298925 :                 if (start >= nbits)
      56                 :            :                         return nbits;
      57                 :            : 
      58                 :    3284979 :                 tmp = addr1[start / BITS_PER_LONG];
      59         [ -  + ]:    3284979 :                 if (addr2)
      60                 :          0 :                         tmp &= addr2[start / BITS_PER_LONG];
      61                 :    3284979 :                 tmp ^= invert;
      62                 :            :         }
      63                 :            : 
      64         [ -  + ]:    7021547 :         if (le)
      65                 :          0 :                 tmp = swab(tmp);
      66                 :            : 
      67                 :    7021547 :         return min(start + __ffs(tmp), nbits);
      68                 :            : }
      69                 :            : #endif
      70                 :            : 
      71                 :            : #ifndef find_next_bit
      72                 :            : /*
      73                 :            :  * Find the next set bit in a memory region.
      74                 :            :  */
      75                 :    5688308 : unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
      76                 :            :                             unsigned long offset)
      77                 :            : {
      78                 :    5688308 :         return _find_next_bit(addr, NULL, size, offset, 0UL, 0);
      79                 :            : }
      80                 :            : EXPORT_SYMBOL(find_next_bit);
      81                 :            : #endif
      82                 :            : 
      83                 :            : #ifndef find_next_zero_bit
      84                 :    4496618 : unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
      85                 :            :                                  unsigned long offset)
      86                 :            : {
      87                 :    4496618 :         return _find_next_bit(addr, NULL, size, offset, ~0UL, 0);
      88                 :            : }
      89                 :            : EXPORT_SYMBOL(find_next_zero_bit);
      90                 :            : #endif
      91                 :            : 
      92                 :            : #if !defined(find_next_and_bit)
      93                 :       8810 : unsigned long find_next_and_bit(const unsigned long *addr1,
      94                 :            :                 const unsigned long *addr2, unsigned long size,
      95                 :            :                 unsigned long offset)
      96                 :            : {
      97                 :       8810 :         return _find_next_bit(addr1, addr2, size, offset, 0UL, 0);
      98                 :            : }
      99                 :            : EXPORT_SYMBOL(find_next_and_bit);
     100                 :            : #endif
     101                 :            : 
     102                 :            : #ifndef find_first_bit
     103                 :            : /*
     104                 :            :  * Find the first set bit in a memory region.
     105                 :            :  */
     106                 :     960447 : unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
     107                 :            : {
     108                 :     960447 :         unsigned long idx;
     109                 :            : 
     110         [ +  + ]:    1267488 :         for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
     111         [ +  + ]:     960636 :                 if (addr[idx])
     112                 :     653595 :                         return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size);
     113                 :            :         }
     114                 :            : 
     115                 :            :         return size;
     116                 :            : }
     117                 :            : EXPORT_SYMBOL(find_first_bit);
     118                 :            : #endif
     119                 :            : 
     120                 :            : #ifndef find_first_zero_bit
     121                 :            : /*
     122                 :            :  * Find the first cleared bit in a memory region.
     123                 :            :  */
     124                 :       9156 : unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
     125                 :            : {
     126                 :       9156 :         unsigned long idx;
     127                 :            : 
     128         [ +  - ]:      28560 :         for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
     129         [ +  + ]:      28560 :                 if (addr[idx] != ~0UL)
     130                 :       9156 :                         return min(idx * BITS_PER_LONG + ffz(addr[idx]), size);
     131                 :            :         }
     132                 :            : 
     133                 :            :         return size;
     134                 :            : }
     135                 :            : EXPORT_SYMBOL(find_first_zero_bit);
     136                 :            : #endif
     137                 :            : 
     138                 :            : #ifndef find_last_bit
     139                 :       1996 : unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
     140                 :            : {
     141         [ +  - ]:       1996 :         if (size) {
     142                 :       1996 :                 unsigned long val = BITMAP_LAST_WORD_MASK(size);
     143                 :       1996 :                 unsigned long idx = (size-1) / BITS_PER_LONG;
     144                 :            : 
     145                 :       2007 :                 do {
     146                 :       2007 :                         val &= addr[idx];
     147         [ +  + ]:       2007 :                         if (val)
     148                 :       1996 :                                 return idx * BITS_PER_LONG + __fls(val);
     149                 :            : 
     150                 :         11 :                         val = ~0ul;
     151         [ +  - ]:         11 :                 } while (idx--);
     152                 :            :         }
     153                 :            :         return size;
     154                 :            : }
     155                 :            : EXPORT_SYMBOL(find_last_bit);
     156                 :            : #endif
     157                 :            : 
     158                 :            : #ifdef __BIG_ENDIAN
     159                 :            : 
     160                 :            : #ifndef find_next_zero_bit_le
     161                 :            : unsigned long find_next_zero_bit_le(const void *addr, unsigned
     162                 :            :                 long size, unsigned long offset)
     163                 :            : {
     164                 :            :         return _find_next_bit(addr, NULL, size, offset, ~0UL, 1);
     165                 :            : }
     166                 :            : EXPORT_SYMBOL(find_next_zero_bit_le);
     167                 :            : #endif
     168                 :            : 
     169                 :            : #ifndef find_next_bit_le
     170                 :            : unsigned long find_next_bit_le(const void *addr, unsigned
     171                 :            :                 long size, unsigned long offset)
     172                 :            : {
     173                 :            :         return _find_next_bit(addr, NULL, size, offset, 0UL, 1);
     174                 :            : }
     175                 :            : EXPORT_SYMBOL(find_next_bit_le);
     176                 :            : #endif
     177                 :            : 
     178                 :            : #endif /* __BIG_ENDIAN */
     179                 :            : 
     180                 :          0 : unsigned long find_next_clump8(unsigned long *clump, const unsigned long *addr,
     181                 :            :                                unsigned long size, unsigned long offset)
     182                 :            : {
     183                 :          0 :         offset = find_next_bit(addr, size, offset);
     184         [ #  # ]:          0 :         if (offset == size)
     185                 :            :                 return size;
     186                 :            : 
     187                 :          0 :         offset = round_down(offset, 8);
     188                 :          0 :         *clump = bitmap_get_value8(addr, offset);
     189                 :            : 
     190                 :          0 :         return offset;
     191                 :            : }
     192                 :            : EXPORT_SYMBOL(find_next_clump8);