home *** CD-ROM | disk | FTP | other *** search
/ C!T ROM 5 / ctrom5b.zip / ctrom5b / PROGRAM / ASM / ALIB30B / SHRINK2.ASM < prev    next >
Assembly Source File  |  1994-11-24  |  10KB  |  329 lines
  1.     page    66,132
  2. ;******************************* SHRINK2.ASM *********************************
  3.         extrn    dos_mem_allocate:far
  4.         extrn    dos_mem_release:far
  5.  
  6.         public    compress
  7.  
  8.  
  9. CLEAR        equ    256        ;Clear code
  10. EOF        equ    257        ;End of file marker
  11. FIRST_FREE    equ    258        ;First free code
  12. MAXMAX        equ    4096        ;Max code + 1
  13. BUFFER_SIZE    equ    1024
  14.  
  15. hash_rec    struc
  16. first    dw    ?            ; First entry with this value
  17. next    dw    ?            ; Next entry along chain
  18. char    db    ?            ; Suffix char
  19. hash_rec    ends
  20. ;----------------------------------------------------------------------------
  21. .xlist
  22.     include  mac.inc
  23. .list
  24. ;--------------------------------------------------------------------
  25.  
  26. data_    struc
  27.  
  28. hash        db    20480 dup (?)
  29.  
  30. feed_process    dd    ?
  31. store_process    dd    ?
  32.  
  33. feed_buffer    db    BUFFER_SIZE dup (?)    ;buffer filled externally
  34. feed_ptr    dw    ?
  35. feed_available    dw    ?
  36.  
  37. store_buffer    db    BUFFER_SIZE dup (?)    ;buffer filled internally
  38. store_ptr    dw    ?
  39. partial_bit_count dw    ?            ;bits beyond store_ptr
  40.  
  41. prefix_code    dw    ?
  42. free_code    dw    ?
  43. max_code    dw    ?
  44. max_bits    dw    ?
  45. k        db    ?
  46.  
  47. data_    ends
  48. ;----------------------------------------------------------------------------
  49.  
  50. LIBSEG           segment byte public 'LIB'
  51.     assume    CS:LIBSEG,DS:nothing,ES:nothing
  52. comment 
  53. ;- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -(COMPRESS )
  54. compress - compress data block using limpel-ziev algorithm
  55. ;  inputs:  es:si = feed function ptr
  56. ;           es:di = store function ptr
  57. ;
  58. ;  output:  feed function is called when data to be compressed is
  59. ;           needed. Feed uses the following parameters:
  60. ;           in: ds:dx = buffer ptr of size (BUFFER_SIZE)
  61. ;                  ax = requested amount
  62. ;           out:   ax = number of bytes placed in buffer, 0=end of input
  63. ;          
  64. ;           store function is called when a block of compressed data
  65. ;           is prepared. Store uses the following parameters:
  66. ;           in:  ds:dx = buffer ptr
  67. ;                ax = amount of data present in buffer
  68. ;           out:  none
  69. ;
  70. ; note:  The feed proceedure is called whenever the compress module runs
  71. ;        out of data.  The store module is called whenever more data is
  72. ;        needed.  Normally, the feed and store data uses a disk file, but
  73. ;        if room it could be placed in memory.
  74. ;        The feed and store modules must restore any registers they
  75. ;        modify.  Specifically, si,di,bp,ds,es
  76. ;
  77. ; note:  compress and decompress work together and the functions
  78. ;        shrink and expand work together.  Compress and decompress
  79. ;        are much faster and smaller code, but do not produce quite
  80. ;        as good compression.
  81. ;
  82. ;                       execution time          code size
  83. ;                       ---------------         ----------
  84. ;        compress            1.75                  430
  85. ;        decompress           .87                  381
  86. ;
  87. ;        shrink             10.05                  1447
  88. ;        expand              1.54                  1447       
  89. ;* * * * * * * * * * * * * *
  90. 
  91.  
  92. compress    proc    far
  93.     push    es
  94.     mov    dx,0
  95.     mov    ax,size data_
  96.     call    dos_mem_allocate
  97.     mov    ax,es
  98.     mov    ds,ax
  99.     pop    es
  100.     jc    error_exit
  101.         mov    word ptr ds:[feed_process],si
  102.         mov    word ptr ds:[store_process],di
  103.         mov    word ptr ds:[feed_process+2],es
  104.         mov    word ptr ds:[store_process+2],es
  105.         mov    es,ax
  106. ;
  107. ; setup the buffer ptrs
  108. ;
  109.     mov    ds:[feed_ptr],offset feed_buffer
  110.     mov    ds:[feed_available],0
  111.     mov    ds:[store_ptr],offset store_buffer
  112.     mov    ds:[partial_bit_count],0
  113.     
  114.        call    init_table        ;Initialize the table and some vars
  115.     mov    ax,CLEAR        ;Write a clear code
  116.     call    write_code
  117.     call    read_char        ;Read first char
  118. c_lp1:    xor    ah,ah            ;Turn char into code
  119. c_lp2:    mov    ds:[prefix_code],ax        ;Set prefix code
  120.     call    read_char        ;Read next char
  121.     jc    c_end1            ;Carry means EOF
  122.     mov    ds:[k],al            ;Save char in k
  123.     mov    bx,ds:[prefix_code]        ;Get prefix code
  124.     call    lookup_code        ;See if this pair in table
  125.     jnc    c_lp2            ;nc means yes, new code in ax
  126.     call    add_code        ;Add pair to table
  127. ;;    push    bx            ;Save new code
  128.     mov    ax,ds:[prefix_code]        ;Write old prefix code
  129.     call    write_code
  130. ;;    pop    bx
  131.     mov    al,ds:[k]            ;Get last char
  132.     cmp    bx,ds:[max_code]        ;Exceed code size?
  133.     jl    c_lp1            ;less means no
  134.     cmp    ds:[max_bits],12        ;Currently less than 12 bits?
  135.     jl    c_tail            ;yes
  136.      mov    ax,CLEAR        ;Write a clear code
  137.      call    write_code
  138.      call    init_table        ;Reinit table
  139.      mov    al,ds:[k]            ;get last char
  140.      jmp    c_lp1            ;Start over
  141.  
  142. c_tail:    inc    ds:[max_bits]            ;Increase number of bits
  143.     shl    ds:[max_code],1        ;Double max code size
  144.     jmp    c_lp1            ;Get next char
  145.  
  146. c_end1:    mov    ax,ds:[prefix_code]        ;Write last code
  147.     call    write_code
  148.     mov    ax,EOF            ;Write EOF code
  149.     call    write_code
  150.     cmp    ds:[partial_bit_count],0
  151.     je    c_end2
  152.     inc    ds:[store_ptr]        ;flush partial bits
  153. c_end2:    call    flush_outbuf
  154.     call    dos_mem_release
  155.     clc
  156. error_exit:
  157.            retf
  158. compress    endp
  159. ;-----------------------------------------------------------------------
  160. ; write_code - build code for output
  161. ;  inputs:  ax = data
  162. ;           partial_bit_count = partial bits in last byte of buffer
  163. ;           nbits = number of bits to add
  164. ;           store_ptr = ptr into store_buffer
  165. ;  output: ax,cx,dx,si,di modified
  166. ;
  167. write_code:
  168.     mov    di,ds:[store_ptr]
  169.     xor    dx,dx
  170.     mov    cx,ds:[partial_bit_count]
  171.     mov    si,cx            ;save partial_bit_count
  172.     jcxz    wc_out            ;jmp if on even byte boundry
  173. bit_lp:    shl    ax,1
  174.     rcl    dx,1            ;position new data
  175.     loop    bit_lp
  176.     or    al,byte ptr [di]    ;merge in new bits
  177. wc_out:    stosw                ;store new data
  178.     mov    byte ptr es:[di],dl    ;store partial byte
  179. ;
  180. ; update ptr's
  181. ;
  182.     xor    dx,dx
  183.     mov    ax,ds:[max_bits]
  184.     add    ax,si            ;nbits + partial_bit_count
  185.     mov    cx,8
  186.     div    cx            ;compute # new bytes stored
  187.     mov    ds:[partial_bit_count],dx
  188.     add    ds:[store_ptr],ax
  189. ;
  190. ; check if time to flush buffer
  191. ;
  192.     cmp    di,offset store_buffer + (BUFFER_SIZE -4)
  193.     jb    wc_done            ;jmp if buffer ok
  194. ;
  195. ; buffer is close to full, flush it
  196. ;
  197.     call    flush_outbuf
  198. wc_done:ret
  199.  
  200. ;------------------------------------------------------------------------
  201. ; read_char - get next data byte
  202. ;  inputs: none
  203. ;  output: carry = eof
  204. ;          no carry, al=data
  205. ;                    si,di modified
  206. ;
  207. read_char:    dec    ds:[feed_available]
  208.         jns    loc_88x                ;jmp if data avail
  209.         call    fill_inbuf            ;fill the buffer
  210.         jc    rc_exit2            ;jmp if out of data
  211.         jmp    read_char
  212. loc_88x:    mov    si,ds:[feed_ptr]
  213.             lodsb                    ;get next byte
  214.         mov    ds:[feed_ptr],si
  215. rc_exit1:       clc
  216. rc_exit2:       ret
  217. ;-------------------------------------------------------------------------
  218. ; lookup_code - convert data to code
  219. ;  inputs:  bx = data
  220. ;  output:  carry = no code
  221. ;           no carry, ax=code
  222. ;                     di=flag
  223. ;                     si modified
  224. ;
  225. lookup_code:
  226.     call    index            ;convert code to address
  227.     xor    di,di                ;flag
  228.     cmp    [si].first,-1        ;Has this code been used?
  229.     je    gc4            ;equal means no
  230.     inc    di            ;set flag
  231.     mov    bx,[si].first        ;Get first entry
  232. gc2:    call    index            ;convert code to address
  233.     cmp    [si].char,al        ;is char the same?
  234.     jne    gc3            ;ne means no
  235. ;;    clc                ;success
  236.     mov    ax,bx            ;put found code in ax
  237.     ret                ;done
  238.  
  239. gc3:    cmp    [si].next,-1        ;More left with this prefix?
  240.     je    gc4            ;equal means no
  241.     mov    bx,[si].next        ;get next code
  242.     jmp    gc2            ;try again
  243.  
  244. gc4:    stc                ;not found
  245.     ret                ;done
  246. ;---------------------------------------------------------------------
  247. ; index - index into hash table
  248. ;  inputs: bx = code
  249. ;  output: si = hash ptr
  250. ;
  251. index:    mov    si,bx            ;si = bx * 5 (5 byte hash entries)
  252.     shl    si,1            ;si = bx * 2 * 2 + bx
  253.     shl    si,1
  254.     add    si,bx
  255.     ret
  256. ;-----------------------------------------------------------------------
  257. ; add_code to table
  258. ;  inputs:  di = flag, first use of prefix
  259. ;           si = hash table ptr
  260. ;
  261. add_code:
  262.     mov    bx,ds:[free_code]        ;Get code to use
  263.     or    di,di               ;First use of this prefix?
  264.     je    ac1            ;equal means yes
  265.     mov    [si].next,bx        ;point last use to new entry
  266.     jmp    short ac2
  267.  
  268. ac1:    mov    [si].first,bx        ;Point first use to new entry
  269. ac2:    cmp    bx,MAXMAX        ;Have we reached code limit?
  270.     je    ac3            ;equal means yes, just return
  271.     call    index            ;get address of new entry
  272.     mov    [si].first,-1        ;initialize pointers
  273.     mov    [si].next,-1
  274.     mov    [si].char,al        ;save suffix char
  275.     inc    ds:[free_code]        ;adjust next code
  276. ac3:    ret
  277. ;--------------------------------------------------------------------------
  278. ; fill_inbuf - fill the input buffer
  279. ;  inputs: none
  280. ;  output: carry set if end of data
  281. ;
  282. fill_inbuf:                ;!!! warning instruction mod here
  283.     apush    bx
  284.     mov    dx,offset feed_buffer
  285.     mov    ds:[feed_ptr],dx        ;restart the ptr
  286.     mov    ax,BUFFER_SIZE        ;get requested amount
  287.     call    dword ptr ds:[feed_process]
  288.     or    ax,ax
  289.     jnz    fill_ok
  290.     stc
  291.     jmp    fill_exit
  292. fill_ok:clc
  293.     mov    word ptr ds:[feed_available],ax    ;zero only if data was found
  294. fill_exit:
  295.     apop    bx
  296.     ret
  297. ;--------------------------------------------------------------------------
  298. ; flush_outbuf - ship the full buffer off to caller
  299. ;  inputs: none
  300. ;  output: none
  301. ;
  302. flush_outbuf:
  303.     mov    ax,ds:[store_ptr]
  304.     mov    dx,offset store_buffer
  305.     sub    ax,dx                ;compute flush size
  306.     call    dword ptr ds:[store_process]
  307.     mov    di,offset store_buffer        ;move partial
  308.     mov    si,ds:[store_ptr]            ;  data back
  309.     mov    ds:[store_ptr],di
  310.     movsb
  311.     ret
  312. ;--------------------------------------------------------------------
  313. ; init_table - setup table 
  314. ;   inputs: none
  315. ;
  316. init_table:
  317.     mov    ds:[max_bits],9            ;Set code size to 9
  318.     mov    ds:[max_code],512        ;Set max code to 512
  319.     mov    ax,-1            ;Unused flag
  320.     mov    cx,(size hash_rec)*256    ;Clear first 256 entries
  321.     mov    di,offset hash        ;Point to first entry
  322.     rep    stosw            ;Clear it out
  323.     mov    ds:[free_code],FIRST_FREE    ;Set next code to use
  324.     ret                ;done
  325.  
  326. LIBSEG    ends
  327.  
  328. ;    end    start
  329.