mips: Ensure PC update with MTC0 single-stepping
[qemu.git] / util / bitops.c
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/bitops.h"
15
16 #define BITOP_WORD(nr) ((nr) / BITS_PER_LONG)
17
18 /*
19 * Find the next set bit in a memory region.
20 */
21 unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
22 unsigned long offset)
23 {
24 const unsigned long *p = addr + BITOP_WORD(offset);
25 unsigned long result = offset & ~(BITS_PER_LONG-1);
26 unsigned long tmp;
27
28 if (offset >= size) {
29 return size;
30 }
31 size -= result;
32 offset %= BITS_PER_LONG;
33 if (offset) {
34 tmp = *(p++);
35 tmp &= (~0UL << offset);
36 if (size < BITS_PER_LONG) {
37 goto found_first;
38 }
39 if (tmp) {
40 goto found_middle;
41 }
42 size -= BITS_PER_LONG;
43 result += BITS_PER_LONG;
44 }
45 while (size >= 4*BITS_PER_LONG) {
46 unsigned long d1, d2, d3;
47 tmp = *p;
48 d1 = *(p+1);
49 d2 = *(p+2);
50 d3 = *(p+3);
51 if (tmp) {
52 goto found_middle;
53 }
54 if (d1 | d2 | d3) {
55 break;
56 }
57 p += 4;
58 result += 4*BITS_PER_LONG;
59 size -= 4*BITS_PER_LONG;
60 }
61 while (size >= BITS_PER_LONG) {
62 if ((tmp = *(p++))) {
63 goto found_middle;
64 }
65 result += BITS_PER_LONG;
66 size -= BITS_PER_LONG;
67 }
68 if (!size) {
69 return result;
70 }
71 tmp = *p;
72
73 found_first:
74 tmp &= (~0UL >> (BITS_PER_LONG - size));
75 if (tmp == 0UL) { /* Are any bits set? */
76 return result + size; /* Nope. */
77 }
78 found_middle:
79 return result + ctzl(tmp);
80 }
81
82 /*
83 * This implementation of find_{first,next}_zero_bit was stolen from
84 * Linus' asm-alpha/bitops.h.
85 */
86 unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
87 unsigned long offset)
88 {
89 const unsigned long *p = addr + BITOP_WORD(offset);
90 unsigned long result = offset & ~(BITS_PER_LONG-1);
91 unsigned long tmp;
92
93 if (offset >= size) {
94 return size;
95 }
96 size -= result;
97 offset %= BITS_PER_LONG;
98 if (offset) {
99 tmp = *(p++);
100 tmp |= ~0UL >> (BITS_PER_LONG - offset);
101 if (size < BITS_PER_LONG) {
102 goto found_first;
103 }
104 if (~tmp) {
105 goto found_middle;
106 }
107 size -= BITS_PER_LONG;
108 result += BITS_PER_LONG;
109 }
110 while (size & ~(BITS_PER_LONG-1)) {
111 if (~(tmp = *(p++))) {
112 goto found_middle;
113 }
114 result += BITS_PER_LONG;
115 size -= BITS_PER_LONG;
116 }
117 if (!size) {
118 return result;
119 }
120 tmp = *p;
121
122 found_first:
123 tmp |= ~0UL << size;
124 if (tmp == ~0UL) { /* Are any bits zero? */
125 return result + size; /* Nope. */
126 }
127 found_middle:
128 return result + ctzl(~tmp);
129 }
130
131 unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
132 {
133 unsigned long words;
134 unsigned long tmp;
135
136 /* Start at final word. */
137 words = size / BITS_PER_LONG;
138
139 /* Partial final word? */
140 if (size & (BITS_PER_LONG-1)) {
141 tmp = (addr[words] & (~0UL >> (BITS_PER_LONG
142 - (size & (BITS_PER_LONG-1)))));
143 if (tmp) {
144 goto found;
145 }
146 }
147
148 while (words) {
149 tmp = addr[--words];
150 if (tmp) {
151 found:
152 return words * BITS_PER_LONG + BITS_PER_LONG - 1 - clzl(tmp);
153 }
154 }
155
156 /* Not found */
157 return size;
158 }