// Copyright (c) 2020 Can Boluk and contributors of the VTIL Project // All rights reserved. // // Redistribution and use in source and binary forms, with or without // modification, are permitted provided that the following conditions are met: // // 1. Redistributions of source code must retain the above copyright notice, // this list of conditions and the following disclaimer. // 2. Redistributions in binary form must reproduce the above copyright // notice, this list of conditions and the following disclaimer in the // documentation and/or other materials provided with the distribution. // 3. Neither the name of mosquitto nor the names of its // contributors may be used to endorse or promote products derived from // this software without specific prior written permission. // // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE // ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE // LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF // SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE // POSSIBILITY OF SUCH DAMAGE. // #include "../io/logger.hpp" #include "operators.hpp" #include "../util/mul128.hpp" namespace vtil::math { // Calculates the size of the result after after the application of the operator [id] on the operands. // bitcnt_t result_size( operator_id id, bitcnt_t bcnt_lhs, bitcnt_t bcnt_rhs ) { switch ( id ) { // - Operators that work with bit-indices. // case operator_id::popcnt: case operator_id::bitscan_fwd: case operator_id::bitscan_rev: case operator_id::bit_count: return bit_index_size; // - Unary and parameterized unary-like operators. // case operator_id::negate: case operator_id::bitwise_not: case operator_id::mask: case operator_id::value_if: return bcnt_rhs; case operator_id::shift_right: case operator_id::shift_left: case operator_id::rotate_right: case operator_id::rotate_left: return bcnt_lhs; // - Boolean operators. // case operator_id::bit_test: case operator_id::greater: case operator_id::greater_eq: case operator_id::equal: case operator_id::not_equal: case operator_id::less_eq: case operator_id::less: case operator_id::ugreater: case operator_id::ugreater_eq: case operator_id::uless_eq: case operator_id::uless: return 1; // - Resizing operators should not call into this helper. // case operator_id::cast: case operator_id::ucast: unreachable(); } // - Rest default to maximum operand size. // return std::max( bcnt_lhs, bcnt_rhs ); } // Applies the specified operator [id] on left hand side [lhs] and right hand side [rhs] // and returns the output as a masked unsigned 64-bit integer <0> and the final size <1>. // std::pair evaluate( operator_id id, bitcnt_t bcnt_lhs, uint64_t lhs, bitcnt_t bcnt_rhs, uint64_t rhs ) { using namespace logger; // Normalize the input. // const operator_desc* desc = descriptor_of( id ); if ( bcnt_lhs != 64 && desc->operand_count != 1 ) lhs = desc->is_signed ? sign_extend( lhs, bcnt_lhs ) : zero_extend( lhs, bcnt_lhs ); if ( bcnt_rhs != 64 ) rhs = desc->is_signed ? sign_extend( rhs, bcnt_rhs ) : zero_extend( rhs, bcnt_rhs ); // Create aliases for signed values to avoid ugly casts. // int64_t& ilhs = ( int64_t& ) lhs; int64_t& irhs = ( int64_t& ) rhs; // Handle __cast and __ucast. // if ( id == operator_id::ucast ) return { zero_extend( lhs, narrow_cast( rhs ) ), narrow_cast( rhs ) }; if ( id == operator_id::cast ) return { sign_extend( lhs, narrow_cast( rhs ) ), narrow_cast( rhs ) }; // Calculate the result of the operation. // uint64_t result = 0; bitcnt_t bcnt_res = result_size( id, bcnt_lhs, bcnt_rhs ); switch ( id ) { // - Bitwise operators. // case operator_id::bitwise_not: result = ~rhs; break; case operator_id::bitwise_and: result = lhs & rhs; break; case operator_id::bitwise_or: result = lhs | rhs; break; case operator_id::bitwise_xor: result = lhs ^ rhs; break; case operator_id::shift_right: result = rhs >= bcnt_lhs ? 0 : lhs >> rhs; break; case operator_id::shift_left: result = rhs >= bcnt_lhs ? 0 : lhs << rhs; break; case operator_id::rotate_right: result = ( lhs >> ( rhs % bcnt_lhs ) ) | ( lhs << ( bcnt_lhs - ( rhs % bcnt_lhs ) ) ); break; case operator_id::rotate_left: result = ( lhs << ( rhs % bcnt_lhs ) ) | ( lhs >> ( bcnt_lhs - ( rhs % bcnt_lhs ) ) ); break; // - Arithmetic operators. // case operator_id::negate: result = -irhs; break; case operator_id::add: result = ilhs + irhs; break; case operator_id::subtract: result = ilhs - irhs; break; case operator_id::multiply_high: result = bcnt_res == 64 ? __mulh( ilhs, irhs ) : uint64_t( ilhs * irhs ) >> bcnt_res; break; case operator_id::umultiply_high: result = bcnt_res == 64 ? __umulh( lhs, rhs ) : ( lhs * rhs ) >> bcnt_res; break; case operator_id::multiply: result = ilhs * irhs; break; case operator_id::umultiply: result = lhs * rhs; break; case operator_id::divide: if( irhs == 0 ) result = INT64_MAX, warning("Division by immediate zero (IDIV)."); else result = ilhs / irhs; break; case operator_id::udivide: if( rhs == 0 ) result = UINT64_MAX, warning("Division by immediate zero (DIV)."); else result = lhs / rhs; break; case operator_id::remainder: if( irhs == 0 ) result = 0, warning("Division by immediate zero (IREM)."); else result = ilhs % irhs; break; case operator_id::uremainder: if( rhs == 0 ) result = 0, warning("Division by immediate zero (REM)."); else result = lhs % rhs; break; // - Special operators. // case operator_id::popcnt: result = popcnt( rhs ); break; case operator_id::bitscan_fwd: result = lsb( rhs ); break; case operator_id::bitscan_rev: result = msb( rhs ); break; case operator_id::bit_test: result = ( lhs >> rhs ) & 1; break; case operator_id::mask: result = fill( bcnt_rhs ); break; case operator_id::bit_count: result = bcnt_rhs; break; case operator_id::value_if: result = ( lhs & 1 ) ? rhs : 0; break; // - MinMax operators // case operator_id::umin_value: result = std::min( lhs, rhs ); break; case operator_id::umax_value: result = std::max( lhs, rhs ); break; case operator_id::min_value: result = std::min( ilhs, irhs ); break; case operator_id::max_value: result = std::max( ilhs, irhs ); break; // - Comparison operators // case operator_id::greater: result = ilhs > irhs; break; case operator_id::greater_eq: result = ilhs >= irhs; break; case operator_id::equal: result = ilhs == irhs; break; case operator_id::not_equal: result = ilhs != irhs; break; case operator_id::uequal: result = lhs == rhs; break; case operator_id::unot_equal: result = lhs != rhs; break; case operator_id::less_eq: result = ilhs <= irhs; break; case operator_id::less: result = ilhs < irhs; break; case operator_id::ugreater: result = lhs > rhs; break; case operator_id::ugreater_eq: result = lhs >= rhs; break; case operator_id::uless_eq: result = lhs <= rhs; break; case operator_id::uless: result = lhs < rhs; break; default: unreachable(); } // Mask and return. // return { result & fill( bcnt_res ), bcnt_res }; } // Applies the specified operator [op] on left hand side [lhs] and right hand side [rhs] where // input and output values are expressed in the format of bit-vectors with optional unknowns, // and no size constraints. // bit_vector evaluate_partial( operator_id op, const bit_vector& lhs, const bit_vector& rhs ) { // If invalid operation, return invalid. // auto* desc = descriptor_of( op ); bool known; switch ( desc ? desc->operand_count : 0 ) { case 1: if ( rhs.is_valid() ) { known = rhs.is_known(); break; } case 2: if ( rhs.is_valid() && lhs.is_valid() ) { known = lhs.is_known() && rhs.is_known(); break; } default: return {}; } // If no unknown bits, redirect to more efficient evaluate(). // if ( known ) { auto [val, size] = evaluate( op, lhs.size(), lhs.known_one(), rhs.size(), rhs.known_one() ); return { val, size }; } switch ( op ) { // // Basic bitwise operators. // // #################################################################################################################################### case operator_id::bitwise_not: // Unknown mask does not change, known bits are flipped. // return bit_vector{ ~rhs.known_one(), rhs.unknown_mask(), rhs.size() }; case operator_id::bitwise_and: // Bitwise AND known bits, unknown mask is unset if one side had a known zero. // return bit_vector { lhs.known_one() & rhs.known_one(), ( lhs.unknown_mask() | rhs.unknown_mask() ) & ~( lhs.known_zero() | rhs.known_zero() ), std::min( lhs.size(), rhs.size() ) }.resize( std::max( lhs.size(), rhs.size() ) ); case operator_id::bitwise_or: // Bitwise OR known bits, unknown mask is unset if one side had a known one. // return bit_vector { lhs.known_one() | rhs.known_one(), ( lhs.unknown_mask() | rhs.unknown_mask() ) & ~( lhs.known_one() | rhs.known_one() ), std::max( lhs.size(), rhs.size() ) }; case operator_id::bitwise_xor: // Bitwise XOR known bits, unknown mask is merged. // return bit_vector { lhs.known_one() ^ rhs.known_one(), lhs.unknown_mask() | rhs.unknown_mask(), std::max( lhs.size(), rhs.size() ) }; // // Rotations and shifts. // // #################################################################################################################################### case operator_id::shift_right: // If shift count is known: // if ( auto n = rhs.get() ) { // If shifting more bits than we have, return 0. // uint64_t shr_count = n.value(); if ( shr_count >= lhs.size() ) return bit_vector( 0, lhs.size() ); // Return shifted masks, vector will normalize rest. // return { lhs.known_one() >> shr_count, lhs.unknown_mask() >> shr_count, lhs.size() }; } // If shift count is unknown, return unknown bit-vector or 0 if input was only consisting of zeros. // return lhs.all_zero() ? lhs : bit_vector( lhs.size() ); case operator_id::shift_left: // If shift count is known: // if ( auto n = rhs.get() ) { // If shifting more bits than we have, return 0. // uint64_t shl_count = n.value(); if ( shl_count >= lhs.size() ) return bit_vector( 0, lhs.size() ); // Return shifted masks, vector will normalize rest. // return { lhs.known_one() << shl_count, lhs.unknown_mask() << shl_count, lhs.size() }; } // If shift count is unknown, return unknown bit-vector or 0 if input was only consisting of zeros. // return lhs.all_zero() ? lhs : bit_vector( lhs.size() ); case operator_id::rotate_right: // If rotation count is known, return rotated masks, vector will normalize rest. // if ( auto n = rhs.get() ) { uint64_t shr_count = n.value() % lhs.size(); uint64_t shl_count = lhs.size() - shr_count; return { ( lhs.known_one() >> shr_count ) | ( lhs.known_one() << shl_count ), ( lhs.unknown_mask() >> shr_count ) | ( lhs.unknown_mask() << shl_count ), lhs.size() }; } // If rotation count is unknown, return unknown bit-vector or 0/1 if input was only consisting of the same bit state. // return ( lhs.all_one() || lhs.all_zero() ) ? lhs : bit_vector( lhs.size() ); case operator_id::rotate_left: // If rotation count is known, return rotated masks, vector will normalize rest. // if ( auto n = rhs.get() ) { uint64_t shl_count = n.value() % lhs.size(); uint64_t shr_count = lhs.size() - shl_count; return { ( lhs.known_one() >> shr_count ) | ( lhs.known_one() << shl_count ), ( lhs.unknown_mask() >> shr_count ) | ( lhs.unknown_mask() << shl_count ), lhs.size() }; } // If rotation count is unknown, return unknown bit-vector or 0/1 if input was only consisting of the same bit state. // return ( lhs.all_one() || lhs.all_zero() ) ? lhs : bit_vector( lhs.size() ); // // Arithmetic operators: // - TODO: Re-implement *fixed* O(1) solution for ADD SUB and NEG. // // #################################################################################################################################### case operator_id::add: { bitcnt_t out_size = std::max( lhs.size(), rhs.size() ); // Return unknown if no bits are known from one side. // if( lhs.unknown_mask() == lhs.value_mask() || rhs.unknown_mask() == rhs.value_mask() ) return bit_vector( out_size ); // Create the temp holding the new bit vector. // uint64_t known_mask = 0; uint64_t unknown_mask = 0; // For each bit in the output size: // bit_vector lhs_sx = bit_vector{ lhs }.resize( out_size, true ); bit_vector rhs_sx = bit_vector{ rhs }.resize( out_size, true ); bit_state carry = bit_state::zero; for ( int i = 0; i < out_size; i++ ) { // Get current bits and choose the branch depending on the type: // bit_state a = lhs_sx[ i ]; bit_state b = rhs_sx[ i ]; if ( const int unk_count = ( a == bit_state::unknown ) + ( b == bit_state::unknown ) + ( carry == bit_state::unknown ) ) { const int one_count = ( a == bit_state::one ) + ( b == bit_state::one ) + ( carry == bit_state::one ); const int zero_count = 3 - one_count - unk_count; // Carry is one if 2 elements are 1, zero if 2 elements are zero // and unknown otherise. // if ( one_count == 2 ) carry = bit_state::one; else if ( zero_count == 2 ) carry = bit_state::zero; else carry = bit_state::unknown; // Output is always unknown. // unknown_mask |= 1ull << i; } else if ( a == b ) { // Duplicated element propagates as carry, output is current carry. // known_mask |= uint64_t( carry == bit_state::one ) << i; carry = a; } else if ( a != b ) { // Carry propagates as is, output is inverse of current carry. // known_mask |= uint64_t( carry == bit_state::zero ) << i; } } return bit_vector( known_mask, unknown_mask, out_size ); /*a = ( lhs.unknown_mask() | lhs.known_one() ) + ( rhs.unknown_mask() | rhs.known_one() ); b = ( lhs.known_one() ) + ( rhs.known_one() ); return { a & b, ~( a & b ) & ~( ~a & ~b ), std::max( lhs.size(), rhs.size() ) }; break;*/ } case operator_id::negate: // -A = 0-A // return evaluate_partial( operator_id::subtract, { 0, rhs.size() }, rhs ); /*a = mask( rhs.size() ) & -__sx64( ( rhs.unknown_mask() | rhs.known_one() ), rhs.size() ); b = mask( rhs.size() ) & -__sx64( ( rhs.known_one() ), rhs.size() ); return { a & b, ~( a & b ) & ~( ~a & ~b ), rhs.size() }; break;*/ case operator_id::subtract: // A-B = ~(~A+B) // return evaluate_partial( operator_id::bitwise_not, {}, evaluate_partial( operator_id::add, evaluate_partial( operator_id::bitwise_not, {}, lhs ), rhs ) ); /*a = ( lhs.unknown_mask() | lhs.known_one() ) - ( rhs.known_one() ); b = ( lhs.known_one() ) - ( rhs.unknown_mask() | rhs.known_one() ); return { a & b, ~( a & b ) & ~( ~a & ~b ), std::max( lhs.size(), rhs.size() ) }; break;*/ // // Bitwise specials. // // #################################################################################################################################### case operator_id::ucast: // Get new size from RHS as constant, and resize LHS to be of size [RHS] with zero extension if relevant. // if ( auto new_size = rhs.get() ) return bit_vector( lhs ).resize( narrow_cast( *new_size ), false ); else unreachable(); case operator_id::cast: // Get new size from RHS as constant, and resize LHS to be of size [RHS] with sign extension if relevant. // if ( auto new_size = rhs.get() ) return bit_vector( lhs ).resize( narrow_cast( *new_size ), true ); else unreachable(); case operator_id::popcnt: // Cannot be calculated with unknown values, return unknown of expected size. // return bit_vector( popcnt( rhs.known_one() | rhs.unknown_mask() ) ).resize( bit_index_size ); case operator_id::bitscan_fwd: case operator_id::bitscan_rev: // Cannot be calculated with unknown values, return unknown of expected size. // return bit_vector( bit_index_size ); case operator_id::bit_test: // If we can get the index being tested as constant, try to evaluate. // if ( auto index = rhs.get() ) { return { ( lhs.known_one() >> rhs.known_one() ) & 1, ( lhs.unknown_mask() >> rhs.known_one() ) & 1, 1 }; } // Otherwise, return unknown of one bit. // return bit_vector( 1 ); case operator_id::mask: // Return the mask of the vector as is. // return bit_vector( rhs.value_mask(), rhs.size() ); case operator_id::bit_count: // Return the number of bits in the vector as is. // return bit_vector( rhs.size(), bit_index_size ); case operator_id::value_if: // Try to evaluate the (x&1)?y:0 statement. // if ( lhs.known_one() & 1 ) return rhs; else if ( lhs.unknown_mask() & 1 ) return bit_vector{ rhs.size() }; else return bit_vector{ 0, rhs.size() }; // // Complex arithmetic operators. // - TODO: Whole thing :) // // #################################################################################################################################### case operator_id::multiply_high: case operator_id::multiply: case operator_id::divide: case operator_id::remainder: case operator_id::umultiply_high: case operator_id::umultiply: case operator_id::udivide: case operator_id::uremainder: return bit_vector( std::max( rhs.size(), lhs.size() ) ); // // MinMax operators: // // #################################################################################################################################### case operator_id::min_value: case operator_id::max_value: case operator_id::umin_value: case operator_id::umax_value: { // Map each min-max to a comperator. // operator_id cmp_id; switch ( op ) { case operator_id::umin_value: cmp_id = operator_id::uless; break; case operator_id::umax_value: cmp_id = operator_id::ugreater_eq; break; case operator_id::min_value: cmp_id = operator_id::less; break; case operator_id::max_value: cmp_id = operator_id::greater_eq; break; default: unreachable(); } // cmp<>(A,B) ? A : B bit_state cmp_res = evaluate_partial( cmp_id, lhs, rhs )[ 0 ]; bitcnt_t cmp_out_size = std::max( lhs.size(), rhs.size() ); switch ( cmp_res ) { case bit_state::one: return bit_vector{ lhs }.resize( cmp_out_size ); case bit_state::zero: return bit_vector{ rhs }.resize( cmp_out_size ); case bit_state::unknown: return bit_vector{ cmp_out_size }; default: unreachable(); } } // // Signed comparisons: // // #################################################################################################################################### case operator_id::greater: case operator_id::greater_eq: case operator_id::less_eq: case operator_id::less: { // Fail if sign bits are not known // bit_state rhs_sign = rhs[ rhs.size() - 1 ]; if ( rhs_sign == bit_state::unknown ) return bit_vector( 1 ); bit_state lhs_sign = lhs[ lhs.size() - 1 ]; if ( lhs_sign == bit_state::unknown ) return bit_vector( 1 ); // If LHS is negative and RHS is positive, <, <= wins. // if ( lhs_sign == bit_state::one && rhs_sign == bit_state::zero ) return bit_vector( op == operator_id::less || op == operator_id::less_eq, 1 ); // If RHS is negative and LHS is positive, >, >= wins. // if ( rhs_sign == bit_state::one && lhs_sign == bit_state::zero ) return bit_vector( op == operator_id::greater || op == operator_id::greater_eq, 1 ); // For each bit index we should compare: // bitcnt_t cmp_size = std::max( lhs.size(), rhs.size() ); bit_vector lhs_sx = bit_vector{ lhs }.resize( cmp_size, true ); bit_vector rhs_sx = bit_vector{ rhs }.resize( cmp_size, true ); for ( int i = cmp_size - 1; i >= 0; i-- ) { // If any of the bits are unknown, result is unknown. // if ( lhs_sx[ i ] == bit_state::unknown || rhs_sx[ i ] == bit_state::unknown ) return bit_vector( 1 ); // If LHS is one and RHS is zero, >, >= and != wins. // if ( lhs_sx[ i ] == bit_state::one && rhs_sx[ i ] == bit_state::zero ) return bit_vector( op == operator_id::greater || op == operator_id::greater_eq, 1 ); // If RHS is one and LHS is zero, <, <= and != wins. // if ( rhs_sx[ i ] == bit_state::one && lhs_sx[ i ] == bit_state::zero ) return bit_vector( op == operator_id::less || op == operator_id::less_eq, 1 ); } // If completely equivalent (when sign extended), <=, >= wins. // return bit_vector( op == operator_id::less_eq || op == operator_id::greater_eq, 1 ); } // // Equality checks: // // #################################################################################################################################### case operator_id::equal: case operator_id::not_equal: { // Fail if sign bits are not known // bit_state rhs_sign = rhs[ rhs.size() - 1 ]; if ( rhs_sign == bit_state::unknown ) return bit_vector( 1 ); bit_state lhs_sign = lhs[ lhs.size() - 1 ]; if ( lhs_sign == bit_state::unknown ) return bit_vector( 1 ); // If signs do not match, != wins. // if ( lhs_sign != rhs_sign ) return bit_vector( op == operator_id::not_equal, 1 ); // Sign extend both. // bitcnt_t cmp_size = std::max( lhs.size(), rhs.size() ); bit_vector lhs_sx = bit_vector{ lhs }.resize( cmp_size, true ); bit_vector rhs_sx = bit_vector{ rhs }.resize( cmp_size, true ); // If known zero of one side maps to known one of other and vice versa, != wins. // if ( ( lhs_sx.known_zero() & rhs_sx.known_one() ) || ( lhs_sx.known_one() & rhs_sx.known_zero() ) ) return bit_vector( op == operator_id::not_equal, 1 ); // If any of the bits are unknown, result is unknown. // if ( lhs_sx.unknown_mask() | rhs_sx.unknown_mask() ) return bit_vector( 1 ); // Simply compare all bits and adjust to the operator result. // return bit_vector( ( op == operator_id::not_equal ) ^ ( lhs_sx.known_one() == rhs_sx.known_one() ), 1 ); } // // Unsigned comparisons: // // #################################################################################################################################### case operator_id::ugreater: case operator_id::ugreater_eq: case operator_id::uless_eq: case operator_id::uless: // For each bit index we should compare: // for ( int i = std::max( lhs.size(), rhs.size() ) - 1; i >= 0; i-- ) { // If any of the bits are unknown, result is unknown. // if ( lhs[ i ] == bit_state::unknown || rhs[ i ] == bit_state::unknown ) return bit_vector( 1 ); // If LHS is one and RHS is zero, >, >= wins. // if ( lhs[ i ] == bit_state::one && rhs[ i ] == bit_state::zero ) return bit_vector( op == operator_id::ugreater || op == operator_id::ugreater_eq, 1 ); // If RHS is one and LHS is zero, <, <= wins. // if ( rhs[ i ] == bit_state::one && lhs[ i ] == bit_state::zero ) return bit_vector( op == operator_id::uless || op == operator_id::uless_eq, 1 ); } // If completely equivalent (when zero extended), <=, >= wins. // return bit_vector( op == operator_id::uless_eq || op == operator_id::ugreater_eq, 1 ); // // Unsigned equality checks: // // #################################################################################################################################### case operator_id::uequal: case operator_id::unot_equal: // If known zero of one side maps to known one of other and vice versa, != wins. // if ( ( lhs.known_zero() & rhs.known_one() ) || ( lhs.known_one() & rhs.known_zero() ) ) return bit_vector( op == operator_id::unot_equal, 1 ); // If any of the bits are unknown, result is unknown. // if ( lhs.unknown_mask() | rhs.unknown_mask() ) return bit_vector( 1 ); // Simply compare all bits and adjust to the operator result. // return bit_vector( ( op == operator_id::unot_equal ) ^ ( lhs.known_one() == rhs.known_one() ), 1 ); } unreachable(); } };