examples/example_count_ones.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "30d69278-57ab-47d9-9871-dcfc6519a80c",
   "metadata": {},
   "source": [
    "# Basic generator examples\n",
    "\n",
    "Construction of a few simple generators (**WIP**)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "b8b2837f-320c-402a-8bd8-c0517e0eae2d",
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "sys.path.insert(0, '../..')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b111c586-1ab8-4b2d-a1eb-20e3ce12e748",
   "metadata": {},
   "source": [
    "## Count one bits in word\n",
    "\n",
    "The simple model counting '1' bits in a standard logic array is as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "a289411e-8f1e-4514-9181-54d9cc85f2d4",
   "metadata": {},
   "outputs": [],
   "source": [
    "def count_ones(v):\n",
    "    ones = 0\n",
    "    for i, item in enumerate(v):\n",
    "        if item == True:\n",
    "            ones += 1\n",
    "    return ones"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1a004472-d082-40bb-b0a4-9080530cd6a7",
   "metadata": {},
   "source": [
    "Verify:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "bd09e53d-559d-49ed-ad2f-e8d23774daf3",
   "metadata": {},
   "outputs": [],
   "source": [
    "from myirl import *\n",
    "v = intbv(0xaa)[8:]\n",
    "assert count_ones(v) == 4"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2bdcc499-8747-4100-b673-21040ca99dfd",
   "metadata": {},
   "source": [
    "We could implement the above *as is* and let synthesis figure out the rest. However, we could also model it according to [this interesting article](https://vhdlguru.blogspot.com/2017/10/count-number-of-1s-in-binary-number.html) using half and full adders with the most basic logic possible. So, we first define these as primitive functions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "ddc45e77-697d-4e86-a8da-bc7463d25d1d",
   "metadata": {},
   "outputs": [],
   "source": [
    "Bool = Signal.Type(bool)\n",
    "\n",
    "def half_adder(a : Bool, b : Bool, q : Bool.Output, c : Bool.Output):\n",
    "    return [\n",
    "        q.set(a ^ b), c.set(a & b)\n",
    "    ]\n",
    "\n",
    "def full_adder(a : Bool, b : Bool, cin : Bool, q : Bool.Output, c : Bool.Output):\n",
    "    x = a ^ b\n",
    "        \n",
    "    return [\n",
    "        q.set(x ^ cin), c.set((a & b) | (cin & (x)))\n",
    "    ]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6a2b6fe5-99d3-4964-9599-1ea563c53221",
   "metadata": {},
   "source": [
    "### Prove the obvious\n",
    "\n",
    "We then compose the '1' bit counter from these primitives by an inductive approach. For a 2-bit intbv, we can use a half adder. Note the `*half_adder` notation to unroll into a flat list for the return value:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "fa2335dc-f2c0-47b1-8a1c-28a4f403d840",
   "metadata": {},
   "outputs": [],
   "source": [
    "def bit_count2(A, ones):\n",
    "    Sum = Bool(name = \"S\")\n",
    "    Carry = Bool(name = \"C\")\n",
    "\n",
    "    return [\n",
    "        *half_adder(A[0], A[1], Sum, Carry),\n",
    "        ones.set(concat(Carry, Sum))\n",
    "    ]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "13ac2700-0d76-4384-bf8f-c8fdc83c6f21",
   "metadata": {},
   "source": [
    "Make sure this yields the same as the `count_ones` function applied on the wire bit array for all values possible.\n",
    "To evaluate this functional description manually:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "a6a76fc3-4722-44d8-bf15-6b639a8d7811",
   "metadata": {},
   "outputs": [],
   "source": [
    "from myirl import *\n",
    "\n",
    "import math\n",
    "\n",
    "@utils.timer\n",
    "def verify(N, func):\n",
    "    A = Signal(intbv()[N:])\n",
    "    M = int(math.log2(N))\n",
    "    ones = Signal(intbv()[1 + M:])\n",
    "    for i in range((2 ** N)-1, -1, -1):\n",
    "        A.set(i).evaluate() # Set current signal value to `i`\n",
    "        for gen in func(A, ones):\n",
    "            gen.evaluate()\n",
    "        n = count_ones(A.wire) # Call count_ones for the wire bits of A\n",
    "        _n = int(ones.evaluate())\n",
    "        print(bin(A.wire), \"-->\", _n)\n",
    "        assert _n == n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "14b6924a-7fe8-4a6a-bef3-cf1d3123ad97",
   "metadata": {},
   "source": [
    "### Cascading\n",
    "\n",
    "Let's take this for the double amount.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "69cb7f24-e69f-465b-a530-5e09e4332107",
   "metadata": {},
   "outputs": [],
   "source": [
    "def bit_count4(A, ones):\n",
    "    o = [ Signal(intbv()[2:]) for _ in range(2)]\n",
    "    C0, C1 = [Bool() for _ in range(2)]\n",
    "    S0, S1 = [Bool() for _ in range(2)]\n",
    "    \n",
    "    logic = [\n",
    "        *bit_count2(A[2:0], o[0]),\n",
    "        *bit_count2(A[4:2], o[1]),\n",
    "        # We could replace this reduction by the adder primitives below:\n",
    "        ones.set(o[0] + o[1]),\n",
    "        # *half_adder(o[0][0], o[1][0], S0, C0),\n",
    "        # *full_adder(o[0][1], o[1][1], C0, S1, C1),\n",
    "        # ones.set(concat(C1, S1, S0))\n",
    "    ]\n",
    "    return logic"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "0701b788-66e9-4c62-8a2b-cce9381d175c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0b1111 --> 4\n",
      "0b1110 --> 3\n",
      "0b1101 --> 3\n",
      "0b1100 --> 2\n",
      "0b1011 --> 3\n",
      "0b1010 --> 2\n",
      "0b1001 --> 2\n",
      "0b1000 --> 1\n",
      "0b111 --> 3\n",
      "0b110 --> 2\n",
      "0b101 --> 2\n",
      "0b100 --> 1\n",
      "0b11 --> 2\n",
      "0b10 --> 1\n",
      "0b1 --> 1\n",
      "0b0 --> 0\n",
      "Finished verify in 2.4207 secs\n"
     ]
    }
   ],
   "source": [
    "verify(4, bit_count4)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "74f5eeaf-bd45-432c-8fa6-ab0b417576ba",
   "metadata": {},
   "source": [
    "**Note**: This does not result in the optimum gate level count, because the two bit result of the half adder is maximum 2 (Input: \"11\"). For recursion with restriction to power of two data widths however, this is easiest to implement."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fe25bd83-1174-4eb5-9d9b-3237b284ea60",
   "metadata": {},
   "source": [
    "Finally, let's go 'recursive'. Since the variables and signals inside the function are flattened by default through the recursion, we need to provide unique names. This is simply done by prefixing.\n",
    "\n",
    "Due to VHDL being stricter with recursive slicing than Python, we need to use variables. We don't prefix them, to generate less unnecessary instances. (Question: Why can't we do this with signals?)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "7a2856cc-b959-483f-bf26-7ddb3f8142ce",
   "metadata": {},
   "outputs": [],
   "source": [
    "def bit_count(A, ones, prefix = \"R\"):\n",
    "    N = len(A)\n",
    "    M = N // 2\n",
    "    \n",
    "    if N > 2: \n",
    "        o = [ Signal(intbv()[len(ones)-1:], name=prefix + \"%do_%d\" % (i, M)) for i in range(2)]\n",
    "        upper = Variable(\"u_%d\" % M, intbv()[M:])\n",
    "        lower = Variable(\"l_%d\" % M, intbv()[M:])\n",
    "\n",
    "        logic = [\n",
    "            lower.assign(A[:M]),\n",
    "            upper.assign(A[M:]),\n",
    "            *bit_count(lower, o[0], prefix + \"0\"),\n",
    "            *bit_count(upper,  o[1], prefix + \"1\"), \n",
    "            ones.set(o[0] + o[1]),\n",
    "        ]\n",
    "        \n",
    "    else:\n",
    "        Sum = Bool(name = prefix + \"S\")\n",
    "        Carry = Bool(name = prefix + \"C\")\n",
    "        \n",
    "        logic = [\n",
    "            *half_adder(A[0], A[1], Sum, Carry),\n",
    "            ones.set(concat(Carry, Sum))\n",
    "        ]\n",
    "        \n",
    "    return logic"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dc3bd677-9f6a-431b-b50b-5bcaf9d67c72",
   "metadata": {},
   "source": [
    "We don't verify that, as it would take too long. Instead, we generate HDL from it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "f7f5febe-474e-4384-bc64-9ab3dffc25d5",
   "metadata": {},
   "outputs": [],
   "source": [
    "from myirl import *\n",
    "\n",
    "\n",
    "@block\n",
    "def ones_counter(data : Signal, count_ones : Signal.Output):\n",
    "    if len(data) != 2 ** (len(count_ones) -1):\n",
    "        raise ValueError(\"Check dimensions\")\n",
    "        \n",
    "    @genprocess()\n",
    "    def worker():\n",
    "        yield bit_count(data, count_ones)\n",
    "    \n",
    "    return instances()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "f667c23a-61a9-4973-885a-a15375c8eb63",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Creating sequential 'testbench/test' \n",
      " Writing 'ones_counter' to file /tmp/myirl_top_testbench_06qpa197/ones_counter.vhdl \n",
      "Finished _elab in 0.0115 secs\n",
      " Writing 'testbench' to file /tmp/myirl_top_testbench_06qpa197/testbench.vhdl \n",
      "DEBUG BOOLOP True count1s == C:8\n",
      "DEBUG BOOLOP True count1s == C:1\n",
      "DEBUG BOOLOP True count1s == C:4\n",
      "Finished _elab in 0.0099 secs\n",
      " Creating library file /tmp/myirl_module_defs_tof8m9tn/module_defs.vhdl \n",
      "==== COSIM stdout ====\n",
      "\n",
      "==== COSIM stderr ====\n",
      "\n",
      "==== COSIM stdout ====\n",
      "analyze /home/testing/src/myhdl2/myhdl.v2we/examples/../../myirl/targets/../test/vhdl/txt_util.vhdl\n",
      "analyze /home/testing/src/myhdl2/myhdl.v2we/examples/../../myirl/targets/libmyirl.vhdl\n",
      "analyze /tmp/myirl_top_testbench_06qpa197/ones_counter.vhdl\n",
      "analyze /tmp/myirl_top_testbench_06qpa197/testbench.vhdl\n",
      "elaborate testbench\n",
      "\n",
      "==== COSIM stderr ====\n",
      "\n",
      "==== COSIM stdout ====\n",
      "COUNT: 0x08\n",
      "COUNT: 0x01\n",
      "COUNT: 0x04\n",
      "\n",
      "==== COSIM stderr ====\n",
      "\n"
     ]
    }
   ],
   "source": [
    "from myirl import simulation as sim\n",
    "\n",
    "from myirl.test.common_test import *\n",
    "\n",
    "@block\n",
    "def testbench():\n",
    "\n",
    "    data = Signal(intbv()[32:])\n",
    "    count1s = Signal(intbv()[6:])\n",
    "    \n",
    "    uut = ones_counter(data, count1s)\n",
    "    \n",
    "    @sim.generator\n",
    "    def test():\n",
    "        \n",
    "        for v in [0xaaf0, 0x1000, 0x2340]:\n",
    "            z = intbv(v)[32:]\n",
    "            c = count_ones(z)\n",
    "\n",
    "            yield [\n",
    "                data.set(z),\n",
    "                sim.wait(\"1 ns\"),\n",
    "                sim.print_(\"COUNT:\", count1s),\n",
    "                sim.assert_(count1s == c, \"Failed\"),\n",
    "            ]\n",
    "        \n",
    "    return instances()\n",
    "\n",
    "def test():\n",
    "    tb = testbench()\n",
    "    f = tb.elab(targets.VHDL, elab_all = True)\n",
    "    run_ghdl(f, tb, debug = True)\n",
    "\n",
    "test()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3c62e49b-c6c9-4799-b8b6-33fe5d447637",
   "metadata": {},
   "source": [
    "The procedurally generated result is rather unreadable:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "b091d893-a4a7-499d-b1d6-aee663cc41d3",
   "metadata": {},
   "outputs": [],
   "source": [
    "# !cat -n {testbench.ctx.path_prefix}ones_counter.vhdl"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a1a4ee5a-9c76-49bf-b80c-997cf53f8295",
   "metadata": {},
   "source": [
    "## Manual example\n",
    "\n",
    "For an 8 bit value, we could also use full adders in the first place and handle the resulting values, likewise:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "a6400c13-16d7-425e-869b-5212e13f57ad",
   "metadata": {},
   "outputs": [],
   "source": [
    "def bit_count8(v, sum_ones):\n",
    "\n",
    "    s = [ Signal(bool()) for _ in range(8)] \n",
    "    c = [ Signal(bool()) for _ in range(8)] \n",
    "\n",
    "    logic = [\n",
    "    #                                  (0)   (1)   (2)\n",
    "    #                                   |     |     |\n",
    "        *full_adder(v[0], v[1], v[2], s[0], c[0]),\n",
    "        *full_adder(v[3], v[4], v[5], s[1], c[1]),\n",
    "        *half_adder(v[6], v[7],       s[2], c[2]),\n",
    "        #                               |     |\n",
    "        #                              (0)   (1)\n",
    "        *full_adder(s[0], s[1], s[2], s[3], c[3]),  # (0)\n",
    "        #                               |     |     |\n",
    "        *full_adder(c[0], c[1], c[2],       s[4], c[4]),  # (1)\n",
    "        #                               |     |     |    \n",
    "        *half_adder(c[3], s[4],             s[5], c[5]),\n",
    "        #                               |                 |\n",
    "        *half_adder(c[4], c[5],                   s[6], c[6]),\n",
    "\n",
    "    ]\n",
    "    #                                   |     |     |     |\n",
    "    bits = [                          s[3], s[5], s[6], c[6]    ]\n",
    "        \n",
    "    logic += [ sum_ones.set(concat(*reversed(bits))) ]\n",
    "    return logic\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "aff6ec8d-d134-444f-8d00-cd44f102a206",
   "metadata": {},
   "outputs": [],
   "source": [
    "N = 8\n",
    "# This will take a long time without acceleration:\n",
    "# verify(N, bit_count8)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}