1baacf047SPaolo Bonzini /*
2baacf047SPaolo Bonzini * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
3baacf047SPaolo Bonzini * Written by David Howells (dhowells@redhat.com)
4baacf047SPaolo Bonzini * Copyright (C) 2008 IBM Corporation
5baacf047SPaolo Bonzini * Written by Rusty Russell <rusty@rustcorp.com.au>
6baacf047SPaolo Bonzini * (Inspired by David Howell's find_next_bit implementation)
7baacf047SPaolo Bonzini *
8baacf047SPaolo Bonzini * This program is free software; you can redistribute it and/or
9baacf047SPaolo Bonzini * modify it under the terms of the GNU General Public License
10baacf047SPaolo Bonzini * as published by the Free Software Foundation; either version
11baacf047SPaolo Bonzini * 2 of the License, or (at your option) any later version.
12baacf047SPaolo Bonzini */
13baacf047SPaolo Bonzini
14aafd7584SPeter Maydell #include "qemu/osdep.h"
15baacf047SPaolo Bonzini #include "qemu/bitops.h"
16baacf047SPaolo Bonzini
17baacf047SPaolo Bonzini /*
18baacf047SPaolo Bonzini * Find the next set bit in a memory region.
19baacf047SPaolo Bonzini */
find_next_bit(const unsigned long * addr,unsigned long size,unsigned long offset)20baacf047SPaolo Bonzini unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
21baacf047SPaolo Bonzini unsigned long offset)
22baacf047SPaolo Bonzini {
23*ab089e05SPeter Xu const unsigned long *p = addr + BIT_WORD(offset);
24baacf047SPaolo Bonzini unsigned long result = offset & ~(BITS_PER_LONG-1);
25baacf047SPaolo Bonzini unsigned long tmp;
26baacf047SPaolo Bonzini
27baacf047SPaolo Bonzini if (offset >= size) {
28baacf047SPaolo Bonzini return size;
29baacf047SPaolo Bonzini }
30baacf047SPaolo Bonzini size -= result;
31baacf047SPaolo Bonzini offset %= BITS_PER_LONG;
32baacf047SPaolo Bonzini if (offset) {
33baacf047SPaolo Bonzini tmp = *(p++);
34baacf047SPaolo Bonzini tmp &= (~0UL << offset);
35baacf047SPaolo Bonzini if (size < BITS_PER_LONG) {
36baacf047SPaolo Bonzini goto found_first;
37baacf047SPaolo Bonzini }
38baacf047SPaolo Bonzini if (tmp) {
39baacf047SPaolo Bonzini goto found_middle;
40baacf047SPaolo Bonzini }
41baacf047SPaolo Bonzini size -= BITS_PER_LONG;
42baacf047SPaolo Bonzini result += BITS_PER_LONG;
43baacf047SPaolo Bonzini }
4449f676a0SPeter Lieven while (size >= 4*BITS_PER_LONG) {
4549f676a0SPeter Lieven unsigned long d1, d2, d3;
4649f676a0SPeter Lieven tmp = *p;
4749f676a0SPeter Lieven d1 = *(p+1);
4849f676a0SPeter Lieven d2 = *(p+2);
4949f676a0SPeter Lieven d3 = *(p+3);
5049f676a0SPeter Lieven if (tmp) {
5149f676a0SPeter Lieven goto found_middle;
5249f676a0SPeter Lieven }
5349f676a0SPeter Lieven if (d1 | d2 | d3) {
5449f676a0SPeter Lieven break;
5549f676a0SPeter Lieven }
5649f676a0SPeter Lieven p += 4;
5749f676a0SPeter Lieven result += 4*BITS_PER_LONG;
5849f676a0SPeter Lieven size -= 4*BITS_PER_LONG;
5949f676a0SPeter Lieven }
6049f676a0SPeter Lieven while (size >= BITS_PER_LONG) {
61baacf047SPaolo Bonzini if ((tmp = *(p++))) {
62baacf047SPaolo Bonzini goto found_middle;
63baacf047SPaolo Bonzini }
64baacf047SPaolo Bonzini result += BITS_PER_LONG;
65baacf047SPaolo Bonzini size -= BITS_PER_LONG;
66baacf047SPaolo Bonzini }
67baacf047SPaolo Bonzini if (!size) {
68baacf047SPaolo Bonzini return result;
69baacf047SPaolo Bonzini }
70baacf047SPaolo Bonzini tmp = *p;
71baacf047SPaolo Bonzini
72baacf047SPaolo Bonzini found_first:
73baacf047SPaolo Bonzini tmp &= (~0UL >> (BITS_PER_LONG - size));
74baacf047SPaolo Bonzini if (tmp == 0UL) { /* Are any bits set? */
75baacf047SPaolo Bonzini return result + size; /* Nope. */
76baacf047SPaolo Bonzini }
77baacf047SPaolo Bonzini found_middle:
78265ce4a5SRichard Henderson return result + ctzl(tmp);
79baacf047SPaolo Bonzini }
80baacf047SPaolo Bonzini
81baacf047SPaolo Bonzini /*
82baacf047SPaolo Bonzini * This implementation of find_{first,next}_zero_bit was stolen from
83baacf047SPaolo Bonzini * Linus' asm-alpha/bitops.h.
84baacf047SPaolo Bonzini */
find_next_zero_bit(const unsigned long * addr,unsigned long size,unsigned long offset)85baacf047SPaolo Bonzini unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
86baacf047SPaolo Bonzini unsigned long offset)
87baacf047SPaolo Bonzini {
88*ab089e05SPeter Xu const unsigned long *p = addr + BIT_WORD(offset);
89baacf047SPaolo Bonzini unsigned long result = offset & ~(BITS_PER_LONG-1);
90baacf047SPaolo Bonzini unsigned long tmp;
91baacf047SPaolo Bonzini
92baacf047SPaolo Bonzini if (offset >= size) {
93baacf047SPaolo Bonzini return size;
94baacf047SPaolo Bonzini }
95baacf047SPaolo Bonzini size -= result;
96baacf047SPaolo Bonzini offset %= BITS_PER_LONG;
97baacf047SPaolo Bonzini if (offset) {
98baacf047SPaolo Bonzini tmp = *(p++);
99baacf047SPaolo Bonzini tmp |= ~0UL >> (BITS_PER_LONG - offset);
100baacf047SPaolo Bonzini if (size < BITS_PER_LONG) {
101baacf047SPaolo Bonzini goto found_first;
102baacf047SPaolo Bonzini }
103baacf047SPaolo Bonzini if (~tmp) {
104baacf047SPaolo Bonzini goto found_middle;
105baacf047SPaolo Bonzini }
106baacf047SPaolo Bonzini size -= BITS_PER_LONG;
107baacf047SPaolo Bonzini result += BITS_PER_LONG;
108baacf047SPaolo Bonzini }
109baacf047SPaolo Bonzini while (size & ~(BITS_PER_LONG-1)) {
110baacf047SPaolo Bonzini if (~(tmp = *(p++))) {
111baacf047SPaolo Bonzini goto found_middle;
112baacf047SPaolo Bonzini }
113baacf047SPaolo Bonzini result += BITS_PER_LONG;
114baacf047SPaolo Bonzini size -= BITS_PER_LONG;
115baacf047SPaolo Bonzini }
116baacf047SPaolo Bonzini if (!size) {
117baacf047SPaolo Bonzini return result;
118baacf047SPaolo Bonzini }
119baacf047SPaolo Bonzini tmp = *p;
120baacf047SPaolo Bonzini
121baacf047SPaolo Bonzini found_first:
122baacf047SPaolo Bonzini tmp |= ~0UL << size;
123baacf047SPaolo Bonzini if (tmp == ~0UL) { /* Are any bits zero? */
124baacf047SPaolo Bonzini return result + size; /* Nope. */
125baacf047SPaolo Bonzini }
126baacf047SPaolo Bonzini found_middle:
1270f9d8bd3SRichard Henderson return result + ctzl(~tmp);
128baacf047SPaolo Bonzini }
129baacf047SPaolo Bonzini
find_last_bit(const unsigned long * addr,unsigned long size)130baacf047SPaolo Bonzini unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
131baacf047SPaolo Bonzini {
132baacf047SPaolo Bonzini unsigned long words;
133baacf047SPaolo Bonzini unsigned long tmp;
134baacf047SPaolo Bonzini
135baacf047SPaolo Bonzini /* Start at final word. */
136baacf047SPaolo Bonzini words = size / BITS_PER_LONG;
137baacf047SPaolo Bonzini
138baacf047SPaolo Bonzini /* Partial final word? */
139baacf047SPaolo Bonzini if (size & (BITS_PER_LONG-1)) {
140baacf047SPaolo Bonzini tmp = (addr[words] & (~0UL >> (BITS_PER_LONG
141baacf047SPaolo Bonzini - (size & (BITS_PER_LONG-1)))));
142baacf047SPaolo Bonzini if (tmp) {
143baacf047SPaolo Bonzini goto found;
144baacf047SPaolo Bonzini }
145baacf047SPaolo Bonzini }
146baacf047SPaolo Bonzini
147baacf047SPaolo Bonzini while (words) {
148baacf047SPaolo Bonzini tmp = addr[--words];
149baacf047SPaolo Bonzini if (tmp) {
150baacf047SPaolo Bonzini found:
1514932398fSRichard Henderson return words * BITS_PER_LONG + BITS_PER_LONG - 1 - clzl(tmp);
152baacf047SPaolo Bonzini }
153baacf047SPaolo Bonzini }
154baacf047SPaolo Bonzini
155baacf047SPaolo Bonzini /* Not found */
156baacf047SPaolo Bonzini return size;
157baacf047SPaolo Bonzini }
158