package hardcaml_circuits

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

Index vector circuit with tracks indexes.

Parameters

module X : sig ... end

Signature

include S with type tag := Hardcaml.Signal.t Hardcaml.Interface.Empty.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)

    *)
}

Operation performed on the vec circuit.

val create : Hardcaml.Reg_spec.t -> op -> t

Create the vec with the given size.

OCaml

Innovation. Community. Security.

GitHub Discord Twitter Peertube RSS
About
Changelog Releases Industrial Users Academic Users Why OCaml
Ecosystem
Packages Community Events OCaml Planet Jobs
Resources
Install OCaml Get Started Platform Tools Language Manual Standard Library API Books Exercises Papers OCaml Playground Logo
Policies
Carbon Footprint Governance Privacy Code of Conduct