home *** CD-ROM | disk | FTP | other *** search
/ Dream 57 / Amiga_Dream_57.iso / Amiga / Programmation / c / QuakeC / qtools0.2-src.lha / src / libqsys / m68k / LZW5b.S < prev    next >
Encoding:
Text File  |  1998-07-08  |  23.0 KB  |  1,022 lines
  1. /* #include "LZW5b.h" */
  2. #define    IDENTIFIER        0x4C5A    /* 'LZ' */
  3.  
  4. #define    NOERROR            1
  5. #define    ERROR            0
  6. #define    ERROR_NOTCRUNCHED    -1
  7. #define    ERROR_LESSMEM        -2
  8. #define    ERROR_OVERFLOW        -3
  9.  
  10.  
  11.  
  12.  
  13.     |MACHINE    MC68030
  14.  
  15.  
  16.     |INCLUDE    Macros.i
  17. |ComFast    MACRO
  18. |    jsr    _LVO\1(a6)
  19. |    ENDM
  20.     .macro    ComFast    lvo
  21.     jsr    a6@(\lvo)
  22.     .endm
  23. |ComExec    MACRO
  24. |    move.l    4.w,a6
  25. |    ComFast    \1
  26. |    ENDM
  27.     .macro    ComExec func
  28.     movel    4.w,a6
  29.     ComFast    \func
  30.     .endm
  31.     
  32.     |INCLUDE    exec/memory.i
  33.     |INCLUDE    xpk/xpk.i
  34.     
  35.     |INCLUDE    LVOs/exec.i
  36.     .equ    _LVOCreatePool,-696
  37.     .equ    _LVODeletePool,-702
  38.     .equ    _LVOAllocPooled,-708
  39.     .equ    _LVOFreePooled,-714
  40.  
  41.     .equ    OFFSET_SIZE,16
  42.     .equ    OFFSET_MASK,0b01111111111111111
  43.     .equ    LENGTH_SIZE,8
  44.     .equ    LENGTH_MASK,0b011111111
  45.     .equ    COMP_SIZE,((OFFSET_SIZE+7)/8)+((LENGTH_SIZE+7)/8)    | size of OFFSET+LENGTH in bytes
  46.  
  47.     .equ    INDEX_LENGTH,4                    | in Bytes
  48.     .equ    INDEX_SIZE,(INDEX_LENGTH*8)/2            | in Bits
  49.  
  50.     .equ    MAX_HISTORY,(1<<OFFSET_SIZE)-1            | in Bytes
  51.     .equ    MIN_LENGTH,COMP_SIZE                | one greater than compressed data
  52.     .equ    MAX_LENGTH,(1<<LENGTH_SIZE)+MIN_LENGTH-1    | in Bytes
  53.  
  54.     .equ    HistoryEntries,1000
  55.     .equ    ArraySizeCount,4
  56.  
  57.     | a0 = input
  58.     | a1 = output
  59.     | d0 = inbuflen
  60.     | d1 = outbuflen
  61.     | d2 = maxnodes
  62.  
  63. | STRUCTURE LZBase,0
  64.     .equ    lzb_InputLength,0
  65.     .equ    lzb_OutputLength,4
  66.     .equ    lzb_Input,8
  67.     .equ    lzb_Output,12
  68.  
  69.     .equ    lzb_Index,16
  70.     .equ    lzb_Previous,20
  71.     .equ    lzb_PreOffset,20
  72.     .equ    lzb_PreLength,22
  73.  
  74.     .equ    lzb_NewCount,24
  75.     .equ    lzb_New,26            | the try one byte after
  76.     | ...
  77.  
  78.     .equ    lzb_MemPool,30
  79.     .equ    lzb_HashSave,34
  80.     .equ    lzb_HashSaveBack,38
  81.     
  82.     .equ    lzb_Space,42
  83.     .equ    lzb_SIZEOF,50
  84.     
  85.  
  86. |GETOFFS    MACRO    |\1=addr, \2=dst , \3=trash
  87. |        |\1=addr, \2=offs, \3=~
  88. |    moveq    #0,\2
  89. |    move.w    (\1),\2
  90. |    ENDM
  91.     .macro    GETOFFS addr,offs
  92.     moveq    #0,\offs
  93.     movew    \addr@,\offs
  94.     .endm
  95.  
  96. |GETOFFI    MACRO    |\1,\2=addr, \3=dst , \4=trash
  97. |        |\1,\2=addr, \3=offs, \4=~
  98. |    moveq    #0,\3
  99. |    move.w    (\1,\2),\3
  100. |    ENDM
  101.     .macro    GETOFFI addr,dist,offs
  102.     moveq    #0,\offs
  103.     movew    \addr@(\dist),\offs
  104.     .endm
  105.  
  106. | *******************************************************************
  107.  
  108.     | globals
  109. #define    inputlength    d6
  110. #define    indexcounter    d5
  111. #define    indexmask    d7
  112.  
  113. #define    outputbuffer    a2
  114. #define    lzhash        a5
  115. #define    inputbuffer    a6
  116.  
  117. #define ASCIICount    256
  118.  
  119. |extern int LZWSCrunch(register int inlen __asm__ ("d0"),
  120. |               register int outlen __asm__ ("d1"),
  121. |               register int maxnodes __asm__ ("d2"),
  122. |               register char *input __asm__ ("a0"),
  123. |               register char *output __asm__ ("a1"));
  124.     .text
  125.     .even
  126.     .globl    _LZWSCrunch
  127. _LZWSCrunch:
  128.     moveml    d2-d7/a1-a6,sp@-
  129.     movew    #IDENTIFIER,a1@+                | identifier LZ
  130.     movel    d0,a1@+                        | for size
  131.  
  132.     lea    sp@(-lzb_SIZEOF),sp
  133.     moveml    d0-d1/a0-a1,sp@
  134.     clrl    sp@(lzb_Previous)
  135.     clrw    sp@(lzb_NewCount)
  136.     clrl    sp@(lzb_New)
  137.  
  138.     movel    d2,d7                        | maxnodes
  139.  
  140. | ***** Analyse inputstream *****************************************
  141.  
  142. AnalyseAndAllocateLZW:
  143.     movel    #0xFFFFFFFF,a4
  144.  
  145.     |movel    #MEMF_FAST!MEMF_PUBLIC!MEMF_CLEAR,d0
  146.     movel    #0x10005,d0
  147.     movel    #65536,d1
  148.     movel    #32768,d2
  149.     ComExec    _LVOCreatePool
  150.     movel    d0,sp@(lzb_MemPool)
  151.     beqw    NoMem1
  152.  
  153.  
  154.     movel    #MAX_LENGTH*4+4,d0
  155.     movel    sp@(lzb_MemPool),a0
  156.     ComFast    _LVOAllocPooled
  157.     movel    d0,sp@(lzb_HashSave)
  158.     beqw    NoMem2
  159.     movel    d0,a0
  160.     clrl    a0@
  161.  
  162.     movel    #MAX_LENGTH*4+4,d0
  163.     movel    sp@(lzb_MemPool),a0
  164.     ComFast    _LVOAllocPooled
  165.     movel    d0,sp@(lzb_HashSaveBack)
  166.     beqw    NoMem2
  167.     movel    d0,a0
  168.     clrl    a0@
  169.  
  170.  
  171.     movel    #(((ASCIICount*ASCIICount)*4)*2),d0
  172.     movel    sp@(lzb_MemPool),a0
  173.     ComFast    _LVOAllocPooled    | 256^2                | max = 65536b*8=512k
  174.     tstl    d0
  175.     beqw    NoMem2
  176.     movel    d0,lzhash
  177.  
  178.  
  179.     movel    #(((ASCIICount*ASCIICount)*4)*2),sp@-
  180.     movel    lzhash,sp@-
  181.     bsr    _FILLMEMORY
  182.     addql    #8,sp
  183.  
  184.  
  185.     movel    sp@(lzb_Input),a1
  186.     movel    sp@(lzb_InputLength),d1
  187.     moveq    #0,d3                        | for addx
  188.     moveq    #0,d4                        | count of different symbols
  189.     moveq    #0,d5                        | count of all parsed symbols
  190.     moveq    #1,d6                        | additional count to -1 if the file is bigger than maxnodes
  191.  
  192.                                 | wir schaetzen die ersten xx bytes ab
  193.     cmpl    d7,d1                        | um etwas sinnvollere nodes zu bekommen
  194.     blts    skip1
  195.     movel    d7,d1
  196.     addql    #4,d6                        | 4*65536=262144
  197. skip1:    movel    d1,d2
  198.  
  199. .Count:    moveq    #0,d0
  200.     movew    a1@,d0
  201.     addql    #1,a1
  202.     addql    #1,lzhash@(d0:l:8)                | add one newhashsavecheck
  203.     addxl    d3,d4                        | add one new hashheader
  204.     addql    #1,d5                        | add one new hashentry
  205.     subql    #1,d2
  206.     bges    .Count
  207.  
  208.     movel    sp@(lzb_InputLength),d1
  209.  
  210.     cmpl    d7,d1
  211.     blts    skip2
  212.     movel    #((ASCIICount*ASCIICount)*5)/2,d4        | *5 = 1 header + 4 entries /2 = no double
  213. skip2:    addl    d4,d5                        | double headers for 4 bytes in back of the hashes
  214.     addl    d4,d5                        | for save
  215.     lsll    #2,d5                        | all headers+entries multiplies by 4
  216.     movel    d5,d0
  217.     movel    sp@(lzb_MemPool),a0
  218.     ComFast    _LVOAllocPooled                    | allocate flowing hash
  219.     movel    d0,a4                        | store it
  220.  
  221.     moveq    #0,d1
  222.     movel    #(ASCIICount*ASCIICount)-1,d3
  223.     movel    lzhash,a3
  224.     
  225. .Alloc2:
  226.     movel    a3@,d0
  227.     addl    d6,d0
  228.     movel    d0,a3@+                        | a minimum of 4 nodes if we doesnt parsed the hole file
  229.     bles    skipM2
  230.     lsll    #2,d0                        | hopefully good nodes
  231.                                 | very simple adaptive (static)
  232.     addql    #8,d0                        | 4 bytes backsave!!
  233.     addl    d1,a4
  234.     movel    d0,d1
  235.     movel    a4,d0
  236.     clrl    a4@
  237. skipM2:
  238.     movel    d0,a3@+
  239.     dbra    d3,.Alloc2
  240.  
  241. | *******************************************************************
  242.  
  243. |AddOneH    MACRO
  244. |    moveq    #1,d0
  245. |    bsrw    AddHash2
  246. |    ENDM
  247.     .macro    AddOneH
  248.     moveq    #1,d0
  249.     bsrw    AddHash2
  250.     .endm
  251.  
  252.     addql    #4,lzhash
  253.  
  254. Crunch:    movel    sp@(lzb_InputLength),inputlength        | store length as bytesleft
  255.     movel    sp@(lzb_Output),sp@(lzb_Index)            | store output
  256.     movel    sp@(lzb_Input),inputbuffer            | store input as currentdata
  257.     addl    inputlength,sp@(lzb_Output)            | calculate dataend without xpk_margin
  258.  
  259. Init:    lea    sp@(lzb_Index)@(INDEX_LENGTH),outputbuffer    | get&skip indexaddress
  260.     moveq    #0,d7                        | delete indexmask, no compression
  261.     moveq    #INDEX_SIZE-1-1,indexcounter            | delete indexcounter, one uncompresses bytes at the beginning
  262.  
  263.     AddOneH                            | param of AddHash
  264.     moveb    inputbuffer@+,outputbuffer@+            | store first three bytes, they will never be compressed
  265.  
  266.     subql    #1,inputlength
  267.  
  268.     | a2 = output
  269.     | a4 = unused -> $FFFFFFFF
  270.     | a5 = basehashaddress
  271.     | a6 = input
  272.     | a7 = relative base
  273.     | d3 = address of longest match
  274.     | d4 = actual matchlength
  275.     | d5 = indexcount
  276.     | d6 = processlength
  277.     | d7 = indexbits
  278.  
  279. | *-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
  280.  
  281.     | d0 = hashcounter
  282.     | d1 = scratch -> #0
  283.     | d2 = scratch -> #0
  284.     | a0 = matchaddress
  285.     | a1 = compareaddress
  286.     | a3 = hashaddress
  287.  
  288.     | find match loop
  289. #define    lzhashcount    d0
  290.  
  291. #define    matchlencheck    d1
  292. #define    maxcompare    matchlencheck
  293. #define    maxcomparestart    d2
  294. #define    matchoffset    d3
  295. #define    matchlength    d4
  296.  
  297. #define    lzhashaddress    a0
  298. #define    actualaddress    a1
  299. #define    lzhashsymbol    a3
  300. #define    temporaryhash    a4
  301.  
  302. InitEndian:
  303.     moveq    #MIN_LENGTH-2,matchlength            | set first lastmatchlen, the next match must be _greater_ than 2
  304. SkipEndian:                            | -2 cause of two bytes must get (VariableLength)
  305.     moveq    #0,d1
  306.     movew    inputbuffer@,d1
  307.     movel    lzhash@(d1:l:8),lzhashsymbol
  308.     movel    lzhashsymbol@+,lzhashcount
  309. .InAnyCaseNotLonger:
  310.     dbra    lzhashcount,bigEndian
  311.     braw    BrutalBreak
  312.  
  313. | *-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
  314.  
  315. bigEndian:
  316.     movel    lzhashsymbol@(lzhashcount:l:4),lzhashaddress    | get next hashpointer
  317.     movel    inputbuffer,actualaddress            | get currentdata
  318.  
  319.     movew    actualaddress@(-1,matchlength:w),matchlencheck
  320.     cmpw    lzhashaddress@(-1,matchlength:w),matchlencheck
  321.     bnes    .InAnyCaseNotLonger
  322.  
  323.     addql    #MIN_LENGTH-1,lzhashaddress
  324.     addql    #MIN_LENGTH-1,actualaddress
  325.  
  326.     | d1 = longest matchlength to beat
  327. .MatchHit:
  328.     movel    matchlength,matchlencheck            | get the next _higher_ lastmatchlen
  329.     subql    #MIN_LENGTH-2,matchlencheck            | eleminate the first four bytes
  330.     beqs    .InitCompare
  331.  
  332. #ifdef UNROLL
  333.     movel    matchlencheck,maxcomparestart
  334.     lsrl    #2,matchlencheck
  335.     andw    #0b000000011,maxcomparestart
  336.     negw    maxcomparestart
  337.     .equ    CMPSIZE,4
  338.     jmp    pc@(.Compp,maxcomparestart:w:CMPSIZE)
  339. .Comp:    cmpb    lzhashaddress@+,actualaddress@+
  340.     bnes    .InAnyCaseNotLonger
  341. |CMPSIZE    EQU    (*-.Comp)
  342.     cmpb    lzhashaddress@+,actualaddress@+
  343.     bnes    .InAnyCaseNotLonger
  344.     cmpb    lzhashaddress@+,actualaddress@+
  345.     bnes    .InAnyCaseNotLonger
  346. .Compp    bras    .EndLoop
  347. .IntLoop:
  348.     cmpl    lzhashaddress@+,actualaddress@+            | chance that in some data are
  349.     bnes    .InAnyCaseNotLonger                | more than 8 equal byte is less
  350. .EndLoop:
  351.     dbra    matchlencheck,.IntLoop
  352. #else
  353. .IsByte:
  354.     lsrl    #1,matchlencheck                | lsr puts last bit in carry
  355.     bccs    .IsWord                
  356.     cmpb    lzhashaddress@+,actualaddress@+
  357.     bnes    .InAnyCaseNotLonger        
  358. .IsWord:
  359.     lsrl    #1,matchlencheck            
  360.     bccs    .IsLong                
  361.     cmpw    lzhashaddress@+,actualaddress@+
  362.     bnes    .InAnyCaseNotLonger        
  363. .IsLong:
  364.     lsrl    #1,matchlencheck            
  365.     bccs    .EndLoop            
  366.     cmpl    lzhashaddress@+,actualaddress@+
  367.     bnes    .InAnyCaseNotLonger        
  368. .IsQuad:
  369.     bras    .EndLoop                    | length-correction for dbra
  370. .IntLoop:
  371.     cmpl    lzhashaddress@+,actualaddress@+            | I think quad is enough, that
  372.     bnes    .InAnyCaseNotLonger                | means 8 equal bytes, and the
  373. .NullCse:
  374.     cmpl    lzhashaddress@+,actualaddress@+            | chance that in some data are
  375.     bnes    .InAnyCaseNotLonger                | more than 8 equal byte is less
  376. .EndLoop:
  377.     dbra    matchlencheck,.IntLoop
  378. #endif
  379.  
  380. .InitCompare:
  381.     addql    #1,matchlength
  382.     movel    lzhashaddress,matchoffset            | get matchdist from current hashdist
  383.     subl    actualaddress,matchoffset
  384.  
  385.     movel    #MAX_LENGTH-1,maxcompare            | put MAX_LENGTH (255+4) as maximum comparisson
  386.     subl    matchlength,maxcompare                | not longer than this
  387.     movel    maxcompare,maxcomparestart            | get 33-2 as differencelen
  388. .Compare:
  389.     cmpb    lzhashaddress@+,actualaddress@+            | calculate the additional matchlength
  390.     dbne    maxcompare,.Compare                | break if its not longer equal
  391.  
  392.     beqs    break                    
  393.     subql    #1,actualaddress                | correction of (a1)+ from compare-loop
  394. break:
  395.     subw    maxcompare,maxcomparestart            | added equal bytes to differencelen
  396.     addl    maxcomparestart,matchlength            | results in new matchlen
  397.  
  398.     movel    sp@(lzb_HashSave),temporaryhash        
  399.     addql    #1,temporaryhash@            
  400.     movel    temporaryhash@,d1            
  401.     movel    actualaddress,temporaryhash@(d1:l:4)        | build an temporary hashbuffer
  402.  
  403.     cmpw    #MAX_LENGTH,matchlength
  404.     dbge    lzhashcount,bigEndian                | some speedup
  405.  
  406. | *-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
  407.  
  408. |ExChng    MACRO
  409. |    movel    lzb_HashSave(sp),d2                | exchange temp hash
  410. |    movel    sp@(lzb_HashSaveBack),lzb_HashSave(sp)
  411. |    movel    d2,sp@(lzb_HashSaveBack)
  412. |    ENDM
  413.     .macro    ExChng
  414.     movel    sp@(lzb_HashSave),d2                | exchange temp hash
  415.     movel    sp@(lzb_HashSaveBack),sp@(lzb_HashSave)
  416.     movel    d2,sp@(lzb_HashSaveBack)
  417.     .endm
  418.  
  419. |TstVal    MACRO
  420. |    cmpw    #MIN_LENGTH-1,lzb_Previous+2(sp)
  421. |    bgew    \1
  422. |    ENDM    
  423.     .macro    TstVal equal
  424.     cmpw    #MIN_LENGTH-1,sp@(lzb_Previous+2)
  425.     bgew    \equal
  426.     .endm
  427. |CmpVal    MACRO
  428. |    cmpw    lzb_Previous+2(sp),\2                | 
  429. |    bles    \1
  430. |    ENDM    
  431.     .macro    CmpVal equal,val
  432.     cmpw    sp@(lzb_Previous+2),\val            | 
  433.     bles    \equal
  434.     .endm
  435. |PutVal    MACRO
  436. |    movemw    matchoffset/matchlength,lzb_Previous+\1(sp)    | store actual match
  437. |    ENDM
  438.     .macro    PutVal offs
  439.     movemw    matchoffset/matchlength,sp@(lzb_Previous+\offs)    | store actual match
  440.     .endm
  441. |GetVal    MACRO
  442. |    movemw    lzb_Previous+\1(sp),matchoffset/matchlength    | restore actual match
  443. |    ENDM
  444.     .macro    GetVal offs
  445.     movemw    sp@(lzb_Previous+\offs),matchoffset/matchlength    | restore actual match
  446.     .endm
  447. |GetOff    MACRO
  448. |    movew    lzb_PreOffset+\1(sp),matchoffset        | restore actual offset
  449. |    moveq    #\2,matchlength
  450. |    ENDM
  451.     .macro    GetOff offs,val
  452.     movew    sp@(lzb_PreOffset+\offs),matchoffset        | restore actual offset
  453.     moveq    #\val,matchlength
  454.     .endm
  455. |DelVal    MACRO
  456. |    clrl    lzb_Previous(sp)
  457. |    clrw    lzb_NewCount(sp)
  458. |    clrl    lzb_New(sp)
  459. |    ENDM
  460.     .macro    DelVal
  461.     clrl    sp@(lzb_Previous)
  462.     clrw    sp@(lzb_NewCount)
  463.     clrl    sp@(lzb_New)
  464.     .endm
  465.  
  466. |BakVal    MACRO
  467. |    movemw    matchoffset/matchlength,lzb_Space(sp)
  468. |    ENDM
  469.     .macro    BakVal
  470.     movemw    matchoffset/matchlength,sp@(lzb_Space)
  471.     .endm
  472. |ResVal    MACRO
  473. |    movemw    lzb_Space(sp),matchoffset/matchlength
  474. |    ENDM
  475.     .macro    ResVal
  476.     movemw    sp@(lzb_Space),matchoffset/matchlength
  477.     .endm
  478.  
  479. | *-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
  480.  
  481. #define    matchlencode    d1
  482.  
  483. BrutalBreak:
  484.     cmpw    #MIN_LENGTH-1,matchlength            | check if the match is optimal
  485.     bltw    NoMatch                        | if not, do not compress
  486.     cmpl    inputlength,matchlength
  487.     bgtw    TstEnd
  488.  
  489.     TstVal    CheckP
  490.  
  491. | begin:
  492. |    previous->0
  493. |    1stnew    ->0
  494. |    2ndnew    ->0
  495. |
  496. | abcd
  497. | ^
  498. | actual
  499. |
  500. | 1.    setp    -> previous=actual
  501. | 2.    checkp
  502. |
  503. |     abcd
  504. |     ^^
  505. |      actual
  506. |     previous
  507. |
  508. |  a.>    newp    -> 1stnew=previous
  509. |
  510. |     abcd
  511. |     ^^^
  512. |       actual
  513. |      previous
  514. |     1stnew
  515. |
  516. |  b.<    oldp
  517.  
  518. Set1st:    PutVal    0
  519.     movew    #1,sp@(lzb_NewCount)
  520.     ExChng
  521.     bras    SetP
  522. Set2nd:    |addw    sp@(lzb_NewCount),matchlength
  523.     addqw    #1,matchlength                    |
  524.     addqw    #1,sp@(lzb_NewCount)
  525.     clrl    sp@(lzb_HashSave)@(0)                | delete temporary HashBuffer
  526. SetP:    |moveq    #1,d0
  527.     |bsr    AddHash2                    | add one
  528.     AddOneH
  529.     addl    d0,inputbuffer
  530.     subl    d0,inputlength
  531.     bles    OldP
  532.     cmpw    #MAX_LENGTH,matchlength
  533.     bltw    SkipEndian
  534.  
  535. OldP:    cmpw    #1,sp@(lzb_NewCount)
  536.     beqs    Set2nd
  537.     GetVal    0
  538.     ExChng
  539.     subql    #2,inputbuffer
  540.     addql    #2,inputlength
  541.     bras    DoneP
  542.  
  543. CheckP:    subw    sp@(lzb_NewCount),matchlength
  544.     CmpVal    OldP,matchlength
  545.  
  546. NewP:    addw    sp@(lzb_NewCount),matchlength
  547.     cmpw    #1,sp@(lzb_NewCount)
  548.     bgts    New2nd
  549. New1st:    moveb    inputbuffer@(-1),outputbuffer@+
  550.     bsr    IncIndx
  551.     cmpw    #MAX_LENGTH,matchlength
  552.     bltw    Set1st
  553.     bras    DoneP
  554. Sma2nd:    moveb    inputbuffer@(-2),outputbuffer@+
  555.     bsr    IncIndx
  556.     moveb    inputbuffer@(-1),outputbuffer@+
  557.     bsr    IncIndx
  558.     bras    Skp2nd
  559. New2nd:    BakVal
  560.     GetOff    0,MIN_LENGTH-1
  561.     movel    #Sma2nd,sp@-
  562.     bsrw    StoreC
  563. Skp2nd:    ResVal
  564.     cmpw    #MAX_LENGTH,matchlength
  565.     bltw    Set1st
  566.  
  567. DoneP:    movel    #TooSmal,sp@-
  568.     bsrs    StoreC
  569.  
  570.     movel    sp@(lzb_HashSave),temporaryhash
  571.     movel    temporaryhash@+,d1
  572.     beqs    .EAdd
  573.     clrl    temporaryhash@(d1:l:4)
  574.     movel    temporaryhash@+,inputbuffer
  575.     movel    temporaryhash@,d0
  576.     beqs    .TEnd
  577. .TAdd:    subl    inputbuffer,d0
  578.     bsrw    AddHash2
  579.     movel    temporaryhash@+,inputbuffer
  580.     movel    temporaryhash@,d0
  581.     bnes    .TAdd
  582. .TEnd:    subl    matchlength,inputbuffer
  583.  
  584. .EAdd:    movel    matchlength,d0
  585.     subql    #3,d0
  586.     blts    .NoAdd1
  587.     addl    d0,inputbuffer
  588.  
  589.     |moveq    #1,d0
  590.     |bsr    AddHash2
  591.     AddOneH
  592.     addl    d0,inputbuffer
  593.     bsr    AddHash2
  594.     addl    d0,inputbuffer
  595.     bsr    AddHash2
  596.     addl    d0,inputbuffer
  597.     bras    .NoAdd2
  598.  
  599. .NoAdd1:
  600.     addl    matchlength,inputbuffer    
  601. .NoAdd2:
  602.     clrl    sp@(lzb_HashSave)@(0)                | delete temporary HashBuffer
  603.     clrl    sp@(lzb_HashSaveBack)@(0)            | delete temporary HashBuffer
  604.     DelVal
  605.  
  606. .EndP:    braw    NextPeriod
  607.  
  608. | *******************************************************************
  609.  
  610. #define    indexsymbol    d2
  611. #define    matchsymbol    d2
  612.  
  613. StoreC:    movew    matchlength,matchlencode        
  614.     subw    #MIN_LENGTH-1,matchlencode            | remove them to make more space
  615. StoreS:    cmpw    #0b01100000000000000,matchoffset            | $FFFF=1 $FFF0=15 $FF00=255 $F000=4096
  616.     blss    set1
  617.     cmpw    #4,matchlencode
  618.     blts    set2
  619.     cmpw    #0b01111000000000000,matchoffset
  620.     blss    set1    
  621.     cmpw    #16,matchlencode
  622.     bges    set1
  623. set3:    movew    matchoffset,matchsymbol
  624.     lslw    #4,matchsymbol
  625.     orw    matchlencode,matchsymbol
  626.     movew    matchsymbol,outputbuffer@+            | store compressed data
  627.     moveq    #0b010,indexsymbol
  628.     bras    .Done
  629. set2:    movew    matchoffset,matchsymbol
  630.     lslw    #2,matchsymbol
  631.     orw    matchlencode,matchsymbol
  632.     movew    matchsymbol,outputbuffer@+            | store compressed data
  633.     moveq    #0b001,indexsymbol
  634.     bras    .Done
  635. set1:    subqw    #1,matchlencode
  636.     blts    AbortC
  637.     moveq    #0b011,indexsymbol
  638.     movew    matchoffset,outputbuffer@+
  639.     moveb    matchlencode,outputbuffer@+            | store compressed data
  640. .Done:    lsll    indexcounter,indexsymbol
  641.     lsll    indexcounter,indexsymbol
  642.     orl    indexsymbol,d7
  643.     movel    sp@+,sp@
  644. IncIndx:                            | if it not reached 32 bits in index
  645.     dbra    indexcounter,.NextBt                | continue
  646.     movel    indexmask,sp@(lzb_Index+4)@(0)            | save indexmask
  647.     movel    outputbuffer,sp@(lzb_Index+4)            | get indexaddress
  648.     addql    #INDEX_LENGTH,outputbuffer            | skip indexaddress
  649.     moveq    #INDEX_SIZE-1,indexcounter            | delete indexcounter
  650.     moveq    #0,indexmask                    | delete indexmask
  651. .NextBt:
  652.     rts
  653. AbortC:    addql    #4,sp
  654.     rts
  655.  
  656. | *******************************************************************
  657.  
  658.     | add hash loop
  659. #define    distance    d0
  660. |lzhashaddress    EQUR    a0
  661. #define    lzhashnew    a1
  662. |lzhashsymbol    EQUR    a3
  663. #define    newhashaddress    inputbuffer
  664.  
  665.     | a5 = hash
  666.     | d0 = next value distance
  667.     | d1/d4 -> do not!!! scratch
  668. AddHash2:
  669.  
  670. #define    newsymbol    d2
  671. #define    newsymbolcount    d3
  672.  
  673.     moveq    #0,newsymbol
  674.     movew    inputbuffer@,newsymbol
  675.     movel    lzhash@(newsymbol:l:8),lzhashsymbol
  676.     movel    lzhashsymbol@,newsymbolcount
  677.     lea    lzhashsymbol@(-4,newsymbolcount:l:4),lzhashnew
  678.     cmpl    lzhashnew@+,newhashaddress
  679.     beqs    .UpdHsh
  680.     cmpl    lzhashnew@+,newhashaddress
  681.     beqs    .UpdHsh
  682.     addql    #1,lzhashsymbol@
  683.     movel    newhashaddress,lzhashnew@
  684.  
  685. #define    nextsymbol    newsymbol
  686. #define    nextsymbolcount    newsymbolcount
  687.  
  688. .UpdHsh:
  689.     moveq    #0,nextsymbol
  690.     movew    newhashaddress@(distance:w),nextsymbol
  691.     lea    lzhash@(-4,nextsymbol:l:8),lzhashaddress
  692.     movel    lzhashaddress@(4),lzhashsymbol
  693.     movel    lzhashsymbol@,nextsymbolcount
  694.     beqs    .NoUpd
  695.  
  696.     lea    lzhashsymbol@(4),lzhashnew
  697.  
  698. #define    nextnewcount    nextsymbol
  699.  
  700. .CutIt:    cmpl    lzhashaddress@,nextsymbolcount            | compare with maximum entries, which are defineable
  701.     blts    .DelOld
  702.     movel    lzhashaddress@,nextnewcount
  703.     subl    nextsymbolcount,nextnewcount
  704.     negl    nextnewcount
  705.     addql    #1,nextnewcount
  706.     subl    nextnewcount,nextsymbolcount
  707.     lea    lzhashnew@(nextnewcount:l:4),lzhashnew        | delete some entries!
  708.  
  709. #define    nextoffset    nextsymbol
  710.  
  711. .DelOld:
  712.     movel    newhashaddress,nextoffset
  713.     addl    distance,nextoffset
  714.     subl    lzhashnew@+,nextoffset
  715.     subl    #MAX_HISTORY,nextoffset                | calculate next max offset
  716.     dblt    nextsymbolcount,.DelOld
  717.     extl    nextsymbolcount
  718.     bles    .DelAll
  719.  
  720.     cmpl    lzhashsymbol@,nextsymbolcount
  721.     bnes    .UpdCpy
  722. .NoUpd:    rts
  723.  
  724. .UpdCpy:
  725.     movel    nextsymbolcount,lzhashsymbol@+
  726.     subql    #4,lzhashnew
  727.     subql    #1,nextsymbolcount
  728. .Copy:    movel    lzhashnew@+,lzhashsymbol@+
  729.     dbra    nextsymbolcount,.Copy
  730.     rts
  731.  
  732. .DelAll:
  733.     clrl    lzhashsymbol@
  734.     rts
  735.  
  736. | *******************************************************************
  737.  
  738. TooSmal:
  739.     cmpw    #MIN_LENGTH-1,sp@(lzb_Previous+2)
  740.     blts    SkipMatch1
  741.     bgtw    OldP
  742.     | dieser Fall tritt nur auf, wenn:
  743.     | abcd
  744.     | ^^ im PreviousBuffer steht mehr als 16k entfernt ist, und:
  745.     | abcd
  746.     |   ^^ der naechste Versuch NICHT! laenger als 2 ist
  747.     | Begruendung:
  748.     |  -zwei strings werden in den hash geschickt
  749.     |  -gibt es einen laengeren string?
  750.     |  -nein
  751.     |  -der restore wird geholt
  752.     |  -der wb bricht ab, da zu kurz, der w bricht ab, da zu weit entfernt
  753.     |  -ZWEI! strings stehen nun im hash
  754.     |  -wir updaten den hash nicht, sondern geben nur die unkomprimierten
  755.     |   bytes aus (stehen schon im hash)
  756.     DelVal
  757.     moveb    inputbuffer@+,outputbuffer@+            | skip uncompressed data and store it at the same time
  758.     bsr    IncIndx
  759.     moveq    #2,matchlength                    | set fake-matchlen
  760.     bras    SkipMatch2
  761. TstEnd:    movel    inputlength,matchlength        
  762.     TstVal    CheckP
  763.     cmpl    #MIN_LENGTH-1,matchlength            | check if the match is optimal
  764.     bgew    DoneP                        | if not, do not compress
  765.     bras    SkipMatch1
  766. NoMatch:
  767.     TstVal    OldP
  768. SkipMatch1:
  769.     moveq    #1,matchlength                    | set fake-matchlen
  770.     AddOneH
  771. SkipMatch2:
  772.     moveb    inputbuffer@+,outputbuffer@+            | skip uncompressed data and store it at the same time
  773.     bsr    IncIndx
  774. NextPeriod:
  775.     cmpl    sp@(lzb_Output),outputbuffer
  776.     bgts    OverFlow
  777.     subl    matchlength,inputlength                | reduce bytesleft with matchlen
  778.     bgtw    InitEndian                    | start BigEndian
  779.  
  780. | *-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
  781.  
  782. EndFle:    addl    indexcounter,indexcounter
  783.     bset    indexcounter,d7
  784.     movel    d7,sp@(lzb_Index)@(0)                | save indexmask
  785.     clrw    outputbuffer@+
  786.  
  787.     movel    sp@(lzb_MemPool),a0
  788.     ComExec    _LVODeletePool
  789.  
  790.     lea    sp@(lzb_SIZEOF),sp
  791.     movel    a2,d0                        | end of data
  792.     moveml    sp@+,d2-d7/a1-a6
  793.     subl    a1,d0                        | begin of data
  794.     rts
  795.  
  796. OverFlow:
  797.     movel    sp@(lzb_MemPool),a0
  798.     ComExec    _LVODeletePool
  799.  
  800.     lea    sp@(lzb_SIZEOF),sp
  801.     moveml    sp@+,d2-d7/a1-a6
  802.     moveq    #ERROR_OVERFLOW,d0
  803.     rts
  804. NoMem1:
  805.     lea    sp@(lzb_SIZEOF),sp
  806.     moveml    sp@+,d2-d7/a1-a6
  807.     moveq    #ERROR_LESSMEM,d0
  808.     rts
  809. NoMem2:
  810.     movel    sp@(lzb_MemPool),a0
  811.     ComExec    _LVODeletePool
  812.  
  813.     lea    sp@(lzb_SIZEOF),sp
  814.     moveml    sp@+,d2-d7/a1-a6
  815.     moveq    #ERROR_LESSMEM,d0
  816.     rts
  817.  
  818. |    LIST
  819. |LZWCrunchLength    EQU    (*-LZWSCrunch)
  820. |    NOLIST
  821.  
  822. |********************************************************************
  823. |FillMemory by Niels Fr÷hling
  824. |  00  UBYTE* buffer
  825. |  04  ULONG  size in bytes
  826. _FILLMEMORY:
  827.     moveml    d0-a6,a7@-        |60+4=64
  828.     movel    a7@(64+00),a6
  829.     movel    a7@(64+04),d0
  830.     addl    d0,a6            |end of buffer
  831.     moveq    #-1,d6
  832.  
  833.     movew    a6,d1
  834.     moveq    #3,d7
  835.     andl    d7,d1            |3
  836.     beqs    .is_quad
  837.     subl    d1,d0            | max 0b011
  838.     negw    d1
  839. #define    FILLSIZE    2
  840.     jmp    pc@(.is_quad,d1:w:FILLSIZE)
  841.     moveb    d6,a6@-
  842. .Fill:    moveb    d6,a6@-
  843. |FILLSIZE    EQU    (*-.Fill)
  844.     moveb    d6,a6@-    |quad align
  845. .is_quad:
  846.     movew    d0,d1
  847.     andw    d7,d1            |3
  848.     movew    d1,a7@-    |push number of single bytes (upto 3)
  849.  
  850.     moveb    d0,d1
  851.     lsrb    #2,d1            |0b011111100
  852.     beqs    .clr256
  853.     subqw    #1,d1
  854. loop4:    movel    d6,a6@-            |clear upto 256/4-1=63 longwords
  855.     dbra    d1,loop4
  856.  
  857. .clr256:
  858.     lsrl    #8,d0            |does set Z-flag if result is zero, doesnt it?
  859.     beqs    .not256
  860.     moveq    #-1,d1
  861.     moveq    #-1,d2
  862.     moveq    #-1,d3
  863.     moveq    #-1,d4
  864.     moveq    #-1,d5
  865.     moveq    #-1,d7
  866.     movel    d1,a0
  867.     movel    d2,a1
  868.     movel    d3,a2
  869.     movel    d4,a3
  870.     movel    d5,a4
  871.     movel    d6,a5
  872.     subqw    #1,d0
  873. loop256:
  874.     moveml    d1-a5,a6@-        |+52  52
  875.     moveml    d1-a5,a6@-        |+52 104
  876.     moveml    d1-a5,a6@-        |+52 156
  877.     moveml    d1-a5,a6@-        |+52 208
  878.     moveml    d1-a4,a6@-        |+48 256
  879.     dbra    d0,loop256
  880.     subl    #0x00010000,d0
  881.     bgts    .clr256
  882.  
  883. .not256:
  884.     movew    a7@+,d0            |pop number of single bytes (upto 3)
  885.     negw    d0
  886.     jmp    pc@(loop1e,d0:w:FILLSIZE)
  887.     moveb    d6,a6@-            | max 0b011
  888.     moveb    d6,a6@-            |quad align
  889.     moveb    d6,a6@-
  890. loop1e:
  891.     moveml    a7@+,d0-a6
  892.     rts
  893.  
  894. | *******************************************************************
  895.  
  896. |extern void LZWSDecrunch(register char *outLen __asm__ ("d0"),
  897. |              register char *input __asm__ ("a0"),
  898. |              register char *output __asm__ ("a1"));
  899.     .text
  900.     .even
  901.     .globl    _LZWSDecrunch
  902. _LZWSDecrunch:
  903.     moveml    d2-d7/a0/a2,sp@-
  904.     cmpw    #IDENTIFIER,a0@+    | identifier LZ
  905.     bnew    .NotCrunched
  906.     cmpl    a0@+,d0            | size
  907.     bltw    .LessMem
  908.  
  909.     moveq    #-1,d1            | clean up for negative offsets
  910.     moveq    #-1,d4            | clean up for negative offsets
  911.     movew    #0b011,d5
  912.     movew    #0b0111,d6
  913.     movew    #0b01111,d7
  914.  
  915. .DLoop:    movel    a0@+,d2            | bits
  916.     beqs    .RawAll
  917.     moveq    #INDEX_SIZE-1,d3    | indexsize b/w/l
  918. .NextD:    addl    d2,d2
  919.     bcss    .CmpData23
  920.     addl    d2,d2
  921.     bcss    .CmpData1
  922. .RawData:
  923.     moveb    a0@+,a1@+        | b/w/l        -------------->
  924.     dbra    d3,.NextD
  925.     bras    .DLoop
  926. .RawAll:
  927.     movel    a0@+,a1@+        | and here 8* b/w/l  -------------->
  928.     movel    a0@+,a1@+
  929.     movel    a0@+,a1@+
  930.     movel    a0@+,a1@+
  931.     bras    .DLoop
  932.  
  933.     | case: 01
  934. .CmpData1:
  935.     movew    a0@+,d1            | $FFFF + (a0)w
  936.     beqs    .Endin
  937.     movew    d1,d4
  938.     asrl    #2,d1
  939.     andw    d5,d4
  940.     lea    a1@(d1:l),a2
  941.     negw    d4            | 0=MIN_LENGTH-1, 1=+1, 2=+2, 3=+3
  942. #define    MOVESIZE    2
  943.     jmp    pc@(.Null,d4:w:MOVESIZE)
  944.     moveb    a2@+,a1@+
  945.     moveb    a2@+,a1@+
  946.     moveb    a2@+,a1@+
  947. .Null:    moveb    a2@+,a1@+
  948.     moveb    a2@+,a1@+
  949.     dbra    d3,.NextD
  950.     braw    .DLoop
  951. .Endin:    braw    .End
  952.     | case: 10
  953. .CmpData23:
  954.     movew    a0@+,d1            | $FFFF + (a0)w
  955.     beqs    .Endin
  956.     addl    d2,d2
  957.     bcss    .CmpData3
  958. .CmpData2:
  959.     movew    d1,d4
  960.     asrl    #4,d1
  961.     andw    d7,d4
  962.     bgts    .DoIt
  963.     lea    a1@(d1:l),a2        | d1 - offset, d4 - length
  964.     bras    .Null
  965.     | case: 11
  966. .CmpData3:
  967.     clrw    d4            | $FFFF00 + d4b must be there
  968.     moveb    a0@+,d4
  969.     addqw    #1,d4
  970. .DoIt:    lea    a1@(d1:l),a2        | d1 - offset, d4 - length
  971.     movew    d4,d1
  972.     lsrw    #3,d1
  973.     andw    d6,d4
  974.     negw    d4
  975.     jmp    pc@(.FastC5,d4:w:MOVESIZE)
  976.     moveb    a2@+,a1@+
  977. .CopyLoopLong2:
  978.     moveb    a2@+,a1@+
  979.     moveb    a2@+,a1@+
  980. .FastC1:
  981.     moveb    a2@+,a1@+
  982. .FastC2:
  983.     moveb    a2@+,a1@+
  984. .FastC3:
  985.     moveb    a2@+,a1@+
  986. .FastC4:
  987.     moveb    a2@+,a1@+
  988. .FastC5:
  989.     moveb    a2@+,a1@+
  990. .FastC6:
  991.     moveb    a2@+,a1@+
  992. |MOVESIZE    EQU    (*-.FastC6)
  993. .Fast:    dbra    d1,.CopyLoopLong2
  994. .DoneSec2:
  995.     dbra    d3,.NextD
  996.     braw    .DLoop
  997. .End:    moveml    sp@+,d2-d7/a0/a2
  998.     movel    a0@(2),d0
  999.     rts
  1000. .NotCrunched:
  1001.     moveml    sp@+,d2-d7/a0/a2
  1002.     moveq    #ERROR_NOTCRUNCHED,d0
  1003.     rts
  1004. .LessMem:
  1005.     moveml    sp@+,d2-d7/a0/a2
  1006.     moveq    #ERROR_LESSMEM,d0
  1007.     rts
  1008.  
  1009. | *******************************************************************
  1010.  
  1011. |extern int LZWSSize(register char *input __asm__ ("a0"));
  1012.     .text
  1013.     .even
  1014.     .globl    _LZWSSize
  1015. _LZWSSize:
  1016.     cmpw    #IDENTIFIER,a0@+    | identifier LZ
  1017.     bnew    .NotC
  1018.     movel    a0@+,d0            | size
  1019.     rts
  1020. .NotC:    moveq    #ERROR_NOTCRUNCHED,d0
  1021.     rts
  1022.