28#include "hash_slide.h"
82 if (!
a->freq &&
b->freq)
84 if (
a->freq && !
b->freq)
87 if (
a->freq ==
b->freq)
88 return a->sym -
b->sym;
90 return a->freq -
b->freq;
99 if (
a->pathlength ==
b->pathlength)
101 return a->sym -
b->sym;
104 return b->sym -
a->sym;
106 return b->pathlength -
a->pathlength;
121 unsigned short cur_code;
122 short codes_too_long = 0;
132 for (leaves_left = 0; leaves_left <
nelem; leaves_left++) {
135 leaves[leaves_left].
sym);
137 if (!leaves[leaves_left].
freq)
break;
139 nleaves = leaves_left;
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;
156 next_inode = cur_inode = inodes;
161 ((cur_inode == next_inode) ||
162 (cur_leaf->
freq <= cur_inode->
freq))) {
166 else if (cur_inode != next_inode) {
171 ((cur_inode == next_inode) ||
172 (cur_leaf->
freq <= cur_inode->
freq))) {
176 else if (cur_inode != next_inode) {
184 next_inode->
freq =
f1->freq +
f2->freq;
185 next_inode->
sym = -1;
189 f1->parent = next_inode;
190 f2->parent = next_inode;
191 if (
f1->pathlength >
f2->pathlength)
195 if (next_inode->
pathlength > max_code_length) {
204 while (codes_too_long);
208 while (cur_inode < next_inode) {
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',
214 (cur_inode->
right->sym!=-1)?
'l':
'i',
222 cur_inode = next_inode - 1;
227 if (cur_inode->
sym == -1) {
229 cur_inode = cur_inode->
left;
237 if (cur_inode->
right) {
239 cur_inode = cur_inode->
right;
250 cur_inode = cur_inode->
parent;
253 while (cur_inode && (cur_inode->
pathlength != -1));
257 cur_inode = cur_inode->
right;
269 while (cur_inode < next_inode) {
270 fprintf(
stderr,
"%d l: %3d%c r: %3d%c freq: %8d pathlength %4d\n",
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',
275 (cur_inode->
right->sym!=-1)?
'l':
'i',
305 for (
i = 0;
i < nleaves;
i++) {
311 leaves[
i].
code = cur_code;
320 for (
i = nleaves - 1;
i >= 0;
i--) {
325 leaves[
i].
code = cur_code;
331 for (
i = 0;
i < nleaves;
i++) {
335 cur_code = leaves[
i].
code;
338 if (cur_code & 1)
code[
j] =
'1';
347 else if (nleaves == 1) {
352 if (leaves[1].
sym > leaves[0].
sym) {
363 for (
i = 0;
i < nleaves;
i++) {
381 for (
i=0,
j=0;
i <= 50;
i += 2) {
383 if ((
i != 0) && (
j < 17))
j++;
386 for (
i=0,
j=0;
i <= 50;
i++) {
456 chars_pad =
n - chars_read;
469 chars_read += chars_pad;
482 if (-*match_locp == loc)
return -1;
483 if (loc < match_len)
return -1;
489 for (
j = 0;
j < match_len;
j++) {
490 if (*c1++ != *c2++)
break;
492 if (
j == match_len) {
494 fprintf(
stderr,
"match found %d, old = %d new = %d len = %d\n", lzi->
cur_loc, -*match_locp, loc, match_len);
509 if (-*match_locp == loc)
return -1;
510 if (loc < match_len)
return -1;
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;
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;
523 if (
j == match_len) {
525 fprintf(
stderr,
"match found %d, old = %d new = %d len = %d\n", lzi->
cur_loc, -*match_locp, loc, match_len);
582 fprintf(
stderr,
"compression ratio (ovh) = %f\n", 100.0 * cur_ratio/9.0);
611 for (
i = 0;
i < match_len;
i++) {
617 pos = match_pos + lzi->front_offset +
i;
618 if (
pos > lzi->slide_buf_size)
619 pos -= lzi->slide_buf_size;
628 if (match_pos == -lzud->R0) {
630 formatted_offset = 0;
633 else if (match_pos == -lzud->R1) {
635 lzud->R0 = -match_pos;
637 formatted_offset = 1;
640 else if (match_pos == -lzud->R2) {
642 lzud->R0 = -match_pos;
644 formatted_offset = 2;
650 if (
find_match_at(lzi, lzud->R0, match_len, &match_pos) == 0)
652 if (
find_match_at(lzi, lzud->R1, match_len, &match_pos) == 0)
654 if (
find_match_at(lzi, lzud->R2, match_len, &match_pos) == 0)
658 formatted_offset = -match_pos + 2;
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))) {
672 lzud->R0 = -match_pos;
685 if (formatted_offset >= 262144) {
686 position_slot = (formatted_offset >> 17) + 34;
692 right = lzud->num_position_slots - 1;
717#ifdef DEBUG_POSITION_SLOT_LOOKUP
718 if (position_slot < 0) {
723 fprintf(
stderr,
"(%d, %d, %d, %d, %d)\n", match_pos, match_len, formatted_offset, position_slot, position_footer);
726 assert(position_slot >= 0);
729 position_footer = ((1UL <<
extra_bits[position_slot]) - 1) & formatted_offset;
733 fprintf(
stderr,
"(%08x, %d, %d, %d, %d, %d)\n", lzud->lzi->cur_loc , match_pos, match_len, formatted_offset, position_slot, position_footer);
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);
743 *lzud->block_codesp++ = 0x80000000 |
744 (position_slot << 25) |
745 (position_footer << 8) |
755 lzud->length_freq_table[length_footer]++;
757 len_pos_header = (position_slot << 3) | length_header;
758 lzud->main_freq_table[len_pos_header +
NUM_CHARS]++;
760 lzud->aligned_freq_table[position_footer & 7]++;
763 lzud->left_in_block -= match_len;
798 while ((cur_bits + nbits) >= 16) {
799 shift_bits = 16 - cur_bits;
800 rshift_bits = nbits - shift_bits;
801 if (shift_bits == 16) {
805 mask_bits = (1U << shift_bits) - 1;
824 mask_bits = (1U << shift_bits) - 1;
863 if (block_code & 0x80000000) {
872 match_len_m2 = block_code & 0xFF;
873 position_footer = (block_code >> 8)& 0x1FFFF;
874 position_slot = (block_code >> 25) & 0x3F;
876#ifdef DEBUG_MATCHES_2
880 length_header = match_len_m2;
887 len_pos_header = (position_slot << 3) | length_header;
890 if (length_footer != 255) {
896 verbatim_bits = position_footer >> 3;
902 verbatim_bits = position_footer;
905 frame_count += match_len_m2 + 2;
919#ifdef DEBUG_MATCHES_2
948 runp = runs =
malloc(treesize*
sizeof(
char));
951 last_len =
tree[0].codelength;
952 for (
i = 1;
i <= treesize;
i++) {
953 if ((
i == treesize) || (
tree[
i].codelength != last_len)) {
955 while (cur_run >= 20) {
956 excess = cur_run - 20;
957 if (excess > 31) excess = 31;
960 cur_run -= excess + 20;
963 while (cur_run >= 4) {
964 excess = cur_run - 4;
965 if (excess > 15) excess = 15;
968 cur_run -= excess + 4;
971 while (cur_run > 0) {
972 *
codep = prevlengths[
i - cur_run];
979 while (cur_run >= 4) {
980 if (cur_run == 4) excess = 0;
987 *
codep = prevlengths[
i-cur_run] - last_len;
993 while (cur_run > 0) {
994 *
codep = prevlengths[
i-cur_run] - last_len;
1002 last_len =
tree[
i].codelength;
1008#ifdef DEBUG_TREE_COMPRESSION
1012 for (
i = 0;
i < treesize;
i++) {
1024 while (
codep < codee) {
1025 cur_code = *
codep++;
1027 if (cur_code == 17) {
1028 cur_run += *runp + 4;
1031 else if (cur_code == 18) {
1032 cur_run += *runp + 20;
1035 else if (cur_code == 19) {
1036 cur_run += *runp + 4;
1038 cur_code = *
codep++;
1056 lzxd->
R0 = lzxd->
R1 = lzxd->
R2 = 1;
1100 if (uncomp_length == 0)
1117 uncomp_bits = comp_bits = 0;
1124 if (comp_bits_ovh < uncomp_bits)
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);
1198 if ((wsize_code < 15) || (wsize_code > 21)) {
1203 *lzxdp = lzxd =
malloc(
sizeof(*lzxd));
1207 lzxd->
in_arg = get_bytes_arg;
1208 lzxd->
out_arg = put_bytes_arg;
1215 wsize = 1 << (wsize_code);
unsigned short int uint16_t
static const DWORD freqs[10]
GLboolean GLboolean GLboolean b
GLenum GLuint GLenum GLsizei const GLchar * buf
GLenum GLint GLenum GLsizei GLsizei GLsizei GLint GLsizei const GLvoid * bits
GLboolean GLboolean GLboolean GLboolean a
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
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
static unsigned char * codep
_Check_return_opt_ _CRTIMP int __cdecl fprintf(_Inout_ FILE *_File, _In_z_ _Printf_format_string_ const char *_Format,...)
static DWORD block_size(DWORD block)
void lz_reset(lz_info *lzi)
void lz_release(lz_info *lzi)
int lz_compress(lz_info *lzi, int nchars)
int lz_left_to_process(lz_info *lzi)
void lz_stop_compressing(lz_info *lzi)
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)
int(* lzx_get_bytes_t)(void *arg, int n, void *buf)
int(* lzx_at_eof_t)(void *arg)
int(* lzx_put_bytes_t)(void *arg, int n, void *buf)
void(* lzx_mark_frame_t)(void *arg, uint32_t uncomp, uint32_t comp)
#define LZX_MAX_CODE_LENGTH
#define NUM_PRIMARY_LENGTHS
#define LZX_ALIGNED_OFFSET_BLOCK
#define LZX_VERBATIM_BLOCK
#define NUM_SECONDARY_LENGTHS
int lzx_finish(struct lzx_data *lzxd, struct lzx_results *lzxr)
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)
short num_position_slots[]
int lzx_compress_block(lzx_data *lzxd, int block_size, int subdivide)
unsigned long position_base[51]
static void lzx_output_literal(lz_info *lzi, u_char ch)
static void lzx_write_compressed_literals(lzx_data *lzxd, int block_type)
static int lzx_output_match(lz_info *lzi, int match_pos, int match_len)
static void lzx_write_bits(lzx_data *lzxd, int nbits, uint32_t bits)
static void check_entropy(lzx_data *lzud, int main_index)
static int cmp_pathlengths(const void *in_a, const void *in_b)
static int find_match_at(lz_info *lzi, int loc, int match_len, int *match_locp)
void lzx_reset(lzx_data *lzxd)
static int cmp_leaves(const void *in_a, const void *in_b)
static void lzx_align_output(lzx_data *lzxd)
static void build_huffman_tree(int nelem, int max_code_length, int *freq, huff_entry *tree)
static int lzx_write_compressed_tree(struct lzx_data *lzxd, struct huff_entry *tree, uint8_t *prevlengths, int treesize)
static void lzx_init_static(void)
static int lzx_get_chars(lz_info *lzi, int n, u_char *buf)
static const char mbstate_t *static wchar_t const char mbstate_t *static const wchar_t int *static double
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 *))
uint32_t len_uncompressed_input
lzx_put_bytes_t put_bytes
int length_freq_table[NUM_SECONDARY_LENGTHS]
huff_entry aligned_tree[LZX_ALIGNED_SIZE]
uint8_t * prev_main_treelengths
lzx_mark_frame_t mark_frame
uint32_t len_compressed_output
huff_entry length_tree[NUM_SECONDARY_LENGTHS]
int aligned_freq_table[LZX_ALIGNED_SIZE]
lzx_get_bytes_t get_bytes
uint8_t prev_length_treelengths[NUM_SECONDARY_LENGTHS]
long len_compressed_output
long len_uncompressed_input