Merged mcb30-realmode-redesign back to HEAD
[people/xl0/gpxe.git] / 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 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 #define SWD_BEST_OFF    1
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         int c = 0;
379
380         if (s->n == 0)
381                 s->n = N;
382         if (s->f == 0)
383                 s->f = F;
384         s->threshold = THRESHOLD;
385         if (s->n > N || s->f > F)
386                 return UCL_E_INVALID_ARGUMENT;
387
388         /* defaults */
389         s->max_chain = SWD_MAX_CHAIN;
390         s->nice_length = s->f;
391         s->use_best_off = 0;
392         s->lazy_insert = 0;
393
394         s->b_size = s->n + s->f;
395         if (s->b_size + s->f >= UINT_MAX)
396                 return UCL_E_ERROR;
397         s->b_wrap = s->b + s->b_size;
398         s->node_count = s->n;
399
400         memset(s->llen3, 0, sizeof(s->llen3[0]) * SWD_HSIZE);
401         for (i = 0; i < 65536U; i++)
402                 s->head2[i] = NIL2;
403
404         s->ip = 0;
405         swd_initdict(s,dict,dict_len);
406         s->bp = s->ip;
407         s->first_rp = s->ip;
408
409         assert(s->ip + s->f <= s->b_size);
410
411         s->look = (unsigned int) (s->c->in_end - s->c->ip);
412         if (s->look > 0)
413         {
414                 if (s->look > s->f)
415                         s->look = s->f;
416                 memcpy(&s->b[s->ip],s->c->ip,s->look);
417                 s->c->ip += s->look;
418                 s->ip += s->look;
419         }
420         if (s->ip == s->b_size)
421                 s->ip = 0;
422
423         if (s->look >= 2 && s->dict_len > 0)
424                 swd_insertdict(s,0,s->dict_len);
425
426         s->rp = s->first_rp;
427         if (s->rp >= s->node_count)
428                 s->rp -= s->node_count;
429         else
430                 s->rp += s->b_size - s->node_count;
431
432         /* unused i */
433         /* unused c */
434         return UCL_E_OK;
435 }
436
437
438 static
439 void swd_exit(struct ucl_swd *s)
440 {
441         /* unused s */
442
443 }
444
445 #define swd_pos2off(s,pos) \
446         (s->bp > (pos) ? s->bp - (pos) : s->b_size - ((pos) - s->bp))
447
448 /***********************************************************************
449 //
450 ************************************************************************/
451
452 static __inline__
453 void swd_getbyte(struct ucl_swd *s)
454 {
455         int c;
456
457         if ((c = getbyte(*(s->c))) < 0)
458         {
459                 if (s->look > 0)
460                         --s->look;
461         }
462         else
463         {
464                 s->b[s->ip] = (uint8_t)(c);
465                 if (s->ip < s->f)
466                         s->b_wrap[s->ip] = (uint8_t)(c);
467         }
468         if (++s->ip == s->b_size)
469                 s->ip = 0;
470         if (++s->bp == s->b_size)
471                 s->bp = 0;
472         if (++s->rp == s->b_size)
473                 s->rp = 0;
474 }
475 /***********************************************************************
476 // remove node from lists
477 ************************************************************************/
478
479 static __inline__
480 void swd_remove_node(struct ucl_swd *s, unsigned int node)
481 {
482         if (s->node_count == 0)
483         {
484                 unsigned int key;
485                 
486 #ifdef UCL_DEBUG
487                 if (s->first_rp != UINT_MAX)
488                 {
489                         if (node != s->first_rp)
490                                 printf("Remove %5d: %5d %5d %5d %5d %6d %6d\n",
491
492                                         node, s->rp, s->ip, s->bp, s->first_rp,
493                                         s->ip - node, s->ip - s->bp);
494                         assert(node == s->first_rp);
495                         s->first_rp = UINT_MAX;
496                 }
497 #endif
498                 
499                 key = HEAD3(s->b,node);
500                 assert(s->llen3[key] > 0);
501                 --s->llen3[key];
502                 
503                 key = HEAD2(s->b,node);
504                 assert(s->head2[key] != NIL2);
505                 if ((unsigned int) s->head2[key] == node)
506                         s->head2[key] = NIL2;
507         }
508         else
509                 --s->node_count;
510 }
511
512
513 /***********************************************************************
514 //
515 ************************************************************************/
516
517
518 static
519 void swd_accept(struct ucl_swd *s, unsigned int n)
520 {
521         assert(n <= s->look);
522
523         if (n > 0) do
524         {
525                 unsigned int key;
526
527                 swd_remove_node(s,s->rp);
528
529                 /* add bp into HEAD3 */
530                 key = HEAD3(s->b,s->bp);
531                 s->succ3[s->bp] = s_head3(s,key);
532                 s->head3[key] = (unsigned int)(s->bp);
533                 s->best3[s->bp] = (unsigned int)(s->f + 1);
534                 s->llen3[key]++;
535                 assert(s->llen3[key] <= s->n);
536
537                 /* add bp into HEAD2 */
538                 key = HEAD2(s->b,s->bp);
539                 s->head2[key] = (unsigned int)(s->bp);
540
541                 swd_getbyte(s);
542         } while (--n > 0);
543 }
544
545 /***********************************************************************
546 //
547 ************************************************************************/
548
549 static
550 void swd_search(struct ucl_swd *s, unsigned int node, unsigned int cnt)
551 {
552         const unsigned char *p1;
553         const unsigned char *p2;
554         const unsigned char *px;
555
556         unsigned int m_len = s->m_len;
557         const unsigned char * b  = s->b;
558         const unsigned char * bp = s->b + s->bp;
559         const unsigned char * bx = s->b + s->bp + s->look;
560         unsigned char scan_end1;
561         
562         assert(s->m_len > 0);
563         
564         scan_end1 = bp[m_len - 1];
565         for ( ; cnt-- > 0; node = s->succ3[node])
566         {
567                 p1 = bp;
568                 p2 = b + node;
569                 px = bx;
570                 
571                 assert(m_len < s->look);
572                 
573                 if (
574                         p2[m_len - 1] == scan_end1 &&
575                         p2[m_len] == p1[m_len] &&
576                         p2[0] == p1[0] &&
577                         p2[1] == p1[1])
578                 {
579                         unsigned int i;
580                         assert(memcmp(bp,&b[node],3) == 0);
581                         
582                         p1 += 2; p2 += 2;
583                         do {} while (++p1 < px && *p1 == *++p2);
584                         i = p1 - bp;
585                         
586 #ifdef UCL_DEBUG
587                         if (memcmp(bp,&b[node],i) != 0)
588                                 printf("%5ld %5ld %02x%02x %02x%02x\n",
589                                         (long)s->bp, (long) node,
590                                         bp[0], bp[1], b[node], b[node+1]);
591 #endif
592                         assert(memcmp(bp,&b[node],i) == 0);
593                         
594 #if defined(SWD_BEST_OFF)
595                         if (i < SWD_BEST_OFF)
596                         {
597                                 if (s->best_pos[i] == 0)
598                                         s->best_pos[i] = node + 1;
599                         }
600 #endif
601                         if (i > m_len)
602                         {
603                                 s->m_len = m_len = i;
604                                 s->m_pos = node;
605                                 if (m_len == s->look)
606                                         return;
607                                 if (m_len >= s->nice_length)
608                                         return;
609                                 if (m_len > (unsigned int) s->best3[node])
610                                         return;
611                                 scan_end1 = bp[m_len - 1];
612                         }
613                 }
614         }
615 }
616
617 static int swd_search2(struct ucl_swd *s)
618 {
619         unsigned int key;
620         
621         assert(s->look >= 2);
622         assert(s->m_len > 0);
623         
624         key = s->head2[ HEAD2(s->b,s->bp) ];
625         if (key == NIL2)
626                 return 0;
627 #ifdef UCL_DEBUG
628         if (memcmp(&s->b[s->bp],&s->b[key],2) != 0)
629                 printf("%5ld %5ld %02x%02x %02x%02x\n", (long)s->bp, (long)key,
630                         s->b[s->bp], s->b[s->bp+1], s->b[key], s->b[key+1]);
631 #endif
632         assert(memcmp(&s->b[s->bp],&s->b[key],2) == 0);
633 #if defined(SWD_BEST_OFF)
634         if (s->best_pos[2] == 0)
635                 s->best_pos[2] = key + 1;
636 #endif
637         
638         if (s->m_len < 2)
639         {
640                 s->m_len = 2;
641                 s->m_pos = key;
642         }
643         return 1;
644 }
645
646 /***********************************************************************
647 //
648 ************************************************************************/
649
650 static
651 void swd_findbest(struct ucl_swd *s)
652 {
653         unsigned int key;
654         unsigned int cnt, node;
655         unsigned int len;
656
657         assert(s->m_len > 0);
658
659         /* get current head, add bp into HEAD3 */
660         key = HEAD3(s->b,s->bp);
661         node = s->succ3[s->bp] = s_head3(s,key);
662         cnt = s->llen3[key]++;
663         assert(s->llen3[key] <= s->n + s->f);
664         if (cnt > s->max_chain && s->max_chain > 0)
665                 cnt = s->max_chain;
666         s->head3[key] = (unsigned int)(s->bp);
667
668         s->b_char = s->b[s->bp];
669         len = s->m_len;
670         if (s->m_len >= s->look)
671         {
672                 if (s->look == 0)
673                         s->b_char = -1;
674                 s->m_off = 0;
675                 s->best3[s->bp] = (unsigned int)(s->f + 1);
676         }
677         else
678         {
679                 if (swd_search2(s))
680                         if (s->look >= 3)
681                                 swd_search(s,node,cnt);
682                 if (s->m_len > len)
683                         s->m_off = swd_pos2off(s,s->m_pos);
684                 s->best3[s->bp] = (unsigned int)(s->m_len);
685
686 #if defined(SWD_BEST_OFF)
687                 if (s->use_best_off)
688                 {
689                         int i;
690                         for (i = 2; i < SWD_BEST_OFF; i++)
691                                 if (s->best_pos[i] > 0)
692                                         s->best_off[i] =
693                                                 swd_pos2off(s,s->best_pos[i]-1);
694
695                                 else
696                                         s->best_off[i] = 0;
697                 }
698 #endif
699         }
700
701         swd_remove_node(s,s->rp);
702
703         /* add bp into HEAD2 */
704         key = HEAD2(s->b,s->bp);
705         s->head2[key] = (unsigned int)(s->bp);
706 }
707
708
709 /***********************************************************************
710 //
711 ************************************************************************/
712
713 static int
714 init_match ( struct ucl_compress *c, struct ucl_swd *s,
715         const uint8_t *dict, unsigned int dict_len,
716         uint32_t flags )
717 {
718         int r;
719         
720         assert(!c->init);
721         c->init = 1;
722         
723         s->c = c;
724         
725         c->last_m_len = c->last_m_off = 0;
726         
727         c->textsize = c->codesize = c->printcount = 0;
728         c->lit_bytes = c->match_bytes = c->rep_bytes = 0;
729         c->lazy = 0;
730         
731         r = swd_init(s,dict,dict_len);
732         if (r != UCL_E_OK)
733         {
734                 swd_exit(s);
735                 return r;
736         }
737         
738         s->use_best_off = (flags & 1) ? 1 : 0;
739         return UCL_E_OK;
740 }
741
742 static int
743 find_match ( struct ucl_compress *c, struct ucl_swd *s,
744         unsigned int this_len, unsigned int skip )
745 {
746         assert(c->init);
747         
748         if (skip > 0)
749         {
750                 assert(this_len >= skip);
751                 swd_accept(s, this_len - skip);
752                 c->textsize += this_len - skip + 1;
753         }
754         else
755         {
756                 assert(this_len <= 1);
757                 c->textsize += this_len - skip;
758         }
759         
760         s->m_len = THRESHOLD;
761 #ifdef SWD_BEST_OFF
762         if (s->use_best_off)
763                 memset(s->best_pos,0,sizeof(s->best_pos));
764 #endif
765         swd_findbest(s);
766         c->m_len = s->m_len;
767         c->m_off = s->m_off;
768         
769         swd_getbyte(s);
770         
771         if (s->b_char < 0)
772         {
773                 c->look = 0;
774                 c->m_len = 0;
775                 swd_exit(s);
776         }
777         else
778         {
779                 c->look = s->look + 1;
780         }
781         c->bp = c->ip - c->look;
782         
783 #if 0
784         /* brute force match search */
785         if (c->m_len > THRESHOLD && c->m_len + 1 <= c->look)
786         {
787                 const uint8_t *ip = c->bp;
788                 const uint8_t *m  = c->bp - c->m_off;
789                 const uint8_t *in = c->in;
790                 
791                 if (ip - in > N)
792                         in = ip - N;
793                 for (;;)
794                 {
795                         while (*in != *ip)
796                                 in++;
797                         if (in == ip)
798                                 break;
799                         if (in != m)
800                                 if (memcmp(in,ip,c->m_len+1) == 0)
801                                         printf("%p %p %p %5d\n",in,ip,m,c->m_len);
802
803                         in++;
804                 }
805         }
806 #endif
807         
808         return UCL_E_OK;
809 }
810
811
812 static int bbConfig(struct ucl_compress *c, int endian, int bitsize)
813 {
814         if (endian != -1)
815         {
816                 if (endian != 0)
817                         return UCL_E_ERROR;
818                 c->bb_c_endian = endian;
819         }
820         if (bitsize != -1)
821         {
822                 if (bitsize != 8 && bitsize != 16 && bitsize != 32 && bitsize != 64)
823                         return UCL_E_ERROR;
824                 c->bb_c_s = bitsize;
825                 c->bb_c_s8 = bitsize / 8;
826         }
827         c->bb_b = 0; c->bb_k = 0;
828         c->bb_p = NULL;
829         c->bb_op = NULL;
830         return UCL_E_OK;
831 }
832
833 static void bbWriteBits(struct ucl_compress *c)
834 {
835         uint8_t *p = c->bb_p;
836         uint64_t b = c->bb_b;
837
838         p[0] = (uint8_t)(b >>  0);
839         if (c->bb_c_s >= 16)
840         {
841                 p[1] = (uint8_t)(b >>  8);
842                 if (c->bb_c_s >= 32)
843                 {
844                         p[2] = (uint8_t)(b >> 16);
845                         p[3] = (uint8_t)(b >> 24);
846                         if (c->bb_c_s == 64)
847                         {
848                                 p[4] = (uint8_t)(b >> 32);
849                                 p[5] = (uint8_t)(b >> 40);
850                                 p[6] = (uint8_t)(b >> 48);
851                                 p[7] = (uint8_t)(b >> 56);
852                         }
853                 }
854         }
855 }
856
857
858 static void bbPutBit(struct ucl_compress *c, unsigned bit)
859 {
860         assert(bit == 0 || bit == 1);
861         assert(c->bb_k <= c->bb_c_s);
862
863         if (c->bb_k < c->bb_c_s)
864         {
865                 if (c->bb_k == 0)
866                 {
867                         assert(c->bb_p == NULL);
868                         c->bb_p = c->bb_op;
869                         c->bb_op += c->bb_c_s8;
870                 }
871                 assert(c->bb_p != NULL);
872                 assert(c->bb_p + c->bb_c_s8 <= c->bb_op);
873
874                 c->bb_b = (c->bb_b << 1) + bit;
875                 c->bb_k++;
876         }
877         else
878         {
879                 assert(c->bb_p != NULL);
880                 assert(c->bb_p + c->bb_c_s8 <= c->bb_op);
881
882                 bbWriteBits(c);
883                 c->bb_p = c->bb_op;
884                 c->bb_op += c->bb_c_s8;
885                 c->bb_b = bit;
886                 c->bb_k = 1;
887         }
888 }
889
890
891 static void bbPutByte(struct ucl_compress *c, unsigned b)
892 {
893         /**printf("putbyte %p %p %x  (%d)\n", op, bb_p, x, bb_k);*/
894         assert(c->bb_p == NULL || c->bb_p + c->bb_c_s8 <= c->bb_op);
895         *c->bb_op++ = (uint8_t)(b);
896 }
897
898 static void bbFlushBits(struct ucl_compress *c, unsigned filler_bit)
899 {
900         if (c->bb_k > 0)
901         {
902                 assert(c->bb_k <= c->bb_c_s);
903                 while (c->bb_k != c->bb_c_s)
904                         bbPutBit(c, filler_bit);
905                 bbWriteBits(c);
906                 c->bb_k = 0;
907         }
908         c->bb_p = NULL;
909 }
910
911
912
913 /***********************************************************************
914 //
915 ************************************************************************/
916
917
918 static void code_prefix_ss11(struct ucl_compress *c, uint32_t i)
919 {
920         if (i >= 2)
921         {
922                 uint32_t t = 4;
923                 i += 2;
924                 do {
925                         t <<= 1;
926                 } while (i >= t);
927                 t >>= 1;
928                 do {
929                         t >>= 1;
930                         bbPutBit(c, (i & t) ? 1 : 0);
931                         bbPutBit(c, 0);
932                 } while (t > 2);
933         }
934         bbPutBit(c, (unsigned)i & 1);
935         bbPutBit(c, 1);
936 }
937
938 static void
939 code_match(struct ucl_compress *c, unsigned int m_len, const unsigned int m_off)
940
941 {
942         while (m_len > c->conf.max_match)
943         {
944                 code_match(c, c->conf.max_match - 3, m_off);
945                 m_len -= c->conf.max_match - 3;
946         }
947         
948         c->match_bytes += m_len;
949         if (m_len > c->result[3])
950                 c->result[3] = m_len;
951         if (m_off > c->result[1])
952                 c->result[1] = m_off;
953
954         bbPutBit(c, 0);
955
956         if (m_off == c->last_m_off)
957         {
958                 bbPutBit(c, 0);
959                 bbPutBit(c, 1);
960         }
961         else
962         {
963                 code_prefix_ss11(c, 1 + ((m_off - 1) >> 8));
964                 bbPutByte(c, (unsigned)m_off - 1);
965         }
966         m_len = m_len - 1 - (m_off > M2_MAX_OFFSET);
967         if (m_len >= 4)
968         {
969                 bbPutBit(c,0);
970                 bbPutBit(c,0);
971                 code_prefix_ss11(c, m_len - 4);
972         }
973         else
974         {
975                 bbPutBit(c, m_len > 1);
976                 bbPutBit(c, (unsigned)m_len & 1);
977         }
978
979         c->last_m_off = m_off;
980 }
981
982 static void
983 code_run(struct ucl_compress *c, const uint8_t *ii, unsigned int lit)
984 {
985         if (lit == 0)
986                 return;
987         c->lit_bytes += lit;
988         if (lit > c->result[5])
989                 c->result[5] = lit;
990         do {
991                 bbPutBit(c, 1);
992                 bbPutByte(c, *ii++);
993         } while (--lit > 0);
994 }
995
996 /***********************************************************************
997 //
998 ************************************************************************/
999
1000 static int
1001 len_of_coded_match(struct ucl_compress *c, unsigned int m_len, unsigned int
1002         m_off)
1003
1004 {
1005         int b;
1006         if (m_len < 2 || (m_len == 2 && (m_off > M2_MAX_OFFSET))
1007                 || m_off > c->conf.max_offset)
1008                 return -1;
1009         assert(m_off > 0);
1010         
1011         m_len = m_len - 2 - (m_off > M2_MAX_OFFSET);
1012         
1013         if (m_off == c->last_m_off)
1014                 b = 1 + 2;
1015         else
1016         {
1017                 b = 1 + 10;
1018                 m_off = (m_off - 1) >> 8;
1019                 while (m_off > 0)
1020                 {
1021                         b += 2;
1022                         m_off >>= 1;
1023                 }
1024         }
1025
1026         b += 2;
1027         if (m_len < 3)
1028                 return b;
1029         m_len -= 3;
1030
1031         do {
1032                 b += 2;
1033                 m_len >>= 1;
1034         } while (m_len > 0);
1035
1036         return b;
1037 }
1038
1039 int ucl_nrv2b_99_compress(
1040         const uint8_t *in, unsigned long in_len,
1041         uint8_t *out, unsigned long *out_len,
1042         unsigned int *result)
1043 {
1044         const uint8_t *ii;
1045         unsigned int lit;
1046         unsigned int m_len, m_off;
1047         struct ucl_compress c_buffer;
1048         struct ucl_compress * const c = &c_buffer;
1049         struct ucl_swd *swd;
1050         unsigned int result_buffer[16];
1051         int r;
1052
1053 /* max compression */
1054 #define SC_TRY_LAZY    2
1055 #define SC_GOOD_LENGTH F
1056 #define SC_MAX_LAZY    F
1057 #define SC_NICE_LENGTH F
1058 #define SC_MAX_CHAIN   4096
1059 #define SC_FLAGS       1
1060 #define SC_MAX_OFFSET  N
1061         
1062         memset(c, 0, sizeof(*c));
1063         c->ip = c->in = in;
1064         c->in_end = in + in_len;
1065         c->out = out;
1066         c->result = result ? result : result_buffer;
1067         memset(c->result, 0, 16*sizeof(*c->result));
1068         c->result[0] = c->result[2] = c->result[4] = UINT_MAX;
1069         result = NULL;
1070         memset(&c->conf, 0xff, sizeof(c->conf));
1071         r = bbConfig(c, ENDIAN, BITSIZE);
1072         if (r == 0)
1073                 r = bbConfig(c, c->conf.bb_endian, c->conf.bb_size);
1074         if (r != 0)
1075                 return UCL_E_INVALID_ARGUMENT;
1076         c->bb_op = out;
1077         
1078         ii = c->ip;             /* point to start of literal run */
1079         lit = 0;
1080         
1081
1082         swd = (struct ucl_swd *) malloc(sizeof(*swd));
1083         if (!swd)
1084                 return UCL_E_OUT_OF_MEMORY;
1085
1086         swd->f = F;
1087         swd->n = N;
1088         if (in_len >= 256 && in_len < swd->n)
1089                 swd->n = in_len;
1090         if (swd->f < 8 || swd->n < 256)
1091                 return UCL_E_INVALID_ARGUMENT;
1092
1093         r = init_match(c,swd,NULL,0, SC_FLAGS);
1094         if (r != UCL_E_OK)
1095         {
1096                 free(swd);
1097                 return r;
1098         }
1099         if (SC_MAX_CHAIN > 0)
1100                 swd->max_chain = SC_MAX_CHAIN;
1101         if (SC_NICE_LENGTH > 0)
1102                 swd->nice_length = SC_NICE_LENGTH;
1103         if (c->conf.max_match < swd->nice_length)
1104                 swd->nice_length = c->conf.max_match;
1105         
1106         c->last_m_off = 1;
1107         r = find_match(c,swd,0,0);
1108         if (r != UCL_E_OK)
1109                 return r;
1110         while (c->look > 0)
1111         {
1112                 unsigned int ahead;
1113                 unsigned int max_ahead;
1114                 int l1, l2;
1115                 
1116                 c->codesize = c->bb_op - out;
1117                 
1118                 m_len = c->m_len;
1119                 m_off = c->m_off;
1120                 
1121                 assert(c->bp == c->ip - c->look);
1122                 assert(c->bp >= in);
1123                 if (lit == 0)
1124                         ii = c->bp;
1125                 assert(ii + lit == c->bp);
1126                 assert(swd->b_char == *(c->bp));
1127                 
1128                 if (m_len < 2 || (m_len == 2 && (m_off > M2_MAX_OFFSET))
1129                         || m_off > c->conf.max_offset)
1130                 {
1131                         /* a literal */
1132                         lit++;
1133                         swd->max_chain = SC_MAX_CHAIN;
1134                         r = find_match(c,swd,1,0);
1135                         assert(r == 0);
1136                         continue;
1137                 }
1138                 
1139                 /* a match */
1140                 assert_match(swd,m_len,m_off);
1141                 
1142                 /* shall we try a lazy match ? */
1143                 ahead = 0;
1144                 if (SC_TRY_LAZY <= 0 || m_len >= SC_MAX_LAZY || m_off ==
1145                         c->last_m_off)
1146
1147                 {
1148                         /* no */
1149                         l1 = 0;
1150                         max_ahead = 0;
1151                 }
1152                 else
1153                 {
1154                         /* yes, try a lazy match */
1155                         l1 = len_of_coded_match(c,m_len,m_off);
1156                         assert(l1 > 0);
1157                         max_ahead = SC_TRY_LAZY;
1158                         if ((m_len - 1) < max_ahead) {
1159                                 max_ahead = m_len -1;
1160                         }
1161                 }
1162                 
1163                 while (ahead < max_ahead && c->look > m_len)
1164                 {
1165                         if (m_len >= SC_GOOD_LENGTH)
1166                                 swd->max_chain = SC_MAX_CHAIN >> 2;
1167                         else
1168                                 swd->max_chain = SC_MAX_CHAIN;
1169                         r = find_match(c,swd,1,0);
1170                         ahead++;
1171                         
1172                         assert(r == 0);
1173                         assert(c->look > 0);
1174                         assert(ii + lit + ahead == c->bp);
1175                         
1176                         if (c->m_len < 2)
1177                                 continue;
1178                         l2 = len_of_coded_match(c,c->m_len,c->m_off);
1179                         if (l2 < 0)
1180                                 continue;
1181                         if (l1 + (int)(ahead + c->m_len - m_len) * 5 > l2 +
1182                                 (int)(ahead) * 9)
1183                         {
1184                                 c->lazy++;
1185                                 assert_match(swd,c->m_len,c->m_off);
1186                                 lit += ahead;
1187                                 assert(ii + lit == c->bp);
1188                                 goto lazy_match_done;
1189                         }
1190                 }
1191                 
1192                 assert(ii + lit + ahead == c->bp);
1193                 
1194                 /* 1 - code run */
1195                 code_run(c,ii,lit);
1196                 lit = 0;
1197                 
1198                 /* 2 - code match */
1199                 code_match(c,m_len,m_off);
1200                 swd->max_chain = SC_MAX_CHAIN;
1201                 r = find_match(c,swd,m_len,1+ahead);
1202                 assert(r == 0);
1203                 
1204         lazy_match_done: ;
1205         }
1206         
1207         /* store final run */
1208         code_run(c,ii,lit);
1209         
1210         /* EOF */
1211         bbPutBit(c, 0);
1212         code_prefix_ss11(c, 0x1000000U);
1213         bbPutByte(c, 0xff);
1214
1215         bbFlushBits(c, 0);
1216         
1217         assert(c->textsize == in_len);
1218         c->codesize = c->bb_op - out;
1219         *out_len = c->bb_op - out;
1220         
1221 #if 0
1222         printf("%7ld %7ld -> %7ld   %7ld %7ld   %ld  (max: %d %d %d)\n",
1223                 (long) c->textsize, (long) in_len, (long) c->codesize,
1224                 c->match_bytes, c->lit_bytes,  c->lazy,
1225                 c->result[1], c->result[3], c->result[5]);
1226 #endif
1227         assert(c->lit_bytes + c->match_bytes == in_len);
1228         
1229         swd_exit(swd);
1230         free(swd);
1231
1232         return UCL_E_OK;
1233 }
1234
1235
1236 void Encode(void)  /* compression */
1237 {
1238         uint8_t *in, *out;
1239         unsigned long in_len, out_len;
1240         uint32_t tw;
1241         int r;
1242         fseek(infile, 0, SEEK_END);
1243         in_len = ftell(infile);
1244 #ifdef VERBOSE
1245         if ((signed long)in_len < 0)
1246                 Fprintf((stderr, "Errno: %d", errno));
1247 #endif
1248 #if UCLPACK_COMPAT
1249         {
1250                 uint8_t byte;
1251                 if (fwrite(magic, sizeof(magic), 1, outfile) != 1)
1252                         Error("Can't write.");
1253                 tw = htonl(0); /* flags */
1254                 if (fwrite(&tw, sizeof(tw), 1, outfile) != 1)
1255                         Error("Can't write.");
1256                 byte = 0x2b;            /* method */
1257                 if (fwrite(&byte, sizeof(byte), 1, outfile) != 1)
1258                         Error("Can't write.");
1259                 byte = 10;              /* level */
1260                 if (fwrite(&byte, sizeof(byte), 1, outfile) != 1)
1261                         Error("Can't write.");
1262                 tw = htonl(256*1024);           /* block_size */
1263                 if (fwrite(&tw, sizeof(tw), 1, outfile) != 1)
1264                         Error("Can't write.");
1265                 tw = htonl(in_len);
1266                 if (fwrite(&tw, sizeof(tw), 1, outfile) != 1)
1267                         Error("Can't write.");  /* output size of text */
1268         }
1269 #else
1270         tw = host_to_i86ul(in_len);
1271         if (fwrite(&tw, sizeof(tw), 1, outfile) != 1)
1272                 Error("Can't write.");  /* output size of text */
1273 #endif  
1274         if (in_len == 0)
1275                 return;
1276         rewind(infile);
1277
1278         in = malloc(in_len);
1279         out_len = in_len + (in_len/8) + 256;
1280         out = malloc(out_len);
1281         if (!in || !out) {
1282                 Error("Can't malloc");
1283         }
1284         if (fread(in, in_len, 1, infile) != 1) {
1285                 Error("Can't read");
1286         }
1287         r = ucl_nrv2b_99_compress(in, in_len, out, &out_len, 0 );
1288         if (r != UCL_E_OK)
1289                 Error("Compression failure\n");
1290 #if UCLPACK_COMPAT
1291         tw = htonl(out_len);
1292         if (fwrite(&tw, sizeof(tw), 1, outfile) != 1)
1293                 Error("Can't write.");  /* file size of text */
1294
1295 #endif
1296         if (fwrite(out, out_len, 1, outfile) != 1) {
1297                 Error("Write error\n");
1298         }
1299 #if UCLPACK_COMPAT
1300         tw = htonl(0); /* EOF marker */
1301         if (fwrite(&tw, sizeof(tw), 1, outfile) != 1)
1302                 Error("Can't write.");
1303
1304 #endif
1305
1306 #ifdef  LONG_REPORT
1307         Fprintf((stdout, "input size    %ld bytes\n", in_len));
1308         Fprintf((stdout, "output size   %ld bytes\n", out_len));
1309         Fprintf((stdout, "input/output  %.3f\n", (double)in_len / out_len));
1310 #else
1311         Fprintf((stdout, "input/output = %ld/%ld = %.3f\n", in_len, out_len,
1312                 (double)in_len / out_len));
1313 #endif
1314         
1315 }
1316
1317 #endif
1318
1319 #ifdef DECODE
1320
1321 #define GETBIT_8(bb, src, ilen) \
1322     (((bb = bb & 0x7f ? bb*2 : ((unsigned)src[ilen++]*2+1)) >> 8) & 1)
1323
1324 #define GETBIT_LE16(bb, src, ilen) \
1325     (bb*=2,bb&0xffff ? (bb>>16)&1 : (ilen+=2,((bb=(src[ilen-2]+src[ilen-1]*256u)*2+1)>>16)&1))
1326
1327 #define GETBIT_LE32(bb, src, ilen) \
1328     (bc > 0 ? ((bb>>--bc)&1) : (bc=31,\
1329     bb=*(const uint32_t *)((src)+ilen),ilen+=4,(bb>>31)&1))
1330
1331 #define GETBIT_LE64(bb, src, ilen) \
1332     (bc > 0 ? ((bb>>--bc)&1) : (bc=63, \
1333     bb=*(const uint64_t *)((src)+ilen),ilen+=8,(bb>>63)&1))
1334
1335 #if ENDIAN == 0 && BITSIZE == 8
1336 #define GETBIT(bb, src, ilen) GETBIT_8(bb, src, ilen)
1337 #endif
1338 #if ENDIAN == 0 && BITSIZE == 16
1339 #define GETBIT(bb, src, ilen) GETBIT_LE16(bb, src, ilen)
1340 #endif
1341 #if ENDIAN == 0 && BITSIZE == 32
1342 #define GETBIT(bb, src, ilen) GETBIT_LE32(bb, src, ilen)
1343 #endif
1344 #if ENDIAN == 0 && BITSIZE == 64
1345 #define GETBIT(bb, src, ilen) GETBIT_LE64(bb, src, ilen)
1346 #endif
1347 #ifndef GETBIT
1348 #error "Bad Combination of ENDIAN and BITSIZE values specified"
1349 #endif
1350
1351 #undef SAFE
1352
1353 #ifdef SAFE
1354 #define FAIL(x,r)   if (x) { Error(r); }
1355 #else
1356 #define FAIL(x,r)
1357 #endif
1358
1359 void Decode(void)  /* recover */
1360 {
1361         uint32_t tw;
1362         uint8_t *src, *dst;
1363         unsigned long max_src_len, src_len, dst_len;
1364         unsigned long ilen = 0, olen = 0, last_m_off =  1;
1365 #if BITSIZE <= 32
1366         uint32_t bb = 0;
1367 #elif BITSIZE == 64
1368         uint64_t bb = 0;
1369 #endif
1370         unsigned bc = 0;
1371 #if UCLPACK_COMPAT
1372         if (fseek(infile, sizeof(magic) + sizeof(tw) + 1 + 1 + sizeof(tw),
1373                 SEEK_SET) != 0)
1374
1375                 Error("Seek Error");
1376         if (fread(&tw, sizeof(tw), 1, infile) < 1)
1377                 Error("Can't read"); /* read size of text */
1378         dst_len = ntohl(tw);
1379         if (fread(&tw, sizeof(tw), 1, infile) < 1)
1380                 Error("Can't read"); /* read size of file */
1381         max_src_len = ntohl(tw);
1382 #else
1383         if (fread(&tw, sizeof(tw), 1, infile) < 1)
1384                 Error("Can't read"); /* read size of text */
1385         dst_len = i86ul_to_host(tw);
1386         max_src_len = dst_len + (dst_len/8) + 256;
1387 #endif
1388         if (dst_len == 0)
1389                 return;
1390         dst = malloc(dst_len);
1391         if (!dst)
1392                 Error("Can't malloc");
1393         src = malloc(max_src_len);
1394         if (!src)
1395                 Error("Can't malloc");
1396         src_len = fread(src, 1, max_src_len, infile);
1397         if (src_len <= 0) 
1398                 Error("Can't read");
1399
1400         for(;;) {
1401                 unsigned int m_off, m_len;
1402                 while(GETBIT(bb, src, ilen)) {
1403                         FAIL(ilen >= src_len, "input overrun");
1404                         FAIL(olen >= dst_len, "output  overrun");
1405                         dst[olen++] = src[ilen++];
1406                 }
1407                 m_off = 1;
1408                 do {
1409                         m_off = m_off*2 + GETBIT(bb, src, ilen);
1410                         FAIL(ilen >= src_len, "input overrun");
1411                         FAIL(m_off > 0xffffffU +3, "lookbehind overrun");
1412                 } while (!GETBIT(bb, src, ilen));
1413                 if (m_off == 2)
1414                 {
1415                         m_off = last_m_off;
1416                 }
1417                 else
1418                 {
1419                         FAIL(ilen >= src_len, "input overrun");
1420                         m_off = (m_off - 3)*256 + src[ilen++];
1421                         if (m_off == 0xffffffffU)
1422                                 break;
1423                         last_m_off = ++m_off;
1424                 }
1425                 m_len = GETBIT(bb, src, ilen);
1426                 m_len = m_len*2 + GETBIT(bb, src, ilen);
1427                 if (m_len == 0) 
1428                 {
1429                         m_len++;
1430                         do {
1431                                 m_len = m_len*2 + GETBIT(bb, src, ilen);
1432                                 FAIL(ilen >= src_len, "input overrun");
1433                                 FAIL(m_len >= dst_len, "output overrun");
1434                         } while(!GETBIT(bb, src, ilen));
1435                         m_len += 2;
1436                 }
1437                 m_len += (m_off > 0xd00);
1438                 FAIL(olen + m_len > dst_len, "output overrun");
1439                 FAIL(m_off > olen, "lookbeind overrun");
1440                 {
1441                         const uint8_t *m_pos;
1442                         m_pos = dst + olen - m_off;
1443                         dst[olen++] = *m_pos++;
1444                         do {
1445                                 dst[olen++] = *m_pos++;
1446                         } while(--m_len > 0);
1447                 }
1448         }
1449         FAIL(ilen < src_len, "input not consumed");
1450         FAIL(ilen > src_len, "input overrun");
1451         assert(ilen == src_len);
1452         Fprintf((stderr, "%12ld\n", olen));
1453         if (dst_len != olen) {
1454                 fprintf(stderr, "length != expected length\n");
1455         }
1456         if (fwrite(dst, olen, 1, outfile) != 1)
1457                 Error("Write error\n");
1458         free(src);
1459         free(dst);
1460 }
1461 #endif
1462
1463 #ifdef MAIN
1464 int main(int argc, char *argv[])
1465 {
1466         char  *s;
1467         FILE  *f;
1468         int    c;
1469         
1470         if (argc == 2) {
1471                 outfile = stdout;
1472                 if ((f = tmpfile()) == NULL) {
1473                         perror("tmpfile");
1474                         return EXIT_FAILURE;
1475                 }
1476                 while ((c = getchar()) != EOF)
1477                         fputc(c, f);
1478                 rewind(infile = f);
1479         }
1480         else if (argc != 4) {
1481                 Fprintf((stderr, "'nrv2b e file1 file2' encodes file1 into file2.\n"
1482                         "'nrv2b d file2 file1' decodes file2 into file1.\n"));
1483                 return EXIT_FAILURE;
1484         }
1485         if (argc == 4) {
1486                 if ((s = argv[1], s[1] || strpbrk(s, "DEde") == NULL)
1487                         || (s = argv[2], (infile  = fopen(s, "rb")) == NULL)
1488                         || (s = argv[3], (outfile = fopen(s, "wb")) == NULL)) {
1489                         Fprintf((stderr, "??? %s\n", s));
1490                         return EXIT_FAILURE;
1491                 }
1492         }
1493         if (toupper(*argv[1]) == 'E')
1494                 Encode();
1495         else
1496                 Decode();
1497         fclose(infile);
1498         fclose(outfile);
1499         return EXIT_SUCCESS;
1500 }
1501 #endif