Comments on: 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


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 [...]


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.



Brian Tiffin
3-Apr-2007 15:14:44
I like this.

Very reminiscent of emumerated data types in Pascal - but with the added bonus of 'knowing their own names'.

Thanks again.

3-Apr-2007 15:28:41
I've missed this a few times. Looks like a great way to abstract setting real bits and perhaps map this to bitsets created by other systems.

What if you want to set multiple flags at once, would that be possible? I would like to set certain presets or states up quickly.


set flags [a b c]
Carl Sassenrath
3-Apr-2007 16:09:44
Brian: yep, I was thinking of PASCAL too.

Henrik: yes, possible, and likely to be supported.

And, of course, someone will suggest bit fields too, eh? But, where do we stop?

Maxim Olivier-Adlhoch
3-Apr-2007 16:28:44
This is good news for those of us which implement APIs (and care about size and stuff like that) and also those who interface binary values outside of REBOL.

Gregg Irwin
3-Apr-2007 17:53:03
I would say the place this will be used most is interfacing outside of REBOL. Of course, if you wanted to have a minimal OS, and write device drivers and things, in the same vein as Forth, this would be fabulous. :-)
3-Apr-2007 19:19:51
I like it as well but I have to say... please don't forget to give us easy way how to convert these bitsets from and to binary format. So I hope that make bitset! 2#{00000110} will be available:)
Peter Wood
3-Apr-2007 22:12:46
And, of course, someone will suggest bit fields too, eh? But, where do we stop?

bit: make bitset! 1

Though I presume that it would be longer than one bit.

Carl Sassenrath
3-Apr-2007 23:51:26
Yes, useful for externals. Writing native ports created the motivation.

Oldes: definitely converters needed and to be provided.

On bit fields, I meant:

  flgs: make bitset! [flaga flagb fld1: 4 fld2: 6]
  print flgs/fld1
  flgs/fld2: 7

But, that's no longer a "bitset" definition, is it. [Buzzer sound]

4-Apr-2007 8:48:25
Bitfields specification! This would be fantastic for the decoding of some protocols I use (e.g. Eurocontrol's ASTERIX for example).

I made a try with Rebol some time ago to generate decoders, but it just felt bad when i saw the result. If I could specify the bitfields just like in your example, it would turn to really trivial stuff.

I would just junk my ruby scripts. ^^

Brian Hawley
4-Apr-2007 11:07:51
Carl, if you are worried about the bitfield syntax, perhaps you could use a placeholder word like none to indicate skipped bits, like this:
flgs: make bitset! [flaga flagb none none fld1 none fld2]

I think converters could be attached to the to action, allowing you to directly convert a binary or integer into a bitset.

Maxim Olivier-Adlhoch
5-Apr-2007 2:24:13
excellent idea brian.
5-Apr-2007 14:48:52
for bitfields, borrow from parse? Not [fld1:4] but [4 fld]. Would work with Brians suggestion, [flaga flagb 2 none]
6-Apr-2007 6:53:46
I like it a lot. It's Rebolish and the first thing how one expects bitsets to work.
Brian Hawley
7-Apr-2007 11:41:22
Volker, that sounds interesting. What he was suggesting was that the flag mean a specific number, rather than be repeated for number of times, so your first example wouldn't work because you wouldn't know which of the bits fld is referring to. Your second example makes much more sense and would be a way to get rid of NONE proliferation.

For that matter, if you are going with PARSE-like syntax, it would make more sense to use SKIP instead of NONE. That would make the repeat values seem more natural.

The main disadvantage of Carl's set-word suggestion would be making sure the numbers don't clash with existing field positions or each other. That wouldn't be a problem with SKIP, although adding them up could be annoying.

11-Apr-2007 11:36:46
I really like this. So series operations can be used like

forall next set-of-bits [...]

Post a Comment:

You can post a comment here. Keep it on-topic.


Blog id:



 Note: HTML tags allowed for: b i u li ol ul font span div a p br pre tt blockquote

This is a technical blog related to the above topic. We reserve the right to remove comments that are off-topic, irrelevant links, advertisements, spams, personal attacks, politics, religion, etc.

Updated 26-Mar-2017 - Edit - Copyright REBOL Technologies -