/* * CDDL HEADER START * * The contents of this file are subject to the terms of the * Common Development and Distribution License, Version 1.0 only * (the "License"). You may not use this file except in compliance * with the License. * * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE * or http://www.opensolaris.org/os/licensing. * See the License for the specific language governing permissions * and limitations under the License. * * When distributing Covered Code, include this CDDL HEADER in each * file and include the License file at usr/src/OPENSOLARIS.LICENSE. * If applicable, add the following below this CDDL HEADER, with the * fields enclosed by brackets "[]" replaced with your own identifying * information: Portions Copyright [yyyy] [name of copyright owner] * * CDDL HEADER END */ /* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */ /* All Rights Reserved */ /* * Copyright 2004 Sun Microsystems, Inc. All rights reserved. * Use is subject to license terms. * Copyright 2022 Oxide Computer Company */ /* * Operations on bitmaps of arbitrary size * A bitmap is a vector of 1 or more ulongs. * The user of the package is responsible for range checks and keeping * track of sizes. */ #include <sys/types.h> #include <sys/bitmap.h> #include <sys/debug.h> /* * Return index of first available bit in denoted bitmap, or -1 for * failure. Size is the cardinality of the bitmap; that is, the * number of bits. * No side-effects. In particular, does not update bitmap. * Caller is responsible for range checks. */ index_t bt_availbit(const ulong_t *bitmap, size_t nbits) { index_t maxword; /* index of last in map */ index_t wx; /* word index in map */ /* * Look for a word with a bit off. * Subtract one from nbits because we're converting it to a * a range of indices. */ nbits -= 1; maxword = nbits >> BT_ULSHIFT; for (wx = 0; wx <= maxword; wx++) if (bitmap[wx] != ~0) break; if (wx <= maxword) { /* * Found a word with a bit off. Now find the bit in the word. */ index_t bx; /* bit index in word */ index_t maxbit; /* last bit to look at */ ulong_t word; ulong_t bit; maxbit = wx == maxword ? nbits & BT_ULMASK : BT_NBIPUL - 1; word = bitmap[wx]; bit = 1; for (bx = 0; bx <= maxbit; bx++, bit <<= 1) { if (!(word & bit)) { return (wx << BT_ULSHIFT | bx); } } } return (-1); } /* * Find highest order bit that is on, and is within or below * the word specified by wx. */ int bt_gethighbit(const ulong_t *mapp, int wx) { ulong_t word; while ((word = mapp[wx]) == 0) { wx--; if (wx < 0) { return (-1); } } return (wx << BT_ULSHIFT | (highbit(word) - 1)); } /* * Search the bitmap for a consecutive pattern of 1's. * Search starts at position pos1. * Returns 1 on success and 0 on failure. * Side effects. * Returns indices to the first bit (pos1) * and one past the last bit (pos2) in the pattern. */ int bt_range(const ulong_t *bitmap, size_t *pos1, size_t *pos2, size_t end_pos) { size_t pos; for (pos = *pos1; pos < end_pos; pos++) if (BT_TEST(bitmap, pos)) break; if (pos == end_pos) return (0); *pos1 = pos; for (; pos < end_pos; pos++) if (!BT_TEST(bitmap, pos)) break; *pos2 = pos; return (1); } /* * return the parity of the supplied long * * this works by successively partitioning the argument in half, and * setting the parity of the result to the parity of the 2 halfs, until * only one bit is left */ int odd_parity(ulong_t i) { #ifdef _LP64 i ^= i >> 32; #endif i ^= i >> 16; i ^= i >> 8; i ^= i >> 4; i ^= i >> 2; i ^= i >> 1; return (i & 0x01); } /* * get the lowest bit in the range of 'start' and 'stop', inclusive. * I.e., if caller calls bt_getlowbit(map, X, Y), any value between X and Y, * including X and Y can be returned. * Neither start nor stop is required to align with word boundaries. * If a bit is set in the range, the bit position is returned; otherwise, * a -1 is returned. */ int bt_getlowbit(const ulong_t *map, size_t start, size_t stop) { ulong_t word; int counter = start >> BT_ULSHIFT; int limit = stop >> BT_ULSHIFT; index_t partial_start = start & BT_ULMASK; index_t partial_stop = stop & BT_ULMASK; if (start > stop) { return (-1); } /* * The range between 'start' and 'stop' can be very large, and the * '1' bits in this range can be sparse. * For performance reason, the underlying implementation operates * on words, not on bits. */ word = map[counter]; if (partial_start) { /* * Since the start is not aligned on word boundary, we * need to patch the unwanted low order bits with 0's before * operating on the first bitmap word. */ word = word & (BT_ULMAXMASK << partial_start); } /* * Locate a word from the map array with one of the bits set. */ while ((word == 0) && (counter < limit)) { word = map[++counter]; } /* * The end of range has similar problems if it is not aligned. * Taking care of the end which is not aligned. */ if ((counter == limit) && (partial_stop != BT_ULMASK)) { /* * Take care the partial word by patch the high order * bits with 0's. Here we dealing with the case that * the last word of the bitmap is not aligned. */ ASSERT(partial_stop < BT_ULMASK); word = word & (~(BT_ULMAXMASK << partial_stop + 1)); } /* * Examine the word. */ if (word == 0) { return (-1); } else { return ((counter << BT_ULSHIFT) | (lowbit(word) - 1)); } } /* * Copy the bitmap. */ void bt_copy(const ulong_t *from, ulong_t *to, ulong_t size) { ulong_t i; for (i = 0; i < size; i++) *to++ = *from++; }
