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