home *** CD-ROM | disk | FTP | other *** search
/ telefisk.org / virusCollection.lzx / VirusResearch / Cjezus-virus / CE_JESUS.LHA / compressor.asm < prev    next >
Assembly Source File  |  1995-09-11  |  10KB  |  360 lines

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