package hardcaml_circuits

  1. Overview
  2. Docs
package hardcaml_circuits
Legend:
Library
Module
Module type
Parameter
Class
Class type

Index vector circuit which tracks indexes and arbitrary user tags

Parameters

module Arg : Arg

Signature

include S with type tag := Hardcaml.Signal.t Arg.Tag.t
type t

Hardware design and queries

The vec is a small, growable array of elements. Elements may be inserted and removed from any position. Note that insertion and deletion shuffle elements up/down.

Unlike a normal data structure, it isn't supposed to hold the actual data. Instead it holds the index at which the data should reside. It should be connected to an external ram with the address connected to:

  • insertion_index when inserting
  • deletion_index when deleting
  • access_index (with the address on op.slot and op.op=noop) when you want to access the data at a slot.

To insert an element, set op.op = insert and *during the same cycle* write the data to the (external) memory at insertion_index. Similarly to delete an element.

In some cases it is necessary to associate some extra bits that move with the indices - this can be done using tags. Tags may be changed (though the tag_next function) so long as the circuit is not currently inserting or deleting. To modify the tag value during insertion or deletion, see insertion_tag and deletion_tag in the type Make_tagged.op below.

val indexes : t -> Hardcaml.Signal.t Base.array

Return an array of current indexes

Get the index for the given position in the vec

Return an array of current tags

Get the tag for the given position in the vec

val insertion_index : t -> Hardcaml.Signal.t

Index at which insertion will take place. It is valid _while_ the insert op is performed.

val deletion_index : t -> Hardcaml.Signal.t

Index at which deletion will take place. It is valid _while_ the delete op is performed.

val access_index : t -> Hardcaml.Signal.t

Index corresponding to op.slot.

Length status

The length is tracked during inserts and removes. To compute the length it tracks the insertion/deletion slot. Removing from an 'empty' slot does not decrease the size.

Using length is optional and probably not required unless treating the vec as a queue or stack (which can also be implemented more efficiently with a fifo like structure).

full and empty are derived combinationally from length.

val length : t -> Hardcaml.Signal.t

Length of the vec

val full : t -> Hardcaml.Signal.t

Is the vec full?

val empty : t -> Hardcaml.Signal.t

Is the vec empty?

type op = {
  1. slot : Hardcaml.Signal.t;
    (*

    Slot to perform operation at

    *)
  2. op : Hardcaml.Signal.t;
    (*

    Operation type (insert, remove or nothing)

    *)
  3. insertion_tag : Hardcaml.Signal.t Arg.Tag.t Base.option;
    (*

    Value to set tag to on insertion. If None the value associated with the free slot moving in is kept

    *)
  4. deletion_tag : Hardcaml.Signal.t Arg.Tag.t Base.option;
    (*

    Value to set the tag to on deletion. If None the value associated with the slot being kicked out is kept

    *)
}

Operation performed on the vec circuit.

Create the vec with the given size.

The tag values may be arbitrarily updated with tag_next on cycles in which no insertion or deletion is taking place (tag_next is similar the the callback argument provided to reg_fb - it takes the current value and optionally modifies it to produce the next value).