Adder-subtractor circuit model with carry/borrow in and condition flags

adder-subtractor.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Integer arithmetic and condition codes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from inspect import signature\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Auxiliary functions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Convert integer to the binary array\n",
    "def int_to_bin(value, nbits):\n",
    "    return [int(x) for x in np.binary_repr(value, width=nbits)]\n",
    "\n",
    "# Convert binary array to the unsigned integer\n",
    "def bin_to_uint(bits):\n",
    "    s = 0\n",
    "    for i in range(len(bits)):\n",
    "        s += bits[len(bits)-i-1] * 2**i\n",
    "    return s\n",
    "\n",
    "# Convert two's complement binary array to the integer\n",
    "def bin_to_int(bits):\n",
    "    sign = bits[0]\n",
    "    if sign:\n",
    "        return -bin_to_uint([1-bi for bi in bits[1:]]) -1\n",
    "    else:\n",
    "        return bin_to_uint(bits[1:])\n",
    "\n",
    "# Print truth table of the logic function\n",
    "def print_truth_table(func):\n",
    "    n_inputs = len(signature(func).parameters)\n",
    "    n_rows = 2**n_inputs\n",
    "    for val in range(n_rows):\n",
    "        inputs = int_to_bin(val, n_inputs)\n",
    "        out = func(*inputs)\n",
    "        print('{} | {}'.format(inputs, out))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Logic blocks"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Full adder\n",
    "![](https://i.imgur.com/8WPVGn2.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Full 1-bit adder\n",
    "def fadd(a, b, cin):\n",
    "    xab = a ^ b\n",
    "    s = xab ^ cin\n",
    "    cout = (a & b) | (xab & cin)\n",
    "    return (s, cout)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4-bit adder-subtractor with flags\n",
    "\n",
    "- CF - carry flag (unsigned overflow)\n",
    "- OF - overflow flag (signed overflow)\n",
    "- ZF - zero flag\n",
    "- SF - sign (negative) flag\n",
    "![](https://i.imgur.com/eLNByEK.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 4-bit adder-subtractor\n",
    "# works with unsigned and two's complement signed integers\n",
    "def add_sub(a, b, is_sub):\n",
    "    cin = 0\n",
    "    if is_sub:\n",
    "        cin = 1\n",
    "        b = [1^bi for bi in b]\n",
    "        \n",
    "    o0, c0 = fadd(a[3], b[3], cin)\n",
    "    o1, c1 = fadd(a[2], b[2], c0)\n",
    "    o2, c2 = fadd(a[1], b[1], c1)\n",
    "    o3, c3 = fadd(a[0], b[0], c2)\n",
    "    res = [o3, o2, o1, o0]\n",
    "    cf = c3\n",
    "    of = c3 ^ c2\n",
    "    zf = 1 if all((bi == 0 for bi in res)) else 0\n",
    "    sf = res[0]\n",
    "    return (res, cf, of, zf, sf)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Conditions based on status flags"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test flags (a-b): a >= b\n",
    "def unsigned_greater_or_equal_than(cf, of, zf, sf):\n",
    "    return cf == 1\n",
    "\n",
    "# Test flags (a-b): a < b\n",
    "def unsigned_lower_than(cf, of, zf, sf):\n",
    "    return cf == 0\n",
    "\n",
    "# Test flags (a-b): a > b\n",
    "def unsigned_greater_than(cf, of, zf, sf):\n",
    "    return cf == 1 and zf == 0\n",
    "\n",
    "# Test flags (a-b): a <= b\n",
    "def unsigned_lower_or_equal_than(cf, of, zf, sf):\n",
    "    return cf == 0 or zf == 1\n",
    "\n",
    "# Test flags (a - b): a >= b\n",
    "def signed_greater_or_equal_than(cf, of, zf, sf):\n",
    "    return sf == of\n",
    "\n",
    "# Test flags (a - b): a < b\n",
    "def signed_less_than(cf, of, zf, sf):\n",
    "    return sf != of\n",
    "\n",
    "# Test flags (a - b): a > b\n",
    "def signed_greater_than(cf, of, zf, sf):\n",
    "    return zf != 1 and sf == of\n",
    "\n",
    "# Test flags (a - b): a <= b\n",
    "def signed_less_or_equal_than(cf, of, zf, sf):\n",
    "    return zf == 1 or sf != of"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Tests for conditions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Testing signed_greater_or_equal_than...\n",
      "Pass\n",
      "Testing signed_less_than...\n",
      "Pass\n",
      "Testing signed_greater_than...\n",
      "Pass\n",
      "Testing signed_less_or_equal_than...\n",
      "Pass\n"
     ]
    }
   ],
   "source": [
    "def condition_test(func, expected_func):\n",
    "    print('Testing {}...'.format(func.__name__))\n",
    "    nbits = 4\n",
    "    fail = False\n",
    "    for a in range(-8, 8):\n",
    "        for b in range(-8, 8):\n",
    "            _, cf, of, zf, sf = add_sub(int_to_bin(a, nbits), int_to_bin(b, nbits), 1)\n",
    "            expected = expected_func(a, b)\n",
    "            actual = func(cf, of, zf, sf)\n",
    "            if expected != actual:\n",
    "                print('Compare {} - {}:'.format(a, b))\n",
    "                print('Expected: {}'.format(expected))\n",
    "                print('Actual: {}'.format(actual))\n",
    "                fail = True\n",
    "    if fail:\n",
    "        print('Failed')\n",
    "    else:\n",
    "        print('Pass')\n",
    "\n",
    "def test_signed_greater_or_equal_than():\n",
    "    condition_test(signed_greater_or_equal_than, lambda a, b: a >= b)\n",
    "    \n",
    "def test_signed_less_than():\n",
    "    condition_test(signed_less_than, lambda a, b: a < b)\n",
    "    \n",
    "def test_signed_greater_than():\n",
    "    condition_test(signed_greater_than, lambda a, b: a > b)\n",
    "    \n",
    "def test_signed_less_or_equal_than():\n",
    "    condition_test(signed_less_or_equal_than, lambda a, b: a <= b)\n",
    "            \n",
    "test_signed_greater_or_equal_than()\n",
    "test_signed_less_than()\n",
    "test_signed_greater_than()\n",
    "test_signed_less_or_equal_than()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Testing unsigned_greater_or_equal_than...\n",
      "Pass\n",
      "Testing unsigned_lower_than...\n",
      "Pass\n",
      "Testing unsigned_greater_than...\n",
      "Pass\n",
      "Testing unsigned_lower_or_equal_than...\n",
      "Pass\n"
     ]
    }
   ],
   "source": [
    "def condition_utest(func, expected_func):\n",
    "    print('Testing {}...'.format(func.__name__))\n",
    "    nbits = 4\n",
    "    fail = False\n",
    "    for a in range(0, 16):\n",
    "        for b in range(0, 16):\n",
    "            _, cf, of, zf, sf = add_sub(int_to_bin(a, nbits), int_to_bin(b, nbits), 1)\n",
    "            expected = expected_func(a, b)\n",
    "            actual = func(cf, of, zf, sf)\n",
    "            if expected != actual:\n",
    "                print('Compare {} - {}:'.format(a, b))\n",
    "                print('Expected: {}'.format(expected))\n",
    "                print('Actual: {}'.format(actual))\n",
    "                fail = True\n",
    "    if fail:\n",
    "        print('Failed')\n",
    "    else:\n",
    "        print('Pass')\n",
    "\n",
    "def test_unsigned_greater_or_equal_than():\n",
    "    condition_utest(unsigned_greater_or_equal_than, lambda a, b: a >= b)\n",
    "    \n",
    "def test_unsigned_lower_than():\n",
    "    condition_utest(unsigned_lower_than, lambda a, b: a < b)\n",
    "    \n",
    "def test_unsigned_greater_than():\n",
    "    condition_utest(unsigned_greater_than, lambda a, b: a > b)\n",
    "    \n",
    "def test_unsigned_lower_or_equal_than():\n",
    "    condition_utest(unsigned_lower_or_equal_than, lambda a, b: a <= b)\n",
    "    \n",
    "test_unsigned_greater_or_equal_than()\n",
    "test_unsigned_lower_than()\n",
    "test_unsigned_greater_than()\n",
    "test_unsigned_lower_or_equal_than()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Adder-subtractor with carry in\n",
    "\n",
    "This adder-subtractor support carry/borrow in to perform multi-word operations\n",
    " - add - summator without carry in\n",
    " - adc - summator with carry in\n",
    " - sub - substrator without borrow in\n",
    " - sbc - substrator with borrow in\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 4-bit adder-subtractor\n",
    "# works with unsigned and two's complement signed integers\n",
    "def add_sub_2(a, b, cin, is_sub=0, use_cin=0):\n",
    "    cin = cin if use_cin == 1 else is_sub\n",
    "    b = [is_sub^bi for bi in b]\n",
    "        \n",
    "    o0, c0 = fadd(a[3], b[3], cin)\n",
    "    o1, c1 = fadd(a[2], b[2], c0)\n",
    "    o2, c2 = fadd(a[1], b[1], c1)\n",
    "    o3, c3 = fadd(a[0], b[0], c2)\n",
    "    res = [o3, o2, o1, o0]\n",
    "    cf = c3\n",
    "    of = c3 ^ c2\n",
    "    zf = 1 if all((bi == 0 for bi in res)) else 0\n",
    "    sf = res[0]\n",
    "    return (res, cf, of, zf, sf)\n",
    "\n",
    "def add(a, b):\n",
    "    return add_sub_2(a, b, 0, 0, 0)\n",
    "\n",
    "def adc(a, b, cin):\n",
    "    return add_sub_2(a, b, cin, 0, 1)\n",
    "\n",
    "def sub(a, b):\n",
    "    return add_sub_2(a, b, 0, 1, 0)\n",
    "\n",
    "def sbc(a, b, cin):\n",
    "    return add_sub_2(a, b, cin, 1, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 1, 1, 1] 0 0\n",
      "[0, 0, 0, 0] 1 0\n"
     ]
    }
   ],
   "source": [
    "# Subtract two multi-word numbers\n",
    "a = [[0, 0, 0, 1], [0, 0, 0, 0]]\n",
    "b = [[0, 0, 0, 0], [0, 0, 0, 1]]\n",
    "cl, cf, of, zf, nf = sub(a[1], b[1])\n",
    "print(cl, cf, of)\n",
    "ch, cf, of, zf, nf = sbc(a[0], b[0], cf)\n",
    "print(ch, cf, of)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 0, 0, 0] 1 0\n",
      "[0, 0, 0, 1] 0 0\n"
     ]
    }
   ],
   "source": [
    "# Add two multi-word numbers\n",
    "a = [[0, 0, 0, 0], [1, 1, 1, 1]]\n",
    "b = [[0, 0, 0, 0], [0, 0, 0, 1]]\n",
    "cl, cf, of, zf, nf = add(a[1], b[1])\n",
    "print(cl, cf, of)\n",
    "ch, cf, of, zf, nf = adc(a[0], b[0], cf)\n",
    "print(ch, cf, of)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Debug functions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sum_debug_t(a, b, is_sub, func):\n",
    "    abin = int_to_bin(a, 4)\n",
    "    bbin = int_to_bin(b, 4)\n",
    "    resbin, cf, of, zf, sf = sub_add(abin, bbin, is_sub)\n",
    "    res = func(resbin)\n",
    "    sign = '-' if is_sub else '+'\n",
    "    print('{} {} {} = {}, CF={}, OF={}, ZF={}, SF={}'.format(a, sign, b, res, cf, of, zf, sf))\n",
    "    \n",
    "def sum_udebug(a, b, is_sub):\n",
    "    sum_test_t(a, b, is_sub, bin_to_uint)\n",
    "    \n",
    "def sum_debug(a, b, is_sub):\n",
    "    sum_test_t(a, b, is_sub, bin_to_int)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}