pallet_revive/vm/evm/instructions/
i256.rs

1// This file is part of Substrate.
2
3// Copyright (C) Parity Technologies (UK) Ltd.
4// SPDX-License-Identifier: Apache-2.0
5
6// Licensed under the Apache License, Version 2.0 (the "License");
7// you may not use this file except in compliance with the License.
8// You may obtain a copy of the License at
9//
10// 	http://www.apache.org/licenses/LICENSE-2.0
11//
12// Unless required by applicable law or agreed to in writing, software
13// distributed under the License is distributed on an "AS IS" BASIS,
14// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15// See the License for the specific language governing permissions and
16// limitations under the License.
17
18use core::cmp::Ordering;
19use revm::primitives::U256;
20
21/// Represents the sign of a 256-bit signed integer value.
22#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
23#[repr(i8)]
24pub enum Sign {
25	// Same as `cmp::Ordering`
26	/// Negative value sign
27	Minus = -1,
28	/// Zero value sign
29	Zero = 0,
30	#[allow(dead_code)] // "constructed" with `mem::transmute` in `i256_sign` below
31	/// Positive value sign
32	Plus = 1,
33}
34
35#[cfg(test)]
36/// The maximum positive value for a 256-bit signed integer.
37pub const MAX_POSITIVE_VALUE: U256 = U256::from_limbs([
38	0xffffffffffffffff,
39	0xffffffffffffffff,
40	0xffffffffffffffff,
41	0x7fffffffffffffff,
42]);
43
44/// The minimum negative value for a 256-bit signed integer.
45pub const MIN_NEGATIVE_VALUE: U256 = U256::from_limbs([
46	0x0000000000000000,
47	0x0000000000000000,
48	0x0000000000000000,
49	0x8000000000000000,
50]);
51
52const FLIPH_BITMASK_U64: u64 = 0x7FFF_FFFF_FFFF_FFFF;
53
54/// Determines the sign of a 256-bit signed integer.
55#[inline]
56pub fn i256_sign(val: &U256) -> Sign {
57	if val.bit(U256::BITS - 1) {
58		Sign::Minus
59	} else {
60		// SAFETY: false == 0 == Zero, true == 1 == Plus
61		unsafe { core::mem::transmute::<bool, Sign>(!val.is_zero()) }
62	}
63}
64
65/// Determines the sign of a 256-bit signed integer and converts it to its absolute value.
66#[inline]
67pub fn i256_sign_compl(val: &mut U256) -> Sign {
68	let sign = i256_sign(val);
69	if sign == Sign::Minus {
70		two_compl_mut(val);
71	}
72	sign
73}
74
75#[inline]
76fn u256_remove_sign(val: &mut U256) {
77	// SAFETY: U256 does not have any padding bytes
78	unsafe {
79		val.as_limbs_mut()[3] &= FLIPH_BITMASK_U64;
80	}
81}
82
83/// Computes the two's complement of a U256 value in place.
84#[inline]
85pub fn two_compl_mut(op: &mut U256) {
86	*op = two_compl(*op);
87}
88
89/// Computes the two's complement of a U256 value.
90#[inline]
91pub fn two_compl(op: U256) -> U256 {
92	op.wrapping_neg()
93}
94
95/// Compares two 256-bit signed integers.
96#[inline]
97pub fn i256_cmp(first: &U256, second: &U256) -> Ordering {
98	let first_sign = i256_sign(first);
99	let second_sign = i256_sign(second);
100	match first_sign.cmp(&second_sign) {
101		// Note: Adding `if first_sign != Sign::Zero` to short circuit zero comparisons performs
102		// slower on average, as of #582
103		Ordering::Equal => first.cmp(second),
104		o => o,
105	}
106}
107
108/// Performs signed division of two 256-bit integers.
109#[inline]
110pub fn i256_div(mut first: U256, mut second: U256) -> U256 {
111	let second_sign = i256_sign_compl(&mut second);
112	if second_sign == Sign::Zero {
113		return U256::ZERO;
114	}
115
116	let first_sign = i256_sign_compl(&mut first);
117	if first == MIN_NEGATIVE_VALUE && second == U256::from(1) {
118		return two_compl(MIN_NEGATIVE_VALUE);
119	}
120
121	// Necessary overflow checks are done above, perform the division
122	let mut d = first / second;
123
124	// Set sign bit to zero
125	u256_remove_sign(&mut d);
126
127	// Two's complement only if the signs are different
128	// Note: This condition has better codegen than an exhaustive match, as of #582
129	if (first_sign == Sign::Minus && second_sign != Sign::Minus) ||
130		(second_sign == Sign::Minus && first_sign != Sign::Minus)
131	{
132		two_compl(d)
133	} else {
134		d
135	}
136}
137
138/// Performs signed modulo of two 256-bit integers.
139#[inline]
140pub fn i256_mod(mut first: U256, mut second: U256) -> U256 {
141	let first_sign = i256_sign_compl(&mut first);
142	if first_sign == Sign::Zero {
143		return U256::ZERO;
144	}
145
146	let second_sign = i256_sign_compl(&mut second);
147	if second_sign == Sign::Zero {
148		return U256::ZERO;
149	}
150
151	let mut r = first % second;
152
153	// Set sign bit to zero
154	u256_remove_sign(&mut r);
155
156	if first_sign == Sign::Minus {
157		two_compl(r)
158	} else {
159		r
160	}
161}
162
163#[cfg(test)]
164mod tests {
165	use super::*;
166	use core::num::Wrapping;
167	use revm::primitives::uint;
168
169	#[test]
170	fn div_i256() {
171		// Sanity checks based on i8. Notice that we need to use `Wrapping` here because
172		// Rust will prevent the overflow by default whereas the EVM does not.
173		assert_eq!(Wrapping(i8::MIN) / Wrapping(-1), Wrapping(i8::MIN));
174		assert_eq!(i8::MAX / -1, -i8::MAX);
175
176		uint! {
177			assert_eq!(i256_div(MIN_NEGATIVE_VALUE, -1_U256), MIN_NEGATIVE_VALUE);
178			assert_eq!(i256_div(MIN_NEGATIVE_VALUE, 1_U256), MIN_NEGATIVE_VALUE);
179			assert_eq!(i256_div(MAX_POSITIVE_VALUE, 1_U256), MAX_POSITIVE_VALUE);
180			assert_eq!(i256_div(MAX_POSITIVE_VALUE, -1_U256), -1_U256 * MAX_POSITIVE_VALUE);
181			assert_eq!(i256_div(100_U256, -1_U256), -100_U256);
182			assert_eq!(i256_div(100_U256, 2_U256), 50_U256);
183		}
184	}
185	#[test]
186	fn test_i256_sign() {
187		uint! {
188			assert_eq!(i256_sign(&0_U256), Sign::Zero);
189			assert_eq!(i256_sign(&1_U256), Sign::Plus);
190			assert_eq!(i256_sign(&-1_U256), Sign::Minus);
191			assert_eq!(i256_sign(&MIN_NEGATIVE_VALUE), Sign::Minus);
192			assert_eq!(i256_sign(&MAX_POSITIVE_VALUE), Sign::Plus);
193		}
194	}
195
196	#[test]
197	fn test_i256_sign_compl() {
198		uint! {
199			let mut zero = 0_U256;
200			let mut positive = 1_U256;
201			let mut negative = -1_U256;
202			assert_eq!(i256_sign_compl(&mut zero), Sign::Zero);
203			assert_eq!(i256_sign_compl(&mut positive), Sign::Plus);
204			assert_eq!(i256_sign_compl(&mut negative), Sign::Minus);
205		}
206	}
207
208	#[test]
209	fn test_two_compl() {
210		uint! {
211			assert_eq!(two_compl(0_U256), 0_U256);
212			assert_eq!(two_compl(1_U256), -1_U256);
213			assert_eq!(two_compl(-1_U256), 1_U256);
214			assert_eq!(two_compl(2_U256), -2_U256);
215			assert_eq!(two_compl(-2_U256), 2_U256);
216
217			// Two's complement of the min value is itself.
218			assert_eq!(two_compl(MIN_NEGATIVE_VALUE), MIN_NEGATIVE_VALUE);
219		}
220	}
221
222	#[test]
223	fn test_two_compl_mut() {
224		uint! {
225			let mut value = 1_U256;
226			two_compl_mut(&mut value);
227			assert_eq!(value, -1_U256);
228		}
229	}
230
231	#[test]
232	fn test_i256_cmp() {
233		uint! {
234			assert_eq!(i256_cmp(&1_U256, &2_U256), Ordering::Less);
235			assert_eq!(i256_cmp(&2_U256, &2_U256), Ordering::Equal);
236			assert_eq!(i256_cmp(&3_U256, &2_U256), Ordering::Greater);
237			assert_eq!(i256_cmp(&-1_U256, &-1_U256), Ordering::Equal);
238			assert_eq!(i256_cmp(&-1_U256, &-2_U256), Ordering::Greater);
239			assert_eq!(i256_cmp(&-1_U256, &0_U256), Ordering::Less);
240			assert_eq!(i256_cmp(&-2_U256, &2_U256), Ordering::Less);
241		}
242	}
243
244	#[test]
245	fn test_i256_div() {
246		uint! {
247			assert_eq!(i256_div(1_U256, 0_U256), 0_U256);
248			assert_eq!(i256_div(0_U256, 1_U256), 0_U256);
249			assert_eq!(i256_div(0_U256, -1_U256), 0_U256);
250			assert_eq!(i256_div(MIN_NEGATIVE_VALUE, 1_U256), MIN_NEGATIVE_VALUE);
251			assert_eq!(i256_div(4_U256, 2_U256), 2_U256);
252			assert_eq!(i256_div(MIN_NEGATIVE_VALUE, MIN_NEGATIVE_VALUE), 1_U256);
253			assert_eq!(i256_div(2_U256, -1_U256), -2_U256);
254			assert_eq!(i256_div(-2_U256, -1_U256), 2_U256);
255		}
256	}
257
258	#[test]
259	fn test_i256_mod() {
260		uint! {
261			assert_eq!(i256_mod(0_U256, 1_U256), 0_U256);
262			assert_eq!(i256_mod(1_U256, 0_U256), 0_U256);
263			assert_eq!(i256_mod(4_U256, 2_U256), 0_U256);
264			assert_eq!(i256_mod(3_U256, 2_U256), 1_U256);
265			assert_eq!(i256_mod(MIN_NEGATIVE_VALUE, 1_U256), 0_U256);
266			assert_eq!(i256_mod(2_U256, 2_U256), 0_U256);
267			assert_eq!(i256_mod(2_U256, 3_U256), 2_U256);
268			assert_eq!(i256_mod(-2_U256, 3_U256), -2_U256);
269			assert_eq!(i256_mod(2_U256, -3_U256), 2_U256);
270			assert_eq!(i256_mod(-2_U256, -3_U256), -2_U256);
271		}
272	}
273}
pallet_revive/vm/evm/instructions/i256.rs

pallet_revive/vm/evm/instructions/
i256.rs
