193 lines
5.5 KiB
NASM
193 lines
5.5 KiB
NASM
;-------------------------------------------------------------------------------
|
|
;Lempel-Ziv decompressor by Johan "Doynax" Forslöf. Call doynamitedepack to decode the entire buffer in
|
|
;one go.
|
|
;
|
|
;This is a fork of the 68000 depacker by Michael Hillebrandt (Axis/Oxyron)
|
|
;for the 6502 Doynamite format, except with the encoding rearranged to take
|
|
;somewhat better advantage of the 68k architecture.
|
|
;
|
|
;The present version is 210 bytes long including the tables and should fit
|
|
;snugly in the 68020+ cache.
|
|
;
|
|
;Note that the scheme with a split input stream for odd literal bytes requires
|
|
;a significant safety buffer for forward in-place decompression (about 3% but
|
|
;dependent on the file to be processed)
|
|
;
|
|
;Parameters:
|
|
;a0 = Input buffer to be decompressed. Must be 16-bit aligned!
|
|
;a1 = Output buffer. Points to the end of the data at exit
|
|
;
|
|
;Register legend:
|
|
;d0 = 32-bit shift register terminated by a least-significant 1 bit.
|
|
;d1 = Run length.
|
|
;d2 = Match offset length in bits.
|
|
;d3 = Match offset bitmask.
|
|
;d4 = Constant offset type mask.
|
|
;d5 = Constant offset length bit mask.
|
|
;a0 = Bit-stream pointer.
|
|
;a1 = Continuous output pointer.
|
|
;a2 = Unaligned literal pointer ahead of the bit-stream. Points to the end of
|
|
; the source buffer at exit.
|
|
;a3 = Mid-point where the literal buffer meets the bit-stream at EOF
|
|
;a4 = Match source pointer.
|
|
;-------------------------------------------------------------------------------
|
|
;Ensure that the shift-register contains at least 16-bits of data by
|
|
;checking whether the trailing word is zero, and if so filling up with
|
|
;another word
|
|
DOY_REFILL macro
|
|
DOY_REFILL1 doy_full\@
|
|
DOY_REFILL2
|
|
doy_full\@:
|
|
endm
|
|
|
|
DOY_REFILL1 macro
|
|
tst.w d0
|
|
bne.s \1
|
|
endm
|
|
|
|
DOY_REFILL2 macro ;This swaps in the new bits ahead of the
|
|
move.w (a0)+,d0 ;old, but that's fine as long as the
|
|
swap.w d0 ;encoder is in on the scheme
|
|
endm
|
|
|
|
;Entry point. Wind up the decruncher
|
|
doynaxdepack:
|
|
movea.l (a0)+,a2 ;Unaligned literal buffer at the end of
|
|
adda.l a0,a2 ;the stream
|
|
move.l a2,a3
|
|
move.l (a0)+,d0 ;Seed the shift register
|
|
moveq #@70,d4 ;Masks for match offset extraction
|
|
moveq #@10,d5
|
|
bra.s doy_literal
|
|
|
|
|
|
;******** Copy a literal sequence ********
|
|
|
|
doy_lcopy: ;Copy two bytes at a time, with the
|
|
move.b (a0)+,(a1)+ ;deferral of the length LSB helping
|
|
move.b (a0)+,(a1)+ ;slightly in the unrolling
|
|
dbf d1,doy_lcopy
|
|
|
|
lsl.l #2,d0 ;Copy odd bytes separately in order
|
|
bcc.s doy_match ;to keep the source aligned
|
|
doy_lsingle:
|
|
move.b (a2)+,(a1)+
|
|
|
|
|
|
;******** Process a match ********
|
|
|
|
;Start by refilling the bit-buffer
|
|
doy_match:
|
|
DOY_REFILL1 doy_mprefix
|
|
cmp.l a0,a3 ;Take the opportunity to test for the
|
|
bls.s doy_return ;end of the stream while refilling
|
|
doy_mrefill:
|
|
DOY_REFILL2
|
|
|
|
doy_mprefix:
|
|
;Fetch the first three bits identifying the match length, and look up
|
|
;the corresponding table entry
|
|
rol.l #3+3,d0
|
|
move.w d0,d1
|
|
and.w d4,d1
|
|
eor.w d1,d0
|
|
movem.w doy_table(pc,d1.w),d2/d3/a4
|
|
|
|
;Extract the offset bits and compute the relative source address from it
|
|
rol.l d2,d0 ;Reduced by 3 to account for 8x offset
|
|
and.w d0,d3 ;scaling
|
|
eor.w d3,d0
|
|
suba.w d3,a4
|
|
adda.l a1,a4
|
|
|
|
;Decode the match length
|
|
DOY_REFILL
|
|
and.w d5,d1 ;Check the initial length bit from the
|
|
beq.s doy_mcopy ;type triple
|
|
|
|
moveq #1,d1 ;This loops peeks at the next flag
|
|
tst.l d0 ;through the sign bit bit while keeping
|
|
bpl.s doy_mendlen2 ;the LSB in carry
|
|
lsl.l #2,d0
|
|
bpl.s doy_mendlen1
|
|
doy_mgetlen:
|
|
addx.b d1,d1
|
|
lsl.l #2,d0
|
|
bmi.s doy_mgetlen
|
|
doy_mendlen1:
|
|
addx.b d1,d1
|
|
doy_mendlen2:
|
|
|
|
;Copy the match data a word at a time. Note that the minimum length is
|
|
;two bytes
|
|
lsl.l #2,d0 ;The trailing length payload bit is
|
|
bcc.s doy_mhalf ;stored out-of-order
|
|
doy_mcopy:
|
|
move.b (a4)+,(a1)+
|
|
doy_mhalf:
|
|
move.b (a4)+,(a1)+
|
|
dbf d1,doy_mcopy
|
|
|
|
;Fetch a bit flag to see whether what follows is a literal run or
|
|
;another match
|
|
add.l d0,d0
|
|
bcc.s doy_match
|
|
|
|
|
|
;******** Process a run of literal bytes ********
|
|
|
|
DOY_REFILL ;Replenish the shift-register
|
|
doy_literal:
|
|
;Extract delta-coded run length in the same swizzled format as the
|
|
;matches above
|
|
moveq #0,d1
|
|
add.l d0,d0
|
|
bcc.s doy_lsingle ;Single out the one-byte case
|
|
bpl.s doy_lendlen
|
|
doy_lgetlen:
|
|
addx.b d1,d1
|
|
lsl.l #2,d0
|
|
bmi.s doy_lgetlen
|
|
doy_lendlen:
|
|
addx.b d1,d1
|
|
|
|
;Branch off to the main copying loop unless the run length is 256 bytes
|
|
;or greater, in which case the sixteen guaranteed bits in the buffer
|
|
;may have run out.
|
|
;In the latter case simply give up and stuff the payload bits back onto
|
|
;the stream before fetching a literal 16-bit run length instead
|
|
doy_lcopy_near:
|
|
dbvs d1,doy_lcopy
|
|
|
|
add.l d0,d0
|
|
eor.w d1,d0
|
|
ror.l #7+1,d0 ;Note that the constant MSB acts as a
|
|
move.w (a0)+,d1 ;substitute for the unfetched stop bit
|
|
bra.s doy_lcopy_near
|
|
|
|
|
|
;******** Offset coding tables ********
|
|
|
|
DOY_OFFSET macro
|
|
dc.w (\1)-3 ;Bit count, reduced by three
|
|
dc.w (1<<(\1))-1 ;Bit mask
|
|
dc.w -(\2) ;Base offset
|
|
endm
|
|
|
|
doy_table:
|
|
DOY_OFFSET 3,1 ;Short A
|
|
doy_return:
|
|
rts
|
|
DOY_OFFSET 4,1 ;Long A
|
|
dc.w 0 ;(Empty hole)
|
|
DOY_OFFSET 6,1+8 ;Short B
|
|
dc.w 0 ;(Empty hole)
|
|
DOY_OFFSET 7,1+16 ;Long B
|
|
dc.w 0 ;(Empty hole)
|
|
DOY_OFFSET 8,1+8+64 ;Short C
|
|
dc.w 0 ;(Empty hole)
|
|
DOY_OFFSET 10,1+16+128 ;Long C
|
|
dc.w 0 ;(Empty hole)
|
|
DOY_OFFSET 10,1+8+64+256 ;Short D
|
|
dc.w 0 ;(Empty hole)
|
|
DOY_OFFSET 13,1+16+128+1024 ;Long D |