;                 EXP2.ASM as of April 29, 1981
; 
;  This  routine is extracted and CP/Mified from an  article 
; 'An  Inroduction  to Data Compression' by  Harold  Corbin, 
; that appeared in the April 1981 issue of Byte magazine.
; 
; CP/Mified by: Kelly Smith, CP/M-Net "SYSOP" April 29, 1981
; 
;  EXP2  (text  expansion routine) accepts data prepared  by 
; the COMP2 (text compression routine) program.  The program 
; runs  until  all bits have been processed  from  the  data 
; buffer (dbuf),  then returns control to CP/M. The decoding 
; process  consists of adding a data bit to the table  entry 
; point,  getting an increment index that points to the next 
; 0-1 pair,  and continues until a "tag" (MSB = 1) in bit 7, 
; indicates  that  the  next  table  entry  is  the  desired 
; character.  The  data are processed 8 bits per  byte,  MSB 
; first.
; 
;  The Huffman Code was derived for the following table,  by 
; the  relative frequency of occurence in a random  sampling 
; of English text.  Frequently used characters are  assigned 
; shorter  bit 'code' patterns,  and seldom used  characters 
; are  assigned longer bit 'code' patterns.  Note:  with any 
; set of codes generated, it is important that no code has a 
; shorter code as part of its beginning. For example, if the 
; letter  'E'  is 100,  then 10010 cannot be  the  code  for 
; another  letter...because in scanning the bit stream  from 
; left  to right (using EXP2,  the text expansion  routine), 
; the decoding algorithm would think that 10010 is 'E' (100) 
; followed  by  10  and NOT the different  letter  that  was 
; intended.
; 
;           Letter    Frequency (%)  Huffman Code
; 
;           E         13.0           100
;           T         10.5           001
;           A          8.1           1111
;           O          7.9           1110
;           N          7.1           1100
;           R          6.8           1011
;           I          6.3           1010
;           S          6.1           0110
;           H          5.2           0101
;           D          3.8           11011
;           L          3.4           01111
;           F          2.9           01001
;           C          2.7           01000
;           M          2.5           00011
;           U          2.4           00010
;           G          2.0           00001
;           Y          1.9           00000
;           P          1.9           110101
;           W          1.5           011101
;           B          1.4           011100
;           V           .9           1101001
;           K           .4           110100011
;           X           .15          110100001
;           J           .13          110100000
;           Q           .11          1101000101
;           Z           .07          1101000100
; 
;  The  EXP2 program expects to find the data to be decoded, 
; in the packed form of 8 bit bytes as encoded by COMP2,  in 
; the data buffer (dbuf).  Basically, the program searches a 
; binary  tree to decode the bit stream generated by  COMP2, 
; selecting  the  appropriate branch in the  tree  structure 
; depending  upon the value of each bit in the data  stream. 
; Note: the data in the table is uniquely dependent upon the 
; code generated by COMP2.
; 
;  There are three parts to the table structure:  the  index 
; values   that  allow  the  program  to  step  through  the 
; appropriate number of table entries (i.e.,  tree branches) 
; as the data stream bit values are serially  examined;  the 
; decoded  character that results from the search;  and  the 
; flag  to indicate to the program that the next table entry 
; found  is a character and not an index  value.  The  index 
; values  are always in pairs,  with a separate index  value 
; for a 1 or a 0 bit stream value. Therefore, as the program 
; scans through the table at each pair of index values,  one 
; or  the other is selected,  depending upon whether the bit 
; in khe data stream was a 1 or a 0.
; 
;  The  table scanning process consists of adding  the  data 
; bit to the current table address. This gives a new address 
; whose contents (an index value) is added to the address of 
; the  index  value itself...this new table address  is  the 
; address  of  the  next node in the  tree  structure.  This 
; process  continues until a flag  is  detected,  indicating 
; that the next entry is the desired character.  If the flag 
; is  on (MSB = 1),  the remaining 7 bits are interpreted as 
; an  ASCII character.  If the flag is off (MSB  =  0),  the 
; remaining  bits  are interpreted as an index  value.  This 
; limits  the index value to 127,  the maximum value in  the 
; table that can be skipped when processing one data bit.
; 
; 
;
true	equ	-1	; define true
false	equ	not true; define false
;
stdcpm	equ	true	; true if regular CP/M (base address 0000h)
altcpm	equ	false	; true if alternate CP/M (base address 4200h)
;
	if	stdcpm	; if standard CP/M...
base	equ	0000h	; bsae for standard CP/M system
	endif		; end if...
;
	if	altcpm	; if alternate CP/M...
base	equ	4200h	; base for H8 or TRS-80 CP/M system
	endif		; end if...
;
bdos	equ	base+5	; CP/M BDOS entry address for function call
;
conout	equ	2	; write console character
;
dbuf	equ	04000h	; data buffer for compressed data
;

	org	base+100h

start:	lxi	h,0	; save "old" CP/M stack pointer
	dad	sp
	shld	oldstk
	lxi	sp,stack; make "new" stack pointer
	lxi	h,dbuf+2; store pointer to next bit location in data buffer
	shld	dadd
	lxi	h,dbuf	; point to data buffer bit count
	mov	c,m	; get it...
	inx	h
	mov	b,m
	mvi	a,1	; set initial position
	sta	pos
expand:	push	b	; save bit count on the stack
	lxi	h,expansion$table	; point to expansion decode table
next:	push	h	; save pointer on the stack
	lhld	dadd	; get data address bit position
	lda	pos	; get bit position
	mov	b,a
	mov	a,m	; get the data
bit:	ral		; get desired bit into carry
	dcr	b	; de-bump bit position count
	jnz	bit	; loop 'til done
	mvi	a,0	; clear data, but preserve carry
	ral		; restore single isolated bit
	mov	c,a	; ...the data value
	mvi	b,0
	shld	dadd	; save data address bit position
	pop	h	; recover pointer
	dad	b	; make bias to table with data bit position
	mov	a,m	; get new pointer
	ral		; check if "tag" bit...
	jc	put$character
	rar		; restore to original position
	mov	e,a	; make bias
	mvi	d,0
	dad	d	; calculate 'tabel'+'data bit'+'pointer'
	pop	b	; recover bit count
	call	decb	; reduce bit count
	push	b
	jmp	next	; process next character
;
put$character:
;
	rar		; restore byte to original position
	ani	07fh	; mask-off "tag" bit
	mov	e,a	; compute bias to expansion table
	mvi	d,0
	dad	d	; add bias
	mov	a,m	; get expanded character from table
	push	b	; save all registers
	push	d
	push	h
	mov	e,a	; CP/M needs character in E register
	mvi	c,conout; output character function
	call	bdos
	pop	h	; recover registers
	pop	d
	pop	b
	pop	b	; adust stack, get bit count
	call	decb	; reduce bit count
	jmp	expand	; expand next character
;
decb:	dcx	b	; reduce bit count
	mov	a,c	; check for all characters expanded
	ora	b
	jz	exit	; if all characters expanded, exit to CP/M
	lda	pos	; get bit position, and update
	inr	a
	sta	pos
	cpi	9	; all 8 bits processed?
	rnz		; return, if not...
	mvi	a,1	; all bits processed, reset bit position
	sta	pos
	push	h	; save table pointer on stack
	lhld	dadd	; get current data byte address, and update
	inx	h
	shld	dadd
	pop	h	; recover table pointer
	ret		; process next bit...
;
exit:	lhld	oldstk	; get "old" CP/M stack pointer
	sphl		; and restore...
	ret		; return to CP/M
;
expansion$table:
;
	db	02ah	; 0	0
	db	001h	; 1	1
	db	002h	; 2	0
	db	008h	; 3	1
	db	082h	; 4	0
	db	002h	; 5	1
	db	'E'	; 6		'E'
	db	082h	; 7	0
	db	082h	; 8	1
	db	'I'	; 9		'I'
	db	'R'	; 10		'R'
	db	006h	; 11	0
	db	001h	; 12	1
	db	082h	; 13	0
	db	082h	; 14	1
	db	'O'	; 15		'O'
	db	'A'	; 16		'A'
	db	082h	; 17	0
	db	002h	; 18	1
	db	'N'	; 19		'N'
	db	003h	; 20	0
	db	081h	; 21	1
	db	'D'	; 22		'D'
	db	003h	; 23	0
	db	081h	; 24	1
	db	'P'	; 25		'P'
	db	003h	; 26	0
	db	081h	; 27	1
	db	'V'	; 28		'V'
	db	002h	; 29	0
	db	005h	; 30	1
	db	082h	; 31	0
	db	082h	; 32	1
	db	'J'	; 33		'J'
	db	'X'	; 34		'X'
	db	003h	; 35	0
	db	081h	; 36	1
	db	'K'	; 37		'K'
	db	082h	; 38	0
	db	082h	; 39	1
	db	'Z'	; 40		'Z'
	db	'Q'	; 41		'Q'
	db	002h	; 42	0
	db	00eh	; 43	1
	db	003h	; 44	0
	db	081h	; 45	1
	db	'T'	; 46		'T'
	db	002h	; 47	0
	db	005h	; 48	1
	db	082h	; 49	0
	db	082h	; 50	1
	db	'Y'	; 51		'Y'
	db	'G'	; 52		'G'
	db	082h	; 53	0
	db	082h	; 54	1
	db	'U'	; 55		'U'
	db	'M'	; 56		'M'
	db	002h	; 57	0
	db	008h	; 58	1
	db	003h	; 59	0
	db	081h	; 60	1
	db	'H'	; 61		'H'
	db	082h	; 62	0
	db	082h	; 63	1
	db	'C'	; 64		'C'
	db	'F'	; 65		'F'
	db	082h	; 66	0
	db	002h	; 67	1
	db	'S'	; 68		'S'
	db	003h	; 69	0
	db	081h	; 70	1
	db	'L'	; 71		'L'
	db	082h	; 72	0
	db	082h	; 73	1
	db	'B'	; 74		'B'
	db	'W'	; 75		'W'
;
dadd:	dw	dbuf+2	; next data address
;
pos:	ds	1	; current bit location
;
oldstk:	ds	2	; storage for "old" CP/M stack pointer
	ds	32	; storage for 16 level stack
stack	equ	$	; top of local stack
;
	end	start
