2024-10-13

Last Sunday (2024-10-06) I travelled back from my partner's place, so I didn't get to write a blog post. Therefore we'll cover two weeks' worth of work today.

All of these changes were picked from lDebug.

• Add support for INICOMP_HEATSHRINK_Z to optimise heatshrink depacker
• Support mvcomp compression method
• Update config file to add zerocomp and mvcomp compression methods

Prompted by a SvarDOS issue for the EDR-DOS kernel, I optimised the bdevio.nas function div64. I'd noticed that its stack layout exactly matches the div32 function. The div64 function implements a very slow bitwise loop to do the division with up to 64-bit dividend and up to 32-bit divisor. My optimisation consists of checking the upper 32 bits of the dividend; if they're zero, pass control to the div32 function instead. This causes a great speedup apparently.

I later picked a comment from the SvarDOS repo's pick of my changeset.

The only unrelated changeset in our EDR-DOS repo is a pick from SvarDOS to supply a video page and attribute for a few int 10.0E calls in drbio/console.nas (as usual I picked the change in the JWasm source texts into both that and the NASM ported sources for the lDOS repo). (Issue at SvarDOS EDR-DOS repo.)

• Add testfile application that uses the inicomp depackers to depack a single file, and write to an output file. This involves passing the depacked size from the depack function to the caller.
• Add -v switch to testfile for verbose debugging output.
• In heatshrink depacker verbose output display destination and source offsets.
• In heatshrink depacker add verbose message for storing zeroes (backreference matches that reference the initial window before the start of the uncompressed data).
• Add -e switch to testfile for exceptional debugging messages. (The -v switch enables a superset of the -e switch messages.)
• Fix heatshrink depacker to work in the inicomp stage again, it had the _TESTFILE define too late.
• Optimise heatshrink depacker with _Z define to drop code for storing zeroes for initial window backreferences, shrinking the depacker somewhat.

The remaining changes involve the mvcomp compression method, based on SvarDOS's language file packer:

• Add mvcomp depacker.
• Support _MVCOMP define for mvcomp depacker.
• Optimise mvcomp depacker:
  • Inline get_word as only a single spot ever called it.
  • In copy_data only support lengths < 256 Bytes.
  • Drop unused .end_check code.
• Double the number of progress dots emitted by mvcomp depacker.
• Add testfile verbose output for matches to mvcomp depacker.

The FAT32 + FSIBOOT boot sector loader was updated a little. In a new revision of the experimental protocol, the directory search function now returns with ds set equal to es (the directory buffer segment) upon success. A week later, I updated the FSIBOOT revision to the non-experimental FSIBOOT5 and pushed the changes to both the ldosboot.exp and the ldosboot repos.

The only changes concern logging the dates of the FSIBEX05 and FSIBOOT5 revisions of the two-stage FAT32 loaders.

Patch to add the -z switch:

Add -z switch (no initial window references) to encoder

As discussed on the SvarDOS issue tracker, refer to: SvarDOS/bugz#127 (comment)

Particular the store zeros calls concern me because they may impose complications on the depacker, if it doesn't use a circular buffer. I may look into adding a mode to heatshrink that forbids references that point before the depacked data.

For example, the lDOS inicomp depacker for heatshrink does some special handling to store zeros. This code can be dropped if the encoder's new -z switch is used: https://hg.pushbx.org/ecm/inicomp/file/f5f72d7078a2/heatshr.asm#l443

Also submitted as a Pull Request, albeit it is unlikely to receive any attention.

• Add option INICOMP_HEATSHRINK_Z with auto-detection whether heatshrink supports the -z switch that I added in the heatshrink patch. This allows to enable the _Z define to inicomp's heatshrink depacker to optimise it, at very little cost to the size of the compressed payload.
• Fix assembling of externally-built help pages, ext_data_max_size_equate wasn't defined
• Add handling of heatshrink -z switch to compressed help build in mak.sh
• hshrink.asm: Add _Z define for optimisation of help page depacker
• Support mvcomp inicomp method in mak.sh and in cfg.sh
• Update cfg.sh to list both mvcomp and zerocomp

Other than an update to the news manual section, all other changes concern the TSC Extension for lDebug (created because of a request from @boeckmann):

• Initial commit of the ELD, featuring installable ELD, a dword variable LASTTSC, and two different commands, TSC (display TSC and write variable) and TSC QUIET (only write variable).
• Add tsc.eld to source/eld/mak.sh and to extlib.asm
• Make LASTTSC an array variable to allow access to high dword
• Add two patch areas to the debugger entry section, in run (any mode) and intrtn (86 Mode only)
• Install tsc.eld handlers into the patch areas

The mvcomp algorithm is a simple, word-based compression method created for the SvarDOS multi-language support library. I contributed mvsize, a tool that reads in the original file and the compressed file, and returns how much buffer space is needed exactly to depack the packed data within an in-place depack buffer.

• Initial commit, only depack once with a full buffer (not in-place depacking).
• Do binary search to find the minimum buffer size in the stubborn way, like inicomp test A mode.
• Fix a wrong overflow check.
• Fix wrong filenames in error messages.
• Change overflow checks to do the rounding first and check whether it results in a smaller value, rather than hardcoding the maximum values.
• Allow to specify an allocation unit (must be a power of 2) on the command line as a third parameter.
• Allow empty string as third parameter, for the default unit of 1 paragraph.
• Calculate maxbytesahead variable during first depack run, which should calculate the same buffer size as determined by the stubborn inicomp inspired test run.

I also fixed a few typos in the mvcomp documentation, and initially documented how I translated the svn repository into an hg repo. All other changesets consist of picks from the original mvcomp repo. In turn, mvcomp's repo picked my changes into the original svn repository.

The development of mvcomp mostly consisted of a back and forth in a SvarDOS issue related to their choice of TREE application. I do not care much for TREE, but I did participate in the talks about mvcomp.

One memorable part is the in-place depack buffer size formula by @mateuszviste (whose initials gave mvcomp its name). This formula says that the combined in-place buffer, including the initial prefix size (as given by my mvsize tool also) and the size of the compressed payload, can always be sized as UncompressedSize + UncompressedSize / 31 + 1. This is a worst-case calculation, unlike mvsize it may result in allocating a larger buffer than needed. However, it appears to be a universal upper boundary for the needed buffer size.

I didn't believe this at first when he shared it, but did come around after some more discussion. In practice SvarLANG uses its packer's maxbytesahead approach which is equivalent to mvsize (and also done by the depacker in the latest mvsize revision).