1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * 4 * Copyright (C) 2019-2021 Paragon Software GmbH, All rights reserved. 5 * 6 */ 7 #include <linux/blkdev.h> 8 #include <linux/buffer_head.h> 9 #include <linux/fs.h> 10 #include <linux/nls.h> 11 12 #include "debug.h" 13 #include "ntfs.h" 14 #include "ntfs_fs.h" 15 16 #define BITS_IN_SIZE_T (sizeof(size_t) * 8) 17 18 /* 19 * fill_mask[i] - first i bits are '1' , i = 0,1,2,3,4,5,6,7,8 20 * fill_mask[i] = 0xFF >> (8-i) 21 */ 22 static const u8 fill_mask[] = { 0x00, 0x01, 0x03, 0x07, 0x0F, 23 0x1F, 0x3F, 0x7F, 0xFF }; 24 25 /* 26 * zero_mask[i] - first i bits are '0' , i = 0,1,2,3,4,5,6,7,8 27 * zero_mask[i] = 0xFF << i 28 */ 29 static const u8 zero_mask[] = { 0xFF, 0xFE, 0xFC, 0xF8, 0xF0, 30 0xE0, 0xC0, 0x80, 0x00 }; 31 32 /* 33 * are_bits_clear 34 * 35 * Returns true if all bits [bit, bit+nbits) are zeros "0" 36 */ 37 bool are_bits_clear(const ulong *lmap, size_t bit, size_t nbits) 38 { 39 size_t pos = bit & 7; 40 const u8 *map = (u8 *)lmap + (bit >> 3); 41 42 if (pos) { 43 if (8 - pos >= nbits) 44 return !nbits || !(*map & fill_mask[pos + nbits] & 45 zero_mask[pos]); 46 47 if (*map++ & zero_mask[pos]) 48 return false; 49 nbits -= 8 - pos; 50 } 51 52 pos = ((size_t)map) & (sizeof(size_t) - 1); 53 if (pos) { 54 pos = sizeof(size_t) - pos; 55 if (nbits >= pos * 8) { 56 for (nbits -= pos * 8; pos; pos--, map++) { 57 if (*map) 58 return false; 59 } 60 } 61 } 62 63 for (pos = nbits / BITS_IN_SIZE_T; pos; pos--, map += sizeof(size_t)) { 64 if (*((size_t *)map)) 65 return false; 66 } 67 68 for (pos = (nbits % BITS_IN_SIZE_T) >> 3; pos; pos--, map++) { 69 if (*map) 70 return false; 71 } 72 73 pos = nbits & 7; 74 if (pos && (*map & fill_mask[pos])) 75 return false; 76 77 // All bits are zero 78 return true; 79 } 80 81 /* 82 * are_bits_set 83 * 84 * Returns 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 // All bits are ones 134 return true; 135 } 136