Google Git
Sign in
qemu / qemu / d567e62f98d5789ff4d273b924a0474931c71e8b / . / bitops.c
blob: d9de71f7e8814ea809a5e8e2cd238e359a6b8a7f [file] [log] [blame]
Corentin Charye0e53b22011-02-04 09:06:04 +0100[diff] [blame]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 "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 */
21unsigned 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 & ~(BITS_PER_LONG-1)) {
46 if ((tmp = *(p++))) {
47 goto found_middle;
48 }
49 result += BITS_PER_LONG;
50 size -= BITS_PER_LONG;
51 }
52 if (!size) {
53 return result;
54 }
55 tmp = *p;
56
57found_first:
58 tmp &= (~0UL >> (BITS_PER_LONG - size));
59 if (tmp == 0UL) { /* Are any bits set? */
60 return result + size; /* Nope. */
61 }
62found_middle:
63 return result + bitops_ffsl(tmp);
64}
65
66/*
67 * This implementation of find_{first,next}_zero_bit was stolen from
68 * Linus' asm-alpha/bitops.h.
69 */
70unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
71 unsigned long offset)
72{
73 const unsigned long *p = addr + BITOP_WORD(offset);
74 unsigned long result = offset & ~(BITS_PER_LONG-1);
75 unsigned long tmp;
76
77 if (offset >= size) {
78 return size;
79 }
80 size -= result;
81 offset %= BITS_PER_LONG;
82 if (offset) {
83 tmp = *(p++);
84 tmp |= ~0UL >> (BITS_PER_LONG - offset);
85 if (size < BITS_PER_LONG) {
86 goto found_first;
87 }
88 if (~tmp) {
89 goto found_middle;
90 }
91 size -= BITS_PER_LONG;
92 result += BITS_PER_LONG;
93 }
94 while (size & ~(BITS_PER_LONG-1)) {
95 if (~(tmp = *(p++))) {
96 goto found_middle;
97 }
98 result += BITS_PER_LONG;
99 size -= BITS_PER_LONG;
100 }
101 if (!size) {
102 return result;
103 }
104 tmp = *p;
105
106found_first:
107 tmp |= ~0UL << size;
108 if (tmp == ~0UL) { /* Are any bits zero? */
109 return result + size; /* Nope. */
110 }
111found_middle:
112 return result + ffz(tmp);
113}
114
115unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
116{
117 unsigned long words;
118 unsigned long tmp;
119
120 /* Start at final word. */
121 words = size / BITS_PER_LONG;
122
123 /* Partial final word? */
124 if (size & (BITS_PER_LONG-1)) {
125 tmp = (addr[words] & (~0UL >> (BITS_PER_LONG
126 - (size & (BITS_PER_LONG-1)))));
127 if (tmp) {
128 goto found;
129 }
130 }
131
132 while (words) {
133 tmp = addr[--words];
134 if (tmp) {
135 found:
136 return words * BITS_PER_LONG + bitops_flsl(tmp);
137 }
138 }
139
140 /* Not found */
141 return size;
142}