util/nrv2b/nrv2b.c

   1 /**************************************************************
   2     Form adapted from lzhuf.c
   3     written by Haruyasu Yoshizaki 11/20/1988
   4     some minor changes 4/6/1989
   5     comments translated by Haruhiko Okumura 4/7/1989
   6
   7     minor beautifications and adjustments for compiling under Linux
   8     by Markus Gutschke <gutschk@math.uni-muenster.de>
   9                                                 1997-01-27
  10
  11     Modifications to allow use as a filter by Ken Yap
  12     <ken_yap@users.sourceforge.net>.
  13
  14                                                 1997-07-01
  15
  16     Small mod to cope with running on big-endian machines
  17     by Jim Hague <jim.hague@acm.org)
  18                                                 1998-02-06
  19
  20     Make compression statistics report shorter
  21     by Ken Yap <ken_yap@users.sourceforge.net>.
  22                                                 2001-04-25
  23
  24     Replaced algorithm with nrv2b from ucl the compression
  25     library from upx.  That code is:
  26     Copyright (C) 1996-2002 Markus Franz Xaver Johannes Oberhumer
  27     And is distributed under the terms of the GPL.
  28     The conversion was performed
  29     by Eric Biederman <ebiederman@lnxi.com>.
  30                                              20 August 2002
  31
  32 **************************************************************/
  33 #define UCLPACK_COMPAT 0
  34 #include <stdio.h>
  35 #include <stdlib.h>
  36 #include <string.h>
  37 #include <ctype.h>
  38 #include <errno.h>
  39 #include <stdint.h>
  40 #include <limits.h>
  41 #include <assert.h>
  42 #if UCLPACK_COMPAT
  43 #include <netinet/in.h>
  44 #endif
  45
  46 #ifndef VERBOSE
  47 #define Fprintf(x)
  48 #define wterr     0
  49 #else
  50 #define Fprintf(x) fprintf x
  51 #endif
  52
  53 #ifndef MAIN
  54 extern
  55 #endif
  56 FILE  *infile, *outfile;
  57
  58 #if defined(ENCODE) || defined(DECODE)
  59
  60 #ifndef ENDIAN
  61 #define ENDIAN   0
  62 #endif
  63 #ifndef BITSIZE
  64 #define BITSIZE 32
  65 #endif
  66
  67 static __inline__ void Error(char *message)
  68 {
  69         Fprintf((stderr, "\n%s\n", message));
  70         exit(EXIT_FAILURE);
  71 }
  72
  73 /* These will be a complete waste of time on a lo-endian */
  74 /* system, but it only gets done once so WTF. */
  75 static unsigned long i86ul_to_host(unsigned long ul)
  76 {
  77         unsigned long res = 0;
  78         int i;
  79         union
  80         {
  81                 unsigned char c[4];
  82                 unsigned long ul;
  83         } u;
  84
  85         u.ul = ul;
  86         for (i = 3; i >= 0; i--)
  87                 res = (res << 8) + u.c[i];
  88         return res;
  89 }
  90
  91 static unsigned long host_to_i86ul(unsigned long ul)
  92 {
  93         int i;
  94         union
  95         {
  96                 unsigned char c[4];
  97                 unsigned long ul;
  98         } u;
  99
 100         for (i = 0; i < 4; i++)
 101         {
 102                 u.c[i] = ul & 0xff;
 103                 ul >>= 8;
 104         }
 105         return u.ul;
 106 }
 107 #endif
 108
 109
 110
 111 #if UCLPACK_COMPAT
 112 /* magic file header for compressed files */
 113 static const unsigned char magic[8] =
 114 { 0x00, 0xe9, 0x55, 0x43, 0x4c, 0xff, 0x01, 0x1a };
 115
 116 #endif
 117
 118 #ifdef ENCODE
 119 /********** NRV2B_99 compression **********/
 120
 121 #define N       (1024*1024ul)       /* size of ring buffer */
 122 #define THRESHOLD       1           /* lower limit for match length */
 123 #define F            2048           /* upper limit for match length */
 124 #define M2_MAX_OFFSET                 0xd00
 125
 126 /* note: to use default values pass -1, i.e. initialize
 127  * this struct by a memset(x,0xff,sizeof(x)) */
 128 struct ucl_compress_config
 129 {
 130         int bb_endian;
 131         int bb_size;
 132         unsigned int max_offset;
 133         unsigned int max_match;
 134         int s_level;
 135         int h_level;
 136         int p_level;
 137         int c_flags;
 138         unsigned int m_size;
 139 };
 140
 141 struct ucl_compress
 142 {
 143         int init;
 144
 145         unsigned int look;          /* bytes in lookahead buffer */
 146
 147         unsigned int m_len;
 148         unsigned int m_off;
 149
 150         unsigned int last_m_len;
 151         unsigned int last_m_off;
 152
 153         const unsigned char *bp;
 154         const unsigned char *ip;
 155         const unsigned char *in;
 156         const unsigned char *in_end;
 157         unsigned char *out;
 158
 159         uint32_t bb_b;
 160         unsigned bb_k;
 161         unsigned bb_c_endian;
 162         unsigned bb_c_s;
 163         unsigned bb_c_s8;
 164         unsigned char *bb_p;
 165         unsigned char *bb_op;
 166
 167         struct ucl_compress_config conf;
 168         unsigned int *result;
 169
 170         unsigned int textsize;      /* text size counter */
 171         unsigned int codesize;      /* code size counter */
 172         unsigned int printcount; /* counter for reporting progress every 1K
 173                                     bytes */
 174
 175
 176         /* some stats */
 177         unsigned long lit_bytes;
 178         unsigned long match_bytes;
 179         unsigned long rep_bytes;
 180         unsigned long lazy;
 181 };
 182
 183
 184
 185 #define getbyte(c)  ((c).ip < (c).in_end ? *((c).ip)++ : (-1))
 186
 187 #define UCL_E_OK               0
 188 #define UCL_E_INVALID_ARGUMENT 1
 189 #define UCL_E_OUT_OF_MEMORY    2
 190 #define UCL_E_ERROR            3
 191
 192 /***********************************************************************
 193 //
 194 ************************************************************************/
 195
 196 #define SWD_HSIZE       16384
 197 #define SWD_MAX_CHAIN   2048
 198
 199 #define HEAD3(b,p) \
 200     (((0x9f5f*(((((uint32_t)b[p]<<5)^b[p+1])<<5)^b[p+2]))>>5) & (SWD_HSIZE-1))
 201
 202 #define HEAD2(b,p)      (b[p] ^ ((unsigned)b[p+1]<<8))
 203 #define NIL2              UINT_MAX
 204
 205 struct ucl_swd
 206 {
 207 /* public - "built-in" */
 208         unsigned int n;
 209         unsigned int f;
 210         unsigned int threshold;
 211
 212 /* public - configuration */
 213         unsigned int max_chain;
 214         unsigned int nice_length;
 215         int use_best_off;
 216         unsigned int lazy_insert;
 217
 218 /* public - output */
 219         unsigned int m_len;
 220         unsigned int m_off;
 221         unsigned int look;
 222         int b_char;
 223 #if defined(SWD_BEST_OFF)
 224         unsigned int best_off[ SWD_BEST_OFF ];
 225 #endif
 226
 227 /* semi public */
 228         struct ucl_compress *c;
 229         unsigned int m_pos;
 230 #if defined(SWD_BEST_OFF)
 231         unsigned int best_pos[ SWD_BEST_OFF ];
 232 #endif
 233
 234 /* private */
 235         const uint8_t *dict;
 236         const uint8_t *dict_end;
 237         unsigned int dict_len;
 238
 239 /* private */
 240         unsigned int ip;                /* input pointer (lookahead) */
 241         unsigned int bp;                /* buffer pointer */
 242         unsigned int rp;                /* remove pointer */
 243         unsigned int b_size;
 244
 245         unsigned char *b_wrap;
 246
 247         unsigned int node_count;
 248         unsigned int first_rp;
 249
 250         unsigned char b [ N + F + F ];
 251         unsigned int head3 [ SWD_HSIZE ];
 252         unsigned int succ3 [ N + F ];
 253         unsigned int best3 [ N + F ];
 254         unsigned int llen3 [ SWD_HSIZE ];
 255         unsigned int head2 [ 65536U ];
 256 };
 257
 258 #define s_head3(s,key)        s->head3[key]
 259
 260
 261 #if !defined( NDEBUG)
 262 static void assert_match(const struct ucl_swd * swd, unsigned int m_len,
 263         unsigned int m_off )
 264
 265 {
 266         const struct ucl_compress *c = swd->c;
 267         unsigned int d_off;
 268
 269         assert(m_len >= 2);
 270         if (m_off <= (unsigned int) (c->bp - c->in))
 271         {
 272                 assert(c->bp - m_off + m_len < c->ip);
 273                 assert(memcmp(c->bp, c->bp - m_off, m_len) == 0);
 274         }
 275         else
 276         {
 277                 assert(swd->dict != NULL);
 278                 d_off = m_off - (unsigned int) (c->bp - c->in);
 279                 assert(d_off <= swd->dict_len);
 280                 if (m_len > d_off)
 281                 {
 282                         assert(memcmp(c->bp, swd->dict_end - d_off, d_off) ==
 283                                 0);
 284
 285                         assert(c->in + m_len - d_off < c->ip);
 286                         assert(memcmp(c->bp + d_off, c->in, m_len - d_off) ==
 287                                 0);
 288
 289                 }
 290                 else
 291                 {
 292                         assert(memcmp(c->bp, swd->dict_end - d_off, m_len) ==
 293                                 0);
 294
 295                 }
 296         }
 297 }
 298 #else
 299 #  define assert_match(a,b,c)   ((void)0)
 300 #endif
 301
 302 /***********************************************************************
 303 //
 304 ************************************************************************/
 305
 306
 307 static
 308 void swd_initdict(struct ucl_swd *s, const uint8_t *dict, unsigned int dict_len)
 309
 310 {
 311         s->dict = s->dict_end = NULL;
 312         s->dict_len = 0;
 313
 314         if (!dict || dict_len <= 0)
 315                 return;
 316         if (dict_len > s->n)
 317         {
 318                 dict += dict_len - s->n;
 319                 dict_len = s->n;
 320         }
 321
 322         s->dict = dict;
 323         s->dict_len = dict_len;
 324         s->dict_end = dict + dict_len;
 325         memcpy(s->b,dict,dict_len);
 326         s->ip = dict_len;
 327 }
 328
 329
 330 static
 331 void swd_insertdict(struct ucl_swd *s, unsigned int node, unsigned int len)
 332 {
 333         unsigned int key;
 334
 335         s->node_count = s->n - len;
 336         s->first_rp = node;
 337
 338         while (len-- > 0)
 339         {
 340                 key = HEAD3(s->b,node);
 341                 s->succ3[node] = s_head3(s,key);
 342                 s->head3[key] = (unsigned int)(node);
 343                 s->best3[node] = (unsigned int)(s->f + 1);
 344                 s->llen3[key]++;
 345                 assert(s->llen3[key] <= s->n);
 346
 347                 key = HEAD2(s->b,node);
 348                 s->head2[key] = (unsigned int)(node);
 349
 350                 node++;
 351         }
 352 }
 353
 354 /***********************************************************************
 355 //
 356 ************************************************************************/
 357
 358
 359 static
 360 int swd_init(struct ucl_swd *s, const uint8_t *dict, unsigned int dict_len)
 361 {
 362         unsigned int i = 0;
 363         int c = 0;
 364
 365         if (s->n == 0)
 366                 s->n = N;
 367         if (s->f == 0)
 368                 s->f = F;
 369         s->threshold = THRESHOLD;
 370         if (s->n > N || s->f > F)
 371                 return UCL_E_INVALID_ARGUMENT;
 372
 373         /* defaults */
 374         s->max_chain = SWD_MAX_CHAIN;
 375         s->nice_length = s->f;
 376         s->use_best_off = 0;
 377         s->lazy_insert = 0;
 378
 379         s->b_size = s->n + s->f;
 380         if (s->b_size + s->f >= UINT_MAX)
 381                 return UCL_E_ERROR;
 382         s->b_wrap = s->b + s->b_size;
 383         s->node_count = s->n;
 384
 385         memset(s->llen3, 0, sizeof(s->llen3[0]) * SWD_HSIZE);
 386         for (i = 0; i < 65536U; i++)
 387                 s->head2[i] = NIL2;
 388
 389         s->ip = 0;
 390         swd_initdict(s,dict,dict_len);
 391         s->bp = s->ip;
 392         s->first_rp = s->ip;
 393
 394         assert(s->ip + s->f <= s->b_size);
 395
 396         s->look = (unsigned int) (s->c->in_end - s->c->ip);
 397         if (s->look > 0)
 398         {
 399                 if (s->look > s->f)
 400                         s->look = s->f;
 401                 memcpy(&s->b[s->ip],s->c->ip,s->look);
 402                 s->c->ip += s->look;
 403                 s->ip += s->look;
 404         }
 405         if (s->ip == s->b_size)
 406                 s->ip = 0;
 407
 408         if (s->look >= 2 && s->dict_len > 0)
 409                 swd_insertdict(s,0,s->dict_len);
 410
 411         s->rp = s->first_rp;
 412         if (s->rp >= s->node_count)
 413                 s->rp -= s->node_count;
 414         else
 415                 s->rp += s->b_size - s->node_count;
 416
 417         /* unused i */
 418         /* unused c */
 419         return UCL_E_OK;
 420 }
 421
 422
 423 static
 424 void swd_exit(struct ucl_swd *s)
 425 {
 426         /* unused s */
 427
 428 }
 429
 430 #define swd_pos2off(s,pos) \
 431         (s->bp > (pos) ? s->bp - (pos) : s->b_size - ((pos) - s->bp))
 432
 433 /***********************************************************************
 434 //
 435 ************************************************************************/
 436
 437 static __inline__
 438 void swd_getbyte(struct ucl_swd *s)
 439 {
 440         int c;
 441
 442         if ((c = getbyte(*(s->c))) < 0)
 443         {
 444                 if (s->look > 0)
 445                         --s->look;
 446         }
 447         else
 448         {
 449                 s->b[s->ip] = (uint8_t)(c);
 450                 if (s->ip < s->f)
 451                         s->b_wrap[s->ip] = (uint8_t)(c);
 452         }
 453         if (++s->ip == s->b_size)
 454                 s->ip = 0;
 455         if (++s->bp == s->b_size)
 456                 s->bp = 0;
 457         if (++s->rp == s->b_size)
 458                 s->rp = 0;
 459 }
 460 /***********************************************************************
 461 // remove node from lists
 462 ************************************************************************/
 463
 464 static __inline__
 465 void swd_remove_node(struct ucl_swd *s, unsigned int node)
 466 {
 467         if (s->node_count == 0)
 468         {
 469                 unsigned int key;
 470
 471 #ifdef UCL_DEBUG
 472                 if (s->first_rp != UINT_MAX)
 473                 {
 474                         if (node != s->first_rp)
 475                                 printf("Remove %5d: %5d %5d %5d %5d %6d %6d\n",
 476
 477                                         node, s->rp, s->ip, s->bp, s->first_rp,
 478                                         s->ip - node, s->ip - s->bp);
 479                         assert(node == s->first_rp);
 480                         s->first_rp = UINT_MAX;
 481                 }
 482 #endif
 483
 484                 key = HEAD3(s->b,node);
 485                 assert(s->llen3[key] > 0);
 486                 --s->llen3[key];
 487
 488                 key = HEAD2(s->b,node);
 489                 assert(s->head2[key] != NIL2);
 490                 if ((unsigned int) s->head2[key] == node)
 491                         s->head2[key] = NIL2;
 492         }
 493         else
 494                 --s->node_count;
 495 }
 496
 497
 498 /***********************************************************************
 499 //
 500 ************************************************************************/
 501
 502
 503 static
 504 void swd_accept(struct ucl_swd *s, unsigned int n)
 505 {
 506         assert(n <= s->look);
 507
 508         if (n > 0) do
 509         {
 510                 unsigned int key;
 511
 512                 swd_remove_node(s,s->rp);
 513
 514                 /* add bp into HEAD3 */
 515                 key = HEAD3(s->b,s->bp);
 516                 s->succ3[s->bp] = s_head3(s,key);
 517                 s->head3[key] = (unsigned int)(s->bp);
 518                 s->best3[s->bp] = (unsigned int)(s->f + 1);
 519                 s->llen3[key]++;
 520                 assert(s->llen3[key] <= s->n);
 521
 522                 /* add bp into HEAD2 */
 523                 key = HEAD2(s->b,s->bp);
 524                 s->head2[key] = (unsigned int)(s->bp);
 525
 526                 swd_getbyte(s);
 527         } while (--n > 0);
 528 }
 529
 530 /***********************************************************************
 531 //
 532 ************************************************************************/
 533
 534 static
 535 void swd_search(struct ucl_swd *s, unsigned int node, unsigned int cnt)
 536 {
 537         const unsigned char *p1;
 538         const unsigned char *p2;
 539         const unsigned char *px;
 540
 541         unsigned int m_len = s->m_len;
 542         const unsigned char * b  = s->b;
 543         const unsigned char * bp = s->b + s->bp;
 544         const unsigned char * bx = s->b + s->bp + s->look;
 545         unsigned char scan_end1;
 546
 547         assert(s->m_len > 0);
 548
 549         scan_end1 = bp[m_len - 1];
 550         for ( ; cnt-- > 0; node = s->succ3[node])
 551         {
 552                 p1 = bp;
 553                 p2 = b + node;
 554                 px = bx;
 555
 556                 assert(m_len < s->look);
 557
 558                 if (
 559                         p2[m_len - 1] == scan_end1 &&
 560                         p2[m_len] == p1[m_len] &&
 561                         p2[0] == p1[0] &&
 562                         p2[1] == p1[1])
 563                 {
 564                         unsigned int i;
 565                         assert(memcmp(bp,&b[node],3) == 0);
 566
 567                         p1 += 2; p2 += 2;
 568                         do {} while (++p1 < px && *p1 == *++p2);
 569                         i = p1 - bp;
 570
 571 #ifdef UCL_DEBUG
 572                         if (memcmp(bp,&b[node],i) != 0)
 573                                 printf("%5ld %5ld %02x%02x %02x%02x\n",
 574                                         (long)s->bp, (long) node,
 575                                         bp[0], bp[1], b[node], b[node+1]);
 576 #endif
 577                         assert(memcmp(bp,&b[node],i) == 0);
 578
 579 #if defined(SWD_BEST_OFF)
 580                         if (i < SWD_BEST_OFF)
 581                         {
 582                                 if (s->best_pos[i] == 0)
 583                                         s->best_pos[i] = node + 1;
 584                         }
 585 #endif
 586                         if (i > m_len)
 587                         {
 588                                 s->m_len = m_len = i;
 589                                 s->m_pos = node;
 590                                 if (m_len == s->look)
 591                                         return;
 592                                 if (m_len >= s->nice_length)
 593                                         return;
 594                                 if (m_len > (unsigned int) s->best3[node])
 595                                         return;
 596                                 scan_end1 = bp[m_len - 1];
 597                         }
 598                 }
 599         }
 600 }
 601
 602 static int swd_search2(struct ucl_swd *s)
 603 {
 604         unsigned int key;
 605
 606         assert(s->look >= 2);
 607         assert(s->m_len > 0);
 608
 609         key = s->head2[ HEAD2(s->b,s->bp) ];
 610         if (key == NIL2)
 611                 return 0;
 612 #ifdef UCL_DEBUG
 613         if (memcmp(&s->b[s->bp],&s->b[key],2) != 0)
 614                 printf("%5ld %5ld %02x%02x %02x%02x\n", (long)s->bp, (long)key,
 615                         s->b[s->bp], s->b[s->bp+1], s->b[key], s->b[key+1]);
 616 #endif
 617         assert(memcmp(&s->b[s->bp],&s->b[key],2) == 0);
 618 #if defined(SWD_BEST_OFF)
 619         if (s->best_pos[2] == 0)
 620                 s->best_pos[2] = key + 1;
 621 #endif
 622
 623         if (s->m_len < 2)
 624         {
 625                 s->m_len = 2;
 626                 s->m_pos = key;
 627         }
 628         return 1;
 629 }
 630
 631 /***********************************************************************
 632 //
 633 ************************************************************************/
 634
 635 static
 636 void swd_findbest(struct ucl_swd *s)
 637 {
 638         unsigned int key;
 639         unsigned int cnt, node;
 640         unsigned int len;
 641
 642         assert(s->m_len > 0);
 643
 644         /* get current head, add bp into HEAD3 */
 645         key = HEAD3(s->b,s->bp);
 646         node = s->succ3[s->bp] = s_head3(s,key);
 647         cnt = s->llen3[key]++;
 648         assert(s->llen3[key] <= s->n + s->f);
 649         if (cnt > s->max_chain && s->max_chain > 0)
 650                 cnt = s->max_chain;
 651         s->head3[key] = (unsigned int)(s->bp);
 652
 653         s->b_char = s->b[s->bp];
 654         len = s->m_len;
 655         if (s->m_len >= s->look)
 656         {
 657                 if (s->look == 0)
 658                         s->b_char = -1;
 659                 s->m_off = 0;
 660                 s->best3[s->bp] = (unsigned int)(s->f + 1);
 661         }
 662         else
 663         {
 664                 if (swd_search2(s))
 665                         if (s->look >= 3)
 666                                 swd_search(s,node,cnt);
 667                 if (s->m_len > len)
 668                         s->m_off = swd_pos2off(s,s->m_pos);
 669                 s->best3[s->bp] = (unsigned int)(s->m_len);
 670
 671 #if defined(SWD_BEST_OFF)
 672                 if (s->use_best_off)
 673                 {
 674                         int i;
 675                         for (i = 2; i < SWD_BEST_OFF; i++)
 676                                 if (s->best_pos[i] > 0)
 677                                         s->best_off[i] =
 678                                                 swd_pos2off(s,s->best_pos[i]-1);
 679
 680                                 else
 681                                         s->best_off[i] = 0;
 682                 }
 683 #endif
 684         }
 685
 686         swd_remove_node(s,s->rp);
 687
 688         /* add bp into HEAD2 */
 689         key = HEAD2(s->b,s->bp);
 690         s->head2[key] = (unsigned int)(s->bp);
 691 }
 692
 693
 694 /***********************************************************************
 695 //
 696 ************************************************************************/
 697
 698 static int
 699 init_match ( struct ucl_compress *c, struct ucl_swd *s,
 700         const uint8_t *dict, unsigned int dict_len,
 701         uint32_t flags )
 702 {
 703         int r;
 704
 705         assert(!c->init);
 706         c->init = 1;
 707
 708         s->c = c;
 709
 710         c->last_m_len = c->last_m_off = 0;
 711
 712         c->textsize = c->codesize = c->printcount = 0;
 713         c->lit_bytes = c->match_bytes = c->rep_bytes = 0;
 714         c->lazy = 0;
 715
 716         r = swd_init(s,dict,dict_len);
 717         if (r != UCL_E_OK)
 718         {
 719                 swd_exit(s);
 720                 return r;
 721         }
 722
 723         s->use_best_off = (flags & 1) ? 1 : 0;
 724         return UCL_E_OK;
 725 }
 726
 727 static int
 728 find_match ( struct ucl_compress *c, struct ucl_swd *s,
 729         unsigned int this_len, unsigned int skip )
 730 {
 731         assert(c->init);
 732
 733         if (skip > 0)
 734         {
 735                 assert(this_len >= skip);
 736                 swd_accept(s, this_len - skip);
 737                 c->textsize += this_len - skip + 1;
 738         }
 739         else
 740         {
 741                 assert(this_len <= 1);
 742                 c->textsize += this_len - skip;
 743         }
 744
 745         s->m_len = THRESHOLD;
 746 #ifdef SWD_BEST_OFF
 747         if (s->use_best_off)
 748                 memset(s->best_pos,0,sizeof(s->best_pos));
 749 #endif
 750         swd_findbest(s);
 751         c->m_len = s->m_len;
 752         c->m_off = s->m_off;
 753
 754         swd_getbyte(s);
 755
 756         if (s->b_char < 0)
 757         {
 758                 c->look = 0;
 759                 c->m_len = 0;
 760                 swd_exit(s);
 761         }
 762         else
 763         {
 764                 c->look = s->look + 1;
 765         }
 766         c->bp = c->ip - c->look;
 767
 768 #if 0
 769         /* brute force match search */
 770         if (c->m_len > THRESHOLD && c->m_len + 1 <= c->look)
 771         {
 772                 const uint8_t *ip = c->bp;
 773                 const uint8_t *m  = c->bp - c->m_off;
 774                 const uint8_t *in = c->in;
 775
 776                 if (ip - in > N)
 777                         in = ip - N;
 778                 for (;;)
 779                 {
 780                         while (*in != *ip)
 781                                 in++;
 782                         if (in == ip)
 783                                 break;
 784                         if (in != m)
 785                                 if (memcmp(in,ip,c->m_len+1) == 0)
 786                                         printf("%p %p %p %5d\n",
 787                                                 in, ip, m, c->m_len);
 788
 789                         in++;
 790                 }
 791         }
 792 #endif
 793
 794         return UCL_E_OK;
 795 }
 796
 797
 798 static int bbConfig(struct ucl_compress *c, int endian, int bitsize)
 799 {
 800         if (endian != -1)
 801         {
 802                 if (endian != 0)
 803                         return UCL_E_ERROR;
 804                 c->bb_c_endian = endian;
 805         }
 806         if (bitsize != -1)
 807         {
 808                 if (bitsize != 8 && bitsize != 16 && bitsize != 32)
 809                         return UCL_E_ERROR;
 810                 c->bb_c_s = bitsize;
 811                 c->bb_c_s8 = bitsize / 8;
 812         }
 813         c->bb_b = 0; c->bb_k = 0;
 814         c->bb_p = NULL;
 815         c->bb_op = NULL;
 816         return UCL_E_OK;
 817 }
 818
 819 static void bbWriteBits(struct ucl_compress *c)
 820 {
 821         uint8_t *p = c->bb_p;
 822         uint32_t b = c->bb_b;
 823
 824         p[0] = (uint8_t)(b >>  0);
 825         if (c->bb_c_s >= 16)
 826         {
 827                 p[1] = (uint8_t)(b >>  8);
 828                 if (c->bb_c_s == 32)
 829                 {
 830                         p[2] = (uint8_t)(b >> 16);
 831                         p[3] = (uint8_t)(b >> 24);
 832                 }
 833         }
 834 }
 835
 836
 837 static void bbPutBit(struct ucl_compress *c, unsigned bit)
 838 {
 839         assert(bit == 0 || bit == 1);
 840         assert(c->bb_k <= c->bb_c_s);
 841
 842         if (c->bb_k < c->bb_c_s)
 843         {
 844                 if (c->bb_k == 0)
 845                 {
 846                         assert(c->bb_p == NULL);
 847                         c->bb_p = c->bb_op;
 848                         c->bb_op += c->bb_c_s8;
 849                 }
 850                 assert(c->bb_p != NULL);
 851                 assert(c->bb_p + c->bb_c_s8 <= c->bb_op);
 852
 853                 c->bb_b = (c->bb_b << 1) + bit;
 854                 c->bb_k++;
 855         }
 856         else
 857         {
 858                 assert(c->bb_p != NULL);
 859                 assert(c->bb_p + c->bb_c_s8 <= c->bb_op);
 860
 861                 bbWriteBits(c);
 862                 c->bb_p = c->bb_op;
 863                 c->bb_op += c->bb_c_s8;
 864                 c->bb_b = bit;
 865                 c->bb_k = 1;
 866         }
 867 }
 868
 869
 870 static void bbPutByte(struct ucl_compress *c, unsigned b)
 871 {
 872         /**printf("putbyte %p %p %x  (%d)\n", op, bb_p, x, bb_k);*/
 873         assert(c->bb_p == NULL || c->bb_p + c->bb_c_s8 <= c->bb_op);
 874         *c->bb_op++ = (uint8_t)(b);
 875 }
 876
 877 static void bbFlushBits(struct ucl_compress *c, unsigned filler_bit)
 878 {
 879         if (c->bb_k > 0)
 880         {
 881                 assert(c->bb_k <= c->bb_c_s);
 882                 while (c->bb_k != c->bb_c_s)
 883                         bbPutBit(c, filler_bit);
 884                 bbWriteBits(c);
 885                 c->bb_k = 0;
 886         }
 887         c->bb_p = NULL;
 888 }
 889
 890
 891
 892 /***********************************************************************
 893 //
 894 ************************************************************************/
 895
 896
 897 static void code_prefix_ss11(struct ucl_compress *c, uint32_t i)
 898 {
 899         if (i >= 2)
 900         {
 901                 uint32_t t = 4;
 902                 i += 2;
 903                 do {
 904                         t <<= 1;
 905                 } while (i >= t);
 906                 t >>= 1;
 907                 do {
 908                         t >>= 1;
 909                         bbPutBit(c, (i & t) ? 1 : 0);
 910                         bbPutBit(c, 0);
 911                 } while (t > 2);
 912         }
 913         bbPutBit(c, (unsigned)i & 1);
 914         bbPutBit(c, 1);
 915 }
 916
 917 static void
 918 code_match(struct ucl_compress *c, unsigned int m_len, const unsigned int m_off)
 919
 920 {
 921         while (m_len > c->conf.max_match)
 922         {
 923                 code_match(c, c->conf.max_match - 3, m_off);
 924                 m_len -= c->conf.max_match - 3;
 925         }
 926
 927         c->match_bytes += m_len;
 928         if (m_len > c->result[3])
 929                 c->result[3] = m_len;
 930         if (m_off > c->result[1])
 931                 c->result[1] = m_off;
 932
 933         bbPutBit(c, 0);
 934
 935         if (m_off == c->last_m_off)
 936         {
 937                 bbPutBit(c, 0);
 938                 bbPutBit(c, 1);
 939         }
 940         else
 941         {
 942                 code_prefix_ss11(c, 1 + ((m_off - 1) >> 8));
 943                 bbPutByte(c, (unsigned)m_off - 1);
 944         }
 945         m_len = m_len - 1 - (m_off > M2_MAX_OFFSET);
 946         if (m_len >= 4)
 947         {
 948                 bbPutBit(c,0);
 949                 bbPutBit(c,0);
 950                 code_prefix_ss11(c, m_len - 4);
 951         }
 952         else
 953         {
 954                 bbPutBit(c, m_len > 1);
 955                 bbPutBit(c, (unsigned)m_len & 1);
 956         }
 957
 958         c->last_m_off = m_off;
 959 }
 960
 961 static void
 962 code_run(struct ucl_compress *c, const uint8_t *ii, unsigned int lit)
 963 {
 964         if (lit == 0)
 965                 return;
 966         c->lit_bytes += lit;
 967         if (lit > c->result[5])
 968                 c->result[5] = lit;
 969         do {
 970                 bbPutBit(c, 1);
 971                 bbPutByte(c, *ii++);
 972         } while (--lit > 0);
 973 }
 974
 975 /***********************************************************************
 976 //
 977 ************************************************************************/
 978
 979 static int
 980 len_of_coded_match(struct ucl_compress *c, unsigned int m_len, unsigned int
 981         m_off)
 982
 983 {
 984         int b;
 985         if (m_len < 2 || (m_len == 2 && (m_off > M2_MAX_OFFSET))
 986                 || m_off > c->conf.max_offset)
 987                 return -1;
 988         assert(m_off > 0);
 989
 990         m_len = m_len - 2 - (m_off > M2_MAX_OFFSET);
 991
 992         if (m_off == c->last_m_off)
 993                 b = 1 + 2;
 994         else
 995         {
 996                 b = 1 + 10;
 997                 m_off = (m_off - 1) >> 8;
 998                 while (m_off > 0)
 999                 {
1000                         b += 2;
1001                         m_off >>= 1;
1002                 }
1003         }
1004
1005         b += 2;
1006         if (m_len < 3)
1007                 return b;
1008         m_len -= 3;
1009
1010         do {
1011                 b += 2;
1012                 m_len >>= 1;
1013         } while (m_len > 0);
1014
1015         return b;
1016 }
1017
1018 int ucl_nrv2b_99_compress(
1019         const uint8_t *in, unsigned long in_len,
1020         uint8_t *out, unsigned long *out_len,
1021         unsigned int *result)
1022 {
1023         const uint8_t *ii;
1024         unsigned int lit;
1025         unsigned int m_len, m_off;
1026         struct ucl_compress c_buffer;
1027         struct ucl_compress * const c = &c_buffer;
1028         struct ucl_swd *swd;
1029         unsigned int result_buffer[16];
1030         int r;
1031
1032 /* max compression */
1033 #define SC_TRY_LAZY    2
1034 #define SC_GOOD_LENGTH F
1035 #define SC_MAX_LAZY    F
1036 #define SC_NICE_LENGTH F
1037 #define SC_MAX_CHAIN   4096
1038 #define SC_FLAGS       1
1039 #define SC_MAX_OFFSET  N
1040
1041         memset(c, 0, sizeof(*c));
1042         c->ip = c->in = in;
1043         c->in_end = in + in_len;
1044         c->out = out;
1045         c->result = result ? result : result_buffer;
1046         memset(c->result, 0, 16*sizeof(*c->result));
1047         c->result[0] = c->result[2] = c->result[4] = UINT_MAX;
1048         result = NULL;
1049         memset(&c->conf, 0xff, sizeof(c->conf));
1050         r = bbConfig(c, ENDIAN, BITSIZE);
1051         if (r == 0)
1052                 r = bbConfig(c, c->conf.bb_endian, c->conf.bb_size);
1053         if (r != 0)
1054                 return UCL_E_INVALID_ARGUMENT;
1055         c->bb_op = out;
1056
1057         ii = c->ip;             /* point to start of literal run */
1058         lit = 0;
1059
1060
1061         swd = (struct ucl_swd *) malloc(sizeof(*swd));
1062         if (!swd)
1063                 return UCL_E_OUT_OF_MEMORY;
1064
1065         swd->f = F;
1066         swd->n = N;
1067         if (in_len >= 256 && in_len < swd->n)
1068                 swd->n = in_len;
1069         if (swd->f < 8 || swd->n < 256)
1070                 return UCL_E_INVALID_ARGUMENT;
1071
1072         r = init_match(c,swd,NULL,0, SC_FLAGS);
1073         if (r != UCL_E_OK)
1074         {
1075                 free(swd);
1076                 return r;
1077         }
1078         if (SC_MAX_CHAIN > 0)
1079                 swd->max_chain = SC_MAX_CHAIN;
1080         if (SC_NICE_LENGTH > 0)
1081                 swd->nice_length = SC_NICE_LENGTH;
1082         if (c->conf.max_match < swd->nice_length)
1083                 swd->nice_length = c->conf.max_match;
1084
1085         c->last_m_off = 1;
1086         r = find_match(c,swd,0,0);
1087         if (r != UCL_E_OK)
1088                 return r;
1089         while (c->look > 0)
1090         {
1091                 unsigned int ahead;
1092                 unsigned int max_ahead;
1093                 int l1, l2;
1094
1095                 c->codesize = c->bb_op - out;
1096
1097                 m_len = c->m_len;
1098                 m_off = c->m_off;
1099
1100                 assert(c->bp == c->ip - c->look);
1101                 assert(c->bp >= in);
1102                 if (lit == 0)
1103                         ii = c->bp;
1104                 assert(ii + lit == c->bp);
1105                 assert(swd->b_char == *(c->bp));
1106
1107                 if (m_len < 2 || (m_len == 2 && (m_off > M2_MAX_OFFSET))
1108                         || m_off > c->conf.max_offset)
1109                 {
1110                         /* a literal */
1111                         lit++;
1112                         swd->max_chain = SC_MAX_CHAIN;
1113                         r = find_match(c,swd,1,0);
1114                         assert(r == 0);
1115                         continue;
1116                 }
1117
1118                 /* a match */
1119                 assert_match(swd,m_len,m_off);
1120
1121                 /* shall we try a lazy match ? */
1122                 ahead = 0;
1123                 if (SC_TRY_LAZY <= 0 || m_len >= SC_MAX_LAZY || m_off ==
1124                         c->last_m_off)
1125
1126                 {
1127                         /* no */
1128                         l1 = 0;
1129                         max_ahead = 0;
1130                 }
1131                 else
1132                 {
1133                         /* yes, try a lazy match */
1134                         l1 = len_of_coded_match(c,m_len,m_off);
1135                         assert(l1 > 0);
1136                         max_ahead = SC_TRY_LAZY;
1137                         if ((m_len - 1) < max_ahead) {
1138                                 max_ahead = m_len -1;
1139                         }
1140                 }
1141
1142                 while (ahead < max_ahead && c->look > m_len)
1143                 {
1144                         if (m_len >= SC_GOOD_LENGTH)
1145                                 swd->max_chain = SC_MAX_CHAIN >> 2;
1146                         else
1147                                 swd->max_chain = SC_MAX_CHAIN;
1148                         r = find_match(c,swd,1,0);
1149                         ahead++;
1150
1151                         assert(r == 0);
1152                         assert(c->look > 0);
1153                         assert(ii + lit + ahead == c->bp);
1154
1155                         if (c->m_len < 2)
1156                                 continue;
1157                         l2 = len_of_coded_match(c,c->m_len,c->m_off);
1158                         if (l2 < 0)
1159                                 continue;
1160                         if (l1 + (int)(ahead + c->m_len - m_len) * 5 > l2 +
1161                                 (int)(ahead) * 9)
1162                         {
1163                                 c->lazy++;
1164                                 assert_match(swd,c->m_len,c->m_off);
1165                                 lit += ahead;
1166                                 assert(ii + lit == c->bp);
1167                                 goto lazy_match_done;
1168                         }
1169                 }
1170
1171                 assert(ii + lit + ahead == c->bp);
1172
1173                 /* 1 - code run */
1174                 code_run(c,ii,lit);
1175                 lit = 0;
1176
1177                 /* 2 - code match */
1178                 code_match(c,m_len,m_off);
1179                 swd->max_chain = SC_MAX_CHAIN;
1180                 r = find_match(c,swd,m_len,1+ahead);
1181                 assert(r == 0);
1182
1183         lazy_match_done: ;
1184         }
1185
1186         /* store final run */
1187         code_run(c,ii,lit);
1188
1189         /* EOF */
1190         bbPutBit(c, 0);
1191         code_prefix_ss11(c, 0x1000000U);
1192         bbPutByte(c, 0xff);
1193
1194         bbFlushBits(c, 0);
1195
1196         assert(c->textsize == in_len);
1197         c->codesize = c->bb_op - out;
1198         *out_len = c->bb_op - out;
1199
1200 #if 0
1201         printf("%7ld %7ld -> %7ld   %7ld %7ld   %ld  (max: %d %d %d)\n",
1202                 (long) c->textsize, (long) in_len, (long) c->codesize,
1203                 c->match_bytes, c->lit_bytes,  c->lazy,
1204                 c->result[1], c->result[3], c->result[5]);
1205 #endif
1206         assert(c->lit_bytes + c->match_bytes == in_len);
1207
1208         swd_exit(swd);
1209         free(swd);
1210
1211         return UCL_E_OK;
1212 }
1213
1214
1215 void Encode(void)  /* compression */
1216 {
1217         uint8_t *in, *out;
1218         unsigned long in_len, out_len;
1219         uint32_t tw;
1220         int r;
1221         fseek(infile, 0, SEEK_END);
1222         in_len = ftell(infile);
1223 #ifdef VERBOSE
1224         if ((signed long)in_len < 0)
1225                 Fprintf((stderr, "Errno: %d", errno));
1226 #endif
1227 #if UCLPACK_COMPAT
1228         {
1229                 uint8_t byte;
1230                 if (fwrite(magic, sizeof(magic), 1, outfile) != 1)
1231                         Error("Can't write.");
1232                 tw = htonl(0); /* flags */
1233                 if (fwrite(&tw, sizeof(tw), 1, outfile) != 1)
1234                         Error("Can't write.");
1235                 byte = 0x2b;            /* method */
1236                 if (fwrite(&byte, sizeof(byte), 1, outfile) != 1)
1237                         Error("Can't write.");
1238                 byte = 10;              /* level */
1239                 if (fwrite(&byte, sizeof(byte), 1, outfile) != 1)
1240                         Error("Can't write.");
1241                 tw = htonl(256*1024);           /* block_size */
1242                 if (fwrite(&tw, sizeof(tw), 1, outfile) != 1)
1243                         Error("Can't write.");
1244                 tw = htonl(in_len);
1245                 if (fwrite(&tw, sizeof(tw), 1, outfile) != 1)
1246                         Error("Can't write.");  /* output size of text */
1247         }
1248 #else
1249         tw = host_to_i86ul(in_len);
1250         if (fwrite(&tw, sizeof(tw), 1, outfile) != 1)
1251                 Error("Can't write.");  /* output size of text */
1252 #endif
1253         if (in_len == 0)
1254                 return;
1255         rewind(infile);
1256
1257         in = malloc(in_len);
1258         out_len = in_len + (in_len/8) + 256;
1259         out = malloc(out_len);
1260         if (!in || !out) {
1261                 Error("Can't malloc");
1262         }
1263         if (fread(in, in_len, 1, infile) != 1) {
1264                 Error("Can't read");
1265         }
1266         r = ucl_nrv2b_99_compress(in, in_len, out, &out_len, 0 );
1267 #if UCLPACK_COMPAT
1268         tw = htonl(out_len);
1269         if (fwrite(&tw, sizeof(tw), 1, outfile) != 1)
1270                 Error("Can't write.");  /* file size of text */
1271
1272 #endif
1273         if (fwrite(out, out_len, 1, outfile) != 1) {
1274                 Error("Write error\n");
1275         }
1276 #if UCLPACK_COMPAT
1277         tw = htonl(0); /* EOF marker */
1278         if (fwrite(&tw, sizeof(tw), 1, outfile) != 1)
1279                 Error("Can't write.");
1280
1281 #endif
1282
1283 #ifdef  LONG_REPORT
1284         Fprintf((stderr, "input size    %ld bytes\n", in_len));
1285         Fprintf((stderr, "output size   %ld bytes\n", out_len));
1286         Fprintf((stderr, "input/output  %.3f\n", (double)in_len / out_len));
1287 #else
1288         Fprintf((stderr, "input/output = %ld/%ld = %.3f\n", in_len, out_len,
1289                 (double)in_len / out_len));
1290 #endif
1291
1292 }
1293
1294 #endif
1295
1296 #ifdef DECODE
1297
1298 #define GETBIT_8(bb, src, ilen) \
1299     (((bb = bb & 0x7f ? bb*2 : ((unsigned)src[ilen++]*2+1)) >> 8) & 1)
1300
1301 #define GETBIT_LE16(bb, src, ilen) \
1302     (bb*=2,bb&0xffff ? (bb>>16)&1 : (ilen+=2,((bb=(src[ilen-2]+src[ilen-1]*256u)*2+1)>>16)&1))
1303
1304 #define GETBIT_LE32(bb, src, ilen) \
1305     (bc > 0 ? ((bb>>--bc)&1) : (bc=31,\
1306     bb=*(const uint32_t *)((src)+ilen),ilen+=4,(bb>>31)&1))
1307
1308 #if ENDIAN == 0 && BITSIZE == 8
1309 #define GETBIT(bb, src, ilen) GETBIT_8(bb, src, ilen)
1310 #endif
1311 #if ENDIAN == 0 && BITSIZE == 16
1312 #define GETBIT(bb, src, ilen) GETBIT_LE16(bb, src, ilen)
1313 #endif
1314 #if ENDIAN == 0 && BITSIZE == 32
1315 #define GETBIT(bb, src, ilen) GETBIT_LE32(bb, src, ilen)
1316 #endif
1317
1318 #ifndef GETBIT
1319 #error "Bad Combination of ENDIAN and BITSIZE values specified"
1320 #endif
1321
1322 #undef SAFE
1323
1324 #ifdef SAFE
1325 #define FAIL(x,r)   if (x) { Error(r); }
1326 #else
1327 #define FAIL(x,r)
1328 #endif
1329
1330 void Decode(void)  /* recover */
1331 {
1332         uint32_t tw;
1333         uint8_t *src, *dst;
1334         unsigned long max_src_len, src_len, dst_len;
1335         unsigned long ilen = 0, olen = 0, last_m_off =  1;
1336         uint32_t bb = 0;
1337         unsigned bc = 0;
1338 #if UCLPACK_COMPAT
1339         if (fseek(infile, sizeof(magic) + sizeof(tw) + 1 + 1 + sizeof(tw),
1340                 SEEK_SET) != 0)
1341
1342                 Error("Seek Error");
1343         if (fread(&tw, sizeof(tw), 1, infile) < 1)
1344                 Error("Can't read"); /* read size of text */
1345         dst_len = ntohl(tw);
1346         if (fread(&tw, sizeof(tw), 1, infile) < 1)
1347                 Error("Can't read"); /* read size of file */
1348         max_src_len = ntohl(tw);
1349 #else
1350         if (fread(&tw, sizeof(tw), 1, infile) < 1)
1351                 Error("Can't read"); /* read size of text */
1352         dst_len = i86ul_to_host(tw);
1353         max_src_len = dst_len + (dst_len/8) + 256;
1354 #endif
1355         if (dst_len == 0)
1356                 return;
1357         dst = malloc(dst_len);
1358         if (!dst)
1359                 Error("Can't malloc");
1360         src = malloc(max_src_len);
1361         if (!src)
1362                 Error("Can't malloc");
1363         src_len = fread(src, 1, max_src_len, infile);
1364         if (src_len <= 0)
1365                 Error("Can't read");
1366
1367         for(;;) {
1368                 unsigned int m_off, m_len;
1369                 while(GETBIT(bb, src, ilen)) {
1370                         FAIL(ilen >= src_len, "input overrun");
1371                         FAIL(olen >= dst_len, "output  overrun");
1372                         dst[olen++] = src[ilen++];
1373                 }
1374                 m_off = 1;
1375                 do {
1376                         m_off = m_off*2 + GETBIT(bb, src, ilen);
1377                         FAIL(ilen >= src_len, "input overrun");
1378                         FAIL(m_off > 0xffffffU +3, "lookbehind overrun");
1379                 } while (!GETBIT(bb, src, ilen));
1380                 if (m_off == 2)
1381                 {
1382                         m_off = last_m_off;
1383                 }
1384                 else
1385                 {
1386                         FAIL(ilen >= src_len, "input overrun");
1387                         m_off = (m_off - 3)*256 + src[ilen++];
1388                         if(m_off == 0xffffffffU)
1389                                 break;
1390                         last_m_off = ++m_off;
1391                 }
1392                 m_len = GETBIT(bb, src, ilen);
1393                 m_len = m_len*2 + GETBIT(bb, src, ilen);
1394                 if (m_len == 0)
1395                 {
1396                         m_len++;
1397                         do {
1398                                 m_len = m_len*2 + GETBIT(bb, src, ilen);
1399                                 FAIL(ilen >= src_len, "input overrun");
1400                                 FAIL(m_len >= dst_len, "output overrun");
1401                         } while(!GETBIT(bb, src, ilen));
1402                         m_len += 2;
1403                 }
1404                 m_len += (m_off > 0xd00);
1405                 FAIL(olen + m_len > dst_len, "output overrun");
1406                 FAIL(m_off > olen, "lookbeind overrun");
1407                 {
1408                         const uint8_t *m_pos;
1409                         m_pos = dst + olen - m_off;
1410                         dst[olen++] = *m_pos++;
1411                         do {
1412                                 dst[olen++] = *m_pos++;
1413                         } while(--m_len > 0);
1414                 }
1415         }
1416         FAIL(ilen < src_len, "input not consumed");
1417         FAIL(ilen > src_len, "input overrun");
1418         assert(ilen == src_len);
1419         Fprintf((stderr, "%12ld\n", olen));
1420         if (dst_len != olen) {
1421                 fprintf(stderr, "length != expected length\n");
1422         }
1423         if (fwrite(dst, olen, 1, outfile) != 1)
1424                 Error("Write error\n");
1425         free(src);
1426         free(dst);
1427 }
1428 #endif
1429
1430 #ifdef MAIN
1431 int main(int argc, char *argv[])
1432 {
1433         char  *s;
1434         FILE  *f;
1435         int    c;
1436
1437         if (argc == 2) {
1438                 outfile = stdout;
1439                 if ((f = tmpfile()) == NULL) {
1440                         perror("tmpfile");
1441                         return EXIT_FAILURE;
1442                 }
1443                 while ((c = getchar()) != EOF)
1444                         fputc(c, f);
1445                 rewind(infile = f);
1446         }
1447         else if (argc != 4) {
1448                 Fprintf((stderr, "'nrv2b e file1 file2' encodes file1 into file2.\n"
1449                         "'nrv2b d file2 file1' decodes file2 into file1.\n"));
1450
1451                 return EXIT_FAILURE;
1452         }
1453         if (argc == 4) {
1454                 if ((s = argv[1], s[1] || strpbrk(s, "DEde") == NULL)
1455                         || (s = argv[2], (infile  = fopen(s, "rb")) == NULL)
1456                         || (s = argv[3], (outfile = fopen(s, "wb")) == NULL)) {
1457                         Fprintf((stderr, "??? %s\n", s));
1458                         return EXIT_FAILURE;
1459                 }
1460         }
1461         if (toupper(*argv[1]) == 'E')
1462                 Encode();
1463         else
1464                 Decode();
1465         fclose(infile);
1466         fclose(outfile);
1467         return EXIT_SUCCESS;
1468 }
1469 #endif