tests/tests_deflate_longest_match.c

#include "unity/unity.h"
#include "zlib.h"
#include "deflate.h"
#include <string.h>
#include <stdlib.h>

/* Use the provided global wrapper for the local function */
extern uInt test_longest_match(deflate_state *s, IPos cur_match);

static z_stream g_strm;
static deflate_state *S;

void setUp(void) {
    memset(&g_strm, 0, sizeof(g_strm));
    int ret = deflateInit(&g_strm, Z_DEFAULT_COMPRESSION);
    TEST_ASSERT_EQUAL_INT(Z_OK, ret);
    S = (deflate_state *)g_strm.state;
    TEST_ASSERT_NOT_NULL(S);
}

void tearDown(void) {
    deflateEnd(&g_strm);
}

/* Helper to prepare a safe strstart and cur_match in the window */
static void prepare_positions(IPos *out_strstart, IPos *out_cur, uInt back_distance) {
    /* Choose a safe strstart with plenty of room before and after */
    IPos strstart = (IPos)(S->w_size); /* centered in the window: safe for MAX_MATCH scans */
    IPos cur = strstart - (IPos)back_distance;
    TEST_ASSERT_TRUE_MESSAGE(cur >= 1, "cur_match must be >= 1");
    *out_strstart = strstart;
    *out_cur = cur;
}

/* Test 1: Basic medium-length match followed by mismatch */
void test_longest_match_basic_match(void) {
    IPos strstart, cur;
    prepare_positions(&strstart, &cur, 100);

    const uInt L = 10;
    /* Ensure at least first three bytes match (important for all code paths) */
    for (uInt i = 0; i < L; i++) {
        Byte b = (Byte)('A' + (i % 3));
        S->window[strstart + i] = b;
        S->window[cur + i] = b;
    }
    /* Mismatch immediately after L to stop the scan */
    S->window[strstart + L] = 'X';
    S->window[cur + L] = 'Y';

    /* Make sure there is enough initialized data past comparisons */
    for (uInt i = L + 1; i <= MAX_MATCH + 5; i++) {
        S->window[strstart + i] = 0;
        S->window[cur + i] = 0;
    }

    S->strstart = strstart;
    S->lookahead = L + 10; /* more than L */

    /* Terminate the hash chain after the first candidate */
    S->prev[cur & S->w_mask] = NIL;

    uInt got = test_longest_match(S, cur);
    TEST_ASSERT_EQUAL_UINT(L, got);
    TEST_ASSERT_EQUAL_UINT(cur, S->match_start);
}

/* Test 2: Match exists but longer than lookahead; result should be capped by lookahead */
void test_longest_match_capped_by_lookahead(void) {
    IPos strstart, cur;
    prepare_positions(&strstart, &cur, 200);

    const uInt actual_match_len = 50;
    const uInt lookahead = 20; /* cap */

    /* Make a long identical sequence (ensure first 3 bytes equal) */
    for (uInt i = 0; i < actual_match_len + 5; i++) {
        Byte b = (Byte)('M' + (i % 5));
        S->window[strstart + i] = b;
        S->window[cur + i] = b;
    }
    /* Different bytes beyond to avoid unintended very long scans */
    S->window[strstart + actual_match_len + 6] = 'p';
    S->window[cur + actual_match_len + 6] = 'q';

    for (uInt i = actual_match_len + 7; i <= MAX_MATCH + 10; i++) {
        S->window[strstart + i] = 0;
        S->window[cur + i] = 0;
    }

    S->strstart = strstart;
    S->lookahead = lookahead;

    S->prev[cur & S->w_mask] = NIL;

    uInt got = test_longest_match(S, cur);
    TEST_ASSERT_EQUAL_UINT(lookahead, got);
    TEST_ASSERT_EQUAL_UINT(cur, S->match_start);
}

/* Test 3: No match (first bytes differ) -> returns prev_length (which defaults to MIN_MATCH-1 == 2) */
void test_longest_match_no_match_returns_prev_length(void) {
    IPos strstart, cur;
    prepare_positions(&strstart, &cur, 50);

    /* Intentionally differ at the start to fail immediately */
    S->window[strstart + 0] = 'A';
    S->window[cur + 0] = 'B';
    S->window[strstart + 1] = 'C';
    S->window[cur + 1] = 'D';
    S->window[strstart + 2] = 'E';
    S->window[cur + 2] = 'F';

    for (uInt i = 3; i <= MAX_MATCH + 5; i++) {
        S->window[strstart + i] = (Byte)0;
        S->window[cur + i] = (Byte)0;
    }

    S->strstart = strstart;
    S->lookahead = 100; /* arbitrary >= 3 */

    S->prev[cur & S->w_mask] = NIL;

    /* After deflateReset, prev_length should be MIN_MATCH-1 == 2 */
    TEST_ASSERT_EQUAL_UINT(MIN_MATCH - 1, S->prev_length);

    uInt got = test_longest_match(S, cur);
    TEST_ASSERT_EQUAL_UINT(MIN_MATCH - 1, got);
    /* match_start is unspecified in this case; don't check it */
}

/* Test 4: Found match shorter than prev_length -> function should return prev_length (discarding shorter match) */
void test_longest_match_discards_shorter_than_prev_length(void) {
    IPos strstart, cur;
    prepare_positions(&strstart, &cur, 120);

    const uInt shorter_match = 10;
    /* Create a match of length 10, then mismatch */
    for (uInt i = 0; i < shorter_match; i++) {
        Byte b = (Byte)('Z' - (i % 3));
        S->window[strstart + i] = b;
        S->window[cur + i] = b;
    }
    S->window[strstart + shorter_match] = 'x';
    S->window[cur + shorter_match] = 'y';

    for (uInt i = shorter_match + 1; i <= MAX_MATCH + 5; i++) {
        S->window[strstart + i] = (Byte)0;
        S->window[cur + i] = (Byte)0;
    }

    S->strstart = strstart;
    S->lookahead = 40;

    /* Set prev_length larger than the short found match */
    S->prev_length = 15;

    S->prev[cur & S->w_mask] = NIL;

    uInt got = test_longest_match(S, cur);
    TEST_ASSERT_EQUAL_UINT(15, got);
    /* match_start may be garbage in this case; do not assert it */
}

int main(void) {
    UNITY_BEGIN();
    RUN_TEST(test_longest_match_basic_match);
    RUN_TEST(test_longest_match_capped_by_lookahead);
    RUN_TEST(test_longest_match_no_match_returns_prev_length);
    RUN_TEST(test_longest_match_discards_shorter_than_prev_length);
    return UNITY_END();
}