Bzip2 forrásfájl beágyazott eszközhöz

https://catchchallenger.first-world.info/wiki/Quick_Benchmark:_Gzip_vs_…

Időd az van? (vagy a betömörítésnek gyorsnak is kell lennie, mert mondjuk akkuról megy az eszköz)

Tömörítendő adatok titkosak? Nem lehetne feltenni valahova? Lehet hogy egy tömörebb adatstruktúrát kellene kialakítani. Például bzip2 bwt-t használ a könnyebb tömöríthetőség miatt, nálad lehet az segít.

+1 :D

Tanulj meg olvasni. "Én is hasonló helyzetben vagyok, bár nekem kitömöríteni kellene."

Egyébként meg az összes általam linkelt megoldás rendelkezik betömörítő párral is, csak hát kattintani meg olvasni luxus ugye?
- https://github.com/pfalcon/uzlib/blob/master/examples/tgzip/tgzip.c
- bzip2-nél eleve *.h, *.c volt
- https://github.com/tukaani-project/xz

Egyébként nem értem, minek ezen pörögni, memóriaallokációmentes, zlib API kompatíbilis, inflate/deflate kb 150 SLoC:

/*** gzip inflate ***/

typedef struct { uint32_t b, c, t; uint8_t *s, *d; uint16_t e[16], f[288], g[16], h[288]; } zlib_z_t;
static void zlib_bt(uint16_t *t, uint16_t *r, const uint8_t *l, uint32_t n) {
    uint32_t i, s, o[16]; for(i = 0; i < 16; i++) { t[i] = 0; } for(i = 0; i < n; i++) t[(uint32_t)l[i]]++;
    for(s = 0, i = 0, t[0] = 0; i < 16; i++) { o[i] = s; s += t[i]; } for(i = 0; i < n; i++) if(l[i]) r[o[(uint32_t)l[i]]++] = i; }
static int zlib_gb(zlib_z_t *d) { uint32_t b; if(!d->b--) { d->t = *d->s++; d->b = 7; } b = d->t & 1; d->t >>= 1; return b; }
static uint32_t zlib_rb(zlib_z_t *d, uint32_t n, uint32_t b) {
    uint32_t v = 0, m, l; if(n) { l = 1 << n; for(m = 1; m < l; m <<= 1) if(zlib_gb(d)) v += m; } return v + b; }
static int zlib_ds(zlib_z_t *d, uint16_t *t, uint16_t *r) {
    int s = 0, c = 0, l = 0; do { c = (c << 1) + zlib_gb(d); s += t[++l]; c -= t[l]; } while(c >= 0); return r[s + c]; }
uint16_t m[30] = {3,4,5,6,7,8,9,10,11,13,15,17,19,23,27,31,35,43,51,59,67,83,99,115,131,163,195,227,258}, n[30] = {1,2,3,4,
    5,7,9,13,17,25,33,49,65,97,129,193,257,385,513,769,1025,1537,2049,3073,4097,6145,8193,12289,16385,24577};
uint8_t k[288+32], c[] = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15};
zlib_z_t d;

int uncompress(uint8_t *in, uint8_t *out, uint32_t siz)
{
    uint32_t i, l, x, y, z;
    uint8_t p;
    int r = 2, s, t = -1, f = 0, o = 0;

    if(!in || !out || in[0] != 0x1f) return 0;
    memset(&d, 0, sizeof(d));
    in += 3;
    p = *in++; in += 6;
    if(p & 4) { i = *in++; i += (*in++ << 8); in += i; }
    if(p & 8) { while(*in++ != 0); }
    if(p & 16) { while(*in++ != 0); }
    if(p & 2) in += 2;
    d.s = in; d.d = out;
    do {
        do {
            if(t == -1) {
again:          f = zlib_gb(&d);
                t = zlib_rb(&d, 2, 0);
                switch(t) {
                    case 1:
                        for(i = 0; i < 7; i++) d.e[i] = 0;
                        d.e[7] = 24; d.e[8] = 152; d.e[9] = 112;
                        for(i = 0; i < 24; i++) d.f[i] = 256 + i;
                        for(i = 0; i < 144; i++) d.f[24 + i] = i;
                        for(i = 0; i < 8; i++) d.f[24 + 144 + i] = 280 + i;
                        for(i = 0; i < 112; i++) d.f[24 + 144 + 8 + i] = 144 + i;
                        for(i = 0; i < 5; i++) d.g[i] = 0;
                        for(i = 0, d.g[5] = 32; i < 32; i++) d.h[i] = i;
                    break;
                    case 2:
                        x = zlib_rb(&d, 5, 257); y = zlib_rb(&d, 5, 1); z = zlib_rb(&d, 4, 4);
                        for(i = 0; i < 19; i++) k[i] = 0;
                        for(i = 0; i < z; i++) k[c[i]] = zlib_rb(&d, 3, 0);
                        zlib_bt(d.e, d.f, k, 19);
                        for(i = 0; i < x + y;)
                            switch((s = zlib_ds(&d, d.e, d.f))) {
                                case 16: for(p = k[i - 1], l = zlib_rb(&d, 2, 3); l; l--) k[i++] = p; break;
                                case 17: for(l = zlib_rb(&d, 3, 3); l; l--) k[i++] = 0; break;
                                case 18: for(l = zlib_rb(&d, 7, 11); l; l--) k[i++] = 0; break;
                                default: k[i++] = s; break;
                            }
                        zlib_bt(d.e, d.f, k, x); zlib_bt(d.g, d.h, k + x, y);
                    break;
                }
            }
            switch(t) {
                case 0:
                    if(!d.c) { d.c = 1 + (d.s[0] | (d.s[1] << 8)); d.s += 4; d.b = 0; }
                    if(!--d.c) r = 1; else { *d.d++ = *d.s++; r = 0; }
                break;
                case 1: case 2:
                    if(!d.c) {
                        s = zlib_ds(&d, d.e, d.f);
                        if(s < 256) { *d.d++ = s; r = 0; break; } else if(s == 256) { r = 1; break; }
                        s -= 257; d.c = zlib_rb(&d, s < 4 || s > 27 ? 0 : ((s - 4) >> 2), m[s]);
                        r = zlib_ds(&d, d.g, d.h); o = -zlib_rb(&d, r < 2 || r > 29 ? 0 : ((r - 2) >> 1), n[r]);
                    }
                    d.d[0] = d.d[o]; d.d++; d.c--; r = 0;
                    break;
                default: return 0;
            }
            if(r == 1 && !f) goto again;
            if(r) break;
        } while(--siz);
    } while(!r);
    return r;
}

/*** gzip deflate ***/

#define HASH_BITS 12
#define HASH_SIZE (1<<HASH_BITS)
#define MIN_MATCH 3
#define MAX_MATCH 258
#define MAX_OFFSET 32768
#define TO_Lc(x, y) x - 3, y - 3
#define FROM_Lc(x) (x + 3)

typedef struct { uint8_t e; uint8_t min, max; } zlib_c_t;
typedef struct { uint8_t c, e; uint16_t min, max; } zlib_d_t;
uint8_t *zlib_h[HASH_SIZE];
static const uint8_t mb[256] = {0x00,0x80,0x40,0xc0,0x20,0xa0,0x60,0xe0,0x10,0x90,0x50,0xd0,0x30,0xb0,0x70,0xf0,0x08,0x88,0x48,0xc8,
  0x28,0xa8,0x68,0xe8,0x18,0x98,0x58,0xd8,0x38,0xb8,0x78,0xf8,0x04,0x84,0x44,0xc4,0x24,0xa4,0x64,0xe4,0x14,0x94,0x54,0xd4,0x34,0xb4,
  0x74,0xf4,0x0c,0x8c,0x4c,0xcc,0x2c,0xac,0x6c,0xec,0x1c,0x9c,0x5c,0xdc,0x3c,0xbc,0x7c,0xfc,0x02,0x82,0x42,0xc2,0x22,0xa2,0x62,0xe2,
  0x12,0x92,0x52,0xd2,0x32,0xb2,0x72,0xf2,0x0a,0x8a,0x4a,0xca,0x2a,0xaa,0x6a,0xea,0x1a,0x9a,0x5a,0xda,0x3a,0xba,0x7a,0xfa,0x06,0x86,
  0x46,0xc6,0x26,0xa6,0x66,0xe6,0x16,0x96,0x56,0xd6,0x36,0xb6,0x76,0xf6,0x0e,0x8e,0x4e,0xce,0x2e,0xae,0x6e,0xee,0x1e,0x9e,0x5e,0xde,
  0x3e,0xbe,0x7e,0xfe,0x01,0x81,0x41,0xc1,0x21,0xa1,0x61,0xe1,0x11,0x91,0x51,0xd1,0x31,0xb1,0x71,0xf1,0x09,0x89,0x49,0xc9,0x29,0xa9,
  0x69,0xe9,0x19,0x99,0x59,0xd9,0x39,0xb9,0x79,0xf9,0x05,0x85,0x45,0xc5,0x25,0xa5,0x65,0xe5,0x15,0x95,0x55,0xd5,0x35,0xb5,0x75,0xf5,
  0x0d,0x8d,0x4d,0xcd,0x2d,0xad,0x6d,0xed,0x1d,0x9d,0x5d,0xdd,0x3d,0xbd,0x7d,0xfd,0x03,0x83,0x43,0xc3,0x23,0xa3,0x63,0xe3,0x13,0x93,
  0x53,0xd3,0x33,0xb3,0x73,0xf3,0x0b,0x8b,0x4b,0xcb,0x2b,0xab,0x6b,0xeb,0x1b,0x9b,0x5b,0xdb,0x3b,0xbb,0x7b,0xfb,0x07,0x87,0x47,0xc7,
  0x27,0xa7,0x67,0xe7,0x17,0x97,0x57,0xd7,0x37,0xb7,0x77,0xf7,0x0f,0x8f,0x4f,0xcf,0x2f,0xaf,0x6f,0xef,0x1f,0x9f,0x5f,0xdf,0x3f,0xbf,
  0x7f,0xff};
static const zlib_c_t lc[] = { {0,TO_Lc(3,3)},{0,TO_Lc(4,4)},{0,TO_Lc(5,5)},{0,TO_Lc(6,6)},{0,TO_Lc(7,7)},{0,TO_Lc(8,8)},
  {0,TO_Lc(9,9)},{0,TO_Lc(10,10)},{1,TO_Lc(11,12)},{1,TO_Lc(13,14)},{1,TO_Lc(15,16)},{1,TO_Lc(17,18)},{2,TO_Lc(19,22)},
  {2,TO_Lc(23,26)},{2,TO_Lc(27,30)},{2,TO_Lc(31,34)},{3,TO_Lc(35,42)},{3,TO_Lc(43,50)},{3,TO_Lc(51,58)},{3,TO_Lc(59,66)},
  {4,TO_Lc(67,82)},{4,TO_Lc(83,98)},{4,TO_Lc(99,114)},{4,TO_Lc(115,130)},{5,TO_Lc(131,162)},{5,TO_Lc(163,194)},{5,TO_Lc(195,226)},
  {5,TO_Lc(227,257)},{0,TO_Lc(258,258)}};
static const zlib_d_t dc[] = { {0,0,1,1},{1,0,2,2},{2,0,3,3},{3,0,4,4},{4,1,5,6},{5,1,7,8},{6,2,9,12},{7,2,13,16},{8,3,17,24},
  {9,3,25,32},{10,4,33,48},{11,4,49,64},{12,5,65,96},{13,5,97,128},{14,6,129,192},{15,6,193,256},{16,7,257,384},{17,7,385,512},
  {18,8,513,768},{19,8,769,1024},{20,9,1025,1536},{21,9,1537,2048},{22,10,2049,3072},{23,10,3073,4096},{24,11,4097,6144},
  {25,11,6145,8192},{26,12,8193,12288},{27,12,12289,16384},{28,13,16385,24576},{29,13,24577,32768}};
void zlib_o(uint32_t b, int n) { d.b|=b<<d.c; d.c+=n; while(d.c >= 8){ d.d[d.t++] = (uint8_t)(d.b & 0xFF); d.b >>= 8; d.c -= 8; } }

uint32_t compressBound(uint32_t len) { return len + (len >> 12) + (len >> 14) + (len >> 25) + 13 + 18; }
uint32_t compress(uint8_t *in, uint8_t *out, uint32_t siz)
{
    const zlib_d_t *r;
    const zlib_c_t *l;
    const uint8_t *t = in + siz - MIN_MATCH;
    const uint8_t *q;
    uint32_t crc = crc32_calc(in, siz);
    uint8_t **b, *s, c;
    int i, j, k, m, n, o, p, h;

    memset(&d, 0, sizeof(d)); memset(out, 0, 10);
    d.d = out + 10; out[0] = 0x1f; out[1] = 0x8b; out[2] = 8; out[9] = 3;
    zlib_o(1, 1); zlib_o(1, 2);
    while(in < t) {
        h = (in[0] << 16) | (in[1] << 8) | in[2]; h = ((h >> (3*8 - HASH_BITS)) - h) & (HASH_SIZE - 1);
        b = &zlib_h[h & (HASH_SIZE - 1)]; s = *b; *b = in;
        if(s && in > s && (in - s) <= MAX_OFFSET && !memcmp(in, s, MIN_MATCH)) {
            for(in += MIN_MATCH, q = s + MIN_MATCH, o = MIN_MATCH; *in == *q && o < MAX_MATCH && in < t; in++, q++, o++);
            p = in - o - s;
            while(o > 0) {
                m = (o > 260 ? 258 : o <= 258 ? o : o - 3); o -= m; i = -1; j = sizeof(lc) / sizeof(*lc);
                while(1) {
                    k = (j + i) / 2;
                    if(m < FROM_Lc(lc[k].min)) j = k; else if(m > FROM_Lc(lc[k].max)) i = k; else { l = &lc[k]; break; }
                }
                n = l - lc + 257;
                if(n <= 279) zlib_o(mb[(n - 256) * 2], 7); else zlib_o(mb[0xc0 - 280 + n], 8);
                if (l->e) zlib_o(m - FROM_Lc(l->min), l->e);
                i = -1; j = sizeof(dc) / sizeof(*dc);
                while(1) {
                    k = (j + i) / 2;
                    if(p < dc[k].min) j = k; else if (p > dc[k].max) i = k; else { r = &dc[k]; break; }
                }
                zlib_o(mb[r->c * 8], 5);
                if(r->e) zlib_o(p - r->min, r->e);
            }
        } else { c = *in++; if(c <= 143) zlib_o(mb[0x30 + c], 8); else zlib_o(1 + 2 * mb[0x90 - 144 + c], 9); }
    }
    t += MIN_MATCH;
    while(in < t) { c = *in++; if(c <= 143) zlib_o(mb[0x30 + c], 8); else zlib_o(1 + 2 * mb[0x90 - 144 + c], 9); }
    zlib_o(0, 7); zlib_o(0, 7);
    *((uint32_t*)&d.d[d.t]) = crc;
    *((uint32_t*)&d.d[d.t + 4]) = siz;
    return d.t + 18;
}

Nem túl gyors, de tökéletesen működik és nem foglal memóriát.

Nincsenek csodák, vagy memóriallokációmentes és nem túl tömörített, vagy jól tömörített de RAM igényes. Lehet választani, olyan sosem lesz, hogy nem foglal memóriát de nagyon jól tömörít.
Ha meg még az is feltétel, hogy kímélje az akksit, akkor végképp el kell felejteni minden számolásigényes (jó tömörítési rátájú) algoritmust.

Par projekthez haszntaltam ezt az mdeflate nevu projektet. Majdnem olyan jo mint a gzip (par %-kal kevesbe hatekony), de a kitotomoriteshez fix memoriamerettel tudsz szamolni (en ugy hasznalom hogy 7k kelljen neki - mert ennyi van - de ez allithato). 

Megnéztem ezt az xz-embedded kódot, és tényleg jónak tűnik. Azonban Arduino környezetben egyetlen felhasználását sem találtam. Arduino libet sem csináltak még belőle. Nem biztos, hogy elég profi vagyok ahhoz, hogy nekem sikerüljön. Már a micro-bunzip is csak úgy fordult le, hogy lib helyett csak a c fájlt tudtam a projektbe tenni. Amúgy maga az xz tényleg nagyon jó. Az én adataimon kb fele akkora tömörített fájlt eredményez, mint a gzip.

Persze, hogy a bzip2 jobban tömörít. Az lzma/lzma2/xz még jobban, az zpaq annál is jobban, a paq8 még jobban, és ezeket is veri a cmix, csak ugye nem Arduinora valók. Sőt, még ezeknél is van durvább, de az ott kezdődik, hogy RTX3090, RTX4090 szintű GPU-kon futtatod. Lehetni mindent lehet, kérdés milyen áron, belefér-e a hardvernek, megéri-e.