[CF-Devel] Suspicious code in common/object.c

[crossfire-devel at archives.real-time.com]

I think the function get_search_arr() in common/object.c does not work
correctly: it should return a permutation of [0..48] but the result
nearly always contains more than one 0 value.

For example: If the statement "tmp=(RANDOM()%(5-i+1))+1" at the end of
the function (for the range i=1..4) always evaluates to "tmp=1", the
result is search_nums[1..4]={1,2,3,0}. This is not correct because it
should be a permutation of {1,2,3,4}.


To fix this issue, I would like to replace the function with:

/*
 * The function permute() randomly reorders the array arr[begin..end-1].
 */
static void permute(int *arr, int begin, int end)
{
    int i, j, tmp, len;

    len = end-begin;
    for(i = begin; i < end; i++)
    {
        j = begin+RANDOM()%len;

        tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

void get_search_arr(int *search_arr)
{
    int i;

    for(i = 0; i < SIZEOFFREE; i++)
    {
        search_arr[i] = i;
    }

    permute(search_arr, 1, SIZEOFFREE1+1);
    permute(search_arr, SIZEOFFREE1+1, SIZEOFFREE2+1);
    permute(search_arr, SIZEOFFREE2+1, SIZEOFFREE);
}


I think this new function is correct, easier to understand (it it smaller
and does not contain a lot hardcoded values), and is a little bit faster.


Note: The old function basically did something like

    permute(search_arr, 0, 1);   /* a */
    permute(search_arr, 1, 5);   /* b */
    permute(search_arr, 5, 9);   /* c */
    permute(search_arr, 9, 13);  /* d */
    permute(search_arr, 13, 21); /* e */
    permute(search_arr, 21, 29); /* F */
    permute(search_arr, 29, 37); /* g */
    permute(search_arr, 37, 49); /* h */

The freearr_x/y[] is:

    46 47 48 25 26 27 28
    45 23 24  9 10 11 29
    44 22  8  1  2 12 30
    43 21  7  0  3 13 31
    42 20  6  5  4 14 32
    41 19 18 17 16 15 33
    40 39 38 37 36 35 34

That is, the old function permutes as follows: (For each letter, the
positions are permuted.)

    h--h--h /F--F--F--F
    h  F--F/ d--d--d  g
    h  F  c  b--b  d  g
    h  F  c  a  b  e  g
    h  e  c--c  b  e  g
    h  e--e--e--e--e  g
    h--h--h--h  g--g--g

I could not find out the reason for these range borderss. Especially the
permutation for "F" is suspicious to me because it covers more than one
distance. Because of this my function simply permutes the positions
within each distance.

_______________________________________________
crossfire-devel mailing list
     
     crossfire-devel at lists.real-time.com
     
     
     https://mailman.real-time.com/mailman/listinfo/crossfire-devel