From 28e5b8a7ea6dc157e890e39b953c980898b5455e Mon Sep 17 00:00:00 2001
From: "rjones@intel.home.annexia.org" <rjones@intel.home.annexia.org>
Date: Tue, 13 May 2008 13:50:27 +0100
Subject: [PATCH] Implement offset_is_free for NTFS.

---
 lib/diskimage_ntfs.ml | 56 ++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 55 insertions(+), 1 deletion(-)

diff --git a/lib/diskimage_ntfs.ml b/lib/diskimage_ntfs.ml
index e4e9036..d0f2f49 100644
--- a/lib/diskimage_ntfs.ml
+++ b/lib/diskimage_ntfs.ml
@@ -540,7 +540,61 @@ and iter_blocks { ntfs_blocksize = blocksize; ntfs_dev = dev }
       in
       loop data_size runlist
 
-and offset_is_free _ _ = false
+(* 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 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 = byte >^> (~^0x80 >^> (Int63.to_int bitoffset)) in
+
+    bit <> ~^0
+  with
+    Not_found -> false			(* play it safe *)
 
 and callbacks =
   let i = ref 0 in
-- 
1.8.3.1