/***********************************************************************
* *
* This software is part of the ast package *
* Copyright (c) 2003-2011 AT&T Intellectual Property *
* and is licensed under the *
* Eclipse Public License, Version 1.0 *
* by AT&T Intellectual Property *
* *
* A copy of the License is available at *
* http://www.eclipse.org/org/documents/epl-v10.html *
* (with md5 checksum b35adb5213ca9657e911e9befb180842) *
* *
* Information and Software Systems Research *
* AT&T Research *
* Florham Park NJ *
* *
* Phong Vo <kpv@research.att.com> *
* *
***********************************************************************/
#include <vclib.h>
/* Move-to-front transformers.
**
** Written by Kiem-Phong Vo (kpv@research.att.com)
*/
typedef ssize_t (*Mtf_f)_ARG_((Vcchar_t*, Vcchar_t*, Vcchar_t*, int));
static ssize_t mtfp _ARG_((Vcchar_t*, Vcchar_t*, Vcchar_t*, int));
static ssize_t mtf0 _ARG_((Vcchar_t*, Vcchar_t*, Vcchar_t*, int));
#define MTFC(c,p,m,n) /* know byte, need to compute position */ \
{ m = mtf[p = 0]; \
while(m != c) \
{ n = mtf[p += 1]; mtf[p] = m; m = n; } \
mtf[0] = c; \
}
#define MTFP(c,p,m,n) /* know position, need to compute byte */ \
{ c = mtf[m = 0]; \
while(m != p) \
{ n = mtf[m += 1]; mtf[m] = c; c = n; } \
mtf[0] = c; \
}
/* arguments to select move-to-front coder */
static Vcmtarg_t _Mtfargs[] =
{ { "0", "Pure move-to-front strategy.", (Void_t*)mtf0 },
{ 0 , "Move-to-front with prediction.", (Void_t*)mtfp }
};
#if __STD_C
static ssize_t mtfp(Vcchar_t* dt, Vcchar_t* enddt, Vcchar_t* output, int encoding)
#else
static ssize_t mtfp(dt, enddt, output, encoding)
Vcchar_t* dt; /* data to be un/mtf-ed */
Vcchar_t* enddt;
Vcchar_t* output; /* output array */
int encoding; /* !=0 if encoding */
#endif
{
reg int c, p, m, n, predc;
reg Vcchar_t *o;
Vcchar_t mtf[256], succ[256];
size_t wght[256];
predc = 0;
for(p = 0; p < 256; ++p)
mtf[p] = succ[p] = p;
memset(wght,0,sizeof(wght));
/* weight increases slightly but decreases quickly */
#define SUCC(c,p,m,n) \
{ if(succ[predc] == c) wght[predc] += 4; \
else if((wght[predc] >>= 1) <= 0) \
{ succ[predc] = c; wght[predc] = 1; } \
predc = c; \
if(wght[c] > 1 && (c = succ[c]) != mtf[0] ) \
MTFC(c,p,m,n); /* predicting succ[c] is next */ \
}
if(encoding)
{ for(o = output; dt < enddt; ++dt, ++o )
{ c = *dt; MTFC(c,p,m,n); *o = p;
SUCC(c,p,m,n);
}
}
else
{ for(o = output; dt < enddt; ++dt, ++o )
{ p = *dt; MTFP(c,p,m,n); *o = c;
SUCC(c,p,m,n);
}
}
return o-output;
}
/* move to zeroth location */
#if __STD_C
static ssize_t mtf0(Vcchar_t* dt, Vcchar_t* enddt, Vcchar_t* output, int encoding)
#else
static ssize_t mtf0(dt, enddt, output, encoding)
Vcchar_t* dt; /* data to be un/mtf-ed */
Vcchar_t* enddt;
Vcchar_t* output; /* output array */
int encoding; /* !=0 if encoding */
#endif
{
reg int c, p, m, n;
reg Vcchar_t *o;
Vcchar_t mtf[256];
for(p = 0; p < 256; ++p)
mtf[p] = p;
if(encoding)
{ for(o = output; dt < enddt; ++dt, ++o )
{ c = *dt; MTFC(c,p,m,n); *o = p;
}
}
else
{ for(o = output; dt < enddt; ++dt, ++o )
{ p = *dt; MTFP(c,p,m,n); *o = c;
}
}
return o-output;
}
#if __STD_C
static ssize_t vcmtf(Vcodex_t* vc, const Void_t* data, size_t size, Void_t** out)
#else
static ssize_t vcmtf(vc, data, size, out)
Vcodex_t* vc;
Void_t* data;
size_t size;
Void_t** out;
#endif
{
Vcchar_t *output, *dt;
ssize_t sz;
Mtf_f mtff = vcgetmtdata(vc, Mtf_f);
if((sz = size) == 0)
return 0;
if(!(output = vcbuffer(vc, NIL(Vcchar_t*), sz, 0)) )
RETURN(-1);
if((*mtff)((Vcchar_t*)data, ((Vcchar_t*)data)+sz, output, 1) != sz)
RETURN(-1);
dt = output;
if(vcrecode(vc, &output, &sz, 0, 0) < 0)
RETURN(-1);
if(dt != output)
vcbuffer(vc, dt, -1, -1);
if(out)
*out = output;
return sz;
}
#if __STD_C
static ssize_t vcunmtf(Vcodex_t* vc, const Void_t* data, size_t size, Void_t** out)
#else
static ssize_t vcunmtf(vc, data, size, out)
Vcodex_t* vc;
Void_t* data;
size_t size;
Void_t** out;
#endif
{
Vcchar_t *dt, *output;
ssize_t sz;
Mtf_f mtff = vcgetmtdata(vc, Mtf_f);
if(size == 0)
return 0;
dt = (Vcchar_t*)data; sz = size;
if(vcrecode(vc, &dt, &sz, 0, 0) < 0 )
RETURN(-1);
if(!(output = vcbuffer(vc, NIL(Vcchar_t*), sz, 0)) )
RETURN(-1);
if((*mtff)(dt, dt+sz, output, 0) != sz)
RETURN(-1);
if(dt != (Vcchar_t*)data)
vcbuffer(vc, dt, -1, -1);
if(out)
*out = output;
return sz;
}
#if __STD_C
static ssize_t mtfextract(Vcodex_t* vc, Vcchar_t** datap)
#else
static ssize_t mtfextract(vc, datap)
Vcodex_t* vc;
Vcchar_t** datap; /* basis string for persistence */
#endif
{
Vcmtarg_t *arg;
char *ident;
ssize_t n;
Void_t *mtdt = vcgetmtdata(vc, Void_t*);
for(arg = _Mtfargs;; ++arg)
if(!arg->name || arg->data == mtdt)
break;
if(!arg->name)
return 0;
n = strlen(arg->name);
if(!(ident = (char*)vcbuffer(vc, NIL(Vcchar_t*), sizeof(int)*n+1, 0)) )
RETURN(-1);
if(!(ident = vcstrcode(arg->name, ident, sizeof(int)*n+1)) )
RETURN(-1);
if(datap)
*datap = (Void_t*)ident;
return n;
}
#if __STD_C
static Vcodex_t* mtfrestore(Vcchar_t* data, ssize_t dtsz)
#else
static Vcodex_t* mtfrestore(data, dtsz)
Vcchar_t* data; /* persistence data */
ssize_t dtsz; /* its length */
#endif
{
Vcmtarg_t *arg;
char *ident, buf[1024];
for(arg = _Mtfargs; arg->name; ++arg)
{ if(!(ident = vcstrcode(arg->name, buf, sizeof(buf))) )
return NIL(Vcodex_t*);
if(dtsz == strlen(ident) && strncmp(ident, (Void_t*)data, dtsz) == 0)
break;
}
return vcopen(0, Vcmtf, (Void_t*)arg->name, 0, VC_DECODE);
}
#if __STD_C
static int mtfevent(Vcodex_t* vc, int type, Void_t* params)
#else
static int mtfevent(vc, type, params)
Vcodex_t* vc;
int type;
Void_t* params;
#endif
{
Vcmtarg_t *arg;
Vcmtcode_t *mtcd;
char *data;
if(type == VC_OPENING )
{ for(arg = NIL(Vcmtarg_t*), data = (char*)params; data && *data; )
{ data = vcgetmtarg(data, 0, 0, _Mtfargs, &arg);
if(arg && arg->name)
break;
}
if(!arg) /* get the default argument */
for(arg = _Mtfargs;; ++arg)
if(!arg->name)
break;
vcsetmtdata(vc, arg->data);
return 0;
}
else if(type == VC_EXTRACT)
{ if(!(mtcd = (Vcmtcode_t*)params) )
RETURN(-1);
if((mtcd->size = mtfextract(vc, &mtcd->data)) < 0 )
RETURN(-1);
return 1;
}
else if(type == VC_RESTORE)
{ if(!(mtcd = (Vcmtcode_t*)params) )
RETURN(-1);
if(!(mtcd->coder = mtfrestore(mtcd->data, mtcd->size)) )
RETURN(-1);
return 1;
}
return 0;
}
Vcmethod_t _Vcmtf =
{ vcmtf,
vcunmtf,
mtfevent,
"mtf", "Move-to-front transform.",
"[-version?mtf (AT&T Research) 2003-01-01]" USAGE_LICENSE,
_Mtfargs,
1024*1024,
0
};
VCLIB(Vcmtf)