Do not understand why I am getting these warnings ...

[Bob Langelaan]

The code snippet:

unsigned long long n = 10000;

//Create vector of size n and initialize to 1 to n
vector<unsigned long long> v(n);
for (unsigned long long i = 1; i < v.size(); ++i)
{
v[i] = i+1;
}

//Shuffle vector
unsigned long long val;
unsigned long long temp;
for (unsigned long long j = 0; j < v.size(); ++j)
{
val = rand() % v.size();
temp = v[j];
v[j] = v[val];
v[val] = temp;
}

I get the following warning for all 4 statements in the last for loop:

warning C4244: 'argument': conversion from 'unsigned __int64' to 'unsigned int', possible loss of data

I do not understand. Aren't all of the operands unsigned long long?

[Ian Collins]

The warning as at which line?

--
Ian

[Bob Langelaan]

All 4 lines in the lower for loop. Some other lines as well.

[Christopher J. Pisz]

What type is i?
What type does std:vector::size return?
What is size_type when you compile for 32 bits?

What type is val?
What type does rand() return?
What type does std::vector::size return?
What is size_type when you compile for 32 bits?

You can static_cast away the problem when you are sure a variable on one
side will always fall withing the range of the variable on the other. If
you aren't sure, check first, handle error if not, and then static_cast.

[Alf P. Steinbach]

On 29.11.2016 04:55, Bob Langelaan wrote:
> unsigned long long n = 10000;
>
> //Create vector of size n and initialize to 1 to n
> vector<unsigned long long> v(n);
> for (unsigned long long i = 1; i < v.size(); ++i)
> {
> v[i] = i+1;
> }
>
> //Shuffle vector
> unsigned long long val;
> unsigned long long temp;
> for (unsigned long long j = 0; j < v.size(); ++j)
> {
> val = rand() % v.size();
> temp = v[j];
> v[j] = v[val];
> v[val] = temp;
> }

You're compiling this with 32-bit Visual C++, or compatible compiler,
where `size_t` is a 32-bit unsigned type.

The size argument of `vector` constructor, as well as the index argument
of `vector::operator[]`, are `size_t`.

So your `unsigned long long` (which the standard requires to be at least
a 64-bit type) is converted down to `size_t`, and the compiler informs
you that that conversion can be lossy, can lose information.

• • •

The fix is not simple, except to use the 64-bit compiler.

Here's the program coded up with more sensible types:

[code]
#include <stddef.h> // std::ptrdiff_t
#include <algorithm> // std::swap
#include <vector> // std::vector
#include <iostream> // std::(cout, endl)
using namespace std;

using Size = ptrdiff_t;

template< class Container >
auto n_items_of( Container const& c )
-> Size
{ return c.size(); }

auto main()
-> int
{
int const n = 10000;

//Create vector of size n and initialize to 1 to n

vector<int> v{ n };
for( int i = 1; i < n_items_of( v ); ++i )
{
v[i] = i;
}

//Shuffle vector
for( int i = 0; i < n_items_of( v ); ++i )
{
int const j = rand() % v.size();
swap( v[i], v[j] );
}
}
[/code]

In general, just use `int`, the natural integer type for the platform,
unless there is a very good, compelling reason to use some other type.

• • •

The `n_items_of` function here avoids warnings about comparison of
signed/unsigned, and in other contexts avoids unintended wrap-around
conversions of number values in expressions that use collection sizes.

An overload of `n_items_of` for raw arrays can look like this:

template< class Item, size_t n >
auto n_items_of( Item (&)[n] )
-> Size
{ return n; }

(In C++17 this can be expressed in terms of `std::size`.)

The template parameter is `size_t` instead of `ptrdiff_t` in order to
support compilation with g++.


Cheers & hth.,

- Alf

[Alf P. Steinbach]

On 29.11.2016 06:53, Alf P. Steinbach wrote:
>
> //Create vector of size n and initialize to 1 to n
> vector<int> v{ n };
> for( int i = 1; i < n_items_of( v ); ++i )
> {
> v[i] = i;
> }

Sorry, I should have replaced your loop here with std::iota, <url:
http://en.cppreference.com/w/cpp/algorithm/iota>.

Cheers!,

- Alf

[mark]

Your code comes with security issues built in. Containers with more than
INT_MAX elements aren't unheard of these days. In fact, I can allocate a
vector<char> with more than INT_MAX elements with both 32-bit Linux and
Windows programs.

Your size_t -> ptrdiff_t conversion can overflow and you end up with a
negative size value (you can get integer overflows and/or buffer
overflows in downstream code on 8/16/32-bit platforms).

Your int loop index can overflow if the container size is too large.

For people compiling with warnings:

clang -Wall -Wconversion -c test.cpp
test.cpp:23:11: warning: implicit conversion changes signedness: 'int'
to 'size_type' (aka 'unsigned long long')
[-Wsign-conversion]
v[i] = i;
~ ^
test.cpp:29:30: warning: implicit conversion changes signedness:
'unsigned long long' to 'const int' [-Wsign-conversion]

int const j = rand() % v.size();

~ ~~~~~~~^~~~~~~~~~
test.cpp:29:23: warning: implicit conversion changes signedness: 'int'
to 'unsigned long long' [-Wsign-conversion]

int const j = rand() % v.size();

^~~~~~ ~
test.cpp:30:17: warning: implicit conversion changes signedness: 'int'
to 'size_type' (aka 'unsigned long long')
[-Wsign-conversion]

swap( v[i], v[j] );

~ ^
test.cpp:30:23: warning: implicit conversion changes signedness: 'const
int' to 'size_type' (aka 'unsigned long long')
[-Wsign-conversion]

swap( v[i], v[j] );

~ ^
test.cpp:12:12: warning: implicit conversion changes signedness:
'size_type' (aka 'unsigned long long') to 'Size'
(aka 'long long') [-Wsign-conversion]
{ return c.size(); }
~~~~~~ ~~^~~~~~
test.cpp:21:25: note: in instantiation of function template specialization
'n_items_of<std::vector<int, std::allocator<int> > >' requested here

for( int i = 1; i < n_items_of( v ); ++i )

^
6 warnings generated.

[Öö Tiib]

Sure, but conforming INT_MAX can't be smaller than size limit 10000 that
is explicitly given in the code.

[Alf P. Steinbach]

False.

> Containers with more than INT_MAX elements aren't unheard of these days.

True.

> In fact, I can allocate a
> vector<char> with more than INT_MAX elements with both 32-bit Linux and
> Windows programs.

True.

> Your size_t -> ptrdiff_t conversion can overflow

It can overflow on a 16-bit system.

That means that the /language/ does not support what one tries to
achieve on such 16-bit system, since `ptrdiff_t` is the type used for
pointer differences -- hence the name.

I am sure that you don't understand this, since you continue to say...

> and you end up with a
> negative size value (you can get integer overflows and/or buffer
> overflows in downstream code on 8/16/32-bit platforms).

False.

> Your int loop index can overflow if the container size is too large.

False, it's not too large.

Don't choose types for some extraordinary situation that's very
different than the ones you need to handle.

For example, don't drive a tractor to work just because you can imagine
that if you were doing something very different, like farm work, you'd
need that tractor.

I think you'll agree that someone driving a tractor to work, for that
reason, is behaving like an idiot.

> For people compiling with warnings:
>
> clang -Wall -Wconversion -c test.cpp
> test.cpp:23:11: warning: implicit conversion changes signedness: 'int'
> to 'size_type' (aka 'unsigned long long')
> [-Wsign-conversion]
> v[i] = i;

I didn't know that g++ supported that silly-warning.

If you enable it then you truly deserve the meaningless avalanche of
warnings.

[mark]

It's not my fault that C++ is one big steaming pile of poo with regards
to integers. Let's try a 32-bit platform (I'm too lazy to get out a
16-bit one), Linux i686, GCC 4.9.2:

-------------------------------------------------------------------
#include <vector>
#include <limits>
#include <iostream>
#include <stdint.h>

using namespace std;

using Size = ptrdiff_t;

template< class Container >
auto n_items_of( Container const& c )
-> Size
{ return c.size(); }

int main() {
std::vector<char> v;
v.resize(size_t(std::numeric_limits<int>::max()) + 10);
std::cout << "size(): " << v.size() << std::endl;
std::cout << "n_items_of (s): " << (int64_t) n_items_of(v) <<
std::endl;
std::cout << "n_items_of (u): " << (uint64_t) n_items_of(v) <<
std::endl;
}
---------------------------------------------------------------------
size(): 2147483657
n_items_of (s): -2147483639
n_items_of (u): 18446744071562067977

I have seen exactly this kind of bug in production code (e.g. with
people using 64-bit ints for large file access).

>> and you end up with a
>> negative size value (you can get integer overflows and/or buffer
>> overflows in downstream code on 8/16/32-bit platforms).
>
> False.

See above.

>> Your int loop index can overflow if the container size is too large.
>
> False, it's not too large.

It is not too large with your hard-coded size. It can easily be too
large if vectors are passed around. 64-bit platform to avoid the size_t
-> ptrdiff_t overflow:

--------------------------------------------------------------------
#include <vector>
#include <limits>
#include <iostream>

using namespace std;

using Size = ptrdiff_t;

template< class Container >
auto n_items_of( Container const& c )
-> Size
{ return c.size(); }

int main() {
std::vector<char> v;
v.resize(size_t(std::numeric_limits<int>::max()) + 10);
for(int i = 0; i < n_items_of(v); i++) ;
}

--------------------------------------------------------------------
g++ -Wall -O2 -std=c++14 test_huge_vector_undef_behavior.cpp
test_huge_vector_undef_behavior.cpp: In function ‘int main()’:
test_huge_vector_undef_behavior.cpp:17:5: warning: iteration 2147483647u
invokes undefined behavior [-Waggressive-loop-optimizations]
for(int i = 0; i < n_items_of(v); i++) ;
^
test_huge_vector_undef_behavior.cpp:17:5: note: containing loop

In this case, GCC "optimizes" this into an endless loop. It would easy
to transform this code to corrupt the entire memory after v.

> Don't choose types for some extraordinary situation that's very
> different than the ones you need to handle.

So how do you deal with the potential overflows above? Do you check the
container size each time you insert something that it's not larger than
INT_MAX?

> For example, don't drive a tractor to work just because you can imagine
> that if you were doing something very different, like farm work, you'd
> need that tractor.
>
> I think you'll agree that someone driving a tractor to work, for that
> reason, is behaving like an idiot.

Advice like yours directly contributes to the endless flow of security
vulnerabilities in C and C++ programs.

>> For people compiling with warnings:
>>
>> clang -Wall -Wconversion -c test.cpp
>> test.cpp:23:11: warning: implicit conversion changes signedness: 'int'
>> to 'size_type' (aka 'unsigned long long')
>> [-Wsign-conversion]
>> v[i] = i;
>
> I didn't know that g++ supported that silly-warning.
>
> If you enable it then you truly deserve the meaningless avalanche of
> warnings.

As it turns out those warnings are entirely justified. Doing anything
with mixed sizes or signedness is one giant minefield.

[mark]

What's your point? I was responding to the generic advice "In general,
just use `int`, the natural integer type for the platform". That's bound
to lead to overflows on a 64-bit platform, since everything else uses
size_t (and ptrdiff_t will be a larger type as well).

There is a nice template function thrown in to silence valid compiler
warnings about this.

[Alf P. Steinbach]

As mentioned, the /language/ doesn't support this. `ptrdiff_t` is the
type of a pointer difference expression, any pointer difference
expression. And it overflows for this case, which means that you need to
treat that exceptionally large array very specially: you need to avoid
handing it to code with any possible pointer differences.

In other words, you're out of bounds of the language.

It is the single example where overflow occurs, and it's not relevant since

* It's not supported by the language.

* It does not occur in practice.

* It's not even supported by Windows (although Windows can be configured
to support it).

Re the last point, a 32-bit Windows application, without special
configuration of Windows, only has 2GB memory available to it.

Since you're apparently unaware of this, thinking that the above example
would not only be generally safe if it used size_t, but thinking that
allocating over half of available address space to a byte array, in
32-bit code, has occurred at least once in the annals of software
development, you prove that you're absolutely clueless.

As I suspected.

> I have seen exactly this kind of bug in production code (e.g. with
> people using 64-bit ints for large file access).

No doubt you have. It's so common allocating > 2G byte arrays in 32-bit
code.

Laughing out loud. :)


Cheers!, & hth.,

- Alf

[Mr Flibble]

One should not use 'int' at all in a C++ program (except as return type
of main()) at it is unsafe and non-portable. One should used the sized
integer typedefs such as int32_t instead.

/Flibble

[Richard]

[Please do not mail me a copy of your followup]

mark <ma...@invalid.invalid> spake the secret code
<o1koc7$qb8$1...@dont-email.me> thusly:

>It's not my fault that C++ is one big steaming pile of poo with regards
>to integers.

Pray tell, what languages are addressing this in a superior fashion?
--
"The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline>
The Terminals Wiki <http://terminals-wiki.org>
The Computer Graphics Museum <http://computergraphicsmuseum.org>
Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com>

[mark]

The language is broken. ptrdiff_t doesn't need to support arbitrary
pointer differences, 5.7 [expr.add]:
<<<
When two pointers to elements of the same array object are subtracted,
the result is the difference of the subscripts of the two array
elements. The type of the result is an implementation-defined signed
integral type; this type shall be the same type that is defined as
std::ptrdiff_t in the <cstddef> header (18.2). As with any other
arithmetic overflow, if the result does not fit in the space provided,
the behavior is undefined.
>>>

Your n_items_of() has undefined behavior.

From what I can tell, the only restriction on ptrdiff_t is that it is
signed. But apparently, per C and C++ standards, it could theoretically
be int8_t and it could be a smaller type than size_t.

> And it overflows for this case, which means that you need to
> treat that exceptionally large array very specially: you need to avoid
> handing it to code with any possible pointer differences.

How do you know in advance how large the array is?

> In other words, you're out of bounds of the language.

???

> It is the single example where overflow occurs, and it's not relevant
since
>
> * It's not supported by the language.

The language supports an array size that's larger than ptrdiff_t. Why
don't you point where standard disallows it, instead of throwing around
insults?

> * It does not occur in practice.

It does occur in practice.

> * It's not even supported by Windows (although Windows can be configured
> to support it).
>
> Re the last point, a 32-bit Windows application, without special
> configuration of Windows, only has 2GB memory available to it.

32-bit programs running on x64 Windows get 4GB of address space without
any special configuration. They just need to be compiled with the
"largeaddressaware" flag.

> Since you're apparently unaware of this, thinking that the above example
> would not only be generally safe if it used size_t, but thinking that
> allocating over half of available address space to a byte array, in
> 32-bit code, has occurred at least once in the annals of software
> development, you prove that you're absolutely clueless.
>
> As I suspected.
>
>> I have seen exactly this kind of bug in production code (e.g. with
>> people using 64-bit ints for large file access).
>
> No doubt you have. It's so common allocating > 2G byte arrays in 32-bit
> code.

Did I say it's common? It was a security bug. A large vector was
allocated shortly after program start, the size being calculated based
on untrusted input. Eventually, there was a comparison between the size
and an int variable leading to memory corruption.

The same kind of thing can happen on platforms where int == int16_t,
size_t == uint16_t, ptrdiff_t == int.

[Alf P. Steinbach]

On 29.11.2016 23:13, mark wrote:
> On 2016-11-29 21:55, Alf P. Steinbach wrote:
>>
>> As mentioned, the /language/ doesn't support this. `ptrdiff_t` is the
>> type of a pointer difference expression, any pointer difference
>> expression.
>
> The language is broken.

Wrong about this.

> ptrdiff_t doesn't need to support arbitrary pointer differences,

Right.

> 5.7 [expr.add]:
> <<<
> When two pointers to elements of the same array object are subtracted,
> the result is the difference of the subscripts of the two array
> elements. The type of the result is an implementation-defined signed
> integral type; this type shall be the same type that is defined as
> std::ptrdiff_t in the <cstddef> header (18.2). As with any other
> arithmetic overflow, if the result does not fit in the space provided,
> the behavior is undefined.

Good.

> Your n_items_of() has undefined behavior.

Wrong.

> From what I can tell, the only restriction on ptrdiff_t is that it is
> signed. But apparently, per C and C++ standards, it could theoretically
> be int8_t and it could be a smaller type than size_t.

No, it's required, by the C standard, to be at least 17 bits. And that's
not a typo, I didn't mean to write 16.

>> And it overflows for this case, which means that you need to
>> treat that exceptionally large array very specially: you need to avoid
>> handing it to code with any possible pointer differences.
>
> How do you know in advance how large the array is?

You don't, in general.

Just like you don't know exactly the required stack size.

And there are other problems with such (relative to 32-bit coding) large
arrays, including that an OS built on the idea that
we-at-Microsoft-make-software-that-know-better-than-you-what-you-need
such as Windows, can just start trashing, swapping to and back from
disk, with no way to configure off that behavior.

>> In other words, you're out of bounds of the language.
>
> ???

The core language doesn't support that array size in general, due to the
fact that the type of a pointer difference is `ptrdiff_t`.

The standard library does not support it, since it also defaults its
difference types, e.g. for `std::distance`, to `ptrdiff_t`.

>> It is the single example where overflow occurs, and it's not relevant
> since
>>
>> * It's not supported by the language.
>
> The language supports an array size that's larger than ptrdiff_t. Why
> don't you point where standard disallows it,

You just did, above.

It's not disallowed. It's just /partly/ supported. Which means it's not
generally or fully supported.

You have to be very careful what you do with it, lest things go haywire.

> instead of throwing around insults?

Oh, sorry about that.

We'll see where this goes.

>> * It does not occur in practice.
>
> It does occur in practice.

Fire those devs.

>> * It's not even supported by Windows (although Windows can be configured
>> to support it).
>>
>> Re the last point, a 32-bit Windows application, without special
>> configuration of Windows, only has 2GB memory available to it.
>
> 32-bit programs running on x64 Windows get 4GB of address space without
> any special configuration. They just need to be compiled with the
> "largeaddressaware" flag.

Well, there's more to it than that, including bugs in the Windows API
(i.e., be careful with axe, Eugene), but the main sub-point is that this
example, the single one of its kind, does not occur naturally.

That's probably why the language design, the limits of pointer
arithmetic, simply assumes that it doesn't occur.


[snip]

>>> I have seen exactly this kind of bug in production code (e.g. with
>>> people using 64-bit ints for large file access).
>>
>> No doubt you have. It's so common allocating > 2G byte arrays in 32-bit
>> code.
>
> Did I say it's common? It was a security bug. A large vector was
> allocated shortly after program start, the size being calculated based
> on untrusted input. Eventually, there was a comparison between the size
> and an int variable leading to memory corruption.

A bug in someone's program means that the function I presented was
unsafe, for they could in theory have used that function in their buggy
code, yes?

No. It doesn't work that way.

A function isn't unsafe because it's possible for someone's buggy code
to give it arguments outside its preconditions.

> The same kind of thing can happen on platforms where int == int16_t,
> size_t == uint16_t, ptrdiff_t == int.

No, `ptrdiff_t` is not allowed to be 16 bits or less.

In a conforming implementation.

Because the C standard requires its limits to be equal or greater in
magnitude to −65535 (lower limit) and +65535 (upper limit).

[Öö Tiib]

My point was only that there are no immediate reasons to use something
else but 'int' for integers in range 0 ... 10000.
Sure, if we need to save or to fix storage then 'int16_t' or even 14 bits
may make better sense. Usage of 'long long' for maximum extending
in future sounds like preliminary pessimization on any case.

>
> There is a nice template function thrown in to silence valid compiler
> warnings about this.

You yourself use claims like "the language is broken" and even
"steaming pile of poo" about how the various limits are handled
else thread. So the programmer has to take full awareness and
control about limits of *every* integer in his program and possible
undefined behaviors when those are breached. The warnings are
red herring and silly at best.

[Geoff]

On Tue, 29 Nov 2016 07:32:41 -0800 (PST), 嘱 Tiib <oot...@hot.ee>
wrote:

>> Your code comes with security issues built in. Containers with more than
>> INT_MAX elements aren't unheard of these days. In fact, I can allocate a
>> vector<char> with more than INT_MAX elements with both 32-bit Linux and
>> Windows programs.
>
>Sure, but conforming INT_MAX can't be smaller than size limit 10000 that
>is explicitly given in the code.

I got the distinct impression that this was an extract of some 'real
world' code and the value of n was assigned arbitrarily in the snippet
to 10000 and the real code might use something larger. It is an error
to assume that n can _never_ be larger than INT_MAX just from the
presented code.

[Öö Tiib]

On Wednesday, 30 November 2016 05:41:39 UTC+2, Geoff wrote:
> On Tue, 29 Nov 2016 07:32:41 -0800 (PST), Öö Tiib <oot...@hot.ee>

It is an error to assume that *anything* else in C++ program than
programmer keeps any limits under control.

From presented code I assumed that vector size can _never_ be larger
than 10000 since so it was written. If 10000 was just "arbitrary"
then sure limit is 32767, since the code used 'rand' for indexing and
RAND_MAX is 0x7FFF on popular platforms:
https://msdn.microsoft.com/en-us/library/2dfe3bzd.aspx
Neither number can be bigger than INT_MAX.

What software it is where just any container may reach bigger size
than INT_MAX out of blue without programmer knowing it? Yuck. I never
assume that we discuss such software unless specially said.

[Ike Naar]

On 2016-11-29, Bob Langelaan <bobl...@gmail.com> wrote:
> The code snippet:
>
> unsigned long long n = 10000;
>
> //Create vector of size n and initialize to 1 to n
> vector<unsigned long long> v(n);
> for (unsigned long long i = 1; i < v.size(); ++i)

This loop does not initialize v[0], but v[0] is used in the next loop.

[Ike Naar]

On 2016-11-29, Bob Langelaan <bobl...@gmail.com> wrote:

> //Shuffle vector
> unsigned long long val;
> unsigned long long temp;
> for (unsigned long long j = 0; j < v.size(); ++j)
> {
> val = rand() % v.size();
> temp = v[j];
> v[j] = v[val];
> v[val] = temp;
> }

There is a standard library function for that:

#include <algorithm>
std::random_shuffle(v.begin(), v.end());

[Öö Tiib]

On Monday, 5 December 2016 09:53:01 UTC+2, Ike Naar wrote:
> On 2016-11-29, Bob Langelaan <bobl...@gmail.com> wrote:
> > The code snippet:
> >
> > unsigned long long n = 10000;
> >
> > //Create vector of size n and initialize to 1 to n
> > vector<unsigned long long> v(n);
> > for (unsigned long long i = 1; i < v.size(); ++i)
>
> This loop does not initialize v[0], but v[0] is used in the next loop.

It feels worth to mention here that the vector elements are not
uninitialized before the loop. The loop modifies values of those.
So v[0] remains with value 0ULL as it was set by declaration of
v and usage of it in next loop is well-defined.

>
> > {
> > v[i] = i+1;
> > }

[asetof...@gmail.com]

On

#include <algorithm>
std::random_shuffle(v.begin(), v.end());

For me it is better
v.shuffle() and too

v.shuffle(indexBegin, indexEnd)

[Ike Naar]

According to the comment, Bob wanted to initialize the elements of
the array to [1..n], but if the first element of the vector is not
set to 1, the initial value of the array will be [0, 2..n] instead
of [1..n].