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