#50 giflib test suite fails for the MinGW build

[Eli Zaretskii]

2 tests fail:

gif2rgb-regress test fails:

 gif2rgb: Checking idempotency
 --- gifgrid.ico 2013-08-29 22:56:39 +0300
 +++ -   2013-10-06 09:23:05 +0300
 @@ -8,9 +8,9 @@
     sort flag on
     rgb 000 000 248 is 0
     rgb 248 000 000 is 1
 -       rgb 000 016 160 is 2
 +       rgb 160 176 160 is 2
     rgb 160 016 000 is 3
 -       rgb 160 176 160 is 4
 +       rgb 000 016 160 is 4
     rgb 248 248 248 is 5
     rgb 000 000 000 is 6
     rgb 000 000 000 is 7

followed by many differences due to 2 <-> 4 swap above.

gifclrmp-regres also fails:

 x-trans.map /tmp/regress differ: char 16, line 1
 makefile:76: recipe for target `gifclrmp-regress' failed
 make[3]: *** [gifclrmp-regress] Error 1

But this is just because of NL <-> CRLF differences between the
expected and actual outputs; replacing "cmp" with "diff -u" fixes
the problem with the gifclrmp-regres test.

Let me know if you need more information about the first failure.

[Eric S. Raymond]

I would like more information about the first failure.

I've applied your suggestion about the test production.

[Eli Zaretskii]

Please tell which additional information to provide. I didn't dig into the program to see why it produces a different output. Pointers as to where to step with a debugger and which variables to examine will be appreciated. (If my original text sounded like I have more info, but omitted it from the report, I apologize.)

[Eric S. Raymond]

Eli Zaretskii eli-zaretskii@users.sf.net:

Please tell which additional information to provide. I didn't dig
into the program to see why it produces a different output.
Pointers as to where to step with a debugger and which variables to
examine will be appreciated. (If my original text sounded like I
have more info, but omitted it from the report, I apologize.)

All I know for sure at the moment is that this test problem doesn't
replicate under a 64-bit Linux.

Looking at this test,

gif2rgb-regress:
@echo "gif2rgb: Checking idempotency"
@$(UTILS)/gif2rgb -c 3 -s 100 100 <gifgrid.rgb | $(UTILS)/gifbuild -d | diff -u gifgrid.ico -

the problem could be in one of two places. To pin down which, please do this:

gif2rgb -c 3 -s 100 100 <gifgrid.rgb>scratch.gif

then mail me scratch.gif. If it compares different from what I generate
the port problem is in gif2rgb; if it compares the same it's in gifbuild.

My bet is on the former, though I have no idea what platform issue
could be involved here.
--
Eric S. Raymond

[Eli Zaretskii]

The file scratch.gif is attached. It was produced by this command:

../util/gif2rgb -c 3 -s 100 100 < gifgrid.rgb > scratch.gif

If the file is different from what you get, please send me yours, so I could use the differences to guide me through debugging this.

[Eli Zaretskii]

I think I see the problem. gif2rgb sorts the colors in the color map using qsort (in quantize.c). But qsort is not a stable sort, so entries that have equal RGB values will have arbitrary positions in the sorted array, depending on the details of the qsort implementation. I see quite a few values that are equal being passed to the comparison routine when the program runs.

Does this make sense? If so, perhaps using some stable sorting algorithm will solve the problem.

[Eric S. Raymond]

Eli Zaretskii eli-zaretskii@users.sf.net:

I think I see the problem. gif2rgb sorts the colors in the color map using qsort (in quantize.c). But qsort is not a stable sort, so entries that have equal RGB values will have arbitrary positions in the sorted array, depending on the details of the qsort implementation. I see quite a few values that are equal being passed to the comparison routine when the program runs.

Does this make sense? If so, perhaps using some stable sorting algorithm will solve the problem.

That does make sense. Looking at the code, it's actually worse than
you're supposing. For some reason, which is probably buried deep in
the details of how the quantization algorithm works, the sort value of
a tuple is one of its coordinates - which one is given by the global
static variable SortRGBAxis.

Here's the sort function in utils/quantize.c

static int
SortCmpRtn(const void Entry1,
const void Entry2) {

return (*((QuantizedColorType **) Entry1))->RGB[SortRGBAxis] -
   (*((QuantizedColorType **) Entry2))->RGB[SortRGBAxis];

}

This code is easier to understand and modify if rewritten this way:

static int
SortCmpRtn(const void Entry1,
const void Entry2) {
QuantizedColorType entry1 = (((QuantizedColorType ) Entry1));
QuantizedColorType entry2 = (((QuantizedColorType ) Entry2));

   /* only sorting on one axis of the color space! */
   int hash1 = entry1->RGB[SortRGBAxis];
   int hash2 = entry2->RGB[SortRGBAxis];

return hash1 - hash2;

}

Before even getting to the sort stability issue, we need to change
this code so preserves the ordering implied by the existing versions,
but hashes in all three RGB components so each RGB tuple has a unique
value. Perhaps something like this:

static int
SortCmpRtn(const void Entry1,
const void Entry2) {
QuantizedColorType entry1 = (((QuantizedColorType ) Entry1));
QuantizedColorType entry2 = (((QuantizedColorType ) Entry2));

   /* sort on all axes of the color space! */
   int hash1 = entry1->RGB[SortRGBAxis] * 256 * 256
            + entry1->RGB[(SortRGBAxis+1) % 3] * 256
            + entry1->RGB[(SortRGBAxis+2) % 3];

return hash1 - hash2;

}

Have you got stable-sort source code in your back pocket?

    <a href="http://www.catb.org/~esr/">Eric S. Raymond</a>

[Eric S. Raymond]

The modified sort function (er, with an additional line to compute hash2) seems to pass all regression tests, so I've pushed that change.

Please test to see if it makes your failure go away

[Eli Zaretskii]

Yes, all tests now pass.

Thanks!

[Eric S. Raymond]

Eli Zaretskii eli-zaretskii@users.sf.net:

Yes, all tests now pass.

Thanks!

Excellent. I'm going to close this, then. The port bug only affects
regression testing - the quantization routine isn't used in the GIF
library itself, and for production purposes the instability should
be harmless anyway..

I've left a comment in the code noting that there could still be a
port problem on images with the same RGB tuple mapped by multiple
color table indices.
--
Eric S. Raymond