blob: b0c35dd5f1e348d66f7ec0079239dc377703753f [file] [log] [blame]
Corentin Charye0e53b22011-02-04 09:06:04 +01001/*
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
Peter Maydellaafd7582016-01-29 17:49:55 +000014#include "qemu/osdep.h"
Paolo Bonzini1de7afc2012-12-17 18:20:00 +010015#include "qemu/bitops.h"
Corentin Charye0e53b22011-02-04 09:06:04 +010016
17#define BITOP_WORD(nr) ((nr) / BITS_PER_LONG)
18
19/*
20 * Find the next set bit in a memory region.
21 */
22unsigned 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 }
Peter Lieven49f676a2013-03-26 10:58:34 +010046 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) {
Corentin Charye0e53b22011-02-04 09:06:04 +010063 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
74found_first:
75 tmp &= (~0UL >> (BITS_PER_LONG - size));
76 if (tmp == 0UL) { /* Are any bits set? */
77 return result + size; /* Nope. */
78 }
79found_middle:
Richard Henderson265ce4a2013-02-13 17:47:37 -080080 return result + ctzl(tmp);
Corentin Charye0e53b22011-02-04 09:06:04 +010081}
82
83/*
84 * This implementation of find_{first,next}_zero_bit was stolen from
85 * Linus' asm-alpha/bitops.h.
86 */
87unsigned 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
123found_first:
124 tmp |= ~0UL << size;
125 if (tmp == ~0UL) { /* Are any bits zero? */
126 return result + size; /* Nope. */
127 }
128found_middle:
Richard Henderson0f9d8bd2013-02-13 17:47:42 -0800129 return result + ctzl(~tmp);
Corentin Charye0e53b22011-02-04 09:06:04 +0100130}
131
132unsigned 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:
Richard Henderson49323982013-02-13 17:47:41 -0800153 return words * BITS_PER_LONG + BITS_PER_LONG - 1 - clzl(tmp);
Corentin Charye0e53b22011-02-04 09:06:04 +0100154 }
155 }
156
157 /* Not found */
158 return size;
159}