_BLOCK TRUNCATION COMPRESSION_
by Anton Kruger

[LISTING ONE]

/* File: btc4x4.c -- Author: Anton Kruger -- Revision: 1.0
 * Copyright (c) Truda Software
 * 215 Marengo Rd, #2, Oxford, IA 52322-9383
 * Description: Contains routines for performing 4x4 block truncation 
 * compression on 8-bit, 256x256 monochrome images.
 * Compilers:   MSC 5.1. 
 */
                      /* *** Headers *** */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

               /* *** Typedefs and defines *** */          
typedef unsigned char byte;   
typedef unsigned int  word;
#define IOBUFFSIZE 2048       /* size of i/o buffers */

               /* *** Function prototypes *** */
void main(int argc, char *argv[]);
void btc4x4(FILE *fp1, FILE * fp2);
void GetStats(byte * block,byte *a,byte *b,byte *mean);
int  GetBlock(byte *block, FILE *fp);
void PutCode(byte a, byte b, word code, FILE *fp);
void inform(char *mess);

void main(int argc, char *argv[])
{
   /* A short driver routine for "btc4x4.c", that performs block truncation 
   ** compression on an image file. */
   FILE        *fp1,*fp2;
   if (argc < 3){
      inform("Usage: BTC4x4 infile outfile\n\n");
      inform("infile is a 256x256 binary image file\n");
      inform("outfile is a BTC-compressed file\n");
      exit(-1);
   }
   if ((fp1 = fopen(argv[1],"rb")) == NULL) {
      inform("ERROR: Could not open input file: ");
      inform(argv[1]);
      exit(-1);
   }
   setvbuf(fp1,(char *)NULL,_IOFBF,IOBUFFSIZE);
   if ((fp2 = fopen(argv[2],"wb")) == NULL) {
      inform("ERROR: Could not open output file: ");
      inform(argv[2]);
      exit(-1);
   }
   setvbuf(fp2,(char *)NULL,_IOFBF,IOBUFFSIZE);
   inform("Block Truncation Compression.\n");
   inform(argv[1]); inform(" -> "); inform(argv[2]);
   inform("\nPlease wait...\n");

   btc4x4(fp1, fp2);

   fclose(fp1);
   fclose(fp2);
   inform("Done!\n");
   exit(0);
}
void btc4x4(FILE *fp1, FILE * fp2)
{
   /* Block truncation compress the file connected to "fp1". The output goes 
   ** to the file connected to "fp2". */
   int         i;
   byte        a,b,mean;
   byte        block[16];
   word        code;
   while (GetBlock(block,fp1) != EOF){
      GetStats(block,&a,&b,&mean);
      code = 0;                       /*  clear bits */   
      for (i=0;i<=15;i++)
         if (block[i] >= mean)
            code = code | (1<<i);     /* set bit "i" */
      PutCode(a,b,code,fp2);
   }
}
void GetStats(byte * block,byte *a,byte *b,byte *mean)
{
   /* This routine computes the statistics "a", "b", and "mean" for the pixels 
   ** in "block". */
   int         i,q;
   float       m1,m2,sigma;
   float       atmp,btmp;
   double      d;

   /* Compute mean, mean-square, and "sigma". */
   m1 = m2 = (float)0.0;
   for (i=0;i<=15;i++){
      m1 = m1 + (float)block[i];
      m2 = m2 + (float)(block[i]*block[i]);
   }
   m1 = m1/16.0;
   m2 = m2/16.0;
   sigma = (float)sqrt((double)(m2- m1*m1));
   
   /* Count "q", the number of pixels >= "mean" , then compute "a", and "b". */
   for (q=0,i=0;i<=15;i++)
      if ((float)block[i] >= m1) q++;
   if (q == 16){
      *mean = (byte)(m1+0.5);
      *a = *b = *mean;    /* all pixels are the same */
   }
   else{
      d  = sqrt((double)q/(16.0-q));
      atmp = m1 - sigma*d;
      btmp = m1 + sigma/d;
      if (atmp < (float)0) atmp = (float)0;
      if (btmp > (float)255) btmp = (float)255;

      /* Round values to nearest integer */
      *a = (byte)(0.5+atmp);  
      *b = (byte)(0.5+btmp);
      *mean = (byte)(m1+0.5);
   }
}
int GetBlock(byte *block, FILE *fp)
{
   /* This routine gets a block of 4x4 pixels from the file connected to "fp". 
   ** Normally it returns 1. If at EOF, or errors occur, it returns  EOF. */
   static int  bp = 256;
   static byte buffer[4][256];
   int         i,j;

   /* If the 4-line buffer is empty, fill it. If it cannot be filled for some 
   ** reason, return EOF. Otherwise, reset the buffer pointer "bp". */
   if (bp == 256){
      for (j=0;j<=3;j++)
         if (fread(buffer[j],1,256,fp) != 256)
            return(EOF);
      bp = 0;
   }

   /* Get 16 pixels from the 4-line buffer. Then update the buffer 
   ** pointer "bp", and return to caller. */
   for (j=0;j<=3;j++)
      for (i=0;i<=3;i++)
         block[i+4*j] = buffer[j][bp+i];
   bp = bp+4;
   return(1);
}
void PutCode(byte a, byte b, word code, FILE *fp)
{
   /* This routine writes "a", "b", and the block truncation "code" to 
   ** the file connected to "fp". */
   fputc((byte)a,fp);
   fputc((byte)b,fp);
   fputc((byte)(code & 255),fp);       /* LSB first  */
   fputc((byte)((code>>8) & 255),fp);  /* MSB second */
}
void inform(char *mess)
{
   fprintf(stderr,"%s",mess);
}


[LISTING TWO]

/* File:  btd4x4.c -- Author: Anton Kruger -- Revision: 1.0
 * Copyright (c) Truda Software
 * 215 Marengo Rd, #2, Oxford, IA 52322-9383
 * Description: Contains routines for performing 4x4 block truncation 
 *  decompression; assumes input files were compressed with "btc4x4".
 * Compilers:   MSC 5.1. 
 */
                      /* *** Headers *** */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

               /* *** Typedefs and defines *** */          
typedef unsigned char byte;   
typedef unsigned int  word;
#define IOBUFFSIZE 2048       /* size of i/o buffers */

               /* *** Function prototypes *** */
void main(int argc, char *argv[]);
void btd4x4(FILE *fp1, FILE * fp2);
int  GetCode(byte *a, byte *b, word * code, FILE *fp);
int  PutBlock(byte *block, FILE *fp);
void inform(char *mess);

void main(int argc, char *argv[])
{
   /* A diver routine for "btd4x4.c", that decompresses a block truncation 
   ** compressed file. */
   FILE        *fp1,*fp2;

   if (argc < 3){
      inform("Usage: BTD4x4 infile outfile\n\n");
      inform("infile is a BTC-compressed file\n");
      inform("outfile is a 256x256 binary image file\n");
      exit(-1);
   }
   if ((fp1 = fopen(argv[1],"rb")) == NULL) {
      inform("ERROR: Could not open input file: ");
      inform(argv[1]);
      exit(-1);
   }
   setvbuf(fp1,(char *)NULL,_IOFBF,IOBUFFSIZE);
   if ((fp2 = fopen(argv[2],"wb")) == NULL) {
      inform("ERROR: Could not open output file: ");
      inform(argv[2]);
      exit(-1);
   }
   setvbuf(fp2,(char *)NULL,_IOFBF,IOBUFFSIZE);

   inform("Block Truncation Decompression.\n");
   inform(argv[1]); inform(" -> "); inform(argv[2]);
   inform("\nPlease wait...\n");

   btd4x4(fp1, fp2);

   fclose(fp1);
   fclose(fp2);
   inform("Done!\n");
   exit(0);
}
void btd4x4(FILE *fp1, FILE * fp2)
{
   /* Decompress the block truncation compressed file connected to "fp1". 
   ** The output goes to the file connected to "fp2". */
   int         i;
   byte        a,b;
   byte        block[16];
   word        code;

   while (GetCode(&a,&b,&code,fp1) != EOF){
      for (i=0;i<=15;i++)
         if (code & (1 << i))    /* is bit "i" set ? */
            block[i] = b;
         else
            block[i] = a;
      PutBlock(block,fp2);
   }
   /* The 4-line buffer maintained by "PutBlock" should be full at this point.  
   ** Output one last dummy block. This will not be written to the output
   ** file, and only serves to flush that buffer. */
   PutBlock(block,fp2);
}

int PutBlock(byte *block, FILE *fp)
{
   /* This routine writes a block of 4x4 pixels to the file connected to "fp". 
   ** Normally it returns 1. If at EOF, or errors occur, it returns EOF. */
   static int  bp = 0;
   static byte buffer[4][256];
   int         i,j;

   /* If the 4-line buffer is full, flush it. If it cannot be flushed for some 
   ** reason, return EOF. Otherwise, reset the buffer pointer "bp". */
   if (bp == 256){
      for (j=0;j<=3;j++)
         if (fwrite(buffer[j],1,256,fp) != 256)
            return(EOF);
      bp = 0;
   }

   /* Place 16 pixels in the 4-line buffer. Then update the buffer pointer 
   ** "bp", and return to caller. */
   for (j=0;j<=3;j++)
      for (i=0;i<=3;i++)
         buffer[j][bp+i] = block[i+4*j];
   bp = bp+4;
   return(1);
}

int  GetCode(byte *a, byte *b, word * code, FILE *fp)
{
   /* This routine gets "a", "b", and the block truncation "code" from the 
   ** file connected to "fp". Normally it returns 1. If at end of file, or
   ** errors occur, it returns EOF. */
   *a = (byte)fgetc(fp);
   *b = (byte)fgetc(fp);
   *code = fgetc(fp);                  /* LSB first  */
   *code = (fgetc(fp) << 8) + *code;   /* MSB second */
   if (feof(fp) || ferror(fp))
      return(EOF);
   else
      return(1);         
}
void inform(char *mess)
{
   fprintf(stderr,"%s",mess);
}