blob: 89a723751471dc69b176ce8702bf9b9718473b7a [file] [log] [blame]
/* -*- mode: C; c-basic-offset: 3; -*- */
/*
This file is part of MemCheck, a heavyweight Valgrind tool for
detecting memory errors.
Copyright (C) 2012-2017 Florian Krohm
This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License as
published by the Free Software Foundation; either version 2 of the
License, or (at your option) any later version.
This program is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
02111-1307, USA.
The GNU General Public License is contained in the file COPYING.
*/
#include <assert.h>
#include <string.h> // memset
#include "vtest.h"
/* A convenience function to compute either v1 & ~v2 & val2 or
v1 & ~v2 & ~val2 depending on INVERT_VAL2. */
static vbits_t
and_combine(vbits_t v1, vbits_t v2, value_t val2, int invert_val2)
{
assert(v1.num_bits == v2.num_bits);
vbits_t new = { .num_bits = v2.num_bits };
if (invert_val2) {
switch (v2.num_bits) {
case 8: val2.u8 = ~val2.u8 & 0xff; break;
case 16: val2.u16 = ~val2.u16 & 0xffff; break;
case 32: val2.u32 = ~val2.u32; break;
case 64: val2.u64 = ~val2.u64; break;
default:
panic(__func__);
}
}
switch (v2.num_bits) {
case 8:
new.bits.u8 = (v1.bits.u8 & ~v2.bits.u8 & val2.u8) & 0xff;
break;
case 16:
new.bits.u16 = (v1.bits.u16 & ~v2.bits.u16 & val2.u16) & 0xffff;
break;
case 32:
new.bits.u32 = (v1.bits.u32 & ~v2.bits.u32 & val2.u32);
break;
case 64:
new.bits.u64 = (v1.bits.u64 & ~v2.bits.u64 & val2.u64);
break;
default:
panic(__func__);
}
return new;
}
/* Check the result of a binary operation. */
static void
check_result_for_binary(const irop_t *op, const test_data_t *data)
{
const opnd_t *result = &data->result;
const opnd_t *opnd1 = &data->opnds[0];
const opnd_t *opnd2 = &data->opnds[1];
opnd_t tmp;
vbits_t expected_vbits;
/* Only handle those undef-kinds that actually occur. */
switch (op->undef_kind) {
case UNDEF_NONE:
expected_vbits = defined_vbits(result->vbits.num_bits);
break;
case UNDEF_ALL:
/* Iop_ShlD64, Iop_ShrD64, Iop_ShlD128, Iop_ShrD128 have
* one immediate operand in operand 2.
*/
expected_vbits = undefined_vbits(result->vbits.num_bits);
break;
case UNDEF_LEFT:
// LEFT with respect to the leftmost 1-bit in both operands
expected_vbits = left_vbits(or_vbits(opnd1->vbits, opnd2->vbits),
result->vbits.num_bits);
break;
case UNDEF_SAME:
assert(opnd1->vbits.num_bits == opnd2->vbits.num_bits);
assert(opnd1->vbits.num_bits == result->vbits.num_bits);
// SAME with respect to the 1-bits in both operands
expected_vbits = or_vbits(opnd1->vbits, opnd2->vbits);
break;
case UNDEF_CONCAT:
assert(opnd1->vbits.num_bits == opnd2->vbits.num_bits);
assert(result->vbits.num_bits == 2 * opnd1->vbits.num_bits);
expected_vbits = concat_vbits(opnd1->vbits, opnd2->vbits);
break;
case UNDEF_SHL:
/* If any bit in the 2nd operand is undefined, so are all bits
of the result. */
if (! completely_defined_vbits(opnd2->vbits)) {
expected_vbits = undefined_vbits(result->vbits.num_bits);
} else {
assert(opnd2->vbits.num_bits == 8);
unsigned shift_amount = opnd2->value.u8;
expected_vbits = shl_vbits(opnd1->vbits, shift_amount);
}
break;
case UNDEF_SHR:
/* If any bit in the 2nd operand is undefined, so are all bits
of the result. */
if (! completely_defined_vbits(opnd2->vbits)) {
expected_vbits = undefined_vbits(result->vbits.num_bits);
} else {
assert(opnd2->vbits.num_bits == 8);
unsigned shift_amount = opnd2->value.u8;
expected_vbits = shr_vbits(opnd1->vbits, shift_amount);
}
break;
case UNDEF_SAR:
/* If any bit in the 2nd operand is undefined, so are all bits
of the result. */
if (! completely_defined_vbits(opnd2->vbits)) {
expected_vbits = undefined_vbits(result->vbits.num_bits);
} else {
assert(opnd2->vbits.num_bits == 8);
unsigned shift_amount = opnd2->value.u8;
expected_vbits = sar_vbits(opnd1->vbits, shift_amount);
}
break;
case UNDEF_AND: {
/* Let v1, v2 be the V-bits of the 1st and 2nd operand, respectively
Let b1, b2 be the actual value of the 1st and 2nd operand, respect.
And output bit is undefined (i.e. its V-bit == 1), iff
(1) (v1 == 1) && (v2 == 1) OR
(2) (v1 == 1) && (v2 == 0 && b2 == 1) OR
(3) (v2 == 1) && (v1 == 0 && b1 == 1)
*/
vbits_t term1, term2, term3;
term1 = and_vbits(opnd1->vbits, opnd2->vbits);
term2 = and_combine(opnd1->vbits, opnd2->vbits, opnd2->value, 0);
term3 = and_combine(opnd2->vbits, opnd1->vbits, opnd1->value, 0);
expected_vbits = or_vbits(term1, or_vbits(term2, term3));
break;
}
case UNDEF_OR: {
/* Let v1, v2 be the V-bits of the 1st and 2nd operand, respectively
Let b1, b2 be the actual value of the 1st and 2nd operand, respect.
And output bit is undefined (i.e. its V-bit == 1), iff
(1) (v1 == 1) && (v2 == 1) OR
(2) (v1 == 1) && (v2 == 0 && b2 == 0) OR
(3) (v2 == 1) && (v1 == 0 && b1 == 0)
*/
vbits_t term1, term2, term3;
term1 = and_vbits(opnd1->vbits, opnd2->vbits);
term2 = and_combine(opnd1->vbits, opnd2->vbits, opnd2->value, 1);
term3 = and_combine(opnd2->vbits, opnd1->vbits, opnd1->value, 1);
expected_vbits = or_vbits(term1, or_vbits(term2, term3));
break;
}
case UNDEF_ORD:
/* Set expected_vbits for the Iop_CmpORD category of iops.
* If any of the input bits is undefined the least significant
* three bits in the result will be set, i.e. 0xe.
*/
expected_vbits = cmpord_vbits(opnd1->vbits.num_bits,
opnd2->vbits.num_bits);
break;
case UNDEF_ALL_64x2:
assert(opnd1->vbits.num_bits == opnd2->vbits.num_bits);
expected_vbits =
undefined_vbits_BxE(64, 2,
or_vbits(opnd1->vbits, opnd2->vbits));
break;
case UNDEF_ALL_32x4:
assert(opnd1->vbits.num_bits == opnd2->vbits.num_bits);
expected_vbits =
undefined_vbits_BxE(32, 4,
or_vbits(opnd1->vbits, opnd2->vbits));
break;
case UNDEF_ALL_16x8:
assert(opnd1->vbits.num_bits == opnd2->vbits.num_bits);
expected_vbits =
undefined_vbits_BxE(16, 8,
or_vbits(opnd1->vbits, opnd2->vbits));
break;
case UNDEF_ALL_8x16:
assert(opnd1->vbits.num_bits == opnd2->vbits.num_bits);
expected_vbits =
undefined_vbits_BxE(8, 16,
or_vbits(opnd1->vbits, opnd2->vbits));
break;
case UNDEF_ALL_32x4_EVEN:
/* Only even input bytes are used, result can be twice as wide */
assert(opnd1->vbits.num_bits == opnd2->vbits.num_bits);
expected_vbits =
undefined_vbits_BxE(64, 2,
undefined_vbits_128_even_element(32, 4,
or_vbits(opnd1->vbits, opnd2->vbits)));
break;
case UNDEF_ALL_16x8_EVEN:
/* Only even input bytes are used, result can be twice as wide */
assert(opnd1->vbits.num_bits == opnd2->vbits.num_bits);
expected_vbits =
undefined_vbits_BxE(32, 4,
undefined_vbits_128_even_element(16, 8,
or_vbits(opnd1->vbits, opnd2->vbits)));
break;
case UNDEF_ALL_8x16_EVEN:
/* Only even input bytes are used, result can be twice as wide */
assert(opnd1->vbits.num_bits == opnd2->vbits.num_bits);
expected_vbits =
undefined_vbits_BxE(16, 8,
undefined_vbits_128_even_element(8, 16,
or_vbits(opnd1->vbits, opnd2->vbits)));
break;
case UNDEF_64x2_ROTATE:
/* Rotate left each element in opnd1 by the amount in the corresponding
* element of opnd2.
*/
assert(opnd1->vbits.num_bits == opnd2->vbits.num_bits);
/* Setup the tmp to match what the vbit tester seems to use. I can't
* use opnd2-value since valgrind doesn't think it has been set.
*/
tmp.value.u128[0] = -1;
tmp.value.u128[1] = -1;
/* Calculate expected for the first operand when it is shifted.
* If any of the vbits are set for the shift field of the second operand
* then the result of the expected result for that element is all 1's.
*/
expected_vbits = or_vbits(undefined_vbits_BxE_rotate(64, 2, opnd1->vbits,
tmp.value),
undefined_vbits_BxE(64, 2, opnd2->vbits));
break;
case UNDEF_32x4_ROTATE:
/* Rotate left each element in opnd1 by the amount in the corresponding
* element of opnd2.
*/
assert(opnd1->vbits.num_bits == opnd2->vbits.num_bits);
expected_vbits = undefined_vbits_BxE_rotate(32, 4, opnd1->vbits,
opnd2->value);
break;
case UNDEF_16x8_ROTATE:
/* Rotate left each element in opnd1 by the amount in the corresponding
* element of opnd2.
*/
assert(opnd1->vbits.num_bits == opnd2->vbits.num_bits);
expected_vbits = undefined_vbits_BxE_rotate(16, 8, opnd1->vbits,
opnd2->value);
break;
case UNDEF_8x16_ROTATE:
/* Rotate left each element in opnd1 by the amount in the corresponding
* element of opnd2.
*/
assert(opnd1->vbits.num_bits == opnd2->vbits.num_bits);
expected_vbits = undefined_vbits_BxE_rotate(16, 8, opnd1->vbits,
opnd2->value);
break;
case UNDEF_SOME:
/* The result for the Iop_SHA256 and Iop_SHA256 is a secure hash. If
* one of the input bits is not defined there must be atleast one
* undefined bit in the output. Which bit and how many depends on
* which bit is undefined. Don't know the secure hash algorithm so
* we can only make sure at least one of the result bits is set.
*
* The Iop_SHA256, Iop_SHA512 iops have one immediate value in the
* second operand.
*/
expected_vbits.num_bits = result->vbits.num_bits;
if ((result->vbits.bits.u128[0] != 0) ||
(result->vbits.bits.u128[1] != 0)) {
expected_vbits.bits.u128[0] = result->vbits.bits.u128[0];
expected_vbits.bits.u128[1] = result->vbits.bits.u128[1];
} else {
/* The input had at least one vbit set but the result doesn't have any
* bit set. Set them all so we will trigger the error on the call
* to complain().
*/
expected_vbits.bits.u128[0] = ~0x0ULL;
expected_vbits.bits.u128[1] = ~0x0ULL;
}
break;
case UNDEF_NARROW256_AtoB:
assert(opnd1->vbits.num_bits == opnd2->vbits.num_bits);
switch(op->op) {
case Iop_NarrowBin64to32x4:
expected_vbits =
undefined_vbits_Narrow256_AtoB(64, 32, opnd1->vbits, opnd1->value,
opnd2->vbits, opnd2->value,
False);
break;
case Iop_QNarrowBin64Sto32Sx4:
expected_vbits =
undefined_vbits_Narrow256_AtoB(64, 32, opnd1->vbits, opnd1->value,
opnd2->vbits, opnd2->value,
True);
break;
case Iop_QNarrowBin64Uto32Ux4:
expected_vbits =
undefined_vbits_Narrow256_AtoB(64, 32, opnd1->vbits, opnd1->value,
opnd2->vbits, opnd2->value,
True);
break;
default:
fprintf(stderr, "ERROR, unknown Iop for UNDEF_NARROW256_AtoB\n");
panic(__func__);
}
break;
default:
panic(__func__);
}
if (! equal_vbits(result->vbits, expected_vbits))
complain(op, data, expected_vbits);
}
static int
test_shift(const irop_t *op, test_data_t *data)
{
unsigned num_input_bits, i;
opnd_t *opnds = data->opnds;
int tests_done = 0;
/* When testing the 1st operand's undefinedness propagation,
do so with all possible shift amnounts */
for (unsigned amount = 0; amount < bitsof_irtype(opnds[0].type); ++amount) {
opnds[1].value.u8 = amount;
// 1st (left) operand
num_input_bits = bitsof_irtype(opnds[0].type);
for (i = 0; i < num_input_bits; ++i) {
opnds[0].vbits = onehot_vbits(i, bitsof_irtype(opnds[0].type));
opnds[1].vbits = defined_vbits(bitsof_irtype(opnds[1].type));
valgrind_execute_test(op, data);
check_result_for_binary(op, data);
tests_done++;
}
}
// 2nd (right) operand
/* If the operand is an immediate value, there are no v-bits to set. */
if (!op->immediate_index) return tests_done;
num_input_bits = bitsof_irtype(opnds[1].type);
for (i = 0; i < num_input_bits; ++i) {
opnds[0].vbits = defined_vbits(bitsof_irtype(opnds[0].type));
opnds[1].vbits = onehot_vbits(i, bitsof_irtype(opnds[1].type));
valgrind_execute_test(op, data);
check_result_for_binary(op, data);
tests_done++;
}
return tests_done;
}
static value_t
all_bits_zero_value(unsigned num_bits)
{
value_t val;
switch (num_bits) {
case 8: val.u8 = 0; break;
case 16: val.u16 = 0; break;
case 32: val.u32 = 0; break;
case 64: val.u64 = 0; break;
default:
panic(__func__);
}
return val;
}
static value_t
all_bits_one_value(unsigned num_bits)
{
value_t val;
switch (num_bits) {
case 8: val.u8 = 0xff; break;
case 16: val.u16 = 0xffff; break;
case 32: val.u32 = ~0u; break;
case 64: val.u64 = ~0ull; break;
default:
panic(__func__);
}
return val;
}
static int
test_and(const irop_t *op, test_data_t *data)
{
unsigned num_input_bits, bitpos;
opnd_t *opnds = data->opnds;
int tests_done = 0;
/* Undefinedness does not propagate if the other operand is 0.
Use an all-bits-zero operand and test the other operand in
the usual way (one bit undefined at a time). */
// 1st (left) operand variable, 2nd operand all-bits-zero
num_input_bits = bitsof_irtype(opnds[0].type);
for (bitpos = 0; bitpos < num_input_bits; ++bitpos) {
opnds[0].vbits = onehot_vbits(bitpos, bitsof_irtype(opnds[0].type));
opnds[1].vbits = defined_vbits(bitsof_irtype(opnds[1].type));
opnds[1].value = all_bits_zero_value(bitsof_irtype(opnds[1].type));
valgrind_execute_test(op, data);
check_result_for_binary(op, data);
tests_done++;
}
// 2nd (right) operand variable, 1st operand all-bits-zero
num_input_bits = bitsof_irtype(opnds[1].type);
for (bitpos = 0; bitpos < num_input_bits; ++bitpos) {
opnds[1].vbits = onehot_vbits(bitpos, bitsof_irtype(opnds[1].type));
opnds[0].vbits = defined_vbits(bitsof_irtype(opnds[0].type));
opnds[0].value = all_bits_zero_value(bitsof_irtype(opnds[0].type));
valgrind_execute_test(op, data);
check_result_for_binary(op, data);
tests_done++;
}
/* Undefinedness propagates if the other operand is 1.
Use an all-bits-one operand and test the other operand in
the usual way (one bit undefined at a time). */
// 1st (left) operand variable, 2nd operand all-bits-one
num_input_bits = bitsof_irtype(opnds[0].type);
for (bitpos = 0; bitpos < num_input_bits; ++bitpos) {
opnds[0].vbits = onehot_vbits(bitpos, bitsof_irtype(opnds[0].type));
opnds[1].vbits = defined_vbits(bitsof_irtype(opnds[1].type));
opnds[1].value = all_bits_one_value(bitsof_irtype(opnds[1].type));
valgrind_execute_test(op, data);
check_result_for_binary(op, data);
tests_done++;
}
// 2nd (right) operand variable, 1st operand all-bits-one
num_input_bits = bitsof_irtype(opnds[1].type);
for (bitpos = 0; bitpos < num_input_bits; ++bitpos) {
opnds[1].vbits = onehot_vbits(bitpos, bitsof_irtype(opnds[1].type));
opnds[0].vbits = defined_vbits(bitsof_irtype(opnds[0].type));
opnds[0].value = all_bits_one_value(bitsof_irtype(opnds[0].type));
valgrind_execute_test(op, data);
check_result_for_binary(op, data);
tests_done++;
}
return tests_done;
}
static int
test_or(const irop_t *op, test_data_t *data)
{
unsigned num_input_bits, bitpos;
opnd_t *opnds = data->opnds;
int tests_done = 0;
/* Undefinedness does not propagate if the other operand is 1.
Use an all-bits-one operand and test the other operand in
the usual way (one bit undefined at a time). */
// 1st (left) operand variable, 2nd operand all-bits-one
num_input_bits = bitsof_irtype(opnds[0].type);
opnds[0].vbits = defined_vbits(bitsof_irtype(opnds[0].type));
opnds[1].vbits = defined_vbits(bitsof_irtype(opnds[1].type));
opnds[1].value = all_bits_one_value(bitsof_irtype(opnds[1].type));
for (bitpos = 0; bitpos < num_input_bits; ++bitpos) {
opnds[0].vbits = onehot_vbits(bitpos, bitsof_irtype(opnds[0].type));
valgrind_execute_test(op, data);
check_result_for_binary(op, data);
tests_done++;
}
// 2nd (right) operand variable, 1st operand all-bits-one
num_input_bits = bitsof_irtype(opnds[1].type);
opnds[0].vbits = defined_vbits(bitsof_irtype(opnds[0].type));
opnds[1].vbits = defined_vbits(bitsof_irtype(opnds[1].type));
opnds[0].value = all_bits_one_value(bitsof_irtype(opnds[0].type));
for (bitpos = 0; bitpos < num_input_bits; ++bitpos) {
opnds[1].vbits = onehot_vbits(bitpos, bitsof_irtype(opnds[1].type));
valgrind_execute_test(op, data);
check_result_for_binary(op, data);
tests_done++;
}
/* Undefinedness propagates if the other operand is 0.
Use an all-bits-zero operand and test the other operand in
the usual way (one bit undefined at a time). */
// 1st (left) operand variable, 2nd operand all-bits-zero
num_input_bits = bitsof_irtype(opnds[0].type);
opnds[0].vbits = defined_vbits(bitsof_irtype(opnds[0].type));
opnds[1].vbits = defined_vbits(bitsof_irtype(opnds[1].type));
opnds[1].value = all_bits_zero_value(bitsof_irtype(opnds[1].type));
for (bitpos = 0; bitpos < num_input_bits; ++bitpos) {
opnds[0].vbits = onehot_vbits(bitpos, bitsof_irtype(opnds[0].type));
valgrind_execute_test(op, data);
check_result_for_binary(op, data);
tests_done++;
}
// 2nd (right) operand variable, 1st operand all-bits-zero
num_input_bits = bitsof_irtype(opnds[1].type);
opnds[0].vbits = defined_vbits(bitsof_irtype(opnds[0].type));
opnds[1].vbits = defined_vbits(bitsof_irtype(opnds[1].type));
opnds[0].value = all_bits_zero_value(bitsof_irtype(opnds[0].type));
for (bitpos = 0; bitpos < num_input_bits; ++bitpos) {
opnds[1].vbits = onehot_vbits(bitpos, bitsof_irtype(opnds[1].type));
valgrind_execute_test(op, data);
check_result_for_binary(op, data);
tests_done++;
}
return tests_done;
}
int
test_binary_op(const irop_t *op, test_data_t *data)
{
unsigned num_input_bits, i, bitpos;
opnd_t *opnds = data->opnds;
int tests_done = 0;
/* Handle special cases upfront */
switch (op->undef_kind) {
case UNDEF_SHL:
case UNDEF_SHR:
case UNDEF_SAR:
return test_shift(op, data);
case UNDEF_AND:
return test_and(op, data);
case UNDEF_OR:
return test_or(op, data);
default:
break;
}
/* For each operand, set a single bit to undefined and observe how
that propagates to the output. Do this for all bits in each
operand. */
for (i = 0; i < 2; ++i) {
/* If this is a Iop that requires an immediate amount,
do not iterate the v-bits of the operand */
if (((i+1) == op->immediate_index)
&& (op->immediate_index)) break;
num_input_bits = bitsof_irtype(opnds[i].type);
opnds[0].vbits = defined_vbits(bitsof_irtype(opnds[0].type));
opnds[1].vbits = defined_vbits(bitsof_irtype(opnds[1].type));
/* Set the value of the 2nd operand to something != 0. So division
won't crash. */
memset(&opnds[1].value, 0xff, sizeof opnds[1].value);
/* For immediate shift amounts choose a value of '1'. That value should
not cause a problem. Note: we always assign to the u64 member here.
The reason is that in ir_inject.c the value_t type is not visible.
The value is picked up there by interpreting the memory as an
ULong value. So, we rely on
union {
ULong v1; // value picked up in ir_inject.c
value_t v2; // value assigned here
} xx;
assert(sizeof xx.v1 == sizeof xx.v2.u64);
assert(xx.v1 == xx.v2.u64);
*/
if (op->immediate_index > 0) {
assert((op->immediate_type == Ity_I8)
|| (op->immediate_type == Ity_I16)
|| (op->immediate_type == Ity_I32));
opnds[1].value.u64 = 1;
}
for (bitpos = 0; bitpos < num_input_bits; ++bitpos) {
opnds[i].vbits = onehot_vbits(bitpos, bitsof_irtype(opnds[i].type));
valgrind_execute_test(op, data);
check_result_for_binary(op, data);
tests_done++;
}
}
return tests_done;
}