home *** CD-ROM | disk | FTP | other *** search
/ Photo CD Demo 1 / Demo.bin / formats / gif / gen_code / gifasm.arc / COMP.ASM < prev    next >
Encoding:
Assembly Source File  |  1988-10-22  |  7.0 KB  |  302 lines
  1.     TITLE    Compress - LZW compressor for GIF
  2.     NAME    Compress
  3.     PAGE    60,132
  4. ; Comp.asm - Compress image data.
  5. ;
  6. ; Called by Microsoft C
  7. ;
  8. ;    int Compress(code_size,get_byte_routine,put_byte_routine);
  9. ;    unsigned int code_size;
  10. ;    int (*get_byte_routine)();
  11. ;    void (*put_byte_routine)(code);
  12. ;    unsigned int code;
  13. ;
  14. ; Returns
  15. ;
  16. ;     0    Normal completion
  17. ;    -1    Cannot allocate memory for hash table
  18. ;    -2    Invalid code size
  19. ;
  20. ; Originated from lzcomp.asm by Tom Pfau, Digital Equipment Corporation
  21. ; C callable version by Steve Becquer (74155,767)
  22. ;
  23. ; Version 1.00 last revised 10/21/88
  24. ;
  25. ; GIF and 'Graphics Interchange Format' are trademarks (tm) of
  26. ; CompuServe Incorporated, an H&R Block Company.
  27.  
  28. ; Equates
  29.  
  30. code_size     EQU    [bp+4]
  31. get_byte_routine EQU    [bp+6]
  32. put_byte_routine EQU    [bp+8]
  33. maxmax         EQU    4096        ; Max code + 1
  34.  
  35. ; Hash table entry
  36.  
  37. hash_rec    STRUC
  38. first    DW    ?            ; First entry with this value
  39. next    DW    ?            ; Next entry along chain
  40. char    DB    ?            ; Suffix char
  41. hash_rec    ENDS
  42.  
  43. ; Declare segments
  44.  
  45. _TEXT    SEGMENT BYTE PUBLIC 'CODE'
  46. _TEXT    ENDS
  47. _DATA    SEGMENT WORD PUBLIC 'DATA'
  48. _DATA    ENDS
  49. memory    SEGMENT PARA 'MEMORY'
  50. hash    LABEL    hash_rec
  51. memory    ENDS
  52.  
  53. DGROUP    GROUP    _DATA
  54.     ASSUME    CS:_TEXT,DS:DGROUP,SS:DGROUP,ES:DGROUP
  55.  
  56. ; Entry coding
  57.  
  58. _TEXT    SEGMENT
  59.  
  60.     PUBLIC    _Compress
  61.  
  62. _Compress    PROC    NEAR
  63.     push    bp            ; Save caller's registers
  64.     mov    bp,sp
  65.     push    di
  66.     push    si
  67.     push    es
  68.  
  69.     mov    bx,1280         ; Allocate space for hash table
  70.     mov    ah,48h
  71.     int    21h
  72.     jnc    memok
  73.     mov    ax,-1            ; Allocation error
  74.     jmp    l19
  75. memok:    mov    hash_seg,ax        ; Save segment address
  76.  
  77.     mov    ax,code_size        ; Validate code size
  78.     cmp    ax,2            ; Code size < 2?
  79.     jl    cserr            ; Yes, error
  80.     cmp    ax,8            ; Code size <= 8?
  81.     jle    init            ; Yes, it's good
  82. cserr:    mov    ax,-2            ; Invalid code size
  83.     jmp    l19
  84.  
  85. init:    xor    ax,ax            ; Initialize variables
  86.     mov    bits_held,ax
  87.     mov    bits,ax
  88.     mov    bits+2,ax
  89. l1:    call    init_table        ; Initialize table
  90.     mov    ax,clear        ; Write a clear code
  91.     call    write_code
  92.     push    es
  93.     call    get_byte_routine    ; Read first char
  94.     pop    es
  95.     cmp    ax,-1            ; End of data?
  96.     je    l18            ; Yes, nothing to do
  97. l4:    xor    ah,ah            ; Turn char into code
  98. l4a:    mov    prefix_code,ax        ; Set prefix code
  99.     push    es
  100.     call    get_byte_routine    ; Read next char
  101.     pop    es
  102.     cmp    ax,-1            ; End of data?
  103.     je    l17            ; Yes
  104.     mov    k,al            ; Save char in k
  105.     mov    bx,prefix_code        ; Get prefix code
  106.     call    lookup_code        ; See if this pair in table
  107.     jnc    l4a            ; nc means yes, new code in ax
  108.     call    add_code        ; Add pair to table
  109.     push    bx            ; Save new code
  110.     mov    ax,prefix_code        ; Write old prefix code
  111.     call    write_code
  112.     pop    bx
  113.     mov    al,k            ; Get last char
  114.     cmp    bx,max_code        ; Exceed code size?
  115.     jl    l4            ; Less means no
  116.     cmp    nbits,12        ; Currently less than 12 bits?
  117.     jl    l14            ; Yes
  118.     mov    ax,clear        ; Write a clear code
  119.     call    write_code
  120.     call    init_table        ; Reinit table
  121.     mov    al,k            ; Get last char
  122.     jmp    short l4        ; Start over
  123. l14:    inc    nbits            ; Increase number of bits
  124.     shl    max_code,1        ; Double max code size
  125.     jmp    short l4        ; Get next char
  126. l17:    mov    ax,prefix_code        ; Write last code
  127.     call    write_code
  128.     mov    ax,eof            ; Write eof code
  129.     call    write_code
  130.     cmp    bits_held,0        ; Make sure buffer is flushed to file
  131.     je    l18
  132. l17a:    call    flush
  133. l18:    mov    es,hash_seg        ; Free hash table space
  134.     mov    ah,49h
  135.     int    21h
  136.     xor    ax,ax            ; Zero return
  137. l19:    pop    es            ; Restore caller's registers
  138.     pop    si
  139.     pop    di
  140.     mov    sp,bp
  141.     pop    bp
  142.     ret
  143.  
  144. _compress    ENDP
  145.  
  146. _DATA    SEGMENT
  147. clear        DW    ?
  148. eof        DW    ?
  149. hash_seg    DW    ?
  150. prefix_code    DW    ?
  151. free_code    DW    ?
  152. max_code    DW    ?
  153. nbits        DW    ?
  154. k        DB    ?
  155. _DATA    ENDS
  156.  
  157. init_table    PROC    NEAR
  158.     mov    cx,code_size        ; Get code size
  159.     mov    ax,1
  160.     shl    ax,cl            ; Compute clear code
  161.     mov    clear,ax
  162.     inc    ax            ; Compute end of info code
  163.     mov    eof,ax
  164.     inc    ax            ; Compute first free entry in
  165.     mov    free_code,ax        ; Code table
  166.     inc    cx            ; Compute bits per code
  167.     mov    nbits,cx
  168.     mov    ax,1
  169.     shl    ax,cl            ; Compute maximum code value
  170.     mov    max_code,ax
  171.     mov    es,hash_seg        ; Address hash table
  172.     mov    ax,-1            ; Unused flag
  173.     mov    cx,clear        ; Clear root codes
  174.     mov    di,offset hash        ; Point to first entry
  175. it1:    stosw                ; Clear it out
  176.     add    di,3            ; Bump to next entry
  177.     loop    it1
  178.     push    ds
  179.     pop    es            ; Restore seg reg
  180.     ret                ; Done
  181. init_table    ENDP
  182.  
  183. write_code    PROC    NEAR
  184.     push    ax            ; Save code
  185. wt1:    cmp    bits_held,8        ; Have enough for a byte?
  186.     jl    wt2            ; No
  187.     mov    ax,bits+2        ; Get bits held
  188.     xor    ah,ah            ; Make a byte
  189.     push    es            ; Preserve seg reg
  190.     push    ax            ; Character to be passed
  191.     call    put_byte_routine    ; Output byte
  192.     add    sp,2            ; Adjust stack
  193.     pop    es
  194.     mov    dx,bits         ; Shift remaining bits right
  195.     mov    ax,bits+2
  196.     mov    al,ah
  197.     mov    ah,dl
  198.     mov    dl,dh
  199.     xor    dh,dh
  200.     mov    bits,dx
  201.     mov    bits+2,ax
  202.     sub    bits_held,8        ; Compute new bits held
  203.     jmp    short wt1        ; See if less than a byte left
  204. wt2:    xor    dx,dx            ; Add new code bits
  205.     pop    ax
  206.     mov    cx,bits_held
  207.     jcxz    wt3            ; If zero, skip shift
  208. wt2a:    shl    ax,1            ; Shift new code
  209.     rcl    dx,1
  210.     loop    wt2a
  211. wt3:    or    bits,dx         ; Save new bits held
  212.     or    bits+2,ax
  213.     mov    cx,nbits        ; Compute new held count
  214.     add    bits_held,cx
  215.     ret
  216. write_code    ENDP
  217.  
  218. _DATA    SEGMENT
  219. bits_held    DW    ?
  220. bits        DW    2 DUP (?)
  221. _DATA    ENDS
  222.  
  223. flush        PROC    NEAR
  224. fl1:    cmp    bits_held,0        ; Have any bits held?
  225.     jle    fl2            ; No
  226.     mov    ax,bits+2        ; Get bits held
  227.     xor    ah,ah            ; Make a byte
  228.     push    es            ; Preserve seg reg
  229.     push    ax            ; Character to be passed
  230.     call    put_byte_routine    ; Output byte
  231.     add    sp,2            ; Adjust stack
  232.     pop    es
  233.     mov    dx,bits         ; Shift remaining bits right
  234.     mov    ax,bits+2
  235.     mov    al,ah
  236.     mov    ah,dl
  237.     mov    dl,dh
  238.     xor    dh,dh
  239.     mov    bits,dx
  240.     mov    bits+2,ax
  241.     sub    bits_held,8        ; Compute new bits held
  242.     jmp    short fl1        ; See if more left
  243. fl2:    ret
  244. flush        ENDP
  245.  
  246. lookup_code    PROC    NEAR
  247.     push    ds            ; Save seg reg
  248.     mov    ds,hash_seg        ; Point to hash table
  249.     call    index            ; Convert code to address
  250.     mov    di,0            ; Flag
  251.     cmp    [si].first,-1        ; Has this code been used?
  252.     je    gc4            ; Equal means no
  253.     inc    di            ; Set flag
  254.     mov    bx,[si].first        ; Get first entry
  255. gc2:    call    index            ; Convert code to address
  256.     cmp    [si].char,al        ; Is char the same?
  257.     jne    gc3            ; ne means no
  258.     clc                ; Success
  259.     mov    ax,bx            ; Put found code in ax
  260.     pop    ds            ; Restore seg reg
  261.     ret                ; Done
  262. gc3:    cmp    [si].next,-1        ; More left with this prefix?
  263.     je    gc4            ; Equal means no
  264.     mov    bx,[si].next        ; Get next code
  265.     jmp    short gc2        ; Try again
  266. gc4:    stc                ; Not found
  267.     pop    ds            ; Restore seg reg
  268.     ret                ; Done
  269. lookup_code    ENDP
  270.  
  271. index        PROC    NEAR
  272.     mov    si,bx            ; si = bx * 5 (5 byte hash entries)
  273.     shl    si,1            ; si = bx * 2 * 2 + bx
  274.     shl    si,1
  275.     add    si,bx
  276.     ret
  277. index        ENDP
  278.  
  279. add_code    PROC    NEAR
  280.     mov    bx,free_code        ; Get code to use
  281.     push    ds            ; Point to hash table
  282.     mov    ds,hash_seg
  283.     cmp    di,0            ; First use of this prefix?
  284.     je    ac1            ; Equal means yes
  285.     mov    [si].next,bx        ; Point last use to new entry
  286.     jmp    short ac2
  287. ac1:    mov    [si].first,bx        ; Point first use to new entry
  288. ac2:    cmp    bx,maxmax        ; Have we reached code limit?
  289.     je    ac3            ; Equal means yes, just return
  290.     call    index            ; Get address of new entry
  291.     mov    [si].first,-1        ; Initialize pointers
  292.     mov    [si].next,-1
  293.     mov    [si].char,al        ; Save suffix char
  294.     inc    es:free_code        ; Adjust next code
  295. ac3:    pop    ds            ; Restore seg reg
  296.     ret
  297. add_code    ENDP
  298.  
  299. _TEXT    ENDS
  300.  
  301.     END
  302.