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