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

Issue #5 resolved
Former user created an issue

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

Comments (15)

  1. 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;
       }
    
    
  2. 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?

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

  4. Former user Account Deleted

    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.

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

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

  7. Former user Account Deleted

    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.

  8. Remi

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

  9. 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;
    }
    
  10. 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.

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

  12. Log in to comment