1 #include <lib9.h> 2 #include <a.out.h> 3 #include "squeeze.h" 4 5 /* 6 * forsyth@vitanuova.com 7 */ 8 9 typedef struct Word Word; 10 struct Word { 11 ulong v; 12 ushort freq; 13 ushort code; 14 Word* next; 15 }; 16 17 typedef struct Squeeze Squeeze; 18 struct Squeeze { 19 int n; 20 /*union {*/ 21 ulong tab[7*256]; 22 Word* rep[7*256]; 23 /*};*/ 24 }; 25 26 enum { 27 HMASK = 0xFFFF, 28 HSIZE = HMASK+1, 29 30 Codebufsize = 3*1024*1024 31 }; 32 33 #define GET4(p) (((((((p)[0]<<8)|(p)[1])<<8)|(p)[2])<<8)|(p)[3]) 34 #define GET4L(p) (((((((p)[3]<<8)|(p)[2])<<8)|(p)[1])<<8)|(p)[0]) 35 #define PUT4(p,v) (((p)[0]=(v)>>24),((p)[1]=(v)>>16),((p)[2]=(v)>>8),((p)[3]=(v))) 36 37 static uchar prog[Codebufsize]; 38 static uchar outbuf[Codebufsize]; 39 static Word* hash1[HSIZE]; 40 static Word* hash2[HSIZE]; 41 static Sqhdr sqhdr; 42 static ulong chksum; 43 44 static int dflag; /* squeeze data, not text */ 45 static int tflag; /* squeeze text, leave data as-is */ 46 static int qflag = 1; /* enable powerpc option */ 47 static int wflag; /* write output */ 48 static int islittle; /* object code uses little-endian byte order */ 49 static int debug; 50 static char* fname; 51 52 static void analyse(ulong*, int, Squeeze*, Squeeze*, Word**); 53 static Word** collate(Word**, int); 54 static void dumpsq(Squeeze*, int); 55 static void freehash(Word**); 56 static long Read(int, void*, long); 57 static void remap(Squeeze*); 58 static int squeeze(ulong*, int, uchar*, ulong); 59 static int squeezetab(int, int, Squeeze*, Word**, int); 60 static void squirt(int, Squeeze*); 61 static void Write(int, void*, long); 62 63 static void 64 usage(void) 65 { 66 fprint(2, "Usage: sqz [-w] [-t] [-d] [-q] q.out\n"); 67 exits("usage"); 68 } 69 70 void 71 main(int argc, char **argv) 72 { 73 int fd, n, ns, nst, nsd; 74 long txtlen, datlen, asis; 75 ulong topdat, toptxt; 76 Exec ex; 77 Squeeze sq3, sq4, sq5, sq6; 78 Word *top; 79 80 setbinmode(); 81 /* fmtinstall('f', gfltconv); */ 82 ARGBEGIN{ 83 case 'D': 84 debug++; 85 break; 86 case 'd': 87 dflag++; 88 break; 89 case 'q': 90 qflag = 0; 91 break; 92 case 't': 93 tflag++; 94 break; 95 case 'w': 96 wflag++; 97 break; 98 default: 99 usage(); 100 }ARGEND 101 fname = *argv; 102 if(fname == nil) 103 usage(); 104 fd = open(fname, OREAD); 105 if(fd < 0){ 106 fprint(2, "sqz: can't open %s: %r\n", fname); 107 exits("open"); 108 } 109 Read(fd, &ex, sizeof(Exec)); 110 txtlen = GET4((uchar*)&ex.text); 111 datlen = GET4((uchar*)&ex.data); 112 switch(GET4((uchar*)&ex.magic)){ 113 case Q_MAGIC: /* powerpc */ 114 islittle = 0; 115 break; 116 case E_MAGIC: /* arm */ 117 islittle = 1; 118 qflag = 0; 119 break; 120 case 0xA0E1: /* arm AIF */ 121 islittle = 1; 122 qflag = 0; 123 txtlen = GET4L((uchar*)&ex+(5*4))-sizeof(Exec); 124 datlen = GET4L((uchar*)&ex+(6*4)); 125 break; 126 default: 127 fprint(2, "sqz: unknown magic for sqz: %8.8ux\n", GET4((uchar*)&ex.magic)); 128 exits("bad magic"); 129 } 130 if(qflag) 131 fprint(2, "PowerPC rules\n"); 132 if(islittle) 133 fprint(2, "Little endian\n"); 134 if(txtlen > sizeof(prog) || datlen > sizeof(prog) || txtlen+datlen > sizeof(prog)){ 135 fprint(2, "sqz: executable too big: %lud+%lud; increase Codebufsize in sqz.c\n", txtlen, datlen); 136 exits("size"); 137 } 138 if(dflag){ 139 seek(fd, txtlen, 1); 140 Read(fd, prog, datlen); 141 }else{ 142 Read(fd, prog, txtlen); 143 Read(fd, prog+txtlen, datlen); 144 } 145 close(fd); 146 asis = 0; 147 if(dflag) 148 n = datlen; 149 else if(tflag){ 150 n = txtlen; 151 asis = datlen; 152 }else 153 n = txtlen+datlen; 154 if(dflag || tflag){ 155 analyse((ulong*)prog, n/4, &sq3, &sq4, &top); 156 nst = squeeze((ulong*)prog, n/4, outbuf, top->v); 157 if(nst < 0) 158 exits("sqz"); 159 nsd = 0; 160 remap(&sq3); 161 remap(&sq4); 162 toptxt = topdat = top->v; 163 }else{ 164 analyse((ulong*)prog, txtlen/4, &sq3, &sq4, &top); 165 nst = squeeze((ulong*)prog, txtlen/4, outbuf, top->v); 166 if(nst < 0) 167 exits("sqz"); 168 toptxt = top->v; 169 remap(&sq3); 170 remap(&sq4); 171 if(datlen/4){ 172 freehash(hash1); 173 freehash(hash2); 174 analyse((ulong*)(prog+txtlen), datlen/4, &sq5, &sq6, &top); 175 nsd = squeeze((ulong*)(prog+txtlen), datlen/4, outbuf+nst, top->v); 176 if(nsd < 0) 177 exits("sqz"); 178 topdat = top->v; 179 remap(&sq5); 180 remap(&sq6); 181 }else{ 182 nsd = 0; 183 topdat = 0; 184 } 185 } 186 ns = nst+nsd; 187 fprint(2, "%d/%d bytes\n", ns, n); 188 fprint(2, "%8.8lux csum\n", chksum); 189 if(!wflag) 190 exits(0); 191 PUT4(sqhdr.magic, SQMAGIC); 192 PUT4(sqhdr.toptxt, toptxt); 193 PUT4(sqhdr.sum, chksum); 194 PUT4(sqhdr.text, nst); 195 PUT4(sqhdr.topdat, topdat); 196 PUT4(sqhdr.data, nsd); 197 PUT4(sqhdr.asis, asis); 198 PUT4(sqhdr.flags, 0); 199 Write(1, &sqhdr, SQHDRLEN); 200 Write(1, &ex, sizeof(Exec)); 201 squirt(1, &sq3); 202 squirt(1, &sq4); 203 Write(1, outbuf, nst); 204 if(nsd){ 205 squirt(1, &sq5); 206 squirt(1, &sq6); 207 Write(1, outbuf+nst, nsd); 208 } 209 if(asis) 210 Write(1, prog+txtlen, asis); 211 exits(0); 212 } 213 214 static void 215 analyse(ulong *prog, int nw, Squeeze *sq3, Squeeze *sq4, Word **top) 216 { 217 Word *w, **hp, **sorts, **resorts; 218 ulong *rp, *ep; 219 ulong v; 220 int i, nv1, nv2, nv, nz; 221 222 rp = prog; 223 ep = prog+nw; 224 nv = 0; 225 nz = 0; 226 while(rp < ep){ 227 if(islittle){ 228 v = GET4L((uchar*)rp); 229 }else{ 230 v = GET4((uchar*)rp); 231 } 232 rp++; 233 chksum += v; 234 if(v == 0){ 235 nz++; 236 if(0) 237 continue; 238 } 239 if(qflag){ 240 QREMAP(v); 241 } 242 for(hp = &hash1[v&HMASK]; (w = *hp) != nil; hp = &w->next) 243 if(w->v == v) 244 break; 245 if(w == nil){ 246 w = (Word*)malloc(sizeof(*w)); 247 w->v = v; 248 w->freq = 0; 249 w->code = 0; 250 w->next = nil; 251 *hp = w; 252 nv++; 253 } 254 w->freq++; 255 } 256 sorts = collate(hash1, nv); 257 fprint(2, "phase 1: %d/%d words (%d zero), %d top (%8.8lux)\n", nv, nw, nz, sorts[0]->freq, sorts[0]->v); 258 *top = sorts[0]; 259 nv1 = squeezetab(1, 0x900, sq3, sorts+1, nv-1)+1; 260 nv2 = 0; 261 for(i=nv1; i<nv; i++){ 262 v = sorts[i]->v >> 8; 263 for(hp = &hash2[v&HMASK]; (w = *hp) != nil; hp = &w->next) 264 if(w->v == v) 265 break; 266 if(w == nil){ 267 w = (Word*)malloc(sizeof(*w)); 268 w->v = v; 269 w->freq = 0; 270 w->code = 0; 271 w->next = nil; 272 *hp = w; 273 nv2++; 274 } 275 w->freq++; 276 } 277 free(sorts); 278 resorts = collate(hash2, nv2); 279 fprint(2, "phase 2: %d/%d\n", nv2, nv-nv1); 280 squeezetab(2, 0x200, sq4, resorts, nv2); 281 free(resorts); 282 fprint(2, "phase 3: 1 4-code, %d 12-codes, %d 20-codes, %d uncoded\n", 283 sq3->n, sq4->n, nv-(sq3->n+sq4->n+1)); 284 } 285 286 static int 287 wdcmp(void *a, void *b) 288 { 289 return (*(Word**)b)->freq - (*(Word**)a)->freq; 290 } 291 292 static Word ** 293 collate(Word **tab, int nv) 294 { 295 Word *w, **hp, **sorts; 296 int i; 297 298 sorts = (Word**)malloc(nv*sizeof(Word**)); 299 i = 0; 300 for(hp = &tab[0]; hp < &tab[HSIZE]; hp++) 301 for(w = *hp; w != nil; w = w->next) 302 sorts[i++] = w; 303 qsort(sorts, nv, sizeof(*sorts), wdcmp); 304 if(debug > 1) 305 for(i=0; i<nv; i++) 306 fprint(2, "%d\t%d\t%8.8lux\n", i, sorts[i]->freq, sorts[i]->v); 307 return sorts; 308 } 309 310 static int 311 tabcmp(void *a, void *b) 312 { 313 ulong av, bv; 314 315 av = (*(Word**)a)->v; 316 bv = (*(Word**)b)->v; 317 if(av > bv) 318 return 1; 319 if(av < bv) 320 return -1; 321 return 0; 322 } 323 324 static int 325 squeezetab(int tabno, int base, Squeeze *sq, Word **sorts, int nv) 326 { 327 int i; 328 329 if(nv >= 7*256) 330 nv = 7*256; 331 memset(sq, 0, sizeof(*sq)); 332 for(i=0; i<nv; i++) 333 sq->rep[sq->n++] = sorts[i]; 334 qsort(sq->rep, sq->n, sizeof(*sq->rep), tabcmp); 335 for(i=0; i<sq->n; i++) 336 sq->rep[i]->code = base + i; 337 if(debug) 338 dumpsq(sq, tabno); 339 return sq->n; 340 } 341 342 static void 343 dumpsq(Squeeze *sq, int n) 344 { 345 int i; 346 347 fprint(2, "table %d: %d entries\n", n, sq->n); 348 for(i=0; i<sq->n; i++) 349 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); 350 } 351 352 static void 353 remap(Squeeze *sq) 354 { 355 int i; 356 ulong v; 357 358 if(sq->n){ 359 v = 0; 360 for(i=0; i<sq->n; i++){ 361 sq->tab[i] = sq->rep[i]->v - v; 362 v += sq->tab[i]; 363 } 364 } 365 } 366 367 static Word * 368 squash(Word **tab, ulong v) 369 { 370 Word *w, **hp; 371 372 for(hp = &tab[v&0xFFFF]; (w = *hp) != nil; hp = &w->next) 373 if(w->v == v) 374 return w; 375 return nil; 376 } 377 378 static void 379 freehash(Word **tab) 380 { 381 Word *w, **hp; 382 383 for(hp = &tab[0]; hp < &tab[HSIZE]; hp++) 384 while((w = *hp) != nil){ 385 *hp = w->next; 386 free(w); 387 } 388 } 389 390 static int 391 squeeze(ulong *prog, int nw, uchar *out, ulong top) 392 { 393 ulong *rp, *ep; 394 ulong v, bits; 395 ulong e1, e2, e3, e4; 396 Word *w; 397 uchar bytes[8], *bp, *wp; 398 int ctl, n; 399 400 rp = prog; 401 ep = prog+nw; 402 bits = 0; 403 e1 = e2 = e3 = e4 = 0; 404 wp = out; 405 n = 0; 406 ctl = 0; 407 bp = bytes; 408 for(;;){ 409 if(n == 2){ 410 *wp++ = ctl; 411 if(0) 412 fprint(2, "%x\n", ctl); 413 memmove(wp, bytes, bp-bytes); 414 wp += bp-bytes; 415 bp = bytes; 416 ctl = 0; 417 n = 0; 418 } 419 ctl <<= 4; 420 n++; 421 if(rp >= ep){ 422 if(n == 1) 423 break; 424 continue; 425 } 426 if(islittle){ 427 v = GET4L((uchar*)rp); 428 }else{ 429 v = GET4((uchar*)rp); 430 } 431 rp++; 432 if(qflag){ 433 QREMAP(v); 434 } 435 if(v == top){ 436 e1++; 437 bits += 4; 438 ctl |= 0; 439 continue; 440 } 441 w = squash(hash1, v); 442 if(w && w->code){ 443 e2++; 444 bits += 4+8; 445 ctl |= w->code>>8; 446 *bp++ = w->code; 447 continue; 448 } 449 w = squash(hash2, v>>8); 450 if(w && w->code){ 451 e3++; 452 bits += 4+8+8; 453 ctl |= w->code>>8; 454 *bp++ = w->code; 455 *bp++ = v & 0xFF; 456 if(debug > 2) 457 fprint(2, "%x %8.8lux %8.8lux\n", w->code, w->v, v); 458 continue; 459 } 460 e4++; 461 bits += 4+32; 462 ctl |= 0x1; 463 bp[0] = v; 464 bp[1] = v>>8; 465 bp[2] = v>>16; 466 bp[3] = v>>24; 467 bp += 4; 468 } 469 fprint(2, "enc: %lud 4-bits, %lud 12-bits %lud 20-bits %lud 36-bits -- %ld bytes\n", 470 e1, e2, e3, e4, wp-out); 471 return wp-out; 472 } 473 474 static void 475 squirt(int fd, Squeeze *sq) 476 { 477 uchar b[7*256*5 + 2], rep[5], *p, *q; 478 ulong v; 479 int i; 480 481 p = b+2; 482 for(i=0; i<sq->n; i++){ 483 v = sq->tab[i]; 484 q = rep; 485 do { 486 *q++ = v & 0x7F; 487 }while((v >>= 7) != 0); 488 do { 489 *p++ = *--q | 0x80; 490 }while(q != rep); 491 p[-1] &= ~0x80; 492 } 493 if(p > b+sizeof(b)) 494 abort(); 495 i = p-b; 496 b[0] = i>>8; 497 b[1] = i; 498 Write(fd, b, i); 499 fprint(2, "table: %d/%d\n", i, (sq->n+1)*4); 500 } 501 502 static long 503 Read(int fd, void *buf, long nb) 504 { 505 long n; 506 507 n = read(fd, buf, nb); 508 if(n < 0){ 509 fprint(2, "sqz: %s: read error: %r\n", fname); 510 exits("read"); 511 } 512 if(n < nb){ 513 fprint(2, "sqz: %s: unexpected end-of-file\n", fname); 514 exits("read"); 515 } 516 return n; 517 } 518 519 static void 520 Write(int fd, void *buf, long nb) 521 { 522 if(write(fd, buf, nb) != nb){ 523 fprint(2, "sqz: write error: %r\n"); 524 exits("write err"); 525 } 526 } 527