fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <stddef.h>
  4. #include <string.h>
  5. #include <setjmp.h>
  6.  
  7. typedef unsigned int   uint;
  8. typedef unsigned char  byte;
  9. typedef unsigned long long int qword;
  10.  
  11. #ifdef __GNUC__
  12.  #define NOINLINE __attribute__((noinline))
  13.  #include <unistd.h>
  14.  #define chsize ftruncate
  15.  uint flen( FILE* f ) { fseek(f,0,SEEK_END); uint len=ftell(f); fseek(f,0,SEEK_SET); return len; }
  16. #else
  17.  #define NOINLINE __declspec(noinline)
  18.  #include <io.h>
  19.  #define flen(f) filelength(fileno(f))
  20. #endif
  21.  
  22. enum{ STKPAD=1<<16 };
  23. struct coroutine {
  24.   volatile int state;
  25.   volatile byte *inpptr, *inpbeg, *inpend, *outptr, *outbeg, *outend;
  26.   jmp_buf PointA, PointB;
  27.   void yield( int value ) { if( setjmp(PointB)==0 ) { state=value; longjmp(PointA,value); } }
  28.   void chkinp( void ) { if( inpptr>=inpend ) yield(1), inpptr=*&inpptr; }
  29.   void chkout( void ) { if( outptr>=outend ) yield(2); }
  30.   template <int f> byte get( void ) { if( f ) chkinp(); return *inpptr++; }
  31.   template <int f> void put( uint c ) { *outptr++ = c; if( f ) chkout(); }
  32.   void coro_init( void ) { inpptr=inpbeg=inpend=0; outptr=outbeg=outend=0; state=0; }
  33.   void addinp( byte* inp,uint inplen ) { inpbeg=inpptr=inp; inpend=&inp[inplen]; }
  34.   void addout( byte* out,uint outlen ) { outbeg=outptr=out; outend=&out[outlen]; }
  35.   template <typename T> NOINLINE void call_do_process() {
  36.     byte stktmp[STKPAD]; state=ptrdiff_t(stktmp); ((T*)this)->do_process();
  37.   }
  38.   template <typename T> int coro_process( T* ) {
  39.     if( setjmp(PointA)==0 ) if( state ) longjmp(PointB,3); else call_do_process<T>();
  40.     return state;
  41.   }
  42. };
  43.  
  44. struct Rangecoder_SH1x : coroutine {
  45.   enum { SCALElog=15, SCALE=1<<SCALElog };
  46.   enum { NUM=4, sTOP=0x01000000U, Thres=0xFF000000U };
  47.   uint f_decode; // 0=encode, 1=decode;
  48.   uint range, Cache, FFNum;
  49.   union {
  50.     struct { uint low; uint Carry; };
  51.     qword lowc;
  52.     uint  code; 
  53.   };
  54.   uint rc_BProcess( uint freq, uint bit ) { 
  55.     uint rnew = (range>>SCALElog)*freq;
  56.     if( f_decode ) bit = (code>=rnew);
  57.     range = ((range-rnew-rnew)&(-bit)) + rnew;
  58.     rnew &= -bit;
  59.     if( f_decode ) code-=rnew; else lowc+=rnew;
  60.     if( f_decode ) while( range<sTOP ) range<<=8, (code<<=8)+=get<1>();
  61.     else while( range<sTOP ) range<<=8, ShiftLow();
  62.     return bit;
  63.   }
  64.   void ShiftLow( void ) {
  65.     if( low<Thres || Carry ) {
  66.       put<1>( Cache+Carry );
  67.       for(; FFNum!=0; FFNum-- ) put<1>( Carry-1 );
  68.       Cache=low>>24; Carry=0;
  69.     } else FFNum++;
  70.     low<<=8;
  71.   }
  72.   void rc_Init( int DECODE ) {
  73.     f_decode=DECODE; range=-1; lowc=FFNum=Cache=0;
  74.     if( f_decode ) for(int _=0; _<NUM; _++) (code<<=8)+=get<1>(); 
  75.   }
  76. };
  77.  
  78. struct Model : Rangecoder_SH1x {
  79.   uint DECODE, f_quit;
  80.   enum{ lCNUM=8, CNUM=1<<lCNUM, ROWSIZE=80 };
  81.   uint count[2*CNUM];
  82.   enum{ inpbufsize=1<<21, outbufsize=1<<12 };
  83.   byte inpbuf[inpbufsize], outbuf[outbufsize];
  84.  
  85.   void Init( const char* s ) {
  86.     uint i,j;
  87.     uint (&p)[CNUM] = (uint(&)[CNUM])count[CNUM];
  88.     for( i=0; i<2*CNUM; i++) count[i]=0;
  89.     for( i=0; s[i]; i++ ) p[byte(s[i])]++;
  90.     for( j=0; j<lCNUM; j++ ) for( i=(CNUM>>j); i<((CNUM+CNUM)>>j); i++ ) count[i>>1] += count[i];
  91.     for( i=1; i<CNUM; i++ ) {
  92.       uint c0=count[i*2+0], c1=count[i*2+1];
  93.       count[i]=(c0+c1)?c0*SCALE/(c0+c1):0;
  94.     }
  95.   }
  96.  
  97.   void do_process( void ) {
  98.     uint i,j;
  99.     rc_Init(1-DECODE);
  100.     for( i=0; !f_quit; i++ ) {
  101.       uint c=0, ctx=1;
  102.       if( DECODE ) do c=get<1>(); while( c==10 );
  103.       for( j=lCNUM-1; j!=-1; j-- ) {
  104.         const uint freq = count[ctx];
  105.         ctx += ctx + ((freq==0) ? 1 : (freq==SCALE) ? 0 : rc_BProcess(freq,(c>>j)&1));
  106.       }
  107.       if( !DECODE ) put<1>(ctx), (((i+1)%ROWSIZE==0)?put<1>(10),0:0);
  108.     }
  109.     yield(0);
  110.   }
  111.  
  112.   void ProcessFile( uint Mode, FILE* f, FILE* g ) {
  113.     volatile uint r; volatile qword g_len=0; uint f_len=0;
  114.     DECODE=Mode; f_quit=0;
  115.     if( DECODE ) addout( (byte*)&g_len, sizeof(f_len)+1 ), r=1;
  116.     else f_len=flen(f), addinp( (byte*)&f_len, sizeof(f_len) ),addout(0,0), r=2;
  117.     do {
  118.       if( r==1 ) {
  119.         uint l = fread( inpbuf, 1, inpbufsize, f );
  120.         if( l>0 ) {
  121.           addinp( inpbuf, l );
  122.         } else {
  123.           if( inpbeg==inpbuf+1 ) f_quit=1;
  124.           memset( inpbuf, 0x80, inpbufsize );
  125.           addinp( inpbuf+1, 5 ); 
  126.         }
  127.       } else if( r==2 ) {
  128.         if( outbeg==outbuf ) fwrite( outbuf, 1, outptr-outbeg, g ); else g_len>>=8;
  129.         addout( outbuf, outbufsize );
  130.       }
  131.       r = coro_process(this); 
  132.     } while(r);
  133.     fwrite( outbuf, 1,outptr-outbuf, g ); // flush
  134.     if( DECODE==0 ) fputc( 10, g ); else fflush(g), chsize( fileno(g), g_len );
  135.   }
  136.  
  137. } M;
  138.  
  139. int main( int argc, char** argv ) {
  140.   //if( argc<4 ) return 1;
  141.   int DECODE = 0; //argv[1][0]=='d';
  142.   FILE* f = stdin; //fopen( argv[2], "rb" ); if( f==0 ) return 2;
  143.   FILE* g = stdout; //fopen( argv[3], "wb" ); if( g==0 ) return 3;
  144.   M.Init( "ABCDEFGHIJKLMNOPQRSTUVWXYZ" );
  145.   M.ProcessFile( DECODE, f, g );
  146.   return 0;
  147. }
  148.  
Success #stdin #stdout 0s 5528KB
comments (?)
stdin
copy 
HDADGABHAEABABEAEGEDEBHEGEAEDEAEABBBEBEHHEGFEHEB EBEDEAEEAEHABDBGEBGADAEDAHFEFAHFEHACEHBDGDABAAHDHE EDDBBABBBGGEHAHCAFAEAGABHADABABAAAFHAGABACAGBBBAFA BBAGECFEBEFAEBEBEHEBEGEHEDEBBHGABCCAGAFAECEADGDABG EABAHDGBDBEGEABDAHGGBAEEEAABADEEBAHCFFEEFCABBHHACB HDFBDBDBEEGHCFBACBCEAGAEBBEGEBEFEBEEEBEBHBDAHEBAEB FCGEABBHABHBGBABAABAHBAEGHHAFFCAFCCAHHDAHHBCFBDADA BADABACAGAFADAEAEAEAABABDBABBHABFBABFHHHFBEBA
stdout
copy 
OQHHJMBHDLOVPCJIPAKAPTKBHUOBNJTDDNRNLRBPVSZYTPKPVQFNAJPBEFELYGELWVZBYGWYLDFGQDCN
KXVKISSDZOCCDJQVFIOTTMVSXPPHCBRJQDXRGPDBBLCKMUJHZYVWLZIDSURKHLXHPUAKJBDAKDBYAJVD
CQGKHURDIBZJRETOJMWZIMZHUMFAAOWSEGTWUXGRDBNSQKVCSOWFKMJTSBGNOBTPUCSUHCTEQZKOAHKJ
YKQYRQGNIVLSJSHIXDOMJAVIKANLSXAXHEQVTHIEGKBEKVHRASVUBXSUMDFXVWJEWSVTSBDNEGUWFNUR
RAGNNTEZISLJPVIVOZRXLQIORTFTOJEMHXDRLZFLWNBGFQYZTANSJNCNAEUKKFPKCSGNOAWSEUQYZSDQ
MIWURKURHHCCRCKZAHOOEAWUCRBAEPNQXRQDCGBPEBXAMRYIYEQHXFKJMOSVWEGPLJSLVQRBIRJARWGL
CWKLWYXZMCAWLEZLCXNKBEZJMBMGDUTGYWCEXNFBHZSUJHSDBRQDXDTTKSHEENKOJRGKIWRVQRTPEIVF
XMFSZSYJBXVSNJGQIHWHYHJRSTDOZDUXXTHUBMIWLQEAQDWPKATAPTLWHCWCLQGOBTFDVBFNQULSYPBP
LRBLPNHYQSKQJXATIDCSSSCWTKRQZLOLZAMUFCEXQGOMHXVNMKA
https://ideone.com/HZ9q6R
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!