runlist.odin (3370B)
1 package ntfs 2 3 // One contiguous extent of a non-resident attribute. 4 Run :: struct { 5 vcn: u64, // first virtual cluster (offset within the attribute, in clusters) 6 lcn: u64, // first logical cluster on the volume; meaningless when sparse 7 length: u64, // clusters 8 sparse: bool, // no clusters allocated; reads as zeros 9 } 10 11 /* 12 Decode NTFS "mapping pairs" into runs. 13 14 Each pair starts with a header byte: the low nibble is the byte width of the length 15 field, the high nibble the byte width of the LCN delta. Widths are variable so short 16 runs cost two or three bytes. The LCN is stored as a signed delta from the previous 17 run's LCN, which is why decoding is stateful. A zero-width delta means the run is 18 sparse. A zero header byte terminates the list. 19 20 `first_vcn` is the attribute's lowest_vcn; it is 0 for the first (or only) extent. 21 */ 22 decode_runlist :: proc( 23 b: []byte, 24 first_vcn: u64, 25 allocator := context.allocator, 26 ) -> ( 27 runs: []Run, 28 err: Error, 29 ) { 30 out := make([dynamic]Run, allocator) 31 vcn := first_vcn 32 lcn: i64 = 0 33 i := 0 34 for i < len(b) { 35 h := b[i] 36 i += 1 37 if h == 0 { 38 break 39 } 40 len_size := int(h & 0xF) 41 ofs_size := int(h >> 4) 42 if len_size == 0 || len_size > 8 || ofs_size > 8 || i + len_size + ofs_size > len(b) { 43 delete(out) 44 return nil, .Bad_Runlist 45 } 46 length := read_uint_le(b[i:i + len_size]) 47 i += len_size 48 if length == 0 { 49 delete(out) 50 return nil, .Bad_Runlist 51 } 52 run := Run { 53 vcn = vcn, 54 length = length, 55 } 56 if ofs_size == 0 { 57 run.sparse = true 58 } else { 59 lcn += read_int_le(b[i:i + ofs_size]) 60 i += ofs_size 61 if lcn < 0 { 62 delete(out) 63 return nil, .Bad_Runlist 64 } 65 run.lcn = u64(lcn) 66 } 67 append(&out, run) 68 vcn += length 69 } 70 // The caller frees the result as a plain slice, so its length must equal the 71 // allocation. Trim the dynamic array's spare capacity before handing it over. 72 shrink(&out) 73 return out[:], .None 74 } 75 76 /* 77 Count the clusters a run list actually allocates, skipping sparse runs, without 78 building the run array. This is the ground truth for disk usage: allocated_size in 79 the attribute header is logical for compressed and sparse attributes, and some system 80 files ($BadClus:$Bad, which spans the whole volume) have entirely unallocated run 81 lists with no sparse flag at all. 82 */ 83 runlist_allocated_clusters :: proc "contextless" (b: []byte) -> (clusters: u64, ok: bool) { 84 i := 0 85 for i < len(b) { 86 h := b[i] 87 i += 1 88 if h == 0 { 89 return clusters, true 90 } 91 len_size := int(h & 0xF) 92 ofs_size := int(h >> 4) 93 if len_size == 0 || len_size > 8 || ofs_size > 8 || i + len_size + ofs_size > len(b) { 94 return 0, false 95 } 96 length := read_uint_le(b[i:i + len_size]) 97 i += len_size + ofs_size 98 if ofs_size != 0 { 99 clusters += length 100 } 101 } 102 return clusters, true 103 } 104 105 // Total clusters covered by a run list, including sparse runs. 106 runlist_clusters :: proc(runs: []Run) -> u64 { 107 total: u64 108 for r in runs { 109 total += r.length 110 } 111 return total 112 } 113 114 @(private) 115 read_uint_le :: proc "contextless" (b: []byte) -> u64 { 116 v: u64 117 for x, k in b { 118 v |= u64(x) << (8 * uint(k)) 119 } 120 return v 121 } 122 123 // Sign-extends a little-endian integer of 1 to 8 bytes. 124 @(private) 125 read_int_le :: proc "contextless" (b: []byte) -> i64 { 126 v := read_uint_le(b) 127 bits := uint(len(b)) * 8 128 if bits < 64 && v & (u64(1) << (bits - 1)) != 0 { 129 v |= ~u64(0) << bits 130 } 131 return i64(v) 132 }