3

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: enter image description here

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.

  • 2
    Perhaps you can find this paper interesting arxiv.org/pdf/1802.08660.pdf. It describe a formal small-step semantics for the Ethereum Virtual Machine. (N.B. It is not up-to-date, e.g., STATICCALL is missing). – Briomkez Nov 26 '18 at 18:02
  • Thanks for linking the paper. Some opcodes are written a bit different, which makes it clearer. Yet, I don't understand their SIGNEXTEND... – Donut Nov 27 '18 at 7:03
4

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! 😃

  • Thanks for your answer. Even it is a nice explanation for Two's Complement I still have no idea how the opcode works :) Do you think you could tell me what kind of values are pushed onto the stack regarding your example of -28? – Donut Nov 27 '18 at 6:55
0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.