fstenc.c

windows gzip source code

				t_match_pos		next_match_pos;

				// sets search
				INSERT_STRING(search,bufpos);

				// no, so check for a better match at X+1
				if (search != 0)
				{
					next_match_len = FastEncoderFindMatch(
						window,
                        prev,
						bufpos, 
						search,
						&next_match_pos,
						match_len < good_length ? search_depth : (search_depth >> 2),
                        nice_length
					);
				
					// truncate match if we're too close to the end of the buffer
					// note: next_match_len could now be < MIN_MATCH
					if (bufpos + next_match_len > context->bufpos_end)
						next_match_len = context->bufpos_end - bufpos;
				}
				else
				{
					next_match_len = 0;
				}

				// right now X and X+1 are both inserted into the search tree
				if (next_match_len > match_len)
				{
					// since next_match_len > match_len, it can't be < MIN_MATCH here

					// match at X+1 is better, so output unmatched char at X
					OUTPUT_CHAR(window[bufpos-1]);

					// now output match at location X+1
					OUTPUT_MATCH(next_match_len, next_match_pos);

					// insert remainder of second match into search tree
					// 
					// example: (*=inserted already)
					//
					// X      X+1               X+2      X+3     X+4
					// *      *
					//        nextmatchlen=3
					//        bufpos
					//
					// If next_match_len == 3, we want to perform 2
					// insertions (at X+2 and X+3).  However, first we must 
					// inc bufpos.
					//
					bufpos++; // now points to X+2
					match_len = next_match_len;
					goto insert;
				}
				else
				{
					// match at X is better, so take it
					OUTPUT_MATCH(match_len, match_pos);

					//
					// Insert remainder of first match into search tree, minus the first
					// two locations, which were inserted by the FindMatch() calls.
					// 
					// For example, if match_len == 3, then we've inserted at X and X+1
					// already (and bufpos is now pointing at X+1), and now we need to insert 
					// only at X+2.
					//
					match_len--;
					bufpos++; // now bufpos points to X+2
					goto insert;
				}
			}
			else /* match_length >= good_match */
			{
				// in assertion: bufpos points to X+1, location X inserted already
					
				// first match is so good that we're not even going to check at X+1
				OUTPUT_MATCH(match_len, match_pos);

				// insert remainder of match at X into search tree
insert:
				if (context->bufpos_end - bufpos <= match_len)
				{
					bufpos += (match_len-1);
				}
				else
				{
   					while (--match_len > 0)
    				{
	    				t_match_pos ignore;

		    			INSERT_STRING(ignore,bufpos);
			    		bufpos++;
				    }
				}
			}
		}
	} /* end ... while (bufpos < bufpos_end) */

    // store local variables back in context
	context->bufpos = bufpos;
    context->bitbuf = bitbuf;
    context->bitcount = bitcount;
    context->output_curpos = output_curpos;

	VERIFY_HASHES(bufpos); // debugger: verify that hash table is correct

    if (bufpos == context->bufpos_end)
        context->state = STATE_NORMAL;
    else
        context->state = STATE_OUTPUTTING_BLOCK;

    // slide the window if bufpos has reached 2*window size
    if (context->bufpos == 2*FAST_ENCODER_WINDOW_SIZE)
        FastEncoderMoveWindows(context);
}


static void FastEncoderMoveWindows(t_encoder_context *context)
{
	t_search_node *lookup = context->fast_encoder->lookup;
	t_search_node *prev = context->fast_encoder->prev;
	BYTE *window = context->fast_encoder->window;
	int i;

    _ASSERT(context->bufpos == 2*FAST_ENCODER_WINDOW_SIZE);

    // verify that the hash table is correct
	VERIFY_HASHES(2*FAST_ENCODER_WINDOW_SIZE);

	memcpy(&window[0], &window[context->bufpos - FAST_ENCODER_WINDOW_SIZE], FAST_ENCODER_WINDOW_SIZE);

    // move all the hash pointers back
    // BUGBUG We are incurring a performance penalty since lookup[] is a USHORT array.  Would be
    // nice to subtract from two locations at a time.
	for (i = 0; i < FAST_ENCODER_HASH_TABLE_SIZE; i++)
	{
		long val = ((long) lookup[i]) - FAST_ENCODER_WINDOW_SIZE;

		if (val <= 0) // too far away now? then set to zero
			lookup[i] = (t_search_node) 0;
		else
			lookup[i] = (t_search_node) val;
	}

    // prev[]'s are absolute pointers, not relative pointers, so we have to move them back too
    // making prev[]'s into relative pointers poses problems of its own
	for (i = 0; i < FAST_ENCODER_WINDOW_SIZE; i++)
	{
		long val = ((long) prev[i]) - FAST_ENCODER_WINDOW_SIZE;

		if (val <= 0)
			prev[i] = (t_search_node) 0;
		else
			prev[i] = (t_search_node) val;
	}

#ifdef FULL_DEBUG
    // For debugging, wipe the window clean, so that if there is a bug in our hashing,
    // the hash pointers will now point to locations which are not valid for the hash value
    // (and will be caught by our ASSERTs).
	memset(&window[FAST_ENCODER_WINDOW_SIZE], 0, FAST_ENCODER_WINDOW_SIZE);
#endif

	VERIFY_HASHES(2*FAST_ENCODER_WINDOW_SIZE); // debug: verify hash table is correct

	context->bufpos = FAST_ENCODER_WINDOW_SIZE;
	context->bufpos_end = context->bufpos;
}


//
// Find match
//
// Returns match length found.  A match length < MIN_MATCH means no match was found.
//
static int FastEncoderFindMatch(
    const BYTE *    window, // window array
    const USHORT *  prev,   // prev ptr array
    long            bufpos, // current buffer position
    long            search, // where to start searching
    t_match_pos *   match_pos, // return match position here
    int             cutoff, // # links to traverse
    int             nice_length // stop immediately if we find a match >= nice_length
)
{
    // make local copies of context variables
	long			earliest;
	int				best_match = 0; // best match length found so far
	t_match_pos		l_match_pos; // absolute match position of best match found
    BYTE            want_char;

	_ASSERT(bufpos >= 0 && bufpos < 2*FAST_ENCODER_WINDOW_SIZE);
	_ASSERT(search < bufpos);
	_ASSERT(FAST_ENCODER_RECALCULATE_HASH(search) == FAST_ENCODER_RECALCULATE_HASH(bufpos));

    // the earliest we can look
	earliest = bufpos - FAST_ENCODER_WINDOW_SIZE;
    _ASSERT(earliest >= 0);

    // store window[bufpos + best_match]
    want_char = window[bufpos];

	while (search > earliest)
	{
        // make sure all our hash links are valid
		_ASSERT(FAST_ENCODER_RECALCULATE_HASH(search) == FAST_ENCODER_RECALCULATE_HASH(bufpos));

        // Start by checking the character that would allow us to increase the match
        // length by one.  This improves performance quite a bit.
		if (window[search + best_match] == want_char)
		{
			int j;

            // Now make sure that all the other characters are correct
			for (j = 0; j < MAX_MATCH; j++)
			{
				if (window[bufpos+j] != window[search+j])
					break;
			}
	
			if (j > best_match)
			{
				best_match	= j;
				l_match_pos	= search; // absolute position

				if (j > nice_length)
					break;

                want_char = window[bufpos+j];
			}
		}

		if (--cutoff == 0)
			break;

        // make sure we're always going backwards
        _ASSERT(prev[search & FAST_ENCODER_WINDOW_MASK] < search);

		search = (long) prev[search & FAST_ENCODER_WINDOW_MASK];
	}

    // doesn't necessarily mean we found a match; best_match could be > 0 and < MIN_MATCH
	*match_pos = bufpos - l_match_pos - 1; // convert absolute to relative position

    // don't allow match length 3's which are too far away to be worthwhile
	if (best_match == 3 && *match_pos >= FAST_ENCODER_MATCH3_DIST_THRESHOLD)
		return 0;

	_ASSERT(best_match < MIN_MATCH || *match_pos < FAST_ENCODER_WINDOW_SIZE);

	return best_match;
}


void FastEncoderReset(t_encoder_context *context)
{
	_ASSERT(context->fast_encoder != NULL);

    // zero hash table
	memset(context->fast_encoder->lookup, 0, sizeof(context->fast_encoder->lookup));

    context->window_size = FAST_ENCODER_WINDOW_SIZE;
	context->bufpos = FAST_ENCODER_WINDOW_SIZE;
    context->bufpos_end = context->bufpos;
    context->fast_encoder->fOutputBlockHeader = FALSE;
}


BOOL FastEncoderInit(t_encoder_context *context)
{
	context->fast_encoder = (t_fast_encoder *) LocalAlloc(LMEM_FIXED, sizeof(t_fast_encoder));

    if (context->fast_encoder == NULL)
        return FALSE;

	FastEncoderReset(context);
	return TRUE;
}


//
// Pregenerate the structure of the dynamic tree header which is output for
// the fast encoder.  Also record the final states of bitcount and bitbuf
// after outputting.
//
void FastEncoderGenerateDynamicTreeEncoding(void)
{
    t_encoder_context context;

    // Create a fake context with output pointers into our global data
    memset(&context, 0, sizeof(context));
    context.output_curpos = g_FastEncoderTreeStructureData;
    context.output_endpos = g_FastEncoderTreeStructureData + sizeof(g_FastEncoderTreeStructureData);
    context.output_near_end_threshold = context.output_endpos - 16;
    InitBitBuffer(&context);

    outputBits(&context, 1, 1); // "final" block flag
    outputBits(&context, 2, BLOCKTYPE_DYNAMIC);
   
    outputTreeStructure(
        &context,
	    g_FastEncoderLiteralTreeLength, 
	    g_FastEncoderDistanceTreeLength
    );

    g_FastEncoderTreeLength = (int) (context.output_curpos - (BYTE *) g_FastEncoderTreeStructureData);
    g_FastEncoderPostTreeBitbuf = context.bitbuf;
    g_FastEncoderPostTreeBitcount = context.bitcount;
}