/***********************************************************************\
*                             bitarrayfix.d                             *
*                                                                       *
*     Functions to implement bit array slicing, slice assignment and    *
*                 concatenation, with unit test program                 *
*                                                                       *
*                           by Stewart Gordon                           *
*                                May 2004                               *
\***********************************************************************/
// imports used only in unit tests and debugging code
import std.c.stdio;
import std.random;

extern (C) void* memcpy(void*, void*, uint);


void writeBits(bit[] data) {
	foreach (int i, bit b; data) {

		putchar(b ? '1' : '0');
		if ((i & 7) == 7) putchar(' ');
	}
	putchar('\n');
}


int main() {
	bit[56] data1, data2;

	rand_seed(0, 0);

	for (int b = 0; b < data1.length; b++) {
		data1[b] = cast(bit) (rand() % 2);
	}

	writeBits(data1);
	writeBits(data2);

	// test case of byte alignments match

	// no byte-aligned boundaries
	// data2[11..31] = data1[3..23];
	copyBits(data1, 3, 23, data2, 11, 31);

	writeBits(data1);
	writeBits(data2);

	// begin on byte
	copyBits(data2, 8, 19, data1, 24, 35);

	writeBits(data1);
	writeBits(data2);

	// end on byte
	copyBits(data1, 39, 48, data2, 31, 40);

	writeBits(data1);
	writeBits(data2);

	// copy part of a byte
	copyBits(data2, 25, 30, data1, 41, 46);

	writeBits(data1);
	writeBits(data2);

	// test general case
	copyBits(data1, 12, 24, data2, 16, 28);

	writeBits(data1);
	writeBits(data2);

	// test slice extraction


	// beginning slice
	// writeBits(data1[0..25]);
	writeBits(sliceBits(data1, 0, 25));
	// byte-aligned slice
	writeBits(sliceBits(data2, 8, 23));
	// general case
	writeBits(sliceBits(data1, 27, 31));

	/+ +++ Error cases +++
	copyBits(data1, 12, 24, data2, 20, 40);	// size mismatch
	copyBits(data1, 35, 60, data2, 25, 50);	// out of bounds
	copyBits(data2, 20, 15, data1, 21, 16);	// negative length
	sliceBits(data1, 0, 57);				// out of bounds
	+/

	// test concatenation

	bit[] data3 = sliceBits(data1, 25, 31);
	// writeBits(data3 ~ data2[11..13]);
	writeBits(concatBits(data3, sliceBits(data2, 11, 13)));
	// data3 ~= data1;

	appendBits(data3, data1);
	writeBits(data3);

	data3.length = 12;
	// data3 ~= 1;
	appendBits(data3, 1);
	appendBits(data3, 0);
	appendBits(data3, 1);
	appendBits(data3, 0);
	appendBits(data3, 0);

	writeBits(data3);

	return 0;
}


// End of unit test code.  The actual implementation code starts here.

/*	I created this alias with a view to experimenting with different sizes of
 *	block to consider at a time; either ubyte, ushort, uint or ulong would work.
 *	ubyte is best for detecting and dealing with the optimised case of matching
 *	unit alignments, since it is most general.  Because it uses memcpy, there is
 *	no performance hit in the bulk.
 *	However, in order to optimise the general (not byte-aligned) case, memcpy
 *	cannot be used.  It would therefore be better to have a larger unit to
 *	reduce the number of shift and assign operations.  When an optimised
 *	algorithm is written for this, a separate alias should be created.
 */
private alias ubyte UNIT;
private const int UBITS = UNIT.size * 8;


/*	Copy bit slices.
 *	Implementation of to[toStart..toEnd] = from[fromStart..fromEnd]
 *	Limitations:
 *		doesn't detect overlap
 *		general case not optimised
 *		want specific errors rather than plain old asserts
 */
bit[] copyBits(bit[] from, int fromStart, int fromEnd,
	  bit[] to, int toStart, int toEnd)
in {
	assert (fromStart >= 0);
	assert (fromEnd >= fromStart);
	assert (fromEnd <= from.length);
	assert (toStart >= 0);
	assert (toEnd - toStart == fromEnd - fromStart);
	assert (toEnd <= to.length);

	debug {
		printf("Copying %d..%d to %d..%d\n",
		  fromStart, fromEnd, toStart, toEnd);
	}
}
out (result) {
	assert (result == to);

	if (toEnd != toStart) {
		int oFromStart = fromEnd - toEnd + toStart;
		assert (to[toStart] == from[oFromStart]);
		assert (to[toEnd - 1] == from[fromEnd - 1]);
	}
}
body {
	int length;

	/*	functions to generate bit masks
	 *	(only used once at present, but would be likely be adapted and reused to
	 *	optimise the general case)
	 */
	version (LittleEndian) {
		UNIT unitMask() {
			// ...EDC.., hgfedcba -> hgfEDCba
			return (UNIT.max >>> (UBITS - toEnd % UBITS))
				  << (toStart % UBITS);
		}

		UNIT startMask() {
			// HGF....., hgfedcba -> HGFedcba
			int shift = toStart % UBITS;
			toStart += UBITS - shift;
			fromStart += UBITS - shift;
			return UNIT.max << shift;
		}

		UNIT endMask() {
			// .....CBA, hgfedcba -> hgfedCBA
			return UNIT.max << (length % UBITS);
		}

	} else {	// big endian
		UNIT unitMask() {
			// ..CDE..., abcdefgh -> abCDEfgh
			return (UNIT.max >>> (fromStart % UBITS))
				  << (UBITS - fromEnd % UBITS);
		}

		UNIT startMask() {
			// .....FGH, abcdefgh -> abcdeFGH
			int shift = toStart % UBITS;
			toStart += UBITS - shift;
			fromStart += UBITS - shift;
			return UNIT.max >>> shift;
		}

		UNIT endMask() {
			// ABC....., abcdefgh -> ABCdefgh
			return UNIT.max >>> (length % UBITS);
		}
	}

	// special case: nothing to do
	if (fromStart == fromEnd) return to;

	// point to first unit to transfer
	UNIT* fromUnits = cast(UNIT*) from + fromStart / UBITS;
	UNIT* toUnits = cast(UNIT*) to + toStart / UBITS;

	// special case: unit alignments match
	if (fromStart % UBITS == toStart % UBITS) {

		// special subcase: all within a unit
		if (fromStart / UBITS == fromEnd / UBITS) {
			UNIT mask = unitMask();

			*toUnits = (*toUnits & ~mask) | (*fromUnits & mask);
			return to;
		}

		if (fromStart % UBITS != 0) {
			// transfer partial first unit
			UNIT mask = startMask();

			/*
			from	HGF.....
			to		hgfedcba
			mask	11100000
			~mask	00011111
			*/
			*toUnits = (*toUnits & ~mask) | (*fromUnits & mask);

			// done beginning bits
			fromUnits++;
			toUnits++;
		}

		// transfer the bulk of the slice
		length = fromEnd - fromStart;
		int wholeUnits = length / UBITS;

		memcpy(toUnits, fromUnits, wholeUnits * UNIT.size);
		fromUnits += wholeUnits;
		toUnits += wholeUnits;

		if (length % UBITS != 0) {
			// transfer partial last unit
			UNIT mask = endMask();

			/*
			from	.....CBA
			to		hgfedcba
			mask	11111000
			~mask	00000111
			*/
			*toUnits = (*toUnits & mask) | (*fromUnits & ~mask);
		}

		return to;
	}

	// general case (unoptimised)
	for (int toIndex = toStart, fromIndex = fromStart;
		  toIndex < toEnd; toIndex++, fromIndex++) {
		to[toIndex] = from[fromIndex];
	}

	return to;
}


/*	Slice a bit array.
 *	Implementation of ba[start..end]
 */
bit[] sliceBits(bit[] ba, int start, int end)
in {
	assert (start >= 0);
	assert (end >= start);
	assert (end <= ba.length);
}
out (result) {
	assert (result.length == end - start);
	if (end != start) {
		assert (result[0] == ba[start]);
		assert (result[end - start - 1] == ba[end - 1]);
	}
}
body {
	int length = end - start;

	// special case: empty slice
	if (length == 0) return null;

	bit[] result;

	// special case: starts at beginning
	if (start == 0) {
		result = ba;
		result.length = length;
		return result;
	}

	// general case
	result.length = length;
	copyBits(ba, start, end, result, 0, length);

	return result;
}


/*	Concatenate bit arrays (probably already implemented like this anyway)
 *	Implementation of first ~ second
 */
bit[] concatBits(bit[] first, bit[] second) {
	bit[] result = first;

	result.length = first.length + second.length;
	copyBits(second, 0, second.length, result, first.length, result.length);
	return result;
}


/*	Append one bit array to another
 *	(probably already implemented like this anyway)
 *	Implementation of first ~= second
 */
bit[] appendBits(inout bit[] first, bit[] second) {
	first = concatBits(first, second);
	return first;
}


/*	Append a single bit to a bit array
 *	Implementation of first ~= second
 */
bit[] appendBits(inout bit[] first, bit second) {
	first.length = first.length + 1;
	first[first.length - 1] = second;
	return first;
}