jjj1comp.c

[随书类]Dos6.0源代码

/*
**  JJJ1COMP.C  --  JJJ1 Compression module - first implementation
*/

/*  This code was written by modifying the Zeck compression code
**  and adding a triple huffman compressor.  The results are much
**  smaller.  This was done by Jeff Johnson, 10/15/90 to accomodate
**  Microsoft Excel 3.0.
*/

#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#include <io.h>
#include <fcntl.h>
#include <stdio.h>

#include "..\sutkcomp.h"

#ifdef OS2SU
#include <doscalls.h>
#endif

#include "jjj1.h"

#include "setjmp.h"

extern BOOL    fJmpEnvSet;
extern jmp_buf jmpEnv;



// Globals used by compression
BYTE  bPassCnt = 0;
long  lcbSrcStart;

BYTE    rgbLitBuf[cbLitMax];
USHORT  ibLitBuf=0;
BYTE    bBitHold = 0, cbBitHold=0;

void  WriteBits(unsigned int val, unsigned int cnt)
{
    if (cnt + cbBitHold <= 8)
        {
        bBitHold <<= (cnt);
        bBitHold  |= (val) & iPowers[cnt];
        if ((cbBitHold += (cnt)) == 8)
            {
            WriteByte(bBitHold);
            cbBitHold = 0;
            }
        }
    else
        {
        bBitHold <<= 8 - cbBitHold;
        bBitHold  |= (val >> (cnt -= (8 - cbBitHold))) & iPowers[8 - cbBitHold];
        WriteByte(bBitHold);
        if (cnt >= 8)
            WriteByte((BYTE) (val >> (cnt -= 8)));
        cbBitHold = (BYTE) cnt;
        bBitHold = (BYTE) val;
        }
}

#define WriteHuffman4a(val) WriteBits(fpct4a[val].usCode,fpct4a[val].cbCode)
#define WriteHuffman4b(val) WriteBits(fpct4b[val].usCode,fpct4b[val].cbCode)
#define WriteHuffman5(val)  WriteBits(fpct5 [val].usCode,fpct5 [val].cbCode)
#define WriteHuffman6(val)  WriteBits(fpct6 [val].usCode,fpct6 [val].cbCode)
#define WriteHuffman8(val)  WriteBits(fpct8 [val].usCode,fpct8 [val].cbCode)


void  InitAnalyze()
{
    int  cnt;

    for (cnt = 0; cnt < 256; cnt++)
        fpbAnalysis8[cnt] = 0;
    for (cnt = 0; cnt < 64; cnt++)
        fpbAnalysis6[cnt] = 0;
    for (cnt = 0; cnt < 32; cnt++)
        fpbAnalysis5[cnt] = 0;
    for (cnt = 0; cnt < 16; cnt++)
        fpbAnalysis4a[cnt] = fpbAnalysis4b[cnt] = 0;
}


int  TraverseHTree(int curpos, CODETABLE far *fpct, int depth)
{
    int  dep1, dep2;

    if (fphtArr[curpos].left == -1) //leaf node
        {
        fpct[curpos].cbCode = (BYTE) depth;
        return(depth);
        }
    dep1 = TraverseHTree(fphtArr[curpos].left , fpct, depth+1);
    dep2 = TraverseHTree(fphtArr[curpos].right, fpct, depth+1);
    if (dep1 > dep2)
        return(dep1);
    else
        return(dep2);
}


void  BuildHTree(long far *fpbInWgt, int cbInWgt, CODETABLE far *fpct)
{
    int   cnt, passcnt, ndxsmall, ndxsmallest, unused;
    long  small, smallest;

LStartBuildHTree:
    unused = 0;
    for (cnt = 0; cnt < cbInWgt; cnt++)
        fpct[cnt].cbCode = 0;

    for (cnt = 0; cnt < cbInWgt; cnt++)
        {
        fphtArr[cnt].left = fphtArr[cnt].right = fphtArr[cnt].parent = -1;
        if ((fphtArr[cnt].weight = fpbInWgt[cnt]) == 0) // Don't give it a code
            {
            fphtArr[cnt].parent = -2;
            unused++;
            }
        }

    if (unused >= cbInWgt - 1) // Can't build a proper tree
        {
        if (unused == cbInWgt) // No entries, just assign 1-bit to last 2 codes
            fpct[cbInWgt-1].cbCode = fpct[cbInWgt-2].cbCode = 1;
        else
            {
            cnt = -1;
            while (!fpbInWgt[++cnt]);
                if (cnt)
                    fpct[cnt].cbCode = fpct[cnt-1].cbCode = 1;
                else
                    fpct[cnt].cbCode = fpct[cnt+1].cbCode = 1;
            }
        return;
        }
       
    for (passcnt = 0; passcnt < cbInWgt - unused - 1; passcnt++)
        {
        small = smallest = 1L << 30;
        for (cnt = 0; cnt < cbInWgt + passcnt; cnt++)
            {
            if ((fphtArr[cnt].weight < small) && (fphtArr[cnt].parent == -1))
                {
                if (fphtArr[cnt].weight < smallest)
                    {
                    small = smallest;
                    ndxsmall = ndxsmallest;
                    smallest = fphtArr[cnt].weight;
                    ndxsmallest = cnt;
                    }
                else
                    {
                    small = fphtArr[cnt].weight;
                    ndxsmall = cnt;
                    }
                }
            }
        fphtArr[ndxsmall].parent = fphtArr[ndxsmallest].parent = cnt;
        fphtArr[cnt].weight = small+smallest;
        fphtArr[cnt].left   = ndxsmallest;
        fphtArr[cnt].right  = ndxsmall;
        fphtArr[cnt].parent = -1;
        }

    for (cnt = 0; cnt < cbInWgt; cnt++)
        fpct[cnt].cbCode = 0;

    if (TraverseHTree(2 * cbInWgt - unused - 2, fpct, 0) < 16)
        return;

    small = 1;
    smallest = 1L << 30;
    for (cnt = 0; cnt < cbInWgt; cnt++)
        {
        long  wgt = fpbInWgt[cnt];

        if (wgt > 0L)
            {
            if (wgt < smallest)
                {
                small = smallest;
                smallest = wgt;
                }
            else if (wgt > smallest && wgt < small)
                small = wgt;
            }
        }

    if (smallest >= small || smallest == 0L)
        return;    /* ERROR */

    for (cnt = 0; cnt < cbInWgt; cnt++)
        {
        if (fpbInWgt[cnt] == smallest)
            fpbInWgt[cnt] = small;
        }
    goto LStartBuildHTree;
}


// Returns TRUE if the given codetable is better than no code at all
BOOL  CodeTradeoff(long far * fpAnal, CODETABLE far * fpct, int cbAnal, int cbHdr,
        int *bBit)
{
    int   cnt = cbAnal, codesize = 0;
    long  size = 0, repcnt = 0;

    while (cnt >>= 1)
        codesize++;

    for (cnt = 0; cnt < cbAnal; cnt++)
        {
        size   += fpAnal[cnt] * fpct[cnt].cbCode;
        repcnt += fpAnal[cnt];
        }
    size >>= 3; // Convert to bytes
    repcnt = repcnt * codesize / 8;

   size += cbHdr;  // Account for the cost of the header

// Calculate interesting info
#ifdef STATS
{

   long totfreq = 0;
   double result = 0.0, work, log(double);
   for(cnt=0;cnt<cbAnal;cnt++)
      totfreq += fpAnal[cnt];
   for(cnt=0;cnt<cbAnal;cnt++)
   {
      if(fpAnal[cnt]) //Don't do if 0 freq
      {
         work = (double) fpAnal[cnt] / (double) totfreq;
         work = log(work) / log(2.0);
         work*= (double) (-fpAnal[cnt]);
         result += work;
      }
   }
   printf("Entries: %3d, Uncomp: %6ld, Comp: %6ld, Optimal: %6.0f, Savings: %6.0f\n",
          cbAnal, repcnt, size, result/8,(double) size - (result/8));
}
#endif

    if (size >= repcnt) // Not worth it
        {
        *bBit = NOTABLE;  // Have to rebuild generic huffman tables
        for (cnt = 0; cnt < cbAnal; cnt++)
            fpct[cnt].cbCode = (BYTE) codesize;
        BuildCodeTable(fpct, cbAnal);
        }
    return ((BOOL)(size < repcnt));
}


int  TableComp(CODETABLE far *fpct, int cbct, int *bBit)
{
//  int  totsize[2] = { 4,4 };			// jem
    int  totsize[2];
    int  lastval    = fpct[0].cbCode;
    int  cnt, diff;

    totsize[0] = totsize[1] = 4;

    for (cnt = 1; cnt < cbct; cnt++)
        {
        diff = fpct[cnt].cbCode - lastval;

        if (!diff)
            totsize[0]++;
        else if (diff == 1)
            totsize[0]+=2;
        else
            totsize[0]+=6;


        if (diff > -2 && diff < 2)
            totsize[1] += 2;
        else
            totsize[1] += 6;

        lastval = fpct[cnt].cbCode;
        }

    totsize[0] >>= 3; //Convert to bytes
    totsize[1] >>= 3; //Convert to bytes

    if ((totsize[0] < totsize[1]) && (totsize[0] < (cbct>>1)))
        {
        *bBit = COMPRESS1BIT;
        cnt   = totsize[0];
        }
    else if (totsize[1] < (cbct >> 1))
        {
        *bBit = COMPRESS2BIT;
        cnt   = totsize[1];
        }
    else
        {
        *bBit = COMPRESSNONE;
        cnt   = cbct >> 1;
        }
    return(cnt);
}


void  WriteTable(CODETABLE far *fpct, int cbct, int Method)
{
    int  cnt, lastval = fpct[0].cbCode, diff, curval;

    if (Method == NOTABLE)
        return;

    WriteBits(lastval, 4);

    for (cnt = 1; cnt < cbct; cnt++)
        {
        curval = fpct[cnt].cbCode;
        diff   = curval - lastval;

        switch (Method)
            {
        case COMPRESSNONE:
            WriteBits(curval, 4);
            break;
        case COMPRESS1BIT:
            if (diff == 0)
                WriteBits(0, 1);
            else if (diff == 1)
                WriteBits(2, 2);
            else
                WriteBits(0x30|curval, 6);
            break;
        case COMPRESS2BIT:
            if ((diff > -2) && (diff < 2))
                WriteBits(diff+1, 2);
            else
                WriteBits(0x30|curval, 6);
            break;
            }
        lastval = curval;
        }
}


/*
**  LONG Lcb_JJJ1_CompressToFile(int fhSrc, int fhDest, LONG lcbDestMax)
**
**  Assumes that the header has already been written.
*/
LONG Lcb_JJJ1_CompressToFile(int fhSrc, int fhDest, LONG lcbDestMax)
{
    USHORT   us,cnt;
    SHORT    ch, cbLen, ibCharCur, ibStringCur, cbMatchLast,iMatchRel;