VirtualBox

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

最後變更 在這個檔案從26594是 3694,由 vboxsync 提交於 17 年 前

WIN -> RT_OS_WINDOWS
  • 屬性 svn:eol-style 設為 native
  • 屬性 svn:keywords 設為 Author Date Id Revision
檔案大小: 31.1 KB
行 
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 <[email protected]>
9 1997-01-27
10
11 Modifications to allow use as a filter by Ken Yap
12 <[email protected]>.
13
14 1997-07-01
15
16 Small mod to cope with running on big-endian machines
17 by Jim Hague <[email protected])
18 1998-02-06
19
20 Make compression statistics report shorter
21 by Ken Yap <[email protected]>.
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 <[email protected]>.
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 return UCL_E_INVALID_ARGUMENT;
1106
1107 r = init_match(c,swd,NULL,0, SC_FLAGS);
1108 if (r != UCL_E_OK)
1109 {
1110 free(swd);
1111 return r;
1112 }
1113 if (SC_MAX_CHAIN > 0)
1114 swd->max_chain = SC_MAX_CHAIN;
1115 if (SC_NICE_LENGTH > 0)
1116 swd->nice_length = SC_NICE_LENGTH;
1117 if (c->conf.max_match < swd->nice_length)
1118 swd->nice_length = c->conf.max_match;
1119
1120 c->last_m_off = 1;
1121 r = find_match(c,swd,0,0);
1122 if (r != UCL_E_OK)
1123 return r;
1124 while (c->look > 0)
1125 {
1126 unsigned int ahead;
1127 unsigned int max_ahead;
1128 int l1, l2;
1129
1130 c->codesize = c->bb_op - out;
1131
1132 m_len = c->m_len;
1133 m_off = c->m_off;
1134
1135 assert(c->bp == c->ip - c->look);
1136 assert(c->bp >= in);
1137 if (lit == 0)
1138 ii = c->bp;
1139 assert(ii + lit == c->bp);
1140 assert(swd->b_char == *(c->bp));
1141
1142 if (m_len < 2 || (m_len == 2 && (m_off > M2_MAX_OFFSET))
1143 || m_off > c->conf.max_offset)
1144 {
1145 /* a literal */
1146 lit++;
1147 swd->max_chain = SC_MAX_CHAIN;
1148 r = find_match(c,swd,1,0);
1149 assert(r == 0);
1150 continue;
1151 }
1152
1153 /* a match */
1154 assert_match(swd,m_len,m_off);
1155
1156 /* shall we try a lazy match ? */
1157 ahead = 0;
1158 if (SC_TRY_LAZY <= 0 || m_len >= SC_MAX_LAZY || m_off ==
1159 c->last_m_off)
1160
1161 {
1162 /* no */
1163 l1 = 0;
1164 max_ahead = 0;
1165 }
1166 else
1167 {
1168 /* yes, try a lazy match */
1169 l1 = len_of_coded_match(c,m_len,m_off);
1170 assert(l1 > 0);
1171 max_ahead = SC_TRY_LAZY;
1172 if ((m_len - 1) < max_ahead) {
1173 max_ahead = m_len -1;
1174 }
1175 }
1176
1177 while (ahead < max_ahead && c->look > m_len)
1178 {
1179 if (m_len >= SC_GOOD_LENGTH)
1180 swd->max_chain = SC_MAX_CHAIN >> 2;
1181 else
1182 swd->max_chain = SC_MAX_CHAIN;
1183 r = find_match(c,swd,1,0);
1184 ahead++;
1185
1186 assert(r == 0);
1187 assert(c->look > 0);
1188 assert(ii + lit + ahead == c->bp);
1189
1190 if (c->m_len < 2)
1191 continue;
1192 l2 = len_of_coded_match(c,c->m_len,c->m_off);
1193 if (l2 < 0)
1194 continue;
1195 if (l1 + (int)(ahead + c->m_len - m_len) * 5 > l2 +
1196 (int)(ahead) * 9)
1197 {
1198 c->lazy++;
1199 assert_match(swd,c->m_len,c->m_off);
1200 lit += ahead;
1201 assert(ii + lit == c->bp);
1202 goto lazy_match_done;
1203 }
1204 }
1205
1206 assert(ii + lit + ahead == c->bp);
1207
1208 /* 1 - code run */
1209 code_run(c,ii,lit);
1210 lit = 0;
1211
1212 /* 2 - code match */
1213 code_match(c,m_len,m_off);
1214 swd->max_chain = SC_MAX_CHAIN;
1215 r = find_match(c,swd,m_len,1+ahead);
1216 assert(r == 0);
1217
1218 lazy_match_done: ;
1219 }
1220
1221 /* store final run */
1222 code_run(c,ii,lit);
1223
1224 /* EOF */
1225 bbPutBit(c, 0);
1226 code_prefix_ss11(c, 0x1000000U);
1227 bbPutByte(c, 0xff);
1228
1229 bbFlushBits(c, 0);
1230
1231 assert(c->textsize == in_len);
1232 c->codesize = c->bb_op - out;
1233 *out_len = c->bb_op - out;
1234
1235#if 0
1236 printf("%7ld %7ld -> %7ld %7ld %7ld %ld (max: %d %d %d)\n",
1237 (long) c->textsize, (long) in_len, (long) c->codesize,
1238 c->match_bytes, c->lit_bytes, c->lazy,
1239 c->result[1], c->result[3], c->result[5]);
1240#endif
1241 assert(c->lit_bytes + c->match_bytes == in_len);
1242
1243 swd_exit(swd);
1244 free(swd);
1245
1246 return UCL_E_OK;
1247}
1248
1249
1250#ifdef VBOX
1251static
1252#endif
1253void Encode(void) /* compression */
1254{
1255 uint8_t *in, *out;
1256 unsigned long in_len, out_len;
1257 uint32_t tw;
1258 int r;
1259 fseek(infile, 0, SEEK_END);
1260 in_len = ftell(infile);
1261#ifdef VERBOSE
1262 if ((signed long)in_len < 0)
1263 Fprintf((stderr, "Errno: %d", errno));
1264#endif
1265#if UCLPACK_COMPAT
1266 {
1267 uint8_t byte;
1268 if (fwrite(magic, sizeof(magic), 1, outfile) != 1)
1269 Error("Can't write.");
1270 tw = htonl(0); /* flags */
1271 if (fwrite(&tw, sizeof(tw), 1, outfile) != 1)
1272 Error("Can't write.");
1273 byte = 0x2b; /* method */
1274 if (fwrite(&byte, sizeof(byte), 1, outfile) != 1)
1275 Error("Can't write.");
1276 byte = 10; /* level */
1277 if (fwrite(&byte, sizeof(byte), 1, outfile) != 1)
1278 Error("Can't write.");
1279 tw = htonl(256*1024); /* block_size */
1280 if (fwrite(&tw, sizeof(tw), 1, outfile) != 1)
1281 Error("Can't write.");
1282 tw = htonl(in_len);
1283 if (fwrite(&tw, sizeof(tw), 1, outfile) != 1)
1284 Error("Can't write."); /* output size of text */
1285 }
1286#else
1287 tw = host_to_i86ul(in_len);
1288 if (fwrite(&tw, sizeof(tw), 1, outfile) != 1)
1289 Error("Can't write."); /* output size of text */
1290#endif
1291 if (in_len == 0)
1292 return;
1293 rewind(infile);
1294
1295 in = malloc(in_len);
1296 out_len = in_len + (in_len/8) + 256;
1297 out = malloc(out_len);
1298 if (!in || !out) {
1299 Error("Can't malloc");
1300 }
1301 if (fread(in, in_len, 1, infile) != 1) {
1302 Error("Can't read");
1303 }
1304 r = ucl_nrv2b_99_compress(in, in_len, out, &out_len, 0 );
1305 if (r != UCL_E_OK)
1306 Error("Compression failure\n");
1307#if UCLPACK_COMPAT
1308 tw = htonl(out_len);
1309 if (fwrite(&tw, sizeof(tw), 1, outfile) != 1)
1310 Error("Can't write."); /* file size of text */
1311
1312#endif
1313 if (fwrite(out, out_len, 1, outfile) != 1) {
1314 Error("Write error\n");
1315 }
1316#if UCLPACK_COMPAT
1317 tw = htonl(0); /* EOF marker */
1318 if (fwrite(&tw, sizeof(tw), 1, outfile) != 1)
1319 Error("Can't write.");
1320
1321#endif
1322
1323#ifdef LONG_REPORT
1324 Fprintf((stdout, "input size %ld bytes\n", in_len));
1325 Fprintf((stdout, "output size %ld bytes\n", out_len));
1326 Fprintf((stdout, "input/output %.3f\n", (double)in_len / out_len));
1327#else
1328 Fprintf((stdout, "input/output = %ld/%ld = %.3f\n", in_len, out_len,
1329 (double)in_len / out_len));
1330#endif
1331
1332}
1333
1334#endif
1335
1336#ifdef DECODE
1337
1338#define GETBIT_8(bb, src, ilen) \
1339 (((bb = bb & 0x7f ? bb*2 : ((unsigned)src[ilen++]*2+1)) >> 8) & 1)
1340
1341#define GETBIT_LE16(bb, src, ilen) \
1342 (bb*=2,bb&0xffff ? (bb>>16)&1 : (ilen+=2,((bb=(src[ilen-2]+src[ilen-1]*256u)*2+1)>>16)&1))
1343
1344#define GETBIT_LE32(bb, src, ilen) \
1345 (bc > 0 ? ((bb>>--bc)&1) : (bc=31,\
1346 bb=*(const uint32_t *)((src)+ilen),ilen+=4,(bb>>31)&1))
1347
1348#define GETBIT_LE64(bb, src, ilen) \
1349 (bc > 0 ? ((bb>>--bc)&1) : (bc=63, \
1350 bb=*(const uint64_t *)((src)+ilen),ilen+=8,(bb>>63)&1))
1351
1352#if ENDIAN == 0 && BITSIZE == 8
1353#define GETBIT(bb, src, ilen) GETBIT_8(bb, src, ilen)
1354#endif
1355#if ENDIAN == 0 && BITSIZE == 16
1356#define GETBIT(bb, src, ilen) GETBIT_LE16(bb, src, ilen)
1357#endif
1358#if ENDIAN == 0 && BITSIZE == 32
1359#define GETBIT(bb, src, ilen) GETBIT_LE32(bb, src, ilen)
1360#endif
1361#if ENDIAN == 0 && BITSIZE == 64
1362#define GETBIT(bb, src, ilen) GETBIT_LE64(bb, src, ilen)
1363#endif
1364#ifndef GETBIT
1365#error "Bad Combination of ENDIAN and BITSIZE values specified"
1366#endif
1367
1368#undef SAFE
1369
1370#ifdef SAFE
1371#define FAIL(x,r) if (x) { Error(r); }
1372#else
1373#define FAIL(x,r)
1374#endif
1375
1376#ifdef VBOX
1377static
1378#endif
1379void Decode(void) /* recover */
1380{
1381 uint32_t tw;
1382 uint8_t *src, *dst;
1383 unsigned long max_src_len, src_len, dst_len;
1384 unsigned long ilen = 0, olen = 0, last_m_off = 1;
1385#if BITSIZE <= 32
1386 uint32_t bb = 0;
1387#elif BITSIZE == 64
1388 uint64_t bb = 0;
1389#endif
1390 unsigned bc = 0;
1391#if UCLPACK_COMPAT
1392 if (fseek(infile, sizeof(magic) + sizeof(tw) + 1 + 1 + sizeof(tw),
1393 SEEK_SET) != 0)
1394
1395 Error("Seek Error");
1396 if (fread(&tw, sizeof(tw), 1, infile) < 1)
1397 Error("Can't read"); /* read size of text */
1398 dst_len = ntohl(tw);
1399 if (fread(&tw, sizeof(tw), 1, infile) < 1)
1400 Error("Can't read"); /* read size of file */
1401 max_src_len = ntohl(tw);
1402#else
1403 if (fread(&tw, sizeof(tw), 1, infile) < 1)
1404 Error("Can't read"); /* read size of text */
1405 dst_len = i86ul_to_host(tw);
1406 max_src_len = dst_len + (dst_len/8) + 256;
1407#endif
1408 if (dst_len == 0)
1409 return;
1410 dst = malloc(dst_len);
1411 if (!dst)
1412 Error("Can't malloc");
1413 src = malloc(max_src_len);
1414 if (!src)
1415 Error("Can't malloc");
1416 src_len = fread(src, 1, max_src_len, infile);
1417 if (src_len <= 0)
1418 Error("Can't read");
1419
1420 for(;;) {
1421 unsigned int m_off, m_len;
1422 while(GETBIT(bb, src, ilen)) {
1423 FAIL(ilen >= src_len, "input overrun");
1424 FAIL(olen >= dst_len, "output overrun");
1425 dst[olen++] = src[ilen++];
1426 }
1427 m_off = 1;
1428 do {
1429 m_off = m_off*2 + GETBIT(bb, src, ilen);
1430 FAIL(ilen >= src_len, "input overrun");
1431 FAIL(m_off > 0xffffffU +3, "lookbehind overrun");
1432 } while (!GETBIT(bb, src, ilen));
1433 if (m_off == 2)
1434 {
1435 m_off = last_m_off;
1436 }
1437 else
1438 {
1439 FAIL(ilen >= src_len, "input overrun");
1440 m_off = (m_off - 3)*256 + src[ilen++];
1441 if (m_off == 0xffffffffU)
1442 break;
1443 last_m_off = ++m_off;
1444 }
1445 m_len = GETBIT(bb, src, ilen);
1446 m_len = m_len*2 + GETBIT(bb, src, ilen);
1447 if (m_len == 0)
1448 {
1449 m_len++;
1450 do {
1451 m_len = m_len*2 + GETBIT(bb, src, ilen);
1452 FAIL(ilen >= src_len, "input overrun");
1453 FAIL(m_len >= dst_len, "output overrun");
1454 } while(!GETBIT(bb, src, ilen));
1455 m_len += 2;
1456 }
1457 m_len += (m_off > 0xd00);
1458 FAIL(olen + m_len > dst_len, "output overrun");
1459 FAIL(m_off > olen, "lookbeind overrun");
1460 {
1461 const uint8_t *m_pos;
1462 m_pos = dst + olen - m_off;
1463 dst[olen++] = *m_pos++;
1464 do {
1465 dst[olen++] = *m_pos++;
1466 } while(--m_len > 0);
1467 }
1468 }
1469 FAIL(ilen < src_len, "input not consumed");
1470 FAIL(ilen > src_len, "input overrun");
1471 assert(ilen == src_len);
1472 Fprintf((stderr, "%12ld\n", olen));
1473 if (dst_len != olen) {
1474 fprintf(stderr, "length != expected length\n");
1475 }
1476 if (fwrite(dst, olen, 1, outfile) != 1)
1477 Error("Write error\n");
1478 free(src);
1479 free(dst);
1480}
1481#endif
1482
1483#ifdef MAIN
1484int main(int argc, char *argv[])
1485{
1486 char *s;
1487 FILE *f;
1488 int c;
1489
1490 if (argc == 2) {
1491 outfile = stdout;
1492 if ((f = tmpfile()) == NULL) {
1493 perror("tmpfile");
1494 return EXIT_FAILURE;
1495 }
1496 while ((c = getchar()) != EOF)
1497 fputc(c, f);
1498 rewind(infile = f);
1499 }
1500 else if (argc != 4) {
1501 Fprintf((stderr, "'nrv2b e file1 file2' encodes file1 into file2.\n"
1502 "'nrv2b d file2 file1' decodes file2 into file1.\n"));
1503 return EXIT_FAILURE;
1504 }
1505 if (argc == 4) {
1506 if ((s = argv[1], s[1] || strpbrk(s, "DEde") == NULL)
1507 || (s = argv[2], (infile = fopen(s, "rb")) == NULL)
1508 || (s = argv[3], (outfile = fopen(s, "wb")) == NULL)) {
1509 Fprintf((stderr, "??? %s\n", s));
1510 return EXIT_FAILURE;
1511 }
1512 }
1513 if (toupper(*argv[1]) == 'E')
1514 Encode();
1515 else
1516 Decode();
1517 fclose(infile);
1518 fclose(outfile);
1519 return EXIT_SUCCESS;
1520}
1521#endif
注意: 瀏覽 TracBrowser 來幫助您使用儲存庫瀏覽器

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