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