5 files changed, 235 insertions, 42 deletions

diff --git a/src/ddhardrescue.c b/src/ddhardrescue.c
index 56cc5bf..a99b9d8 100755
--- a/src/ddhardrescue.c
+++ b/src/ddhardrescue.c
@@ -6,30 +6,53 @@
 #include "recover.h"
 
 int end=0;
+unsigned long c=0;
 
 void sigHookAbrt() {
 	end=1;
 }
 
 int main() {
-	char *src, *dst, *ddOpts;
-	address_t beginSector, endSector;
-	int depth;
+	char *src, *dst, *ddOpts, *dump;
+	address_t beginSector, endSector, blockSize;
+	int /*depth,*/i;
 	slices_t *slices;
+	slice_t *curr, *toFree;
 	
 	//TODO Parse args
 	src="/dev/sdb";
 	dst="./test.img";
 	ddOpts="";
 	beginSector=0;
-	endSector=100;
-	depth=10;
-
+	endSector=19999;
+//	depth=1;
+/*
+	endSector=1999999999;
+	depth=100000;
+*/
 	//TODO signal...
 
-	slices=recover(src,dst,ddOpts,beginSector,endSector,depth);
+	slices=recover(src,dst,ddOpts,beginSector,endSector/*,depth*/);
 	
-	//TODO final reporting
+	blockSize=0;
+	dump=slicesDump(slices, &blockSize, 1000, beginSector, endSector);
+	puts(dump);
+	free(dump);
+	printf("blockSize==%ld\n", blockSize);
+	printf("c==%ld\n", c);
+	printf("slices->count==%d\n", slices->count);
+
+	curr=slices->first;
+	i=0;
+	while (curr!=NULL) {
+		i++;
+		toFree=curr;
+		curr=curr->next;
+		free(toFree);
+	}
+	free(slices);
+
+	printf("i==%d\n", i);
 
 	return 0;
 }
diff --git a/src/recover.c b/src/recover.c
index c2c2eff..0f305a1 100755
--- a/src/recover.c
+++ b/src/recover.c
@@ -1,7 +1,10 @@
 #include <errno.h>
+#include <stdio.h>
 #include "recover.h"
 
-slices_t *recover(char *src, char *dst, char*ddOpts, address_t beginSector, address_t endSector, int depth) {
+extern unsigned long c;
+
+slices_t *recover(char *src, char *dst, char*ddOpts, address_t beginSector, address_t endSector/*, int depth*/) {
 	slices_t *slices;
 	slice_t *sliceToRead;
 	address_t firstError=0, median;
@@ -16,17 +19,21 @@ slices_t *recover(char *src, char *dst, char*ddOpts, address_t beginSector, addr
 	slicesAppend(slices, sliceToRead);
 	
 	// Main loop 
-	while (!end && slices->count < (endSector-beginSector)/depth) {
+	while (!end) { // && slices->count < (endSector-beginSector)/depth) {
 		// try to recover sliceToRead and split it if read error
-		switch ( tryRecoverUntilError(sliceToRead, &firstError) ) {
+		switch ( tryRecoverUntilError(sliceToRead, &firstError, src, dst, ddOpts) ) {
 			case 0:
 				// slice recovery has been executed without read error
 				sliceToRead->status=S_RECOVERED;
 				break;
 			case EIO:
-				// slice recovery has encuontered a readerror
-				res=sliceSplit(sliceToRead, firstError, S_RECOVERED, S_UNREADABLE, S_UNKNOWN);
-				if (res!=0) { exit(5); } //TODO
+				// slice recovery has encountered a readerror
+				res=sliceSplit(slices, sliceToRead, firstError, S_RECOVERED, S_UNREADABLE, S_UNKNOWN);
+				if (res<1) {
+					//TODO
+					printf("sliceSplit return %d\n", res);
+					exit(5);
+				}
 				break;
 			default:
 				exit(2); //TODO
@@ -35,34 +42,84 @@ slices_t *recover(char *src, char *dst, char*ddOpts, address_t beginSector, addr
 		/* Now, search the largest S_UNKNOWN zone
 		 split it in two parts */
 		sliceToRead=slicesFindLargest(slices, S_UNKNOWN);
-		if ( sliceToRead == NULL ) { exit(3); } //TODO 
+		if ( sliceToRead == NULL ) {
+			// There is nothing more to recover, bailout
+			end=1;
+			continue;
+		}
+			
 
  		median=(sliceToRead->begin+sliceToRead->end)/2;
-		res=sliceSplit(sliceToRead, median, S_UNKNOWN, S_UNKNOWN, S_UNKNOWN);
-		if (res!=0) { exit(4); } //TODO
-
-		/* After splitting an S_UNKNOWN zone in two parts
-		   take the second for further analysis.
-		   We already now that this first one is just preceded by
-		   a read error, and errors are frequently grouped in zones,
-		   so trying to read a sector just after a faulty sector is
-		   most likely a waste of time.
-		*/
-		sliceToRead=sliceToRead->next; 
+		res=sliceSplit(slices, sliceToRead, median, S_UNKNOWN, S_UNKNOWN, S_UNKNOWN);
+		switch (res) {
+			case 1:
+				// No split, try analyse this zone
+				// Should be a slice of length 1
+				break;
+			case 2:
+				/* After splitting an S_UNKNOWN zone in two parts
+				   take the second for further analysis.
+				   We already now that this first one is just preceded by
+				   a read error, and errors are frequently grouped in zones,
+				   so trying to read a sector just after a faulty sector is
+				   most likely a waste of time.
+				*/
+				sliceToRead=sliceToRead->next; 
+				break;
+			case 3:
+				// Internal error of sliceSlpit because this set of parameters prevent split by 3
+				exit(5); // TODO
+				break;
+			case -1:
+				// Memory error
+				exit(4); //TODO
+				break;
+			default:
+				// API error, all necessary cases are already listed
+				exit(6); // TODO
+			}
 	}
 	return slices;
 }
 
-int tryRecoverUntilError(slice_t *sliceToRead, address_t *firstError) {
+int tryRecoverUntilError(slice_t *sliceToRead, address_t *firstError, char *src, char *dst, char*ddOpts) {
 	//TODO : implement realy that
+	char ddinvocation[256];
 	int res;
+	address_t seek, count;
+
+	c++; //XXX This is a debug counter
 
+	seek=sliceToRead->begin;
+	count=sliceToRead->end - seek + 1;
+	res=snprintf(ddinvocation, 255, "dd %s %s %s seek=%ld skip=%ld count=%ld", src, dst, ddOpts, seek, seek, count);
+	puts(ddinvocation);
+
+	// Simulate that we have systematically a read error at first sector
+	*firstError=sliceToRead->begin;
+	res=EIO;
+
+/*
+	// Simulate for each read, tha we have an error just in the middle if read for mor than one sector
 	if ( sliceToRead->begin == sliceToRead->end ) {
 		res=0;
 	} else {
 		*firstError=(sliceToRead->begin + sliceToRead->end)/2;
 		res=EIO;
 	}
+*/
+
+/*
+	// Simulate for each read a pseudo random error position and generate some cases of full read without error
+	int error=sliceToRead->begin + rand()%count;
+	if ( error % 42 == 0 ) {
+		res=0;
+	} else {
+		res=EIO;
+		*firstError=error;
+	}
+*/
+
 	return res;
 }
 
diff --git a/src/recover.h b/src/recover.h
index d8b1409..84c7286 100755
--- a/src/recover.h
+++ b/src/recover.h
@@ -5,7 +5,7 @@
 
 extern int end;
 
-slices_t *recover(char *src, char *dst, char*ddOpts, address_t beginSector, address_t endSector, int depth);
-int tryRecoverUntilError(slice_t *sliceToRead, address_t *firstError);
+slices_t *recover(char *src, char *dst, char*ddOpts, address_t beginSector, address_t endSector/*, int depth*/);
+int tryRecoverUntilError(slice_t *sliceToRead, address_t *firstError, char *src, char *dst, char*ddOpts);
 
 #endif /*RECOVER_H*/
diff --git a/src/slices.c b/src/slices.c
index edae571..8e9aee6 100755
--- a/src/slices.c
+++ b/src/slices.c
@@ -1,8 +1,12 @@
 #include <string.h>
 #include "slices.h"
 
+int min(int a, int b) { return (a<b)?a:b; }
+
 slice_t *sliceNew(address_t begin, address_t end, sliceStatus_t status, slice_t *next) {
-	slice_t *s = malloc(1*sizeof(slice_t));
+	slice_t *s;
+
+	s = malloc(1*sizeof(slice_t));
 	if (s!=NULL) {
 		s->begin=begin;
 		s->end=end;
@@ -13,8 +17,62 @@ slice_t *sliceNew(address_t begin, address_t end, sliceStatus_t status, slice_t
 	return s;
 }
 
-int sliceSplit(slice_t *slice, address_t splitAt, sliceStatus_t statusBefore, sliceStatus_t statusAt, sliceStatus_t statusAfter) {
-	return 1;
+// Return the numbers of slices after split (3 in the general case, 2 or 1 in particular cases. -1 is memory error)
+int sliceSplit(slices_t *slices, slice_t *initialSlice, address_t splitAt, sliceStatus_t statusBefore, sliceStatus_t statusAt, sliceStatus_t statusAfter) {
+	slice_t *secondSlice, *thirdSlice, *rightSlice;
+	int splitAfterSingularity, splitBeforeSingularity;
+
+	/* Basically, we want to split the slice in 3 :
+	[a;b] shoud be transformed in : [a;splitAt-1], [splitAt;splitAt], [splitAt+1;b]
+	There is exceptions and singularities :
+	* If splitAt is not within [a;b], bail out, no coherent solution
+	* If splitAt==a, the first slice should not exists
+	* If splitAt==b, the last slice shoud not exists
+	* If a==b (and so, ==splitAt), there is nothing to split, just change status
+	But, if statusBefore==statusAt, we don't want an interval [splitAt;splitAt], we want just split in 2.
+	This unwanted interval should be kept merged with the first interval.
+
+	For pratical reasons with pointer mess-up, the first action is to split between the second and the last slice
+	and then between he first and second if needed.
+	*/
+
+	if ( splitAt < initialSlice->begin || splitAt > initialSlice->end ) return 2;
+	
+	// Test before act because we'll change values of the initialSlice because
+	//  it would become the firstSlice or even the second one if the first is zero-lenght
+	splitAfterSingularity=(splitAt != initialSlice->end);
+	splitBeforeSingularity=(splitAt != initialSlice->begin) && (statusBefore != statusAt);
+
+	if ( splitAfterSingularity ) {
+		thirdSlice = sliceNew(splitAt+1, initialSlice->end, statusAfter, initialSlice->next);
+		if ( thirdSlice == NULL ) return -1;
+
+		initialSlice->end = splitAt;
+		// No status change because we'll split again in 2 parts or not
+		initialSlice->next = thirdSlice;
+		if ( initialSlice == slices->last ) slices->last = thirdSlice;
+		(slices->count)++;
+
+		rightSlice=thirdSlice;
+	} else {
+		rightSlice=initialSlice->next;
+	}
+
+	if ( splitBeforeSingularity ) {
+		secondSlice = sliceNew(splitAt, splitAt, statusAt, rightSlice);
+		if ( secondSlice == NULL ) return -1;
+		
+		initialSlice->end = splitAt-1;
+		initialSlice->status=statusBefore;
+		initialSlice->next = secondSlice;
+		if ( initialSlice == slices->last ) slices->last = secondSlice;
+		(slices->count)++;
+	} else {
+		initialSlice->status=statusAt; // Two cases : a==splitAt or statusAt==statusBefore
+	}
+
+	
+	return 1 + (splitBeforeSingularity?1:0) + (splitAfterSingularity?1:0);
 }
 
 slices_t *slicesNew() {
@@ -29,25 +87,75 @@ slices_t *slicesNew() {
 }
 
 void slicesAppend(slices_t *slices, slice_t *slice) {
-
+	slice->next=NULL; //XXX Could be generalized
+	if (slices->first==NULL || slices->last==NULL) {
+		slices->first = slice;
+	} else {
+		slices->last->next=slice;
+	}
+	slices->last=slice;
+	(slices->count)++;
 }
 
 slice_t *slicesFindLargest(slices_t *slices, sliceStatus_t status) {
-	return NULL;
+	slice_t *curr, *sMax = NULL;
+	address_t i, iMax = 0;
+	
+	curr = slices->first;
+	while (curr != NULL) {
+		i=curr->end - curr->begin + 1;
+		if ( curr->status == status && i > iMax ) {
+			iMax = i;
+			sMax = curr;
+		}
+		curr=curr->next;
+	}
+	return sMax;
 }
 
-char *slicesDump(slices_t *slices, int charCount, address_t begin, address_t end) {
+char *slicesDump(slices_t *slices, address_t *blockSize, unsigned int charCount, address_t begin, address_t end) {
 	slice_t *curr = slices->first;
-	address_t sb,se, blockSize=(end-begin)/(charCount+1);
-	char *dump=malloc(1*charCount+1);
+	unsigned int sb,se,i;
+	char *dump, ci;
+
+	// If blockSize is 0, try to autodetect to display entire slice chain
+	if (*blockSize == 0) {
+		*blockSize=(end-begin+1)/(charCount+1);
+		// If we have a too big zoom factor, draw it at 1:1 scale
+		if (*blockSize==0) *blockSize=1;
+	}
+
+	dump = malloc(charCount+1);
+	if (dump==NULL) { return NULL; }
 	memset(dump, ' ', charCount);
+	dump[charCount]=0;
 
 	while (curr != NULL) {
-		sb=curr->begin;
-		// TODO : boucle pour dessiner les caractères correspondant selon le type de zone. Attention aux cas ou 1 caractère contient la frontière de plusieurs zones (ne pas toujours écraser avec la dernière valeur)
+		sb=curr->begin / *blockSize; //FIXME : gérer le max également !
+		se=min(curr->end / *blockSize,charCount-1);
+
+		switch (curr->status) {
+			case S_UNKNOWN:		ci='_'; break;
+			case S_UNREADABLE:	ci='!'; break;
+			case S_RECOVERED:	ci='.'; break;
+			default:		ci='~'; break;
+		}
+
+		for (i=sb;i<=se;i++) {
+			if (dump[i] == ' ' ) {
+				// This is a new information
+				dump[i]=ci;
+			} else if ( dump[i] == ci || dump[i] == '!' ) {
+				// Already the right information or error, don't modify
+			} else {
+				// Multiple information on the same character
+				dump[i]='#';
+			}
+		}
 
 		curr=curr->next;
 	}
 
 	return dump;
 }
+
diff --git a/src/slices.h b/src/slices.h
index 062c4f4..9f97246 100755
--- a/src/slices.h
+++ b/src/slices.h
@@ -4,8 +4,13 @@
 #include <stdint.h>
 #include <stdlib.h>
 
+/* IMPORTANT NOTES
+Slice are inclusive intervals. Let say sliceNew(1,2,S_UNKNOWN,NULL) return a [1;2] interval,
+ so interval lenght is end-begin+1. Here, it is 2 sectors lenght slice.
+*/
+
 typedef enum { S_UNKNOWN, S_RECOVERED, S_UNREADABLE } sliceStatus_t;
-typedef uint32_t address_t;
+typedef unsigned long int address_t;
 
 typedef struct _slice {
 	uint32_t begin, end;
@@ -19,11 +24,11 @@ typedef struct {
 } slices_t;
 
 slice_t *sliceNew(address_t begin, address_t end, sliceStatus_t status, slice_t *next);
-int sliceSplit(slice_t *slice, address_t splitAt, sliceStatus_t statusBefore, sliceStatus_t statusAt, sliceStatus_t statusAfter); 
+int sliceSplit(slices_t *slices, slice_t *initialSlice, address_t splitAt, sliceStatus_t statusBefore, sliceStatus_t statusAt, sliceStatus_t statusAfter);
 
 slices_t *slicesNew();
 void slicesAppend(slices_t *slices, slice_t *slice);
 slice_t *slicesFindLargest(slices_t *slices, sliceStatus_t status);
-char *slicesDump(slices_t *slices, int charCount, address_t begin, address_t end);
+char *slicesDump(slices_t *slices, address_t *blockSize, unsigned int charCount, address_t begin, address_t end);
 
 #endif /*SLICES_H*/