saturating

Saturating data types

The goal of this proposal is to introduce a new integer data type to enable saturating arithmetic. For these data types, all operations such as addition and multiplication are limited to a fixed range between a minimum and maximum value. We proposed to introduce both signed and unsigned saturating integers. Some ASIC platforms natively support saturating arithmetic due to its practical advantages. According to Wikipedia (https://en.wikipedia.org/wiki/Saturation_arithmetic) the result of saturating arithmetic is as numerically close to the true answer as possible; for 8-bit binary signed arithmetic, when the correct answer is 130, it is considerably less surprising to get an answer of 127 from saturating arithmetic than to get an answer of −126 from modular arithmetic. Likewise, for 8-bit binary unsigned arithmetic, when the correct answer is 258, it is less surprising to get an answer of 255 from saturating arithmetic than to get an answer of 2 from modular arithmetic.

Note that P4_14 supports saturating arithmetic using the saturating modifier applied to fields, counters, registers, Section 9.1.1 in the P4_14 specification v1.0.4 discusses the saturating attribute.

Status quo

There is currently no support for saturating arithmetic in P4_16.

Design

We propose to add two new data types for saturating arithmetic in P4_16, saturating_bit<W> and saturating_int<W>, for unsigned and signed fixed-width saturating integers, respectively.

We still get away without the need to support arithmetic exceptions in P4, as there is no overflow or underflow for saturating arithmetic.

We propose that saturating arithmetic is supported for a limited set of operations: addition, subtraction, and multiplication, as well as equality, inequality, and comparison operations. We do not support saturating division. Bitwise operations are not supported.

Explicit casting is allowed between saturating and modular integers, with appropriate sign extension, clamping, or truncation.

Fixed-width unsigned saturating integers

A saturating unsigned integer is declared using saturating_bit<W>. It has a bit-width of W, and thus will have a minimum value of 0 and a maximum value of 2^W^-1. W must be a compile-time known value.

Operations on fixed-width unsigned saturating integers

As opposed to the modular arithmetic supported with bit<W>, saturating arithmetic will clamp the value of the result to either the minimum or maximum value supported by the data type.

All binary operations require both operands to have the same exact type, saturating, signedness, and width. Supplying operands of different types produces a compile-time error. No implicit casts (conversions) are inserted by the compiler to equalize the types. P4 does not support any binary operations that combine saturating and modular arithmetic, except cast.

The saturating_bit<W> datatype supports the following operations:

• Addition, denoted by +. Example:

saturating_bit<W> a, b;
int tmp = a + b;
if (tmp < a.min)      // a.min = 0
    a.min
else if (tmp > a.max) // a.max = 2^W-1
    a.max
else
    tmp

• Subtraction, denoted by -.
• Multiplication, denoted by *. Result has the same width as the operands. P4 architectures may impose additional restrictions---e.g., they may only allow multiplication by a power of two.
• Comparison for equality and inequality, denoted == and != respectively. These operations produce a Boolean result.
• Numeric comparisons, denoted by <,<=,>, and >=. These operations produce a Boolean result.

Fixed-width signed saturating integers

A saturating integer is declared using saturating_int<W>. It has a bit-width of W, and thus will have a minimum value of -2^W-1^ and a maximum value of 2^W-1^-1. The most significant bit (bit W-1) is the sign bit. W must be a compile-time known value.

Operations on fixed-width signed saturating integers

As opposed to the modular arithmetic supported with int<W>, saturating arithmetic will clamp the value of the result to either the minimum or maximum value supported by the data type.

All binary operations require both operands to have the same exact type, saturating, signedness, and width. Supplying operands of different types produces a compile-time error. No implicit casts (conversions) are inserted by the compiler to equalize the types. P4 does not support any binary operations that combine saturating and modular arithmetic, except cast.

The saturating_int<W> datatype supports the following operations:

• Negation, denoted by unary -.
• Unary plus, denoted by +. This operation behaves like a no-op.
• Addition, denoted by +. Example:

saturating_int<W> a, b;
int tmp = a + b;
if (tmp < a.min)       // a.min = -2^W-1^
    a.min
else if (tmp > a.max)  // a.max = 2^W-1^ - 1
    a.max
else
    tmp

• Subtraction, denoted by -.
• Multiplication, denoted by *. Result has the same width as the operands. P4 architectures may impose additional restrictions---e.g., they may only allow multiplication by a power of two.
• Comparison for equality and inequality, denoted == and != respectively. These operations produce a Boolean result.
• Numeric comparisons, denoted by <,<=,>, and >=. These operations produce a Boolean result.

Example

header ipv4_t {
        bit<4>  version;
        bit<4>  ihl;
        bit<8>  diffserv;
        bit<16> totalLen;
        saturating_bit<16> identification;
        bit<3>  flags : 3;
        bit<13> fragOffset;
        saturating_bit<8> ttl;
        bit<8>  protocol;
        bit<16> hdrChecksum;
        bit<32> srcAddr;
        bit<32> dstAddr;
    }
}

control ingress(...) {
    action a(in saturating_bit<16> value) {
        // even if ttl == 0, following the decrement operation, ttl will continue to be 0
        ttl = ttl - saturating_bit<8>(1);

        // assuming identification == 0xFFE0, adding value = 0x0FFF, will result in
        // identification == 0xFFFF
        identification = identification + value;
    }
    ...
}