1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
|
/*
* $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;
}
|
