DOS ain't dead

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

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

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"

> > 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

> 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

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"

> 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

> > 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

> 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

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

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

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

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

> 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?

> 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