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

[Former user]

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

[Rashad Kanavath]

@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;
   }

[Pierre Joye]

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?

[Rashad Kanavath]

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

[Former user]

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 b0481588.

[Remi]

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

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

[Remi]

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.

[Former user]

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

[Pierre Joye]

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.

[Former user]

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

[Remi]

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

[Remi]

fix integer overflow in AAline, fixed issue #5

→ <<cset 837b73276dea>>

[Remi]

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

#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;
}

[Remi]

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.

[Pierre Joye]

@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.