|
|
|
|
— |
blog:pushbx:2026:0711_early_july_compression_woes [2026-07-11 20:33:58 +0200 Jul Sat] (current)
ecm created |
| | ====== Early July: Compression woes ====== |
| | |
| | **2026-07-11** |
| | |
| | This week I found some bugs in several compression details, and I also found something I thought was a bug but isn't. |
| | |
| | |
| | ===== lDOS kernel ===== |
| | |
| | * [[https://hg.pushbx.org/ecm/msdos4/rev/5250f229c862|Empty changeset to rebuild]] with new LZSA2N depacker. |
| | |
| | |
| | ===== mvcomp ===== |
| | |
| | * [[https://hg.pushbx.org/ecm/mvcomp/shortlog/4fdc51b7b12e|Import several commits]] from last year. |
| | |
| | |
| | ===== lDOS boot ===== |
| | |
| | * directpl.asm: [[https://hg.pushbx.org/ecm/ldosboot/rev/29cd20bfd32e|Add a payload stage that just passes through]] a given binary as the payload directly. Needed for using kernwrap if the caller provides an lDOS boot payload stage in a binary file. |
| | |
| | |
| | ===== lfreedos ===== |
| | |
| | * [[https://hg.pushbx.org/ecm/lfreedos/rev/13fbb34277dc|Add a "syntax: glob" line]] to the .hgignore file. |
| | |
| | |
| | ===== testcy ===== |
| | |
| | * Import lfreedos history. |
| | * [[https://hg.pushbx.org/ecm/testcy/rev/9a20ba61a5a9|Make an address underflow test]]. This is supposed to check that a kernel-mode inicomp depacking to 00600h, in the heatshrink format with INICOMP_HEATSHRINK_Z=0, will properly handle the underflow of an all-zeroes match that's longer than the 1.5 KiB of address space below the destination. Turns out there is no bug, [[https://hg.pushbx.org/ecm/inicomp/file/5bc471e8d9a2/heatshr.asm#l420|the underflow is correctly handled]]. |
| | * [[https://hg.pushbx.org/ecm/testcy/rev/037646458576|Add the testcy.bin file to .hgignore]] |
| | |
| | |
| | ===== kernwrap ===== |
| | |
| | Most of these changes are mirrored in lDebug's mak.sh, either imported from lDebug to kernwrap or the other way around. |
| | |
| | * [[https://hg.pushbx.org/ecm/kernwrap/rev/d9ed88b86edf|Support ZX0 inicomp method]]. |
| | * [[https://hg.pushbx.org/ecm/kernwrap/rev/6abf41bf1602|Use binbigfile variable]], partial pick from [[https://hg.pushbx.org/ecm/ldebug/rev/d2ae80e1d614|an lDebug change]] (2026-03-16) added as part of the link branch (using makefiles, object fils, and the linker). |
| | * [[https://hg.pushbx.org/ecm/kernwrap/rev/eed208fd986d|Fix replacing filename extension]] for the double-compressed file (.bi2) |
| | * Older lDebug patches: |
| | * [[https://hg.pushbx.org/ecm/kernwrap/rev/c24d7ce7ce43|Append test program payload]]. |
| | * [[https://hg.pushbx.org/ecm/kernwrap/rev/28d3e4da364b|Allow using XMS]] for decompression test. |
| | * [[https://hg.pushbx.org/ecm/kernwrap/rev/9cb2df0fe40e|Allow using executable file]] for decompression test. |
| | * [[https://hg.pushbx.org/ecm/kernwrap/rev/cdb456f9b507|Allow using either XMS or executable file]] for decompression test in a single executable. |
| | * [[https://hg.pushbx.org/ecm/kernwrap/rev/fc086ded6835|Fix the long literal INICOMP_LZEXEDAT_L) option]] using variables of the 4 KiB window option. |
| | * [[https://hg.pushbx.org/ecm/kernwrap/rev/ead19bbec1d7|Support ecm lzsa2 -M switch]]. |
| | * [[https://hg.pushbx.org/ecm/kernwrap/rev/fd8d319ec822|And the -N switch]]. |
| | * [[https://hg.pushbx.org/ecm/kernwrap/rev/d3a4565516bc|Auto-detect -N switch]]. (As the -M switch's only advantage over -N is higher compatibility, it isn't auto-detected.) |
| | * [[https://hg.pushbx.org/ecm/kernwrap/rev/4c525de10838|Support and auto-detect -S switch]]. (While this does pass an _S define to inicomp, this isn't actually used.) |
| | * [[https://hg.pushbx.org/ecm/kernwrap/rev/1ac63f913d72|Fix to filter out]] the "Terminated ..." line for the progress decompression test. |
| | * [[https://hg.pushbx.org/ecm/kernwrap/rev/bd565df2c62d|Add support for decompression scan]]. |
| | * [[https://hg.pushbx.org/ecm/kernwrap/rev/184baee31614|Fix build of a small inicomp test program]]. The allocation had a term of minus 1024 that was meant to account for the INIT1 size. Somehow this made the test program fail on small payloads. It wasn't strictly needed anyway so I stripped it out. |
| | |
| | |
| | ===== lDebug ===== |
| | |
| | * [[https://hg.pushbx.org/ecm/ldebug/rev/00ca022cf1e0|Fix long literal option]] using 4 KiB variables. |
| | * [[https://hg.pushbx.org/ecm/ldebug/rev/63be6e87b684|Support lzsa -M]]. |
| | * [[https://hg.pushbx.org/ecm/ldebug/rev/2c6730c4736f|Support lzsa -N]]. |
| | * [[https://hg.pushbx.org/ecm/ldebug/rev/68846b42be73|Use the binbigext variable for changing to .bi2 filename extension]] in the double compressed test case. Unifies this code with kernwrap's mak.sh |
| | * [[https://hg.pushbx.org/ecm/ldebug/rev/5ce9a377750b|Auto-detect lzsa -N]]. |
| | * [[https://hg.pushbx.org/ecm/ldebug/rev/c9bb3535fbc8|Add three variables to the veriable setup]] for reproducing. (This bit is exclusive to lDebug, not present in kernwrap.) |
| | * doc: [[https://hg.pushbx.org/ecm/ldebug/rev/17af28a2a22a|Add ZX0 depacker]] to addusage.src |
| | * doc: [[https://hg.pushbx.org/ecm/ldebug/rev/5c5429e57299|Mention]] lzsa -N, zerocomp, mvcomp, zx0 methods. |
| | * doc: [[https://hg.pushbx.org/ecm/ldebug/rev/5a99eff861f5|Document new variables]]. |
| | * doc: [[https://hg.pushbx.org/ecm/ldebug/rev/6dca0a09335a|Link to the entire lzsa Pull Request]] rather than a single comment. |
| | * doc: [[https://hg.pushbx.org/ecm/ldebug/rev/9104436ab96e|List zx0 again]]. |
| | * doc: [[https://hg.pushbx.org/ecm/ldebug/rev/d1c682e4bbc3|List LZSA2N]] in news-r11 |
| | * [[https://hg.pushbx.org/ecm/ldebug/rev/e7d852a01db4|Support lzsa -S switch]] and auto-detect it. |
| | * doc: [[https://hg.pushbx.org/ecm/ldebug/rev/80c4d2a124ff|Document lzsa -S]]. |
| | * [[https://hg.pushbx.org/ecm/ldebug/rev/a1f8d77ad719|Add INICOMP_LZSA_S]] to variable setup. |
| | * [[https://hg.pushbx.org/ecm/ldebug/rev/523354a1c5d0|Filter out Terminated line]] for progress test. |
| | * [[https://hg.pushbx.org/ecm/ldebug/rev/68ff079d7749|Add support for decompression scan]]. |
| | * [[https://hg.pushbx.org/ecm/ldebug/rev/7273c0f26e77|Fix small inicomp test programs]]. |
| | |
| | |
| | ===== testrand ===== |
| | |
| | This is a test program for inicomp to test maximum block sizes with lots of uncompressible data. The data used was generated from the server's /dev/random device. |
| | |
| | * Import lfreedos and testcy history. |
| | * [[https://hg.pushbx.org/ecm/testrand/rev/64201df8c58c|Adjust names]] to testrand. |
| | * [[https://hg.pushbx.org/ecm/testrand/rev/c1ecdb52a02c|Add a 32 KiB random data file]]. |
| | * [[https://hg.pushbx.org/ecm/testrand/rev/e152067e6ffb|Add the random data]] to the program. |
| | * [[https://hg.pushbx.org/ecm/testrand/rev/435d30491082|Move random data to end]] of the payload image. |
| | * [[https://hg.pushbx.org/ecm/testrand/rev/a3471894d31a|Enlarge random data to 128 KiB]]. This caused the LZSA2 depacker to fail, for multiple reasons. The fixes required were to add the -S switch to lzsa, and to account for uncompressed block lengths in the depacker. |
| | * [[https://hg.pushbx.org/ecm/testrand/rev/ea5e09c3c873|Pass mak.sh parameters]] to the NASM command. |
| | * [[https://hg.pushbx.org/ecm/testrand/rev/8aee68984451|Add defines for smaller test payloads]]. This exposed several small payload test failures, in the mak.sh scripts (see above) and in the LZMA-lzip depacker. |
| | |
| | |
| | ===== LZSA ===== |
| | |
| | * Problem described in [[https://pushbx.org/ecm/bug/1011/|ticket #1011]]. The lzsa packer operated on 64 KiB blocks, but with the frame header taken into account, a compressed block consisting of exactly 64 KiB of compressed data could start eg at offset 6 (of a normalised pointer). Therefore the offset could overflow if not specifically normalised during processing of this block. |
| | |
| | The lack of pointer normalisation is a major feature of the LZSA2 depacker, so it was undesirable to work around the problem on our end. Instead, I added the -S switch which makes the packer operate on 65_520 B blocks rather than full 64 KiB ones. Now regardless of the frame header, a normalised address at the start of a block (compressed or uncompressed) won't overflow until after the block is completely processed. |
| | |
| | ==== The patch ==== |
| | |
| | <blockquote>[[https://github.com/ecm-pushbx/lzsa/commit/8d11612acd26c0be16adff2c1bf4cf378d05bfdd|New commit]] added: |
| | |
| | **Add capital -S, smaller blocks (<= 65_520 rather than <= 65_536)** |
| | |
| | This insures that whatever offset 0..15 is in SI after having just processed a frame header (either for a compressed or uncompressed block), adding the length of the source block won't overflow SI past 65_535. This invariant is required to efficiently handle large blocks without intra-block pointer normalisation. With large uncompressible (random data) blocks, lDOS inicomp could fail to depack as SI + length of block could overflow. |
| | |
| | <cite>[[https://github.com/emmanuel-marty/lzsa/pull/74#issuecomment-4938446585|My comment]] on the lzsa Pull Request</cite></blockquote> |
| | |
| | |
| | ===== inicomp ===== |
| | |
| | * [[https://hg.pushbx.org/ecm/inicomp/rev/28a25b6dc29f|Add _UNSAFE option for LZSA2 depacker]]. Decreases the amount of buffer size bookkeeping kept track of. |
| | * [[https://hg.pushbx.org/ecm/inicomp/rev/b4bee386f2db|Support _N option]] to make use of lzsa -N switch. |
| | * For _UNSAFE and _N both selected, [[https://hg.pushbx.org/ecm/inicomp/rev/b68681741761|completely get rid of buffer lengths bookkeeping]]. |
| | * Fix, [[https://hg.pushbx.org/ecm/inicomp/rev/09184219288e|account for lengths of uncompressed blocks]]. This never came up because typically there are no uncompressed blocks. The testrand example proved that this fix is needed. |
| | * [[https://hg.pushbx.org/ecm/inicomp/rev/152fed5c244a|Add macros for note section and note incbin]]. This allows to post-process using convlist.pl so that the listing file of embedded binaries can be listed in a resulting .tls file. The note incbin facility was [[https://hg.pushbx.org/ecm/instsect/file/17a79f48fff1/instsect.asm#l49|lifted from instsect]], while the note section one was [[https://hg.pushbx.org/ecm/ldebug/file/7273c0f26e77/source/debug.mac#l98|lifted from lDebug]]. |
| | * [[https://hg.pushbx.org/ecm/inicomp/rev/7cdb390be625|Add scan support to inicomp]]. This is a scanner that runs ahead of the usual tests of the test program, displaying statistics on the payload such as its depacked size and the "maximum bytes ahead" amount. The latter is equivalent to calculating the allocation size needed to depack, but as opposed to inicomp's stubborn repeated depacking binary search loop, the exact same result is obtained from a single scan run. |
| | * [[https://hg.pushbx.org/ecm/inicomp/rev/e50bb1dac48b|Support scan mode]] in LZSA2 depacker. This scanner doesn't require an output buffer, only processing the source data and keeping track of a virtual output pointer that starts out at all-zeroes. |
| | * [[https://hg.pushbx.org/ecm/inicomp/rev/4056d48a685c|Shorten scan output line]]. |
| | * [[https://hg.pushbx.org/ecm/inicomp/rev/67297bf50f18|Support scan mode]] in mvcomp depacker. This is relevant because [[https://github.com/SvarDOS/bugz/issues/127|the discussions around the mvcomp packer]] and the mvsize tool that I contributed produced the algorithm with which the scanner determines the maximum bytes ahead using a single scan run. This is the plussrc and plusdst method, which keeps track of how far into each buffer the source and destination pointers are. The checks are needed after expanding matches that take more space in the decompressed buffer than in the compressed data, precisely when my existing code called check_pointers_not_overlapping, so the scan checks are done in that function. |
| | * In inicomp.asm [[https://hg.pushbx.org/ecm/inicomp/rev/9d04d891bbab|pass the buffer to scan function]]. The existing (LZSA2 and mvcomp) scanners do not need this and will ignore the additional parameters on the stack. However, the buffer is needed for the next scanner to be added. |
| | * [[https://hg.pushbx.org/ecm/inicomp/rev/11c2c78372f8|Place the scan binary at origin 0]] in the INIT2 section. Needed if the scanner refers to its own code section using offsets rather than only relative branches. |
| | * [[https://hg.pushbx.org/ecm/inicomp/rev/89f0b886144c|Fix LZMA-lzip depacker for small buffer sizes]], the bxcx subtraction can check both registers *only* for subtraction borrow (CY). It tried checking for ZR also (jbe), which is invalid, as it branches also if only the upper word is zero. Add work around code to check for cx being zero separately. |
| | * [[https://hg.pushbx.org/ecm/inicomp/rev/507dfd1bf72f|Drop a forgotten jcxz]] in the LZMA-lzip depacker. This early oversight did not lead to a disaster (and much more obvious bug) purely due to luck. Bug in [[https://hg.pushbx.org/ecm/inicomp/rev/158d3d0479fd|hg 158d3d0479fd]] on 2020-04-12. |
| | * In mvcomp.asm for _SCAN binary [[https://hg.pushbx.org/ecm/inicomp/rev/3737885480ed|make sure offset 0 is the entrypoint]]. |
| | * [[https://hg.pushbx.org/ecm/inicomp/rev/ea2edce0d911|Support scan mode]] for LZMA-lzip depacker. Unlike the earlier scanners, this one requires a destination buffer. The reasons are twofold: There's the local variables, some 16 KiB of data structures that are set up dynamically in the destination buffer. These are intrinsically required by the depacker. The other reason is the fact that the depacker "peeks" into the past decompressed data to steer its control flow for depacking subsequent data. |
| | * [[https://hg.pushbx.org/ecm/inicomp/rev/5bc471e8d9a2|Change the error message for lack of scan mode support]] to a %fatal error. This avoids the spam about labels "changed during code generation" that is produced when using %error |
| | |
| | |
| | ===== lmacros ===== |
| | |
| | **ETA**: |
| | |
| | * [[https://hg.pushbx.org/ecm/lmacros/rev/b1e37316f1ca|Disable label-redef-late warning]]. This addresses the same problem as the last inicomp change, but instructs the assembler to silence this warning. As mentioned in the comment, we previously used grep commands to filter out the uninteresting warnings. |
| | |
| | |
| | ===== The old mvcomp related thread on SvarDOS bugz tracker ===== |
| | |
| | I [[https://github.com/SvarDOS/bugz/issues/127#issuecomment-4944955160|commented on]] a 2024 SvarDOS bugz thread discussing the mvcomp format, as well as the three methods to determine "max bytes ahead" or the "allocation" required for depacking with destination starting below and overlapping the source. [[blog:pushbx:2024:1013_late_september_early_october_work#mvcomp|As previously discussed]] on the blog. |
| | |
| | <blockquote> |
| | |
| | <blockquote>2. I also [[https://hg.pushbx.org/ecm/mvcomp/rev/0cc061c18c01|added a maxbytesahead calculation]] to the first depack run. The resulting maxunitsahead should match what the stubborn mvsize run calculates. That means if everything works we don't have to do the entire run any longer, just the first depack call would suffice.</blockquote> |
| | |
| | I just updated my inicomp LZSA2, mvcomp, and LZMA-lzip depackers with a "scan" mode. This [[https://hg.pushbx.org/ecm/inicomp/file/5bc471e8d9a2/inicomp.asm#l2369|returns four results]]: |
| | |
| | * Success or error status |
| | * Progress ticks (how often the counter variable is incremented) |
| | * maxbytesahead |
| | * Depacked size |
| | |
| | The maxbytesahead calculation uses my technique from mvsize mentioned above. The scan caller can trivially calculate the maxparasahead (just divide by 16, rounding up) and then the allocation needed (maxparasahead [[https://hg.pushbx.org/ecm/inicomp/file/5bc471e8d9a2/inicomp.asm#l2441|plus compressed payload size plus init1 depacker size]]), which absent bugs exactly matches the stubborn binary search result that is found by repeatedly running the depacker. |
| | |
| | Out of these methods, mvcomp and LZSA2 never refer to the depacked data except for window matches that generate more depacked data. Therefore, their scanners do not actually need any destination buffer memory and will work on virtual pointers. LZMA-lzip however, I found it [[https://hg.pushbx.org/ecm/inicomp/file/5bc471e8d9a2/lzd.asm#l612|does "peek" into previously depacked data]] to control the decompression, so its scanner has to actually depack the data. |
| | |
| | Here's an example: |
| | |
| | ''~/proj/testrand$ INICOMP_WINNER=smallest INICOMP_METHOD='lzsa2 mvcomp lzd' use_build_decomp_test_size=1 use_build_decomp_scan=1 use_build_decomp_test_file=1 use_build_decomp_test_xms=1 ./mak.sh -DEMPTY'' |
| | |
| | This uses the testrand, kernwrap, lmacros, ldosboot, inicomp, and scanptab repos from [[https://hg.pushbx.org/ecm/|our hgweb]] |
| | |
| | And here's the parts of the example output that are interesting: |
| | |
| | <code>About to Execute : ttestr.com |
| | Note: Scan depack=48 pack=49 ahead=4,para=1 alloc=84 tick=2 |
| | Info: 1SSSSSSF |
| | 84 |
| | About to Execute : ttestr.com c |
| | Note: Scan depack=48 pack=49 ahead=4,para=1 alloc=84 tick=2 |
| | 0 |
| | 0 progress dots, method lzsa2 |
| | ... |
| | About to Execute : ttestr.com |
| | Note: Scan depack=48 pack=38 ahead=10,para=1 alloc=59 tick=4 |
| | Info: 1SSSSSSF |
| | 59 |
| | About to Execute : ttestr.com c |
| | Note: Scan depack=48 pack=38 ahead=10,para=1 alloc=59 tick=4 |
| | 0 |
| | 0 progress dots, method mvcomp |
| | ... |
| | About to Execute : ttestr.com |
| | Note: Scan depack=48 pack=74 ahead=14688,para=918 alloc=1099 tick=36 |
| | Info: 1SFFSFFFSSSF |
| | 1099 |
| | About to Execute : ttestr.com c |
| | Note: Scan depack=48 pack=74 ahead=14688,para=918 alloc=1099 tick=36 |
| | 0 |
| | 0 progress dots, method lzd</code> |
| | |
| | (LZMA-lzip has several KiB of local variables that it puts into the depack buffer, hence the large maxbytesahead.) |
| | |
| | Note how the ''alloc='' exactly matches the number displayed after the ''Info: 1...'' line.</blockquote> |
| | |
| | |
| | {{tag>ldos msdos4 mvcomp ldosboot lfreedos testcy kernwrap ldebug testrand lzsa inicomp lmacros}} |
| | |
| | |
| | ~~DISCUSSION~~ |
| |
