Logo Search packages:      
Sourcecode: ksh version File versions

vdsqueeze.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    "vdelhdr.h"

/*    Squeeze a string.
**
**    Written by Kiem-Phong Vo, kpv@research.att.com, 2/15/95
*/

#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 _table_s Table_t;
struct _table_s
{     uchar*            delta;            /* output area          */
      uchar*            tar;        /* target string  */
      int         n_tar;
      K_DDECL(quick,recent,rhere);  /* address caches */
      int*        link;       /* base of elements     */
      int         size;       /* size of hash table   */
      int*        hash;       /* hash table           */
};

/* encode and output delta instructions */
#if __STD_C
static int vdputinst(Table_t* tab, uchar* begs, uchar* here, reg int copy, int n_copy)
#else
static int vdputinst(tab, begs, here, copy, n_copy)
Table_t*    tab;
uchar*            begs; /* ADD data if any      */
uchar*            here; /* current location     */
reg int           copy; /* 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, best, d;
      uchar       buf[sizeof(long)+1];

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

      if(copy >= 0)     /* process the COPY instruction */
      {     /**/DBTOTAL(N_copy,1); DBTOTAL(S_copy,n_copy); DBMAX(M_copy,n_copy);

            best = copy;
            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;

            STRPUTC(tab, i_add);
            if(!A_ISLOCAL(n_add) )
                  STRPUTU(tab, (ulong)A_PUT(n_add), buf);
            STRWRITE(tab, begs, n_add);
      }

      if(n_copy > 0)
      {     if(!MERGABLE(n_add,n_copy,k_type))
                  STRPUTC(tab, i_copy);

            if(!C_ISLOCAL(n_copy) )
                  STRPUTU(tab, (ulong)C_PUT(n_copy), buf);

            if(k_type >= K_QUICK && k_type < (K_QUICK+K_QTYPE) )
                  STRPUTC(tab, (uchar)best);
            else  STRPUTU(tab, (ulong)best, buf);
      }

      return 0;
}


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

      endfold = (s = tar) + tab->n_tar;
      curm = 0;
      if(tab->n_tar < M_MIN)
            return vdputinst(tab,s,endfold,-1,0);

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

                  if(bestm >= 0) /* skip over past elements */
                        for(n = bestm+len; m < n;)
                              if((m = link[m]) == list)
                                    goto endsearch;

                  head = len - (M_MIN-1); /* header before the match */
                  heade = s+head;
                  for(;;)
                  {     
                        if((n = m) < 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;
                        for(; ss < ends; ++ss, ++sm)
                              if(*sm != *ss)
                                    goto extend;
                        goto extend;

                  next: if((m = link[m]) == 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 >= 0)
            {     if(vdputinst(tab,add,s,bestm,len) < 0)
                        return -1;

                  /* add a sufficient number of suffices */
                  ends = (s += len);
                  ss = ends - (M_MIN-1);
                  curm = (ss-tar);

                  len = M_MIN-1;
                  add = NIL(uchar*);
                  bestm = -1;
            }
            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 = hash[n]) < 0 )
                        link[curm] = curm;
                  else
                  {     link[curm] = link[m];
                        link[m] = curm;
                  }
                  hash[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);
      }

      return vdputinst(tab,add,endfold,-1,0);
}


#if __STD_C
int vdsqueeze(Void_t* target, reg int size, Void_t* delta)
#else
int vdsqueeze(target, size, delta)
Void_t*     target;
reg int     size;
Void_t*     delta;
#endif
{
      reg int           k, n;
      Table_t           tab;
      uchar       buf[sizeof(long)+1];

      if(size <= 0)
            return 0;
      else if(!target || !delta)
            return -1;

      tab.n_tar = size;
      tab.tar = (uchar*)target;
      tab.delta = (uchar*)delta;
      tab.link = NIL(int*);
      tab.hash = NIL(int*);

      /* space for the hash table */
      k = size;
      n = size/2;
      do (size = n); while((n &= n-1) != 0);
      if(size < 64)
            size = 64;
      k += size;

      if(!(tab.hash = (int*)malloc(k*sizeof(int))) )
            return -1;
      tab.link = tab.hash + size;
      tab.size = size-1;

      /* initialize table before processing */
      for(n = tab.size; n >= 0; --n)
            tab.hash[n] = -1;
      K_INIT(tab.quick,tab.recent,tab.rhere);

      STRPUTU(&tab,tab.n_tar,buf);
      n = vdfold(&tab);

      free((Void_t*)tab.hash);

      return n < 0 ? -1 : (tab.delta - (uchar*)delta);
}

Generated by  Doxygen 1.6.0   Back to index