t03_full_add_signal.py

# BSD-3-clause
#
# Copyright (c) 2024 tsinghua-ideal
# All rights reserved.
#
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions
# are met:
#
# 1. Redistributions of source code must retain the above copyright
#    notice, this list of conditions and the following disclaimer.
# 2. Redistributions in binary form must reproduce the above copyright
#    notice, this list of conditions and the following disclaimer in the
#    documentation and/or other materials provided with the distribution.
# 3. Neither the name of the copyright holder nor the names of its
#    contributors may be used to endorse or promote products derived
#    from this software without specific prior written permission.
#
# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
# ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
# LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
# CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
# SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
# INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
# CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
# ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
# POSSIBILITY OF SUCH DAMAGE.
#
#
#
# This code checks the correctness of full adder combinational net.
# The module assumes that the signal is generated by an SRAM and several
# full adders. Verify that the signal produced by this method is exactly
# the same as the result of directly specifying any Automorphism with an
# extra Shift.

from t01_auto_dec import decompose_automorphism_to_shift_signals
from t01_auto_dec import is_array_equals
from t01_auto_dec import ShiftNetwork


def full_adder(a, b, ci):
    """
    Performs a full addition operation on two binary inputs and a carry-in bit.

    This function implements the logic of a full adder, which takes two binary inputs (a and b) and a carry-in bit (ci),
    and returns the sum and carry-out bit.

    The full adder logic is as follows:

    1. Compute the XOR of a and b, which gives the sum without considering the carry-in bit.
    2. Compute the XOR of the result from step 1 and the carry-in bit, which gives the final sum.
    3. Compute the AND of a and b, which gives the carry-out bit if both a and b are 1.
    4. Compute the AND of the carry-in bit and the result from step 1, which gives the carry-out bit if the carry-in bit
       and either a or b are 1.
    5. Compute the OR of the results from steps 3 and 4, which gives the final carry-out bit.

    Args:
        a (int): The first binary input (0 or 1).
        b (int): The second binary input (0 or 1).
        ci (int): The carry-in bit (0 or 1).

    Returns:
        tuple: A tuple containing the sum (s) and carry-out (co) bits.

    Raises:
        ValueError: If a, b, or ci is not a binary value (0 or 1).

    Example:
        >>> s, co = full_adder(1, 1, 0)
        >>> print(s, co)
        0 1

    Note:
        This function assumes that the inputs are binary values (0 or 1). If the inputs are not binary values, a ValueError
        is raised.

    See Also:
        to_bin_array: Converts an integer to a binary array.
        merge_extra_shift_by_full_adder: Merges extra shift signals using a full adder.
    """
    ab_xor = a ^ b
    s = ab_xor ^ ci
    co = (a & b) | (ci & ab_xor)
    return s, co


def to_bin_array(x, w):
    """
    Converts an integer to a binary array of a specified width.

    This function takes an integer (x) and a width (w), and returns a list of binary digits representing the integer.

    Args:
        x (int): The integer to convert.
        w (int): The width of the binary array.

    Returns:
        list: A list of binary digits (0 or 1) representing the integer.

    Example:
        >>> bin_array = to_bin_array(11, 4)
        >>> print(bin_array)
        [1, 0, 1, 1]

    Note:
        This function assumes that the width is sufficient to represent the integer.
    """
    b = []
    for _ in range(w):
        b.append(x & 1)
        x = x >> 1
    return b


def merge_extra_shift_by_full_adder(reduced_signals, shift_stride):
    """
    Merges extra shift signals using a full adder.

    This function takes a list of reduced signals and a shift stride, and returns a new list of signals with the extra shift
    merged using a full adder.

    Args:
        reduced_signals (list): A list of reduced signals.
        shift_stride (int): The shift stride.

    Returns:
        list: A new list of signals with the extra shift merged.

    Example:
        >>> reduced_signals = [[0, 0, 1, 0, 1, 1, 0, 1], [0, 1, 1, 0], [0, 1], [0]]
        >>> shift_stride = 11
        >>> merged_signals = merge_extra_shift_by_full_adder(reduced_signals, shift_stride)
        >>> print(merged_signals)
        [[1, 0, 0, 1, 0, 1, 1, 0], [0, 0, 1, 1], [1, 0], [1]]

    Note:
        This function assumes that the reduced signals are valid and the shift stride is non-zero.
    """
    r = reduced_signals
    for rline in r:
        for rcell in rline:
            assert rcell in [0, 1]
    logN = len(r)
    c = [[0] * (1 << (logN - i - 1)) for i in range(logN)]  # carry
    b = to_bin_array(shift_stride, len(r))
    s = [[0] * (1 << (logN - i - 1)) for i in range(logN)]  # output signals
    for i in range(logN - 1, -1, -1):
        if i == logN - 1:
            cin = 0
            sum, cout = full_adder(r[i][0], b[logN - i - 1], cin)
            c[i][0] = cout
            s[i][0] = sum
        else:
            half = 1 << (logN - i - 2)
            for j in range(1 << (logN - i - 1)):
                cin_idx = j % half
                cin = c[i + 1][cin_idx]
                sum, cout = full_adder(r[i][j], b[logN - i - 1], cin)
                c[i][j] = cout
                s[i][j] = sum
    for sline in s:
        for scell in sline:
            assert scell in [0, 1]
    return s


def show_fa_merge():
    """
    Shows if merge the extra Shift signal by full adder equals
    to signals reduced by normal method.
    """
    logN = 4
    phi = 7
    shift_stride = 11
    n = 1 << logN
    net = ShiftNetwork(logN)
    a = list(range(n))
    ctrl = decompose_automorphism_to_shift_signals(n, phi)
    ctrl.signals[-1][0] = shift_stride
    ctrl.reduce()
    assert ctrl.is_physical_signals()
    print("----- standard extra shift -----")
    print(ctrl.signals)
    print(net.forward(a, ctrl))
    ctrl = decompose_automorphism_to_shift_signals(n, phi)
    ctrl.reduce()
    assert ctrl.is_physical_signals()
    print("----- merge signals by full adder -----")
    s = merge_extra_shift_by_full_adder(ctrl.signals, shift_stride)
    ctrl.signals = s
    print(ctrl.signals)
    print(net.forward(a, ctrl))


def check_fa_merge():
    """
    Check if the signals merged from automorphism decomposition and full adder
    equals to the signals reduced from automorphism with an extra shift.

    Check only on logN = 10.
    """
    logN = 10
    n = 1 << logN
    for phi in range(n):
        if phi % 2 == 0:
            # The parameter must be coprime with the length,
            # otherwise it cannot form an Automorphism
            continue

        for x in range(n):
            if x == 0:
                # skip shift stride equals to 0,
                # because these cases test in t01_auto_dec.py
                continue

            ctrl = decompose_automorphism_to_shift_signals(n, phi)
            ctrl.reduce()
            signals_by_comb_net = merge_extra_shift_by_full_adder(ctrl.signals, x)
            ctrl.signals[-1][0] = x
            ctrl.reduce()
            signals_reference = ctrl.signals
            assert is_array_equals(signals_by_comb_net, signals_reference)


if __name__ == "__main__":
    show_fa_merge()
    check_fa_merge()