Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

gdImageLine may misbehave or enter infinite loop if anti-aliasing is used and image size > 32768 #5

Closed
imazen-bot opened this Issue Feb 5, 2015 · 14 comments

Comments

Projects
None yet
1 participant
@imazen-bot
Copy link

imazen-bot commented Feb 5, 2015

Please look at the following piece of code:

#include<stdio.h>
#include "gd.h"

int main() {
  /* Declare the image */
  gdImagePtr im;
  /* Declare output files */
  FILE *pngout;
  int black, white;

  im = gdImageCreateTrueColor(63318, 771);

  /* Allocate the color white (red, green and blue all maximum). */
  white = gdImageColorAllocate(im, 255, 255, 255);  
  /* Allocate the color white (red, green and blue all maximum). */
  black = gdImageColorAllocate(im, 0, 0, 0);  

  /* white background */
  gdImageFill(im, 1, 1, white);

  gdImageSetAntiAliased(im, black);

  /* This line fails! */
  gdImageLine(im, 28562, 631, 34266, 750, gdAntiAliased);  

  /* Open a file for writing. "wb" means "write binary", important
    under MSDOS, harmless under Unix. */
  pngout = fopen("test.png", "wb");

 /* Output the image to the disk file in PNG format. */
  gdImagePng(im, pngout);

  /* Close the files. */
  fclose(pngout);

  /* Destroy the image in memory. */
  gdImageDestroy(im);
}

The function gdImageLine seems to never return, if at least one of the coordinates is over 32768 and anti-aliasing is used.

With coordinates different from the above example, the function may return, but the line drawn is still incorrect.

This problem was originally reported to gnuplot (bug no. 3377536), but I was able to isolate it.

gd version: 2.0.36
system: Ubuntu linux 10.04.2 32-bit

Péter Juhász


@imazen-bot

This comment has been minimized.

Copy link
Author

imazen-bot commented Feb 5, 2015

@line 3716 src/gd.c
{{{

//infinite loop here
not exiting from this loop
while ((x >> 16) <= x2)
{
gdImageSetAAPixelColor(im, x >> 16, y >> 16, col, (y >> 8) & 0xFF);
gdImageSetAAPixelColor(im, x >> 16, (y >> 16) + 1,col, (~y >> 8) & 0xFF);
x += (1 << 16);
y += inc;
}

}}}


Originally posted by bugbrains (Rashad M) on Nov 28 2011 via Bitbucket

@imazen-bot

This comment has been minimized.

Copy link
Author

imazen-bot commented Feb 5, 2015

Also it is more about the horizontal distance covered by the line being larger than 32768 than the actual image size. We may clip the line before if it is not already done. no?


Originally posted by pierrejoye (Pierre Joye) on Nov 28 2011 via Bitbucket

@imazen-bot

This comment has been minimized.

Copy link
Author

imazen-bot commented Feb 5, 2015

you mean to add a check that if line's horizontal distance is in range of actual image size?. please tell me how to get original image size of image so that i can add a patch


Originally posted by bugbrains (Rashad M) on Dec 16 2011 via Bitbucket

@imazen-bot imazen-bot closed this Feb 5, 2015

@imazen-bot

This comment has been minimized.

Copy link
Author

imazen-bot commented Feb 5, 2015

Hi, @bugbrains, I am unable to reproduce the bug in the 2.1.0RC1 using the code you have sent. There's PASSing test based on your code now in b048158.


Originally posted by oerdnj (Ondřej Surý) on Jun 07 2013 via Bitbucket

@imazen-bot

This comment has been minimized.

Copy link
Author

imazen-bot commented Feb 5, 2015

I can reproduce: gdimageline_bug5.c hangs on 32bits build.

When x > 32767, x<<16 is < 0


Originally posted by remicollet (Remi Collet) on Jun 10 2013 via Bitbucket

@imazen-bot

This comment has been minimized.

Copy link
Author

imazen-bot commented Feb 5, 2015

See eca37d6
This fixes the hang.
As (x<<16) is never used, simply use x for the loop.
But we still can have interger overflow in (y<<16).
I'm searching for a better/full fix.


Originally posted by remicollet (Remi Collet) on Jun 10 2013 via Bitbucket

@imazen-bot

This comment has been minimized.

Copy link
Author

imazen-bot commented Feb 5, 2015

True, only amd64, ia64 and s390x builds ok: https://buildd.debian.org/status/package.php?p=libgd2


Originally posted by oerdnj (Ondřej Surý) on Jun 10 2013 via Bitbucket

@imazen-bot

This comment has been minimized.

Copy link
Author

imazen-bot commented Feb 5, 2015

we have other places where large images may cause issues, sometimes much smaller than 32768. One solution I was thinking is to have to implementation and use int64_t if the requested size of a drawing ops will overflow.


Originally posted by pierrejoye (Pierre Joye) on Jun 10 2013 via Bitbucket

@imazen-bot

This comment has been minimized.

Copy link
Author

imazen-bot commented Feb 5, 2015

Same thinking, I have just replaced long(s) with (u)int32_t(s) in ad501ab, and the check now passes just fine in i386 chroot.


Originally posted by oerdnj (Ondřej Surý) on Jun 10 2013 via Bitbucket

@imazen-bot

This comment has been minimized.

Copy link
Author

imazen-bot commented Feb 5, 2015

Switching from 31 to 32 bits will solve some run case (16bits value), but not all, as we can have greater value.


Originally posted by remicollet (Remi Collet) on Jun 10 2013 via Bitbucket

@imazen-bot

This comment has been minimized.

Copy link
Author

imazen-bot commented Feb 5, 2015

fix integer overflow in AAline, fixed issue #5

→ <<cset 837b732>>


Originally posted by remicollet (Remi Collet) on Jun 10 2013 via Bitbucket

@imazen-bot

This comment has been minimized.

Copy link
Author

imazen-bot commented Feb 5, 2015

Here is the piece of code run to check both algo give same result

#!c

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAX 50000
long stack[MAX];
int pos, nb;

void pull(long x, long y, long frac) {
    if ((nb+3)>=MAX) {
        printf("Stack overflow\n");
    } else {
        stack[nb++] = x;
        stack[nb++] = y;
        stack[nb++] = frac;
    }
}

int check(long x, long y, long frac) {
    int ret = 0;
    if (pos>=nb) {
        printf("Emty stack\n");
    } else {
        if (stack[pos]!=x || stack[pos+1]!=y || stack[pos+2]!=frac) {
            printf("%ld,%ld,%ld, expected %ld,%ld,%ld\n",
                x, y, frac,
                stack[pos], stack[pos+1], stack[pos+2]);
            ret = 1;
        }
        pos+=3;
    }
    return ret;
}

int main(int argc, char *argv[]) {
    //int x1=28562, y1=631, x2=34266, y2=750;
    int x1=28562, y1=750, x2=34266, y2=631;
    long x, y, inc;
    long dx, dy;
    long w, wid, wstart, frac; 
    double ag;

    printf("Build ref\n");
    dx = x2 - x1;
    dy = y2 - y1;
    ag = (abs(dy) < abs(dx)) ? cos(atan2(dy, dx)) : sin(atan2(dy, dx));
    if (ag != 0) {
        wid = abs(1 / ag);
    } else {
        wid = 1;
    }
    if (wid == 0) {
        wid = 1;
    }
    printf("wid = %ld\n", wid);

    printf("dx=%ld, dy=%ld\n", dx, dy);

    pos = nb = 0;

    x = x1;
    y = y1 << 16;
    inc = (dy * 65536) / dx;
    printf("inc=%ld\n", inc);

    while (x <= x2) {
        wstart = (y >> 16) - wid / 2;
        for (w = wstart; w < wstart + wid; w++) {
            pull(x , w , (y >> 8) & 0xFF);
            pull(x , w+1 , (~y >> 8) & 0xFF);
        }
        x++;
        y += inc;
    }

    printf("New algo\n");
    y = y1;
    inc = (dy * 65536) / dx;
    frac = 0;
    for (x=x1 ; x <= x2 ; x++) {
        wstart = y - wid / 2;
        for (w = wstart; w < wstart + wid; w++) {
            if (check(x , w , (frac >> 8) & 0xFF)) {
                printf("FRAC = %ld\n", frac);
            }
            check(x , w+1 , (~frac >> 8) & 0xFF);
        }
        frac += inc;
        if (frac >= 65536) {
            frac -= 65536;
            y++;
        } else if (frac < 0) {
            frac += 65536;
            y--;
        }
    }


    return 0;
}

Originally posted by remicollet (Remi Collet) on Jun 10 2013 via Bitbucket

@imazen-bot

This comment has been minimized.

Copy link
Author

imazen-bot commented Feb 5, 2015

Current implemented solution is to use 2 values, both in int32 range.

@pierrejoye : yes I think a switch to int64 will make code more legible, more consistent, easier to maintain, especially as most of us now works on 64bits OS.


Originally posted by remicollet (Remi Collet) on Jun 10 2013 via Bitbucket

@imazen-bot

This comment has been minimized.

Copy link
Author

imazen-bot commented Feb 5, 2015

@remicollet by 64bit I mean on 64bit systems only, and 32bit on 32bit systems.

Also in 2.2 we should really get rid of long, it is not portable and use int32/64_t instead.


Originally posted by pierrejoye (Pierre Joye) on Jun 10 2013 via Bitbucket

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.