#include <cstdio>

#include <string>
#include <iostream>
using namespace std;

typedef unsigned char uint8;
typedef unsigned short uint16;
typedef unsigned int uint32;
typedef unsigned long long uint64;

void CompressorRAnsFastCmp(uint8* orgBb,int orgSize,uint32* counters,uint8* cmpBb,int& cmpSize){
    const int totFreqBits=12;
    const int totFreq=1<<totFreqBits;
    int cumFreqs[256]={};
    for(int code=0;code<255;code++)
        cumFreqs[code+1]=cumFreqs[code]+counters[code];

    cmpSize=0;
    uint64 x=0x100000000;

    for(int i=orgSize-1;i>=0;i--){
        int code=orgBb[i];
        uint32 freq=counters[code];
        uint32 cumFreq=cumFreqs[code];

        uint64 xNext=(x>>32);
        xNext=xNext/freq*totFreq+xNext%freq+cumFreq;
        if(xNext>=((1L<<32))){
            *((uint32*)(cmpBb+cmpSize))=x;
            cmpSize+=4;
            x=xNext;
        }
        else{
            x=x/freq*totFreq+x%freq+cumFreq;
        }
    }

    *((uint64*)(cmpBb+cmpSize))=x;
    cmpSize+=8;
}


void CompressorRAnsFastDcm(uint8* cmpBb,int cmpSize,int orgSize,uint32* counters,uint8* dcmBb,int& dcmSize){
    const int totFreqBits=12;

    uint64_t xFreqToData[(1L<<totFreqBits)]={};
    for(int cumFreqsIndex=0, symb=0, cumFreq=counters[symb]; cumFreqsIndex<(1L<<totFreqBits); )
        if(cumFreqsIndex>=cumFreq){
            cumFreq+=counters[++symb];
        }else{
            xFreqToData[cumFreqsIndex]|=(uint64_t)symb<<16;
            xFreqToData[cumFreqsIndex]|=(uint64_t)(cumFreqsIndex-(cumFreq-counters[symb]))<<32;
            xFreqToData[cumFreqsIndex]|=(uint64_t)counters[symb];
            cumFreqsIndex++;
        }

    uint8_t* dcmBbCur=(uint8_t*)dcmBb;
    uint8_t* dcmBbEnd=(uint8_t*)(dcmBb+orgSize);
    uint32_t* cmpBbCur=(uint32_t*)(cmpBb+cmpSize)-1;
    uint64_t x=(((uint64_t)*cmpBbCur--)<<32)|*cmpBbCur--;

    while(dcmBbCur<dcmBbEnd){
        if( x<(1L<<32) ) x=(x<<32)+*cmpBbCur--;
        uint64_t d=xFreqToData[x&((1L<<totFreqBits)-1)];
        x=(x>>totFreqBits)*(uint16_t)(d)+(d>>32);
        *dcmBbCur++=d>>16;
    }

    dcmSize=orgSize;
}