source: box/trunk/test/backupdiff/difftestfiles.cpp @ 2506

// --------------------------------------------------------------------------
//
// 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]);
        }
}