lz_nonslide.c File Reference

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <strings.h>
#include "lz_nonslide.h"

Include dependency graph for lz_nonslide.c:

Go to the source code of this file.

Macros
#define	MAX_MATCH   253
#define	MIN_MATCH   2

Functions
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)
void	lz_release (lz_info *lzi)
void	lz_reset (lz_info *lzi)
int	lz_left_to_process (lz_info *lzi)
static void	fill_blockbuf (lz_info *lzi, int maxchars)
static void	lz_analyze_block (lz_info *lzi)
void	lz_stop_compressing (lz_info *lzi)
int	lz_compress (lz_info *lzi, int nchars)

Macro Definition Documentation

MAX_MATCH

#define MAX_MATCH   253

Definition at line 39 of file lz_nonslide.c.

MIN_MATCH

#define MIN_MATCH   2

Definition at line 40 of file lz_nonslide.c.

Function Documentation

fill_blockbuf()

static void fill_blockbuf ( lz_info *  lzi, int  maxchars  )

static

Definition at line 148 of file lz_nonslide.c.

{
  int toread;
  u_char *readhere;
  int nread;
 
  if (lzi->eofcount) return;
  maxchars -= lz_left_to_process(lzi);
  toread = lzi->block_buf_size - lzi->chars_in_buf;
  if (toread > maxchars) toread = maxchars;
  readhere = lzi->block_buf + lzi->chars_in_buf;
  nread = lzi->get_chars(lzi, toread, readhere);
  lzi->chars_in_buf += nread;
  if (nread != toread)
    lzi->eofcount++;
}

Referenced by lz_compress().

lz_analyze_block()

static void lz_analyze_block ( lz_info *  lzi )

static

Definition at line 165 of file lz_nonslide.c.

{
  int *lentab, *lenp;
  u_char **prevtab, **prevp;
  u_char *bbp, *bbe;
  u_char *chartab[256];
  u_char *cursor;
  int prevlen;
  int ch;
  int maxlen;
  long wasinc;
  int max_dist = lzi->max_dist;
#ifdef DEBUG_ANALYZE_BLOCK
  static short n = 0;
#endif
#ifdef DEBUG_PERF
  struct rusage innerloop;
  struct timeval innertime, tmptime;
  struct rusage outerloop;
  struct timeval outertime;
  struct rusage initialloop;
  struct timeval initialtime;
  struct rusage totalloop;
  struct timeval totaltime;
#endif
 
#ifdef DEBUG_ANALYZE_BLOCK
  fprintf(stderr, "Analyzing block %d, cur_loc = %06x\n", n, lzi->cur_loc);
#endif
  memset(chartab, 0, sizeof(chartab));
  prevtab = prevp = lzi->prevtab;
  lentab = lenp = lzi->lentab;
  memset(prevtab, 0, sizeof(*prevtab) * lzi->chars_in_buf);
  memset(lentab, 0, sizeof(*prevtab) * lzi->chars_in_buf);
#ifdef DEBUG_PERF
  memset(&innertime, 0, sizeof(innertime));
  memset(&outertime, 0, sizeof(outertime));
  getrusage(RUSAGE_SELF, &initialloop);
  totalloop = initialloop;
#endif
  bbp = lzi->block_buf;
  bbe = bbp + lzi->chars_in_buf;
  while (bbp < bbe) {
    if (chartab[ch = *bbp]) {
      *prevp = chartab[ch];
      *lenp = 1;
    }
    chartab[ch] = bbp;
    bbp++;
    prevp++;
    lenp++;
  }
#ifdef DEBUG_PERF
  initialtime = initialloop.ru_utime;
  getrusage(RUSAGE_SELF, &initialloop);
  timersub(&initialloop.ru_utime, &initialtime, &initialtime);
#endif
  wasinc = 1;
  for (maxlen = 1; wasinc && (maxlen < lzi->max_match); maxlen++) {
#ifdef DEBUG_PERF
    getrusage(RUSAGE_SELF, &outerloop);
#endif
    bbp = bbe - maxlen - 1;
    lenp = lentab + lzi->chars_in_buf - maxlen - 1;
    prevp = prevtab + lzi->chars_in_buf - maxlen - 1;
    wasinc = 0;
    while (bbp > lzi->block_buf) {
      if (*lenp == maxlen) {
#ifdef DEBUG_PERF
    getrusage(RUSAGE_SELF, &innerloop);
#endif
    ch = bbp[maxlen];
    cursor = *prevp;
    while(cursor && ((bbp - cursor) <= max_dist)) {
      prevlen = *(cursor - lzi->block_buf + lentab);
      if (cursor[maxlen] == ch) {
        *prevp = cursor;
        (*lenp)++;
        wasinc++;
        break;
      }
      if (prevlen != maxlen) break;
      cursor = *(cursor - lzi->block_buf + prevtab);
    }
#ifdef DEBUG_PERF
    tmptime = innerloop.ru_utime;
    getrusage(RUSAGE_SELF, &innerloop);
    timersub(&innerloop.ru_utime, &tmptime, &tmptime);
    timeradd(&tmptime, &innertime, &innertime);
#endif
      }
      bbp--;
      prevp--;
      lenp--;
    }
#ifdef DEBUG_PERF
    tmptime = outerloop.ru_utime;
    getrusage(RUSAGE_SELF, &outerloop);
    timersub(&outerloop.ru_utime, &tmptime, &tmptime);
    timeradd(&tmptime, &outertime, &outertime);
#endif
    //    fprintf(stderr, "maxlen = %d, wasinc = %ld\n", maxlen, wasinc);
  }
#ifdef DEBUG_PERF
  totaltime = totalloop.ru_utime;
  getrusage(RUSAGE_SELF, &totalloop);
  timersub(&totalloop.ru_utime, &totaltime, &totaltime);
  fprintf(stderr, "Time spend in initial loop = %f\n", initialtime.tv_sec + initialtime.tv_usec/(double)1E6);
  fprintf(stderr, "Time spend in outer loop = %f\n", outertime.tv_sec + outertime.tv_usec/(double)1E6);
  fprintf(stderr, "Time spend in inner loop = %f\n", innertime.tv_sec + innertime.tv_usec/(double)1E6);
  fprintf(stderr, "Time spend in all loops = %f\n", totaltime.tv_sec + totaltime.tv_usec/(double)1E6);
#endif
  lzi->analysis_valid = 1;
#ifdef DEBUG_ANALYZE_BLOCK
  fprintf(stderr, "Done analyzing block %d, cur_loc = %06x\n", n++, lzi->cur_loc);
#endif
}

Referenced by lz_compress().

lz_compress()

int lz_compress	(	lz_info *	lzi,
		int	nchars
	)

Definition at line 289 of file lz_nonslide.c.

{
 
  u_char *bbp, *bbe;
  int *lentab, *lenp;
  u_char **prevtab, **prevp;
  int len;
  int holdback;
  short trimmed;
 
  lzi->stop = 0;
  while ((lz_left_to_process(lzi) || !lzi->eofcount) && !lzi->stop && nchars > 0) {
#if 1
    if (!lzi->analysis_valid ||
    (!lzi->eofcount &&
     ((lzi->chars_in_buf- lzi->block_loc) < nchars))) {
      int residual = lzi->chars_in_buf - lzi->block_loc;
      int bytes_to_move = lzi->max_dist + residual;
      if (bytes_to_move > lzi->chars_in_buf)
    bytes_to_move = lzi->chars_in_buf;
#ifdef DEBUG_ANALYZE_BLOCK
      fprintf(stderr, "Moving %06x, chars_in_buf %06x, residual = %06x, nchars= %06x block_loc = %06x\n", bytes_to_move, lzi->chars_in_buf, residual, nchars, lzi->block_loc);
#endif
      memmove(lzi->block_buf, lzi->block_buf + lzi->chars_in_buf - bytes_to_move,
          bytes_to_move);
 
      lzi->block_loc = bytes_to_move - residual;
      lzi->chars_in_buf = bytes_to_move;
#ifdef DEBUG_ANALYZE_BLOCK
      fprintf(stderr, "New chars_in_buf %06x,  new block_loc = %06x, eof = %1d\n", lzi->chars_in_buf, lzi->block_loc, lzi->eofcount);
#endif
      fill_blockbuf(lzi, nchars);
#ifdef DEBUG_ANALYZE_BLOCK
      fprintf(stderr, "Really new chars_in_buf %06x,  new block_loc = %06x, eof = %1d\n", lzi->chars_in_buf, lzi->block_loc, lzi->eofcount);
#endif
      lz_analyze_block(lzi);
    }
#else
    if (!lzi->analysis_valid ||
    (lzi->block_loc - lzi->chars_in_buf) == 0) {
      lzi->block_loc = 0;
      lzi->chars_in_buf = 0;
      fill_blockbuf(lzi, nchars);
      lz_analyze_block(lzi);
    }
#endif
    prevtab = prevp = lzi->prevtab + lzi->block_loc;
    lentab = lenp = lzi->lentab + lzi->block_loc;
    bbp = lzi->block_buf + lzi->block_loc;
    holdback = lzi->max_match;
    if (lzi->eofcount) holdback = 0;
    if (lzi->chars_in_buf < (nchars + lzi->block_loc))
      bbe = lzi->block_buf + lzi->chars_in_buf - holdback;
    else
      bbe = bbp + nchars;
    while ((bbp < bbe) && (!lzi->stop)) {
      trimmed = 0;
      len = *lenp;
      if (lzi->frame_size && (len > (lzi->frame_size - lzi->cur_loc % lzi->frame_size))) {
#ifdef DEBUG_TRIMMING
    fprintf(stderr, "Trim for framing: %06x %d %d\n", lzi->cur_loc,len, (lzi->frame_size - lzi->cur_loc % lzi->frame_size));
#endif
    trimmed = 1;
    len = (lzi->frame_size - lzi->cur_loc % lzi->frame_size);
      }
      if (len > nchars) {
#ifdef DEBUG_TRIMMING
    fprintf(stderr, "Trim for blocking: %06x %d %d\n", lzi->cur_loc,len, nchars);
#endif
    trimmed = 1;
    len = nchars;
      }
      if (len >= lzi->min_match) {
#ifdef LAZY
    if ((bbp < bbe -1) && !trimmed &&
        ((lenp[1] > (len + 1)) /* || ((lenp[1] == len) && (prevp[1] > prevp[0])) */)) {
      len = 1;
      /* this is the lazy eval case */
    }
    else
#endif
      if (lzi->output_match(lzi, (*prevp - lzi->block_buf) - lzi->block_loc,
                len) < 0) {
        //      fprintf(stderr, "Match rejected: %06x %d\n", lzi->cur_loc, len);
        len = 1; /* match rejected */
      }
      }
      else
    len = 1;
 
      if (len < lzi->min_match) {
    assert(len == 1);
    lzi->output_literal(lzi, *bbp);
      }
      //      fprintf(stderr, "len = %3d, *lenp = %3d, cur_loc = %06x, block_loc = %06x\n", len, *lenp, lzi->cur_loc, lzi->block_loc);
      bbp += len;
      prevp += len;
      lenp += len;
      lzi->cur_loc += len;
      lzi->block_loc += len;
      assert(nchars >= len);
      nchars -= len;
 
    }
  }
  return 0;
}

Referenced by lzx_compress_block().

lz_init()

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 at line 42 of file lz_nonslide.c.

{
  /* the reason for the separate max_dist value is LZX can't reach the
     first three characters in its nominal window.  But using a smaller
     window results in inefficiency when dealing with reset intervals
     which are the length of the nominal window */
 
  lzi->wsize = wsize;
  if (max_match > wsize)
    lzi->max_match = wsize;
  else
    lzi->max_match = max_match;
 
  lzi->min_match = min_match;
  if (lzi->min_match < 3) lzi->min_match = 3;
 
  lzi->max_dist = max_dist;
  lzi->block_buf_size = wsize + lzi->max_dist;
  lzi->block_buf = malloc(lzi->block_buf_size);
  lzi->block_bufe = lzi->block_buf + lzi->block_buf_size;
  assert(lzi->block_buf != NULL);
 
  lzi->cur_loc = 0;
  lzi->block_loc = 0;
  lzi->chars_in_buf = 0;
  lzi->eofcount = 0;
  lzi->get_chars = get_chars;
  lzi->output_match = output_match;
  lzi->output_literal = output_literal;
  lzi->user_data = user_data;
  lzi->frame_size = frame_size;
  lzi->lentab = calloc(sizeof(int), lzi->block_buf_size);
  lzi->prevtab = calloc(sizeof(u_char *), lzi->block_buf_size);
  lzi->analysis_valid = 0;
}

Referenced by lzx_init().

lz_left_to_process()

int lz_left_to_process

(

lz_info *

lzi

)

Definition at line 142 of file lz_nonslide.c.

{
  return lzi->chars_in_buf - lzi->block_loc;
}

Referenced by fill_blockbuf(), lz_compress(), and lzx_compress_block().

lz_release()

void lz_release

(

lz_info *

lzi

)

Definition at line 83 of file lz_nonslide.c.

{
  free(lzi->block_buf);
  free(lzi->lentab);
  free(lzi->prevtab);
}

Referenced by lzx_finish().

lz_reset()

void lz_reset

(

lz_info *

lzi

)

Definition at line 90 of file lz_nonslide.c.

{
  int residual = lzi->chars_in_buf - lzi->block_loc;
  memmove(lzi->block_buf, lzi->block_buf + lzi->block_loc, residual);
  lzi->chars_in_buf = residual;
  lzi->block_loc = 0;
  lzi->analysis_valid = 0;
}

Referenced by lzx_reset().

lz_stop_compressing()

void lz_stop_compressing

(

lz_info *

lzi

)

Definition at line 283 of file lz_nonslide.c.

{
  lzi->stop = 1;
  /*  fprintf(stderr, "Stopping...\n");*/
}

Referenced by check_entropy().