Dream 52/Amiga_Dream_52.iso/Amiga/Workbench/Archivers/PPCxDMSWOS.lha/source.lha/src/u_deep.c

C/C++ Source or Header | 1998-02-17 | 4KB | 209 lines

/*
 *     xDMS  v1.0  -  Portable DMS archive unpacker  -  Public Domain
 *     Written by     Andre R. de la Rocha  <[e-mail]>
 *
 *     Lempel-Ziv-DynamicHuffman decompression functions used in Deep
 *     mode.
 *     Most routines ripped from LZHUF written by  Haruyasu Yoshizaki
 *
 */

#include <string.h>

#include "cdata.h"
#include "tables.h"
#include "u_deep.h"
#include "getbits.h"


static USHORT deep_text_loc;



INLINE USHORT DecodeChar(void);
INLINE USHORT DecodePosition(void);
INLINE void update(USHORT c);
static void reconst(void);



#define DBITMASK 0x3fff   /*  uses 16Kb dictionary  */

#define F       60  /* lookahead buffer size */
#define THRESHOLD   2
#define N_CHAR      (256 - THRESHOLD + F)   /* kinds of characters (character code = 0..N_CHAR-1) */
#define T       (N_CHAR * 2 - 1)    /* size of table */
#define R       (T - 1)         /* position of root */
#define MAX_FREQ    0x8000      /* updates tree when the */


USHORT freq[T + 1]; /* frequency table */

USHORT prnt[T + N_CHAR]; /* pointers to parent nodes, except for the */
                /* elements [T..T + N_CHAR - 1] which are used to get */
                /* the positions of leaves corresponding to the codes. */

USHORT son[T];   /* pointers to child nodes (son[], son[] + 1) */



void Init_DEEP(void){
    USHORT i, j;

    for (i = 0; i < N_CHAR; i++) {
        freq[i] = 1;
        son[i] = (USHORT)(i + T);
        prnt[i + T] = i;
    }
    i = 0; j = N_CHAR;
    while (j <= R) {
        freq[j] = (USHORT) (freq[i] + freq[i + 1]);
        son[j] = i;
        prnt[i] = prnt[i + 1] = j;
        i += 2; j++;
    }
    freq[T] = 0xffff;
    prnt[R] = 0;

    deep_text_loc = 0x3fc4;
    memset(text,0,0x3fc8);
}



USHORT Unpack_DEEP(UCHAR *in, UCHAR *out, UCHAR flags, USHORT origsize){
    USHORT i, j, c;
    UCHAR *outend;

    initbitbuf(in);

    outend = out+origsize;
    while (out < outend) {
        c = DecodeChar();
        if (c < 256) {
            *out++ = text[deep_text_loc++ & DBITMASK] = (UCHAR)c;
        } else {
            j = (USHORT) (c - 255 + THRESHOLD);
            i = (USHORT) (deep_text_loc - DecodePosition() - 1);
            while (j--) *out++ = text[deep_text_loc++ & DBITMASK] = text[i++ & DBITMASK];
        }
    }

    deep_text_loc = (USHORT)((deep_text_loc+60) & DBITMASK);

    if (!(flags & 1)) Init_DEEP();

    return 0;
}



INLINE USHORT DecodeChar(void){
    USHORT c;

    c = son[R];

    /* travel from root to leaf, */
    /* choosing the smaller child node (son[]) if the read bit is 0, */
    /* the bigger (son[]+1} if 1 */
    while (c < T) {
        c = son[c + GETBITS(1)];
        DROPBITS(1);
    }
    c -= T;
    update(c);
    return c;
}



INLINE USHORT DecodePosition(void){
    USHORT i, j, c;

    i = GETBITS(8);  DROPBITS(8);
    c = (USHORT) (d_code[i] << 8);
    j = d_len[i];
    i = (USHORT) (((i << j) | GETBITS(j)) & 0xff);  DROPBITS(j);

    return (USHORT) (c | i) ;
}



/* reconstruction of tree */

static void reconst(void){
    USHORT i, j, k, f, l;

    /* collect leaf nodes in the first half of the table */
    /* and replace the freq by (freq + 1) / 2. */
    j = 0;
    for (i = 0; i < T; i++) {
        if (son[i] >= T) {
            freq[j] = (USHORT) ((freq[i] + 1) / 2);
            son[j] = son[i];
            j++;
        }
    }
    /* begin constructing tree by connecting sons */
    for (i = 0, j = N_CHAR; j < T; i += 2, j++) {
        k = (USHORT) (i + 1);
        f = freq[j] = (USHORT) (freq[i] + freq[k]);
        for (k = (USHORT)(j - 1); f < freq[k]; k--);
        k++;
        l = (USHORT)((j - k) * 2);
        memmove(&freq[k + 1], &freq[k], (size_t)l);
        freq[k] = f;
        memmove(&son[k + 1], &son[k], (size_t)l);
        son[k] = i;
    }
    /* connect prnt */
    for (i = 0; i < T; i++) {
        if ((k = son[i]) >= T) {
            prnt[k] = i;
        } else {
            prnt[k] = prnt[k + 1] = i;
        }
    }
}



/* increment frequency of given code by one, and update tree */

INLINE void update(USHORT c){
    USHORT i, j, k, l;

    if (freq[R] == MAX_FREQ) {
        reconst();
    }
    c = prnt[c + T];
    do {
        k = ++freq[c];

        /* if the order is disturbed, exchange nodes */
        if (k > freq[l = (USHORT)(c + 1)]) {
            while (k > freq[++l]);
            l--;
            freq[c] = freq[l];
            freq[l] = k;

            i = son[c];
            prnt[i] = l;
            if (i < T) prnt[i + 1] = l;

            j = son[l];
            son[l] = i;

            prnt[j] = c;
            if (j < T) prnt[j + 1] = c;
            son[c] = j;

            c = l;
        }
    } while ((c = prnt[c]) != 0); /* repeat up to root */
}