qemu

FORK: QEMU emulator
git clone https://git.neptards.moe/neptards/qemu.git
Log | Files | Refs | Submodules | LICENSE

bitops.c (3921B)

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