;---------------------------------------------------------------------------; ; ; ; This is the Ross Data Compression implemented in 68000 assembler ; ; by Niklas Sjöberg, 2:203/415.3@Fidonet ; ; ; ; ; ; The source is fully in the Public Domain. If you think you can improve ; ; some parts, feel free to modify the code. HOWEVER, be carefull to comment ; ; the parts where you change! ; ; ; ; On entry (if you compre to the C-code): ; ; ; ; a0 = ctrl_idx, pointer to 'outbuff' where the 16 bits control-word is ; ; stored after each 16th sequence. On startup, ctrl_idx is set to ; ; the start of 'outbuff' and 'outbuff' is advanced two bytes. ; ; a1 = in_idx, pointer to next byte of input ; ; a2 = out_idx, pointer to 'outbuff' ; ; a3 = inbuff_end, end of input buffer (could you guess? :) ; ; a4 = anchor, temporary pointer to in_idx, undefined on entry! ; ; a5 = pat_idx, temporary pointer to pattern in dictionary, undefined on ; ; entry! ; ; a6 = hash_tbl (uchar **hash_tbl) pointer. Size is 16K, just enough for ; ; 4096 pointers. ; ; d0 = ctrl_cnt, used to keep track of when control-word is to be written ; ; to ctrl_idx. (every 16th sequence). Start at 1(!), counts to 16 ; ; 0 one startup, but note that d0 is increased by one _before_ it ; ; actually is used. ; d1 = c. Stores various chars when comparing source and destination. ; ; always byte-size. Zero on startup. ; ; d2 = cnt. Stores different values. Used as a 'quick counter' instead of ; ; subtracting to addresses. Zero on startup. ; ; d3 = ctrl_bits, 16 bit compression code. Zero on startup. ; ; d4 = gap. Used as counter to see if pattern occured with 4098 range. ; ; Zero on startup. ; ; d5 = hash. 16 bit hash-value used as dictionary lookup. Always in range ; ; from 0 to 4095. Zero on startup. ; ; d6 = outbuff_end, end of 'outbuff'. If we exceed this limit (actually we ; ; have a 48 byte margin) data couldn't be compressed! ; ; ; ; ; ;---------------------------------------------------------------------------; ; Since both a4 and a5 just are used temprarily they're used as temporary ; ; scratch in some places. Similary d5 (hash) and d7 are used as scratch ; ;---------------------------------------------------------------------------; ; ; ; Version changes: ; 921205 - ctrl_cnt (d0) now count from 16 and downwards. Slightly faster. ; Now uses bset instead of asl and or. ; 921205 - Due to optimizing all comments may not be totally accurate. Ie. ; you have to read 5 lines at a time in order to understand the ; comments.. xdef _pack_one ; only one routine, called from the ; C-part of the library INCLUDE "libraries/xpksub.i" section code _pack_one movem.l a2-a6/d2-d7,-(SP) ; Save non-scratch registers moveq #16,d0 moveq #$0,d1 moveq #$0,d2 moveq #$0,d3 moveq #$0,d4 moveq #$0,d5 moveq #$0,d7 suba.l a4,a4 ; not necessary, but may help debugging. suba.l a5,a5 pstart cmpa.l a1,a3 ; Main-loop, running as long as in_idx bls.w ploop_end ; doesn't exceed outbuff_end. tst.b d0 ; Is it time to write controlbits into bne.s no_makeroom ; ctrl_idx? move.w d3,(a0) ; store control-word and moveq #0,d3 moveq #15,d0 ; advance out_idx two bytes. move.l a2,a0 ; but first store address where addq.w #2,a2 ; the next word is to be written cmp.l d6,a2 ; Make sure there is no overflow. bls.s no_overflow ; out_idx really should be < outbuff_end :) moveq #0,d0 ; If overflow the C-code will return movem.l (SP)+,a2-a6/d2-d7 ; XPKERR_EXPANSION rts ; This and ploop end are the only exit points no_makeroom subq.b #1,d0 ; Increase ctrl_cnt no_overflow move.l a1,a4 ; Use anchor = in_idx move.b (a1)+,d1 ; First byte to compare. in_idx is advanced moveq #1,d2 ; and we use 'quick counter' cnt in d2. rep1 cmp.b (a1),d1 ; Does next char match the one before bne.s nrep cmp.w #4114,d2 ; Make sure we don't exceed the longest bge.s nrep ; possible RLE cmpa.l a1,a3 ; Make sure we're not running out of source bls.s nrep addq.w #1,a1 ; Bytes obviously was equal, advance in_idx addq.w #1,d2 ; to next byte. bra.s rep1 nrep cmpi.w #$2,d2 ; cnt must > 2 in order to be able to compress bls.s n_rleseq ; check for pattern if cnt <= 2 cmpi.w #18,d2 ; if cnt <= 18 we use short form of RLE bgt.s l_rlen subq.b #3,d2 ; count, at least three chars move.b d2,(a2)+ move.b d1,(a2)+ ; the character itself bset d0,d3 ; asl.w #1,d3 ; Shift and set control bits ; or.w #1,d3 bra.s pstart ; re-start loop, until in_idx => outbuff_end l_rlen ; If cnt > 18 we encode a long RLE (max 4114 chars) sub.w #19,d2 ; cnt -= 19, at least 19 repeated characters move.b d2,d7 ; out_idx++ = 16 + (cnt & 0x0F) Store low count and.b #15,d7 ; and code add.b #16,d7 move.b d7,(a2)+ asr.w #4,d2 ; out_idx++ = cnt >> 4 move.b d2,(a2)+ ; and store high count move.b d1,(a2)+ ; the character itself ; asl.w #1,d3 ; Just like above, set and shift ; or.w #1,d3 bset d0,d3 bra.s pstart n_rleseq ; if cnt <= 2 we have to search for patterns move.l a3,a5 ; inbuff_end - in_idx > 2 suba.l a4,a5 ; we must have at least 3 characters left in cmpa.w #$2,a5 ; order to calc the hash. bls.w cant_compress ; if less bytes left, just copy them move.l a4,a1 ; in_idx = anchor, restore to original start moveq #0,d5 ; hash moveq #0,d7 ; scratch ; Now lets calculate the hash, in C this is done as: ; unsigned short int hash = ((((in_idx[0] & 15) << 8) | in_idx[1]) ^ ; ((in_idx[0] >> 4) | (in_idx[2] << 4))) & 4096-5 ; ; cnt (=d2) is used as scratch here.. move.b (a1),d5 ; in_idx[0] & 15 << 8 move.b d5,d7 ; in_idx[0] and.b #15,d5 asl.w #8,d5 or.b 1(a1),d5 ; | in_idx[1] asr.b #4,d7 ; ^ in_idx[0] >> 4 moveq #0,d2 ; gee, almost ran out of registers :) move.b 2(a1),d2 ; in_idx[2] << 4 asl.w #4,d2 or.w d2,d7 eor.w d7,d5 and.w #4096-1,d5 asl.w #2,d5 ; char * is 4 bytes, adjust offset ; The zero here is used in order to stop SAS asm from stupid complaining! move.l 0(a6,d5.w),a5 ; pat_idx now zero or pointer to pattern move.l a1,0(a6,d5.w) ; store in_idx at this offset move.l a1,d4 ; gap = in_idx - pat_idx, ie. if move.l a5,d7 ; pat_idx was zero, gap will be huge sub.l d7,d4 ; which showed that we didn't find cmp.l #4098,d4 ; a pattern. That's why .l is used here! bgt.s cant_compress moveq #0,d2 : clr cnt rep2 move.b (a1),d7 ; also, the byte pattern_idx points to must cmp.b (a5),d7 ; equal to the current inbyte. bne.s nrep2 cmpa.l a5,a4 ; and pat_idx doesn't advance into the source! bls.s nrep2 ; this is VERY important!! cmpa.l a1,a3 ; While we don't run out of source.. bls.s nrep2 cmpi.w #271,d2 ; This is the longest pattern we can handle beq.s nrep2 addq.w #1,a1 ; advance inbuffer addq.w #1,a5 ; advance pattern-pointer to next byte addq.w #1,d2 ; advance pattern-length bra.s rep2 nrep2 cmp.w #2,d2 ; If cnt <= 2 we can't compress! bls.w cant_compress subq.w #3,d4 ; gap -= 3, at least length of three cmpi.w #15,d2 ; if cnt <= 15 we encode as short pattern bgt.s is_lpat asl.b #4,d2 ; *out_idx++ = (cnt << 4) + (gap & 0x0F) move.b d4,d7 ; store count (low) and low offset and.b #15,d7 add.b d7,d2 move.b d2,(a2)+ asr.w #4,d4 ; *out_idx++ = gap >> 4 move.b d4,(a2)+ ; store high offset in hash-table ; asl.w #1,d3 ; set and shift control-bits ; or.w #1,d3 bset d0,d3 bra.w pstart ; back to main-loop ; cnt > 15 so encode as long pattern is_lpat move.b d4,d7 ; *out_idx++ = 32 + (gap & 0x0F) and.b #15,d7 ; store 2 (low) and low offset add.b #32,d7 move.b d7,(a2)+ asr.w #4,d4 ; *out_idx++ = gap >> 4 move.b d4,(a2)+ ; store high offset sub.w #16,d2 ; *out_idx++ = cnt - 16; move.b d2,(a2)+ ; store count (since length is at least ; 16 we can subtract 16 and thus handle ; patterns <= 271 ; asl.w #1,d3 ; set and shift control word ; or.w #1,d3 bset d0,d3 bra.w pstart cant_compress move.b d1,(a2)+ ; Data couldn't be compressed so ; addq.l #1,a4 : just copy to out_idx, and set ; move.l a4,a1 ; in_idx to next byte of data lea 1(a4),a1 ; asl.w #1,d3 ; Do NOT set control bit, just shift bra.w pstart ploop_end ; We ran out of buffer, phew! ; move.w #16,d7 ; make sure the last control bits ; sub.w d0,d7 ; are written to ctrl_idx first- ; asl.w d7,d3 move.w d3,(a0) ; *ctrl_idx = ctrl_bits move.l a2,d0 ; return out_idx, on error (overflow) movem.l (SP)+,a2-a6/d2-d7 ; we return 0 rts END