/*
 * @(#) arithpck.c - Arithmetic encode/decode operations library (source).
 * (c) 1998 Ivan Maidanski <ivmai@chat.ru> http://ivmai.chat.ru
 * Freeware function library source. All rights reserved.
 **
 * Language: ANSI C
 * Tested with: Microsoft Visual C++ (R) v4.2, Borland C/C++ v3.1
 * Last modified: 1998-08-16 11:30:00 GMT+04:00
 */

#include "arithpck.h" /* library header */

/*
 Note:
  declare your own ARITHPCK_MUL_SHR macro to override
   the use of predefined "mul&shr" function,
  declare your own ARITHPCK_DIV macro to override
   the use of predefined "div" function.
*/

#include <stddef.h> /* NULL */
#include <limits.h> /* CHAR_BIT */

#ifndef ARITHPCK_MUL_SHR
#include "lmuldiv.h" /* lu_mul_shr() */
#define ARITHPCK_MUL_SHR(a,b) \
 ((ARITHPCK_VALUE_TYPE)lu_mul_shr((unsigned long)(a),(unsigned long)(b)<< \
  ((sizeof(unsigned long)-sizeof(ARITHPCK_VALUE_TYPE))*CHAR_BIT)))
#endif

#ifndef ARITHPCK_DIV
#include "lmuldiv.h" /* lu_div_mod() */
#define ARITHPCK_DIV(h,l,d) \
 ((ARITHPCK_VALUE_TYPE)lu_div_mod(NULL,(unsigned long)(h)>> \
  ((sizeof(unsigned long)-sizeof(ARITHPCK_VALUE_TYPE))*CHAR_BIT), \
  ((unsigned long)(sizeof(ARITHPCK_VALUE_TYPE)<sizeof(unsigned long)? h:0) \
   <<(sizeof(ARITHPCK_VALUE_TYPE)*CHAR_BIT))| \
  (unsigned long)(ARITHPCK_VALUE_TYPE)(l),(unsigned long)(d)))
#endif

#define ARITHPCK_VALUE_HBIT \
 ((ARITHPCK_VALUE_TYPE)~((ARITHPCK_VALUE_TYPE)~(ARITHPCK_VALUE_TYPE)0>>1))
#define ARITHPCK_CODEBIT \
 ((unsigned char)~((unsigned char)~0>>1))

void arithencode(ARITHPCK_VALUE_TYPE *plow, ARITHPCK_VALUE_TYPE *phigh,
                 ARITHPCK_VALUE_TYPE cumlower, ARITHPCK_VALUE_TYPE cumupper,
                 ARITHPCK_VALUE_TYPE maxcum)
{
 register ARITHPCK_VALUE_TYPE oldrange=(ARITHPCK_VALUE_TYPE)(*phigh-*plow);
 oldrange++;
 if (cumupper<maxcum)
 {
  cumupper++;
  maxcum++;
  *phigh=(ARITHPCK_VALUE_TYPE)(oldrange?
          ARITHPCK_MUL_SHR(oldrange,cumupper) : cumupper);
  *phigh=(ARITHPCK_VALUE_TYPE)(*plow+(maxcum?
          ARITHPCK_DIV(*phigh,oldrange*cumupper,maxcum) : *phigh));
  maxcum--;
  --*phigh;
 }
 if (cumlower<=maxcum)
 {
  maxcum++;
  cumupper=(ARITHPCK_VALUE_TYPE)(oldrange?
            ARITHPCK_MUL_SHR(oldrange,cumlower) : cumlower);
  *plow=(ARITHPCK_VALUE_TYPE)(*plow+(maxcum?
         ARITHPCK_DIV(cumupper,oldrange*cumlower,maxcum) : cumupper));
 }
}

ARITHPCK_VALUE_TYPE arithdecode(ARITHPCK_VALUE_TYPE low,
                                ARITHPCK_VALUE_TYPE high,
                                ARITHPCK_VALUE_TYPE input,
                                ARITHPCK_VALUE_TYPE maxcum)
{
 if (input>=high)
  return maxcum;
 low--;
 input=(ARITHPCK_VALUE_TYPE)(input-low);
 high=(ARITHPCK_VALUE_TYPE)(high-low);
 low=(ARITHPCK_VALUE_TYPE)(++maxcum*input);
 maxcum=(ARITHPCK_VALUE_TYPE)(maxcum?
         ARITHPCK_MUL_SHR(maxcum,input) : input);
 if (!low)
  maxcum--;
 return (ARITHPCK_VALUE_TYPE)(high?
                              ARITHPCK_DIV(maxcum,--low,high) : maxcum);
}

void arithpacksym(ARITHPCK_VALUE_TYPE *plow, ARITHPCK_VALUE_TYPE *phigh,
                  ARITHPCK_SYM_TYPE sym,
                  ARITHPCK_SYM_TYPE symtbl[], ARITHPCK_FREQ_TYPE freqtbl[],
                  ARITHPCK_FREQ_TYPE scale, ARITHPCK_VALUE_TYPE *pmaxcum)
{
 ARITHPCK_VALUE_TYPE cumlower,cumupper;
 sym=freqmodelsearch(sym,symtbl);
 freqmodelgetcum(&cumlower,&cumupper,freqtbl,sym);
 arithencode(plow,phigh,cumlower,cumupper,*pmaxcum);
 freqmodelupdate(symtbl,freqtbl,pmaxcum,scale,sym);
}

ARITHPCK_SYM_TYPE arithunpacksym(ARITHPCK_VALUE_TYPE *plow,
                                 ARITHPCK_VALUE_TYPE *phigh,
                                 ARITHPCK_VALUE_TYPE input,
                                 ARITHPCK_SYM_TYPE symtbl[],
                                 ARITHPCK_FREQ_TYPE freqtbl[],
                                 ARITHPCK_FREQ_TYPE scale,
                                 ARITHPCK_VALUE_TYPE *pmaxcum)
{
 ARITHPCK_VALUE_TYPE cumlower=arithdecode(*plow,*phigh,input,*pmaxcum);
 ARITHPCK_SYM_TYPE index=freqmodelindex(&cumlower,&input,freqtbl);
 ARITHPCK_SYM_TYPE sym=symtbl[index];
 arithencode(plow,phigh,cumlower,input,*pmaxcum);
 freqmodelupdate(symtbl,freqtbl,pmaxcum,scale,index);
 return sym;
}

int arithoutput(unsigned char *poutcode,
                ARITHPCK_VALUE_TYPE *pinput, unsigned char *pincode,
                ARITHPCK_VALUE_TYPE *plow, ARITHPCK_VALUE_TYPE *phigh,
                ARITHPCK_VALUE_TYPE newmaxcum)
{
 register ARITHPCK_VALUE_TYPE value=0;
 if (!*poutcode)
  *poutcode=(unsigned char)1;
 *phigh=(ARITHPCK_VALUE_TYPE)(*plow^(~*phigh));
 while (*phigh&ARITHPCK_VALUE_HBIT)
 {
  if (pinput!=NULL)
  {
   *pinput<<=1;
   if (*pincode&ARITHPCK_CODEBIT)
    ++*pinput;
   *pincode<<=1;
  }
  value=(ARITHPCK_VALUE_TYPE)(*poutcode&ARITHPCK_CODEBIT);
  *poutcode<<=1;
  if (*plow&ARITHPCK_VALUE_HBIT)
   *poutcode|=(unsigned char)1;
  *plow<<=1,*phigh<<=1;
  if (value)
   break;
 }
 *phigh=(ARITHPCK_VALUE_TYPE)~(*plow^*phigh);
 if (!value && *phigh-*plow<newmaxcum)
 {
  for (value=0,*phigh=(ARITHPCK_VALUE_TYPE)~*phigh;
       *plow<<=1,*phigh<<=1,*plow&*phigh&ARITHPCK_VALUE_HBIT;
       value|=ARITHPCK_VALUE_HBIT,value>>=1);
  if (*plow|*phigh)
   value|=ARITHPCK_VALUE_HBIT,value>>=1;
  *plow=(ARITHPCK_VALUE_TYPE)(*plow&ARITHPCK_VALUE_HBIT?
                              ARITHPCK_VALUE_HBIT : value);
  *phigh=(ARITHPCK_VALUE_TYPE)(value^ARITHPCK_VALUE_HBIT);
  do
  {
   if (pinput!=NULL)
   {
    *pinput<<=1;
    if (*pincode&ARITHPCK_CODEBIT)
     ++*pinput;
    *pincode<<=1;
   }
   value=(ARITHPCK_VALUE_TYPE)(*poutcode&ARITHPCK_CODEBIT);
   *poutcode<<=1;
   if (*plow&ARITHPCK_VALUE_HBIT)
    *poutcode|=(unsigned char)1;
   *plow<<=1,*phigh<<=1;
  } while (!value && *phigh&ARITHPCK_VALUE_HBIT);
  *phigh=(ARITHPCK_VALUE_TYPE)~(*plow^*phigh);
 }
 return value? 1 : 0;
}

int arithinitinput(ARITHPCK_VALUE_TYPE *pinput, unsigned char incode)
{
 if (!*pinput)
  *pinput=1;
 if (*pinput&
     ((ARITHPCK_VALUE_TYPE)1<<((sizeof(ARITHPCK_VALUE_TYPE)-1)*CHAR_BIT)))
 {
  *pinput<<=CHAR_BIT;
  *pinput|=(ARITHPCK_VALUE_TYPE)incode;
  return 0;
 }
 *pinput<<=CHAR_BIT;
 *pinput|=(ARITHPCK_VALUE_TYPE)incode;
 return 1;
}

int arithflushfinish(unsigned char *poutcode,
                     ARITHPCK_VALUE_TYPE *pinput, unsigned char *pincode)
{
 if (*poutcode<=1)
  return 0;
 while (!(*poutcode&ARITHPCK_CODEBIT))
  if (*poutcode<<=1,pinput!=NULL)
  {
   *pinput<<=1;
   if (*pincode&ARITHPCK_CODEBIT)
    ++*pinput;
   *pincode<<=1;
  }
 *poutcode<<=1;
 if (pinput!=NULL)
 {
  *pinput<<=1;
  if (*pincode&ARITHPCK_CODEBIT)
   ++*pinput;
  *pincode<<=1;
 }
 return 1;
}

void freqmodelstart(ARITHPCK_SYM_TYPE symtbl[],
                    ARITHPCK_FREQ_TYPE freqtbl[],
                    ARITHPCK_VALUE_TYPE *pmaxcum, ARITHPCK_SYM_TYPE maxsym)
{
 *pmaxcum=(ARITHPCK_VALUE_TYPE)maxsym;
 do freqtbl[symtbl[maxsym]=maxsym]=0;
  while (maxsym--);
}

void freqmodelupdate(ARITHPCK_SYM_TYPE symtbl[],
                     ARITHPCK_FREQ_TYPE freqtbl[],
                     ARITHPCK_VALUE_TYPE *pmaxcum, ARITHPCK_FREQ_TYPE scale,
                     ARITHPCK_SYM_TYPE index)
{
 register ARITHPCK_SYM_TYPE cur;
 register ARITHPCK_VALUE_TYPE oldmax;
 while (freqtbl[index]>(ARITHPCK_FREQ_TYPE)(ARITHPCK_FREQ_MAX-scale) ||
        (ARITHPCK_VALUE_TYPE)(*pmaxcum+(ARITHPCK_VALUE_TYPE)scale)<
        (ARITHPCK_VALUE_TYPE)scale)
 {
  if (freqtbl[index]<=0)
   return;
  for (cur=0,oldmax=*pmaxcum,*pmaxcum=0;
       oldmax>(ARITHPCK_VALUE_TYPE)*freqtbl;cur++,
       oldmax=(ARITHPCK_VALUE_TYPE)(oldmax-(ARITHPCK_VALUE_TYPE)*freqtbl-1),
       *pmaxcum=(ARITHPCK_VALUE_TYPE)(*pmaxcum+
                 (ARITHPCK_VALUE_TYPE)(*(freqtbl++)>>=1)));
  *pmaxcum=(ARITHPCK_VALUE_TYPE)(*pmaxcum+(ARITHPCK_VALUE_TYPE)(*freqtbl>>=1)+
                                 (ARITHPCK_VALUE_TYPE)cur);
  freqtbl-=cur;
 }
 *pmaxcum=(ARITHPCK_VALUE_TYPE)(*pmaxcum+(ARITHPCK_VALUE_TYPE)scale);
 for (cur=*(symtbl+=index),
      scale=(ARITHPCK_FREQ_TYPE)(*(freqtbl+=index)+scale);
      index>0;symtbl--,freqtbl--,index--)
  if (*(freqtbl-1)<scale)
  {
   *symtbl=*(symtbl-1);
   *freqtbl=*(freqtbl-1);
  }
   else break;
 *symtbl=cur;
 *freqtbl=scale;
}

ARITHPCK_SYM_TYPE freqmodelsearch(ARITHPCK_SYM_TYPE sym,
                                  ARITHPCK_SYM_TYPE symtbl[])
{
 register ARITHPCK_SYM_TYPE index;
 for (index=0;*symtbl!=sym;symtbl++,index++);
 return index;
}

void freqmodelgetcum(ARITHPCK_VALUE_TYPE *pcumlower,
                     ARITHPCK_VALUE_TYPE *pcumupper,
                     ARITHPCK_FREQ_TYPE freqtbl[], ARITHPCK_SYM_TYPE index)
{
 register ARITHPCK_VALUE_TYPE cum=(ARITHPCK_VALUE_TYPE)index;
 while ((index--)>0)
  cum=(ARITHPCK_VALUE_TYPE)((ARITHPCK_VALUE_TYPE)*(freqtbl++)+cum);
 *pcumupper=(ARITHPCK_VALUE_TYPE)((*pcumlower=cum)+
             (ARITHPCK_VALUE_TYPE)*freqtbl);
}

ARITHPCK_SYM_TYPE freqmodelindex(ARITHPCK_VALUE_TYPE *pcumlower,
                                 ARITHPCK_VALUE_TYPE *pcumupper,
                                 ARITHPCK_FREQ_TYPE freqtbl[])
{
 register ARITHPCK_SYM_TYPE index;
 register ARITHPCK_VALUE_TYPE cum;
 for (index=0,cum=*pcumlower;
      cum>(ARITHPCK_VALUE_TYPE)*freqtbl;freqtbl++,index++)
  cum=(ARITHPCK_VALUE_TYPE)(cum-
       (ARITHPCK_VALUE_TYPE)*freqtbl-(ARITHPCK_VALUE_TYPE)1);
 *pcumupper=(ARITHPCK_VALUE_TYPE)((*pcumlower=
             (ARITHPCK_VALUE_TYPE)(*pcumlower-cum))+
             (ARITHPCK_VALUE_TYPE)*freqtbl);
 return index;
}