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 } 158