[myhdl-list] Wrap-around support in MyHDL

[Jan D. <ja...@ja...>]

Recently, there has been a lot of activity regarding
"wrap-around" types. I have looked at the proposals. My own
thoughts on the matter have evolved also. Here is my
analysis and proposal.

Background
----------

One my main critiques on the mainstream use of Verilog/VHDL
is the focus on "representational" types for integer
arithmetic. In other words, the starting point is a bit
vector representation to which an integer interpretation is
added later. The hidden assumption is that this is necessary
for implementation efficiency.

I believe that MyHDL has convincingly demonstrated that
there is a better way by taking a top-down perspective. In
MyHDL, integer arithmetic simply works as expected. The
convertor takes care of representational details as required
by the Verilog/VHDL target.

This is not just a semantic discussion. In MyHDL, you don't
need castings, manual sign extentions or resizings to get
integer arithmetic to work. In Verilog/VHDL, it's the name
of the game. Best of all, there is no implementation
efficiency price to pay.

Understandably, I would like to use a similar approach when
considering to introduce new types: first look at the
modelling aspect, that is, how a designer would prefer to
use a type, and only then move to conversion and efficiency
concerns.

Wrap-around type proposals
--------------------------

There is no question that there is a genuine need for the
elegant modeling of wrap-around behavior in hardware
modeling. The question is whether this is important enough to
warrant dedicated language support.

In the past, I have suggested that this need may not be that
high. For example, in the common case of an incrementer (or
decrementor), it is often necessary to decode the end count
anyway:

     if count == N:
        count.next = 0
        # decode action
     else:
         count.next = count + 1
    
However, I would agree that even then it could be clearer to
keep the incrementer description separate from the decoding:

     if count == N:
         # decode action

     count.next = (count + 1) % N

I have also argued that the modulo operator offers an
explicit and elegant high-level solution to describe
wrap-around behavior in a one-liner. Chris F has pointed out
that this doesn't work for the case of a signed integer. He
has proposed a .wrap() method as a solution.

Both the modulo operator and a wrap() method have some
disadvantages. Through they are explicit in good Python
style, there is a conflict with another good principle: DRY
(Don't Repeat Yourself). If wrap-around is the desired
behavior, it is probably a property of an object and its
type, not of a particular assignment.

The two techniques have another problem that I have
successfully managed to keep out of spotlights in earlier
discussions :-) I believe a common use case would be an
incrementor/decrementer as an intbv variable, using augmented
assignment:

    count += 1

The two techniques above cannot support this.

Tom D has proposed a 'wrap' parameter to the intbv
constructor, with default False. When True, it would modify
the assignment behavior as desired.

This proposal addresses the issues mentioned above, but has
some problems itself.  An additional parameter makes object
construction heavier. Also, the use of a default value
suggests that one type of behavior is the rule, and the
other the exception.  I don't like the idea of modifying the
fundamental behavior of a type in such a way.  If
wrap-around behavior is considered important enough to
warrant direct language support, it should be as easy to use
as other behaviors.

Finally, a parameter cannot support the following conversion
trick:

    a = intbv(0)[N:]

to construct a "N bits wide" positive intbv, even though
such "closer to hardware" objects are probably popular
candidates for wrap-around behavior.

The most important problem that I have with the current
proposals is still elsewhere: they go against the
MyHDL-specific philosophy that I outlined in the
background. The starting point of the proposals is that
wrap-around behavior will only supported on "full range"
bit-vectors. This is likely influenced by implicit
assumptions of efficient hardware implementation.

In my modeling work, I use wrap-around counters all the
time. However, more often than not, their bounds are not
powers of 2. I suspect this is the same for many
designers. As I have argued earlier, we should look at
modeling first, and at hardware efficiency later. In
previous cases, such as the intbv type, we have been able to
achieve much easier modeling without having to pay a price
in efficiency.

Ada modular types
-----------------

Recently I got introduced to Ada modular types. These are
natural integer types with wrap-around behaviour.

The wrap-around behavior of modular types is based on the
sound mathematical concept of modulo arithmetic. Therefore,
the modulus is not limited to powers of 2.

The rationale behind modular types is interesting. For
example:

"The modulus of a modular type need not be a power of two
although it often will be. It might, however, be convenient
to use some obscure prime number as the modulus perhaps in
the implementation of hash tables."

[http://www.adaic.org/resources/add_content/standards/95rat/rat95html/rat95-p2-3.html]

Another resource says:

"Modular types don't need to be powers of two, but if they
are the Ada compiler will select especially efficient
operations to implement them."

[http://www.dwheeler.com/lovelace/s17sf.htm]

This is exactly the kind of reasoning I'm looking for. Ada
considers module arithmetic important enough to warrant
direct language support, but in the general, mathematically
sound sense. On the other hand, it recognizes that
powers of 2 bounds are very important. There is actually a
predefined package with power of 2 based subtypes. Moreover,
the compiler can select "especially efficient operations" to
implement them.

Interestingly, Ada even defines and/or/xor bit operations on
modular types, unlike other integer types. Apparently it
chooses modular types for this purpose because their
"unsigned" interpretation poses less problems than bit
operations on "signed" representations. In any case, the
dual nature of the type - both high-level and
representation-friendly - is similar to what MyHDL does with
the intbv. When reading all this, I can only conclude that
VHDL lost a big opportunity by forgetting about its origins.

I believe the Ada example is the route to follow. Two issues
still have to be addressed:

1) Ada modular types are restricted to natural values.
We want to support integer values.
2) Ada modular types are types, which means that conversions
would be needed to let them work with other integer-like
types. (I am not entirely sure of this statement.)

A proposal for MyHDL: the modbv type
------------------------------------

Ada's modular type is called 'mod'. By analogy, I am
proposing a 'modbv' type in MyHDL. Behaviorally, the only
difference with intbv would be how bounds are handled:
out-of-bound values result in an error in the intbv, and
wrap-around in the modbv. In particular, modbv would have
exactly the same interface as the intbv. Wrap-around
behavior would be defined as follows:

    val = (val - min) % (max - min) + min

Unlike Ada, intbv and modbv would be subtypes of a general
integer-bitvector type. Therefore, they can be mixed
transparantly in expressions. This should be not problem as
the bound handling only occurs at assignment time in the
assigned object.
           
This proposal addresses the issues mentioned earlier. In
particular:

     count += 1

and

     count = modbv(0)[32:]

would have wrap-around behavior.

Implementation notes
--------------------

Technically, the cleanest implementation would probably be
to make both intbv and modbv a subtype of some general
integer-bitvector class. In a first phase, it would
probably be OK to simply subclass intbv.

To make this kind of subclassing possible, the intbv class
has to be made more robust. For example, at some points were
it returns a literal 'intbv' object, it should use the
actual subtype itself.

The basic difference with intbv is bound
handling. Currently, this is already done in a separate
method called intbv._checkBounds(). This method should
probably be renamed to intbv._handleBounds(), and then
overwritten with the proper behavior in the subclass.

Conversion notes
----------------

It is expected that conversion would work directly for the
case of "full range" modbv objects. (Note that it is not
sufficient that both bounds are powers of 2.) In a first
phase, the convertor could impose that restriction.

To demonstrate the advantage of the chosen approach, we
could attempt to lift some restrictions for interesting use
cases. For example, a common use case for wrap-around
behavior would be incrementors and decrementors. The
analyzer could detect such cases and mark them. For such
patterns, we could then support general wrap-around for non
full-range objects also. For example:

     count.next = count + 1

would be converted to:

     if count == MAX-1:
         count.next = MIN
     else:
         count.next = count + 1

It is probably possible to remove more restrictions in a
gradual process. When doing so, we would be adding items to
the list of useful features that MyHDL can fully support,
even though they have no native support in Verilog/VHDL. At
some point, this list of features, unique to MyHDL, could
become very attractive to Verilog/VHDL designers.


-- 
Jan Decaluwe - Resources bvba - http://www.jandecaluwe.com
     Python as a HDL: http://www.myhdl.org
     VHDL development, the modern way: http://www.sigasi.com
     Analog design automation: http://www.mephisto-da.com
     World-class digital design: http://www.easics.com