/*
 * Copyright 2015 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#ifndef ANDROID_MODULO_H
#define ANDROID_MODULO_H

namespace android {

// Modulo class is used for intentionally wrapping variables such as
// counters and timers.
//
// It may also be used for variables whose computation depends on the
// associativity of addition or subtraction.
//
// Features:
// 1) Modulo checks type sizes before performing operations to ensure
//    that the wrap points match. This is critical for safe modular arithmetic.
// 2) Modulo returns Modulo types from arithmetic operations, thereby
//    avoiding unintentional use in a non-modular computation.  A Modulo
//    type is converted to its base non-Modulo type through the value() function.
// 3) Modulo separates out overflowable types from non-overflowable types.
//    A signed overflow is technically undefined in C and C++.
//    Modulo types do not participate in sanitization.
// 4) Modulo comparisons are based on signed differences to account for wrap;
//    this is not the same as the direct comparison of values.
// 5) Safe use of binary arithmetic operations relies on conversions of
//    signed operands to unsigned operands (which are modular arithmetic safe).
//    Conversions which are implementation-defined are assumed to use 2's complement
//    representation. (See A, B, C, D from the ISO/IEC FDIS 14882
//    Information technology — Programming languages — C++).
//
// A: ISO/IEC 14882:2011(E) p84 section 4.7 Integral conversions
// (2) If the destination type is unsigned, the resulting value is the least unsigned
// integer congruent to the source integer (modulo 2^n where n is the number of bits
// used to represent the unsigned type). [ Note: In a two’s complement representation,
// this conversion is conceptual and there is no change in the bit pattern (if there
// is no truncation). — end note ]
// (3) If the destination type is signed, the value is unchanged if it can be represented
// in the destination type (and bit-field width); otherwise, the value is
// implementation-defined.
//
// B: ISO/IEC 14882:2011(E) p88 section 5 Expressions
// (9) Many binary operators that expect operands of arithmetic or enumeration type
// cause conversions and yield result types in a similar way. The purpose is to
// yield a common type, which is also the type of the result. This pattern is called
// the usual arithmetic conversions, which are defined as follows:
// [...]
// Otherwise, if both operands have signed integer types or both have unsigned
// integer types, the operand with the type of lesser integer conversion rank shall be
// converted to the type of the operand with greater rank.
// — Otherwise, if the operand that has unsigned integer type has rank greater than
// or equal to the rank of the type of the other operand, the operand with signed
// integer type shall be converted to the type of the operand with unsigned integer type.
//
// C: ISO/IEC 14882:2011(E) p86 section 4.13 Integer conversion rank
// [...] The rank of long long int shall be greater than the rank of long int,
// which shall be greater than the rank of int, which shall be greater than the
// rank of short int, which shall be greater than the rank of signed char.
// — The rank of any unsigned integer type shall equal the rank of the corresponding
// signed integer type.
//
// D: ISO/IEC 14882:2011(E) p75 section 3.9.1 Fundamental types
// [...] Unsigned integers, declared unsigned, shall obey the laws of arithmetic modulo
// 2^n where n is the number of bits in the value representation of that particular
// size of integer.
//
// Note:
// Other libraries do exist for safe integer operations which can detect the
// possibility of overflow (SafeInt from MS and safe-iop in android).
// Signed safe computation is also possible from the art header safe_math.h.

template <typename T> class Modulo {
    T mValue;

public:
    typedef typename std::make_signed<T>::type signedT;
    typedef typename std::make_unsigned<T>::type unsignedT;

    Modulo() { } // intentionally uninitialized data
    Modulo(const T &value) { mValue = value; }
    const T & value() const { return mValue; } // not assignable
    signedT signedValue() const { return mValue; }
    unsignedT unsignedValue() const { return mValue; }
    void getValue(T *value) const { *value = mValue; } // more type safe than value()

    // modular operations valid only if size of T <= size of S.
    template <typename S>
    __attribute__((no_sanitize("integer")))
    Modulo<T> operator +=(const Modulo<S> &other) {
        static_assert(sizeof(T) <= sizeof(S), "argument size mismatch");
        mValue += other.unsignedValue();
        return *this;
    }

    template <typename S>
    __attribute__((no_sanitize("integer")))
    Modulo<T> operator -=(const Modulo<S> &other) {
        static_assert(sizeof(T) <= sizeof(S), "argument size mismatch");
        mValue -= other.unsignedValue();
        return *this;
    }

    // modular operations resulting in a value valid only at the smaller of the two
    // Modulo base type sizes, but we only allow equal sizes to avoid confusion.
    template <typename S>
    __attribute__((no_sanitize("integer")))
    const Modulo<T> operator +(const Modulo<S> &other) const {
        static_assert(sizeof(T) == sizeof(S), "argument size mismatch");
        return Modulo<T>(mValue + other.unsignedValue());
    }

    template <typename S>
    __attribute__((no_sanitize("integer")))
    const Modulo<T> operator -(const Modulo<S> &other) const {
        static_assert(sizeof(T) == sizeof(S), "argument size mismatch");
        return Modulo<T>(mValue - other.unsignedValue());
    }

    // modular operations that should be checked only at the smaller of
    // the two type sizes, but we only allow equal sizes to avoid confusion.
    //
    // Caution: These relational and comparison operations are not equivalent to
    // the base type operations.
    template <typename S>
    __attribute__((no_sanitize("integer")))
    bool operator >(const Modulo<S> &other) const {
        static_assert(sizeof(T) == sizeof(S), "argument size mismatch");
        return static_cast<signedT>(mValue - other.unsignedValue()) > 0;
    }

    template <typename S>
    __attribute__((no_sanitize("integer")))
    bool operator >=(const Modulo<S> &other) const {
        static_assert(sizeof(T) == sizeof(S), "argument size mismatch");
        return static_cast<signedT>(mValue - other.unsignedValue()) >= 0;
    }

    template <typename S>
    __attribute__((no_sanitize("integer")))
    bool operator ==(const Modulo<S> &other) const {
        static_assert(sizeof(T) == sizeof(S), "argument size mismatch");
        return static_cast<signedT>(mValue - other.unsignedValue()) == 0;
    }

    template <typename S>
    __attribute__((no_sanitize("integer")))
    bool operator <=(const Modulo<S> &other) const {
        static_assert(sizeof(T) == sizeof(S), "argument size mismatch");
        return static_cast<signedT>(mValue - other.unsignedValue()) <= 0;
    }

    template <typename S>
    __attribute__((no_sanitize("integer")))
    bool operator <(const Modulo<S> &other) const {
        static_assert(sizeof(T) == sizeof(S), "argument size mismatch");
        return static_cast<signedT>(mValue - other.unsignedValue()) < 0;
    }


    // modular operations with a non-Modulo type allowed with wrapping
    // because there should be no confusion as to the meaning.
    template <typename S>
    __attribute__((no_sanitize("integer")))
    Modulo<T> operator +=(const S &other) {
        mValue += unsignedT(other);
        return *this;
    }

    template <typename S>
    __attribute__((no_sanitize("integer")))
    Modulo<T> operator -=(const S &other) {
        mValue -= unsignedT(other);
        return *this;
    }

    // modular operations with a non-Modulo type allowed with wrapping,
    // but we restrict this only when size of T is greater than or equal to
    // the size of S to avoid confusion with the nature of overflow.
    //
    // Use of this follows left-associative style.
    //
    // Note: a Modulo type may be promoted by using "differences" off of
    // a larger sized type, but we do not automate this.
    template <typename S>
    __attribute__((no_sanitize("integer")))
    const Modulo<T> operator +(const S &other) const {
        static_assert(sizeof(T) >= sizeof(S), "argument size mismatch");
        return Modulo<T>(mValue + unsignedT(other));
    }

    template <typename S>
    __attribute__((no_sanitize("integer")))
    const Modulo<T> operator -(const S &other) const {
        static_assert(sizeof(T) >= sizeof(S), "argument size mismatch");
        return Modulo<T>(mValue - unsignedT(other));
    }

    // multiply is intentionally omitted, but it is a common operator in
    // modular arithmetic.

    // shift operations are intentionally omitted, but perhaps useful.
    // For example, left-shifting a negative number is undefined in C++11.
};

} // namespace android

#endif /* ANDROID_MODULO_H */