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
7 minor beautifications and adjustments for compiling under Linux
8 by Markus Gutschke <gutschk@math.uni-muenster.de>
11 Modifications to allow use as a filter by Ken Yap
12 <ken_yap@users.sourceforge.net>.
16 Small mod to cope with running on big-endian machines
17 by Jim Hague <jim.hague@acm.org)
20 Make compression statistics report shorter
21 by Ken Yap <ken_yap@users.sourceforge.net>.
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>.
32 **************************************************************/
33 #define UCLPACK_COMPAT 0
48 #include <netinet/in.h>
55 #define Fprintf(x) fprintf x
61 FILE *infile
, *outfile
;
63 #if defined(ENCODE) || defined(DECODE)
72 static __inline__
void Error(char *message
)
74 Fprintf((stderr
, "\n%s\n", message
));
78 /* These will be a complete waste of time on a lo-endian */
79 /* system, but it only gets done once so WTF. */
80 static unsigned long __attribute__ (( unused
)) i86ul_to_host(unsigned long ul
)
82 unsigned long res
= 0;
91 for (i
= 3; i
>= 0; i
--)
92 res
= (res
<< 8) + u
.c
[i
];
96 static unsigned long host_to_i86ul(unsigned long ul
)
105 for (i
= 0; i
< 4; i
++)
117 /* magic file header for compressed files */
118 static const unsigned char magic
[8] =
119 { 0x00, 0xe9, 0x55, 0x43, 0x4c, 0xff, 0x01, 0x1a };
124 /********** NRV2B_99 compression **********/
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.
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
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
146 unsigned int max_offset
;
147 unsigned int max_match
;
159 unsigned int look
; /* bytes in lookahead buffer */
164 unsigned int last_m_len
;
165 unsigned int last_m_off
;
167 const unsigned char *bp
;
168 const unsigned char *ip
;
169 const unsigned char *in
;
170 const unsigned char *in_end
;
175 unsigned bb_c_endian
;
179 unsigned char *bb_op
;
181 struct ucl_compress_config conf
;
182 unsigned int *result
;
184 unsigned int textsize
; /* text size counter */
185 unsigned int codesize
; /* code size counter */
186 unsigned int printcount
; /* counter for reporting progress every 1K
191 unsigned long lit_bytes
;
192 unsigned long match_bytes
;
193 unsigned long rep_bytes
;
199 #define getbyte(c) ((c).ip < (c).in_end ? *((c).ip)++ : (-1))
202 #define UCL_E_INVALID_ARGUMENT 1
203 #define UCL_E_OUT_OF_MEMORY 2
204 #define UCL_E_ERROR 3
206 /***********************************************************************
208 ************************************************************************/
210 #define SWD_HSIZE 16384
211 #define SWD_MAX_CHAIN 2048
215 (((0x9f5f*(((((uint32_t)b[p]<<5)^b[p+1])<<5)^b[p+2]))>>5) & (SWD_HSIZE-1))
217 #define HEAD2(b,p) (b[p] ^ ((unsigned)b[p+1]<<8))
218 #define NIL2 UINT_MAX
222 /* public - "built-in" */
225 unsigned int threshold
;
227 /* public - configuration */
228 unsigned int max_chain
;
229 unsigned int nice_length
;
231 unsigned int lazy_insert
;
233 /* public - output */
238 #if defined(SWD_BEST_OFF)
239 unsigned int best_off
[ SWD_BEST_OFF
];
243 struct ucl_compress
*c
;
245 #if defined(SWD_BEST_OFF)
246 unsigned int best_pos
[ SWD_BEST_OFF
];
251 const uint8_t *dict_end
;
252 unsigned int dict_len
;
255 unsigned int ip
; /* input pointer (lookahead) */
256 unsigned int bp
; /* buffer pointer */
257 unsigned int rp
; /* remove pointer */
260 unsigned char *b_wrap
;
262 unsigned int node_count
;
263 unsigned int first_rp
;
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 ];
273 #define s_head3(s,key) s->head3[key]
276 #if !defined( NDEBUG)
277 static void assert_match(const struct ucl_swd
* swd
, unsigned int m_len
,
281 const struct ucl_compress
*c
= swd
->c
;
285 if (m_off
<= (unsigned int) (c
->bp
- c
->in
))
287 assert(c
->bp
- m_off
+ m_len
< c
->ip
);
288 assert(memcmp(c
->bp
, c
->bp
- m_off
, m_len
) == 0);
292 assert(swd
->dict
!= NULL
);
293 d_off
= m_off
- (unsigned int) (c
->bp
- c
->in
);
294 assert(d_off
<= swd
->dict_len
);
297 assert(memcmp(c
->bp
, swd
->dict_end
- d_off
, d_off
) ==
300 assert(c
->in
+ m_len
- d_off
< c
->ip
);
301 assert(memcmp(c
->bp
+ d_off
, c
->in
, m_len
- d_off
) ==
307 assert(memcmp(c
->bp
, swd
->dict_end
- d_off
, m_len
) ==
314 # define assert_match(a,b,c) ((void)0)
317 /***********************************************************************
319 ************************************************************************/
323 void swd_initdict(struct ucl_swd
*s
, const uint8_t *dict
, unsigned int dict_len
)
326 s
->dict
= s
->dict_end
= NULL
;
329 if (!dict
|| dict_len
<= 0)
333 dict
+= dict_len
- s
->n
;
338 s
->dict_len
= dict_len
;
339 s
->dict_end
= dict
+ dict_len
;
340 memcpy(s
->b
,dict
,dict_len
);
346 void swd_insertdict(struct ucl_swd
*s
, unsigned int node
, unsigned int len
)
350 s
->node_count
= s
->n
- len
;
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);
360 assert(s
->llen3
[key
] <= s
->n
);
362 key
= HEAD2(s
->b
,node
);
363 s
->head2
[key
] = (unsigned int)(node
);
369 /***********************************************************************
371 ************************************************************************/
375 int swd_init(struct ucl_swd
*s
, const uint8_t *dict
, unsigned int dict_len
)
383 s
->threshold
= THRESHOLD
;
384 if (s
->n
> N
|| s
->f
> F
)
385 return UCL_E_INVALID_ARGUMENT
;
388 s
->max_chain
= SWD_MAX_CHAIN
;
389 s
->nice_length
= s
->f
;
393 s
->b_size
= s
->n
+ s
->f
;
394 if (s
->b_size
+ s
->f
>= UINT_MAX
)
396 s
->b_wrap
= s
->b
+ s
->b_size
;
397 s
->node_count
= s
->n
;
399 memset(s
->llen3
, 0, sizeof(s
->llen3
[0]) * SWD_HSIZE
);
400 for (i
= 0; i
< 65536U; i
++)
404 swd_initdict(s
,dict
,dict_len
);
408 assert(s
->ip
+ s
->f
<= s
->b_size
);
410 s
->look
= (unsigned int) (s
->c
->in_end
- s
->c
->ip
);
415 memcpy(&s
->b
[s
->ip
],s
->c
->ip
,s
->look
);
419 if (s
->ip
== s
->b_size
)
422 if (s
->look
>= 2 && s
->dict_len
> 0)
423 swd_insertdict(s
,0,s
->dict_len
);
426 if (s
->rp
>= s
->node_count
)
427 s
->rp
-= s
->node_count
;
429 s
->rp
+= s
->b_size
- s
->node_count
;
438 void swd_exit(struct ucl_swd
*s
)
444 #define swd_pos2off(s,pos) \
445 (s->bp > (pos) ? s->bp - (pos) : s->b_size - ((pos) - s->bp))
447 /***********************************************************************
449 ************************************************************************/
452 void swd_getbyte(struct ucl_swd
*s
)
456 if ((c
= getbyte(*(s
->c
))) < 0)
463 s
->b
[s
->ip
] = (uint8_t)(c
);
465 s
->b_wrap
[s
->ip
] = (uint8_t)(c
);
467 if (++s
->ip
== s
->b_size
)
469 if (++s
->bp
== s
->b_size
)
471 if (++s
->rp
== s
->b_size
)
474 /***********************************************************************
475 // remove node from lists
476 ************************************************************************/
479 void swd_remove_node(struct ucl_swd
*s
, unsigned int node
)
481 if (s
->node_count
== 0)
486 if (s
->first_rp
!= UINT_MAX
)
488 if (node
!= s
->first_rp
)
489 printf("Remove %5d: %5d %5d %5d %5d %6d %6d\n",
491 node
, s
->rp
, s
->ip
, s
->bp
, s
->first_rp
,
492 s
->ip
- node
, s
->ip
- s
->bp
);
493 assert(node
== s
->first_rp
);
494 s
->first_rp
= UINT_MAX
;
498 key
= HEAD3(s
->b
,node
);
499 assert(s
->llen3
[key
] > 0);
502 key
= HEAD2(s
->b
,node
);
503 assert(s
->head2
[key
] != NIL2
);
504 if ((unsigned int) s
->head2
[key
] == node
)
505 s
->head2
[key
] = NIL2
;
512 /***********************************************************************
514 ************************************************************************/
518 void swd_accept(struct ucl_swd
*s
, unsigned int n
)
520 assert(n
<= s
->look
);
526 swd_remove_node(s
,s
->rp
);
528 /* add bp into HEAD3 */
529 key
= HEAD3(s
->b
,s
->bp
);
530 s
->succ3
[s
->bp
] = s_head3(s
,key
);
531 s
->head3
[key
] = (unsigned int)(s
->bp
);
532 s
->best3
[s
->bp
] = (unsigned int)(s
->f
+ 1);
534 assert(s
->llen3
[key
] <= s
->n
);
536 /* add bp into HEAD2 */
537 key
= HEAD2(s
->b
,s
->bp
);
538 s
->head2
[key
] = (unsigned int)(s
->bp
);
544 /***********************************************************************
546 ************************************************************************/
549 void swd_search(struct ucl_swd
*s
, unsigned int node
, unsigned int cnt
)
551 const unsigned char *p1
;
552 const unsigned char *p2
;
553 const unsigned char *px
;
555 unsigned int m_len
= s
->m_len
;
556 const unsigned char * b
= s
->b
;
557 const unsigned char * bp
= s
->b
+ s
->bp
;
558 const unsigned char * bx
= s
->b
+ s
->bp
+ s
->look
;
559 unsigned char scan_end1
;
561 assert(s
->m_len
> 0);
563 scan_end1
= bp
[m_len
- 1];
564 for ( ; cnt
-- > 0; node
= s
->succ3
[node
])
570 assert(m_len
< s
->look
);
573 p2
[m_len
- 1] == scan_end1
&&
574 p2
[m_len
] == p1
[m_len
] &&
579 assert(memcmp(bp
,&b
[node
],3) == 0);
582 do {} while (++p1
< px
&& *p1
== *++p2
);
586 if (memcmp(bp
,&b
[node
],i
) != 0)
587 printf("%5ld %5ld %02x%02x %02x%02x\n",
588 (long)s
->bp
, (long) node
,
589 bp
[0], bp
[1], b
[node
], b
[node
+1]);
591 assert(memcmp(bp
,&b
[node
],i
) == 0);
593 #if defined(SWD_BEST_OFF)
594 if (i
< SWD_BEST_OFF
)
596 if (s
->best_pos
[i
] == 0)
597 s
->best_pos
[i
] = node
+ 1;
602 s
->m_len
= m_len
= i
;
604 if (m_len
== s
->look
)
606 if (m_len
>= s
->nice_length
)
608 if (m_len
> (unsigned int) s
->best3
[node
])
610 scan_end1
= bp
[m_len
- 1];
616 static int swd_search2(struct ucl_swd
*s
)
620 assert(s
->look
>= 2);
621 assert(s
->m_len
> 0);
623 key
= s
->head2
[ HEAD2(s
->b
,s
->bp
) ];
627 if (memcmp(&s
->b
[s
->bp
],&s
->b
[key
],2) != 0)
628 printf("%5ld %5ld %02x%02x %02x%02x\n", (long)s
->bp
, (long)key
,
629 s
->b
[s
->bp
], s
->b
[s
->bp
+1], s
->b
[key
], s
->b
[key
+1]);
631 assert(memcmp(&s
->b
[s
->bp
],&s
->b
[key
],2) == 0);
632 #if defined(SWD_BEST_OFF)
633 if (s
->best_pos
[2] == 0)
634 s
->best_pos
[2] = key
+ 1;
645 /***********************************************************************
647 ************************************************************************/
650 void swd_findbest(struct ucl_swd
*s
)
653 unsigned int cnt
, node
;
656 assert(s
->m_len
> 0);
658 /* get current head, add bp into HEAD3 */
659 key
= HEAD3(s
->b
,s
->bp
);
660 node
= s
->succ3
[s
->bp
] = s_head3(s
,key
);
661 cnt
= s
->llen3
[key
]++;
662 assert(s
->llen3
[key
] <= s
->n
+ s
->f
);
663 if (cnt
> s
->max_chain
&& s
->max_chain
> 0)
665 s
->head3
[key
] = (unsigned int)(s
->bp
);
667 s
->b_char
= s
->b
[s
->bp
];
669 if (s
->m_len
>= s
->look
)
674 s
->best3
[s
->bp
] = (unsigned int)(s
->f
+ 1);
680 swd_search(s
,node
,cnt
);
682 s
->m_off
= swd_pos2off(s
,s
->m_pos
);
683 s
->best3
[s
->bp
] = (unsigned int)(s
->m_len
);
685 #if defined(SWD_BEST_OFF)
689 for (i
= 2; i
< SWD_BEST_OFF
; i
++)
690 if (s
->best_pos
[i
] > 0)
692 swd_pos2off(s
,s
->best_pos
[i
]-1);
700 swd_remove_node(s
,s
->rp
);
702 /* add bp into HEAD2 */
703 key
= HEAD2(s
->b
,s
->bp
);
704 s
->head2
[key
] = (unsigned int)(s
->bp
);
708 /***********************************************************************
710 ************************************************************************/
713 init_match ( struct ucl_compress
*c
, struct ucl_swd
*s
,
714 const uint8_t *dict
, unsigned int dict_len
,
724 c
->last_m_len
= c
->last_m_off
= 0;
726 c
->textsize
= c
->codesize
= c
->printcount
= 0;
727 c
->lit_bytes
= c
->match_bytes
= c
->rep_bytes
= 0;
730 r
= swd_init(s
,dict
,dict_len
);
737 s
->use_best_off
= (flags
& 1) ?
1 : 0;
742 find_match ( struct ucl_compress
*c
, struct ucl_swd
*s
,
743 unsigned int this_len
, unsigned int skip
)
749 assert(this_len
>= skip
);
750 swd_accept(s
, this_len
- skip
);
751 c
->textsize
+= this_len
- skip
+ 1;
755 assert(this_len
<= 1);
756 c
->textsize
+= this_len
- skip
;
759 s
->m_len
= THRESHOLD
;
762 memset(s
->best_pos
,0,sizeof(s
->best_pos
));
778 c
->look
= s
->look
+ 1;
780 c
->bp
= c
->ip
- c
->look
;
783 /* brute force match search */
784 if (c
->m_len
> THRESHOLD
&& c
->m_len
+ 1 <= c
->look
)
786 const uint8_t *ip
= c
->bp
;
787 const uint8_t *m
= c
->bp
- c
->m_off
;
788 const uint8_t *in
= c
->in
;
799 if (memcmp(in
,ip
,c
->m_len
+1) == 0)
800 printf("%p %p %p %5d\n",in
,ip
,m
,c
->m_len
);
811 static int bbConfig(struct ucl_compress
*c
, int endian
, int bitsize
)
817 c
->bb_c_endian
= endian
;
821 if (bitsize
!= 8 && bitsize
!= 16 && bitsize
!= 32 && bitsize
!= 64)
824 c
->bb_c_s8
= bitsize
/ 8;
826 c
->bb_b
= 0; c
->bb_k
= 0;
832 static void bbWriteBits(struct ucl_compress
*c
)
834 uint8_t *p
= c
->bb_p
;
835 uint64_t b
= c
->bb_b
;
837 p
[0] = (uint8_t)(b
>> 0);
840 p
[1] = (uint8_t)(b
>> 8);
843 p
[2] = (uint8_t)(b
>> 16);
844 p
[3] = (uint8_t)(b
>> 24);
847 p
[4] = (uint8_t)(b
>> 32);
848 p
[5] = (uint8_t)(b
>> 40);
849 p
[6] = (uint8_t)(b
>> 48);
850 p
[7] = (uint8_t)(b
>> 56);
857 static void bbPutBit(struct ucl_compress
*c
, unsigned bit
)
859 assert(bit
== 0 || bit
== 1);
860 assert(c
->bb_k
<= c
->bb_c_s
);
862 if (c
->bb_k
< c
->bb_c_s
)
866 assert(c
->bb_p
== NULL
);
868 c
->bb_op
+= c
->bb_c_s8
;
870 assert(c
->bb_p
!= NULL
);
871 assert(c
->bb_p
+ c
->bb_c_s8
<= c
->bb_op
);
873 c
->bb_b
= (c
->bb_b
<< 1) + bit
;
878 assert(c
->bb_p
!= NULL
);
879 assert(c
->bb_p
+ c
->bb_c_s8
<= c
->bb_op
);
883 c
->bb_op
+= c
->bb_c_s8
;
890 static void bbPutByte(struct ucl_compress
*c
, unsigned b
)
892 /**printf("putbyte %p %p %x (%d)\n", op, bb_p, x, bb_k);*/
893 assert(c
->bb_p
== NULL
|| c
->bb_p
+ c
->bb_c_s8
<= c
->bb_op
);
894 *c
->bb_op
++ = (uint8_t)(b
);
897 static void bbFlushBits(struct ucl_compress
*c
, unsigned filler_bit
)
901 assert(c
->bb_k
<= c
->bb_c_s
);
902 while (c
->bb_k
!= c
->bb_c_s
)
903 bbPutBit(c
, filler_bit
);
912 /***********************************************************************
914 ************************************************************************/
917 static void code_prefix_ss11(struct ucl_compress
*c
, uint32_t i
)
929 bbPutBit(c
, (i
& t
) ?
1 : 0);
933 bbPutBit(c
, (unsigned)i
& 1);
938 code_match(struct ucl_compress
*c
, unsigned int m_len
, const unsigned int m_off
)
941 while (m_len
> c
->conf
.max_match
)
943 code_match(c
, c
->conf
.max_match
- 3, m_off
);
944 m_len
-= c
->conf
.max_match
- 3;
947 c
->match_bytes
+= m_len
;
948 if (m_len
> c
->result
[3])
949 c
->result
[3] = m_len
;
950 if (m_off
> c
->result
[1])
951 c
->result
[1] = m_off
;
955 if (m_off
== c
->last_m_off
)
962 code_prefix_ss11(c
, 1 + ((m_off
- 1) >> 8));
963 bbPutByte(c
, (unsigned)m_off
- 1);
965 m_len
= m_len
- 1 - (m_off
> M2_MAX_OFFSET
);
970 code_prefix_ss11(c
, m_len
- 4);
974 bbPutBit(c
, m_len
> 1);
975 bbPutBit(c
, (unsigned)m_len
& 1);
978 c
->last_m_off
= m_off
;
982 code_run(struct ucl_compress
*c
, const uint8_t *ii
, unsigned int lit
)
987 if (lit
> c
->result
[5])
995 /***********************************************************************
997 ************************************************************************/
1000 len_of_coded_match(struct ucl_compress
*c
, unsigned int m_len
, unsigned int
1005 if (m_len
< 2 || (m_len
== 2 && (m_off
> M2_MAX_OFFSET
))
1006 || m_off
> c
->conf
.max_offset
)
1010 m_len
= m_len
- 2 - (m_off
> M2_MAX_OFFSET
);
1012 if (m_off
== c
->last_m_off
)
1017 m_off
= (m_off
- 1) >> 8;
1033 } while (m_len
> 0);
1038 int ucl_nrv2b_99_compress(
1039 const uint8_t *in
, unsigned long in_len
,
1040 uint8_t *out
, unsigned long *out_len
,
1041 unsigned int *result
)
1045 unsigned int m_len
, m_off
;
1046 struct ucl_compress c_buffer
;
1047 struct ucl_compress
* const c
= &c_buffer
;
1048 struct ucl_swd
*swd
;
1049 unsigned int result_buffer
[16];
1052 /* max compression */
1053 #define SC_TRY_LAZY 2
1054 #define SC_GOOD_LENGTH F
1055 #define SC_MAX_LAZY F
1056 #define SC_NICE_LENGTH F
1057 #define SC_MAX_CHAIN 4096
1059 #define SC_MAX_OFFSET N
1061 memset(c
, 0, sizeof(*c
));
1063 c
->in_end
= in
+ in_len
;
1065 c
->result
= result ? result
: result_buffer
;
1066 memset(c
->result
, 0, 16*sizeof(*c
->result
));
1067 c
->result
[0] = c
->result
[2] = c
->result
[4] = UINT_MAX
;
1069 memset(&c
->conf
, 0xff, sizeof(c
->conf
));
1070 r
= bbConfig(c
, ENDIAN
, BITSIZE
);
1072 r
= bbConfig(c
, c
->conf
.bb_endian
, c
->conf
.bb_size
);
1074 return UCL_E_INVALID_ARGUMENT
;
1077 ii
= c
->ip
; /* point to start of literal run */
1081 swd
= (struct ucl_swd
*) malloc(sizeof(*swd
));
1083 return UCL_E_OUT_OF_MEMORY
;
1087 if (in_len
>= 256 && in_len
< swd
->n
)
1089 if (swd
->f
< 8 || swd
->n
< 256)
1090 return UCL_E_INVALID_ARGUMENT
;
1092 r
= init_match(c
,swd
,NULL
,0, SC_FLAGS
);
1098 if (SC_MAX_CHAIN
> 0)
1099 swd
->max_chain
= SC_MAX_CHAIN
;
1100 if (SC_NICE_LENGTH
> 0)
1101 swd
->nice_length
= SC_NICE_LENGTH
;
1102 if (c
->conf
.max_match
< swd
->nice_length
)
1103 swd
->nice_length
= c
->conf
.max_match
;
1106 r
= find_match(c
,swd
,0,0);
1112 unsigned int max_ahead
;
1115 c
->codesize
= c
->bb_op
- out
;
1120 assert(c
->bp
== c
->ip
- c
->look
);
1121 assert(c
->bp
>= in
);
1124 assert(ii
+ lit
== c
->bp
);
1125 assert(swd
->b_char
== *(c
->bp
));
1127 if (m_len
< 2 || (m_len
== 2 && (m_off
> M2_MAX_OFFSET
))
1128 || m_off
> c
->conf
.max_offset
)
1132 swd
->max_chain
= SC_MAX_CHAIN
;
1133 r
= find_match(c
,swd
,1,0);
1139 assert_match(swd
,m_len
,m_off
);
1141 /* shall we try a lazy match ? */
1143 if (SC_TRY_LAZY
<= 0 || m_len
>= SC_MAX_LAZY
|| m_off
==
1153 /* yes, try a lazy match */
1154 l1
= len_of_coded_match(c
,m_len
,m_off
);
1156 max_ahead
= SC_TRY_LAZY
;
1157 if ((m_len
- 1) < max_ahead
) {
1158 max_ahead
= m_len
-1;
1162 while (ahead
< max_ahead
&& c
->look
> m_len
)
1164 if (m_len
>= SC_GOOD_LENGTH
)
1165 swd
->max_chain
= SC_MAX_CHAIN
>> 2;
1167 swd
->max_chain
= SC_MAX_CHAIN
;
1168 r
= find_match(c
,swd
,1,0);
1172 assert(c
->look
> 0);
1173 assert(ii
+ lit
+ ahead
== c
->bp
);
1177 l2
= len_of_coded_match(c
,c
->m_len
,c
->m_off
);
1180 if (l1
+ (int)(ahead
+ c
->m_len
- m_len
) * 5 > l2
+
1184 assert_match(swd
,c
->m_len
,c
->m_off
);
1186 assert(ii
+ lit
== c
->bp
);
1187 goto lazy_match_done
;
1191 assert(ii
+ lit
+ ahead
== c
->bp
);
1197 /* 2 - code match */
1198 code_match(c
,m_len
,m_off
);
1199 swd
->max_chain
= SC_MAX_CHAIN
;
1200 r
= find_match(c
,swd
,m_len
,1+ahead
);
1206 /* store final run */
1211 code_prefix_ss11(c
, 0x1000000U
);
1216 assert(c
->textsize
== in_len
);
1217 c
->codesize
= c
->bb_op
- out
;
1218 *out_len
= c
->bb_op
- out
;
1221 printf("%7ld %7ld -> %7ld %7ld %7ld %ld (max: %d %d %d)\n",
1222 (long) c
->textsize
, (long) in_len
, (long) c
->codesize
,
1223 c
->match_bytes
, c
->lit_bytes
, c
->lazy
,
1224 c
->result
[1], c
->result
[3], c
->result
[5]);
1226 assert(c
->lit_bytes
+ c
->match_bytes
== in_len
);
1235 void Encode(void) /* compression */
1238 unsigned long in_len
, out_len
;
1241 fseek(infile
, 0, SEEK_END
);
1242 in_len
= ftell(infile
);
1244 if ((signed long)in_len
< 0)
1245 Fprintf((stderr
, "Errno: %d", errno
));
1250 if (fwrite(magic
, sizeof(magic
), 1, outfile
) != 1)
1251 Error("Can't write.");
1252 tw
= htonl(0); /* flags */
1253 if (fwrite(&tw
, sizeof(tw
), 1, outfile
) != 1)
1254 Error("Can't write.");
1255 byte
= 0x2b; /* method */
1256 if (fwrite(&byte
, sizeof(byte
), 1, outfile
) != 1)
1257 Error("Can't write.");
1258 byte
= 10; /* level */
1259 if (fwrite(&byte
, sizeof(byte
), 1, outfile
) != 1)
1260 Error("Can't write.");
1261 tw
= htonl(256*1024); /* block_size */
1262 if (fwrite(&tw
, sizeof(tw
), 1, outfile
) != 1)
1263 Error("Can't write.");
1265 if (fwrite(&tw
, sizeof(tw
), 1, outfile
) != 1)
1266 Error("Can't write."); /* output size of text */
1269 tw
= host_to_i86ul(in_len
);
1270 if (fwrite(&tw
, sizeof(tw
), 1, outfile
) != 1)
1271 Error("Can't write."); /* output size of text */
1277 in
= malloc(in_len
);
1278 out_len
= in_len
+ (in_len
/8) + 256;
1279 out
= malloc(out_len
);
1281 Error("Can't malloc");
1283 if (fread(in
, in_len
, 1, infile
) != 1) {
1284 Error("Can't read");
1286 r
= ucl_nrv2b_99_compress(in
, in_len
, out
, &out_len
, 0 );
1288 Error("Compression failure\n");
1290 tw
= htonl(out_len
);
1291 if (fwrite(&tw
, sizeof(tw
), 1, outfile
) != 1)
1292 Error("Can't write."); /* file size of text */
1295 if (fwrite(out
, out_len
, 1, outfile
) != 1) {
1296 Error("Write error\n");
1299 tw
= htonl(0); /* EOF marker */
1300 if (fwrite(&tw
, sizeof(tw
), 1, outfile
) != 1)
1301 Error("Can't write.");
1306 Fprintf((stdout
, "input size %ld bytes\n", in_len
));
1307 Fprintf((stdout
, "output size %ld bytes\n", out_len
));
1308 Fprintf((stdout
, "input/output %.3f\n", (double)in_len
/ out_len
));
1310 Fprintf((stdout
, "input/output = %ld/%ld = %.3f\n", in_len
, out_len
,
1311 (double)in_len
/ out_len
));
1320 #define GETBIT_8(bb, src, ilen) \
1321 (((bb = bb & 0x7f ? bb*2 : ((unsigned)src[ilen++]*2+1)) >> 8) & 1)
1323 #define GETBIT_LE16(bb, src, ilen) \
1324 (bb*=2,bb&0xffff ? (bb>>16)&1 : (ilen+=2,((bb=(src[ilen-2]+src[ilen-1]*256u)*2+1)>>16)&1))
1326 #define GETBIT_LE32(bb, src, ilen) \
1327 (bc > 0 ? ((bb>>--bc)&1) : (bc=31,\
1328 bb=*(const uint32_t *)((src)+ilen),ilen+=4,(bb>>31)&1))
1330 #define GETBIT_LE64(bb, src, ilen) \
1331 (bc > 0 ? ((bb>>--bc)&1) : (bc=63, \
1332 bb=*(const uint64_t *)((src)+ilen),ilen+=8,(bb>>63)&1))
1334 #if ENDIAN == 0 && BITSIZE == 8
1335 #define GETBIT(bb, src, ilen) GETBIT_8(bb, src, ilen)
1337 #if ENDIAN == 0 && BITSIZE == 16
1338 #define GETBIT(bb, src, ilen) GETBIT_LE16(bb, src, ilen)
1340 #if ENDIAN == 0 && BITSIZE == 32
1341 #define GETBIT(bb, src, ilen) GETBIT_LE32(bb, src, ilen)
1343 #if ENDIAN == 0 && BITSIZE == 64
1344 #define GETBIT(bb, src, ilen) GETBIT_LE64(bb, src, ilen)
1347 #error "Bad Combination of ENDIAN and BITSIZE values specified"
1353 #define FAIL(x,r) if (x) { Error(r); }
1358 void Decode(void) /* recover */
1362 unsigned long max_src_len
, src_len
, dst_len
;
1363 unsigned long ilen
= 0, olen
= 0, last_m_off
= 1;
1371 if (fseek(infile
, sizeof(magic
) + sizeof(tw
) + 1 + 1 + sizeof(tw
),
1374 Error("Seek Error");
1375 if (fread(&tw
, sizeof(tw
), 1, infile
) < 1)
1376 Error("Can't read"); /* read size of text */
1377 dst_len
= ntohl(tw
);
1378 if (fread(&tw
, sizeof(tw
), 1, infile
) < 1)
1379 Error("Can't read"); /* read size of file */
1380 max_src_len
= ntohl(tw
);
1382 if (fread(&tw
, sizeof(tw
), 1, infile
) < 1)
1383 Error("Can't read"); /* read size of text */
1384 dst_len
= i86ul_to_host(tw
);
1385 max_src_len
= dst_len
+ (dst_len
/8) + 256;
1389 dst
= malloc(dst_len
);
1391 Error("Can't malloc");
1392 src
= malloc(max_src_len
);
1394 Error("Can't malloc");
1395 src_len
= fread(src
, 1, max_src_len
, infile
);
1397 Error("Can't read");
1400 unsigned int m_off
, m_len
;
1401 while(GETBIT(bb
, src
, ilen
)) {
1402 FAIL(ilen
>= src_len
, "input overrun");
1403 FAIL(olen
>= dst_len
, "output overrun");
1404 dst
[olen
++] = src
[ilen
++];
1408 m_off
= m_off
*2 + GETBIT(bb
, src
, ilen
);
1409 FAIL(ilen
>= src_len
, "input overrun");
1410 FAIL(m_off
> 0xffffffU
+3, "lookbehind overrun");
1411 } while (!GETBIT(bb
, src
, ilen
));
1418 FAIL(ilen
>= src_len
, "input overrun");
1419 m_off
= (m_off
- 3)*256 + src
[ilen
++];
1420 if (m_off
== 0xffffffffU
)
1422 last_m_off
= ++m_off
;
1424 m_len
= GETBIT(bb
, src
, ilen
);
1425 m_len
= m_len
*2 + GETBIT(bb
, src
, ilen
);
1430 m_len
= m_len
*2 + GETBIT(bb
, src
, ilen
);
1431 FAIL(ilen
>= src_len
, "input overrun");
1432 FAIL(m_len
>= dst_len
, "output overrun");
1433 } while(!GETBIT(bb
, src
, ilen
));
1436 m_len
+= (m_off
> 0xd00);
1437 FAIL(olen
+ m_len
> dst_len
, "output overrun");
1438 FAIL(m_off
> olen
, "lookbeind overrun");
1440 const uint8_t *m_pos
;
1441 m_pos
= dst
+ olen
- m_off
;
1442 dst
[olen
++] = *m_pos
++;
1444 dst
[olen
++] = *m_pos
++;
1445 } while(--m_len
> 0);
1448 FAIL(ilen
< src_len
, "input not consumed");
1449 FAIL(ilen
> src_len
, "input overrun");
1450 assert(ilen
== src_len
);
1451 Fprintf((stderr
, "%12ld\n", olen
));
1452 if (dst_len
!= olen
) {
1453 fprintf(stderr
, "length != expected length\n");
1455 if (fwrite(dst
, olen
, 1, outfile
) != 1)
1456 Error("Write error\n");
1463 int main(int argc
, char *argv
[])
1471 if ((f
= tmpfile()) == NULL
) {
1473 return EXIT_FAILURE
;
1475 while ((c
= getchar()) != EOF
)
1479 else if (argc
!= 4) {
1480 Fprintf((stderr
, "'nrv2b e file1 file2' encodes file1 into file2.\n"
1481 "'nrv2b d file2 file1' decodes file2 into file1.\n"));
1482 return EXIT_FAILURE
;
1485 if ((s
= argv
[1], s
[1] || strpbrk(s
, "DEde") == NULL
)
1486 || (s
= argv
[2], (infile
= fopen(s
, "rb")) == NULL
)
1487 || (s
= argv
[3], (outfile
= fopen(s
, "wb")) == NULL
)) {
1488 Fprintf((stderr
, "??? %s\n", s
));
1489 return EXIT_FAILURE
;
1492 if (toupper(*argv
[1]) == 'E')
1498 return EXIT_SUCCESS
;