home *** CD-ROM | disk | FTP | other *** search
/ Stars of Shareware: Programmierung / SOURCE.mdf / programm / msdos / c / xv221src / unsupt / vms / gifdecom.mar < prev    next >
Encoding:
Text File  |  1992-04-26  |  10.2 KB  |  296 lines
  1.     .title GIF_DECOMPRESSOR
  2. ;++
  3. ; Define optimized routines for decompressing GIF files.
  4. ;
  5. ; procedure GIF_DECOMPRESS_INIT
  6. ;       Initialize internal tables used by the GIF_DECOMPRESS procedure.
  7. ;    arguments:
  8. ;    4(AP)    address of byte containing sizeof output data in bits.
  9. ;        must be in range 2 - 8.
  10. ;
  11. ; procedure GIF_DECOMPRESS
  12. ;    Decompress stream of input codes into user buffer.
  13. ;    arguments:
  14. ;    4(AP)    Address of input procedure.
  15. ;    8(AP)    Unspecified.  Additional argument for input procedure.
  16. ;    12(AP)    Number of output bytes to produce.
  17. ;    16(AP)    Address of output buffer.
  18. ;
  19. ; User-supplied input procedure:
  20. ;    arguments:
  21. ;    4(AP)    Argument specified in call to GIF_DECOMPRESS
  22. ;    8(AP)    Address of quadword to receive output descriptor.  The
  23. ;        input routine must fill in the count and buffer address field
  24. ;        of this descritor.
  25. ;    
  26. ;--
  27. ;
  28. ; Define data area that holds string table
  29.     .PSECT GIF_DECOMP_STABLE, WRT, LONG
  30. GIF_MAC_STABLE::
  31. CODE_BITS:    .LONG 0            ; Current input size
  32. BITS_USED:    .LONG 0            ; Number of bits used with cur buffer.
  33. TABLE_SIZE:     .LONG 0            ; Highest code defined in table
  34. PREV_CODE:     .LONG 0            ; Previous input code
  35. STACK_PTR:    .LONG 0            ; Output stack pointer
  36. CLEAR_CODE:     .LONG 0            ; Code value to signal table clears
  37. EOI_CODE:     .LONG 0            ; Code value to signal data end
  38. INBUF:        .BLKL 2            ; Descriptor filled in by input routine
  39. ; make tables 4100 instead of 4096 to avoid cache stride.
  40. PREFIX:        .BLKW 4100        ; prefix code table.
  41. EXTENSION:    .BLKB 4100        ; last char in code's expansion.
  42. STACK:        .BLKB 4100        ; Decoder output stack.
  43. STACK_TOP:
  44. ARG_LIST: .BLKL 5            ; Copy of argument list.
  45.  
  46.     .PSECT GIF_DECOMP_CODE, NOWRT, LONG, EXE
  47. ;
  48. ; Define initialization routine.  Initialize the GIF_DECOMP_STABLE psect.
  49. ;
  50.     .ENTRY GIF_DECOMPRESS_INIT, ^M<R2, R3>
  51. ;
  52. ; Compute the clear and EOI codes for the specified data size and initial
  53. ; input code size.
  54. ;
  55.     ASHL @4(AP), #1, G^CLEAR_CODE    ; Convert Root size to input.
  56.     ADDL3 G^CLEAR_CODE, #1, -
  57.          G^EOI_CODE
  58.     CVTBL    @4(AP), R0
  59.     ADDL3 R0, #1, G^CODE_BITS    ; Initial code size
  60. ;
  61. ; Initialize the decoder table so, each code less than CLEAR_CODE expands
  62. ; to itself.   Clear and EOI have special prefix values to aid testing for
  63. ; those special codes.
  64. ;
  65.     CLRL  R0
  66.     MOVAW    G^PREFIX, R1        ; Base address of code table
  67.     MOVAB    G^EXTENSION, R2        ; Base address of suffix table.
  68.     MOVL    G^CLEAR_CODE, R3    ; Loop end value.
  69. 10$:
  70.     MNEGW    #1, (R1)[R0]        ; Mark code as having no prefix (-1).
  71.     MOVB    R0, (R2)[R0]        ; Suffix value is save as code value.
  72.     AOBLSS    R3, R0, 10$        ; Do next code value.
  73.     MOVW    #-2, (R1)[R0]        ; Mark clear code specially
  74.     INCL    R0            ; EOI code is 1 after clear code.
  75.     MOVW    #-2, (R1)[R0]        ; Mark EOI code specially
  76.  
  77.     INCL     R0
  78. 20$:    CLRW    (R1)[R0]
  79.     AOBLEQ    #257, R0, 20$        ; Zero rest of table up to 8 bits.
  80.  
  81. ;
  82. ; Initialize input state and output stack to prepare for first call to
  83. ; GIF_DECOMPRESS.
  84. ;
  85. 30$:    CLRL    G^BITS_USED        ; Init buffer pointer.
  86.     CLRL    G^INBUF            ; Zero length of input buffer.
  87.     MNEGL    #1, G^PREV_CODE        ; No previous code.
  88.     MNEGL    #1, G^TABLE_SIZE    ; Indicates table just cleared.
  89.     MOVAB    G^STACK_TOP, -        ; Output stack is initially empty.
  90.         G^STACK_PTR
  91.     MOVL #1, R0            ; Return success.
  92.     RET
  93. ;
  94. ; Define main routine for decompressing.
  95. ;
  96.     .ENTRY GIF_DECOMPRESS, ^M<R2,R3,R4,R5,R6,R7,R8,R9,R10,R11>
  97. ;
  98. ; Move variables into registers and make copy of argument list.  Note that
  99. ; the value of AP was made to correspond to the top of the output stack 
  100. ; in order to simplify testing for an empty stack (R10 >= AP).
  101. ;
  102.     ASHL    G^CODE_BITS, #1, R1    ; Compute new max value.
  103.     DECL    R1            ;    as 2^code_bits - 1
  104. ;    CLRL    R2            ; R2 is input code value.
  105.     MOVAW    G^PREFIX, R3        ; Base address of PREFIX table
  106.     MOVAB    G^EXTENSION, R4        ; Base address of EXTENSION table
  107.     MOVL    G^TABLE_SIZE, R5    ; Number of codes defined.
  108.     MOVL    G^PREV_CODE, R6        ; Previous input code
  109.     MOVL    G^BITS_USED, R7        ; Number of bit within cur. buffer used.
  110.     MOVL    G^CODE_BITS, R8        ; Input code size.
  111.     MOVZWL    G^INBUF, R9        ; Current # of bytes in input buffer.
  112.     ASHL    #3, R9, R9        ;   Convert to number of bits in buffer.
  113.     MOVL    G^STACK_PTR, R10    ; Recover current output stack position.
  114.     MOVL    16(AP), R11        ; Output pointer.
  115.     MOVQ    4(AP), G^<ARG_LIST+4>    ; Copy args 1 and 2.
  116.     MOVQ    12(AP), G^<ARG_LIST+12>    ; Copy args 3 and 4.
  117.     MOVAL    G^<ARG_LIST>, AP    ; Make new AP that overlaps with
  118.                     ;   the address of the stack top.
  119.     MOVL    12(AP), R0        ; Size of output buffer.
  120.     MOVAB    (R11)[R0], 12(AP)    ; 12(AP) now has overflow address
  121.     BRB    CHECK_IF_DONE        ; Jump into loop.
  122. ;
  123. ; When done, save registers back to memory to preserve for next call.
  124. ;
  125. DONE:
  126.     MOVL    R5, G^TABLE_SIZE    ; Save table size
  127.     MOVL    R6, G^PREV_CODE     ; Save previous code
  128.     MOVL    R7, G^BITS_USED        ; Save # bits used out of input buffer.
  129.     MOVL    R8, G^CODE_BITS        ; save current code bits.
  130.     MOVL    R10, G^STACK_PTR    ; Save stack pointer.
  131.     MOVL    #1, R0            ; Set success status
  132.     RET                ;     and return
  133. ;
  134. ; Handle case where input code is split between buffers.
  135. REFILL:
  136.     BSBW    SPAN_BUFFER        ; do work.
  137.     ASHL    R8, #1, R1        ; Regenerate max value.
  138.     DECL    R1            ;   as 2^code_bits - 1
  139.     BRB    CHECK_CODE        ; Rejoin loop to process R2.
  140. ;
  141. ; Main loop processes input codes until we've filled the user's buffer.
  142. ; take 26 instructions/input code with 1 branch and 12 memory references.
  143. ;
  144. ; Optimally, each input code executes 18 instructions plus 8 instructions
  145. ; for each output byte produced.  The number of branches taken is one less
  146. ; than twice the number of output bytes produced.  Each input code results
  147. ; in 1 PC relative deferred, 1 register deferred, 3 indexed register deferred
  148. ; and 2 immediate data memory references.  Each output byte results in
  149. ; 3 autoinc/dec, 1 byte displacement, and 2 indexed register deferred memory
  150. ; references.
  151. ;
  152.     .ALIGN    LONG
  153. OUTPUT_BYTE:
  154.     MOVB    (R10)+, (R11)+        ; Pop byte from stack, append to output
  155. CHECK_IF_DONE:
  156.     CMPL    R11, 12(AP)        ; Any room left in output buffer?
  157.     BGEQ    DONE            ; No, we are done
  158.     CMPL    R10, AP            ; Stack empty?
  159.     BLSS    OUTPUT_BYTE        ; No, copy to output buffer
  160. ;
  161. ;  process next input code, producing result on stack.
  162. ;
  163.     ADDL3    R7, R8, R0        ; bits-used + code_bits -> R0
  164.     CMPL    R0, R9            ; Is R0 > than number of bits in buffer
  165.     BGTR    REFILL             ; Yes, do special stuff.
  166.     EXTZV    R7, R8, @<INBUF+4>, R2    ; No, directly extract code.
  167.     MOVL    R0, R7            ; update pointer by code_bits amount
  168.  
  169. CHECK_CODE:
  170.     CMPW    (R3)[R2], #-2        ; is Code a special code (prefix -2)?
  171.     BEQL    SPECIAL_CODE        ;   Yes, handle it.
  172.     CMPL    R2, R5            ; Is code in table?
  173.     BGTR    OUT_OF_RANGE        ;   No, handle it.
  174.  
  175.     MOVL    R2, R0            ;   Yes, init loop variable to CODE
  176. 10$:
  177.     MOVB    (R4)[R0], -(R10)    ; Push extension char onto stack
  178.     CVTWL    (R3)[R0], R0        ; Replace code with prefix code
  179.     BGEQ    10$            ; If another code, continue
  180.                     ; else add to table.
  181. EXPAND_TABLE:
  182.     INCL    R5            ; Bump table size.
  183.     CMPL    R5, #4096        ; at max?
  184.     BGTR    40$             ; Yes, skip.
  185. 10$:
  186.     MOVW    R6, (R3)[R5]        ; Prefix for previous code in new code
  187.     MOVB    (R10), (R4)[R5]        ; Extension is last thing put on stack
  188.     MOVL    R2, R6            ; new previous code.
  189. 20$:
  190.     CMPL    R5, R1            ; Is table size < max for code size?
  191.     BLSS    OUTPUT_BYTE        ; yes, leave it alone
  192.     CMPL    R8, #12            ; no, is code_bits at max?
  193.     BGEQ    OUTPUT_BYTE        ; yes, leave alone
  194.     INCL    R8            ; no, go to next higher size.
  195.     ASHL    R8, #1, R1        ; Compute new max value.
  196.     DECL    R1
  197.     BRB    20$            ; test the new size.
  198. 40$:
  199.     MOVL    #4096, R5        ; Set to dummy entry.
  200.     BRB    10$
  201. ;--------------------------
  202. SPECIAL_CODE:
  203.     CMPL    R2, G^EOI_CODE        ; Is code end of information code.
  204.     BEQL    END_OF_INFORMATION
  205.  
  206.     CLRL    R8            ; Reset code size
  207. 10$:
  208.     INCL    R8            ; Increase size of code_bits.
  209.     ASHL    R8, #1, R1        ; max value for code bits.
  210.     DECL    R1
  211.     CMPL    G^EOI_CODE, R1        ; Is table size > max value forcode_bits
  212.     BGEQ    10$            ; Yes, try higher code size.
  213.  
  214.     MNEGL    #1, R5            ; Flag table size for first code.
  215.     BRW    CHECK_IF_DONE
  216. ;-----------------------------------
  217.  
  218. OUT_OF_RANGE:
  219.     ADDL3    R5, #1, R0        ; Compute table_size + 1?
  220.     BLEQ    FIRST_CODE        ; Table size was negative.
  221.     CMPL    R0, R2            ; Is code = table_size+1?
  222.     BNEQ    BAD_CODE         ; No abort.
  223. ;
  224. ; Special case, expand previous code onto stack and place final char in front.
  225.     DECL    R10            ; Make gap on stack.
  226.     MOVL    R6, R0            ; Set loop variable to prev_code
  227. 20$:
  228.     MOVB    (R4)[R0], -(R10)    ; Push onto stack
  229.     CVTWL    (R3)[R0], R0        ; Get prefix string
  230.     BGEQ    20$
  231.     MOVB    (R10), G^<STACK_TOP-1>    ; Copy last char to front.
  232.     BRW    EXPAND_TABLE        ; Add new code to table.
  233. ;-----------------------------------
  234. BAD_CODE:
  235.     MOVL    #20, R0            ; Bad parameter status.
  236.     RET
  237. END_OF_INFORMATION:
  238.     MOVL    #2160, R0
  239.     RET
  240. ;-----------------------------------
  241. FIRST_CODE:
  242.     MOVL    R2, R6            ; Update previous code.
  243.     MOVB    (R4)[R2], -(R10)    ; Push onto stack
  244.     MOVL    G^EOI_CODE, R5
  245.     BRW    OUTPUT_BYTE
  246. ;-----------------------------------
  247. ;
  248. ; Define subroutine to handle getting input code when buffer spans
  249. ; boundaries.
  250. ;
  251. ; Input:
  252. ;    R7    Number of bits used in INBUF
  253. ;    R8    Code size (number of bits to extract).
  254. ;    R9    Number of bits in INBUF, we assume (R7+R8) > R9
  255. ;
  256. ; Output:
  257. ;    R0,R1    Destroyed
  258. ;    R2    Code.
  259. ;    R7    Number of bits used in INBUF
  260. ;    R9    Totoal number of bits in INBUF
  261. ;
  262. SPAN_BUFFER:
  263.     SUBL3    R7, R9, R0        ; Calculate bits left in buffer
  264.     PUSHL    R0            ; save for later use
  265.     EXTZV    R7, R0, @<INBUF+4>, R2    ; Get remaining bits.
  266.     ADDL    R8, R7            ; Make phantom bits-used.
  267. 50$:
  268.     MOVAL    G^INBUF, -(SP)        ; Output descriptor
  269.     MOVL    8(AP), -(SP)        ; user arg for input routine
  270.     CALLS    #2, @4(AP)        ; Get input
  271.     BLBC     R0, 100$        ; abort if error.
  272.     MOVL    (SP)+, R0        ; Recover # bits taken from last buffer
  273.     SUBL    R9, R7            ; Number of overflow bits becomes # used
  274.     MOVZWL    G^INBUF, R9        ; Current # of bytes in input buffer.
  275.     ASHL    #3, R9, R9        ; Convert to number of bits.
  276.     CMPL    R9, R7            ; Is number of bits to take more
  277.     BLSS    110$            ; Yes, go to special case.
  278.     EXTZV    #0, R7, @<INBUF+4>, R1    ; No, extract the bits.
  279.     ASHL    R0, R1, R0        ; Shift over by overflow amount
  280.     BISL    R0, R2            ; OR into output code.
  281.     RSB
  282. 100$:
  283.     RET
  284. ;
  285. ; Handle the rare case where more bits left to extract than bits in
  286. ; buffer read.
  287. 110$:
  288.     EXTZV #0, R9, -            ; Extract entire buffer.
  289.         @<INBUF+4>, R1
  290.     ASHL    R0, R1, R0        ; Shift over
  291.     BISL    R0, R2            ; Add to result
  292.     ADDL3    R9, R0, -(SP)        ; update number of bits to shift
  293.     BRB     50$            ; read another buffer.
  294. ;
  295.     .END
  296.