encode.c

来自「开放源码的编译器open watcom 1.6.0版的源代码」· C语言 代码 · 共 949 行 · 第 1/2 页

/****************************************************************************
*
*                            Open Watcom Project
*
*    Portions Copyright (c) 1983-2002 Sybase, Inc. All Rights Reserved.
*
*  ========================================================================
*
*    This file contains Original Code and/or Modifications of Original
*    Code as defined in and that are subject to the Sybase Open Watcom
*    Public License version 1.0 (the 'License'). You may not use this file
*    except in compliance with the License. BY USING THIS FILE YOU AGREE TO
*    ALL TERMS AND CONDITIONS OF THE LICENSE. A copy of the License is
*    provided with the Original Code and Modifications, and is also
*    available at www.sybase.com/developer/opensource.
*
*    The Original Code and all software distributed under the License are
*    distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
*    EXPRESS OR IMPLIED, AND SYBASE AND ALL CONTRIBUTORS HEREBY DISCLAIM
*    ALL SUCH WARRANTIES, INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF
*    MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR
*    NON-INFRINGEMENT. Please see the License for the specific language
*    governing rights and limitations under the License.
*
*  ========================================================================
*
* Description:  wpack routines used to encode files.
*
****************************************************************************/


#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <malloc.h>
#include "wpack.h"
#ifdef UNIX
#include <clibext.h>
#endif

// external function declarations

extern void             EncWriteByte( char );
extern byte             EncReadByte( void );
extern void             DecWriteByte( unsigned char );
extern void             WriteMsg( char * );
extern void             WriteFiller( unsigned );
extern void             FlushRead( void );
extern void             FlushWrite( void );
extern int              QOpenR( char * );
extern unsigned long    QFileLen( int );
extern unsigned long    QGetDate( int );
extern unsigned_32      GetCRC( void );
extern void             LinkList( void **, void * );
extern void             QClose( int );
extern void             QSeek( int, signed long, int );
extern int              QWrite( int, void *, int );
extern void             WriteNumeric( char *, unsigned long );
extern file_info **     ReadHeader( arccmd *, arc_header * );
extern void             Error( int, char * );
extern void             PackExit( void );
extern int              QOpenM( char * );
extern void             CopyInfo( int, int, unsigned long );
extern int              WriteSeek( unsigned long );
extern int              QOpenW( char * );
extern void             SwitchBuffer( int, bool, void * );
extern void             RestoreBuffer( bool );
extern int              QRead( int, void *, int );
extern int              QWrite( int, void *, int );

extern uchar            text_buf[];
extern int              IOStatus;
extern int              infile, outfile;
extern int              indicies[];
extern byte             len[];

typedef struct runlist {
    struct runlist *        next;
    char                    data[1];
} runlist;

#define MAX_COPYLIST_SIZE (16*1024)

// the code array is also used to keep track of the frequency in the first
// pass through encoding the information

unsigned                code[ NUM_CHARS ];     // the code value for each char
static int              match_position, match_length;
static int              lson[N + 1], rson[N + 257], dad[N + 1];
static runlist *        RunList;
static runlist *        CurrRun;
static int              LastRunLen;
static int              NumSpilled;
static int              RunHandle;
static int              TmpHandle;
static void *           AltBuffer;

unsigned long    codesize;

#if defined( __WATCOMC__ ) && defined( __386__ )
unsigned fastcmp( char *src, char *dst, int *cmp );

#pragma aux fastcmp parm [esi] [edi] [edx] modify exact [eax ebx] value [ecx] = \
        "       xor ecx,ecx" \
        "L1:    mov eax,[esi+ecx]" \
        "       mov ebx,[edi+ecx]" \
        "       lea ecx,4[ecx]" \
        "       xor eax,ebx" \
        "       jne dscan" \
        "       cmp ecx,60" \
        "       jb  L1" \
        "       jmp finished" \
        "dscan: lea ecx,-4[ecx]" \
        "       test ax,ax" \
        "       jne in_low_word" \
        "       lea ecx,2[ecx]" \
        "       shr eax,16" \
        "in_low_word:" \
        "       test al,al" \
        "       jne almost" \
        "       inc ecx" \
        "almost:"\
        "       xor eax,eax"\
        "       xor ebx,ebx"\
        "       mov al, [esi+ecx]" \
        "       mov bl, [edi+ecx]" \
        "       sub eax,ebx"\
        "       mov [edx],eax"\
        "finished:";
#endif

static void InitTree( void )  /* Initializing tree */
/**************************/
{
    int  i;

    for (i = N + 1; i <= N + 256; i++) {
        rson[i] = NIL;            /* root */
    }
    for (i = 0; i < N; i++) {
        dad[i] = NIL;            /* node */
    }
}

static void InsertNode(int r)  /* Inserting node to the tree */
/***************************/
{
    int  i, p, cmp;
    unsigned char  *key;
    unsigned c;

    cmp = 1;
    key = &text_buf[r];
    p = N + 1 + key[0];
    rson[r] = lson[r] = NIL;
    match_length = 0;
    for ( ; ; ) {
        if (cmp >= 0) {
            if (rson[p] != NIL)
                p = rson[p];
            else {
                rson[p] = r;
                dad[r] = p;
                return;
            }
        } else {
            if (lson[p] != NIL)
                p = lson[p];
            else {
                lson[p] = r;
                dad[r] = p;
                return;
            }
        }
        cmp = 0;
#if defined( __WATCOMC__ ) && defined( __386__ )
        i = fastcmp( key + 1, &text_buf[p + 1], &cmp ) + 1;
#else
        for (i = 1; i < F; i++) {
            if( key[i] != text_buf[p + i] ) {
                cmp = key[i] - text_buf[p + i];
                break;
            }
        }
#endif
        if (i > THRESHOLD) {
            if (i > match_length) {
                match_position = ((r - p) & (N - 1)) - 1;
                if ((match_length = i) >= F) {
                    break;
                }
            }
            if (i == match_length) {
                if ((c = ((r - p) & (N - 1)) - 1) < match_position) {
                    match_position = c;
                }
            }
        }
    }
    dad[r] = dad[p];
    lson[r] = lson[p];
    rson[r] = rson[p];
    dad[lson[p]] = r;
    dad[rson[p]] = r;
    if (rson[dad[p]] == p)
        rson[dad[p]] = r;
    else
        lson[dad[p]] = r;
    dad[p] = NIL;  /* remove p */
}

static void DeleteNode(int p)  /* Deleting node from the tree */
/***************************/
{
    int  q;

    if (dad[p] == NIL)
        return;            /* unregistered */
    if (rson[p] == NIL)
        q = lson[p];
    else
    if (lson[p] == NIL)
        q = rson[p];
    else {
        q = lson[p];
        if (rson[q] != NIL) {
            do {
                q = rson[q];
            } while (rson[q] != NIL);
            rson[dad[q]] = lson[q];
            dad[lson[q]] = dad[q];
            lson[q] = lson[p];
            dad[lson[p]] = q;
        }
        rson[q] = rson[p];
        dad[rson[p]] = q;
    }
    dad[q] = dad[p];
    if (rson[dad[p]] == p)
        rson[dad[p]] = q;
    else
        lson[dad[p]] = q;
    dad[p] = NIL;
}

/*
 * Tables for encoding/decoding upper 6 bits of
 * sliding dictionary pointer
 */
/* encoder table */
static uchar p_len[64] = {
    0x03, 0x04, 0x04, 0x04, 0x05, 0x05, 0x05, 0x05,
    0x05, 0x05, 0x05, 0x05, 0x06, 0x06, 0x06, 0x06,
    0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
    0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
    0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
    0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
    0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
    0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08
};

static uchar p_code[64] = {
    0x00, 0x20, 0x30, 0x40, 0x50, 0x58, 0x60, 0x68,
    0x70, 0x78, 0x80, 0x88, 0x90, 0x94, 0x98, 0x9C,
    0xA0, 0xA4, 0xA8, 0xAC, 0xB0, 0xB4, 0xB8, 0xBC,
    0xC0, 0xC2, 0xC4, 0xC6, 0xC8, 0xCA, 0xCC, 0xCE,
    0xD0, 0xD2, 0xD4, 0xD6, 0xD8, 0xDA, 0xDC, 0xDE,
    0xE0, 0xE2, 0xE4, 0xE6, 0xE8, 0xEA, 0xEC, 0xEE,
    0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7,
    0xF8, 0xF9, 0xFA, 0xFB, 0xFC, 0xFD, 0xFE, 0xFF
};

static int CompLen( const void *_left, const void *_right )
/******************************************/
{
    const int *left  = _left;
    const int *right = _right;

    return( (int)len[ *left ] - (int)len[ *right ] );
}

static void SortLengths( int num )
/********************************/
{
    qsort( indicies, num, sizeof( int ), CompLen );
}

static bool AssignCodes( int num, arccmd *cmd )
/*********************************************/
// this generates the shannon-fano code values in reverse order in the high
// bits of the code array. returns TRUE if codes successfully assigned.
{
    unsigned    codeinc;
    unsigned    lastlen;
    unsigned    codeval;
    int         index;

    SortLengths( num );
    if( len[ indicies[ num - 1 ] ] > MAX_CODE_BITS ) {
        if( !(cmd->flags & BE_QUIET) ) {
            WriteMsg( "Can't do shannon-fano compression: code length too long\n" );
        }
        return( FALSE );
    }
    memset( code, 0, NUM_CHARS * sizeof( unsigned ) );
    codeval = 0;
    codeinc = 0;
    lastlen = 0;
    for( index = num - 1; index >= 0; index -- ) {
        codeval += codeinc;
        if( len[ indicies[ index ] ] != lastlen ) {
            lastlen = len[ indicies[ index ] ];
            codeinc = 1 << (MAX_CODE_BITS - lastlen);
        }
        code[ indicies[ index ] ] = codeval;
    }
    return( TRUE );
}

static unsigned putbuf = 0;
static uchar putlen = 0;

static void Putcode(int l, unsigned c)        /* output c bits */
/************************************/
{
    putbuf |= c >> putlen;
    if ((putlen += l) >= 8) {
        EncWriteByte( putbuf >> 8 );
        if ((putlen -= 8) >= 8) {
            EncWriteByte( putbuf );
            codesize += 2;
            putlen -= 8;
            putbuf = c << (l - putlen);
        } else {
            putbuf <<= 8;
            codesize++;
        }
    }
}

static void EncodePosition( void )
/********************************/
{
    unsigned i;

    /* output upper 6 bits with encoding */
    i = EncReadByte();
    Putcode(p_len[i], (unsigned)p_code[i] << 8);

    i = EncReadByte();
    /* output lower 6 bits directly */
    Putcode(6, i << 10);
}

static void EncodeEnd( void )
/***************************/
{
    if (putlen) {
        EncWriteByte( putbuf >> 8 );
        codesize++;
    }
    putbuf = 0;
    putlen = 0;
}

static void CalcLengths( unsigned long num, int start, int finish, byte tlen )
/****************************************************************************/
{
    unsigned long   subtotal;
    int             index;


// find place that divides frequency as evenly as possible

    subtotal = 0;
    index = start;
    for(;;) {
        subtotal += code[ indicies[ index ] ];
        if( subtotal >= num / 2 ) break;
        if( index >= finish - 1 ) break;
        index++;
    }

// recursively keep subdividing the list until all elements have a length

    tlen++;
    if( index == start ) {
        len[ indicies[ index ] ] = tlen;
    } else {
        CalcLengths( subtotal, start, index, tlen );
    }
    if( index >= finish - 1 ) {
        len[ indicies[ finish ] ] = tlen;
    } else {
        CalcLengths( num - subtotal, index + 1, finish, tlen );
    }
}

static void FreeRunList( void )
/*****************************/
{
    runlist *   next;

    while( RunList != NULL ) {
        next = RunList->next;
        free( RunList );
        RunList = next;
    }
}

static void StartRunList( void )
/******************************/
{
    RunList = WPMemAlloc( MAX_COPYLIST_SIZE + sizeof( runlist ) );
    RunList->next = NULL;
    CurrRun = RunList;
    NumSpilled = 0;
    LastRunLen = 0;
}

static void NewRunBuffer( void )
/******************************/
{
    runlist *   buf;

    buf = NULL;
    if( NumSpilled == 0 ) {
        buf = malloc( sizeof( runlist ) + MAX_COPYLIST_SIZE );
    }
    if( buf == NULL ) {
        NumSpilled++;
        QWrite( RunHandle, CurrRun->data, MAX_COPYLIST_SIZE );
    } else {
        CurrRun->next = buf;
        buf->next = NULL;
        CurrRun = buf;
    }
    LastRunLen = 0;
}

static bool     WasLiteral;
static byte     CurrRunLen;

static void AddRunEntry( void )
/*****************************/
{
    if( !WasLiteral ) CurrRunLen |= 0x80;
    if( LastRunLen >= MAX_COPYLIST_SIZE ) NewRunBuffer();
    *(CurrRun->data + LastRunLen) = CurrRunLen;
    LastRunLen++;
    CurrRunLen = 0;
}

static void WriteTmpByte( bool inliteral, unsigned c )
/****************************************************/
{
    int     index;

    if( inliteral != WasLiteral || CurrRunLen >= 0x7F ) {
        AddRunEntry();
        WasLiteral = inliteral;
   }
    CurrRunLen++;
    if( code[ c ] == 0xFFFF ) {
        for( index = 0; index < NUM_CHARS; index++ ) {
            code[ index ] = (code[ index ] + 1) / 2;
        }
    }
    code[ c ]++;
}

static void WriteCodes( void )
/****************************/
{
    int     index;