home *** CD-ROM | disk | FTP | other *** search
/ CP/M / CPM_CDROM.iso / simtel / sigm / vols000 / vol040 / comp2.asm < prev    next >
Assembly Source File  |  1984-04-29  |  8KB  |  233 lines
  1. ;                COMP2.ASM as of April 29, 1981
  2. ; 
  3. ;  This  routine is extracted and CP/Mified from an  article 
  4. ; 'An  Inroduction  to Data Compression' by  Harold  Corbin, 
  5. ; that appeared in the April 1981 issue of Byte magazine.
  6. ; 
  7. ; CP/Mified by: Kelly Smith, CP/M-Net "SYSOP" April 29, 1981
  8. ; 
  9. ;  COMP2  (text  compression  routine) takes  keyboard  text 
  10. ; (uppercase  letters  ONLY) and compresses them  using  the 
  11. ; Huffman coding technique.  The first two bytes in the data 
  12. ; buffer (dbuf) are the bit count. Encoded data is stored in 
  13. ; the data buffer in packed form, 8 bits to the data byte.
  14. ; 
  15. ;  The Huffman Code was derived for the following table,  by 
  16. ; the  relative frequency of occurence in a random  sampling 
  17. ; of English text.  Frequently used characters are  assigned 
  18. ; shorter  bit 'code' patterns,  and seldom used  characters 
  19. ; are  assigned longer bit 'code' patterns.  Note:  with any 
  20. ; set of codes generated, it is important that no code has a 
  21. ; shorter code as part of its beginning. For example, if the 
  22. ; letter  'E'  is 100,  then 10010 cannot be  the  code  for 
  23. ; another  letter...because in scanning the bit stream  from 
  24. ; left  to right (using EXP2,  the text expansion  routine), 
  25. ; the decoding algorithm would think that 10010 is 'E' (100) 
  26. ; followed  by  10  and NOT the different  letter  that  was 
  27. ; intended.
  28. ; 
  29. ;           Letter    Frequency (%)  Huffman Code
  30. ; 
  31. ;           E         13.0           100
  32. ;           T         10.5           001
  33. ;           A          8.1           1111
  34. ;           O          7.9           1110
  35. ;           N          7.1           1100
  36. ;           R          6.8           1011
  37. ;           I          6.3           1010
  38. ;           S          6.1           0110
  39. ;           H          5.2           0101
  40. ;           D          3.8           11011
  41. ;           L          3.4           01111
  42. ;           F          2.9           01001
  43. ;           C          2.7           01000
  44. ;           M          2.5           00011
  45. ;           U          2.4           00010
  46. ;           G          2.0           00001
  47. ;           Y          1.9           00000
  48. ;           P          1.9           110101
  49. ;           W          1.5           011101
  50. ;           B          1.4           011100
  51. ;           V           .9           1101001
  52. ;           K           .4           110100011
  53. ;           X           .15          110100001
  54. ;           J           .13          110100000
  55. ;           Q           .11          1101000101
  56. ;           Z           .07          1101000100
  57. ; 
  58. ;  The  COMP2  program  takes  characters  entered  via  the 
  59. ; keyboard,  checks for a legal character, finds the Huffman 
  60. ; Code  corresponding  to  the entered  character,  and  the 
  61. ; serial  bit stream that results from the encoding  process 
  62. ; is packed and stored 8 bits to the byte.
  63. ; 
  64. ;  The heart of the program's operation is the table  lookup 
  65. ; and shifting function.  Based upon a letter ASCII code, an 
  66. ; index  is computed that is then added to the base  address 
  67. ; of  the  encoding  table.  This table  has  the  following 
  68. ; format: two 8 bit words are required for each letter to be 
  69. ; encoded;  the low order 4 bits of the first word in memory 
  70. ; contain  a count of the number of bits required to  encode 
  71. ; the  letter.  The remaining 12 bits,  8 in the second byte 
  72. ; followed  by 4 in the top half of the first byte are  used 
  73. ; to  store the compressed code.  The code is  stored  left-
  74. ; justified in the 12 bit word.
  75. ; 
  76. ;  With  the compressing code located,  it is serialized  by 
  77. ; shifting  left according to the count in the 4 bit part of 
  78. ; the table. As each bit is shifted out, the total bit count 
  79. ; in  the  buffer is updated.  The processing of  the  input 
  80. ; stream  continues  until a period  (.)  is  detected,  and 
  81. ; control  returns to CP/M.  The data buffer at address 4000 
  82. ; Hex then remains intact for expansion by EXP2.
  83. ; 
  84. ; 
  85. ; 
  86. true    equ    -1    ; define true
  87. false    equ    not true; define false
  88. ;
  89. stdcpm    equ    true    ; true if regular CP/M (base address 0000h)
  90. altcpm    equ    false    ; true if alternate CP/M (base address 4200h)
  91. ;
  92.     if    stdcpm    ; if standard CP/M...
  93. base    equ    0000h    ; bsae for standard CP/M system
  94.     endif        ; end if...
  95. ;
  96.     if    altcpm    ; if alternate CP/M...
  97. base    equ    4200h    ; base for H8 or TRS-80 CP/M system
  98.     endif        ; end if...
  99. ;
  100. bdos    equ    base+5    ; CP/M BDOS entry address for function call
  101. ;
  102. rdcon    equ    1    ; read console character
  103. ;
  104. dbuf    equ    04000h    ; data buffer for compressed data
  105. ;
  106.     org    base+100h
  107.  
  108. start:    lxi    h,0    ; save "old" CP/M stack pointer
  109.     shld    dbuf    ; clear compressed bit count
  110.     dad    sp
  111.     shld    oldstk
  112.     lxi    sp,stack; make "new" stack pointer
  113.     lxi    h,dbuf+2; store pointer to next bit location in data buffer
  114.     shld    dadd
  115.     xra    a    ; clear bit position
  116.     sta    pos
  117. ;
  118. ; get character from keyboard, check if end of text '.' character
  119. ;
  120. get$character:
  121. ;
  122.     push    b    ; save reigisters
  123.     push    d
  124.     push    h
  125.     mvi    c,rdcon    ; read console character function
  126.     call    bdos
  127.     pop    h    ; restore registers
  128.     pop    d
  129.     pop    b
  130.     ani    07fh    ; mask-off parity bit
  131.     cpi    '.'    ; end of text?
  132.     jnz    process    ; if not, process this character
  133.     lhld    dadd    ; clean up partial byte remaining
  134.     lda    pos    ; compute remaining shift count
  135.     mov    b,a
  136.     mvi    a,8
  137.     sub    b
  138.     ani    7
  139.     mov    b,a    ; keep shift count
  140.     mov    a,m    ; get compressed byte
  141. shift:    jz    exit    ; exit to CP/M, if all bytes processed
  142.     ral
  143.     dcr    b
  144.     mov    m,a    ; replace compressed byte
  145.     jmp    shift    ; loop 'till done
  146. process:sui    'A'    ; character < 'A'?
  147.     jc    get$character
  148.     cpi    'Z'-'A'+1    ; character > 'Z'?
  149.     jnc    get$character
  150.     add    a    ; multiply by 2 to get table index
  151.     mov    c,a
  152.     mvi    b,0    ; make index bias to table
  153.     lxi    h,compression$table    ; point to base of table
  154.     dad    b    ; add index bias to table pointer
  155.     mov    e,m    ; get encoded value
  156.     inx    h
  157.     mov    d,m
  158.     mov    a,e    ; get bit count for this character
  159.     ani    00fh    ; mask-off high nibble
  160.     mov    b,a    ; keep bit count
  161.     xchg        ; swap pointer for encoded value
  162. next:    xra    a
  163.     dad    h    ; shift out bit stream...
  164.     ral        ; ...MSB first
  165.     ani    1    ; mask-off all but output bit
  166.     push    h
  167.     lhld    dadd    ; get pointer to next bit location
  168.     mov    d,a
  169.     lda    pos    ; get current bit position
  170.     mov    e,a    ; keep it
  171.     mov    a,m    ; get "old" compressed data
  172.     ral        ; make room...
  173.     ora    d    ; ...compress
  174.     mov    m,a    ; save it, done with this compression
  175.     inr    e    ; update position
  176.     mov    a,e
  177.     cpi    8    ; full byte processed?
  178.     jnz    stor
  179.     xra    a    ; clear position
  180.     inx    h    ; bump for next bit location
  181.     shld    dadd
  182. stor:    sta    pos
  183.     lhld    dbuf    ; update compressed bit count
  184.     inx    h
  185.     shld    dbuf
  186.     pop    h
  187.     dcr    b    ; de-bump count
  188.     jnz    next    ; continue compression, if not done
  189.     jmp    get$character    ; get next character, and compress
  190. ;
  191. exit:    lhld    oldstk    ; get "old" CP/M stack pointer
  192.     sphl        ; and restore...
  193.     ret        ; return to CP/M
  194. ;
  195. compression$table:
  196. ;
  197.     dw    0f004h    ; 'A'
  198.     dw    07006h    ; 'B'
  199.     dw    04005h    ; 'C'
  200.     dw    0d805h    ; 'D'
  201.     dw    08003h    ; 'E'
  202.     dw    04805h    ; 'F'
  203.     dw    00805h    ; 'G'
  204.     dw    05004h    ; 'H'
  205.     dw    0a004h    ; 'I'
  206.     dw    0d009h    ; 'J'
  207.     dw    0d189h    ; 'K'
  208.     dw    07805h    ; 'L'
  209.     dw    01805h    ; 'M'
  210.     dw    0c004h    ; 'N'
  211.     dw    0e004h    ; 'O'
  212.     dw    0d406h    ; 'P'
  213.     dw    0d14ah    ; 'Q'
  214.     dw    0b004h    ; 'R'
  215.     dw    06004h    ; 'S'
  216.     dw    02003h    ; 'T'
  217.     dw    01005h    ; 'U'
  218.     dw    0d207h    ; 'V'
  219.     dw    07406h    ; 'W'
  220.     dw    0d089h    ; 'X'
  221.     dw    00005h    ; 'Y'
  222.     dw    0d10ah    ; 'Z'
  223. ;
  224. dadd:    dw    0    ; next bit location
  225. ;
  226. pos:    ds    1    ; current bit location
  227. ;
  228. oldstk:    ds    2    ; storage for "old" CP/M stack pointer
  229.     ds    32    ; storage for 16 level stack
  230. stack    equ    $    ; top of local stack
  231. ;
  232.     end    start
  233.