RAM Arithmetic Plugin

The ram_arith_v0 and ram_arith_v1 plugin provides private indexed array access for arithmetic field types. These plugins are nearly identical, however the v0 API requires extra allocation hints in the plugin type declaration.

Types

The ram type is a plugin type for a privately indexable array. It uses the following plugin parameters.

  1. Plugin Name: ram_arith_v0 or ram_arith_v1

  2. Type name: ram

  3. Number: type index for the index and element type

  4. Number: number of allocations (v0 only)

  5. Number: total size of all allocations (v0 only)

  6. Number: maximum size concurrently allocated buffers (v0 only)

For example, if a program using the v0 plugin had two allocations, both with 64 elements but one is free’d before the other allocated, the type could be declared as such.

@type @plugin(ram_arith_v0, ram, 0, 2, 128, 64);

If, instead, both were allocated before one was free’d, the concurrent allocation size would be the same as the total.

@type @plugin(ram_arith_v0, ram, 0, 2, 128, 128);

When using the v1 plugin, regardless of the allocation pattern the following type could be used.

@type @plugin(ram_arith_v0, ram, 0);

Operations

The following operations are used with RAM.

init

Create a new RAM buffer with specified size.

read

Retrieve and return the element at a specified index.

write

overwrite the value at the specified index.

Here is an example declaration of each.

// index/element is type 0, buffer is type 1

// initialize a RAM buffer. Each element is given the input value as a start value.
// The size is a constant given in the plugin binding.
//                           buffer    fill
@function(ram_init_64, @out: 1:1, @in: 0:1)
//                            size
  @plugin(ram_arith_v1, init, 64);

// Read an element from the RAM buffer.
//                        out       buffer index
@function(ram_read, @out: 0:1, @in: 1:1,   0:1)
  @plugin(ram_arith_v1, read);

// Write an element into the RAM buffer.
//                        buffer index element
#function(ram_write, @in: 1:1,   0:1,  0:1)
  @plugin(ram_arith_v1, read);

init

Initialize a new RAM buffer. For a given buffer type b, index type i, and size s, the following parameters are used.

Function Signature

  • Output b:1: The newly created buffer

  • Input i:1: A value copied into each buffer element

Plugin Binding

  • Plugin Name: ram_arith_v0 or ram_arith_v1

  • Operation: init

  • Number: the size of the buffer.

read

Read a value from the buffer. For a given buffer type b, index type i, the following parameters are used. Although the read operation does not have a parameter for the size, if the index exceeds the size declared when the buffer was initialized, an @assert_zero failure occurs. If this failure occurs, the backend may assign to the output value an unspecified value.

Function Signature

  • Output i:1: output value

  • Input b:1: the buffer

  • Input i:1: the index

Plugin Binding

  • Plugin Name: ram_arith_v0 or ram_arith_v1

  • Operation: read

write

write a value into the buffer. For a given buffer type b, index type i, the following parameters are used. Although the write operation does not have a parameter for the size, if the index exceeds the size declared when the buffer was initialized, an @assert_zero failure occurs. If this failure occurs, the backend may assign an unspecified value to the indexed element.

Function Signature

  • Input b:1: the buffer

  • Input i:1: the index

  • Input i:1: the input value

Plugin Binding

  • Plugin Name: ram_arith_v0 or ram_arith_v1

  • Operation: write

Implementing the ram_arith_v0 or ram_arith_v1 Plugin

The RAM plugin is likely the trickiest plugin to implement, because it utilizes "IR Plugin Types". That means that an IR type will describe wires which aren’t arithmeic or boolean values. Instead, wires in the RAM buffer type carry RAM buffers.

This means that in addition to implementing operations for init, read, and write, you need a Buffer_T template to take the place of Wire_T, and you need a wtk::TypeBackend<Number, Buffer_T> to allow NAILS to interact with your Buffer_T. Fortunately, whether you choose to implement your own RAM, or use the fallback implementation, WizToolKit has you covered.

Both the arithmetic RAM interface and fallback implementation reside in the #include <wtk/plugins/ArithmeticRAM.h> header.

Implementing your own RAM Plugin

To implement your RAM plugin, you’ll need to start with your Buffer_T type. This type must follow the same rules as any other wire template used with NAILS: it must be default and move constructible. Of course, you will also need a Wire_T for the buffer’s private indices and elements.

Next you’ll need to implement a wtk::TypeBackend<Number_T, Buffer_T>. Ordinarily, this has callbacks for @add and @mul gates, however, such operations are nonsensical with RAM. Instead, subclass the wtk::plugins::RAMBackend<Number_T, Buffer_T, Wire_T>, which indicates to NAILS that such gates are unsupported (and implements no-ops in the unused callbacks). You must provide a constructor with the wire’s type and backend, and implement the check() method to indicate if proof errors occurred.

struct MyRAMBackend
  : public wtk::plugins::RAMBackend<Number, MyBuffer, MyWire>
{
  MyRAMBackend(wtk::type_idx type, wtk::TypeBackend<Number, MyWire>* backend)
    : wtk::plugins::RAMBackend<Number, MyBuffer, MyWire>(type, backend);

  bool failure = false;

  // Returns false if any errors are encountered, true otherwise
  bool check() override
  {
    return !this->failure;
    // alternatively, report failures through this->wireBackend->assertZero()
    // and always return true;
  }
};

You’ll need to implement the three RAM operations: init, read, and write. These have convenient superclasses which handle signature and argument checking and provide easy-to-implement callbacks.

struct MyRAMInit
  : public wtk::plugins::RAMInitOperation<Number, MyBuffer, MyWire>
{
  void init(wtk::wire_idx const size,
      MyBuffer* const buffer, MyWire const* const fill) override
  {
    /**
     * Instantiate the buffer with the stated size. Then assign each
     * element the fill value
     */
  }
};

struct MyRAMRead
  : public wtk::plugins::RAMReadOperation<Number, MyBuffer, MyWire>
{
  void read(MyWire* const out,
      MyBuffer* const buffer, MyWire const* const idx) override
  {
    /* implement: out = buffer[idx]; */
  }
};

struct MyRAMWrite
  : public wtk::plugins::RAMReadOperation<Number, MyBuffer, MyWire>
{
  void write(MyBuffer* const buffer,
      MyWire const* const idx, MyWire const* const in) override
  {
    /* implement: obuffer[idx] = in; */
  }
};

Lastly, you’ll want to implement the wtk::plugins::RAMPlugin<Number_T, Buffer_T, Wire_T> superclass, which is essentially a factory for your operations.

Fallback RAM Plugin

WizToolKit provides a buffer, wtk::plugins::FallbackRAMBuffer<Wire_T>, backend, wtk::plugins::FallbackRAMBackend<Number_T, Wire_T>, and plugin, wtk::plugins::FallbackRAMPlugin<Number_T, Wire_T>, the latter two using the afformentioned buffer to fill the middle Buffer_T template.

Instantiating the RAM Plugin

To instantiate an instance of the RAM plugin, allocate both a plugin object and a RAM backend object. Pass the plugin object to your plugins manager and the backend to both the plugins manager and NAILS interpreter.

To see the RAM plugin in action, check out our plugins sample backend.