Re: thoughts on memory usage...

  This message is in MIME format. The first part should be readable text,
  while the remaining parts are likely unreadable without MIME-aware tools.
  Send mail to mime@docserver.cac.washington.edu for more info.

--1602371712-1845522394-871971069=:8099
Content-Type: TEXT/PLAIN; charset=US-ASCII

Re: Michael's suggestoin of a URL compression scheme for in-memory URLs.
I've implemented a simple URL compression scheme as a filter to see how
good this would be, and it seems feasable assuming that the URL can be
encoded/decoded at the right times without causing too many problems.

I'm getting 33% compression (65484675 bytes, including trailing \n's on
disk, into 44138496 bytes) using 10 or so URL prefixes, URL suffixes and
host suffixes. The substrings were just things which I thought up as
'probably fairly common', I'm sure a much better set could be found. I
haven't written the decompress routine to verify this is reversable on all
URLs, but I believe I've considered all quoting, etc, needed.

[note - the trailing \n's on disk are equivalent to trailing \0's in
memory]

I've attached the source code I'm using; I'm not sure how I'll determine
the "optimal" string set or what compression that'll give, hopefully over
33% but probably less than 50%. Then there's the issue of inserting calls
to compress/decompress URLs at interactions with the outside world (Qstn:
should "log" be 'compressed'?).

The "encode" routine probably uses too many malloc()s/free()s. A static
buffer might be the answer (since the code doesn't have to be threadsafe,
and we have a max url length). It could also be sped up by caching the
results of pointer dereferences and strlen calls; I'll do this later. The
"decode" routine is half written, completely broken, and will segfault if
you try to use it.

The source code is currently for Linux, and uses malloc/strdup instead of
xmalloc/xstrdup, but should work on any OS with a strdup() in its libc
(ie, anything with the slightest BSD influence).

/* pfx/sfx strings MUST be sorted in ascending order of string length
 * since the "first longest" match is used.
 *
 * encoding:
 * encode URL PFX
 * * examples assume PFX string A is "http://www."
 * * {full-pfx-match} -> pfx-letter eg http://www. -> A
 * * {partial-pfx-match} -> pfx-letter, len eg http://www- -> A10
 * * quoting - a following numeric, quote with \
 * eg http://www8 -> A\8
 * - quote a following \ eg,
 * http://www.ibm.com/\thingy ->
 * Z\\thingy
 * if PFX string Z was http://www.ibm.com/
 * encode HOST SFX
 * * work back from 3rd / in original URL
 * * full/partial matches, use pfx_char[len] for partials
 * ie. string A = ".x.com"; .y.com/ -> AD/
 * * no quoting of following char since it must be a /
 * * no quoting of preceeding char since it must not be a capital
 * or special in a hostname
 * * do not compress/encode already encoded data
 * encode URL SFX
 * * work back from terminating NULL
 * * do not compress/encode already encoded data
 * * if there is no SFX string, add a # to quote preceeding char
 * if it is a possible SFX char or digit
 * * full/partial matches, as above
 * don't let URL SFX enclose 3rd /
 * if URL PFX has no length element and runs in to HOST SFX, seperate
with !
 * if(strlen(out) > strlen(in) + 1)
 * out = in ++ "#";
 */

/* example output of test prog:
 * http://www20.ibm.com/index.html [31] --> E10\20.A/G [10]
 * (when input: http://www20.ibm.com/index.html)
 */

Opinions, comments, suggestions, anyone?

David.

--1602371712-1845522394-871971069=:8099
Content-Type: TEXT/plain; name="url-comp.c"
Content-Transfer-Encoding: BASE64
Content-ID: <Pine.LNX.3.96.970819141109.8099E@typhaon.ucs.uwa.edu.au>
Content-Description: url-comp.c

I2RlZmluZSBfQlNEX1NPVVJDRSAxDQojaW5jbHVkZSA8Y3R5cGUuaD4NCiNp
bmNsdWRlIDxzdGRpby5oPg0KI2luY2x1ZGUgPG1hbGxvYy5oPg0KI2luY2x1
ZGUgPHN0cmluZ3MuaD4NCg0KLyogcGZ4L3NmeCBzdHJpbmdzIE1VU1QgYmUg
c29ydGVkIGluIGFzY2VuZGluZyBvcmRlciBvZiBzdHJpbmcgbGVuZ3RoDQog
KiBzaW5jZSB0aGUgImZpcnN0IGxvbmdlc3QiIG1hdGNoIGlzIHVzZWQuDQog
Kg0KICogZW5jb2Rpbmc6DQogKiAgIGVuY29kZSBVUkwgUEZYDQogKiAgICAg
ICAgKiBleGFtcGxlcyBhc3N1bWUgUEZYIHN0cmluZyBBIGlzICJodHRwOi8v
d3d3LiINCiAqICAgICAgICAqIHtmdWxsLXBmeC1tYXRjaH0gLT4gcGZ4LWxl
dHRlciAgICAgICAgICBlZyBodHRwOi8vd3d3LiAtPiBBDQogKiAgICAgICAg
KiB7cGFydGlhbC1wZngtbWF0Y2h9IC0+IHBmeC1sZXR0ZXIsIGxlbiAgZWcg
aHR0cDovL3d3dy0gLT4gQTEwDQogKiAgICAgICAgKiBxdW90aW5nIC0gYSBm
b2xsb3dpbmcgbnVtZXJpYywgcXVvdGUgd2l0aCBcDQogKiAgICAgICAgICAg
ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGVnIGh0dHA6
Ly93d3c4IC0+IEFcOA0KICogICAgICAgICAgICAgICAgICAtIHF1b3RlIGEg
Zm9sbG93aW5nIFwgZWcsDQogKiAgICAgICAgICAgICAgICAgICAgICBodHRw
Oi8vd3d3LmlibS5jb20vXHRoaW5neSAtPg0KICogICAgICAgICAgICAgICAg
ICAgICAgICAgICBaXFx0aGluZ3kNCiAqICAgICAgICAgICAgICAgICAgaWYg
UEZYIHN0cmluZyBaIHdhcyBodHRwOi8vd3d3LmlibS5jb20vDQogKiAgIGVu
Y29kZSBIT1NUIFNGWA0KICogICAgICAgICogd29yayBiYWNrIGZyb20gM3Jk
IC8gaW4gb3JpZ2luYWwgVVJMDQogKiAgICAgICAgKiBmdWxsL3BhcnRpYWwg
bWF0Y2hlcywgdXNlIHBmeF9jaGFyW2xlbl0gZm9yIHBhcnRpYWxzDQogKiAg
ICAgICAgICAgICAgICAgICAgICBpZS4gc3RyaW5nIEEgPSAiLnguY29tIjsg
IC55LmNvbS8gLT4gIEFELw0KICogICAgICAgICogbm8gcXVvdGluZyBvZiBm
b2xsb3dpbmcgY2hhciBzaW5jZSBpdCBtdXN0IGJlIGEgLw0KICogICAgICAg
ICogbm8gcXVvdGluZyBvZiBwcmVjZWVkaW5nIGNoYXIgc2luY2UgaXQgbXVz
dCBub3QgYmUgYSBjYXBpdGFsDQogKiAgICAgICAgICBvciBzcGVjaWFsIGlu
IGEgaG9zdG5hbWUNCiAqICAgICAgICAqIGRvIG5vdCBjb21wcmVzcy9lbmNv
ZGUgYWxyZWFkeSBlbmNvZGVkIGRhdGENCiAqICAgZW5jb2RlIFVSTCBTRlgN
CiAqICAgICAgICAqIHdvcmsgYmFjayBmcm9tIHRlcm1pbmF0aW5nIE5VTEwN
CiAqICAgICAgICAqIGRvIG5vdCBjb21wcmVzcy9lbmNvZGUgYWxyZWFkeSBl
bmNvZGVkIGRhdGENCiAqICAgICAgICAqIGlmIHRoZXJlIGlzIG5vIFNGWCBz
dHJpbmcsIGFkZCBhICMgdG8gcXVvdGUgcHJlY2VlZGluZyBjaGFyDQogKiAg
ICAgICAgICBpZiBpdCBpcyBhIHBvc3NpYmxlIFNGWCBjaGFyIG9yIGRpZ2l0
DQogKiAgICAgICAgKiBmdWxsL3BhcnRpYWwgbWF0Y2hlcywgYXMgYWJvdmUN
CiAqICAgZG9uJ3QgbGV0IFVSTCBTRlggZW5jbG9zZSAzcmQgLw0KICogICBp
ZiBVUkwgUEZYIGhhcyBubyBsZW5ndGggZWxlbWVudCBhbmQgcnVucyBpbiB0
byBIT1NUIFNGWCwgc2VwZXJhdGUgd2l0aCAhDQogKiAgIGlmKHN0cmxlbihv
dXQpID4gc3RybGVuKGluKSArIDEpDQogKiAgICAgICBvdXQgPSBpbiArKyAi
IyI7DQogKi8NCg0KLyogZXhhbXBsZSBvdXRwdXQ6DQogKiAgIGh0dHA6Ly93
d3cyMC5pYm0uY29tL2luZGV4Lmh0bWwgWzMxXSAtLT4gRTEwXDIwLkEvRyAg
WzEwXQ0KICovDQoNCnN0YXRpYyBjaGFyICp1cmxfcGZ4X3N0cmluZ3NbMzJd
ID0gew0KICAiZnRwOi8vIiwNCiAgImh0dHA6Ly8iLA0KICAiaHR0cHM6Ly8i
LA0KICAiZnRwOi8vZnRwIiwNCiAgImdvcGhlcjovLyIsDQogICJodHRwOi8v
d3d3IiwNCiAgImh0dHA6Ly93d3cuIiwNCiAgImh0dHA6Ly93ZWIiLA0KICAi
aHR0cDovL3d3dy0iLA0KICAiaHR0cDovL2hvbWUuIiwNCiAgImdvcGhlcjov
L2dvcGh0ZXIuIiwNCiAgImh0dHA6Ly93d3cubmV0c2NhcGUiLA0KICAiaHR0
cDovL3d3dy5wZW50aG91c2VtYWciLA0KICAiIiwNCiAgIiIsDQogICIiLA0K
ICAiIiwNCiAgIiIsDQogICIiLA0KICAiIiwNCiAgIiIsDQogICIiLA0KICAi
IiwNCiAgIiIsDQogICIiLA0KICAiIiwNCiAgIiIsDQogICIiLA0KICAiIiwN
CiAgIiIsDQogICIiLA0KICAiIg0KfTsNCg0Kc3RhdGljIGNoYXIgKmhvc3Rf
c2Z4X3N0cmluZ3NbMzJdID0gew0KICAiaWJtLmNvbSIsDQogICIuZGUiLA0K
ICAiLmF1IiwNCiAgIi5jYSIsDQogICIuZWR1IiwNCiAgIi5vcmciLA0KICAi
Lm5ldCIsDQogICIuZWR1LmF1IiwNCiAgIi5uZXQuYXUiLA0KICAiLmNvbS5h
dSIsDQogICJtYWcuY29tIiwNCiAgIi5tc24uY29tIiwNCiAgIi55YWhvby5j
b20iLA0KICAiLm5ldHNjYXBlLmNvbSIsDQogICIuZ2VvY2l0aWVzLmNvbSIs
DQogICJhbHRhdmlzdGEuZGlnaXRhbC5jb20iLA0KICAiIiwNCiAgIiIsDQog
ICIiLA0KICAiIiwNCiAgIiIsDQogICIiLA0KICAiIiwNCiAgIiIsDQogICIi
LA0KICAiIiwNCiAgIiIsDQogICIiLA0KICAiIiwNCiAgIiIsDQogICIiLA0K
ICAiIiwNCiAgIiINCn07DQoNCnN0YXRpYyBjaGFyICp1cmxfc2Z4X3N0cmlu
Z3NbMzJdID0gew0KICAiLmh0bSIsDQogICIuemlwIiwNCiAgIi5naWYiLA0K
ICAiLmpwZyIsDQogICIuYXNwIiwNCiAgIi5HSUYiLA0KICAiLkpQRyIsDQog
ICIuSFRNIiwNCiAgIi5odG1sIiwNCiAgIi5IVE1MIiwNCiAgImluZGV4Lmh0
bSIsDQogICJpbmRleC5odG1sIiwNCiAgIi9pbmRleC5odG0iLA0KICAiL2lu
ZGV4Lmh0bWwiLA0KICAid2VsY29tZS5odG0iLA0KICAiV2VsY29tZS5odG1s
IiwNCiAgIi93ZWxjb21lLmh0bSIsDQogICJ3ZWxjb21lLmh0bWwiLA0KICAi
L1dlbGNvbWUuaHRtbCIsDQogICIvd2VsY29tZS5odG1sIiwNCiAgIiIsDQog
ICIiLA0KICAiIiwNCiAgIiIsDQogICIiLA0KICAiIiwNCiAgIiIsDQogICIi
LA0KICAiIiwNCiAgIiIsDQogICIiLA0KICAiIg0KfTsNCg0Kc3RhdGljIGNo
YXIgKnBmeF9jaGFyID0gIkFCQ0RFRkdISUpMS01OT1BRUlNUVVZXWFlaJioo
KV8rIjsNCnN0YXRpYyBjaGFyIHBmeF9zZnhfY2hhclsxMjhdOw0Kc3RhdGlj
IGNoYXIgbnVtX3BmeF9zZnhfY2hhcnMgPSAwOw0KaW50ICp1cmxfc2Z4X2Nv
bXByZXNzX2FycmF5Ow0KaW50ICp1cmxfcGZ4X2NvbXByZXNzX2FycmF5Ow0K
aW50ICpob3N0X3NmeF9jb21wcmVzc19hcnJheTsNCg0KaW50IHNjYW5fc3Ry
bGVuKGNoYXIgKnMpIHsNCmludCBpID0gMDsNCg0KICBpZighKnMpDQogICAg
cmV0dXJuIDA7DQogIHdoaWxlKCpzKSB7DQogICAgaWYoIXBmeF9zZnhfY2hh
clsqc10pDQogICAgICBwZnhfc2Z4X2NoYXJbKnNdID0gKytudW1fcGZ4X3Nm
eF9jaGFyczsNCiAgICBpKyssIHMrKzsNCiAgfQ0KICByZXR1cm4gaTsNCn0N
Cg0Kdm9pZCBtYWtlX2NvbXByZXNzX2FycmF5KGludCAqKmNhcnJheSwgY2hh
ciAqKnN0cmluZ3MsIGNoYXIgbWF4bGVuLCBjaGFyIGluYykgew0KaW50IGks
IHBvczsNCmNoYXIgKnN0cjsNCg0KICAqY2FycmF5ID0gY2FsbG9jKG51bV9w
Znhfc2Z4X2NoYXJzICogKG1heGxlbiArIDEpLCBzaXplb2YoaW50KSk7DQog
IGZvcihpPTA7IGk8MzI7IGkrKykgew0KICAgIHN0ciA9IChpbmMgPT0gMSkg
PyBzdHJpbmdzW2ldIDogKHN0cmluZ3NbaV0gKyBzdHJsZW4oc3RyaW5nc1tp
XSkgLSAxKTsNCiAgICBwb3MgPSAwOw0KICAgIHdoaWxlKChpbmMgPT0gMSkg
PyAqc3RyIDogc3RyID49IHN0cmluZ3NbaV0pIHsNCiAgICAgICgqY2FycmF5
KVtwb3MgKiBudW1fcGZ4X3NmeF9jaGFycyArIHBmeF9zZnhfY2hhclsqc3Ry
XSAtIDFdIHw9IDE8PGk7DQogICAgICBzdHIgKz0gaW5jOw0KICAgICAgcG9z
Kys7DQogICAgfQ0KICB9DQp9DQoNCnZvaWQgdXJsX2NvbXByZXNzX2luaXQo
KSB7DQppbnQgbWF4X3Bvc3NfdXJsX3NmeCA9IDA7DQppbnQgbWF4X3Bvc3Nf
aG9zdF9zZnggPSAwOw0KaW50IG1heF9wb3NzX3VybF9wZnggPSAwOw0KaW50
IGk7DQoNCiAgZm9yKGk9MDsgaTwxMjg7IGkrKykgew0KICAgIHBmeF9zZnhf
Y2hhcltpXSA9IDA7DQogIH0NCiAgZm9yKGk9MDsgaTwzMjsgaSsrKSB7DQog
ICAgaWYoc2Nhbl9zdHJsZW4odXJsX3NmeF9zdHJpbmdzW2ldKSA+IG1heF9w
b3NzX3VybF9zZngpDQogICAgICBtYXhfcG9zc191cmxfc2Z4ID0gc3RybGVu
KHVybF9zZnhfc3RyaW5nc1tpXSk7DQogICAgaWYoc2Nhbl9zdHJsZW4oaG9z
dF9zZnhfc3RyaW5nc1tpXSkgPiBtYXhfcG9zc19ob3N0X3NmeCkNCiAgICAg
IG1heF9wb3NzX2hvc3Rfc2Z4ID0gc3RybGVuKGhvc3Rfc2Z4X3N0cmluZ3Nb
aV0pOw0KICAgIGlmKHNjYW5fc3RybGVuKHVybF9wZnhfc3RyaW5nc1tpXSkg
PiBtYXhfcG9zc191cmxfcGZ4KQ0KICAgICAgbWF4X3Bvc3NfdXJsX3BmeCA9
IHN0cmxlbih1cmxfcGZ4X3N0cmluZ3NbaV0pOw0KICB9DQogIG1ha2VfY29t
cHJlc3NfYXJyYXkoJnVybF9zZnhfY29tcHJlc3NfYXJyYXksIHVybF9zZnhf
c3RyaW5ncywgbWF4X3Bvc3NfdXJsX3NmeCwgLTEpOw0KICBtYWtlX2NvbXBy
ZXNzX2FycmF5KCZob3N0X3NmeF9jb21wcmVzc19hcnJheSwgaG9zdF9zZnhf
c3RyaW5ncywgbWF4X3Bvc3NfaG9zdF9zZngsIC0xKTsNCiAgbWFrZV9jb21w
cmVzc19hcnJheSgmdXJsX3BmeF9jb21wcmVzc19hcnJheSwgdXJsX3BmeF9z
dHJpbmdzLCBtYXhfcG9zc191cmxfcGZ4LCAxKTsNCn0NCg0KY2hhciBmaXJz
dGJpdCh1bnNpZ25lZCBpbnQgaSkgew0KLyogcHJlOiBpICE9IDAgKi8NCnVu
c2lnbmVkIGludCBqID0gMDsNCg0KICB3aGlsZSghKGkmMHhmZikpIHsNCiAg
ICBpID4+PSA4Ow0KICAgIGogKz0gODsNCiAgfQ0KICBpZighKGkmMHgwZikp
IHsNCiAgICBpID4+PSA0Ow0KICAgIGogKz0gNDsNCiAgfQ0KICBpZighKGkm
MHgwMykpIHsNCiAgICBpID4+PSAyOw0KICAgIGogKz0gMjsNCiAgfQ0KICBp
ZihpJjB4MDEpDQogICAgcmV0dXJuIGo7DQogIGVsc2UNCiAgICByZXR1cm4g
aiArIDE7DQp9DQoNCmNoYXIgKnVybF9lbmNvZGUoY2hhciAqdXJsKSB7DQpp
bnQgcG9zc19wZnggPSAweGZmZmY7DQppbnQgbmV4dCwgc2xhc2ggPSAwLCB1
c2VkOw0KY2hhciAqb3JpZ191cmwgPSB1cmwsICpyZWFsX29yaWdfdXJsID0g
dXJsLCAqcmV0LCAqb2xkX3JldDsNCmNoYXIgcGZ4Ow0KDQogIHdoaWxlKCp1
cmwgJiYgcG9zc19wZngpIHsNCiAgICBpZihwZnhfc2Z4X2NoYXJbKnVybF0p
DQogICAgICBuZXh0ID0gcG9zc19wZnggJiB1cmxfcGZ4X2NvbXByZXNzX2Fy
cmF5Wyh1cmwgLSBvcmlnX3VybCkgKiBudW1fcGZ4X3NmeF9jaGFycyArIHBm
eF9zZnhfY2hhclsqdXJsXSAtIDFdOw0KICAgIGVsc2UNCiAgICAgIG5leHQg
PSAwOw0KICAgIGlmKCFuZXh0KQ0KICAgICAgaWYocG9zc19wZnggPT0gMHhm
ZmZmKQ0KICAgICAgICBwZnggPSAtMTsNCiAgICAgIGVsc2UNCiAgICAgICAg
cGZ4ID0gZmlyc3RiaXQocG9zc19wZngpOw0KICAgIGVsc2Ugew0KICAgICAg
aWYoKnVybCA9PSAnLycpDQogICAgICAgIHNsYXNoKys7DQogICAgICB1cmwr
KzsNCiAgICB9DQogICAgcG9zc19wZnggPSBuZXh0Ow0KICB9DQogIGlmKCEq
dXJsKSB7DQogICAgaWYocG9zc19wZnggPT0gMHhmZmZmKQ0KICAgICAgcGZ4
ID0gLTE7DQogICAgZWxzZQ0KICAgICAgcGZ4ID0gZmlyc3RiaXQocG9zc19w
ZngpOw0KICB9DQogIHVzZWQgPSAwOw0KICBpZihwZnggPT0gLTEpDQogICAg
LyoNCiAgICAgKiBubyB2YWxpZCBwcmVmaXgNCiAgICAgKi8NCiAgICByZXQg
PSBzdHJkdXAodXJsKTsNCiAgZWxzZSBpZih1cmwgLSBvcmlnX3VybCA9PSBz
dHJsZW4odXJsX3BmeF9zdHJpbmdzW3BmeF0pKSB7DQogICAgcGZ4ID0gcGZ4
X2NoYXJbcGZ4XTsNCiAgICBpZihpc2RpZ2l0KCp1cmwpIHx8ICp1cmwgPT0g
J1xcJykgew0KICAgICAgLyogaWYgZm9sbG93ZWQgYnkgYSBudW1lcmljLCBm
b2xsb3cgYnkgYSBcIGJlZm9yZSB0aGUgbnVtZXJpYw0KICAgICAgICogaWYg
Zm9sbG93ZWQgYnkgYSBcLCBtYWtlIGl0IGEgXFwNCiAgICAgICAqIG5vdGUg
dGhhdCB0aGUgcGZ4IHN0cmluZyBjYW5ub3QgYmUgY29uZnVzZWQgZm9yIGEg
dmFsaWQsIGxvd2VyY2FzZWQNCiAgICAgICAqIHN0YXJ0IG9mIGEgVVJMIHNv
IG5vIG5lZWQgdG8gZXNjYXBlIHRoYXQgY2FzZSwgYnV0LCBuZWVkIHRvIGVz
Y2FwZQ0KICAgICAgICogYWZ0ZXIgcGZ4IHN0cmluZyBzaW5jZSBwZnggc3Ry
aW5nIGNvdWxkIGJlIGVudGlyZSBtZXRob2QsIGhvc3RuYW1lLA0KICAgICAg
ICogYW5kIHBhcnRpYWwgb2JqZWN0IG5hbWUNCiAgICAgICAqLw0KICAgICAg
cmV0ID0gbWFsbG9jKHN0cmxlbih1cmwpICsgMyk7DQogICAgICByZXRbMF0g
PSBwZng7DQogICAgICByZXRbMV0gPSAnXFwnOw0KICAgICAgc3RyY3B5KHJl
dCArIDIsIHVybCk7DQogICAgICB1c2VkID0gMzsNCiAgICB9IGVsc2Ugew0K
ICAgICAgLyoNCiAgICAgICAqIHNpbXBsZSBwcmVmaXgNCiAgICAgICAqLw0K
ICAgICAgcmV0ID0gc3RyZHVwKC0tdXJsKTsNCiAgICAgIHJldFswXSA9IHBm
eDsNCiAgICAgIHVzZWQgPSAxOw0KICAgIH0NCiAgfSBlbHNlIHsNCiAgICBp
bnQgbGw7DQoNCiAgIC8qDQogICAgKiBpZiBub3QgYSBjb21wbGV0ZSBwcmVm
aXggc3RyaW5nLCBhZGQgdGhlIGxlbmd0aCB1c2VkIGluIHRleHQNCiAgICAq
IFdBUk5JTkc6IHBmeCBzdHJpbmdzIG92ZXIgMTAwMCBjaGFycyBub3QgY29u
c2lkZXJlZA0KICAgICovDQogICAgcGZ4ID0gcGZ4X2NoYXJbcGZ4XTsNCiAg
ICBpZih1cmwgLSBvcmlnX3VybCA+PSAxMDApDQogICAgICBsbCA9IDM7DQog
ICAgZWxzZSBpZih1cmwgLSBvcmlnX3VybCA+PSAxMCkNCiAgICAgIGxsID0g
MjsNCiAgICBlbHNlDQogICAgICBsbCA9IDE7DQogICAgaWYoaXNkaWdpdCgq
dXJsKSB8fCAqdXJsID09ICdcXCcpIHsNCiAgICAgIHJldCA9IG1hbGxvYyhz
dHJsZW4odXJsKSArIDMgKyBsbCk7DQogICAgICBzcHJpbnRmKHJldCwgIiVj
JWRcXCVzIiwgcGZ4LCB1cmwtb3JpZ191cmwsIHVybCk7DQogICAgICB1c2Vk
ID0gbGwgKyAzOw0KICAgIH0gZWxzZSB7DQogICAgICByZXQgPSBtYWxsb2Mo
c3RybGVuKHVybCkgKyAyICsgbGwpOw0KICAgICAgc3ByaW50ZihyZXQsICIl
YyVkJXMiLCBwZngsIHVybC1vcmlnX3VybCwgdXJsKTsNCiAgICAgIHVzZWQg
PSBsbCArIDE7DQogICAgfQ0KICB9DQogIHVybCA9IHJldDsNCiAgd2hpbGUo
c2xhc2ggPCAyIHx8ICp1cmwgIT0gJy8nKSB7DQogICAgaWYoKnVybCA9PSAn
LycpDQogICAgICBzbGFzaCsrOw0KICAgIGlmKCEqKyt1cmwpDQogICAgICBi
cmVhazsNCiAgfQ0KICBwb3NzX3BmeCA9IDB4ZmZmZjsNCiAgaWYgKHNsYXNo
ID09IDIgJiYgKnVybCA9PSAnLycgJiYgdXJsID49IHJldCArIHVzZWQpIHsN
CiAgICAvKiBub3cgZG8gYSBob3N0IHN1ZmZpeCBzZWFyY2ggKi8NCiAgICBv
cmlnX3VybCA9IC0tdXJsOw0KICAgIHdoaWxlKHVybCA+PSByZXQgKyB1c2Vk
ICYmIHBvc3NfcGZ4KSB7DQogICAgICBpZihwZnhfc2Z4X2NoYXJbKnVybF0p
DQogICAgICAgIG5leHQgPSBwb3NzX3BmeCAmIGhvc3Rfc2Z4X2NvbXByZXNz
X2FycmF5WyhvcmlnX3VybCAtIHVybCkgKiBudW1fcGZ4X3NmeF9jaGFycyAr
IHBmeF9zZnhfY2hhclsqdXJsXSAtIDFdOw0KICAgICAgZWxzZQ0KICAgICAg
ICBuZXh0ID0gMDsNCiAgICAgIGlmKCFuZXh0KQ0KICAgICAgICBpZihwb3Nz
X3BmeCA9PSAweGZmZmYpDQogICAgICAgICAgcGZ4ID0gLTE7DQogICAgICAg
IGVsc2UNCiAgICAgICAgICBwZnggPSBmaXJzdGJpdChwb3NzX3BmeCk7DQog
ICAgICBlbHNlDQogICAgICAgIHVybC0tOw0KICAgICAgcG9zc19wZnggPSBu
ZXh0Ow0KICAgIH0NCiAgICBpZiAodXJsIDwgcmV0ICsgdXNlZCkNCiAgICAg
IGlmKHBvc3NfcGZ4ID09IDB4ZmZmZikNCiAgICAgICAgcGZ4ID0gLTE7DQog
ICAgICBlbHNlDQogICAgICAgIHBmeCA9IGZpcnN0Yml0KHBvc3NfcGZ4KTsN
CiAgICBpZiAocGZ4ICE9IC0xKSB7DQogICAgICAvKiBvaywgd2UgaGF2ZSBh
IGhvc3QgU0ZYDQogICAgICAgKiBub3RlLCBuZXh0IGNoYXIgaXMgZ3VhcmVu
dGVlZCAvLCB0aGVyZSBpcyBubyBuZWVkIHRvIGVzY2FwZQ0KICAgICAgICog
Y2FwaXRhbHMgb3Igc3BlY2lhbCBjaGFycyBpbiB0aGUgaG9zdG5hbWUsIHNv
Li4uIGdvIGZvciBpdA0KICAgICAgICovDQogICAgICBpZiAob3JpZ191cmwg
LSB1cmwgPT0gc3RybGVuKGhvc3Rfc2Z4X3N0cmluZ3NbcGZ4XSkpIHsNCiAg
ICAgICAgb2xkX3JldCA9IHJldDsNCiAgICAgICAgaWYodXJsIDwgb2xkX3Jl
dCArIHVzZWQpIHsNCiAgICAgICAgICByZXQgPSBtYWxsb2ModXJsIC0gb2xk
X3JldCArIDMgKyBzdHJsZW4ob3JpZ191cmwpKTsNCiAgICAgICAgICBzdHJu
Y3B5KHJldCwgb2xkX3JldCwgdXJsIC0gb2xkX3JldCArIDEpOw0KICAgICAg
ICAgIHJldFt1cmwgLSBvbGRfcmV0ICsgMV0gPSAnISc7DQogICAgICAgICAg
cmV0W3VybCAtIG9sZF9yZXQgKyAyXSA9IHBmeF9jaGFyW3BmeF07DQogICAg
ICAgICAgc3RyY3B5KHJldCArICh1cmwgLSBvbGRfcmV0KSArIDMsIG9yaWdf
dXJsICsgMSk7DQogICAgICAgICAgdXNlZCA9ICh1cmwgLSBvbGRfcmV0KSAr
IDM7DQogICAgICAgIH0gZWxzZSB7DQogICAgICAgICAgcmV0ID0gbWFsbG9j
KHVybCAtIG9sZF9yZXQgKyAyICsgc3RybGVuKG9yaWdfdXJsKSk7DQogICAg
ICAgICAgc3RybmNweShyZXQsIG9sZF9yZXQsIHVybCAtIG9sZF9yZXQgKyAx
KTsNCiAgICAgICAgICByZXRbdXJsIC0gb2xkX3JldCArIDFdID0gcGZ4X2No
YXJbcGZ4XTsNCiAgICAgICAgICBzdHJjcHkocmV0ICsgKHVybCAtIG9sZF9y
ZXQpICsgMiwgb3JpZ191cmwgKyAxKTsNCiAgICAgICAgICB1c2VkID0gKHVy
bCAtIG9sZF9yZXQpICsgMjsNCiAgICAgICAgfQ0KICAgICAgICBmcmVlKG9s
ZF9yZXQpOw0KICAgICAgfSBlbHNlIHsNCglpbnQgbGw7DQoNCiAgICAgICAg
b2xkX3JldCA9IHJldDsNCiAgICAgICAgaWYob3JpZ191cmwgLSB1cmwgPj0g
MTAwKQ0KICAgICAgICAgIGxsID0gMzsNCiAgICAgICAgZWxzZSBpZihvcmln
X3VybCAtIHVybCA+PSAxMCkNCiAgICAgICAgICBsbCA9IDI7DQogICAgICAg
IGVsc2UNCiAgICAgICAgICBsbCA9IDE7DQogICAgICAgIHJldCA9IG1hbGxv
Yyh1cmwgLSBvbGRfcmV0ICsgMiArIHN0cmxlbihvcmlnX3VybCkgKyBsbCk7
DQogICAgICAgIHN0cm5jcHkocmV0LCBvbGRfcmV0LCB1cmwgLSBvbGRfcmV0
ICsgMSk7DQogICAgICAgIHJldFsodXJsIC0gb2xkX3JldCkgKyAxXSA9IHBm
eF9jaGFyW3BmeF07DQogICAgICAgIHVzZWQgPSAodXJsIC0gb2xkX3JldCkg
KyAyICsgbGw7DQogICAgICAgIGxsID0gb3JpZ191cmwgLSB1cmw7DQogICAg
ICAgIHdoaWxlKGxsKSB7DQogICAgICAgICAgcmV0WygrK3VybCAtIG9sZF9y
ZXQpICsgMV0gPSBwZnhfY2hhcltsbCAlIDEwXTsNCiAgICAgICAgICBsbCAv
PSAxMDsNCiAgICAgICAgfQ0KICAgICAgICBzdHJjcHkocmV0ICsgKHVybCAt
IG9sZF9yZXQpICsgMSwgb3JpZ191cmwgKyAxKTsNCiAgICAgICAgZnJlZShv
bGRfcmV0KTsNCiAgICAgIH0NCiAgICB9DQogIH0NCiAgdXNlZCsrOw0KICB1
cmwgPSByZXQgKyB1c2VkICsgc3RybGVuKHJldCArIHVzZWQpOw0KICBvcmln
X3VybCA9IC0tdXJsOw0KICBwb3NzX3BmeCA9IDB4ZmZmZjsNCiAgLyogdHJ5
IHRvIGNvbXByZXNzIHVybCBzZnggKi8NCiAgd2hpbGUodXJsID49IHJldCAr
IHVzZWQgJiYgcG9zc19wZngpIHsNCiAgICBpZihwZnhfc2Z4X2NoYXJbKnVy
bF0pDQogICAgICBuZXh0ID0gcG9zc19wZnggJiB1cmxfc2Z4X2NvbXByZXNz
X2FycmF5WyhvcmlnX3VybCAtIHVybCkgKiBudW1fcGZ4X3NmeF9jaGFycyAr
IHBmeF9zZnhfY2hhclsqdXJsXSAtIDFdOw0KICAgIGVsc2UNCiAgICAgIG5l
eHQgPSAwOw0KICAgIGlmKCFuZXh0KQ0KICAgICAgaWYocG9zc19wZnggPT0g
MHhmZmZmKQ0KICAgICAgICBwZnggPSAtMTsNCiAgICAgIGVsc2UNCiAgICAg
ICAgcGZ4ID0gZmlyc3RiaXQocG9zc19wZngpOw0KICAgIGVsc2UNCiAgICAg
IHVybC0tOw0KICAgIHBvc3NfcGZ4ID0gbmV4dDsNCiAgfQ0KICBpZiAodXJs
IDwgcmV0ICsgdXNlZCkNCiAgICBpZihwb3NzX3BmeCA9PSAweGZmZmYpDQog
ICAgICBwZnggPSAtMTsNCiAgICBlbHNlDQogICAgICBwZnggPSBmaXJzdGJp
dChwb3NzX3BmeCk7DQogIGlmIChwZnggIT0gLTEpIHsNCiAgICAvKiBvaywg
d2UgaGF2ZSBhIFVSTCBTRlguDQogICAgICogbm90ZSB0aGF0IHRoZSBudWxs
IFNGWCBlbmNvZGVzIHRvICMsIGEgc3ViLVNGWCBlbmNvZGVzIHRvIFtjaGFy
XVtsZW5dDQogICAgICogYWxsIFVSTCBzdHJpbmdzIGVuZCBpbiBhbiBTRlgg
YWJicmV2OyBtYWtlIHN1cmUgdGhlcmUgaXMgYSBTRlggYWJiZXYgZm9yIC8N
CiAgICAgKi8NCiAgICAvKiBob3BlIHdlIGdldCBhIGZ1bGwgbWF0Y2gsIGJ1
dC4uLiAqLw0KICAgIGlmIChvcmlnX3VybCAtIHVybCA9PSBzdHJsZW4odXJs
X3NmeF9zdHJpbmdzW3BmeF0pKSB7DQogICAgICBvbGRfcmV0ID0gcmV0Ow0K
ICAgICAgcmV0ID0gbWFsbG9jKHVybCAtIG9sZF9yZXQgKyAzKTsNCiAgICAg
IHN0cm5jcHkocmV0LCBvbGRfcmV0LCB1cmwgLSBvbGRfcmV0ICsgMSk7DQog
ICAgICByZXRbdXJsIC0gb2xkX3JldCArIDFdID0gcGZ4X2NoYXJbcGZ4XTsN
CiAgICAgIHJldFt1cmwgLSBvbGRfcmV0ICsgMl0gPSAnXDAnOw0KICAgICAg
ZnJlZShvbGRfcmV0KTsNCiAgICB9IGVsc2Ugew0KICAgICAgaW50IGxsOw0K
DQogICAgICBvbGRfcmV0ID0gcmV0Ow0KICAgICAgaWYob3JpZ191cmwgLSB1
cmwgPj0gMTAwKQ0KICAgICAgICBsbCA9IDM7DQogICAgICBlbHNlIGlmKG9y
aWdfdXJsIC0gdXJsID49IDEwKQ0KICAgICAgICBsbCA9IDI7DQogICAgICBl
bHNlDQogICAgICAgIGxsID0gMTsNCiAgICAgIHJldCA9IG1hbGxvYyh1cmwg
LSBvbGRfcmV0ICsgMyArIGxsKTsNCiAgICAgIHN0cm5jcHkocmV0LCBvbGRf
cmV0LCB1cmwgLSBvbGRfcmV0ICsgMSk7DQogICAgICBzcHJpbnRmKHJldCAr
ICh1cmwgLSBvbGRfcmV0KSArIDEsICIlYyVkIiwgcGZ4X2NoYXJbcGZ4XSwN
CiAgICAgICAgICAgICAgb3JpZ191cmwgLSB1cmwpOw0KICAgICAgZnJlZShv
bGRfcmV0KTsNCiAgICB9DQogIH0gZWxzZSB7DQogICAgLyogcGZ4ID09IC0x
IDsgIy10ZXJtaW5hdGUgaWYgbmVlZGVkICovDQogICAgdXNlZCA9IHN0cmxl
bihyZXQpOw0KICAgIGlmKHN0cmNocihwZnhfY2hhciwgcmV0W3BmeCAtIDFd
KSB8fCBpc2RpZ2l0KHJldFt1c2VkIC0gMV0pKSB7DQogICAgICBvbGRfcmV0
ID0gcmV0Ow0KICAgICAgcmV0ID0gbWFsbG9jKHVzZWQgKyAyKTsNCiAgICAg
IHN0cmNweShyZXQsIG9sZF9yZXQpOw0KICAgICAgcmV0W3VzZWRdID0gJyMn
Ow0KICAgICAgcmV0W3VzZWQgKyAxXSA9ICdcMCc7DQogICAgICBmcmVlKG9s
ZF9yZXQpOw0KICAgIH0NCiAgfQ0KICBpZihzdHJsZW4ocmV0KSA+IHN0cmxl
bihyZWFsX29yaWdfdXJsKSArIDEpIHsNCiAgICBmcmVlKHJldCk7DQogICAg
cmV0ID0gbWFsbG9jKHN0cmxlbihyZWFsX29yaWdfdXJsKSArIDIpOw0KICAg
IHN0cmNweShyZXQsIHJlYWxfb3JpZ191cmwpOw0KICAgICoodXJsID0gKHJl
dCArIHN0cmxlbihyZXQpKSkgPSAnIyc7DQogICAgKih1cmwgKyAxKSA9ICdc
MCc7DQogIH0NCiAgcmV0dXJuIHJldDsNCn0NCg0KaW50IHVybF9kZWNvZGUo
Y2hhciAqcGFja2VkKSB7DQpjaGFyICpyZXQsICpwMSwgKnAyLCAqcDIyLCAq
cHRyOw0KaW50IGxlbiwgc2VnMWxlbiA9IC0xLCBzMWwgPSAtMSwgc2VnMmxl
biA9IC0xLCBzMmwgPSAtMSwgczJsMiA9IC0xLCBzZWczbGVuID0gLTEsIHNs
YXNoID0gMCwgaTsNCg0KICBsZW4gPSBzdHJsZW4ocGFja2VkKSArIDE7DQog
IGlmKChwMSA9IHN0cmNocihwZnhfY2hhciwgKnJldCkpKSB7DQogICAgaWYo
aXNkaWdpdChyZXRbMV0pKSB7DQogICAgICBsZW4gKz0gKHNlZzFsZW4gPSBh
dG9pKHJldCsxKSk7DQogICAgICBpZihzZWcxbGVuID49IDEwMCkNCiAgICAg
ICAgbGVuIC09IChzMWwgPSAzKTsNCiAgICAgIGVsc2UgaWYoc2VnMWxlbiA+
PSAxMCkNCiAgICAgICAgbGVuIC09IChzMWwgPSAyKTsNCiAgICAgIGVsc2UN
CiAgICAgICAgbGVuIC09IChzMWwgPSAxKTsNCiAgICB9IGVsc2Ugew0KICAg
ICAgbGVuICs9IChzZWcxbGVuID0gc3RybGVuKHVybF9wZnhfc3RyaW5nc1tw
MSAtIHBmeF9jaGFyXSkpIC0gMTsNCiAgICAgIHMxbCA9IDA7DQogICAgfQ0K
ICAgIGlmKHJldFsxICsgczFsXSA9PSAnXFwnKQ0KICAgICAgbGVuLS07DQog
ICAgZm9yKGk9MDsgaTxzZWcxbGVuOyBpKyspDQogICAgICBpZih1cmxfcGZ4
X3N0cmluZ3NbcDEgLSBwZnhfY2hhcl1baV0gPT0gJy8nKQ0KICAgICAgICBz
bGFzaCsrOw0KICB9DQogIHdoaWxlKHNsYXNoIDwgMiB8fCAqcHRyICE9ICcv
Jykgew0KICAgIHB0cisrOw0KICAgIGlmKCEqcHRyKQ0KICAgICAgYnJlYWs7
DQogICAgaWYoKnB0ciA9ICcvJykNCiAgICAgIHNsYXNoKys7DQogIH0NCiAg
aWYoKnB0ciA9PSAnLycgJiYgc2xhc2ggPT0gMikgew0KICAgIHB0ci0tOw0K
ICAgIGlmKChwMiA9IHN0cmNocihwZnhfY2hhciwgKnB0cikpKSB7DQogICAg
ICBzZWcybGVuID0gczJsID0gMDsNCiAgICAgIHMybDIgPSAxOw0KICAgICAg
d2hpbGUoKHAyMiA9IHN0cmNocihwZnhfY2hhciwgKi0tcHRyKSkpIHsNCiAg
ICAgICAgc2VnMmxlbiA9IHNlZzJsZW4gKyBzMmwyICogKHAyMiAtIHBmeF9j
aGFyKTsNCiAgICAgICAgczJsMiAqPSAxMDsNCiAgICAgICAgczJsKys7DQog
ICAgICB9DQogICAgfQ0KICB9DQogIHJldHVybiBsZW47DQp9DQoNCmNoYXIg
Km1haW4oKSB7DQpjaGFyIGJ1Zls0MDk2XSwgKnN0cjsNCg0KICB1cmxfY29t
cHJlc3NfaW5pdCgpOw0KICB3aGlsZShnZXRzKGJ1ZikpIHsNCiAgICBwcmlu
dGYoIiVzIFslZF0gLS0+ICVzICIsIGJ1Ziwgc3RybGVuKGJ1ZiksIHN0ciA9
IHVybF9lbmNvZGUoYnVmKSk7DQogICAgcHJpbnRmKCIgWyVkXVxuIiwgc3Ry
bGVuKHN0cikpOw0KICAgIGZyZWUoc3RyKTsNCiAgfQ0KICByZXR1cm4gMDsN
Cn0NCg==
--1602371712-1845522394-871971069=:8099--
Received on Tue Jul 29 2003 - 13:15:42 MDT