lbxdelta.c   [plain text]

/*
 * $NCDXorg: @(#)lbxdelta.c,v 1.2 1994/01/22 02:23:40 dct Exp $
 * $Xorg: lbxdelta.c,v 1.5 2000/08/17 19:46:40 cpqbld Exp $
 * $XdotOrg: lib/lbxutil/src/delta/lbxdelta.c,v 1.7 2005/07/30 21:07:25 alanc Exp $
 *
 * Copyright 1993 Network Computing Devices
 *
 * Permission to use, copy, modify, distribute, and sell this software and its
 * documentation for any purpose is hereby granted without fee, provided that
 * the above copyright notice appear in all copies and that both that
 * copyright notice and this permission notice appear in supporting
 * documentation, and that the name of NCD. not be used in advertising or
 * publicity pertaining to distribution of the software without specific,
 * written prior permission.  NCD. makes no representations about the
 * suitability of this software for any purpose.  It is provided "as is"
 * without express or implied warranty.
 *
 * NCD. DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING ALL
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL NCD.
 * BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
 * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN 
 * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 *
 * Author:  Dale Tonogai, Network Computing Devices
 */
/* $XFree86: xc/lib/lbxutil/delta/lbxdelta.c,v 1.7 2001/07/25 15:04:57 dawes Exp $ */

#include <X11/X.h>
#include <X11/Xproto.h>
#define _XLBX_SERVER_
#include <X11/extensions/lbxstr.h>
#include <X11/extensions/lbxdeltastr.h>

#include <stddef.h>
#include <string.h>

#ifdef LBXREQSTATS
#include "../lbx_zlib/reqstats.h"
extern int LbxWhoAmI;
extern struct ReqStats CoreRequestStats[128];
extern struct ReqStats LbxRequestStats[LbxNumberReqs];

#define LBX_CODE 136 /* XXX - this should not be hardcoded - on todo list */
#endif

/* Copied from xc/programs/Xserver/include/xorg/os.h */
#ifndef _HAVE_XALLOC_DECLS
#define _HAVE_XALLOC_DECLS
#include <X11/Xdefs.h>

extern pointer Xalloc(unsigned long /*amount*/);
extern pointer Xcalloc(unsigned long /*amount*/);
extern pointer Xrealloc(pointer /*ptr*/, unsigned long /*amount*/);
extern void Xfree(pointer /*ptr*/);
#endif

/*
 * Allocate data structures needed for doing Delta compaction
 */
int
LBXInitDeltaCache(LBXDeltasPtr	pcache,
		  int		nDeltas,
		  int		maxDeltasize)
{
    int			i;
    unsigned char	*mem;

    if ((pcache->nDeltas = nDeltas)) {
	pcache->maxDeltasize = maxDeltasize;
	if ((pcache->deltas = (LBXDeltaElemPtr)
	    Xalloc(pcache->nDeltas * sizeof(LBXDeltaElemRec) +
		pcache->nDeltas * pcache->maxDeltasize)) == NULL) {
	    return -1;
	}

	mem = (unsigned char *) (pcache->deltas + pcache->nDeltas);
	for (i = 0; i < pcache->nDeltas; i++) {
	    pcache->deltas[i].buf = mem;
	    mem += pcache->maxDeltasize;
	}
    }
    else
	pcache->maxDeltasize = 0;

    pcache->nextDelta = 0;
    pcache->activeDeltas = 0;
    return 0;
}

/*
 * Free data structures used for doing Delta compaction
 */
void
LBXFreeDeltaCache(LBXDeltasPtr pcache)
{
    if (pcache->nDeltas && pcache->deltas)
	Xfree(pcache->deltas);
}

static int 
BytesDiff(unsigned char *ptr1, unsigned char *ptr2,
	  int  n,
	  int  maxn)
{
    int  result = 0;

    while (n--)
	if (*(ptr1++) != *(ptr2++))
	    if (++result >= maxn)
		break;
    return (result);
}

/*
 * Find the message in the outgoing delta cache with the least number of 
 * differing bytes and return the number of differences.  If all
 * messages have greater than maxdiff differences, return -1.
 */
int
LBXDeltaMinDiffs(LBXDeltasPtr	pcache,
		 unsigned char	*inmsg,
		 int		inmsglen,
		 int		maxdiff,
		 int		*pindex)
{
    int			i, j, k = 0, l = maxdiff + 1;
    int		   	m;
    LBXDeltaElemPtr	dm;

    for (m = pcache->nextDelta-1, dm = &pcache->deltas[m], i = 0;
	    i < pcache->activeDeltas;
	    i++, m--, dm--
	) {
	if (m < 0) {
	    m = pcache->nDeltas - 1;
	    dm = &pcache->deltas[m];
	}
	if (dm->length == inmsglen) {
	    j = BytesDiff(inmsg, dm->buf, inmsglen, l);
	    if (j < l) {
		k = m;
		l = j;
	    }
	}
    }

    if (l > maxdiff)
	return -1;
    else {
	*pindex = k;
	return l;
    }
}

/*
 * Delta compact a given message
 */
void
LBXEncodeDelta(LBXDeltasPtr	pcache,
	       unsigned char	*inmsg,
	       int		ndiff,
	       int		index,
	       unsigned char	*buf)
{
    int			i, off, diff;
    xLbxDiffItem	*deltas = (xLbxDiffItem *)buf;

    for (off = i = 0; i < ndiff; off++) {
	if ((diff = inmsg[off] - pcache->deltas[index].buf[off])) {
	    deltas[i].offset = off;
	    deltas[i++].diff = diff;
	}
    }
}

/*
 * Uncompact a message
 */
int
LBXDecodeDelta(LBXDeltasPtr	pcache,
	       xLbxDiffItem	*deltas,
	       int		ndiff,
	       int		index,
	       unsigned char	**buf)
{
    int			i;
    int			newindex = pcache->nextDelta;
    int			len = pcache->deltas[index].length;
    unsigned char	*p = pcache->deltas[newindex].buf;
#ifdef LBXREQSTATS
    xReq		*req;
#endif

    pcache->nextDelta = (pcache->nextDelta + 1) % pcache->nDeltas;
    if (index != newindex) {
	memcpy(p, pcache->deltas[index].buf, len);
	pcache->deltas[newindex].length = len;
    }
    for (i = 0; i < ndiff; i++)
	p[deltas[i].offset] += deltas[i].diff;
    *buf = p;

#ifdef LBXREQSTATS
    req = (xReq *) p;

    if (LbxWhoAmI == 1)		/* server */
    {
	struct ReqStats *reqStat = NULL;

	if (req->reqType == LBX_CODE)
	    reqStat = &LbxRequestStats[req->data];
	else if (req->reqType < 128)
	    reqStat = &CoreRequestStats[req->reqType];

	if (reqStat)
	{
	    reqStat->delta_count++;
	    reqStat->pre_delta_bytes += (req->length << 2);
	    reqStat->post_delta_bytes +=
		(((sz_xLbxDeltaReq + sz_xLbxDiffItem * ndiff + 3) >> 2) << 2);
	}
    }
#endif

    return len;
}

/*
 * Add a message to the outgoing delta cache
 */
void
LBXAddDeltaOut(LBXDeltasPtr	pcache,
	       unsigned char	*inmsg,
	       int		inmsglen)
{
    memcpy(pcache->deltas[pcache->nextDelta].buf, inmsg, inmsglen);
    pcache->deltas[pcache->nextDelta].length = inmsglen;
    pcache->nextDelta = (pcache->nextDelta + 1) % pcache->nDeltas;
    if (pcache->activeDeltas < pcache->nDeltas)
	pcache->activeDeltas++;
}

/*
 * Add a message to the incoming delta cache
 */
void
LBXAddDeltaIn(LBXDeltasPtr	pcache,
	      unsigned char	*inmsg,
	      int		inmsglen)
{
    memcpy(pcache->deltas[pcache->nextDelta].buf, inmsg, inmsglen);
    pcache->deltas[pcache->nextDelta].length = inmsglen;
    pcache->nextDelta = (pcache->nextDelta + 1) % pcache->nDeltas;
}