GHGAEA8@cc1.kuleuven.ac.be (05/02/91)
=========================================================================
Newsgroups: comp.compression
Subject: LZRW1 derivative for 68000
This program should actually be listed in comp.compression (and
it is), but since the code described herein is 68000 specific and was
written on an Amiga it may be also at its place in .amiga.programmer,
so here it is :
=========================================================================
This file was written on an Amiga and then copied onto VM, therefor
lines may ve longer than some mailers ro readers can handle, if so, I
will UUENCODE the file and post it again. All bug reports are welcome
at the addresses given in the listing ... A C listing containing the
optimized LZRW1 compression will follow soon !
I added some optimization to the program when it was already on VM,
so I haven't been able to test that yet. It's the part between the
ELSE and ENDIF statements in FindMatch. If you should find a bug, be
so kind as to report it ... Simply post it to Netnews and mail it to
GHGAEA8 @ BLEKUL11
**************************************************************************
** **
** ###### # #### ## ## #### #### ## ## ##### **
** ## ## ### ## ## ## ## ## ## ## ## ### ### ## ## **
** ## ## ## ## ###### ## ## ## ####### ## ## **
** #### ####### #### #### ## ## ## ## # ## ##### **
** ## ## ## ## ## ## ## ## ## ## ## **
** ## ## ## ## ## ## ## ## ## ## ## ## ## ## **
** ###### ## ## #### ## #### #### ## ## ## **
** **
** A fast and easy-to-understand compression algoritm **
** **
** **
** This compression routine is based on an algoritme written **
** by Ross N. Williams. Some optimization was done by Kurt **
** Haenen and the code was rewritten for 68000 assembler. **
** **
** If you should enhance or modify this code in any way, you **
** should put an article in Netnews describing the changes **
** you made and you should also include the source. This is **
** not done to control the usage of the program (by the way, **
** this stuff is completely public domain), but to keep up **
** with the possible optimizations and enhancements which **
** can be useful for others aswell ! I hope you'll like the **
** code. I think this routine has one of the highest speed **
** vs. compression ratios, zoo sometimes compresses better, **
** but is much slower. There could still be some unefficient **
** code floating around here ... for you to find it and post **
** the fixed versions. Hope to hear from you all very soon. **
** **
** Kurt HAENEN **
** **
** Special thanks should go to the following persons: **
** **
** - Ross N. Williams for the original algoritm published in **
** "An extremely fast data compression algoritm", Data **
** Compression Conference, Utah, 7-11 April, 1991. **
** - Sigrid Pinnoy for her constant support and her efforts **
** to keep me away from my Amiga and study instead. **
** - Lieven van Uytfanghe for his constant critics on my **
** work and his supply of Bicky Burgers. **
** - All the guys I know at the URC KU Leuven, who allow me **
** to read netnews and get some EMAILs. **
** **
** If you should like to contact me, you can always try **
** sending an EMAIL to GHGAEA8 @ BLEKUL11, however this **
** account is only temporarily at my disposal, so if it's **
** really important : **
** my "-M-essing -A-round -I-n my -L-etters" address is ... **
** **
** Kurt HAENEN **
** Homsemstraat 53 **
** 3891 Borlo **
** Belgium **
** **
**----------------------------------------------------------------------**
** ANNOUNCEMENT UNDER THE NAME UTOPIA : **
** **
** /// I AM STILL SEARCHING FOR SOMEONE WHO'S **
** /// WILLING TO DONATE AN AMIGA 3000 TO ME. **
** \\\/// IF YOU'RE INTERESTED ... DON'T WAIT ! **
** \XX/ SEND ME AN EMAIL, MAIL, OR ... **
** **
**************************************************************************
**************************************************************************
** **
** This code was designed to be compiled with the MACRO 68 **
** assembler on the Amiga. It should be easy to convert to **
** other assemblers. Try removing the following lines ... **
** **
**************************************************************************
EXEOBJ
NEWSYNTAX
MC68000
SYM
**************************************************************************
** **
** Some Constants we use **
** **
**************************************************************************
Block_CopiedAll EQU %10000000
Block_EasyCompression EQU %01000000
EntryBitsPerHash EQU 0
EntriesPerHash EQU (1<<EntryBitsPerHash)
**************************************************************************
** **
** ROUTINE: Compress **
** **
** INPUTS: A0.l = Pointer to source buffer **
** A1.l = Pointer to destination buffer **
** D0.l = Size of source buffer **
** OUTPUTS: D1.l = Size of destination buffer **
** **
** NOTES: The destination buffer should be at least **
** two bytes larger than the source buffer. **
** The compressed data will at the most be **
** one byte larger than the source data. **
** **
**************************************************************************
SECTION "Compression Code",CODE
Compress movem.l d0/d2-d7/a0-a6,-(sp)
bsr ClearHashTable
move.b #Block_EasyCompression,(a1)
moveq #3,d1 ; Position in
destination buffer
moveq #0,d2 ; Position in source
buffer
moveq #1,d3 ; Position of current
command-word
moveq #0,d4 ; Value of current
command-word
move.w #15,d5 ; Number of bits to do
in command-word
COMP_NextLoop bsr FindMatch
cmp.l #-1,d7
beq.s COMP_NoCompression
move.b d7,(1,a1,d1.l)
ror.w #8,d7
move.b d7,(a1,d1.l)
addq.l #2,d1
ror.w #8,d7
and.l #$0000000f,d7
add.l d7,d2
addq.l #3,d2
lsl.w #1,d4
or.w #$0001,d4
bra.s COMP_BitShifted
COMP_NoCompression move.b (a0,d2.l),(a1,d1.l)
addq.l #1,d2
addq.l #1,d1
lsl.w #1,d4
COMP_BitShifted dbra d5,COMP_NotFull
move.b d4,(1,a1,d3.l)
ror.w #8,d4
move.b d4,(a1,d3.l)
move.l d1,d3
addq.l #2,d1
moveq #0,d4
move.w #15,d5
COMP_NotFull cmp.l d0,d1
bhi.s COMP_Overflow
cmp.l d0,d2
blo.s COMP_NextLoop
lsl.w d5,d4
lsl.w #1,d4
move.b d4,(1,a1,d3.l)
ror.w #8,d4
move.b d4,(a1,d3.l)
COMP_Exit movem.l (sp)+,d0/d2-d7/a0-a6
rts
COMP_Overflow moveq #0,d1
move.b #Block_CopiedAll,(a1)
COMP_CopyLoop move.b (a0,d1.l),(1,a1,d1.l)
addq.l #1,d1
cmp.l d0,d1
blo.s COMP_CopyLoop
addq.l #1,d1
bra.s COMP_Exit
**************************************************************************
** **
** ROUTINE: Decompress **
** **
** INPUTS: A0.l = Pointer to source buffer **
** A1.l = Pointer to destination buffer **
** D0.l = Size of source buffer **
** OUTPUTS: D1.l = Size of destination buffer **
** **
** NOTES: The routine will not check overflows on the **
** destination buffer, so you should make sure **
** your destination buffer can hold the **
** decompressed data ! **
** **
**************************************************************************
Decompress movem.l d0/d2-d7/a0-a6,-(sp)
cmp.b #Block_CopiedAll,(a0)
bne.s DEC_NotACopy
moveq #1,d1
DEC_CopyLoop move.b (a0,d1.l),(-1,a1,d1.l)
addq.l #1,d1
cmp.l d0,d1
blo.s DEC_CopyLoop
subq.l #1,d1
bra.s DEC_Exit
DEC_NotACopy moveq #0,d1
cmp.b #Block_EasyCompression,(a0)
bne.s DEC_Exit
moveq #0,d1 ; Position in
destination buffer
moveq #1,d2 ; Position in source
buffer
DEC_NextCommand move.b (a0,d2.l),d3 ; Current command-word
lsl.w #8,d3
move.b (1,a0,d2.l),d3
addq.l #2,d2
move.w #15,d4
DEC_ProcessLoop btst #15,d3
bne.s DEC_DecompressIt
move.b (a0,d2.l),(a1,d1.l)
addq.l #1,d2
addq.l #1,d1
bra.s DEC_NextByte
DEC_DecompressIt move.b (1,a0,d2.l),d5 ; Size of item
and.w #$000f,d5
addq.w #2,d5
move.b (a0,d2.l),d6 ; Position of item
lsl.w #8,d6
move.b (1,a0,d2.l),d6
lsr.w #4,d6
and.l #$00000fff,d6
neg.l d6
add.l d1,d6
addq.l #2,d2
DEC_RepeatLoop move.b (a1,d6.l),(a1,d1.l)
addq.l #1,d6
addq.l #1,d1
dbra d5,DEC_RepeatLoop
DEC_NextByte cmp.l d0,d2
bhs.s DEC_Exit
lsl.w #1,d3
dbra d4,DEC_ProcessLoop
bra.s DEC_NextCommand
DEC_Exit movem.l (sp)+,d0/d2-d7/a0-a6
rts
**************************************************************************
** **
** ROUTINE: FindMatch **
** **
** INPUTS: A0.l = Pointer to source buffer **
** D0.l = Size of source buffer **
** D2.l = Position in source-buffer **
** OUTPUTS: D7.l = Command in lo-word or -1 if not found **
** **
**************************************************************************
FindMatch movem.l d0-d1/d3-d6/a0-a6,-(sp)
lea (HashTable),a1
move.b (a0,d2.l),d1
lsl.w #4,d1
move.b (1,a0,d2.l),d3
eor.b d3,d1
lsl.w #4,d1
move.b (2,a0,d2.l),d3
eor.b d3,d1
mulu #40543,d1
lsr.l #4,d1
and.l #$00000fff,d1
lsl.l #(2+EntryBitsPerHash),d1
lea (a1,d1.l),a1
IFGT EntryBitsPerHash
move.l a1,a2
moveq #-3,d7 ; D7 Lo-word = Length of largest
match
; D7 Hi-word = Relative position
move.w #(EntriesPerHash-1),d6
FM_FindLongest move.l (a2)+,d1
bmi.s FM_FoundLargest
move.l d2,d4
sub.l d1,d4
cmp.l #4095,d4
bhi.s FM_NotLarger
move.l d2,d4
moveq #-3,d5 ; Length of match
FM_MatchLoop move.b (a0,d1.l),d3
cmp.b (a0,d4.l),d3
bne.s FM_NotMatching
addq.w #1,d5
addq.l #1,d1
addq.l #1,d4
cmp.l d0,d4
bhs.s FM_FoundLargest
cmp.w #15,d5
bne.s FM_MatchLoop
FM_NotMatching cmp.w d7,d5
ble.s FM_NotLarger
move.w d5,d7
move.l d2,d5
sub.l (-4,a2),d5
swap d7
move.w d5,d7
swap d7
cmp.w #15,d7
beq.s FM_FoundLargest
FM_NotLarger dbra d6,FM_FindLongest
FM_FoundLargest tst.w d7
bmi.s FM_NoMatch
ror.w #4,d7
lsr.l #8,d7
lsr.l #4,d7
FM_AddToHash move.w #(EntriesPerHash*4-8),d1
FM_ShiftHash move.l (a1,d1.w),(4,a1,d1.w)
subq.w #4,d1
bhs.s FM_ShiftHash
ELSE
move.l (a1),d1
bmi.s FM_NoMatch
move.l d2,d5
sub.l d1,d5
cmp.l #4095,d5
bhi.s FM_NoMatch
move.l d2,d4
moveq #-3,d7
FM_MatchLoop move.b (a0,d1.l),d3
cmp.b (a0,d4.l),d3
bne.s FM_FoundLargest
addq.w #1,d7
addq.l #1,d1
addq.l #1,d4
cmp.l d0,d4
bhs.s FM_FoundLargest
cmp.w #15,d7
bne.s FM_MatchLoop
FM_FoundLargest tst.w d7
bmi.s FM_NoMatch
swap d7
move.w d5,d7
ror.w #4,d7
lsr.l #8,d7
lsr.l #4,d7
FM_AddToHash
ENDIF
move.l d2,(a1)
FM_Exit movem.l (sp)+,d0-d1/d3-d6/a0-a6
rts
FM_NoMatch moveq #-1,d7
bra.s FM_AddToHash
**************************************************************************
** **
** ROUTINE: ClearHashTable **
** **
** INPUTS: None **
** OUTPUTS: None **
** **
**************************************************************************
ClearHashTable movem.l d0-d7/a0-a6,-(sp)
lea (HashTable),a0
move.l #(EntriesPerHash*4096-1),d0
CHT_Loop move.l #-1,(a0)+
subq.l #1,d0
bhs.s CHT_Loop
movem.l (sp)+,d0-d7/a0-a6
rts
**************************************************************************
** **
** The Hash Table **
** **
** The hash table contains 4096 * EntriesPerHash pointers **
** to sub-arrays containing specific characters. This method **
** is used to speed up the match-searching, without the loss **
** of too much compression. **
** **
**************************************************************************
SECTION "Hash Table",BSS
HashTable ds.l (4096*EntriesPerHash)
END