encode.c

open arj source

   putbits(CBIT, 0);
   putbits(CBIT, root);
  }
  root=make_tree(NP, p_freq, pt_len, (unsigned short FAR *)pt_code);
  if(root>=NP)
   write_pt_len(NP, PBIT, -1);
  else
  {
   putbits(PBIT, 0);
   putbits(PBIT, root);
  }
  pos=0;
  for(i=0; i<size; i++)
  {
   if(unpackable)
    return;
   if(i%CHAR_BIT==0)
    flags=buf[pos++];
   else
    flags<<=1;
   if(flags&(1U<<(CHAR_BIT-1)))
   {
    c=(unsigned int)buf[pos++]+(1<<CHAR_BIT);
    encode_c(c);
    k=buf[pos++];
    k|=(unsigned int)buf[pos++]<<CHAR_BIT;
    encode_p(k);
   }
   else
   {
    c=buf[pos++];
    encode_c(c);
   }
  }
  for(i=0; i<NC; i++)
   c_freq[i]=0;
  for(i=0; i<NP; i++)
   p_freq[i]=0;
 }
}

/* Handy macro for retrieval of two bytes (don't care about the portability) */

#ifdef ALIGN_POINTERS
 #define word_ptr(c) (  (((unsigned char *) (c))[0]<<8)+ ((unsigned char *) (c))[1] )
 #define _diff(c1,c2) ( (c1)[0]!=(c2)[0] || (c1)[1]!=(c2)[1] )
#elif !defined(TILED)
 #define word_ptr(c) (*(unsigned short *)(c))
#endif

/* Tree update routine. Possibly the most time-consuming one. */

static int upd_tree(int n_c)
{
 #ifdef ASM8086
  asm{
                push    bp
                push    si
                push    di
                mov     si, n_c
                mov     bp, 1
                mov     es, word ptr dtree+2
                mov     bx, si
                mov     bx, es:[bx+si]
                or      bx, bx
                jl      done_dup
  }
ok:
  asm{
                mov     di, tree
                add     si, di
                add     di, bx
                mov     ax, [si]
                cld
                mov     dx, numchars
                dec     dx
                jge     ut_loop
  }
done_dup:
  asm{
                jmp     done
  }
ut_fetch:
  asm{
                mov     ax, [bp+si-1]
  }
select_pos:
  asm{
                mov     di, tree
                add     di, bp
  }
ut_loopbody:
  asm{
                dec     dx
                jl      ut_brk
                shl     bx, 1
                mov     bx, es:[bx]
                or      bx, bx
                jl      ut_brk
                cmp     ax, [bx+di-1]
                jz      ut_rcount
                dec     dx
                shl     bx, 1
                mov     bx, es:[bx]
                or      bx, bx
                jl      ut_brk
                cmp     ax, [bx+di-1]
                je      ut_rcount
                dec     dx
                shl     bx, 1
                mov     bx, es:[bx]
                or      bx, bx
                jl      ut_brk
                cmp     ax, [bx+di-1]
                je      ut_rcount
                dec     dx
                shl     bx, 1
                mov     bx, es:[bx]
                or      bx, bx
                jl      ut_brk
                cmp     ax, [bx+di-1]
                je      ut_rcount
                dec     dx
                shl     bx, 1
                mov     bx, es:[bx]
                or      bx, bx
                jl      ut_brk
                cmp     ax, [bx+di-1]
                je      ut_rcount
                dec     dx
                shl     bx, 1
                mov     bx, es:[bx]
                or      bx, bx
                jl      ut_brk
                cmp     ax, [bx+di-1]
                je      ut_rcount
                jmp     short ut_loopbody
  }
ut_brk:
  asm{
                jmp     short upd_finish
  }
ut_rcount:
  asm{
                sub     di, bp
                add     di, bx
  }
ut_loop:
  asm{
                mov     cx, [si]
                cmp     cx, [di]
                jnz     select_pos
                mov     ax, ds
                mov     es, ax
                mov     ax, di
                add     di, 2
                add     si, 2
                mov     cx, 128
                repe cmpsw
                mov     cl, [di-2]
                sub     cl, [si-2]
                xchg    ax, di
                sub     ax, di
                sub     si, ax
                sub     cl, 1
                adc     ax, -2
                mov     es, word ptr dtree+2
                cmp     ax, bp
                jg      verify_pos
                jmp     ut_fetch
  }
verify_pos:
  asm{
                mov     cx, si
                sub     cx, di
                cmp     cx, dicsiz_cur
                jg      upd_finish
                dec     cx
                mov     dicpos, cx
                mov     bp, ax
                cmp     bp, 256
                jge     upd_finish
                jmp     ut_fetch
  }
upd_finish:
  asm{
                cmp     bp, 256
                jle     done
                mov     bp, 256
  }
done:
  asm{
                mov     ax, bp
                mov     tc_passes, ax
                pop     di
                pop     si
                pop     bp
  }
  return(tc_passes);
 #else
 short FAR *dptr;
 short r_bx, r_dx;
 unsigned short r_ax;
 short r_bp=1;
 unsigned char *tptr;
 unsigned char *tdptr;
 unsigned char *prev_tptr, *prev_tdptr;
 int c;
 char diff;
 int remainder;

 dptr=dtree;
 if((r_bx=dptr[n_c])>=0)
 {
  tptr=tree+n_c;
  tdptr=tree+r_bx;
  r_ax=word_ptr(tptr);
  r_dx=numchars;
  if(--r_dx>=0)
   goto ut_loop;
ut_fetch:
  r_ax=word_ptr(tptr+r_bp-1);
select_pos:
  tdptr=tree+r_bp;
  do
  {
   if(--r_dx<0)
    goto upd_finish;
   r_bx=dptr[r_bx];
   if(r_bx<0)
    goto upd_finish;
  } while(r_ax!=word_ptr(tdptr+r_bx-1));
  tdptr+=r_bx-r_bp;
ut_loop:
  #ifdef ALIGN_POINTERS
  if (_diff(tptr,tdptr))
  #else  
  if(word_ptr(tptr)!=word_ptr(tdptr))
  #endif
   goto select_pos;
  prev_tptr=tptr;
  prev_tdptr=tdptr;
  tptr+=2;
  tdptr+=2;
  for(c=128; c>0; c--)
  {
   #ifdef ALIGN_POINTERS
   if (_diff(tptr,tdptr))
   #else  
   if(word_ptr(tptr)!=word_ptr(tdptr))
   #endif
    break;
   tptr+=2;
   tdptr+=2;
  }
  diff=*(tdptr)-*(tptr);
  remainder=tdptr-prev_tdptr;
  if(diff==0)
   remainder+=1;
  tptr=prev_tptr;
  tdptr=prev_tdptr;
  if(remainder<=r_bp)
   goto ut_fetch;
  if(tptr-tdptr<=dicsiz_cur)
  {
   dicpos=tptr-tdptr-1;
   r_bp=remainder;
   if(r_bp<256)
    goto ut_fetch;
  }
upd_finish:
  if(r_bp>256)
   r_bp=256;
 }
 return(tc_passes=r_bp);
 #endif
}

/* Optimized output routine */

static void output(int c, unsigned short p)
{
 unsigned char FAR *bptr;
 unsigned char cy;
 unsigned short r_dx;
 unsigned short r_bx;

 bptr=buf;
 r_dx=cpos;
 cy=output_mask&1;
 output_mask=(cy?0x80:0)|((output_mask&0xFF)>>1);
 if(cy)
 {
  if(r_dx>=bufsiz)
  {
   send_block();
   if(unpackable)
   {
    cpos=bptr-buf;
    return;
   }
   r_dx=0;
  }
  output_pos=r_dx;
  buf[r_dx]=0;
  r_dx++;
 }
 bptr+=r_dx;
 *bptr++=c;
 c_freq[c]++;
 if(c>=256)
 {
  buf[output_pos]|=output_mask;
  *bptr++=p&0xFF;
  *bptr++=(p>>8);
  for(r_bx=0; p!=0; p>>=1)
   r_bx++;
  p_freq[r_bx]++;
 }
 cpos=bptr-buf;
}

/* Unstubbed optimized output routine */

static void output_opt(unsigned char c)
{
 unsigned char FAR *bptr, FAR *cptr;
 unsigned short r_dx;
 unsigned char cy;

 cptr=bptr=buf;
 r_dx=cpos;
 cy=output_mask&1;
 output_mask=(cy?0x80:0)|((output_mask&0xFF)>>1);
 if(cy)
 {
  if(r_dx>=bufsiz)
  {
   send_block();
   r_dx=0;
   if(unpackable)
   {
    cpos=r_dx;
    return;
   }
  }
  output_pos=r_dx;
  cptr[r_dx]=0;
  r_dx++;
 }
 bptr+=r_dx;
 *bptr++=c;
 c_freq[c]++;
 cpos=bptr-cptr;
}

/* Initializes memory for encoding */

void allocate_memory()
{
 int i;

 if((c_freq=calloc(NC*2-1, sizeof(*c_freq)))==NULL)
  error(M_OUT_OF_NEAR_MEMORY);
 if((c_code=farcalloc(NC, sizeof(*c_code)))==NULL)
  error(M_OUT_OF_MEMORY);
 if((heap=farcalloc(NC+1, sizeof(*heap)))==NULL)
  error(M_OUT_OF_MEMORY);
 for(i=0; i<NP; i++)
  p_freq[i]=0;
 depth=0;
 bufsiz=current_bufsiz;
 if(bufsiz>=MAX_BUFSIZ-BUFSIZ_INCREMENT)
  bufsiz=MAX_BUFSIZ-1;
 #ifdef FINETUNE_BUFSIZ
  i=1;
 #endif
 /* Adjust the buffer size if there's not enough memory for it */
 while((buf=farmalloc(bufsiz))==NULL)
 {
  #ifndef FINETUNE_BUFSIZ
   bufsiz=bufsiz/10U*9U;
  #else
   if(i<2048)
    bufsiz-=i++;
   else
    bufsiz=bufsiz/16U*15U;
  #endif
  if(bufsiz<MIN_BUFSIZ)
   error(M_OUT_OF_MEMORY);
 }
 if(debug_enabled&&strchr(debug_opt, 'v')!=NULL)
  msg_cprintf(0, M_BUFSIZ, bufsiz);
 init_putbits();
 output_mask=1;
 output_pos=0;
 cpos=0;
 buf[output_pos]='\0';
 bufsiz-=30;
}

/* Shutdown the encoding */

void NEAR huf_encode_end()
{
 if(!unpackable)
  send_block();
 shutdown_putbits();
 free(c_freq);
 farfree(c_code);
 farfree(heap);
 farfree(buf);
 bufsiz=0;
 cpos=0;
}

/* Basic encoding routine */

static void NEAR huf_encode()
{
 int hash_bits;
 unsigned short fp_max;
 int nchars;
 int i, j, m=0;
 short k, l;
 unsigned short t;                      /* Exchange variable */
 int tree_el;
 unsigned int n_passes;
 unsigned int f_dicpos;
 unsigned int fetch;
 unsigned int max_fetch;                /* For comparision */
 short FAR *fptr;
 short FAR *dtptr;
 unsigned char *tptr;
 unsigned short r_cx, r_dx, r_ax;
 int pm;

 hash_bits=(dicbit+2)/3;
 fpcount=1U<<dicbit;
 fp_max=fpcount-1;
 if(tree==NULL)
 {
  if((tree=calloc(treesize+2, sizeof(*tree)))==NULL)
   error(M_OUT_OF_NEAR_MEMORY);
  #ifdef ASM8086
   ftree=farcalloc_based((unsigned long)treesize+16L, sizeof(*ftree));
   dtree=(FP_OFF(ftree)==0)?ftree:MK_FP(FP_SEG(ftree)+((FP_OFF(ftree)+15)>>4), 0);
  #else
   ftree=dtree=farcalloc((unsigned long)treesize+16L, sizeof(*ftree));
  #endif
  fpbuf=farcalloc((unsigned long)fpcount+4L, 2L);
  if(ftree==NULL||fpbuf==NULL)
   error(M_OUT_OF_MEMORY);
 }
 if(dic_alloc<1024)
  dic_alloc=1024;
 allocate_memory();
 nchars=(UCHAR_MAX+THRESHOLD)*2;
 display_indicator(0L);
 encoded_bytes=0L;
 tc_passes=0;
 dicpos=0;
 i=j=0;
 while(!unpackable)
 {
  tree_el=0;
  k=0;
  if(j!=0)
  {
   tree_el=dic_alloc;
   if((k=j-tree_el)<=0)
   {
    k=0;
    tree_el=j;
   }
   else
    memmove(tree, tree+k, tree_el);
  }
  max_fetch=fetch=(unsigned int)(treesize-tree_el);
  if(multivolume_option)
   fetch=check_multivolume(fetch);
  if(max_fetch!=fetch)
   nchars=4;
  if((fetch=fetch_uncomp(tree+tree_el, fetch))==0)
  {
   if(tree_el==0||k==0)
    break;
   memmove(tree+k, tree, tree_el);
   dicsiz_cur=min(tree_el-i-1, dicsiz_cur);
   break;
  }
  j=fetch+tree_el;
  encoded_bytes+=(unsigned long)fetch;
  display_indicator(encoded_bytes);
  m=0;
  if(k<=0)
   fill_fpbuf();
  else
  {
   fptr=fpbuf;
   for(l=fpcount>>2; l>0; l--)
   {
    *fptr=max(*fptr-k, -1);
    fptr++;
    *fptr=max(*fptr-k, -1);
    fptr++;
    *fptr=max(*fptr-k, -1);
    fptr++;
    *fptr=max(*fptr-k, -1);
    fptr++;
   }
   dtptr=dtree;
   for(l=tree_el>>3; l>0; l--)
   {
    *dtptr=max(dtptr[k]-k, -1);
    dtptr++;
    *dtptr=max(dtptr[k]-k, -1);
    dtptr++;
    *dtptr=max(dtptr[k]-k, -1);
    dtptr++;
    *dtptr=max(dtptr[k]-k, -1);
    dtptr++;
    *dtptr=max(dtptr[k]-k, -1);
    dtptr++;
    *dtptr=max(dtptr[k]-k, -1);
    dtptr++;
    *dtptr=max(dtptr[k]-k, -1);
    dtptr++;
    *dtptr=max(dtptr[k]-k, -1);
    dtptr++;
   }
   /* Store the remainder */
   for(l=tree_el%8; l>0; l--)
   {
    *dtptr=max(dtptr[k]-k, -1);
    dtptr++;
   }
   m+=tree_el;
   if(m>=2)
    m-=2;
  }
  tptr=&tree[m];
  r_dx=(unsigned short)*(tptr++);
  r_cx=(fp_max&0xFF00)|(hash_bits&0xFF);
  r_dx<<=(hash_bits&0xFF);
  r_dx^=(unsigned short)*(tptr++);