path: root/chapters/pseudocode.adoc

//
// This confidential and proprietary software may be used only as
// authorised by a licensing agreement from ARM Limited
// (C) COPYRIGHT 2021-2022 ARM Limited
// ALL RIGHTS RESERVED
// The entire notice above must be reproduced on all authorised
// copies and copies may only be made to the extent permitted
// by a licensing agreement from ARM Limited.

== TOSA Pseudocode

The TOSA pseudocode provides precise descriptions of TOSA operations.
Each operator contains pseudocode describing the operator's functionality.
This section contains pseudocode functions shared across multiple operators in the specification.

=== Operator Validation Helpers

The following functions are used to define the valid conditions for TOSA operators.

The REQUIRE function defines the conditions required by the TOSA operator.
If the conditions are not met then the result of the TOSA graph is marked as unpredictable.
Once the tosa_graph_result is set to tosa_unpredictable, the whole graph is considered unpredictable.

The ERROR_IF function defines a condition that must set an error if the condition holds and the graph is not unpredictable.
Note that if a graph contains both unpredictable and error statements then result of tosa_execute_graph() is tosa_unpredictable.
This condition is captured in the ERROR_IF function.

*Implementation Notes*

* An implementation is not required to detect unpredictable behavior. If tosa_execute_graph() returns tosa_unpredictable then the tosa_test_compliance() function does not require any specific output from an implementation.
* An implementation is required to detect errors in a graph that does not have unpredictable behavior (see tosa_test_compliance).
* An acceptable implementation is to stop and report an error on the first ERROR_IF condition that occurs. This satifies tosa_test_compliance() even if the tosa_execute_graph() was tosa_unpredictable.
* If the tosa_execute_graphs() result is tosa_unpredictable or tosa_error, then there is no requirement on the implementation to execute any portion of the TOSA graph.

[source,c++]
----
void REQUIRE(condition) {
    // Unpredictable overrides any previous result
    if (!(condition)) {
        tosa_graph_result = tosa_unpredictable;
    }
}

void ERROR_IF(condition) {
    // Error encodes a predictable error state and so is not registered
    // if the graph is marked as unpredictable.
    if (tosa_graph_result != tosa_unpredictable && condition) {
        tosa_graph_result = tosa_error;
    }
}
----

=== Tensor Access Helpers

==== Tensor Utilities

[source,c++]
----
size_t tensor_index_to_offset(dim_t shape, dim_t index) {
    // Ensure this is a proper tensor with each dimension having size >= 1
    for_each(dimension_size in shape) {
        REQUIRE(dimension_size >= 1);
    }
    size_t offset = 0;
    for (int32_t i = 0; i < rank(shape); i++) {
        REQUIRE(index[i] >= 0 && index[i] < shape[i]);
        offset = offset * shape[i] + index[i];
    }
    return offset;
}

dim_t tensor_offset_to_index(dim_t shape, size_t offset) {
    // Index is a dim_t with rank equal to the rank of shape
    dim_t index(rank(shape));
    for(int32_t r = rank(shape1) - 1; r >= 0; r--) {
        index[r] = offset % shape1[r];
        calculated_index /= shape[r];
    }
    return index;
}

// Input is the shape of the given tensor
size_t tensor_size(dim_t shape) {
    size_t size = 1;
    for (int32_t i=0; i < rank(shape); i++) {
        size *= input[i];
    }
    return size;
}
----

==== Tensor Read

tensor_read reads a single data value out of the given tensor.
The shape argument contains the shape of the tensor.
Index is the coordinates within the tensor of the value to be read.

[source,c++]
----
in_t tensor_read<in_t>(in_t *address, dim_t shape, dim_t index) {
    size_t offset = tensor_index_to_offset(shape, index);
    return address[offset];
}
----

==== Tensor Write

tensor_write writes a single data value into the given tensor.
The shape argument contains the shape of the tensor.
Index is the coordinates within the tensor of the value to be written.
value is the value to be written to the given coordinate.

[source,c++]
----
void tensor_write<type>(<type> *address, dim_t shape, dim_t index, <type> value) {
    size_t offset = tensor_index_to_offset(shape, index);
    address[offset] = value;
}
----

==== Broadcast Helper

The following function maps an index in the output tensor to an index in the input tensor.

[source,c++]
----
// The index argument should be a valid location within out_shape.
// The function returns the location within in_shape that contributes
// to the output based on broadcasting rules.

dim_t apply_broadcast(dim_t out_shape, dim_t in_shape, dim_t index) {
    ERROR_IF(rank(out_shape) != rank(in_shape));
    ERROR_IF(rank(out_shape) != rank(index));
    for (int32_t i = 0; i < rank(out_shape); i++) {
        if (out_shape[i] != in_shape[i]) {
            ERROR_IF(in_shape[i] != 1);
            index[i] = 0;
        }
    }
    return index;
}
----

=== General Pseudocode Helpers

This section contains general pseudocode utility functions used throughout the specification.

==== Arithmetic Helpers

The following functions provide arithmetic while defining requirements such that values stay in the valid range.

[source,c++]
----
in_t apply_add<in_t>(in_t a, in_t b) {
    if (<in_t> == float_t) return a + b;
    int64_t c = (int64_t)a + (int64_t)b;
    REQUIRE(c >= minimum<in_t> && c <= maximum<in_t>);
    return (in_t)c;
}

in_t apply_ceil<in_t>(in_t input) {
    return input value rounded up to nearest integer
}

in_t apply_clip<in_t>(in_t value, in_t min_val, in_t max_val) {
    REQUIRE(min_val <= max_val);
    value = apply_max(value, min_val);
    value = apply_min(value, max_val);
    return value;
}

in_t apply_exp<in_t>(in_t input) {
    return e to the power input
}

in_t apply_floor<in_t>(in_t input) {
    return input value rounded down to nearest integer
}

in_t apply_log<in_t>(in_t input) {
    if (input == 0) {
        return -INFINITY
    }
    else if (input < 0) {
        return NaN;
    }
    return the natural logarithm of input
}

in_t apply_max<in_t>(in_t a, in_t b) {
    if (in_t == float_t) {
        if (isNaN(a) || isNaN(b)) {
            return NaN;
        }
    }
    if (a >= b) return a; else return b;
}

in_t apply_min<in_t>(in_t a, in_t b) {
    if (in_t == float_t) {
        if (isNaN(a) || isNaN(b)) {
            return NaN;
        }
    }
    if (a < b) return a; else return b;
}

in_t apply_pow<in_t>(in_t a, in_t b) {
    return a ** b; // a raised to the power b
}

in_t apply_sqrt<in_t>(in_t input) {
    return the square root of input
}

in_t apply_sub<in_t>(in_t a, in_t b) {
    if (in_t == float_t) return a - b;
    int64_t c = (int64_t)a - (int64_t)b;
    REQUIRE(c >= minimum<in_t> && c <= maximum<in_t>);
    return (in_t)c;
}

int32_t count_leading_zeros(int32_t a) {
    int32_t acc = 32;
    if (a != 0) {
        uint32_t mask;
        mask = 1 << (32 - 1); // width of int32_t - 1
        acc = 0;
        while ((mask & a) == 0) {
            mask = mask >> 1;
            acc = acc + 1;
        }
    }
    return acc;
}
----

==== Numeric Conversion Helpers

The following definitions are used in pseudocode to do numeric conversions.

[source,c++]
----
int round_to_nearest_int(float_t f)
  Converts the floating-point value to f, with rounding to the nearest integer value.

float_t round_to_nearest_float(in_t f)
  Converts the input value into floating-point, rounding to the nearest representable value.
  The behavior for ties is implementation dependent.

out_t sign_extend(in_t input)
  Only valid for two's complement integer values where out_t has more bits than in_t.
  Output = input
  Replicate the top bit of input for all bits between the top bit of input and the top bit of output.

out_t truncate(in_t input)
  output is the sizeof(out_t) least significant bits in input.
----

The following definition is used to flatten a list of lists into a single list.

[source,c++]
----
in_t* flatten(in_t lists[]) {
    in_t output = [];
    for_each(list in lists) {
        for_each(element in list) {
            output.append(element);
        }
    }
}
----

Generic helper functions used to keep the pseudocode concise.

[source,c++]
----

int32_t idiv(int32_t input1, int32_t input2) {
    return input1 / input2; // Integer divide that truncates towards zero
}

// Integer division that checks input1 is a multiple of input2

int32_t idiv_check(int32_t input1, int32_t input2) {
    ERROR_IF(input1 % input2 != 0); // input1 must be a multiple of input2
    return input1 / input2;         // exact quotient without rounding
}

int32_t length(in_t input)
    return number of elements in input list

int32_t rank(in_t input)
    return rank of an input tensor

int32_t sum(in_t input[])
    return the sum of values of an input list

bool isNaN(float input)
    return True if floating-point input value is NaN

float_t pi()
    returns value of pi

float_t sin(angle)
    return sine of angle given in radians

float_t cos(angle)
    return cosine of angle given in radians

bool power_of_two(int32_t value)
    return true if value is a power of two, false otherwise
----