deflate.s

给出了 zip 压缩算法的完整实现过程。

        MOVINT  Head,d0                 ; parm for longest_match
        bsr     longest_match           ; sets match_start
        cmp.w   Look,d0                 ; does length exceed valid data?
        bls.s   fstml
        move.w  Look,d0
fstml:  move.w  d0,MatchL               ; valid length of match

fno_new_match:
        cmp.w   #MIN_MATCH,MatchL
        blo     fliteral
        ; CHECK_MATCH   Strst,match_start,MatchL
        MOVINT  Strst,_strstart         ; ct_tally reads this variable
        move.l  MatchL,d0
        subq.w  #MIN_MATCH,d0
        movem.l d2/a2,-(sp)
        MOVINT  d0,-(sp)
        move.l  Strst,d0
        sub.w   (match_start,pc),d0
        MOVINT  d0,-(sp)
        jsr     _ct_tally               ; sets d0 true if we have to flush
        addq    #2*INTSIZE,sp
        movem.l (sp)+,d2/a2
        sub.w   MatchL,Look
        cmp.w   (max_lazy_match,pc),MatchL
        bhi     ftoolong
        subq.w  #2,MatchL
finsertmatch:
        addq.w  #1,Strst
        IN_STR  a0,d1                   ; preserve d0
        dbra    MatchL,finsertmatch
        moveq   #0,MatchL               ; not needed?
        addq.w  #1,Strst
        bra.s   flushfill

ftoolong:
        add.w   MatchL,Strst
        moveq   #0,MatchL
        moveq   #0,d1                   ; preserve d0
        move.b  (Window,Strst.l),d1
        move.w  d1,ins_h
; My assembler objects to passing <1(Window,Strst.l)> directly to UP_HASH...
        move.b  1(Window,Strst.l),Avail ; Avail is not used in deflate_fast
        UP_HASH d1,Avail                ; preserve d0
    IFNE    MIN_MATCH-3
        FAIL  needs to UP_HASH another MIN_MATCH-3 times, but with what arg?
    ENDC
        bra.s   flushfill

fliteral:
        TRACE_C <(Window,Strst.l)>
        MOVINT  Strst,_strstart         ; ct_tally reads this variable
        moveq   #0,d0
        move.b  (Window,Strst.l),d0
        movem.l d2/a2,-(sp)
        MOVINT  d0,-(sp)
        CLRINT  -(sp)
        jsr     _ct_tally               ; d0 set if we need to flush
        addq    #2*INTSIZE,sp
        movem.l (sp)+,d2/a2
        addq.w  #1,Strst
        subq.w  #1,Look

flushfill:
        tst.w   d0
        beq.s   frefill
        FLUSH_B 0
        move.l  Strst,_block_start
frefill:
        cmp.w   #MIN_LOOKAHEAD,Look
        bhs     flook_loop
        bsr     fill_window
        bra     flook_loop

flast_flush:
        FLUSH_B 1                       ; sets our return value

deflate_exit:
        MOVINT  Strst,_strstart         ; save back cached values
        move.w  PrevL,prev_length
        move.w  Look,lookahead
        movem.l (sp)+,DEFREGS
        rts


; =========================================================================
; void fill_window(void) calls the input function to refill the sliding
; window that we use to find substring matches in.

More    reg     Head                    ; local variable in fill_window
WindTop reg     Prev                    ; local variable used for sliding
SlidIx  reg     PrevL                   ; local variable used for sliding

FWREGS  reg     d2-d5/a2-a6             ; does NOT include Look and Strst
; all registers available to be clobbered by the sliding operation:
; we exclude More, WindTop, SlidIx, Look, Strst, Window, a4 and a7.
SPAREGS reg     d0-d3/a0-a1/a5-a6
SPCOUNT equ     8                       ; number of registers in SPAREGS


_fill_window:                           ; C-callable entry point
        movem.l Look/Strst,-(sp)
    IFDEF   INT16
        moveq   #0,Strst                ; Strst must be valid as a long
    ENDC
        MOVINT  (_strstart,pc),Strst
        move.w  (lookahead,pc),Look
        BASEPTR _window,Window
        bsr.s   fill_window
        MOVINT  Strst,_strstart
        move.w  Look,lookahead
        movem.l (sp)+,Look/Strst
        rts

; strstart, lookahead, and window must be cached in Strst, Look, and Window:
fill_window:                            ; asm-callable entry point
        movem.l FWREGS,-(sp)
        move.w  (eofile,pc),d0          ; we put this up here for speed
        bne     fwdone
        and.l   #$FFFF,Look             ; make sure Look is valid as long
fw_refill:
        move.l  (_window_size,pc),More  ; <= 64K
        sub.l   Look,More
        sub.l   Strst,More              ; Strst is already valid as long
        cmp.w   #EOF,More
        bne.s   notboundary
        subq.w  #1,More
        bra     checkend

notboundary:
        move.w  (sliding,pc),d0
        beq     checkend
        cmp.w   #WSIZE+MAX_DIST,Strst
        blo     checkend
    IF      (32768-WSIZE)>0
        lea     WSIZE(Window),WindTop   ; WindTop is aligned when Window is
    ELSE
        move.l  Window,WindTop
        add.l   #WSIZE,WindTop
    ENDC
        move.l  Window,d0
        and.w   #3,d0
        beq.s   isaligned
        subq.w  #1,d0
align:  move.b  (WindTop)+,(Window)+    ; copy up to a longword boundary
        dbra    d0,align
isaligned:
; This is faster than a simple move.l (WindTop)+,(Window)+ / dbra loop:
        move.w  #(WSIZE-1)/(4*SPCOUNT),SlidIx
slide:  movem.l (WindTop)+,SPAREGS      ; copy, 32 bytes at a time!
        movem.l SPAREGS,(Window)        ; a slight overshoot doesn't matter.
        lea     4*SPCOUNT(Window),Window        ; can't use (aN)+ as movem.l dest
        dbra    SlidIx,slide
        BASEPTR _window,Window                  ; restore cached value
        sub.w   #WSIZE,match_start
        sub.w   #WSIZE,Strst
        sub.l   #WSIZE,_block_start
        add.w   #WSIZE,More
        BASEPTR _head,a0
        move.w  #HASH_SIZE-1,d0
fixhead:
        move.w  (a0),d1
        sub.w   #WSIZE,d1
        bpl.s   headok
        moveq   #0,d1
headok: move.w  d1,(a0)+
        dbra    d0,fixhead
        BASEPTR _prev,a0
        move.w  #WSIZE-1,d0
fixprev:
        move.w  (a0),d1
        sub.w   #WSIZE,d1
        bpl.s   prevok
        moveq   #0,d1
prevok: move.w  d1,(a0)+
        dbra    d0,fixprev
        TRACE_C #'.'

        move    _verbose+INTSIZE-2,d0
        beq     checkend
        movem.l d2/a2,-(sp)
        xref    _print_period
        jsr     _print_period
        movem.l (sp)+,d2/a2

checkend:                               ; assert eofile is false
        movem.l d2/a2,-(sp)
        MOVINT  More,-(sp)              ; assert More's upper word is zero
        move.l  Strst,d0
        add.w   Look,d0
        add.l   Window,d0
        move.l  d0,-(sp)
        move.l  _read_buf,a0
        jsr     (a0)                    ; refill the upper part of the window
        addq    #4+INTSIZE,sp
        movem.l (sp)+,d2/a2
        tst.w   d0
        beq.s   iseof
        cmp.w   #EOF,d0
        beq.s   iseof
        add.w   d0,Look
        cmp.w   #MIN_LOOKAHEAD,Look
        blo     fw_refill               ; eofile is still false

        bra.s   fwdone
iseof:  move.w  #1,eofile
fwdone: movem.l (sp)+,FWREGS
        rts


; =========================================================================
; void lm_free(void) frees dynamic arrays in the DYN_ALLOC version.

;;;     xdef    _lm_free                ; the entry point

_lm_free:
    IFDEF   DYN_ALLOC
        move.l  _window,d0
        beq.s   lf_no_window
        movem.l d2/a2,-(sp)
        move.l  d0,-(sp)
        jsr     _free
        addq    #4,sp
        movem.l (sp)+,d2/a2
        clr.l   _window
lf_no_window:
        move.l  _prev,d0
        beq.s   lf_no_prev
        movem.l d2/a2,-(sp)
        move.l  d0,-(sp)
        jsr     _free
        move.l  _head,(sp)              ; reuse the same stack arg slot
        jsr     _free
        addq    #4,sp
        movem.l (sp)+,d2/a2
        clr.l   _prev
        clr.l   _head
lf_no_prev:
    ENDC
        rts

; ============================================================================
; void lm_init(int pack_level, unsigned short *flags) allocates dynamic arrays
; if any, and initializes all variables so that deflate() is ready to go.

;;;     xdef    _lm_init                ; the entry point

Level   reg     d2
;Window reg     a2      ; as in deflate()

_lm_init:
        MOVINT  4(sp),d0
        move.l  4+INTSIZE(sp),a0
        move.w  d0,Level
        cmp.w   #1,Level
        blt.s   levelerr
        bgt.s   try9
        bset.b  #B_FAST,1(a0)
try9:   cmp.w   #9,Level
        bgt.s   levelerr
        blt.s   levelok
        bset.b  #B_SLOW,1(a0)
        bra.s   levelok
levelerr:
        pea     (level_message,pc)
        jsr     _error                  ; never returns
levelok:
        clr.w   sliding
        move.l  (_window_size,pc),d0
        bne.s   gotawindowsize
        move.w  #1,sliding
        move.l  #2*WSIZE,_window_size
gotawindowsize:

        BASEPTR _window,Window
    IFDEF   DYN_ALLOC
        move.l  Window,d0               ; fake tst.l
        bne.s   gotsomewind
        CAL_SH  WSIZE
        move.l  d0,Window
        move.l  d0,_window
        bne.s   gotsomewind
        pea     (window_message,pc)
        bra     error
gotsomewind:
        tst.l   _prev
        bne.s   gotsomehead
        CAL_SH  WSIZE
        move.l  d0,_prev
        beq.s   nohead
        CAL_SH  HASH_SIZE
        move.l  d0,_head
        bne.s   gotfreshhead            ; newly calloc'd memory is zeroed
nohead: pea     (hash_message,pc)
error:  MOVINT  #ZE_MEM,-(sp)
        jsr     _ziperr                 ; never returns
gotsomehead:
    ENDC    ; DYN_ALLOC

        move.w  #(HASH_SIZE/2)-1,d0     ; two shortwords per loop
        BASEPTR _head,a0
wipeh:  clr.l   (a0)+
        dbra    d0,wipeh
gotfreshhead:
        move.l  Level,d0
    IFEQ    Sizeof_config-8
        asl.l   #3,d0
    ELSE
        mulu    #Sizeof_config,d0
    ENDC
        lea     (config_table,pc),a0
        add.l   d0,a0
        move.w  Max_lazy(a0),max_lazy_match
        move.w  Good_length(a0),good_match
        move.w  Nice_length(a0),nice_match
        move.w  Max_chain(a0),max_chain_len
        CLRINT  _strstart
        clr.l   _block_start
        bsr     match_init

        clr.w   eofile
        movem.l d2/a2,-(sp)
        MOVINT  #WSIZE,-(sp)    ; We read only 32K because lookahead is short
        move.l  Window,-(sp)    ; even when int size is long, as if deflate.c
        move.l  _read_buf,a0    ; were compiled with MAXSEG_64K defined.
        jsr     (a0)
        addq    #4+INTSIZE,sp
        movem.l (sp)+,d2/a2
        move.w  d0,lookahead
        beq.s   noread
        cmp.w   #EOF,d0
        bne.s   irefill
noread: move.w  #1,eofile
        clr.w   lookahead
        bra.s   init_done

irefill:
        move.w  (lookahead,pc),d0
        cmp.w   #MIN_LOOKAHEAD,d0
        bhs.s   hashify
        bsr     _fill_window            ; use the C-callable version
hashify:
        clr.w   ins_h
        moveq   #MIN_MATCH-2,d0
hash1:  move.b  (Window)+,d1
        UP_HASH Level,d1
        dbra    d0,hash1

init_done:
        rts

; strings for error messages:
    IFDEF   DYN_ALLOC
hash_message    dc.b    'hash table allocation',0
window_message  dc.b    'window allocation',0
    ENDC
level_message   dc.b    'bad pack level',0

        end