path: root/src/slices.c

#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;

	s = malloc(1*sizeof(slice_t));
	if (s!=NULL) {
		s->begin=begin;
		s->end=end;
		s->status=status;
		s->next=next;
	}	

	return s;
}

// 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 *slicesNewEmpty() {
	slices_t *ss = malloc(1*sizeof(slices_t));
	if (ss==NULL) {
		return NULL;
	}

	memset(ss, 0, sizeof(slices_t));
	return ss;
}

slices_t *slicesNewSingleton(address_t begin, address_t end, sliceStatus_t status) {
	slice_t *s=NULL;
	slices_t *ss = slicesNewEmpty();
	if (ss==NULL) {
		return NULL;
	}
	s=sliceNew(begin,end,status,NULL);
	if (s==NULL) {
		free(ss);
		return NULL;
	}
	slicesAppend(ss,s);

	return ss;
}

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) {
	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;
}

slice_t *slicesFindLargestFast(slices_t *slices, address_t *foundMax, sliceStatus_t status, address_t knownMax, slice_t *firstToTry) {
	slice_t *curr, *sMax = NULL;
	address_t i, iMax = 0;
	
	curr = firstToTry;
	while (curr != NULL) {
		i=curr->end - curr->begin + 1;
		if ( curr->status == status ) {
			if ( knownMax == i ) { *foundMax=i; return curr; }
			if ( i > iMax ) {
				iMax = i;
				sMax = curr;
			}
		}
		curr=curr->next;
	}
	curr = slices->first;
	while (curr != firstToTry) {
		i=curr->end - curr->begin + 1;
		if ( curr->status == status && i > iMax ) {
			iMax = i;
			sMax = curr;
		}
		curr=curr->next;
	}
	*foundMax=iMax;
	return sMax;
}

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,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 / *blockSize; //FIXME : gérer le max également !
/*
if ( curr->end / *blockSize > charCount -1 )  {
	printf("\nBUG : end/blkSze==%lli, charCount==%i\n", curr->end / *blockSize,charCount-1);
}
*/
		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;
}