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

C/C++

Sziasztok,

32 bites mikrochip-en akarok bzip2-vel tömöríteni. Sima zip-re találtam kódot, de annál nagyobb tömörítése kell, ezért a bzip2. Előbbi kb. 37%-ra nyomja le az adatot, utóbbi 16%. Előbbi <2 MB residens mem-et használ futáshoz, utóbbi <8 MB.

Egyetlen szál C forrás fájlt keresek, amelyhez nem kell külön header fájl vagy egyéb lib. Zip-hez van egy ilyen, egy ilyesmit keresek bzip2-hez:

https://paste.ubuntu.com/26539770/

Ötlet? Kösz.

( log69 | 2018. 02. 08., cs – 09:02 )

Vagy tudnátok-e ajánlani bzip2 helyett valamit, ami beágyazott eszközre van és jobban tömörít? Köszi.

Egyébként megnéztem sok tömörítőt (zpaq, lrzip, xz, zstd stb), de az adat típusomra bzip2 tömörít a legjobban és nagyságrenddel kevesebb memória kell neki.

Ez jó kérdés, lehet hogy nem. 8 MB rezidens mem használatot mértem --best opcióval bzip2-nél, nekem fél megám lesz úgy néz ki, ezért az is kérdés hogy tudom-e limitálni a memória erőforrást a betömörítésnél.

Más algo-t találtam sokat ahol lehet limitálni, sőt pár byte-on túl nem is kell, de azoknál a fenti 1/3 rátájú tömörítés van. Ennél jobban össze akarom nyomni az adatot.

Az adat átalakításával is kísérleteztem, de maradtak az arányok.

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.

( tbs v | 2018. 02. 16., p – 14:27 )

Megneznem a libszl-t (haproxy low memory footprint tomoritoje), hatha.

Szep a forrasa, piszkosul nem ker ramot, es hangyanyival tomorit benabban.

( plt | 2024. 11. 29., p – 07:44 )

Megkérdezhetem, mi lett a vége? Én is hasonló helyzetben vagyok, bár nekem kitömöríteni kellene. A micro-bunzip.c kódot próbáltam, de irdatlan mennyiségű RAM kell neki, így elvetettem. Lett jobb a zip/gzip-nél?

( bzt | 2024. 11. 29., p – 10:17 )

zip/gzip-re egyszem fejlécfájl (egyáltalán nem foglal memóriát): inflate.h (működik zlib headerrel és gzip headerrel is, portolhatósághoz csak a "pb_*" hívásokat kell kivenni az "uncompress()" függvényből).

Egyébként a gyári bzip2 miért nem jó? Ha nagyon akarod, berámolhatod a forrását egyetlen fájlba, simán működik. "cat *.h *.c >bzip2lib.c", aztán szövegszerkesztővel az include-okat kitörlöd, kész.

Ami még esélyes lehet, xz embedded. Ezt használja a Linux is, ez is csak a contexthez foglal memóriát, a kitömörített bufferhez nem (tehát a memóriafoglalása konstans, nem függ az adattól).

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.