Solving Advent Of Code on FPGAs with Haskell Clash

This post presents how I solved the Advent Of Code (AOC) day four on a Field-Programmable Gate Array (FPGA) chip using Clash:

• First, I introduce the specifics of hardware design with Clash.

• Next, I demonstrate three incremental designs to solve the first few problems.

• Finally, I show how to compute the solutions on real hardware.

This post contains many code snippets for Haskell programmers and the full source code is available in my advent-of-clash repository. To dive deeper into how that works, I can only recommend the Retrocomputing with Clash book.

I invite you to follow along with this post by starting a REPL like this:

$ git clone https://codeberg.org/TristanCacqueray/advent-of-clash
$ cd advent-of-clash
$ nix run git+https://codeberg.org/TristanCacqueray/clash-osc#ghci
λ> import Clash.Prelude
λ> :load AdventOfClash.Utils
[1 of 1] Compiling AdventOfClash.Utils ( AdventOfClash/Utils.hs, interpreted )
Ok, one module loaded.
λ> showDigit 7
0b0011_0111

Introduction

FPGAs are digital circuits that can be programmed at a very low level using a Hardware Description Language (HDL). Clash is a functional HDL, that compiles high-level designs written in Haskell down to a low-level synthesizable HDL, such as Verilog. AOC is an advent calendar made of small programming puzzles, each consisting of a problem description, a text input and the expected output. AOC has always been a great way for me to learn a new programming language as the puzzles gradually introduce new concepts within the language.

Day four’s problem involved processing a grid similar to a single-rule Game Of Life. This was an interesting challenge because I only had a superficial understanding of Clash. Solving this puzzle has prompted me to implement my own RAM machine, a fundamental building block I hadn’t worked with before.

Clash Prelude

Before diving into FPGA designs, this section introduces the Clash standard library named clash-prelude. It provides alternative data types and APIs made specifically for creating hardware designs. This is necessary because the core data types provided by the Haskell standard library are not suitable for HDL synthesis.

KnownNat

Most of Clash’s API relies on the KnownNat constraint to express static sizes. They are type-level naturals that contain their values in their types. This compile-time size information is important for FPGAs because the integrated circuits (IC) must be inter-connected with exact bit-width wires before synthesis. This requires the DataKinds Haskell language extension to be able to use term-level values at the type-level. Thus, Clash uses singleton types for type-level natural numbers defined in Clash.Promoted.Nat with this constructor:

SNat :: KnownNat n => SNat n

… which can be created like that:

-- 41 is a type-level KnownNat value.
myNat :: SNat 41
myNat = SNat

-- 21 is also a KnownNat, declared with a type application inline.
twentyOne = SNat @21

SNats can be used to do type-level computation, for example:

-- From Clash.Promoted.Nat:
succSNat :: SNat a -> SNat (a + 1)
mulSNat  :: SNat a -> SNat b -> SNat (a * b)

Note

These type definitions are rather special because they include type-level operations such as a + 1 or a * b.

The SNat values are known at compile time, for example by inferring the final type:

λ> :t succSNat myNat
succSNat myNat :: SNat 42

λ> :t mulSNat twentyOne (SNat @2)
mulSNat twentyOne (SNat @2) :: SNat 42

Tip

To improve the ergonomics of KnownNats, Clash provides custom compiler plugins to solve the constraints for advanced usage. The REPL must be set up this way:

ghci -XDataKinds -fplugin GHC.TypeLits.KnownNat.Solver -fplugin GHC.TypeLits.Normalise -fplugin GHC.TypeLits.Extra.Solver

Singletons like SNats took me a bit of time to get used to, though they are not too complicated in practice. This Unfolder episode #50 provides a solid explanation on how they work and why they are necessary.

BitPack Constraint

Thanks to KnownNat, the Clash prelude features fixed-size data types that can be efficiently represented at the bit level.

Sized Integers

Clash provides its own data types to represent fixed-size integers:

• Unsigned n is analogous to Words.

• Signed n is analogous to Ints.

For example, Signed 64 is equivalent to Int64, or Unsigned 8 is like Word8. These data types come with convenient bitCoerce and resize functions to convert between representations:

resizeDemo :: Signed 8 -> Signed 16
resizeDemo = resize

bitCoerceDemo :: Signed 8 -> Unsigned 8
bitCoerceDemo = bitCoerce

bitResizeDemo :: Signed 8 -> Unsigned 16
bitResizeDemo = resize . bitCoerce

These new data types are powerful as they enable defining arbitrarily sized numbers, that are not limited to multiples of two. For example, here is the maximum number that can be represented with 13-bits:

λ> maxBound :: Unsigned 13
8191

These new data types are essential in hardware design because they let you use exactly the right number of bits (like 13 instead of 16) to match the number of wires between ICs (e.g. 13-bit is 13 physical wires). Unlike raw bit manipulation, the BitPack constraint provides type safety to prevent width mismatches that would cause synthesis errors.

Clash also provides the Index n type for values that goes from 0 to n. They are useful for countable things, like vector positions, or digits as shown in in the next sections.

Sized Vectors

Haskell’s lists are not suitable when using Clash because they can have unbounded size. Instead, Clash prescribes the following vector type:

-- From Clash.Sized.Vector:
data Vec :: Nat -> Type -> Type where
  Nil :: Vec 0 a
  Cons :: a -> Vec n a -> Vec (n + 1) a

pattern (:>) :: a -> Vec n a -> Vec (n + 1) a

As you can see, the empty vector Nil has a type-level size of 0, and adding an element increases its size by 1. For example, creating a vector looks like this:

λ> myVec  = 4 :> 2 :> Nil
λ> :t myVec
myVec :: Vec 2 Int

Note

Notice how the inference automatically keeps track of the number of elements at the type-level.

To initialize a vector, the repeat function can be used:

repeat :: KnownNat n => a -> Vec n a

And here are some examples from the Clash.Sized.Vector module:

head :: Vec (n + 1) a -> a
(++) :: Vec n a -> Vec m a -> Vec (n + m) a
zip  :: Vec n a -> Vec n b -> Vec n (a, b)

The Vec API provides strong type safety when manipulating lists of values, for example:

• head ensures that the vector has at least 1 element.

• ++ returns a concatenated vector whose length is the sum of the argument lengths.

• zip only works with vectors of the same length.

Here is how compilation errors look like when the vector lengths don’t match:

λ> zip (4 :> 2 :> Nil) (1 :> Nil)

<interactive>:5:20: error: [GHC-83865]
    • Couldn't match type ‘1’ with ‘2’
      Expected: Vec 2 a
        Actual: Vec 1 a
    • In the second argument of ‘zip’, namely
        ‘(1 :> Nil)’

BitVector

Clash provides a custom data type for raw bits called BitVector n analogous to ByteString:

-- From Clash.Class.BitPack:
pack   :: BitPack a => a -> BitVector (BitSize a)
unpack :: BitPack a => BitVector (BitSize a) -> a

That can be used that way:

λ> pack (7 :: Index 10)
0b0111
λ> resize @BitVector @_ @8 $ pack  'A'
0b0100_0001

Here are a few example helpers to convert ASCII Char:

-- From AdventOfClash.Utils:
type Byte = BitVector 8

-- Truncate unicode to ascii byte:
charPack :: Char -> BitVector 8
charPack = resize @BitVector @21 @8 . pack

-- Expand ascii to full Haskell's char size
charUnpack :: BitVector 8 -> Char
charUnpack = unpack . resize @BitVector @8 @21

Binary Coded Decimal

Binary Coded Decimal (BCD) is a special encoding for decimal numbers that can be more efficient than regular integers when handling base 10 numbers. BCD will be useful to output the AOC’s solutions because they consist of decimal numbers. With Clash, BCD can be defined like this:

type Digit = Index 10
type BCD n = Vec n Digit

To determine the length of a BCD representation for a given integer, the following type-level function can be used:

-- From RetroClash.BCD:

-- Compute the digit count for a given /n/ bit sized number
type BCDSize n = CLog 10 (2 ^ n)

-- | Convert Unsigned number to a list of digit
toBCD :: forall n. (KnownNat n) => Unsigned n -> BCD (BCDSize n)

… which can be used that way:

λ> import RetroClash.BCD
λ> toBCD (42 :: Unsigned 13)
0 :> 0 :> 4 :> 2 :> Nil

Info

toBCD is able to produce the right vector size for a given number type (here, 4 digits are needed to display a 13-bit number) thanks to BCDSize, which performs the computation at compile time.

To summarize, here are the new typeclasses introduced by Clash:

• BitPack a to convert types, and compute the number of bits needed to represent elements of type a. Provides: pack, unpack and bitCoerce

• Resize f to coerce a value to be represented by a different number of bits. Provides: resize

• SaturatingNum a to handle overflow and underflow behavior. Provides: satAdd, satSub, …

Now that we understand Clash’s type-level data structures, we need to explore how these types interact with hardware timing. Unlike pure functional programming where computations are timeless, most FPGA designs must account for clock cycles and state changes.

Register Transfer Level

Before moving on to solving the Advent Of Code with an FPGA, I need to introduce one more Clash primitive to define wires and create registers. In digital circuits, Register Transfer Level modeling (RTL) is a design abstraction at the base of HDLs:

FPGAs are essentially made of logic gates such as NAND gates. To model stateful computations, we need to define how often the state gets updated and where to store the value that is being computed. Thus, RTL is a synchronous model that consists of:

• Sequential logic made of registers (like flip-flops or latches) that are updated at every clock cycle.

• Combinational logic that processes the values and feeds its output back to the register.

Clock

Clash’s clocks are parameterized by a domain type variable, usually named dom, that describes its frequency and other properties like its active-edge. Thanks to type-level computation, clock dividers can be obtained using the domain type variable:

-- From RetroClash.Clock:
type ClockDivider dom ps = ps `Div` DomainPeriod dom

type Nanoseconds  (ns :: Nat) = 1_000 * ns
type Microseconds (us :: Nat) = Nanoseconds  (1_000 * us)
type Milliseconds (ms :: Nat) = Microseconds (1_000 * ms)

Clash provides a default clock, named System running at 100MHz, and the number of cycles for a given duration can be computed this way:

-- 10 nanoseconds at 100MHz lasts for 1 cycle
λ> SNat :: SNat (ClockDivider System (Nanoseconds 10))
SNat @1

-- 42 ms at 100MHz lasts for 4.2 million cycles
λ> SNat :: SNat (ClockDivider System (Milliseconds 42))
SNat @4_200_000

The clock domain type variable enables writing circuits that work for any clock by using the KnownDomain constraint:

-- From Clash.Signal:
class (KnownSymbol dom, KnownNat (DomainPeriod dom)) => KnownDomain (dom :: Domain)

Note

This allows you to write a single circuit design that can be reused across FPGAs with different clock without modifying the code.

Moreover, a register also needs a reset and an enable line, so instead of passing all these wires around, the following constraint can be used instead:

type HiddenClockResetEnable dom = (HiddenClock dom, HiddenReset dom, HiddenEnable dom)

That way, the clock can be set only once, at the root of the design with:

withResetEnableGen :: KnownDomain dom => (HiddenClockResetEnable dom => circuit) -> Clock dom -> circuit
withResetEnableGen circuit clk = withClockResetEnable clk resetGen enableGen circuit

Info

This helper takes a circuit constrained by HiddenClockResetEnable and a Clock, and it removes the constraint by connecting the clock, reset and enable lines automatically and returning a fully connected circuit.

Register

A register is essentially a signal that remembers its previous value. While a Signal represents any time-varying value, a register specifically stores state across clock cycles. Here is how to create a register with Clash:

-- From Clash.Signal:
register :: (HiddenClockResetEnable dom, NFDataX a) => a -> Signal dom a -> Signal dom a

Note

NFDataX is an extra constraint for values that are passed in Signals. It can be derived automatically like NFData.

This definition precisely models the register as shown in the RTL diagram above: it takes an initial value with the input value signal, and it produces the output value signal. Signal implements the applicative typeclass, which means idiomatic Haskell code can be used to manipulate them. For example, here is how to create a component that counts up to 5 repeatedly using a register:

count2five :: (HiddenClockResetEnable dom) => Signal dom (Index 5)
count2five = counter
  where
    counter = register 0 (satSucc SatWrap <$> counter)

Note

Notice how the counter is defined recursively. Its next value is produced based on the previous one in a feedback loop, which is exactly how RTL designs function. If you are curious, here is how Clash compiles this code into verilog: Count2Five.v.

Clash provides a few operators that work well with Signals:

mux    :: Applicative f => f Bool -> f a -> f a -> f a
(.&&.) :: Applicative f => f Bool -> f Bool -> f Bool
(.||.) :: Applicative f => f Bool -> f Bool -> f Bool

Tip

mux is like an if statement that can be used with signals.

Here is another example component that discards repeated Just in a stream of Maybe values by storing the last seen value in a local register named prev:

onceJust :: (HiddenClockResetEnable dom, NFDataX a) => Signal dom (Maybe a) -> Signal dom (Maybe a)
onceJust i = mux (hasChanged <$> prev <*> i) i (pure Nothing)
  where
    hasChanged Nothing (Just _) = True
    hasChanged _ _ = False
    prev = register Nothing i

Lastly, signals can be simulated with sample:

-- From Clash.Signal:
sample :: (KnownDomain dom, NFDataX a) => (HiddenClockResetEnable dom => Signal dom a) -> [a]

… which can be used like this:

λ> take 13 $ sample @System $ count2five
[0,0,1,2,3,4,0,1,2,3,4,0,1]

λ> take 6 $ sample $ onceJust @System [Nothing, Just 42, Just 42, Nothing, Just 23]
[Nothing,Just 42,Nothing,Nothing,Just 23,Nothing]

Bundle

Lastly, Clash provides an extra feature to help with signal handling: Bundle. When working with complex circuits that have multiple input and output signals, managing them individually becomes cumbersome. Bundle provides a way to treat related signals as a single unit that can be used to group and ungroup multiple signals. Here are a couple of examples:

bundleTuple   :: (Signal dom a, Signal dom b) -> Signal dom (a, b)
bundleTuple = bundle

unBundleTuple :: Signal dom (a, b) -> (Signal dom a, Signal dom b)
unBundleTuple = unbundle

Bundles are implemented using a GHC feature called “Associated Types”, which can be confusing. Writing concrete helpers, like the above examples, may be helpful to fix weird compilation errors.

Summary

Before implementing the AOC solution, let’s recap the key Clash concepts we’ll be using:

• Clash provides arbitrary-sized data types like Index n that can be converted into bits thanks to the KnownNat n type-level machinery.

• The Resize and BitPack typeclasses can be used to change the representation in place of the usual Num type conversion helpers.

• RTL is a synchronous model that is used to implement stateful computations with Clash’s Signal.

• The HiddenClockResetEnable dom constraint is used to implement RTL with an implicit clock.

• Signals can be simulated in the ghci interpreter with sample.

• Clash comes with GHC plugins to enable compile-time calculations, for example, to compute ClockDividers.

Equipped with these new abstractions, the next sections describe how to solve AOC’s puzzles.

Mealy Machine

To implement puzzle solvers efficiently, I used Mealy machines, a fundamental model in digital design that combines state and computation. The first puzzle can be solved using a fixed computation performed on the puzzle input, one byte at a time. Thus, the following simple circuit design can be used to get started:

-- From AdventOfClash.Simple01:
type Solver dom = Signal dom Byte -> Signal dom Byte

Info

This type means that, for a given clock domain, a solver consumes a stream of bytes from the puzzle input, and it produces a stream of bytes containing the solution.

Since the signals are synchronous and I needed to handle variable-length inputs, I defined the following protocol for input/output:

• The “end of text” byte (0x03) is used to indicate the end of the transmission.

• “NUL” bytes (0x00) are ignored.

Stateful Computation

Clash provides a helper to create Mealy machines by lifting pure stateful computations into the world of signals using this API:

-- From Clash.Prelude.Mealy:
mealyS :: (HiddenClockResetEnable dom, NFDataX s) => (i -> State s o) -> s -> Signal dom i -> Signal dom o

Note

The first parameter is the Mealy transfer function: it is called for every input i and it updates the machine state s as it produces the desired output o, which is the i -> State s o type.

Info

State is defined in the standard transformers library as follows:

type State s = StateT s Identity
newtype StateT s m a = StateT { runStateT :: s -> m (a, s) }
get    :: (Monad m) => StateT s m s
put    :: (Monad m) => s -> StateT s m ()
modify :: (Monad m) => (s -> s) -> StateT s m ()

It’s a very common Haskell abstraction that is used to express all sorts of stateful computations. And it’s truly remarkable that Clash enables using such a high-level construct to design digital circuits.

This Mealy machine abstraction takes care of the sequential logic using registers so that the transfer function can focus on the combinational logic part of the circuit. Thus, to solve the first puzzle, I used the following PureSolver definition, which can be converted to the desired Solver interface using mealyS:

type PureSolver s = Byte -> State s Byte

mkSolver :: (HiddenClockResetEnable dom, NFDataX s) => PureSolver s -> s -> Solver dom
mkSolver = mealyS

Tip

It is often useful to write down the desired concret types for a polymorphic function like mealyS to help resolve compilation errors.

Solving Day 1

Solving the first puzzle requires checking whenever a dial rotation crosses the zero position. To keep track of the dial position and the final solution, I created the following state:

-- From AdventOfClash.Day01:
data St = MkSt
    { status :: Status
    -- ^ The current processing status
    , result :: Unsigned 32
    -- ^ The zero crossing count (the solution)
    , position :: Index 100
    -- ^ The last dial position
    }
    deriving (Eq, Show, Generic, NFDataX)

data Status
    = -- | Reading input
      Reading ReadStatus
    | -- | Writing the solution
      WritingOutput (OutputWriter (BCDSize 32))
    | -- | This is the end
      Completed
    deriving (Eq, Show, Generic, NFDataX)

data ReadStatus = Direction | Number Direction (BCD 3)
    deriving (Eq, Show, Generic, NFDataX)

initState :: St
initState = MkSt (Reading Direction) 0 50

… and here is the Mealy transfer function for solving this puzzle using an advance helper function below to update the result after each rotation:

-- type PureSolver s = Byte -> State s Byte
step :: PureSolver St
step 3 = do
    -- 'end of text' byte received
    modify $ \s -> s{status = WritingOutput $ startOutput $ toBCD s.result}
    pure 0
step n = do
    st <- get
    -- traceM $ "input: " <> show (charUnpack n) <> " state: " <> show st
    case st.status of
        -- Reading a byte
        Reading rs -> do
            modify $ case rs of
                Direction -> case n of
                    -- read the rotation direction
                    ByteChar 'L' -> setDir DLeft
                    ByteChar 'R' -> setDir DRight
                    _ -> error "bad direction?"

                Number dir buf -> case readDigit n of
                    -- read a single digit
                    Right d -> addNum dir buf d
                    -- the rotation input is complete, update the state
                    Left '\n' -> advance dir buf
                    _ -> error "bad num?"

            -- when reading input, the solver produces NUL byte.
            pure 0

        -- Writing the solution
        WritingOutput ow -> fromMaybe 0 <$> writeOutput Completed WritingOutput (\sts s -> s{status = sts}) ow

        -- When done, produce 'end of text' byte.
        Completed -> pure 3

-- | Helper to update the state when a new dial direction is received.
advance :: Direction -> BCD 3 -> St -> St
advance dir buf s = s{status = Reading Direction, position = pos, result = res}
  where
    -- update the new dial position
    pos = upd s.position $ readPos buf
    upd = case dir of
        DLeft -> satSub SatWrap
        DRight -> satAdd SatWrap

    -- check if the dial crossed the zero point
    res = s.result + case dir of
            DLeft  | pos > s.position -> 1 + cents
            DRight | pos < s.position -> 1 + cents
            _ -> cents

    -- add extra turns
    cents = resize . bitCoerce $ head buf

Note

Besides the custom types like Byte and BCD, this is in fact fairly standard Haskell code.

Writing the result

Once the solution is computed, I needed a way to print the result. Becauses the Mealy transfer function only produces one byte at a time, I created the following abstraction to keep track of which digit needed to be emitted:

data OutputWriter n = OutputWriter
    { printing :: Bool
    , value :: BCD n
    , pos :: Index n
    }
    deriving (Eq, Show, Generic, NFDataX)

startOutput :: (KnownNat n) => BCD n -> OutputWriter n
startOutput n = OutputWriter False n minBound

-- | OutputWriter takes care of writing one digit at a time, skipping the zeros prefix.
writeOutput :: (KnownNat n) => st -> (OutputWriter n -> st) -> (st -> s -> s) -> OutputWriter n -> State s (Maybe Byte)
writeOutput done next setStatus ow = do
    -- update the state, either with 'done' value, or the next output writer.
    modify $ setStatus $ maybe done next $ mow
    -- return the current digit to be transmitted.
    pure $ if disp then Just (showDigit digit) else Nothing
  where
    -- get the current digit
    digit = (ow.value !! ow.pos) :: Index 10
    -- start printing at the first non zero digit.
    nonZero = digit /= 0
    disp = ow.printing || nonZero
    -- stop printing when position exceed the BCD vector size
    mow = OutputWriter disp ow.value <$> succIdx ow.pos

Tip

This function is polymorphic over the machine state s so that it can be used with any state data type s for the other solutions.

Pure Simulation

Before deploying to hardware, it’s useful to verify the design. Mealy machines can be simulated directly by evaluating the transfer function manually without bothering to sample the signals. Here is a little simulator that runs the PureSolver directly on the puzzle input:

simulatePure :: forall s. (Show s) => PureSolver s -> s -> (String -> String)
simulatePure solver initialState = convertOutput . go initialState . encodeInput
  where
    go :: s -> [Byte] -> [Byte]
    go s (input : nextInput) =
        let (output, nextState) = runState (solver input) s
         in case output of
                -- end of text
                3 -> [3]
                -- ignore null byte
                0 -> go nextState nextInput
                -- output and keep on processing
                b -> b : go nextState nextInput

… and here is an example simulation with the trace to observe the state transitions:

λ> :load AdventOfClash.Simple01
λ> simulatePure step initState "L51\nR98\n"
input: 'L'  state: MkSt {status = Reading Direction, result = 0, position = 50}
input: '5'  state: MkSt {status = Reading (Number DLeft (0 :> 0 :> 0 :> Nil)), result = 0, position = 50}
input: '1'  state: MkSt {status = Reading (Number DLeft (0 :> 0 :> 5 :> Nil)), result = 0, position = 50}
input: '\n' state: MkSt {status = Reading (Number DLeft (0 :> 5 :> 1 :> Nil)), result = 0, position = 50}
input: 'R'  state: MkSt {status = Reading Direction, result = 1, position = 99}
input: '9'  state: MkSt {status = Reading (Number DRight (0 :> 0 :> 0 :> Nil)), result = 1, position = 99}
input: '8'  state: MkSt {status = Reading (Number DRight (0 :> 0 :> 9 :> Nil)), result = 1, position = 99}
input: '\n' state: MkSt {status = Reading (Number DRight (0 :> 9 :> 8 :> Nil)), result = 1, position = 99}
input: 3    state: WritingOutput
input: 0    state: MkSt {status = WritingOutput (OutputWriter False (0 :> 0 :> 2 :> Nil) 0), result = 2, position = 97}
input: 0    state: MkSt {status = WritingOutput (OutputWriter False (0 :> 0 :> 2 :> Nil) 1), result = 2, position = 97}
input: 0    state: MkSt {status = WritingOutput (OutputWriter False (0 :> 0 :> 2 :> Nil) 2), result = 2, position = 97}
input: 0    state: MkSt {status = Completed, result = 2, position = 97}
2

As you can see, the result is updated in the same cycle as the input is received, which made that first design particularly easy to implement. You can check the full code to solve the first puzzle in the Simple01 module. This simulation confirmed my implementation was correct and I used it to solve the first puzzle.

Summary

• Mealy machine transfer functions enable pure stateful computations to implement the solution core logic:

type PureSolver s = Byte -> State s Byte

• This section introduced the simplest design for processing puzzle input:

type Solver dom = Signal dom Byte -> Signal dom Byte

• Signals operate synchronously, updating the input/output at every clock cycle.

---

Machine Phase

The second puzzle required a different strategy because the solution could not be computed in a fixed number of cycles. The input contained ranges that needed an arbitrary number of steps to process. My first attempt used the following function:

countInvalid :: BCDs -> BCDs -> BCDs -> BCDs
countInvalid acc cur end
  | cur == end = newAcc
  | otherwise  = countInvalid newAcc (incrBCD cur) end
  where
    newAcc = acc + isInvalid cur

… which worked in simulation, but synthesizing this code was impossible because recursively defined functions are not allowed in Clash. This restriction makes sense because it can take an unknown amount of time to complete, and the compiler is not able to create a structural specification for such a circuit.

Since recursive functions cannot be synthesized into hardware, I needed a way to break the computation into discrete steps that the hardware could handle sequentially. Thus, I introduced a phase-based system so that the solver can indicate when it is ready to receive the next byte. The plan was that when a range is received, the solver would switch to a “busy” mode until it was ready to process the next byte. Thus, to solve the second puzzle I used the following design:

-- From AdventOfClash.Simple02:
type Solver dom =
    "INPUT" ::: Signal dom Byte ->
    ( "BUSY" ::: Signal dom Bool
    , "OUT"  ::: Signal dom (Maybe Byte)
    )

Tip

This second solver is similar to the first one but includes an additional output to indicate when it is busy. Its type features a special ::: type-level operator (see Clash.NamedTypes) which can be used to name the type to give them extra meaning.

Solver Output

Instead of producing the byte directly, the PureSolver can be expressed using this higher level output definition:

type PureSolver s = Byte -> State s SolverOutput

data SolverOutput
    = -- Need more time
      Busy
    | -- Need the next input byte
      ReadInput
    | -- Send an output byte
      Output Byte
    | -- This is the end
      Done
    deriving (Show)

This output data type looks a bit like a CPU instruction set, but unlike a regular CPU, my solver implementation is an integrated circuit that is not dynamically programmable: its behavior is fixed at synthesis time, baked directly into the circuit’s logic.

Info

This sum type approach is very convenient for hardware design like CPU instruction set. In languages without algebraic data types, a tagged union (or multiple flags) is needed to represent a CPU instruction, which can result in inconsistent states. With Haskell’s sum types, the compiler enforces that exactly one variant is active at any time, making invalid states unrepresentable.

Solving Day 2

Solving the second puzzle requires counting a number of elements in the given ranges. To keep track of the position in the range and the final count, I created the following state:

type NumCount = BCDSize 64

type BCDs = BCD NumCount

data St = MkSt
    { status :: Status
    -- ^ The current processing status
    , result :: BCDs
    -- ^ The number of invalid ID
    }
    deriving (Eq, Show, Generic, NFDataX)

data Status
    = -- | Reading a range
      ReadID Range BCDs BCDs
    | -- | Counting a range
      Counting BCDs BCDs
    | -- | Writing the solution
      WriteOutput (OutputWriter NumCount)
    | -- | This is the end
      Completed
    deriving (Eq, Show, Generic, NFDataX)

The main difference from the previous solution is that the step function can now return a “busy” output, so that it will be called again without advancing in the puzzle input:

-- type PureSolver s = Byte -> State s SolverOutput
step :: PureSolver St
step n = do
    st <- get
    case st.status of
        Counting cur end -> do
            let nextResult = processID st.result cur
                done = cur == end
                nextStatus
                    | done = initRead
                    | otherwise = Counting (addBCD (repeat 0 <<+ 1) cur) end
            put $ MkSt nextStatus nextResult
            -- Here, the solver can indicate if it needs more time.
            pure $ if done then ReadInput else Busy

        WriteOutput ow -> maybe Busy Output <$> advanceOutput ow
        Completed -> pure Done
        -- ReadID status is implemented like before.

This enables using a non-recursive implementation for the solutation that, instead of processing the whole range in one cycle with countInvalid, can now process one element per cycle with:

processID :: BCDs -> BCDs -> BCDs
processID total cur
    | isInvalid cur = addBCD total cur
    | otherwise = total

Internal Phase

To interpret the new PureSolver definition, an additional state variable is required to keep track of the machine’s phase.

data MachinePhase
    = -- Ready to accept new data
      WaitingInput
    | -- Computing the solution
      Working
    | -- This is the end
      Halted
    deriving (Eq, Show, Generic, NFDataX)

… which can be used to create a Solver from a PureSolver by carefully setting the busy output value when needed:

data MachineState s = MkMachine
    { state :: s
    , phase :: MachinePhase
    }
    deriving (Eq, Show, Generic, NFDataX)

-- type Solver dom = Signal dom Byte -> (Signal dom Bool, Signal dom (Maybe Byte))
mkSolver :: forall s dom. (HiddenClockResetEnable dom, Show s, NFDataX s) => PureSolver s -> s -> Solver dom
mkSolver solver initialState = mealyB mstep (MkMachine initialState WaitingInput)
  where
    -- mstep updates the MachineState and return the busy bit along with an optional output
    mstep :: (MachineState s) -> Byte -> (MachineState s, (Bool, Maybe Byte))
    mstep machine input =
        let
            -- input is only provided when waiting for it
            value = case machine.phase of
                WaitingInput -> input
                _ -> 0

            -- run the pure solver transfer function
            (solverOutput, nextState) = runState (solver value) machine.state

            -- update the phase
            (nextPhase, outputByte) = case solverOutput of
                Busy -> (Working, Nothing)
                ReadInput -> (WaitingInput, Nothing)
                Output b -> (Working, Just b)
                Done -> (Halted, Just 3)
         in
            -- return the new state and the solver output for this cycle
            (MkMachine nextState nextPhase, (nextPhase == Working, outputByte))

Info

The mkSolver function wraps the PureSolver and manages the output signals based on the SolverOutput and its internal phase. This enables a separation of concern where the PureSolver does not handle the input and output directly.

Simulation

Simulating such a design is interesting because the input signal now depends on the output: when the solver is busy, the input must be delayed. Thanks to Haskell, the simulation’s input stream can be defined lazily, using a technique known as “tying the knot”, effectively pausing the stream when the output signals “busy”:

simulateSolver :: forall dom. (KnownDomain dom) => ((HiddenClockResetEnable dom) => Solver dom) -> (String -> String)
simulateSolver solver input = do
    let
        -- input is generated using the output
        inputSignal = genInput (fst <$> outputSignal) (encodeInput input)

        -- output is produced by sampling the Solver
        outputSignal :: [(Bool, Maybe Byte)]
        outputSignal = sample $ bundle $ board $ fromList $ 0 : inputSignal
     in
        convertOutput $ catMaybes $ snd <$> outputSignal
  where
    genInput :: [Bool] -> [Byte] -> [Byte]
    -- solver is busy, wait before sending the next byte
    genInput (True : os) is = 0 : genInput os is
    -- send the next byte
    genInput (_ : os) (i : is) = i : genInput os is

    -- setup the implicit clock
    board = withClockResetEnable clockGen resetGen enableGen solver

Note

The inputSignal is defined using the outputSignal, which is an interesting property of lazy languages like Haskell.

While this design works in theory, it is not very practical because the user must somehow delay the input while the machine is busy. In retrospect, this might have not been the best idea, but that’s how I did it at the time. You can check the full code to solve the second puzzle in the Simple02 module. I also solved the third puzzle with this design.

Summary

• Recursively defined functions cannot be synthesized into HDL. Arbitrarly long computation must be defined from the inside out.

• This section introduced a new design to perform long computation using a busy flag to delay the input:

type Solver dom =
    "INPUT" ::: Signal dom Byte ->
    ("BUSY" ::: Signal dom Bool, "OUT" ::: Signal dom (Maybe Byte))

• The Mealy machine can use an extra “phase” state to handle the lower level details for the pure solver:

data MachinePhase = WaitingInput | Working | Halted

This approach effectively turned an arbitrary-length computation into a state machine that hardware can synthesize.

---

RAM Machine

The fourth puzzle required yet another strategy because the state was too large to fit in the Mealy machine register. The input was a 2D grid of elements, and my first attempt tried to store the whole grid in the state with:

type Grid n = Vec n (Vec n Bit)

… which worked in simulation using a grid of 139x139 elements, but synthesizing this code resulted in a gigantic circuit that stalled during the “Start Timing Optimization” assembly step. The synthesizer likely attempted to implement each grid cell as individual register, consuming more logic resources than available on the chip.

In solving this challenge, I also realized that the earlier design had a fundamental issue: external input arriving when the solver was busy simply got lost. A better approach would buffer incoming data so nothing gets dropped. This led me back to my very first design, but replacing the direct byte stream with a Maybe Byte stream to explicitly handle the end of data state:

type SerialCircuit dom = Signal dom (Maybe Byte) -> Signal dom (Maybe Byte)

Note

Buffering incoming bytes would solve both the data loss issue and the size problem by keeping the grid outside of the solver state.

Introducing Block RAM

FPGAs chips provide a special element called Block RAM (BRAM), which is similar to regular RAM but directly accessible from inside the FPGA. The available amount of BRAM depends on the chip; for example the A7-50T can store up to 337KB of data. This happens automatically in the later stage of the assembly process and every vendor has it’s own implementation. Thankfully, Clash provides the following helper to create BRAM:

-- From Clash.Prelude.BlockRam:
blockRam1 :: (HiddenClockResetEnable dom, NFDataX a, Enum addr, NFDataX addr, 1 <= n)
  => ResetStrategy r
  -> SNat n
  -- ^ Number of elements in BRAM
  -> a
  -- ^ Initial content of the BRAM (replicated /n/ times)
  -> Signal dom addr
  -- ^ Read address
  -> Signal dom (Maybe (addr, a))
  -- ^ (write address, value to write)
  -> Signal dom a
  -- ^ Value of the BRAM at read address from the previous clock cycle

… which defines three signals to read from and write to the BRAM:

Note

Remember that signals are synchronous. In this case, that means the read value is always emitted based on what was last set on the address input.

For example, here is a circuit that simply write the input stream to BRAM with a tiny Mealy machine to keep track of the write address:

-- | 16-bit address bus
type Addr = Unsigned 16

-- | 8-bit data bus
type Byte = BitVector 8

-- | 64k ram size
ramSize :: SNat 65_536
ramSize = SNat

-- type SerialCircuit dom = Signal dom (Maybe Byte) -> Signal dom (Maybe Byte)

-- | Copy the input to bram
bufferCircuit :: forall dom. (HiddenClockResetEnable dom) => SerialCircuit dom
bufferCircuit input = pure Nothing
  where
    -- Setup the ram block
    ramValue :: Signal dom Byte
    ramValue = blockRam1 NoClearOnReset ramSize 0 ramAddr ramWrite

    -- Ram write signal is handled with the 'writeInput' Mealy step below
    ramWrite :: Signal dom (Maybe (Addr, Byte))
    ramWrite = mealy writeInput 0 input

    -- To be continued...
    ramAddr :: Signal dom Addr
    ramAddr = undefined

-- | Increment the bram addr and set the write signal on incoming bytes
writeInput :: Addr -> Maybe Byte -> (Addr, Maybe (Addr, Byte))
-- writeInput addr byte | trace ("writing: " <> show addr <> ": " <> show (charUnpack <$> byte)) False = undefined
writeInput addr Nothing = (addr, Nothing)
writeInput addr (Just v) = (addr + 1, Just (addr, v))

Info

The bufferCircuit shows how the input stream can be written to BRAM. It uses a a tiny Mealy machine to store the byte in the correct location.

Tip

The writeInput transfer function uses a lesser-known trick to inject trace points: adding a pattern guard like | trace ".." False causes a debug message to be printed each time the function is called. The guard is always False, thus the implementation can be undefined.

The next sections shows how to read from BRAM.

Solving Day 4

With the puzzle input being stored in memory, the transfer function can now simply set the addr value based on the grid position to read the grid location directly from BRAM.

Thus, the SolverOutput can be changed to replace the ReadInput case with ReadMem Addr to access the puzzle input from specific address in BRAM.

-- From AdventOfClash.Simple04:
data SolverOutput
    = -- Need more time
      Busy
    | -- Need arbitrary byte from bram
      ReadMem Addr
    | -- Send an output byte
      Output Byte
    | -- Is terminated
      Done
    deriving (Show)

And for reference, I used the following state to process the grid:

data St n = MkSt
    { status :: Status n
    , total :: Unsigned 25
    -- ^ The total number of removed roll
    }
    deriving (Eq, Show, Generic, NFDataX)

data Status n
    = -- | Figuring out if a roll can be removed
      Solving {adjacentCount :: Index 4, currentAdjacentPos :: Adjacent, rolPos :: Position n}
    | -- | Advancing to the next roll position
      NextPosition (Position n)
    | -- | Writing the solution
      WritingOutput (OutputWriter (BCDSize 25))
    | -- | This is the end
      Completed
    deriving (Eq, Show, Generic, NFDataX)

data Position n = MkPos {col :: Index n, row :: Index n}
    deriving (Eq, Show, Generic, NFDataX)

data Adjacent = UL | UP | UR | ML | MR | DL | DW | DR
    deriving (Eq, Show, Generic, NFDataX, Enum, Bounded)

initState :: (KnownNat n) => St n
initState = MkSt (NextPosition $ MkPos 0 0) 0

Info

The St data has a type parameter n to define the size of the grid statically. This allows using the same code for different grid size by using a data kind type application when creating the initial state that way: initState @139

And here is how the Mealy transfer function leverage the new ReadMem output:

step :: (KnownNat n) => PureSolver (St n)
step n = do
    st <- get
    case st.status of
        NextPosition pos -> case n of
            -- This position is a roll, need to solve it
            ByteChar '@' -> do
                let (adj, apos) = firstAdjacent pos
                modify $ \s -> s{status = Solving 0 adj pos}
                -- Request adjacent position value from memory
                pure $ ReadMem $ posAddr apos

            -- Otherwise advance in the grid
            _ -> advance pos 0

        -- other status are omitted

Note

This design is more powerful because a solver can now access any part of the puzzle as needed.

RAM Phase

To interpret the new PureSolver memory access, the following Solver design can be used:

-- From AdventOfClash.Simple04:
type Solver dom =
    "READ" ::: Signal dom Byte ->
    ( "ADDR" ::: Signal dom Addr
    , "OUTPUT" ::: Signal dom (Maybe Byte)
    )

… with the following machine phases which now include WaitingMem and Ready:

data MachinePhase
    = -- | Reading from BRAM takes one cycle
      WaitingMem
    | -- | Memory read is available
      Ready
    | -- | The solver is busy
      Working
    | -- | This is the end
      Halted
    deriving (Eq, Show, Generic, NFDataX)

data MachineState s = MkMachine
    { phase :: MachinePhase
    -- ^ The machine phase
    , addr :: Addr
    -- ^ The current read address
    , state :: s
    -- ^ The solver state
    }
    deriving (Eq, Show, Generic, NFDataX)

… along with this new helper to manage the transitions:

-- type Solver dom = Signal dom Byte -> (Signal dom Addr, Signal dom (Maybe Byte))
mkSolver :: forall s dom. (HiddenClockResetEnable dom, Show s, NFDataX s) => PureSolver s -> s -> Solver dom
mkSolver solver initialState = MealyB mstep (MkMachine WaitingMem 0 initialState)
  where
  where
    mstep :: (MachineState s) -> Byte -> (MachineState s, (Addr, Maybe Byte))
    -- 0 value is the uninitialized memory default value, data is still pending, we have to wait
    mstep m 0 = (m, (m.addr, Nothing))
    mstep machine ibyte = case machine.phase of
        -- Waiting for memory only takes a single cycle, switch to Ready right away:
        WaitingMem -> (machine{phase = Ready}, (machine.addr, Nothing))

        -- When memory is available, advance the solver
        Ready -> stepSolver ibyte

        -- When busy, advance the solver with zero input
        Working -> stepSolver 0

        -- When halted, don't change the phase:
        Halted -> (machine, (0, Nothing))

      where
        stepSolver input =
            let
                -- run the pure solver transfer function
                (stepOutput, nextState) = runState (solver input) machine.state

                -- prepare the mstep output
                next phase addr output = (MkMachine phase addr nextState, (addr, output))
             in
                case stepOutput of
                    -- Switch to Working phase
                    Busy -> next Working machine.addr Nothing

                    -- Update the addr and switch to WaitingMem phase
                    ReadMem addr -> next WaitingMem addr Nothing

                    -- Set the output byte
                    Output byte -> next Working machine.addr $ Just byte

                    -- Switch to Halted phase and send the 'end of text' byte
                    Done -> next Halted 0 $ Just 3

Note

The key purpose of this machine is to delay one cycle when reading from BRAM:

• Cycle N: the solver needs data and returns a ReadMem addr, the machine transitions to WaitingMem phase and sets the BRAM addr input.

• Cycle N+1: the BRAM read data is available, the machine transitions to Ready phase.

• Cycle N+2: the solver receives the data and can process it.

The PureSolver is responsible for the core computation, while the Solver manages the interaction with BRAM using MachinePhase.

Serial Circuit

Finally the BRAM can be connected to the solver using the following circuit:

-- type Solver dom = Signal dom Byte -> (Signal dom Addr, Signal dom (Maybe Byte))
mkSerialCircuit :: (HiddenClockResetEnable dom) => Solver dom -> SerialCircuit dom
mkSerialCircuit solver input = output
  where
    -- Ram write signal, as already explained above
    ramWrite = mealy writeInput 0 input

    -- Solve the puzzle (and skip the initial read value which is undefined)
    (ramAddr, output) = solver $ register 0 $ ramRead

    -- Setup the ram block
    ramRead = blockRam1 NoClearOnReset ramSize 0 ramAddr ramWrite

Note

This circuit writes the puzzle input to BRAM and enables random access for the solver. This solves both the data loss when the solver is busy, and the data size because the puzzle input is no longer stored in the mealy machine.

Simulation

This third design is easier to simulate as the input can be provided in bulk:

simulateCircuit :: (KnownDomain dom) => ((HiddenClockResetEnable dom) => SerialCircuit dom) -> (String -> String)
simulateCircuit circuit input = convertOutput $ catMaybes $ sample $ bundle $ board $ fromList $ handleInput input
  where
    board = withClockResetEnable clockGen resetGen enableGen circuit

And here is the simulation trace if you are interested in seeing how the phase and state change over time:

input: '\0'  phase: WaitingMem   addr: 0     state: NextPosition (MkPos 0 0)
writing: 0: '\NUL'
input: '\0'  phase: WaitingMem   addr: 0     state: NextPosition (MkPos 0 0)
writing: 0: '.'
input: '\0'  phase: WaitingMem   addr: 0     state: NextPosition (MkPos 0 0)
writing: 1: '.'
input: '.'   phase: WaitingMem   addr: 0     state: NextPosition (MkPos 0 0)
writing: 2: '@'
input: '.'   phase: Ready        addr: 0     state: NextPosition (MkPos 0 0)
writing: 3: '@'
input: '.'   phase: WaitingMem   addr: 1     state: NextPosition (MkPos 1 0)
writing: 4: '.'
input: '.'   phase: Ready        addr: 1     state: NextPosition (MkPos 1 0)
writing: 5: '@'
input: '.'   phase: WaitingMem   addr: 2     state: NextPosition (MkPos 2 0)
writing: 6: '@'
input: '@'   phase: Ready        addr: 2     state: NextPosition (MkPos 2 0)
writing: 7: '@'
input: '@'   phase: WaitingMem   addr: 1     state: Solving {adjacentCount = 0, adjacentPos = ML, rolPos = MkPos 2 0}
writing: 8: '@'
input: '.'   phase: Ready        addr: 1     state: Solving {adjacentCount = 0, adjacentPos = ML, rolPos = MkPos 2 0}
writing: 9: '.'
input: '.'   phase: WaitingMem   addr: 3     state: Solving {adjacentCount = 0, adjacentPos = MR, rolPos = MkPos 2 0}
writing: 10: '\n'
input: '@'   phase: Ready        addr: 3     state: Solving {adjacentCount = 0, adjacentPos = MR, rolPos = MkPos 2 0}
writing: 11: '@'
input: '@'   phase: WaitingMem   addr: 12    state: Solving {adjacentCount = 1, adjacentPos = DL, rolPos = MkPos 2 0}
writing: 12: '@'
input: '\0'  phase: Ready        addr: 12    state: Solving {adjacentCount = 1, adjacentPos = DL, rolPos = MkPos 2 0}
writing: 13: '@'
input: '@'   phase: Ready        addr: 12    state: Solving {adjacentCount = 1, adjacentPos = DL, rolPos = MkPos 2 0}
writing: 14: '.'
input: '@'   phase: WaitingMem   addr: 13    state: Solving {adjacentCount = 2, adjacentPos = DW, rolPos = MkPos 2 0}
writing: 15: '@'
input: '@'   phase: Ready        addr: 13    state: Solving {adjacentCount = 2, adjacentPos = DW, rolPos = MkPos 2 0}
writing: 16: '.'

Note

What’s really neat to see is that the solver is starting as soon as the first byte is written. This happens because every part of the circuit are operating in parallel at every clock cycle.

You can check the full code to solve the fourth puzzle in the Simple04 module.

Summary

• Block RAM can be created to store data that does not fit in registers.

• This section introduced a new design using random-access memory to read the puzzle:

type Solver dom =
    "READ" ::: Signal dom Byte ->
    ("ADDR" ::: Signal dom Addr, "OUTPUT" ::: Signal dom (Maybe Byte))

• The Mealy machine gained an extra phase state to handle the memory read delay:

data MachinePhase = WaitingMem | Ready | Working | Halted

---

The next section shows how to move from an ideal simulation to a physical chip.

Running on FPGA

This section shows the last remaining steps to run the puzzle solver on a real piece of hardware:

Final design

The previous designs omitted a few key capabilities to be usable in practice. Specifically, I needed to wait between successive outputs to ensure the device isn’t sending the result too fast. Here is the full design I ended up creating for this project:

type Solver dom =
    "ACK" ::: Signal dom Bool ->
    "READ" ::: Signal dom Byte ->
    ( "ADDR" ::: Signal dom Addr
    , "WRITE" ::: Signal dom (Maybe (Addr, Byte))
    , "OUTPUT" ::: Signal dom (Maybe Byte)
    )

• The ACK input is necessary to wait for the output transmission to be completed. This is mandatory for flow control to ensure the device isn’t sending the data too fast.

• The WRITE output enables writing to arbitrary locations in the BRAM, which was needed to solve the second part of day 4.

I also updated the machine phase to include a welcome message, as well as a mechanism to clear the memory after a solver is halted so that the system can be re-used without having to reset the device:

welcomeMessage :: Vec 10 Byte
welcomeMessage = charPack <$> '\n' :> 'A' :> 'o' :> 'C' :> ' ' :> 'F' :> 'P' :> 'G' :> 'A' :> '\n' :> Nil
  -- Message value can also be generated with TemplateHaskell: $(listToVecTH $ charPack <$> "\nAoC FPGA\n")

data MachinePhase
    = Welcoming (Index 10)
    | WaitingRam
    | WaitingOutput Byte
    | WaitingWrite (Addr, Byte)
    | Working
    | Ready
    | Halted Addr
    deriving (Eq, Show, Generic, NFDataX)

UART Device

The circuit still needed to implement a Universal Asynchronous Receiver-Transmitter (UART) device to be usable outside of simulation. The final design actually looked like this:

type UARTCircuit dom = Signal dom Bit -> Signal dom Bit

The retroclash-lib provides, among other things, useful modules to implement serial communication:

-- From RetroClash.SerialRx:
serialRx :: (KnownNat n, KnownNat (ClockDivider dom (HzToPeriod rate)), HiddenClockResetEnable dom) =>
    SNat rate -> Signal dom Bit -> Signal dom (Maybe (BitVector n))

-- From RetroClash.SerialTx:
serialTx :: (KnownNat n, KnownNat (ClockDivider dom (HzToPeriod rate)), HiddenClockResetEnable dom) =>
    SNat rate -> Signal dom (Maybe (BitVector n)) -> (Signal dom Bit, Signal dom Bool)

… which can be used as follows:

-- | uart speed in baud
speed :: SNat 57600
speed = SNat

-- | Create the final board with serial i/o
mkUARTCircuit :: (HiddenClockResetEnable dom, _) => SerialCircuit dom -> UARTCircuit dom
mkUARTCircuit serialCircuit rx = tx
  where
    (tx, ack) = serialTx speed $ serialCircuit ack ibyte
    ibyte = serialRx speed rx

Tip

As often with Haskell code, the actual term is a small fraction of all the imports and type signatures. This is in fact desirable as the term is the part that requires the most work to read and review.

Note that in the above type, the serial modules impose a clock domain constraint to make sure the frequency is fast enough for the desired transmission speed. Thankfully, the constraint can be omitted as it can be solved automatically by using a type hole _ instead. This is a convenient GHC feature that can be used to skip parts of a type declaration, it requires the following options: -XPartialTypeSignatures and -Wno-partial-type-signatures.

Top Module

The last remaining step with Clash is to create the topEntity module and instantiate the clock domain for the target board. I implemented the puzzle solution as Mealy transfer function and I wrote a mkBoard helper to create the circuit in a general purpose module named AdventOfClash.Circuit. That way, the final topEntity for a given puzzle can be created like this:

module Day04Board where

import Clash.Annotations.TH
import Clash.Prelude

import AdventOfClash.Day04 (solution)
import AdventOfClash.Circuit (mkBoard)

topEntity :: "CLK" ::: Clock System -> "RX" ::: Signal System Bit -> "TX" ::: Signal System Bit
topEntity clk = withClockResetEnable clk resetGen enableGen (mkBoard solution)

makeTopEntity 'topEntity

Note

The last line is a TemplateHaskell expression to generate some boilerplate.

The final verilog code can then be generated using the following command:

$ echo ":verilog" | clashi Day04Board
Clashi, version 1.8.4 (using clash-lib, version 1.8.4):
https://clash-lang.org/  :? for help
[1 of 4] Compiling AdventOfClash.Utils ( AdventOfClash/Utils.hs, interpreted )
[2 of 4] Compiling AdventOfClash.Circuit ( AdventOfClash/Circuit.hs, interpreted )
[3 of 4] Compiling AdventOfClash.Day04 ( AdventOfClash/Day04.hs, interpreted )
[4 of 4] Compiling Day04Board       ( Day04Board.hs, interpreted )
Ok, four modules loaded.
GHC: Setting up GHC took: 0.073s
GHC: Compiling and loading modules took: 5.424s
Clash: Parsing and compiling primitives took 0.352s
GHC+Clash: Loading modules cumulatively took 8.950s
Clash: Compiling Day04Board.topEntity
Clash: Normalization took 2.112s
[WARNING] Dubious primitive instantiation for GHC.Num.Integer.integerToInt#: GHC.Num.Integer.integerToInt#: Integers are dynamically sized in simulation, but fixed-length after synthesis. Use carefully. (disable with -fclash-no-prim-warn)
Clash: Netlist generation took 0.067s
Clash: Compiling Day04Board.topEntity took 2.234s
Clash: Total compilation took 11.186s

… which produces a verilog source file that looks like this: topEntity.v.

Next, the physical board pin mapping needs to be defined using a vendor defined “constraint file”:

## Clock signal
set_property -dict { PACKAGE_PIN E3    IOSTANDARD LVCMOS33 } [get_ports { CLK100MHZ }]; #IO_L12P_T1_MRCC_35 Sch=clk100mhz
create_clock -add -name sys_clk_pin -period 10.00 -waveform {0 5} [get_ports {CLK100MHZ}];

## USB-RS232 Interface
set_property -dict { PACKAGE_PIN C4    IOSTANDARD LVCMOS33 } [get_ports { UART_TXD_IN }]; #IO_L7P_T1_AD6P_35 Sch=uart_txd_in
set_property -dict { PACKAGE_PIN D4    IOSTANDARD LVCMOS33 } [get_ports { UART_RXD_OUT }]; #IO_L11N_T1_SRCC_35 Sch=uart_rxd_out

… which is used to create the final Top entity wires:

// target/nexys-a7-50t/src-hdl/Top.v
module Top(
           input wire  CLK100MHZ,
           input wire  UART_TXD_IN,
           output wire UART_RXD_OUT
           );

   // instantiate the Haskell code.
   topEntity u_topEntity
     (.CLK(CLK100MHZ),
      .RX(UART_TXD_IN),
      .TX(UART_RXD_OUT)
      );

endmodule

Info

The Top wire names come from the constraint file and the topEntity ones come from the ::: anotations.

The Top module can be used to instantiate foreign code, for example to setup a PLL for adjusting the clock. This is where the Haskell topEntity code is connected to the real world.

Clash Shake

Once the verilog Top module is ready, it still needs to be converted into a binary format, called bitstream, that can be uploaded to the FPGA chip. Unfortunately, there is no real standard, and each vendor has its own toolchain. Thankfully, the clash-shake library provides build rules that can be used to deal with the vendor toolchains idiosyncrasies using a Shakefile that looks like this:

import Clash.Shake
import Development.Shake

outDir :: FilePath
outDir = "_build"

main :: IO ()
main = shakeArgs shakeOptions{shakeFiles = outDir} do
    let boards =
            [ ("nexys-a7-50t", Xilinx.vivado Xilinx.nexysA750T)
            , ("de0-nano", Intel.quartus de0Nano)
            ]
    for_ boards \(name, synth) -> do
        let files = staticFiles ("target" </> name </> "src-hdl")
        bitfile <- synth files
        mapM_ (uncurry $ nestedPhony name) $
            ("bitfile", need [bitfile]) : phonies

This build system then provides the following convenient commands to pilot the toolchains:

  - nexys-a7-50t:bitfile
  - nexys-a7-50t:upload
  - de0-nano:bitfile
  - de0-nano:upload

… which looks like this when building the final bitstream file:

$ shake nexys-a7-50t:bitfile
Running vivado (for _build/nexys-a7-50t/synth/Top/Top.xpr)
...
Report Cell Usage:
+------+-----------+------+
|      |Cell       |Count |
+------+-----------+------+
|1     |BUFG       |     1|
|2     |CARRY4     |    47|
|3     |LUT1       |    79|
|4     |LUT2       |    97|
|5     |LUT3       |    65|
|6     |LUT4       |   120|
|7     |LUT5       |   186|
|8     |LUT6       |   500|
|9     |RAMB36E1   |     1|
|10    |RAMB36E1_2 |     7|
|11    |RAMB36E1_4 |     1|
|12    |RAMB36E1_5 |     7|
|13    |FDRE       |   244|
|14    |FDSE       |     9|
|15    |IBUF       |     2|
|16    |OBUF       |     1|
+------+-----------+------+

Report Instance Areas:
+------+--------------+----------+------+
|      |Instance      |Module    |Cells |
+------+--------------+----------+------+
|1     |top           |          |  1367|
|2     |  u_topEntity |topEntity |  1363|
+------+--------------+----------+------+
...
Phase 7 Route finalize

Router Utilization Summary
  Global Vertical Routing Utilization    = 0.961014 %
  Global Horizontal Routing Utilization  = 0.706012 %
  Routable Net Status*
  *Does not include unroutable nets such as driverless and loadless.
  Run report_route_status for detailed report.
  Number of Failed Nets               = 0
  Number of Unrouted Nets             = 0
  Number of Partially Routed Nets     = 0
  Number of Node Overlaps             = 0

Congestion Report
North Dir 1x1 Area, Max Cong = 78.3784%, No Congested Regions.
South Dir 1x1 Area, Max Cong = 80.1802%, No Congested Regions.
East Dir 1x1 Area, Max Cong = 66.1765%, No Congested Regions.
West Dir 1x1 Area, Max Cong = 58.8235%, No Congested Regions.
...
Build completed in 8m52s

$ du --si _build/nexys-a7-50t/synth/Top/Top.runs/impl_1/Top.bit
2.2M

Note

The number of “Cells” seems to depend on the complexicity of the design, but I’m not sure how this relate to the chip capacity. For example the A7-50T chip has 8150 Logic Slices.

Finally, the chip can be programmed with the final bitstream file using a tool like openFPGAloader.

Serial Port

Once the FPGA is running, I wrote a serial client to send the puzzle input:

module Client where

import Data.ByteString qualified as BS
import System.Hardware.Serialport qualified as S
import Clash.Promoted.Nat (snatToNatural)
import AdventOfClash.Circuit as Circuit (speed)

-- | Set the speed based on the circuit implementation
commSpeed = case snatToNatural Circuit.speed of
    57600 -> S.CS57600
    9600 -> S.CS9600
    n -> error $ "unknown baud: " <> show n

main :: IO ()
main = do
    input <- BS.getContents
    let settings = S.defaultSerialSettings{S.commSpeed = commSpeed}
    S.withSerial dev settings $ \port -> do
        -- Start transmission
        S.send port "\x02"
        -- Send puzzle input
        sendAll port (BS.length input) input
        -- End transmission
        S.send port "\x03"
        putStrLn $ dev <> "> waiting..."
        recvAll port
    putStrLn "\ndone!"

… which looked like this when solving a puzzle:

$ cat d4.txt | cabal run -O0 exe:client
/dev/ttyUSB1> sending: 19460
/dev/ttyUSB1> waiting...
AoC FPGA
8537

It was at that moment that I decided to write this blog post:)

Summary

To summarize, this post introduced a tower of abstraction to solve the advent of code on a FPGA:

• The puzzle solutions were implemented using combinational logic as a Mealy machine transfer function:

type PureSolver s = Byte -> State s SolverOutput

• The solver circuit was implemented using a phase system:

type Solver dom =
    "ACK" ::: Signal dom Bool ->
    "READ" ::: Signal dom Byte ->
    ("ADDR" ::: Signal dom Addr, "WRITE" ::: Signal dom (Maybe (Addr, Byte)), "OUTPUT" ::: Signal dom (Maybe Byte))

• The solver was hosted in a serial logic circuit using Block RAM:

type SerialCircuit dom =
    "ACK" ::: Signal dom Bool ->
    "RX" ::: Signal dom (Maybe Byte) ->
    "TX" ::: Signal dom (Maybe Byte)

• Which was converted into an UART device:

type UARTCircuit dom =
    "RX" ::: Signal dom Bit ->
    "TX" ::: Signal dom Bit

• The following helpers converts the puzzle solution into a digital circuit:

mkSolver        :: PureSolver s -> s -> Solver dom
mkSerialCircuit :: Solver dom        -> SerialCircuit dom
mkUARTCircuit   :: SerialCircuit dom -> UARTCircuit dom

• I showed three levels of simulation for the individual layers:

simulatePure    :: PureSolver s -> s -> String -> String
simulateSolver  :: ((HiddenClockResetEnable dom) => Solver dom) -> String -> String
simulateCircuit :: ((HiddenClockResetEnable dom) => SerialCircuit dom) -> String -> String

---

You can find the full circuit design and my puzzle solutions in the advent-of-clash repository:

• Sequential logic: Circuit.

• Combinational logic: Day01, Day02, Day03, Day04, Day05.

• Standalone examples for this post: Simple01, Simple02 and Simple04.

• Test suites to validate the simulation: Spec and the serialport client: Client.

Conclusion

This post demonstrated how I solved the first few Advent Of Code 2025 puzzles by designing custom-made circuits on an FPGA. While my implementation has room for improvements, it lays the groundwork for implementing serial text processing devices.

It’s mind-boggling that Haskell, such a high-level and general purpose language, can be used to design digital circuits that run directly on silicon. The Clash compiler translates abstract concepts like monadic state into physical flip-flops and logic gates, making hardware design accessible to functional programmers.

FPGAs themselves are fascinating because they operate in a fundamentally different way than traditional CPUs: the entire circuit updates simultaneously at every clock cycle. For example, to blink a LED, a register can measures time by counting these cycles, incrementing hundreds of millions of times per second, just to know when to turn the light on or off.

However, moving from simulation to real hardware requires dealing with annoying vendor-specific toolchains that are opaque and difficult to work with. While Yosys looks like a promising open-source alternative, I wish there were more accessible platforms to experiment with this technology.

This project wouldn’t have been possible without the Retrocomputing with Clash book, which led me to discover this fascinating intersection of hardware and software.

Finally, I would like to thank Solal and Gergő for their early feedback and corrections.