fs/ntfs3/bitfunc.c

0001 // SPDX-License-Identifier: GPL-2.0
0002 /*
0003  *
0004  * Copyright (C) 2019-2021 Paragon Software GmbH, All rights reserved.
0005  *
0006  */
0007
0008 #include <linux/types.h>
0009
0010 #include "ntfs_fs.h"
0011
0012 #define BITS_IN_SIZE_T (sizeof(size_t) * 8)
0013
0014 /*
0015  * fill_mask[i] - first i bits are '1' , i = 0,1,2,3,4,5,6,7,8
0016  * fill_mask[i] = 0xFF >> (8-i)
0017  */
0018 static const u8 fill_mask[] = { 0x00, 0x01, 0x03, 0x07, 0x0F,
0019                 0x1F, 0x3F, 0x7F, 0xFF };
0020
0021 /*
0022  * zero_mask[i] - first i bits are '0' , i = 0,1,2,3,4,5,6,7,8
0023  * zero_mask[i] = 0xFF << i
0024  */
0025 static const u8 zero_mask[] = { 0xFF, 0xFE, 0xFC, 0xF8, 0xF0,
0026                 0xE0, 0xC0, 0x80, 0x00 };
0027
0028 /*
0029  * are_bits_clear
0030  *
0031  * Return: True if all bits [bit, bit+nbits) are zeros "0".
0032  */
0033 bool are_bits_clear(const ulong *lmap, size_t bit, size_t nbits)
0034 {
0035     size_t pos = bit & 7;
0036     const u8 *map = (u8 *)lmap + (bit >> 3);
0037
0038     if (pos) {
0039         if (8 - pos >= nbits)
0040             return !nbits || !(*map & fill_mask[pos + nbits] &
0041                        zero_mask[pos]);
0042
0043         if (*map++ & zero_mask[pos])
0044             return false;
0045         nbits -= 8 - pos;
0046     }
0047
0048     pos = ((size_t)map) & (sizeof(size_t) - 1);
0049     if (pos) {
0050         pos = sizeof(size_t) - pos;
0051         if (nbits >= pos * 8) {
0052             for (nbits -= pos * 8; pos; pos--, map++) {
0053                 if (*map)
0054                     return false;
0055             }
0056         }
0057     }
0058
0059     for (pos = nbits / BITS_IN_SIZE_T; pos; pos--, map += sizeof(size_t)) {
0060         if (*((size_t *)map))
0061             return false;
0062     }
0063
0064     for (pos = (nbits % BITS_IN_SIZE_T) >> 3; pos; pos--, map++) {
0065         if (*map)
0066             return false;
0067     }
0068
0069     pos = nbits & 7;
0070     if (pos && (*map & fill_mask[pos]))
0071         return false;
0072
0073     return true;
0074 }
0075
0076 /*
0077  * are_bits_set
0078  *
0079  * Return: True if all bits [bit, bit+nbits) are ones "1".
0080  */
0081 bool are_bits_set(const ulong *lmap, size_t bit, size_t nbits)
0082 {
0083     u8 mask;
0084     size_t pos = bit & 7;
0085     const u8 *map = (u8 *)lmap + (bit >> 3);
0086
0087     if (pos) {
0088         if (8 - pos >= nbits) {
0089             mask = fill_mask[pos + nbits] & zero_mask[pos];
0090             return !nbits || (*map & mask) == mask;
0091         }
0092
0093         mask = zero_mask[pos];
0094         if ((*map++ & mask) != mask)
0095             return false;
0096         nbits -= 8 - pos;
0097     }
0098
0099     pos = ((size_t)map) & (sizeof(size_t) - 1);
0100     if (pos) {
0101         pos = sizeof(size_t) - pos;
0102         if (nbits >= pos * 8) {
0103             for (nbits -= pos * 8; pos; pos--, map++) {
0104                 if (*map != 0xFF)
0105                     return false;
0106             }
0107         }
0108     }
0109
0110     for (pos = nbits / BITS_IN_SIZE_T; pos; pos--, map += sizeof(size_t)) {
0111         if (*((size_t *)map) != MINUS_ONE_T)
0112             return false;
0113     }
0114
0115     for (pos = (nbits % BITS_IN_SIZE_T) >> 3; pos; pos--, map++) {
0116         if (*map != 0xFF)
0117             return false;
0118     }
0119
0120     pos = nbits & 7;
0121     if (pos) {
0122         mask = fill_mask[pos];
0123         if ((*map & mask) != mask)
0124             return false;
0125     }
0126
0127     return true;
0128 }