1*4882a593Smuzhiyun // SPDX-License-Identifier: GPL-2.0
2*4882a593Smuzhiyun /*
3*4882a593Smuzhiyun * Copyright (c) 2000-2005 Silicon Graphics, Inc.
4*4882a593Smuzhiyun * All Rights Reserved.
5*4882a593Smuzhiyun */
6*4882a593Smuzhiyun #include "xfs.h"
7*4882a593Smuzhiyun #include "xfs_log_format.h"
8*4882a593Smuzhiyun #include "xfs_bit.h"
9*4882a593Smuzhiyun
10*4882a593Smuzhiyun /*
11*4882a593Smuzhiyun * XFS bit manipulation routines, used in non-realtime code.
12*4882a593Smuzhiyun */
13*4882a593Smuzhiyun
14*4882a593Smuzhiyun /*
15*4882a593Smuzhiyun * Return whether bitmap is empty.
16*4882a593Smuzhiyun * Size is number of words in the bitmap, which is padded to word boundary
17*4882a593Smuzhiyun * Returns 1 for empty, 0 for non-empty.
18*4882a593Smuzhiyun */
19*4882a593Smuzhiyun int
xfs_bitmap_empty(uint * map,uint size)20*4882a593Smuzhiyun xfs_bitmap_empty(uint *map, uint size)
21*4882a593Smuzhiyun {
22*4882a593Smuzhiyun uint i;
23*4882a593Smuzhiyun
24*4882a593Smuzhiyun for (i = 0; i < size; i++) {
25*4882a593Smuzhiyun if (map[i] != 0)
26*4882a593Smuzhiyun return 0;
27*4882a593Smuzhiyun }
28*4882a593Smuzhiyun
29*4882a593Smuzhiyun return 1;
30*4882a593Smuzhiyun }
31*4882a593Smuzhiyun
32*4882a593Smuzhiyun /*
33*4882a593Smuzhiyun * Count the number of contiguous bits set in the bitmap starting with bit
34*4882a593Smuzhiyun * start_bit. Size is the size of the bitmap in words.
35*4882a593Smuzhiyun */
36*4882a593Smuzhiyun int
xfs_contig_bits(uint * map,uint size,uint start_bit)37*4882a593Smuzhiyun xfs_contig_bits(uint *map, uint size, uint start_bit)
38*4882a593Smuzhiyun {
39*4882a593Smuzhiyun uint * p = ((unsigned int *) map) + (start_bit >> BIT_TO_WORD_SHIFT);
40*4882a593Smuzhiyun uint result = 0;
41*4882a593Smuzhiyun uint tmp;
42*4882a593Smuzhiyun
43*4882a593Smuzhiyun size <<= BIT_TO_WORD_SHIFT;
44*4882a593Smuzhiyun
45*4882a593Smuzhiyun ASSERT(start_bit < size);
46*4882a593Smuzhiyun size -= start_bit & ~(NBWORD - 1);
47*4882a593Smuzhiyun start_bit &= (NBWORD - 1);
48*4882a593Smuzhiyun if (start_bit) {
49*4882a593Smuzhiyun tmp = *p++;
50*4882a593Smuzhiyun /* set to one first offset bits prior to start */
51*4882a593Smuzhiyun tmp |= (~0U >> (NBWORD-start_bit));
52*4882a593Smuzhiyun if (tmp != ~0U)
53*4882a593Smuzhiyun goto found;
54*4882a593Smuzhiyun result += NBWORD;
55*4882a593Smuzhiyun size -= NBWORD;
56*4882a593Smuzhiyun }
57*4882a593Smuzhiyun while (size) {
58*4882a593Smuzhiyun if ((tmp = *p++) != ~0U)
59*4882a593Smuzhiyun goto found;
60*4882a593Smuzhiyun result += NBWORD;
61*4882a593Smuzhiyun size -= NBWORD;
62*4882a593Smuzhiyun }
63*4882a593Smuzhiyun return result - start_bit;
64*4882a593Smuzhiyun found:
65*4882a593Smuzhiyun return result + ffz(tmp) - start_bit;
66*4882a593Smuzhiyun }
67*4882a593Smuzhiyun
68*4882a593Smuzhiyun /*
69*4882a593Smuzhiyun * This takes the bit number to start looking from and
70*4882a593Smuzhiyun * returns the next set bit from there. It returns -1
71*4882a593Smuzhiyun * if there are no more bits set or the start bit is
72*4882a593Smuzhiyun * beyond the end of the bitmap.
73*4882a593Smuzhiyun *
74*4882a593Smuzhiyun * Size is the number of words, not bytes, in the bitmap.
75*4882a593Smuzhiyun */
xfs_next_bit(uint * map,uint size,uint start_bit)76*4882a593Smuzhiyun int xfs_next_bit(uint *map, uint size, uint start_bit)
77*4882a593Smuzhiyun {
78*4882a593Smuzhiyun uint * p = ((unsigned int *) map) + (start_bit >> BIT_TO_WORD_SHIFT);
79*4882a593Smuzhiyun uint result = start_bit & ~(NBWORD - 1);
80*4882a593Smuzhiyun uint tmp;
81*4882a593Smuzhiyun
82*4882a593Smuzhiyun size <<= BIT_TO_WORD_SHIFT;
83*4882a593Smuzhiyun
84*4882a593Smuzhiyun if (start_bit >= size)
85*4882a593Smuzhiyun return -1;
86*4882a593Smuzhiyun size -= result;
87*4882a593Smuzhiyun start_bit &= (NBWORD - 1);
88*4882a593Smuzhiyun if (start_bit) {
89*4882a593Smuzhiyun tmp = *p++;
90*4882a593Smuzhiyun /* set to zero first offset bits prior to start */
91*4882a593Smuzhiyun tmp &= (~0U << start_bit);
92*4882a593Smuzhiyun if (tmp != 0U)
93*4882a593Smuzhiyun goto found;
94*4882a593Smuzhiyun result += NBWORD;
95*4882a593Smuzhiyun size -= NBWORD;
96*4882a593Smuzhiyun }
97*4882a593Smuzhiyun while (size) {
98*4882a593Smuzhiyun if ((tmp = *p++) != 0U)
99*4882a593Smuzhiyun goto found;
100*4882a593Smuzhiyun result += NBWORD;
101*4882a593Smuzhiyun size -= NBWORD;
102*4882a593Smuzhiyun }
103*4882a593Smuzhiyun return -1;
104*4882a593Smuzhiyun found:
105*4882a593Smuzhiyun return result + ffs(tmp) - 1;
106*4882a593Smuzhiyun }
107