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 | |