text: /*
    diff.c -- binary diff generator
  
    Copyright 2004,2005 Michael Schroeder
  
    rewritten from bsdiff.c,
        http://www.freebsd.org/cgi/cvsweb.cgi/src/usr.bin/bsdiff
    added library interface and hash method, enhanced suffix method.
  */
  /*-
   * Copyright 2003-2005 Colin Percival
   * All rights reserved
   *
   * Redistribution and use in source and binary forms, with or without
   * modification, are permitted providing that the following conditions 
   * are met:
   * 1. Redistributions of source code must retain the above copyright
   *    notice, this list of conditions and the following disclaimer.
   * 2. Redistributions in binary form must reproduce the above copyright
   *    notice, this list of conditions and the following disclaimer in the
   *    documentation and/or other materials provided with the distribution.
   *
   * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
   * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
   * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
   * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
   * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
   * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
   * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
   * POSSIBILITY OF SUCH DAMAGE.
   */
  
  #include <stdio.h>
  #include <stdlib.h>
  #include <unistd.h>
  #include <string.h>
  #include <bzlib.h>
  
  #include "delta.h"
  
  struct bzblock {
    unsigned char *data;
    unsigned int len;
    bz_stream strm;
  };
  
  static struct bzblock *blockopen()
  {
    struct bzblock *bzf;
    int ret;
    bzf = malloc(sizeof(*bzf));
    if (!bzf)
      return 0;
    bzf->strm.bzalloc = 0;
    bzf->strm.bzfree = 0;
    bzf->strm.opaque = 0;
    bzf->len = 0;
    ret = BZ2_bzCompressInit(&bzf->strm, 9, 0, 30);
    if (ret != BZ_OK)
      {
        free(bzf);
        return 0;
      }
    bzf->data = 0;
    bzf->strm.avail_in = 0;
    bzf->strm.next_in  = 0;
    bzf->strm.avail_out = 0;
    bzf->strm.next_out  = 0;
    return bzf;
  }
  
  static int blockwrite(struct bzblock *bzf, void *buf, int len)
  {
    int ret;
  
    if (len <= 0)
      return len < 0 ? -1 : 0;
    bzf->strm.avail_in = len;
    bzf->strm.next_in = buf;
    for (;;)
      {
        if (bzf->strm.avail_out < 4096)
  	{
  	  if (bzf->len + 8192 < bzf->len)
  	    return -1;
  	  if (bzf->data)
  	    bzf->data = realloc(bzf->data, bzf->len + 8192);
  	  else
  	    bzf->data = malloc(bzf->len + 8192);
  	  if (!bzf->data)
  	    return -1;
  	  bzf->strm.avail_out = 8192;
  	}
        bzf->strm.next_out = (char *)bzf->data + bzf->len;
        ret = BZ2_bzCompress(&bzf->strm, BZ_RUN);
        if (ret != BZ_RUN_OK)
  	return -1;
        bzf->len = (unsigned char *)bzf->strm.next_out - bzf->data;
        if (bzf->strm.avail_in == 0)
  	return len;
      }
  }
  
  static int blockclose(struct bzblock *bzf, unsigned char **datap, unsigned int *lenp)
  {
    int ret;
    bzf->strm.avail_in = 0;
    bzf->strm.next_in = 0;
    for (;;)
      {
        if (bzf->strm.avail_out < 4096)
  	{
  	  if (bzf->len + 8192 < bzf->len)
  	    return -1;
  	  if (bzf->data)
  	    bzf->data = realloc(bzf->data, bzf->len + 8192);
  	  else
  	    bzf->data = malloc(bzf->len + 8192);
  	  if (!bzf->data)
  	    return -1;
  	  bzf->strm.avail_out = 8192;
  	}
        bzf->strm.next_out = (char *)bzf->data + bzf->len;
        ret = BZ2_bzCompress(&bzf->strm, BZ_FINISH);
        if (ret != BZ_FINISH_OK && ret != BZ_STREAM_END)
          return -1;
        bzf->len = (unsigned char *)bzf->strm.next_out - bzf->data;
        if (ret == BZ_STREAM_END)
          break;
      }
    BZ2_bzCompressEnd (&bzf->strm);
    *datap = bzf->data;
    *lenp = bzf->len;
    free(bzf);
    return 0;
  }
  
  static inline bsuint matchlen(unsigned char *old, bsuint oldlen, unsigned char *new, bsuint newlen)
  {
    unsigned char *oldsave;
    bsuint max;
    oldsave = old;
    max = oldlen > newlen ? newlen : oldlen;
    while (max-- > 0)
      if (*old++ != *new++)
        return old - oldsave - 1;
    return old - oldsave;
  }
  
  #ifndef BSDIFF_NO_HASH
  
  /******************************************************************/
  /*                                                                */
  /*         hash method                                            */
  /*                                                                */
  /******************************************************************/
  
  #define HSIZESHIFT      4
  #define HSIZE           (1 << HSIZESHIFT)
  
  /* 256 random numbers generated by a quantum source */
  static unsigned int noise[256] =
  {
    0x9be502a4U, 0xba7180eaU, 0x324e474fU, 0x0aab8451U, 0x0ced3810U,
    0x2158a968U, 0x6bbd3771U, 0x75a02529U, 0x41f05c14U, 0xc2264b87U,
    0x1f67b359U, 0xcd2d031dU, 0x49dc0c04U, 0xa04ae45cU, 0x6ade28a7U,
    0x2d0254ffU, 0xdec60c7cU, 0xdef5c084U, 0x0f77ffc8U, 0x112021f6U,
    0x5f6d581eU, 0xe35ea3dfU, 0x3216bfb4U, 0xd5a3083dU, 0x7e63e9cdU,
    0xaa9208f6U, 0xda3f3978U, 0xfe0e2547U, 0x09dfb020U, 0xd97472c5U,
    0xbbce2edeU, 0x121aebd2U, 0x0e9fdbebU, 0x7b6f5d9cU, 0x84938e43U,
    0x30694f2dU, 0x86b7a7f8U, 0xefaf5876U, 0x263812e6U, 0xb6e48ddfU,
    0xce8ed980U, 0x4df591e1U, 0x75257b35U, 0x2f88dcffU, 0xa461fe44U,
    0xca613b4dU, 0xd9803f73U, 0xea056205U, 0xccca7a89U, 0x0f2dbb07U,
    0xc53e359eU, 0xe80d0137U, 0x2b2d2a5dU, 0xcfc1391aU, 0x2bb3b6c5U,
    0xb66aea3cU, 0x00ea419eU, 0xce5ada84U, 0xae1d6712U, 0x12f576baU,
    0x117fcbc4U, 0xa9d4c775U, 0x25b3d616U, 0xefda65a8U, 0xaff3ef5bU,
    0x00627e68U, 0x668d1e99U, 0x088d0eefU, 0xf8fac24dU, 0xe77457c7U,
    0x68d3beb4U, 0x921d2acbU, 0x9410eac9U, 0xd7f24399U, 0xcbdec497U,
    0x98c99ae1U, 0x65802b2cU, 0x81e1c3c4U, 0xa130bb09U, 0x17a87badU,
    0xa70367d6U, 0x148658d4U, 0x02f33377U, 0x8620d8b6U, 0xbdac25bdU,
    0xb0a6de51U, 0xd64c4571U, 0xa4185ba0U, 0xa342d70fU, 0x3f1dc4c1U,
    0x042dc3ceU, 0x0de89f43U, 0xa69b1867U, 0x3c064e11U, 0xad1e2c3eU,
    0x9660e8cdU, 0xd36b09caU, 0x4888f228U, 0x61a9ac3cU, 0xd9561118U,
    0x3532797eU, 0x71a35c22U, 0xecc1376cU, 0xab31e656U, 0x88bd0d35U,
    0x423b20ddU, 0x38e4651cU, 0x3c6397a4U, 0x4a7b12d9U, 0x08b1cf33U,
    0xd0604137U, 0xb035fdb8U, 0x4916da23U, 0xa9349493U, 0xd83daa9bU,
    0x145f7d95U, 0x868531d6U, 0xacb18f17U, 0x9cd33b6fU, 0x193e42b9U,
    0x26dfdc42U, 0x5069d8faU, 0x5bee24eeU, 0x5475d4c6U, 0x315b2c0cU,
    0xf764ef45U, 0x01b6f4ebU, 0x60ba3225U, 0x8a16777cU, 0x4c05cd28U,
    0x53e8c1d2U, 0xc8a76ce5U, 0x8045c1e6U, 0x61328752U, 0x2ebad322U,
    0x3444f3e2U, 0x91b8af11U, 0xb0cee675U, 0x55dbff5aU, 0xf7061ee0U,
    0x27d7d639U, 0xa4aef8c9U, 0x42ff0e4fU, 0x62755468U, 0x1c6ca3f3U,
    0xe4f522d1U, 0x2765fcb3U, 0xe20c8a95U, 0x3a69aea7U, 0x56ab2c4fU,
    0x8551e688U, 0xe0bc14c2U, 0x278676bfU, 0x893b6102U, 0xb4f0ab3bU,
    0xb55ddda9U, 0xa04c521fU, 0xc980088eU, 0x912aeac1U, 0x08519badU,
    0x991302d3U, 0x5b91a25bU, 0x696d9854U, 0x9ad8b4bfU, 0x41cb7e21U,
    0xa65d1e03U, 0x85791d29U, 0x89478aa7U, 0x4581e337U, 0x59bae0b1U,
    0xe0fc9df3U, 0x45d9002cU, 0x7837464fU, 0xda22de3aU, 0x1dc544bdU,
    0x601d8badU, 0x668b0abcU, 0x7a5ebfb1U, 0x3ac0b624U, 0x5ee16d7dU,
    0x9bfac387U, 0xbe8ef20cU, 0x8d2ae384U, 0x819dc7d5U, 0x7c4951e7U,
    0xe60da716U, 0x0c5b0073U, 0xb43b3d97U, 0xce9974edU, 0x0f691da9U,
    0x4b616d60U, 0x8fa9e819U, 0x3f390333U, 0x6f62fad6U, 0x5a32b67cU,
    0x3be6f1c3U, 0x05851103U, 0xff28828dU, 0xaa43a56aU, 0x075d7dd5U,
    0x248c4b7eU, 0x52fde3ebU, 0xf72e2edaU, 0x5da6f75fU, 0x2f5148d9U,
    0xcae2aeaeU, 0xfda6f3e5U, 0xff60d8ffU, 0x2adc02d2U, 0x1dbdbd4cU,
    0xd410ad7cU, 0x8c284aaeU, 0x392ef8e0U, 0x37d48b3aU, 0x6792fe9dU,
    0xad32ddfaU, 0x1545f24eU, 0x3a260f73U, 0xb724ca36U, 0xc510d751U,
    0x4f8df992U, 0x000b8b37U, 0x292e9b3dU, 0xa32f250fU, 0x8263d144U,
    0xfcae0516U, 0x1eae2183U, 0xd4af2027U, 0xc64afae3U, 0xe7b34fe4U,
    0xdf864aeaU, 0x80cc71c5U, 0x0e814df3U, 0x66cc5f41U, 0x853a497aU,
    0xa2886213U, 0x5e34a2eaU, 0x0f53ba47U, 0x718c484aU, 0xfa0f0b12U,
    0x33cc59ffU, 0x72b48e07U, 0x8b6f57bcU, 0x29cf886dU, 0x1950955bU,
    0xcd52910cU, 0x4cecef65U, 0x05c2cbfeU, 0x49df4f6aU, 0x1f4c3f34U,
    0xfadc1a09U, 0xf2d65a24U, 0x117f5594U, 0xde3a84e6U, 0x48db3024U,
    0xd10ca9b5U
  };
  
  /* buzhash by Robert C. Uzgalis */
  /* General hash functions. Technical Report TR-92-01, The University
     of Hong Kong, 1993 */
  
  static unsigned int buzhash(unsigned char *buf)
  {
    unsigned int x = 0x83d31df4U;
    int i;
    for (i = HSIZE; i != 0; i--)
      x = (x << 1) ^ (x & (1 << 31) ? 1 : 0) ^ noise[*buf++];
    return x;
  }
  
  static unsigned int primes[] =
  {
    65537, 98317, 147481, 221227, 331841, 497771, 746659, 1120001,
    1680013, 2520031, 3780053, 5670089, 8505137, 12757739, 19136609,
    28704913, 43057369, 64586087, 96879131, 145318741, 217978121,
    326967209, 490450837, 735676303, 1103514463, 1655271719,
    0xffffffff
  };
  
  struct hash_data {
    bsuint *hash;
    unsigned int prime;
  };
  
  static void *hash_create(unsigned char *buf, bsuint len)
  {
    struct hash_data *hd;
    bsuint *hash;
    unsigned char *bp = buf;
    bsuint off;
    unsigned int s;
    unsigned int prime;
    unsigned int num;
  
    hd = malloc(sizeof(*hd));
    if (!hd)
      return 0;
  #ifdef BSDIFF_64BIT
    /* this is a 16GB limit for HSIZESHIFT == 4 */
    if (len >= (bsuint)(0xffffffff / 4) << HSIZESHIFT)
      return 0;
  #endif
    num = (len + HSIZE - 1) >> HSIZESHIFT;
    prime = num * 4;
    for (s = 0; s < sizeof(primes)/sizeof(*primes) - 1; s++)
      if (prime < primes[s])
        break;
    prime = primes[s];
    hash = calloc(prime, sizeof(*hash));
    if (!hash)
      {
        free(hd);
        return 0;
      }
    for (off = 0; len >= HSIZE; off += HSIZE, buf += HSIZE, len -= HSIZE)
      {
        s = buzhash(buf) % prime;
        if (hash[s])
          {
            if (hash[(s == prime - 1) ? 0 : s + 1])
              continue;
            if (!memcmp(buf, bp + hash[s], HSIZE))
              continue;
            s = (s == prime - 1) ? 0 : s + 1;
          }
        hash[s] = off + 1;
      }
    hd->hash = hash;
    hd->prime = prime;
    return hd;
  }
  
  static void hash_free(void *data)
  {
    struct hash_data *hd = data;
    free(hd->hash);
    free(hd);
  }
  
  static bsuint hash_findnext(void *data, unsigned char *old, bsuint oldlen, unsigned char *new, bsuint newlen, bsuint lastoffset, bsuint scan, bsuint *posp, bsuint *lenp)
  {
    struct hash_data *hd = data;
    bsuint scanstart, oldscore, oldscorenum, oldscorestart;
    bsuint pos, len;
    bsuint lscan, lpos, llen;
    bsuint i, ss, scsc;
    unsigned int ssx;
    unsigned int prime;
    bsuint *hash;
  
    hash = hd->hash;
    prime = hd->prime;
    scanstart = scan;
    oldscore = oldscorenum = oldscorestart = 0;
    ssx = scan <= newlen - HSIZE ? buzhash(new + scan) : 0;
    pos = 0;
    len = 0;
    lpos = lscan = llen = 0;
    for (;;)
      {
        if (scan >= newlen - HSIZE)
  	{
  	  if (llen >= 32)
  	    goto gotit;
  	  break;
  	}
        ss = ssx % prime;
        pos = hash[ss];
        if (!pos)
  	{
  	  unsigned int oldc;
  scannext:
  	  if (llen >= 32 && scan - lscan >= HSIZE)
  	    goto gotit;
  	  ssx = (ssx << 1) ^ (ssx & (1 << 31) ? 1 : 0) ^ noise[new[scan + HSIZE]];
  	  oldc = noise[new[scan]] ^ (0x83d31df4U ^ 0x07a63be9U);
  #if HSIZE % 32 != 0
  	  ssx ^= (oldc << (HSIZE % 32)) ^ (oldc >> (32 - (HSIZE % 32)));
  #else
  	  ssx ^= oldc;
  #endif
  	  scan++;
  	  continue;
  	}
        pos--;
        if (memcmp(old + pos, new + scan, HSIZE))
  	{
  	  pos = hash[ss == prime - 1 ? 0 : ss + 1];
  	  if (!pos)
  	    goto scannext;
  	  pos--;
  	  if (memcmp(old + pos, new + scan, HSIZE))
  	    goto scannext;
  	}
        len = matchlen(old + pos + HSIZE, oldlen - pos - HSIZE, new + scan + HSIZE, newlen - scan - HSIZE) + HSIZE;
        if (scan + HSIZE * 4 <= newlen)
  	{
  	  unsigned int ssx2;
  	  bsuint len2, pos2;
  	  ssx2 = buzhash(new + scan + HSIZE * 3) % prime;
  	  pos2 = hash[ssx2];
  	  if (pos2)
  	    {
  	      if (memcmp(new + scan + HSIZE *3, old + pos2 - 1, HSIZE))
  		{
  		  ssx2 = (ssx2 == prime) ? 0 : ssx2 + 1;
  		  pos2 = hash[ssx2];
  		}
  	    }
  	  if (pos2 > 1 + HSIZE*3)
  	    {
  	      pos2 = pos2 - 1 - HSIZE*3;
  	      if (pos2 != pos)
  		{
  		  len2 = matchlen(old + pos2, oldlen - pos2, new + scan, newlen - scan);
  		  if (len2 > len)
  		    {
  		      pos = pos2;
  		      len = len2;
  		    }
  		}
  	    }
  	}
        if (len > llen)
  	{
  	  llen = len;
  	  lpos = pos;
  	  lscan = scan;
  	}
        goto scannext;
  gotit:
        scan = lscan;
        len = llen;
        pos = lpos;
        if (scan + lastoffset == pos)
  	{
  	  scan += len;
  	  scanstart = scan;
  	  if (scan + HSIZE < newlen)
  	    ssx = buzhash(new + scan);
  	  llen = 0;
  	  continue;
  	}
        for (i = scan - scanstart; i && pos && scan && old[pos - 1] == new[scan - 1]; i--)	
  	{
  	  len++;
  	  pos--;
  	  scan--;
  	}
        if (oldscorestart + 1 != scan || oldscorenum == 0 || oldscorenum - 1 > len)
  	{
  	  oldscore = 0;
  	  for (scsc = scan; scsc<scan+len; scsc++)
  	    if ((scsc+lastoffset<oldlen) && (old[scsc+lastoffset] == new[scsc]))
  	      oldscore++;
  	  oldscorestart = scan;
  	  oldscorenum = len;
  	}
        else
  	{
  	  if (oldscorestart + lastoffset < oldlen && old[oldscorestart + lastoffset] == new[oldscorestart])
  	    oldscore--;
  	  oldscorestart++;
  	  oldscorenum--;
  	  for (scsc = oldscorestart + oldscorenum; oldscorenum < len; scsc++)
  	    {
  	      if ((scsc+lastoffset<oldlen) && (old[scsc+lastoffset] == new[scsc]))
  		oldscore++;
  		oldscorenum++;
  	    }
  	}
        if (len - oldscore >= 32)
  	break;
        if (len > HSIZE * 3 + 32)
          scan += len - (HSIZE * 3 + 32);
        if (scan <= lscan)
  	scan = lscan + 1;
        scanstart = scan;
        if (scan + HSIZE < newlen)
  	ssx = buzhash(new + scan);
        llen = 0;
      }
    if (scan >= newlen - HSIZE)
      {
        scan = newlen;
        pos = 0;
        len = 0;
      }
    *posp = pos;
    *lenp = len;
    return scan;
  }
  
  #endif /* BSDIFF_NO_HASH */
  
  #ifndef BSDIFF_NO_SUF
  
  /******************************************************************/
  /*                                                                */
  /*         suffix list method                                     */
  /*                                                                */
  /******************************************************************/
  
  struct suf_data {
    bsint *I;
    bsint F[257];
  };
  
  static void suf_split(bsint *I, bsint *V, bsint start, bsint len, bsint h)
  {
    bsint i, j, k, x, tmp, jj, kk;
  
    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)
  		{
  		  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];
    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)
  	{
  	  tmp = I[i];
            I[i] = I[jj + j];
            I[jj + j] = tmp;
  	  j++;
  	}
        else
  	{
  	  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
  	{
  	  tmp = I[jj + j];
  	  I[jj + j] = I[kk + k];
  	  I[kk + k] = tmp;
  	  k++;
  	}
      }
  
    if(jj > start)
      suf_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)
      suf_split(I, V, kk, start + len - kk, h);
  }
  
  static bsint suf_bucketsort(bsint *V, bsint *I, bsint n, bsint s)
  {
    bsint c, d, g, i, j;
    bsint *B; 
  
    B = calloc(s, sizeof(bsint));
    if (!B)
      return 0;
    for (i = n - 1; i >= 0; i--)
      {
        c = V[i]; 
        V[i] = B[c]; 
        B[c] = i + 1;
      }
    for (j = s - 1, i = n; i; j--)
      {
        for (d = B[j], g = i; d; i--)
  	{
  	  c = d - 1;
  	  d = V[c]; 
  	  V[c] = g;
  	  I[i] = !d && g == i ? -1 : c; 
  	}
      }
    V[n] = 0;
    I[0] = -1;
    free(B);
    return 1;
  }
  
  static void *suf_create(unsigned char *buf, bsuint ulen)
  {
    struct suf_data *sd;
    bsint *V, *I;
    bsint i, h, l, oldv, s, len;
  
    len = ulen;
    if (len < 0)
      return 0;
    sd = malloc(sizeof(*sd));
    if (!sd)
      return 0;
    V = malloc(sizeof(bsint) * (len + 3));
    if (!V)
      {
        free(sd);
        return 0;
      }
    I = malloc(sizeof(bsint) * (len + 3));
    if (!I)
      {
        free(V);
        free(sd);
        return 0;
      }
    memset(sd->F, 0, sizeof(sd->F));
    if (len >= 0x1000000)
      {
        s = 0x1000002;
        sd->F[buf[0]]++;
        sd->F[buf[1]]++;
        oldv = buf[0] << 8 | buf[1];
        for (i = 2; i < len; i++)
  	{
  	  sd->F[buf[i]]++;
  	  oldv = (oldv & 0xffff) << 8 | buf[i];
  	  V[i - 2] = oldv + 2;
          }
        oldv = (oldv & 0xffff) << 8;
        V[len - 2] = oldv + 2;
        oldv = (oldv & 0xffff) << 8;
        V[len - 1] = oldv + 2;
        len += 2;
        V[len - 2] = 1;
        V[len - 1] = 0;
        h = 3;
      }
    else
      {
        s = 0x10001;
        sd->F[buf[0]]++;
        oldv = buf[0];
        for (i = 1; i < len; i++)
  	{
  	  sd->F[buf[i]]++;
  	  oldv = (oldv & 0xff) << 8 | buf[i];
  	  V[i - 1] = oldv + 1;
  	}
        oldv = (oldv & 0xff) << 8;
        V[len - 1] = oldv + 1;
        len += 1;
        V[len - 1] = 0;
        h = 2;
      }
    oldv = len;
    for (i = 256; i > 0; i--)
      {
        sd->F[i] = oldv;
        oldv -= sd->F[i - 1];
      }
    sd->F[0] = oldv;
    if (!suf_bucketsort(V, I, len, s))
      {
        free(I);
        free(V);
        free(sd);
        return 0;
      }
    for(; I[0] != -(len + 1); h += h)
      {
        l=0;
        for (i = 0; i < len + 1; )
  	{
            if (I[i] < 0)
  	    {
                l -= I[i];
                i -= I[i];
              }
  	  else
  	    {
                if(l)
  		 I[i - l] = -l;
                l = V[I[i]] + 1 - i;
                suf_split(I, V, i, l, h);
                i += l;
                l = 0;
              }
          }
        if (l)
  	 I[i - l] = -l;
      }
    for (i = 0; i < len + 1; i++)
      I[V[i]] = i;
    free(V);
    sd->I = I;
    return sd;
  }
  
  static void suf_free(void *data)
  {
    struct suf_data *sd = data;
    free(sd->I);
    free(sd);
  }
  
  static bsuint suf_bsearch(bsint *I, unsigned char *old, bsuint oldlen, unsigned char *new, bsuint newlen, bsuint st, bsuint en, bsuint *posp)
  {
    bsuint x, y;
    if (st > en)
      return 0;
    while (en - st >= 2)
      {
        x = st + (en - st) / 2;
        if (memcmp(old + I[x], new, oldlen - I[x] < newlen ? oldlen - I[x] : newlen) < 0)
  	st = x;
        else
  	en = x;
      }
    x = matchlen(old + I[st], oldlen - I[st], new, newlen);
    y = matchlen(old + I[en], oldlen - I[en], new, newlen);
    *posp = x > y ? I[st] : I[en];
    return x > y ? x : y;
  }
  
  static bsuint suf_findnext(void *data, unsigned char *old, bsuint oldlen, unsigned char *new, bsuint newlen, bsuint lastoffset, bsuint scan, bsuint *posp, bsuint *lenp)
  {
    bsuint scsc, oldscore, len;
  
    struct suf_data *sd = data;
    len = 0;
    *posp = 0;
    scsc = scan;
    oldscore = 0;
    while (scan < newlen)
      {
        len = suf_bsearch(sd->I, old, oldlen, new + scan, newlen - scan, sd->F[new[scan]] + 1, sd->F[new[scan] + 1], posp);
        for (; scsc < scan + len; scsc++)
  	if (scsc + lastoffset < oldlen && old[scsc + lastoffset] == new[scsc])
  	  oldscore++;
        if (len && len == oldscore)
  	{
  	  scan += len;
  	  scsc = scan;
  	  oldscore = 0;
  	  continue;
  	}
        if (len > oldscore + 32)
  	break;
        if (scan + lastoffset < oldlen && old[scan + lastoffset] == new[scan])
  	oldscore--;
        scan++;
      }
    *lenp = len;
    return scan;
  }
  
  #endif /* BSDIFF_NO_SUF */
  
  /******************************************************************/
  
  struct deltamode {
    int mode;
    void *(*create)(unsigned char *buf, bsuint len);
    bsuint (*findnext)(void *data, unsigned char *old, bsuint oldlen, unsigned char *new, bsuint newlen, bsuint lastoffset, bsuint scan, bsuint *posp, bsuint *lenp);
    void (*free)(void *data);
  };
  
  struct deltamode deltamodes[] =
  {
  #ifndef BSDIFF_NO_SUF
    {DELTAMODE_SUF, suf_create, suf_findnext, suf_free}, 
  #endif
  #ifndef BSDIFF_NO_HASH
    {DELTAMODE_HASH, hash_create, hash_findnext, hash_free},
  #endif
  };
  
  static void addoff(struct bzblock *bzi, bsint off)
  {
    int i, sign = 0;
    unsigned char b[8];
  
    if (off < 0)
      {
        sign = 0x80;
        off = -off;
      }
    for (i = 0; i < 7; i++)
      {
        b[i] = off & 0xff;
        off >>= 8;
      }
    b[7] = sign | (off & 0xff);
    blockwrite(bzi, b, 8);
  }
  
  void mkdiff(int mode,
              unsigned char *old, bsuint oldlen,
              unsigned char *new, bsuint newlen,
              struct instr **instrp, int *instrlenp,
              unsigned char **instrblkp, unsigned int *instrblklenp,
              unsigned char **addblkp, unsigned int *addblklenp,
              unsigned char **extrablkp, unsigned int *extrablklenp)
  {
    struct instr *instr = 0;
    int instrlen = 0;
    bsuint i, scan, pos, len;
    bsuint lastscan, lastpos, lastoffset;
    bsuint s, Sf, lenf, Sb, lenb;
    bsuint overlap, Ss, lens;
    struct bzblock *bza = 0;
    struct bzblock *bze = 0;
    struct bzblock *bzi = 0;
    void *data;
    struct deltamode *dm;
    int noaddblk = 0;
  
    if ((mode & DELTAMODE_NOADDBLK) != 0)
      {
        mode ^= DELTAMODE_NOADDBLK;
        noaddblk = 1;
      }
    dm = 0;
    for (i = 0; i < sizeof(deltamodes)/sizeof(*deltamodes); i++)
      {
        dm = deltamodes + i;
        if (deltamodes[i].mode == mode)
  	break;
      }
    if (!dm)
      {
        fprintf(stderr, "mkdiff: no mode installed\n");
        exit(1);
      }
    if (addblkp)
      {
        *addblkp = 0;
        *addblklenp = 0;
      }
    if (extrablkp)
      {
        *extrablkp = 0;
        *extrablklenp = 0;
      }
    if (instrblkp)
      {
        *instrblkp = 0;
        *instrblklenp = 0;
      }
    if (!noaddblk && addblkp && (bza = blockopen()) == 0)
      {
        fprintf(stderr, "mkdiff: could not create compression stream\n");
        exit(1);
      }
    if (extrablkp && (bze = blockopen()) == 0)
      {
        fprintf(stderr, "mkdiff: could not create compression stream\n");
        exit(1);
      }
    if (instrblkp && (bzi = blockopen()) == 0)
      {
        fprintf(stderr, "mkdiff: could not create compression stream\n");
        exit(1);
      }
    data = dm->create(old, oldlen);
    if (!data)
      {
        fprintf(stderr, "mkdiff: could not create data\n");
        exit(1);
      }
  
    scan = 0; len = 0; lenf = 0;
    lastscan = 0; lastpos = 0;
  
    while (lastscan < newlen)
      {
        /* search for data matching something in new[scan...]
         * input:
         *   old/oldlen, new/newlen: search data
         *   lastoffset: lastpos - lastscan  (because we want to find a different match)
         * returns:
         *   scan: start of match in new[]
         *   pos:  start of match in old[]
         *   len:  length of match
         * (if no match is found, scan = newlen, len = 0)
         */
        lastoffset = noaddblk ? oldlen : lastpos - lastscan;
        scan = dm->findnext(data, old, oldlen, new, newlen, lastoffset, scan, &pos, &len);
  
        /* extand old match forward */
        if (!noaddblk)
  	{
  	  s = Sf = lenf = 0;
  	  for (i = 0; lastscan + i < scan && lastpos + i < oldlen; )
  	    {
  	      if (old[lastpos+i] == new[lastscan+i])
  		{
  		  s++;
  		  i++;
  		  if (s >= Sf + i - s)
  		    {
  		      Sf = 2 * s - i;
  		      lenf = i;
  		    }
  		}
  	      else
  	        i++;
  	    }
  	}
        else
  	{
  	  for (i = 0; lastscan + i < scan && lastpos + i < oldlen; i++)
  	    if (old[lastpos+i] != new[lastscan+i])
  	      break;
  	  lenf = i;
  	}
  
        lenb = 0;
        /* extand new match backward, scan == newlen means we're going to finish */
        if (!noaddblk && scan < newlen)
  	{
  	  s = Sb = 0;
  	  for(i = 1; scan >= lastscan + i && pos >= i; i++)
  	    {
  	      if (old[pos-i] == new[scan-i])
  		{
  		  s++;
  		  if(s >= Sb + i - s)
  		    {
  		      Sb = 2 * s - i;
  		      lenb = i;
  		    }
  		}
  	    }
  	}
  
        /* if there is an overlap find good place to split */
        if (lastscan + lenf > scan - lenb)
  	{
  	  overlap = (lastscan + lenf) - (scan - lenb);
  	  s = Sb = Ss = lens = 0;
  	  for (i = 0; i < overlap; i++)
  	    {
  	      if(new[lastscan + lenf - overlap + i] == old[lastpos + lenf - overlap + i])
  		s++;
  	      if(new[scan - lenb + i] == old[pos - lenb + i])
  		Sb++;
  	      if (s > Sb && s - Sb > Ss)
  		{
  		  Ss = s - Sb;
  		  lens = i + 1;
  		}
  	    }
  	  lenf -= overlap - lens;
  	  lenb -= lens;
  	}
  
        /*
         *         lastscan                    scan
         *            |--- lenf ---|    |- lenb -|-- len --|
         *            |            |    |        |         |
         * new: ------+=======-----+----+--------+=========+--
         *           /                           \
         *          /                             |
         * old: ---+=======-----------------------+=========---
         *         |                              |
         *      lastpos                          pos
         */
  
        if (instrp)
  	{
  	  if ((instrlen & 31) == 0)
  	    {
  	      if (instr)
  	        instr = realloc(instr, sizeof(*instr) * (instrlen + 32));
  	      else
  	        instr = malloc(sizeof(*instr) * (instrlen + 32));
  	      if (!instr)
  		{
  		  fprintf(stderr, "out of memory\n");
  		  exit(1);
  		}
  	    }
  	  instr[instrlen].copyout = lenf;
  	  instr[instrlen].copyin = (scan - lenb) - (lastscan + lenf);
  	  instr[instrlen].copyinoff = lastscan + lenf;
  	  instr[instrlen].copyoutoff = lastpos;
  	  instrlen++;
  	}
        if (bzi)
  	{
  	  addoff(bzi, lenf);
  	  addoff(bzi, (scan - lenb) - (lastscan + lenf));
  	  addoff(bzi, (pos - lenb) - (lastpos + lenf));
  	}
        if (bze)
  	{
  	  i = lastscan + lenf;
  	  s = (scan - lenb) - i;
  	  while (s > 0)
  	    {
  	      int len2 = s > 0x40000000 ? 0x40000000 : s;
  	      blockwrite(bze, new + i, len2);
  	      i += len2;
  	      s -= len2;
  	    }
  	}
        if (bza)
  	{
  	  while (lenf > 0)
  	    {
  	      unsigned char addblk[4096];
  	      int len2;
  	      len2 = lenf > 4096 ? 4096 : lenf;
  	      for (i = 0; i < len2; i++)
  		addblk[i] = new[lastscan + i] - old[lastpos + i];
  	      if (blockwrite(bza, addblk, len2) != len2)
  		{
  		  fprintf(stderr, "could not append to data block\n");
  		  exit(1);
  		}
  	      lastscan += len2;
  	      lastpos += len2;
  	      lenf -= len2;
  	    }
  	}
  
        /* advance */
        lastscan = scan - lenb;
        lastpos = pos - lenb;
        scan += len;
      }
    if (bza && blockclose(bza, addblkp, addblklenp))
      {
        fprintf(stderr, "could not close data block\n");
        exit(1);
      }
    if (bze && blockclose(bze, extrablkp, extrablklenp))
      {
        fprintf(stderr, "could not close extra block\n");
        exit(1);
      }
    if (bzi && blockclose(bzi, instrblkp, instrblklenp))
      {
        fprintf(stderr, "could not close instr block\n");
        exit(1);
      }
    if (instrp)
      {
        *instrp = instr;
        *instrlenp = instrlen;
      }
    dm->free(data);
  }
  
  struct stepdata {
    struct deltamode *dm;
    void *data;
    int noaddblk;
  };
  
  void *
  mkdiff_step_setup(int mode)
  {
    int noaddblk = 0;
    struct stepdata *sd;
    struct deltamode *dm;
    int i;
  
    if ((mode & DELTAMODE_NOADDBLK) != 0)
      {
        mode ^= DELTAMODE_NOADDBLK;
        noaddblk = 1;
      }
    dm = 0;
    for (i = 0; i < sizeof(deltamodes)/sizeof(*deltamodes); i++)
      {
        dm = deltamodes + i;
        if (deltamodes[i].mode == mode)
  	break;
      }
    if (!dm)
      {
        fprintf(stderr, "mkdiff: no mode installed\n");
        exit(1);
      }
    sd = calloc(1, sizeof(*sd));
    if (!sd)
      return 0;
    sd->dm = dm;
    sd->data = 0;
    sd->noaddblk = noaddblk;
    return sd;
  }
  
  void
  mkdiff_step(void *sdata,
              unsigned char *old, bsuint oldlen,
              unsigned char *new, bsuint newlen,
              struct instr *instr,
  	    bsuint *scanp, bsuint *lastposp, bsuint *lastscanp)
    
  {
    struct stepdata *sd = sdata;
    struct deltamode *dm = sd->dm;
    bsuint scan, lastpos, lastscan;
    bsuint pos, len, lastoffset;
    bsuint s, Sf, lenf, Sb, lenb;
    bsuint overlap, Ss, lens;
    bsuint i;
  
    if (!sd->data)
      {
        sd->data = dm->create(old, oldlen);
        if (!sd->data)
  	{
  	  fprintf(stderr, "mkdiff: could not create data\n");
  	  exit(1);
  	}
      }
    scan = *scanp;
    lastscan = *lastscanp;
    lastpos = *lastposp;
  
    lastoffset = sd->noaddblk ? oldlen : lastpos - lastscan;
    scan = dm->findnext(sd->data, old, oldlen, new, newlen, lastoffset, scan, &pos, &len);
    if (!sd->noaddblk)
      {
        s = Sf = lenf = 0;
        for (i = 0; lastscan + i < scan && lastpos + i < oldlen; )
  	{
  	  if (old[lastpos+i] == new[lastscan+i])
  	    {
  	      s++;
  	      i++;
  	      if (s >= Sf + i - s)
  		{
  		  Sf = 2 * s - i;
  		  lenf = i;
  		}
  	    }
  	  else
  	    i++;
  	}
      }
    else
      {
        for (i = 0; lastscan + i < scan && lastpos + i < oldlen; i++)
  	if (old[lastpos+i] != new[lastscan+i])
  	  break;
        lenf = i;
      }
  
    lenb = 0;
    /* extand new match backward, scan == newlen means we're going to finish */
    if (!sd->noaddblk && scan < newlen)
      {
        s = Sb = 0;
        for(i = 1; scan >= lastscan + i && pos >= i; i++)
  	{
  	  if (old[pos-i] == new[scan-i])
  	    {
  	      s++;
  	      if(s >= Sb + i - s)
  		{
  		  Sb = 2 * s - i;
  		  lenb = i;
  		}
  	    }
  	}
      }
  
    /* if there is an overlap find good place to split */
    if (lastscan + lenf > scan - lenb)
      {
        overlap = (lastscan + lenf) - (scan - lenb);
        s = Sb = Ss = lens = 0;
        for (i = 0; i < overlap; i++)
  	{
  	  if(new[lastscan + lenf - overlap + i] == old[lastpos + lenf - overlap + i])
  	    s++;
  	  if(new[scan - lenb + i] == old[pos - lenb + i])
  	    Sb++;
  	  if (s > Sb && s - Sb > Ss)
  	    {
  	      Ss = s - Sb;
  	      lens = i + 1;
  	    }
  	}
        lenf -= overlap - lens;
        lenb -= lens;
      }
  
    /* printf("MATCH len %d @ %d:%d-%d-%d:%d -- %d\n", len, lastscan, lenf, (scan - lenb) - (lastscan + lenf), lenb, scan, pos); */
  
    instr->copyout = lenf;
    instr->copyin = (scan - lenb) - (lastscan + lenf);
    instr->copyinoff = lastscan + lenf;
    instr->copyoutoff = lastpos;
    *scanp = scan + len;
    *lastscanp = scan - lenb;
    if (scan != newlen)
      *lastposp = pos - lenb;
    else
      *lastposp = lastpos + lenf;
  }
  
  void
  mkdiff_step_freedata(void *sdata)
  {
    struct stepdata *sd = sdata;
    struct deltamode *dm = sd->dm;
    if (sd->data)
      dm->free(sd->data);
    sd->data = 0;
  }
  
  void
  mkdiff_step_free(void *sdata)
  {
    struct stepdata *sd = sdata;
    struct deltamode *dm = sd->dm;
    if (sd->data)
      dm->free(sd->data);
    free(sd);
  }
  