unaplib_small.asm

;
;  Size-optimized ApLib decompressor by spke & uniabis (ver.04 01-07/06/2020, 139 bytes)
;
;  The original Z80 decompressor for ApLib was written by Dan Weiss (Dwedit),
;  then tweaked by Francisco Javier Pena Pareja (utopian),
;  and optimized by Jaime Tejedor Gomez (Metalbrain).
;
;  This version was heavily re-optimized for size by spke.
;  (It is 17 bytes shorter and 22% faster than the 156b version by Metalbrain.)
;
;  ver.00 by spke (21/08/2018-01/09/2018, 141 bytes);
;  ver.01 by spke (spring 2019, 140(-1) bytes, slightly faster);
;  ver.02 by spke (05-07/01/2020, added full revision history, support for long offsets
;                  and an option to use self-modifying code instead of IY)
;  ver.03 by spke (18-29/05/2020, +0.5% speed, added support for backward compression)
;  ver.04 by uniabis (01-07/06/2020, 139(-1) bytes, +1% speed, added support for HD64180)
;
;  The data must be compressed using any compressor for ApLib capable of generating raw data.
;  At present, two best available compressors are:
;
;  "APC" by Sven-Ake Dahl: https://github.com/svendahl/cap or
;  "apultra" by Emmanuel Marty: https://github.com/emmanuel-marty/apultra
;
;  The compression can be done as follows:
;
;  apc.exe e <sourcefile> <outfile>
;  or
;  apultra.exe <sourcefile> <outfile>
;
;  A decent compressor was written by r57shell (although it is worse than compressors above):
;  http://gendev.spritesmind.net/forum/viewtopic.php?p=32548#p32548
;  The use of the official ApLib compressor by Joergen Ibsen is not recommended.
;
;  The decompression is done in the standard way:
;
;  ld hl,FirstByteOfCompressedData
;  ld de,FirstByteOfMemoryForDecompressedData
;  call DecompressApLib
;
;  Backward decompression is also supported; you can compress files backward using:
;
;  apultra.exe -b <sourcefile> <outfile>
;
;  uncomment option "DEFINE BackwardDecompression" and decompress the resulting files using:
;
;  ld hl,LastByteOfCompressedData
;  ld de,LastByteOfMemoryForDecompressedData
;  call DecompressApLib
;
;  The decompressor modifies AF, AF', BC, DE, HL, IX.
;
;  Of course, ApLib compression algorithms are (c) 1998-2014 Joergen Ibsen,
;  see http://www.ibsensoftware.com/ for more information
;
;  Drop me an email if you have any comments/ideas/suggestions: zxintrospec@gmail.com
;
;  This software is provided 'as-is', without any express or implied
;  warranty.  In no event will the authors be held liable for any damages
;  arising from the use of this software.
;
;  Permission is granted to anyone to use this software for any purpose,
;  including commercial applications, and to alter it and redistribute it
;  freely, subject to the following restrictions:
;
;  1. The origin of this software must not be misrepresented; you must not
;     claim that you wrote the original software. If you use this software
;     in a product, an acknowledgment in the product documentation would be
;     appreciated but is not required.
;  2. Altered source versions must be plainly marked as such, and must not be
;     misrepresented as being the original software.
;  3. This notice may not be removed or altered from any source distribution.

;	DEFINE FasterGetBit					; 16% speed-up at the cost of extra 4 bytes
;	DEFINE SupportLongOffsets				; +4 bytes for long offset support. slows decompression down by 1%, but may be needed to decompress files >=32K
;	DEFINE BackwardDecompression				; decompress data compressed backwards, -5 bytes, speeds decompression up by 3%


	IFDEF FasterGetBit
		MACRO	GET_BIT
			add a : call z,ReloadByte
		ENDM
	ELSE
		MACRO	GET_BIT
			call GetOneBit
		ENDM
	ENDIF

	IFNDEF BackwardDecompression

		MACRO NEXT_HL
		inc hl
		ENDM

		MACRO COPY_1
		ldi
		ENDM

		MACRO COPY_BC
		ldir
		ENDM

	ELSE

		MACRO NEXT_HL
		dec hl
		ENDM

		MACRO COPY_1
		ldd
		ENDM

		MACRO COPY_BC
		lddr
		ENDM

	ENDIF

@DecompressApLib:	ld a,128

;
;  case "0"+BYTE: copy a single literal

CASE0:			COPY_1					; first byte is always copied as literal
ResetLWM:		ld b,-1					; LWM = 0 (LWM stands for "Last Was Match"; a flag that we did not have a match)

;
;  main decompressor loop

MainLoop:		GET_BIT : jr nc,CASE0			; "0"+BYTE = copy literal
			GET_BIT : jr nc,CASE10			; "10"+gamma(offset/256)+BYTE+gamma(length) = the main matching mechanism

			ld bc,%11100000
			GET_BIT : jr nc,CASE110			; "110"+[oooooool] = matched 2-3 bytes with a small offset

;
;  case "111"+"oooo": copy a byte with offset -1..-15, or write zero to dest

CASE111:
ReadFourBits		GET_BIT					; read short offset (4 bits)
			rl c : jr c,ReadFourBits
			ex de,hl : jr z,WriteZero		; zero offset means "write zero" (NB: B is zero here)

			; "write a previous byte (1-15 away from dest)"
			push hl					; BC = offset, DE = src, HL = dest
	IFNDEF BackwardDecompression
			sbc hl,bc				; HL = dest-offset (SBC works because branching above ensured NC)
	ELSE
			add hl,bc				; HL = dest-offset (SBC works because branching above ensured NC)
	ENDIF
			ld c,(hl) : pop hl

WriteZero		ld (hl),c : NEXT_HL
			ex de,hl : jr ResetLWM			; write one byte, reset LWM

;
;  branch "110"+[oooooool]: copy two or three bytes (bit "l") with the offset -1..-127 (bits "ooooooo"), or stop

CASE110:		; "use 7 bit offset, length = 2 or 3"
			; "if a zero is found here, it's EOF"
			ld c,(hl) : rr c : ret z		; process EOF
			NEXT_HL

			push hl					; save src
			ld h,b : ld l,c				; HL = offset

			; flag NC means len=2, flag C means len=3
			ld c,1 : rl c : jr SaveLWMOffset
			
;
;  branch "10"+gamma(offset/256)+BYTE+gamma(length): the main matching mechanism

CASE10:			; save state of LWM into A'
			exa : ld a,b : exa

			; "use a gamma code * 256 for offset, another gamma code for length"
			call GetGammaCoded

			; the original decompressor contains
			;
			; if ((LWM == 0) && (offs == 2)) { ... }
			; else {
			;	if (LWM == 0) { offs -= 3; }
			;	else { offs -= 2; }
			; }
			;
			; so, the idea here is to use the fact that GetGammaCoded returns (offset/256)+2,
			; and to split the first condition by noticing that C-1 can never be zero
			exa : add c : ld c,a : exa

			; "if gamma code is 2, use old r0 offset"
			dec c : jr z,KickInLWM
			dec c
			ld b,c : ld c,(hl) : NEXT_HL		; BC = offset

			push bc					; (SP) = offset
			call GetGammaCoded			; BC = len*
			ex (sp),hl				; HL = offset, (SP) = src

			; interpretation of length value is offset-dependent
			exa : ld a,h
	IFDEF	SupportLongOffsets
			; NB offsets over 32000 require an additional check, which is skipped in most
			; Z80 decompressors (seemingly as a performance optimization)
			cp 32000/256 : jr nc,.Add2
	ENDIF
			cp 5 : jr nc,.Add1
			or a : jr nz,.Add0
			bit 7,l : jr nz,.Add0
.Add2			inc bc
.Add1			inc bc
.Add0			exa

SaveLWMOffset:
			push hl : pop ix			; save offset for future LWMs

CopyMatch:		; this assumes that BC = len, DE = dest, HL = offset
			; and also that (SP) = src, while having NC
	IFNDEF BackwardDecompression
			push de
			ex de,hl : sbc hl,de			; HL = dest-offset
			pop de					; DE = dest
	ELSE
			add hl,de				; HL = dest+offset
	ENDIF

			COPY_BC
			pop hl					; recover src
			jr MainLoop

;
;  the re-use of the previous offset (LWM magic)

KickInLWM:		; "and a new gamma code for length"
			call GetGammaCoded			; BC = len
			push ix : ex (sp),hl			; DE = dest, HL = prev offset
			jr CopyMatch

;
;  interlaced gamma code reader
;  x0 -> 1x
;  x1y0 -> 1xy
;  x1y1z0 -> 1xyz etc
;  (technically, this is a 2-based variation of Exp-Golomb-1)

GetGammaCoded:		ld bc,1
ReadGamma		GET_BIT : rl c : rl b
			GET_BIT : ret nc
			jr ReadGamma

;
;  pretty usual getbit for mixed datastreams

	IFNDEF FasterGetBit
GetOneBit:		add a : ret nz
	ENDIF
ReloadByte:		ld a,(hl) : NEXT_HL
			rla : ret