ReactOS  0.4.15-dev-5112-g22d8c0f
lzx_layer.c File Reference
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <assert.h>
#include <math.h>
#include "lzx_config.h"
#include "hash_slide.h"
#include "lz_slide.h"
#include "lzx_compress.h"
#include "lzx_constants.h"
Include dependency graph for lzx_layer.c:

Go to the source code of this file.

Classes

struct  ih_elem
 
struct  h_elem
 
struct  huff_entry
 
struct  lzx_data
 

Typedefs

typedef struct ih_elem ih_elem
 
typedef struct h_elem h_elem
 
typedef struct huff_entry huff_entry
 

Functions

static int cmp_leaves (const void *in_a, const void *in_b)
 
static int cmp_pathlengths (const void *in_a, const void *in_b)
 
static void build_huffman_tree (int nelem, int max_code_length, int *freq, huff_entry *tree)
 
static void lzx_init_static (void)
 
static int lzx_get_chars (lz_info *lzi, int n, u_char *buf)
 
static int find_match_at (lz_info *lzi, int loc, int match_len, int *match_locp)
 
static void check_entropy (lzx_data *lzud, int main_index)
 
static int lzx_output_match (lz_info *lzi, int match_pos, int match_len)
 
static void lzx_output_literal (lz_info *lzi, u_char ch)
 
static void lzx_write_bits (lzx_data *lzxd, int nbits, uint32_t bits)
 
static void lzx_align_output (lzx_data *lzxd)
 
static void lzx_write_compressed_literals (lzx_data *lzxd, int block_type)
 
static int lzx_write_compressed_tree (struct lzx_data *lzxd, struct huff_entry *tree, uint8_t *prevlengths, int treesize)
 
void lzx_reset (lzx_data *lzxd)
 
int lzx_compress_block (lzx_data *lzxd, int block_size, int subdivide)
 
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)
 
int lzx_finish (struct lzx_data *lzxd, struct lzx_results *lzxr)
 

Variables

short num_position_slots [] = {30, 32, 34, 36, 38, 42, 50}
 
unsigned long position_base [51]
 
u_char extra_bits [52]
 
double rloge2
 

Typedef Documentation

◆ h_elem

typedef struct h_elem h_elem

◆ huff_entry

◆ ih_elem

Function Documentation

◆ build_huffman_tree()

static void build_huffman_tree ( int  nelem,
int  max_code_length,
int freq,
huff_entry tree 
)
static

Microsoft's second condition on its canonical huffman codes is:

For each level, starting at the deepest level of the tree and then moving upwards, leaf nodes must start as far left as possible. An alternative way of stating this constraint is that if any tree node has children then all tree nodes to the left of it with the same path length must also have children.

These 'alternatives' are not equivalent. The latter alternative gives the common canonical code where the longest code is all zeros. The former gives an opposite code where the longest code is all ones. Microsoft uses the former alternative.

Definition at line 111 of file lzx_layer.c.

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 }
short pathlength
Definition: lzx_layer.c:67
#define free
Definition: debug_ros.c:5
#define assert(x)
Definition: debug.h:53
#define nelem(x)
Definition: shaptest.c:19
_Check_return_opt_ _CRTIMP int __cdecl fprintf(_Inout_ FILE *_File, _In_z_ _Printf_format_string_ const char *_Format,...)
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 *))
static int cmp_leaves(const void *in_a, const void *in_b)
Definition: lzx_layer.c:77
struct ih_elem * parent
Definition: lzx_layer.c:59
static int cmp_pathlengths(const void *in_a, const void *in_b)
Definition: lzx_layer.c:94
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
Definition: lzx_layer.c:72
short pathlength
Definition: lzx_layer.c:58
Definition: inflate.c:139
#define f1(x, y, z)
Definition: sha1.c:30
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
struct ih_elem * left
Definition: lzx_layer.c:60
int freq
Definition: lzx_layer.c:56
#define NULL
Definition: types.h:112
short sym
Definition: lzx_layer.c:66
FILE * stderr
unsigned short code
Definition: lzx_layer.c:69
int freq
Definition: lzx_layer.c:65
#define malloc
Definition: debug_ros.c:4
short sym
Definition: lzx_layer.c:57
int f2(S1 &, S2 &)
#define memset(x, y, z)
Definition: compat.h:39
struct ih_elem * right
Definition: lzx_layer.c:61

Referenced by lzx_compress_block(), and lzx_write_compressed_tree().

◆ check_entropy()

static void check_entropy ( lzx_data lzud,
int  main_index 
)
static

Definition at line 533 of file lzx_layer.c.

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;
589  lz_stop_compressing(lzud->lzi);
590  }
591  lzud->last_ratio = cur_ratio;
592  }
593 }
double rloge2
Definition: lzx_layer.c:53
short subdivide
Definition: lzx_layer.c:428
GLdouble n
Definition: glext.h:7729
#define NUM_CHARS
Definition: chargen.c:15
double main_entropy
Definition: lzx_layer.c:421
#define NUM_SECONDARY_LENGTHS
Definition: lzx_constants.h:30
_Check_return_opt_ _CRTIMP int __cdecl fprintf(_Inout_ FILE *_File, _In_z_ _Printf_format_string_ const char *_Format,...)
static const char mbstate_t *static wchar_t const char mbstate_t *static const wchar_t int *static double
Definition: string.c:80
double last_ratio
Definition: lzx_layer.c:422
uint32_t * block_codes
Definition: lzx_layer.c:413
int left_in_block
Definition: lzx_layer.c:405
uint32_t * block_codesp
Definition: lzx_layer.c:414
void lz_stop_compressing(lz_info *lzi)
Definition: lz_nonslide.c:283
int * main_freq_table
Definition: lzx_layer.c:410
int main_tree_size
Definition: lzx_layer.c:418
struct lz_info * lzi
Definition: lzx_layer.c:401
FILE * stderr
#define log(outFile, fmt,...)
Definition: util.h:15

Referenced by lzx_output_literal().

◆ cmp_leaves()

static int cmp_leaves ( const void in_a,
const void in_b 
)
static

Definition at line 77 of file lzx_layer.c.

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 }
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204

Referenced by build_huffman_tree().

◆ cmp_pathlengths()

static int cmp_pathlengths ( const void in_a,
const void in_b 
)
static

Definition at line 94 of file lzx_layer.c.

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 }
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204

Referenced by build_huffman_tree().

◆ find_match_at()

static int find_match_at ( lz_info lzi,
int  loc,
int  match_len,
int match_locp 
)
static

Definition at line 502 of file lzx_layer.c.

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 }
int cur_loc
Definition: lz_nonslide.h:37
_Check_return_opt_ _CRTIMP int __cdecl fprintf(_Inout_ FILE *_File, _In_z_ _Printf_format_string_ const char *_Format,...)
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
FILE * stderr
UCHAR u_char
Definition: types.h:80

◆ lzx_align_output()

static void lzx_align_output ( lzx_data lzxd)
static

Definition at line 835 of file lzx_layer.c.

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 }
uint32_t len_compressed_output
Definition: lzx_layer.c:426
void * mark_frame_arg
Definition: lzx_layer.c:396
int bits_in_buf
Definition: lzx_layer.c:420
static void lzx_write_bits(lzx_data *lzxd, int nbits, uint32_t bits)
Definition: lzx_layer.c:787
lzx_mark_frame_t mark_frame
Definition: lzx_layer.c:400
uint32_t len_uncompressed_input
Definition: lzx_layer.c:425

Referenced by lzx_write_compressed_literals().

◆ lzx_compress_block()

int lzx_compress_block ( lzx_data lzxd,
int  block_size,
int  subdivide 
)

Definition at line 1062 of file lzx_layer.c.

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;
1080  lzxd->left_in_frame = LZX_FRAME_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)
1091  lzxd->left_in_frame = LZX_FRAME_SIZE;
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++) {
1171  lzxd->prev_main_treelengths[i] = lzxd->main_tree[i].codelength;
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 }
void * in_arg
Definition: lzx_layer.c:394
int lz_compress(lz_info *lzi, int nchars)
Definition: lz_nonslide.c:289
static void build_huffman_tree(int nelem, int max_code_length, int *freq, huff_entry *tree)
Definition: lzx_layer.c:111
int lz_left_to_process(lz_info *lzi)
Definition: lz_nonslide.c:142
#define free
Definition: debug_ros.c:5
short subdivide
Definition: lzx_layer.c:428
huff_entry * main_tree
Definition: lzx_layer.c:415
#define NUM_CHARS
Definition: chargen.c:15
double main_entropy
Definition: lzx_layer.c:421
uint8_t * prev_main_treelengths
Definition: lzx_layer.c:423
#define NUM_SECONDARY_LENGTHS
Definition: lzx_constants.h:30
static DWORD block_size(DWORD block)
Definition: jsutils.c:66
#define LZX_ALIGNED_SIZE
Definition: lzx_constants.h:37
#define LZX_FRAME_SIZE
Definition: lzx_constants.h:34
_Check_return_opt_ _CRTIMP int __cdecl fprintf(_Inout_ FILE *_File, _In_z_ _Printf_format_string_ const char *_Format,...)
int left_in_frame
Definition: lzx_layer.c:404
double last_ratio
Definition: lzx_layer.c:422
huff_entry aligned_tree[LZX_ALIGNED_SIZE]
Definition: lzx_layer.c:417
uint32_t * block_codes
Definition: lzx_layer.c:413
static int lzx_write_compressed_tree(struct lzx_data *lzxd, struct huff_entry *tree, uint8_t *prevlengths, int treesize)
Definition: lzx_layer.c:930
int left_in_block
Definition: lzx_layer.c:405
short need_1bit_header
Definition: lzx_layer.c:427
static void lzx_write_compressed_literals(lzx_data *lzxd, int block_type)
Definition: lzx_layer.c:845
#define LZX_ALIGNED_OFFSET_BLOCK
Definition: lzx_constants.h:40
static void lzx_write_bits(lzx_data *lzxd, int nbits, uint32_t bits)
Definition: lzx_layer.c:787
short codelength
Definition: lzx_layer.c:73
uint32_t * block_codesp
Definition: lzx_layer.c:414
lzx_at_eof_t at_eof
Definition: lzx_layer.c:398
int block_size
Definition: lzx_layer.c:409
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
#define LZX_VERBATIM_BLOCK
Definition: lzx_constants.h:39
int * main_freq_table
Definition: lzx_layer.c:410
int length_freq_table[NUM_SECONDARY_LENGTHS]
Definition: lzx_layer.c:411
#define NULL
Definition: types.h:112
int main_tree_size
Definition: lzx_layer.c:418
UINT32 uint32_t
Definition: types.h:75
#define LZX_MAX_CODE_LENGTH
Definition: lzx_constants.h:33
struct lz_info * lzi
Definition: lzx_layer.c:401
FILE * stderr
#define malloc
Definition: debug_ros.c:4
uint8_t prev_length_treelengths[NUM_SECONDARY_LENGTHS]
Definition: lzx_layer.c:424
huff_entry length_tree[NUM_SECONDARY_LENGTHS]
Definition: lzx_layer.c:416
#define memset(x, y, z)
Definition: compat.h:39
int aligned_freq_table[LZX_ALIGNED_SIZE]
Definition: lzx_layer.c:412

Referenced by chmc_crunch_lzx().

◆ lzx_finish()

int lzx_finish ( struct lzx_data lzxd,
struct lzx_results lzxr 
)

Definition at line 1236 of file lzx_layer.c.

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);
1245  free(lzxd->prev_main_treelengths);
1246  free(lzxd->main_tree);
1247  free(lzxd->main_freq_table);
1248  free(lzxd);
1249  return 0;
1250 }
uint32_t len_compressed_output
Definition: lzx_layer.c:426
#define free
Definition: debug_ros.c:5
huff_entry * main_tree
Definition: lzx_layer.c:415
uint8_t * prev_main_treelengths
Definition: lzx_layer.c:423
long len_compressed_output
Definition: lzx_compress.h:27
int * main_freq_table
Definition: lzx_layer.c:410
long len_uncompressed_input
Definition: lzx_compress.h:28
struct lz_info * lzi
Definition: lzx_layer.c:401
void lz_release(lz_info *lzi)
Definition: lz_nonslide.c:83
uint32_t len_uncompressed_input
Definition: lzx_layer.c:425

Referenced by chmc_crunch_lzx().

◆ lzx_get_chars()

static int lzx_get_chars ( lz_info lzi,
int  n,
u_char buf 
)
static

Definition at line 432 of file lzx_layer.c.

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)
453  lzud->left_in_frame += LZX_FRAME_SIZE;
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 }
void * in_arg
Definition: lzx_layer.c:394
short subdivide
Definition: lzx_layer.c:428
GLdouble n
Definition: glext.h:7729
if(dx==0 &&dy==0)
Definition: linetemp.h:174
GLenum GLuint GLenum GLsizei const GLchar * buf
Definition: glext.h:7751
#define LZX_FRAME_SIZE
Definition: lzx_constants.h:34
int left_in_frame
Definition: lzx_layer.c:404
void * user_data
Definition: lz_nonslide.h:50
int left_in_block
Definition: lzx_layer.c:405
lzx_get_bytes_t get_bytes
Definition: lzx_layer.c:397
#define memset(x, y, z)
Definition: compat.h:39

Referenced by lzx_init().

◆ lzx_init()

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 at line 1189 of file lzx_layer.c.

1194 {
1195  int wsize;
1196  struct lzx_data *lzxd;
1197 
1198  if ((wsize_code < 15) || (wsize_code > 21)) {
1199  return -1;
1200  }
1201  lzx_init_static();
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 }
void * in_arg
Definition: lzx_layer.c:394
void lzx_reset(lzx_data *lzxd)
Definition: lzx_layer.c:1053
#define MIN_MATCH
Definition: zutil.h:64
uint32_t len_compressed_output
Definition: lzx_layer.c:426
void * mark_frame_arg
Definition: lzx_layer.c:396
#define MAX_MATCH
Definition: zutil.h:65
int num_position_slots
Definition: lzx_layer.c:407
huff_entry * main_tree
Definition: lzx_layer.c:415
#define NUM_CHARS
Definition: chargen.c:15
static int lzx_output_match(lz_info *lzi, int match_pos, int match_len)
Definition: lzx_layer.c:596
lzx_put_bytes_t put_bytes
Definition: lzx_layer.c:399
uint8_t * prev_main_treelengths
Definition: lzx_layer.c:423
#define LZX_FRAME_SIZE
Definition: lzx_constants.h:34
static void lzx_output_literal(lz_info *lzi, u_char ch)
Definition: lzx_layer.c:771
short num_position_slots[]
Definition: lzx_layer.c:50
int bits_in_buf
Definition: lzx_layer.c:420
uint32_t * block_codes
Definition: lzx_layer.c:413
Definition: lzx_layer.c:72
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
BYTE uint8_t
Definition: msvideo1.c:66
void * out_arg
Definition: lzx_layer.c:395
lzx_at_eof_t at_eof
Definition: lzx_layer.c:398
lzx_mark_frame_t mark_frame
Definition: lzx_layer.c:400
static void lzx_init_static(void)
Definition: lzx_layer.c:374
int * main_freq_table
Definition: lzx_layer.c:410
#define NULL
Definition: types.h:112
int main_tree_size
Definition: lzx_layer.c:418
struct lz_info * lzi
Definition: lzx_layer.c:401
lzx_get_bytes_t get_bytes
Definition: lzx_layer.c:397
#define malloc
Definition: debug_ros.c:4
uint32_t len_uncompressed_input
Definition: lzx_layer.c:425
static int lzx_get_chars(lz_info *lzi, int n, u_char *buf)
Definition: lzx_layer.c:432

Referenced by chmc_crunch_lzx().

◆ lzx_init_static()

static void lzx_init_static ( void  )
static

Definition at line 374 of file lzx_layer.c.

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 }
double rloge2
Definition: lzx_layer.c:53
u_char extra_bits[52]
Definition: lzx_layer.c:52
unsigned long position_base[51]
Definition: lzx_layer.c:51
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
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
#define log(outFile, fmt,...)
Definition: util.h:15

Referenced by lzx_init().

◆ lzx_output_literal()

static void lzx_output_literal ( lz_info lzi,
u_char  ch 
)
static

Definition at line 771 of file lzx_layer.c.

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 }
short subdivide
Definition: lzx_layer.c:428
static void check_entropy(lzx_data *lzud, int main_index)
Definition: lzx_layer.c:533
_Check_return_opt_ _CRTIMP int __cdecl fprintf(_Inout_ FILE *_File, _In_z_ _Printf_format_string_ const char *_Format,...)
int left_in_block
Definition: lzx_layer.c:405
uint32_t * block_codesp
Definition: lzx_layer.c:414
int * main_freq_table
Definition: lzx_layer.c:410
struct lz_info * lzi
Definition: lzx_layer.c:401
FILE * stderr

Referenced by lzx_init().

◆ lzx_output_match()

static int lzx_output_match ( lz_info lzi,
int  match_pos,
int  match_len 
)
static

Definition at line 596 of file lzx_layer.c.

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 }
#define NUM_PRIMARY_LENGTHS
Definition: lzx_constants.h:29
#define MIN_MATCH
Definition: zutil.h:64
int R0
Definition: lzx_layer.c:406
static int find_match_at(lz_info *lzi, int loc, int match_len, int *match_locp)
Definition: lzx_layer.c:502
short subdivide
Definition: lzx_layer.c:428
int num_position_slots
Definition: lzx_layer.c:407
#define assert(x)
Definition: debug.h:53
#define NUM_CHARS
Definition: chargen.c:15
int R1
Definition: lzx_layer.c:406
u_char extra_bits[52]
Definition: lzx_layer.c:52
unsigned long position_base[51]
Definition: lzx_layer.c:51
unsigned short int uint16_t
Definition: acefiex.h:54
static void check_entropy(lzx_data *lzud, int main_index)
Definition: lzx_layer.c:533
_Check_return_opt_ _CRTIMP int __cdecl fprintf(_Inout_ FILE *_File, _In_z_ _Printf_format_string_ const char *_Format,...)
int left_in_block
Definition: lzx_layer.c:405
#define for
Definition: utility.h:88
GLint left
Definition: glext.h:7726
GLdouble GLdouble right
Definition: glext.h:10859
uint32_t * block_codesp
Definition: lzx_layer.c:414
BYTE uint8_t
Definition: msvideo1.c:66
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
int * main_freq_table
Definition: lzx_layer.c:410
int length_freq_table[NUM_SECONDARY_LENGTHS]
Definition: lzx_layer.c:411
int R2
Definition: lzx_layer.c:406
UINT32 uint32_t
Definition: types.h:75
struct lz_info * lzi
Definition: lzx_layer.c:401
FILE * stderr
#define UL
Definition: tui.h:148
int aligned_freq_table[LZX_ALIGNED_SIZE]
Definition: lzx_layer.c:412

Referenced by lzx_init().

◆ lzx_reset()

void lzx_reset ( lzx_data lzxd)

Definition at line 1053 of file lzx_layer.c.

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 }
int R0
Definition: lzx_layer.c:406
int R1
Definition: lzx_layer.c:406
uint8_t * prev_main_treelengths
Definition: lzx_layer.c:423
#define NUM_SECONDARY_LENGTHS
Definition: lzx_constants.h:30
void lz_reset(lz_info *lzi)
Definition: lz_nonslide.c:90
short need_1bit_header
Definition: lzx_layer.c:427
BYTE uint8_t
Definition: msvideo1.c:66
int main_tree_size
Definition: lzx_layer.c:418
int R2
Definition: lzx_layer.c:406
struct lz_info * lzi
Definition: lzx_layer.c:401
uint8_t prev_length_treelengths[NUM_SECONDARY_LENGTHS]
Definition: lzx_layer.c:424
#define memset(x, y, z)
Definition: compat.h:39

Referenced by chmc_crunch_lzx(), and lzx_init().

◆ lzx_write_bits()

static void lzx_write_bits ( lzx_data lzxd,
int  nbits,
uint32_t  bits 
)
static

Definition at line 787 of file lzx_layer.c.

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 }
uint32_t len_compressed_output
Definition: lzx_layer.c:426
#define U(x)
Definition: wordpad.c:45
unsigned short int uint16_t
Definition: acefiex.h:54
lzx_put_bytes_t put_bytes
Definition: lzx_layer.c:399
GLenum GLint GLenum GLsizei GLsizei GLsizei GLint GLsizei const GLvoid * bits
Definition: glext.h:10929
_Check_return_opt_ _CRTIMP int __cdecl fprintf(_Inout_ FILE *_File, _In_z_ _Printf_format_string_ const char *_Format,...)
int bits_in_buf
Definition: lzx_layer.c:420
uint16_t bit_buf
Definition: lzx_layer.c:419
void * out_arg
Definition: lzx_layer.c:395
FILE * stderr

Referenced by lzx_align_output(), lzx_compress_block(), lzx_write_compressed_literals(), and lzx_write_compressed_tree().

◆ lzx_write_compressed_literals()

static void lzx_write_compressed_literals ( lzx_data lzxd,
int  block_type 
)
static

Definition at line 845 of file lzx_layer.c.

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 }
#define NUM_PRIMARY_LENGTHS
Definition: lzx_constants.h:29
unsigned short code
Definition: lzx_layer.c:74
huff_entry * main_tree
Definition: lzx_layer.c:415
#define assert(x)
Definition: debug.h:53
#define NUM_CHARS
Definition: chargen.c:15
u_char extra_bits[52]
Definition: lzx_layer.c:52
unsigned short int uint16_t
Definition: acefiex.h:54
#define LZX_FRAME_SIZE
Definition: lzx_constants.h:34
_Check_return_opt_ _CRTIMP int __cdecl fprintf(_Inout_ FILE *_File, _In_z_ _Printf_format_string_ const char *_Format,...)
huff_entry aligned_tree[LZX_ALIGNED_SIZE]
Definition: lzx_layer.c:417
uint32_t * block_codes
Definition: lzx_layer.c:413
Definition: lzx_layer.c:72
#define LZX_ALIGNED_OFFSET_BLOCK
Definition: lzx_constants.h:40
static void lzx_write_bits(lzx_data *lzxd, int nbits, uint32_t bits)
Definition: lzx_layer.c:787
short codelength
Definition: lzx_layer.c:73
uint32_t * block_codesp
Definition: lzx_layer.c:414
const char cursor[]
Definition: icontest.c:13
static void lzx_align_output(lzx_data *lzxd)
Definition: lzx_layer.c:835
UINT32 uint32_t
Definition: types.h:75
FILE * stderr
uint32_t len_uncompressed_input
Definition: lzx_layer.c:425
huff_entry length_tree[NUM_SECONDARY_LENGTHS]
Definition: lzx_layer.c:416

Referenced by lzx_compress_block().

◆ lzx_write_compressed_tree()

static int lzx_write_compressed_tree ( struct lzx_data lzxd,
struct huff_entry tree,
uint8_t prevlengths,
int  treesize 
)
static

Definition at line 930 of file lzx_layer.c.

933 {
934  u_char *codes;
935  u_char *runs;
936  int freqs[LZX_PRETREE_SIZE];
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 */
1017  build_huffman_tree(LZX_PRETREE_SIZE, 16, freqs, 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 }
static void build_huffman_tree(int nelem, int max_code_length, int *freq, huff_entry *tree)
Definition: lzx_layer.c:111
#define free
Definition: debug_ros.c:5
#define LZX_PRETREE_SIZE
Definition: lzx_constants.h:35
_Check_return_opt_ _CRTIMP int __cdecl fprintf(_Inout_ FILE *_File, _In_z_ _Printf_format_string_ const char *_Format,...)
static unsigned char * codep
Definition: i386-dis.c:1287
Definition: lzx_layer.c:72
static void lzx_write_bits(lzx_data *lzxd, int nbits, uint32_t bits)
Definition: lzx_layer.c:787
static const DWORD freqs[10]
Definition: mpegsplit.c:111
Definition: inflate.c:139
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
FILE * stderr
#define malloc
Definition: debug_ros.c:4
UCHAR u_char
Definition: types.h:80
#define memset(x, y, z)
Definition: compat.h:39

Referenced by lzx_compress_block().

Variable Documentation

◆ extra_bits

u_char extra_bits[52]

◆ num_position_slots

short num_position_slots[] = {30, 32, 34, 36, 38, 42, 50}

Definition at line 50 of file lzx_layer.c.

Referenced by lzx_init().

◆ position_base

unsigned long position_base[51]

Definition at line 51 of file lzx_layer.c.

Referenced by lzx_init_static().

◆ rloge2

double rloge2

Definition at line 53 of file lzx_layer.c.

Referenced by check_entropy(), and lzx_init_static().