← Back to branch summary

~pmdj/ubuntu/trusty/qemu/2.9+applesmc+fadtv3

« back to all changes in this revision

Viewing changes to roms/ipxe/src/util/nrv2b.c

  • Committer: Phil Dennis-Jordan
  • Date: 2017-07-21 08:03:43 UTC
  • mfrom: (1.1.1)
  • Revision ID: phil@philjordan.eu-20170721080343-2yr2vdj7713czahv
New upstream release 2.9.0.

Show diffs side-by-side

added added

removed removed

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