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 */
20unsigned 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
72found_first:
73 tmp &= (~0UL >> (BITS_PER_LONG - size));
74 if (tmp == 0UL) { /* Are any bits set? */
75 return result + size; /* Nope. */
76 }
77found_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 */
85unsigned 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
121found_first:
122 tmp |= ~0UL << size;
123 if (tmp == ~0UL) { /* Are any bits zero? */
124 return result + size; /* Nope. */
125 }
126found_middle:
127 return result + ctzl(~tmp);
128}
129
130unsigned 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