Summator simulation

Question

This is a reference implementation of a summation unit. The algorithm used is a most straightforward carry-propagation. If necessary, a test driving code could be provided.

Few notes for the reviewers:

The code does compile and works indeed. Test harness is available on demand.
I am a steadfast proponent of descriptive names. This is a rare case where one-letter names are descriptive. N,Z,C,V were adopted and blessed by generations of designers. Calling the flag overflow instead of V would sound like a blasphemy.
Validity of register indices is intentionally not verified. Just pretend that they are always valid.
For a V calculation, refer to this wonderful explanation

Looking for an Ultimate Review of the Clarity, the Universe and Everything.

#include <vector>
#include <limits>
#include <algorithm>
#include <ostream>

template<typename Int>
struct GPR {
    std::vector<bool> bits;

    GPR(): bits(std::numeric_limits<Int>::digits, false) {};
    ~GPR() { delete bits; }

    bool sign() const { return bits.back(); }

    auto begin()  -> decltype(bits.begin())  { return bits.begin(); }
    auto end()    -> decltype(bits.end())    { return bits.end(); }
    auto rbegin() -> decltype(bits.rbegin()) { return bits.rbegin(); }
    auto rend()   -> decltype(bits.rend())   { return bits.rend(); }

    void load(Int value) {
        for(auto it = begin(); it != end(); ++it) {
            *it = value & 0x01;
            value >>= 1;
        }
    }

    void store(Int& value) {
        for(auto it = rbegin(); it != rend(); ++it) {
            value <<= 1;
            value |= *it;
        }
    }

    friend std::ostream& operator<<(std::ostream& os, GPR& reg) {
        std::copy(reg.begin(), reg.end(), os);
        return os;
    }
};

template<typename Int>
class CPU {
    struct flags {
        bool N;
        bool C;
        bool Z;
        bool V;
        flags(): N(false), C(false), Z(false), V(false) {}
        friend std::ostream& operator<<(std::ostream& os, flags& f) {
            os << f.N << f.C << f.Z << f.V;
            return os;
        }
    };

    struct adder {
        flags& f;
        adder(flags& f): f(f) {}
        bool operator()(bool x, bool y) {
            bool s = x ^ y ^ f.C;
            f.C = x & y | f.C & (x ^ y);
            f.Z &= !s;
            return s;
        }
    };

    flags flags;
    std::vector<GPR<Int> > regfile;

    void add_internal(GPR<Int>& r1, GPR<Int>& r2) {
        bool s1 = r1.sign();
        bool s2 = r2.sign();
        flags.Z = true;
        std::transform(r1.begin(), r1.end(), r2.begin(), r1.begin(), adder(flags));
        flags.N = r1.sign();
        flags.V = !(s1 ^ s2) & (s1 ^ r1.sign());
    }

public:
    CPU(int regs): regfile(regs) {}

    void add(unsigned rx1, unsigned rx2) {
        flags.C = false;
        add_internal(regfile[rx1], regfile[rx2]);
    }
    void addc(unsigned rx1, unsigned rx2) {
        add_internal(regfile[rx1], regfile[rx2]);
    }

    void load(unsigned rx, Int value) {
        regfile[rx].load(value);
    }
    void store(unsigned rx, Int& x) {
        regfile[rx].store(x);
    }
};

Nobody moving away from SE · Accepted Answer · 2014-09-04 16:25:56Z

First of all I would like to dispute your assertion that the one letter names are descriptive. The only people how will find them descriptive are those who are used to them but readers that have no understanding of the topic are at a total loss here (not having any comments on the variables reinforces this).

But this is only my opinion.

On to more substantial problems:

Using `vector<bool>` considered harmful?

I see that you are using the dreaded vector<bool>. I also see that you don't change its size after initialization and that the size is known at compiletime. Together with the fact that you are doing bit manipulations this calls for a std::bitset.

However, fact that vector<bool> offers these nice iterators that you can use with the standard algorithms might be enough of a reason to use it nonetheless.

`delete std::vector()`?

Why are you deleting a non pointer in GPR's destructor:

std::vector<bool> bits;
//...
~GPR() { delete bits; }

I am nearly certain that this should be a compiler error (although my compiler only warns about it)

C++11

Why didn't you use a range based for in GPR::load?

for(auto &currentBit: bits) {
    currentBit = value & 0x01;
    value >>= 1;
}

Using boost's reversed range adaptor you could also do this in store.

Compiler warnings about operator order

Compiling your code gave me warnings about recommended parentheses on:

f.C = x & y | f.C & (x ^ y);

and

flags.V = !(s1 ^ s2) & (s1 ^ r1.sign());

Output order of the bits of reg

You output the bits in reg with the least significant coming first and the sign last. Is this intended?

std::copy(reg.begin(), reg.end(), os);

Or should it be

std::copy(reg.rbegin(), reg.rend(), os);

And while we are at it you surely mean std::ostream_iterator<bool>(os) instead of os.

Flag Output

The output for the flags is only understandable when you read the code and see the order. At the very least I would output the flag "descriptor" instead of 0 or 1 to better indicate which flags are set.

You could use the case to identify the flag or simply leave out those that are not set.

Extract non template members

Neither flags nor adder depend on the template parameter of CPU so you should take it out of the that class to avoid code bloat due to unnecessary multiple instantiations.

If you insist on making them private members than you should put them in a non templated base class for CPU.

Naming

the member variable CPU::flags shadows the member struct CPU::flags
adder -> BitAdder (or bit_adder but I would choose the former to distinguish class and function names)
regfile -> registers (although the former might be more domain specific)

Side effects in functors are OK in C++11, as long as you don't modify elements of the range or invalidate iterators. — Aurelius
– Aurelius, Commented Sep 4, 2014 at 16:23
@Aurelius: Thanks, I did not know that. How much does the C++11 standard mandate then? Would an implementation be allowed to parallelize std::transform (which would break this code)? — Nobody moving away from SE
– Nobody moving away from SE, Commented Sep 4, 2014 at 16:28
Those are the only requirements I can find. I don't know whether parallelization is allowed. The wording would suggest that it is, though I would be surprised if an implementation actually did this. The more important consideration is that transform() is not guaranteed to traverse the range in order, which seems to break the assumptions in adder. — Aurelius
– Aurelius, Commented Sep 4, 2014 at 16:53
@Aurelius: Which is what I actually was after. Having read the last standard draft on transform did not show any limitations. The only requirements for transform are to call the function with the correct input iterators and assign the result to the corresponding output iterator, no word about order. But why did they drop the side effect wording in the first place if the possible reording bites you in many cases. — Nobody moving away from SE
– Nobody moving away from SE, Commented Sep 4, 2014 at 17:03
I'm not privy to their reasoning, but I can imagine side effects that aren't dependent on application order. A contrived example: a static variable which counts the number of times the functor was applied. — Aurelius
– Aurelius, Commented Sep 4, 2014 at 17:08

Aurelius · Accepted Answer · 2014-09-05 17:43:22Z

In addition to Nobody's excellent answer, there are some other improvements which can be made.

Header organization

Order your headers alphabetically -- it becomes easier to remove duplicate includes, and is just more organized.

`const`-correctness

Mark variables and function parameters which are only read as const. This guarantees they can't be accidentally modified, and makes your code easier to reason about.

Additionally, you do not provide const overloads for your begin() and end() functions, which you should do. Currently it is impossible to use these methods on a const object or reference.

Iterator typedefs

It looks like you want to treat GPR as a container type. In that case, you should add iterator typedefs like those found in standard-library containers, since some algorithms may depend on their existence. For example,

using iterator = std::vector<bool>::iterator;
// add the rest...

Then you can change the declarations of begin() and company to

iterator begin() {return bits.begin();}

instead of using auto and decltype, which I find more difficult to understand.

`transform()` portability

Your adder functor assumes that transform() will call it in order starting with begin() and ending at end(). This is not the case: transform() does not guarantee a particular iteration order. Since C++ doesn't allow you to zip ranges easily, the best portable equivalent I can come up with is this:

adder add(flags);

auto it1 = r1.begin();
auto it2 = r2.begin();
for (; it1 != r1.end() ||  it2 != r2.end(); ++it1, ++it2)
{
    *it1 = add(*it1, *it2);
}

Public exposure of `bits`

You expose the bits member of the GPR struct. This exposes an implementation detail unnecessarily. You should make bits private, and probably change GPR to a class.

Stack Exchange Network

Summator simulation

2 Answers 2

Using `vector<bool>` considered harmful?

`delete std::vector()`?

C++11

Compiler warnings about operator order

Output order of the bits of reg

Flag Output

Extract non template members

Naming

Header organization

`const`-correctness

Iterator typedefs

`transform()` portability

Public exposure of `bits`

You must log in to answer this question.

Hot Network Questions

Summator simulation

2 Answers 2

Using vector<bool> considered harmful?

delete std::vector()?

C++11

Compiler warnings about operator order

Output order of the bits of reg

Flag Output

Extract non template members

Naming

Header organization

const-correctness

Iterator typedefs

transform() portability

Public exposure of bits

You must log in to answer this question.

Related

Hot Network Questions

Using `vector<bool>` considered harmful?

`delete std::vector()`?

`const`-correctness

`transform()` portability

Public exposure of `bits`