path: root/test/backupdiff/difftestfiles.cpp

// --------------------------------------------------------------------------
//
// File
//		Name:    createtestfiles.cpp
//		Purpose: Create the test files for the backupdiff test
//		Created: 12/1/04
//
// --------------------------------------------------------------------------

#include "Box.h"

#include <string.h>
#include <stdio.h>

#include "FileStream.h"
#include "PartialReadStream.h"
#include "Test.h"
#include "RollingChecksum.h"

#include "MemLeakFindOn.h"

#define ACT_END		0
#define ACT_COPY	1
#define	ACT_NEW		2
#define	ACT_SKIP	3
#define ACT_COPYEND	4

typedef struct
{
	int action, length, seed;
} gen_action;

#define INITIAL_FILE_LENGTH (128*1024 + 342)


gen_action file1actions[] = {
	{ACT_COPYEND, 0, 0},
	{ACT_END, 0, 0} };

gen_action file2actions[] = {
	{ACT_COPY, 16*1024, 0},
	// Do blocks on block boundaries, but swapped around a little
	{ACT_SKIP, 4*1024, 0},
	{ACT_COPY, 8*1024, 0},
	{ACT_SKIP, -12*1024, 0},
	{ACT_COPY, 4*1024, 0},
	{ACT_SKIP, 8*1024, 0},
	// Get rest of file with some new data inserted
	{ACT_COPY, 37*1024 + 12, 0},
	{ACT_NEW, 23*1024 + 129, 23990},
	{ACT_COPYEND, 0, 0},
	{ACT_END, 0, 0} };

gen_action file3actions[] = {
	{ACT_COPY, 12*1024 + 983, 0},
	{ACT_SKIP, 37*1024 + 12, 0},
	{ACT_COPYEND, 0, 0},
	{ACT_END, 0, 0} };

gen_action file4actions[] = {
	{ACT_COPY, 20*1024 + 2385, 0},
	{ACT_NEW, 12, 2334},
	{ACT_COPY, 16*1024 + 385, 0},
	{ACT_SKIP, 9*1024 + 42, 0},
	{ACT_COPYEND, 0, 0},
	{ACT_END, 0, 0} };

// insert 1 byte a block into the file, between two other blocks
gen_action file5actions[] = {
	{ACT_COPY, 4*1024, 0},
	{ACT_NEW, 1, 2334},
	{ACT_COPYEND, 0, 0},
	{ACT_END, 0, 0} };

gen_action file6actions[] = {
	{ACT_NEW, 6*1024, 12353452},
	{ACT_COPYEND, 0, 0},
	{ACT_END, 0, 0} };

// but delete that one byte block, it's annoying
gen_action file7actions[] = {
	{ACT_COPY, 10*1024, 0},
	{ACT_SKIP, 1, 0},
	{ACT_COPYEND, 0, 0},
	{ACT_NEW, 7*1024, 1235352},
	{ACT_END, 0, 0} };

gen_action file8actions[] = {
	{ACT_NEW, 54*1024 + 9, 125352},
	{ACT_END, 0, 0} };

gen_action file9actions[] = {
	{ACT_END, 0, 0} };

gen_action *testfiles[] = {file1actions, file2actions, file3actions, file4actions,
	file5actions, file6actions, file7actions, file8actions, file9actions, 0};


// Nice random data for testing written files
class R250 {
public:
	// Set up internal state table with 32-bit random numbers.  
	// The bizarre bit-twiddling is because rand() returns 16 bits of which
	// the bottom bit is always zero!  Hence, I use only some of the bits.
	// You might want to do something better than this....

	R250(int seed) : posn1(0), posn2(103)
	{
		// populate the state and incr tables
		srand(seed);

		for (int i = 0; i != stateLen; ++i)	{
			state[i] = ((rand() >> 2) << 19) ^ ((rand() >> 2) << 11) ^ (rand() >> 2);
			incrTable[i] = i == stateLen - 1 ? 0 : i + 1;
		}

		// stir up the numbers to ensure they're random

		for (int j = 0; j != stateLen * 4; ++j)			
			(void) next();
	}

	// Returns the next random number.  Xor together two elements separated
	// by 103 mod 250, replacing the first element with the result.  Then
	// increment the two indices mod 250.
	inline int next()
	{
		int ret = (state[posn1] ^= state[posn2]);	// xor and replace element

		posn1 = incrTable[posn1];		// increment indices using lookup table
		posn2 = incrTable[posn2];

		return ret;
	}
private:
	enum { stateLen = 250 };	// length of the state table
	int state[stateLen];		// holds the random number state
	int incrTable[stateLen];	// lookup table: maps i to (i+1) % stateLen
	int posn1, posn2;			// indices into the state table
};

void make_random_data(void *buffer, int size, int seed)
{
	R250 rand(seed);

	int n = size / sizeof(int);
	int *b = (int*)buffer;
	for(int l = 0; l < n; ++l)
	{
		b[l] = rand.next();
	}
}

void write_test_data(IOStream &rstream, int size, int seed)
{
	R250 rand(seed);
	
	while(size > 0)
	{
		// make a nice buffer of data
		int buffer[2048/sizeof(int)];
		for(unsigned int l = 0; l < (sizeof(buffer) / sizeof(int)); ++l)
		{
			buffer[l] = rand.next();
		}
		
		// Write out...
		unsigned int w = size;
		if(w > sizeof(buffer)) w = sizeof(buffer);
		rstream.Write(buffer, w);
		
		size -= w;
	}	
}

void gen_varient(IOStream &out, char *sourcename, gen_action *pact)
{
	// Open source
	FileStream source(sourcename);
	
	while(true)
	{
		switch(pact->action)
		{
		case ACT_END:
			{
				// all done
				return;
			}
		case ACT_COPY:
			{
				PartialReadStream copy(source, pact->length);
				copy.CopyStreamTo(out);
				break;
			}
		case ACT_NEW:
			{
				write_test_data(out, pact->length, pact->seed);
				break;
			}
		case ACT_SKIP:
			{
				source.Seek(pact->length, IOStream::SeekType_Relative);
				break;
			}
		case ACT_COPYEND:
			{
				source.CopyStreamTo(out);
				break;
			}
		}
	
		++pact;
	}
}

void create_test_files()
{
	// First, the keys for the crypto
	{
		FileStream keys("testfiles/backup.keys", O_WRONLY | O_CREAT);
		write_test_data(keys, 1024, 237);
	}
	
	// Create the initial file -- needs various special properties...
	// 1) Two blocks much be the different, but have the same weak checksum
	// 2) A block must exist twice, but at an offset which isn't a multiple of the block size.
	{
		FileStream f0("testfiles/f0", O_WRONLY | O_CREAT);
		// Write first bit.
		write_test_data(f0, (16*1024), 20012);
		// Now repeated checksum blocks
		uint8_t blk[4096];
		make_random_data(blk, sizeof(blk), 12201);
		// Three magic numbers which make the checksum work: Use this perl to find them:
		/*
			for($z = 1; $z < 4096; $z++)
			{
				for($n = 0; $n <= 255; $n++)
				{
					for($m = 0; $m <= 255; $m++)
					{
						if($n != $m && (($n*4096 + $m*(4096-$z)) % (64*1024) == ($n*(4096-$z) + $m*4096) % (64*1024)))
						{
							print "$z: $n $m\n";
						}
					}
				}
			}
		*/
		blk[0] = 255;
		blk[1024] = 191;
		// Checksum to check
		RollingChecksum c1(blk, sizeof(blk));
		// Write
		f0.Write(blk, sizeof(blk));
		// Adjust block and write again
		uint8_t blk2[4096];
		memcpy(blk2, blk, sizeof(blk2));
		blk2[1024] = 255;
		blk2[0] = 191;
		TEST_THAT(::memcmp(blk2, blk, sizeof(blk)) != 0);
		RollingChecksum c2(blk2, sizeof(blk2));
		f0.Write(blk2, sizeof(blk2));
		// Check checksums
		TEST_THAT(c1.GetChecksum() == c2.GetChecksum());
		
		// Another 4k block
		write_test_data(f0, (4*1024), 99209);
		// Offset block
		make_random_data(blk, 2048, 1234199);
		f0.Write(blk, 2048);
		f0.Write(blk, 2048);
		f0.Write(blk, 2048);
		make_random_data(blk, 2048, 1343278);
		f0.Write(blk, 2048);
	
		write_test_data(f0, INITIAL_FILE_LENGTH - (16*1024) - ((4*1024)*2) - (4*1024) - (2048*4), 202);
	
	}
	
	// Then... create the varients
	for(int l = 0; testfiles[l] != 0; ++l)
	{
		char n1[256];
		char n2[256];
		sprintf(n1, "testfiles/f%d", l + 1);
		sprintf(n2, "testfiles/f%d", l);

		FileStream f1(n1, O_WRONLY | O_CREAT);
		gen_varient(f1, n2, testfiles[l]);
	}
}