Debian Codegraph @

amiga/deflate.a

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