deflate.a

infozip2.2源码

; This is a 680x0 assembly language translation of the Info-ZIP source file
; deflate.c, by Paul Kienitz.  No rights reserved.  The function longest_match
; is based in part on match.a by Carsten Steger, which in turn is partly based
; on match.s for 386 by Jean-loup Gailly and Kai Uwe Rommel.  Mostly, however,
; this material is based on deflate.c, by Gailly, Rommel, and Igor Mandrichenko.
; This code is not commented very much; see deflate.c for comments that explain
; what the functions are doing.
;
; The symbols that can be used to select different versions are as follows:
;
;   CPU020     if defined, use 68020 instructions always.
;
;   CPUTEST    if defined, check at runtime for CPU type.  Another symbol
;               specifying the platform-specific test must be used with this.
;               If neither of these is defined, use 68000 instructions only.
;               Runtime test is nonportable; it is different for each OS.
;
;   AMIGA      use Amiga-specific test for 68020, if CPUTEST defined.  Also
;               tells it that registers d0/a0/d1/a1 are not preserved by
;               function calls.  At present, if AMIGA is not defined, it
;               causes functions to preserve all registers.  ALL OF THIS CODE
;               CURRENTLY ASSUMES THAT REGISTERS D2-D7/A2-A6 WILL BE PRESERVED
;               BY ANY FUNCTIONS THAT IT CALLS.
;
;   DYN_ALLOC  should be defined here if it is defined for C source; tells us
;               that big arrays are allocated instead of static.
;
;   WSIZE      must be defined as the same number used for WSIZE in the C
;               source, and must be a power of two <= 32768.  As elsewhere,
;               the default value is 32768.
;
;   INT16      define this if ints are 16 bits; otherwise 32 bit ints assumed.
;
;   SMALL_MEM  define this if it is defined in the C source; otherwise it uses
;               the MEDIUM_MEM model.  BIG_MEM and MMAP are *not* supported.
;               The FULL_SEARCH option in deflate.c is also not supported.
;
;   DEBUG      activates some tracing output, as in the C source.
;
;   QUADLONG   this selects a different version of the innermost longest_match
;               loop code for 68020 operations, comparing bytes four at a time
;               instead of two at a time.  It seems to be a tiny bit faster on
;               average, but it's slower often enough that one can't generalize.
;
; This code currently assumes that function results are returned in D0 for
; all platforms.  It assumes that args to functions are pushed onto the stack,
; last arg first.  It also currently assumes that all C symbols have an
; underscore prepended when referenced from assembly.

    IFND    CPU020
     IFND   CPUTEST
CPU000  equ     1
     ENDC
    ENDC

; Use these macros for accessing variables of type int:
    IFD     INT16
MOVINT  MACRO
        move.w  \1,\2
        ENDM
CLRINT  MACRO
        clr.w   \1
        ENDM
INTSIZE equ     2
    ELSE    ; !INT16
MOVINT  MACRO
        move.l  \1,\2
        ENDM
CLRINT  MACRO
        clr.l   \1
        ENDM
INTSIZE equ     4
    ENDC

    IFD     DYN_ALLOC
BASEPTR MACRO
        move.l  \1,\2
        ENDM
    ELSE
BASEPTR MACRO
        lea     \1,\2
        ENDM
    ENDC

; constants we use, many of them adjustable:

MAX_MATCH       equ     258
MIN_MATCH       equ     3
TOO_FAR         equ     4096
    IFND    WSIZE
WSIZE           equ     32768
    ENDC
WMASK           equ     WSIZE-1
MAX_DIST        equ     WSIZE-MAX_MATCH-MIN_MATCH-1
MIN_LOOKAHEAD   equ     MAX_MATCH+MIN_MATCH+1
;    IFD     BIG_MEM      ; NOT supported -- type Pos needs to be 32 bits
;HASH_BITS      equ     15
;    ELSE
    IFD    SMALL_MEM
HASH_BITS       equ     13
    ELSE
HASH_BITS       equ     14      ; default -- MEDIUM_MEM
    ENDC
;    ENDC    ; BIG_MEM
HASH_SIZE       equ     1<<HASH_BITS
HASH_MASK       equ     HASH_SIZE-1
H_SHIFT         equ     (HASH_BITS+MIN_MATCH-1)/MIN_MATCH
B_SLOW          equ     1
B_FAST          equ     2
ZE_MEM          equ     4
EOF             equ     -1

; struct config is defined by these offsets:
Good_length     equ     0
Max_lazy        equ     2
Nice_length     equ     4
Max_chain       equ     6
Sizeof_config   equ     8


; external functions we call:
        xref    _ct_tally       ; int ct_tally(int, int)
        xref    _flush_block    ; unsigned long F(char *, unsigned long, int)
        xref    _ziperr         ; void ziperr(int, char *)
        xref    _error          ; void error(char *)
        xref    _calloc         ; stdlib function: void *calloc(size_t, size_t)
        xref    _free           ; stdlib function: void free(void *)
    IFD     DEBUG
        xref    _fputc          ; stdio function: int fputc(int, FILE *)
        xref    _stderr         ; pointer to FILE, which we pass to fputc
    ENDC

; our entry points:
        xdef    _lm_init        ; void lm_init(int level, unsigned short *flags)
        xdef    _lm_free        ; void lm_free(void)
        xdef    _deflate        ; void deflate(void)  ...the big one
        xdef    _fill_window    ; this line is just for debugging


; ============================================================================
; Here is where we have our global variables.

        section deflatevars,data

; external global variables we reference:
        xref    _verbose        ; signed int
        xref    _level          ; signed int
        xref    _read_buf       ; int (*read_buf)(char *, unsigned int)

; global variables we make available:

        xdef    _window
        xdef    _prev
        xdef    _head
        xdef    _window_size
        xdef    _block_start
        xdef    _strstart

    IFD     DYN_ALLOC
_prev:          ds.l    1       ; pointer to calloc()'d unsigned short array
_head:          ds.l    1       ; pointer to calloc()'d unsigned short array
_window:        ds.l    1       ; pointer to calloc()'d unsigned char array
    ELSE    ; !DYN_ALLOC
_prev:          ds.w    WSIZE           ; array of unsigned short
_head:          ds.w    HASH_SIZE       ; array of unsigned short
_window:        ds.b    2*WSIZE         ; array of unsigned char
    ENDC    ; ?DYN_ALLOC
_window_size:   ds.l    1               ; unsigned long
_block_start:   ds.l    1               ; unsigned long
_strstart:      ds.w    INTSIZE/2       ; unsigned int

; Now here are our private variables:

    IFD     CPUTEST
is020:          ds.w    1       ; bool: CPU type is '020 or higher
    ENDC
ins_h:          ds.w    1       ; unsigned short
sliding:        ds.w    1       ; bool: the file is read a piece at a time
eofile:         ds.w    1       ; bool: we have read in the end of the file
max_lazy_match: ds.w    1       ; unsigned short
lookahead:      ds.w    1       ; unsigned short

; These are NOT DECLARED AS STATIC in deflate.c, but currently could be:
max_chain_len:  ds.w    1       ; unsigned short (unsigned int in deflate.c)
prev_length:    ds.w    1       ; unsigned short (unsigned int in deflate.c)
good_match:     ds.w    1       ; unsigned short (unsigned int in deflate.c)
nice_match:     ds.w    1       ; unsigned short (signed int in deflate.c)
match_start:    ds.w    1       ; unsigned short (unsigned int in deflate.c)

; This array of struct config is a constant and could be in the code section:
config_table:   dc.w    0,0,0,0         ; level 0: store uncompressed
                dc.w    4,4,8,4         ; level 1: fastest, loosest compression
                dc.w    4,5,16,8        ; level 2
                dc.w    4,6,32,32       ; level 3: highest to use deflate_fast
                dc.w    4,4,16,16       ; level 4: lowest to use lazy matches
                dc.w    8,16,32,32      ; level 5
                dc.w    8,16,128,128    ; level 6: the default level
                dc.w    8,32,128,256    ; level 7
                dc.w    32,128,258,1024 ; level 8
                dc.w    32,258,258,4096 ; level 9: maximum compression, slow


;;CAL_SH  MACRO                   ; macro for calling zcalloc()
;;     IFD    INT16
;;        move.w  #2,-(sp)
;;        move.w  #\1,-(sp)
;;        jsr     _zcalloc
;;        addq    #4,sp
;;     ELSE
;;        pea     2
;;        pea     \1
;;        jsr     _zcalloc
;;        addq    #8,sp
;;     ENDC
;;        ENDM

CAL_SH  MACRO                   ; Okay, we're back to using regular calloc()...
        pea     2
        pea     \1
        jsr     _calloc
        addq    #8,sp
        ENDM

; ============================================================================
; And here we begin our functions.  match_init is for internal use only:

        section deflate,code

match_init:
    IFD     CPUTEST             ; now check for platform type
     IFD    AMIGA               ; Amiga specific test for '020 CPU:
        xref    _SysBase
        NOLIST
        INCLUDE       'exec/execbase.i'
        LIST

        clr.w   is020                   ; default value is 68000
        move.l  _SysBase,a0
        btst    #AFB_68020,AttnFlags+1(a0)
        beq.s   cheap
        move.w  #1,is020
cheap:
     ELSE   ; !AMIGA

        FAIL    Write an '020-detector for your system here!
; On the Macintosh, I believe GetEnvironment() provides the information.

     ENDC   ; AMIGA
    ENDC    ; CPUTEST
        rts     ; match_init consists only of rts if CPUTEST unset


; ============================================================================
; Here is longest_match(), the function that the rest of this was built up
; from, the hottest hot spot in the program and therefore the most heavily
; optimized.  It has two different versions, one for '020 and higher CPUs, and
; one for 68000/68010.  It can test at runtime which version to use if you
; create a test function in match_init for your platform.  Currently such a
; test is implemented for the Amiga.  It can also be assembled to use '000 or
; '020 code only.

Cur_Match       equr    d0              ; unsigned int, kept valid as long
Best_Len        equr    d1              ; unsigned int, kept valid as long
Scan_Start      equr    d3              ; pair of bytes
Scan_End        equr    d4              ; pair of bytes
Limit           equr    d5              ; unsigned int
Chain_Length    equr    d6              ; unsigned int
Scan_Test       equr    d7              ; counter, pair of bytes sometimes
Scan            equr    a0              ; pointer to unsigned char
Match           equr    a1              ; pointer to unsigned char
Prev_Address    equr    a2              ; pointer to unsigned short
Scan_Ini        equr    a3              ; pointer to unsigned char
Match_Ini       equr    a5              ; pointer to unsigned char
; Note: "pair of bytes" means the two low order bytes of the register in
; 68020 code, but means the lowest and third lowest bytes on the 68000.
    IFD     AMIGA
SAVEREGS        reg     d3-d7/a2/a3/a5      ; don't protect d0/d1/a0/a1
    ELSE    ; !AMIGA
SAVEREGS        reg     d1/d3-d7/a0-a3/a5   ; protect all except d0 return val
    ENDC    ; ?AMIGA
; d2, a4, a6 not used... on Amiga, a4 is used by small-data memory model


longest_match:
        movem.l SAVEREGS,-(sp)

; setup steps common to byte and word versions:
    IFD     INT16
        and.l   #$0000FFFF,Cur_Match    ; upper half must be zero!
; we use an and.l down here for the sake of ATSIGN/REGARGS.
        moveq   #0,Limit                ; so adding to Scan_Ini works
    ENDC
        move.w  max_chain_len,Chain_Length
        move.w  prev_length,Best_Len
        MOVINT  _strstart,Limit
        BASEPTR _prev,Prev_Address
        BASEPTR _window,Match_Ini
        move.l  Match_Ini,Scan_Ini
        addq    #MIN_MATCH,Match_Ini    ; optimizes inner loop
        add.l   Limit,Scan_Ini
        sub.w   #MAX_DIST,Limit
        bhi.s   limit_ok
        moveq   #0,Limit
limit_ok:
        cmp.w   good_match,Best_Len
        blo.s   length_ok
        lsr.w   #2,Chain_Length
length_ok:
        subq.w  #1,Chain_Length

    IFD     CPUTEST
        tst.w   is020                   ; can we use '020 stuff today?
        bne     WORD_match
    ENDC

    IFND    CPU020

; for 68000 or 68010, use byte operations:
        moveq   #0,Scan_Start           ; clear 2nd & 4th bytes, use 1st & 3rd
        moveq   #0,Scan_End             ; likewise
        moveq   #0,Scan_Test            ; likewise
        move.b  (Scan_Ini),Scan_Start
        swap    Scan_Start              ; swap is faster than 8 bit shift
        move.b  1(Scan_Ini),Scan_Start
        move.b  -1(Scan_Ini,Best_Len.w),Scan_End
        swap    Scan_End
        move.b  0(Scan_Ini,Best_Len.w),Scan_End
        bra.s   bdo_scan

blong_loop:
        move.b  -1(Scan_Ini,Best_Len.w),Scan_End
        swap    Scan_End
        move.b  0(Scan_Ini,Best_Len.w),Scan_End

bshort_loop:
        add.w   Cur_Match,Cur_Match     ; assert value before doubling < 32K
     IFNE   32768-WSIZE
        and.w   #(WMASK*2),Cur_Match
     ENDC
        move.w  (Prev_Address,Cur_Match.l),Cur_Match
        cmp.w   Limit,Cur_Match
        dbls    Chain_Length,bdo_scan
        bra     return

bdo_scan:
        move.l  Match_Ini,Match
        add.l   Cur_Match,Match
        move.b  -MIN_MATCH-1(Match,Best_Len.w),Scan_Test
        swap    Scan_Test