Kumulative Komprimierung eines wachsenden Puffers (C++, ZLIB)

Question

Ich habe einen Puffer (Zeichenfolge), die im Laufe der Zeit wächst, und ich muss diesen Puffer über einen Kanal mit einer begrenzten Eingabegröße (4096 Bytes) senden. Die Kommunikation über diesen Kanal ist teuer, deshalb ist es besser komprimierte Daten zu senden. Das Wachsen des Puffers geschieht durch Blöcke unterschiedlicher Größe. Diese Blöcke können nicht geteilt werden oder die Bedeutung ist verloren.

Ich benutze zlib in C++ tatsächlich für die Komprimierung mit einem abilary Puffergrößenlimit. Wenn dieses Limit erreicht ist, wird die Zeichenfolge komprimiert und an den Kanal gesendet. Dies funktioniert, aber es ist nicht optimal, da das Limit eher niedrig ist, um Informationen nicht zu verlieren (Kanaleingabegrenze von 4096 Bytes).

Meine Idee ist es, mit zlib einen wachsenden komprimierten Puffer mit unterschiedlich großen Komprimierungsblöcken aufzubauen und den Prozess vor dem Erreichen der Kanaleingabegrenze zu stoppen. Erlaubt zlib das Arbeiten mit Kompressionsblöcken unterschiedlicher Größe oder brauche ich einen anderen Algorithmus?

Answer 1

Es ist mir gelungen, einen Kompressor zu entwickeln, der den wachsenden Puffer Teil für Teil durch den Kanal mit einer begrenzten Eingangsgröße sendet. Ich gebe hier die Antwort für jeden, der an dem gleichen Problem arbeitet. Thx zu Mark Adler und zu MSalters, um mich zum richtigen Weg zu führen.

class zStreamManager { 
    public: 
     zStreamManager(); 
     ~zStreamManager(); 
     void endStream(); 
     void addToStream(const void *inData, size_t inDataSize); 

    private: 
     // Size of base64 encoded is about 4*originalSize/3 + (3 to 6) 
     // so with maximum output size of 4096, 3050 max zipped out 
     // buffer will be fine 
     const size_t CHUNK_IN = 1024, CHUNK_OUT = 3050; 
     const std::string base64Chars = 
     "ABCDEFGHIJKLMNOPQRSTUVWXYZ" 
     "abcdefghijklmnopqrstuvwxyz" 
     "/"; 
     bool deallocated = true; 
     z_stream stream; 
     std::vector<uint8_t> outBuffer; 
     std::string base64Encode(std::vector<uint8_t> &str); 
}; 

zStreamManager::~zStreamManager() { 
    endStream(); 
} 

void zStreamManager::endStream() { 
    if(!deallocated) { 
     deallocated = true; 
     uint8_t tempBuffer[CHUNK_IN]; 
     int response = Z_OK; 
     unsigned int have; 

     while(response == Z_OK) { 
      if (stream.avail_out == 0) { 
       outBuffer.insert(outBuffer.end(), tempBuffer, tempBuffer + CHUNK_IN); 
       stream.next_out = tempBuffer; 
       stream.avail_out = CHUNK_IN; 
      } 
      response = deflate(&stream, Z_FINISH); 
     } 

     have = CHUNK_IN - stream.avail_out; 
     if(have) 
      outBuffer.insert(outBuffer.end(), tempBuffer, tempBuffer + have); 

     deflateEnd(&stream); 

     if(outBuffer.size()) 
      SEND << outBuffer << "$"; 
    } 
} 

void zStreamManager::addToStream(const void *inData, size_t inDataSize) { 
    if(deallocated) { 
     deallocated = false; 
     stream.zalloc = 0; 
     stream.zfree = 0; 
     stream.opaque = 0; 
     deflateInit(&stream, 9); 
    } 

    std::vector<uint8_t> tempBuffer(inDataSize); 
    unsigned int have; 

    stream.next_in = reinterpret_cast<uint8_t *>(const_cast<void*>(inData)); 
    stream.avail_in = inDataSize; 
    stream.next_out = &tempBuffer[0]; 
    stream.avail_out = inDataSize; 

    while (stream.avail_in != 0) { 
     deflate(&stream, Z_SYNC_FLUSH); 
     if (stream.avail_out == 0) { 
      outBuffer.insert(outBuffer.end(), tempBuffer.begin(), tempBuffer.begin() + inDataSize); 
      stream.next_out = &tempBuffer[0]; 
      stream.avail_out = inDataSize; 
     } 
    } 

    have = inDataSize - stream.avail_out; 
    if(have) 
     outBuffer.insert(outBuffer.end(), tempBuffer.begin(), tempBuffer.begin() + have); 

    while(outBuffer.size() >= CHUNK_OUT) { 
     std::vector<uint8_t> zipped; 

     zipped.insert(zipped.end(), outBuffer.begin(), outBuffer.begin() + CHUNK_OUT); 
     outBuffer.erase(outBuffer.begin(), outBuffer.begin() + CHUNK_OUT); 

     if(zipped.size()) 
      SEND << zipped << "|"; 
    } 
} 

std::string zStreamManager::base64Encode(std::vector<uint8_t> &str) { 
    /* ALTERED VERSION OF René Nyffenegger BASE64 CODE 
    Copyright (C) 2004-2008 René Nyffenegger 

    This source code is provided 'as-is', without any express or implied 
    warranty. In no event will the author be held liable for any damages 
    arising from the use of this software. 

    Permission is granted to anyone to use this software for any purpose, 
    including commercial applications, and to alter it and redistribute it 
    freely, subject to the following restrictions: 

    1. The origin of this source code must not be misrepresented; you must not 
     claim that you wrote the original source code. If you use this source code 
     in a product, an acknowledgment in the product documentation would be 
     appreciated but is not required. 

    2. Altered source versions must be plainly marked as such, and must not be 
     misrepresented as being the original source code. 

    3. This notice may not be removed or altered from any source distribution. 

    René Nyffenegger rene.nyffenegger@adp-gmbh.ch 
    */ 
    unsigned char const* bytes_to_encode = &str[0]; 
    unsigned int in_len = str.size(); 
    std::string ret; 
    int i = 0, j = 0; 
    unsigned char char_array_3[3], char_array_4[4]; 

    while(in_len--) { 
    char_array_3[i++] = *(bytes_to_encode++); 
    if (i == 3) { 
     char_array_4[0] = (char_array_3[0] & 0xfc) >> 2; 
     char_array_4[1] = ((char_array_3[0] & 0x03) << 4) + ((char_array_3[1] & 0xf0) >> 4); 
     char_array_4[2] = ((char_array_3[1] & 0x0f) << 2) + ((char_array_3[2] & 0xc0) >> 6); 
     char_array_4[3] = char_array_3[2] & 0x3f; 

     for(i = 0; (i <4) ; i++) 
     ret += base64Chars[char_array_4[i]]; 
     i = 0; 
    } 
    } 

    if(i) { 
    for(j = i; j < 3; j++) 
     char_array_3[j] = '\0'; 

    char_array_4[0] = (char_array_3[0] & 0xfc) >> 2; 
    char_array_4[1] = ((char_array_3[0] & 0x03) << 4) + ((char_array_3[1] & 0xf0) >> 4); 
    char_array_4[2] = ((char_array_3[1] & 0x0f) << 2) + ((char_array_3[2] & 0xc0) >> 6); 
    char_array_4[3] = char_array_3[2] & 0x3f; 

    for(j = 0; (j < i + 1); j++) 
     ret += base64Chars[char_array_4[j]]; 

    while((i++ < 3)) 
     ret += '='; 
    } 

    return ret; 
} 

Ein Anwendungsfall:

zStreamManager zm; 
string growingBuffer = ""; 
bool somethingToSend = true; 

while(somethingToSend) { 
    RECEIVE(&growingBuffer); 
    if(growingBuffer.size()) { 
    zm.addToStream(growingBuffer.c_str(), growingBuffer.size()); 
    growingBuffer.clear(); 
    } else { 
    somethingToSend = false; 
    } 
} 

zm.endStream(); 

Mit RECEIVE und SEND, den verwendeten Methoden für den Puffer zu empfangen und es über den Kanal zu senden. Zum Dekomprimieren wird jeder Teil durch das '|' Zeichen und das Ende des gesamten Puffers wird durch '$' begrenzt. Jeder Teil muss base64 decodiert und dann verkettet werden. Letztendlich kann es mit zlib wie alle anderen komprimierten Daten dekomprimiert werden.

Answer 2

Die einfachste Lösung besteht darin, die Out-of-Band-Paketbeschreibung in ein In-Band-Format umzuwandeln. Bei weitem der einfachste Weg, dies zu tun, ist, wenn Ihre Eingangsblöcke nicht alle 256 möglichen Bytes verwenden. Z.B. Wenn der Wert 00 nicht in Blöcken auftritt, kann er verwendet werden, um Blöcke vor der Komprimierung zu trennen. Andernfalls benötigen Sie einen Escape-Code.

In beiden Fällen komprimieren Sie den kontinuierlichen Strom mit Blocktrennzeichen. Auf der Empfängerseite dekomprimieren Sie den Stream, erkennen die Separatoren und bauen die Blöcke wieder zusammen.

Answer 3

Sie können einfach eine kontinuierliche Zlib-Komprimierung durchführen und Daten auf Ihrem Kanal senden, sobald 4K komprimierte Daten generiert wurden. Auf der anderen Seite müssen Sie sicherstellen, dass der Dekomprimierer die 4K-Blöcke komprimierter Daten in der richtigen Reihenfolge erhält.

Der Deflate-Algorithmus in zlib ist stoßweise und akkumuliert interne Daten in der Größenordnung von 16 KB bis 64 KB oder mehr, bevor komprimierte Daten ausgegeben werden. Anschließend wird ein Block komprimierter Daten ausgegeben und dann erneut akkumuliert. Es wird also eine Latenz geben, es sei denn, Sie fordern die Deflate-Flush-Daten an. Sie können kleinere Blöcke durch Spülen mit geringen Auswirkungen auf die Komprimierung verwenden, wenn Sie die Latenz verringern möchten.