Efficient 8-bits and 16-bits computations in OCaml

user_11825819 0
Viewed 202

I am currently working on a project in OCaml where I have to manipulate unsigned integers on 8 bits and on 16 bits. In my context, things can get a little messy, I sometimes want to convert an 8 bit integer into a 16 bits one, or split a 16 bits integer into two 8 bits one. I also want to use all the operations like addition, or the bitwise operations on those. Since there are all these interaction between 8 and 16 bits, I really like the comfort of having separate types for those. However, I still want my program to compute reasonnably efficiently, and I don't want to actually lose too much time casting an integer of a given size into another size. So my question is essentially how should I go about this? I have two main options but I don't know enough about the low-level interpretation of OCaml to comfortably chose:

Option 1 : Use dedicated types

I figured that I can use the Stdint library that is available through opam and has an implementation of the types uint8 and uint16 which are exactly what I am looking for.

Pros

I get very good mileage from the typing and will definitely avoid silly bugs from this

Cons

I have to constantly use the functions Uint8.to_uint16 and Uint16.to_uint8, which might eventually add up to heavy memory usage and poor efficiency of the compiled program, depending on how the precise representation is stored in machine

Option 2 : Encode everything within the type int

This means that all my integers will simply be of type int and I will have to program the addition of two 8-bits integers and of two 16-bits integers in this type, for instance.

Pros:

I think these operations can be programmed in a very efficient way using usual operations and the bitwise operations on the type int.

Cons:

I get essentially nothing from the typing and I have to trust myself to chose the right function at the right time.

Possible workaround

I could use two modules for defining 8-bits and 16-bits integers encoded in an int declared as private. I think that would essentially work like I presented with Option 2. The fact that I chose the type to be private would however mean that I cannot switch from one to the other without running into a typing mistake, thus forcing explicit casts and getting leverage from the type system. Still I expect the casts to be very efficient, since the memory representation of the object won't change.

So I would like to know how you would go about that? Is it worth going through all the trouble, do you think a solution is clearly better, or are they reasonably equivalent?

Bonus

Everytime I want to print (in hexadecimal) the value of a variable a of type uint8, I am writing

Printf.ksprintf "a = %02x" (Uint8.to_int a)

There is again a cast that seems to me a bit silly, I could also use direclty the Uint8.to_string_hex function, but it writes explicitly the 0x in front of the number, which I don't want. Ideally I would like to just write

Printf.ksprintf "a = %02x" (Uint8.to_int a)

Is there a way to change the scopes and do some magic with the Printf to make it happen?

bit-manipulation ocaml
1 Answers

In the stdint library both int8 and int16 are represented as int so there is no real tradeoff between option 1 and option 2,

type int8 = private int
(** Signed 8-bit integer *)

type int16 = private int
(** Signed 16-bit integer *)

The stdint library already provides you the best of two worlds, you have an efficient implementation and type safety. Yes, you need to do these translations but they no-ops and there only for the typechecker.

Also, if you're looking for modular arithmetic (and, in general, modeling machine words and bitvectors) then you can look at our Bitvec library, which we developed as part of the Binary Analysis Platform. It is focused on performance while still providing type safety and a lot of operations. We modeled it based on the latest SMT-LIB specification to give clear semantics to all operations. It uses the excellent Zarith library underneath the hood that enables efficient representation for small and arbitrary-length integers.

Since the modularity is not a property of a bitvector itself, but a property of an operation we do not encode the number of bits in the type and use the same type (and representation) for all bitvectors from 1-bits to thousands-of-bits. However, it is impossible to use mix-match the types incorrectly. E.g., you can use generic functions,

(x + y) mod m8

Or predefined modules for the specified modulus, e.g.,

M8.(x + y)

The library has a minimal number of dependencies, so try it by installing

opam install bitvec

There are also additional libraries like bitvec-order, bitvec-sexp, and bitvec-order that enable further integration with the Core suite of libraries, if you need them.

user_26254420
Related