Physical level

The protocol starts when a sender pulls exactly one wire low. If two or more wires are pulled low, there is an (initial) collision; the senders pulling down the lower-numbered wire(s) will immediately de-assert the line. The lowest-priority wire shall be the one labelled zero.

A sender must not start unless the bus has been idle (all-high) for at least 3.5 ticks. Exception: retries after a collision may start 2.5 ticks after the line has returned to idle state, as described below. (Backing off due to lost bus arbitration is not a collision.)

The sender chops the message into unsigned integers and sends those in base[2^n-1] encoding, by adding one to each digit and flipping the affected bits. It detects collisions (a wire is pulled low which should not be) and retries as soon as possible.

The integer's size depends on n:

bits = 8 if n==2 else 16 if n==3 else 32

An idle time of more than 1.5 ticks with a signal asserted is a hard protocol error. All nodes which notice the problem shall assert all bus lines, wait 2.5 ticks, and release the bus.

Transmission algorithm (plaintext)

• the sender waits for an idle bus, then sets one bit as per priority. If any higher bits are set, it clears its bit and repeats. Otherwise it waits until exactly one bit is set, plus one tick.

• the message is prefixed with a length byte. If the length is >127, the length is extended to two bytes; the lower 7 bits are stored in the first byte (with the high bit set). Messages >32767 bytes are not supported.

• a 16-bit checksum is appended to the message. The checksum includes the length bytes.

• the sender segments the message into 8-, 16- or 32-bit unsigned integers and sends them, consecutively, in base[2^n-1] encoding by adding one to each digit, converting the digit to base-2, and then flipping the state of those wires whose bits are set. Lower-valued digits are sent first.

• If there is a collision, the sender immediately turns itself off, waits for the bus to become idle, and retries some random time later.

  Depending on the colliding values, this may cause both senders to abort. To avoid a repeat collision, senders use the lowest-numbered wire which they did not set during the collision as their new priority and may restart their transmission early (2.5 ticks after idle bus). If a sender loses this arbitration after restart, it must wait 3.5 ticks for a second chance.

• A recipient starts when at least one wire leaves the idle state. It waits for bus arbitration to settle, then reads the first integer(s), decodes them, and extracts the packet length. It then continues to read until the buffer is full. If the bus is idle before the packet is complete, there probably was a mutual collision; reception is aborted.

• Waiting for bus idle: start a 1.5 tick timer. When a wire changes state, reset the timer. When the timer completes and the bus is not idle, start fatal error handling.

• Arbitration: An arbitration cycle may be longer due to collision resolution: use a 2 tick timer to monitor bus state.

• Fatal error handling: pull all lines low, wait 4 ticks, release all lines, wait until they're all clear (this should not take longer than 2 ticks, but we already had a fatal error, so who knows), wait 4 ticks before sending. Nothing may change on the bus during that time, except for the last 0.5 ticks.

  If this method fails, well … try again, and hope that the offender resets itself before long.

Transmission algorithm (Python)

In Python, the algorithm would probably look like this:

from math import ceil, log
from checksum import ccitt16
import wires

n = 2 ## number of wires

bits = 8 if n==2 else 16 if n==3 else 32
chunk = bits>>3

width = (1<<n) -1
items = ceil(log(1<<bits)/log(width))

def sender(prio:int, data:bytearray, send_early:bool=False):
    while True:
        wires.wait_idle(short_wait=1 if send_early else 0)
        state = wires.set(1<<prio)
        if state < 1<<(prio+1):
            while state != 1<<prio:
                # We need to wait for a reasonable state
                state = wires.get()
            if wires.get(immediate=True) == state:
                break
        wires.set(0, immediate=True)
        send_early = False

    # At this point, we have set the highest-numbered wire.

    n = len(data)
    if n > 127:
        data[0:0] = ((n|128)&0xFF, n>>7)
    else:
        data[0:0] = (n,)
    chk = ccitt16(data)
    data.append((chk>>8,chk&0xFF)

    while data:
        x = bytes[0]
        if chunk > 1:
            x |= bytes[1]<<8
        if chunk > 2:
            x |= bytes[2]<<16 | bytes[3]<<24
        del bytes[0:chunk]

        for i in range(items):
            x,res = divmod(x,width)
            state ^= res+1
            nstate = wires.set(state)
            if nstate != state:
                wires.set(0, immediate=True)
                nstate &= ~state
                if nstate == 0:
                    raise RuntimeError("This cannot happen")
                prio = 0
                while not (nstate & (1<<prio)):
                    prio += 1
                return sender(prio, data, send_early=True)
                # Yes, tail recursion is ugly, but this isn't real code anyway

    wires.set(0)

def receive():
    def receive_one():
        # read one block, return as bytearray
        nonlocal state
        f = 1
        res = 0
        for i in range(items):
            ostate = state
            state = wires.get() # will raise an error on timeout
            b = (state^ostate)
            if not b:
                raise RuntimeError("Cannot happen")
            res += (b-1)*f
            f *= width
        bytes = bytearray(chunk)
        for i in range(chunk):
            bytes[i] = res & 0xFF
            res >>= 8
        return bytes

    # Wait
    # Real code would set an 1.5 ticks timer "start reading" that's
    # reset whenever a wire changes state; when that timer runs out and
    # a bit is set, start fatal error processing
    while True:
        wires.wait_idle(short_wait=2)
        state = wires.get()
        while state & (state-1): # more than one bit is set
            state = wires.get(immediate=True)
        if state:
            break

    bytes = receive_one()
    n = bytes[0]
    if n > 128:
        n &= 0x7F
        if chunk == 1:
            bytes += receive_one()
        n |= bytes[1]<<7
    while len(bytes) < n+2:
        bytes += receive_one()
    del bytes[n+2:]
    if ccitt16(bytes) != 0:
        raise ProtocolError("Checksum")
    del bytes[n:]
    del bytes[0:1+(n>127)]
    state = wires.get()
    if state:
        raise RuntimeError("Long packet!")
    return bytes