arith.cpp

来自「zlib-1.2.3.tar是新的zlib库藏 用于压缩 等等」· C++ 代码 · 共 236 行

/*   Multiply-free Arithmetic Coding Implementation - Compression version 0.0.0
 
 
     Copyright Feb. 1993
              
     Gordon V. Cormack  Feb. 1993
     University of Waterloo
     [e-mail]
 
 
     All rights reserved.
 
     This code and the algorithms herein are the property of Gordon V. Cormack.
 
     Neither the code nor any algorithm herein may be included in any software,
     device, or process which is sold, exchanged for profit, or for which a 
     licence or royalty fee is charged.
 
     Permission is granted to use this code for educational, research, or
     commercial purposes, provided this notice is included, and provided this
     code is not used as described in the above paragraph.
 
*/
 
/* 
     This code uses a one-byte finite state predictor to drive an arithmetic
     coder for data compression.  It should give compression nearly identical
     to one-byte huffman coding.
 
     Find a better predictor, and you'll have a better compressor!

     It uses no floating point, no multiplies, no divides during compression.

     ***EOF is handled in a non-general way; (char)EOF is stuffed into the
     compressed stream.
 
*/

/* JC [06/01/2000] Encoding/decoding routines enclosed in arith_encode/decode
 *                 Converted to ANSI C++
 *                 C getchar/write_byte -> ComprLib read_byte/write_byte
 *
 * JC = Jeff Connelly <[e-mail]>
 */

 /* TODO: merge arithshifte.c + arithshiftc.c */

#include "codec.h"

#define THRESH 0

#include <stdio.h>

int diff[0x10000];

int inc0tab [0x10000];
int inc1tab [0x10000];

int cnt[0x100];


#define INC0(x) inc0tab[(unsigned int)(x)]
#define INC1(x) inc1tab[(unsigned int)(x)]
#define DIFF(x) diff[(unsigned int)(x)]
#define CNT1(x) ((x&0xff)+1)
#define CNT0(x) ((x>>8)+1)

int init() {
   int i,j;
   for (i=0;i<256;i++) for (j=0;j<256;j++) {
     if (i != 255)
        inc0tab[(i<<8)+j] = ((i+1)<<8) + j;
     else
        inc0tab[(i<<8)+j] = (127<<8) + (j>>1);
     if (j != 255)
        inc1tab[(i<<8)+j] = (i<<8) + j + 1;
     else
        inc1tab[(i<<8)+j] = ((i>>1)<<8) + 127;
     if (i < j) {
        diff[(i<<8)+j] = 175 * (i+1) / (i+j+2);
        if (!diff[(i<<8)+j]) diff[(i<<8)+j]++;
     }else{
        diff[(i<<8)+j] = -175 * (j+1) / (i+j+2);
        if (!diff[(i<<8)+j]) diff[(i<<8)+j]--;
     }
   }
   return 0;
}


/* main(){ */
int encode_arith()
{

register int *pinc0tab, *pinc1tab, *pdiff;


register int space = 0xff,
    min = 0,
   index;
unsigned register char c = 0;

unsigned register int last = 0;
register int count = -24;

init();

pinc0tab = inc0tab;
pinc1tab = inc1tab;
pdiff = diff;

do{
   register int mask;

   c = 0xff & read_byte();
   index = 1;
   for (mask = 0x80;mask;mask>>=1){
         register int l = last  + index;
         register int a = cnt[l];
         register int x = DIFF(a);
         if (x>0) 
            if (c & mask) { 
               space -=x;
               cnt[l] = INC1(a);
               index += index + 1;
            }else { 
               min += space-x;
               space = x;
               cnt[l] = INC0(a);
               index += index;
            }
         else 
            if (!(c & mask)) {
               space +=x; 
               cnt[l] = INC0(a);
               index += index;
            } else { 
              min += space+x; 
              space = -x;
              cnt[l] = INC1(a);
              index += index+1;
            }
      while ((space) < 128) {
         space <<= 1;
         min <<= 1;
         if (!++count) {
            count = -8;
            write_byte(min >> 24);
            min &= 0xffffff;
            if (0xffffff - min < space){
                space = 0xffffff - min;
                }
            }
         }
      }
   }
while (c != (unsigned char)EOF);
/* fprintf(stderr,"count %d min %x minshift %x\n",count&7,min,min<<(8-(count&0x7))); */
min <<= 8-(count&7);
write_byte(min>>24);
write_byte((min>>16) & 0xff);
write_byte((min>>8) & 0xff);
write_byte(min & 0x00ff);
return 0;
}

int decode_arith()
{
register int count = -8;
unsigned register int mask;
register int space = 0xff,
    min = 0,
   index;
unsigned register char c=0,gc = 0;
unsigned register int last = 0;
unsigned register int val;

init();

val = read_byte();
gc = read_byte();

do{
   c = 0;
   index = 1;
   for(mask=0x80;mask;mask>>=1){
         register int l = last  + index;
         register int a = cnt[l];
         register int x = DIFF(a);
         if (x>0) 
            if ((unsigned)val < (unsigned)min+space-x) {
               c |= mask;
               space -=x;
               cnt[l] = INC1(a);
               index += index + 1;
            }else { 
               min += space-x;
               space = x;
               cnt[l] = INC0(a);
               index += index;
            }
         else 
            if ((unsigned)val < (unsigned)min+space+x) {
               space +=x; 
               cnt[l] = INC0(a);
               index += index;
            } else { 
               c |= mask;
              min += space+x; 
              space = -x;
              cnt[l] = INC1(a);
              index += index+1;
            }
      while ((space) < 128) {
         space <<= 1;
         min <<= 1;
         val = (val<<1) | (gc>>(7-(count&7)));
         if (!++count) {
            count = -8;
            gc = read_byte();
            min &= 0xffffff;
            val &= 0xffffff;
            if (0xffffff - min < space){
                space = 0xffffff - min;
                }
            }
         }
      }
   if (c == (unsigned char)EOF) break;
   write_byte(c);
   }
while (1);
   return 0;
}