# V108. Incorrect index type: 'foo[not a memsize-type]'. Use memsize type instead.

The analyzer found a possible error of indexing large arrays. The error may consist in the incorrect index determination.

The first example.

    extern char *longString;
    extern bool *isAlnum;
    ...
    unsigned i = 0;
    while (*longString) {
      isAlnum[i] = isalnum(*longString++);
      ++i;
    }

The given code is absolutely correct for the 32-bit platform where it is actually impossible to process arrays more than 'UINT_MAX' bytes (4Gb). On the 64-bit platform it is possible to process an array with the size more than 4 Gb that is sometimes very convenient. The error consists in the use of the variable of 'unsigned' type for indexing the array 'isAlnum'. When we fill the first 'UINT_MAX' of the items the variable 'i' overflow will occur and it will equal zero. As the result we'll begin to rewrite the array 'isAlnum' items which are situated in the beginning and some items will be left unassigned.

The correction is to replace the variable 'i' type with memsize type:

    ...
    size_t i = 0;
    while (*longString)
      isAlnum[i++] = isalnum(*longString++);

The second example.

    class Region {
      float *array;
      int Width, Height, Depth;
      float Region::GetCell(int x, int y, int z) const;
      ...
    };
    float Region::GetCell(int x, int y, int z) const {
      return array[x + y * Width + z * Width * Height];
    }

For computational modeling programs, the main memory size is an important source, and the possibility to use more than 4 Gb of memory on the 64-bit architecture increases computational possibilities greatly. In such programs, one-dimensional arrays are often used which are then dealt with as three-dimensional ones. There are functions for that which are similar to 'GetCell' that provide access to the necessary items. But the given code may deal correctly with arrays containing not more than 'INT_MAX' (2Gb) items. The reason is in the use of 32-bit 'int' types which participate in calculating the item index. If the number of items in the 'array' exceeds 'INT_MAX' (2 Gb), an overflow will occur and the index value will be calculated incorrectly. Programmers often make a mistake trying to correct the code in the following way:

    float Region::GetCell(int x, int y, int z) const {
      return array[static_cast<ptrdiff_t>(x) + y * Width +
                        z * Width * Height];
    }

They know that according to C++ rules the expression for calculating the index will have 'ptrdiff_t' type and because of it hope to avoid the overflow. Unfortunately, the overflow may occur inside the subexpression "y * Width or z * Width * Height" for to determine them 'int' type is still used.

If you want to correct the code without changing the types of the variables included into the expression you should convert each variable explicitly to memsize type:

    float Region::GetCell(int x, int y, int z) const {
      return array[ptrdiff_t(x) +
           ptrdiff_t(y) * ptrdiff_t(Width) +
           ptrdiff_t(z) * ptrdiff_t(Width) *
           ptrdiff_t(Height)];
    }

Another decision is to replace the variables types with memsize type:

    class Region {
      float *array;
      ptrdiff_t Width, Height, Depth;
      float
        Region::GetCell(ptrdiff_t x, ptrdiff_t y, ptrdiff_t z) const;
      ...
    };
    float Region::GetCell(ptrdiff_t x, ptrdiff_t y, ptrdiff_t z) const
    {
      return array[x + y * Width + z * Width * Height];
    }

If you use expressions which type is different from memsize type for indexing but are sure about the code correctness, you may use the explicit type conversion to suppress the analyzer's warning messages as follows:

    bool *Seconds;
    int min, sec;
    ...
    bool flag = Seconds[static_cast<size_t>(min * 60 + sec)];

If you suspect that the program may contain errors related to the incorrect explicit type conversion in expressions you may use the V201.

The analyzer tries as far as possible to understand when using non-memsize-type as the array's index is safe and keep from displaying warnings in such cases. As the result the analyzer's behaviour can sometimes seem strange. In such situations we ask you not to hurry and try to analyze the situation. Let's consider the following code:

    char Arr[] = { '0', '1', '2', '3', '4' };
    char *p = Arr + 2;
    cout << p[0u + 1] << endl;
    cout << p[0u - 1] << endl; //V108

This code works correctly in 32-bit mode and displays numbers 3 and 1. While testing this code we'll get a warning message only on one line with the expression "p[0u - 1]". And it's absolutely right. If you compile and launch this example in 64-bit mode you'll see that the value 3 will be displayed and after that a program crash will occur.

The error relates to that indexing of "p[0u - 1]" is incorrect on a 64-bit system and this is what analyzer warns about. According to C++ rules "0u - 1" expression will have unsigned type and equal 0xFFFFFFFFu. On a 32-bit architecture addition of an index with this number will be the same as substraction of 1. And on a 64-bit system 0xFFFFFFFFu value will be justly added to the index and memory will be addressed outside the array.

Of course indexing to arrays with the use of such types as int and unsigned is often safe. In this case analyzer's warnings may seem inappropriate. But you should keep in mind that such code still may be unsafe in case of its modernization for processing a different data set. The code with int and unsigned types can appear to be less efficient than it is possible on a 64-bit architecture.

If you are sure that indexation is correct you use "Suppression of false alarms" or use filters. You can use explicit type conversion in the code:

    for (int i = 0; i != n; ++i)
      Array[static_cast<ptrdiff_t>(i)] = 0;

Additional materials on this topic:

- 64-bit Lessons. Lesson 13. Pattern 5. Address arithmetic.