home *** CD-ROM | disk | FTP | other *** search
/ back2roots/padua / padua.7z / padua / ftp.vapor.com / microdot-1 / md1_src_02.lzx / comp.a < prev    next >
Text File  |  1989-06-24  |  11KB  |  358 lines
  1.         include 'include:exec/types.i'
  2.  
  3.     section    "text",code
  4.  
  5. STARTBITS       equ     9
  6. MINBITS         equ     9
  7. MAXBITS         equ     15
  8. BYTESPERTABENT  equ     6
  9. SOURCEBITS      equ     8
  10.  
  11.         xdef    _GenCompress,_GenCompTableSize
  12.  
  13.         STRUCTURE stackframe,0
  14.     UWORD ss_IncCode      ; Last code before incrementing table size
  15.     UWORD ss_PrevRatio    ; Revious compression ratio
  16.     ULONG ss_MaxDest      ; Pointer past end of destination
  17.     ULONG ss_Dest         ; Pointer to destination stream
  18.     UWORD ss_TabSize      ; Compression table size
  19.     UWORD ss_MaxString    ; Max string size
  20.     UWORD ss_MaxBits      ; Max number of compression bits
  21.     UWORD ss_pad          
  22.     ULONG ss_SMarker      ; Source marker for compression ratio checking
  23.     ULONG ss_DMarker      ; Dest marker
  24.     LABEL ss_Size
  25.  
  26. *** GenCompress - General LZW compression routine - compress any byte stream
  27. * d0.l = Length of source
  28. * d1.l = Maximum number of bits to compress with
  29. * a0 = Pointer to source byte stream
  30. * a1 = Pointer to destination area (at least as big as source)
  31. * a2 = Pointer to an area for the hash tables, of size found with gentablesize
  32. * Returns: d0 = Total byte size of compressed data, null if the data did not compress
  33. _GenCompress
  34.         movem.l d2-d7/a2-a6,-(sp)
  35. ;        lea     -ss_Size(sp),sp
  36.         sub.w    #ss_Size,sp
  37.  
  38.        moveq   #$7f,d2                 ; Refuse to compress insultingly small streams...
  39.        cmp.l   d2,d0
  40.        bls     outerr
  41.  
  42.         move.l  a1,ss_Dest(sp)         ; Save original dest to find final length later
  43.  
  44.         move.l  d0,d2                   ; Find max destination address
  45.         andi.w  #$ffe0,d2
  46.         add.l   d2,a1
  47.         lea     -8(a1),a3               ; Safety margin
  48.         move.l  a3,ss_MaxDest(sp)
  49.  
  50.         lsr.l   #5,d2                   ; Clear entire destination
  51.         subq.l  #1,d2
  52.         move.l  d2,d3
  53.         swap    d3
  54.         moveq   #0,d4
  55.         moveq   #0,d5
  56.         moveq   #0,d6
  57.         moveq   #0,d7
  58.         move.l  d4,a3
  59.         move.l  d5,a4
  60.         move.l  d6,a5
  61.         move.l  d7,a6
  62. 1$      movem.l d4-d7/a3-a6,-(a1)
  63.         dbra    d2,1$
  64.         dbra    d3,1$
  65.  
  66.         move.l  a2,a5                   ; Hash table pointer (a5)
  67.  
  68.         lea     hashentstab(pc),a3     ; Find the hash table size (d2)
  69.         move.l  d1,d2
  70.         add.w   d2,d2
  71.         move.w  -MINBITS*2(a3,d2.w),d2
  72.         move.w  d2,ss_TabSize(sp)      ; Save a copy of the table size
  73.  
  74.         add.l   d2,d2                   ; table size * 6 (a2)
  75.         move.l  d2,a2
  76.         add.l   d2,a2
  77.         add.l   d2,a2
  78.  
  79.         move.w  d1,ss_MaxBits(sp)      ; Save MaxBits
  80.  
  81.         subq.w  #SOURCEBITS,d1          ; Calculate HashCharShift (a6)
  82.         move.w  d1,a6
  83.  
  84.         addq.w  #4,a1                   ; Room for max bits and max string length
  85.  
  86.         moveq   #32,d2                  ; Initial bitcount (d2)
  87.  
  88.         clr.w   ss_MaxString(sp)       ; Clear MaxString
  89.  
  90.         moveq   #0,d5                   ; Clear high bits of d5
  91.  
  92. resetloop
  93.         move.l  a5,a3                   ; Invalidate the append_char entries
  94.         moveq   #-1,d7
  95.         move.w  ss_TabSize(sp),d6
  96.         subq.w  #1,d6
  97. .clr
  98.         move.w  d7,(a3)
  99.         addq    #6,a3
  100.         dbra    d6,.clr
  101.  
  102.         move.w  #1<<SOURCEBITS+3,d3     ; Initial nextcode (d3.w)
  103.         move.w  #STARTBITS,a3           ; Initial outbits (a3)
  104.         move.w  #1<<STARTBITS,ss_IncCode(sp) ; Initial inccode
  105.  
  106.         moveq   #0,d4                   ; Initial string_code (d4)
  107.         move.b  (a0)+,d4
  108.         subq.l  #1,d0                   ; One less byte to munch
  109.  
  110.         moveq   #4,d1                   ; Init string size (with safety margin)
  111.         bra.b   loop
  112.  
  113. bounceout
  114.         bra     out
  115.  
  116. found                                   ; String found
  117.         move.w  4(a5,d6.l),d4
  118.         addq.w  #1,d1
  119.  
  120. loop
  121.         subq.l  #1,d0                   ; One less byte to munch
  122.         bmi.b   bounceout
  123.  
  124.         move.b  (a0)+,d5                ; Get next character (d5)
  125.  
  126. findmatch
  127.         move.l  d5,d6                   ; Find the hash table entry (d6)
  128.         move.w  a6,d7
  129.         asl.w   d7,d6
  130.         eor.w   d4,d6
  131.         add.l   d6,d6                   ; Offset (d6) = index * 6
  132.         move.l  d6,d7
  133.         add.l   d6,d6
  134.         add.l   d7,d6
  135.  
  136.         move.l  0(a5,d6.l),d7           ; See if this entry is unused
  137.         bmi.b   notfound
  138.         cmp.w   d7,d4                   ; See if it contains the right code
  139.         bne.b   1$
  140.         swap    d7
  141.         cmp.w   d7,d5
  142.         beq.b   found
  143. 1$
  144.         move.l  d6,a4                   ; Find negative index (a4)
  145.         sub.l   a2,a4
  146.         addq.w  #6,a4
  147.  
  148.         add.l   a4,d6                   ; Find the next appropriate entry
  149.         bpl.b   .hunt
  150.         add.l   a2,d6
  151.  
  152. .hunt
  153.         move.l  0(a5,d6.l),d7          ; See if this entry is unused
  154.         bmi.b   notfound
  155.         cmp.w   d7,d4                   ; See if it contains the right code
  156.         bne.b   .notthis
  157.         swap    d7
  158.         cmp.w   d7,d5
  159.         beq.b   found
  160. .notthis
  161.         add.l   a4,d6                   ; Find the next appropriate entry
  162.         bpl.b   .hunt
  163.         add.l   a2,d6
  164.         bra.b   .hunt
  165.  
  166. notfound:
  167.         cmp.w   ss_MaxString(sp),d1    ; See if we've set a new record
  168.         bls.b   2$
  169.         move.w  d1,ss_MaxString(sp)
  170. 2$
  171.         lea     4(a5,d6.l),a4          ; Add a new hash table entry
  172.         move.w  d3,(a4)
  173.         bmi.b   tabfull
  174.         move.w  d4,-(a4)
  175.         move.w  d5,-(a4)
  176. ;        movem.w    d4/d5,-(a4)
  177.  
  178.         addq.w  #1,d3                   ; Find the next code
  179.  
  180.         cmp.w   ss_IncCode(sp),d3      ; See if we've passed a boundary
  181.         bhs.b   pastbound
  182.  
  183. outnew:
  184.         move.l  d4,d7                   ; Output a new code
  185.         move.l  d5,d4
  186.  
  187.         sub.w   a3,d2                   ; Find the bit position
  188.         bpl.b   1$
  189.         addq.w  #2,a1
  190.         cmpa.l  ss_MaxDest(sp),a1
  191.         bge.b   outerrbounce
  192.         addq.w  #8,d2
  193.         addq.w  #8,d2
  194. 1$
  195.         asl.l   d2,d7                   ; Insert the code into the bit stream
  196.         or.l    d7,(a1)
  197.  
  198.         moveq   #4,d1                   ; Reset string size
  199.         bra   loop
  200.  
  201. outerrbouncepop
  202.         addq    #4,sp
  203. outerrbounce
  204.         bra     outerr
  205.  
  206. outcode:
  207.         sub.w   a3,d2                   ; Find the bit position
  208.         bpl.b   1$
  209.         addq.w  #2,a1
  210.         cmpa.l  4+ss_MaxDest(sp),a1
  211.         bge.b   outerrbouncepop
  212.         addq.w  #8,d2
  213.         addq.w  #8,d2
  214. 1$
  215.         asl.l   d2,d7                   ; Insert the code into the bit stream
  216.         or.l    d7,(a1)
  217.         rts
  218.  
  219. pastbound:
  220.         cmpa.w  ss_MaxBits(sp),a3      ; Check for entire table full
  221.         beq.b   settabfull
  222.  
  223. outcheck:
  224.         cmp.w   ss_IncCode(sp),d4      ; See if we're about to output a too-big code
  225.         blo.b   outnew
  226.  
  227.         move.l  #1<<SOURCEBITS+2,d7     ; Output an increment-code-size code
  228.         bsr.b   outcode
  229.  
  230.         addq.w  #1,a3                   ; Increase code size
  231.         asl.w   ss_IncCode(sp)
  232.  
  233.         bra.b   outnew                  ; Now output the new code
  234.  
  235. settabfull:
  236.         move.l  ss_Dest(sp),a4         ; Set the header to maximum number of bits
  237.         move.w  ss_MaxBits(sp),(a4)
  238.  
  239.         moveq   #-1,d3                  ; Flag that the table is full
  240.  
  241.         move.l  a0,ss_SMarker(sp)      ; Set the markers
  242.         move.l  a1,ss_DMarker(sp)
  243. ;        movem.l    a0/a1,ss_SMarker(sp)
  244.         clr.w   ss_PrevRatio(sp)
  245.  
  246.         bra.b   outnew
  247.  
  248. tabfull:
  249.         subq.b  #1,d3                   ; Count out 256 codes
  250.         bne.b   outnew
  251.  
  252.         ; FIXME: Try just using DMarker
  253.         move.l  a0,d6                   ; Compute the compression ratio
  254.         sub.l   ss_SMarker(sp),d6
  255.         asl.l   #8,d6
  256.         move.l  a1,d7
  257.         sub.l   ss_DMarker(sp),d7
  258.         divu.w  d7,d6
  259.         cmp.w   ss_PrevRatio(sp),d6    ; See if it dropped
  260.         blo.b   cleartab
  261.  
  262.         move.l  a0,ss_SMarker(sp)      ; Reset the markers
  263.         move.l  a1,ss_DMarker(sp)
  264. ;        movem.l    a0/a1,ss_SMarker(sp)
  265.         move.w  d6,ss_PrevRatio(sp)
  266.         bra     outnew
  267.  
  268. cleartab
  269.         moveq   #$7f,d6                 ; Don't clear the table if there's only a little more
  270.         cmp.l   d6,d0
  271.         bls     outnew
  272.  
  273.         move.l  d4,d7                   ; Finish up the last two codes
  274.         bsr     outcode
  275.         move.l  d5,d7
  276.         bsr     outcode
  277.  
  278.         move.l  #1<<SOURCEBITS+1,d7     ; Output a clear code
  279.         pea     resetloop(pc)
  280.         bra     outcode
  281.  
  282. out
  283.         cmp.w   ss_IncCode(sp),d4      ; See if the last code is too big
  284.         blo.b   .nottoobig
  285.  
  286.         move.l  #1<<SOURCEBITS+2,d7     ; Output an increment-code-size code
  287.         bsr     outcode
  288.  
  289.         addq.w  #1,a3                   ; Increase the code size one last time
  290. .nottoobig
  291.  
  292.         move.l  d4,d7                   ; Send out the last code
  293.         bsr     outcode
  294.  
  295.         move.l  #1<<SOURCEBITS,d7       ; Send the end-of-file code
  296.         bsr     outcode
  297.  
  298.         addq.w  #4,a1                   ; "Flush" the output buffer
  299.  
  300.         move.l  ss_Dest(sp),a0         ; Find original destination
  301.  
  302.         move.w  ss_MaxString(sp),d7    ; Save the maximum string length
  303.         andi.w  #$fffc,d7
  304.         move.w  d7,2(a0)
  305.  
  306.         tst.w   (a0)                    ; Record the largest number of bits used
  307.         bne.b   1$
  308.         move.w  a3,(a0)
  309. 1$
  310.         suba.l  a0,a1                   ; Find the compressed size
  311.         move.l  a1,d0
  312.  
  313. outt
  314. ;        lea     ss_Size(sp),sp         ; Pop the junk off the stack
  315.         add    #ss_Size,sp
  316.         movem.l (sp)+,d2-d7/a2-a6
  317.         rts
  318.  
  319. outerr
  320.         moveq   #0,d0                   ; Return an error
  321.         bra.b   outt
  322.  
  323. hashentstab
  324.         dc.w    641     ; 9 bits
  325.         dc.w    1283    ; 10 bits
  326.         dc.w    2579    ; 11 bits
  327.         dc.w    5147    ; 12 bits
  328.         dc.w    10243   ; 13 bits
  329.         dc.w    20483   ; 14 bits
  330.         dc.w    40961   ; 15 bits
  331.  
  332. *** GenCompTableSize - Find the compression table size required for a particular number of bits
  333. * d0.l = Maximum number of bits of compression
  334. * Returns: d0 = Size in bytes of required hash tables, zero if unsupported number of bits
  335. _GenCompTableSize:
  336.         sub.b   #MINBITS,d0             ; Check the range
  337.         blo.b   .err
  338.         moveq   #MAXBITS-MINBITS,d1
  339.         cmp.l   d1,d0
  340.         bhi.b   .err
  341.  
  342.         add.w   d0,d0                   ; Find the required number of entries
  343.   lea     hashentstab(pc),a0
  344.   move.w  0(a0,d0.w),d0
  345.  
  346.         add.l   d0,d0                   ; Table size = entries * 6
  347.         move.l  d0,d1
  348.         add.l   d0,d0
  349.         add.l   d1,d0
  350.  
  351.         rts
  352.  
  353. .err
  354.         moveq   #0,d0
  355.         rts
  356.  
  357.         end
  358.