[PATCH] fix potential infinite loop given large unsigned integer

[PATCH] fix potential infinite loop given large unsigned integer

[Ryan Flynn]

given n, tried to find i greater than n via i=1, iterate i *= 10.
given n sufficiently close to UINT_MAX this will overflow; which can
produce i==0, which results in an infinite loop. iteratively dividing
n /= 10 does not have this problem, and though division is slower than
multiplication this only runs once per `git format-patch
--cover-letter`

Signed-off-by: pizza <parseerror@gmail.com>
---
 log-tree.c |    6 +++---
 1 files changed, 3 insertions(+), 3 deletions(-)

diff --git a/log-tree.c b/log-tree.c
index 6f73c17..53a1bd2 100644
--- a/log-tree.c
+++ b/log-tree.c
@@ -160,9 +160,9 @@ static void append_signoff(struct strbuf *sb,
const char *signoff)

 static unsigned int digits_in_number(unsigned int number)
 {
-       unsigned int i = 10, result = 1;
-       while (i <= number) {
-               i *= 10;
+       unsigned int result = 1;
+       while (number > 9) {
+    number /= 10;
                result++;
        }
        return result;
-- 
1.6.0.4

Re: [PATCH] fix potential infinite loop given large unsigned integer

[Junio C Hamano]

Ryan Flynn <parseerror@gmail.com> writes:

> given n, tried to find i greater than n via i=1, iterate i *= 10.
> given n sufficiently close to UINT_MAX this will overflow; which can
> produce i==0, which results in an infinite loop. iteratively dividing
> n /= 10 does not have this problem, and though division is slower than
> multiplication this only runs once per `git format-patch
> --cover-letter`
>
> Signed-off-by: pizza <parseerror@gmail.com>

Pizza?

This is somewhat amusing.

 - digits_in_number() is called only with opt->total that is "int";

 - opt->total is the total number of patches.

 - the return value is used like this:

     sprintf(buf, "%0*d", digits_in_number(opt->total), opt->nr);

   and opt->nr runs from 1 to opt->total; the use of "d" would be already
   wrong anyway even if you computed digits_in_number() correctly.

Perhaps we should get rid of this function altogether?

Re: [PATCH] fix potential infinite loop given large unsigned integer

[Junio C Hamano]

Junio C Hamano <gitster@pobox.com> writes:

> Ryan Flynn <parseerror@gmail.com> writes:
>
>> given n, tried to find i greater than n via i=1, iterate i *= 10.
>> given n sufficiently close to UINT_MAX this will overflow; which can
>> produce i==0, which results in an infinite loop. iteratively dividing
>> n /= 10 does not have this problem, and though division is slower than
>> multiplication this only runs once per `git format-patch
>> --cover-letter`
>>
>> Signed-off-by: pizza <parseerror@gmail.com>
>
> Pizza?
>
> This is somewhat amusing.
>
>  - digits_in_number() is called only with opt->total that is "int";
>
>  - opt->total is the total number of patches.
>
>  - the return value is used like this:
>
>      sprintf(buf, "%0*d", digits_in_number(opt->total), opt->nr);
>
>    and opt->nr runs from 1 to opt->total; the use of "d" would be already
>    wrong anyway even if you computed digits_in_number() correctly.
>
> Perhaps we should get rid of this function altogether?

Or perhaps something stupid like this...

 builtin-log.c |    6 +++++-
 log-tree.c    |   12 +-----------
 revision.h    |    2 +-
 3 files changed, 7 insertions(+), 13 deletions(-)

diff --git a/builtin-log.c b/builtin-log.c
index 3817bf1..321e8f5 100644
--- a/builtin-log.c
+++ b/builtin-log.c
@@ -1096,8 +1096,12 @@ int cmd_format_patch(int argc, const char **argv, const char *prefix)
 	total = nr;
 	if (!keep_subject && auto_number && total > 1)
 		numbered = 1;
-	if (numbered)
+	if (numbered) {
+		static char num_buf[64];
 		rev.total = total + start_number - 1;
+		sprintf(num_buf, "%d", rev.total);
+		rev.num_width = strlen(num_buf);
+	}
 	if (in_reply_to || thread || cover_letter)
 		rev.ref_message_ids = xcalloc(1, sizeof(struct string_list));
 	if (in_reply_to) {
diff --git a/log-tree.c b/log-tree.c
index 6f73c17..0d32a6c 100644
--- a/log-tree.c
+++ b/log-tree.c
@@ -158,16 +158,6 @@ static void append_signoff(struct strbuf *sb, const char *signoff)
 	strbuf_addch(sb, '\n');
 }
 
-static unsigned int digits_in_number(unsigned int number)
-{
-	unsigned int i = 10, result = 1;
-	while (i <= number) {
-		i *= 10;
-		result++;
-	}
-	return result;
-}
-
 static int has_non_ascii(const char *s)
 {
 	int ch;
@@ -212,7 +202,7 @@ void log_write_email_headers(struct rev_info *opt, struct commit *commit,
 		snprintf(buffer, sizeof(buffer),
 			 "Subject: [%s %0*d/%d] ",
 			 opt->subject_prefix,
-			 digits_in_number(opt->total),
+			 opt->num_width,
 			 opt->nr, opt->total);
 		subject = buffer;
 	} else if (opt->total == 0 && opt->subject_prefix && *opt->subject_prefix) {
diff --git a/revision.h b/revision.h
index fb74492..21e4d9d 100644
--- a/revision.h
+++ b/revision.h
@@ -84,7 +84,7 @@ struct rev_info {
 	unsigned int	abbrev;
 	enum cmit_fmt	commit_format;
 	struct log_info *loginfo;
-	int		nr, total;
+	int		nr, total, num_width;
 	const char	*mime_boundary;
 	const char	*patch_suffix;
 	int		numbered_files;

Re: [PATCH] fix potential infinite loop given large unsigned integer

[Erik Faye-Lund]

On Sun, Aug 9, 2009 at 9:38 AM, Junio C Hamano<gitster@pobox.com> wrote:
> +               static char num_buf[64];
>                rev.total = total + start_number - 1;
> +               sprintf(num_buf, "%d", rev.total);
> +               rev.num_width = strlen(num_buf);

how about
rev.num_width = (int)log10((double)rev.total) + 1;

hm?

log10() appears to be C99, but can be emulated on earlier C-versions by doing
#define log10(x) (log(x) / log(10.0))

-- 
Erik "kusma" Faye-Lund
kusmabite@gmail.com
(+47) 986 59 656

Re: [PATCH] fix potential infinite loop given large unsigned integer

[Christian Couder]

On Sunday 09 August 2009, Erik Faye-Lund wrote:
> On Sun, Aug 9, 2009 at 9:38 AM, Junio C Hamano<gitster@pobox.com> wrote:
> > +               static char num_buf[64];
> >                rev.total = total + start_number - 1;
> > +               sprintf(num_buf, "%d", rev.total);
> > +               rev.num_width = strlen(num_buf);
>
> how about
> rev.num_width = (int)log10((double)rev.total) + 1;
>
> hm?
>
> log10() appears to be C99, but can be emulated on earlier C-versions by
> doing #define log10(x) (log(x) / log(10.0))

That would mean linking with -lm?

Regards,
Christian.

Re: [PATCH] fix potential infinite loop given large unsigned integer

[Erik Faye-Lund]

On Mon, Aug 10, 2009 at 7:24 AM, Christian
Couder<chriscool@tuxfamily.org> wrote:
>> log10() appears to be C99, but can be emulated on earlier C-versions by
>> doing #define log10(x) (log(x) / log(10.0))
>
> That would mean linking with -lm?

I guess so. Are we currently trying to avoid linking to the math-parts of libc?

-- 
Erik "kusma" Faye-Lund
kusmabite@gmail.com
(+47) 986 59 656

Re: [PATCH] fix potential infinite loop given large unsigned integer

[Johannes Schindelin]

Hi,

On Mon, 10 Aug 2009, Erik Faye-Lund wrote:

> On Mon, Aug 10, 2009 at 7:24 AM, Christian
> Couder<chriscool@tuxfamily.org> wrote:
> >> log10() appears to be C99, but can be emulated on earlier C-versions by
> >> doing #define log10(x) (log(x) / log(10.0))
> >
> > That would mean linking with -lm?
> 
> I guess so. Are we currently trying to avoid linking to the math-parts 
> of libc?

Yes.

I guess we could fix the overflow thing very easily, though:

static unsigned int digits_of_number(unsigned int number) {
	unsigned int result;
	for (result = 1; number; number /= 10, result++)
		; /* do nothing */
	return result;
}

Ciao,
Dscho

Re: [PATCH] fix potential infinite loop given large unsigned integer

[Ryan Flynn]

On Mon, Aug 10, 2009 at 8:24 AM, Johannes
Schindelin<Johannes.Schindelin@gmx.de> wrote:
> Hi,
>
> On Mon, 10 Aug 2009, Erik Faye-Lund wrote:
>
>> On Mon, Aug 10, 2009 at 7:24 AM, Christian
>> Couder<chriscool@tuxfamily.org> wrote:
>> >> log10() appears to be C99, but can be emulated on earlier C-versions by
>> >> doing #define log10(x) (log(x) / log(10.0))
>> >
>> > That would mean linking with -lm?
>>
>> I guess so. Are we currently trying to avoid linking to the math-parts
>> of libc?
>
> Yes.
>
> I guess we could fix the overflow thing very easily, though:
>
> static unsigned int digits_of_number(unsigned int number) {
>        unsigned int result;
>        for (result = 1; number; number /= 10, result++)
>                ; /* do nothing */
>        return result;
> }
>
> Ciao,
> Dscho
>
>

that is equivalent to the original patch, yes.

Re: [PATCH] fix potential infinite loop given large unsigned integer

[Ryan Flynn]

On Mon, Aug 10, 2009 at 8:24 AM, Johannes
Schindelin<Johannes.Schindelin@gmx.de> wrote:
> Hi,
>
> On Mon, 10 Aug 2009, Erik Faye-Lund wrote:
>
>> On Mon, Aug 10, 2009 at 7:24 AM, Christian
>> Couder<chriscool@tuxfamily.org> wrote:
>> >> log10() appears to be C99, but can be emulated on earlier C-versions by
>> >> doing #define log10(x) (log(x) / log(10.0))
>> >
>> > That would mean linking with -lm?
>>
>> I guess so. Are we currently trying to avoid linking to the math-parts
>> of libc?
>
> Yes.
>
> I guess we could fix the overflow thing very easily, though:
>
> static unsigned int digits_of_number(unsigned int number) {
>        unsigned int result;
>        for (result = 1; number; number /= 10, result++)
>                ; /* do nothing */
>        return result;
> }
>
> Ciao,
> Dscho
>
>

whoops, actually yours: digits_of_number(1) -> 2

Re: [PATCH] fix potential infinite loop given large unsigned integer

[Johannes Schindelin]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 845 bytes --]

Hi,

[please cull the quoted text to what you are actually replying to.  
Thanks]

On Mon, 10 Aug 2009, Ryan Flynn wrote:

> On Mon, Aug 10, 2009 at 8:24 AM, Johannes
> Schindelin<Johannes.Schindelin@gmx.de> wrote:
> >
> > static unsigned int digits_of_number(unsigned int number) {
> >     unsigned int result;
> >     for (result = 1; number; number /= 10, result++)
> >         ; /* do nothing */
> >     return result;
> > }
> 
> whoops, actually yours: digits_of_number(1) -> 2

static unsigned int digits(unsigned int number)
{
        unsigned int result;
        for (result = 1; (number /= 10); result++)
                ; /* do nothing */
        return result;
}

I'm sorry, I forgot the "something like this" in my mail.

This version is actually tested.

It has non-optimal runtime, but then, it does not really matter.

Ciao,
Dscho

Re: [PATCH] fix potential infinite loop given large unsigned integer

[Jeff Epler]

On Sun, Aug 09, 2009 at 02:25:40PM +0200, Erik Faye-Lund wrote:
> log10() appears to be C99, but can be emulated on earlier C-versions by doing
> #define log10(x) (log(x) / log(10.0))

I don't think you'll like the results of this very much.
    #include <math.h>
    #include <stdio.h>

    int main(void) {
        double n=1;
        int i, j;
        for(i=0; i<10; i++, n*=10) {
            j = (int)(log(n)/log(10));
            if(i != j) printf("%d %d\n", i, (int)j);
        }
        return 0;
    }

(on my system, 3 of the 10 tested cases give the wrong answer due to
rounding)

For a tour of some of the difficulties of implementing log10,
    http://www.cs.berkeley.edu/~wkahan/LOG10HAF.TXT

Jeff

Re: [PATCH] fix potential infinite loop given large unsigned integer

[Ryan Flynn]

On Sun, Aug 9, 2009 at 3:38 AM, Junio C Hamano<gitster@pobox.com> wrote:
> Junio C Hamano <gitster@pobox.com> writes:
>
>> Ryan Flynn <parseerror@gmail.com> writes:
>>
>>> given n, tried to find i greater than n via i=1, iterate i *= 10.
>>> given n sufficiently close to UINT_MAX this will overflow; which can
>>> produce i==0, which results in an infinite loop. iteratively dividing
>>> n /= 10 does not have this problem, and though division is slower than
>>> multiplication this only runs once per `git format-patch
>>> --cover-letter`
>>>
>>> Signed-off-by: pizza <parseerror@gmail.com>
>>
>> Pizza?
>>
>> This is somewhat amusing.
>>
>>  - digits_in_number() is called only with opt->total that is "int";
>>
>>  - opt->total is the total number of patches.
>>
>>  - the return value is used like this:
>>
>>      sprintf(buf, "%0*d", digits_in_number(opt->total), opt->nr);
>>
>>    and opt->nr runs from 1 to opt->total; the use of "d" would be already
>>    wrong anyway even if you computed digits_in_number() correctly.
>>
>> Perhaps we should get rid of this function altogether?
>
> Or perhaps something stupid like this...
>
>  builtin-log.c |    6 +++++-
>  log-tree.c    |   12 +-----------
>  revision.h    |    2 +-
>  3 files changed, 7 insertions(+), 13 deletions(-)
>
> diff --git a/builtin-log.c b/builtin-log.c
> index 3817bf1..321e8f5 100644
> --- a/builtin-log.c
> +++ b/builtin-log.c
> @@ -1096,8 +1096,12 @@ int cmd_format_patch(int argc, const char **argv, const char *prefix)
>        total = nr;
>        if (!keep_subject && auto_number && total > 1)
>                numbered = 1;
> -       if (numbered)
> +       if (numbered) {
> +               static char num_buf[64];
>                rev.total = total + start_number - 1;
> +               sprintf(num_buf, "%d", rev.total);
> +               rev.num_width = strlen(num_buf);
> +       }
>        if (in_reply_to || thread || cover_letter)
>                rev.ref_message_ids = xcalloc(1, sizeof(struct string_list));
>        if (in_reply_to) {
> diff --git a/log-tree.c b/log-tree.c
> index 6f73c17..0d32a6c 100644
> --- a/log-tree.c
> +++ b/log-tree.c
> @@ -158,16 +158,6 @@ static void append_signoff(struct strbuf *sb, const char *signoff)
>        strbuf_addch(sb, '\n');
>  }
>
> -static unsigned int digits_in_number(unsigned int number)
> -{
> -       unsigned int i = 10, result = 1;
> -       while (i <= number) {
> -               i *= 10;
> -               result++;
> -       }
> -       return result;
> -}
> -
>  static int has_non_ascii(const char *s)
>  {
>        int ch;
> @@ -212,7 +202,7 @@ void log_write_email_headers(struct rev_info *opt, struct commit *commit,
>                snprintf(buffer, sizeof(buffer),
>                         "Subject: [%s %0*d/%d] ",
>                         opt->subject_prefix,
> -                        digits_in_number(opt->total),
> +                        opt->num_width,
>                         opt->nr, opt->total);
>                subject = buffer;
>        } else if (opt->total == 0 && opt->subject_prefix && *opt->subject_prefix) {
> diff --git a/revision.h b/revision.h
> index fb74492..21e4d9d 100644
> --- a/revision.h
> +++ b/revision.h
> @@ -84,7 +84,7 @@ struct rev_info {
>        unsigned int    abbrev;
>        enum cmit_fmt   commit_format;
>        struct log_info *loginfo;
> -       int             nr, total;
> +       int             nr, total, num_width;
>        const char      *mime_boundary;
>        const char      *patch_suffix;
>        int             numbered_files;
>

why carry around a piece of information that is only used in one place
and is not expensive to calculate? how about a middle-ground such as:

diff --git a/log-tree.c b/log-tree.c
index 6f73c17..4888518 100644
--- a/log-tree.c
+++ b/log-tree.c
@@ -158,14 +158,11 @@ static void append_signoff(struct strbuf *sb,
const char *signoff)
        strbuf_addch(sb, '\n');
 }

-static unsigned int digits_in_number(unsigned int number)
+static int digits_in_number(int number)
 {
-       unsigned int i = 10, result = 1;
-       while (i <= number) {
-               i *= 10;
-               result++;
-       }
-       return result;
+  static char num_buf[64];
+  sprintf(num_buf, "%u", number);
+  return (int)strlen(num_buf);
 }

 static int has_non_ascii(const char *s)

Re: [PATCH] fix potential infinite loop given large unsigned integer

[Tony Finch]

On Sun, 9 Aug 2009, Junio C Hamano wrote:

> +	if (numbered) {
> +		static char num_buf[64];
>  		rev.total = total + start_number - 1;
> +		sprintf(num_buf, "%d", rev.total);
> +		rev.num_width = strlen(num_buf);
> +	}

why not

	if (numbered) {
		rev.total = total + start_number - 1;
		rev.num_width = snprintf(NULL, 0, "%d", rev.total);
	}

?

Tony.
-- 
f.anthony.n.finch  <dot@dotat.at>  http://dotat.at/
GERMAN BIGHT HUMBER: SOUTHWEST 5 TO 7. MODERATE OR ROUGH. SQUALLY SHOWERS.
MODERATE OR GOOD.

Re: [PATCH] fix potential infinite loop given large unsigned integer

[Ryan Flynn]

> Perhaps we should get rid of this function altogether?

I was thinking of something like that, but figured i'd start small and
fix the bug first.