qapi: Remove visit_start_alternate() parameter promote_int
[qemu/ar7.git] / util / bitops.c
blobb0c35dd5f1e348d66f7ec0079239dc377703753f
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)
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.
14 #include "qemu/osdep.h"
15 #include "qemu/bitops.h"
17 #define BITOP_WORD(nr) ((nr) / BITS_PER_LONG)
20 * Find the next set bit in a memory region.
22 unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
23 unsigned long offset)
25 const unsigned long *p = addr + BITOP_WORD(offset);
26 unsigned long result = offset & ~(BITS_PER_LONG-1);
27 unsigned long tmp;
29 if (offset >= size) {
30 return size;
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;
40 if (tmp) {
41 goto found_middle;
43 size -= BITS_PER_LONG;
44 result += BITS_PER_LONG;
46 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;
55 if (d1 | d2 | d3) {
56 break;
58 p += 4;
59 result += 4*BITS_PER_LONG;
60 size -= 4*BITS_PER_LONG;
62 while (size >= BITS_PER_LONG) {
63 if ((tmp = *(p++))) {
64 goto found_middle;
66 result += BITS_PER_LONG;
67 size -= BITS_PER_LONG;
69 if (!size) {
70 return result;
72 tmp = *p;
74 found_first:
75 tmp &= (~0UL >> (BITS_PER_LONG - size));
76 if (tmp == 0UL) { /* Are any bits set? */
77 return result + size; /* Nope. */
79 found_middle:
80 return result + ctzl(tmp);
84 * This implementation of find_{first,next}_zero_bit was stolen from
85 * Linus' asm-alpha/bitops.h.
87 unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
88 unsigned long offset)
90 const unsigned long *p = addr + BITOP_WORD(offset);
91 unsigned long result = offset & ~(BITS_PER_LONG-1);
92 unsigned long tmp;
94 if (offset >= size) {
95 return size;
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;
105 if (~tmp) {
106 goto found_middle;
108 size -= BITS_PER_LONG;
109 result += BITS_PER_LONG;
111 while (size & ~(BITS_PER_LONG-1)) {
112 if (~(tmp = *(p++))) {
113 goto found_middle;
115 result += BITS_PER_LONG;
116 size -= BITS_PER_LONG;
118 if (!size) {
119 return result;
121 tmp = *p;
123 found_first:
124 tmp |= ~0UL << size;
125 if (tmp == ~0UL) { /* Are any bits zero? */
126 return result + size; /* Nope. */
128 found_middle:
129 return result + ctzl(~tmp);
132 unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
134 unsigned long words;
135 unsigned long tmp;
137 /* Start at final word. */
138 words = size / BITS_PER_LONG;
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;
149 while (words) {
150 tmp = addr[--words];
151 if (tmp) {
152 found:
153 return words * BITS_PER_LONG + BITS_PER_LONG - 1 - clzl(tmp);
157 /* Not found */
158 return size;