From e96ccec8159f91d60bed8342184fb969b06eaf4f Mon Sep 17 00:00:00 2001 From: "Bobby R. Bruce" Date: Wed, 9 Oct 2019 15:20:57 -0700 Subject: [PATCH] tests,base: Added GTests for base/condcodes.hh The documentation for the "findParity" and "findCarry" functions in base/condcodes.hh has been enhanced to better explain their behavior. Change-Id: I9ba3bf68eb56529a3030e965ec21e41d2dacfad6 Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/21639 Reviewed-by: Gabe Black Reviewed-by: Bobby R. Bruce Maintainer: Bobby R. Bruce Tested-by: kokoro --- src/base/SConscript | 1 + src/base/condcodes.hh | 53 ++++++++ src/base/condcodes.test.cc | 263 +++++++++++++++++++++++++++++++++++++ 3 files changed, 317 insertions(+) create mode 100644 src/base/condcodes.test.cc diff --git a/src/base/SConscript b/src/base/SConscript index 07a76cbba..b11775daf 100644 --- a/src/base/SConscript +++ b/src/base/SConscript @@ -100,6 +100,7 @@ GTest('circlebuf.test', 'circlebuf.test.cc') GTest('circular_queue.test', 'circular_queue.test.cc') GTest('sat_counter.test', 'sat_counter.test.cc') GTest('refcnt.test','refcnt.test.cc') +GTest('condcodes.test', 'condcodes.test.cc') DebugFlag('Annotate', "State machine annotation debugging") DebugFlag('AnnotateQ', "State machine annotation queue debugging") diff --git a/src/base/condcodes.hh b/src/base/condcodes.hh index 986e8d310..d15e832c5 100644 --- a/src/base/condcodes.hh +++ b/src/base/condcodes.hh @@ -37,6 +37,46 @@ /** * Calculate the carry flag from an addition. This should work even when * a carry value is also added in. + * + * Parameters: + * dest: The result value of the addition. + * src1: One of the addends that was added. + * src2: The other addend that was added in. + * + * Rationale: + * This code analyzes the most sig. bits of the source addends and result, + * and deduces the carry out flag from them without needing the carry in bit. + * + * Observe that we have four cases after an addition regarding the carry + * in and carry out bits: + * + * If we have no carry in but a carry out: + * src1 and src2 must both be 1, with the result bit being 0. Hence, + * ~0 + 1 + 1 => 11, which has a high second bit. We return true. + * + * If we have a carry in and a carry out: + * src1 and src2 can either be 1 and 0, or vice versa. In this case, + * the addition with the carry in gives a result bit of 0 but a carry out. + * Hence, + * ~0 + 1 + 0 => 10, or ~0 + 0 + 1 => 10. We return true. + * + * Or, src1 and src2 can both be one. Along with the carry, this gives + * a result of 1 and a carry out of 1. Hence, + * ~1 + 1 + 1 => 10. We return true. + * + * If we have no carry in and no carry out: + * src1 and src2 can either be 1 and 0, 0 and 1, or 0 and 0. + * In the first two cases the result bit is 1, which when negated does not + * contribute to the sum algorithm at all. In the last case the result bit + * is zero, but neither src1 nor src2 contribute to the sum either. Hence, + * ~1 + 1 + 0 => 1, + * ~1 + 0 + 1 => 1, + * ~0 + 0 + 0 => 1. + * So we return false for all of these cases. + * + * If we have a carry in, but no carry out: + * src1 and src2 can neither be 1. So the overall result bit is 1. Hence: + * ~1 + 0 + 0 => 0. We return false. */ inline bool @@ -59,6 +99,19 @@ findOverflow(int width, uint64_t dest, uint64_t src1, uint64_t src2) { /** * Calculate the parity of a value. 1 is for odd parity and 0 is for even. + * + * Parameters: + * dest: a value to be tested. + * + * Rationale: + * findParity simply performs bitwise XOR operations on each "pair" of bits + * in the dest parameter; the procedure being that a pair of ones will be + * XOR'ed out of the intermediate value. + * + * This process is repeated until one last pair of bits are XOR'ed together. + * If the intermediate is still one, then there is exactly one high bit + * which does not have a corresponding high bit. Therefore, the value must + * have odd parity, and we return 1 accordingly. Otherwise we return 0. */ inline bool diff --git a/src/base/condcodes.test.cc b/src/base/condcodes.test.cc new file mode 100644 index 000000000..d9863be78 --- /dev/null +++ b/src/base/condcodes.test.cc @@ -0,0 +1,263 @@ +/* + * Copyright (c) 2019 The Regents of the University of California + * All rights reserved + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer; + * 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; + * neither the name of the copyright holders 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. + * + * Authors: Bobby R. Bruce + * Jared J. Barocsi + */ + +#include + +#include "base/condcodes.hh" + +/* + * Add 0x80 + 0x80 to get 0x100. findCarry should report a carry flag after + * this operation. + */ +TEST(CondCodes, FindCarryWithNoCarryIn8Bit) +{ + EXPECT_TRUE(findCarry(8, 0x100, 0x80, 0x80)); +} + +/* + * Add 0xf0 + 0x0f to get 0xff. findCarry should not report a carry flag after + * this operation. + */ +TEST(CondCodes, FindNoCarryWithNoCarryIn8Bit) +{ + EXPECT_FALSE(findCarry(8, 0xff, 0xf0, 0x0f)); +} + +/* + * Add 0x7f + 0x80 + 0x01 to get 0x100. findCarry should report a carry flag + * after this operation. + */ +TEST(CondCodes, FindCarryWithCarryIn8Bit) +{ + EXPECT_TRUE(findCarry(8, 0x100, 0x80, 0x7f)); +} + +/* + * Add 0x80 + 0x7e + 0x01 to get 0xff. findCarry should not report a carry + * flag after this operation. + */ +TEST(CondCodes, FindNoCarryWithCarryIn8Bit) +{ + EXPECT_FALSE(findCarry(8, 0xff, 0x80, 0x7e)); +} + +/* + * Add 0x80000000 + 0x80000000 to get 0x100000000. findCarry should report a + * carry flag after this operation. + */ +TEST(CondCodes, FindCarryWithNoCarryIn32Bit) +{ + EXPECT_TRUE(findCarry(32, 0x100000000, 0x80000000, 0x80000000)); +} + +/* + * Add 0xffff0000 + 0x0000ffff to get 0xffffffff. findCarry should not report a + * carry flag after this operation. + */ +TEST(CondCodes, FindNoCarryWithNoCarryIn32Bit) +{ + EXPECT_FALSE(findCarry(32, 0xffffffff, 0xffff0000, 0x0000ffff)); +} + +TEST(CondCodes, FindCarryWithCarryIn32Bit) +{ + /* + * Add 0x80000000 + 0x7fffffff + 0x00000001 to get 0x100000000, + * resulting in a carry + */ + EXPECT_TRUE(findCarry(32, 0x100000000, 0x80000000, 0x7fffffff)); + // Add 0x80000000 + 0x7ffffffe + 0x00000001 to get 0xffffffff, + // resulting in no carry + EXPECT_FALSE(findCarry(32, 0xffffffff, 0x80000000, 0x7ffffffe)); + // Add 0xffffffff + 0x00000000 + 0x00000001 to get 0x100000000, + // resulting in a carry + EXPECT_TRUE(findCarry(32, 0x100000000, 0xffffffff, 0x00000000)); +} + +TEST(CondCodes, FindCarryWithNoCarryIn64Bit) +{ + // Add 0x8000000000000000 + 0x8000000000000000 to get 0x10000000000000000, + // (unrepresentable with uint64_t), resulting in a carry + EXPECT_TRUE(findCarry(64, 0x0000000000000000, + 0x8000000000000000, + 0x8000000000000000)); + /* + * Add 0x0000000000000000 + 0x0000000000000000 to get 0x0000000000000000 + * resulting in no carry + * We get the same sum as above case due to unrepresentability, but we + * should still expect no carry + */ + EXPECT_FALSE(findCarry(64, 0x0000000000000000, + 0x0000000000000000, + 0x0000000000000000)); + /* + * Add 0x8000000000000000 + 0x7fffffffffffffff to get 0xffffffffffffffff, + * resulting in no carry + */ + EXPECT_FALSE(findCarry(64, 0xffffffffffffffff, + 0x8000000000000000, + 0x7fffffffffffffff)); + /* + * Add 0xffffffff00000000 + 0x00000000ffffffff to get 0xffffffffffffffff, + * resulting in no carry + */ + EXPECT_FALSE(findCarry(64, 0xffffffffffffffff, + 0xffffffff00000000, + 0x00000000ffffffff)); +} + +TEST(CondCodes, FindCarryWithCarryIn64Bit) +{ + /* Add 0x8000000000000000 + 0x8000000000000000 + 0x0000000000000001 + * to get 0x1 000000000000001 (unrepresentable with uint64_t), + * resulting in a carry + */ + EXPECT_TRUE(findCarry(64, 0x0000000000000000, + 0x8000000000000000, + 0x7fffffffffffffff)); + /* + * Add 0x0000000000000000 + 0x0000000000000000 + 0x0000000000000001 + * resulting in no carry + * We get the same sum as the above case due to unrepresentability, but we + * should still expect no carry + */ + EXPECT_FALSE(findCarry(64, 0x0000000000000001, + 0x0000000000000000, + 0x0000000000000000)); + /* + * Add 0x8000000000000000 + 0x7fffffffffffffff + 0x0000000000000001 + * to get 0x1 0000000000000000 (unrepresentable with uint64_t), + * resulting in a carry + */ + EXPECT_TRUE(findCarry(64, 0x0000000000000000, + 0x8000000000000000, + 0x7fffffffffffffff)); + /* + * Add 0xffffffff00000000 + 0x000000000000000 + 0x0000000000000001 + * to get 0x1 0000000000000000 (unrepresentable with uint64_t), + * resulting in a carry + */ + EXPECT_TRUE(findCarry(64, 0x0000000000000000, + 0xffffffffffffffff, + 0x0000000000000001)); +} + +TEST(CondCodes, FindOverflow8Bit) +{ + /* + * Addition of 127 + 1 = 128 or -128 as signed two's complement. + * Overflow occurs in this case + */ + EXPECT_TRUE(findOverflow(8, 0x80, 0x7f, 0x01)); + /* + * Addition of 64 + 63 = 127, or 127 as signed two's complement. + * No overflow occurs + */ + EXPECT_FALSE(findOverflow(8, 0x7f, 0x40, 0x3f)); +} + +TEST(CondCodes, FindOverflow32Bit) +{ + /* + * Addition of 2,147,483,647 + 1 = 2,147,483,648, or -2,147,483,648 as + * signed two's complement. Overflow occurs in this case + */ + EXPECT_TRUE(findOverflow(32, 0x80000000, 0x7fffffff, 0x00000001)); + /* + * Addition of 1,073,741,824 + 1,073,741,823 = 2,147,483,647, or + * 2,147,483,647 as signed two's complement. No overflow occurs + */ + EXPECT_FALSE(findOverflow(32, 0x7fffffff, 0x40000000, 0x3fffffff)); +} + +TEST(CondCodes, FindOverflow64Bit) +{ + /* + * Addition of 0x7fffffffffffffff + 0x0000000000000001 = + * 0x8000000000000000, or -9,223,372,036,854,775,808 as signed two's + * complement. Overflow occurs in this case + */ + EXPECT_TRUE(findOverflow(64, 0x8000000000000000, + 0x7fffffffffffffff, + 0x0000000000000001)); + /* Addition of 0x4000000000000000 + 0x3fffffffffffffff = + * 0x7fffffffffffffff, or 9,223,372,036,854,775,807 as signed two's + * complement. No overflow occurs + */ + EXPECT_FALSE(findOverflow(64, 0x7fffffffffffffff, + 0x4000000000000000, + 0x3fffffffffffffff)); +} + +TEST(CondCodes, OddParity) +{ + EXPECT_EQ(1, findParity(8, 1)); +} + +TEST(CondCodes, EvenParity) +{ + EXPECT_EQ(0, findParity(8, 3)); +} + +TEST(CondCodes, OddParityOverflow) +{ + EXPECT_EQ(1, findParity(8, 0x102)); +} + +TEST(CondCodes, EvenParityOverflow) +{ + EXPECT_EQ(0, findParity(4,0x43)); +} + +TEST(CondCodes, IsNegative) +{ + EXPECT_EQ(1, findNegative(8, 128)); +} + +TEST(CondCodes, IsNotNegative) +{ + EXPECT_EQ(0, findNegative(8, 127)); +} + +TEST(CondCodes, IsZero) +{ + EXPECT_EQ(1, findZero(8, 0)); +} + +TEST(CondCodes, IsNotZero) +{ + EXPECT_EQ(0, findZero(8, 1)); +} + +TEST(CondCodes, IsZeroOverflow) +{ + EXPECT_EQ(1, findZero(8,0x100)); +} -- 2.30.2