Day 3: Digit Processing

Problem

For each line of digits:

1. Find x = maximum digit in positions 0 to n-2 (exclude last digit)
2. Find i = first position where digit equals x
3. Find y = maximum digit from position i+1 to n-1 (include last digit)
4. Add x * 10 + y to running total

Example

Line: 123456789

1. Find max in positions 0-7 (exclude last): max = 8 at position 7
2. First position where digit = 8: position 7
3. Find max from position 8 to 8 (just the last digit): max = 9
4. Result: 8 * 10 + 9 = 89

Circuit Interface

module I = struct
  type 'a t =
    { clock : 'a
    ; clear : 'a
    ; start : 'a                        (* Reset and start processing *)
    ; digit : 'a [@bits 4]             (* Current digit 0-9 *)
    ; digit_valid : 'a                  (* Pulse when digit is ready *)
    ; end_of_line : 'a                 (* Pulse at end of each line *)
    }
  [@@deriving hardcaml]
end

module O = struct
  type 'a t =
    { result : 'a [@bits 32]           (* Accumulated sum *)
    }
  [@@deriving hardcaml]
end

Key Implementation Details

State Tracking

The circuit needs to track multiple pieces of state:

(* Current line state *)
let%hw_var max_so_far = Variable.reg spec ~width:digit_bits in
let%hw_var max_pos = Variable.reg spec ~width:pos_bits in
let%hw_var max_after = Variable.reg spec ~width:digit_bits in
let%hw_var pos = Variable.reg spec ~width:pos_bits in

(* Previous state (for exclude-last-digit logic) *)
let%hw_var prev_max = Variable.reg spec ~width:digit_bits in
let%hw_var prev_max_pos = Variable.reg spec ~width:pos_bits in
let%hw_var prev_max_after = Variable.reg spec ~width:digit_bits in
let%hw_var prev_digit = Variable.reg spec ~width:digit_bits in

Finding Maximum

Track the maximum digit seen so far (excluding the last digit):

let is_new_max = digit >: max_so_far.value in

(* Update max if this digit is larger *)
if_ is_new_max
    [ max_so_far <-- digit
    ; max_pos <-- pos.value
    ; max_after <-- zero digit_bits  (* Reset - no digits after new max yet *)
    ]
    [ (* Not a new max - update max_after if we're past max_pos *)
      when_ (pos.value >: max_pos.value)
        [ max_after <-- new_max_after ]
    ]

Computing y Value

At the end of a line, compute y from the previous state:

(* y = max(prev_max_after, prev_digit) if prev_max_pos < pos-1, else prev_digit *)
let y_candidate = mux2 (prev_digit.value >: prev_max_after.value)
                       prev_digit.value
                       prev_max_after.value in

(* If prev_max_pos >= pos-1, then y = prev_digit *)
let pos_minus_one = pos.value -: one pos_bits in
let y_value = mux2 (prev_max_pos.value >=: pos_minus_one) prev_digit.value y_candidate in

Line Result Computation

Compute x * 10 + y:

let compute_width = 8 in
let x_small = uresize ~width:compute_width prev_max.value in
let y_small = uresize ~width:compute_width y_value in
let ten = of_int_trunc ~width:compute_width 10 in
let x_times_10 = sel_bottom ~width:compute_width (x_small *: ten) in
let line_result_small = x_times_10 +: y_small in
let line_result = uresize ~width:result_bits line_result_small in

State Machine

compile
  [ when_ start
      [ (* Reset all state *)
        max_so_far <-- zero digit_bits
      ; max_pos <-- zero pos_bits
      ; max_after <-- zero digit_bits
      ; pos <-- zero pos_bits
      ; prev_max <-- zero digit_bits
      ; prev_max_pos <-- zero pos_bits
      ; prev_max_after <-- zero digit_bits
      ; prev_digit <-- zero digit_bits
      ; result_acc <-- zero result_bits
      ]
  ; when_ digit_valid
      [ (* Save current state to prev_* before updating *)
        prev_max <-- max_so_far.value
      ; prev_max_pos <-- max_pos.value
      ; prev_max_after <-- max_after.value
      ; prev_digit <-- digit

      (* Update current state *)
      ; if_ is_new_max
          [ max_so_far <-- digit
          ; max_pos <-- pos.value
          ; max_after <-- zero digit_bits
          ]
          [ when_ (pos.value >: max_pos.value)
              [ max_after <-- new_max_after ]
          ]
      ; pos <-- pos.value +: one pos_bits
      ]
  ; when_ end_of_line
      [ (* Add line result to accumulator *)
        result_acc <-- result_acc.value +: line_result

      (* Reset line state for next line *)
      ; max_so_far <-- zero digit_bits
      ; max_pos <-- zero pos_bits
      ; max_after <-- zero digit_bits
      ; pos <-- zero pos_bits
      ]
  ];

Testing

The test harness feeds digits one at a time:

(* Start processing *)
inputs.start := Bits.vdd;
Cyclesim.cycle sim;

(* Process digits: 1, 2, 3, 4, 5, 6, 7, 8, 9 *)
for digit in [1; 2; 3; 4; 5; 6; 7; 8; 9] do
  inputs.digit := Bits.of_int ~width:4 digit;
  inputs.digit_valid := Bits.vdd;
  Cyclesim.cycle sim;
done;

(* End of line *)
inputs.end_of_line := Bits.vdd;
Cyclesim.cycle sim;
(* result = 89 *)

Try it in IDE →

Part 2

Part 2 extends the problem with different processing rules. The circuit structure is similar but uses different state tracking logic.

Try Part 2 →