1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * 4 * Copyright (C) 2019-2021 Paragon Software GmbH, All rights reserved. 5 * 6 */ 7 8 #include <linux/types.h> 9 10 #include "ntfs_fs.h" 11 12 #define BITS_IN_SIZE_T (sizeof(size_t) * 8) 13 14 /* 15 * fill_mask[i] - first i bits are '1' , i = 0,1,2,3,4,5,6,7,8 16 * fill_mask[i] = 0xFF >> (8-i) 17 */ 18 static const u8 fill_mask[] = { 0x00, 0x01, 0x03, 0x07, 0x0F, 19 0x1F, 0x3F, 0x7F, 0xFF }; 20 21 /* 22 * zero_mask[i] - first i bits are '0' , i = 0,1,2,3,4,5,6,7,8 23 * zero_mask[i] = 0xFF << i 24 */ 25 static const u8 zero_mask[] = { 0xFF, 0xFE, 0xFC, 0xF8, 0xF0, 26 0xE0, 0xC0, 0x80, 0x00 }; 27 28 /* 29 * are_bits_clear 30 * 31 * Return: True if all bits [bit, bit+nbits) are zeros "0". 32 */ 33 bool are_bits_clear(const void *lmap, size_t bit, size_t nbits) 34 { 35 size_t pos = bit & 7; 36 const u8 *map = (u8 *)lmap + (bit >> 3); 37 38 if (pos) { 39 if (8 - pos >= nbits) 40 return !nbits || !(*map & fill_mask[pos + nbits] & 41 zero_mask[pos]); 42 43 if (*map++ & zero_mask[pos]) 44 return false; 45 nbits -= 8 - pos; 46 } 47 48 pos = ((size_t)map) & (sizeof(size_t) - 1); 49 if (pos) { 50 pos = sizeof(size_t) - pos; 51 if (nbits >= pos * 8) { 52 for (nbits -= pos * 8; pos; pos--, map++) { 53 if (*map) 54 return false; 55 } 56 } 57 } 58 59 for (pos = nbits / BITS_IN_SIZE_T; pos; pos--, map += sizeof(size_t)) { 60 if (*((size_t *)map)) 61 return false; 62 } 63 64 for (pos = (nbits % BITS_IN_SIZE_T) >> 3; pos; pos--, map++) { 65 if (*map) 66 return false; 67 } 68 69 pos = nbits & 7; 70 if (pos && (*map & fill_mask[pos])) 71 return false; 72 73 return true; 74 } 75 76 /* 77 * are_bits_set 78 * 79 * Return: True if all bits [bit, bit+nbits) are ones "1". 80 */ 81 bool are_bits_set(const void *lmap, size_t bit, size_t nbits) 82 { 83 u8 mask; 84 size_t pos = bit & 7; 85 const u8 *map = (u8 *)lmap + (bit >> 3); 86 87 if (pos) { 88 if (8 - pos >= nbits) { 89 mask = fill_mask[pos + nbits] & zero_mask[pos]; 90 return !nbits || (*map & mask) == mask; 91 } 92 93 mask = zero_mask[pos]; 94 if ((*map++ & mask) != mask) 95 return false; 96 nbits -= 8 - pos; 97 } 98 99 pos = ((size_t)map) & (sizeof(size_t) - 1); 100 if (pos) { 101 pos = sizeof(size_t) - pos; 102 if (nbits >= pos * 8) { 103 for (nbits -= pos * 8; pos; pos--, map++) { 104 if (*map != 0xFF) 105 return false; 106 } 107 } 108 } 109 110 for (pos = nbits / BITS_IN_SIZE_T; pos; pos--, map += sizeof(size_t)) { 111 if (*((size_t *)map) != MINUS_ONE_T) 112 return false; 113 } 114 115 for (pos = (nbits % BITS_IN_SIZE_T) >> 3; pos; pos--, map++) { 116 if (*map != 0xFF) 117 return false; 118 } 119 120 pos = nbits & 7; 121 if (pos) { 122 mask = fill_mask[pos]; 123 if ((*map & mask) != mask) 124 return false; 125 } 126 127 return true; 128 } 129