home *** CD-ROM | disk | FTP | other *** search
/ Amiga MA Magazine 1998 #6 / amigamamagazinepolishissue1998.iso / packery / xpk_source / libraries / fast / compress.a next >
Text File  |  1996-10-19  |  10KB  |  343 lines
  1. ;;;                Remarks
  2. ;;;                =======
  3. ;;;
  4. ;;;   * This code relies on XPK_MARGIN being >= 32 !!!
  5. ;;;     If only one Bit in the last ControlWord is used, the remaining 15
  6. ;;;     will be filled with 0.  This will result in 15 LiteralItems on
  7. ;;;     decompression.  Additionaly there is NO CHECK, whether a match
  8. ;;;     matches more than the input.  This can result in a match which is
  9. ;;;     17 Bytes to long giving a maximum total of 32 Bytes garbled after
  10. ;;;     the outputblock after decompresion.
  11. ;;;       (XPK_MARGIN is 256 in xpkmaster.library V2.0)
  12.  
  13.     XDEF    compress_fast
  14.  
  15. ;On entry:
  16. ;    a0 = InBuf
  17. ;    a1 = OutBuf
  18. ;    a2 = HashTab
  19. ;    d0 = InLen
  20.  
  21. ;We only test if we have compressed all the input after we already have
  22. ;compressed all the data belonging to a group.  A group is the data encoded
  23. ;using one controlword.  Therefor it could happen, that we compress 16*18
  24. ;bytes to much, garbling inocent memory on decompression and compressing 
  25. ;too much data.  To prevent this (doing too much work is always a bad thing(tm))
  26. ;we compress the data with two different abortion strategies:
  27. ;1st we only test for completion after compressing all the data belonging
  28. ;to one group.  This test fails, if there are fewer than a safetymargin bytes
  29. ;to compress.  We then switch to the second safer but slower method
  30. ;of testing after each controlbit.
  31.  
  32. SAFETYMARGIN = 16*18
  33.  
  34. compress_fast:
  35.     movem.l    a3-a6/d1-d7,-(sp)
  36.     move.l    a1,-(sp)    ;push OutBuf for total length calculation
  37.     move.l    d0,d5        ;d5:=InLen
  38.  
  39.                 ;Fill the Hash with pointers to the end
  40.                 ;of the input.  So we never ever get a
  41.                 ;valid Hashentry by chance, but only
  42.                 ;if we stored it there.
  43.  
  44.     move.l    a1,d7
  45.     add.l    d0,d7        ;d7:=OutBuf+InLen
  46.     and.b    #$fc,d7        ;align d7 to long (for wordstreammove at end)
  47.     move.l    d7,a4        ;a4:=OutBuf+InLen
  48.     add.l    a0,d5        ;d5:=InBuf+InLen
  49.  
  50.     move.l    a2,a6        ;a6:=Hash
  51.     move.w    #2048-1,d0    ;Hashsize=2^(11+3+2) = 2^16 Bytes
  52. fillHashLoop:
  53.     move.l    d5,(a6)+
  54.     move.l    d5,(a6)+
  55.     move.l    d5,(a6)+
  56.     move.l    d5,(a6)+
  57.     move.l    d5,(a6)+
  58.     move.l    d5,(a6)+
  59.     move.l    d5,(a6)+
  60.     move.l    d5,(a6)+
  61.     dbra    d0,fillHashLoop
  62.  
  63.     sub.l    #SAFETYMARGIN,d5 ;d5:=InBuf+InLen-SAFETYMARGIN
  64.  
  65.     lea    NewControlWord(pc),a3
  66.     move.l    #4095,d4    ;d4:=Const:4095
  67.     moveq.l    #0,d1        ;upper word has to be 0
  68.  
  69.     bra.s    StartMainLoop
  70.  
  71.                 ;REGISTER MAP
  72.                 ;============
  73.  
  74. ;    a0 Points to the next input  byte.
  75. ;    a1 Points to the next literal output byte.
  76. ;    a2 Points to the hash table.
  77. ;    a3 Pointer to NewControlWord/SafeControl code.
  78. ;    a4 Points to the word output stream.
  79. ;    a5 Points to place to put control word in output.
  80. ;    a6 Temporary.
  81. ;    a7 Stack pointer. Don't touch!
  82.  
  83. ;    d0 Temporary
  84. ;    d1 Temporary
  85. ;    d2 Counter of Controlbits to insert into the control word.
  86. ;    d3 Buffers the current control word.
  87. ;    d4 Constant 4095 for rangecheck.
  88. ;    d5 Points to the byte after the input block.
  89. ;    d6 Second level controlbit counter used in the safe loop.
  90. ;    d7 Points to the byte after the output block.
  91.  
  92. ;;;---------------------------------------------------------------------------
  93.  
  94. COPYN    MACRO
  95.     IFGE    \1-10
  96.     addq.w    #18-\1,d0
  97.     ENDC
  98.     IFLT    \1-10
  99.     add.w    #18-\1,d0
  100.     ENDC
  101.     dbra    d2,MatchFinish    ;End of loop.
  102.     jmp    MatchExitOfs(a3); control word is full.
  103.     ENDM
  104.  
  105. ;=====================================================================
  106.  
  107.                 ;SAFE COMPRESSION LOOP
  108.                 ;=====================
  109. ;This loopcontrol part fools the main compression part into thinking
  110. ;The control word is allways full.  The main part thus calls us each
  111. ;time it has filled a bit into the control word.  This enables us to
  112. ;check for completion and overrun after each compressed item.
  113.  
  114. ;There's no need to check for overruns!
  115. ;An overrun occurs if the TOTAL size of the literal bytes and
  116. ;the control words and the copyinfo TOGETHER do exceed the size
  117. ;of the input.  Even in the worst case the literal byte stream or
  118. ;the control words and the copyinfo together do not exceed
  119. ;the size of the outbuf.  Therefore the overruncheck can safely be
  120. ;postponed to the end.
  121.                 
  122. EnterSafeLoop:
  123.     lea    SafeControl(pc),a3    ;redirect jumps to NewControlWord.
  124.     add.l    #SAFETYMARGIN,d5    ;d5:=InBuf+InLen
  125.     bra.s    StartSafeMainLoop    
  126.  
  127. ;===============================
  128.  
  129.     subq.l    #1,a0        ; = These two instructions have to be identical
  130.     move.w    d0,-(a4)    ; = to the two before NewControlWord!!!
  131. SafeControl:            ;Jump here every iteration to test for end.
  132.  
  133.     cmp.l    a0,d5            ;Input bytes left=d5-a0
  134.     bls    end_compress_loop    ;Loop ends if no more input bytes.
  135.  
  136.     dbra    d6,NextRound    ;control word isn't full, do next.
  137.  
  138.     move.w    d3,(a5)        ;Write control word.
  139. StartSafeMainLoop:
  140.     subq.l    #2,a4
  141.     move.l    a4,a5        ;Next output word is control word.
  142.  
  143.     moveq    #15,d6        ;Reinitialize control bits counter
  144.     moveq    #-1,d3        ;Fill new control word with $ffff
  145. NextRound:
  146.     moveq    #0,d2        ;Clear control bit counter to fool
  147.                 ;the others into thinking it is full
  148.                 ;so we get called 
  149.     bra.s    CompressLoop
  150.  
  151. ;===================================================================
  152.  
  153.                 ;FAST COMPRESSION LOOP
  154.                 ;=====================
  155.  
  156. MatchExit:            ;undo the effect on a0 of the last
  157.     subq.l    #1,a0        ;failing cmp.b (a6)+,(a0)+
  158. MatchExit_18:            
  159.     move.w    d0,-(a4)    ;Write the CopyItemInformation
  160.  
  161. NewControlWord:    ;Jump here every 16 iterations to set up a new control word.
  162.  
  163. MatchExitOfs    = MatchExit-NewControlWord
  164. MatchExit18Ofs    = MatchExit_18-NewControlWord
  165.  
  166.     move.w    d3,(a5)        ;Write control word.
  167. StartMainLoop:
  168.     cmp.l    a0,d5        ;reached the safetymargin ?
  169.     bls.s    EnterSafeLoop    ;Fast Loop ends if to few input bytes.
  170.     subq.l    #2,a4
  171.     move.l    a4,a5        ;Next output word is control word.
  172.     moveq    #15,d2        ;Reinitialize control bits counter
  173.     moveq    #-1,d3        ;Fill new control word with $ffff
  174.     bra.s    CompressLoop
  175.  
  176. ;=====================================================================
  177. ;placed here to be within bra.s range, could be anywhere
  178.  
  179. do_literal_1:
  180.     move.b    -1(a0),(a1)+    ;Copy the literal byte to the output.
  181.     add.w    d3,d3        ;Inject a 0 (literal) into control buffer.
  182.     dbra    d2,CompressLoop    ;End of loop.
  183.     jmp    (a3)        ; control word is full.
  184.  
  185. do_literal_2:
  186.     subq.l    #2,a0
  187.     move.b    (a0)+,(a1)+    ;Copy the literal byte to the output.
  188.     add.w    d3,d3        ;Inject a 0 (literal) into control buffer.
  189.     dbra    d2,CompressLoop    ;End of loop.
  190.     jmp    (a3)        ; control word is full.
  191.  
  192. do_literal_3:
  193.     subq.l    #3,a0
  194. do_literal:
  195.     move.b    (a0)+,(a1)+    ;Copy the literal byte to the output.
  196.     add.w    d3,d3        ;Inject a 0 (literal) into control buffer.
  197.     dbra    d2,CompressLoop    ;End of loop.
  198.     jmp    (a3)        ; control word is full.
  199.  
  200. do_copy_3:  COPYN 3
  201. do_copy_4:  COPYN 4
  202. do_copy_5:  COPYN 5
  203. ;=====================================================================
  204.  
  205. MatchFinish:
  206.     subq.l    #1,a0        ;Undo effect of last cmp.b (a6)+,(a0)+
  207. MatchFinish_18:
  208.     move.w    d0,-(a4)    ;Write the CopyItemInformation
  209. ;-----------------------------------------
  210. ;CALCULATE HASH TABLE ENTRY FOR KEY IN ZIV
  211. ;-----------------------------------------
  212. CompressLoop:
  213.     move.l    a0,a6        ;d1:=hashtable entry for
  214.     move.b    (a6)+,d1    ;(a0), 1(a0) and 2(a0)
  215.     lsl.w    #3,d1
  216.     add.b    (a6)+,d1
  217.     lsl.w    #3,d1
  218.     add.b    (a6),d1
  219.     lsl.w    #2,d1
  220.  
  221.     move.l    0(a2,d1.l),a6    ;Place the hash table entry into a6.
  222.     move.l    a0,d0        ;Calculate the entry's offset from src pos.
  223.     sub.l    a6,d0        ;d0 := a0-entry
  224.     move.l    a0,0(a2,d1.l)    ;Replace hash entry by current source address
  225.     cmp.l    d4,d0        ;Is the Hashentry more than 4095 Bytes away?
  226.     bhi.s    do_literal
  227.  
  228. COMPARE_BYTE    MACRO
  229.     cmp.b    (a6)+,(a0)+
  230.     bne.s    \1
  231.     ENDM
  232.  
  233.     COMPARE_BYTE    do_literal_1    ;Look if there is a match of at least
  234.     COMPARE_BYTE    do_literal_2    ;length 3.
  235.     COMPARE_BYTE    do_literal_3
  236.  
  237.     asl.w    #4,d0        ;Shift Offset to make room for lengthinfo
  238.     rol.w    #1,d3        ;Inject a 1 (copy) into control buffer.
  239.                 ;since we definitely are doing a copy.
  240.  
  241.     COMPARE_BYTE    do_copy_3    ;determine the length of the match
  242.     COMPARE_BYTE    do_copy_4
  243.     COMPARE_BYTE    do_copy_5
  244.     COMPARE_BYTE    do_copy_6
  245.     COMPARE_BYTE    do_copy_7
  246.     COMPARE_BYTE    do_copy_8
  247.     COMPARE_BYTE    do_copy_9
  248.     COMPARE_BYTE    do_copy_10
  249.     COMPARE_BYTE    do_copy_11
  250.     COMPARE_BYTE    do_copy_12
  251.     COMPARE_BYTE    do_copy_13
  252.     COMPARE_BYTE    do_copy_14
  253.     COMPARE_BYTE    do_copy_15
  254.     COMPARE_BYTE    do_copy_16
  255.     COMPARE_BYTE    do_copy_17
  256.  
  257. do_copy_18:                ;Match length is 18 Bytes.
  258.     dbra    d2,MatchFinish_18    ;End of loop.
  259.     jmp    MatchExit18Ofs(a3)    ;control word is full.
  260.  
  261. do_copy_6:  COPYN 6
  262. do_copy_7:  COPYN 7
  263. do_copy_8:  COPYN 8
  264. do_copy_9:  COPYN 9
  265. do_copy_10: COPYN 10
  266. do_copy_11: COPYN 11
  267. do_copy_12: COPYN 12
  268. do_copy_13: COPYN 13
  269. do_copy_14: COPYN 14
  270. do_copy_15: COPYN 15
  271. do_copy_16: COPYN 16
  272. do_copy_17: COPYN 17
  273.  
  274. ;;;The main loop ends here.
  275. ;;;---------------------------------------------------------------------------
  276.                 ;FINALIZATION
  277.                 ;============
  278.  
  279. end_compress_loop:        ;Fill the rest of the control word
  280.     lsl.w    d6,d3        ;with 0. [0 means literal items]
  281.     move.w    d3,(a5)        ;Write it to its output position
  282.  
  283.     ;Copy the wordstream after the literals pointed to by a1.
  284.     move.l    a4,d0        ;d0:=Number of Bytes to increase a1
  285.     sub.l    a1,d0        ;till a1 and a4 are equally aligned.
  286.     bcs.s    overrun        ;byte- and wordstream together exceede the
  287.                 ;size of the output buffer.
  288.     moveq    #3,d1
  289.     and.w    d0,d1
  290.  
  291.     moveq.l    #0,d0        ;pad a1 up to make a1 and a4 equally aligned.
  292.     bra.s    EFLoop
  293. FLoop:    move.b    d0,(a1)+
  294. EFLoop:    dbra    d1,FLoop
  295.  
  296.     sub.l    a4,d7        ;d7:=size of wordstream
  297.  
  298.     lsr.l    #2,d7
  299.     bcc.s    NoWord
  300.     move.w    (a4)+,(a1)+
  301. NoWord:    lsr.l    #1,d7
  302.     bcc.s    NoLong
  303.     move.l    (a4)+,(a1)+
  304. NoLong:    lsr.l    #1,d7
  305.     bcc.s    NoQuad
  306.     move.l    (a4)+,(a1)+
  307.     move.l    (a4)+,(a1)+
  308. NoQuad:    lsr.l    #1,d7
  309.     bcc.s    ECLoop
  310.     bra.s    MCLoop
  311.  
  312. CLoopH:    swap    d7
  313. CLoop:    move.l    (a4)+,(a1)+
  314.     move.l    (a4)+,(a1)+
  315.     move.l    (a4)+,(a1)+
  316.     move.l    (a4)+,(a1)+
  317. MCLoop:    move.l    (a4)+,(a1)+
  318.     move.l    (a4)+,(a1)+
  319.     move.l    (a4)+,(a1)+
  320.     move.l    (a4)+,(a1)+
  321. ECLoop:    dbra    d7,CLoop
  322.     swap    d7
  323.     dbra    d7,CLoopH
  324.  
  325.     move.l    (sp)+,a0        ;Pop OutBuf
  326.     move.l    a1,d0
  327.     sub.l    a0,d0            ;d0:=Final output length
  328. endcompress:
  329.     movem.l    (sp)+,a3-a6/d1-d7
  330.     rts
  331.  
  332.                 ;OVERRUN PROCESSING
  333.                 ;==================
  334.     ;This is the place to jump when an overrun occurs.
  335.     ;When an overrun occurs we can drop everything we are doing
  336. overrun:
  337.     moveq.l    #0,d0
  338.     addq.l    #4,sp        ;pop OutBuf.
  339.     bra.s    endcompress
  340. ;;;---------------------------------------------------------------------------
  341.  
  342.     END
  343.