home *** CD-ROM | disk | FTP | other *** search
/ Simtel MSDOS 1992 September / Simtel20_Sept92.cdr / msdos / arc_lbr / mdcd10.arc / LZ.MD / LZCOMP.ASM < prev    next >
Assembly Source File  |  1986-07-01  |  7KB  |  288 lines
  1.     title    lzcomp - file compressor using limpel-ziv algorithm
  2.  
  3. ;Tom Pfau
  4. ;Digital Equipment Corporation
  5. ;Parsippany, NJ
  6.  
  7. ;Constants
  8. clear        equ    256        ;Clear code
  9. eof        equ    257        ;End of file marker
  10. first_free    equ    258        ;First free code
  11. maxmax        equ    4096        ;Max code + 1
  12.  
  13.     include macros.mlb
  14.  
  15. ;Hash table entry
  16. hash_rec    struc
  17. first    dw    ?            ; First entry with this value
  18. next    dw    ?            ; Next entry along chain
  19. char    db    ?            ; Suffix char
  20. hash_rec    ends
  21.  
  22. ;Declare Segments
  23. code    segment byte public 'code'
  24. code    ends
  25. stack    segment word stack 'data'
  26.     dw    128 dup (?)
  27. stack    ends
  28. data    segment word public 'data'
  29. data    ends
  30. memory    segment para public 'memory'
  31. hash    label    hash_rec
  32. memory    ends
  33.  
  34. ;Start writing code
  35. code    segment
  36.     assume    cs:code,ds:data,es:data,ss:stack
  37.  
  38. start    proc    far
  39.     mov    bx,seg hash        ;End of program
  40.     mov    ax,ds            ;Start of program
  41.     sub    bx,ax            ;Program size
  42.     inc    bx            ;Make sure
  43.     setmem    bx            ;Set our size
  44.     mov    bx,data            ;Set up data segment addressability
  45.     mov    es,bx
  46.     mov    ds,bx
  47.     print    input_prompt        ;Get input file name
  48.     input    input_file
  49.     print    crlf
  50.     print    output_prompt        ;And output
  51.     input    output_file
  52.     print    crlf
  53.     mov    al,input_file+1        ;Terminate file names with nulls
  54.     xor    ah,ah
  55.     mov    si,ax
  56.     mov    input_file+2[si],0
  57.     mov    al,output_file+1
  58.     mov    si,ax
  59.     mov    output_file+2[si],0
  60.     hopen    input_file+2,0
  61.     mov    input_handle,ax
  62.     hcreat    output_file+2,0
  63.     mov    output_handle,ax
  64.     call    compress        ;Compress file
  65.     hclose    input_handle        ;Close in and out
  66.     hclose    output_handle
  67.     exit                ;Done
  68. start    endp
  69.  
  70. data    segment
  71. input_prompt    db    'Input file: $'
  72. output_prompt    db    'Output file: $'
  73. input_file    db    80,0,80 dup (?)
  74. output_file    db    80,0,80 dup (?)
  75. crlf        db    13,10,'$'
  76. input_handle    dw    ?
  77. output_handle    dw    ?
  78. data    ends
  79.  
  80. compress    proc    near
  81.     malloc    1280            ;Allocate space for hash table
  82.     mov    hash_seg,ax        ;Save segment address
  83. l1:    call    init_table        ;Initialize the table and some vars
  84.     mov    ax,clear        ;Write a clear code
  85.     call    write_code
  86.     call    read_char        ;Read first char
  87. l4:    xor    ah,ah            ;Turn char into code
  88. l4a:    mov    prefix_code,ax        ;Set prefix code
  89.     call    read_char        ;Read next char
  90.     jc    l17            ;Carry means eof
  91.     mov    k,al            ;Save char in k
  92.     mov    bx,prefix_code        ;Get prefix code
  93.     call    lookup_code        ;See if this pair in table
  94.     jnc    l4a            ;nc means yes, new code in ax
  95.     call    add_code        ;Add pair to table
  96.     push    bx            ;Save new code
  97.     mov    ax,prefix_code        ;Write old prefix code
  98.     call    write_code
  99.     pop    bx
  100.     mov    al,k            ;Get last char
  101.     cmp    bx,max_code        ;Exceed code size?
  102.     jl    l4            ;less means no
  103.     cmp    nbits,12        ;Currently less than 12 bits?
  104.     jl    l14            ;yes
  105.     mov    ax,clear        ;Write a clear code
  106.     call    write_code
  107.     call    init_table        ;Reinit table
  108.     mov    al,k            ;get last char
  109.     jmp    l4            ;Start over
  110. l14:    inc    nbits            ;Increase number of bits
  111.     shl    max_code,1        ;Double max code size
  112.     jmp    l4            ;Get next char
  113. l17:    mov    ax,prefix_code        ;Write last code
  114.     call    write_code
  115.     mov    ax,eof            ;Write eof code
  116.     call    write_code
  117.     mov    ax,bit_offset        ;Make sure buffer is flushed to file
  118.     cmp    ax,0
  119.     je    l18
  120.     mov    cx,8            ;convert bits to bytes
  121.     xor    dx,dx
  122.     div    cx
  123.     or    dx,dx            ;If extra bits, make sure they get
  124.     je    l17a            ;written
  125.     inc    ax
  126. l17a:    call    flush
  127. l18:    ret
  128. compress    endp
  129.  
  130. data    segment
  131. hash_seg    dw    ?
  132. prefix_code    dw    ?
  133. free_code    dw    ?
  134. max_code    dw    ?
  135. nbits        dw    ?
  136. k        db    ?
  137. data    ends
  138.  
  139. init_table    proc    near
  140.     mov    nbits,9            ;Set code size to 9
  141.     mov    max_code,512        ;Set max code to 512
  142.     push    es            ;Save seg reg
  143.     mov    es,hash_seg        ;Address hash table
  144.     mov    ax,-1            ;Unused flag
  145.     mov    cx,640            ;Clear first 256 entries
  146.     mov    di,offset hash        ;Point to first entry
  147. rep    stosw                ;Clear it out
  148.     pop    es            ;Restore seg reg
  149.     mov    free_code,first_free    ;Set next code to use
  150.     ret                ;done
  151. init_table    endp
  152.  
  153. write_code    proc    near
  154.     push    ax            ;Save code
  155.     mov    ax,bit_offset        ;Get bit offset
  156.     mov    cx,nbits        ;Adjust bit offset by code size
  157.     add    bit_offset,cx
  158.     mov    cx,8            ;Convert bit offset to byte offset
  159.     xor    dx,dx
  160.     div    cx
  161.     cmp    ax,1020            ;Approaching end of buffer?
  162.     jl    wc1            ;less means no
  163.     call    flush            ;Write the buffer
  164.     push    dx            ;dx contains offset within byte
  165.     add    dx,nbits        ;adjust by code size
  166.     mov    bit_offset,dx        ;new bit offset
  167.     pop    dx            ;restore dx
  168.     add    ax,offset output_data    ;Point to last byte
  169.     mov    si,ax            ;put in si
  170.     mov    al,byte ptr [si]    ;move byte to first position
  171.     mov    output_data,al
  172.     xor    ax,ax            ;Byte offset of zero
  173. wc1:    add    ax,offset output_data    ;Point into buffer
  174.     mov    di,ax            ;Destination
  175.     pop    ax            ;Restore code
  176.     mov    cx,dx            ;offset within byte
  177.     xor    dx,dx            ;dx will catch bits rotated out
  178.     jcxz    wc3            ;If offset in byte is zero, skip shift
  179. wc2:    shl    ax,1            ;Rotate code
  180.     rcl    dx,1
  181.     loop    wc2
  182.     or    al,byte ptr [di]    ;Grab bits currently in buffer
  183. wc3:    stosw                ;Save data
  184.     mov    al,dl            ;Grab extra bits
  185.     stosb                ;and save
  186.     ret
  187. write_code    endp
  188.  
  189. data    segment
  190. bit_offset    dw    ?
  191. output_data    db    1024 dup (?)
  192. data    ends
  193.  
  194. flush        proc    near
  195.     push    ax            ;Save all registers
  196.     push    bx            ;AX contains number of bytes to write
  197.     push    cx
  198.     push    dx
  199.     hwrite    output_handle,output_data,ax    ;write output file
  200.     pop    dx
  201.     pop    cx
  202.     pop    bx
  203.     pop    ax
  204.     ret
  205. flush        endp
  206.  
  207. read_char    proc    near
  208.     mov    di,input_offset        ;Anything left in buffer?
  209.     cmp    di,input_size
  210.     jl    rd1            ;less means yes
  211.     hread    input_handle,input_data,1024    ;Read next chunk of input
  212.     cmp    ax,0            ;Anything left?
  213.     je    rd2            ;equal means no, finished
  214.     mov    input_size,ax        ;Save bytes read
  215.     mov    input_offset,0        ;Point to beginning of buffer
  216.     mov    di,0
  217. rd1:    lea    si,input_data[di]    ;Point at character
  218.     lodsb                ;Read it in
  219.     inc    input_offset        ;Adjust pointer
  220.     clc                ;Success
  221.     ret
  222. rd2:    stc                ;Nothing left
  223.     ret
  224. read_char    endp
  225.  
  226. data    segment
  227. input_data    db    1024 dup (?)
  228. input_offset    dw    0
  229. input_size    dw    0
  230. data    ends
  231.  
  232. lookup_code    proc    near
  233.     push    ds            ;Save seg reg
  234.     mov    ds,hash_seg        ;point to hash table
  235.     call    index            ;convert code to address
  236.     mov    di,0            ;flag
  237.     cmp    [si].first,-1        ;Has this code been used?
  238.     je    gc4            ;equal means no
  239.     inc    di            ;set flag
  240.     mov    bx,[si].first        ;Get first entry
  241. gc2:    call    index            ;convert code to address
  242.     cmp    [si].char,al        ;is char the same?
  243.     jne    gc3            ;ne means no
  244.     clc                ;success
  245.     mov    ax,bx            ;put found code in ax
  246.     pop    ds            ;restore seg reg
  247.     ret                ;done
  248. gc3:    cmp    [si].next,-1        ;More left with this prefix?
  249.     je    gc4            ;equal means no
  250.     mov    bx,[si].next        ;get next code
  251.     jmp    gc2            ;try again
  252. gc4:    stc                ;not found
  253.     pop    ds            ;restore seg reg
  254.     ret                ;done
  255. lookup_code    endp
  256.  
  257. index        proc    near
  258.     mov    si,bx            ;si = bx * 5 (5 byte hash entries)
  259.     shl    si,1            ;si = bx * 2 * 2 + bx
  260.     shl    si,1
  261.     add    si,bx
  262.     ret
  263. index        endp
  264.  
  265. add_code    proc    near
  266.     mov    bx,free_code        ;Get code to use
  267.     push    ds            ;point to hash table
  268.     mov    ds,hash_seg
  269.     cmp    di,0            ;First use of this prefix?
  270.     je    ac1            ;equal means yes
  271.     mov    [si].next,bx        ;point last use to new entry
  272.     jmp    short ac2
  273. ac1:    mov    [si].first,bx        ;Point first use to new entry
  274. ac2:    cmp    bx,maxmax        ;Have we reached code limit?
  275.     je    ac3            ;equal means yes, just return
  276.     call    index            ;get address of new entry
  277.     mov    [si].first,-1        ;initialize pointers
  278.     mov    [si].next,-1
  279.     mov    [si].char,al        ;save suffix char
  280.     inc    es:free_code        ;adjust next code
  281. ac3:    pop    ds            ;restore seg reg
  282.     ret
  283. add_code    endp
  284.  
  285. code    ends
  286.  
  287.     end    start
  288.