sys/src/cmd/disk/sacfs/sac.c

   1 #include <u.h>
   2 #include <libc.h>
   3 #include <bio.h>
   4 #include "sac.h"
   5 #include "ssort.h"
   6
   7 typedef struct Chain    Chain;
   8 typedef struct Chains   Chains;
   9 typedef struct Huff     Huff;
  10
  11 enum
  12 {
  13         ZBase           = 2,                    /* base of code to encode 0 runs */
  14         LitBase         = ZBase-1,              /* base of literal values */
  15         MaxLit          = 256,
  16
  17         MaxLeaf         = MaxLit+LitBase,
  18
  19         MaxHuffBits     = 16,                   /* limit of bits in a huffman code */
  20         ChainMem        = 2 * (MaxHuffBits - 1) * MaxHuffBits,
  21 };
  22
  23 /*
  24  * huffman code table
  25  */
  26 struct Huff
  27 {
  28         short   bits;                           /* length of the code */
  29         ulong   encode;                         /* the code */
  30 };
  31
  32 struct Chain
  33 {
  34         ulong   count;                          /* occurances of everything in the chain */
  35         ushort  leaf;                           /* leaves to the left of chain, or leaf value */
  36         char    col;                            /* ref count for collecting unused chains */
  37         char    gen;                            /* need to generate chains for next lower level */
  38         Chain   *up;                            /* Chain up in the lists */
  39 };
  40
  41 struct Chains
  42 {
  43         Chain   *lists[(MaxHuffBits - 1) * 2];
  44         ulong   leafcount[MaxLeaf];             /* sorted list of leaf counts */
  45         ushort  leafmap[MaxLeaf];               /* map to actual leaf number */
  46         int     nleaf;                          /* number of leaves */
  47         Chain   chains[ChainMem];
  48         Chain   *echains;
  49         Chain   *free;
  50         char    col;
  51         int     nlists;
  52 };
  53
  54 static  jmp_buf errjmp;
  55
  56 static  uchar   *bout;
  57 static  int     bmax;
  58 static  int     bpos;
  59
  60 static  ulong   leafcount[MaxLeaf];
  61 static  ulong   nzero;
  62 static  ulong   *hbuf;
  63 static  int     hbpos;
  64 static  ulong   nzero;
  65 static  ulong   maxblocksym;
  66
  67 static  void    henc(int);
  68 static  void    hbflush(void);
  69
  70 static  void    mkprecode(Huff*, ulong *, int, int);
  71 static  ulong   sendtab(Huff *tab, int maxleaf, ushort *map);
  72 static  int     elimBits(int b, ulong *bused, char *tmtf, int maxbits);
  73 static  void    elimBit(int b, char *tmtf, int maxbits);
  74 static  void    nextchain(Chains*, int);
  75 static  void    hufftabinit(Huff*, int, ulong*, int);
  76 static  void    leafsort(ulong*, ushort*, int, int);
  77
  78 static  void    bitput(int, int);
  79
  80 static  int     mtf(uchar*, int);
  81 static  void    fatal(char*, ...);
  82
  83 static  ulong   headerbits;
  84 static  ulong   charmapbits;
  85 static  ulong   hufftabbits;
  86 static  ulong   databits;
  87 static  ulong   nbits;
  88 static  ulong   bits;
  89
  90 int
  91 sac(uchar *dst, uchar *src, int n)
  92 {
  93         uchar front[256];
  94         ulong *perm, cmap[256];
  95         long i, c, rev;
  96
  97         rev = 0;
  98
  99         perm = nil;
 100
 101         if(setjmp(errjmp)){
 102                 free(perm);
 103                 if(rev){
 104                         for(i = 0; i < n/2; i++){
 105                                 c = src[i];
 106                                 src[i] = src[n-i-1];
 107                                 src[n-i-1] = c;
 108                         }
 109                 }
 110                 return -1;
 111         }
 112
 113         /*
 114          * set up the output buffer
 115          */
 116         bout = dst;
 117         bmax = n;
 118         bpos = 0;
 119
 120         perm = malloc((n+1)*sizeof *perm);
 121         if(perm == nil)
 122                 return -1;
 123
 124         hbuf = perm;
 125         hbpos = 0;
 126
 127         nbits = 0;
 128         nzero = 0;
 129         for(i = 0; i < MaxLeaf; i++)
 130                 leafcount[i] = 0;
 131
 132         if(rev){
 133                 for(i = 0; i < n/2; i++){
 134                         c = src[i];
 135                         src[i] = src[n-i-1];
 136                         src[n-i-1] = c;
 137                 }
 138         }
 139
 140         i = ssortbyte(src, (int*)perm, nil, n);
 141
 142         headerbits += 16;
 143         bitput(i, 16);
 144
 145         /*
 146          * send the map of chars which occur in this block
 147          */
 148         for(i = 0; i < 256; i++)
 149                 cmap[i] = 0;
 150         for(i = 0; i < n; i++)
 151                 cmap[src[i]] = 1;
 152         charmapbits += 1;
 153         bitput(cmap[0] != 0, 1);
 154         for(i = 0; i < 256; i = c){
 155                 for(c = i + 1; c < 256 && (cmap[c] != 0) == (cmap[i] != 0); c++)
 156                         ;
 157                 charmapbits += 8;
 158                 bitput(c - i - 1, 8);
 159         }
 160
 161         /*
 162          * initialize mtf state
 163          */
 164         c = 0;
 165         for(i = 0; i < 256; i++){
 166                 if(cmap[i]){
 167                         cmap[i] = c;
 168                         front[c] = i;
 169                         c++;
 170                 }
 171         }
 172         maxblocksym = c + LitBase;
 173
 174         for(i = 0; i <= n; i++){
 175                 c = perm[i] - 1;
 176                 if(c < 0)
 177                         continue;
 178                 henc(mtf(front, src[c]));
 179         }
 180
 181         hbflush();
 182         bitput(0, 24);
 183         bitput(0, 8 - nbits);
 184
 185         free(perm);
 186         return bpos;
 187 }
 188
 189 static void
 190 bitput(int c, int n)
 191 {
 192         bits <<= n;
 193         bits |= c;
 194         for(nbits += n; nbits >= 8; nbits -= 8){
 195                 c = bits << (32 - nbits);
 196
 197                 if(bpos >= bmax)
 198                         longjmp(errjmp, 1);
 199                 bout[bpos++] = c >> 24;
 200         }
 201 }
 202
 203 static int
 204 mtf(uchar *front, int c)
 205 {
 206         int i, v;
 207
 208         for(i = 0; front[i] != c; i++)
 209                 ;
 210         for(v = i; i > 0; i--)
 211                 front[i] = front[i - 1];
 212         front[0] = c;
 213         return v;
 214 }
 215
 216 /*
 217  * encode a run of zeros
 218  * convert to funny run length coding:
 219  * add one, omit implicit top 1 bit.
 220  */
 221 static void
 222 zenc(void)
 223 {
 224         int m;
 225
 226         nzero++;
 227         while(nzero != 1){
 228                 m = nzero & 1;
 229                 hbuf[hbpos++] = m;
 230                 leafcount[m]++;
 231                 nzero >>= 1;
 232         }
 233         nzero = 0;
 234 }
 235
 236 /*
 237  * encode one symbol
 238  */
 239 static void
 240 henc(int c)
 241 {
 242         if(c == 0){
 243                 nzero++;
 244                 return;
 245         }
 246
 247         if(nzero)
 248                 zenc();
 249         c += LitBase;
 250         leafcount[c]++;
 251
 252         hbuf[hbpos++] = c;
 253 }
 254
 255 static void
 256 hbflush(void)
 257 {
 258         Huff tab[MaxLeaf];
 259         int i, b, s;
 260
 261         if(nzero)
 262                 zenc();
 263         if(hbpos == 0)
 264                 return;
 265
 266         mkprecode(tab, leafcount, maxblocksym, MaxHuffBits);
 267
 268         hufftabbits += sendtab(tab, maxblocksym, nil);
 269
 270         /*
 271          * send the data
 272          */
 273         for(i = 0; i < hbpos; i++){
 274                 s = hbuf[i];
 275                 b = tab[s].bits;
 276                 if(b == 0)
 277                         fatal("bad tables %d", i);
 278                 databits += b;
 279                 bitput(tab[s].encode, b);
 280         }
 281 }
 282
 283 static ulong
 284 sendtab(Huff *tab, int maxleaf, ushort *map)
 285 {
 286         ulong ccount[MaxHuffBits+1], bused[MaxHuffBits+1];
 287         Huff codetab[MaxHuffBits+1];
 288         char tmtf[MaxHuffBits+1];
 289         ulong bits;
 290         int i, b, max, ttb, s, elim;
 291
 292         /*
 293          * make up the table table
 294          * over cleverness: the data is known to be a huffman table
 295          * check for fullness at each bit level, and wipe it out from
 296          * the possibilities;  when nothing exists except 0, stop.
 297          */
 298         for(i = 0; i <= MaxHuffBits; i++){
 299                 tmtf[i] = i;
 300                 ccount[i] = 0;
 301                 bused[i] = 0;
 302         }
 303         tmtf[0] = -1;
 304         tmtf[MaxHuffBits] = 0;
 305
 306         elim = 0;
 307         for(i = 0; i < maxleaf && elim != MaxHuffBits; i++){
 308                 b = i;
 309                 if(map)
 310                         b = map[b];
 311                 b = tab[b].bits;
 312                 for(s = 0; tmtf[s] != b; s++)
 313                         if(s >= MaxHuffBits)
 314                                 fatal("bitlength not found");
 315                 ccount[s]++;
 316                 for(; s > 0; s--)
 317                         tmtf[s] = tmtf[s-1];
 318                 tmtf[0] = b;
 319
 320                 elim += elimBits(b, bused, tmtf, MaxHuffBits);
 321         }
 322         if(elim != MaxHuffBits && elim != 0)
 323                 fatal("incomplete huffman table");
 324
 325         /*
 326          * make up and send the table table
 327          */
 328         max = 8;
 329         mkprecode(codetab, ccount, MaxHuffBits+1, max);
 330         for(i = 0; i <= max; i++){
 331                 tmtf[i] = i;
 332                 bused[i] = 0;
 333         }
 334         tmtf[0] = -1;
 335         tmtf[max] = 0;
 336         elim = 0;
 337         bits = 0;
 338         for(i = 0; i <= MaxHuffBits && elim != max; i++){
 339                 b = codetab[i].bits;
 340                 for(s = 0; tmtf[s] != b; s++)
 341                         if(s > max)
 342                                 fatal("bitlength not found");
 343                 ttb = 4;
 344                 while(max - elim < (1 << (ttb-1)))
 345                         ttb--;
 346                 bits += ttb;
 347                 bitput(s, ttb);
 348
 349                 elim += elimBits(b, bused, tmtf, max);
 350         }
 351         if(elim != max)
 352                 fatal("incomplete huffman table table");
 353
 354         /*
 355          * send the table
 356          */
 357         for(i = 0; i <= MaxHuffBits; i++){
 358                 tmtf[i] = i;
 359                 bused[i] = 0;
 360         }
 361         tmtf[0] = -1;
 362         tmtf[MaxHuffBits] = 0;
 363         elim = 0;
 364         for(i = 0; i < maxleaf && elim != MaxHuffBits; i++){
 365                 b = i;
 366                 if(map)
 367                         b = map[b];
 368                 b = tab[b].bits;
 369                 for(s = 0; tmtf[s] != b; s++)
 370                         if(s >= MaxHuffBits)
 371                                 fatal("bitlength not found");
 372                 ttb = codetab[s].bits;
 373                 if(ttb < 0)
 374                         fatal("bad huffman table table");
 375                 bits += ttb;
 376                 bitput(codetab[s].encode, ttb);
 377                 for(; s > 0; s--)
 378                         tmtf[s] = tmtf[s-1];
 379                 tmtf[0] = b;
 380
 381                 elim += elimBits(b, bused, tmtf, MaxHuffBits);
 382         }
 383         if(elim != MaxHuffBits && elim != 0)
 384                 fatal("incomplete huffman table");
 385
 386         return bits;
 387 }
 388
 389 static int
 390 elimBits(int b, ulong *bused, char *tmtf, int maxbits)
 391 {
 392         int bb, elim;
 393
 394         if(b < 0)
 395                 return 0;
 396
 397         elim = 0;
 398
 399         /*
 400          * increase bits counts for all descendants
 401          */
 402         for(bb = b + 1; bb < maxbits; bb++){
 403                 bused[bb] += 1 << (bb - b);
 404                 if(bused[bb] == (1 << bb)){
 405                         elim++;
 406                         elimBit(bb, tmtf, maxbits);
 407                 }
 408         }
 409
 410         /*
 411          * steal bits from parent & check for fullness
 412          */
 413         for(; b >= 0; b--){
 414                 bused[b]++;
 415                 if(bused[b] == (1 << b)){
 416                         elim++;
 417                         elimBit(b, tmtf, maxbits);
 418                 }
 419                 if((bused[b] & 1) == 0)
 420                         break;
 421         }
 422         return elim;
 423 }
 424
 425 static void
 426 elimBit(int b, char *tmtf, int maxbits)
 427 {
 428         int bb;
 429
 430         for(bb = 0; bb < maxbits; bb++)
 431                 if(tmtf[bb] == b)
 432                         break;
 433         if(tmtf[bb] != b)
 434                 fatal("elim bit not found");
 435         while(++bb <= maxbits)
 436                 tmtf[bb - 1] = tmtf[bb];
 437 }
 438
 439 /*
 440  * fast?, in-place huffman codes
 441  *
 442  * A. Moffat, J. Katajainen, "In-Place Calculation of Minimum-Redundancy Codes",
 443  *
 444  * counts must be sorted, and may be aliased to bitlens
 445  */
 446 static int
 447 fmkprecode(ulong *bitcount, ulong *bitlen, ulong *counts, int n, int maxbits)
 448 {
 449         int leaf, tree, treet, depth, nodes, internal;
 450
 451         /*
 452          * form the internal tree structure:
 453          * [0, tree) are parent pointers,
 454          * [tree, treet) are weights of internal nodes,
 455          * [leaf, n) are weights of remaining leaves.
 456          *
 457          * note that at the end, there are n-1 internal nodes
 458          */
 459         leaf = 0;
 460         tree = 0;
 461         for(treet = 0; treet != n - 1; treet++){
 462                 if(leaf >= n || tree < treet && bitlen[tree] < counts[leaf]){
 463                         bitlen[treet] = bitlen[tree];
 464                         bitlen[tree++] = treet;
 465                 }else
 466                         bitlen[treet] = counts[leaf++];
 467                 if(leaf >= n || tree < treet && bitlen[tree] < counts[leaf]){
 468                         bitlen[treet] += bitlen[tree];
 469                         bitlen[tree++] = treet;
 470                 }else
 471                         bitlen[treet] += counts[leaf++];
 472         }
 473         if(tree != treet - 1)
 474                 fatal("bad fast mkprecode");
 475
 476         /*
 477          * calculate depth of internal nodes
 478          */
 479         bitlen[n - 2] = 0;
 480         for(tree = n - 3; tree >= 0; tree--)
 481                 bitlen[tree] = bitlen[bitlen[tree]] + 1;
 482
 483         /*
 484          * calculate depth of leaves:
 485          * at each depth, leaves(depth) = nodes(depth) - internal(depth)
 486          * and nodes(depth+1) = 2 * internal(depth)
 487          */
 488         leaf = n;
 489         tree = n - 2;
 490         depth = 0;
 491         for(nodes = 1; nodes > 0; nodes = 2 * internal){
 492                 internal = 0;
 493                 while(tree >= 0 && bitlen[tree] == depth){
 494                         tree--;
 495                         internal++;
 496                 }
 497                 nodes -= internal;
 498                 if(depth < maxbits)
 499                         bitcount[depth] = nodes;
 500                 while(nodes-- > 0)
 501                         bitlen[--leaf] = depth;
 502                 depth++;
 503         }
 504         if(leaf != 0 || tree != -1)
 505                 fatal("bad leaves in fast mkprecode");
 506
 507         return depth - 1;
 508 }
 509
 510 /*
 511  * fast, low space overhead algorithm for max depth huffman type codes
 512  *
 513  * J. Katajainen, A. Moffat and A. Turpin, "A fast and space-economical
 514  * algorithm for length-limited coding," Proc. Intl. Symp. on Algorithms
 515  * and Computation, Cairns, Australia, Dec. 1995, Lecture Notes in Computer
 516  * Science, Vol 1004, J. Staples, P. Eades, N. Katoh, and A. Moffat, eds.,
 517  * pp 12-21, Springer Verlag, New York, 1995.
 518  */
 519 static void
 520 mkprecode(Huff *tab, ulong *count, int n, int maxbits)
 521 {
 522         Chains cs;
 523         Chain *c;
 524         ulong bitcount[MaxHuffBits];
 525         int i, m, em, bits;
 526
 527         /*
 528          * set up the sorted list of leaves
 529          */
 530         m = 0;
 531         for(i = 0; i < n; i++){
 532                 tab[i].bits = -1;
 533                 tab[i].encode = 0;
 534                 if(count[i] != 0){
 535                         cs.leafcount[m] = count[i];
 536                         cs.leafmap[m] = i;
 537                         m++;
 538                 }
 539         }
 540         if(m < 2){
 541                 if(m != 0){
 542                         m = cs.leafmap[0];
 543                         tab[m].bits = 0;
 544                         tab[m].encode = 0;
 545                 }
 546                 return;
 547         }
 548         cs.nleaf = m;
 549         leafsort(cs.leafcount, cs.leafmap, 0, m);
 550
 551         /*
 552          * try fast code
 553          */
 554         bits = fmkprecode(bitcount, cs.leafcount, cs.leafcount, m, maxbits);
 555         if(bits < maxbits){
 556                 for(i = 0; i < m; i++)
 557                         tab[cs.leafmap[i]].bits = cs.leafcount[i];
 558                 bitcount[0] = 0;
 559         }else{
 560                 for(i = 0; i < m; i++)
 561                         cs.leafcount[i] = count[cs.leafmap[i]];
 562
 563                 /*
 564                  * set up free list
 565                  */
 566                 cs.free = &cs.chains[2];
 567                 cs.echains = &cs.chains[ChainMem];
 568                 cs.col = 1;
 569
 570                 /*
 571                  * initialize chains for each list
 572                  */
 573                 c = &cs.chains[0];
 574                 c->count = cs.leafcount[0];
 575                 c->leaf = 1;
 576                 c->col = cs.col;
 577                 c->up = nil;
 578                 c->gen = 0;
 579                 cs.chains[1] = cs.chains[0];
 580                 cs.chains[1].leaf = 2;
 581                 cs.chains[1].count = cs.leafcount[1];
 582                 for(i = 0; i < maxbits-1; i++){
 583                         cs.lists[i * 2] = &cs.chains[0];
 584                         cs.lists[i * 2 + 1] = &cs.chains[1];
 585                 }
 586
 587                 cs.nlists = 2 * (maxbits - 1);
 588                 m = 2 * m - 2;
 589                 for(i = 2; i < m; i++)
 590                         nextchain(&cs, cs.nlists - 2);
 591
 592                 bits = 0;
 593                 bitcount[0] = cs.nleaf;
 594                 for(c = cs.lists[cs.nlists - 1]; c != nil; c = c->up){
 595                         m = c->leaf;
 596                         bitcount[bits++] -= m;
 597                         bitcount[bits] = m;
 598                 }
 599                 m = 0;
 600                 for(i = bits; i >= 0; i--)
 601                         for(em = m + bitcount[i]; m < em; m++)
 602                                 tab[cs.leafmap[m]].bits = i;
 603         }
 604         hufftabinit(tab, n, bitcount, bits);
 605 }
 606
 607 /*
 608  * calculate the next chain on the list
 609  * we can always toss out the old chain
 610  */
 611 static void
 612 nextchain(Chains *cs, int list)
 613 {
 614         Chain *c, *oc;
 615         int i, nleaf, sumc;
 616
 617         oc = cs->lists[list + 1];
 618         cs->lists[list] = oc;
 619         if(oc == nil)
 620                 return;
 621
 622         /*
 623          * make sure we have all chains needed to make sumc
 624          * note it is possible to generate only one of these,
 625          * use twice that value for sumc, and then generate
 626          * the second if that preliminary sumc would be chosen.
 627          * however, this appears to be slower on current tests
 628          */
 629         if(oc->gen){
 630                 nextchain(cs, list - 2);
 631                 nextchain(cs, list - 2);
 632                 oc->gen = 0;
 633         }
 634
 635         /*
 636          * pick up the chain we're going to add;
 637          * collect unused chains no free ones are left
 638          */
 639         for(c = cs->free; ; c++){
 640                 if(c >= cs->echains){
 641                         cs->col++;
 642                         for(i = 0; i < cs->nlists; i++)
 643                                 for(c = cs->lists[i]; c != nil; c = c->up)
 644                                         c->col = cs->col;
 645                         c = cs->chains;
 646                 }
 647                 if(c->col != cs->col)
 648                         break;
 649         }
 650
 651         /*
 652          * pick the cheapest of
 653          * 1) the next package from the previous list
 654          * 2) the next leaf
 655          */
 656         nleaf = oc->leaf;
 657         sumc = 0;
 658         if(list > 0 && cs->lists[list-1] != nil)
 659                 sumc = cs->lists[list-2]->count + cs->lists[list-1]->count;
 660         if(sumc != 0 && (nleaf >= cs->nleaf || cs->leafcount[nleaf] > sumc)){
 661                 c->count = sumc;
 662                 c->leaf = oc->leaf;
 663                 c->up = cs->lists[list-1];
 664                 c->gen = 1;
 665         }else if(nleaf >= cs->nleaf){
 666                 cs->lists[list + 1] = nil;
 667                 return;
 668         }else{
 669                 c->leaf = nleaf + 1;
 670                 c->count = cs->leafcount[nleaf];
 671                 c->up = oc->up;
 672                 c->gen = 0;
 673         }
 674         cs->free = c + 1;
 675
 676         cs->lists[list + 1] = c;
 677         c->col = cs->col;
 678 }
 679
 680 static void
 681 hufftabinit(Huff *tab, int n, ulong *bitcount, int nbits)
 682 {
 683         ulong code, nc[MaxHuffBits];
 684         int i, bits;
 685
 686         code = 0;
 687         for(bits = 1; bits <= nbits; bits++){
 688                 code = (code + bitcount[bits-1]) << 1;
 689                 nc[bits] = code;
 690         }
 691
 692         for(i = 0; i < n; i++){
 693                 bits = tab[i].bits;
 694                 if(bits > 0)
 695                         tab[i].encode = nc[bits]++;
 696         }
 697 }
 698
 699 static int
 700 pivot(ulong *c, int a, int n)
 701 {
 702         int j, pi, pj, pk;
 703
 704         j = n/6;
 705         pi = a + j;     /* 1/6 */
 706         j += j;
 707         pj = pi + j;    /* 1/2 */
 708         pk = pj + j;    /* 5/6 */
 709         if(c[pi] < c[pj]){
 710                 if(c[pi] < c[pk]){
 711                         if(c[pj] < c[pk])
 712                                 return pj;
 713                         return pk;
 714                 }
 715                 return pi;
 716         }
 717         if(c[pj] < c[pk]){
 718                 if(c[pi] < c[pk])
 719                         return pi;
 720                 return pk;
 721         }
 722         return pj;
 723 }
 724
 725 static  void
 726 leafsort(ulong *leafcount, ushort *leafmap, int a, int n)
 727 {
 728         ulong t;
 729         int j, pi, pj, pn;
 730
 731         while(n > 1){
 732                 if(n > 10){
 733                         pi = pivot(leafcount, a, n);
 734                 }else
 735                         pi = a + (n>>1);
 736
 737                 t = leafcount[pi];
 738                 leafcount[pi] = leafcount[a];
 739                 leafcount[a] = t;
 740                 t = leafmap[pi];
 741                 leafmap[pi] = leafmap[a];
 742                 leafmap[a] = t;
 743                 pi = a;
 744                 pn = a + n;
 745                 pj = pn;
 746                 for(;;){
 747                         do
 748                                 pi++;
 749                         while(pi < pn && (leafcount[pi] < leafcount[a] || leafcount[pi] == leafcount[a] && leafmap[pi] > leafmap[a]));
 750                         do
 751                                 pj--;
 752                         while(pj > a && (leafcount[pj] > leafcount[a] || leafcount[pj] == leafcount[a] && leafmap[pj] < leafmap[a]));
 753                         if(pj < pi)
 754                                 break;
 755                         t = leafcount[pi];
 756                         leafcount[pi] = leafcount[pj];
 757                         leafcount[pj] = t;
 758                         t = leafmap[pi];
 759                         leafmap[pi] = leafmap[pj];
 760                         leafmap[pj] = t;
 761                 }
 762                 t = leafcount[a];
 763                 leafcount[a] = leafcount[pj];
 764                 leafcount[pj] = t;
 765                 t = leafmap[a];
 766                 leafmap[a] = leafmap[pj];
 767                 leafmap[pj] = t;
 768                 j = pj - a;
 769
 770                 n = n-j-1;
 771                 if(j >= n){
 772                         leafsort(leafcount, leafmap, a, j);
 773                         a += j+1;
 774                 }else{
 775                         leafsort(leafcount, leafmap, a + (j+1), n);
 776                         n = j;
 777                 }
 778         }
 779 }
 780
 781 static void
 782 fatal(char *fmt, ...)
 783 {
 784         char buf[512];
 785         va_list arg;
 786
 787         va_start(arg, fmt);
 788         doprint(buf, buf+sizeof(buf), fmt, arg);
 789         va_end(arg);
 790
 791         longjmp(errjmp, 1);
 792 }