Re: Implementation of LZS algorithm for user space code


"USENET-news" <usenet@xxxxxxxxxxxxxxxx> wrote in message
news:444ff0e3$0$2529$ed2619ec@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Hello,

Where can I find an implementation of LZS please? I am looking for one
that is suitable for execution in user space as opposed to the kernel
patches I have seen when LZS is used over routers etc for compressing IP
packets.

looked some, it is a mildly interesting algo...

note that, in general, most generic code designed to work in kernel space is
easy enough to modify to work in userspace (assuming it is not too overly
tied, eg, to the workings of the network stack).

otherwise, I can't answer your question exactly (I don't know where you can
find one), and am not personally that motivated to write something like that
right now.


some more context as to what you intend to do with the algo could help in
giving more useful answers (also, protocol compression vs data compression,
speed vs quality, ...).

do you actually need this particular protocol, or will nearly any (similar)
algo work?...


misc thought:
in general an idea that comes up after looking at this could be a
"miniflate" type algo.
point:
sort of like deflate, but greatly simplified...

uses: ?... ok, not so good. unlikely to offer any real speed advantage over,
eg, deflate, complexity is high enough that it may not win wrt code size for
fixed decoder (eg: vs. deflate, in assembler). could outperform, eg, LZSS
wrt ratios (not saying much).


otherwise for the idea:

window is dropped from 32kB to 2kB, and the max length is reduced (258 to
34). likewise, there are no huffman tables.

Coded-Item:
0 <byte>
1 <Offs> <Len>

Len:
00 2
010 3
011 x 4/5
100 xx 6..9
101 xxx 10..17
110 xxxx 18..33
111 34

Offs:
000 1
001 2
0100 3
0101 4
0110 x 5..6
0111 xx 7..10
1000 xxx 11..18
1001 xxxx 19..34
1010 xxxxx 35..66
1011 xxxxxx 67..130
1100 xxxxxxx 131..258
1101 xxxxxxxx 259..514
1110 xxxxxxxxx 515..1026
1111 xxxxxxxxxx 1027..2050

EOF: 1 1111 1111111111 (15 bits)

RLE run of 2 bytes: 1 000 00 (6 bits)

Any help gratefully received,

Regards,


Andrew Marlow


.

Relevant Pages

  • Re: Checkpoint/restart (was Re: [PATCH 0/4] - v2 - Object creation with a specified id)
    ... kernel representation. ... If the state can be inferred from user space it is visible to user ... In the worst case today we can restore a checkpoint by replaying all of ... Checkpoints coordinated between multiple containers or real ...
    (Linux-Kernel)
  • Re: [OT] ALSA userspace API complexity
    ... Why we have X servers in user space (and only some supporting code is in the kernel) then? ... Can you do this with ALSA way? ... comercial OSS have ALSA emulation and ALSA have OSS emulation. ...
    (Linux-Kernel)
  • Re: Things that Longhorn seems to be doing right
    ... Updating a user space database every time ... >is just as bad as putting an SQL optimizer into the kernel. ... Well, since I don't think that SQL belongs in the filesystem, and I ...
    (Linux-Kernel)
  • Re: syscalls implementation
    ... In user space, the system calls are stubs in a library that traps into ... the vector code generated from syscalls.master in the kernel. ... stack, and then a trap is issued by ... argument pointer are passed to the system call. ...
    (freebsd-hackers)
  • Re: [OT] ALSA userspace API complexity
    ... >> It means that you are saying that kernel should be bigger and bigger. ... Why we have X servers in user space (and ... > All abstraction are NOW coded but some parts of this abstraction are on ... > If you have sound device without this soft mixing is moved to user space ...
    (Linux-Kernel)