/* * @(#) arithpck.c - Arithmetic encode/decode operations library (source). * (c) 1998 Ivan Maidanski 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 /* NULL */ #include /* 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)>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=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>=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)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; }