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