Logo Search packages:      
Sourcecode: ksh version File versions

vddelta01.c

/***********************************************************************
*                                                                      *
*               This software is part of the ast package               *
*           Copyright (c) 1995-2007 AT&T Knowledge Ventures            *
*                      and is licensed under the                       *
*                  Common Public License, Version 1.0                  *
*                      by AT&T Knowledge Ventures                      *
*                                                                      *
*                A copy of the License is available at                 *
*            http://www.opensource.org/licenses/cpl1.0.txt             *
*         (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9)         *
*                                                                      *
*              Information and Software Systems Research               *
*                            AT&T Research                             *
*                           Florham Park NJ                            *
*                                                                      *
*                   Phong Vo <kpv@research.att.com>                    *
*                                                                      *
***********************************************************************/
#include    "vdelhdr01.h"

/*    Compute a transformation that takes source data to target data
**
**    Written by Kiem-Phong Vo, kpv@research.att.com, 5/20/94
*/

#ifdef DEBUG
long  S_copy, S_add;    /* amount of input covered by COPY and ADD      */
long  N_copy, N_add;    /* # of COPY and ADD instructions         */
long  M_copy, M_add;    /* max size of a COPY or ADD instruction  */
long  N_merge;    /* # of merged instructions               */
#endif

#define MERGABLE(a,c,k) ((a) > 0 && A_ISTINY(a) && \
                   (c) > 0 && C_ISTINY(c) && \
                   (k) >= K_SELF )

typedef struct _match_s Match_t;
typedef struct _table_s Table_t;
struct _match_s
{     Match_t*    next;       /* linked list ptr      */
};
struct _table_s
{     Vdio_t            io;         /* io structure         */
      uchar*            src;        /* source string  */
      int         n_src;
      uchar*            tar;        /* target string  */
      int         n_tar;
      K_DDECL(quick,recent,rhere);  /* address caches */
      Match_t*    base;       /* base of elements     */
      int         size;       /* size of hash table   */
      Match_t**   table;            /* hash table           */
};

/* encode and output delta instructions */
#if __STD_C
static int vdputinst(Table_t* tab, uchar* begs, uchar* here, Match_t* match, int n_copy)
#else
static int vdputinst(tab, begs, here, match, n_copy)
Table_t*    tab;
uchar*            begs; /* ADD data if any      */
uchar*            here; /* current location     */
Match_t*    match;      /* best match if any    */
int         n_copy;     /* length of match      */
#endif
{
      reg int     n_add, i_add, i_copy, k_type;
      reg int     n, c_addr, copy, best, d;

      n_add = begs ? here-begs : 0;       /* add size       */
      c_addr = (here-tab->tar)+tab->n_src;      /* current address      */
      k_type = 0;

      if(match)   /* process the COPY instruction */
      {     /**/DBTOTAL(N_copy,1); DBTOTAL(S_copy,n_copy); DBMAX(M_copy,n_copy);

            best = copy = match - tab->base;
            k_type = K_SELF;
            if((d = c_addr - copy) < best)
            {     best = d;
                  k_type = K_HERE;
            }
            for(n = 0; n < K_RTYPE; ++n)
            {     if((d = copy - tab->recent[n]) < 0 || d >= best)
                        continue;
                  best = d;
                  k_type = K_RECENT+n;
            }
            if(best >= I_MORE && tab->quick[n = copy%K_QSIZE] == copy)
            {     for(d = K_QTYPE-1; d > 0; --d)
                        if(n >= (d<<VD_BITS) )
                              break;
                  best = n - (d<<VD_BITS); /**/ASSERT(best < (1<<VD_BITS));
                  k_type = K_QUICK+d;
            }

            /**/ASSERT(best >= 0);
            /**/ASSERT((k_type+K_MERGE) < (1<<I_BITS) );

            /* update address caches */
            K_UPDATE(tab->quick,tab->recent,tab->rhere,copy);

            /* see if mergable to last ADD instruction */
            if(MERGABLE(n_add,n_copy,k_type) )
            {     /**/DBTOTAL(N_merge,1);
                  i_add = K_TPUT(k_type)|A_TPUT(n_add)|C_TPUT(n_copy);
            }
            else
            {     i_copy = K_PUT(k_type);
                  if(C_ISLOCAL(n_copy) )
                        i_copy |= C_LPUT(n_copy);
            }
      }

      if(n_add > 0)
      {     /**/DBTOTAL(N_add,1); DBTOTAL(S_add,n_add); DBMAX(M_add,n_add);

            if(!MERGABLE(n_add,n_copy,k_type) )
                  i_add = A_ISLOCAL(n_add) ? A_LPUT(n_add) : 0;

            if(VDPUTC((Vdio_t*)tab,i_add) < 0 )
                  return -1;
            if(!A_ISLOCAL(n_add) &&
               (*_Vdputu)((Vdio_t*)tab, (ulong)A_PUT(n_add)) < 0 )
                  return -1;
            if((*_Vdwrite)((Vdio_t*)tab, begs, n_add) < 0 )
                  return -1;
      }

      if(n_copy > 0)
      {     if(!MERGABLE(n_add,n_copy,k_type) && VDPUTC((Vdio_t*)tab,i_copy) < 0 )
                  return -1;

            if(!C_ISLOCAL(n_copy) &&
               (*_Vdputu)((Vdio_t*)tab, (ulong)C_PUT(n_copy)) < 0 )
                  return -1;

            if(k_type >= K_QUICK && k_type < (K_QUICK+K_QTYPE) )
            {     if(VDPUTC((Vdio_t*)tab,(uchar)best) < 0 )
                        return -1;
            }
            else
            {     if((*_Vdputu)((Vdio_t*)tab, (ulong)best) < 0 )
                        return -1;
            }
      }
      else
      {     if((*_Vdflsbuf)((Vdio_t*)tab) < 0)
                  return -1;
      }

      return 0;
}


/* Fold a string */
#if __STD_C
static int vdfold(Table_t* tab, int output)
#else
static int vdfold(tab, output)
Table_t*    tab;
int         output;
#endif
{
      reg ulong   key, n;
      reg uchar   *s, *sm, *ends, *ss, *heade;
      reg Match_t *m, *list, *curm, *bestm;
      reg uchar   *add, *endfold;
      reg int           head, len, n_src = tab->n_src;
      reg int           size = tab->size;
      reg uchar   *src = tab->src, *tar = tab->tar;
      reg Match_t *base = tab->base, **table = tab->table;

      if(!output)
      {     if(tab->n_src < M_MIN)
                  return 0;
            endfold = (s = src) + tab->n_src;
            curm = base;
      }
      else
      {     endfold = (s = tar) + tab->n_tar;
            curm = base+n_src;
            if(tab->n_tar < M_MIN)
                  return vdputinst(tab,s,endfold,NIL(Match_t*),0);
      }

      add = NIL(uchar*);
      bestm = NIL(Match_t*);
      len = M_MIN-1;
      HINIT(key,s,n);
      for(;;)
      {     for(;;)     /* search for the longest match */
            {     if(!(m = table[key&size]) )
                        goto endsearch;
                  list = m = m->next;     /* head of list */

                  if(bestm) /* skip over past elements */
                  {     for(;;)
                        {     if(m >= bestm+len)
                                    break;
                              if((m = m->next) == list)
                                    goto endsearch;
                        }
                  }

                  head = len - (M_MIN-1); /* header before the match */
                  heade = s+head;
                  for(;;)
                  {     if((n = m-base) < n_src)
                        {     if(n < head)
                                    goto next;
                              sm = src + n;
                        }
                        else
                        {     if((n -= n_src) < head)
                                    goto next;
                              sm = tar + n;
                        }

                        /* make sure that the M_MIN bytes match */
                        if(!EQUAL(heade,sm))
                              goto next;

                        /* make sure this is a real match */
                        for(sm -= head, ss = s; ss < heade; )
                              if(*sm++ != *ss++)
                                    goto next;
                        ss += M_MIN;
                        sm += M_MIN;
                        ends = endfold;
                        if((m-base) < n_src && (n = (src+n_src)-sm) < (ends-s) )
                              ends = s+n;
                        for(; ss < ends; ++ss, ++sm)
                              if(*sm != *ss)
                                    goto extend;
                        goto extend;

                  next: if((m = m->next) == list )
                              goto endsearch;
                  }

            extend: bestm = m-head;
                  n = len;
                  len = ss-s;
                  if(ss >= endfold) /* already match everything */
                        goto endsearch;

                  /* check for a longer match */
                  ss -= M_MIN-1;
                  if(len == n+1)
                        HNEXT(key,ss,n);
                  else  HINIT(key,ss,n);
            }

      endsearch:
            if(bestm)
            {     if(output && vdputinst(tab,add,s,bestm,len) < 0)
                        return -1;

                  /* add a sufficient number of suffices */
                  ends = (s += len);
                  ss = ends - (M_MIN-1);
                  if(!output)
                        curm = base + (ss-src);
                  else  curm = base + n_src + (ss-tar);

                  len = M_MIN-1;
                  add = NIL(uchar*);
                  bestm = NIL(Match_t*);
            }
            else
            {     if(!add)
                        add = s;
                  ss = s;
                  ends = (s += 1);  /* add one prefix */
            }

            if(ends > (endfold - (M_MIN-1)) )
                  ends = endfold - (M_MIN-1);

            if(ss < ends) for(;;)   /* add prefices/suffices */
            {     n = key&size;
                  if(!(m = table[n]) )
                        curm->next = curm;
                  else
                  {     curm->next = m->next;
                        m->next = curm;
                  }
                  table[n] = curm++;

                  if((ss += 1) >= ends)
                        break;
                  HNEXT(key,ss,n);
            }

            if(s > endfold-M_MIN)   /* too short to match */
            {     if(!add)
                        add = s;
                  break;
            }

            HNEXT(key,s,n);
      }

      if(output)  /* flush output */
            return vdputinst(tab,add,endfold,NIL(Match_t*),0);
      return 0;
}


#if __STD_C
long _vddelta_01(Vddisc_t* source, Vddisc_t* target, Vddisc_t* delta, long window)
#else
long _vddelta_01(source, target, delta, window)
Vddisc_t*   source;     /* source data                */
Vddisc_t*   target;     /* target data                */
Vddisc_t*   delta;      /* transform output data      */
long        window;     /* amount to process each time      */
#endif
{
      reg int           size, k, n;
      reg long    p, n_src, n_tar;
      Table_t           tab;

      if(!target || (n_tar = target->size) < 0)
            return -1;
      if(n_tar > 0 && !target->data && !target->readf)
            return -1;

      if((n_src = source ? source->size : 0) < 0)
            n_src = 0;
      if(n_src > 0 && !source->data && !source->readf)
            return -1;

      if(!delta || (!delta->data && !delta->writef) )
            return -1;

      tab.n_src = tab.n_tar = tab.size = 0;
      tab.tar = tab.src = NIL(uchar*);
      tab.base = NIL(Match_t*);
      tab.table = NIL(Match_t**);
      INIT(&tab.io,delta);

      if(window <= 0)
            window = DFLTWINDOW;
      else if(window > MAXWINDOW)
            window = MAXWINDOW;
      if(window > n_tar)
            window = n_tar;
      if(n_src > 0 && window > n_src)
            window = n_src;

      /* try to allocate working space */
      while(window > 0)
      {     /* space for the target string */
            size = (n_tar == 0 || target->data) ? 0 : (int)window;
            if((long)size > n_tar)
                  size = (int)n_tar;
            if(size > 0 && !(tab.tar = (uchar*)malloc(size*sizeof(uchar))) )
                  goto reduce_window;

            /* space for sliding header or source string */
            if(n_src <= 0)    /* compression only */
                  size = target->data ? 0 : HEADER(window);
            else        /* differencing */
            {     size = source->data ? 0 : window;
                  if((long)size > n_src)
                        size = (int)n_src;
            }
            if(size > 0 && !(tab.src = (uchar*)malloc(size*sizeof(uchar))) )
                  goto reduce_window;

            /* space for the hash table elements */
            size = (int)(window < n_tar ? window : n_tar);
            if(n_src <= 0)
                  size += (int)(window < n_tar ? HEADER(window) : 0);
            else  size += (int)(window < n_src ? window : n_src);
            if(!(tab.base = (Match_t*)malloc(size*sizeof(Match_t))) )
                  goto reduce_window;

            /* space for the hash table */
            n = size/2;
            do (size = n); while((n &= n-1) != 0);
            if(size < 64)
                  size = 64;
            while(!(tab.table = (Match_t**)malloc(size*sizeof(Match_t*))) )
                  if((size >>= 1) <= 0)
                        goto reduce_window;

            /* if get here, successful */
            tab.size = size-1;
            break;

      reduce_window:
            if(tab.tar)
            {     free((Void_t*)tab.tar);
                  tab.tar = NIL(uchar*);
            }
            if(tab.src)
            {     free((Void_t*)tab.src);
                  tab.src = NIL(uchar*);
            }
            if(tab.base)
            {     free((Void_t*)tab.base);
                  tab.base = NIL(Match_t*);
            }
            if((window >>= 1) <= 0)
                  return -1;
      }

      /* amount processed */
      n = 0;

      /* output magic bytes and sizes */
      for(k = 0; VD_MAGIC[k]; k++)
            ;
      if((*_Vdwrite)(&tab.io,(uchar*)VD_MAGIC,k) != k ||
         (*_Vdputu)(&tab.io,(ulong)n_tar) <= 0 ||
         (*_Vdputu)(&tab.io,(ulong)n_src) <= 0 ||
         (*_Vdputu)(&tab.io,(ulong)window) <= 0 )
            goto done;

      /* do one window at a time */
      while(n < n_tar)
      {     /* prepare the source string */
            if(n_src <= 0)    /* data compression */
            {     if(n <= 0)
                        tab.n_src = 0;
                  else
                  {     size = (int)HEADER(window);
                        if(target->data)
                              tab.src = tab.tar + tab.n_tar - size;
                        else  memcpy((Void_t*)tab.src,
                                     (Void_t*)(tab.tar + tab.n_tar - size),
                                     size );
                        tab.n_src = size;
                  }
            }
            else  /* data differencing */
            {     if(n < n_src)
                  {     if(n+window > n_src)
                              p = n_src-window;
                        else  p = n;
                        if(source->data)
                              tab.src = (uchar*)source->data + p;
                        else
                        {     size = (*source->readf)
                                    (tab.src, (int)window, p, source);
                              if((long)size != window)
                                    goto done;
                        }
                  } /* else use last window */

                  tab.n_src = window;
            }

            /* prepare the target string */
            size = (int)((n_tar-n) < window ? (n_tar-n) : window);
            tab.n_tar = size;
            if(target->data)
                  tab.tar = (uchar*)target->data + n;
            else
            {     size = (*target->readf)(tab.tar, size, (long)n, target);
                  if((long)size != tab.n_tar)
                        goto done;
            }

            /* reinitialize table before processing */
            for(k = tab.size; k >= 0; --k)
                  tab.table[k] = NIL(Match_t*);
            K_INIT(tab.quick,tab.recent,tab.rhere);

            if(tab.n_src > 0 && vdfold(&tab,0) < 0)
                  goto done;
            if(vdfold(&tab,1) < 0)
                  goto done;

            n += size;
      }

done:
      if(!target->data && tab.tar)
            free((Void_t*)tab.tar);
      if(tab.src && ((n_src <= 0 && !target->data) || (n_src > 0 && !source->data) ) )
            free((Void_t*)tab.src);
      if(tab.base)
            free((Void_t*)tab.base);
      if(tab.table)
            free((Void_t*)tab.table);

      return tab.io.here + (tab.io.next - tab.io.data);
}

Generated by  Doxygen 1.6.0   Back to index