peppy/BSDiffer.cs

## BSDiffer.cs
using System;
using System.IO;
using System.Text;
using ICSharpCode.SharpZipLib.BZip2;
using Ionic.Zlib;

/* uncomment this to use unsafe version of memcmp */
//#define MEMCMP_UNSAFE

namespace osu_common.Libraries
{
    public class BSDiffer
    {
        /// <summary>
        /// Occurs when more than one whole percentage has been processed.
        /// This is not totally accurate because we do not push updates during large stream reads
        /// for performance reasons.
        /// </summary>
        public event ProgressUpdateHandler OnProgress;

        /// <summary>
        /// Internal check for change in progress of over 1%.
        /// </summary>
        private int progress;

        /// <summary>
        /// Read/write block size
        /// </summary>
        private const int SIZE = 64 * 1024;

        #region Algorithms

        private void split(int[] I, int[] V, int start, int len, int h)
        {
            int x, i, j, k;

            if (len < 16)
            {
                for (k = start; k < start + len; k += j)
                {
                    j = 1;
                    x = V[I[k] + h];
                    for (i = 1; k + i < start + len; i++)
                    {
                        if (V[I[k + i] + h] < x)
                        {
                            x = V[I[k + i] + h];
                            j = 0;
                        }

                        if (V[I[k + i] + h] == x)
                        {
                            int tmp = I[k + j];
                            I[k + j] = I[k + i];
                            I[k + i] = tmp;
                            j++;
                        }
                    }

                    for (i = 0; i < j; i++)
                        V[I[k + i]] = k + j - 1;

                    if (j == 1)
                        I[k] = -1;
                }

                return;
            }

            x = V[I[start + len / 2] + h];
            int jj = 0, kk = 0;
            for (i = start; i < start + len; i++)
            {
                if (V[I[i] + h] < x)
                    jj++;
                if (V[I[i] + h] == x)
                    kk++;
            }

            jj += start;
            kk += jj;

            i = start;
            j = 0;
            k = 0;

            while (i < jj)
            {
                if (V[I[i] + h] < x)
                {
                    i++;
                }
                else if (V[I[i] + h] == x)
                {
                    int tmp = I[i];
                    I[i] = I[jj + j];
                    I[jj + j] = tmp;
                    j++;
                }
                else
                {
                    int tmp = I[i];
                    I[i] = I[kk + k];
                    I[kk + k] = tmp;
                    k++;
                }
            }

            while (jj + j < kk)
            {
                if (V[I[jj + j] + h] == x)
                {
                    j++;
                }
                else
                {
                    int tmp = I[jj + j];
                    I[jj + j] = I[kk + k];
                    I[kk + k] = tmp;
                    k++;
                }
            }

            if (jj > start)
                split(I, V, start, jj - start, h);

            for (i = 0; i < kk - jj; i++)
                V[I[jj + i]] = kk - 1;
            if (jj == kk - 1)
                I[jj] = -1;

            if (start + len > kk)
                split(I, V, kk, start + len - kk, h);
        }

        private void qsufsort(int[] I, int[] V, byte[] oldfile, int oldsize)
        {
            int[] buckets = new int[256];

            for (int i = 0; i < oldsize; i++)
                buckets[oldfile[i]]++;
            for (int i = 1; i < 256; i++)
                buckets[i] += buckets[i - 1];
            for (int i = 255; i > 0; i--)
                buckets[i] = buckets[i - 1];
            buckets[0] = 0;

            for (int i = 0; i < oldsize; i++)
                I[++buckets[oldfile[i]]] = i;
            I[0] = oldsize;
            for (int i = 0; i < oldsize; i++)
                V[i] = buckets[oldfile[i]];
            V[oldsize] = 0;
            for (int i = 1; i < 256; i++)
            {
                if (buckets[i] == buckets[i - 1] + 1)
                    I[buckets[i]] = -1;
            }
            I[0] = -1;

            for (int h = 1; I[0] != -(oldsize + 1); h += h)
            {
                int len = 0;
                int i;
                for (i = 0; i < oldsize + 1; )
                {
                    updateProgress(i, oldsize);
                    if (I[i] < 0)
                    {
                        len -= I[i];
                        i -= I[i];
                    }
                    else
                    {
                        if (len != 0)
                            I[i - len] = -len;
                        len = V[I[i]] + 1 - i;
                        split(I, V, i, len, h);
                        i += len;
                        len = 0;
                    }
                }

                if (len != 0)
                    I[i - len] = -len;
            }

            for (int i = 0; i < oldsize + 1; i++)
                I[V[i]] = i;
        }

        private static int matchlen(byte[] oldfile, int oldoffset, int oldsize, byte[] newfile, int newoffset, int newsize)
        {
            int i;

            for (i = 0; (i < oldsize - oldoffset) && (i < newsize - newoffset); i++)
            {
                if (oldfile[i + oldoffset] != newfile[i + newoffset])
                    break;
            }

            return i;
        }

        private int search(int[] I, byte[] oldfile, int oldsize, byte[] newfile, int newoffset, int newsize, int st, int en, out int pos)
        {
            int x, y;

            if (en - st < 2)
            {
                x = matchlen(oldfile, I[st], oldsize, newfile, newoffset, newsize);
                y = matchlen(oldfile, I[en], oldsize, newfile, newoffset, newsize);

                if (x > y)
                {
                    pos = I[st];
                    return x;
                }
                else
                {
                    pos = I[en];
                    return y;
                }
            }

            x = st + (en - st) / 2;

            int memcmpres;

#if MEMCMP_UNSAFE
            unsafe
            {
                fixed(byte* a = oldfile, b = newfile)
                {
                    memcmpres = memcmp(a + I[x], b + newoffset, Math.Min(oldsize - I[x], newsize - newoffset));
                }
            }
#else
            memcmpres = memcmp(oldfile, I[x], newfile, newoffset, Math.Min(oldsize - I[x], newsize - newoffset));
#endif
            if (memcmpres < 0)
            {
                return search(I, oldfile, oldsize, newfile, newoffset, newsize, x, en, out pos);
            }
            else
            {
                return search(I, oldfile, oldsize, newfile, newoffset, newsize, st, x, out pos);
            }
        }

        private void offtout(int x, byte[] buf)
        {
            int y;
            if (x < 0)
                y = -x;
            else
                y = x;

            for (int i = 0; i < 7; i++)
            {
                buf[i] = (byte)(y % 256);
                y -= buf[i];
                y /= 256;
            }
            buf[7] = (byte)(y % 256);

            if (x < 0)
                buf[7] |= 0x80;
        }

        private unsafe static int memcmp(byte* a, byte* b, int count)
        {
            int v = 0;
            for (int i = 0; i < count && v == 0; i++)
                v = a[i] - b[i];

            return v;
        }

        private static int memcmp(byte[] a, int aoffset, byte[] b, int boffset, int count)
        {
            int v = 0;
            for (int i = 0; i < count && v == 0; i++)
                v = a[i + aoffset] - b[i + boffset];

            return v;
        }

        #endregion

        private Stream getCompressionStream(Compression compression, Stream wrapped)
        {
            switch (compression)
            {
                case Compression.BZip2:
                    return new BZip2OutputStream(wrapped);
                case Compression.GZip:
                    return new GZipStream(wrapped, CompressionMode.Compress, CompressionLevel.BestCompression, true);
                default:
                    return null;
            }
        }

        public void Diff(string oldpath, string newpath, Stream outStream)
        {
            Diff(oldpath, newpath, outStream, Compression.BZip2);
        }

        public void Diff(string oldpath, string newpath, string patchpath)
        {
            using (FileStream fileStream = File.Open(patchpath, FileMode.Create))
                Diff(oldpath, newpath, fileStream);
        }

        public void Diff(string oldpath, string newpath, Stream outStream, Compression compression)
        {
            int oldsize, newsize;
            int progressMax;
            int progressCur = 0;

            byte[] oldfile;
            using (FileStream stream = File.OpenRead(oldpath))
            {
                oldsize = (int)stream.Length;
                oldfile = new byte[oldsize];

                progressMax = oldsize * 9;

                for (int i = 0; i < oldsize; i += SIZE)
                {
                    stream.Read(oldfile, i, Math.Min(SIZE, oldsize - i));
                    updateProgress(progressCur + i, progressMax);
                }

                progressCur = oldsize;
            }

            int[] I = new int[oldsize + 1];
            int[] V = new int[oldsize + 1];

            // runs
            qsufsort(I, V, oldfile, oldsize);

            // free V
            V = null;

            byte[] newfile;
            using (FileStream stream = File.OpenRead(newpath))
            {
                newsize = (int)stream.Length;
                newfile = new byte[newsize];

                progressMax += newsize * 7 - oldsize * 7;

                for (int i = 0; i < newsize; i += SIZE)
                {
                    stream.Read(newfile, i, Math.Min(SIZE, newsize - i));
                    updateProgress(progressCur + i, progressMax);
                }

                progressCur += newsize;
            }

            byte[] db = new byte[newsize + 1];
            byte[] eb = new byte[newsize + 1];

            int dblen = 0;
            int eblen = 0;

            using (BinaryWriter bw = new BinaryWriter(outStream))
            {
                /* Header is
		            0	8	 "BSDIFF40"
		            8	8	length of bzip2ed ctrl block
		            16	8	length of bzip2ed diff block
		            24	8	length of new file */
                /* File is
                    0	32	Header
                    32	??	Bzip2ed ctrl block
                    ??	??	Bzip2ed diff block
                    ??	??	Bzip2ed extra block */

                bw.Write(Encoding.ASCII.GetBytes("BSDIFF40"));
                bw.Write((long)0);
                bw.Write((long)0);
                bw.Write((long)newsize);

                using (MemoryStream mem = new MemoryStream())
                {
                    using (Stream gzstream = getCompressionStream(compression, mem))
                    {
                        int pos = 0;
                        int scan = 0, len = 0;
                        int lastscan = 0, lastpos = 0, lastoffset = 0;

                        while (scan < newsize)
                        {
                            int oldscore = 0;

                            for (int scsc = (scan += len); scan < newsize; scan++)
                            {
                                len = search(I, oldfile, oldsize, newfile, scan, newsize, 0, oldsize, out pos);

                                for (; scsc < scan + len; scsc++)
                                {
                                    if ((scsc + lastoffset < oldsize) && (oldfile[scsc + lastoffset] == newfile[scsc]))
                                        oldscore++;
                                }

                                if (((len == oldscore) && (len != 0)) || (len > oldscore + 8))
                                    break;

                                if ((scan + lastoffset < oldsize) &&
                                    (oldfile[scan + lastoffset] == newfile[scan]))
                                    oldscore--;
                            }

                            if ((len != oldscore) || (scan == newsize))
                            {
                                int s = 0, Sf = 0, lenf = 0;
                                int Sb = 0, lenb = 0;
                                int Ss = 0, lens = 0;

                                for (int i = 0; (lastscan + i < scan) && (lastpos + i < oldsize); )
                                {
                                    if (oldfile[lastpos + i] == newfile[lastscan + i])
                                        s++;

                                    i++;

                                    if (s * 2 - i > Sf * 2 - lenf)
                                    {
                                        Sf = s;
                                        lenf = i;
                                    }
                                }

                                if (scan < newsize)
                                {
                                    s = 0;

                                    for (int i = 1; (scan >= lastscan + i) && (pos >= i); i++)
                                    {
                                        if (oldfile[pos - i] == newfile[scan - i])
                                            s++;

                                        if (s * 2 - i > Sb * 2 - lenb)
                                        {
                                            Sb = s;
                                            lenb = i;
                                        }
                                    }
                                }

                                if (lastscan + lenf > scan - lenb)
                                {
                                    int overlap = (lastscan + lenf) - (scan - lenb);
                                    s = 0;

                                    for (int i = 0; i < overlap; i++)
                                    {
                                        if (newfile[lastscan + lenf - overlap + i] ==
                                            oldfile[lastpos + lenf - overlap + i])
                                            s++;

                                        if (newfile[scan - lenb + i] == oldfile[pos - lenb + i])
                                            s--;

                                        if (s > Ss)
                                        {
                                            Ss = s;
                                            lens = i + 1;
                                        }
                                    }

                                    lenf += lens - overlap;
                                    lenb -= lens;
                                }

                                for (int i = 0; i < lenf; i++)
                                    db[dblen + i] = (byte)(newfile[lastscan + i] - oldfile[lastpos + i]);

                                for (int i = 0; i < (scan - lenb) - (lastscan + lenf); i++)
                                    eb[eblen + i] = newfile[lastscan + lenf + i];

                                dblen += lenf;
                                eblen += (scan - lenb) - (lastscan + lenf);

                                byte[] buffer = new byte[8];

                                offtout(lenf, buffer);
                                gzstream.Write(buffer, 0, 8);

                                offtout((scan - lenb) - (lastscan + lenf), buffer);
                                gzstream.Write(buffer, 0, 8);

                                offtout((pos - lenb) - (lastpos + lenf), buffer);
                                gzstream.Write(buffer, 0, 8);

                                lastscan = scan - lenb;
                                lastpos = pos - lenb;
                                lastoffset = pos - scan;
                            }

                            updateProgress(progressCur + scan, progressMax);
                        }

                        progressCur += newsize;
                    }

                    byte[] data = mem.ToArray();
                    progressMax += data.Length - newsize;
                    for (int i = 0; i < data.Length; i += SIZE)
                    {
                        bw.Write(data, i, Math.Min(SIZE, data.Length - i));
                        updateProgress(progressCur + i, progressMax);
                    }

                    progressCur += data.Length;
                }

                bw.Flush();
                long lenctrl = bw.BaseStream.Position - 32;

                // write compressed diff data
                using (MemoryStream mem = new MemoryStream())
                {
                    using (Stream gzstream = getCompressionStream(compression, mem))
                    {
                        progressMax += dblen - newsize;

                        for (int i = 0; i < dblen; i += SIZE)
                        {
                            gzstream.Write(db, i, Math.Min(SIZE, dblen - i));
                            updateProgress(progressCur + i, progressMax);
                        }

                        progressCur += dblen;
                    }

                    byte[] data = mem.ToArray();
                    progressMax += data.Length - newsize;
                    for (int i = 0; i < data.Length; i += SIZE)
                    {
                        bw.Write(data, i, Math.Min(SIZE, data.Length - i));
                        updateProgress(progressCur += i, progressMax);
                    }
                }

                bw.Flush();
                long lendiff = bw.BaseStream.Position - lenctrl - 32;

                // write compressed extra data
                using (MemoryStream mem = new MemoryStream())
                {
                    using (Stream gzstream = getCompressionStream(compression, mem))
                    {
                        progressMax += eblen - newsize;

                        for (int i = 0; i < eblen; i += SIZE)
                        {
                            gzstream.Write(eb, i, Math.Min(SIZE, eblen - i));
                            updateProgress(progressCur + i, progressMax);
                        }

                        progressCur += eblen;
                    }

                    byte[] data = mem.ToArray();
                    progressMax += data.Length - newsize;
                    for (int i = 0; i < data.Length; i += SIZE)
                    {
                        bw.Write(data, i, Math.Min(SIZE, data.Length - i));
                        updateProgress(progressCur + i, progressMax);
                    }
                }

                // fill in gaps in header
                bw.Flush();
                bw.Seek(8, SeekOrigin.Begin);
                bw.Write(lenctrl);
                bw.Write(lendiff);

                if (OnProgress != null)
                    OnProgress(this, 1, 1);
            }
        }

        private void updateProgress(long pos, long size)
        {
            int lastPercent = progress;
            progress = (int)((float)pos / size * 100);
            if (lastPercent != progress && OnProgress != null)
                OnProgress(this, pos, size);
        }
    }
}

## BSPatcher.cs
using System;
using System.IO;
using ICSharpCode.SharpZipLib.BZip2;
using Ionic.Zlib;

namespace osu_common.Libraries
{
    public delegate void ProgressUpdateHandler(object sender, long current, long total);

    public class BSPatcher
    {
        /// <summary>
        /// Occurs when more than one whole percentage has been processed.
        /// This is not totally accurate because we do not push updates during large stream reads
        /// for performance reasons.
        /// </summary>
        public event ProgressUpdateHandler OnProgress;

        /// <summary>
        /// Internal check for change in progress of over 1%.
        /// </summary>
        private int progress;

        private static int offtin(byte[] buf, int startOffset)
        {
            int y = buf[7 + startOffset] & 0x7F;
            y = y * 256;
            y += buf[6 + startOffset];
            y = y * 256;
            y += buf[5 + startOffset];
            y = y * 256;
            y += buf[4 + startOffset];
            y = y * 256;
            y += buf[3 + startOffset];
            y = y * 256;
            y += buf[2 + startOffset];
            y = y * 256;
            y += buf[1 + startOffset];
            y = y * 256;
            y += buf[0 + startOffset];

            if ((buf[7 + startOffset] & 0x80) > 0) y = -y;

            return y;
        }

        public void Patch(string oldfile, string newfile, string patchfile, Compression cmp)
        {
            long controlLength, dataLength, newSize;

            /*
            File format:
            0	8	"BSDIFF40"
            8	8	X
            16	8	Y
            24	8	sizeof(newfile)
            32	X	bzip2(control block)
            32+X	Y	bzip2(diff block)
            32+X+Y	???	bzip2(extra block)
            with control block a set of triples (x,y,z) meaning "add x bytes
            from oldfile to x bytes from the diff block; copy y bytes from the
            extra block; seek forwards in oldfile by z bytes".
            */

            using (FileStream header = File.OpenRead(patchfile))
            {
                byte[] headerBuf = new byte[32];

                if (header.Read(headerBuf, 0, 32) < 32)
                    throw new Exception("invalid patch file (too small)");

                if (!buffcmp(headerBuf, "BSDIFF40", 0, 8))
                    throw new Exception("invalid patch file (no magic)");

                controlLength = offtin(headerBuf, 8);
                dataLength = offtin(headerBuf, 16);
                newSize = offtin(headerBuf, 24);

                if (controlLength < 0 || dataLength < 0 || newSize < 0)
                    throw new Exception("invalid patch file (sizes are corrupt)");
            }

            long progressSize = newSize * 3;

            Stream controlStream, diffStream, extraStream;

            byte[] cfs, dfs, efs;

            using (FileStream stream = File.OpenRead(patchfile))
            {
                stream.Seek(32, SeekOrigin.Begin);

                cfs = new byte[controlLength];
                stream.Read(cfs, 0, cfs.Length);

                dfs = new byte[dataLength];
                stream.Read(dfs, 0, dfs.Length);

                efs = new byte[stream.Length - stream.Position];
                stream.Read(efs, 0, efs.Length);
            }

            switch (cmp)
            {
                case Compression.BZip2:
                    controlStream = new BZip2InputStream(new MemoryStream(cfs));
                    diffStream = new BZip2InputStream(new MemoryStream(dfs));
                    extraStream = new BZip2InputStream(new MemoryStream(efs));
                    break;
                default:
                    controlStream = new GZipStream(new MemoryStream(cfs), CompressionMode.Decompress, CompressionLevel.BestCompression);
                    diffStream = new GZipStream(new MemoryStream(dfs), CompressionMode.Decompress, CompressionLevel.BestCompression);
                    extraStream = new GZipStream(new MemoryStream(efs), CompressionMode.Decompress, CompressionLevel.BestCompression);
                    break;
            }

            byte[] oldFileBytes;

            int segment_length = 1048573;

            using (FileStream stream = new FileStream(oldfile, FileMode.Open, FileAccess.Read, FileShare.Read))
            {
                long length = stream.Length;
                oldFileBytes = new byte[(int)length];
                for (int i = 0; i < oldFileBytes.Length; i += segment_length)
                {
                    stream.Read(oldFileBytes, i, Math.Min(segment_length, oldFileBytes.Length - i));
                    updateProgress(i, progressSize);
                }
            }

            byte[] newFileBytes = new byte[newSize];

            long oldSize = oldFileBytes.Length;

            int newPos = 0;
            int oldPos = 0;

            int[] ctrl = new int[3];
            byte[] buf = new byte[8];

            /* Read control data */
            while (newPos < newSize)
            {
                int lenRead;

                for (int i = 0; i <= 2; i++)
                {
                    lenRead = controlStream.Read(buf, 0, 8);
                    if (lenRead < 8)
                        throw new Exception("invalid patch file (corrupt)");
                    ctrl[i] = offtin(buf, 0);
                }

                if (newPos + ctrl[0] > newSize)
                    throw new Exception("invalid patch file (corrupt)");

                /* Read diff string */
                lenRead = 0;

                for (int i = newPos; i < newPos + ctrl[0]; i += 65536)
                {
                    lenRead += diffStream.Read(newFileBytes, i, Math.Min(65536, (newPos + ctrl[0]) - i));
                    updateProgress(newSize + newPos + lenRead, progressSize);
                }

                if (lenRead < ctrl[0])
                    throw new Exception("invalid patch file (corrupt)");

                /* Add old data to diff string */
                for (int i = 0; i < ctrl[0]; i++)
                    if ((oldPos + i >= 0) && (oldPos + i < oldSize))
                        newFileBytes[newPos + i] += oldFileBytes[oldPos + i];

                /* Adjust pointers */
                newPos += ctrl[0];
                oldPos += ctrl[0];

                if (newPos > newSize)
                    throw new Exception("invalid patch file (corrupt)");

                /* Read extra string */
                lenRead = extraStream.Read(newFileBytes, newPos, ctrl[1]);
                if (lenRead < ctrl[1])
                    throw new Exception("invalid patch file (corrupt)");

                /* Sanity-check */
                newPos += ctrl[1];
                oldPos += ctrl[2];
            }

            controlStream.Close();
            diffStream.Close();
            extraStream.Close();

            using (FileStream str = File.Create(newfile))
            {
                for (int i = 0; i < newFileBytes.Length; i += segment_length)
                {
                    str.Write(newFileBytes, i, Math.Min(segment_length, newFileBytes.Length - i));
                    updateProgress(newSize * 2 + i, progressSize);
                }
            }

            if (OnProgress != null)
                OnProgress(this, 1, 1);
        }

        private void updateProgress(long pos, long size)
        {
            int lastPercent = progress;
            progress = (int)((float)pos / size * 100);
            if (lastPercent != progress && OnProgress != null)
                OnProgress(this, pos, size);
        }

        private static bool buffcmp(byte[] buf, string s, int start, int count)
        {
            for (int i = start; i < start + count; i++)
                if (buf[i] != s[i])
                    return false;
            return true;
        }
    }

    public enum Compression
    {
        GZip,
        BZip2
    }
}
	using System;
	using System.IO;
	using System.Text;
	using ICSharpCode.SharpZipLib.BZip2;
	using Ionic.Zlib;

	/* uncomment this to use unsafe version of memcmp */
	//#define MEMCMP_UNSAFE

	namespace osu_common.Libraries
	{
	public class BSDiffer
	{
	/// <summary>
	/// Occurs when more than one whole percentage has been processed.
	/// This is not totally accurate because we do not push updates during large stream reads
	/// for performance reasons.
	/// </summary>
	public event ProgressUpdateHandler OnProgress;

	/// <summary>
	/// Internal check for change in progress of over 1%.
	/// </summary>
	private int progress;

	/// <summary>
	/// Read/write block size
	/// </summary>
	private const int SIZE = 64 * 1024;

	#region Algorithms

	private void split(int[] I, int[] V, int start, int len, int h)
	{
	int x, i, j, k;

	if (len < 16)
	{
	for (k = start; k < start + len; k += j)
	{
	j = 1;
	x = V[I[k] + h];
	for (i = 1; k + i < start + len; i++)
	{
	if (V[I[k + i] + h] < x)
	{
	x = V[I[k + i] + h];
	j = 0;
	}

	if (V[I[k + i] + h] == x)
	{
	int tmp = I[k + j];
	I[k + j] = I[k + i];
	I[k + i] = tmp;
	j++;
	}
	}

	for (i = 0; i < j; i++)
	V[I[k + i]] = k + j - 1;

	if (j == 1)
	I[k] = -1;
	}

	return;
	}

	x = V[I[start + len / 2] + h];
	int jj = 0, kk = 0;
	for (i = start; i < start + len; i++)
	{
	if (V[I[i] + h] < x)
	jj++;
	if (V[I[i] + h] == x)
	kk++;
	}

	jj += start;
	kk += jj;

	i = start;
	j = 0;
	k = 0;

	while (i < jj)
	{
	if (V[I[i] + h] < x)
	{
	i++;
	}
	else if (V[I[i] + h] == x)
	{
	int tmp = I[i];
	I[i] = I[jj + j];
	I[jj + j] = tmp;
	j++;
	}
	else
	{
	int tmp = I[i];
	I[i] = I[kk + k];
	I[kk + k] = tmp;
	k++;
	}
	}

	while (jj + j < kk)
	{
	if (V[I[jj + j] + h] == x)
	{
	j++;
	}
	else
	{
	int tmp = I[jj + j];
	I[jj + j] = I[kk + k];
	I[kk + k] = tmp;
	k++;
	}
	}

	if (jj > start)
	split(I, V, start, jj - start, h);

	for (i = 0; i < kk - jj; i++)
	V[I[jj + i]] = kk - 1;
	if (jj == kk - 1)
	I[jj] = -1;

	if (start + len > kk)
	split(I, V, kk, start + len - kk, h);
	}

	private void qsufsort(int[] I, int[] V, byte[] oldfile, int oldsize)
	{
	int[] buckets = new int[256];

	for (int i = 0; i < oldsize; i++)
	buckets[oldfile[i]]++;
	for (int i = 1; i < 256; i++)
	buckets[i] += buckets[i - 1];
	for (int i = 255; i > 0; i--)
	buckets[i] = buckets[i - 1];
	buckets[0] = 0;

	for (int i = 0; i < oldsize; i++)
	I[++buckets[oldfile[i]]] = i;
	I[0] = oldsize;
	for (int i = 0; i < oldsize; i++)
	V[i] = buckets[oldfile[i]];
	V[oldsize] = 0;
	for (int i = 1; i < 256; i++)
	{
	if (buckets[i] == buckets[i - 1] + 1)
	I[buckets[i]] = -1;
	}
	I[0] = -1;

	for (int h = 1; I[0] != -(oldsize + 1); h += h)
	{
	int len = 0;
	int i;
	for (i = 0; i < oldsize + 1; )
	{
	updateProgress(i, oldsize);
	if (I[i] < 0)
	{
	len -= I[i];
	i -= I[i];
	}
	else
	{
	if (len != 0)
	I[i - len] = -len;
	len = V[I[i]] + 1 - i;
	split(I, V, i, len, h);
	i += len;
	len = 0;
	}
	}

	if (len != 0)
	I[i - len] = -len;
	}

	for (int i = 0; i < oldsize + 1; i++)
	I[V[i]] = i;
	}

	private static int matchlen(byte[] oldfile, int oldoffset, int oldsize, byte[] newfile, int newoffset, int newsize)
	{
	int i;

	for (i = 0; (i < oldsize - oldoffset) && (i < newsize - newoffset); i++)
	{
	if (oldfile[i + oldoffset] != newfile[i + newoffset])
	break;
	}

	return i;
	}

	private int search(int[] I, byte[] oldfile, int oldsize, byte[] newfile, int newoffset, int newsize, int st, int en, out int pos)
	{
	int x, y;

	if (en - st < 2)
	{
	x = matchlen(oldfile, I[st], oldsize, newfile, newoffset, newsize);
	y = matchlen(oldfile, I[en], oldsize, newfile, newoffset, newsize);

	if (x > y)
	{
	pos = I[st];
	return x;
	}
	else
	{
	pos = I[en];
	return y;
	}
	}

	x = st + (en - st) / 2;

	int memcmpres;

	#if MEMCMP_UNSAFE
	unsafe
	{
	fixed(byte* a = oldfile, b = newfile)
	{
	memcmpres = memcmp(a + I[x], b + newoffset, Math.Min(oldsize - I[x], newsize - newoffset));
	}
	}
	#else
	memcmpres = memcmp(oldfile, I[x], newfile, newoffset, Math.Min(oldsize - I[x], newsize - newoffset));
	#endif
	if (memcmpres < 0)
	{
	return search(I, oldfile, oldsize, newfile, newoffset, newsize, x, en, out pos);
	}
	else
	{
	return search(I, oldfile, oldsize, newfile, newoffset, newsize, st, x, out pos);
	}
	}

	private void offtout(int x, byte[] buf)
	{
	int y;
	if (x < 0)
	y = -x;
	else
	y = x;

	for (int i = 0; i < 7; i++)
	{
	buf[i] = (byte)(y % 256);
	y -= buf[i];
	y /= 256;
	}
	buf[7] = (byte)(y % 256);

	if (x < 0)
	buf[7] \|= 0x80;
	}

	private unsafe static int memcmp(byte* a, byte* b, int count)
	{
	int v = 0;
	for (int i = 0; i < count && v == 0; i++)
	v = a[i] - b[i];

	return v;
	}

	private static int memcmp(byte[] a, int aoffset, byte[] b, int boffset, int count)
	{
	int v = 0;
	for (int i = 0; i < count && v == 0; i++)
	v = a[i + aoffset] - b[i + boffset];

	return v;
	}

	#endregion

	private Stream getCompressionStream(Compression compression, Stream wrapped)
	{
	switch (compression)
	{
	case Compression.BZip2:
	return new BZip2OutputStream(wrapped);
	case Compression.GZip:
	return new GZipStream(wrapped, CompressionMode.Compress, CompressionLevel.BestCompression, true);
	default:
	return null;
	}
	}

	public void Diff(string oldpath, string newpath, Stream outStream)
	{
	Diff(oldpath, newpath, outStream, Compression.BZip2);
	}

	public void Diff(string oldpath, string newpath, string patchpath)
	{
	using (FileStream fileStream = File.Open(patchpath, FileMode.Create))
	Diff(oldpath, newpath, fileStream);
	}

	public void Diff(string oldpath, string newpath, Stream outStream, Compression compression)
	{
	int oldsize, newsize;
	int progressMax;
	int progressCur = 0;

	byte[] oldfile;
	using (FileStream stream = File.OpenRead(oldpath))
	{
	oldsize = (int)stream.Length;
	oldfile = new byte[oldsize];

	progressMax = oldsize * 9;

	for (int i = 0; i < oldsize; i += SIZE)
	{
	stream.Read(oldfile, i, Math.Min(SIZE, oldsize - i));
	updateProgress(progressCur + i, progressMax);
	}

	progressCur = oldsize;
	}

	int[] I = new int[oldsize + 1];
	int[] V = new int[oldsize + 1];

	// runs
	qsufsort(I, V, oldfile, oldsize);

	// free V
	V = null;

	byte[] newfile;
	using (FileStream stream = File.OpenRead(newpath))
	{
	newsize = (int)stream.Length;
	newfile = new byte[newsize];

	progressMax += newsize * 7 - oldsize * 7;

	for (int i = 0; i < newsize; i += SIZE)
	{
	stream.Read(newfile, i, Math.Min(SIZE, newsize - i));
	updateProgress(progressCur + i, progressMax);
	}

	progressCur += newsize;
	}

	byte[] db = new byte[newsize + 1];
	byte[] eb = new byte[newsize + 1];

	int dblen = 0;
	int eblen = 0;

	using (BinaryWriter bw = new BinaryWriter(outStream))
	{
	/* Header is
	0 8 "BSDIFF40"
	8 8 length of bzip2ed ctrl block
	16 8 length of bzip2ed diff block
	24 8 length of new file */
	/* File is
	0 32 Header
	32 ?? Bzip2ed ctrl block
	?? ?? Bzip2ed diff block
	?? ?? Bzip2ed extra block */

	bw.Write(Encoding.ASCII.GetBytes("BSDIFF40"));
	bw.Write((long)0);
	bw.Write((long)0);
	bw.Write((long)newsize);

	using (MemoryStream mem = new MemoryStream())
	{
	using (Stream gzstream = getCompressionStream(compression, mem))
	{
	int pos = 0;
	int scan = 0, len = 0;
	int lastscan = 0, lastpos = 0, lastoffset = 0;

	while (scan < newsize)
	{
	int oldscore = 0;

	for (int scsc = (scan += len); scan < newsize; scan++)
	{
	len = search(I, oldfile, oldsize, newfile, scan, newsize, 0, oldsize, out pos);

	for (; scsc < scan + len; scsc++)
	{
	if ((scsc + lastoffset < oldsize) && (oldfile[scsc + lastoffset] == newfile[scsc]))
	oldscore++;
	}

	if (((len == oldscore) && (len != 0)) \|\| (len > oldscore + 8))
	break;

	if ((scan + lastoffset < oldsize) &&
	(oldfile[scan + lastoffset] == newfile[scan]))
	oldscore--;
	}

	if ((len != oldscore) \|\| (scan == newsize))
	{
	int s = 0, Sf = 0, lenf = 0;
	int Sb = 0, lenb = 0;
	int Ss = 0, lens = 0;

	for (int i = 0; (lastscan + i < scan) && (lastpos + i < oldsize); )
	{
	if (oldfile[lastpos + i] == newfile[lastscan + i])
	s++;

	i++;

	if (s * 2 - i > Sf * 2 - lenf)
	{
	Sf = s;
	lenf = i;
	}
	}

	if (scan < newsize)
	{
	s = 0;

	for (int i = 1; (scan >= lastscan + i) && (pos >= i); i++)
	{
	if (oldfile[pos - i] == newfile[scan - i])
	s++;

	if (s * 2 - i > Sb * 2 - lenb)
	{
	Sb = s;
	lenb = i;
	}
	}
	}

	if (lastscan + lenf > scan - lenb)
	{
	int overlap = (lastscan + lenf) - (scan - lenb);
	s = 0;

	for (int i = 0; i < overlap; i++)
	{
	if (newfile[lastscan + lenf - overlap + i] ==
	oldfile[lastpos + lenf - overlap + i])
	s++;

	if (newfile[scan - lenb + i] == oldfile[pos - lenb + i])
	s--;

	if (s > Ss)
	{
	Ss = s;
	lens = i + 1;
	}
	}

	lenf += lens - overlap;
	lenb -= lens;
	}

	for (int i = 0; i < lenf; i++)
	db[dblen + i] = (byte)(newfile[lastscan + i] - oldfile[lastpos + i]);

	for (int i = 0; i < (scan - lenb) - (lastscan + lenf); i++)
	eb[eblen + i] = newfile[lastscan + lenf + i];

	dblen += lenf;
	eblen += (scan - lenb) - (lastscan + lenf);

	byte[] buffer = new byte[8];

	offtout(lenf, buffer);
	gzstream.Write(buffer, 0, 8);

	offtout((scan - lenb) - (lastscan + lenf), buffer);
	gzstream.Write(buffer, 0, 8);

	offtout((pos - lenb) - (lastpos + lenf), buffer);
	gzstream.Write(buffer, 0, 8);

	lastscan = scan - lenb;
	lastpos = pos - lenb;
	lastoffset = pos - scan;
	}

	updateProgress(progressCur + scan, progressMax);
	}

	progressCur += newsize;
	}

	byte[] data = mem.ToArray();
	progressMax += data.Length - newsize;
	for (int i = 0; i < data.Length; i += SIZE)
	{
	bw.Write(data, i, Math.Min(SIZE, data.Length - i));
	updateProgress(progressCur + i, progressMax);
	}

	progressCur += data.Length;
	}

	bw.Flush();
	long lenctrl = bw.BaseStream.Position - 32;

	// write compressed diff data
	using (MemoryStream mem = new MemoryStream())
	{
	using (Stream gzstream = getCompressionStream(compression, mem))
	{
	progressMax += dblen - newsize;

	for (int i = 0; i < dblen; i += SIZE)
	{
	gzstream.Write(db, i, Math.Min(SIZE, dblen - i));
	updateProgress(progressCur + i, progressMax);
	}

	progressCur += dblen;
	}

	byte[] data = mem.ToArray();
	progressMax += data.Length - newsize;
	for (int i = 0; i < data.Length; i += SIZE)
	{
	bw.Write(data, i, Math.Min(SIZE, data.Length - i));
	updateProgress(progressCur += i, progressMax);
	}
	}

	bw.Flush();
	long lendiff = bw.BaseStream.Position - lenctrl - 32;

	// write compressed extra data
	using (MemoryStream mem = new MemoryStream())
	{
	using (Stream gzstream = getCompressionStream(compression, mem))
	{
	progressMax += eblen - newsize;

	for (int i = 0; i < eblen; i += SIZE)
	{
	gzstream.Write(eb, i, Math.Min(SIZE, eblen - i));
	updateProgress(progressCur + i, progressMax);
	}

	progressCur += eblen;
	}

	byte[] data = mem.ToArray();
	progressMax += data.Length - newsize;
	for (int i = 0; i < data.Length; i += SIZE)
	{
	bw.Write(data, i, Math.Min(SIZE, data.Length - i));
	updateProgress(progressCur + i, progressMax);
	}
	}

	// fill in gaps in header
	bw.Flush();
	bw.Seek(8, SeekOrigin.Begin);
	bw.Write(lenctrl);
	bw.Write(lendiff);

	if (OnProgress != null)
	OnProgress(this, 1, 1);
	}
	}

	private void updateProgress(long pos, long size)
	{
	int lastPercent = progress;
	progress = (int)((float)pos / size * 100);
	if (lastPercent != progress && OnProgress != null)
	OnProgress(this, pos, size);
	}
	}
	}