C++でRange Coder(桁上がりなし)

・高速な算術圧縮を実現する「Range Coder」

https://codezine.jp/article/detail/443

・Algorithms with Python レンジコーダ(range coder)[2]

http://www.nct9.ne.jp/m_hiroi/light/pyalgo37.html

を参考にC++でプログラミングしてみました。

テストをあまりしていないですし、圧縮率も調べてないですが参考までに載せます。

range_coder.hpp

range_coder.cpp

encoder.cpp

decoder.cpp

の4つのプログラムを載せます。

// range_coder.hpp

#pragma once

#include<iostream>
#include<fstream>
#include<vector>
#include<string>

using uint = unsigned int;
using byte = unsigned char;
using filename = std::string;

class RangeCoder{
private:
    uint low;
    std::vector<byte> lows;
    uint lows_count;
    uint code;
    std::vector<byte> codes;
    uint codes_count;
    uint range;
    uint total;

    filename inputfilename;
    filename outputfilename;
    std::ifstream ifs;
    std::ofstream ofs;
    std::vector<byte> words;
    uint digit_start[0x100] = {0};
    uint digit_size[0x100] = {0};

    const uint max_range = 0xffffffff;
    const uint min_range = 0x00010000;
    const uint mask = 0xffffffff;
    const uint mask1 = 0xff000000;
    const uint shift = 24;

    void initializeEncoder();
    void runEncoder();
    void encode(uint start, uint size);
    void encode_normalize();

    void initializeDecoder();
    void runDecoder();
    void decode();
    void decode_normalize();

public:
    RangeCoder(filename inputfile, filename outputfile, bool encode);
};

// range_coder.cpp

#include"range_coder.hpp"

RangeCoder::RangeCoder(filename inputfile, filename outputfile, bool encode){
    inputfilename = inputfile;
    outputfilename = outputfile;

    ifs.open(inputfilename, std::ios::in | std::ios::binary);
    if(!ifs){
        std::cout << "can not open a inputfile." << std::endl;
        exit(0);
    }
    
    ofs.open(outputfilename, std::ios::out | std::ios::binary);
    if(!ofs){
        std::cout << "can not open a outputfile." << std::endl;
        exit(0);
    }
    
    if(encode){
        byte buffer;
        do{
            ifs.read( (char*)&buffer, sizeof(byte));
            words.push_back(buffer);
            ++digit_size[buffer];
            //std::cout << (unsigned short)buffer << std::endl;
        }while(!ifs.eof());
        
        runEncoder();
        // totalを出力ファイルへ埋め込む
        ofs.write( (char*)(&total), sizeof(uint));
        // digit_sizeを出力ファイルへ埋め込む
        for(uint i = 0; i < 0x100; ++i){
            ofs.write( (char*)(&digit_size[i]), sizeof(uint));
        }
        // lowsを出力ファイルへ埋め込む
        ofs.write( (char*)(&lows_count), sizeof(uint));
        //std::cout << lows_count << std::endl;
        for(uint i = 0; i < lows_count; ++i){
            ofs.write( (char*)(&lows[i]), sizeof(byte));
        }

        //std::cout << total << std::endl;

        // テスト用
        /*
        for(uint i = 0; i < 0x100; ++i){
            std::cout << i << " " << digit_start[i] << " " << digit_size[i] << std::endl;
        }*/
        //　テスト用
        /*
        for(uint i = 0; i < static_cast<uint>(word.size()); ++i){
            ofs.write( (char*)(&word[i]), sizeof(byte));
        }*/
    }else{
        ifs.read( (char*)&total, sizeof(uint));
        //std::cout << total << std::endl;
        for(uint i = 0; i < 0x100; ++i){
            ifs.read( (char*)(&digit_size[i]), sizeof(uint));
        }
        // lowsをcodesとして入力する
        ifs.read( (char*)&lows_count, sizeof(uint));
        //std::cout << lows_count << std::endl;
        codes.assign(lows_count, 0);
        for(uint i = 0; i < lows_count; ++i){
            ifs.read( (char*)(&codes[i]), sizeof(byte));
        }
        runDecoder();
        for(uint i = 0; i < total; ++i){
            ofs.write( (char*)(&words[i]), sizeof(byte));
        }
        
        //std::cout << total << std::endl;
        //　テスト用
        /*
        for(uint i = 0; i < 0x100; ++i){
            std::cout << i << " " << digit_start[i] << " " << digit_size[i] << std::endl;
        }*/
    }
}
void RangeCoder::initializeEncoder(){
    low = 0;
    range = max_range;
    total = words.size() - 1;
    lows_count = 0;
    for(uint i = 0; i < 0x100; ++i){
        digit_start[i] = digit_size[i];
    }
    for(uint i = 0; i < 0x100-1u; ++i){
        digit_start[i+1] += digit_start[i];
        digit_start[i] -= digit_size[i];
    }
}
void RangeCoder::runEncoder(){
    initializeEncoder();
    for(uint i = 0; i < total; ++i){
        encode(digit_start[words[i]], digit_size[words[i]]);
    }
    //std::cout << low << std::endl;
    lows.push_back( (byte)( (low >> 24) & 0xff));
    ++lows_count;
    lows.push_back( (byte)( (low >> 16) & 0xff));
    ++lows_count;
    lows.push_back( (byte)( (low >> 8) & 0xff));
    ++lows_count;
    lows.push_back( (byte)(low & 0xff));
    ++lows_count;

}
void RangeCoder::encode(uint start, uint size){
    uint unit = range / total;
    low = low + start * unit;
    range = size * unit;
    encode_normalize();
}
void RangeCoder::encode_normalize(){
    while( (low & mask1) == ( (low + range) & mask1)){
        lows.push_back( (byte)(low >> shift));
        ++lows_count;
        low = (low << 8) & mask;
        range <<= 8;
    }
    while(range < min_range){
        range = (min_range - (low & (min_range-1))) << 8;
        lows.push_back( (byte)(low >> shift));
        ++lows_count;
        low = (low << 8) & mask;
    }
}

void RangeCoder::initializeDecoder(){
    low = 0;
    range = max_range;
    codes_count = 0;

    code = codes[codes_count];
    ++codes_count;
    code = (code << 8) + codes[codes_count];
    ++codes_count;
    code = (code << 8) + codes[codes_count];
    ++codes_count;
    code = (code << 8) + codes[codes_count];
    ++codes_count;
    
    //std::cout << code << std::endl;
    
    for(uint i = 0; i < 0x100; ++i){
        digit_start[i] = digit_size[i];
    }
    for(uint i = 0; i < 0x100-1u; ++i){
        digit_start[i+1] += digit_start[i];
        digit_start[i] -= digit_size[i];
    }
}
void RangeCoder::runDecoder(){
    //std::cout << "test message runDecoder in." << std::endl;
    initializeDecoder();
    for(uint i = 0; i < total; ++i){
        decode();
    }
}
void RangeCoder::decode(){
    uint unit = range / total;
    uint value = (code - low) / unit;
    byte word;
    
    for(byte i = 0; i <= 0xff; ++i){
        if(digit_start[i] <= value && value < digit_start[i]+digit_size[i]){
            word = i;
            break;
        }
    }
    words.push_back(word);
    low = low + digit_start[word] * unit;
    range = digit_size[word] * unit;
    decode_normalize();
}
void RangeCoder::decode_normalize(){
    while( (low & mask1) == ( (low + range) & mask1)){
        code = ( (code << 8) & mask) + codes[codes_count];
        ++codes_count;
        low = (low << 8) & mask;
        range <<= 8;
    }
    while(range < min_range){
        range = (min_range - (low & (min_range-1))) << 8;
        code = ( (code << 8) & mask) + codes[codes_count];
        ++codes_count;
        low = (low << 8) & mask;
    }
}

// encoder.cpp

#include<iostream>
#include"range_coder.hpp"

using namespace std;

int main(int argc, char *argv){
    if(argc != 2){
        return 0;
    }
    filename inputfile(argv[1]);
    filename outputfile = inputfile + ".rc";
    RangeCoder* rc = new RangeCoder(inputfile, outputfile, true);
    delete rc;

    return 0;
}

// decoder.cpp

#include<iostream>
#include"range_coder.hpp"

using namespace std;

int main(int argc, char *argv){
    if(argc != 2){
        return 0;
    }
    filename inputfile(argv[1]);
    filename outputfile(argv[1], inputfile.size()-3);
    RangeCoder* rc = new RangeCoder(inputfile, outputfile, false);
    delete rc;

    return 0;
}