Re: [PATCH v6] diff-delta: use safe integer arithmetic

From: Pablo Sabater <pabloosabaterr@gmail.com>
Date: Oct 27, 2026, 10:33 UTC
Message-ID: <DMFJX3GJOXI0.1US2IH6P4LRUR@gmail.com>
In-Reply-To: <pull.2276.v6.git.1793076683043.gitgitgadget@gmail.com>

On Tue Oct 27, 2026 at 4:51 AM WET, Srujith A Poojary via GitGitGadget wrote:

> From: Srujith A Poojary <poojarysrujith@gmail.com>
>

[snip]

>
> For the unpacked index allocation:
> - sizeof(struct unpacked_index_entry) is 12 bytes on 32-bit systems,
>   which may be padded to 16 bytes depending on compiler alignment rules.

	l 117-125 'diff-delta.c'

	struct index_entry {
		const unsigned char *ptr;
		unsigned int val;
	};

	struct unpacked_index_entry {
		struct index_entry entry;
		struct unpacked_index_entry *next;
	};

On 32 bit systems we have 4 bytes ptr + 4 bytes uint + 4 bytes ptr. I don't see how it could be padded to 16.

> - sizeof(struct index_entry *) is 4 bytes.
> - entries is capped by (0xffffffu / RABIN_WINDOW) where RABIN_WINDOW is 16,
>   limiting entries to 1,048,575.

	l 148-158 'diff-delta.c'

	/* Determine index hash size.  Note that indexing skips the
	   first byte to allow for optimizing the Rabin's polynomial
	   initialization in create_delta(). */
	entries = (bufsize - 1) / RABIN_WINDOW;
	if (bufsize >= 0xffffffffUL) {
		/*
		 * Current delta format can't encode offsets into
		 * reference buffer with more than 32 bits.
		 */
		entries = 0xfffffffeU / RABIN_WINDOW;
	}

entries are capped by 0xfffffffeU so the real limit is: 268 435 455 (256 times more)

> - hsize is the smallest power of 2 greater than or equal to entries,
>   capped at 1,048,576.

After the code above we find this:

	l 159-162 'diff-delta.c'

	hsize = entries / 4;
	for (i = 4; (1u << i) < hsize; i++);
	hsize = 1 << i;
	hmask = hsize - 1;

What this does is set hsize to the smallest power of 2 >= entries / 4 (with a minimum of 16), so it's "capped" at 67 108 864 (2^26).

[snip]

Show 34 quoted lines

>
>  diff-delta.c | 10 +++++-----
>  1 file changed, 5 insertions(+), 5 deletions(-)
>
> diff --git a/diff-delta.c b/diff-delta.c
> index 7cbedeb507..efebce3aca 100644
> --- a/diff-delta.c
> +++ b/diff-delta.c
> @@ -162,8 +162,8 @@ struct delta_index * create_delta_index(const void *buf, size_t bufsize)
>  	hmask = hsize - 1;
>  
>  	/* allocate lookup index */
> -	memsize = sizeof(*hash) * hsize +
> -		  sizeof(*entry) * entries;
> +	memsize = st_add(st_mult(sizeof(*hash), hsize),
> +			 st_mult(sizeof(*entry), entries));
>  	mem = malloc(memsize);
>  	if (!mem)
>  		return NULL;
> @@ -258,9 +258,9 @@ struct delta_index * create_delta_index(const void *buf, size_t bufsize)
>  	 * Now create the packed index in array form
>  	 * rather than linked lists.
>  	 */
> -	memsize = sizeof(*index)
> -		+ sizeof(*packed_hash) * (hsize+1)
> -		+ sizeof(*packed_entry) * entries;
> +	memsize = st_add3(sizeof(*index),
> +			  st_mult(sizeof(*packed_hash), hsize + 1),
> +			  st_mult(sizeof(*packed_entry), entries));
>  	mem = malloc(memsize);
>  	if (!mem) {
>  		free(hash);
>
> base-commit: 47fdf2208c5b94c8cc01c106b8f7c85efb91c926

The code looks good.

Good job ;), Pablo