ReactOS 0.4.15-dev-7788-g1ad9096
lzx_layer.c
Go to the documentation of this file.
1/*
2 File lzx_layer.c, part of lzxcomp library
3 Copyright (C) 2002 Matthew T. Russotto
4
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU Lesser General Public License as published by
7 the Free Software Foundation; version 2.1 only
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU Lesser General Public License for more details.
13
14 You should have received a copy of the GNU Lesser General Public License
15 along with this program; if not, write to the Free Software
16 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17*/
18#include <stdio.h>
19#include <stdlib.h>
20#include <stdint.h>
21#include <string.h> /* for memset on Linux */
22#include <assert.h>
23#include <math.h>
24#include "lzx_config.h"
25#ifdef NONSLIDE
26#include "lz_nonslide.h"
27#else
28#include "hash_slide.h"
29#include "lz_slide.h"
30#endif
31#include "lzx_compress.h"
32#include "lzx_constants.h"
33
34/* Debugging defines useful during development. All add diagnostic output
35 at various points in the system */
36
37/*#define DEBUG_MATCHES *//* When matches come in from the LZ engine */
38/*#define DEBUG_MATCHES_2 *//* When matches are being output */
39/*#define DEBUG_HUFFMAN *//* When huffman trees are built */
40/*#define DEBUG_ENTROPY *//* In entropy calculation */
41/*#define DEBUG_LZ *//* Uncompressed input reconstructed from
42 LZ engine */
43/*#define DEBUG_BITBUF *//* Raw output to upper layer */
44/*#define DEBUG_EXTRA_BITS *//* Savings due to extra bits huffman tree */
45/*#define DEBUG_POSITION_SLOT_LOOKUP */
46/*#define DEBUG_TREE_COMPRESSION *//* During RLE compression of trees */
47
48/* number of position slots given window_size-5 */
49/* as corrected by Caie */
50short num_position_slots[] = {30, 32, 34, 36, 38, 42, 50};
51unsigned long position_base[51];
53double rloge2;
54
55typedef struct ih_elem {
56 int freq;
57 short sym;
59 struct ih_elem *parent;
60 struct ih_elem *left;
61 struct ih_elem *right;
63
64typedef struct h_elem {
65 int freq;
66 short sym;
68 struct ih_elem *parent;
69 unsigned short code;
71
72typedef struct huff_entry {
74 unsigned short code;
76
77static int cmp_leaves(const void *in_a, const void *in_b)
78{
79 const struct h_elem *a = in_a;
80 const struct h_elem *b = in_b;
81
82 if (!a->freq && b->freq)
83 return 1;
84 if (a->freq && !b->freq)
85 return -1;
86
87 if (a->freq == b->freq)
88 return a->sym - b->sym;
89
90 return a->freq - b->freq;
91}
92
93static int
94cmp_pathlengths(const void *in_a, const void *in_b)
95{
96 const struct h_elem *a = in_a;
97 const struct h_elem *b = in_b;
98
99 if (a->pathlength == b->pathlength)
100#if 0
101 return a->sym - b->sym;
102#else
103 /* see note on canonical pathlengths */
104 return b->sym - a->sym;
105#endif
106 return b->pathlength - a->pathlength;
107}
108
109/* standard huffman building algorithm */
110static void
111build_huffman_tree(int nelem, int max_code_length, int *freq, huff_entry *tree)
112{
113 h_elem *leaves = malloc(nelem * sizeof(h_elem));
114 ih_elem *inodes;
115 ih_elem *next_inode;
116 ih_elem *cur_inode;
117 h_elem *cur_leaf;
118 int leaves_left;
119 int nleaves;
120 int pathlength;
121 unsigned short cur_code;
122 short codes_too_long = 0;
123 ih_elem *f1, *f2;
124 int i;
125
126 for (i = 0; i < nelem; i++) {
127 leaves[i].freq = freq[i];
128 leaves[i].sym = i;
129 leaves[i].pathlength = 0;
130 }
131 qsort(leaves, nelem, sizeof(h_elem), cmp_leaves);
132 for (leaves_left = 0; leaves_left < nelem; leaves_left++) {
133#ifdef DEBUG_HUFFMAN
134 fprintf(stderr, "%3d: %3d '%c'\n", leaves_left, leaves[leaves_left].freq,
135 leaves[leaves_left].sym);
136#endif
137 if (!leaves[leaves_left].freq) break;
138 }
139 nleaves = leaves_left;
140
141 if (nleaves >= 2) {
142 inodes = malloc((nelem-1) * sizeof(ih_elem));
143 do {
144 if (codes_too_long) {
145 for (leaves_left = 0; leaves_left < nelem; leaves_left++) {
146 if (!leaves[leaves_left].freq) break;
147 if (leaves[leaves_left].freq != 1) {
148 leaves[leaves_left].freq >>= 1;
149 codes_too_long = 0;
150 }
151 }
152 assert (!codes_too_long);
153 }
154
155 cur_leaf = leaves;
156 next_inode = cur_inode = inodes;
157
158 do {
159 f1 = f2 = NULL;
160 if (leaves_left &&
161 ((cur_inode == next_inode) ||
162 (cur_leaf->freq <= cur_inode->freq))) {
163 f1 = (ih_elem *)cur_leaf++;
164 leaves_left--;
165 }
166 else if (cur_inode != next_inode) {
167 f1 = cur_inode++;
168 }
169
170 if (leaves_left &&
171 ((cur_inode == next_inode) ||
172 (cur_leaf->freq <= cur_inode->freq))) {
173 f2 = (ih_elem *)cur_leaf++;
174 leaves_left--;
175 }
176 else if (cur_inode != next_inode) {
177 f2 = cur_inode++;
178 }
179
180#ifdef DEBUG_HUFFMAN
181 fprintf(stderr, "%d %d\n", f1, f2);
182#endif
183 if (f1 && f2) {
184 next_inode->freq = f1->freq + f2->freq;
185 next_inode->sym = -1;
186 next_inode->left = f1;
187 next_inode->right = f2;
188 next_inode->parent = NULL;
189 f1->parent = next_inode;
190 f2->parent = next_inode;
191 if (f1->pathlength > f2->pathlength)
192 next_inode->pathlength = f1->pathlength + 1;
193 else
194 next_inode->pathlength = f2->pathlength + 1;
195 if (next_inode->pathlength > max_code_length) {
196 codes_too_long = 1;
197 break;
198 }
199 next_inode++;
200 }
201 }
202 while (f1 && f2);
203 }
204 while (codes_too_long);
205
206#ifdef DEBUG_HUFFMAN
207 cur_inode = inodes;
208 while (cur_inode < next_inode) {
209 fprintf(stderr, "%d l: %3d%c r: %3d%c freq: %8d\n",
210 cur_inode - inodes,
211 (cur_inode->left->sym!=-1)?(((struct h_elem *)cur_inode->left)-leaves):(cur_inode->left-inodes),
212 (cur_inode->left->sym!=-1)?'l':'i',
213 (cur_inode->right->sym!=-1)?(((struct h_elem *)cur_inode->right)-leaves):(cur_inode->right-inodes),
214 (cur_inode->right->sym!=-1)?'l':'i',
215 (cur_inode->freq)
216 );
217 cur_inode++;
218 }
219#endif
220
221 /* now traverse tree depth-first */
222 cur_inode = next_inode - 1;
223 pathlength = 0;
224 cur_inode->pathlength = -1;
225 do {
226 /* precondition: at unmarked node*/
227 if (cur_inode->sym == -1) /*&& (cur_inode->left)*/ {
228 /* left node of unmarked node is unmarked */
229 cur_inode = cur_inode->left;
230 cur_inode->pathlength = -1;
231 pathlength++;
232 }
233 else {
234 /* mark node */
235 cur_inode->pathlength = pathlength;
236#if 0
237 if (cur_inode->right) {
238 /* right node of previously unmarked node is unmarked */
239 cur_inode = cur_inode->right;
240 cur_inode->pathlength = -1;
241 pathlength++;
242 }
243 else
244#endif
245 {
246
247 /* time to come up. Keep coming up until an unmarked node is reached */
248 /* or the tree is exhausted */
249 do {
250 cur_inode = cur_inode->parent;
251 pathlength--;
252 }
253 while (cur_inode && (cur_inode->pathlength != -1));
254 if (cur_inode) {
255 /* found unmarked node; mark it and go right */
256 cur_inode->pathlength = pathlength;
257 cur_inode = cur_inode->right;
258 cur_inode->pathlength = -1;
259 pathlength++;
260 /* would be complex if cur_inode could be null here. It can't */
261 }
262 }
263 }
264 }
265 while (cur_inode);
266
267#ifdef DEBUG_HUFFMAN
268 cur_inode = inodes;
269 while (cur_inode < next_inode) {
270 fprintf(stderr, "%d l: %3d%c r: %3d%c freq: %8d pathlength %4d\n",
271 cur_inode - inodes,
272 (cur_inode->left->sym!=-1)?(((struct h_elem *)cur_inode->left)-leaves):(cur_inode->left-inodes),
273 (cur_inode->left->sym!=-1)?'l':'i',
274 (cur_inode->right->sym!=-1)?(((struct h_elem *)cur_inode->right)-leaves):(cur_inode->right-inodes),
275 (cur_inode->right->sym!=-1)?'l':'i',
276 (cur_inode->freq),
277 (cur_inode->pathlength)
278 );
279 cur_inode++;
280 }
281#endif
282 free(inodes);
283
284 /* the pathlengths are already in order, so this sorts by symbol */
285 qsort(leaves, nelem, sizeof(h_elem), cmp_pathlengths);
286
302#if 0
303 pathlength = leaves[0].pathlength;
304 cur_code = 0;
305 for (i = 0; i < nleaves; i++) {
306 while (leaves[i].pathlength < pathlength) {
307 assert(!(cur_code & 1));
308 cur_code >>= 1;
309 pathlength--;
310 }
311 leaves[i].code = cur_code;
312 cur_code++;
313 }
314#else
315 pathlength = leaves[nleaves-1].pathlength;
316 assert(leaves[0].pathlength <= 16); /* this method cannot deal with bigger codes, though
317 the other canonical method can in some cases
318 (because it starts with zeros ) */
319 cur_code = 0;
320 for (i = nleaves - 1; i >= 0; i--) {
321 while (leaves[i].pathlength > pathlength) {
322 cur_code <<= 1;
323 pathlength++;
324 }
325 leaves[i].code = cur_code;
326 cur_code++;
327 }
328#endif
329
330#ifdef DEBUG_HUFFMAN
331 for (i = 0; i < nleaves; i++) {
332 char code[18];
333 int j;
334
335 cur_code = leaves[i].code;
336 code[leaves[i].pathlength] = 0;
337 for (j = leaves[i].pathlength-1; j >= 0; j--) {
338 if (cur_code & 1) code[j] = '1';
339 else code[j] = '0';
340 cur_code >>= 1;
341 }
342 fprintf(stderr, "%3d: %3d %3d %-16.16s '%c'\n", i, leaves[i].freq, leaves[i].pathlength, code,
343 leaves[i].sym);
344 }
345#endif
346 }
347 else if (nleaves == 1) {
348 /* 0 symbols is OK (not according to doc, but according to Caie) */
349 /* but if only one symbol is present, two symbols are required */
350 nleaves = 2;
351 leaves[0].pathlength = leaves[1].pathlength = 1;
352 if (leaves[1].sym > leaves[0].sym) {
353 leaves[1].code = 1;
354 leaves[0].code = 0;
355 }
356 else {
357 leaves[0].code = 1;
358 leaves[1].code = 0;
359 }
360 }
361
362 memset(tree, 0, nelem * sizeof(huff_entry));
363 for (i = 0; i < nleaves; i++) {
364 tree[leaves[i].sym].codelength = leaves[i].pathlength;
365 tree[leaves[i].sym].code = leaves[i].code;
366 }
367
368 free(leaves);
369}
370
371/* from Stuart Caie's code -- I'm hoping this code is too small to encumber
372 this file. If not, you could rip it out and hard-code the tables */
373
374static void lzx_init_static(void)
375{
376 int i, j;
377
378 if (extra_bits[49]) return;
379
380 rloge2 = 1.0/log(2);
381 for (i=0, j=0; i <= 50; i += 2) {
382 extra_bits[i] = extra_bits[i+1] = j; /* 0,0,0,0,1,1,2,2,3,3... */
383 if ((i != 0) && (j < 17)) j++; /* 0,0,1,2,3,4...15,16,17,17,17,17... */
384 }
385
386 for (i=0, j=0; i <= 50; i++) {
387 position_base[i] = j; /* 0,1,2,3,4,6,8,12,16,24,32,... */
388 j += 1 << extra_bits[i]; /* 1,1,1,1,2,2,4,4,8,8,16,16,32,32,... */
389 }
390}
391
393{
394 void *in_arg;
395 void *out_arg;
401 struct lz_info *lzi;
402 /* a 'frame' is an 0x8000 byte thing. Called that because otherwise
403 I'd confuse myself overloading 'block' */
406 int R0, R1, R2;
408 /* this is the LZX block size */
428 short subdivide; /* 0 = don't subdivide, 1 = allowed, -1 = requested */
429};
430
431static int
433{
434 /* force lz compression to stop after every block */
435 int chars_read;
436 int chars_pad;
437
438 lzx_data *lzud = (lzx_data *)lzi->user_data;
439#ifdef OLDFRAMING
440 if (lzud->subdivide < 0) return 0;
441 if (n > lzud->left_in_frame)
442 n = lzud->left_in_frame;
443 if (n > lzud->left_in_block)
444 n = lzud->left_in_block;
445#endif
446 chars_read = lzud->get_bytes(lzud->in_arg, n, buf);
447#ifdef OLDFRAMING
448 lzud->left_in_frame -= chars_read;
449 lzud->left_in_block -= chars_read;
450#else
451 lzud->left_in_frame -= chars_read % LZX_FRAME_SIZE;
452 if (lzud->left_in_frame < 0)
454#endif
455 if ((chars_read < n) && (lzud->left_in_frame)) {
456 chars_pad = n - chars_read;
457 if (chars_pad > lzud->left_in_frame) chars_pad = lzud->left_in_frame;
458 /* never emit a full frame of padding. This prevents silliness when
459 lzx_compress is called when at EOF but EOF not yet detected */
460 if (chars_pad == LZX_FRAME_SIZE) chars_pad = 0;
461#ifdef OLDFRAMING
462 if (chars_pad > lzud->left_in_block) chars_pad = lzud->left_in_block;
463#endif
464 memset(buf + chars_read, 0, chars_pad);
465 lzud->left_in_frame -= chars_pad;
466#ifdef OLDFRAMING
467 lzud->left_in_block -= chars_pad;
468#endif
469 chars_read += chars_pad;
470 }
471 return chars_read;
472}
473
474#ifdef NONSLIDE
475static int find_match_at(lz_info *lzi, int loc, int match_len, int *match_locp)
476{
477 u_char *matchb;
478 u_char *nmatchb;
479 u_char *c1, *c2;
480 int j;
481
482 if (-*match_locp == loc) return -1;
483 if (loc < match_len) return -1;
484
485 matchb = lzi->block_buf + lzi->block_loc + *match_locp;
486 nmatchb = lzi->block_buf + lzi->block_loc - loc;
487 c1 = matchb;
488 c2 = nmatchb;
489 for (j = 0; j < match_len; j++) {
490 if (*c1++ != *c2++) break;
491 }
492 if (j == match_len) {
493#ifdef DEBUG_MATCHES
494 fprintf(stderr, "match found %d, old = %d new = %d len = %d\n", lzi->cur_loc, -*match_locp, loc, match_len);
495#endif
496 *match_locp = -loc;
497 return 0;
498 }
499 return -1;
500}
501#else
502static int find_match_at(lz_info *lzi, int loc, int match_len, int *match_locp)
503{
504 u_char *matchb;
505 u_char *nmatchb;
506 u_char *c1, *c2;
507 int j;
508
509 if (-*match_locp == loc) return -1;
510 if (loc < match_len) return -1;
511
512 matchb = lzi->slide_bufp + *match_locp;
513 if (matchb < lzi->slide_buf) matchb += lzi->slide_buf_size;
514 nmatchb = lzi->slide_bufp - loc;
515 if (nmatchb < lzi->slide_buf) nmatchb += lzi->slide_buf_size;
516 c1 = matchb;
517 c2 = nmatchb;
518 for (j = 0; j < match_len; j++) {
519 if (*c1++ != *c2++) break;
520 if (c1 == lzi->slide_bufe) c1 = lzi->slide_buf;
521 if (c2 == lzi->slide_bufe) c2 = lzi->slide_buf;
522 }
523 if (j == match_len) {
524#ifdef DEBUG_MATCHES
525 fprintf(stderr, "match found %d, old = %d new = %d len = %d\n", lzi->cur_loc, -*match_locp, loc, match_len);
526#endif
527 *match_locp = -loc;
528 return 0;
529 }
530 return -1;
531}
532#endif
533static void check_entropy(lzx_data *lzud, int main_index)
534{
535 /* entropy = - sum_alphabet P(x) * log2 P(x) */
536 /* entropy = - sum_alphabet f(x)/N * log2 (f(x)/N) */
537 /* entropy = - 1/N sum_alphabet f(x) * (log2 f(x) - log2 N) */
538 /* entropy = - 1/N (sum_alphabet f(x) * log2 f(x)) - sum_alphabet f(x) log2 N */
539 /* entropy = - 1/N (sum_alphabet f(x) * log2 f(x)) - log2 N sum_alphabet f(x) */
540 /* entropy = - 1/N (sum_alphabet f(x) * log2 f(x)) - N * log2 N */
541
542 /* entropy = - 1/N ((sum_alphabet f(x) * log2 f(x) ) - N * log2 N) */
543 /* entropy = - 1/N ((sum_alphabet f(x) * ln f(x) * 1/ln 2) - N * ln N * 1/ln 2) */
544 /* entropy = 1/(N ln 2) (N * ln N - (sum_alphabet f(x) * ln f(x))) */
545 /* entropy = 1/(N ln 2) (N * ln N + (sum_alphabet -f(x) * ln f(x))) */
546
547 /* entropy = 1/(N ln 2) ( sum_alphabet ln N * f(x) + (sum_alphabet -f(x) * ln f(x))) */
548 /* entropy = 1/(N ln 2) ( sum_alphabet ln N * f(x) + (-f(x) * ln f(x))) */
549 /* entropy = -1/(N ln 2) ( sum_alphabet -ln N * f(x) + (f(x) * ln f(x))) */
550 /* entropy = -1/(N ln 2) ( sum_alphabet f(x)(- ln N + ln f(x))) */
551 /* entropy = -1/(N ln 2) ( sum_alphabet f(x)(ln f(x)/N)) */
552 /* entropy = -1/N ( sum_alphabet (1/(ln 2))f(x)(ln f(x)/N)) */
553 /* entropy = -1/N ( sum_alphabet f(x)(log2 f(x)/N)) */
554 /* entropy = - ( sum_alphabet f(x)/N(log2 f(x)/N)) */
555 /* entropy = - ( sum_alphabet P(x)(log2 P(x))) */
556
557
558 double freq;
559 double n_ln_n;
560 double rn_ln2;
561 double cur_ratio;
562 int n;
563
564 /* delete old entropy accumulation */
565 if (lzud->main_freq_table[main_index] != 1) {
566 freq = (double)lzud->main_freq_table[main_index]-1;
567 lzud->main_entropy += freq * log(freq);
568 }
569 /* add new entropy accumulation */
570 freq = (double)lzud->main_freq_table[main_index];
571 lzud->main_entropy -= freq * log(freq);
572 n = lzud->block_codesp - lzud->block_codes;
573
574 if (((n & 0xFFF) == 0) && (lzud->left_in_block >= 0x1000)) {
575 n_ln_n = (double)n * log((double)n);
576 rn_ln2 = rloge2 / (double)n;
577 cur_ratio = (n * rn_ln2 *(n_ln_n + lzud->main_entropy) + 24 + 3 * 80 + NUM_CHARS + (lzud->main_tree_size-NUM_CHARS)*3 + NUM_SECONDARY_LENGTHS ) / (double)n;
578#ifdef DEBUG_ENTROPY
579 fprintf(stderr, "n = %d\n", n);
580 fprintf(stderr, "main entropy = %f\n", rn_ln2 *(n_ln_n + lzud->main_entropy) );
581 fprintf(stderr, "compression ratio (raw) = %f\n", 100.0 * rn_ln2 *(n_ln_n + lzud->main_entropy) /9.0 );
582 fprintf(stderr, "compression ratio (ovh) = %f\n", 100.0 * cur_ratio/9.0);
583#endif
584 if (cur_ratio > lzud->last_ratio) {
585#ifdef DEBUG_ENTROPY
586 fprintf(stderr, "resetting huffman tables at %d\n", n);
587#endif
588 lzud->subdivide = -1;
590 }
591 lzud->last_ratio = cur_ratio;
592 }
593}
594
595static int
596lzx_output_match(lz_info *lzi, int match_pos, int match_len)
597{
598 lzx_data *lzud = (lzx_data *)lzi->user_data;
599 uint32_t formatted_offset;
600 uint32_t position_footer;
601 uint8_t length_footer;
602 uint8_t length_header;
603 uint16_t len_pos_header;
604 int position_slot;
605 short btdt;
606
607#ifdef DEBUG_LZ
608 {
609 int i;
610 int pos;
611 for (i = 0; i < match_len; i++) {
612
613#ifdef NONSLIDE
614 pos = match_pos + lzi->block_loc + i;
615 fprintf(stderr, "%c", lzi->block_buf[pos]);
616#else
617 pos = match_pos + lzi->front_offset + i;
618 if (pos > lzi->slide_buf_size)
619 pos -= lzi->slide_buf_size;
620 fprintf(stderr, "%c", lzi->slide_buf[pos]);
621#endif
622 }
623 }
624#endif
625 position_footer = 0;
626 btdt = 0;
627 testforr:
628 if (match_pos == -lzud->R0) {
629 match_pos = 0;
630 formatted_offset = 0;
631 position_slot = 0;
632 }
633 else if (match_pos == -lzud->R1) {
634 lzud->R1 = lzud->R0;
635 lzud->R0 = -match_pos;
636 match_pos = 1;
637 formatted_offset = 1;
638 position_slot = 1;
639 }
640 else if (match_pos == -lzud->R2) {
641 lzud->R2 = lzud->R0;
642 lzud->R0 = -match_pos;
643 match_pos = 2;
644 formatted_offset = 2;
645 position_slot = 2;
646 }
647 else {
648 if (!btdt) {
649 btdt = 1;
650 if (find_match_at(lzi, lzud->R0, match_len, &match_pos) == 0)
651 goto testforr;
652 if (find_match_at(lzi, lzud->R1, match_len, &match_pos) == 0)
653 goto testforr;
654 if (find_match_at(lzi, lzud->R2, match_len, &match_pos) == 0)
655 goto testforr;
656 }
657
658 formatted_offset = -match_pos + 2;
659
660 if ((match_len < 3) ||
661 ((formatted_offset >= 64) && (match_len < 4)) ||
662 ((formatted_offset >= 2048) && (match_len < 5)) ||
663 ((formatted_offset >= 65536) && (match_len < 6))) {
664 /* reject matches where extra_bits will likely be bigger than just outputting
665 literals. The numbers are basically derived through guessing
666 and trial and error */
667 return -1; /* reject the match */
668 }
669
670 lzud->R2 = lzud->R1;
671 lzud->R1 = lzud->R0;
672 lzud->R0 = -match_pos;
673
674 /* calculate position base using binary search of table; if log2 can be
675 done in hardware, approximation might work;
676 trunc(log2(formatted_offset*formatted_offset)) gets either the proper
677 position slot or the next one, except for slots 0, 1, and 39-49
678
679 Slots 0-1 are handled by the R0-R1 procedures
680
681 Slots 36-49 (formatted_offset >= 262144) can be found by
682 (formatted_offset/131072) + 34 ==
683 (formatted_offset >> 17) + 34;
684 */
685 if (formatted_offset >= 262144) {
686 position_slot = (formatted_offset >> 17) + 34;
687 }
688 else {
689 int left, right, mid;
690
691 left = 3;
692 right = lzud->num_position_slots - 1;
693 position_slot = -1;
694 while (left <= right) {
695 mid = (left + right)/2;
696 if ((position_base[mid] <= formatted_offset) &&
697 position_base[mid+1] > formatted_offset) {
698 position_slot = mid;
699 break;
700 }
701#if 0
702 fprintf(stderr, "BEFORE: %06x %06x %06x %06x\n",
704 formatted_offset, position_base[right]);
705#endif
706 if (formatted_offset > position_base[mid])
707 /* too low */
708 left = mid + 1;
709 else /* too high */
710 right = mid;
711#if 0
712 fprintf(stderr, "AFTER : %06x %06x %06x %06x\n",
714 formatted_offset, position_base[right]);
715#endif
716 }
717#ifdef DEBUG_POSITION_SLOT_LOOKUP
718 if (position_slot < 0) {
719 fprintf(stderr, "lmr npr: %d %d %d %d\n", left, mid, right, lzud->num_position_slots);
720 fprintf(stderr, "AFTER : %07d %07d %07d %07d\n",
722 formatted_offset, position_base[right]);
723 fprintf(stderr, "(%d, %d, %d, %d, %d)\n", match_pos, match_len, formatted_offset, position_slot, position_footer);
724 }
725#endif
726 assert(position_slot >= 0);
727 /* FIXME precalc extra_mask table */
728 }
729 position_footer = ((1UL << extra_bits[position_slot]) - 1) & formatted_offset;
730 }
731#ifdef DEBUG_MATCHES
732#ifdef NONSLIDE
733 fprintf(stderr, "(%08x, %d, %d, %d, %d, %d)\n", lzud->lzi->cur_loc , match_pos, match_len, formatted_offset, position_slot, position_footer);
734#else
735 fprintf(stderr, "(%08x, %d, %d, %d, %d, %d)\n", lzud->lzi->cur_loc - lzud->lzi->chars_in_match , match_pos, match_len, formatted_offset, position_slot, position_footer);
736#endif
737#endif
738 /* match length = 8 bits */
739 /* position_slot = 6 bits */
740 /* position_footer = 17 bits */
741 /* total = 31 bits */
742 /* plus one to say whether it's a literal or not */
743 *lzud->block_codesp++ = 0x80000000 | /* bit 31 in intelligent bit ordering */
744 (position_slot << 25) | /* bits 30-25 */
745 (position_footer << 8) | /* bits 8-24 */
746 (match_len - MIN_MATCH); /* bits 0-7 */
747
748 if (match_len < (NUM_PRIMARY_LENGTHS + MIN_MATCH)) {
749 length_header = match_len - MIN_MATCH;
750 /* length_footer = 255; */ /* not necessary */
751 }
752 else {
753 length_header = NUM_PRIMARY_LENGTHS;
754 length_footer = match_len - (NUM_PRIMARY_LENGTHS + MIN_MATCH);
755 lzud->length_freq_table[length_footer]++;
756 }
757 len_pos_header = (position_slot << 3) | length_header;
758 lzud->main_freq_table[len_pos_header + NUM_CHARS]++;
759 if (extra_bits[position_slot] >= 3) {
760 lzud->aligned_freq_table[position_footer & 7]++;
761 }
762#ifndef OLDFRAMING
763 lzud->left_in_block -= match_len;
764#endif
765 if (lzud->subdivide)
766 check_entropy(lzud, len_pos_header + NUM_CHARS);
767 return 0; /* accept the match */
768}
769
770static void
772{
773 lzx_data *lzud = (lzx_data *)lzi->user_data;
774
775#ifndef OLDFRAMING
776 lzud->left_in_block--;
777#endif
778 *lzud->block_codesp++ = ch;
779#ifdef DEBUG_LZ
780 fprintf(stderr, "%c", ch);
781#endif
782 lzud->main_freq_table[ch]++;
783 if (lzud->subdivide)
784 check_entropy(lzud, ch);
785}
786
787static void lzx_write_bits(lzx_data *lzxd, int nbits, uint32_t bits)
788{
789 int cur_bits;
790 int shift_bits;
791 int rshift_bits;
792 uint16_t mask_bits;
793
794#ifdef DEBUG_BITBUF
795 fprintf(stderr, "WB: %2d %08x\n", nbits, bits);
796#endif
797 cur_bits = lzxd->bits_in_buf;
798 while ((cur_bits + nbits) >= 16) {
799 shift_bits = 16 - cur_bits;
800 rshift_bits = nbits - shift_bits;
801 if (shift_bits == 16) {
802 lzxd->bit_buf = (bits>>rshift_bits) & 0xFFFF;
803 }
804 else {
805 mask_bits = (1U << shift_bits) - 1;
806 lzxd->bit_buf <<= shift_bits;
807 lzxd->bit_buf |= (bits>>rshift_bits) & mask_bits;
808 }
809#ifdef DEBUG_BITBUF
810 fprintf(stderr, "WBB: %04x\n", lzxd->bit_buf);
811#endif
812#ifdef LZX_BIG_ENDIAN
813 lzxd->bit_buf = ((lzxd->bit_buf & 0xFF)<<8) | (lzxd->bit_buf >> 8);
814#endif
815 lzxd->put_bytes(lzxd->out_arg, sizeof(lzxd->bit_buf), &lzxd->bit_buf);
816 lzxd->len_compressed_output += sizeof(lzxd->bit_buf);
817 lzxd->bit_buf = 0;
818 nbits -= shift_bits;
819 cur_bits = 0;
820 }
821 /* (cur_bits + nbits) < 16. If nbits = 0, we're done.
822 otherwise move bits in */
823 shift_bits = nbits;
824 mask_bits = (1U << shift_bits) - 1;
825 lzxd->bit_buf <<= shift_bits;
826 lzxd->bit_buf |= bits & mask_bits;
827 cur_bits += nbits;
828
829#ifdef DEBUG_BITBUF
830 fprintf(stderr, "OBB: %2d %04x\n", cur_bits, lzxd->bit_buf);
831#endif
832 lzxd->bits_in_buf = cur_bits;
833}
834
835static void lzx_align_output(lzx_data *lzxd)
836{
837 if (lzxd->bits_in_buf) {
838 lzx_write_bits(lzxd, 16 - lzxd->bits_in_buf, 0);
839 }
840 if (lzxd->mark_frame)
842}
843
844static void
846{
847 uint32_t *cursor = lzxd->block_codes;
848 uint32_t *endp = lzxd->block_codesp;
849 uint16_t position_slot;
850 uint32_t position_footer;
851 uint32_t match_len_m2; /* match length minus 2, which is MIN_MATCH */
852 uint32_t verbatim_bits;
853 uint32_t block_code;
854 uint16_t length_header;
855 uint16_t length_footer;
856 uint16_t len_pos_header;
857 huff_entry *huffe;
858 int frame_count = (lzxd->len_uncompressed_input % LZX_FRAME_SIZE);
859
860 lzxd->len_uncompressed_input -= frame_count; /* will be added back in later */
861 while (cursor < endp) {
862 block_code = *cursor++;
863 if (block_code & 0x80000000) {
864 /*
865 * 0x80000000 | bit 31 in intelligent bit ordering
866 * (position_slot << 25) | bits 30-25
867 * (position_footer << 8) | bits 8-24
868 * (match_len - MIN_MATCH); bits 0-7
869 *
870 */
871
872 match_len_m2 = block_code & 0xFF; /* 8 bits */
873 position_footer = (block_code >> 8)& 0x1FFFF; /* 17 bits */
874 position_slot = (block_code >> 25) & 0x3F; /* 6 bits */
875
876#ifdef DEBUG_MATCHES_2
877 fprintf(stderr, "%08x, %3d %2d %d\n", lzxd->len_uncompressed_input + frame_count, match_len_m2, position_slot, position_footer);
878#endif
879 if (match_len_m2 < NUM_PRIMARY_LENGTHS) {
880 length_header = match_len_m2;
881 length_footer = 255; /* personal encoding for NULL */
882 }
883 else {
884 length_header = NUM_PRIMARY_LENGTHS;
885 length_footer = match_len_m2 - NUM_PRIMARY_LENGTHS;
886 }
887 len_pos_header = (position_slot << 3) | length_header;
888 huffe = &lzxd->main_tree[len_pos_header+NUM_CHARS];
889 lzx_write_bits(lzxd, huffe->codelength, huffe->code);
890 if (length_footer != 255) {
891 huffe = &lzxd->length_tree[length_footer];
892 lzx_write_bits(lzxd, huffe->codelength, huffe->code);
893 }
894 if ((block_type == LZX_ALIGNED_OFFSET_BLOCK) && (extra_bits[position_slot] >= 3)) {
895 /* aligned offset block and code */
896 verbatim_bits = position_footer >> 3;
897 lzx_write_bits(lzxd, extra_bits[position_slot] - 3, verbatim_bits);
898 huffe = &lzxd->aligned_tree[position_footer&7];
899 lzx_write_bits(lzxd, huffe->codelength, huffe->code);
900 }
901 else {
902 verbatim_bits = position_footer;
903 lzx_write_bits(lzxd, extra_bits[position_slot], verbatim_bits);
904 }
905 frame_count += match_len_m2 + 2;
906 }
907 else {
908 /* literal */
909 assert(block_code < NUM_CHARS);
910 huffe = &lzxd->main_tree[block_code];
911 lzx_write_bits(lzxd, huffe->codelength, huffe->code);
912 frame_count++;
913 }
914 if (frame_count == LZX_FRAME_SIZE) {
915 lzxd->len_uncompressed_input += frame_count;
916 lzx_align_output(lzxd);
917 frame_count = 0;
918 }
919#ifdef DEBUG_MATCHES_2
920 if (frame_count > LZX_FRAME_SIZE) {
921 fprintf(stderr, "uncomp_len = %x, frame_count = %x, block_code = %08x, match_len_m2 = %d", lzxd->len_uncompressed_input, frame_count, block_code, match_len_m2);
922 }
923#endif
924 assert (frame_count < LZX_FRAME_SIZE);
925 }
926 lzxd->len_uncompressed_input += frame_count;
927}
928
929static int
931 struct huff_entry *tree, uint8_t *prevlengths,
932 int treesize)
933{
934 u_char *codes;
935 u_char *runs;
937 int cur_run;
938 int last_len;
939 huff_entry pretree[20];
940 u_char *codep;
941 u_char *codee;
942 u_char *runp;
943 int excess;
944 int i;
945 int cur_code;
946
947 codep = codes = malloc(treesize*sizeof(char));
948 runp = runs = malloc(treesize*sizeof(char));
949 memset(freqs, 0, sizeof(freqs));
950 cur_run = 1;
951 last_len = tree[0].codelength;
952 for (i = 1; i <= treesize; i++) {
953 if ((i == treesize) || (tree[i].codelength != last_len)) {
954 if (last_len == 0) {
955 while (cur_run >= 20) {
956 excess = cur_run - 20;
957 if (excess > 31) excess = 31;
958 *codep++ = 18;
959 *runp++ = excess;
960 cur_run -= excess + 20;
961 freqs[18]++;
962 }
963 while (cur_run >= 4) {
964 excess = cur_run - 4;
965 if (excess > 15) excess = 15;
966 *codep++ = 17;
967 *runp++ = excess;
968 cur_run -= excess + 4;
969 freqs[17]++;
970 }
971 while (cur_run > 0) {
972 *codep = prevlengths[i - cur_run];
973 freqs[*codep++]++;
974 *runp++ = 0; /* not necessary */
975 cur_run--;
976 }
977 }
978 else {
979 while (cur_run >= 4) {
980 if (cur_run == 4) excess = 0;
981 else excess = 1;
982 *codep++ = 19;
983 *runp++ = excess;
984 freqs[19]++;
985 /* right, MS lies again. Code is NOT
986 prev_len + len (mod 17), it's prev_len - len (mod 17)*/
987 *codep = prevlengths[i-cur_run] - last_len;
988 if (*codep > 16) *codep += 17;
989 freqs[*codep++]++;
990 *runp++ = 0; /* not necessary */
991 cur_run -= excess+4;
992 }
993 while (cur_run > 0) {
994 *codep = prevlengths[i-cur_run] - last_len;
995 if (*codep > 16) *codep += 17;
996 *runp++ = 0; /* not necessary */
997 cur_run--;
998 freqs[*codep++]++;
999 }
1000 }
1001 if (i != treesize)
1002 last_len = tree[i].codelength;
1003 cur_run = 0;
1004 }
1005 cur_run++;
1006 }
1007 codee = codep;
1008#ifdef DEBUG_TREE_COMPRESSION
1009 *codep++ = 255;
1010 *runp++ = 255;
1011 fprintf(stderr, "num: len code run\n");
1012 for (i = 0; i < treesize; i++) {
1013 fprintf(stderr, "%3d: %2d %2d %2d\n", i, tree[i].codelength, codes[i], runs[i]);
1014 }
1015#endif
1016 /* now create the huffman table and write out the pretree */
1018 for (i = 0; i < LZX_PRETREE_SIZE; i++) {
1019 lzx_write_bits(lzxd, 4, pretree[i].codelength);
1020 }
1021 codep = codes;
1022 runp = runs;
1023 cur_run = 0;
1024 while (codep < codee) {
1025 cur_code = *codep++;
1026 lzx_write_bits(lzxd, pretree[cur_code].codelength, pretree[cur_code].code);
1027 if (cur_code == 17) {
1028 cur_run += *runp + 4;
1029 lzx_write_bits(lzxd, 4, *runp);
1030 }
1031 else if (cur_code == 18) {
1032 cur_run += *runp + 20;
1033 lzx_write_bits(lzxd, 5, *runp);
1034 }
1035 else if (cur_code == 19) {
1036 cur_run += *runp + 4;
1037 lzx_write_bits(lzxd, 1, *runp);
1038 cur_code = *codep++;
1039 lzx_write_bits(lzxd, pretree[cur_code].codelength, pretree[cur_code].code);
1040 runp++;
1041 }
1042 else {
1043 cur_run++;
1044 }
1045 runp++;
1046 }
1047 free(codes);
1048 free(runs);
1049 return 0;
1050}
1051
1052void
1054{
1055 lzxd->need_1bit_header = 1;
1056 lzxd->R0 = lzxd->R1 = lzxd->R2 = 1;
1057 memset(lzxd->prev_main_treelengths, 0, lzxd->main_tree_size * sizeof(uint8_t));
1059 lz_reset(lzxd->lzi);
1060}
1061
1062int lzx_compress_block(lzx_data *lzxd, int block_size, int subdivide)
1063{
1064 int i;
1065 uint32_t written_sofar = 0;
1066 int block_type;
1067 long uncomp_bits;
1068 long comp_bits;
1069 long comp_bits_ovh;
1070 long uncomp_length;
1071
1072 if ((lzxd->block_size != block_size) || (lzxd->block_codes == NULL)) {
1073 if (lzxd->block_codes != NULL) free(lzxd->block_codes);
1074 lzxd->block_size = block_size;
1075 lzxd->block_codes = malloc(block_size * sizeof(uint32_t));
1076 }
1077 lzxd->subdivide = subdivide?1:0;
1078
1079 lzxd->left_in_block = block_size;
1081 lzxd->main_entropy = 0.0;
1082 lzxd->last_ratio = 9999999.0;
1083 lzxd->block_codesp = lzxd->block_codes;
1084
1085 memset(lzxd->length_freq_table, 0, NUM_SECONDARY_LENGTHS * sizeof(int));
1086 memset(lzxd->main_freq_table, 0, lzxd->main_tree_size * sizeof(int));
1087 memset(lzxd->aligned_freq_table, 0, LZX_ALIGNED_SIZE * sizeof(int));
1088 do {
1089 lz_compress(lzxd->lzi, lzxd->left_in_block);
1090 if (lzxd->left_in_frame == 0)
1092
1093 if ((lzxd->subdivide<0) || !lzxd->left_in_block ||
1094 (!lz_left_to_process(lzxd->lzi) && lzxd->at_eof(lzxd->in_arg))) {
1095 /* now one block is LZ-analyzed. */
1096 /* time to write it out */
1097 uncomp_length = lzxd->block_size - lzxd->left_in_block - written_sofar;
1098 /* uncomp_length will sometimes be 0 when input length is
1099 an exact multiple of frame size */
1100 if (uncomp_length == 0)
1101 continue;
1102 if (lzxd->subdivide < 0) {
1103#ifdef DEBUG_ENTROPY
1104 fprintf(stderr, "subdivided\n");
1105#endif
1106 lzxd->subdivide = 1;
1107 }
1108
1109 if (lzxd->need_1bit_header) {
1110 /* one bit Intel preprocessing header */
1111 /* always 0 because this implementation doesn't do Intel preprocessing */
1112 lzx_write_bits(lzxd, 1, 0);
1113 lzxd->need_1bit_header = 0;
1114 }
1115
1116 /* handle extra bits */
1117 uncomp_bits = comp_bits = 0;
1119 for (i = 0; i < LZX_ALIGNED_SIZE; i++) {
1120 uncomp_bits += lzxd->aligned_freq_table[i]* 3;
1121 comp_bits += lzxd->aligned_freq_table[i]* lzxd->aligned_tree[i].codelength;
1122 }
1123 comp_bits_ovh = comp_bits + LZX_ALIGNED_SIZE * 3;
1124 if (comp_bits_ovh < uncomp_bits)
1125 block_type = LZX_ALIGNED_OFFSET_BLOCK;
1126 else
1127 block_type = LZX_VERBATIM_BLOCK;
1128
1129#ifdef DEBUG_EXTRA_BITS
1130 fprintf(stderr, "Extra bits uncompressed: %5d compressed: %5d compressed w/overhead %5d gain/loss %5d\n", uncomp_bits, comp_bits, comp_bits_ovh, uncomp_bits - comp_bits_ovh);
1131#endif
1132
1133 /* block type */
1134 lzx_write_bits(lzxd, 3, block_type);
1135 /* uncompressed length */
1136 lzx_write_bits(lzxd, 24, uncomp_length);
1137
1138 written_sofar = lzxd->block_size - lzxd->left_in_block;
1139
1140 /* now write out the aligned offset trees if present */
1141 if (block_type == LZX_ALIGNED_OFFSET_BLOCK) {
1142 for (i = 0; i < LZX_ALIGNED_SIZE; i++) {
1143 lzx_write_bits(lzxd, 3, lzxd->aligned_tree[i].codelength);
1144 }
1145 }
1146 /* end extra bits */
1148 lzxd->main_freq_table, lzxd->main_tree);
1150 lzxd->length_freq_table, lzxd->length_tree);
1151
1152
1153
1154 /* now write the pre-tree and tree for main 1 */
1156
1157 /* now write the pre-tree and tree for main 2*/
1160 lzxd->main_tree_size - NUM_CHARS);
1161
1162 /* now write the pre tree and tree for length */
1165
1166 /* now write literals */
1167 lzx_write_compressed_literals(lzxd, block_type);
1168
1169 /* copy treelengths somewhere safe to do delta compression */
1170 for (i = 0; i < lzxd->main_tree_size; i++) {
1172 }
1173 for (i = 0; i < NUM_SECONDARY_LENGTHS; i++) {
1175 }
1176 lzxd->main_entropy = 0.0;
1177 lzxd->last_ratio = 9999999.0;
1178 lzxd->block_codesp = lzxd->block_codes;
1179
1180 memset(lzxd->length_freq_table, 0, NUM_SECONDARY_LENGTHS * sizeof(int));
1181 memset(lzxd->main_freq_table, 0, lzxd->main_tree_size * sizeof(int));
1182 memset(lzxd->aligned_freq_table, 0, LZX_ALIGNED_SIZE * sizeof(int));
1183 }
1184 }
1185 while (lzxd->left_in_block && (lz_left_to_process(lzxd->lzi) || !lzxd->at_eof(lzxd->in_arg)));
1186 return 0;
1187}
1188
1189int lzx_init(struct lzx_data **lzxdp, int wsize_code,
1190 lzx_get_bytes_t get_bytes, void *get_bytes_arg,
1191 lzx_at_eof_t at_eof,
1192 lzx_put_bytes_t put_bytes, void *put_bytes_arg,
1193 lzx_mark_frame_t mark_frame, void *mark_frame_arg)
1194{
1195 int wsize;
1196 struct lzx_data *lzxd;
1197
1198 if ((wsize_code < 15) || (wsize_code > 21)) {
1199 return -1;
1200 }
1202
1203 *lzxdp = lzxd = malloc(sizeof(*lzxd));
1204 if (lzxd == 0)
1205 return -2;
1206
1207 lzxd->in_arg = get_bytes_arg;
1208 lzxd->out_arg = put_bytes_arg;
1210 lzxd->get_bytes = get_bytes;
1211 lzxd->put_bytes = put_bytes;
1212 lzxd->at_eof = at_eof;
1213 lzxd->mark_frame = mark_frame;
1214
1215 wsize = 1 << (wsize_code);
1216
1217 lzxd->bits_in_buf = 0;
1218 lzxd->block_codes = NULL;
1219 lzxd->num_position_slots = num_position_slots[wsize_code-15];
1220 lzxd->main_tree_size = (NUM_CHARS + 8 * lzxd->num_position_slots);
1221
1222 lzxd->main_freq_table = malloc(sizeof(int) * lzxd->main_tree_size);
1223 lzxd->main_tree = malloc(sizeof(huff_entry)* lzxd->main_tree_size);
1224 lzxd->prev_main_treelengths = malloc(sizeof(uint8_t)*lzxd->main_tree_size);
1225
1226 lzxd->lzi = malloc(sizeof (*lzxd->lzi));
1227 /* the -3 prevents matches at wsize, wsize-1, wsize-2, all of which are illegal */
1228 lz_init(lzxd->lzi, wsize, wsize - 3, MAX_MATCH, MIN_MATCH, LZX_FRAME_SIZE,
1230 lzxd->len_uncompressed_input = 0;
1231 lzxd->len_compressed_output = 0;
1232 lzx_reset(lzxd);
1233 return 0;
1234}
1235
1236int lzx_finish(struct lzx_data *lzxd, struct lzx_results *lzxr)
1237{
1238 /* lzx_align_output(lzxd); Not needed as long as frame padding is in place */
1239 if (lzxr) {
1242 }
1243 lz_release(lzxd->lzi);
1244 free(lzxd->lzi);
1246 free(lzxd->main_tree);
1247 free(lzxd->main_freq_table);
1248 free(lzxd);
1249 return 0;
1250}
1251
unsigned short int uint16_t
Definition: acefiex.h:54
#define NUM_CHARS
Definition: chargen.c:15
#define free
Definition: debug_ros.c:5
#define malloc
Definition: debug_ros.c:4
#define NULL
Definition: types.h:112
UCHAR u_char
Definition: types.h:80
UINT32 uint32_t
Definition: types.h:75
static const DWORD freqs[10]
Definition: mpegsplit.c:111
#define assert(x)
Definition: debug.h:53
#define MIN_MATCH
Definition: zutil.h:64
#define MAX_MATCH
Definition: zutil.h:65
GLdouble n
Definition: glext.h:7729
GLdouble GLdouble right
Definition: glext.h:10859
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
GLenum GLuint GLenum GLsizei const GLchar * buf
Definition: glext.h:7751
GLenum GLint GLenum GLsizei GLsizei GLsizei GLint GLsizei const GLvoid * bits
Definition: glext.h:10929
GLint left
Definition: glext.h:7726
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint GLint GLint j
Definition: glfuncs.h:250
static unsigned char * codep
Definition: i386-dis.c:1286
const char cursor[]
Definition: icontest.c:13
#define stderr
Definition: stdio.h:100
_Check_return_opt_ _CRTIMP int __cdecl fprintf(_Inout_ FILE *_File, _In_z_ _Printf_format_string_ const char *_Format,...)
static DWORD block_size(DWORD block)
Definition: jsutils.c:66
if(dx< 0)
Definition: linetemp.h:194
void lz_reset(lz_info *lzi)
Definition: lz_nonslide.c:90
void lz_release(lz_info *lzi)
Definition: lz_nonslide.c:83
int lz_compress(lz_info *lzi, int nchars)
Definition: lz_nonslide.c:289
int lz_left_to_process(lz_info *lzi)
Definition: lz_nonslide.c:142
void lz_stop_compressing(lz_info *lzi)
Definition: lz_nonslide.c:283
void lz_init(lz_info *lzi, int wsize, int max_dist, int max_match, int min_match, int frame_size, get_chars_t get_chars, output_match_t output_match, output_literal_t output_literal, void *user_data)
Definition: lz_nonslide.c:42
int(* lzx_get_bytes_t)(void *arg, int n, void *buf)
Definition: lzx_compress.h:19
int(* lzx_at_eof_t)(void *arg)
Definition: lzx_compress.h:22
int(* lzx_put_bytes_t)(void *arg, int n, void *buf)
Definition: lzx_compress.h:20
void(* lzx_mark_frame_t)(void *arg, uint32_t uncomp, uint32_t comp)
Definition: lzx_compress.h:21
#define LZX_PRETREE_SIZE
Definition: lzx_constants.h:35
#define LZX_ALIGNED_SIZE
Definition: lzx_constants.h:37
#define LZX_MAX_CODE_LENGTH
Definition: lzx_constants.h:33
#define NUM_PRIMARY_LENGTHS
Definition: lzx_constants.h:29
#define LZX_FRAME_SIZE
Definition: lzx_constants.h:34
#define LZX_ALIGNED_OFFSET_BLOCK
Definition: lzx_constants.h:40
#define LZX_VERBATIM_BLOCK
Definition: lzx_constants.h:39
#define NUM_SECONDARY_LENGTHS
Definition: lzx_constants.h:30
int lzx_finish(struct lzx_data *lzxd, struct lzx_results *lzxr)
Definition: lzx_layer.c:1236
int lzx_init(struct lzx_data **lzxdp, int wsize_code, lzx_get_bytes_t get_bytes, void *get_bytes_arg, lzx_at_eof_t at_eof, lzx_put_bytes_t put_bytes, void *put_bytes_arg, lzx_mark_frame_t mark_frame, void *mark_frame_arg)
Definition: lzx_layer.c:1189
short num_position_slots[]
Definition: lzx_layer.c:50
int lzx_compress_block(lzx_data *lzxd, int block_size, int subdivide)
Definition: lzx_layer.c:1062
unsigned long position_base[51]
Definition: lzx_layer.c:51
static void lzx_output_literal(lz_info *lzi, u_char ch)
Definition: lzx_layer.c:771
static void lzx_write_compressed_literals(lzx_data *lzxd, int block_type)
Definition: lzx_layer.c:845
static int lzx_output_match(lz_info *lzi, int match_pos, int match_len)
Definition: lzx_layer.c:596
static void lzx_write_bits(lzx_data *lzxd, int nbits, uint32_t bits)
Definition: lzx_layer.c:787
double rloge2
Definition: lzx_layer.c:53
u_char extra_bits[52]
Definition: lzx_layer.c:52
static void check_entropy(lzx_data *lzud, int main_index)
Definition: lzx_layer.c:533
static int cmp_pathlengths(const void *in_a, const void *in_b)
Definition: lzx_layer.c:94
static int find_match_at(lz_info *lzi, int loc, int match_len, int *match_locp)
Definition: lzx_layer.c:502
void lzx_reset(lzx_data *lzxd)
Definition: lzx_layer.c:1053
static int cmp_leaves(const void *in_a, const void *in_b)
Definition: lzx_layer.c:77
static void lzx_align_output(lzx_data *lzxd)
Definition: lzx_layer.c:835
static void build_huffman_tree(int nelem, int max_code_length, int *freq, huff_entry *tree)
Definition: lzx_layer.c:111
static int lzx_write_compressed_tree(struct lzx_data *lzxd, struct huff_entry *tree, uint8_t *prevlengths, int treesize)
Definition: lzx_layer.c:930
static void lzx_init_static(void)
Definition: lzx_layer.c:374
static int lzx_get_chars(lz_info *lzi, int n, u_char *buf)
Definition: lzx_layer.c:432
#define for
Definition: utility.h:88
static const char mbstate_t *static wchar_t const char mbstate_t *static const wchar_t int *static double
Definition: string.c:80
BYTE uint8_t
Definition: msvideo1.c:66
#define f2(x, y, z)
Definition: sha1.c:31
#define f1(x, y, z)
Definition: sha1.c:30
#define memset(x, y, z)
Definition: compat.h:39
#define log(outFile, fmt,...)
Definition: util.h:15
void __cdecl qsort(_Inout_updates_bytes_(_NumOfElements *_SizeOfElements) void *_Base, _In_ size_t _NumOfElements, _In_ size_t _SizeOfElements, _In_ int(__cdecl *_PtFuncCompare)(const void *, const void *))
#define nelem(x)
Definition: shaptest.c:19
Definition: inflate.c:139
unsigned short code
Definition: lzx_layer.c:69
struct ih_elem * parent
Definition: lzx_layer.c:68
short sym
Definition: lzx_layer.c:66
short pathlength
Definition: lzx_layer.c:67
int freq
Definition: lzx_layer.c:65
Definition: lzx_layer.c:72
unsigned short code
Definition: lzx_layer.c:74
short codelength
Definition: lzx_layer.c:73
short pathlength
Definition: lzx_layer.c:58
int freq
Definition: lzx_layer.c:56
struct ih_elem * left
Definition: lzx_layer.c:60
struct ih_elem * right
Definition: lzx_layer.c:61
struct ih_elem * parent
Definition: lzx_layer.c:59
short sym
Definition: lzx_layer.c:57
int cur_loc
Definition: lz_nonslide.h:37
u_char * block_buf
Definition: lz_nonslide.h:33
int wsize
Definition: lz_nonslide.h:30
void * user_data
Definition: lz_nonslide.h:50
int block_loc
Definition: lz_nonslide.h:38
uint32_t len_uncompressed_input
Definition: lzx_layer.c:425
void * in_arg
Definition: lzx_layer.c:394
int left_in_frame
Definition: lzx_layer.c:404
short need_1bit_header
Definition: lzx_layer.c:427
void * mark_frame_arg
Definition: lzx_layer.c:396
int num_position_slots
Definition: lzx_layer.c:407
void * out_arg
Definition: lzx_layer.c:395
lzx_at_eof_t at_eof
Definition: lzx_layer.c:398
lzx_put_bytes_t put_bytes
Definition: lzx_layer.c:399
short subdivide
Definition: lzx_layer.c:428
double last_ratio
Definition: lzx_layer.c:422
int length_freq_table[NUM_SECONDARY_LENGTHS]
Definition: lzx_layer.c:411
uint32_t * block_codesp
Definition: lzx_layer.c:414
int main_tree_size
Definition: lzx_layer.c:418
int bits_in_buf
Definition: lzx_layer.c:420
huff_entry aligned_tree[LZX_ALIGNED_SIZE]
Definition: lzx_layer.c:417
uint8_t * prev_main_treelengths
Definition: lzx_layer.c:423
int R2
Definition: lzx_layer.c:406
int block_size
Definition: lzx_layer.c:409
uint16_t bit_buf
Definition: lzx_layer.c:419
struct lz_info * lzi
Definition: lzx_layer.c:401
int R1
Definition: lzx_layer.c:406
lzx_mark_frame_t mark_frame
Definition: lzx_layer.c:400
uint32_t len_compressed_output
Definition: lzx_layer.c:426
int left_in_block
Definition: lzx_layer.c:405
int * main_freq_table
Definition: lzx_layer.c:410
uint32_t * block_codes
Definition: lzx_layer.c:413
huff_entry length_tree[NUM_SECONDARY_LENGTHS]
Definition: lzx_layer.c:416
double main_entropy
Definition: lzx_layer.c:421
int aligned_freq_table[LZX_ALIGNED_SIZE]
Definition: lzx_layer.c:412
lzx_get_bytes_t get_bytes
Definition: lzx_layer.c:397
uint8_t prev_length_treelengths[NUM_SECONDARY_LENGTHS]
Definition: lzx_layer.c:424
int R0
Definition: lzx_layer.c:406
huff_entry * main_tree
Definition: lzx_layer.c:415
long len_compressed_output
Definition: lzx_compress.h:27
long len_uncompressed_input
Definition: lzx_compress.h:28