ref: e81c54ba2ecc673a4d5f8aed0e9b52841fe07b0d
dir: /utils/sqz/sqz.c/
#include <lib9.h> #include <a.out.h> #include "squeeze.h" /* * forsyth@vitanuova.com */ typedef struct Word Word; struct Word { ulong v; ushort freq; ushort code; Word* next; }; typedef struct Squeeze Squeeze; struct Squeeze { int n; /*union {*/ ulong tab[7*256]; Word* rep[7*256]; /*};*/ }; enum { HMASK = 0xFFFF, HSIZE = HMASK+1, Codebufsize = 3*1024*1024 }; #define GET4(p) (((((((p)[0]<<8)|(p)[1])<<8)|(p)[2])<<8)|(p)[3]) #define GET4L(p) (((((((p)[3]<<8)|(p)[2])<<8)|(p)[1])<<8)|(p)[0]) #define PUT4(p,v) (((p)[0]=(v)>>24),((p)[1]=(v)>>16),((p)[2]=(v)>>8),((p)[3]=(v))) static uchar prog[Codebufsize]; static uchar outbuf[Codebufsize]; static Word* hash1[HSIZE]; static Word* hash2[HSIZE]; static Sqhdr sqhdr; static ulong chksum; static int dflag; /* squeeze data, not text */ static int tflag; /* squeeze text, leave data as-is */ static int qflag = 1; /* enable powerpc option */ static int wflag; /* write output */ static int islittle; /* object code uses little-endian byte order */ static int debug; static char* fname; static void analyse(ulong*, int, Squeeze*, Squeeze*, Word**); static Word** collate(Word**, int); static void dumpsq(Squeeze*, int); static void freehash(Word**); static long Read(int, void*, long); static void remap(Squeeze*); static int squeeze(ulong*, int, uchar*, ulong); static int squeezetab(int, int, Squeeze*, Word**, int); static void squirt(int, Squeeze*); static void Write(int, void*, long); static void usage(void) { fprint(2, "Usage: sqz [-w] [-t] [-d] [-q] q.out\n"); exits("usage"); } void main(int argc, char **argv) { int fd, n, ns, nst, nsd; long txtlen, datlen, asis; ulong topdat, toptxt; Exec ex; Squeeze sq3, sq4, sq5, sq6; Word *top; setbinmode(); /* fmtinstall('f', gfltconv); */ ARGBEGIN{ case 'D': debug++; break; case 'd': dflag++; break; case 'q': qflag = 0; break; case 't': tflag++; break; case 'w': wflag++; break; default: usage(); }ARGEND fname = *argv; if(fname == nil) usage(); fd = open(fname, OREAD); if(fd < 0){ fprint(2, "sqz: can't open %s: %r\n", fname); exits("open"); } Read(fd, &ex, sizeof(Exec)); txtlen = GET4((uchar*)&ex.text); datlen = GET4((uchar*)&ex.data); switch(GET4((uchar*)&ex.magic)){ case Q_MAGIC: /* powerpc */ islittle = 0; break; case E_MAGIC: /* arm */ islittle = 1; qflag = 0; break; case 0xA0E1: /* arm AIF */ islittle = 1; qflag = 0; txtlen = GET4L((uchar*)&ex+(5*4))-sizeof(Exec); datlen = GET4L((uchar*)&ex+(6*4)); break; default: fprint(2, "sqz: unknown magic for sqz: %8.8ux\n", GET4((uchar*)&ex.magic)); exits("bad magic"); } if(qflag) fprint(2, "PowerPC rules\n"); if(islittle) fprint(2, "Little endian\n"); if(txtlen > sizeof(prog) || datlen > sizeof(prog) || txtlen+datlen > sizeof(prog)){ fprint(2, "sqz: executable too big: %lud+%lud; increase Codebufsize in sqz.c\n", txtlen, datlen); exits("size"); } if(dflag){ seek(fd, txtlen, 1); Read(fd, prog, datlen); }else{ Read(fd, prog, txtlen); Read(fd, prog+txtlen, datlen); } close(fd); asis = 0; if(dflag) n = datlen; else if(tflag){ n = txtlen; asis = datlen; }else n = txtlen+datlen; if(dflag || tflag){ analyse((ulong*)prog, n/4, &sq3, &sq4, &top); nst = squeeze((ulong*)prog, n/4, outbuf, top->v); if(nst < 0) exits("sqz"); nsd = 0; remap(&sq3); remap(&sq4); toptxt = topdat = top->v; }else{ analyse((ulong*)prog, txtlen/4, &sq3, &sq4, &top); nst = squeeze((ulong*)prog, txtlen/4, outbuf, top->v); if(nst < 0) exits("sqz"); toptxt = top->v; remap(&sq3); remap(&sq4); if(datlen/4){ freehash(hash1); freehash(hash2); analyse((ulong*)(prog+txtlen), datlen/4, &sq5, &sq6, &top); nsd = squeeze((ulong*)(prog+txtlen), datlen/4, outbuf+nst, top->v); if(nsd < 0) exits("sqz"); topdat = top->v; remap(&sq5); remap(&sq6); }else{ nsd = 0; topdat = 0; } } ns = nst+nsd; fprint(2, "%d/%d bytes\n", ns, n); fprint(2, "%8.8lux csum\n", chksum); if(!wflag) exits(0); PUT4(sqhdr.magic, SQMAGIC); PUT4(sqhdr.toptxt, toptxt); PUT4(sqhdr.sum, chksum); PUT4(sqhdr.text, nst); PUT4(sqhdr.topdat, topdat); PUT4(sqhdr.data, nsd); PUT4(sqhdr.asis, asis); PUT4(sqhdr.flags, 0); Write(1, &sqhdr, SQHDRLEN); Write(1, &ex, sizeof(Exec)); squirt(1, &sq3); squirt(1, &sq4); Write(1, outbuf, nst); if(nsd){ squirt(1, &sq5); squirt(1, &sq6); Write(1, outbuf+nst, nsd); } if(asis) Write(1, prog+txtlen, asis); exits(0); } static void analyse(ulong *prog, int nw, Squeeze *sq3, Squeeze *sq4, Word **top) { Word *w, **hp, **sorts, **resorts; ulong *rp, *ep; ulong v; int i, nv1, nv2, nv, nz; rp = prog; ep = prog+nw; nv = 0; nz = 0; while(rp < ep){ if(islittle){ v = GET4L((uchar*)rp); }else{ v = GET4((uchar*)rp); } rp++; chksum += v; if(v == 0){ nz++; if(0) continue; } if(qflag){ QREMAP(v); } for(hp = &hash1[v&HMASK]; (w = *hp) != nil; hp = &w->next) if(w->v == v) break; if(w == nil){ w = (Word*)malloc(sizeof(*w)); w->v = v; w->freq = 0; w->code = 0; w->next = nil; *hp = w; nv++; } w->freq++; } sorts = collate(hash1, nv); fprint(2, "phase 1: %d/%d words (%d zero), %d top (%8.8lux)\n", nv, nw, nz, sorts[0]->freq, sorts[0]->v); *top = sorts[0]; nv1 = squeezetab(1, 0x900, sq3, sorts+1, nv-1)+1; nv2 = 0; for(i=nv1; i<nv; i++){ v = sorts[i]->v >> 8; for(hp = &hash2[v&HMASK]; (w = *hp) != nil; hp = &w->next) if(w->v == v) break; if(w == nil){ w = (Word*)malloc(sizeof(*w)); w->v = v; w->freq = 0; w->code = 0; w->next = nil; *hp = w; nv2++; } w->freq++; } free(sorts); resorts = collate(hash2, nv2); fprint(2, "phase 2: %d/%d\n", nv2, nv-nv1); squeezetab(2, 0x200, sq4, resorts, nv2); free(resorts); fprint(2, "phase 3: 1 4-code, %d 12-codes, %d 20-codes, %d uncoded\n", sq3->n, sq4->n, nv-(sq3->n+sq4->n+1)); } static int wdcmp(void *a, void *b) { return (*(Word**)b)->freq - (*(Word**)a)->freq; } static Word ** collate(Word **tab, int nv) { Word *w, **hp, **sorts; int i; sorts = (Word**)malloc(nv*sizeof(Word**)); i = 0; for(hp = &tab[0]; hp < &tab[HSIZE]; hp++) for(w = *hp; w != nil; w = w->next) sorts[i++] = w; qsort(sorts, nv, sizeof(*sorts), wdcmp); if(debug > 1) for(i=0; i<nv; i++) fprint(2, "%d\t%d\t%8.8lux\n", i, sorts[i]->freq, sorts[i]->v); return sorts; } static int tabcmp(void *a, void *b) { ulong av, bv; av = (*(Word**)a)->v; bv = (*(Word**)b)->v; if(av > bv) return 1; if(av < bv) return -1; return 0; } static int squeezetab(int tabno, int base, Squeeze *sq, Word **sorts, int nv) { int i; if(nv >= 7*256) nv = 7*256; memset(sq, 0, sizeof(*sq)); for(i=0; i<nv; i++) sq->rep[sq->n++] = sorts[i]; qsort(sq->rep, sq->n, sizeof(*sq->rep), tabcmp); for(i=0; i<sq->n; i++) sq->rep[i]->code = base + i; if(debug) dumpsq(sq, tabno); return sq->n; } static void dumpsq(Squeeze *sq, int n) { int i; fprint(2, "table %d: %d entries\n", n, sq->n); for(i=0; i<sq->n; i++) fprint(2, "%.3x\t%8.8lux\t%lux\n", sq->rep[i]->code, sq->rep[i]->v, i? sq->rep[i]->v - sq->rep[i-1]->v: 0); } static void remap(Squeeze *sq) { int i; ulong v; if(sq->n){ v = 0; for(i=0; i<sq->n; i++){ sq->tab[i] = sq->rep[i]->v - v; v += sq->tab[i]; } } } static Word * squash(Word **tab, ulong v) { Word *w, **hp; for(hp = &tab[v&0xFFFF]; (w = *hp) != nil; hp = &w->next) if(w->v == v) return w; return nil; } static void freehash(Word **tab) { Word *w, **hp; for(hp = &tab[0]; hp < &tab[HSIZE]; hp++) while((w = *hp) != nil){ *hp = w->next; free(w); } } static int squeeze(ulong *prog, int nw, uchar *out, ulong top) { ulong *rp, *ep; ulong v, bits; ulong e1, e2, e3, e4; Word *w; uchar bytes[8], *bp, *wp; int ctl, n; rp = prog; ep = prog+nw; bits = 0; e1 = e2 = e3 = e4 = 0; wp = out; n = 0; ctl = 0; bp = bytes; for(;;){ if(n == 2){ *wp++ = ctl; if(0) fprint(2, "%x\n", ctl); memmove(wp, bytes, bp-bytes); wp += bp-bytes; bp = bytes; ctl = 0; n = 0; } ctl <<= 4; n++; if(rp >= ep){ if(n == 1) break; continue; } if(islittle){ v = GET4L((uchar*)rp); }else{ v = GET4((uchar*)rp); } rp++; if(qflag){ QREMAP(v); } if(v == top){ e1++; bits += 4; ctl |= 0; continue; } w = squash(hash1, v); if(w && w->code){ e2++; bits += 4+8; ctl |= w->code>>8; *bp++ = w->code; continue; } w = squash(hash2, v>>8); if(w && w->code){ e3++; bits += 4+8+8; ctl |= w->code>>8; *bp++ = w->code; *bp++ = v & 0xFF; if(debug > 2) fprint(2, "%x %8.8lux %8.8lux\n", w->code, w->v, v); continue; } e4++; bits += 4+32; ctl |= 0x1; bp[0] = v; bp[1] = v>>8; bp[2] = v>>16; bp[3] = v>>24; bp += 4; } fprint(2, "enc: %lud 4-bits, %lud 12-bits %lud 20-bits %lud 36-bits -- %ld bytes\n", e1, e2, e3, e4, wp-out); return wp-out; } static void squirt(int fd, Squeeze *sq) { uchar b[7*256*5 + 2], rep[5], *p, *q; ulong v; int i; p = b+2; for(i=0; i<sq->n; i++){ v = sq->tab[i]; q = rep; do { *q++ = v & 0x7F; }while((v >>= 7) != 0); do { *p++ = *--q | 0x80; }while(q != rep); p[-1] &= ~0x80; } if(p > b+sizeof(b)) abort(); i = p-b; b[0] = i>>8; b[1] = i; Write(fd, b, i); fprint(2, "table: %d/%d\n", i, (sq->n+1)*4); } static long Read(int fd, void *buf, long nb) { long n; n = read(fd, buf, nb); if(n < 0){ fprint(2, "sqz: %s: read error: %r\n", fname); exits("read"); } if(n < nb){ fprint(2, "sqz: %s: unexpected end-of-file\n", fname); exits("read"); } return n; } static void Write(int fd, void *buf, long nb) { if(write(fd, buf, nb) != nb){ fprint(2, "sqz: write error: %r\n"); exits("write err"); } }