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

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.

Xref: sparky comp.sys.amiga.programmer:17364 comp.sys.amiga.hardware:21505