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/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