home *** CD-ROM | disk | FTP | other *** search
/ C!T ROM 5 / ctrom5b.zip / ctrom5b / PROGRAM / ASM / ALIB30B / SHRINK3.ASM < prev    next >
Assembly Source File  |  1994-11-26  |  8KB  |  296 lines
  1.     page    66,132
  2. ;****************************** SHRINK3.ASM  *********************************
  3.         extrn    dos_mem_allocate:far
  4.         extrn    dos_mem_release:far
  5.  
  6.         public    decompress
  7.  
  8.  
  9. CLEAR        equ    256
  10. EOF        equ    257
  11. FIRST_FREE    equ    258
  12. BUFFSIZE    equ    4096        ;
  13.  
  14. hash_rec    struc
  15. next    dw    ?            ; prefix code
  16. char    db    ?            ; suffix char
  17. hash_rec    ends
  18.  
  19. ;----------------------------------------------------------------------------
  20. .xlist
  21.     include  mac.inc
  22. .list
  23. ;----------------------------------------------------------------------------
  24.  
  25. data_    struc
  26. feed_process    dd    ?
  27. store_process    dd    ?
  28.  
  29. cur_code    dw    ?    ;?
  30. old_code    dw    ?    ;?
  31. in_code        dw    ?    ;?
  32. max_code    dw    ?
  33. fin_char    db    ?    ;?
  34.  
  35.  
  36. feed_buffer    db    BUFFSIZE dup (?)
  37. feed_ptr    dw    ?
  38. feed_available    dw    ?
  39. partial_bit_count dw    ?
  40. nbits        dw    ?
  41.  
  42. store_buffer    db    BUFFSIZE dup (?)
  43.  
  44. hash        db    20480 dup (?)
  45. data_    ends
  46. ;------------------------------------------------------------------------
  47. LIBSEG           segment byte public 'LIB'
  48.     assume    CS:LIBSEG,DS:nothing, ES:nothing
  49.  
  50. masks        dw    1ffh,3ffh,7ffh,0fffh
  51.  
  52. comment 
  53. ;- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -(COMPRESS )
  54. decompress - decompress data block using limpel-ziev algorithm
  55. ;
  56. ; inputs:  es:si = feed proceedure ptr
  57. ;          es:di = store proceedure ptr
  58. ;          dx,ax = size of block of data to be compressed
  59. ;
  60. ; output:  If carry returned then, insufficent
  61. ;          Normal operation is results in:
  62. ;
  63. ;          The feed proceedure is called with:  ds:dx = buffer area
  64. ;                                                  ax = request byte count
  65. ;          The feed proceedure returns:  ax = byte count of data placed in
  66. ;                                             buffer.
  67. ;
  68. ;          The store proceedure is called with:  ds:dx = buffer pointer
  69. ;                                                   ax = buffer size
  70. ;
  71. ; note:  The feed proceedure is called whenever the compress module runs
  72. ;        out of data.  The store module is called whenever more data is
  73. ;        needed.  Normally, the feed and store data uses a disk file, but
  74. ;        if room it could be placed in memory.
  75. ;        The feed and store modules must restore any registers they
  76. ;        modify.  Specifically, si,di,bp,ds,es
  77. ;
  78. ; note:  compress and decompress work together and the functions
  79. ;        shrink and expand work together.  Compress and decompress
  80. ;        are much faster and smaller code, but do not produce quite
  81. ;        as good compression.
  82. ;
  83. ;                       execution time          code size
  84. ;                       ---------------         ----------
  85. ;        compress            1.75                  430
  86. ;        decompress           .87                  381
  87. ;
  88. ;        shrink             10.05                  1447
  89. ;        expand              1.54                  1447       
  90. ;* * * * * * * * * * * * * *
  91. 
  92.  
  93. decompress    proc    far
  94.     push    es
  95.     mov    dx,0
  96.     mov    ax,size data_
  97.     call    dos_mem_allocate
  98.     mov    ax,es
  99.     mov    ds,ax
  100.     pop    es
  101.     jc    error_exit
  102.         mov    word ptr ds:[feed_process],si
  103.         mov    word ptr ds:[store_process],di
  104.         mov    word ptr ds:[feed_process+2],es
  105.         mov    word ptr ds:[store_process+2],es
  106.         mov    es,ax
  107. ;
  108. ; setup the buffer ptrs
  109. ;
  110.     mov    ds:[feed_ptr],offset feed_buffer
  111.     mov    ds:[feed_available],0
  112.     mov    di,offset store_buffer
  113.     mov    ds:[partial_bit_count],0
  114.     call    init_tab
  115.     jmp    lp1
  116. ;
  117. ; flush remaining data in buffer
  118. ;
  119. compress_done:
  120.     call    flush_outbuf
  121.     call    dos_mem_release
  122.     clc
  123. error_exit:
  124.         retf                ;done
  125. ;
  126. ; clear code was found, restart table
  127. ;
  128. clear_found:
  129.     call    init_tab        ;Initialize table
  130.     call    read_code        ;Read next code
  131.     mov    ds:[cur_code],ax        ;Initialize variables
  132.     mov    ds:[old_code],ax
  133.     mov    ds:[fin_char],al
  134.  
  135.     stosb
  136.     cmp    di,offset store_buffer + BUFFSIZE
  137.     jb    lp1            ;jmp if room in buffer
  138.     call    flush_outbuf
  139.     
  140. lp1:       call    read_code        ;Get a code
  141.     cmp    ax,EOF            ;End of file?
  142.     je    compress_done
  143.     cmp    ax,CLEAR        ;Clear code?
  144.     je    clear_found        ; jmp if clear code
  145.     xor    cx,cx            ;clear stacked char count
  146.     mov    ds:[cur_code],ax        ;Save new code
  147.     mov    ds:[in_code],ax
  148.     cmp    ax,bp            ;bp=free_code,Code in table?
  149.     jl    process_code        ;yes
  150.      mov    dx,ds:[old_code]        ;get previous code
  151.      mov    ds:[cur_code],dx        ;make current
  152.      mov    al,ds:[fin_char]        ;get old last char
  153.      push    ax            ;push it
  154.      inc    cx            ;stack_count
  155.      mov    ax,dx            ;set ax=cur_code
  156. process_code:
  157.     cmp    ax,255            ; Code or character?
  158.     jle    process_char        ;Char
  159.      mov    bx,ax            ; Convert code to address
  160. ;
  161. ; index into hash table
  162. ;
  163.     shl    bx,1            ;bp = bx
  164.     add    bx,ax            ;bx = bx * 2 + bp
  165.     add    bx,offset hash        ; add in hashtable base offset
  166.  
  167.      mov    al,[bx.char]        ;Get suffix char
  168.      push    ax            ;push it
  169.      inc    cx            ;stack_count
  170.      mov    ax,[bx]            ;Get prefix code
  171.      jmp    process_code        ;Translate again
  172.  
  173. flush:    call    flush_outbuf
  174.     jmp    wc_test
  175.     
  176. process_char:
  177.     mov    ds:[fin_char],al    ;Save as final
  178. wc_lp:    stosb
  179.     cmp    di,offset store_buffer + BUFFSIZE
  180.     jae    flush            ;jmp if buffer full
  181.  
  182. wc_test:jcxz    add_cod            ;jmp if stack empty
  183.     pop    ax
  184.     dec    cx
  185.     jns    wc_lp            ;this should alway jump
  186. ;
  187. ; add_code - add code to table
  188. ;  inputs:  fin_char = data to add
  189. ;                bx = code
  190. ;
  191. add_cod:mov    bx,bp            ;bx = bx * 3 (3 byte entries)
  192.     shl    bx,1            ;
  193.     add    bx,bp            ;bx = bx * 2 + bp
  194.     add    bx,offset hash        ; add in hashtable base offset
  195.     mov    al,ds:[fin_char]
  196.     mov    [bx].char,al        ;save it
  197.     mov    ax,ds:[old_code]    ;get prefix code
  198.     mov    [bx].next,ax        ;save it
  199.     inc    bp            ;bp=free_code,    ;set next code
  200.  
  201.     mov    ax,ds:[in_code]        ;Save input code
  202.     mov    ds:[old_code],ax
  203.     cmp    bp,ds:[max_code]    ;bp=free_code, hit table limit?
  204.     jl    lp1              ;Less means no
  205.     cmp    ds:[nbits],12        ;Still within twelve bits?
  206.     je    lp1              ;no (next code should be clear)
  207.     inc    ds:[nbits]        ;Increase code size
  208.     shl    ds:[max_code],1        ;Double max code
  209.           jmp    lp1            ;Get next code
  210. decompress    endp    
  211. ;--------------------------------------------------------------------------
  212. ; read_code - get bits from input
  213. ;  inputs:  nbits = number of bits to get
  214. ;  output:  ax = data
  215. ;
  216. read_code:
  217.     cmp    ds:[feed_available],3
  218.     jb    fill_inbuf
  219. ;
  220. ; compute ptr update
  221. ;
  222. rc1:    mov    ax,ds:[partial_bit_count]
  223.     add    ax,ds:[nbits]
  224.     mov    cx,8
  225.     xor    dx,dx                ;clear dx
  226.     div    cx
  227.     mov    si,ds:[feed_ptr]            ;get current feed_ptr
  228.     add    ds:[feed_ptr],ax            ;update feed ptr in memory
  229.     sub    ds:[feed_available],ax
  230.     xchg    ds:[partial_bit_count],dx
  231. ;
  232. ; get data from buffer
  233. ;
  234.     lodsw
  235.     mov    bx,ax
  236.     lodsb
  237. ;
  238. ; position data
  239. ;
  240.     mov    cx,dx
  241.     jcxz    rd2            ;jmp if no positioning needed
  242. rd1:    shr    al,1
  243.     rcr    bx,1
  244.     loop    rd1
  245. ;
  246. ; used nbits to isolate correct number of bits
  247. ;
  248. rd2:    mov    ax,bx
  249.     mov    bx,ds:[nbits]
  250.     sub    bx,9
  251.     shl    bx,1
  252.     and    ax,cs:masks[bx]
  253. rc_exit:ret
  254.  
  255. ; fill_inbuf - fill the input buffer
  256.  
  257. fill_inbuf:
  258.     apush    bx,di
  259.     mov    cx,ds:[feed_available]
  260.     mov    di,offset feed_buffer
  261.     mov    si,ds:[feed_ptr]
  262.     mov    ds:[feed_ptr],di        ;feed ptr = offset feed_buffer
  263.     jcxz    fi_1                ;jmp if buffer empty
  264.     rep    movsb
  265. fi_1:    mov    dx,di
  266.     mov    ax,BUFFSIZE -3
  267.     call    dword ptr ds:[feed_process]
  268. fill_ok:add    word ptr ds:[feed_available],ax    
  269.     apop    di,bx
  270.     jmp    rc1
  271. ;--------------------------------------------------------------------------
  272. ; flush_outbuf - ship the full buffer off to caller
  273. ;  inputs: di = current store ptr
  274. ;  output: none
  275. ;
  276. flush_outbuf:
  277.     mov    ax,di                ;store_ptr to -ax-
  278.     mov    dx,offset store_buffer
  279.     sub    ax,dx                ;compute flush size
  280.     jz    fo_done                ;jmp if no data in buffer
  281.     mov    di,dx
  282.     call    dword ptr ds:[store_process]
  283. fo_done:ret
  284. ;--------------------------------------------------------------------------
  285. ; init_tab - initialize table pointers
  286. ;
  287. init_tab:
  288.     mov    ds:[nbits],9            ;Initialize variables
  289.     mov    ds:[max_code],512
  290.     mov    bp,FIRST_FREE        ;free_code = FIRST_FREE
  291.     ret
  292. ;-----------------------------------------------------------------------
  293. LIBSEG    ENDS
  294.  
  295. ;;    end
  296.