GHGAEA8@cc1.kuleuven.ac.be (05/02/91)
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