Replace compression algorithm

[boeckmann]

Currently the kernel is zero-compressed. The single-file kernel is ~60K in size. It could be made smaller by utilizing another compression algorithm. Constraints: uncompressor should fit within 512 bytes.

[boeckmann]

Related discussion: https://github.com/SvarDOS/edrdos/issues/28#issuecomment-1964185475

[rofl0r]

is there even an advantage to that - except in terms of floppy space ? my understanding is that the kernel will be extracted to memory anyway. so a fast decompression like your existing zero-compression would probably be more beneficial.

[boeckmann]

No, this is mainly for size on floppy. Matheusz prefers it to be no larger than the FreeDOS kernel, which is compressed (I think UPX?!?). Uncompression time is a high priority. We will not include any algorithm that makes uncompression time annoying on ancient machines. It is also a topic that is quite interesting (at least to me) :)

[mateuszviste]

FD kernel is indeed compressed with upx (the "UPX!" string is easily visible in the file). Dunno if it uses NRV or something else, though. EDR is currently 60K (zero-stripped), while the FD kernel is 45K. That's already very good, I have no issue incorporating a 60K kernel in SvarDOS. Now of course if this compression thing makes you "tick", then even better :-) BTW in #28 I was asking why not apply to EDR the same upx scheme that FD uses. ECM mentioned that it would require EDR to be a single file and loadable at seg 60h. Both of these things are done now, so maybe the upx option could be revisited to avoid reinventing the wheel? I am sorry if this is naive or wishful thinking on my part, I understand little of the magic you are pulling up, guys.

[boeckmann]

@mateuszviste I see no reason why UPX should not work. But I have no understanding yet how the uncompression stage of FreeDOS works. Is UPX fast enough to be run on an 8088?

My idea is to have an uncompressor which fits in the 512 unused bytes of the deblocking buffer near the start of the EDR kernel, and from the view of the boot process leave everything as it is now. This would be the most compatible, least invasive kind of doing it, I think. The current zero-uncompression also works like this, and since a few days lives in the deblocking buffer. So this would "simply" be a substitution of the uncompression algorithm.

A more sophisticated, albeit more complex and harder to build (more tools, repos needed) approach, like @ecm-pushbx has chosen, is to give the kernel as a payload to an initial loader, capable of supporting different compression algorithms. But I prefer to keep it a little more simple, keeping complexity so low that I still can understand it :)

[boeckmann]

See https://github.com/SvarDOS/edrdos/issues/28#issuecomment-2248801739 for a nice evaluation of the different compression algorithms.

[ecm-pushbx]

I updated the thread in https://github.com/SvarDOS/edrdos/issues/28#issuecomment-2248801739 with a new comparison of compression methods, including one that just adapts the zerocomp that originates with DR-DOS but applies it to the entire payload file.

@mateuszviste I see no reason why UPX should not work. But I have no understanding yet how the uncompression stage of FreeDOS works.

Basically you massage an intermediate kernel file so it looks like either a flat-format DOS/SYS driver file or a segmented DOS/EXE application. That gets fed into UPX. The UPX output is then prepended with a small entrypoint stub that sets up things for UPX so it looks like the expected environment (using different stubs for DOS/SYS or DOS/EXE format). Might be the UPX depacker is patched a little, or maybe not any longer. It's been a while since I worked with it. Most of the implementation is in the exeflat utility: https://github.com/FDOS/kernel/blob/db43a4b3438047caccec220e349ede57fb24f88f/utils/exeflat.c

Is UPX fast enough to be run on an 8088?

Insufficient data. I don't know that anyone ever tested it. FWIW my FreeDOS kernel build is uncompressed.

My idea is to have an uncompressor which fits in the 512 unused bytes of the deblocking buffer near the start of the EDR kernel, and from the view of the boot process leave everything as it is now. This would be the most compatible, least invasive kind of doing it, I think. The current zero-uncompression also works like this, and since a few days lives in the deblocking buffer. So this would "simply" be a substitution of the uncompression algorithm.

A more sophisticated, albeit more complex and harder to build (more tools, repos needed) approach, like @ecm-pushbx has chosen, is to give the kernel as a payload to an initial loader, capable of supporting different compression algorithms. But I prefer to keep it a little more simple, keeping complexity so low that I still can understand it :)

Yes, my approach is more complex but also more flexible. I think your most recent work doesn't support compressed size > 64 KiB yet. And my approach comes with support for triple-mode execution with little additional overhead, as an MZ EXE application, MZ EXE device driver, or kernel.

[boeckmann]

Yes, my approach is more complex but also more flexible. I think your most recent work doesn't support compressed size > 64 KiB yet. And my approach comes with support for triple-mode execution with little additional overhead, as an MZ EXE application, MZ EXE device driver, or kernel.

Correct, but that would not be that hard to implement. I think about prepending the zero-compressed data with its size in paragraphs, then I know how many data I have to move before uncompressing. And the move itself would have to be adjusted to support >64k. But apart from that nothing should prevent a greater than 64K kernel.

[boeckmann]

my approach comes with support for triple-mode execution with little additional overhead, as an MZ EXE application, MZ EXE device driver, or kernel.

Does this mean I can use it similar UPX to pack a DOS executable with it (but would have to "build" it instead simply executing the packer)?

[ecm-pushbx]

my approach comes with support for triple-mode execution with little additional overhead, as an MZ EXE application, MZ EXE device driver, or kernel.

Does this mean I can use it similar UPX to pack a DOS executable with it (but would have to "build" it instead simply executing the packer)?

Yes, you can do that. On freedos-devel I described how to do this for the dual-mode logger executable:

https://sourceforge.net/p/freedos/mailman/message/37838099/

https://sourceforge.net/p/freedos/mailman/message/37838107/

[ecm-pushbx]

In that case the output is a flat-format .COM executable but you could wrap that in an MZ .EXE header as well to make use of the MZ header, particularly if you want it to specify a minimum allocation size.

[boeckmann]

A middle way would be to leave the zero compression (with slight refinements) as it is as a "good enough" compression for most cases. This keeps the build system and tools dependency low. And for SvarDOS, especially the floppies, create iniload wrapped kernels.

[boeckmann]

I would then build uncompressed single-file binary with the command

wmake SINGLEFILE=1 UNCOMPRESSED=1

And take this uncompressed file as a payload for iniload for SvarDOS kernels.

[mateuszviste]

@mateuszviste I see no reason why UPX should not work. But I have no understanding yet how the uncompression stage of FreeDOS works. Is UPX fast enough to be run on an 8088?

The UPX-packed FD kernel boots within a couple of seconds on my Toshiba (T1200 80C86 @4MHz).

My idea is to have an uncompressor which fits in the 512 unused bytes of the deblocking buffer near the start of the EDR kernel

It is a very attractive perspective indeed, thank you for clarifying. I had not realized that upx and ECM's approaches were multistage-based while yours is much simpler and straight forward. I agree it would be nice to keep it that way, even if it means the kernel is a little bigger on disk (but also presumably faster to depack). The thought of fitting a decompressor in 512 bytes is challenging in itself, I can definitely understand why it inspires you. There are probably some demo scene lessons out there to learn from... an interesting chat on the subject: https://encode.su/threads/3387-(Extremely)-tiny-decompressors and crinkler (mentioned in the chat): http://code4k.blogspot.com/2010/12/crinkler-secrets-4k-intro-executable.html?m=1

[boeckmann]

As the ECM repo provides the ability to use different compression algorithms, and the zero-compression used here is considered "good enough", we leave it as is for the foreseeable future...

[mateuszviste]

I agree -- the zero-comp algorithm provides nice results already, the gain with something more sophisticated is not that big, but load times would certainly suffer.

That being said, would it be possible/easy/reasonable to extend the zero-comp compression to include also the 0x90 character?

Seems like there is some 512 bytes to save. It is some filler data apparently - alternatively maybe it would be possible to zero it out? I do not know if the 90h value is supposed to mean anything, in the code it is here: https://github.com/SvarDOS/edrdos/blob/e62ca5db79db138ca656ec5760ea27816640fafd/drdos/header.asm#L1393 https://github.com/SvarDOS/edrdos/blob/e62ca5db79db138ca656ec5760ea27816640fafd/drbio/biosinit.asm#L296

[ecm-pushbx]

I agree -- the zero-comp algorithm provides nice results already, the gain with something more sophisticated is not that big, but load times would certainly suffer.

That being said, would it be possible/easy/reasonable to extend the zero-comp compression to include also the 0x90 character?

Seems like there is some 512 bytes to save. It is some filler data apparently - alternatively maybe it would be possible to zero it out? I do not know if the 90h value is supposed to mean anything, in the code it is here:

https://github.com/SvarDOS/edrdos/blob/e62ca5db79db138ca656ec5760ea27816640fafd/drdos/header.asm#L1393

https://github.com/SvarDOS/edrdos/blob/e62ca5db79db138ca656ec5760ea27816640fafd/drbio/biosinit.asm#L296

Discussed previously in https://github.com/SvarDOS/edrdos/issues/96#issuecomment-2296928587

[mateuszviste]

Currently the kernel is zero-compressed. The single-file kernel is ~60K in size. It could be made smaller by utilizing another compression algorithm. Constraints: uncompressor should fit within 512 bytes.

Any chance you could point me to the place where this magic happens? ie. where exactly is this 512 buffer, what is it supposed to decompress exactly, and how is the kernel compressed in the first place? I'd be curious to look into that, maybe trying to replace zerocomp with mvcomp for a test. I don't know if I will get anywhere since even compiling the kernel at all is a challenge for me, but who knows - maybe I'll get lucky. :)

[boeckmann]

I don't know if I will get anywhere since even compiling the kernel at all is a challenge for me, but who knows - maybe I'll get lucky. :)

That should not be the case! I try very hard to make building the kernel as simple as possible: wmake SINGLEFILE=1, provided the needed tools are installed, that is OW and JWasm. If it does not work then, it is a BUG!

The kernel compression is done via ltools\compkern.c. It does some magic by putting certain numbers into the right place (regarding sizes etc.). It also puts together drbio.sys and drdos.sys into a combined kernel.sys.

The decompression takes place at init0 routine: https://github.com/SvarDOS/edrdos/blob/7d3cf5610508352513c581962ca63ee0bf67a7ad/drbio/init.asm#L607

This is some clusterfuck of mine, doing two steps in one: decompression and relocation (as FreeDOS loader puts the kernel to segment 60h, but the kernel wants to live at 70h), but only conditionally, if the kernel is compressed and / or is not loaded to 70h (DR-DOS loader does it). If it is uncompressed and loaded to 70h, nothing is to be done.

[mateuszviste]

That should not be the case! I try very hard to make building the kernel as simple as possible

Oh, I have no doubts on that, and the build process does seem to be carefully thought out. My issue is really stupid - I tried to build the kernel the other day on my linux pc and discovered it needs jwasm. Did not find it in any rpm package, so I tried compiling it from sources. But then it complained it needs some exotic tools (bin-386-something) and since I did not know what that is I dropped out. I will retry under SvarDOS, might have better luck there with all the precompiled packages.

[rofl0r]

compiling jwasm should be a matter of running "make -f GccUnix.mak" and then copying the binary build/GccUnixR/jwasm to a directory in your $PATH. my recipe for building it doesn't list any dependencies other than gcc and libc.

[mateuszviste]

compiling jwasm should be a matter of running "make -f GccUnix.mak" and then copying the binary build/GccUnixR/jwasm to a directory in your $PATH. my recipe for building it doesn't list any dependencies other than gcc and libc.

I think I might have used OWLinux.mak. And hence maybe it was OW that complained about a missing something. I will retry tomorrow once I'm behind my PC. The other day I did not investigate much as it was a quick try out of pure curiosity. Thanks for the tips!

[boeckmann]

compiling jwasm should be a matter of running "make -f GccUnix.mak" and then copying the binary build/GccUnixR/jwasm to a directory in your $PATH. my recipe for building it doesn't list any dependencies other than gcc and libc.

This is the same that I am using on Linux (openSUSE tumbleweed), and it works flawless. For compiling the EDR sources under Linux, you should also adapt the Watcom owsetenv.sh like described in the README.md.

[boeckmann]

That is, changing the INCLUDE path from .../lh to .../h