From f33dc92cbd908a6d852368fa30144bda9e8da439 Mon Sep 17 00:00:00 2001 From: Daniel Kirchner Date: Mon, 7 May 2018 19:09:52 +0200 Subject: Use proper SAR for signed right shifts and emulate on pre-constantinople. --- libsolidity/codegen/ExpressionCompiler.cpp | 25 +++++++++++++++++++++---- 1 file changed, 21 insertions(+), 4 deletions(-) (limited to 'libsolidity/codegen/ExpressionCompiler.cpp') diff --git a/libsolidity/codegen/ExpressionCompiler.cpp b/libsolidity/codegen/ExpressionCompiler.cpp index 93d440c8..908c703a 100644 --- a/libsolidity/codegen/ExpressionCompiler.cpp +++ b/libsolidity/codegen/ExpressionCompiler.cpp @@ -1737,11 +1737,28 @@ void ExpressionCompiler::appendShiftOperatorCode(Token::Value _operator, Type co m_context << u256(2) << Instruction::EXP << Instruction::MUL; break; case Token::SAR: - // NOTE: SAR rounds differently than SDIV - if (m_context.evmVersion().hasBitwiseShifting() && !c_valueSigned) - m_context << Instruction::SHR; + if (m_context.evmVersion().hasBitwiseShifting()) + m_context << (c_valueSigned ? Instruction::SAR : Instruction::SHR); else - m_context << u256(2) << Instruction::EXP << Instruction::SWAP1 << (c_valueSigned ? Instruction::SDIV : Instruction::DIV); + { + if (c_valueSigned) + // For negative values xor_mask has all bits set and xor(value_to_shift, xor_mask) will be + // the bitwise complement of value_to_shift, i.e. abs(value_to_shift) - 1. Dividing this by + // exp(2, shift_amount) results in a value that is positive and strictly smaller than the + // absolute value of the desired result. Taking the complement again changes the sign + // back to negative and subtracts one, resulting in rounding towards negative infinity. + // For positive values xor_mask is zero and xor(value_to_shift, xor_mask) is again value_to_shift. + m_context.appendInlineAssembly(R"({ + let xor_mask := sub(0, slt(value_to_shift, 0)) + value_to_shift := xor(div(xor(value_to_shift, xor_mask), exp(2, shift_amount)), xor_mask) + })", {"value_to_shift", "shift_amount"}); + else + m_context.appendInlineAssembly(R"({ + value_to_shift := div(value_to_shift, exp(2, shift_amount)) + })", {"value_to_shift", "shift_amount"}); + m_context << Instruction::POP; + + } break; case Token::SHR: default: -- cgit v1.2.3 From e84b55bd6feded46789d2d398cd1b4092ef7a1c0 Mon Sep 17 00:00:00 2001 From: Daniel Kirchner Date: Thu, 7 Jun 2018 17:08:42 +0200 Subject: Extend explanatory remark and argue using bitwise operations instead of rounding. --- libsolidity/codegen/ExpressionCompiler.cpp | 20 ++++++++++++++------ 1 file changed, 14 insertions(+), 6 deletions(-) (limited to 'libsolidity/codegen/ExpressionCompiler.cpp') diff --git a/libsolidity/codegen/ExpressionCompiler.cpp b/libsolidity/codegen/ExpressionCompiler.cpp index 908c703a..0470c3ec 100644 --- a/libsolidity/codegen/ExpressionCompiler.cpp +++ b/libsolidity/codegen/ExpressionCompiler.cpp @@ -1742,12 +1742,20 @@ void ExpressionCompiler::appendShiftOperatorCode(Token::Value _operator, Type co else { if (c_valueSigned) - // For negative values xor_mask has all bits set and xor(value_to_shift, xor_mask) will be - // the bitwise complement of value_to_shift, i.e. abs(value_to_shift) - 1. Dividing this by - // exp(2, shift_amount) results in a value that is positive and strictly smaller than the - // absolute value of the desired result. Taking the complement again changes the sign - // back to negative and subtracts one, resulting in rounding towards negative infinity. - // For positive values xor_mask is zero and xor(value_to_shift, xor_mask) is again value_to_shift. + // In the following assembly snippet, xor_mask will be zero, if value_to_shift is positive. + // Therefor xor'ing with xor_mask is the identity and the computation reduces to + // div(value_to_shift, exp(2, shift_amount)), which is correct, since for positive values + // arithmetic right shift is dividing by a power of two (which, as a bitwise operation, results + // in discarding bits on the right and filling with zeros from the left). + // For negative values arithmetic right shift, viewed as a bitwise operation, discards bits to the + // right and fills in ones from the left. This is achieved as follows: + // If value_to_shift is negative, then xor_mask will have all bits set, so xor'ing with xor_mask + // will flip all bits. First all bits in value_to_shift are flipped. As for the positive case, + // dividing by a power of two using integer arithmetic results in discarding bits to the right + // and filling with zeros from the left. Flipping all bits in the result again, turns all zeros + // on the left to ones and restores the non-discarded, shifted bits to their original value (they + // have now been flipped twice). In summary we now have discarded bits to the right and filled with + // ones from the left, i.e. we have performed an arithmetic right shift. m_context.appendInlineAssembly(R"({ let xor_mask := sub(0, slt(value_to_shift, 0)) value_to_shift := xor(div(xor(value_to_shift, xor_mask), exp(2, shift_amount)), xor_mask) -- cgit v1.2.3