Source file `index_vec.ml`

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
open Base
open Hardcaml
open Signal

module type Arg = Index_vec_intf.Arg
module type S = Index_vec_intf.S

module Make_tagged (Arg : Arg) = struct
  open Arg

  let log_vec_size = Int.ceil_log2 vec_size
  let insert = Vec.insert
  let remove = Vec.remove

  (* The data tracked in the vec. The index is the place in the external ram the bulk of
     data is supposed to be kept. The tag is an optional value which shifts along with the
     indexes - it is for special use cases such as an associated valid bit with an index.
  *)
  module Interface = struct
    type 'a t =
      { index : 'a [@bits log_vec_size]
      ; tag : 'a Arg.Tag.t
      }
    [@@deriving hardcaml]
  end

  (* Construct the vec. The indexes need special values written when the table is reset.
     The tag reset value is up to the user. *)
  module Vec = Vec.Make (struct
    module Interface = Interface

    (* Initialize the indexes with [0,1,2,3,4, ...].  Tags are up to the user. *)
    let spec ~index spec =
      { Interface.index =
          Reg_spec.override spec ~clear_to:(of_int ~width:log_vec_size index)
      ; tag = Arg.spec ~index spec
      }
    ;;
  end)

  type t =
    { vec : Vec.t
    ; length : Signal.t
    ; full : Signal.t
    ; empty : Signal.t
    ; insertion_index : Signal.t
    ; deletion_index : Signal.t
    }
  [@@deriving fields ~getters]

  type op =
    { slot : Signal.t
    ; op : Signal.t
    ; insertion_tag : Signal.t Arg.Tag.t option
    ; deletion_tag : Signal.t Arg.Tag.t option
    }

  let create ?index_next ~tag_next spec op =
    let insertion_index = Interface.Of_signal.wires () in
    let deletion_index = Interface.Of_signal.wires () in
    let vec =
      Vec.create
        spec
        ~vec_size
        ~next:(fun ~index d ->
          { index =
              Option.value_map index_next ~default:d.index ~f:(fun f -> f ~index d.index)
          ; tag = tag_next ~index d.tag
          })
        { slot = op.slot
        ; op = op.op
        ; insert_data = insertion_index
        ; delete_data = deletion_index
        }
    in
    (* The last element will be used for inserting into the vec. The currently addressed
       element will be popped from the vec and placed at the end. *)
    Interface.iter2
      insertion_index
      (let d = Vec.get vec ~index:(vec_size - 1) in
       { d with tag = Option.value ~default:d.tag op.insertion_tag })
      ~f:( <== );
    Interface.iter2
      deletion_index
      (let d = Vec.read_mux ~index:op.slot vec in
       { d with tag = Option.value ~default:d.tag op.deletion_tag })
      ~f:( <== );
    (* the following is entirely optional, but useful for debugging. Track the highest
       index inserted, and the size of the vec as items are deleted. It means somewhat
       less if the user arbitrarily writes to slots (which is fine, but those indexes are
       not tracked by this module). *)
    let length = wire (Int.ceil_log2 (vec_size + 1)) in
    let do_insert = op.op ==: insert (module Signal) in
    let do_remove = op.op ==: remove (module Signal) in
    length
    <== reg_fb
          spec
          ~enable:(do_insert |: do_remove)
          ~width:(Int.ceil_log2 (vec_size + 1))
          ~f:(fun length ->
            let slot = uresize op.slot (width length) in
            let next = length +:. 1 in
            let prev = length -:. 1 in
            let max = of_int ~width:(width length) vec_size in
            let min = of_int ~width:(width length) 0 in
            let slot_is_empty = slot >=: length in
            let on_insert =
              mux2 (length ==: max) max @@ mux2 slot_is_empty (slot +:. 1) next
            in
            let on_delete = mux2 (length ==:. 0) min @@ mux2 slot_is_empty length prev in
            mux2 do_insert on_insert on_delete);
    let full = length ==:. vec_size in
    let empty = length ==:. 0 in
    { vec
    ; length
    ; full
    ; empty
    ; insertion_index = insertion_index.index
    ; deletion_index = deletion_index.index
    }
  ;;

  let indexes t =
    Array.init (Vec.vec_size t.vec) ~f:(fun index -> (Vec.get t.vec ~index).index)
  ;;

  let index ~at t = (Vec.read_mux ~index:at t.vec).index

  let tags t =
    Array.init (Vec.vec_size t.vec) ~f:(fun index -> (Vec.get t.vec ~index).tag)
  ;;

  let tag ~at t = (Vec.read_mux ~index:at t.vec).tag

  (* binding just for documentation purposes. *)
  let access_index = deletion_index
end

module Make (Arg : sig
  val vec_size : int
end) =
struct
  module Tagged = Make_tagged (struct
    let vec_size = Arg.vec_size

    module Tag = Interface.Empty

    let spec ~index:_ _spec = Interface.Empty.None
  end)

  include Tagged

  type op =
    { slot : Signal.t
    ; op : Signal.t
    }

  let create ?index_next spec op =
    Tagged.create
      ~tag_next:(fun ~index:_ -> Fn.id)
      ?index_next
      spec
      { Tagged.slot = op.slot; op = op.op; insertion_tag = None; deletion_tag = None }
  ;;
end