Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watnot!watmath!clyde!cuae2!ihnp4!ptsfa!lll-lcc!pyramid!hplabs!felix!macintosh
From: macintosh@felix.UUCP
Newsgroups: mod.mac.sources
Subject: Unpit version 0.3.1 Source (part 2 of 3)
Message-ID: <2278@felix.UUCP>
Date: Fri, 13-Feb-87 02:41:22 EST
Article-I.D.: felix.2278
Posted: Fri Feb 13 02:41:22 1987
Date-Received: Sat, 14-Feb-87 14:53:04 EST
References: <2277@felix.UUCP>
Sender: macintosh@felix.UUCP
Reply-To: macintosh@felix.UUCP (The Moderator)
Organization: FileNet Corp., Costa Mesa, Ca.
Lines: 603
Approved: bytebug@felix.UUCP (Roger L. Long)

[Unpit version 0.3.1 Source - part 2 of 3]

---
	    }
	    DisposDialog(theDialog); theDialog = 0L;
	    decode = 0;
	    bit = 0;	/* flush unused bits */
	    }
	else if (str_cmp_4(temp, "PEnd"))
	    break;
	else {
	    Err2(errNotPackit);
	    return;
	    }
    }
error:				/* should never be reached except by "goto" */
    if (theDialog != 0L)
        DisposDialog(theDialog);
    return;
}

/*
Read compression decoding data.
##############################   Read_Tree   ##############################

    This routine recursively reads the compression decoding data.
    It appears to be Huffman compression.
    
*/

nodeptr read_tree(eflag)
Boolean *eflag;
{	int bit;

	nodeptr np;
	np = freenode++;
	bit = getbit(eflag); if (*eflag) return (0L);
	if (bit == 1) {
		np->flag = 1;
		np->byte = getbyte(eflag); if (*eflag) return (0L);
	}
	else {
		np->flag = 0;
		np->zero = read_tree(eflag); if (*eflag) return (0L);
		np->one  = read_tree(eflag); if (*eflag) return (0L);
	}
	return(np);
}


/*
Read header containing information about the packed file to follow.
###############################   Read_Hdr   ##############################
*/

crctype read_hdr(eflag)
Boolean *eflag;
{
	register int n;

	for (n = 0; n < HDRBYTES; n++) {
		hdr[n] = getbyte(eflag);
		if (*eflag) return;
	}
	datalen = get4(hdr + H_DLENOFF);
	rsrclen = get4(hdr + H_RLENOFF);
	return(upd_crc(0, hdr, (long) HDRBYTES));
}


/*
Write one fork of an unpacked file.
##############################   Write_Fork   #############################

    saveOutput indicates whether or not the output should be saved; to skip
        a file it is still necessary to read it from the .PIT file in order
        to advance to the start of the next file that can be unpacked.

*/

crctype write_fork(saveOutput, out_ref_num, bytes, crc, eflag)
Boolean saveOutput, *eflag;
int out_ref_num;
long bytes;
register crctype crc;
{
	register int b, i;
	long Count;
	static char out_buffer[BSIZE];
	int out_index = 0;
	
	if ((decode == 0) && (bit == 0)) {
	    /* Special-case the unpacking of Packit-I files, as unpacking */
	    /* them using more general-purpose code takes >50% longer (33 */
	    /* vs 19 seconds when unpacking ResEdit on a RAMDisk).  While */
	    /* this code isn't very pretty, it gets the job done. . .     */

	    if ((bytes > 0) && ((Count = pit_max_index-pit_index) > 0L)) {
	        /* we won't be using read_byte(), so empty its buffer */
	        if (bytes < Count) Count = bytes;
	        if (saveOutput && Err(FSWrite(out_ref_num, &Count,
	            &pit_buffer[pit_index]),errWriting)) {
	            *eflag = TRUE; return 0;
	        }
	        crc = upd_crc(crc, &pit_buffer[pit_index], Count);
	        bytes -= Count; pit_index += (int) Count;
	    }

	    while (bytes > 0L) {
	        Count = (bytes >= BSIZE) ? BSIZE : bytes;
	        if (Err(FSRead (pit_ref_num,&Count,out_buffer),errReading) ||
	            (saveOutput && Err( /* this isn't the most elegant code */
		        FSWrite(out_ref_num,&Count,out_buffer),errWriting))) {
	            *eflag = TRUE;
	            return 0;
	        }
	        crc = upd_crc(crc, out_buffer, Count);
	        bytes -= Count; pit_bytes_left -= Count;
	    }
	} else {
	    while (bytes-- > 0) {
		b = getbyte(eflag); if (*eflag) return;
		crc = crc ^ (b << 8);
		for (i = 0; i < 8; i++)
			if (crc & 0x8000)
				crc = (crc << 1) ^ 0x1021;
			else
				crc <<= 1;
		if (saveOutput) {
		    if (out_index == BSIZE) {
			Count = (long) out_index;
			if (Err(FSWrite(out_ref_num, &Count, &out_buffer),
				errWriting)) {
			    *eflag = TRUE;
			    return 0;
			}
			out_index = 0;
    		    }
		    out_buffer[out_index++] = (char) b;
		}
	    }
	    if (saveOutput && (out_index > 0)) {
	        Count = (long) out_index;
	        if (Err(FSWrite(out_ref_num, &Count, &out_buffer),errWriting)) {
	            *eflag = TRUE;
	            return 0;
	        }
	    }
	}
	return(crc & 0xffff);
}

/*
Convert four input characters into a long.
#################################   Get4   #################################
*/
long
get4(bp)
char *bp;
{
	register int i;
	long value = 0;

	for (i = 0; i < 4; i++) {
		value <<= 8;
		value |= (*bp & BYTEMASK);
		bp++;
	}
	return(value);
}

/*
Read and return a two-byte CRC from the input file.
################################   GetCrc   ################################
*/
crctype getcrc(eflag)
Boolean *eflag;
{
	int value1, value2;
	
	value1 = getbyte(eflag) & BYTEMASK; if (*eflag) return 0;
	value2 = getbyte(eflag) & BYTEMASK; if (*eflag) return 0;
	return((value1 << 8) | value2);
}

/*
Copy n characters from p2 to p1.
#################################   Copy   #################################
*/
copy(p1, p2, n)
char *p1, *p2;
int n;
{
	while (n-- > 0)
		*p1++ = *p2++;
}


/*
Return the next bit in the input stream (MSB first).
################################   GetBit   ################################
*/
static char b;
getbit(eflag)
Boolean *eflag;
{
	if (bit == 0) {
		b = read_byte(eflag) & 0xff; if (*eflag) return 0;
		bit = 8;
	}
	bit--;
	return((b >> bit) & 1);
}

/*
Get the next virtual byte from the input file.
###############################   GetByte   ################################

    This routine returns the next 8 bits.  If decoding is on, it finds the
    byte in the decoding tree based on the bits from the input stream.  If
    decoding is not on, it either gets it directly from the input stream or
    puts it together from 8 calls to getbit(), depending upon whether or not
    we are currently on a byte boundary.  (Note: the calls to getbit() have
    been expanded inline in order to gain some speed . . . ((b >> bit) & 1)
    is used where the value of getbit(eflag) was used before, and it's
    preceded by the statements "if (bit == 0 {...}" and "bit--").
    
*/
getbyte(eflag)
Boolean *eflag;
{
	register nodeptr np;
	register int i, byt;
	
	if (decode) {
		np = nodelist;
		while (np->flag == 0) {
			if (bit == 0) {
				b = read_byte(eflag) & 0xff;
				if (*eflag) return 0;
				bit = 8;
			}
			bit--;
			np = ((int) ((b >> bit) & 1)) ? np->one : np->zero;
		}
		byt = np->byte;
	}
	else {
		if (bit == 0) {	/* on byte boundary? */
			byt = read_byte(eflag) & 0xff; if (*eflag) return 0;
			}
		else {		/* no, put a byte together */
			byt = 0;
			for (i = 8; i > 0; i--) {
				if (bit == 0) {
					b = read_byte(eflag) & 0xff;
					if (*eflag) return 0;
					bit = 8;
				}
				bit--;
				byt = (byt << 1) + (int) ((b >> bit) & 1);
			}
		}
	}
	return(byt);
}

/*
Create a Packit-I or -II format file containing files selected by the user.
#################################   Pack   ################################
*/
pack()
	{
	SFReply PitRecord;
    Point   where;
    int     pit_ref_num, i;
    Boolean Success;
    char   *msg;

    /* Get name of output file */
    where.h = PUT_FILE_X; where.v = PUT_FILE_Y;
    msg = Compress ? "\PSave Packit-II file as:" : "\PSave Packit-I file as:";
    SFPutFile(where,msg,"\PPackit.pit",0L,&PitRecord);
    if (! PitRecord.good) return;

    /* Create and open output file */
    if ((i=Create(PitRecord.fName,PitRecord.vRefNum,'UPIT','PIT '))==dupFNErr) {
        FSDelete(PitRecord.fName,PitRecord.vRefNum);
        i = Create(PitRecord.fName, PitRecord.vRefNum, 'UPIT', 'PIT ');
    }
    if (Err(i,errCreateFile)) return;
    if (Err(FSOpen(PitRecord.fName,PitRecord.vRefNum,&pit_ref_num),
            errOpenDataFk)) return;

     /* Call routine that does real work */
     Success = pack_files(pit_ref_num);
     FSClose(pit_ref_num);
     if (! Success) FSDelete(PitRecord.fName, PitRecord.vRefNum);
     FlushVol(0L, PitRecord.vRefNum);
}


/*
Pass the indicated file header, data fork, resource fork, and computed CRCs
through the supplied function "MyWrite".  This function saves some space in
"pack_files", as compressed files need to be scanned twice (once to get the
frequency counts, once to write the Huffman encodings for the bytes).

###########################    Run_Through_File   ##########################
*/
run_through_file(MyWrite,pit_ref_num,fileHeader,InpRecord,data_len,rsrc_len)
int      	(*MyWrite)();
int	        pit_ref_num;
unsigned char  *fileHeader;
long		data_len, rsrc_len;
SFReply        *InpRecord;
{   long	     Count, bytesLeft;
    register crctype crc;
    unsigned char    io_buffer[BSIZE], fileCRC[2];
    int		     inp_ref_num;


    /* Write file header */
    Count = HDRBYTES + 2;
    if (Err((*MyWrite)(pit_ref_num, &Count, fileHeader), errWriting))
        goto error;

    /* Initialize data/resource CRC */
    crc = 0;

    /* Copy file's data fork to Packit file, if it has one */
    if (bytesLeft = data_len) {
        if (Err(FSOpen(InpRecord->fName,InpRecord->vRefNum,&inp_ref_num),
    		          errOpenDataFk)) goto error;
        while (bytesLeft > 0L) {
            Count = (bytesLeft >= BSIZE) ? BSIZE : bytesLeft;
            if (Err(  FSRead  (inp_ref_num,&Count,io_buffer),errReading) ||
	        Err((*MyWrite)(pit_ref_num,&Count,io_buffer),errWriting)) {
	        FSClose(inp_ref_num);
                goto error;
            }
            crc = upd_crc(crc, io_buffer, Count);
            bytesLeft -= Count;
        }
        FSClose(inp_ref_num);
    }

    /* Copy file's resource fork to Packit file, if it has one */
    if (bytesLeft = rsrc_len) {
        if (Err(Open_Rsrc(InpRecord->fName,InpRecord->vRefNum,fsRdPerm,
    		          &inp_ref_num),errOpenRsrcFk)) goto error;
        while (bytesLeft > 0L) {
            Count = (bytesLeft >= BSIZE) ? BSIZE : bytesLeft;
            if (Err(  FSRead  (inp_ref_num,&Count,io_buffer),errReading) ||
	        Err((*MyWrite)(pit_ref_num,&Count,io_buffer),errWriting)) {
	        FSClose(inp_ref_num);
                goto error;
            }
            crc = upd_crc(crc, io_buffer, Count);
            bytesLeft -= Count;
        }
        FSClose(inp_ref_num);
    }

    /* Write file's data/resource CRC */
    fileCRC[0] = (((unsigned int) crc) >> 8) & 0xff;
    fileCRC[1] = (((unsigned int) crc) & 0xff);
    Count = 2;
    if (Err((*MyWrite)(pit_ref_num,&Count,fileCRC),errWriting)) goto error;
    return FALSE;
error:
    return TRUE;
}


/*
Allow FSWrite() to be passed as a parameter to Run_Through_File (above)
###############################   C_FSWrite   ##############################
*/
int C_FSWrite(arg1, arg2, arg3)
int	arg1;
long   *arg2;
char   *arg3;
{
    return FSWrite(arg1, arg2, arg3);
}


/*
Initialize frequency counts to zero.
###############################   InitCount   ##############################
*/
void init_count()
{   int i;

    for (i = 0; i < 256; i++) {
        nodelist[i].flag   = TRUE;
        nodelist[i].byte   = i;
        nodelist[i].index2 = 0;
        nodelist[i].count  = 0L;
        nodelist[i].zero   = 0L;
        nodelist[i].one    = 0L;
        }
}


/*
Build byte frequency counts on a buffer-by-buffer basis.
###############################   FreqCount   ##############################
*/
int freq_count(Dummy, Count, Buffer)
int            Dummy;
long          *Count;
unsigned char *Buffer;
{   long MyCount = *Count;

    while (MyCount--) {
        nodelist[*Buffer].count += 1;
        Buffer++;
    }
    return noErr;
}


/* Macros to simplify using an ordering relationship with a secondary key */
#define GTR(a,b) ((a->count  > b->count) ||\
                 ((a->count == b->count) && (a->index2  > b->index2)))
#define LEQ(a,b) ((a->count  < b->count) ||\
                 ((a->count == b->count) && (a->index2 <= b->index2)))


/*
Insert a new value into the heap in O(log(n)) time.
##############################   HeapInsert   ##############################
*/
void heapinsert(n)	/* standard heap insertion algorithm from a textbook */
int n;			/* inserts heap[n] into heap stored in heap[1...n-1] */
{   int      i, j;
    nodeptr  item;

    j = n;  i = n / 2;  item = heap[n];
    while ((i > 0) && GTR(heap[i], item)) {
        heap[j] = heap[i];
        j = i; i = i / 2;
    }
    heap[j] = item;
}


/*
Turn a tree whose left & right sons are heaps into a heap in O(log(n)) time.
##############################   HeapAdjust   ##############################
*/
void heapadjust(i, n)	/* standard heap adjustment algorithm */
int i, n;
{   int      j;
    nodeptr  item;

    j = 2 * i; item = heap[i];
    while (j <= n) {
        if ((j < n) && GTR(heap[j], heap[j+1])) j++;
        if (LEQ(item, heap[j])) break;
        heap[j / 2] = heap[j];
        j = 2 * j;
    }
    heap[j / 2] = item;
}


/*
Return the heap element with the smallest value and delete it from the heap.
################################   HeapMin   ###############################
*/
nodeptr heapmin(n)
int *n;
{   nodeptr item;

    item = heap[1];
    heap[1] = heap[*n];
    if (*n -= 1) heapadjust(1, *n);
    return item;
}


/*
Build a minimum weighted binary tree using the counts in nodelist[0..255].
###############################   BuildTree   ##############################
*/
nodeptr build_tree()
{   int      i, n, gen;
    nodeptr  lson, rson, nnod, free;
    	 
    n = 0; free = 0L; gen = 0;
    for (i = 256; i < 512; i++) {	/* All nodes that we know don't */
        nodelist[i].zero = free;	/*     contain frequency counts */
        free = &nodelist[i];		/*     go to the free node list */
        }
    for (i = 0; i < 256; i++)
        if (nodelist[i].count) {	/* If a particular byte doesn't */
            heap[++n] = &nodelist[i];	/*     occur at all, it doesn't */
            if (n > 1) heapinsert(n);	/*     get placed into the tree */
    	} else {			/*     since it would just make */
    	    nodelist[i].zero = free;	/*     the header larger . . .  */
    	    free = &nodelist[i];
    	}
    while (n >= 2) {
        lson = heapmin(&n);		/* The standard algorithm which */
        rson = heapmin(&n);		/*     we use to build the tree */
	nnod = free;			/*     is quite elegant...given */
	free = free->zero;		/*     W1, W2, .. Wn one simply */
	nnod->flag   = FALSE;		/*     solves a smaller problem */
	nnod->zero   = lson;            /*     W1 + W2, W3, .. Wn until */
	nnod->one    = rson;		/*     one gets the trivial W1. */
        nnod->count  = lson->count + rson->count;
        nnod->index2 = ++gen;           /* Use a secondary key to place */
        heap[++n]    = nnod;		/*     W1 + W2 subtree so as to */
        if (n > 1) heapinsert(n);	/*     minimize unweighted sum. */
        }
    return heapmin(&n);
}

/*
Write a single bit to the output file.
################################   PutBit   ###############################

    Note that this routine reuses a buffer that was allocated for Unpack.

*/
char OutChar;
int  BitCount;

putbit(bit, file)
int bit, file;
{   long Count;

    OutChar <<= 1;
    if (bit) OutChar |= 1;
    if (++BitCount == 8) {
        pit_buffer[pit_index++] = OutChar;
        BitCount = 0; OutChar = (char) 0;
        if (pit_index == BSIZE) {
            Count = BSIZE;
            pit_index = 0;
            return FSWrite(file, &Count, pit_buffer);
        }
    }
    return noErr;
}


/*
Write a byte to the output file, using eight calls to putbit().
###############################   PutByte   ###############################
*/
putbyte(byt, file)
int byt, file;
{   int retval, i;

    for (i = 7; i >= 0; i--) {
        retval = putbit((byt & (1 << i)) ? 1 : 0, file);
        if (retval != noErr) return retval;
    }
    return noErr;
}

/*
Initialize various status variables before outputting a compressed file.
#############################   Init_Output   #############################
*/
void init_output()
{
    pit_index = 0;
    BitCount  = 0;
    OutChar   = (char) 0;
}

/*
Add needed bit padding and empty buffer after outputting a compressed file.
#############################   Flush_Output   ############################
*/
int flush_output(file)
int file;
{   int  errcode;
    long Count;

    while (BitCount) { if (errcode = putbit(0, file)) return errcode; }
    if  (pit_index)  {
        Count = pit_index;
        return FSWrite(file, &Count, pit_buffer);
    }
    return noErr;
}


/*
Write a copy of the Huffman tree we're using for compression to pit_file.
##############################   Write_Tree   #############################
*/
int write_tree(root, file)
nodeptr   root;
int 	  file;
{   int   errno;
--- end of part 2 ---