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