The MOS 6502’s Parallel Binary/BCD Adder patent expired today!

The patent for the 6502’s ALU adder circuits expired today, by chance the same day I wrote a BCD adder in Verilog to go with a toy 6502ish CPU I am designing. So, I thought I’d re-implement it loosely based on the MOS solution.

U.S. Patent Nov. 9, 1976 Sheet 1 of 3 3,991,307

The following schematic is unlikely to be needed, but might shed some light on the details. The scans have been pasted together, but don’t quite align towards the bottom. Some squinting will be required to make sense of it. There are a few lines that look unconnected, which I assume are just separators.

Schematic of the Parallel Binary/BCD of the MOS 6502 from patent US3991307

Roughly, the schematic is formed by three columns, the left side defines the binary adder, the middle shows the decimal carry calculation, and the right side generates the decimal correction.

The patent text really just describes the gates implemented above. However, it talks about them logically, rather than referring to the actual gates used, so unless you can apply De Morgan’s’ laws as you read (I can’t!), then it will be slow going trying to figure it all out.

The C code below is a behavioural implementation of the circuits described in the patent. It doesn’t overlap exactly the diagram in Fig.1, e.g. the carry flags are generated in the adder module rather than being derived separately using gates.

The code in the main() block generates test data output for the adder, the decimal corrector, and then both parts combined into two 4-bit adders.

#include <stdio.h>
#include <stdbool.h>

/*
 * The Parallel Binary Adder - (4-bit) module.
 */
void pbAdder(
        unsigned char A,        // 4-bit nibble
        unsigned char B,        // 4-bit nibble
        bool Cin,               // Carry in
        unsigned char *BS,      // Binary Sum
        bool *BC,               // Binary Carry
        bool *DC)               // Decimal Carry
{
        // Sanitise 8-bit values to 4 bits.
        A = A & 0xf;
        B = B & 0xf;

        *BS = (A + B + Cin) & 0xf;
        *BC = ((A + B + Cin) & 0x10) != 0;
        *DC = (A + B + Cin) > 9;

        printf("A=%d, B=%d, BS=%d, BC=%d, DC=%d\n", A, B, *BS, *BC, *DC);
}

/*
 * Decimal correction gating, generating DS (final ACC output)
 */
void dcGating(
        unsigned char BS,       // 4-bit Binary Sum
        bool DAA,               // Decimal Addition flag
        bool DSA,               // Decimal Subtraction flag
        unsigned char *DS)      // Decimal Sum (or Binary pass-thru)
{
        bool BS0 = (BS & 1);
        bool BS1 = (BS & 2) >> 1;
        bool BS2 = (BS & 4) >> 2;
        bool BS3 = (BS & 8) >> 3;

        bool DS0 = BS0;
        bool DS1 = (DAA | DSA) ^ BS1;
        bool DS2 = ((DSA & BS1) | (DAA & ~BS1)) ^ BS2;
        bool DS3 = ( ((BS1 | BS2) & DAA) | (~BS1 | ~BS2) & DSA) ^ BS3;

        printf("BS: %d%d%d%d\t", BS3, BS2, BS1, BS0);
        printf("DS: %d%d%d%d\n", DS3, DS2, DS1, DS0);

        // Select DS if resulting decimal is 0xa thru 0xf
        *DS = (DAA | DSA) & BS3 & (BS1|BS2)
                ? DS3 << 3|DS2 << 2|DS1 << 1 | DS0
                : BS3 << 3|BS2 << 2|BS1 << 1 | BS0;
        printf("ACC OUT: %02X\n", *DS);
}

void main()
{
        // Test some 4-bit addition and carry outputs.
        unsigned char sum;
        bool BC3;       // Binary Carry from adder bit 3
        bool DC3;       // Decimal Carry from adder bit 3

        // Test data 1 - mostly boundary cases. {A, B, Cin}
        unsigned char td1[][3] = { {1,2,0}, {8,1,0}, {8,1,1},
                {9,1,0}, {9,1,1}, {14,1,0}, {14,1,1} };
        int num_td1 = sizeof(td1) / sizeof(*td1);

        int i;
        for(i=0; i < num_td1; i++) {
                pbAdder(td1[i][0], td1[i][1], td1[i][2],
                        &sum, &BC3, &DC3);
        }

        // Enumerate all adder outputs, with decimal corrections.
        unsigned char accumulator;

        for(i=9; i < 16; i++) {
                printf("\n");

                dcGating(i, 1, 0, &accumulator);
        }
        printf("\n");

        // Test combination of two 4-bit adders

        unsigned char td2[][5] = {
                {0, 15, 0, 0, 0},
                {240, 15, 0, 0, 0},
                {0x98, 1, 0, 1, 0},
                {0x98, 1, 1, 1, 0},
                {0x98, 2, 0, 1, 0},
                {0x99, ~2, 1, 0, 1},
                {0x99, ~0x22, 1, 0, 1},
                {100, ~2, 1, 0, 0}
        };
        int num_td2 = sizeof(td2) / sizeof(*td2);

        for(i=0; i < num_td2; i++) {

                unsigned char A=td2[i][0], B=td2[i][1];
                bool Cin = td2[i][2];
                bool DAA=td2[i][3], DSA=td2[i][4];
                unsigned char sumL, sumH;
                unsigned char ACC;

                printf("A:%02X (%d), B:%02X (%d), Cin:%d\n",
                        A, A, B, B, Cin);

                pbAdder(A&0xf, B&0xf, Cin, &sumL, &BC3, &DC3);
                dcGating(sumL, DAA, DSA, &sumL);
                pbAdder((A&0xf0)>>4, (B&0xf0)>>4, DAA&DC3|BC3,
                        &sumH, &BC3, &DC3);
                dcGating(sumH, DAA, DSA, &sumH);

                ACC=sumH * 16 + sumL;
                printf("8-Bit OUT: 0x%02X (%d) BC=%d, DC=%d\n\n",
                        ACC, ACC, BC3, DC3);
        }
}

A:00 (0), B:0F (15), Cin:0
A=0, B=15, BS=15, BC=0, DC=1
BS: 1111        DS: 1111
ACC OUT: 0F
A=0, B=0, BS=0, BC=0, DC=0
BS: 0000        DS: 0000
ACC OUT: 00
8-Bit OUT: 0x0F (15) BC=0, DC=0

A:F0 (240), B:0F (15), Cin:0
A=0, B=15, BS=15, BC=0, DC=1
BS: 1111        DS: 1111
ACC OUT: 0F
A=15, B=0, BS=15, BC=0, DC=1
BS: 1111        DS: 1111
ACC OUT: 0F
8-Bit OUT: 0xFF (255) BC=0, DC=1

A:98 (152), B:01 (1), Cin:0
A=8, B=1, BS=9, BC=0, DC=0
BS: 1001        DS: 1111
ACC OUT: 09
A=9, B=0, BS=9, BC=0, DC=0
BS: 1001        DS: 1111
ACC OUT: 09
8-Bit OUT: 0x99 (153) BC=0, DC=0

A:98 (152), B:01 (1), Cin:1
A=8, B=1, BS=10, BC=0, DC=1
BS: 1010        DS: 0000
ACC OUT: 00
A=9, B=0, BS=10, BC=0, DC=1
BS: 1010        DS: 0000
ACC OUT: 00
8-Bit OUT: 0x00 (0) BC=0, DC=1

A:98 (152), B:02 (2), Cin:0
A=8, B=2, BS=10, BC=0, DC=1
BS: 1010        DS: 0000
ACC OUT: 00
A=9, B=0, BS=10, BC=0, DC=1
BS: 1010        DS: 0000
ACC OUT: 00
8-Bit OUT: 0x00 (0) BC=0, DC=1

A:99 (153), B:FD (253), Cin:1
A=9, B=13, BS=7, BC=1, DC=1
BS: 0111        DS: 0001
ACC OUT: 07
A=9, B=15, BS=9, BC=1, DC=1
BS: 1001        DS: 0011
ACC OUT: 09
8-Bit OUT: 0x97 (151) BC=1, DC=1

A:99 (153), B:DD (221), Cin:1
A=9, B=13, BS=7, BC=1, DC=1
BS: 0111        DS: 0001
ACC OUT: 07
A=9, B=13, BS=7, BC=1, DC=1
BS: 0111        DS: 0001
ACC OUT: 07
8-Bit OUT: 0x77 (119) BC=1, DC=1

A:64 (100), B:FD (253), Cin:1
A=4, B=13, BS=2, BC=1, DC=1
BS: 0010        DS: 0010
ACC OUT: 02
A=6, B=15, BS=6, BC=1, DC=1
BS: 0110        DS: 0110
ACC OUT: 06
8-Bit OUT: 0x62 (98) BC=1, DC=1

The output from the 8-bit operations is shown in the right-hand column. Note that the patent is based on the NMOS version of the 6502, and predates the CMOS version that included changes to the way flags get handled.

The test data provides negative numbers pre-converted to 2’s complement form, which would normally be done within the ALU.

This code was written as an intermediate step to be subsequently converted to Verilog – I’m more familiar with C, so this made sense to me. A hardware engineer would doubtless go straight to the testbench.

The Verilog code below behaviourally describes the 4 bit adder. The carry input to the next 4-bit adder is Cdec (decimal carry), though in the full implementation this would be DAA & Cdec | Cbin (decimal flag AND decimal carry, or binary carry).

/*
 * BCD Digit Adder
 * Given two 4 bit inputs and a carry, produce a BCD addition.
 */

module bcdAdder(
  input [3:0] A,
  input [3:0] B,
  input Cin,
  output [3:0] OUT,
  output Cbin,
  output Cdec
);

wire [4:0] binSum;

assign binSum = (A + B) + Cin;
assign OUT = (binSum > 9) ? binSum + 6 : binSum;
assign Cbin = binSum[4];
assign Cdec = binSum > 9;

endmodule

All those gates described in eight pages of a patent in the mid 1970s boil down to the simple behaviour above. What was arguably patentable a few decades ago is, given today’s tools, meaningless as any kind of ‘invention’. I see this as an example of why the patent system needs to keep pace with tools. What made sense in the mid 1970s is absurd today.

Anyway, I digress. Here’s the testbed code that puts two of these together to form an 8-bit BCD parallel adder, and generates signals to show typical and boundary calculations.

`timescale 1us / 1us

module bcdd_tb;

reg [7:0] A;
reg [7:0] B;
reg Cin;
wire [7:0] OUT;
wire hCbin;
wire hCdec;
wire Cbin;
wire Cdec;

initial begin
  $dumpfile("bcdd_tb.lxt");
  $dumpvars(0, bcdd_tb, A,B,Cin,OUT,hCbin,hCdec,Cbin,Cdec);

  // 1 + 7 = 8
  #0 Cin = 0;
  #0 A = 1;
  #0 B = 7;

  // 8 + 3 = 1 with C
  #1 Cin = 0;
  #0 A = 8;
  #0 B = 3;

  // 1 + 0 = 1
  #1 Cin = 0;
  #0 A = 1;
  #0 B = 0;

  // 8 + 0 + C = 9
  #1 Cin = 1;
  #0 A = 8;
  #0 B = 0;

  // 75 + 21 = 96
  #1 Cin = 0;
  #0 A = 8'h75;
  #0 B = 8'h21;

  // 98 + 1 + C = 100
  #1 Cin = 1;
  #0 A = 8'h98;
  #0 B = 8'h1;

  // 99 + 1 = 100
  #1 Cin = 0;
  #0 A = 8'h99;
  #0 B = 8'h1;

  #1 $finish;
end

bcdAdder bcdd1(
  A[3:0], B[3:0], Cin, OUT[3:0], hCbin, hCdec
);
bcdAdder bcdd2(
  A[7:4], B[7:4], hCbin|hCdec, OUT[7:4], Cbin, Cdec
);

The resulting waveforms are shown below, which includes both the nibble adders as well as the register inputs and outputs.

So, that’s good enough for now to go into the ALU of my toy 6502ish CPU. I have a mild urge to reproduce the schematic in Verilog at gate level, but I can’t face the (admittedly modest) boolean algebra needed. I’m not made of the same stuff as the folk who invented this stuff!

Something’s wrong with the Internet

Looking for a present for a four-turning-five year old who loves numbers, I figured I’d find some ideas around number cubes. Let’s see what maths cube toys I can find…

Where them cubes gone?

None in the top hits were even cube related, even those with ‘cube’ in the title did not actually refer to anything remotely cuboid in shape, nor characteristics. The irony of these search results tempers my frustration with at least a little humour. The rest of the results were no better.

I thought that Google images would give me a broader view that might help me spot something interesting.

Spot the cube.

No maths related cubes here – there are cubes that look fun, but just cubes, and there are maths toys that look at least interesting, but not really what I was looking for.

Yet I know there are businesses that seek out and carefully choose toys that are genuinely interesting and innovative. I’ve seen them in the past, I’m certain that there are lots more – why are my search results dominated by Amazon and eBay sellers peddling pretty much exactly the same stuff?

To be fair, I managed to find one site among the results that’s worth a browse, and the second time I did an image search, the results also included a power-of-two cube that looked interesting. But wow – talk about drowned out by the noise!

This isn’t a ‘things were better in the good old days’ sort of a rant. It’s a clear statement – discovery of sites on the World Wide Web used to be a lot better than it appears to be today.

LXD now runs my WordPress

Here are some notes on how I used LXD to run a container for WordPress. This is (a lot) more convenient than using Docker, which was my original approach to getting my WordPress site into a container.

Getting LXD onto Debian Stretch

LXD is installed on Debian via a Snap package, so sudo apt-get install snapd if this is not already installed. See https://docs.snapcraft.io/installing-snap-on-debian. Then run snap install lxd (see https://stgraber.org/2017/01/18/lxd-on-debian/) and log in again to get an updated command path to the new snap-installed binaries.

Run lxd init to configure the default environment, the storage type I chose was simply directories, since it’s the most convenient for moving files from the Docker setup that I’m migrating from.

Create and configure our container

When lxd is installed, create a new Debian container with lxc launch 'images:debian/9' susanet-wp.

Use lxc exec susanet-wp passwd to set a root password, then lxc console susanet-wp to log into the console. From here we can install the required packages.

apt-get install apache2 php-curl php-gd php-intl php-mbstring php-soap 
php-xml php-xmlrpc php-zip libapache2-mod-php php-mysql
libphp-phpmailer mariadb-server mariadb-client iputils-ping
exim4-daemon-light curl wget netcat

From here it’s pretty much a normal WordPress installation. Since I was migrating from another database, the commands used to get MariaDB set up were as follows: –

create database wp_db
create user 'wp_user'@'localhost' identified by '<db password>'
grant all privileges on wp_db.* to 'wp_user'@'localhost'
flush privileges

I used this command to install my SQL dump file taken from the old Docker setup: –

zcat kakapo_wordpress_db.gz|lxc exec susanet-wp -- mysql wp_db 

Some notes on LXD

LXD creates containers from locally stored images, though these images might themselves be fetched from a remote server.

There are a number of pre-configured public repositories, which can be viewed with lxc remote list, and if you have another LXD installation elsewhere, then this can be used as a further remote server.

The command to register a new remote server is lxc remote add myremote 10.81.1.4, where the IP address is that of another server running LXD, and ‘myremote’ is the alias by which I want to refer to the remote server.

Note that the remote server must be exposed on port 8443 (by default) of the specified IP. A password also has to be defined – clients will be prompted for this when adding this remote server. The following commands will configure the remote server.

lxc config unset core.https_address
lxc config set core.https_address [::]:8443
lxc config set core.trust_password <my_remote's password>

A snapshot in LXD refers to the state of a container as at a specific point in time, and can be used to easily restore the state of the container.

An image can be created from a stopped container, or from a snapshot of a running container. The following commands are listed as examples of usage: –

lxc snapshot susanet-wp my-snapshot
lxc publish susanet-wp/my-snapshot --alias my-new-image
lxc delete susanet-wp/my-snapshot

The snapshot command takes a snapshot of the given container. The publish command creates a local image from this snapshot, and the delete command removes the snapshot (assuming you no longer want it).

Putting the above together, this can be used to copy a container to a backup server. The main local server would be configured to bind to an IP address/socket and given a password, and the backup server adds this as a remote. It can then ‘launch’ this image.

Alternatively, it’s even possible to simply push a local image to a backup server: –

lxc launch my-new-image myremote:susanet-backup

In this case, my local image ‘my-new-image’ is created on a remote server I aliased as ‘myremote’, and the new container on the remote server is called ‘susanet-backup’.

Networking to the outside world

A container can be given an interface on the bridge using something like the following: –

lxc config device add susanet-wp eth0 nic name=eth0 nictype=bridged parent=lxdbr0

We can use DNAT to forward host ports (e.g. on an external IP address) to the bridged interface using something like the following: –

iptables -t nat -A PREROUTING -i eth0 -p tcp --dport 80 -j DNAT \
--to-destination 10.102.22.71:80

iptables -t nat -A PREROUTING -i eth0 -p tcp --dport 443 -j DNAT \
--to-destination 10.102.22.71:443

A possibly simpler and more convenient way to connect the container to an external IP address is to use the ‘proxy’ device. This connects an ip:port address on the host to an ip:port in the container, so: –

kevin@vps1:~$ lxc config device add susanet-wp http proxy \
listen=tcp:0.0.0.0:80 connect=tcp:127.0.0.1:80
kevin@vps1:~$ lxc config device add susanet-wp https proxy \
listen=tcp:0.0.0.0:443 connect=tcp:127.0.0.1:443

would connect port 80 on all host interfaces to port 80 on the container’s localhost interface.