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 & ~(BITS_PER_LONG-1)) { 46 if ((tmp = *(p++))) { 47 goto found_middle; 48 } 49 result += BITS_PER_LONG; 50 size -= BITS_PER_LONG; 51 } 52 if (!size) { 53 return result; 54 } 55 tmp = *p; 56 57 found_first: 58 tmp &= (~0UL >> (BITS_PER_LONG - size)); 59 if (tmp == 0UL) { /* Are any bits set? */ 60 return result + size; /* Nope. */ 61 } 62 found_middle: 63 return result + ctzl(tmp); 64 } 65 66 /* 67 * This implementation of find_{first,next}_zero_bit was stolen from 68 * Linus' asm-alpha/bitops.h. 69 */ 70 unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size, 71 unsigned long offset) 72 { 73 const unsigned long *p = addr + BITOP_WORD(offset); 74 unsigned long result = offset & ~(BITS_PER_LONG-1); 75 unsigned long tmp; 76 77 if (offset >= size) { 78 return size; 79 } 80 size -= result; 81 offset %= BITS_PER_LONG; 82 if (offset) { 83 tmp = *(p++); 84 tmp |= ~0UL >> (BITS_PER_LONG - offset); 85 if (size < BITS_PER_LONG) { 86 goto found_first; 87 } 88 if (~tmp) { 89 goto found_middle; 90 } 91 size -= BITS_PER_LONG; 92 result += BITS_PER_LONG; 93 } 94 while (size & ~(BITS_PER_LONG-1)) { 95 if (~(tmp = *(p++))) { 96 goto found_middle; 97 } 98 result += BITS_PER_LONG; 99 size -= BITS_PER_LONG; 100 } 101 if (!size) { 102 return result; 103 } 104 tmp = *p; 105 106 found_first: 107 tmp |= ~0UL << size; 108 if (tmp == ~0UL) { /* Are any bits zero? */ 109 return result + size; /* Nope. */ 110 } 111 found_middle: 112 return result + ctzl(~tmp); 113 } 114 115 unsigned long find_last_bit(const unsigned long *addr, unsigned long size) 116 { 117 unsigned long words; 118 unsigned long tmp; 119 120 /* Start at final word. */ 121 words = size / BITS_PER_LONG; 122 123 /* Partial final word? */ 124 if (size & (BITS_PER_LONG-1)) { 125 tmp = (addr[words] & (~0UL >> (BITS_PER_LONG 126 - (size & (BITS_PER_LONG-1))))); 127 if (tmp) { 128 goto found; 129 } 130 } 131 132 while (words) { 133 tmp = addr[--words]; 134 if (tmp) { 135 found: 136 return words * BITS_PER_LONG + BITS_PER_LONG - 1 - clzl(tmp); 137 } 138 } 139 140 /* Not found */ 141 return size; 142 } 143