Home | History | Annotate | Download | only in util 
      1 /*
      2  * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
      3  * Written by David Howells (dhowells (at) redhat.com)
      4  * Copyright (C) 2008 IBM Corporation
      5  * Written by Rusty Russell <rusty (at) rustcorp.com.au>
      6  * (Inspired by David Howell's find_next_bit implementation)
      7  *
      8  * This program is free software; you can redistribute it and/or
      9  * modify it under the terms of the GNU General Public License
     10  * as published by the Free Software Foundation; either version
     11  * 2 of the License, or (at your option) any later version.
     12  */
     13 
     14 #include "qemu/bitops.h"
     15 
     16 #define BITOP_WORD(nr)		((nr) / BITS_PER_LONG)
     17 
     18 /*
     19  * Find the next set bit in a memory region.
     20  */
     21 unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
     22 			    unsigned long offset)
     23 {
     24     const unsigned long *p = addr + BITOP_WORD(offset);
     25     unsigned long result = offset & ~(BITS_PER_LONG-1);
     26     unsigned long tmp;
     27 
     28     if (offset >= size) {
     29         return size;
     30     }
     31     size -= result;
     32     offset %= BITS_PER_LONG;
     33     if (offset) {
     34         tmp = *(p++);
     35         tmp &= (~0UL << offset);
     36         if (size < BITS_PER_LONG) {
     37             goto found_first;
     38         }
     39         if (tmp) {
     40             goto found_middle;
     41         }
     42         size -= BITS_PER_LONG;
     43         result += BITS_PER_LONG;
     44     }
     45     while (size >= 4*BITS_PER_LONG) {
     46         unsigned long d1, d2, d3;
     47         tmp = *p;
     48         d1 = *(p+1);
     49         d2 = *(p+2);
     50         d3 = *(p+3);
     51         if (tmp) {
     52             goto found_middle;
     53         }
     54         if (d1 | d2 | d3) {
     55             break;
     56         }
     57         p += 4;
     58         result += 4*BITS_PER_LONG;
     59         size -= 4*BITS_PER_LONG;
     60     }
     61     while (size >= BITS_PER_LONG) {
     62         if ((tmp = *(p++))) {
     63             goto found_middle;
     64         }
     65         result += BITS_PER_LONG;
     66         size -= BITS_PER_LONG;
     67     }
     68     if (!size) {
     69         return result;
     70     }
     71     tmp = *p;
     72 
     73 found_first:
     74     tmp &= (~0UL >> (BITS_PER_LONG - size));
     75     if (tmp == 0UL) {		/* Are any bits set? */
     76         return result + size;	/* Nope. */
     77     }
     78 found_middle:
     79     return result + ctzl(tmp);
     80 }
     81 
     82 /*
     83  * This implementation of find_{first,next}_zero_bit was stolen from
     84  * Linus' asm-alpha/bitops.h.
     85  */
     86 unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
     87 				 unsigned long offset)
     88 {
     89     const unsigned long *p = addr + BITOP_WORD(offset);
     90     unsigned long result = offset & ~(BITS_PER_LONG-1);
     91     unsigned long tmp;
     92 
     93     if (offset >= size) {
     94         return size;
     95     }
     96     size -= result;
     97     offset %= BITS_PER_LONG;
     98     if (offset) {
     99         tmp = *(p++);
    100         tmp |= ~0UL >> (BITS_PER_LONG - offset);
    101         if (size < BITS_PER_LONG) {
    102             goto found_first;
    103         }
    104         if (~tmp) {
    105             goto found_middle;
    106         }
    107         size -= BITS_PER_LONG;
    108         result += BITS_PER_LONG;
    109     }
    110     while (size & ~(BITS_PER_LONG-1)) {
    111         if (~(tmp = *(p++))) {
    112             goto found_middle;
    113         }
    114         result += BITS_PER_LONG;
    115         size -= BITS_PER_LONG;
    116     }
    117     if (!size) {
    118         return result;
    119     }
    120     tmp = *p;
    121 
    122 found_first:
    123     tmp |= ~0UL << size;
    124     if (tmp == ~0UL) {	/* Are any bits zero? */
    125         return result + size;	/* Nope. */
    126     }
    127 found_middle:
    128     return result + ctzl(~tmp);
    129 }
    130 
    131 unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
    132 {
    133     unsigned long words;
    134     unsigned long tmp;
    135 
    136     /* Start at final word. */
    137     words = size / BITS_PER_LONG;
    138 
    139     /* Partial final word? */
    140     if (size & (BITS_PER_LONG-1)) {
    141         tmp = (addr[words] & (~0UL >> (BITS_PER_LONG
    142                                        - (size & (BITS_PER_LONG-1)))));
    143         if (tmp) {
    144             goto found;
    145         }
    146     }
    147 
    148     while (words) {
    149         tmp = addr[--words];
    150         if (tmp) {
    151         found:
    152             return words * BITS_PER_LONG + BITS_PER_LONG - 1 - clzl(tmp);
    153         }
    154     }
    155 
    156     /* Not found */
    157     return size;
    158 }
    159