The Cairo bitwise integer library (cairo-bitwise-int v0.1.1)
The Cairo smart test library (cairo-smart-test v0.1.1)
Author: Jamie Gabbay
What is this?
The Cairo Abstract Machine’s primitive notion of counting is a finite field over a prime of size approximately 2^251. This differs significantly from that of a typical Intel or ARM chip, which is typically a 64-bit integer bitwise representation.
This directory contains:
cairo-bitwise-int: a collection of Cairo libraries to emulate signed and unsigned integer datatypes of various bit lengths (e.g. 8-bit unsigned integers, also known as ‘bytes’), and
cairo-smart-test: an automated unit- and property-based test suite.
I am pleased to share this with the Cairo community, and feedback and suggestions are welcome.
How to use the Cairo bitwise library off-the-shelf
code directory contains prepared source files. For example:
uint8.cairois a library for unsigned 8-bit integers (i.e. “bytes”).
uint32.cairois a library for unsigned 32-bit integers (i.e. “words”).
int32.cairois a library for signed 32-bit integers (i.e. “signed words”).
Assuming you are writing Cairo code, You can import these libraries using the usual Cairo library import mechanism.
How to customise the library
The code is templated over a
BIT_LENGTH parameter which may vary between 4 and 125.
- The templates are in the
- Generation of code from templates is controlled by the file
run-this-file-to-build-code-directory-from-template-directory.py, which also contains a list of bit lengths to use.
This means that if you want an
int93.cairo library, you can have one, by following the instructions below.
You’ll need a working Cairo installation. Cairo install instructions are here — so do that first! The rest of these instructions assume you’re in a Cairo virtual environment.
We’ll also assume you’re using a Linux system; YMMV on other systems but the overall idea should be the same.
To set up:
- Make sure you have
jinja2and (optionally for testing)
hypothesisinstalled in your Cairo virtual environment, e.g. by typing
pip3 install jinja2 hypothesis.
- Execute the python3 file
run-this-file-to-build-code-directory-from-template-directory.pyto build the
codedirectory using the templates in the
- (Optionally) Execute the bash file
run_all_tests.shfrom inside the
Let’s say that again in code:
source ./enter-enviroment.sh pip3 install jinja2 hypothesis python3 run-this-file-to-build-code-directory-from-template-directory.py cd code bash run_all_tests.sh
For custom bit lengths, just edit the list of
run-this-file-to-build-code-directory-from-template-directory.py (direct link to line, correct at time of writing).
That’s it! The bitwise integer library files should now be in your
code directory and (optionally) fully tested.
The Cairo smart test suite
The unit- and property-based test suite is in the file
templates/cairo_smart_test_framework.py. The smart test suite is applied here to the bitwise library, but it exists independently and provides a comprehensive test framework for Cairo code.
You can use the smart test suite in your own Cairo development just by copying the
templates/cairo_smart_test_framework.py file into your development and using it, following
- the documentation in that file, and
- the example usages in
- a systematic demonstration of the test suite on a (deliberately buggy!) Cairo code file in the directory
Usage is designed to be straightforward but I’m happy to answer questions and act on feedback.
Why do we need a Cairo bitwise integer library?
As you may know, Cairo’s primitive numerical datatype is a felt (field element) which is a number between 0 and a constant DEFAULT_PRIME, currently set to just over 2^251.
However, the difference between the number model of Cairo and that of a typical computer chip goes deeper than the difference between 2^64 and 2^251. For instance:
- In Cairo, every number element has a multiplicative inverse, since we are in a finite field. So for example “divide by two” is well-defined and is a bijection on the number space. This is not the case for a typical bitwise representation!
- Conversely, Cairo has no native notions of “shift left one bit” or “shift right one bit” (multiplying or dividing by two is not the same thing, in a finite field) — nor of “add with overflow” (there is no native notion of overflow, again because we are in a finite field), and so forth.
This sets up a representational mismatch between Cairo and bitwise-based models of computing on numbers.
The Cairo bitwise integer library helps to bridge this gap with suitable library emulations of “bitwise-flavoured” datatypes for numerical computations — the ones you’re probably used to, such as “64-bit unsigned integers” (see
Why do we need a Cairo test framework?
Seriously? You do! The code in this repo has been tested using a unit- and property-based test suite specifically designed to work well with Cairo.
Feedback and comments …
… are very welcome. Thanks in advance.