From mboxrd@z Thu Jan 1 00:00:00 1970 From: jamie.couture at gmail.com (Jamie Couture) Date: Sat, 10 Sep 2011 20:44:22 -0400 Subject: [PATCH] move LCS table away from the stack In-Reply-To: <1315701862-30457-1-git-send-email-jamie.couture@gmail.com> References: <1315543390-12451-2-git-send-email-jamie.couture@gmail.com> <1315701862-30457-1-git-send-email-jamie.couture@gmail.com> Message-ID: <1315701862-30457-2-git-send-email-jamie.couture@gmail.com> Printing deferred line changes for files containing long lines would cause a segfault. Set limitations and move lookup table out of the stack. Signed-off-by: Jamie Couture --- cgit.h | 12 ++++++++++++ ui-ssdiff.c | 32 ++++++++++++++++++++++++++++++-- 2 files changed, 42 insertions(+), 2 deletions(-) diff --git a/cgit.h b/cgit.h index bad66f0..1ff5cb3 100644 --- a/cgit.h +++ b/cgit.h @@ -47,6 +47,18 @@ */ #define PAGE_ENCODING "UTF-8" +/* + * ssdiff line limits + */ +#ifndef MAX_SSDIFF_M +#define MAX_SSDIFF_M 1024 +#endif + +#ifndef MAX_SSDIFF_N +#define MAX_SSDIFF_N 1024 +#endif +#define MAX_SSDIFF_SIZE ((MAX_SSDIFF_M) * (MAX_SSDIFF_N)) + typedef void (*configfn)(const char *name, const char *value); typedef void (*filepair_fn)(struct diff_filepair *pair); typedef void (*linediff_fn)(char *line, int len); diff --git a/ui-ssdiff.c b/ui-ssdiff.c index 2481585..4df01ed 100644 --- a/ui-ssdiff.c +++ b/ui-ssdiff.c @@ -16,16 +16,41 @@ struct deferred_lines { static struct deferred_lines *deferred_old, *deferred_old_last; static struct deferred_lines *deferred_new, *deferred_new_last; +static int **create_lcs_table(size_t m, size_t n) +{ + int **L; + int i; + + // xcalloc will die if we ran out of memory; + // not very helpful for debugging + L = (int**)xcalloc(m, sizeof(int *)); + *L = (int*)xcalloc(m * n, sizeof(int)); + + for (i = 1; i < m; i++) { + L[i] = *L + i * n; + } + + return L; +} + static char *longest_common_subsequence(char *A, char *B) { int i, j, ri; int m = strlen(A); int n = strlen(B); - int L[m + 1][n + 1]; - int tmp1, tmp2; + int **L; + int tmp1, tmp2, length; int lcs_length; char *result; + length = (m + 1) * (n + 1); + + // We bail if the lines are too long + if (length > MAX_SSDIFF_SIZE) + return NULL; + + L = create_lcs_table(m + 1, n + 1); + for (i = m; i >= 0; i--) { for (j = n; j >= 0; j--) { if (A[i] == '\0' || B[j] == '\0') { @@ -59,6 +84,9 @@ static char *longest_common_subsequence(char *A, char *B) j += 1; } } + + free(*L); + free(L); return result; } -- 1.7.6