;9.8.94 17:00 ;d7 end of packing area ;d6 bits buffer ;d5 scratch ;d4 scratch ;d3 match length and match offset ;d2 temporary ;d1 temporary ;d0 temporary ;a0 source pointer ;a1 destination pointer ;a2 hash index table ;a3 linked list ;a4 scratch ;a5 scratch ;a6 actual bit store address ;Macro for hash function - RETURN (8+7) bit HASH MACRO moveq #0,d1 move.b 1(a0),d1 lsl.w d5,d1 move.b (a0),d1 add.l d1,d1 move.w a0,d0 sub.w (a3,d1.l),d0 ;get previous hash match address move.w a0,(a3,d1.l) ;and store new one move.w a0,d1 add.w d1,d1 move.w d0,(a2,d1.w) ENDM CLEARHUFFMANTAB MACRO lea table(pc),a1 add.l #$1000,a1 ;clear tables move.l #$2ff,d1 moveq #0,d0 .\@1 move.l d0,-(a1) dbra d1,.\@1 subq.b #1,d0 .\@2 move.l d0,-(a1) ;init index-table dbra d0,.\@2 move.l a1,a2 add.l #$400,a2 ENDM TABLEWRITE MACRO lea ta(pc),a5 lsl.w #2,d0 addq.l #1,0(a5,d0) lsr.w #2,d0 ENDM realbuffer=$20+$80+$200+$400+$800+$1000+$2000+$4000-1 bufferlength=$8000 ;length of buffer bits=8 indexlength=$200< get previous match move.l (a7)+,d2 ;restore last match cmp.w d3,d2 ;compare with previous match bcs.b .match0 bra.b .match3 ;which was better .match2 move.l (a7)+,d2 ;restore previous match .match3 move.l d2,d3 subq.l #1,a0 IFEQ SO cmp.l #endcode-source+uklad-50,a1 ELSE cmp.l xsp_Sub+2*4(a4),a1 ENDIF bcc.w deadend goodmatch move.l (a7)+,a5 ;count number of uncompressed bytes move.l a0,d0 sub.l a5,d0 bsr.w write_uncompressed ;store number of uncompressed bytes ; move.l uloa2,a4 tt bra.b .startl cnop 0,4 .write_uncompressed_bytes ; moveq #0,d0 ; move.b (a5),d0 ; lsl.w #2,d0 ; addq.l #1,(a4,d0.w) ;cetnost hufman move.b (a5)+,(a1)+ ;transfer uncompressed bytes .startl cmp.l a0,a5 bcs.b .write_uncompressed_bytes ;Now we have to write all compressed bytes into hash tables move.w d3,d2 addq.l #1,a0 ;this byte is already in hash bra.b .start .loop HASH ;store in hash table all bytes .start addq.l #1,a0 dbf d2,.loop moveq #0,d0 move.w d3,d0 bne.b bigger_than_two move.l d3,d0 lsl.l #5,d0 moveq #10,d1 ;2+9-1 offset is 512 bytes bra.b hopla bigger_than_two bsr.w write_match_lenght moveq #0,d0 swap d3 move.w d3,d0 lea table0(pc),a5 ;Calculate offset .loop move.l (a5)+,d2 sub.w d2,d0 bcc.b .loop add.w d2,d0 swap d2 move.w d2,d1 or.l 28(a5),d0 ror.l d1,d0 subq.w #1,d1 ;for DBRA IFEQ SO addq.l #1,60(a5) ENDIF hopla bsr.w compis move.l a0,-(a7) ;set counter for uncompr bytes cmp.l d7,a0 bcs.w main_loop moveq #0,d0 moveq #7,d1 bsr.w compis addq.l #4,a7 move.l (a7)+,d0 exg a1,d0 sub.l a1,d0 dead movem.l (a7)+,SAVEPACKREGS rts deadend addq.l #8,a7 moveq #0,d0 bra.b dead nocompress addq.l #1,a0 cmp.l d7,a0 bcs.w main_loop moveq #0,d3 bra.w goodmatch table0 dc.w 3+5, $20, 3+7, $80, 3+9, $200,3+10, $400 dc.w 3+11,$800,3+12,$1000,3+13,$2000,3+14,$4000 dc.l %00000000,%0010000000,%010000000000,%0110000000000 dc.l %10000000000000,%101000000000000,%1100000000000000 dc.l %11100000000000000 IFEQ SO ddd dc.l 0,0,0,0,0,0,0,0,0,0,0,0 ENDIF ;---------------------------------------------------- ; search rutine for matching strings ; optimized for the maximum speed ; Input : a0 - source address ; a2,a3 - tables ; d7 - end of block ; Results : d3 - match offset/match length ; Carry is set when there is no match ; Destroy : d0,d1,d2,d4,a5 ;---------------------------------------------------- n_repeat=32 COMPRESSREGS reg d5-d6/a4 compress moveq #0,d0 ;clear MSW D0!!! HASH lea -realbuffer(a0),a5 move.l a5,d2 ;end of search buffer move.l a0,a5 ;get previous match address sub.l d0,a5 cmp.l d2,a5 bcs.b c_ret1 movem.l COMPRESSREGS,-(a7) move.l a0,d6 move.b 0(a0,d3.w),d5 ;last byte for comparing - heuristic IFEQ SO move.w #n_repeat,d1 ELSE move.l xsp_Sub+3*4(a4),d1 ENDIF .c_next move.l a5,d4 move.l a0,a4 cmpm.b (a4)+,(a5)+ bne.b c_ret cmpm.b (a4)+,(a5)+ bne.b .c_nextmatch move.w #521,d0 ;max 521 same bytes for search .c_still_same cmpm.b (a4)+,(a5)+ ;compare for same bytes dbne d0,.c_still_same cmp.l a4,d6 bcc.b .c_nextmatch ;do we have better match ? move.l a4,d6 move.b -(a4),d5 ;get new byte for compare move.w a0,d3 sub.w d4,d3 swap d3 cmp.l d7,a4 ;is it end ? bcs.b .c_ok move.w d7,d3 sub.w a0,d3 bra.b c_ret .c_ok move.w a4,d3 sub.w a0,d3 cmp.w #256,d3 bcc.b c_ret .c_nextmatch move.l d4,a5 ;heuristic method .c_nb move.l a5,d4 ;reducing number of compared add.w d4,d4 ;strings down to 2% move.w 0(a2,d4.w),d0 ;when the last byte is not sub.l d0,a5 ;matching, take next match cmp.l d2,a5 ;immediately bcs.b c_ret cmp.b 0(a5,d3.w),d5 dbeq d1,.c_nb beq.b .c_next c_ret movem.l (a7)+,COMPRESSREGS c_ret1 subq.w #2,d3 bne.b .c_ret3 move.l d3,d0 ;if we found match length=2 add.l #$fe000000,d0 ;we need only offsets <512 bytes .c_ret3 rts ;----------------------------------------------- ; Write Match Length ;Input : match length in d0 ;Results : write bit representation of d0 ;Destroy : d0, d1, d2, d4 ;----------------------------------------------- ;to be fast - 0-15 taken from table table1 dc.b %00000000,1 ;0 dc.b %01000000,1 ;1 dc.b %10000000,2 ;2 dc.b %10100000,2 dc.b %11000000,4 dc.b %11001000,4 dc.b %11010000,4 dc.b %11011000,4 dc.b %11100000,6 dc.b %11100010,6 dc.b %11100100,6 dc.b %11100110,6 dc.b %11101000,6 dc.b %11101010,6 dc.b %11101100,6 dc.b %11101110,6 ;15 write_match_lenght moveq #16,d1 move.l d0,d2 add.w d0,d0 move.w table1(pc,d0.w),d0 sub.l d1,d2 bcs.b count1 moveq #16,d0 moveq #3,d1 moveq #5,d4 bra.b count3 count2 moveq #4,d0 moveq #6,d1 moveq #3,d4 count3 sub.l d0,d2 bcs.b count4 addq.l #1,d1 addq.l #1,d4 add.l d0,d0 bra.b count3 count4 add.l d0,d2 ror.l d4,d2 moveq #-1,d0 bsr.b compis move.l d2,d0 move.l d4,d1 subq.w #1,d1 bra.b compis ;----------------------------------------------- ; Write Length of Uncompressed Bytes ;Input : number of uncompressed bytes in d0 ;Results : write bit representation of d0 ;Destroy : d0, d1, d2, d4 ;----------------------------------------------- ;to be fast - 0-7 taken from table table2 dc.b %00000000,0 ;0 dc.b %10000000,1 dc.b %11000000,2 dc.b %11100000,3 dc.b %11110000,4 dc.b %11111000,5 dc.b %11111100,7 dc.b %11111101,7 ;7 write_uncompressed moveq #8,d1 move.l d0,d2 add.w d0,d0 sub.l d1,d2 bcc.b count2 move.w table2(pc,d0.w),d0 count1 move.b d0,d1 swap d0 ;----------------------------------------------- ; Write bits in bit stream ;Inputs : bits in D0, number of bits in D1 ;Results : d0 is written in bit stream ;Destroy : d0,d1 ;----------------------------------------------- compis tst.b d6 bne.b .comp2 .comp1 move.l a1,a6 addq.l #1,a1 moveq #1,d6 .comp2 add.l d0,d0 addx.b d6,d6 bcc.b .comp3 move.b d6,(a6) dbra d1,.comp1 moveq #0,d6 rts .comp3 dbra d1,.comp2 rts ;----------------------------------------------- ;dekomprese ;a3 used for fast jumping into subrutines ;a2 used for tables ;a1 destination ;a0 source ;d0,d1,d2 scratch ;d3 byte acumulator ;d4 end of file ByteBuf EQUR D3 ;macro for moving bytes BYTE_MOVE MACRO move.b (a0)+,(a1)+ ENDM ;macro for getting next bit NEXTBIT MACRO add.b ByteBuf,ByteBuf bne.b .\@ move.b (a0)+,ByteBuf addx.b ByteBuf,ByteBuf .\@ ENDM ;macro for getting bits - number is in D1, bits are stored in \1 register GETXBITS MACRO moveq #0,\1 ;subrutine - GetXBites from file .\@loop NEXTBIT addx.w \1,\1 dbra d1,.\@loop ENDM str IFEQ SO .loop0 btst #6,$bfe001 bne.b .loop0 move.l #uklad,a1 move.l #endcode,d0 addq.l #7,d0 moveq #$fffffffc,d1 and.l d1,d0 move.l d0,a0 move.l celkove,d0 addq.l #3,d0 and.l d1,d0 add.l d0,a1 lsr.l #2,d0 subq #1,d0 swap d0 .loop1 swap d0 .loop2 move.l -(a1),-(a0) dbra d0,.loop2 swap d0 dbra d0,.loop1 move.l #source,a1 move.l #endcode,d4 bra.w UnPack_It ENDIF ;-------------------------------- ;start of main decompress rutine cnop 0,4 UNCOMPRESSREGS reg d0-d4/a2-a5 UnPack_It movem.l UNCOMPRESSREGS,-(a7) lea tab0-4(pc),a4 lea tab1-4(pc),a5 moveq #-128,ByteBuf ; starting buffer - empty + Carry looping NEXTBIT bcc.b cont NEXTBIT bcc.b mov1 NEXTBIT bcc.b mov2 NEXTBIT bcc.b mov3 NEXTBIT bcc.b mov4 NEXTBIT bcc.b mov5 ; lea tab0-4(pc),a2 move.l a4,a2 ;get number of uncompressed bytes .loop addq.l #4,a2 NEXTBIT bcs.b .loop move.w (a2)+,d1 ; lea cont1(pc),a3 ; bra.b GetXB GETXBITS d0 cont1 add.w (a2),d0 .loop BYTE_MOVE ;transfer uncompressed bytes dbra d0,.loop mov5 BYTE_MOVE mov4 BYTE_MOVE mov3 BYTE_MOVE mov2 BYTE_MOVE mov1 BYTE_MOVE cont NEXTBIT ;get match length bcs.b more_than_three less NEXTBIT bcs.b three_bytes moveq #8,d1 ;9 bits offset moveq #0,d2 ;0+2 bytes for match length bra.b GetOffs ;get offset three_bytes moveq #1,d2 ;1+2 bytes for match length bra.b Offset ;get offset more_than_three ; lea tab1-4(pc),a2 move.l a5,a2 .loop addq.l #4,a2 NEXTBIT bcs.b .loop move.w (a2)+,d1 ; lea cont2(pc),a3 ; bra.b GetXB cont2 GETXBITS d2 add.w (a2),d2 ;d2 - number of compressed bytes Offset moveq #2,d1 ;count offset ; lea cont3(pc),a3 ; bra.b GetXB GETXBITS d0 cont3 add.w d0,d0 add.w d0,d0 move.l tab2(pc,d0.w),d1 GetOffs ; lea cont4(pc),a3 ;GetXB moveq #0,d0 ;subrutine - GetXBites from file ;.loop NEXTBIT ; addx.l d0,d0 ; dbra d1,.loop ; jmp (a3) GETXBITS d0 cont4 swap d1 add.w d1,d0 move.l a1,a3 sub.l d0,a3 ;MSW D0 is 0 - no problem with .l .loop move.b (a3)+,(a1)+ ;transfer bytes from buffer dbra d2,.loop move.b (a3)+,(a1)+ cmp.l a1,d4 ;is it end of file? bhi.w looping movem.l (a7)+,UNCOMPRESSREGS IFEQ SO move.l celkove,d0 ENDIF rts ;table for offset tab2 dc.l $00000004,$00200006,$00a00008,$02a00009 dc.l $06a0000a,$0ea0000b,$1ea0000c,$3ea0000d ;table for match length (max.is 1024 bytes) tab1 dc.l $00000002,$00010004,$00020008,$00030010 dc.l $00040020,$00050040,$00060080,$00070100 dc.l $00080200,$00090400 ;table for length of uncompressed bytes tab0 dc.w 0,$0000, 1,$0002, 2,$0006, 3,$000e dc.w 4,$001e, 5,$003e, 6,$007e, 7,$00fe dc.w 8,$01fe, 9,$03fe,$a,$07fe,$b,$0ffe dc.w $c,$1ffe,$d,$3ffe,$e,$7ffe,$f,$fffe ;+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ IFEQ 1 2 ; Currently not used in this program ;21:27 93.12.11 ;Hufman static encoding ;d7 lenght of the file ;a0 start of file ;a1 start of tables ;memory map ;TABLE bytes -> longwords /1KB table of indexs ;compressed tree /1KB frequence ;buffer /1KB copy of frequency/tree - sons ; /1KB tree - fathers ;st ; move.l #konec-soubor,d7 ; lea soubor(pc),a0 lea table(pc),a1 add.l #$1000,a1 ;clear tables move.l #$2ff,d0 moveq #0,d1 .cleart move.l d1,-(a1) dbra d0,.cleart subq.b #1,d1 .make move.l d1,-(a1) ;initialize index-table dbra d1,.make move.l d7,d0 subq.l #1,d0 move.l a1,a2 add.l #$400,a2 swap d0 .count0 swap d0 .count1 moveq #0,d1 ;frequency of bytes move.b (a0)+,d1 lsl.w #2,d1 addq.l #1,(a2,d1.w) dbra d0,.count1 swap d0 dbra d0,.count0 continue_huffman move.l uloa1,a1 move.l uloa2,a2 move.l a2,a4 move.l #ta,a3 ;pro strom delek move.w #$ff,d0 ;.copyc move.l (a3)+,(a4)+ ; dbra d0,.copyc move.l a2,a3 ;copy into work partition add.l #$400,a3 move.w #$ff,d0 copycet move.l (a2)+,(a3)+ dbra d0,copycet ;------------------------------------------------ ; Now we'll build tree ;d0 various ;d1 big loop ;d2 small loop ;d3 first minimum ;d4 second minimum ;d5 position 1 min ;d6 position 2 min ;a1 start of tables - index ;a2 index table - moving in big loop ;a3 frequency ;a4 frequency moving in small loop ;a5 frequency moving in big loop ;a6 table of fathers ;------------------------------------------------ moveq #0,d2 ;prepare registers move.l d2,d1 bset #10,d1 move.l a1,a2 move.l a1,a3 add.l d1,a3 add.l d1,a3 move.l a3,a5 move.l a3,a6 add.l d1,a6 lsr.w #2,d1 make_tr0 move.l #$7fffffff,d3 ;start of big loop move.b d1,d2 move.l a5,a4 make_tr1 move.l (a4)+,d0 ;small loop beq.s make_tr3 cmp.l d0,d3 ble.s make_tr2 ;compare with first minimum move.l d3,d4 move.w d5,d6 move.l d0,d3 move.w d2,d5 bra.s make_tr3 make_tr2 cmp.l d0,d4 ble.s make_tr3 ;otherwise with second minimum move.l d0,d4 move.w d2,d6 make_tr3 addq.b #1,d2 bne.s make_tr1 ;next in small loop add.l d4,d3 ;now D4, D5 contains two minimums bmi.s make_trend cmp.w d5,d6 ;we need to be D5>D6 bcs.s make_tr4 exg d5,d6 ;if they aren't then swap them make_tr4 lsl.w #2,d5 move.l d3,(a3,d5.w) ;new frequency lsl.w #2,d6 move.l (a5),(a3,d6.w) move.w $02(a1,d6.w),d4 move.w d4,(a5)+ move.b d1,(a6,d4.w) ;left son move.w $02(a1,d5.w),d4 move.w d4,(a5)+ move.b d1,(a6,d4.w) ;right son move.w d1,$02(a1,d5.w) ;new father move.l (a2)+,(a1,d6.w) addq.b #1,d1 bne.s make_tr0 ;next in big loop make_trend ;------------------------------------------------ ; Here we make short_cuts for each byte ;d0 temporary ;d1 main index ;d2 index for each byte ;d3 copy of index ;d4 for rotation ;d5 for counting roration ;d6 bit counter ;------------------------------------------------ cuts move.l a1,a2 move.l a2,a3 moveq #0,d1 moveq #0,d6 bset #10,d1 add.l d1,a3 ;frequency move.l a3,a4 add.l d1,a4 ;sons move.l a4,a5 add.l d1,a5 ;fathers moveq #0,d1 moveq #0,d7 ;total lenght of packed file cuts_loop1 moveq #0,d3 moveq #0,d4 moveq #1,d5 move.b (a5,d1.w),d3 move.w d3,d0 bset #8,d3 lsl.w #2,d0 cmp.w (a4,d0.w),d1 bne.s cuts_loop3 bset #31,d4 bra.s cuts_loop3 cuts_loop2 moveq #0,d0 move.b d3,d0 addq.b #1,d5 lsr.l #1,d4 lsl.w #2,d0 cmp.w (a4,d0.w),d2 bne.s cuts_loop3 bset #31,d4 cuts_loop3 move.w d3,d2 move.b (a5,d3.w),d3 bne.s cuts_loop2 move.b d5,d4 ;length in bits into the lowest byte move.l (a3)+,d3 ;add to new lenght of file bne.s cuts_l5 moveq #0,d4 bra.b cuts_l6 cuts_l5 add.w d5,d6 cuts_l6 subq.b #1,d5 cuts_l4 add.l d3,d7 dbra d5,cuts_l4 move.l d4,(a2)+ addq.b #1,d1 bne.s cuts_loop1 lsr.l #3,d7 move.w #255,d5 moveq #0,d4 move.l #t1,a0 .lop move.l (a0)+,d0 add.w d0,d4 dbra d5,.lop lsr.w #3,d4 add.w #128,d4 move.l celkove,d5 sub.l bytneko,d5 add.l d7,d5 add.l d4,d5 move.l bitleng,d0 lsr.l #3,d0 move.l d0,bitleng move.l bitoffs,d0 lsr.l #3,d0 move.l d0,bitoffs move.l bitneko,d0 lsr.l #3,d0 move.l d0,bitneko move.l celkove,d0 rts uloa1 dc.l 0 uloa2 dc.l 0 table ds.b 4096 t1 equ table t2 equ table+4*256 t3 equ table+8*256 t4 equ table+12*256 bitleng dc.l 0 bitoffs dc.l 0 bitneko dc.l 0 offslen dc.l 0 offssho dc.l 0 bytneko dc.l 0 bytkomp dc.l 0 ENDC IFEQ SO celkove dc.l 0 ;------------------------------- ta ds.b 300*4 buf1str ds.b 2*bufferlength ;kvuli zapornym adresam buf2str ds.b indexlength cnop 0,4 u uklad ds.b $8000 s source incdir 'ram:' incbin "OneFont" endcode dc.b 6,5,4,3,2,1,2,3,4,5,6,0,0,0,0,0 ENDC