zrle

Compress zeros using Run Length Encoding
git clone https://noulin.net/git/zrle.git
Log | Files | Refs | LICENSE

commit 66589683f26a2619859ad6755953a9c27334b5fe
parent f7e79b73f0c225d9447e990d320f8a9b81046b97
Author: Remy Noulin <loader2x@gmail.com>
Date:   Sun, 20 May 2018 10:52:17 +0200

zrle library

package.yml |  17 +++++
test.c      |  36 ++++++++++
zrle.c      | 219 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
zrle.h      |  14 ++++
4 files changed, 286 insertions(+)

Diffstat:
Apackage.yml | 17+++++++++++++++++
Atest.c | 36++++++++++++++++++++++++++++++++++++
Azrle.c | 219+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Azrle.h | 14++++++++++++++
4 files changed, 286 insertions(+), 0 deletions(-)

diff --git a/package.yml b/package.yml @@ -0,0 +1,17 @@ +--- + name: zrle + version: 0.0.3 + description: "Compress zeros using Run Length Encoding" + bin: ./zrle.c + cflags: -O3 -std=gnu11 -fPIC -pipe + #lflags: -lpcre + repository: + type: git + url: git+https://github.com/RemyNoulin/zrle.git + keywords: + - utility + author: Remy Noulin + license: MIT + bugs: + url: https://github.com/RemyNoulin/zrle/issues + homepage: https://github.com/RemyNoulin/zrle#readme diff --git a/test.c b/test.c @@ -0,0 +1,36 @@ +#! /usr/bin/env sheepy +/* or direct path to sheepy: #! /usr/local/bin/sheepy */ + +#include "libsheepyObject.h" +#include "zrle.h" + +int argc; char **argv; + +uint8_t data[] = {0x00, 0x00, 0x00, 0x1, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x1, 0x00, 0x00, 0x00, 0x00, 0x1, 0xfe, 0xfd, 0xfc, 0}; + +int main(int ARGC, char** ARGV) { + + argc = ARGC; argv = ARGV; + + initLibsheepy(argv[0]); + + puts("C template"); + + logVarG(COUNT_ELEMENTS(data)); + loghex(data, COUNT_ELEMENTS(data)); + put + + zrlebuft b = zrle(data, COUNT_ELEMENTS(data)); + + if (b.buf) { + put + logVarG(b.count); + loghex(b.buf, b.count); + + put + zrlebuft buf = dezrle(b.buf, b.count); + loghex(buf.buf, buf.count); + + free(b.buf); + } +} diff --git a/zrle.c b/zrle.c @@ -0,0 +1,219 @@ + +#include "libsheepyObject.h" +#include "zrle.h" + +zrlebuft zrle(void *buf, size_t len) { + zrlebuft r; + + // allocate compressed buffer, twice bigger than b + // initialize state + // copy bytes + // replace anchors with 0xfc+anchor + // copy + // zero is found, count zeros + // check for buffer overflow, error when overflow + // zero is found again, count zeros + // check if the zero count exceeds the max count (0xfb) + // zero count exceeded max, write 0xfc 0xfb in compressed buffer and start a new zero count + // non zero is found + // when count is less 3, write 0 in compressed buffer + // when count is 3, write 0xfe in compressed buffer + // when count is 7, write 0xfd in compressed buffer + // write 0xfc zcount-4 in compressed buffer + // copy byte + // when state is ZCOUNT at the end, write last zero string + // realloc to fit compress buffer size to data + + if (!buf || len < 3) { + // buffer too small + r.buf = NULL; + return r; + } + + u8 *b = buf; + + // allocate compressed buffer, twice bigger than b + // (compressed buffer should be smaller than source) + r.buf = malloc(len*2); + + // initialize state + enum {COPY, ZCOUNT}; + u8 state = COPY; + + // offset of first zero in b in current zero string + u32 src; + // offset in compressed buffer + u32 dst = 0; + // zero count in current zero string + u8 zcount; + range(i, len) { + if (state == ZCOUNT) { + if (!b[i]) { + // zero is found again, count zeros + zcount++; + // check if the zero count exceeds the max count (0xfb) + if (zcount-4 == 0xfc) { + // zero count exceeded max, write 0xfc 0xfb in compressed buffer and start a new zero count + r.buf[dst++] = 0xfc; + r.buf[dst++] = 0xfb; + zcount = 1; + } + goto next; + } + else { + // when count is less 3, write 0 in compressed buffer + if (zcount < 3) + range(j, zcount) + r.buf[dst++] = 0; + // when count is 3, write 0xfe in compressed buffer + else if (zcount == 3) + r.buf[dst++] = 0xfe; + // when count is 7, write 0xfd in compressed buffer + else if (zcount == 7) + r.buf[dst++] = 0xfd; + // write 0xfc zcount-4 in compressed buffer + else { + r.buf[dst++] = 0xfc; + r.buf[dst++] = zcount-4; + } + // copy byte + r.buf[dst++] = b[i]; + state = COPY; + goto next; + } + } + if (state == COPY) { + // copy bytes + if (b[i]) { + switch (b[i]) { + case 0xfe: + case 0xfd: + case 0xfc: + // replace anchors with 0xfc+anchor + r.buf[dst++] = 0xfc; + r.buf[dst++] = b[i]; + break; + default: + // copy + r.buf[dst++] = b[i]; + } + } + else { + // zero is found, count zeros + zcount = 1; + src = i; + state = ZCOUNT; + } + } + + next: + // check for buffer overflow + if (dst > 2*len-2) { + // end of buffer - stop error + free(r.buf); + r.buf = NULL; + break; + } + } + + // when state is ZCOUNT at the end, write last zero string + if (state == ZCOUNT) { + // when count is less 3, write 0 in compressed buffer + if (zcount < 3) + range(j, zcount) + r.buf[dst++] = 0; + // when count is 3, write 0xfe in compressed buffer + else if (zcount == 3) + r.buf[dst++] = 0xfe; + // when count is 7, write 0xfd in compressed buffer + else if (zcount == 7) + r.buf[dst++] = 0xfd; + // write 0xfc zcount-4 in compressed buffer + else { + r.buf[dst++] = 0xfc; + r.buf[dst++] = zcount-4; + } + } + + r.count = dst; + // realloc to fit compress buffer size to data + r.buf = realloc(r.buf, dst); + + return r; +} + +zrlebuft dezrle(void *buf, size_t len) { + zrlebuft r; + + // initialize state + // not an anchor, copy byte + // expand anchors + // reallocate when there is buffer overflow + // when count >= 0xfc, copy count as a byte + // check for buffer overflow when expanding + // realloc to fit buffer size to data + + // initialize state + u8 *b = buf; + r.buf = malloc(len*2); + u32 blen = len*2; + u32 dst = 0; + enum {COPY, EXPAND}; + u8 state = COPY; + + range(i, len) { + // expand anchors + if (state == EXPAND) { + // when count >= 0xfc, copy count as a byte + if (b[i] >= 0xfc) + r.buf[dst++] = b[i]; + else { + // check for buffer overflow when expanding + if (dst+(u16)(b[i])+4 >= blen) { + r.buf = realloc(r.buf, 2*blen + (u16)(b[i])+4); + blen = 2*blen + (u16)(b[i])+4; + } + range(j, (u16)(b[i])+4) + r.buf[dst++] = 0; + } + state = COPY; + goto next; + } + // not an anchor, copy byte + if ((b[i] != 0xfe) and (b[i] != 0xfd) and (b[i] != 0xfc)) { + r.buf[dst++] = b[i]; + } + // expand anchors + if (b[i] == 0xfe) { + if (dst+3 >= blen) { + r.buf = realloc(r.buf, 2*blen + 3); + blen = 2*blen + 3; + } + range(j, 3) + r.buf[dst++] = 0; + } + if (b[i] == 0xfd) { + if (dst+7 >= blen) { + r.buf = realloc(r.buf, 2*blen + 7); + blen = 2*blen + 7; + } + range(j, 7) + r.buf[dst++] = 0; + } + if (b[i] == 0xfc) { + state = EXPAND; + } + next: + // reallocate when there is buffer overflow + if (dst >= blen) { + r.buf = realloc(r.buf, 2*blen); + blen = 2*blen; + } + } + + r.count = dst; + // realloc to fit buffer size to data + r.buf = realloc(r.buf, dst); + + return r; +} diff --git a/zrle.h b/zrle.h @@ -0,0 +1,14 @@ + +#include "libsheepyObject.h" + +typedef struct { + u8 *buf; + u32 count; +} zrlebuft; + +#define bufZRLE(zlreb) zlreb.buf +#define lenZRLE(zlreb) zlreb.count +#define freeZRLE(zlreb) free(zlreb.buf) + +zrlebuft zrle(void *buf, size_t len); +zrlebuft dezrle(void *buf, size_t len);