NetNews Usenet Archive 1992 #30

home *** CD-ROM | disk | FTP | other *** search

/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / sys / amiga / programm / 17412 < prev next >

Wrap

Text File | 1992-12-15 | 16.4 KB | 430 lines

Newsgroups: comp.sys.amiga.programmer Path: sparky!uunet!think.com!spool.mu.edu!umn.edu!doug.cae.wisc.edu!pochanay From: pochanay@cae.wisc.edu (Adisak Pochanayon) Subject: RUN BYTE! RUN! Organization: College of Engineering, Univ. of Wisconsin--Madison Date: 15 Dec 92 21:33:59 CST Message-ID: <1992Dec15.213400.28437@doug.cae.wisc.edu> Sender: pochanay@cae.wisc.edu Lines: 419 A Modified Byte Run Compression Algorithm. Part 2: ------------------------------------------------------------------------- OK, Class.... We left off in part one with an idea for an extremely fast graphics compression algorithm that was roughly based on the IFF byte run method. This article will again cover the decompression algorithm as I have made some improvements in the assembly code. The main compression routines and algorithm are unchanged however and the format for the compressed files has not changed. In the second part of this article, I describe a Compressor (and DeCompressor) program in C. It is not written for optimal speed merely because I wanted the code to be readable and the time that speed is really needed is decompression (which occurs in the 36-byte assembly routine). Using this code along with the unpacker.asm will allow you to include any raw compressed graphics easily in your own programs. NOTE: This is not a repost per se. I got several suggestions on how to improve the decompression speed by up to 10 cycles per byte-tag. Many thanks to all who replied. Espescially: Bjoern Reese | Email: breese@imada.ou.dk for his insight. There is also much more information on the compression process as well as a compressor program. ------------------------------------------------------------------------- Adisak Pochanayon 2525 University Avenue Apt #J Madison WI 53706 608-238-2463 Fancy title screens and graphics can spice up an otherwise mudane program but they can also present a problem to the programmer. Including the actual bitplane data in a program can take a lot of memory and disk space. IFF graphics files do employ compression but loading an iff graphic requires the programmer to add additional source code that may bulk up the program and forces the program to access external support files. A simple way of avoiding these problems is to include compress data directly within a program. When compressing bitplane data on the Amiga, byte run compression or the compression of repeated bytes provides a simple yet rather efficient method of compression. As a matter of fact, the IFF ILBM file format employs byte run compression. The IFF compression scheme uses the format of "byte-tag data", where byte-tag is a single byte and data is anywhere from zero to 128 bytes. If the byte-tag is 128, then the length of he data is zero and nothing happens (this is a NOP). If the byte-tag is less than 128, then the data is (byte-tag + 1) bytes in length and is a literal representation of bitplane data. If the byte-tag is greater than 128, then the data is one byte that is to be repeated (257 - byte-tag) times. There are two main problems with using the IFF byte run compression. First, the compression format can be slightly complicated and second, IFF compresses each line in each bitplane individually. This leads to slower decompression and lower compression ratios. In order to modify the byte-run to achieve the fastest decompression as well as the best compression ratio, some changes must be made. This begins with the simple change of compressing entire bitplanes or bitmaps as a single entity rather than using line by line compression on each bitplane. The next improvement comes from a simplification of the "byte-tag data" format. A byte-tag of zero will represent STOP. A byte-tag of less than 128 will mean repeating the next byte (byte-tag + 1) times. A byte-tag of 128 or greater (note that when using signed numbers, a byte greater than or equal to 128 is negative) will mean copying the next (byte-tag - 127) bytes literally. This will allow an extremely fast decompression method which only takes 36 bytes of code in assembly. To better understand how this modified byte-run compression works, let's look at the assembly for the decompression: ---------------------------BEGIN ASM---------------------------------------- CODE, PUBLIC ***** VOID __regargs UnPackByteRun(UBYTE *from, UBYTE *to) ***** calling from assembly: a0 , a1 ***** This code takes a Byte Run packed buffer and unpacks it to ***** another buffer. Note: for maximum speed, no checking of any ***** sort is performed for boundaries. Also, there is no CRC or ***** error correction/detection. It is assumed that your data is ***** valid. ***** If you're using C with UnPackByteRun1 and your compiler doesn't ***** support, Lattice/SAS 's __regargs register passing convention, ***** you will need to use the following commented-out code. ***** XDEF _UnPackByteRun ***** _UnPackByteRun: ***** movea.l 4(SP),a0 ***** movea.l 8(SP),a1 XDEF @UnPackByteRun @UnPackByteRun: move.l d2,-(SP) ; Move #7F to d2 so that the and.w move.b #$7F,d2 ; instruction at the upb_copyit label ; will execute more quickly bra.s upb_startit ; Process First byte-tag ********************************* upb_copyit and.w d2,d0 ; Clear bit seven in d0 upb_copy_loop ; Note: 68010+ optimized dbf loop to move.b (a0)+,(a1)+ ; Copy a literal string d0 +1 in length dbf d0,upb_copy_loop ; Process next byte-tag when loop ends ********************************* upb_startit moveq.l #0,d0 ; Require to clear MSB of d0 for dbf loops ; Which is $FF after dbf loops move.b (a0)+,d0 ; Load byte-tag into d0 and test byte-tag bmi.s upb_copyit ; Negative -> COPY bytes literally beq.s upb_out ; Zero -> quit ; Else Repeat a byte (Positive) ********************************* move.b (a0)+,d1 ; Repeat this byte d0 +1 times upb_repeatit ; Note 68010+ optimized dbf loop move.b d1,(a1)+ dbf d0,upb_repeatit bra.s upb_startit ; Process next byte-tag ********************************* upb_out move.l (SP)+,d2 ; Restore value of d2 before exiting rts END ---------------------------END ASM------------------------------------------ The code is passed a pointer to the compressed data buffer in memory in a0 and a pointer to the buffer for data decompression in a1. Care was taken to ensure that speed of decompression was of the first importance. Decoding each byte tag takes a maximum of four instructions in assembly. If the byte-tag just read is equal to zero, the routine has finished. After a byte-tag is decoded, control can be passed to the repeat byte routine or copy bytes routine. If the control is passed to the repeat byte routine, the byte to be repeated is loaded into d1 and then written to the output buffer using a 68010+ optimized "dbf loop" of two instructions. When the repeated byte string is finished, the next byte-tag is processed. If the control is passed to the copy bytes routine, the high bit in the byte-tag is cleared. Then data is copied literally from the compressed buffer to the output buffer in another 68010+ optimized "dbf loop". When this data has been copied, the next byte-tag is processed. This simple yet extremely fast assembly routine is the heart of the modified byte run compression scheme. It is very easy to link to any program and takes very little memory. In order to use the decompression routine, however, a compression routine is required. This compressor's source follows immediately as "BR.c". In can pack or unpack any file using the modified byte run compression scheme noted above. The syntax for using "BR" is: "BR FLAG SOURCE DESTINATION" where FLAG can be U - unpack or P - pack. ---------------------------BEGIN C------------------------------------------ ;/* BR.c - BYte Run (un)packer -- Source for Lattice/SAS C version 5.10 LC -b1 -ccist -v -O -L BR.c quit */ /***************************************************************************** BR - Byte Run (un)packer. C. 1991-1992 SilverFox SoftWare. Written by Adisak Pochanayon All Rights Reserved. This program is a simple example of using BYTE-RUN compression upon a file. It will allow you to both pack and unpack a file using BYTE-RUN compression. The syntax for calling this program from the CLI is: BR FLAG SOURCE DESTINATION FLAG can be U - unpack P - pack *****************************************************************************/ #include <stdio.h> /* defines for interpreting the CLI arguments */ #define arg_flag 1 #define arg_srce 2 #define arg_dest 3 #define arg_count 4 /* defines for handling argument and file errors */ #define br_error 1024 #define error_read 0 #define error_args 1 #define error_srce 2 #define error_dest 4 #define error_write 8 /* defines for file compression / decompression */ #define FILE_ERROR 0 #define MAX_RUN 128 #define LITERAL 128 #define TRUE 1 #define FALSE 0 /*** GLOBAL VARIABLE FOR ERRORS ***/ int error=0; char __regargs readchar(register FILE *infile) { register int inchar; if ((inchar=getc(infile))!=EOF) return((char)inchar); /* OTHERWISE AN ERROR OCCURRED READING THE INPUT FILE */ if (error==0) { error = br_error + error_read; printf("Unexpected end of file on input file.\nOutput file may be corrupt.\n"); } return(FILE_ERROR); } void __regargs writechar(register char outchar, register FILE *outfile) { if (putc(outchar,outfile)==EOF) { printf("Error writing output file.\n"); fcloseall(); exit(br_error + error_write); } } void __regargs UnPackByteRun(register FILE *infile, register FILE *outfile) { register char number, fillbyte; while ((number=readchar(infile)) != 0) { if ((number & LITERAL)==0) /* Expand compressed string from input to output */ { fillbyte=readchar(infile); for (number++; number!=0; number--) writechar(fillbyte,outfile); } else /* Copy string from input to output */ { number&=0x7f; for (number++; number!=0; number--) writechar(readchar(infile),outfile); } } } void __regargs primebuffer(register short *in,register FILE *infile) { in[0]=in[1]; in[1]=in[2]; in[2]=getc(infile); } void __regargs PackByteRun(register FILE *infile, register FILE *outfile) { char outbuffer[MAX_RUN]; short inbuff[3]={0,0,0}; short repeatme; register short *incheck=inbuff; register short tag, loop; primebuffer(incheck,infile); /* Prime the input "pump" */ primebuffer(incheck,infile); primebuffer(incheck,infile); while (incheck[0] != EOF) /* As long as input file is not exhausted */ { if (incheck[0] == incheck[1]) { /*** Compress repeated string of bytes ***/ tag=2; outbuffer[0] = incheck[0]; repeatme=incheck[0]; primebuffer(incheck,infile); primebuffer(incheck,infile); while ((incheck[0] == repeatme)&&(tag != MAX_RUN)) { primebuffer(incheck,infile); tag++; } writechar(tag-1,outfile); writechar(outbuffer[0],outfile); } else { /*** Copy string from input to output ***/ outbuffer[0] = incheck[0]; tag=1; primebuffer(incheck,infile); loop=TRUE; while (loop) { if ((tag == MAX_RUN) || (incheck[0] == EOF) || ((incheck[0] == incheck[1]) && (incheck[1] == incheck[2]))) loop=FALSE; else { outbuffer[tag] = incheck[0]; tag+=1; primebuffer(incheck,infile); } } writechar(tag+(LITERAL-1),outfile); for (loop=0; loop!=tag; loop++) writechar(outbuffer[loop],outfile); } } writechar(0,outfile); /* Terminate output file with zero pad */ } main(int argc, char *argv[]) { FILE *infile=NULL, *outfile=NULL; printf(" BR -- BYte Run (un)packer. C. 1991-1992 SilverFox SoftWare.\n"); printf(" Written by Adisak Pochanayon All Rights Reserved.\n\n"); if (argc != arg_count) { error= br_error + error_args; printf("Error -- Please check arguments.\n"); } else if ((infile = fopen(argv[arg_srce],"r"))==FILE_ERROR) { error= br_error + error_srce; printf("Error -- SOURCE file could not be opened.\n"); } else if ((outfile = fopen(argv[arg_dest],"w"))==FILE_ERROR) { error= br_error + error_dest; printf("Error -- DESTINATION file could not be opened.\n"); } switch (*argv[arg_flag]) { case 'U' : case 'u' : printf("UnPacking File %s.\n",argv[arg_srce]); UnPackByteRun(infile, outfile); break; case 'P' : case 'p' : printf("Packing File %s.\n",argv[arg_srce]); PackByteRun(infile, outfile); break; default : error=8; printf("Error -- no FLAG selected.\n"); } if (error!=0) printf("\nBR command syntax is: \"BR FLAG SOURCE DESTINATION\"\n where FLAG can be U - unpack P - pack.\n\n"); else printf("\nBR successfully completed\n"); fcloseall(); exit(error); } -----------------------------END C------------------------------------------ The basic idea of the Byte Run compression is to compress strings of a single repeating byte wherever they occur. However, this algorithm improves slightly upon the algorithm by using a three-byte lookahead. If the compressor is currently copying a literal string, it will not break for a two-byte repeat string. It waits until it finds a three-byte string. This results in often saving a byte-tag as interrupting the literal string requires two byte-tags and the copy-byte (or a total of three bytes to compress two). For those who have difficulty following the asm unpacker, there is a short C unpacking section within the compressor program so that the compressor can translate files in both directions. The compression program BR.c does a fairly good job at compressing graphics files. Especially for its simplicity. In order to optimize compression at a minimal cost in CPU time, it uses a three character lookahead. There are several optimizations that could make the compressor faster or more efficient that I may implement when I have more time. The first optimization involves bufferring. Currently I use no file buffering other than the simple bufferring provided by Lattice C and Amiga DOS (i.e. inherent buffering). Using 16K or 32K read and write buffers would greatly improve the speed of compression if you are using floppies. If you perform the file compression in RAM or on a HD, you probably won't notice much difference. The second optimization comes from a lookahead/lookaside compression algorithm. Implementing this algorithm allows short byte breaks of 2 repeated bytes in a literal string to be compressed if it allows the following literal string to be represented in fewer bytes (by saving a byte tag). This optimization has a very high CPU cost as it requires a minimumal 128 character lookahead. This is an optimization that would be impossible without buffering. I have decided not to implement this optimization as it would slow processing of files by a factor of 20 for an increase in compression of less than .5%!!! However, for the picky out there who want to save a byte or two, I invite you to implement the optimization. This optimization can also be extended to byte-tag start strings to determine whether a literal may be more valuable than a repeat string. ----------------------------------------------------------------------- As usual, I invite any questions or comments. Please feel free to e-mail me at pochanay@cae.wisc.edu for more indepth discussions. I am still looking for Amiga Artists to help with new games and programs I am planning on writing.