Bitwise shifting in EVM

[axic]

Is there any reason bitwise shifting was omitted from the EVM? Other bitwise operators are present.

In the past few months in Solidity it was a challenge to deal with arbitrary data and even efficiently implement something like hex to string or string to hex conversion.

Rudimentary shift alternatives are: a * (2 ** b) for shl and a / (2 ** b) for shr. One can use SIGNEXTEND to implement arithmetic right shift. (Using this to implement shift in Solidity: ethereum/solidity#527. Having a progression path to native shifting would make sense.)

While there are some alternative opcodes in certain cases (such as the BYTE and MSTORE8) I still think it would be a very useful addition to have native logical shifts (SHL and SHR). I am not fully convinced about the necessity of arithmetic right shift (SAR). Additionally bit rotation (ROR/ROL) might make sense.

@chfast @gcolvin I know you were discussing the option to have 64 bit arithmetic. Did you think about including bit shifting?

[VoR0220]

So now that I have some understanding for this...it makes sense why this was left out. Basically bit shifting could be implemented natively by the underlying client....they would simply take in the opcodes that acted like shifting and then use bit shifting underneath....so this kind of makes sense to leave out now...I think.

[gcolvin]

@axic I agree that shifting and rotation should be included, as they are basic arithmetic that can be performed much more efficiently as one operation by the VM than as a sequence of operations by the programmer.

[ebuchman]

this is especially true since the solidity ABI uses bit (well, byte) shifting, and every contract does this, but instead of being implemented as a shift, its a big int division by a massive number. shifts could be a major performance boon. it's a shame they've been left out. that said, maybe this is something the JITs can just do for us instead of fussing with new opcodes.

[ebuchman]

this is potentially related to #101 , tho native contracts seem like overkill when all you're trying to do is shift bits/bytes

[axic]

@VoR0220:

Basically bit shifting could be implemented natively by the underlying client....they would simply take in the opcodes that acted like shifting and then use bit shifting underneath....

Either static analysis is done or specific patterns need to be following for it to pick up. I don't think it is a good reason for leaving it out.

[chfast]

I think the conclusion is that shifts in form of a * (2 ** b) are unnecessary expensive and perform badly if the b is not a constant.

Providing there is strong interest in implementing some hash/crypto functions in EVM, I'm for including shift ops at some point.

[axic]

Proposal

0xc: SHL - logical left shift
0xd: SHR - logical right shift

Arithmetic (SAR) right shift can be achieved as a combination of SHR and SIGNEXTEND. Not, because SIGNEXTEND needs the offset of the sign bit.

Both shift operators take two stack elements, with the top element being the index to shift with. Both take stack elements are considered unsigned.

It is aligned with the rest of EVM in case of overflows: they are ignored and the result is truncated.

[axic]

I'm still unsure about including rotation opcodes. They can be very useful when implementing hash functions in EVM (such as SHA* and BLAKE).

[axic]

Replaced by #145.