IntegerOperators < P1076

P1076 Web>Vhdl2019CollectedRequirements>IntegerOperators (2020-02-17, JimLewis) (raw view)EditAttach
---+ Additional Operators to Integers

%TOC%

---++ Proposal Information
   * Who Updates: Main.JimLewis
   * Date Proposed: 2013-12-07
   * Date Last Updated: -- Main.YannGuidon - 2014-10-24
   * Priority:
   * Complexity: low/small (hundreds of lines of code ?)
   * Focus: General Language
---++ Language Change Specification Link

[[TopLCS2016_051][LCS-2016-051]]
---++ Summary

Just add logic, shift and rotate operators for integers. Nothing fancy.

Needed for replacing arithmetic operators used as boolean operators, which loses semantic, time and flexibility.

For example, a masking operation on coverage modeling:

<verbatim>Y <= A and 16#FF# ;  -- instead of Y <= A mod 65535;</verbatim>

This use of mod can only work if contiguous LSB are set (otherwise this leads to weird results or overly complex composite expressions)

Other cases of arithmetic kludges :

- =NOT= is emulated by (-x)+1 for a 2s-complement computer.

- =OR= can be emulated by integer "+" but it only works if the set bits of both operands don't overlap (or else, the result is wrong because of carries)

- =XOR= is impossible to emulate completely and correctly with only a few arithmetic operators.

- =SRA= can be implemented by a division by 2**N but negative numbers might get an off-by-one adjustment to preserve arithmetic (but not boolean) accuracy.

- =SRL= can be emulated by masking SRA's result, the expression starts to become unreadable/unmaintainable

- =ROL= and =ROR= : too much complexity

This set of operators is not primarily intended to speed up simulation, other types are specific for this purpose and are sometimes well optimised (bit_vector, std_(u)logic_vector, (un)signed). The integer boolean operators are meant to extend the communication and interfacing capabilities of simulators so they provide richer sources and sinks of data. However it would make no sense to restrict the use of these operators.

Some practical applications :

- pseudo-random generators (LFSR) to create test vectors (you can shift left by adding the register to itself, but how do you XOR ?)

- import and export compressed data (either test vectors such as signals or raster graphics, or export signal dumps) with LZW, LZMA, GZIP coded in VHDL

- high-level model of the Design Under Test to test against (if one wants to test a graphics or cryptographic function)

- communication over a network (adapt endianness, pack values and bits in network frames...)

To be fully consistent, this proposal goes hand in hand with another proposal, which provides the necessary safety and wrap-around, by extending the RANGE mechanism to provide "modular" behaviour.

---+ Proposal

That operators =not, and, or, xor, nand, nor, xnor, srl, sll, sra, sla, ror, rol= be defined for INTEGER (and NATURAL ?) types.

They will operate on numbers represented as 2-s complement, whatever the size of the platform's integer type.

To get valid results, the user should constrain the destination variable to a suitable range, with "range" or "modular" modifiers. The (upcoming) modular attribute will wrap results around and keep the requested number of LSB. In this case, the range should be a power of two such as "0 to (2**n)-1" (which makes it a NATURAL). Otherwise, the simulator could raise a warning and the operation or the assignation might raise an error because "It is an error if the execution of such an operation (in particular, an implicit conversion) cannot deliver the correct result. "

When used as intended (with a power-of-two "modular" attribute),

- The result of most operators is simply masked out by the result variable's 'high attribute.

- =sra=, =rol= and =ror= get properly handled, so the MSB is the reduced range's MSB, not the integer's MSB (usually at bit position 31).

The result is undefined (and implementation-dependant, or throw an error) if the ='low= attribute is not 0. The eventual direction ( =to= / =downto=) has no effect.

The operators will have their conventional mathematical meanings (in particular note that =sla= will fill the lsb with 0). LSBs "dropped off" the right hand side by a right shift are discarded.

<verbatim>-- example with and without range
constant a: integer range 249 to 256 :=  254;
constant b : integer range 0 to 7 := 7;
constant c : integer := -7;
a and b = 6
a or b = 7
a sll 1 = 508
a sla 1 = 508
a srl 1 = 127
a sra 1 = 127
c sra 1 = -3
c ror 1 = -3
c rol 1 = -13
INTEGER'HIGH sla 1 = ERROR</verbatim>

Note 1 : with integer width equal to N bits (usually 32, may be 64), it's not possible to define a variable that is "0 to (2**N)-1" because this overflows the positive range of the signed variable (a set MSB represents a negative number in 2s complement). In this case, the variable should be simply of un-ranged integer type. The user should first check the host's integer range to preserve portability.

Note 2: this proposal is independent of the integer size or host preferred size. The recent proposal of a "universal integer" ( http://www.eda.org/twiki/bin/view.cgi/P1076/ArbitraryIntegers and/or similar) should not affect this proposal.

Note 3 : the operators =sra=, =ror=, =rol= must check the 'high attribute, and perform correctly.

- =srl= works as expected, independently of the number of bits, because the MSB is always filled with 0. The LSB is dropped.

- =sla= and =sll= work as expected, independently of the number of bits, because the LSB is always filled with 0. The MSB get masked out by the modular mask during assignation to the destination variable.

- =sra= must first be "sign extended" because the actual operation will replicate cleared MSBs

Example :

=subtype m32 : integer modular 0 to 31;=

variable i32, j32 : m32;

i32 := 28 ; -- represents -4 in 2s complement

=j32 : i32 sra 1; -- j should not be 14, but (-4 sra 1) = -1 = 30=

- =ror= and =rol= must wrap around at the correct MSB, not the integer type's MSB (usually at position 31 or 63)

The other boolean operators ( =not, and, or, xor, nand, nor, xnor=) do not need special care because the result is truncated before it is written to the destination. They can be directely implemented using the host's CPU instruction.
---++ Supporters

_Add your signature here to indicate your support for the proposal_

_-- Main.JimLewis - 2013-12-09_

-- Main.YannGuidon - 2014-10-17 (see also [Modular Types] ) <br /> - 2014-10-23 : removed the constraint on the integer size and defered the error logic on the range/modular mechanics.

-- Main.MortenZilmer - 2015-01-21

---++ Opposers

-- Main.ErnstChristen - 2015-01-21 - Integer types in VHDL have always been abstract types. This proposal intends to add semantics related to some representation in hardware. Bridging this gap should be done, if at all, in a larger context and include supporting encodings for enumeration literals.
---++ Comments on proposal

It is accepted that this proposal limits implementation flexibility for integer types, in favour of an easily understood (and described!) set of operators. Tools are still free to use different representations for integer types where these operations are not performed on them.

Also note that there is nothing (functionally) to actually stop this being implemented as a package, which maybe counts against it being added to the language, although it may be quite inefficient. For example:

<verbatim>function "and" (a,b : in integer) return integer is
  begin
    return to_integer(to_signed(a, 32) and to_signed(b, 32));
  end;</verbatim>

Finally note that similar discussions are taking place regarding logical operations on arbitrary sized Integers: ArbitraryIntegers
---

[TristanGingold] (reflector 2014-10-22)

I think we are approaching the point where this proposal raises a lot of issues.

The range of integers types (including the type INTEGER) is not specified by the standard. The standard simply says the range should be large enough to contain the subtype range.

So consider a integer type declaration:

type int7 is range 0 to 7;

The implementation may choose to use a 8 bit or a 16 bit or a 32 bit type for int7. So the result of: not int7'(3) would be implementation dependent. Arg, this is not a good idea.

Maybe you may propose to restrict the use of logical operators only to the type STD.STANDARD.INTEGER. First, that would be weird, and second that won't be more portable. The standard doesn't prevent INTEGER to be a 64bit types.

Given the above reasons, I think it wouldn't wise to add logical operators to integer types (even the C language makes this operation implementation defined in many cases). If you want logical operators, it should be on modular power of 2 types.

---

-- Main.YannGuidon - 2014-10-23

@TristanGingold : I try to fix that in this new version.
---++ Early discussion

-- Main.DavidKoontz - 2013-12-08

Today there is no fixed relationship between an integer type and an underlying implementation. With suffcient accuracy an integer can be adequately stored in a floating point format, or a BCD format. Trying to enforce a bitwise relationship through logical operators that enforce a relationship to a binary array is implementation restrictive. There's also suddenly an implication that the range of an integer above the minimum ranges be expressable as a power of two.

<img alt="" height="266" src="http://www.math.uwaterloo.ca/~snburris/htdocs/SEGS_CUT/TEX/FIG/bin_tree_b.gif" title="binary tree bit representation" width="431" />

This is image showing the relationship between bits P1,P2,P3,... (it's a borrowed image) and not shown, an eventual array of index values representing the numerical range of index values. Essential a bitwise representation a vector spline traversing bits to an index value.

Today, integer types do not have that relationship instead having only an index range, representing a numerical value, and that value can be mapped according to range.

So far IntegerOperators don't appear to take into account subtype indications (range constraints), which also run foul of power of two issues.

There's also the issue that there are already scalar array types (e.g. BIT_VECTOR, SIGNED, UNSIGNED and STD_LOGIC_VECTOR) that have a bit array representation useful for logical operations as well as adding, multiplying and and shift operators.

-- Main.JimLewis - 2013-12-08

It is even more interesting since we have proposals for increasing the length of integers. None the less, there are logical operations that make sense. Masking for example. When I read a value, I may get 32 bits, however, I may only be interested in the lower 16 bits, so the following is a valuable operation:

<verbatim>Y <= A and 16#FF# ;</verbatim>

I suppose this could be implemented with "mod" instead, however, for a masking operation do you consider this more readable?

<verbatim>Y <= A mod 16#100# ;</verbatim>

Why integers and not a type signed or unsigned? Integers store smaller and for operations such as addition, subtraction, and multiplication, they simulate faster. As long as we do not need to represent 'X' or 'Z', integers offer a significant advantage. Hence for data structures - such as functional coverage modeling, they result in significantly less storage. Given that programming languages like C implement these operations on integers, then I would expect that we would not have a problem.

-- Main.DavidKoontz - 2013-12-09

A programming language like C doesn't allow you to arbitrarily constrain the range of an integer. While such a subtype would be closely related and adding or multiplying would work, bitwise operators aren't so straight forward. for an integer constrained to a range of say 157 to 160 we get binary representations 10011101, 10011110, 10011111, 10100000. There isn't a single bit mask value that can represent that range (it takes three).

It sounds like what you want is an new integer type that can't be constrained, can have a bit relationship established with it's range sort of like those other HDLs.

-- Main.JimLewis - 2013-12-09

It is not about whether there are some things that don't fit in the box, it is about how many practical things that do. And by the way, the problem you suggest above is simply the following:

<verbatim>subtype IntDKType is integer range 157 to 160 ;
signal IntDk : IntDkType ;
signal Masked : integer ;
...
Masked <= (IntDk - IntDkType'left) and 16#3# ;</verbatim>

-- Main.DavidKoontz - 2013-12-09

Range 256 to 260 (10000, 10001, 10010, 10011, 10100) normalizes to 0 through 4 ( 000, 001, 010, 011, 100, basically non-powers of two) and all the sudden you get a range constraint error on the AND operation and you're back to if then else/else if statements or case statements and relational operators for non-power of two index range constraints, even normalized. Do some adding or multiplying operators and you're re-normalizing, a characteristic not shared with bit operations on fixed range integers in say C.

It's also likely you could optimize bit vectors speed and size (bit packing) giving that natural power of two relationship necessary to implying arithmetic and bit oriented operations. The same person speculating along those lines today has previously noted Ada95's added modular types provide the logical operator functionality you describe albeit for a smaller set of operators while functioning as an unsigned integer.

-- [[Main.BrentHahoe][Brent Hayhoe]] I'm leaning more twoards David's side in this discussion.

I think we need to define the requirement a bit more. When I first started reading this, my first thought was 'masking' and sure enough that was Jim's first example.

Next, I started thinking this is very 'C'ish in its style and with 'C' modeling I always consider intergers as 32bit unsigned vectors.

Given this and ignoring the verbosity for now, isn't what we require already provided in VHDL as shown:
<verbatim>    Y <= To_Integer(To_Unsigned(A, 32) and X"FF") ;</verbatim>

Is this the type of thing that this proposal is trying to achieve?

-- [[Main.BrentHahoe][/Brent Hayhoe/]] - 2013-12-09

-- Main.DavidKoontz - 2013-12-09

With respect to Brent's example with the conversion functions you could note that numeric_bit also includes a type UNSIGNED opening the possibility of bit_vector acceleration in tool implementation. To allow numeric_bit and numeric_std to be used concurrently implies selected names for integer conversion TO_UNSIGNED or TO_SIGNED. It also says you could implement IntegerOperators in a package, sacrificing Jim's size and speed for clarity of definition noting to date shift operators haven't been mentioned and allowing demonstration of use cases and limitations.

-- Main.TristanGingold - 2014-10-21

I agree with David. In VHDL integer, physical and enumerated types closely follow the mathematical types. You don't know how they are represented in memory (and you don't need to). Furthermore, in C most of the logical operations are not completly defined (what is the result of '&' on a negative value ?) for good reasons, and I prefer to avoid adding undefined behaviour to VHDL.

If you need logical operations, use logical types (std_logic or bit). If they aren't fast enough, complain to your vendor.

<p/>
Main.RyanHinton: Quoting Tristan from a different thread, "computer language is not mathematics."  I heartily agree with the sentiment in the Summary section above that when I'm working with communications, interfaces, and algorithms -- especially those involving data from the outside world -- I really want to be able to easily port a reference implementation of GZIP or raster graphics or network protocol bit fiddling using =integer= variables.

-- Main.RyanHinton - 2016-12-14


---++ General Comments

There is similar/additional discussion in [[ModularTypes][Modular Types]]

-- Main.YannGuidon - 2014-07-24
<div id="_mcePaste" style="position: absolute; left: -10000px; top: 3489px; width: 1px; height: 1px; overflow: hidden;">

srl works as expected, independently of the number of bits, because the MSB is always filled with 0.
---++ 
</div>
Topic revision: r24 - 2020-02-17 - 15:34:34 - JimLewis
P1076