C++17及更早版本的实时字符串压缩

8dtrkrch  于 11个月前  发布在  其他
关注(0)|答案(2)|浏览(111)

我有一个应用程序,它使用了长串重复字符的字符串。我想将它们以压缩/混淆的形式添加到二进制文件中。为了简单起见,我目前使用的是修改后的RLE算法。
我使用的是下面的算法,它适用于C20。不幸的是,现在我不得不支持C17,以及出于商业原因。我目前的解决方案为C17是把字符串在一个YAML文件,并生成相应的.cpp“压缩”文件在构建时,然后链接到进程。
做了一些研究,我发现this solution与霍夫曼,但只支持C
20(及以上)。
我也见过this solution,但“压缩”数据与原始数据大小相同。
所以问题是我如何用C++17重写下面的算法?

#include <cstdint>
#include <algorithm>
#include <iostream>
#include <array>
#include <span>
#include <sstream>

struct Array {
    const char* data;
    std::size_t size;
};

constexpr std::size_t compress( const char* data, std::size_t size, char* buf ) {
        if ( size==0 ) return 0;
        std::size_t offset = 0;
        char lastch = *data;
        std::size_t counter = 0;
        auto push = [&]() {
            if ( counter <= 3 ) {
                for ( int j=0; j<counter; ++j ) buf[offset++] = lastch;
            }
            else {
                buf[offset++] = 0;
                buf[offset++] = lastch;
                buf[offset++] = counter;
            }
            counter = 0;
        };
        lastch = data[0];
        counter = 1;
        for ( std::size_t j=1; j<size; ++j ) {
            if ( (data[j]!=lastch) || (counter==255) ) {
                push(); 
                lastch = data[j];
            }
            counter++;
        }
        push();        
        return offset;
}

template< std::size_t N > 
struct RawContainer {
    char raw_data[N];
    constexpr RawContainer( const char (&s)[N] ) {
        std::copy(s,s+N,raw_data);
    }
    constexpr operator const char* () const noexcept {
        return data;
    }
    constexpr auto data() const noexcept {
        return raw_data;
    }
    constexpr auto size() const noexcept {
        return N;
    }
};

template< auto Container >
struct StringCompressor {
    StringCompressor() noexcept {
        compress(Container.data(),Container.size(),compressed_data.data());
    }
    constexpr static auto build_size() noexcept {
        char out[Container.size()*3];
        return compress(Container.data(),Container.size(),out);
    }
    std::string str() noexcept {
        std::ostringstream out;
        out << compressed_data.size() << ": ";
        for ( std::size_t j=0; j<compressed_data.size(); ++j ) {
            out << (int)compressed_data[j] << " ";
        }
        return out.str();
    }
    std::array<char,build_size()> compressed_data;
};

template<RawContainer str>
constexpr StringCompressor<str> operator ""_x() noexcept
{
    return StringCompressor<str>();
}


auto value = "aaaabbbbbbbbbbbbbbbbbbbc"_x;

int main() {
    std::cout << value.str() << std::endl;
}

字符串
Godbolt:https://godbolt.org/z/Eh9fMxW75

:为简单起见,未包含解压缩算法。

g52tjvyc

g52tjvyc1#

Here是我的版本。compress函数是从你的代码中复制的,没有任何变化,其余的是从我的评论中提取的,做了一些小修改。用法很简单:

COMPRESSED_LITERAL("aaaabbbbbbbbbbbbbc")

字符串
正如您所看到的,原始字符串和压缩代码都不会在生成的对象中留下任何痕迹。
我没有实现str(),因为压缩的字符串在生成的程序集中是可见的。我让压缩和未压缩的版本都输出到std::cout,只是为了并排比较生成的程序集,尽管压缩的版本当然不会输出任何东西,因为在开始时嵌入了零。
我能想到的唯一缺点是你需要使用宏。

niwlg2el

niwlg2el2#

我可能有一个C++17的例子here,它的额外好处是它不存储二进制中的字符串字面量。我检查了相当长的参数(汇编程序中第35行的字符串是压缩结果)。
与你的代码不同,字符串字面量用于初始化一个constexpr数组或指针变量,然后将其馈送到一个简化的压缩器类。大小必须单独计算。这是每个字符串更多的代码,但仍然,字面量只出现一次。看起来它可以很容易地生成。
调用端看起来像这样:

constexpr const char p[] = "aaaabbbbbbbbbbbbbbbbbbbc";
        constexpr std::size_t comprSz = compress(p, sizeof(p), nullptr);
        constexpr Compressor<comprSz> cpr{p, sizeof(p)};
        print(cpr.comprData, comprSz);

字符串
可以将大小计算转移到另一个中间类中,但无论出于何种原因,似乎不可能使用普通字符串字面量作为模板参数,以便调用可以是单个语句,就像使用用户字面量一样。

相关问题