home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 9 Archive / 09-Archive.zip / zip22.zip / amiga / deflate.a < prev    next >
Text File  |  1997-10-15  |  35KB  |  1,046 lines
  1. ; This is a 680x0 assembly language translation of the Info-ZIP source file
  2. ; deflate.c, by Paul Kienitz.  No rights reserved.  The function longest_match
  3. ; is based in part on match.a by Carsten Steger, which in turn is partly based
  4. ; on match.s for 386 by Jean-loup Gailly and Kai Uwe Rommel.  Mostly, however,
  5. ; this material is based on deflate.c, by Gailly, Rommel, and Igor Mandrichenko.
  6. ; This code is not commented very much; see deflate.c for comments that explain
  7. ; what the functions are doing.
  8. ;
  9. ; The symbols that can be used to select different versions are as follows:
  10. ;
  11. ;   CPU020     if defined, use 68020 instructions always.
  12. ;
  13. ;   CPUTEST    if defined, check at runtime for CPU type.  Another symbol
  14. ;               specifying the platform-specific test must be used with this.
  15. ;               If neither of these is defined, use 68000 instructions only.
  16. ;               Runtime test is nonportable; it is different for each OS.
  17. ;
  18. ;   AMIGA      use Amiga-specific test for 68020, if CPUTEST defined.  Also
  19. ;               tells it that registers d0/a0/d1/a1 are not preserved by
  20. ;               function calls.  At present, if AMIGA is not defined, it
  21. ;               causes functions to preserve all registers.  ALL OF THIS CODE
  22. ;               CURRENTLY ASSUMES THAT REGISTERS D2-D7/A2-A6 WILL BE PRESERVED
  23. ;               BY ANY FUNCTIONS THAT IT CALLS.
  24. ;
  25. ;   DYN_ALLOC  should be defined here if it is defined for C source; tells us
  26. ;               that big arrays are allocated instead of static.
  27. ;
  28. ;   WSIZE      must be defined as the same number used for WSIZE in the C
  29. ;               source, and must be a power of two <= 32768.  As elsewhere,
  30. ;               the default value is 32768.
  31. ;
  32. ;   INT16      define this if ints are 16 bits; otherwise 32 bit ints assumed.
  33. ;
  34. ;   SMALL_MEM  define this if it is defined in the C source; otherwise it uses
  35. ;               the MEDIUM_MEM model.  BIG_MEM and MMAP are *not* supported.
  36. ;               The FULL_SEARCH option in deflate.c is also not supported.
  37. ;
  38. ;   DEBUG      activates some tracing output, as in the C source.
  39. ;
  40. ;   QUADLONG   this selects a different version of the innermost longest_match
  41. ;               loop code for 68020 operations, comparing bytes four at a time
  42. ;               instead of two at a time.  It seems to be a tiny bit faster on
  43. ;               average, but it's slower often enough that one can't generalize.
  44. ;
  45. ; This code currently assumes that function results are returned in D0 for
  46. ; all platforms.  It assumes that args to functions are pushed onto the stack,
  47. ; last arg first.  It also currently assumes that all C symbols have an
  48. ; underscore prepended when referenced from assembly.
  49.  
  50.     IFND    CPU020
  51.      IFND   CPUTEST
  52. CPU000  equ     1
  53.      ENDC
  54.     ENDC
  55.  
  56. ; Use these macros for accessing variables of type int:
  57.     IFD     INT16
  58. MOVINT  MACRO
  59.         move.w  \1,\2
  60.         ENDM
  61. CLRINT  MACRO
  62.         clr.w   \1
  63.         ENDM
  64. INTSIZE equ     2
  65.     ELSE    ; !INT16
  66. MOVINT  MACRO
  67.         move.l  \1,\2
  68.         ENDM
  69. CLRINT  MACRO
  70.         clr.l   \1
  71.         ENDM
  72. INTSIZE equ     4
  73.     ENDC
  74.  
  75.     IFD     DYN_ALLOC
  76. BASEPTR MACRO
  77.         move.l  \1,\2
  78.         ENDM
  79.     ELSE
  80. BASEPTR MACRO
  81.         lea     \1,\2
  82.         ENDM
  83.     ENDC
  84.  
  85. ; constants we use, many of them adjustable:
  86.  
  87. MAX_MATCH       equ     258
  88. MIN_MATCH       equ     3
  89. TOO_FAR         equ     4096
  90.     IFND    WSIZE
  91. WSIZE           equ     32768
  92.     ENDC
  93. WMASK           equ     WSIZE-1
  94. MAX_DIST        equ     WSIZE-MAX_MATCH-MIN_MATCH-1
  95. MIN_LOOKAHEAD   equ     MAX_MATCH+MIN_MATCH+1
  96. ;    IFD     BIG_MEM      ; NOT supported -- type Pos needs to be 32 bits
  97. ;HASH_BITS      equ     15
  98. ;    ELSE
  99.     IFD    SMALL_MEM
  100. HASH_BITS       equ     13
  101.     ELSE
  102. HASH_BITS       equ     14      ; default -- MEDIUM_MEM
  103.     ENDC
  104. ;    ENDC    ; BIG_MEM
  105. HASH_SIZE       equ     1<<HASH_BITS
  106. HASH_MASK       equ     HASH_SIZE-1
  107. H_SHIFT         equ     (HASH_BITS+MIN_MATCH-1)/MIN_MATCH
  108. B_SLOW          equ     1
  109. B_FAST          equ     2
  110. ZE_MEM          equ     4
  111. EOF             equ     -1
  112.  
  113. ; struct config is defined by these offsets:
  114. Good_length     equ     0
  115. Max_lazy        equ     2
  116. Nice_length     equ     4
  117. Max_chain       equ     6
  118. Sizeof_config   equ     8
  119.  
  120.  
  121. ; external functions we call:
  122.         xref    _ct_tally       ; int ct_tally(int, int)
  123.         xref    _flush_block    ; unsigned long F(char *, unsigned long, int)
  124.         xref    _ziperr         ; void ziperr(int, char *)
  125.         xref    _error          ; void error(char *)
  126.         xref    _calloc         ; stdlib function: void *calloc(size_t, size_t)
  127.         xref    _free           ; stdlib function: void free(void *)
  128.     IFD     DEBUG
  129.         xref    _fputc          ; stdio function: int fputc(int, FILE *)
  130.         xref    _stderr         ; pointer to FILE, which we pass to fputc
  131.     ENDC
  132.  
  133. ; our entry points:
  134.         xdef    _lm_init        ; void lm_init(int level, unsigned short *flags)
  135.         xdef    _lm_free        ; void lm_free(void)
  136.         xdef    _deflate        ; void deflate(void)  ...the big one
  137.         xdef    _fill_window    ; this line is just for debugging
  138.  
  139.  
  140. ; ============================================================================
  141. ; Here is where we have our global variables.
  142.  
  143.         section deflatevars,data
  144.  
  145. ; external global variables we reference:
  146.         xref    _verbose        ; signed int
  147.         xref    _level          ; signed int
  148.         xref    _read_buf       ; int (*read_buf)(char *, unsigned int)
  149.  
  150. ; global variables we make available:
  151.  
  152.         xdef    _window
  153.         xdef    _prev
  154.         xdef    _head
  155.         xdef    _window_size
  156.         xdef    _block_start
  157.         xdef    _strstart
  158.  
  159.     IFD     DYN_ALLOC
  160. _prev:          ds.l    1       ; pointer to calloc()'d unsigned short array
  161. _head:          ds.l    1       ; pointer to calloc()'d unsigned short array
  162. _window:        ds.l    1       ; pointer to calloc()'d unsigned char array
  163.     ELSE    ; !DYN_ALLOC
  164. _prev:          ds.w    WSIZE           ; array of unsigned short
  165. _head:          ds.w    HASH_SIZE       ; array of unsigned short
  166. _window:        ds.b    2*WSIZE         ; array of unsigned char
  167.     ENDC    ; ?DYN_ALLOC
  168. _window_size:   ds.l    1               ; unsigned long
  169. _block_start:   ds.l    1               ; unsigned long
  170. _strstart:      ds.w    INTSIZE/2       ; unsigned int
  171.  
  172. ; Now here are our private variables:
  173.  
  174.     IFD     CPUTEST
  175. is020:          ds.w    1       ; bool: CPU type is '020 or higher
  176.     ENDC
  177. ins_h:          ds.w    1       ; unsigned short
  178. sliding:        ds.w    1       ; bool: the file is read a piece at a time
  179. eofile:         ds.w    1       ; bool: we have read in the end of the file
  180. max_lazy_match: ds.w    1       ; unsigned short
  181. lookahead:      ds.w    1       ; unsigned short
  182.  
  183. ; These are NOT DECLARED AS STATIC in deflate.c, but currently could be:
  184. max_chain_len:  ds.w    1       ; unsigned short (unsigned int in deflate.c)
  185. prev_length:    ds.w    1       ; unsigned short (unsigned int in deflate.c)
  186. good_match:     ds.w    1       ; unsigned short (unsigned int in deflate.c)
  187. nice_match:     ds.w    1       ; unsigned short (signed int in deflate.c)
  188. match_start:    ds.w    1       ; unsigned short (unsigned int in deflate.c)
  189.  
  190. ; This array of struct config is a constant and could be in the code section:
  191. config_table:   dc.w    0,0,0,0         ; level 0: store uncompressed
  192.                 dc.w    4,4,8,4         ; level 1: fastest, loosest compression
  193.                 dc.w    4,5,16,8        ; level 2
  194.                 dc.w    4,6,32,32       ; level 3: highest to use deflate_fast
  195.                 dc.w    4,4,16,16       ; level 4: lowest to use lazy matches
  196.                 dc.w    8,16,32,32      ; level 5
  197.                 dc.w    8,16,128,128    ; level 6: the default level
  198.                 dc.w    8,32,128,256    ; level 7
  199.                 dc.w    32,128,258,1024 ; level 8
  200.                 dc.w    32,258,258,4096 ; level 9: maximum compression, slow
  201.  
  202.  
  203. ;;CAL_SH  MACRO                   ; macro for calling zcalloc()
  204. ;;     IFD    INT16
  205. ;;        move.w  #2,-(sp)
  206. ;;        move.w  #\1,-(sp)
  207. ;;        jsr     _zcalloc
  208. ;;        addq    #4,sp
  209. ;;     ELSE
  210. ;;        pea     2
  211. ;;        pea     \1
  212. ;;        jsr     _zcalloc
  213. ;;        addq    #8,sp
  214. ;;     ENDC
  215. ;;        ENDM
  216.  
  217. CAL_SH  MACRO                   ; Okay, we're back to using regular calloc()...
  218.         pea     2
  219.         pea     \1
  220.         jsr     _calloc
  221.         addq    #8,sp
  222.         ENDM
  223.  
  224. ; ============================================================================
  225. ; And here we begin our functions.  match_init is for internal use only:
  226.  
  227.         section deflate,code
  228.  
  229. match_init:
  230.     IFD     CPUTEST             ; now check for platform type
  231.      IFD    AMIGA               ; Amiga specific test for '020 CPU:
  232.         xref    _SysBase
  233.         NOLIST
  234.         INCLUDE       'exec/execbase.i'
  235.         LIST
  236.  
  237.         clr.w   is020                   ; default value is 68000
  238.         move.l  _SysBase,a0
  239.         btst    #AFB_68020,AttnFlags+1(a0)
  240.         beq.s   cheap
  241.         move.w  #1,is020
  242. cheap:
  243.      ELSE   ; !AMIGA
  244.  
  245.         FAIL    Write an '020-detector for your system here!
  246. ; On the Macintosh, I believe GetEnvironment() provides the information.
  247.  
  248.      ENDC   ; AMIGA
  249.     ENDC    ; CPUTEST
  250.         rts     ; match_init consists only of rts if CPUTEST unset
  251.  
  252.  
  253. ; ============================================================================
  254. ; Here is longest_match(), the function that the rest of this was built up
  255. ; from, the hottest hot spot in the program and therefore the most heavily
  256. ; optimized.  It has two different versions, one for '020 and higher CPUs, and
  257. ; one for 68000/68010.  It can test at runtime which version to use if you
  258. ; create a test function in match_init for your platform.  Currently such a
  259. ; test is implemented for the Amiga.  It can also be assembled to use '000 or
  260. ; '020 code only.
  261.  
  262. Cur_Match       equr    d0              ; unsigned int, kept valid as long
  263. Best_Len        equr    d1              ; unsigned int, kept valid as long
  264. Scan_Start      equr    d3              ; pair of bytes
  265. Scan_End        equr    d4              ; pair of bytes
  266. Limit           equr    d5              ; unsigned int
  267. Chain_Length    equr    d6              ; unsigned int
  268. Scan_Test       equr    d7              ; counter, pair of bytes sometimes
  269. Scan            equr    a0              ; pointer to unsigned char
  270. Match           equr    a1              ; pointer to unsigned char
  271. Prev_Address    equr    a2              ; pointer to unsigned short
  272. Scan_Ini        equr    a3              ; pointer to unsigned char
  273. Match_Ini       equr    a5              ; pointer to unsigned char
  274. ; Note: "pair of bytes" means the two low order bytes of the register in
  275. ; 68020 code, but means the lowest and third lowest bytes on the 68000.
  276.     IFD     AMIGA
  277. SAVEREGS        reg     d3-d7/a2/a3/a5      ; don't protect d0/d1/a0/a1
  278.     ELSE    ; !AMIGA
  279. SAVEREGS        reg     d1/d3-d7/a0-a3/a5   ; protect all except d0 return val
  280.     ENDC    ; ?AMIGA
  281. ; d2, a4, a6 not used... on Amiga, a4 is used by small-data memory model
  282.  
  283.  
  284. longest_match:
  285.         movem.l SAVEREGS,-(sp)
  286.  
  287. ; setup steps common to byte and word versions:
  288.     IFD     INT16
  289.         and.l   #$0000FFFF,Cur_Match    ; upper half must be zero!
  290. ; we use an and.l down here for the sake of ATSIGN/REGARGS.
  291.         moveq   #0,Limit                ; so adding to Scan_Ini works
  292.     ENDC
  293.         move.w  max_chain_len,Chain_Length
  294.         move.w  prev_length,Best_Len
  295.         MOVINT  _strstart,Limit
  296.         BASEPTR _prev,Prev_Address
  297.         BASEPTR _window,Match_Ini
  298.         move.l  Match_Ini,Scan_Ini
  299.         addq    #MIN_MATCH,Match_Ini    ; optimizes inner loop
  300.         add.l   Limit,Scan_Ini
  301.         sub.w   #MAX_DIST,Limit
  302.         bhi.s   limit_ok
  303.         moveq   #0,Limit
  304. limit_ok:
  305.         cmp.w   good_match,Best_Len
  306.         blo.s   length_ok
  307.         lsr.w   #2,Chain_Length
  308. length_ok:
  309.         subq.w  #1,Chain_Length
  310.  
  311.     IFD     CPUTEST
  312.         tst.w   is020                   ; can we use '020 stuff today?
  313.         bne     WORD_match
  314.     ENDC
  315.  
  316.     IFND    CPU020
  317.  
  318. ; for 68000 or 68010, use byte operations:
  319.         moveq   #0,Scan_Start           ; clear 2nd & 4th bytes, use 1st & 3rd
  320.         moveq   #0,Scan_End             ; likewise
  321.         moveq   #0,Scan_Test            ; likewise
  322.         move.b  (Scan_Ini),Scan_Start
  323.         swap    Scan_Start              ; swap is faster than 8 bit shift
  324.         move.b  1(Scan_Ini),Scan_Start
  325.         move.b  -1(Scan_Ini,Best_Len.w),Scan_End
  326.         swap    Scan_End
  327.         move.b  0(Scan_Ini,Best_Len.w),Scan_End
  328.         bra.s   bdo_scan
  329.  
  330. blong_loop:
  331.         move.b  -1(Scan_Ini,Best_Len.w),Scan_End
  332.         swap    Scan_End
  333.         move.b  0(Scan_Ini,Best_Len.w),Scan_End
  334.  
  335. bshort_loop:
  336.         add.w   Cur_Match,Cur_Match     ; assert value before doubling < 32K
  337.      IFNE   32768-WSIZE
  338.         and.w   #(WMASK*2),Cur_Match
  339.      ENDC
  340.         move.w  (Prev_Address,Cur_Match.l),Cur_Match
  341.         cmp.w   Limit,Cur_Match
  342.         dbls    Chain_Length,bdo_scan
  343.         bra     return
  344.  
  345. bdo_scan:
  346.         move.l  Match_Ini,Match
  347.         add.l   Cur_Match,Match
  348.         move.b  -MIN_MATCH-1(Match,Best_Len.w),Scan_Test
  349.         swap    Scan_Test
  350.         move.b  -MIN_MATCH(Match,Best_Len.w),Scan_Test
  351.         cmp.l   Scan_Test,Scan_End
  352.         bne.s   bshort_loop
  353.         move.b  -MIN_MATCH(Match),Scan_Test
  354.         swap    Scan_Test
  355.         move.b  -MIN_MATCH+1(Match),Scan_Test
  356.         cmp.l   Scan_Test,Scan_Start
  357.         bne.s   bshort_loop
  358.         move.w  #(MAX_MATCH-3),Scan_Test
  359.         lea     MIN_MATCH(Scan_Ini),Scan        ; offset optimizes inner loop
  360.  
  361. bscan_loop:
  362.         cmp.b   (Match)+,(Scan)+
  363.         dbne    Scan_Test,bscan_loop
  364.         subq    #1,Scan
  365.  
  366.         sub.l   Scan_Ini,Scan           ; assert difference is 16 bits
  367.         cmp.w   Best_Len,Scan
  368.         bls.s   bshort_loop
  369.         MOVINT  Scan,Best_Len
  370.         move.w  Cur_Match,match_start
  371.         cmp.w   nice_match,Best_Len
  372.         blo.s   blong_loop
  373.      IFD    CPUTEST
  374.         bra     return
  375.      ENDC
  376.  
  377.     ENDC    ; !CPU020
  378.  
  379.     IFND    CPU000
  380.         MACHINE MC68020
  381.  
  382. ; for 68020 or higher, use word operations even on odd addresses:
  383. WORD_match:
  384.         move.w  (Scan_Ini),Scan_Start
  385.         move.w  -1(Scan_Ini,Best_Len.w),Scan_End
  386.         bra.s   wdo_scan
  387.  
  388. wlong_loop:
  389.         move.w  -1(Scan_Ini,Best_Len.w),Scan_End
  390.  
  391. wshort_loop:
  392.         and.w   #WMASK,Cur_Match
  393.         move.w  (Prev_Address,Cur_Match.w*2),Cur_Match  ; '020 addressing mode
  394.         cmp.w   Limit,Cur_Match
  395.         dbls    Chain_Length,wdo_scan
  396.         bra.s   return
  397.  
  398. wdo_scan:
  399.         move.l  Match_Ini,Match
  400.         add.l   Cur_Match,Match
  401.         cmp.w   -MIN_MATCH-1(Match,Best_Len.w),Scan_End
  402.         bne.s   wshort_loop
  403.         cmp.w   -MIN_MATCH(Match),Scan_Start
  404.         bne.s   wshort_loop
  405.      IFD    QUADLONG
  406. ; By some measurements, this version of the code is a little tiny bit faster.
  407. ; But on some files it's slower.  It probably pays off only when there are
  408. ; long match strings, and costs in the most common case of three-byte matches.
  409.         moveq   #((MAX_MATCH-MIN_MATCH)/16),Scan_Test     ; value = 15
  410.         lea     MIN_MATCH(Scan_Ini),Scan        ; offset optimizes inner loop
  411.  
  412. wscan_loop:
  413.         cmp.l   (Match)+,(Scan)+                ; test four bytes at a time
  414.         bne.s   odd
  415.         cmp.l   (Match)+,(Scan)+
  416.         bne.s   odd
  417.         cmp.l   (Match)+,(Scan)+
  418.         bne.s   odd
  419.         cmp.l   (Match)+,(Scan)+
  420.         dbne    Scan_Test,wscan_loop            ; '020 can cache a bigger loop
  421. odd:
  422.         subq    #4,Scan
  423.         subq    #4,Match
  424.         cmp.b   (Match)+,(Scan)+        ; find good bytes in bad longword
  425.         bne.s   even
  426.         cmp.b   (Match)+,(Scan)+
  427.         bne.s   even
  428.         cmp.b   (Match)+,(Scan)+
  429.         beq.s   steven
  430. even:   subq    #1,Scan
  431.      ELSE   ; !QUADLONG
  432.         moveq   #((MAX_MATCH-MIN_MATCH)/2),Scan_Test    ; value = 127
  433.         lea     MIN_MATCH(Scan_Ini),Scan        ; offset optimizes inner loop
  434.  
  435. wscan_loop:
  436.         cmp.w   (Match)+,(Scan)+
  437.         dbne    Scan_Test,wscan_loop
  438.         subq    #2,Scan
  439.         move.b  -2(Match),Scan_Test
  440.         cmp.b   (Scan),Scan_Test
  441.         bne.s   steven
  442.         addq    #1,Scan
  443.      ENDC   ; ?QUADLONG
  444. steven:
  445.         sub.l   Scan_Ini,Scan           ; assert: difference is 16 bits
  446.         cmp.w   Best_Len,Scan
  447.         bls.s   wshort_loop
  448.         MOVINT  Scan,Best_Len
  449.         move.w  Cur_Match,match_start
  450.         cmp.w   nice_match,Best_Len
  451.         blo.s   wlong_loop
  452.  
  453.         MACHINE MC68000
  454.     ENDC    ; !CPU000
  455.  
  456. return:
  457.         MOVINT  Best_Len,d0         ; return value (upper half should be clear)
  458.         movem.l (sp)+,SAVEREGS
  459.         rts
  460.  
  461.  
  462. ; =============================================================================
  463. ; This is the deflate() function itself, our main entry point.  It calls
  464. ; longest_match, above, and some outside functions.  It is a hot spot, but not
  465. ; as hot as longest_match.  It uses no special '020 code.
  466.  
  467. ; ================== Several macros used in deflate() and later functions:
  468.  
  469. ; Arg 1 is D-reg that new ins_h value is to be left in,
  470. ; arg 2 is the byte value to be hashed into it, which must not be the same reg
  471. UP_HASH MACRO
  472.         move.w  ins_h,\1
  473.         asl.w   #H_SHIFT,\1
  474.         eor.b   \2,\1
  475.         and.w   #HASH_MASK,\1           ; ((ins_h << H_SHIFT) ^ c) & HASH_MASK
  476.         move.w  \1,ins_h                ; ins_h = that
  477.         ENDM
  478.  
  479. ; Arg 1 is scratch A, arg 2 is scratch D
  480. IN_STR  MACRO
  481.         move.l  Strst,\2
  482.         addq.w  #MIN_MATCH-1,\2
  483.         move.b  (Window,\2.l),\2        ; window[strstart + MIN_MATCH - 1]
  484.         UP_HASH Head,\2
  485.         add.l   Head,Head               ; assert upper word is zero before add
  486.         BASEPTR _head,\1
  487.         add.l   Head,\1
  488.         move.w  (\1),Head               ; hash_head = head[ins_h]
  489.         move.w  Strst,(\1)              ; head[ins_h] = strstart
  490.         move.l  Strst,\2
  491.     IFNE    WSIZE-32768
  492.         and.w   #WMASK,\2
  493.     ENDC
  494.         add.w   \2,\2                   ; masks implicitly when WSIZE == 32768
  495.         move.w  Head,(Prev,\2.l)        ; prev[str_start & WMASK] = hash_head
  496.         ENDM
  497.  
  498. ; Arg 1 is bool (int) EOF flag, flush_block result is in d0, trashes d1/a0/a1
  499. FLUSH_B MACRO
  500.     IFC     '\1','#0'
  501.         CLRINT  -(sp)
  502.     ELSE
  503.         MOVINT  \1,-(sp)
  504.     ENDC
  505.         move.l  _block_start,d0
  506.         blt.s   nenu\@
  507.         move.l  Window,a0
  508.         add.l   d0,a0
  509.         bra.s   nun\@
  510. nenu\@: sub.l   a0,a0           ; if block_start < 0, push NULL
  511. nun\@:  sub.l   Strst,d0
  512.         neg.l   d0
  513.         move.l  d0,-(sp)
  514.         move.l  a0,-(sp)
  515.         jsr     _flush_block
  516.         lea     8+INTSIZE(sp),sp
  517.         ENDM
  518.  
  519. ; This expands to nothing unless DEBUG is defined.
  520. ; Arg 1 is a byte to be trace-outputted -- if it is d0 it must be a valid int
  521. TRACE_C MACRO
  522.     IFD    DEBUG
  523.         cmp.w  #1,_verbose+INTSIZE-2    ; test lower word only
  524.         ble.s   qui\@
  525.      IFNC    '\1','d0'
  526.         moveq   #0,d0
  527.         move.b  \1,d0
  528.      ENDC
  529.         move.l  _stderr,-(sp)
  530.         MOVINT  d0,-(sp)
  531.         jsr     _fputc
  532.         addq    #4+INTSIZE,sp
  533. qui\@:
  534.     ENDC    ; DEBUG
  535.         ENDM
  536.  
  537. ; ================== Here are the register vars we use, and deflate() itself:
  538.  
  539. Window  equr    a2              ; cached address of window[]
  540. Prev    equr    a3              ; cached address of prev[]
  541. Strst   equr    d7              ; strstart cached as a longword
  542. Look    equr    d6              ; lookahead cached as short
  543. Head    equr    d5              ; local variable hash_head, short
  544. PrevL   equr    d4              ; prev_length cached as short
  545. MatchL  equr    d3              ; local variable match_length, unsigned short
  546. Avail   equr    d2              ; local variable available_match, bool
  547. PrevM   equr    a5              ; local variable prev_match, int in an A-reg
  548.  
  549.     IFD     AMIGA
  550. DEFREGS reg     d2-d7/a2/a3/a5
  551.     ELSE
  552. DEFREGS reg     d0-d7/a0/a2/a3/a5       ; play it safe, preserve all regs
  553.     ENDC
  554.  
  555.  
  556. _deflate:           ; first, setup steps common to deflate and deflate_fast:
  557.         movem.l DEFREGS,-(sp)
  558.     IFD     INT16
  559.         moveq   #0,Strst                ; make sure strstart is valid as a long
  560.     ENDC
  561.         moveq   #0,Head                 ; ditto for hash_head
  562.         MOVINT  _strstart,Strst
  563.         move.w  lookahead,Look
  564.         move.w  prev_length,PrevL
  565.         BASEPTR _window,Window
  566.         BASEPTR _prev,Prev
  567.         MOVINT  _level,d0
  568.         cmp.w   #3,d0
  569.         ble     deflate_fast
  570.         moveq   #MIN_MATCH-1,MatchL
  571.         moveq   #0,Avail
  572.  
  573. look_loop:
  574.         tst.w   Look
  575.         beq     last_tally
  576.         IN_STR  a0,d0
  577.         move.w  MatchL,PrevL
  578.         move.w  match_start,PrevM
  579.         move.w  #MIN_MATCH-1,MatchL
  580.  
  581.         tst.w   Head
  582.         beq.s   no_new_match
  583.         cmp.w   max_lazy_match,PrevL
  584.         bhs.s   no_new_match
  585.         move.w  Strst,d0
  586.         sub.w   Head,d0
  587.         cmp.w   #MAX_DIST,d0
  588.         bhi.s   no_new_match
  589.         move.w  PrevL,prev_length       ; longest_match reads these variables
  590.         MOVINT  Strst,_strstart
  591.         MOVINT  Head,d0                 ; parm for longest_match
  592.         bsr     longest_match           ; sets match_start
  593.         cmp.w   Look,d0                 ; does length exceed valid data?
  594.         bls.s   stml
  595.         move.w  Look,d0
  596. stml:   move.w  d0,MatchL               ; valid length of match
  597.         cmp.w   #MIN_MATCH,MatchL       ; is the match only three bytes?
  598.         bne.s   no_new_match
  599.         move.w  match_start,d0
  600.         sub.w   Strst,d0
  601.         cmp.w   #-TOO_FAR,d0
  602.         bge.s   no_new_match
  603.         moveq   #MIN_MATCH-1,MatchL     ; mark the current match as no good
  604.  
  605. no_new_match:
  606.         cmp.w   #MIN_MATCH,PrevL
  607.         blo     literal
  608.         cmp.w   MatchL,PrevL
  609.         blo     literal
  610.         ; CHECK_MATCH   Strst-1,PrevM,PrevL
  611.         MOVINT  Strst,_strstart         ; ct_tally reads this variable
  612.         move.l  PrevL,d0
  613.         subq.w  #MIN_MATCH,d0
  614.         MOVINT  d0,-(sp)
  615.         move.l  Strst,d0
  616.         sub.w   PrevM,d0
  617.         subq.w  #1,d0
  618.         MOVINT  d0,-(sp)
  619.         jsr     _ct_tally               ; sets d0 true if we have to flush
  620.         addq    #2*INTSIZE,sp
  621.         subq.w  #3,PrevL                ; convert for dbra (prev_length - 2)
  622.         sub.w   PrevL,Look
  623.         subq.w  #2,Look
  624. insertmatch:
  625.         addq.w  #1,Strst
  626.         IN_STR  a0,d1                   ; don't clobber d0
  627.         dbra    PrevL,insertmatch
  628.         moveq   #0,Avail
  629.         moveq   #0,PrevL                ; not needed?
  630.         moveq   #MIN_MATCH-1,MatchL
  631.         addq.w  #1,Strst
  632.         tst.w   d0
  633.         beq     refill
  634.         FLUSH_B #0
  635.         move.l  Strst,_block_start
  636.         bra.s   refill
  637.  
  638. literal:
  639.         tst.w   Avail
  640.         bne.s   yeslit
  641.         moveq   #1,Avail
  642.         bra.s   skipliteral
  643. yeslit: TRACE_C <-1(Window,Strst.l)>
  644.         MOVINT  Strst,_strstart         ; ct_tally reads this variable
  645.         moveq   #0,d0
  646.         move.b  -1(Window,Strst.l),d0
  647.         MOVINT  d0,-(sp)
  648.         CLRINT  -(sp)
  649.         jsr     _ct_tally
  650.         addq    #2*INTSIZE,sp
  651.         tst.w   d0
  652.         beq.s   skipliteral
  653.         FLUSH_B #0
  654.         move.l  Strst,_block_start
  655. skipliteral:
  656.         addq.w  #1,Strst
  657.         subq.w  #1,Look
  658.  
  659. refill:
  660.         cmp.w   #MIN_LOOKAHEAD,Look
  661.         bhs     look_loop
  662.         bsr     fill_window
  663.         bra     look_loop
  664.  
  665. last_tally:
  666.         tst.w   Avail
  667.         beq     last_flush
  668.         MOVINT  Strst,_strstart         ; ct_tally reads this variable
  669.         moveq   #0,d0
  670.         move.b  -1(Window,Strst.l),d0
  671.         MOVINT  d0,-(sp)
  672.         CLRINT  -(sp)
  673.         jsr     _ct_tally
  674.         addq    #2*INTSIZE,sp
  675. last_flush:
  676.         FLUSH_B #1
  677.         bra     deflate_exit
  678.  
  679. ; ================== This is another version used for low compression levels:
  680.  
  681. deflate_fast:
  682.         moveq   #0,MatchL
  683.         moveq   #MIN_MATCH-1,PrevL
  684. flook_loop:
  685.         tst.w   Look
  686.         beq     flast_flush
  687.  
  688.         IN_STR  a0,d0
  689.         tst.w   Head
  690.         beq.s   fno_new_match
  691.         move.w  Strst,d0
  692.         sub.w   Head,d0
  693.         cmp.w   #MAX_DIST,d0
  694.         bhi.s   fno_new_match
  695.         move.w  PrevL,prev_length       ; longest_match reads these variables
  696.         MOVINT  Strst,_strstart
  697.         MOVINT  Head,d0                 ; parm for longest_match
  698.         bsr     longest_match           ; sets match_start
  699.         cmp.w   Look,d0                 ; does length exceed valid data?
  700.         bls.s   fstml
  701.         move.w  Look,d0
  702. fstml:  move.w  d0,MatchL               ; valid length of match
  703.  
  704. fno_new_match:
  705.         cmp.w   #MIN_MATCH,MatchL
  706.         blo     fliteral
  707.         ; CHECK_MATCH   Strst,match_start,MatchL
  708.         MOVINT  Strst,_strstart         ; ct_tally reads this variable
  709.         move.l  MatchL,d0
  710.         subq.w  #MIN_MATCH,d0
  711.         MOVINT  d0,-(sp)
  712.         move.l  Strst,d0
  713.         sub.w   match_start,d0
  714.         MOVINT  d0,-(sp)
  715.         jsr     _ct_tally               ; sets d0 true if we have to flush
  716.         addq    #2*INTSIZE,sp
  717.         sub.w   MatchL,Look
  718.         cmp.w   max_lazy_match,MatchL
  719.         bhi     ftoolong
  720.         subq.w  #2,MatchL
  721. finsertmatch:
  722.         addq.w  #1,Strst
  723.         IN_STR  a0,d1                   ; preserve d0
  724.         dbra    MatchL,finsertmatch
  725.         moveq   #0,MatchL               ; not needed?
  726.         addq.w  #1,Strst
  727.         bra.s   flushfill
  728.  
  729. ftoolong:
  730.         add.w   MatchL,Strst
  731.         moveq   #0,MatchL
  732.         moveq   #0,d1                   ; preserve d0
  733.         move.b  (Window,Strst.l),d1
  734.         move.w  d1,ins_h
  735. ; My assembler objects to passing <1(Window,Strst.l)> directly to UP_HASH...
  736.         move.b  1(Window,Strst.l),Avail ; Avail is not used in deflate_fast
  737.         UP_HASH d1,Avail                ; preserve d0
  738.     IFNE    MIN_MATCH-3
  739.         FAIL  needs to UP_HASH another MIN_MATCH-3 times, but with what arg?
  740.     ENDC
  741.         bra.s   flushfill
  742.  
  743. fliteral:
  744.         TRACE_C <(Window,Strst.l)>
  745.         MOVINT  Strst,_strstart         ; ct_tally reads this variable
  746.         moveq   #0,d0
  747.         move.b  (Window,Strst.l),d0
  748.         MOVINT  d0,-(sp)
  749.         CLRINT  -(sp)
  750.         jsr     _ct_tally               ; d0 set if we need to flush
  751.         addq    #2*INTSIZE,sp
  752.         addq.w  #1,Strst
  753.         subq.w  #1,Look
  754.  
  755. flushfill:
  756.         tst.w   d0
  757.         beq.s   frefill
  758.         FLUSH_B #0
  759.         move.l  Strst,_block_start
  760. frefill:
  761.         cmp.w   #MIN_LOOKAHEAD,Look
  762.         bhs     flook_loop
  763.         bsr     fill_window
  764.         bra     flook_loop
  765.  
  766. flast_flush:
  767.         FLUSH_B #1                      ; sets our return value
  768.  
  769. deflate_exit:
  770.         MOVINT  Strst,_strstart         ; save back cached values
  771.         move.w  PrevL,prev_length
  772.         move.w  Look,lookahead
  773.         movem.l (sp)+,DEFREGS
  774.         rts
  775.  
  776.  
  777. ; =========================================================================
  778. ; void fill_window(void) calls the input function to refill the sliding
  779. ; window that we use to find substring matches in.
  780.  
  781. More    equr    Head                    ; local variable in fill_window
  782. WindTop equr    Prev                    ; local variable used for sliding
  783. SlidIx  equr    PrevL                   ; local variable used for sliding
  784.  
  785.     IFD     AMIGA
  786. FWREGS  reg     d2-d5/a2-a6             ; does NOT include Look and Strst
  787.     ELSE
  788. FWREGS  reg     d1-d5/a0-a6             ; likewise
  789.     ENDC
  790. ; all registers available to be clobbered by the sliding operation:
  791. ; we exclude More, WindTop, SlidIx, Look, Strst, Window, a4 and a7.
  792. SPAREGS reg     d0-d3/a0-a1/a5-a6
  793. SPCOUNT equ     8                       ; number of registers in SPAREGS
  794.  
  795.  
  796. _fill_window:                           ; C-callable entry point
  797.         movem.l Strst/Look,-(sp)
  798.     IFD     INT16
  799.         moveq   #0,Strst                ; Strst must be valid as a long
  800.     ENDC
  801.         MOVINT  _strstart,Strst
  802.         move.w  lookahead,Look
  803.         BASEPTR _window,Window
  804.         bsr.s   fill_window
  805.         MOVINT  Strst,_strstart
  806.         move.w  Look,lookahead
  807.         movem.l (sp)+,Strst/Look
  808.         rts
  809.  
  810. ; strstart, lookahead, and window must be cached in Strst, Look, and Window:
  811. fill_window:                            ; asm-callable entry point
  812.         movem.l FWREGS,-(sp)
  813.         tst.w   eofile                  ; we put this up here for speed
  814.         bne     fwdone
  815.         and.l   #$FFFF,Look             ; make sure Look is valid as long
  816. fw_refill:
  817.         move.l  _window_size,More       ; <= 64K
  818.         sub.l   Look,More
  819.         sub.l   Strst,More              ; Strst is already valid as long
  820.         cmp.w   #EOF,More
  821.         bne.s   notboundary
  822.         subq.w  #1,More
  823.         bra     checkend
  824.  
  825. notboundary:
  826.         tst.w   sliding
  827.         beq     checkend
  828.         cmp.w   #WSIZE+MAX_DIST,Strst
  829.         blo     checkend
  830.     IFGT    32768-WSIZE
  831.         lea     WSIZE(Window),WindTop   ; WindTop is aligned when Window is
  832.     ELSE
  833.         move.l  Window,WindTop
  834.         add.l   #WSIZE,WindTop
  835.     ENDC
  836.         move.l  Window,d0
  837.         and.w   #3,d0
  838.         beq.s   isaligned
  839.         subq.w  #1,d0
  840. align:  move.b  (WindTop)+,(Window)+    ; copy up to a longword boundary
  841.         dbra    d0,align
  842. isaligned:
  843. ; This is faster than a simple move.l (WindTop)+,(Window)+ / dbra loop:
  844.         move.w  #(WSIZE-1)/(4*SPCOUNT),SlidIx
  845. slide:  movem.l (WindTop)+,SPAREGS      ; copy, 32 bytes at a time!
  846.         movem.l SPAREGS,(Window)        ; a slight overshoot doesn't matter.
  847.         lea     4*SPCOUNT(Window),Window        ; can't use (aN)+ as movem.l dest
  848.         dbra    SlidIx,slide
  849.         BASEPTR _window,Window                  ; restore cached value
  850.         sub.w   #WSIZE,match_start
  851.         sub.w   #WSIZE,Strst
  852.         sub.l   #WSIZE,_block_start
  853.         add.w   #WSIZE,More
  854.         BASEPTR _head,a0
  855.         move.w  #HASH_SIZE-1,d0
  856. fixhead:
  857.         move.w  (a0),d1
  858.         sub.w   #WSIZE,d1
  859.         bpl.s   headok
  860.         moveq   #0,d1
  861. headok: move.w  d1,(a0)+
  862.         dbra    d0,fixhead
  863.         BASEPTR _prev,a0
  864.         move.w  #WSIZE-1,d0
  865. fixprev:
  866.         move.w  (a0),d1
  867.         sub.w   #WSIZE,d1
  868.         bpl.s   prevok
  869.         moveq   #0,d1
  870. prevok: move.w  d1,(a0)+
  871.         dbra    d0,fixprev
  872.         TRACE_C #'.'
  873.  
  874. checkend:                               ; assert eofile is false
  875.         MOVINT  More,-(sp)              ; assert More's upper word is zero
  876.         move.l  Strst,d0
  877.         add.w   Look,d0
  878.         add.l   Window,d0
  879.         move.l  d0,-(sp)
  880.         move.l  _read_buf,a0
  881.         jsr     (a0)                    ; refill the upper part of the window
  882.         addq    #4+INTSIZE,sp
  883.         tst.w   d0
  884.         beq.s   iseof
  885.         cmp.w   #EOF,d0
  886.         beq.s   iseof
  887.         add.w   d0,Look
  888.         cmp.w   #MIN_LOOKAHEAD,Look
  889.         blo     fw_refill               ; eofile is still false
  890.  
  891.         bra.s   fwdone
  892. iseof:  move.w  #1,eofile
  893. fwdone: movem.l (sp)+,FWREGS
  894.         rts
  895.  
  896.  
  897. ; =========================================================================
  898. ; void lm_free(void) frees dynamic arrays in the DYN_ALLOC version.
  899.  
  900.         xdef    _lm_free                ; the entry point
  901.  
  902. _lm_free:
  903.     IFD     DYN_ALLOC
  904.         move.l  _window,d0
  905.         beq.s   lf_no_window
  906.         move.l  d0,-(sp)
  907.         jsr     _free
  908.         addq    #4,sp
  909.         clr.l   _window
  910. lf_no_window:
  911.         move.l  _prev,d0
  912.         beq.s   lf_no_prev
  913.         move.l  d0,-(sp)
  914.         jsr     _free
  915.         move.l  _head,(sp)              ; reuse the same stack arg slot
  916.         jsr     _free
  917.         addq    #4,sp
  918.         clr.l   _prev
  919.         clr.l   _head
  920. lf_no_prev:
  921.     ENDC
  922.         rts
  923.  
  924. ; ============================================================================
  925. ; void lm_init(int pack_level, unsigned short *flags) allocates dynamic arrays
  926. ; if any, and initializes all variables so that deflate() is ready to go.
  927.  
  928.         xdef    _lm_init                ; the entry point
  929.  
  930. Level   equr    d2
  931. ;Window equr    a2      ; as in deflate()
  932.     IFD     AMIGA
  933. INIREGS reg     d2/a2
  934.     ELSE
  935. INIREGS reg     d0-d2/a0-a1
  936.     ENDC
  937.  
  938. _lm_init:
  939.         MOVINT  4(sp),d0
  940.         move.l  4+INTSIZE(sp),a0
  941.         movem.l INIREGS,-(sp)
  942.         move.w  d0,Level
  943.         cmp.w   #1,Level
  944.         blt.s   levelerr
  945.         bgt.s   try9
  946.         bset.b  #B_FAST,1(a0)
  947. try9:   cmp.w   #9,Level
  948.         bgt.s   levelerr
  949.         blt.s   levelok
  950.         bset.b  #B_SLOW,1(a0)
  951.         bra.s   levelok
  952. levelerr:
  953.         pea     level_message
  954.         jsr     _error                  ; never returns
  955. levelok:
  956.         clr.w   sliding
  957.         tst.l   _window_size
  958.         bne.s   gotawindowsize
  959.         move.w  #1,sliding
  960.         move.l  #2*WSIZE,_window_size
  961. gotawindowsize:
  962.  
  963.         BASEPTR _window,Window
  964.     IFD     DYN_ALLOC
  965.         move.l  Window,d0               ; fake tst.l
  966.         bne.s   gotsomewind
  967.         CAL_SH  WSIZE
  968.         move.l  d0,Window
  969.         move.l  d0,_window
  970.         bne.s   gotsomewind
  971.         pea     window_message
  972.         MOVINT  #ZE_MEM,-(sp)
  973.         jsr     _ziperr                 ; never returns
  974. gotsomewind:
  975.         tst.l   _prev
  976.         bne.s   gotsomehead
  977.         CAL_SH  WSIZE
  978.         move.l  d0,_prev
  979.         beq.s   nohead
  980.         CAL_SH  HASH_SIZE
  981.         move.l  d0,_head
  982.         bne.s   gotfreshhead            ; newly calloc'd memory is zeroed
  983. nohead: pea     hash_message
  984.         MOVINT  #ZE_MEM,-(sp)
  985.         jsr     _ziperr                 ; never returns
  986. gotsomehead:
  987.     ENDC    ; DYN_ALLOC
  988.  
  989.         move.w  #(HASH_SIZE/2)-1,d0     ; two shortwords per loop
  990.         BASEPTR _head,a0
  991. wipeh:  clr.l   (a0)+
  992.         dbra    d0,wipeh
  993. gotfreshhead:
  994.         move.l  Level,d0
  995.     IFEQ    Sizeof_config-8
  996.         asl.l   #3,d0
  997.     ELSE
  998.         mulu    #Sizeof_config,d0
  999.     ENDC
  1000.         lea     config_table,a0
  1001.         add.l   d0,a0
  1002.         move.w  Max_lazy(a0),max_lazy_match
  1003.         move.w  Good_length(a0),good_match
  1004.         move.w  Nice_length(a0),nice_match
  1005.         move.w  Max_chain(a0),max_chain_len
  1006.         CLRINT  _strstart
  1007.         clr.l   _block_start
  1008.         bsr     match_init
  1009.  
  1010.         clr.w   eofile
  1011.         MOVINT  #WSIZE,-(sp)    ; We read only 32K because lookahead is short
  1012.         move.l  Window,-(sp)    ; even when int size is long, as if deflate.c
  1013.         move.l  _read_buf,a0    ; were compiled with MAXSEG_64K defined.
  1014.         jsr     (a0)
  1015.         addq    #4+INTSIZE,sp
  1016.         move.w  d0,lookahead
  1017.         beq.s   noread
  1018.         cmp.w   #EOF,d0
  1019.         bne.s   irefill
  1020. noread: move.w  #1,eofile
  1021.         clr.w   lookahead
  1022.         bra.s   init_done
  1023.  
  1024. irefill:
  1025.         move.w  lookahead,d0
  1026.         cmp.w   #MIN_LOOKAHEAD,d0
  1027.         bhs.s   hashify
  1028.         bsr     _fill_window            ; use the C-callable version
  1029. hashify:
  1030.         clr.w   ins_h
  1031.         moveq   #MIN_MATCH-2,d0
  1032. hash1:  move.b  (Window)+,d1
  1033.         UP_HASH Level,d1
  1034.         dbra    d0,hash1
  1035.  
  1036. init_done:
  1037.         movem.l (sp)+,INIREGS
  1038.         rts
  1039.  
  1040. ; strings for error messages:
  1041. hash_message    dc.b    'hash table allocation',0
  1042. window_message  dc.b    'window allocation',0
  1043. level_message   dc.b    'bad pack level',0
  1044.  
  1045.         end
  1046.