home *** CD-ROM | disk | FTP | other *** search
/ Amiga ISO Collection / AmigaUtilCD2.iso / Workbench / Libs / XPKMA-R1.LHA / xpkMASH16.library.S < prev    next >
Encoding:
Text File  |  1994-03-26  |  16.5 KB  |  890 lines
  1. ;9.8.94  17:00
  2.  
  3. ;d7 end of packing area
  4. ;d6 bits buffer
  5. ;d5 scratch
  6. ;d4 scratch
  7. ;d3 match length and match offset
  8. ;d2 temporary
  9. ;d1 temporary
  10. ;d0 temporary
  11.  
  12. ;a0 source pointer
  13. ;a1 destination pointer
  14. ;a2 hash index table
  15. ;a3 linked list
  16. ;a4 scratch
  17. ;a5 scratch
  18. ;a6 actual bit store address
  19.  
  20.  
  21.  
  22. ;Macro for hash function - RETURN (8+7) bit
  23.  
  24. HASH    MACRO
  25.     moveq    #0,d1
  26.      move.b    1(a0),d1
  27.      lsl.w    d5,d1
  28.      move.b    (a0),d1
  29.      add.l    d1,d1
  30.      move.w    a0,d0
  31.      sub.w    (a3,d1.l),d0        ;get previous hash match address
  32.      move.w    a0,(a3,d1.l)        ;and store new one
  33.      move.w    a0,d1
  34.      add.w    d1,d1
  35.      move.w    d0,(a2,d1.w)
  36.     ENDM
  37.  
  38. CLEARHUFFMANTAB    MACRO
  39.          lea    table(pc),a1
  40.          add.l    #$1000,a1    ;clear tables
  41.          move.l    #$2ff,d1
  42.          moveq    #0,d0
  43. .\@1         move.l    d0,-(a1)
  44.          dbra    d1,.\@1
  45.          subq.b    #1,d0
  46. .\@2         move.l    d0,-(a1)    ;init index-table
  47.          dbra    d0,.\@2
  48.          move.l    a1,a2
  49.          add.l    #$400,a2
  50.         ENDM
  51.  
  52. TABLEWRITE    MACRO
  53.          lea    ta(pc),a5
  54.          lsl.w    #2,d0
  55.          addq.l    #1,0(a5,d0)
  56.          lsr.w    #2,d0
  57.         ENDM
  58.  
  59.  
  60. realbuffer=$20+$80+$200+$400+$800+$1000+$2000+$4000-1
  61.  
  62. bufferlength=$8000            ;length of buffer
  63.  
  64. bits=8
  65.  
  66. indexlength=$200<<bits            ;hash table 15 bits
  67.  
  68. ;SO - for debug informations set to zero
  69. SO=1
  70. star
  71. ;    CLEARHUFFMANTAB
  72. ;    move.l    a1,uloa1
  73. ;    move.l    a2,uloa2
  74.  
  75.     IFEQ    SO
  76.     moveq    #bits,d5
  77.     move.l    #source,a0        ;source pointer
  78.     move.l    #endcode-source,d7    ;length of source file
  79.     move.l    #uklad,a1        ;destination pointer
  80.     move.l    #buf1str,a2        ;address of buffers
  81.     move.l    #buf2str,a3
  82.     move.l    #0,a4
  83.  
  84.     bsr.b    Pack_It
  85.     move.l    d0,celkove
  86.     beq.b    rts0
  87. ;    rts
  88.     jmp    str
  89. ;    bra.w    continue_huffman    ;Dokonceni Huffmanem
  90. rts0    rts
  91.     ENDIF
  92.  
  93. ;Clear fast 128KB of memory
  94.  
  95.     cnop    0,4
  96.     
  97. ClearMemFast
  98.     lsr.l    #8,d1
  99.     movem.l    d2-a5,-(a7)
  100.     move.l    d0,d2
  101.     move.l    d0,d3
  102.     move.l    d0,d4
  103.     move.l    d0,d5
  104.     move.l    d0,d6
  105.     move.l    d0,d7
  106.     move.l    d0,a0
  107.     move.l    d0,a1
  108.     move.l    d0,a2
  109.     move.l    d0,a3
  110.     move.l    d0,a4
  111.     move.l    d0,a5
  112.     bra.b    .clr2
  113. .clr1    movem.l    d0/d2-d7/a0-a5,-(a6)    ;fill 256 byte
  114.     movem.l    d0/d2-d7/a0-a5,-(a6)
  115.     movem.l    d0/d2-d7/a0-a5,-(a6)
  116.     movem.l    d0/d2-d7/a0-a5,-(a6)
  117.     movem.l    d0/d2-d7/a0-a4,-(a6)
  118. .clr2    dbra    d1,.clr1
  119.     movem.l    (a7)+,d2-a5
  120.     rts
  121.  
  122. ;-------------------------------------    
  123. SAVEPACKREGS    reg    d1-a6
  124.  
  125. Pack_It
  126.     movem.l    SAVEPACKREGS,-(a7)
  127.     moveq    #-1,d0
  128.     move.l    #bufferlength,d1
  129.     add.l    d1,a2
  130.     move.l    a2,a6
  131.     add.l    d1,a6
  132.     add.l    d1,d1
  133.     bsr.b    ClearMemFast
  134.  
  135.     move.w    a0,d0
  136.     swap    d0
  137.     move.w    a0,d0
  138.     moveq    #$40,d1
  139.     asl.w    #3,d1
  140.     asl.l    d5,d1            ;d1 contains length for
  141.     move.l    a3,a6
  142.     add.l    d1,a6
  143.     bsr.b    ClearMemFast
  144.  
  145.     add.l    a0,d7            ;end of compress chunk
  146.     move.l    a1,-(a7)
  147.     moveq    #0,d6            ;clear byte for bit storing
  148.     move.l    a0,-(a7)        ;store the first uncompressed byte
  149.     addq.l    #1,a0            ;skip the first byte
  150.         
  151. main_loop
  152.     IFEQ    SO
  153.     move.w    a0,$dff180
  154.     btst    #6,$bfe001        ;mousetest
  155.     beq.w    deadend            ;left button pressed ?
  156.     ENDIF
  157.     moveq    #1,d3
  158.     bsr.w    compress        ;get match - SIZE/OFFSET
  159.     bcs.w    nocompress        ;not succesfull searching
  160. .match0    move.l    d3,-(a7)        ;save match
  161.     addq.l    #1,a0            ;try on next byte for better match
  162.     cmp.l    d7,a0
  163.     bcc.b    .match2            ;end of file?
  164.     bsr.w    compress        ;get new match
  165.     bcs.b    .match2            ;no match -> get previous match
  166.     move.l    (a7)+,d2        ;restore last match
  167.     cmp.w    d3,d2            ;compare with previous match
  168.     bcs.b    .match0
  169.     bra.b    .match3            ;which was better
  170.  
  171. .match2    move.l    (a7)+,d2        ;restore previous match
  172. .match3    move.l    d2,d3
  173.     subq.l    #1,a0
  174.  
  175.     IFEQ    SO
  176.     cmp.l    #endcode-source+uklad-50,a1
  177.     ELSE
  178.     cmp.l    xsp_Sub+2*4(a4),a1
  179.     ENDIF
  180.     bcc.w    deadend
  181.     
  182. goodmatch
  183.     move.l    (a7)+,a5        ;count number of uncompressed bytes
  184.     move.l    a0,d0
  185.     sub.l    a5,d0
  186.     bsr.w    write_uncompressed    ;store number of uncompressed bytes
  187. ;    move.l    uloa2,a4
  188. tt    bra.b    .startl
  189.     cnop    0,4
  190. .write_uncompressed_bytes
  191. ;    moveq    #0,d0
  192. ;    move.b    (a5),d0
  193. ;    lsl.w    #2,d0
  194. ;    addq.l    #1,(a4,d0.w)    ;cetnost hufman
  195.     move.b    (a5)+,(a1)+        ;transfer uncompressed bytes
  196. .startl    cmp.l    a0,a5
  197.     bcs.b    .write_uncompressed_bytes
  198.  
  199. ;Now we have to write all compressed bytes into hash tables
  200.     move.w    d3,d2
  201.     addq.l    #1,a0            ;this byte is already in hash
  202.     bra.b    .start
  203. .loop    HASH                ;store in hash table all bytes
  204. .start    addq.l    #1,a0
  205.     dbf    d2,.loop
  206.  
  207.     moveq    #0,d0
  208.     move.w    d3,d0
  209.     bne.b    bigger_than_two
  210.     move.l    d3,d0
  211.     lsl.l    #5,d0
  212.     moveq    #10,d1            ;2+9-1  offset is 512 bytes
  213.     bra.b    hopla
  214.  
  215. bigger_than_two
  216.     bsr.w    write_match_lenght
  217.     moveq    #0,d0
  218.     swap    d3
  219.     move.w    d3,d0
  220.     lea    table0(pc),a5        ;Calculate offset
  221. .loop    move.l    (a5)+,d2
  222.     sub.w    d2,d0
  223.     bcc.b    .loop
  224.     add.w    d2,d0
  225.     swap    d2
  226.     move.w    d2,d1
  227.     or.l    28(a5),d0
  228.     ror.l    d1,d0
  229.     subq.w    #1,d1            ;for DBRA
  230.  
  231.     IFEQ    SO
  232.     addq.l    #1,60(a5)
  233.     ENDIF
  234. hopla
  235.     bsr.w    compis
  236.     move.l    a0,-(a7)        ;set counter for uncompr bytes
  237.     cmp.l    d7,a0
  238.     bcs.w    main_loop
  239.     moveq    #0,d0
  240.     moveq    #7,d1
  241.     bsr.w    compis
  242.     addq.l    #4,a7
  243.     move.l    (a7)+,d0
  244.     exg    a1,d0
  245.     sub.l    a1,d0
  246. dead    movem.l    (a7)+,SAVEPACKREGS
  247.     rts
  248.  
  249. deadend    addq.l    #8,a7
  250.     moveq    #0,d0
  251.     bra.b    dead
  252.  
  253. nocompress
  254.     addq.l    #1,a0
  255.     cmp.l    d7,a0
  256.     bcs.w    main_loop
  257.     moveq    #0,d3
  258.     bra.w    goodmatch
  259.  
  260. table0
  261.     dc.w     3+5, $20, 3+7,  $80, 3+9, $200,3+10, $400
  262.     dc.w    3+11,$800,3+12,$1000,3+13,$2000,3+14,$4000
  263.  
  264.     dc.l    %00000000,%0010000000,%010000000000,%0110000000000
  265.     dc.l    %10000000000000,%101000000000000,%1100000000000000
  266.     dc.l    %11100000000000000
  267.  
  268.     IFEQ    SO
  269. ddd    dc.l    0,0,0,0,0,0,0,0,0,0,0,0
  270.     ENDIF
  271.  
  272. ;----------------------------------------------------
  273. ; search rutine for matching strings
  274. ; optimized for the maximum speed
  275. ; Input      :    a0    - source address
  276. ;        a2,a3    - tables
  277. ;        d7    - end of block
  278. ; Results :    d3    - match offset/match length
  279. ;        Carry is set when there is  no match
  280. ; Destroy : d0,d1,d2,d4,a5
  281. ;----------------------------------------------------
  282. n_repeat=32
  283.  
  284. COMPRESSREGS    reg    d5-d6/a4
  285.  
  286. compress
  287.     moveq    #0,d0            ;clear MSW D0!!!
  288.     HASH
  289.     lea    -realbuffer(a0),a5
  290.     move.l    a5,d2            ;end of search buffer
  291.     move.l    a0,a5            ;get previous match address
  292.     sub.l    d0,a5
  293.     cmp.l    d2,a5
  294.     bcs.b    c_ret1
  295.     movem.l    COMPRESSREGS,-(a7)
  296.     move.l    a0,d6
  297.     move.b    0(a0,d3.w),d5        ;last byte for comparing - heuristic
  298.  
  299.     IFEQ    SO
  300.     move.w    #n_repeat,d1
  301.     ELSE
  302.     move.l    xsp_Sub+3*4(a4),d1
  303.     ENDIF
  304.  
  305. .c_next    move.l    a5,d4
  306.     move.l    a0,a4
  307.     cmpm.b    (a4)+,(a5)+
  308.     bne.b    c_ret
  309.     cmpm.b    (a4)+,(a5)+
  310.     bne.b    .c_nextmatch
  311.     move.w    #521,d0            ;max 521 same bytes for search
  312. .c_still_same    
  313.     cmpm.b    (a4)+,(a5)+        ;compare for same bytes
  314.     dbne    d0,.c_still_same
  315.     cmp.l    a4,d6
  316.     bcc.b    .c_nextmatch        ;do we have better match ?
  317.     move.l    a4,d6
  318.     move.b    -(a4),d5        ;get new byte for compare
  319.     move.w    a0,d3
  320.     sub.w    d4,d3
  321.     swap    d3
  322.     cmp.l    d7,a4            ;is it end ?
  323.     bcs.b    .c_ok
  324.     move.w    d7,d3
  325.     sub.w    a0,d3
  326.     bra.b    c_ret
  327. .c_ok    move.w    a4,d3
  328.     sub.w    a0,d3
  329.     cmp.w    #256,d3
  330.     bcc.b    c_ret
  331. .c_nextmatch
  332.     move.l    d4,a5            ;heuristic method
  333. .c_nb    move.l    a5,d4            ;reducing number of compared
  334.     add.w    d4,d4            ;strings down to 2%
  335.     move.w    0(a2,d4.w),d0        ;when the last byte is not
  336.     sub.l    d0,a5            ;matching, take next match
  337.     cmp.l    d2,a5            ;immediately
  338.     bcs.b    c_ret
  339.     cmp.b    0(a5,d3.w),d5
  340.     dbeq    d1,.c_nb
  341.     beq.b    .c_next
  342. c_ret
  343.     movem.l    (a7)+,COMPRESSREGS
  344. c_ret1
  345.     subq.w    #2,d3
  346.     bne.b    .c_ret3
  347.     move.l    d3,d0            ;if we found match length=2
  348.     add.l    #$fe000000,d0        ;we need only offsets <512 bytes
  349. .c_ret3    rts
  350.  
  351. ;-----------------------------------------------
  352. ;      Write Match Length            
  353. ;Input   : match length in d0    
  354. ;Results : write bit representation of d0    
  355. ;Destroy : d0, d1, d2, d4
  356. ;-----------------------------------------------
  357. ;to be fast - 0-15 taken from table
  358. table1    dc.b    %00000000,1        ;0
  359.     dc.b    %01000000,1        ;1
  360.     dc.b    %10000000,2        ;2
  361.     dc.b    %10100000,2        
  362.     dc.b    %11000000,4
  363.     dc.b    %11001000,4
  364.     dc.b    %11010000,4
  365.     dc.b    %11011000,4
  366.     dc.b    %11100000,6
  367.     dc.b    %11100010,6
  368.     dc.b    %11100100,6
  369.     dc.b    %11100110,6
  370.     dc.b    %11101000,6
  371.     dc.b    %11101010,6
  372.     dc.b    %11101100,6
  373.     dc.b    %11101110,6        ;15
  374.  
  375. write_match_lenght
  376.     moveq    #16,d1
  377.     move.l    d0,d2
  378.     add.w    d0,d0
  379.     move.w    table1(pc,d0.w),d0
  380.     sub.l    d1,d2
  381.     bcs.b    count1
  382.     moveq    #16,d0
  383.     moveq    #3,d1
  384.     moveq    #5,d4
  385.     bra.b    count3
  386. count2    moveq    #4,d0
  387.     moveq    #6,d1
  388.     moveq    #3,d4
  389. count3    sub.l    d0,d2
  390.     bcs.b    count4
  391.     addq.l    #1,d1
  392.     addq.l    #1,d4
  393.     add.l    d0,d0
  394.     bra.b    count3
  395. count4    add.l    d0,d2
  396.     ror.l    d4,d2
  397.     moveq    #-1,d0
  398.     bsr.b    compis
  399.     move.l    d2,d0
  400.     move.l    d4,d1
  401.     subq.w    #1,d1
  402.     bra.b    compis
  403.  
  404. ;-----------------------------------------------
  405. ;     Write Length of Uncompressed Bytes
  406. ;Input   : number of uncompressed bytes in d0
  407. ;Results : write bit representation of d0    
  408. ;Destroy : d0, d1, d2, d4
  409. ;-----------------------------------------------
  410. ;to be fast - 0-7 taken from table
  411.  
  412. table2    dc.b    %00000000,0        ;0
  413.     dc.b    %10000000,1
  414.     dc.b    %11000000,2
  415.     dc.b    %11100000,3
  416.     dc.b    %11110000,4
  417.     dc.b    %11111000,5
  418.     dc.b    %11111100,7
  419.     dc.b    %11111101,7        ;7
  420.  
  421. write_uncompressed
  422.     moveq    #8,d1
  423.     move.l    d0,d2
  424.     add.w    d0,d0
  425.     sub.l    d1,d2
  426.     bcc.b    count2
  427.     move.w    table2(pc,d0.w),d0
  428. count1    move.b    d0,d1
  429.     swap    d0
  430.  
  431. ;-----------------------------------------------
  432. ;     Write bits in bit stream
  433. ;Inputs  : bits in D0, number of bits in D1
  434. ;Results : d0 is written in bit stream
  435. ;Destroy : d0,d1
  436. ;-----------------------------------------------
  437.  
  438. compis    tst.b    d6
  439.     bne.b    .comp2
  440. .comp1    move.l    a1,a6
  441.     addq.l    #1,a1
  442.     moveq    #1,d6
  443. .comp2    add.l    d0,d0
  444.     addx.b    d6,d6
  445.     bcc.b    .comp3
  446.     move.b    d6,(a6)
  447.     dbra    d1,.comp1
  448.     moveq    #0,d6
  449.     rts
  450. .comp3    dbra    d1,.comp2
  451.     rts
  452.  
  453. ;-----------------------------------------------
  454. ;dekomprese
  455.  
  456. ;a3 used for fast jumping into subrutines
  457. ;a2 used for tables
  458. ;a1 destination
  459. ;a0 source
  460.  
  461. ;d0,d1,d2 scratch
  462. ;d3 byte acumulator
  463. ;d4 end of file
  464.  
  465. ByteBuf    EQUR    D3
  466.  
  467. ;macro for moving bytes
  468. BYTE_MOVE    MACRO
  469.          move.b    (a0)+,(a1)+
  470.         ENDM
  471. ;macro for getting next bit    
  472. NEXTBIT        MACRO
  473.          add.b    ByteBuf,ByteBuf
  474.          bne.b    .\@
  475.          move.b    (a0)+,ByteBuf
  476.          addx.b    ByteBuf,ByteBuf
  477. .\@
  478.         ENDM
  479. ;macro for getting bits - number is in D1, bits are stored in \1 register        
  480. GETXBITS    MACRO
  481.           moveq    #0,\1            ;subrutine - GetXBites from file
  482. .\@loop          NEXTBIT
  483.          addx.w    \1,\1
  484.          dbra    d1,.\@loop
  485.         ENDM
  486.  
  487. str
  488.     IFEQ    SO
  489. .loop0    btst    #6,$bfe001
  490.     bne.b    .loop0
  491.     move.l    #uklad,a1
  492.     move.l    #endcode,d0
  493.     addq.l    #7,d0
  494.     moveq    #$fffffffc,d1
  495.     and.l    d1,d0
  496.     move.l    d0,a0
  497.     move.l    celkove,d0
  498.     addq.l    #3,d0
  499.     and.l    d1,d0
  500.     add.l    d0,a1
  501.     lsr.l    #2,d0
  502.     subq    #1,d0
  503.     swap    d0
  504. .loop1    swap    d0
  505. .loop2    move.l    -(a1),-(a0)
  506.     dbra    d0,.loop2
  507.     swap    d0
  508.     dbra    d0,.loop1
  509.     move.l    #source,a1
  510.     move.l    #endcode,d4
  511.     bra.w    UnPack_It
  512.     ENDIF
  513. ;--------------------------------
  514. ;start of main decompress rutine
  515.     cnop    0,4
  516. UNCOMPRESSREGS    reg    d0-d4/a2-a5
  517.  
  518. UnPack_It
  519.     movem.l    UNCOMPRESSREGS,-(a7)
  520.     lea    tab0-4(pc),a4
  521.     lea    tab1-4(pc),a5
  522.  
  523.     moveq    #-128,ByteBuf        ; starting buffer - empty + Carry
  524. looping    NEXTBIT
  525.     bcc.b    cont
  526.     NEXTBIT
  527.     bcc.b    mov1
  528.     NEXTBIT
  529.     bcc.b    mov2
  530.     NEXTBIT
  531.     bcc.b    mov3
  532.     NEXTBIT
  533.     bcc.b    mov4
  534.     NEXTBIT
  535.     bcc.b    mov5
  536.  
  537. ;    lea    tab0-4(pc),a2
  538.     move.l    a4,a2            ;get number of uncompressed bytes
  539. .loop    addq.l    #4,a2
  540.     NEXTBIT
  541.     bcs.b    .loop
  542.     move.w    (a2)+,d1
  543.  
  544. ;    lea    cont1(pc),a3
  545. ;    bra.b    GetXB
  546.     GETXBITS d0
  547. cont1    add.w    (a2),d0
  548. .loop    BYTE_MOVE            ;transfer uncompressed bytes
  549.     dbra    d0,.loop
  550. mov5    BYTE_MOVE
  551. mov4    BYTE_MOVE
  552. mov3    BYTE_MOVE
  553. mov2    BYTE_MOVE
  554. mov1    BYTE_MOVE
  555.  
  556. cont    NEXTBIT                ;get match length
  557.     bcs.b    more_than_three
  558. less    NEXTBIT
  559.     bcs.b    three_bytes
  560.     moveq    #8,d1            ;9 bits offset
  561.     moveq    #0,d2            ;0+2 bytes for match length
  562.     bra.b    GetOffs            ;get offset
  563. three_bytes
  564.     moveq    #1,d2            ;1+2 bytes for match length
  565.     bra.b    Offset            ;get offset
  566. more_than_three
  567. ;    lea    tab1-4(pc),a2
  568.     move.l    a5,a2
  569. .loop    addq.l    #4,a2
  570.     NEXTBIT
  571.     bcs.b    .loop
  572.     move.w    (a2)+,d1
  573. ;    lea    cont2(pc),a3
  574. ;    bra.b    GetXB
  575. cont2    GETXBITS d2
  576.     add.w    (a2),d2            ;d2 - number of compressed bytes
  577.  
  578. Offset    moveq    #2,d1            ;count offset
  579. ;    lea    cont3(pc),a3
  580. ;    bra.b    GetXB
  581.     GETXBITS d0
  582. cont3    add.w    d0,d0
  583.     add.w    d0,d0
  584.     move.l    tab2(pc,d0.w),d1
  585.  
  586. GetOffs
  587. ;    lea    cont4(pc),a3
  588. ;GetXB    moveq    #0,d0            ;subrutine - GetXBites from file
  589. ;.loop    NEXTBIT
  590. ;    addx.l    d0,d0
  591. ;    dbra    d1,.loop
  592. ;    jmp    (a3)
  593.     GETXBITS d0
  594. cont4    swap    d1
  595.     add.w    d1,d0
  596.     
  597.     move.l    a1,a3
  598.     sub.l    d0,a3            ;MSW D0 is 0 - no problem with .l
  599. .loop    move.b    (a3)+,(a1)+        ;transfer bytes from buffer
  600.     dbra    d2,.loop
  601.     move.b    (a3)+,(a1)+
  602.     cmp.l    a1,d4            ;is it end of file?
  603.     bhi.w    looping
  604.     movem.l    (a7)+,UNCOMPRESSREGS    
  605.     IFEQ    SO
  606.     move.l    celkove,d0
  607.     ENDIF
  608.     rts
  609.  
  610. ;table for offset
  611. tab2    dc.l    $00000004,$00200006,$00a00008,$02a00009
  612.     dc.l    $06a0000a,$0ea0000b,$1ea0000c,$3ea0000d
  613.  
  614. ;table for match length    (max.is 1024 bytes)
  615. tab1    dc.l    $00000002,$00010004,$00020008,$00030010
  616.     dc.l    $00040020,$00050040,$00060080,$00070100
  617.     dc.l    $00080200,$00090400
  618.     
  619. ;table for length of uncompressed bytes    
  620. tab0    dc.w     0,$0000, 1,$0002, 2,$0006, 3,$000e
  621.     dc.w     4,$001e, 5,$003e, 6,$007e, 7,$00fe
  622.     dc.w     8,$01fe, 9,$03fe,$a,$07fe,$b,$0ffe
  623.     dc.w    $c,$1ffe,$d,$3ffe,$e,$7ffe,$f,$fffe
  624.  
  625. ;+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
  626.  
  627.     IFEQ    1 2
  628.  
  629. ; Currently not used in this program
  630. ;21:27        93.12.11
  631. ;Hufman static encoding
  632. ;d7 lenght of the file
  633. ;a0 start of file
  634. ;a1 start of tables
  635. ;memory map
  636. ;TABLE bytes -> longwords    /1KB table of indexs
  637. ;compressed tree        /1KB frequence
  638. ;buffer                /1KB copy of frequency/tree - sons
  639. ;                /1KB tree - fathers
  640. ;st
  641. ;    move.l    #konec-soubor,d7
  642. ;    lea    soubor(pc),a0
  643.  
  644.     lea    table(pc),a1
  645.  
  646.     add.l    #$1000,a1    ;clear tables
  647.     move.l    #$2ff,d0
  648.     moveq    #0,d1
  649. .cleart    move.l    d1,-(a1)
  650.     dbra    d0,.cleart
  651.     subq.b    #1,d1
  652. .make    move.l    d1,-(a1)    ;initialize index-table
  653.     dbra    d1,.make
  654.  
  655.     move.l    d7,d0
  656.     subq.l    #1,d0
  657.     move.l    a1,a2
  658.     add.l    #$400,a2
  659.     swap    d0
  660. .count0    swap    d0
  661. .count1    moveq    #0,d1        ;frequency of bytes
  662.     move.b    (a0)+,d1
  663.     lsl.w    #2,d1
  664.     addq.l    #1,(a2,d1.w)
  665.     dbra    d0,.count1
  666.     swap    d0
  667.     dbra    d0,.count0
  668.  
  669. continue_huffman
  670.     move.l    uloa1,a1
  671.     move.l    uloa2,a2
  672.  
  673.     move.l    a2,a4
  674.     move.l    #ta,a3        ;pro strom delek
  675.     move.w    #$ff,d0
  676. ;.copyc    move.l    (a3)+,(a4)+
  677. ;    dbra    d0,.copyc
  678.  
  679.     move.l    a2,a3        ;copy into work partition
  680.     add.l    #$400,a3
  681.     move.w    #$ff,d0
  682. copycet    move.l    (a2)+,(a3)+
  683.     dbra    d0,copycet
  684. ;------------------------------------------------
  685. ; Now we'll build tree
  686. ;d0 various
  687. ;d1 big loop
  688. ;d2 small loop
  689. ;d3 first minimum
  690. ;d4 second minimum
  691. ;d5 position  1 min
  692. ;d6 position  2 min
  693. ;a1 start of tables - index
  694. ;a2 index table - moving in big loop
  695. ;a3 frequency
  696. ;a4 frequency moving in small loop
  697. ;a5 frequency moving in big loop
  698. ;a6 table of fathers
  699. ;------------------------------------------------
  700.     moveq    #0,d2        ;prepare registers
  701.     move.l    d2,d1
  702.     bset    #10,d1
  703.     move.l    a1,a2
  704.     move.l    a1,a3
  705.     add.l    d1,a3
  706.     add.l    d1,a3
  707.     move.l    a3,a5
  708.     move.l    a3,a6
  709.     add.l    d1,a6
  710.     lsr.w    #2,d1
  711.  
  712. make_tr0
  713.     move.l    #$7fffffff,d3    ;start of big loop
  714.     move.b    d1,d2
  715.     move.l    a5,a4
  716. make_tr1
  717.     move.l    (a4)+,d0    ;small loop
  718.     beq.s    make_tr3
  719.     cmp.l    d0,d3
  720.     ble.s    make_tr2    ;compare with first minimum
  721.     move.l    d3,d4
  722.     move.w    d5,d6
  723.     move.l    d0,d3
  724.     move.w    d2,d5
  725.     bra.s    make_tr3
  726. make_tr2
  727.     cmp.l    d0,d4
  728.     ble.s    make_tr3    ;otherwise with second minimum
  729.     move.l    d0,d4
  730.     move.w    d2,d6
  731. make_tr3
  732.     addq.b    #1,d2
  733.     bne.s    make_tr1    ;next in small loop
  734.  
  735.     add.l    d4,d3        ;now D4, D5 contains two minimums
  736.     bmi.s    make_trend
  737.     cmp.w    d5,d6        ;we need to be D5>D6
  738.     bcs.s    make_tr4
  739.     exg    d5,d6        ;if they aren't then swap them
  740. make_tr4
  741.     lsl.w    #2,d5
  742.     move.l    d3,(a3,d5.w)    ;new frequency
  743.     lsl.w    #2,d6
  744.     move.l    (a5),(a3,d6.w)
  745.     move.w    $02(a1,d6.w),d4
  746.     move.w    d4,(a5)+
  747.     move.b    d1,(a6,d4.w)    ;left son
  748.     move.w    $02(a1,d5.w),d4
  749.     move.w    d4,(a5)+
  750.     move.b    d1,(a6,d4.w)    ;right son
  751.     move.w    d1,$02(a1,d5.w)    ;new father
  752.     move.l    (a2)+,(a1,d6.w)
  753.  
  754.     addq.b    #1,d1
  755.     bne.s    make_tr0    ;next in big loop
  756. make_trend
  757.  
  758. ;------------------------------------------------
  759. ; Here we make short_cuts for each byte
  760. ;d0 temporary
  761. ;d1 main index
  762. ;d2 index for each byte
  763. ;d3 copy of index
  764. ;d4 for rotation
  765. ;d5 for counting roration
  766. ;d6 bit counter
  767. ;------------------------------------------------
  768. cuts
  769.     move.l    a1,a2
  770.     move.l    a2,a3
  771.     moveq    #0,d1
  772.     moveq    #0,d6
  773.     bset    #10,d1
  774.     add.l    d1,a3        ;frequency
  775.     move.l    a3,a4
  776.     add.l    d1,a4        ;sons
  777.     move.l    a4,a5
  778.     add.l    d1,a5        ;fathers
  779.     moveq    #0,d1
  780.     moveq    #0,d7        ;total lenght of packed file    
  781. cuts_loop1
  782.     moveq    #0,d3
  783.     moveq    #0,d4
  784.     moveq    #1,d5
  785.     move.b    (a5,d1.w),d3
  786.     move.w    d3,d0
  787.     bset    #8,d3
  788.     lsl.w    #2,d0
  789.     cmp.w    (a4,d0.w),d1
  790.     bne.s    cuts_loop3
  791.     bset    #31,d4
  792.     bra.s    cuts_loop3
  793. cuts_loop2
  794.     moveq    #0,d0
  795.     move.b    d3,d0
  796.     addq.b    #1,d5
  797.     lsr.l    #1,d4
  798.     lsl.w    #2,d0
  799.     cmp.w    (a4,d0.w),d2
  800.     bne.s    cuts_loop3
  801.     bset    #31,d4
  802. cuts_loop3
  803.     move.w    d3,d2
  804.     move.b    (a5,d3.w),d3
  805.     bne.s    cuts_loop2
  806.     move.b    d5,d4        ;length in bits into the lowest byte
  807.     move.l    (a3)+,d3    ;add to  new lenght of file
  808.     bne.s    cuts_l5
  809.     moveq    #0,d4
  810.     bra.b    cuts_l6
  811. cuts_l5    
  812.     add.w    d5,d6
  813. cuts_l6    subq.b    #1,d5
  814. cuts_l4    add.l    d3,d7
  815.     dbra    d5,cuts_l4
  816.     move.l    d4,(a2)+
  817.     addq.b    #1,d1
  818.     bne.s    cuts_loop1
  819.     lsr.l    #3,d7
  820.  
  821.     move.w    #255,d5
  822.     moveq    #0,d4
  823.     move.l    #t1,a0
  824. .lop    move.l    (a0)+,d0
  825.     add.w    d0,d4
  826.     dbra    d5,.lop
  827.     lsr.w    #3,d4
  828.     add.w    #128,d4
  829.  
  830.     move.l    celkove,d5
  831.     sub.l    bytneko,d5
  832.     add.l    d7,d5
  833.     add.l    d4,d5
  834.  
  835.     move.l    bitleng,d0
  836.     lsr.l    #3,d0
  837.     move.l    d0,bitleng
  838.     move.l    bitoffs,d0
  839.     lsr.l    #3,d0
  840.     move.l    d0,bitoffs
  841.     move.l    bitneko,d0
  842.     lsr.l    #3,d0
  843.     move.l    d0,bitneko
  844.     move.l    celkove,d0
  845.     rts
  846.  
  847. uloa1    dc.l    0
  848. uloa2    dc.l    0
  849.  
  850. table    ds.b    4096
  851.     
  852. t1    equ    table
  853. t2    equ    table+4*256
  854. t3    equ    table+8*256
  855. t4    equ    table+12*256
  856.  
  857. bitleng    dc.l    0
  858. bitoffs    dc.l    0
  859. bitneko    dc.l    0
  860. offslen    dc.l    0
  861. offssho    dc.l    0
  862. bytneko    dc.l    0
  863. bytkomp    dc.l    0
  864.  
  865.     ENDC
  866.  
  867.     IFEQ    SO
  868.  
  869. celkove    dc.l    0
  870.  
  871. ;-------------------------------
  872.  
  873. ta    ds.b    300*4
  874.  
  875. buf1str    ds.b    2*bufferlength        ;kvuli zapornym adresam
  876.  
  877. buf2str    ds.b    indexlength
  878.  
  879.     cnop    0,4
  880. u
  881. uklad    ds.b    $8000
  882. s
  883. source
  884.     incdir    'ram:'
  885.     incbin    "OneFont"
  886. endcode
  887.     dc.b    6,5,4,3,2,1,2,3,4,5,6,0,0,0,0,0
  888.  
  889.     ENDC
  890.