+(* Parse $Bitmap::$Data to get free/used. Returns (used, free) blocks. *)
+and parse_bitmap_freespace ntfs =
+ (* Can throw Not_found - allow that to escape because we don't
+ * expect an NTFS filesystem without this magic file.
+ *)
+ let file = find_system_file ntfs "$Bitmap" in
+
+ (* Count used/free bits. *)
+ let used = ref ~^0 and free = ref ~^0 in
+ iter_blocks ntfs file (
+ fun lcn vcn data ->
+ for i = 0 to String.length data - 1 do
+ let c = Char.code data.[i] in
+ if c = 0 then (* common cases *)
+ free := !free +^ ~^8
+ else if c = 0xff then
+ used := !used +^ ~^8
+ else ( (* uncommon case: count the bits *)
+ let m = ref 0x80 in
+ while !m > 0 do
+ if c land !m <> 0 then
+ used := !used +^ ~^1
+ else
+ free := !free +^ ~^1;
+ m := !m lsr 1
+ done
+ )
+ done
+ );
+ (!used, !free)
+
+and find_system_file { ntfs_mft_records = mft_records } fname =
+ let rec loop =
+ function
+ | [] -> raise Not_found
+ | ({ ntfs_filename = Some { ntfs_name = name } } as file) :: _
+ when name = fname ->
+ file
+ | _ :: rest -> loop rest
+ in
+ loop mft_records
+
+and iter_blocks { ntfs_blocksize = blocksize; ntfs_dev = dev }
+ { ntfs_data = data } f =
+ match data with
+ | None -> () (* No $Data attribute. *)
+ | Some { ntfs_data_size = data_size; ntfs_runlist = runlist } ->
+ let rec loop data_size = function
+ | [] -> ()
+
+ (* Run of vcnsize clusters. *)
+ | ((vcnstart, vcnsize), Some lcn) :: rest ->
+ let data_size = ref data_size in
+ let lcn = ref lcn in
+ let vcn = ref vcnstart in
+ let vcnsize = ref vcnsize in
+ while !vcnsize > ~^0 && !data_size > ~^0 do
+ let size = min blocksize !data_size in
+ let data = dev#read (!lcn *^ blocksize) size in
+ f (Some !lcn) !vcn data;
+ lcn := !lcn +^ ~^1;
+ vcn := !vcn +^ ~^1;
+ vcnsize := !vcnsize -^ ~^1;
+ data_size := !data_size -^ size
+ done;
+ loop !data_size rest
+
+ (* Sparse hole. *)
+ | ((vcnstart, vcnsize), None) :: rest ->
+ let data_size = ref data_size in
+ let vcn = ref vcnstart in
+ let vcnsize = ref vcnsize in
+ while !vcnsize > ~^0 && !data_size > ~^0 do
+ let size = min blocksize !data_size in
+ let data = String.make (Int63.to_int size) '\000' in
+ f None !vcn data;
+ vcn := !vcn +^ ~^1;
+ vcnsize := !vcnsize -^ ~^1;
+ data_size := !data_size -^ size
+ done;
+ loop !data_size rest
+ in
+ loop data_size runlist
+
+(* This is a bit limited at the moment because it can only read from
+ * a contiguous part of the file. System files are usually contiguous
+ * so this is OK for us.
+ *)
+and read_file { ntfs_blocksize = blocksize; ntfs_dev = dev }
+ { ntfs_data = data } offset size =
+ match data with
+ | None -> raise Not_found (* No $Data attribute. *)
+ | Some { ntfs_data_size = data_size; ntfs_runlist = runlist } ->
+ if offset < ~^0 || size < ~^0 || offset +^ size >= data_size then
+ invalid_arg "ntfs: read_file: tried to read outside file";
+
+ (* Get the first and last VCNs containing the data. *)
+ let vcn = offset /^ blocksize in
+ let vcnoffset = offset %^ blocksize in
+ let vcnend = (offset +^ size -^ ~^1) /^ blocksize in
+
+ (* Find the run containing this VCN. *)
+ let rec find = function
+ | [] -> raise Not_found
+ | ((vcnstart, vcnsize), lcn) :: _
+ when vcnstart <= vcn && vcn < vcnstart +^ vcnsize &&
+ vcnstart <= vcnend && vcnend < vcnstart +^ vcnsize ->
+ lcn
+ | _ :: rest -> find rest
+ in
+ let lcn = find runlist in
+
+ (* Read the LCNs. *)
+ let data =
+ match lcn with
+ | Some lcn -> dev#read (lcn *^ blocksize +^ vcnoffset) size
+ | None -> String.make (Int63.to_int size) '\000' (* sparse hole *) in
+ data
+
+(* This is easy: just look at the bitmap. *)
+and offset_is_free fs offset =
+ try
+ let ntfs = get_private_data fs in
+ let blocksize = ntfs.ntfs_blocksize in
+
+ (* Get the $Bitmap file. *)
+ let file = find_system_file ntfs "$Bitmap" in
+
+ let lcn = offset /^ blocksize in
+
+ (* Read the byte in the bitmap corresponding to this LCN. *)
+ let byteoffset = lcn >^> 3 and bitoffset = lcn &^ ~^7 in
+ let byte = read_file ntfs file byteoffset ~^1 in
+ let byte = Char.code byte.[0] in
+ let bit = Int63.of_int byte >^> (0x80 lsr Int63.to_int bitoffset) in
+
+ bit <> ~^0
+ with
+ Not_found -> false (* play it safe *)