encode.c

arj source code

/*
 * $Id: encode.c,v 1.5 2003/05/03 22:18:47 andrew_belov Exp $
 * ---------------------------------------------------------------------------
 * The data compression procedures are located in this module.
 *
 */

#include "arj.h"

#ifdef TILED
 #include <dos.h>                       /* Weird, eh? */
#endif

DEBUGHDR(__FILE__)                      /* Debug information block */

static int st_n;

unsigned short *c_freq;
unsigned short FAR *c_code;
unsigned short FAR *heap;
unsigned short len_cnt[17];
unsigned short p_freq[2*NP-1];
unsigned short pt_code[NPT];
int depth;
unsigned char FAR *buf;
unsigned char output_mask;
unsigned short output_pos;
int dicbit;
unsigned short t_freq[2*NT-1];
int heapsize;
unsigned short FAR *sortptr;
unsigned char *len;
unsigned short *freq;
unsigned short fpcount;
short FAR *fpbuf;
short FAR *dtree;
unsigned short treesize;
unsigned char *tree=NULL;
unsigned short numchars;
unsigned short dicsiz_cur;
unsigned short dicpos;
unsigned short tc_passes;
short FAR *ftree;
unsigned int dic_alloc;
unsigned long encoded_bytes;

/* Inline functions */

#define encode_c(c)                     \
        putbits(c_len[c], c_code[c])

#define encode_p(p)                     \
{                                       \
 unsigned int qc, q;                    \
 qc=0;                                  \
 q=p;                                   \
 while(q)                               \
 {                                      \
  q>>=1;                                \
  qc++;                                 \
 }                                      \
 putbits(pt_len[qc], pt_code[qc]);      \
 if(qc>1)                               \
  putbits(qc-1, p);                     \
}

/* Bitwise output routine */

void putbits(int n_c, unsigned short n_x)
{
 #ifdef ASM8086
  asm{
                mov     cl, byte ptr n_c
                mov     dx, n_x
                mov     ch, cl
                sub     cl, 16
                neg     cl
                shl     dx, cl
                mov     cl, byte ptr bitcount
                mov     ax, dx
                shr     ax, cl
                or      bitbuf, ax
                add     cl, ch
                cmp     cl, 8
                jge     chunk1
                mov     byte ptr bitcount, cl
                jmp     procend
  }
chunk1:
  asm{
                push    si
                mov     si, out_bytes
                cmp     si, out_avail
                jge     flush
  }
acc_loop:
  asm{
                mov     bx, out_buffer
                mov     ah, byte ptr bitbuf+1
                mov     [bx+si], ah
                inc     si
                sub     cl, 8
                cmp     cl, 8
                jge     avail_chk
 #if TARGET==OS2
                shl     bitbuf, 8
 #else
                mov     ah, byte ptr bitbuf
                mov     al, 0
                mov     bitbuf, ax
 #endif
                jmp     endpoint
  }
avail_chk:
  asm{
                cmp     si, out_avail
                jge     r_flush
  }
cpoint:
  asm{
                mov     al, byte ptr bitbuf
                mov     [bx+si], al
                inc     si
                sub     cl, 8
                sub     ch, cl
                xchg    cl, ch
                shl     dx, cl
                mov     bitbuf, dx
                mov     cl, ch
                jmp     endpoint
  }
flush:
  asm{
                push    dx
                push    cx
  }
                flush_compdata();
  asm{
                pop     cx
                pop     dx
                mov     si, out_bytes
                jmp     short acc_loop
  }
 r_flush:
  asm{
                mov     out_bytes, si
                push    dx
                push    cx
                push    bx
  }
                flush_compdata();
  asm{
                pop     bx
                pop     cx
                pop     dx
                mov     si, out_bytes
                jmp     short cpoint
  }
 endpoint:
  asm{
                mov     out_bytes, si
                pop     si
                mov     byte ptr bitcount, cl
  }
 procend:;
 #else
  int p_n;
  int bt;

  p_n=n_c;
  n_c=16-n_c;
  n_x<<=n_c;
  n_c=bitcount;
  bitbuf|=(n_x>>n_c);
  n_c+=p_n;
  if(n_c<8)
  {
   bitcount=n_c;
   return;
  }
  bt=out_bytes;
  if(bt>=out_avail)
  {
   flush_compdata();
   bt=out_bytes;
  }
  out_buffer[bt++]=bitbuf>>8;
  n_c-=8;
  if(n_c<8)
  {
   bitbuf<<=8;
   out_bytes=bt;
   bitcount=n_c;
   return;
  }
  if(bt>=out_avail)
  {
   out_bytes=bt;
   flush_compdata();
   bt=out_bytes;
  }
  out_buffer[bt++]=bitbuf;
  n_c-=8;
  p_n-=n_c;
  bitbuf=n_x<<p_n;
  out_bytes=bt;
  bitcount=n_c;
 #endif
}

/* Quick fill routine */

static void fill_fpbuf()
{
 #ifdef ASM8086
  asm{
                push    di
                cld
                mov     ax, 65535
                les     di, fpbuf
                mov     cx, fpcount
                rep     stosw
                pop     di
  }
 #else
  unsigned int i;

  for(i=0; i<fpcount; i++)
   fpbuf[i]=-1;
 #endif
}

/* Reduces the number of bits for smaller files */

void adjust_dicbit()
{
 if(uncompsize<16384)
  dicbit=12;
}

/* Reads data from the source file or a memory region */

#if SFX_LEVEL>=ARJ
int fetch_uncomp(char *dest, int n)
{
 unsigned int fetch_size;

 if(file_packing)
  return(fread_crc(dest, n, encstream));
 else
 {
  if(encmem_remain==0)
   return(0);
  fetch_size=min((unsigned int)n, encmem_remain);
  far_memmove((char FAR *)dest, encblock_ptr, fetch_size);
  crc32_for_block(dest, fetch_size);
  encmem_remain-=fetch_size;
  encblock_ptr+=fetch_size;
  return(fetch_size);
 }
}
#endif

/* Fills the length table depending on the leaf depth (call with i==root) */

static void count_len(int i)
{
 static int depth=0;

 if(i<st_n)
  len_cnt[(depth<16)?depth:16]++;
 else
 {
  depth++;
  count_len(left[i]);
  count_len(right[i]);
  depth--;
 }
}

/* Makes length counter table */

static void NEAR make_len(int root)
{
 int i, k;
 unsigned short cum;

 for(i=0; i<=16; i++)
  len_cnt[i]=0;
 count_len(root);
 cum=0;
 for(i=16; i>0; i--)
  cum+=len_cnt[i]<<(16-i);
 while(cum!=0)
 {
  if(debug_enabled&&strchr(debug_opt, 'f')!=NULL)
   msg_cprintf(0, M_HDF_FIX);
  len_cnt[16]--;
  for(i=15; i>0; i--)
  {
   if(len_cnt[i]!=0)
   {
    len_cnt[i]--;
    len_cnt[i+1]+=2;
    break;
   }
  }
  cum--;
 }
 for(i=16; i>0; i--)
 {
  k=len_cnt[i];
  while(--k>=0)
   len[*sortptr++]=i;
 }
}

/* Sends i-th entry down the heap */

static void NEAR downheap(int i)
{
 int j, k;

 k=heap[i];
 while((j=2*i)<=heapsize)
 {
  if(j<heapsize&&freq[heap[j]]>freq[heap[j+1]])
   j++;
  if(freq[k]<=freq[heap[j]])
   break;
  heap[i]=heap[j];
  i=j;
 }
 heap[i]=k;
}

/* Encodes a length table element */

static void NEAR make_code(int n, unsigned char *len, unsigned short FAR *code)
{
 int i;
 unsigned short start[18];

 start[1]=0;
 for(i=1; i<=16; i++)
  start[i+1]=(start[i]+len_cnt[i])<<1;
 for(i=0; i<n; i++)
  code[i]=start[len[i]]++;
}

/* Makes tree, calculates len[], returns root */

static int make_tree(int nparm, unsigned short *freqparm, unsigned char *lenparm, unsigned short FAR *codeparm)
{
 int i, j, k, avail;

 st_n=nparm;
 freq=freqparm;
 len=lenparm;
 avail=st_n;
 heapsize=0;
 heap[1]=0;
 for(i=0; i<st_n; i++)
 {
  len[i]=0;
  if(freq[i]!=0)
   heap[++heapsize]=i;
 }
 if(heapsize<2)
 {
  codeparm[heap[1]]=0;
  return(heap[1]);
 }
 for(i=heapsize>>1; i>=1; i--)
  downheap(i);                          /* Make priority queue */
 sortptr=codeparm;
 /* While queue has at least two entries */
 do
 {
  i=heap[1];                     	/* Take out least-freq entry */
  if(i<st_n)
   *(sortptr++)=i;
  heap[1]=heap[heapsize--];
  downheap(1);
  j=heap[1];                            /* Next least-freq entry */
  if(j<st_n)
   *(sortptr++)=j;
  k=avail++;                     	/* Generate new node */
  freq[k]=freq[i]+freq[j];
  heap[1]=k;
  downheap(1);                   	/* Put into queue */
  left[k]=i;
  right[k]=j;
 } while(heapsize>1);
 sortptr=codeparm;
 make_len(k);
 make_code(nparm, lenparm, codeparm);
 return(k);                            /* Return root */
}

/* Counts the cumulative frequency */

void count_t_freq()
{
 int i, k, n, count;

 for(i=0; i<NT; i++)
  t_freq[i]=0;
 n=NC;
 while(n>0&&c_len[n-1]==0)
  n--;
 i=0;
 while(i<n)
 {
  k=c_len[i++];
  if(k==0)
  {
   count=1;
   while(i<n&&c_len[i]==0)
   {
    i++;
    count++;
   }
   if(count<=2)
    t_freq[0]+=count;
   else if(count<=18)
    t_freq[1]++;
   else if(count==19)
   {
    t_freq[0]++;
    t_freq[1]++;
   }
   else
    t_freq[2]++;
  }
  else
   t_freq[k+2]++;
 }
}

/* Writes the encoded length */

void write_pt_len(int n, int nbit, int i_special)
{
 int i, k;

 while(n>0&&pt_len[n-1]==0)
  n--;
 putbits(nbit, n);
 i=0;
 while(i<n)
 {
  k=(int)pt_len[i++];
  if(k<=6)
  {
   putbits(3, k);
  }
  else
   putbits(k-3, 0xFFFE);
  if(i==i_special)
  {
   while(i<6&&pt_len[i]==0)
    i++;
   putbits(2, i-3);
  }
 }
}

/* Writes character length */

void write_c_len()
{
 int i, k, n, count;

 n=NC;
 while(n>0&&c_len[n-1]==0)
  n--;
 putbits(CBIT, n);
 i=0;
 while(i<n)
 {
  k=(int)c_len[i++];
  if(k==0)
  {
   count=1;
   while(i<n&&c_len[i]==0)
   {
    i++;
    count++;
   }
   if(count<=2)
   {
    for(k=0; k<count; k++)
     putbits(pt_len[0], pt_code[0]);
   }
   else if(count<=18)
   {
    putbits(pt_len[1], pt_code[1]);
    putbits(4, count-3);
   }
   else if(count==19)
   {
    putbits(pt_len[0], pt_code[0]);
    putbits(pt_len[1], pt_code[1]);
    putbits(4, 15);
   }
   else
   {
    putbits(pt_len[2], pt_code[2]);
    putbits(CBIT, count-20);
   }
  }
  else
   putbits(pt_len[k+2], pt_code[k+2]);
 }
}

/* Encodes a block and writes it to the output file */

void send_block()
{
 unsigned int i, k, flags=0, root, pos, size;
 unsigned int c;

 if(!unpackable)
 {
  root=make_tree(NC, c_freq, c_len, c_code);
  size=c_freq[root];
  putbits(16, size);
  if(root>=NC)
  {
   count_t_freq();
   root=make_tree(NT, t_freq, pt_len, (unsigned short FAR *)pt_code);
   if(root>=NT)
    write_pt_len(NT, TBIT, 3);
   else
   {
    putbits(TBIT, 0);
    putbits(TBIT, root);
   }
   write_c_len();
  }
  else
  {
   putbits(TBIT, 0);
   putbits(TBIT, 0);