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