VirtualBox

source: vbox/trunk/src/VBox/Devices/PC/Etherboot-src/util/nrv2b.c@ 46355

Last change on this file since 46355 was 43804, checked in by vboxsync, 12 years ago

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

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette