bitmap.odin (3448B)
1 package ntfs 2 3 import "core:math/bits" 4 import "core:mem" 5 6 /* 7 Count the volume's allocated clusters from $Bitmap, which holds one bit per cluster, 8 set meaning allocated. 9 10 This is the file system's own account of used space, arrived at without looking at any 11 file. Summing every file's run list should reproduce it almost exactly, so a large 12 divergence points at the run list decoding being wrong rather than at space having 13 gone missing. Files small enough to live inside their MFT record occupy no clusters 14 and so appear in neither figure; their bytes are counted under $MFT. 15 16 `mft` must be an extent reader over the MFT's own run list. `scratch` is reused for 17 the record read and then for the bitmap stream, so it must hold at least one record 18 and its length must be a whole number of clusters. 19 */ 20 @(private) 21 read_bitmap_clusters :: proc( 22 mft: ^Extent_Reader, 23 boot: Boot_Sector, 24 scratch: []byte, 25 allocator: mem.Allocator, 26 ) -> ( 27 clusters: u64, 28 err: Error, 29 ) { 30 record_size := int(boot.record_size) 31 cluster := u64(boot.bytes_per_cluster) 32 if len(scratch) < record_size || u64(len(scratch)) < cluster { 33 return 0, .Short_Read 34 } 35 36 rec := scratch[:record_size] 37 if read_err := read_logical(mft, u64(RECORD_BITMAP) * u64(record_size), rec); read_err != nil { 38 return 0, read_err 39 } 40 if fix_err := apply_fixups(rec); fix_err != nil { 41 return 0, fix_err 42 } 43 if .In_Use not_in record_header(rec).flags { 44 return 0, .Bad_Record 45 } 46 47 runs: []Run 48 data_size: u64 49 found := false 50 it := attributes(rec) 51 for { 52 a, ok := next_attribute(&it) 53 if !ok { 54 break 55 } 56 if a.type != .Data || len(a.name) != 0 || !a.non_resident || a.lowest_vcn != 0 { 57 continue 58 } 59 decoded, run_err := decode_runlist(a.runlist, 0, allocator) 60 if run_err != nil { 61 return 0, run_err 62 } 63 runs = decoded 64 data_size = a.data_size 65 found = true 66 break 67 } 68 if !found { 69 return 0, .Bad_Record 70 } 71 defer delete(runs, allocator) 72 73 // Bits past the last cluster are padding that NTFS leaves set, so stop counting at 74 // the volume's real cluster count instead of trusting the attribute length. 75 total := boot.total_sectors / u64(boot.sectors_per_cluster) 76 covered := runlist_clusters(runs) * cluster 77 want := (total + 7) / 8 78 limit := min(min(want, data_size), covered) 79 tail := uint(total % 8) 80 if limit < want { 81 tail = 0 // the last byte is out of reach, so there is nothing to mask 82 } 83 84 // Raw volume reads must cover whole sectors, so read whole clusters and count only 85 // the prefix that maps to real clusters. 86 read_limit := min((limit + cluster - 1) / cluster * cluster, covered) 87 88 br := Extent_Reader { 89 v = mft.v, 90 runs = runs, 91 cluster = cluster, 92 } 93 for offset: u64 = 0; offset < read_limit; { 94 n := int(min(u64(len(scratch)), read_limit - offset)) 95 if read_err := read_logical(&br, offset, scratch[:n]); read_err != nil { 96 return 0, read_err 97 } 98 if offset < limit { 99 countable := int(min(u64(n), limit - offset)) 100 if offset + u64(countable) == limit && tail != 0 { 101 scratch[countable - 1] &= byte(1 << tail) - 1 102 } 103 clusters += count_set_bits(scratch[:countable]) 104 } 105 offset += u64(n) 106 } 107 return clusters, .None 108 } 109 110 // Population count over a byte slice, eight bytes at a time. 111 @(private) 112 count_set_bits :: proc "contextless" (b: []byte) -> (n: u64) { 113 i := 0 114 for ; i + 8 <= len(b); i += 8 { 115 n += bits.count_ones((^u64)(raw_data(b[i:]))^) 116 } 117 for ; i < len(b); i += 1 { 118 n += u64(bits.count_ones(b[i])) 119 } 120 return 121 }