From:	CRDGW2::CRDGW2::MRGATE::"SMTP::KCGL1.ENG.OHIO-STATE.EDU::JONESD" 21-JUN-1989 14:52
To:	MRGATE::"ARISIA::EVERHART"
Subj:	Appendum to compress/decomress routines: bitpack routines

Message-Id:  <8906211842.AA13357@crdgw1.ge.com>
Date: Wed, 21 Jun 89 14:42 EDT
From: Dave Jones <JONESD@kcgl1.eng.ohio-state.edu>
Subject: Appendum to compress/decomress routines: bitpack routines
To: everhart@arisia.decnet
X-Vms-To: IN%"everhart%arisia.decnet@crdgw1.ge.com"

I made a casual scan of the file containing the LZ_COMPRESS routines and
noticed a dependency upon LZ_MAX_BIT.  Here is the set of routines I wrote
for bit packing/unpacking.  Dealing with bit fields is hard to do in fortran,
and even harder to do efficiently. This set was the third iteration.

>>Dave
------------------------------------------------------------------------------
C	Handle compressing-decompressing code values into variable length
C	bit fields.
C	    BITS = LZ_MAX_BIT ( min-field-size, max-value )
C	    CALL LZ_PACK_CODE ( CODE, BITS, POS, BUFFER )
C	    CALL LZ_UNPACK_CODE ( BITS, POS, BUFFER, CODE )
C
	INTEGER FUNCTION LZ_MAX_BIT ( MIN_FIELD, VALUE )
C+
C**	    Function LZ_MAX_BIT
C	This utility function returns the maximum of the number of bits needed 
C	to encode a specified value and a specified minimum.  The minimum
C	value is present in order to speed up calculation since we expect
C	values to increase incrementally of successive calls.  MIN_FIELD
C	is usually the LZ_MAX_BIT returned for VALUE-1, in which case all
C	we are effectively doing is checking for value to cross the next
C	threshold.
C
C	Author:	David Jones
C	Date:	24-AUG-1988
C
C	Input:
C	    MIN_FIELD	Integer.  Minimum return value for LZ_MAX_BIT
C	    VALUE     	Integer.  Value we wish to encode.  Must be
C			in range 0 - 2^20-1
C-
	IMPLICIT NONE
	INTEGER MIN_FIELD, VALUE
C
C	The array MAX_VALUE(I) stores the maximum possible value that
C	can be stored in I bits.
C
	INTEGER I, MAX_VALUE ( 20 ) / 1, '03'X, '07'X, '0F'X, 
	1	'1F'X, '3F'X, '7F'X, '0FF'X, 
	2	'1FF'X, '3FF'X, '7FF'X, '0FFF'X, 
	3	'1FFF'X, '3FFF'X, '7FFF'X, '0FFFF'X, 
	4	'1FFFF'X, '3FFFF'X, '7FFFF'X, '7FFFFFFF'X /
C
C	Scan for first field size into which VALUE will fit.
C
	I = MIN_FIELD
	DO WHILE ( VALUE .GT. MAX_VALUE ( I ) )
	    I = I + 1
	END DO
	LZ_MAX_BIT = I
	END
C
	SUBROUTINE LZ_PACK_CODE ( CODE, BITS, POS, BUFFER )
C+
C**	    Subroutine LZ_PACK_CODE
C	Pack the low BITS numbre of bts out of CODE value into buffer.
C	We must not attempt to pack more bits into buffer than exist.
C
C	Author:	David Jones
C	Date:	24-AUG-1988
C
C	Input:
C	    CODE	Integer.  Value to be added to buffer.
C	    BITS	Integer.  Number of bits of value to pack.
C	Modified:
C	    POS		Integer.  Maintains buffer buffer position at
C			which to write the code value.  Initialize to 0 to
C			set to beginnin of buffer.
C	    BUFFER	Byte array(8192).  Buffer containing packed values.
C-
	IMPLICIT NONE
	INTEGER CODE, BITS, POS, BUFFER(0:1023)
	BYTE OUT(4)
	INTEGER WORK, I, START, FINISH, MASK, OV_BITS
	BYTE WORK_B(4)
	EQUIVALENCE ( WORK, WORK_B )
C
C	The array element MAX_VALUE(I) stores the maximum possible value that
C	can be stored in I bits.
C
	INTEGER MAX_VALUE ( 0:32 ) / 0, 1, '03'X, '07'X, '0F'X, 
	1	'1F'X, '3F'X, '7F'X, '0FF'X, 
	2	'1FF'X, '3FF'X, '7FF'X, '0FFF'X, 
	3	'1FFF'X, '3FFF'X, '7FFF'X, '0FFFF'X, 
	4	'1FFFF'X, '3FFFF'X, '7FFFFF'X, '0FFFFF'X,
	5	'1FFFFF'X, '3FFFFF'X, '7FFFFFF'X, '0FFFFFF'X,
	6	'1FFFFFF'X, '3FFFFFF'X, '7FFFFFF'X, '0FFFFFFF'X,
	7	'1FFFFFFF'X, '3FFFFFFF'X, '7FFFFFFF'X, 'FFFFFFFF'X/
C
C	Determine which elements will receive fragments
C
	START = ISHFT ( POS, -5 )
	FINISH = ISHFT ( POS+BITS-1, -5 )
C
C	Insert first part.
C
	MASK = ISHFT ( MAX_VALUE(BITS), IAND(POS,31) )
	BUFFER(START) = IAND ( BUFFER(START), NOT(MASK) ) ! clear field
	MASK = IAND ( MASK, ISHFT(CODE, IAND(POS,31)) )
	BUFFER(START) = IOR ( BUFFER(START), MASK )
C
	IF ( START .NE. FINISH ) THEN
C
C	    Add overflow into next higher space.
C
	    OV_BITS = BITS - (32-IAND(POS,31))
	    BUFFER(FINISH) = IAND(BUFFER(FINISH), NOT(MAX_VALUE(OV_BITS)))
	    MASK = ISHFT(CODE,OV_BITS-BITS)
	    BUFFER(FINISH) = IOR ( BUFFER(FINISH), MASK )
	END IF
	POS = POS + BITS
C
	END
C
	SUBROUTINE LZ_UNPACK_CODE ( BITS, POS, BUFFER, CODE )
C+
C**	    Subroutine LZ_UNPACK_CODE
C	Extract next bitpacked value from a buffer.
C
C	Author:	David Jones
C	Date:	24-AUG-1988
C
C	Input:
C	    BITS	Integer.  Number of bits of value to pack.
C	Modified:
C	    POS		Integer.  Maintains buffer buffer position at
C			which to write the code value.  Initialize to 0 to
C			set to beginning of buffer.
C	    BUFFER	Byte array(8192).  Buffer containing packed values.
C	Output:
C	    CODE	Integer.  Value to be added to buffer.
C-
	IMPLICIT NONE
	INTEGER BITS, POS, BUFFER(0:1023), CODE
	BYTE IN(4)
	INTEGER WORK, I, START, FINISH, OV_BITS, MASK
	BYTE WORK_B(4)
	EQUIVALENCE ( WORK, WORK_B )
C
C	The array element MAX_VALUE(I) stores the maximum possible value that
C	can be stored in I bits.
C
	INTEGER MAX_VALUE ( 0:32 ) / 0, 1, '03'X, '07'X, '0F'X, 
	1	'1F'X, '3F'X, '7F'X, '0FF'X, 
	2	'1FF'X, '3FF'X, '7FF'X, '0FFF'X, 
	3	'1FFF'X, '3FFF'X, '7FFF'X, '0FFFF'X, 
	4	'1FFFF'X, '3FFFF'X, '7FFFFF'X, '0FFFFF'X,
	5	'1FFFFF'X, '3FFFFF'X, '7FFFFFF'X, '0FFFFFF'X,
	6	'1FFFFFF'X, '3FFFFFF'X, '7FFFFFF'X, '0FFFFFFF'X,
	7	'1FFFFFFF'X, '3FFFFFFF'X, '7FFFFFFF'X, 'FFFFFFFF'X/
C
C	Determine which segments contain the code.
C
	START = ISHFT ( POS, -5 )
	FINISH = ISHFT ( POS+BITS-1, -5 )
C
C	Extract lower part
C
	CODE = ISHFT ( BUFFER(START), -IAND(POS,31) )
	CODE = IAND(CODE,MAX_VALUE( MIN(BITS,32-IAND(POS,31)) ) )
C
	IF ( START .NE. FINISH ) THEN
C
	    OV_BITS = BITS -(32-IAND(POS,31))
	    MASK = IAND(BUFFER(FINISH),MAX_VALUE(OV_BITS))
	    CODE = IOR ( CODE, ISHFT(MASK,BITS-OV_BITS) )
	END IF
	POS = POS + BITS
C
	END
