DOS ain't dead - New kernel compression methods

ecm

Düsseldorf, Germany,
13.04.2020, 00:05

New kernel compression methods (Announce)

I just finished fixing the lzd port to my inicomp kernel compression stage. It is a rather direct port of the lzd reference implementation that is shipped along with lzip's manual.

It decompresses a specific variant of LZMA, called LZMA-302eos or LZMA-lzip. This presumably simplifies the decompressor somewhat as compared to the xz and 7-Zip uses of the LZMA.

LZMA-lzip beats, in final compressed executable size, all six formats I've previously implemented. These are (in order of implementation) BriefLZ, LZ4, Snappy, Exomizer 3, X compressor, and Heatshrink. LZMA's high compression ratios do incur CPU time costs though.

For the following numbers, do note that I have not yet optimised the lzd compressor. In particular, I have not yet added overlapping source and destination buffers support. That is only part of the high memory usage for LZMA-lzip though; its probability tables need about 30 KiB of buffer space. To be honest, that is less than what I expected prior to putting it together.

The X compressor does actually have a memory need that large. That's 256 KiB of context tables, and then some more as a multi-layer decompression threshold. The author has suggested variants to lessen this but I only want to implement existing formats, as produced by the corresponding tools.

By the way, as yet I always ignore the checksums, if present in the format. I preferred the best compression settings. Because the depacker reads and writes from memory, the dictionary size doesn't matter to us; if there is enough memory to hold the (possibly overlapping) buffers while decompressing then the entire history of the decompression output is available to the decompressor. With enough contiguous low memory area space permitting, my decompressors all handle compressed and uncompressed file lengths exceeding 64 KiB well. (I think the FreeDOS kernel compression doesn't properly allow that.)

I used a scriptlet to gather some numbers to compare the decompressors. Here's the results when building the lDebug default branch, revision a6c6df3e2820. Size is the total executable file size. Ini size is the iniload (loader) and inicomp (compression) stage sizes together. Alloc specifies how much memory is needed to run the file in EXE mode, which is dynamically detected during building when the use_build_decomp_test option is in effect. The last line for each method gives the time in seconds for a quick test, running the executable 512 times from a single batch file, in dosemu2 gb2414e9c7 running FreeCom version 0.84-pre7 - GNUC - XMS_Swap [Dec 29 2019 15:36:33] and FreeDOS kernel - SVN (build 2042 OEM:0xfd) [compiled Sep 22 2017].

ldebug/tmp$ hg id a6c6df3e2820 tip ldebug/tmp$ fname="ldebug.com"; fname2="debug"; fname3="debug.big"; fnameu="ldebugu.com"; arg="/C=Q"; upcase=0; method=none; ((upcase)) && method="$(echo "$method" | tr 'a-z' 'A-Z')"; mkdir -p "$method"; cp -a ../bin/"$fnameu" "$method"/"$fname"; cp -a "$fname3" "$method/$fname2.$method"; for method in none blz lz4 sz exo x hs lz; do ((upcase)) && method="$(echo "$method" | tr 'a-z' 'A-Z')"; echo -e "\nmethod=$method\nsize=$(stat -c %s "$method/$fname")"; echo -e "ini size=$(( $(stat -c %s "$method/$fname") - ( ($(stat -c %s "$method/$fname2.$method") + 15) / 16 * 16 ) ))"; echo -e "alloc=$(exememls "$method/$fname")"; echo "@echo off" > test.bat; for jj in $(seq 0 511); do echo "@$method\\$fname $arg"; done >> test.bat; (export TIMEFORMAT='%3R'; time dosemu -dumb -quiet -K "$PWD" -E "test.bat" 2> /dev/null > /dev/null); done method=none size=82944 ini size=4944 alloc=96912 bytes = 6057 paragraphs 2.244 method=blz size=64512 ini size=6064 alloc=96688 bytes = 6043 paragraphs 5.011 method=lz4 size=62976 ini size=5936 alloc=96672 bytes = 6042 paragraphs 3.378 method=sz size=70144 ini size=6144 alloc=96864 bytes = 6054 paragraphs 2.858 method=exo size=54784 ini size=5888 alloc=96688 bytes = 6043 paragraphs 6.111 method=x size=71680 ini size=6384 alloc=343920 bytes = 21495 paragraphs 12.471 method=hs size=63488 ini size=5536 alloc=343904 bytes = 21494 paragraphs 7.730 method=lz size=53760 ini size=8336 alloc=344208 bytes = 21513 paragraphs 16.503 ldebug/tmp$

Here are the same numbers for the RxDOS kernel revision 5161b8327e36.

rxdos/tmp$ hg id 5161b8327e36 tip rxdos/tmp$ fname="RxDOS.COM"; fname2="RxDOS"; fname3="RxDOS.BIN"; fnameu="RxDOSU.COM"; arg="version"; upcase=1; method=none; ((upcase)) && method="$(echo "$method" | tr 'a-z' 'A-Z')"; mkdir -p "$method"; cp -a ../bin/"$fnameu" "$method"/"$fname"; cp -a "$fname3" "$method/$fname2.$method"; for method in none blz lz4 sz exo x hs lz; do ((upcase)) && method="$(echo "$method" | tr 'a-z' 'A-Z')"; echo -e "\nmethod=$method\nsize=$(stat -c %s "$method/$fname")"; echo -e "ini size=$(( $(stat -c %s "$method/$fname") - ( ($(stat -c %s "$method/$fname2.$method") + 15) / 16 * 16 ) ))"; echo -e "alloc=$(exememls "$method/$fname")"; echo "@echo off" > test.bat; for jj in $(seq 0 511); do echo "@$method\\$fname $arg"; done >> test.bat; (export TIMEFORMAT='%3R'; time dosemu -dumb -quiet -K "$PWD" -E "test.bat" 2> /dev/null > /dev/null); done method=NONE size=101376 ini size=4528 alloc=98992 bytes = 6187 paragraphs 2.230 method=BLZ size=56320 ini size=6240 alloc=100480 bytes = 6280 paragraphs 4.685 method=LZ4 size=54784 ini size=5712 alloc=99968 bytes = 6248 paragraphs 3.223 method=SZ size=59904 ini size=5760 alloc=100000 bytes = 6250 paragraphs 3.137 method=EXO size=47616 ini size=5776 alloc=100016 bytes = 6251 paragraphs 5.658 method=X size=68608 ini size=6752 alloc=363152 bytes = 22697 paragraphs 24.592 method=HS size=57344 ini size=5504 alloc=99744 bytes = 6234 paragraphs 6.824 method=LZ size=47104 ini size=8336 alloc=170688 bytes = 10668 paragraphs 15.271 rxdos/tmp$

---
l

ecm

Düsseldorf, Germany,
13.04.2020, 00:17

@ ecm

New kernel compression methods

Post reply

By the way, all these decompressors are permissively licensed. I think the lzip compressor is GNU GPL v2-or-later, ie with copyleft. All of the compressors are FLOSS in any case.

---
l

tkchia

13.04.2020, 14:23

@ ecm

New kernel compression methods

Post reply

Hello ecm,

> By the way, as yet I always ignore the checksums, if present in the format.
> I preferred the best compression settings. Because the depacker reads and
> writes from memory, the dictionary size doesn't matter to us; if there is
> enough memory to hold the (possibly overlapping) buffers while
> decompressing then the entire history of the decompression output is
> available to the decompressor. With enough contiguous low memory area space
> permitting, my decompressors all handle compressed and uncompressed file
> lengths exceeding 64 KiB well. (I think the FreeDOS kernel compression
> doesn't properly allow that.)

Thanks for your work. From what I see, the FreeDOS kernel uses UPX, which has no problems with uncompressed kernels larger than 64 KiB. However, the stub that is added after UPX-ing assumes that the compressed kernel is smaller than 64 KiB.

(The sizes for my kernel build: 77,180 bytes when uncompressed (.exe), 52,043 when compressed (as .sys).)

So I would guess that any compression method that compresses even better than UPX should not have much of a problem with the FreeDOS kernel.

Thank you!

---
https://gitlab.com/tkchia · https://codeberg.org/tkchia · 😴 "MOV AX,0D500H+CMOS_REG_D+NMI"

ecm

Düsseldorf, Germany,
13.04.2020, 18:31

@ tkchia

New kernel compression methods

Post reply

> > With enough contiguous low memory area space
> > permitting, my decompressors all handle compressed and uncompressed file
> > lengths exceeding 64 KiB well. (I think the FreeDOS kernel compression
> > doesn't properly allow that.)
>
> Thanks for your work. From what I see, the FreeDOS kernel uses UPX, which
> has no problems with uncompressed kernels larger than 64 KiB. However, the
> stub that is added after UPX-ing assumes that the compressed kernel
> is smaller than 64 KiB.
>
> (The sizes for my kernel build: 77,180 bytes when uncompressed (.exe),
> 52,043 when compressed (as .sys).)

Yep, something like that. I don't remember the exact details but I came away with the impression it won't work. But FreeDOS isn't alone in thinking its kernels should be smaller than 64 KiB.

> So I would guess that any compression method that compresses even better
> than UPX should not have much of a problem with the FreeDOS kernel.

By the way, you can put a FreeDOS kernel (better to use an uncompressed one then) into ldosboot's fdkernpl stage, then can use that payload for inicomp. You'd use _IMAGE_EXE=0 then because the FreeDOS kernel cannot be entered as an .EXE file. However, the FreeDOS kernel entrypoint (and the lDOS/RxDOS and PC-DOS/MS-DOS 6/MS-DOS 7 kernel entrypoints) would still work. The only thing that that does not support is the kernel CONFIG section expected fixed at the start of the file by FreeDOS's kernel configuration (which is part of the FreeDOS SYS program).

Funny, I don't actually know how much UPX would compress things. So I made a test. I had to patch out the short jump in the "last page size" bytes of the EXE header. (These are used for the MS-DOS 6.x and FreeDOS kernel entrypoints.) The invalid value of the short jump instruction in that field otherwise leads to "CantPackException: exe header corrupted". (Obviously, packing the kernel file with UPX without special handling makes it no longer work as a kernel file.)

Here are the results. They aren't entirely fair to my compression stage because my files have not only the depacker in the uncompressed initial part but also the iniload loader stage, which according to my OP is 4944 bytes for the uncompressed ldebugu.com file. So the 51 kB really should be read as 51 + 5 kB, which is indeed beaten by the Exomizer 3 and LZMA-lzip methods. The --8086 option does not appreciably alter the result. (My depackers are all 8086 safe.)

testupx$ upx --version; hg id; for file in *.pat; do echo "=== $file"; cat "$file"; done; echo "==="; cp -at . ../ldebug.com ../ldebugu.com ../debug.com; bpatch -f ldebug.pat; bpatch -f ldebugu.pat; ls -lgG *.com; for x in --8086 ""; do for y in debug.com ldebugu.com ldebug.com; do upx --best --ultra-brute $x -fvvvv -o $y.upx $y; done; done upx 3.95 UCL data compression library 1.03 zlib data compression library 1.2.11 LZMA SDK version 4.43 Copyright (C) 1996-2018 Markus Franz Xaver Johannes Oberhumer Copyright (C) 1996-2018 Laszlo Molnar Copyright (C) 2000-2018 John F. Reiser Copyright (C) 2002-2018 Jens Medoch Copyright (C) 1995-2005 Jean-loup Gailly and Mark Adler Copyright (C) 1999-2006 Igor Pavlov UPX comes with ABSOLUTELY NO WARRANTY; for details type 'upx -L'. a6c6df3e2820 === ldebug.pat File: ldebug.com 000002: 00 00 [ EB 16 ] === ldebugu.pat File: ldebugu.com 000002: 00 00 [ EB 16 ] === -rw-r--r-- 1 78032 Apr 13 17:59 debug.com -rw-r--r-- 1 53760 Apr 13 17:59 ldebug.com -rw-r--r-- 1 82944 Apr 13 17:59 ldebugu.com Ultimate Packer for eXecutables Copyright (C) 1996 - 2018 UPX 3.95 Markus Oberhumer, Laszlo Molnar & John Reiser Aug 26th 2018 File size Ratio Format Name -------------------- ------ ----------- ----------- 78032 -> 51015 65.38% dos/exe debug.com.upx Packed 1 file. Ultimate Packer for eXecutables Copyright (C) 1996 - 2018 UPX 3.95 Markus Oberhumer, Laszlo Molnar & John Reiser Aug 26th 2018 File size Ratio Format Name -------------------- ------ ----------- ----------- 82944 -> 51070 61.57% dos/exe ldebugu.com.upx Packed 1 file. Ultimate Packer for eXecutables Copyright (C) 1996 - 2018 UPX 3.95 Markus Oberhumer, Laszlo Molnar & John Reiser Aug 26th 2018 File size Ratio Format Name -------------------- ------ ----------- ----------- upx: ldebug.com: NotCompressibleException Packed 1 file: 0 ok, 1 error. Ultimate Packer for eXecutables Copyright (C) 1996 - 2018 UPX 3.95 Markus Oberhumer, Laszlo Molnar & John Reiser Aug 26th 2018 File size Ratio Format Name -------------------- ------ ----------- ----------- 78032 -> 51004 65.36% dos/exe debug.com.upx Packed 1 file. Ultimate Packer for eXecutables Copyright (C) 1996 - 2018 UPX 3.95 Markus Oberhumer, Laszlo Molnar & John Reiser Aug 26th 2018 File size Ratio Format Name -------------------- ------ ----------- ----------- 82944 -> 51059 61.56% dos/exe ldebugu.com.upx Packed 1 file. Ultimate Packer for eXecutables Copyright (C) 1996 - 2018 UPX 3.95 Markus Oberhumer, Laszlo Molnar & John Reiser Aug 26th 2018 File size Ratio Format Name -------------------- ------ ----------- ----------- upx: ldebug.com: NotCompressibleException Packed 1 file: 0 ok, 1 error. testupx$

---
l

ecm

Düsseldorf, Germany,
13.04.2020, 18:35

@ ecm

New kernel compression methods

Post reply

> upx 3.95> UCL data compression library 1.03 > zlib data compression library 1.2.11 > LZMA SDK version 4.43 > Copyright (C) 1996-2018 Markus Franz Xaver Johannes Oberhumer > Copyright (C) 1996-2018 Laszlo Molnar > Copyright (C) 2000-2018 John F. Reiser > Copyright (C) 2002-2018 Jens Medoch > Copyright (C) 1995-2005 Jean-loup Gailly and Mark Adler > Copyright (C) 1999-2006 Igor Pavlov > UPX comes with ABSOLUTELY NO WARRANTY; for details type 'upx -L'.

This should be from the current Debian testing (bullseye) package upx-ucl 3.95-2+b1 by the way.

---
l

tkchia

14.04.2020, 14:46
(edited by tkchia, 14.04.2020, 16:56)

@ ecm

New kernel compression methods

Post reply

Hello ecm,

> By the way, you can put a FreeDOS kernel (better to use an uncompressed one
> then) into ldosboot's
> fdkernpl stage, then can use that payload for inicomp. You'd use _IMAGE_EXE=0
> then because the FreeDOS kernel cannot be entered as an .EXE file. However,
> the FreeDOS kernel entrypoint (and the lDOS/RxDOS and PC-DOS/MS-DOS
> 6/MS-DOS 7 kernel entrypoints) would still work. The only thing that that
> does not support is the kernel CONFIG section expected fixed at the start
> of the file by FreeDOS's kernel configuration (which is part of the FreeDOS
> SYS program).

Thanks! I guess I will need to look at the lzd.asm code --- and, if necessary, the fdkernpl.asm code --- to see how to stitch everything together.

> Funny, I don't actually know how much UPX would compress things. So I made
> a test. I had to patch out the short jump in the "last page size" bytes of
> the EXE header. (These are used for the MS-DOS 6.x and FreeDOS kernel
> entrypoints.) The invalid value of the short jump instruction in that field
> otherwise leads to "CantPackException: exe header corrupted". (Obviously,
> packing the kernel file with UPX without special handling makes it no
> longer work as a kernel file.)

Not sure which short jump you are referring to --- care to elaborate?

Also, you might already know this --- but the magic for invoking UPX, converting the .exe to .sys, and adding (a second copy of) the CONFIG structure, is pretty much all in utils/exeflat.c in the kernel source tree. So the workflow is roughly like this:

{uncompressed .exe kernel}
|
v
flatten, but keep a .exe header around
|
v
compress with UPX
|
v
flatten, remove .exe header
|
v
wrap compressed kernel with stub code and CONFIG structure
|
v
{compressed .sys kernel}

The first "flattening" pass basically resolves the .exe relocations (since the kernel is known to go to 0x60:0) and removes the relocation entries. A second "flattening" pass is needed to resolve the relocations introduced by UPX itself.

I guess it will be interesting to see if UPX can be replaced with some other compressor (that also supports .exe files).

Thank you!

---
https://gitlab.com/tkchia · https://codeberg.org/tkchia · 😴 "MOV AX,0D500H+CMOS_REG_D+NMI"

ecm

Düsseldorf, Germany,
14.04.2020, 17:05

@ tkchia

New kernel compression methods - fdkernpl

Post reply

> Thanks! I guess I will need to look at the lzd.asm code --- and, if
> necessary, the fdkernpl.asm code --- to see how to stitch everything
> together.

Your best bet is to look at the mak.sh file in the lDebug repo or its sister in the RxDOS 7.2x repo. (They share most of their code.) In particular, there's this lzip run and this code which builds a compressed kernel. Adapting that to a non-EXE-mode FreeDOS kernel build gives us:

mkdir -p tmp/LZ \ && nasm path/to/ldosboot/fdkernpl.asm -f bin \ -I path/to/lmacros/ \ -D_PAYLOAD_FILE="'path/to/kernel.sys'" \ -o tmp/FDKERNEL.BIN \ && lzip -9vvfkc tmp/FDKERNEL.BIN > tmp/LZ/FDKERNEL.LZ \ && nasm path/to/inicomp/inicomp.asm \ -I path/to/lmacros/ \ -I path/to/inicomp/ -D_LZD \ -o tmp/LZ/FDKERNEL.BIN \ -D_PAYLOAD_FILE="'tmp/LZ/FDKERNEL.LZ'" -D_EXEC_OFFSET=0 \ -D_IMAGE_EXE=0 \ && nasm path/to/ldosboot/iniload.asm -f bin \ -I path/to/lmacros/ \ -I path/to/ldosboot/ \ -I path/to/scanptab/ \ -D_INILOAD_SIGNATURE="'FD'" \ -o tmp/LZ/FDKERNEL.SYS \ -D_PAYLOAD_FILE="'tmp/LZ/FDKERNEL.BIN'" -D_EXEC_OFFSET=0 \ -D_IMAGE_EXE=0

Note that you need the ldosboot, inicomp, scanptab, and lmacros repos. All of those are found on my bitbucket (legacy, hg support being dropped later this year) or my partner's hgweb server. You need lzip to compress the payload, and then you have to pass -D_LZD to the inicomp.asm build. The _PAYLOAD_FILE defines need to be wrapped in twofold quotemarks for bash, so as to pass literal quotemarks to NASM. I set the _INILOAD_SIGNATURE define to the string "FD" here, to indicate a FreeDOS kernel. The "build decomp test" step is only relevant for _IMAGE_EXE=1 kernels so I skipped all of that here.

Here's a test run doing all this, from the ldosboot subdirectory of an RxDOS 7.2x repo (this has all the needed repos as subrepos). The file kernel.sys holds the FreeDOS kernel to pack into our loader. tmp/LZ/FDKERNEL.SYS is the final kernel. I checked (in qemu) that it runs as expected.

rxdos/ldosboot$ hg id 408cd08cb836 tip rxdos/ldosboot$ hg -R .. id 3f6090716e42 tip rxdos/ldosboot$ mkdir -p tmp/LZ rxdos/ldosboot$ nasm fdkernpl.asm -f bin -I ../lmacros/ -D_PAYLOAD_FILE="'kernel.sys'" -o tmp/FDKERNEL.BIN rxdos/ldosboot$ lzip -9vvfkc tmp/FDKERNEL.BIN > tmp/LZ/FDKERNEL.LZ tmp/FDKERNEL.BIN: 1.886:1, 53.02% ratio, 46.98% saved, 80048 in, 42441 out. rxdos/ldosboot$ nasm ../inicomp/inicomp.asm -I ../lmacros/ -I ../inicomp/ -D_LZD -o tmp/LZ/FDKERNEL.BIN -D_PAYLOAD_FILE="'tmp/LZ/FDKERNEL.LZ'" -D_EXEC_OFFSET=0 -D_IMAGE_EXE=0 ../inicomp/lzd.asm:627: warning: localvariables has 14704 bytes [-w+user] ../inicomp/inicomp.asm:866: warning: inilz: 2736 bytes used for depacker [-w+user] rxdos/ldosboot$ nasm ../ldosboot/iniload.asm -f bin -I ../lmacros/ -I ../ldosboot/ -I ../scanptab/ -D_INILOAD_SIGNATURE="'FD'" -o tmp/LZ/FDKERNEL.SYS -D_PAYLOAD_FILE="'tmp/LZ/FDKERNEL.BIN'" -D_EXEC_OFFSET=0 -D_IMAGE_EXE=0 ../ldosboot/iniload.asm:743: warning: 0 bytes in front of ms7_entry [-w+user] ../ldosboot/iniload.asm:1138: warning: 3 bytes in front of ldos_entry [-w+user] ../ldosboot/iniload.asm:1526: warning: 15 bytes in front of end [-w+user] ../ldosboot/iniload.asm:1598: warning: 431 bytes in front of end2 [-w+user] rxdos/ldosboot$

Here's the result:

rxdos/ldosboot$ ls -lgG kernel.sys tmp/ tmp/LZ/ -rw-r--r-- 1 79880 Sep 22 2017 kernel.sys tmp/: total 84 -rw-r--r-- 1 80048 Apr 14 15:57 FDKERNEL.BIN drwxr-xr-x 2 4096 Apr 14 15:45 LZ tmp/LZ/: total 140 -rw-r--r-- 1 45184 Apr 14 15:58 FDKERNEL.BIN -rw-r--r-- 1 42441 Apr 14 15:57 FDKERNEL.LZ -rw-r--r-- 1 49120 Apr 14 15:58 FDKERNEL.SYS rxdos/ldosboot$

---
l

ecm

Düsseldorf, Germany,
14.04.2020, 17:06

@ tkchia

New kernel compression methods - exeExtraBytes jump

Post reply

> > Funny, I don't actually know how much UPX would compress things. So I
> made
> > a test. I had to patch out the short jump in the "last page size" bytes
> of
> > the EXE header. (These are used for the MS-DOS 6.x and FreeDOS kernel
> > entrypoints.) The invalid value of the short jump instruction in that
> field
> > otherwise leads to "CantPackException: exe header corrupted".
> (Obviously,
> > packing the kernel file with UPX without special handling makes it no
> > longer work as a kernel file.)
>
> Not sure which short jump you are referring to --- care to elaborate?

Sure! It is the jump at line 236 in iniload.asm, which reads as follows:

start: db "MZ" ; exeSignature ; dec bp, pop dx jmp strict short ms6_entry ; exeExtraBytes ; db 0EBh, 16h ; dw 16EBh

This is need because the FreeDOS, PC-DOS (6/7), and MS-DOS (6) entrypoints don't care about the kernel being in .EXE format, they always load their kernels (whole kernel at 60h:0 for FreeDOS) or initial loaders (at 70h:0 for the other three protocols) to the segment start and then jump to the entrypoint at offset zero. Because the pop dx instruction (the "Z" in the MZ .EXE signature) overwrites the dl register, we depend on ss:bp pointing to a valid BPB with the boot load unit field set.

We do need our kernel file to be in .EXE format because it can grow larger than 64 KiB, which would disable loading (properly) as a .COM format application program. This can be either simply due to the kernel's size, or due to appended large data (such as a .ZIP archive) which is valid for the RxDOS.3 / lDOS protocols. Besides, the .EXE format allows for the file to specify how much additional memory it needs (for decompression or in the case of lDebug also to make the initial relocations work). That means an error due to too little memory will be detected by the OS's executable loader, rather than later by the application itself. And the OS's loader can also determine that a potential UMB would be too small to load the application into it.

The jump instruction, as the comment indicates, sits in the "exeExtraBytes" field of the .EXE header. This field is not used by the MS-DOS executable loader I believe; its structure's field exec_len_mod_512 (link to permissively licensed MS-DOS 2 sources) is never referenced. For systems that do use the field, we assume they will treat an invalid value as some value between zero and 512. We include alignment to a 512 bytes boundary and then an additional 512 bytes of padding after the .EXE image, to insure that even with a low assumed value all of the actual image will be loaded. And the exeInitSS is calculated assuming a low exeExtraBytes too.

---
l

tom

Germany (West),
14.04.2020, 20:06
(edited by tom, 14.04.2020, 22:36)

@ ecm

New kernel compression methods

Post reply

> Yep, something like that. I don't remember the exact details but I came
> away with the impression it won't work. But FreeDOS isn't alone in thinking
> its
> kernels should be smaller than 64 KiB.

it's not FreeDOS that thinks that compressed kernels should be smaller than 64K.
but when he implemented this Tom knew that the compressed kernel was much smaller then 64K and decided not to waste valuable lifetime in thinking about kernels > 64k.
so far this decision looks good. and it would be trivial to handle larger kernels.

Tom

ecm

Düsseldorf, Germany,
16.04.2020, 17:29

@ ecm

New kernel compression methods - Updated lDebug lzd results

Post reply

Most notable change is that overlapping source and destination buffers are now allowed for the LZMA-lzip decompressor.

ldebug/tmp$ hg id 246b9ff45d45 tip ldebug/tmp$ fname="ldebug.com"; fname2="debug"; fname3="debug.big"; fnameu="ldebugu.com"; arg="/C=Q"; upcase=0; method=none; ((upcase)) && method="$(echo "$method" | tr 'a-z' 'A-Z')"; mkdir -p "$method"; cp -a ../bin/"$fnameu" "$method"/"$fname"; cp -a "$fname3" "$method/$fname2.$method"; for method in none lz; do ((upcase)) && method="$(echo "$method" | tr 'a-z' 'A-Z')"; echo -e "\nmethod=$method\nsize=$(stat -c %s "$method/$fname")"; echo -e "ini size=$(( $(stat -c %s "$method/$fname") - ( ($(stat -c %s "$method/$fname2.$method") + 15) / 16 * 16 ) ))"; echo -e "alloc=$(exememls "$method/$fname")"; echo "@echo off" > test.bat; for jj in $(seq 0 511); do echo "@$method\\$fname $arg"; done >> test.bat; (export TIMEFORMAT='%3R'; time dosemu -dumb -quiet -K "$PWD" -E "test.bat" 2> /dev/null > /dev/null); done method=none size=82944 ini size=4800 alloc=96912 bytes = 6057 paragraphs 2.234 method=lz size=53248 ini size=7680 alloc=97952 bytes = 6122 paragraphs 15.073 ldebug/tmp$

---
l

ecm

Düsseldorf, Germany,
16.04.2020, 22:06

@ ecm

New kernel compression methods - Corrections

Post reply

This part of the lDebug results is wrong. The x method does use that much memory. However, the heatshrink and lzip methods do not. That was due to an error in the mak script used to build the debugger.

> method=x> size=71680 > ini size=6384 > alloc=343920 bytes = 21495 paragraphs > 12.471 > > method=hs > size=63488 > ini size=5536 > alloc=343904 bytes = 21494 paragraphs > 7.730 > > method=lz > size=53760 > ini size=8336 > alloc=344208 bytes = 21513 paragraphs > 16.503 > ldebug/tmp$

Here are the fixed results. First, the original lzd port, then all the other methods with the updated lzd that allows overlap and halves the probability table size (localvariables < 16 KiB now).

ldebug/tmp$ hg id 246b9ff45d45+ tip ldebug/tmp$ fname="ldebug.com"; fname2="debug"; fname3="debug.big"; fnameu="ldebugu.com"; arg="/C=Q"; upcase=0; method=none; ((upcase)) && method="$(echo "$method" | tr 'a-z' 'A-Z')"; mkdir -p "$method"; cp -a ../bin/"$fnameu" "$method"/"$fname"; cp -a "$fname3" "$method/$fname2.$method"; for method in none lz; do ((upcase)) && method="$(echo "$method" | tr 'a-z' 'A-Z')"; echo -e "\nmethod=$method\nsize=$(stat -c %s "$method/$fname")"; echo -e "ini size=$(( $(stat -c %s "$method/$fname") - ( ($(stat -c %s "$method/$fname2.$method") + 15) / 16 * 16 ) ))"; echo -e "alloc=$(exememls "$method/$fname")"; echo "@echo off" > test.bat; for jj in $(seq 0 511); do echo "@$method\\$fname $arg"; done >> test.bat; (export TIMEFORMAT='%3R'; time dosemu -dumb -quiet -K "$PWD" -E "test.bat" 2> /dev/null > /dev/null); done method=none size=82944 ini size=4800 alloc=96912 bytes = 6057 paragraphs 2.280 method=lz size=53760 ini size=8208 alloc=158640 bytes = 9915 paragraphs 15.614 ldebug/tmp$ fname="ldebug.com"; fname2="debug"; fname3="debug.big"; fnameu="ldebugu.com"; arg="/C=Q"; upcase=0; method=none; ((upcase)) && method="$(echo "$method" | tr 'a-z' 'A-Z')"; mkdir -p "$method"; cp -a ../bin/"$fnameu" "$method"/"$fname"; cp -a "$fname3" "$method/$fname2.$method"; for method in none blz lz4 sz exo x hs lz; do ((upcase)) && method="$(echo "$method" | tr 'a-z' 'A-Z')"; echo -e "\nmethod=$method\nsize=$(stat -c %s "$method/$fname")"; echo -e "ini size=$(( $(stat -c %s "$method/$fname") - ( ($(stat -c %s "$method/$fname2.$method") + 15) / 16 * 16 ) ))"; echo -e "alloc=$(exememls "$method/$fname")"; echo "@echo off" > test.bat; for jj in $(seq 0 511); do echo "@$method\\$fname $arg"; done >> test.bat; (export TIMEFORMAT='%3R'; time dosemu -dumb -quiet -K "$PWD" -E "test.bat" 2> /dev/null > /dev/null); done method=none size=82944 ini size=4800 alloc=96912 bytes = 6057 paragraphs 2.253 method=blz size=64512 ini size=5920 alloc=96688 bytes = 6043 paragraphs 5.155 method=lz4 size=62976 ini size=5824 alloc=96704 bytes = 6044 paragraphs 3.403 method=sz size=70144 ini size=6000 alloc=96864 bytes = 6054 paragraphs 2.907 method=exo size=54784 ini size=5776 alloc=96736 bytes = 6046 paragraphs 6.188 method=x size=72192 ini size=6832 alloc=344512 bytes = 21532 paragraphs 12.561 method=hs size=64000 ini size=5904 alloc=96960 bytes = 6060 paragraphs 7.668 method=lz size=53248 ini size=7680 alloc=97952 bytes = 6122 paragraphs 15.084 ldebug/tmp$

Here's the RxDOS results in the same order. The mak bug did not affect this build.

rxdos/tmp$ hg id 4e74dca146e1+ tip rxdos/tmp$ fname="RxDOS.COM"; fname2="RxDOS"; fname3="RxDOS.BIN"; fnameu="RxDOSU.COM"; arg="version"; upcase=1; method=none; ((upcase)) && method="$(echo "$method" | tr 'a-z' 'A-Z')"; mkdir -p "$method"; cp -a ../bin/"$fnameu" "$method"/"$fname"; cp -a "$fname3" "$method/$fname2.$method"; for method in none lz; do ((upcase)) && method="$(echo "$method" | tr 'a-z' 'A-Z')"; echo -e "\nmethod=$method\nsize=$(stat -c %s "$method/$fname")"; echo -e "ini size=$(( $(stat -c %s "$method/$fname") - ( ($(stat -c %s "$method/$fname2.$method") + 15) / 16 * 16 ) ))"; echo -e "alloc=$(exememls "$method/$fname")"; echo "@echo off" > test.bat; for jj in $(seq 0 511); do echo "@$method\\$fname $arg"; done >> test.bat; (export TIMEFORMAT='%3R'; time dosemu -dumb -quiet -K "$PWD" -E "test.bat" 2> /dev/null > /dev/null); done method=NONE size=101376 ini size=4512 alloc=98992 bytes = 6187 paragraphs 2.231 method=LZ size=47104 ini size=8336 alloc=170704 bytes = 10669 paragraphs 15.343 rxdos/tmp$ fname="RxDOS.COM"; fname2="RxDOS"; fname3="RxDOS.BIN"; fnameu="RxDOSU.COM"; arg="version"; upcase=1; method=none; ((upcase)) && method="$(echo "$method" | tr 'a-z' 'A-Z')"; mkdir -p "$method"; cp -a ../bin/"$fnameu" "$method"/"$fname"; cp -a "$fname3" "$method/$fname2.$method"; for method in none blz lz4 sz exo x hs lz; do ((upcase)) && method="$(echo "$method" | tr 'a-z' 'A-Z')"; echo -e "\nmethod=$method\nsize=$(stat -c %s "$method/$fname")"; echo -e "ini size=$(( $(stat -c %s "$method/$fname") - ( ($(stat -c %s "$method/$fname2.$method") + 15) / 16 * 16 ) ))"; echo -e "alloc=$(exememls "$method/$fname")"; echo "@echo off" > test.bat; for jj in $(seq 0 511); do echo "@$method\\$fname $arg"; done >> test.bat; (export TIMEFORMAT='%3R'; time dosemu -dumb -quiet -K "$PWD" -E "test.bat" 2> /dev/null > /dev/null); done method=NONE size=101376 ini size=4512 alloc=98992 bytes = 6187 paragraphs 2.251 method=BLZ size=56320 ini size=6240 alloc=100496 bytes = 6281 paragraphs 4.733 method=LZ4 size=54784 ini size=5712 alloc=99984 bytes = 6249 paragraphs 3.271 method=SZ size=59904 ini size=5760 alloc=100016 bytes = 6251 paragraphs 3.195 method=EXO size=47616 ini size=5760 alloc=100016 bytes = 6251 paragraphs 5.601 method=X size=68608 ini size=6576 alloc=362992 bytes = 22687 paragraphs 24.478 method=HS size=57856 ini size=6000 alloc=100256 bytes = 6266 paragraphs 6.999 method=LZ size=46080 ini size=7312 alloc=116288 bytes = 7268 paragraphs 14.264 rxdos/tmp$

---
l

ecm

Düsseldorf, Germany,
16.04.2020, 22:22

@ ecm

New kernel compression methods - X compressor layers

Post reply

The difference in timing between this

> method=x
> size=72192
> ini size=6832
> alloc=344512 bytes = 21532 paragraphs
> 12.561

and this

> method=X
> size=68608
> ini size=6576
> alloc=362992 bytes = 22687 paragraphs
> 24.478

is due to the fact that the RxDOS kernel (second result, 24s) is compressed into two layers by the X compressor, whereas the debugger (first result, 12s) is compressed into only one layer. Dual layer operation means that the first layer's output is used as the second layer's input. The X compressor is called with -9 which makes it try adding layers until there is no more benefit in compressed size from adding another layer.

This is from building lDebug 24768bf20fbc:

Creating ldebug.com Compressing... Input size: 78144 bytes Number of layers: 1 Output size: 65352 bytes

This is the RxDOS kernel 31a3a83363f6:

Creating RxDOS.COM Compressing... Input size: 96848 bytes Number of layers: 2 Output size: 61716 bytes

---
l

ecm

Düsseldorf, Germany,
25.04.2020, 22:23

@ ecm

New kernel compression methods - Updated lzd, new lzo

Post reply

I updated the lzd depacker somewhat, in particular to use repeated string instructions for copying over matches. The saving is about 3 seconds shaved off for the test case, from 16.4s to 13.0s (lDebug) or 15.3s to 11.5s (RxDOS kernel).

I also added an LZO depacker, based on the lzo.txt file from the Linux kernel. The resulting size is fairly competitive, compressing 83 kB to 61 kB (lDebug) or 101 kB to 53 kB (RxDOS kernel). The decompression time places it among the faster methods, around 3.8s for both test cases. The LZ4 and Snappy depackers are only slightly faster.

I mailed the authors of the lzo.txt description regarding two issues with the text, one concerning the first byte interpretation (18 = 1 literal) and the other the LZO-RLE extension parsing of the L L L bits of the 0 0 0 1 H L L L instructions.

In the following I list all new test results again. Other than the LZD time optimisation and adding LZO not much has changed.

ldebug/tmp$ hg id 24b1bbf37614 tip ldebug/tmp$ fname="ldebug.com"; fname2="debug"; fname3="debug.big"; fnameu="ldebugu.com"; arg="/C=Q"; upcase=0; method=none; ((upcase)) && method="$(echo "$method" | tr 'a-z' 'A-Z')"; mkdir -p "$method"; cp -a ../bin/"$fnameu" "$method"/"$fname"; cp -a "$fname3" "$method/$fname2.$method"; for method in none blz lz4 sz exo x hs lz lzo; do ((upcase)) && method="$(echo "$method" | tr 'a-z' 'A-Z')"; echo -e "\nmethod=$method\nsize=$(stat -c %s "$method/$fname")"; echo -e "ini size=$(( $(stat -c %s "$method/$fname") - ( ($(stat -c %s "$method/$fname2.$method") + 15) / 16 * 16 ) ))"; echo -e "alloc=$(exememls "$method/$fname")"; echo "@echo off" > test.bat; for jj in $(seq 0 511); do echo "@$method\\$fname $arg"; done >> test.bat; (export TIMEFORMAT='%3R'; time dosemu -dumb -quiet -K "$PWD" -E "test.bat" 2> /dev/null > /dev/null); done method=none size=82944 ini size=4496 alloc=96912 bytes = 6057 paragraphs 2.225 method=blz size=65024 ini size=6160 alloc=97232 bytes = 6077 paragraphs 5.059 method=lz4 size=63488 ini size=6064 alloc=97248 bytes = 6078 paragraphs 3.373 method=sz size=70656 ini size=6192 alloc=97360 bytes = 6085 paragraphs 2.941 method=exo size=55296 ini size=6048 alloc=97312 bytes = 6082 paragraphs 6.159 method=x size=72192 ini size=6512 alloc=344496 bytes = 21531 paragraphs 13.263 method=hs size=64000 ini size=5632 alloc=96992 bytes = 6062 paragraphs 7.850 method=lz size=53248 ini size=7488 alloc=98064 bytes = 6129 paragraphs 12.910 method=lzo size=60928 ini size=6416 alloc=96960 bytes = 6060 paragraphs 3.786 ldebug/tmp$

rxdos/tmp$ hg id d441a721725f tip rxdos/tmp$ fname="RxDOS.COM"; fname2="RxDOS"; fname3="RxDOS.BIN"; fnameu="RxDOSU.COM"; arg="version"; upcase=1; method=none; ((upcase)) && method="$(echo "$method" | tr 'a-z' 'A-Z')"; mkdir -p "$method"; cp -a ../bin/"$fnameu" "$method"/"$fname"; cp -a "$fname3" "$method/$fname2.$method"; for method in none blz lz4 sz exo x hs lz lzo; do ((upcase)) && method="$(echo "$method" | tr 'a-z' 'A-Z')"; echo -e "\nmethod=$method\nsize=$(stat -c %s "$method/$fname")"; echo -e "ini size=$(( $(stat -c %s "$method/$fname") - ( ($(stat -c %s "$method/$fname2.$method") + 15) / 16 * 16 ) ))"; echo -e "alloc=$(exememls "$method/$fname")"; echo "@echo off" > test.bat; for jj in $(seq 0 511); do echo "@$method\\$fname $arg"; done >> test.bat; (export TIMEFORMAT='%3R'; time dosemu -dumb -quiet -K "$PWD" -E "test.bat" 2> /dev/null > /dev/null); done method=NONE size=101376 ini size=4528 alloc=98992 bytes = 6187 paragraphs 2.184 method=BLZ size=56320 ini size=6240 alloc=100480 bytes = 6280 paragraphs 4.762 method=LZ4 size=54784 ini size=5712 alloc=99968 bytes = 6248 paragraphs 3.240 method=SZ size=59904 ini size=5760 alloc=100000 bytes = 6250 paragraphs 3.087 method=EXO size=47616 ini size=5776 alloc=100016 bytes = 6251 paragraphs 5.712 method=X size=68608 ini size=6336 alloc=362736 bytes = 22671 paragraphs 24.434 method=HS size=57344 ini size=5504 alloc=99744 bytes = 6234 paragraphs 6.839 method=LZ size=46592 ini size=7824 alloc=116800 bytes = 7300 paragraphs 11.539 method=LZO size=52736 ini size=6336 alloc=100576 bytes = 6286 paragraphs 3.761 rxdos/tmp$

---
l

tom

Germany (West),
26.04.2020, 13:46

@ ecm

New kernel compression methods - Updated lzd, new lzo

Post reply

> I updated the lzd depacker somewhat, in particular
> to use repeated
> string instructions for copying over matches. The saving is about 3
> seconds shaved off for the test case, from 16.4s to 13.0s (lDebug) or 15.3s
> to 11.5s (RxDOS kernel).
>
> I also added
> an LZO
> depacker, based on the
> lzo.txt file
> from the Linux kernel. The resulting size is fairly competitive,
> compressing 83 kB to 61 kB (lDebug) or 101 kB to 53 kB (RxDOS kernel). The
> decompression time places it among the faster methods, around 3.8s for both
> test cases. The LZ4 and Snappy depackers are only slightly faster.

what hardware is this?
using 10 seconds to decompress 100K, or 10KB/s sounds tremendously slow.

could you run UPX and show results to as comparison?

ecm

Düsseldorf, Germany,
26.04.2020, 20:17

@ tom

New kernel compression methods - UPX, 512 runs clarification

Post reply

> what hardware is this?
> using 10 seconds to decompress 100K, or 10KB/s sounds tremendously slow.

The answer is given in the scriptlet, and in my original post describing that scriptlet:

> > The last line for each method gives the time in seconds
> > for a quick test, running the executable 512 times from
> > a single batch file,

In addition, note that even without any compression the test takes about 2.2 seconds, which presumably includes overhead from the dosemu startup as well as the repeated actual execution of the debugger or kernel (EXE mode, ie COM loader) initialisation and quitting.

The platform is an "AMD A10-7870K Radeon R7, 12 Compute Cores 4C+8G" (a quadcore CPU) running Debian testing (bullseye) amd64, with a recent dosemu2 built from its git repo.

> could you run UPX and show results to as comparison?

Sure, good idea. This is the UPX from the Debian package version 3.95-2+b1, which I believe is an UPX-UCL (FLOSS) build. I included only the tests of the uncompressed and the UPX-compressed executable.

Note that the 4.5 kB initial loader stage is dropped by UPX. Thus the filesize should be interpreted with that in mind. The "ini size" result is not meaningful for these UPX runs because UPX doesn't give us the same way to determine how large its depacker stub is. I went with the --best --ultra-brute --8086 switches. As mentioned in the other post, "The --8086 option does not appreciably alter the result." As also mentioned in that post, "I had to patch out the short jump in the "last page size" bytes of the EXE header."

The results, compared to those in the "Updated lzd, new lzo" post, have UPX as a very fast depacker, the fastest of all of them in fact. The compression ratio is competitive. The debugger is packed from 83 kB to 51 kB. However, with the size of the dropped initial loader, the value to compare should be 55 kB. The Exomizer 3 (55 kB) and LZMA-lzip (53 kB) methods beat this calculated value. The kernel is packed from 101 kB to 43 kB. This gives 47 kB as the value to compare. Again Exomizer 3 (48 kB) and LZMA-lzip (47 kB) are very close.

ldebug/tmp$ upx --version upx 3.95 UCL data compression library 1.03 zlib data compression library 1.2.11 LZMA SDK version 4.43 Copyright (C) 1996-2018 Markus Franz Xaver Johannes Oberhumer Copyright (C) 1996-2018 Laszlo Molnar Copyright (C) 2000-2018 John F. Reiser Copyright (C) 2002-2018 Jens Medoch Copyright (C) 1995-2005 Jean-loup Gailly and Mark Adler Copyright (C) 1999-2006 Igor Pavlov UPX comes with ABSOLUTELY NO WARRANTY; for details type 'upx -L'. ldebug/tmp$ hg id 24b1bbf37614 tip ldebug/tmp$ fname="ldebug.com"; fname2="debug"; fname3="debug.big"; fnameu="ldebugu.com"; arg="/C=Q"; upcase=0; method=none; ((upcase)) && method="$(echo "$method" | tr 'a-z' 'A-Z')"; mkdir -p "$method"; cp -a ../bin/"$fnameu" "$method"/"$fname"; cp -a "$fname3" "$method/$fname2.$method"; method=upx; ((upcase)) && method="$(echo "$method" | tr 'a-z' 'A-Z')"; mkdir -p "$method"; cp -a ../bin/"$fnameu" "$method"/"$fnameu"; echo -ne "File: $method/$fnameu\n000002: 00 00 [ EB 16 ]\n" >> "$method"/"$fname2".pat; bpatch -f "$method"/"$fname2".pat; upx --best --ultra-brute --8086 -fvvvv -o "$method"/"$fname" "$method"/"$fnameu"; cp -a "$method"/"$fname" "$method"/"$fname2.$method"; for method in none upx; do ((upcase)) && method="$(echo "$method" | tr 'a-z' 'A-Z')"; echo -e "\nmethod=$method\nsize=$(stat -c %s "$method/$fname")"; echo -e "ini size=$(( $(stat -c %s "$method/$fname") - ( ($(stat -c %s "$method/$fname2.$method") + 15) / 16 * 16 ) ))"; echo -e "alloc=$(exememls "$method/$fname")"; echo "@echo off" > test.bat; for jj in $(seq 0 511); do echo "@$method\\$fname $arg"; done >> test.bat; (export TIMEFORMAT='%3R'; time dosemu -dumb -quiet -K "$PWD" -E "test.bat" 2> /dev/null > /dev/null); done Ultimate Packer for eXecutables Copyright (C) 1996 - 2018 UPX 3.95 Markus Oberhumer, Laszlo Molnar & John Reiser Aug 26th 2018 File size Ratio Format Name -------------------- ------ ----------- ----------- 82944 -> 51427 62.00% dos/exe ldebug.com Packed 1 file. method=none size=82944 ini size=4496 alloc=96912 bytes = 6057 paragraphs 2.301 method=upx size=51427 ini size=-13 alloc=97200 bytes = 6075 paragraphs 2.778 ldebug/tmp$

rxdos/tmp$ upx --version upx 3.95 UCL data compression library 1.03 zlib data compression library 1.2.11 LZMA SDK version 4.43 Copyright (C) 1996-2018 Markus Franz Xaver Johannes Oberhumer Copyright (C) 1996-2018 Laszlo Molnar Copyright (C) 2000-2018 John F. Reiser Copyright (C) 2002-2018 Jens Medoch Copyright (C) 1995-2005 Jean-loup Gailly and Mark Adler Copyright (C) 1999-2006 Igor Pavlov UPX comes with ABSOLUTELY NO WARRANTY; for details type 'upx -L'. rxdos/tmp$ hg id d441a721725f tip rxdos/tmp$ fname="RxDOS.COM"; fname2="RxDOS"; fname3="RxDOS.BIN"; fnameu="RxDOSU.COM"; arg="version"; upcase=1; method=none; ((upcase)) && method="$(echo "$method" | tr 'a-z' 'A-Z')"; mkdir -p "$method"; cp -a ../bin/"$fnameu" "$method"/"$fname"; cp -a "$fname3" "$method/$fname2.$method"; method=upx; ((upcase)) && method="$(echo "$method" | tr 'a-z' 'A-Z')"; mkdir -p "$method"; cp -a ../bin/"$fnameu" "$method"/"$fnameu"; echo -ne "File: $method/$fnameu\n000002: 00 00 [ EB 16 ]\n" >> "$method"/"$fname2".pat; bpatch -f "$method"/"$fname2".pat; upx --best --ultra-brute --8086 -fvvvv -o "$method"/"$fname" "$method"/"$fnameu"; cp -a "$method"/"$fname" "$method"/"$fname2.$method"; for method in none upx; do ((upcase)) && method="$(echo "$method" | tr 'a-z' 'A-Z')"; echo -e "\nmethod=$method\nsize=$(stat -c %s "$method/$fname")"; echo -e "ini size=$(( $(stat -c %s "$method/$fname") - ( ($(stat -c %s "$method/$fname2.$method") + 15) / 16 * 16 ) ))"; echo -e "alloc=$(exememls "$method/$fname")"; echo "@echo off" > test.bat; for jj in $(seq 0 511); do echo "@$method\\$fname $arg"; done >> test.bat; (export TIMEFORMAT='%3R'; time dosemu -dumb -quiet -K "$PWD" -E "test.bat" 2> /dev/null > /dev/null); done Ultimate Packer for eXecutables Copyright (C) 1996 - 2018 UPX 3.95 Markus Oberhumer, Laszlo Molnar & John Reiser Aug 26th 2018 File size Ratio Format Name -------------------- ------ ----------- ----------- 101376 -> 43133 42.55% dos/exe RxDOS.COM Packed 1 file. method=NONE size=101376 ini size=4528 alloc=98992 bytes = 6187 paragraphs 2.290 method=UPX size=43133 ini size=-3 alloc=99376 bytes = 6211 paragraphs 2.735 rxdos/tmp$

---
l