REBOL 3.0

Minor Bitsets

Carl Sassenrath, CTO
REBOL Technologies
3-Apr-2007 18:23 GMT

Article #0077
Main page || Index || Prior Article [0076] || Next Article [0078] || 15 Comments || Send feedback

UPDATE

This feature was implemented in several alpha releases in the logic! datatype then removed. It didn't prove useful or efficient. Although it did allow named bits within a logic value, a map of those names (as a block) had to be attached to the datatype (internally). So, it's more useful simply to use that block directly. An example, is system/options/flags, the boot flags of R3.

That said, it is possible to create various mapping functions that could set bits based upon specific word positions or set words based on specific bits, or even a test function that maps words-to-bits. But, so far, we've seen little or no interest from developers.

As you know, the bitset! datatype performs simple bit mapping logic functions. They allow an efficient mapping between simple scalar values (e.g. chars) and a logic true/false value.

Currently, bitsets are implemented as unbounded arrays of bytes... in fact as a binary! series type. This means that bitset values are references to a series (they are indirect values).

This is fine for larger bitsets, such as character maps, but there are often times when I need "minor" bitsets. For example, some of the fields in R2 system/options and also port states are implemented as integers with specific bit values.

The problem with that integer approach is that the abstraction of the bit flags is informal. You define various integer values and use operators as bitwise and and or logic functions.

opened: 4096
if port/state/flags and opened [...]

This is a standard practice with lower-level languages, but not very REBOL-like. Those of you who have attempted to interpret the internal states of network ports know what I'm talking about.

A solution is to allow minor bitsets. A minor bitset is one requiring 64 bits or less. Such bitsets would be implemented as direct values, not requiring the series and its associated overhead.

Such a bitset could be created with a line such as:

flags: make bitset! 64 ; or less

The result remains a bitset! datatype:

>> type? flags
== bitset!

but, its internal implementation would be directly mapped to the value (hence, more efficient).

Access to the bit could be done with the normal variety of methods, including:

if flags/6 [...]
flags/4: true
if pick flags 4 [...]

In addition, it would be useful to allow a direct association between words and bit flags. For example:

flags: make bitset! [opened closed connecting exited async]

The words in the block would be associated with the bits in the set. Now I can write:

if not flags/opened [
    flags/closed: true
]

and also:

if find flags 'opened [...]

or:

if find flags [opened connecting async] [...]

The feature is also nicely reflective, because I can request:

>> words-of flags  ; (sane replacement for SECOND of)
== [opened closed connecting exited async]

so the bit definitions travel with the value itself.

It may also be possible to allow an import/export method to allow a minor bitset to be applied to arbitrary integers. Certainly we would allow:

iflags: to-integer flags

to convert the flags to an integer value, and there would likely be an inverse to that.

We can get into more detail later. I just wanted to open the discussion, and I prefer to limit the length of my postings to keep them focused.

15 Comments

REBOL 3.0
Updated 23-Nov-2017 - Edit - Copyright REBOL Technologies - REBOL.net