Schulze STV bugs

Here are the bugs I found in prog01.c, Schulze's 2007 implementation of 
Schulze STV:

1. Undefined behavior due to sequence ordering:

This is the big one. In line 818 of prog01.c, we have

> Value2[i2]=Value2[i2]++;

This is undefined, because (as far as I understand it) Value[i2] is 
being altered twice: once by the assignment and once by the 
postdecrement, but the C standard doesn't specify in what order this 
should happen. Presumably the MSVC compiler Schulze used interpreted 
this as incrementing Value2[i2]. Modern compilers do something else, and 
this breaks the implementation, producing erroneous election outcomes. 
To fix, replace the line with

> Value2[i2]++;

This bug can be exercised by the A68.dat election: the intended Schulze 
STV outcome is ACD, but if the code behaves incorrectly, it'll return 
ABC instead.


2. The Test3 array is in some cases too small, leading to out-of-bounds 
writes.

The following example election exercises the bug:

> M 10
> C 13
> N 1
> F 2
> 
> BEGIN
> 1 A B C D E F G
> END

The allocation statement at fault is

> Test3    =(int                 *)calloc(N2+1           ,sizeof(int                 ));

Apparently N2+1 is too small. I don't know what the proper allocation 
size is, though.


3. The n-choose-k function over(n, k) doesn't recognize overflow, and 
internally overflows in some cases even when n choose k is well within 
integer bounds.

Thus with enough candidates, over() overflows and returns a negative 
value, which leads to a crash in malloc. This is kinda theoretical 
because even with the bug fixed, such instances will usually be too 
large to practically count anyway. However, one may note that over() can 
also overflow on say, over(30, 29), even if 30 choose 29 is not itself 
very large.

The following election exercises this bug:

> M 29
> C 30
> N 1
> F 2
> 
> BEGIN
> 1 A
> END

Even with the bug fixed, prog01 gets stuck on this example: something 
inside the proportional completion function is taking a very long time. 
But I don't know if it's a bug or an unavoidable consequence of the 
algorithm itself.

-km
----
Election-Methods mailing list - see https://electorama.com/em for list info