1/*
2 * CDDL HEADER START
3 *
4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License, Version 1.0 only
6 * (the "License").  You may not use this file except in compliance
7 * with the License.
8 *
9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10 * or http://www.opensolaris.org/os/licensing.
11 * See the License for the specific language governing permissions
12 * and limitations under the License.
13 *
14 * When distributing Covered Code, include this CDDL HEADER in each
15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16 * If applicable, add the following below this CDDL HEADER, with the
17 * fields enclosed by brackets "[]" replaced with your own identifying
18 * information: Portions Copyright [yyyy] [name of copyright owner]
19 *
20 * CDDL HEADER END
21 */
22/*	Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T	*/
23/*	  All Rights Reserved  	*/
24
25
26/*
27 * Copyright 2004 Sun Microsystems, Inc.  All rights reserved.
28 * Use is subject to license terms.
29 */
30
31#pragma ident	"%Z%%M%	%I%	%E% SMI"
32
33/*
34 * Operations on bitmaps of arbitrary size
35 * A bitmap is a vector of 1 or more ulongs.
36 * The user of the package is responsible for range checks and keeping
37 * track of sizes.
38 */
39
40#include <sys/types.h>
41#include <sys/bitmap.h>
42#include <sys/debug.h>		/* ASSERT */
43
44/*
45 * Return index of first available bit in denoted bitmap, or -1 for
46 * failure.  Size is the cardinality of the bitmap; that is, the
47 * number of bits.
48 * No side-effects.  In particular, does not update bitmap.
49 * Caller is responsible for range checks.
50 */
51index_t
52bt_availbit(ulong_t *bitmap, size_t nbits)
53{
54	index_t	maxword;	/* index of last in map */
55	index_t	wx;		/* word index in map */
56
57	/*
58	 * Look for a word with a bit off.
59	 * Subtract one from nbits because we're converting it to a
60	 * a range of indices.
61	 */
62	nbits -= 1;
63	maxword = nbits >> BT_ULSHIFT;
64	for (wx = 0; wx <= maxword; wx++)
65		if (bitmap[wx] != ~0)
66			break;
67
68	if (wx <= maxword) {
69		/*
70		 * Found a word with a bit off.  Now find the bit in the word.
71		 */
72		index_t	bx;	/* bit index in word */
73		index_t	maxbit; /* last bit to look at */
74		ulong_t		word;
75		ulong_t		bit;
76
77		maxbit = wx == maxword ? nbits & BT_ULMASK : BT_NBIPUL - 1;
78		word = bitmap[wx];
79		bit = 1;
80		for (bx = 0; bx <= maxbit; bx++, bit <<= 1) {
81			if (!(word & bit)) {
82				return (wx << BT_ULSHIFT | bx);
83			}
84		}
85	}
86	return (-1);
87}
88
89
90/*
91 * Find highest order bit that is on, and is within or below
92 * the word specified by wx.
93 */
94int
95bt_gethighbit(ulong_t *mapp, int wx)
96{
97	ulong_t word;
98
99	while ((word = mapp[wx]) == 0) {
100		wx--;
101		if (wx < 0) {
102			return (-1);
103		}
104	}
105	return (wx << BT_ULSHIFT | (highbit(word) - 1));
106}
107
108
109/*
110 * Search the bitmap for a consecutive pattern of 1's.
111 * Search starts at position pos1.
112 * Returns 1 on success and 0 on failure.
113 * Side effects.
114 * Returns indices to the first bit (pos1)
115 * and one past the last bit (pos2) in the pattern.
116 */
117int
118bt_range(ulong_t *bitmap, size_t *pos1, size_t *pos2, size_t end_pos)
119{
120	size_t pos;
121
122	for (pos = *pos1; pos < end_pos; pos++)
123		if (BT_TEST(bitmap, pos))
124			break;
125
126	if (pos == end_pos)
127		return (0);
128
129	*pos1 = pos;
130
131	for (; pos < end_pos; pos++)
132		if (!BT_TEST(bitmap, pos))
133			break;
134	*pos2 = pos;
135
136	return (1);
137}
138
139
140/*
141 * return the parity of the supplied long
142 *
143 * this works by successively partitioning the argument in half, and
144 * setting the parity of the result to the parity of the 2 halfs, until
145 * only one bit is left
146 */
147int
148odd_parity(ulong_t i)
149{
150#ifdef _LP64
151	i ^= i >> 32;
152#endif
153	i ^= i >> 16;
154	i ^= i >> 8;
155	i ^= i >> 4;
156	i ^= i >> 2;
157	i ^= i >> 1;
158
159	return (i & 0x01);
160}
161
162
163/*
164 * get the lowest bit in the range of 'start' and 'stop', inclusive.
165 * I.e., if caller calls bt_getlowbit(map, X, Y), any value between X and Y,
166 * including X and Y can be returned.
167 * Neither start nor stop is required to align with word boundaries.
168 * If a bit is set in the range, the bit position is returned; otherwise,
169 * a -1 is returned.
170 */
171int
172bt_getlowbit(ulong_t *map, size_t start, size_t stop)
173{
174	ulong_t		word;
175	int		counter = start >> BT_ULSHIFT;
176	int		limit = stop >> BT_ULSHIFT;
177	index_t		partial_start = start & BT_ULMASK;
178	index_t		partial_stop = stop & BT_ULMASK;
179
180	if (start > stop) {
181		return (-1);
182	}
183
184	/*
185	 * The range between 'start' and 'stop' can be very large, and the
186	 * '1' bits in this range can be sparse.
187	 * For performance reason, the underlying implementation operates
188	 * on words, not on bits.
189	 */
190	word = map[counter];
191
192	if (partial_start) {
193		/*
194		 * Since the start is not aligned on word boundary, we
195		 * need to patch the unwanted low order bits with 0's before
196		 * operating on the first bitmap word.
197		 */
198		word = word & (BT_ULMAXMASK << partial_start);
199	}
200
201	/*
202	 * Locate a word from the map array with one of the bits set.
203	 */
204
205	while ((word == 0) && (counter < limit)) {
206		word = map[++counter];
207	}
208
209	/*
210	 * The end of range has similar problems if it is not aligned.
211	 * Taking care of the end which is not aligned.
212	 */
213
214	if ((counter == limit) && (partial_stop != BT_ULMASK)) {
215		/*
216		 * Take care the partial word by patch the high order
217		 * bits with 0's. Here we dealing with the case that
218		 * the last word of the bitmap is not aligned.
219		 */
220
221		ASSERT(partial_stop < BT_ULMASK);
222		word = word & (~(BT_ULMAXMASK << partial_stop + 1));
223	}
224
225	/*
226	 * Examine the word.
227	 */
228	if (word == 0) {
229		return (-1);
230	} else {
231		return ((counter << BT_ULSHIFT) | (lowbit(word) - 1));
232	}
233}
234
235/*
236 * Copy the bitmap.
237 */
238void
239bt_copy(ulong_t *from, ulong_t *to, ulong_t size)
240{
241	ulong_t i;
242	for (i = 0; i < size; i++)
243		*to++ = *from++;
244}
245