Jump to content
  • Advertisement
Sign in to follow this  
FordPerfect

C++ Well-defined shifts

This topic is 497 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

This is basically a repost of http://www.gamedev.ru/flame/forum/?id=228402 .

 

As many programmers know, there is quite a lot of undefined behavior in C++ shifts.

So let's make our own ones!

Since the task is relatively small, it seems worth doing WELL, to save everyone using it a bit of time.

Motivation:

0. Well-defined semantics rulez.

1. For many cases (e. g. shifts by a constant) the result should be exactly the same as built-in shifts, with no performance penalty.

2. For many other cases performance does not matter.

3. If old code (with built-in shifts) worked, then, presumably the shift amount was always in the allowed range, and the branch in the new code would have essentially 100% prediction.

4. For the cases, where shifts are variable, and performance matters so much, that even predicted branches make difference (e. g. coding/decoding) - well there built-in shifts still remain. Hopefully, it is <5% of code.

My present attempt:

// This software is in the public domain. Where that dedication is not
// recognized, you are granted a perpetual, irrevocable license to copy
// and modify this file as you see fit.

template<typename L,typename R>
L shl(L value,R amount)
{
    if(amount>=R(sizeof(L))*8) return L(0);
    if(amount<R(0))
    {
        if(amount<=-R(sizeof(L))*8)
        {
            if(value<L(0)) return L(-1);
            return L(0);
        }
        return value>>(-amount);
    }
    return value<<amount;
}

template<typename L,typename R>
L shr(L value,R amount)
{
    if(amount>=R(sizeof(L))*8)
    {
        if(value<L(0)) return L(-1);
        return L(0);
    }
    if(amount<R(0))
    {
        if(amount<=-R(sizeof(L))*8) return L(0);
        return value<<(-amount);
    }
    return value>>amount;
}

I subject it to scrutiny of the community.

Basically, pretty please, check that all corner cases actually work.

Quite a bit of trickery went into the writing this code, to satisfy the rules of C++. As you can imagine, there are A LOT of corner cases, and I am not confident everithing works correctly.

 

Some useful links:

http://www.gamedev.ru/flame/forum/?id=228402 - original post (in Russian)

http://en.cppreference.com/w/cpp/language/operator_arithmetic - for language-lawering

http://en.cppreference.com/w/cpp/language/implicit_cast#Integral_promotion - likewise

http://rextester.com - for testing snippets

http://gcc.godbolt.org - for testing assembly output

 

P. S. Does anyone see a nice way to do it in C? Templates are C11, macros evaluate arguments multiple times, and lots of functions are ugly.

I'm asking because it seems like a good candidate for inclusion into stb_* (right along with stb_divide.h), and maybe if we ask really nicely, Sean Barrett can do just that.

Share this post


Link to post
Share on other sites
Advertisement

I'm not sure what you're on about.  This seems unnecessary.

They're undefined if you have a negative number of bits or if the shift is larger than the number of bits.  But you should never be in either situation.  That is a bug in the code, a bug in the logic. Writing code that solves a bug by wrapping it inside a function that hides the bug is nonsense.  That is a "Don't Do That" bug, the problem is that the programmer did something they shouldn't.

It also gets into trouble if you attempt to shift a signed negative value. Since the language does not specify exactly how numbers are encoded it would be nonsensical to enforce what happens on those situations.  That's another case of "Don't Do That'.  

None of those are particularly problematic. Programmers shouldn't be doing that in the first place, and if they do, that's a bug that should be caught through testing.

As for your performance concerns, every CPU that matters implements a bit shift opcode. Every compiler I'm aware of either simplifies the expression to something even faster, or it generates the CPU-specific opcode.  It is hard to get much faster, especially compared to all your branching code.

Share this post


Link to post
Share on other sites

Bugfix: to prevent UB for left-shifting negative numbers

//return value<<amount;
return L((typename std::make_unsigned<L>::type)(value)<<amount);

//return value<<(-amount);
return L((typename std::make_unsigned<L>::type)(value)<<(-amount));

This requires C++11.

Share this post


Link to post
Share on other sites

So you impose a cost to ALL code using bitwise shift because someone once wrote a bug?

Most functions have rules about their use, such as not passing null values as parameters, or ensuring elements are within a legal range.  This is no different. Shift operations have a mandatory range between zero and the number of bits of the type.  

Passing a negative shift distance is a bad parameter, exactly the same as if the programmer had passed an invalid object address or dereferenced a null pointer.  Don't do that in the first place, then you don't need to write special code to handle the buggy code.

Share this post


Link to post
Share on other sites

I could see adding some asserts, do the shifts assert?  I can't remember the last time I passed a bad parameter to a shift.

Share this post


Link to post
Share on other sites

I for one think this is a good idea. I would like to be able to shift something to the left some number of times as a way to divide it by a power of 2. If I shift by too much, the result should be 0 (at least for unsigned integer types).

The current C++ rules are written so shifts can be translated to machine-code shifts, and those have semantics that made the hardware easy to implement (usually several decades ago). There are natural semantics for shifts with any number of bits, and it would be good to have them available.

A similar "feature" of C++ that bothers me even more is the rules on integer modulo and division when it comes to signs. a % b should always return a number in the interval [0, abs(b)), and a / b should round down. The fact that 7 % 10 and -3 % 10 can be different boggles the mind. The whole point of arithmetic modulo 10 is that you should not see any difference between numbers that are a multiple of 10 apart. Just ask your mathematician friends.

 

Share this post


Link to post
Share on other sites
4 hours ago, frob said:

It also gets into trouble if you attempt to shift a signed negative value. Since the language does not specify exactly how numbers are encoded it would be nonsensical to enforce what happens on those situations.  That's another case of "Don't Do That'.  

In practice, on every compiler that matters to gamedev, shifting an unsigned integer to the right is a zero-fill right shift (logical shift), and shifting a signed integer to the right is a sign-extending right shift (arithmetic shift).

The standard doesn't define this because the language needs to be able to run on a soviet toaster as well as a PC... but in practice, this is the defacto definition of what signed and unsigned shifts should do. Every sane CPU architecture has instructions for both arithmetic and logical shift, and every sane C/C++ compiler will map unsigned to logical and signed to arithmetic. You'll likely find code at every gamedev company that relies on this definition, even though it's not guaranteed by the standard, e.g.

#define MAKE_MASK_64(StartBit, NumBits) \
	((u64) ((s64) 0x8000000000000000i64 >> (NumBits-1)) >> (64-NumBits-StartBit))

The cautious projects will include a static assertion that verifies that the compiler is doing the defacto standard behaviour ;)

Share this post


Link to post
Share on other sites
41 minutes ago, Hodgman said:

 the language needs to be able to run on a soviet toaster as well as a PC

Soviet toasters probably ran 8086 knockoffs, ironically.

Edited by TheChubu

Share this post


Link to post
Share on other sites
2 hours ago, alvaro said:

The fact that 7 % 10 and -3 % 10 can be different boggles the mind.

When either value is negative the resulting sign is implementation defined. 

It is the polite way of saying: "The operation does whatever your hardware does on that opcode."

Various chipsets handle it differently, and the standards committee tries very hard to prevent systems from being slow in the name of uniformity.  Java tried doing that, and it backfired spectacularly. It took until Java 6 for them to work most of them out, but during the early years many operations, especially trickier floating point operations, were incredibly slow as they were processed in software rather than using the slightly different hardware operations.

In practicality it is not an issue.  In our field you typically have either a single platform, or you have up to four platforms with known specifications, and that's it. You don't need to write code for every conceivable platform, nor have thousands of variations for every compiler and chipset and operating system throughout history.

Share this post


Link to post
Share on other sites
14 hours ago, frob said:

 

I'm not sure what you're on about.

 

The core difference seems to be that you consider shift amount outside of [0; width) nonsensical. I do not.

Not necessarily trying to convince you, just hope this helps to explain where I'm coming from.

This (to me) is about providing sensible, uniform semantics.

It seems pretty obvious to me that the Right Thing(TM) semantics-wise (ignoring performance) is for 20<<100 to be 0, and for 20<<-2 to be the same as 20>>2, namely 5.

It is also looks like it makes more sense mathematically.

alvaro seems to agree.

At very least, when shifting bunch of numbers it would be nice not to special-case full-width shifts.

Also sometimes it does make sense to write a<<(b-c) with the sign of (b-c) not known at compile-time.

14 hours ago, frob said:

Most functions have rules about their use, such as not passing null values as parameters, or ensuring elements are within a legal range.  This is no different. Shift operations have a mandatory range between zero and the number of bits of the type.  

Yes, this is the semantics of shift operations in C++ Standard. It does not necessarily follows that this is a good idea for C++. It SURELY does not follow that this is a good idea for my own bit-shifting function.

Also, ambiguous wording: "number of bits of the type" is actually excluded from range.

14 hours ago, frob said:

So you impose a cost to ALL code using bitwise shift because someone once wrote a bug?

I'm not advocating changing all shifts into functions calls, just considering it.

Suppose you have two functions to do some things: one is robust, and another is fast, but works only for restricted inputs.

You can usually do one of the the following:

1. Use robust one everywhere in code, and change it to fast, where it causes performance problems.

2. Use fast one everywhere in code, and change it to robust, where it causes correctness problems.

It does not seem too outrageous to prefer option 1.

Even if you go with the option 2, the shl/shr functions provide the robust functionality mentioned.

Also, for shifts by constant the cost should be exactly zero, assuming compiler is allowed to optimize at all.

8 hours ago, frob said:

When either value is negative the resulting sign is implementation defined. 

Not since C99 and C++11 respectively. It is well-defined now.

So

8 hours ago, frob said:

In practicality it is not an issue.

it (result being implementation-defined) is indeed not an issue. Result being well-defined (to the value it is) is.

10 hours ago, alvaro said:

A similar "feature" of C++ that bothers me even more is the rules on integer modulo and division when it comes to signs. a % b should always return a number in the interval [0, abs(b)), and a / b should round down. The fact that 7 % 10 and -3 % 10 can be different boggles the mind. The whole point of arithmetic modulo 10 is that you should not see any difference between numbers that are a multiple of 10 apart. Just ask your mathematician friends.

Yes, C++ lack of Euclidean division is similar (I mention stb_divide.h in the opening post). However:

1. Division is actually well-defined (sans INT_MIN/-1), even if the definition is suboptimal. So it just produces garbage value, whereas UB nukes entire codepaths. I slightly prefer the former, I suppose.

2. Non-Euclidean division seems to be problematic more often, than restricted shifts.

3. Performance considerations are probably no concern, since the division itself is so slow.

10 hours ago, Hodgman said:

In practice, on every compiler that matters to gamedev, shifting an unsigned integer to the right is a zero-fill right shift (logical shift), and shifting a signed integer to the right is a sign-extending right shift (arithmetic shift).

In fact, in the code above I rely on implementation-defined behavior:

1. Signed right-shift sign-extends.

2. Unsigned->signed conversion produces the value with the same bitwise representation.

Both seem to be rock-solid in practice.

Edited by FordPerfect

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!