EVM SIGNEXTEND Opcode explanation

Question

I am trying to develop my own small EVM. That is a good way for me to learn more about the bytelevel. I hadn't had any problems with most of the instructions, but there are a few, which I just don't understand. SIGNEXTEND is one of it...

This is how the yellow paper describes the opcode:

I am trying to understand and figure out what is happening here and how this opcode works. I can't find a suitable example, nor a case where I might need this opcode.

Does anyone of you have any examples or an explanation for this opcode?

Thanks in advance.

Answer 1

Awesome! That is a great way to learn about the EVM. The answer may be verbose but it will be complete.

---

Two's Complement

Two's complement is a way to represent integers in binary. It enables us to easily and simply express signed integers (pasted for convenience; see source for more details):

Suppose we're working with 8 bit quantities (for simplicity's sake) and suppose we want to find how -28 would be expressed in two's complement notation. First we write out 28 in binary form.

00011100

Then we invert the digits. 0 becomes 1, 1 becomes 0.

11100011

Then we add 1.

11100100

That is how one would write -28 in 8 bit binary.

Extending Length of a Signed Integer

The concept of extending the length of an unsigned integer is rather trivial, for instance:

Take the number 01010101 for example. It is 1 byte in length.

Suppose that we want to represent it as 2 bytes. All we need to do is add eight 0's to our number like so: 00000000 01010101. Now it is 2 bytes.

However, the left most bit of a signed integer is the sign bit, we must take care to include the sign bit when extended a signed integer or we will alter it's original value. Let's say I wanted to extend the number we used above -28 in binary 11100100 that same way we extended the unsigned integer, like so:

00000000 11100100

Now our signed integer is no longer -28 but rather 228. Thus, we need a mechanism for extending the signed integer while preserving the sign bit. It's not that actually, all we need to do is instead of appending eight 0's, we'll append eight of the sign bits. In this case the sign bit is 1. So we'll append eight 1's 1 like so:

11111111 11100100

Now we have the value -28 expressed in two bytes instead of 1.

See source for more details.

So why??

Why is there a special opcode for this? This could get low level very fast but the process of extending the sign of an signed integer would need several opcodes. I'll briefly explain how I would do it without the SIGNEXTEND opcode:

1. Bit mask to get the left most bit
2. Check value of left most bit
3. Append the value of the left most bit

Because of this and because it is used frequently enough the developers must have thought it necessary to create a special opcode for it.

And why would we use it? This is an educated guess but one might use it to move data between different size registers as this article would suggest.

Let me know if you found this helpful! 😃

Answer 2

After talking with some guys at gitter/yellowpaper, I am now able to explain the SIGNEXTEND operation.

My mistake was to think that the LSB at μ_s[1] has position 0. The MSB has position 0 and the LSB has position 255.

Furthermore, the evm extends everything always to word size, no matter which size the values itself has.

Just an example to make this operation more clear:

Let's say we have -2, which is 1111 1110 in binary. Since everything has word size in the evm, the 0 in the binary string is at position 255. To get the signing bit, μ_s[0] has value 0. That means for t:

t = 256 - 8(0 + 1) = 256 - 8 = 248

Using this, it extends the 1111 1110 to 1111 1111 ... 1111 1110, where the 1111 1111 occurs 31 more times :)

Hope it helps.

Answer 3

how this opcode works

assume:
x = us[0]
y = us[1]

Let's figure out what y_i represents:

10101010101...111  
^               ^   
y_0             y_255

In general, the output will be the y, and modified some bits according to x:
if x > 31, output = y;
if x: 0, 1, .., 31;
then t = 248, 240, .., 0;
then output_(0~t) = y_t

for example: y = 0x0000000000000000000000000000000000000000000000000000000000000080
x = 0
t = 248, and y_248 = 1!
so output_(0~248) = 1
that is: 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff80

you can run this byte code in evm.codes: 7f000000000000000000000000000000000000000000000000000000000000008060000B

It can be seen that this opcode can fully realize bit expansion, by specifying x to determine which effective bits of y are (even if y always has 256 bits in the stack), for example, the y in example is 8 bits, which can be extended to 256 bits.

I can't find a suitable example, nor a case where I might need this opcode.

SIGNEXTEND does appear rarely. Because SIGNEXTEND is used for complement code, and the complement code is to use addition instead of subtraction. For example, for 4 bit numbers, y = x + a mod 16, subtracting 1 is equal to adding 15, which is why the complement code of -1 is equal to 1111, standing for 15.

But in evm, we have SUB opcode, so SIGNEXTEND is rarely needed