root / bitops.c @ 0ef654e3
History | View | Annotate | Download (3.4 kB)
1 | e0e53b2f | Corentin Chary | /*
|
---|---|---|---|
2 | e0e53b2f | Corentin Chary | * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
|
3 | e0e53b2f | Corentin Chary | * Written by David Howells (dhowells@redhat.com)
|
4 | e0e53b2f | Corentin Chary | * Copyright (C) 2008 IBM Corporation
|
5 | e0e53b2f | Corentin Chary | * Written by Rusty Russell <rusty@rustcorp.com.au>
|
6 | e0e53b2f | Corentin Chary | * (Inspired by David Howell's find_next_bit implementation)
|
7 | e0e53b2f | Corentin Chary | *
|
8 | e0e53b2f | Corentin Chary | * This program is free software; you can redistribute it and/or
|
9 | e0e53b2f | Corentin Chary | * modify it under the terms of the GNU General Public License
|
10 | e0e53b2f | Corentin Chary | * as published by the Free Software Foundation; either version
|
11 | e0e53b2f | Corentin Chary | * 2 of the License, or (at your option) any later version.
|
12 | e0e53b2f | Corentin Chary | */
|
13 | e0e53b2f | Corentin Chary | |
14 | e0e53b2f | Corentin Chary | #include "bitops.h" |
15 | e0e53b2f | Corentin Chary | |
16 | e0e53b2f | Corentin Chary | #define BITOP_WORD(nr) ((nr) / BITS_PER_LONG)
|
17 | e0e53b2f | Corentin Chary | |
18 | e0e53b2f | Corentin Chary | /*
|
19 | e0e53b2f | Corentin Chary | * Find the next set bit in a memory region.
|
20 | e0e53b2f | Corentin Chary | */
|
21 | e0e53b2f | Corentin Chary | unsigned long find_next_bit(const unsigned long *addr, unsigned long size, |
22 | e0e53b2f | Corentin Chary | unsigned long offset) |
23 | e0e53b2f | Corentin Chary | { |
24 | e0e53b2f | Corentin Chary | const unsigned long *p = addr + BITOP_WORD(offset); |
25 | e0e53b2f | Corentin Chary | unsigned long result = offset & ~(BITS_PER_LONG-1); |
26 | e0e53b2f | Corentin Chary | unsigned long tmp; |
27 | e0e53b2f | Corentin Chary | |
28 | e0e53b2f | Corentin Chary | if (offset >= size) {
|
29 | e0e53b2f | Corentin Chary | return size;
|
30 | e0e53b2f | Corentin Chary | } |
31 | e0e53b2f | Corentin Chary | size -= result; |
32 | e0e53b2f | Corentin Chary | offset %= BITS_PER_LONG; |
33 | e0e53b2f | Corentin Chary | if (offset) {
|
34 | e0e53b2f | Corentin Chary | tmp = *(p++); |
35 | e0e53b2f | Corentin Chary | tmp &= (~0UL << offset);
|
36 | e0e53b2f | Corentin Chary | if (size < BITS_PER_LONG) {
|
37 | e0e53b2f | Corentin Chary | goto found_first;
|
38 | e0e53b2f | Corentin Chary | } |
39 | e0e53b2f | Corentin Chary | if (tmp) {
|
40 | e0e53b2f | Corentin Chary | goto found_middle;
|
41 | e0e53b2f | Corentin Chary | } |
42 | e0e53b2f | Corentin Chary | size -= BITS_PER_LONG; |
43 | e0e53b2f | Corentin Chary | result += BITS_PER_LONG; |
44 | e0e53b2f | Corentin Chary | } |
45 | e0e53b2f | Corentin Chary | while (size & ~(BITS_PER_LONG-1)) { |
46 | e0e53b2f | Corentin Chary | if ((tmp = *(p++))) {
|
47 | e0e53b2f | Corentin Chary | goto found_middle;
|
48 | e0e53b2f | Corentin Chary | } |
49 | e0e53b2f | Corentin Chary | result += BITS_PER_LONG; |
50 | e0e53b2f | Corentin Chary | size -= BITS_PER_LONG; |
51 | e0e53b2f | Corentin Chary | } |
52 | e0e53b2f | Corentin Chary | if (!size) {
|
53 | e0e53b2f | Corentin Chary | return result;
|
54 | e0e53b2f | Corentin Chary | } |
55 | e0e53b2f | Corentin Chary | tmp = *p; |
56 | e0e53b2f | Corentin Chary | |
57 | e0e53b2f | Corentin Chary | found_first:
|
58 | e0e53b2f | Corentin Chary | tmp &= (~0UL >> (BITS_PER_LONG - size));
|
59 | e0e53b2f | Corentin Chary | if (tmp == 0UL) { /* Are any bits set? */ |
60 | e0e53b2f | Corentin Chary | return result + size; /* Nope. */ |
61 | e0e53b2f | Corentin Chary | } |
62 | e0e53b2f | Corentin Chary | found_middle:
|
63 | e0e53b2f | Corentin Chary | return result + bitops_ffsl(tmp);
|
64 | e0e53b2f | Corentin Chary | } |
65 | e0e53b2f | Corentin Chary | |
66 | e0e53b2f | Corentin Chary | /*
|
67 | e0e53b2f | Corentin Chary | * This implementation of find_{first,next}_zero_bit was stolen from
|
68 | e0e53b2f | Corentin Chary | * Linus' asm-alpha/bitops.h.
|
69 | e0e53b2f | Corentin Chary | */
|
70 | e0e53b2f | Corentin Chary | unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size, |
71 | e0e53b2f | Corentin Chary | unsigned long offset) |
72 | e0e53b2f | Corentin Chary | { |
73 | e0e53b2f | Corentin Chary | const unsigned long *p = addr + BITOP_WORD(offset); |
74 | e0e53b2f | Corentin Chary | unsigned long result = offset & ~(BITS_PER_LONG-1); |
75 | e0e53b2f | Corentin Chary | unsigned long tmp; |
76 | e0e53b2f | Corentin Chary | |
77 | e0e53b2f | Corentin Chary | if (offset >= size) {
|
78 | e0e53b2f | Corentin Chary | return size;
|
79 | e0e53b2f | Corentin Chary | } |
80 | e0e53b2f | Corentin Chary | size -= result; |
81 | e0e53b2f | Corentin Chary | offset %= BITS_PER_LONG; |
82 | e0e53b2f | Corentin Chary | if (offset) {
|
83 | e0e53b2f | Corentin Chary | tmp = *(p++); |
84 | e0e53b2f | Corentin Chary | tmp |= ~0UL >> (BITS_PER_LONG - offset);
|
85 | e0e53b2f | Corentin Chary | if (size < BITS_PER_LONG) {
|
86 | e0e53b2f | Corentin Chary | goto found_first;
|
87 | e0e53b2f | Corentin Chary | } |
88 | e0e53b2f | Corentin Chary | if (~tmp) {
|
89 | e0e53b2f | Corentin Chary | goto found_middle;
|
90 | e0e53b2f | Corentin Chary | } |
91 | e0e53b2f | Corentin Chary | size -= BITS_PER_LONG; |
92 | e0e53b2f | Corentin Chary | result += BITS_PER_LONG; |
93 | e0e53b2f | Corentin Chary | } |
94 | e0e53b2f | Corentin Chary | while (size & ~(BITS_PER_LONG-1)) { |
95 | e0e53b2f | Corentin Chary | if (~(tmp = *(p++))) {
|
96 | e0e53b2f | Corentin Chary | goto found_middle;
|
97 | e0e53b2f | Corentin Chary | } |
98 | e0e53b2f | Corentin Chary | result += BITS_PER_LONG; |
99 | e0e53b2f | Corentin Chary | size -= BITS_PER_LONG; |
100 | e0e53b2f | Corentin Chary | } |
101 | e0e53b2f | Corentin Chary | if (!size) {
|
102 | e0e53b2f | Corentin Chary | return result;
|
103 | e0e53b2f | Corentin Chary | } |
104 | e0e53b2f | Corentin Chary | tmp = *p; |
105 | e0e53b2f | Corentin Chary | |
106 | e0e53b2f | Corentin Chary | found_first:
|
107 | e0e53b2f | Corentin Chary | tmp |= ~0UL << size;
|
108 | e0e53b2f | Corentin Chary | if (tmp == ~0UL) { /* Are any bits zero? */ |
109 | e0e53b2f | Corentin Chary | return result + size; /* Nope. */ |
110 | e0e53b2f | Corentin Chary | } |
111 | e0e53b2f | Corentin Chary | found_middle:
|
112 | e0e53b2f | Corentin Chary | return result + ffz(tmp);
|
113 | e0e53b2f | Corentin Chary | } |
114 | e0e53b2f | Corentin Chary | |
115 | e0e53b2f | Corentin Chary | unsigned long find_last_bit(const unsigned long *addr, unsigned long size) |
116 | e0e53b2f | Corentin Chary | { |
117 | e0e53b2f | Corentin Chary | unsigned long words; |
118 | e0e53b2f | Corentin Chary | unsigned long tmp; |
119 | e0e53b2f | Corentin Chary | |
120 | e0e53b2f | Corentin Chary | /* Start at final word. */
|
121 | e0e53b2f | Corentin Chary | words = size / BITS_PER_LONG; |
122 | e0e53b2f | Corentin Chary | |
123 | e0e53b2f | Corentin Chary | /* Partial final word? */
|
124 | e0e53b2f | Corentin Chary | if (size & (BITS_PER_LONG-1)) { |
125 | e0e53b2f | Corentin Chary | tmp = (addr[words] & (~0UL >> (BITS_PER_LONG
|
126 | e0e53b2f | Corentin Chary | - (size & (BITS_PER_LONG-1)))));
|
127 | e0e53b2f | Corentin Chary | if (tmp) {
|
128 | e0e53b2f | Corentin Chary | goto found;
|
129 | e0e53b2f | Corentin Chary | } |
130 | e0e53b2f | Corentin Chary | } |
131 | e0e53b2f | Corentin Chary | |
132 | e0e53b2f | Corentin Chary | while (words) {
|
133 | e0e53b2f | Corentin Chary | tmp = addr[--words]; |
134 | e0e53b2f | Corentin Chary | if (tmp) {
|
135 | e0e53b2f | Corentin Chary | found:
|
136 | e0e53b2f | Corentin Chary | return words * BITS_PER_LONG + bitops_flsl(tmp);
|
137 | e0e53b2f | Corentin Chary | } |
138 | e0e53b2f | Corentin Chary | } |
139 | e0e53b2f | Corentin Chary | |
140 | e0e53b2f | Corentin Chary | /* Not found */
|
141 | e0e53b2f | Corentin Chary | return size;
|
142 | e0e53b2f | Corentin Chary | } |