Learning Forth Bit by Bit
Bit Manipulations in Forth
First, Boolean flags will be discussed, then bit manipulations, categorized as folows: 1) words that manipulate the stack, 2) words that manipulate bytes in RAM, and 3) bit arrays.
A Boolean flag, often simply called a flag, is a quantity that can have two possible states, true or false. In the ANS standard, false is represented by a "single-cell datum with all bits unset" and true a "single-cell datum with all bits set." false is in the Core Extension Set, and is defined as the value of a single cell containing a false flag. true is equivalent to 0 0=.
To conform to the standard, a word that leaves a Boolean flag on the stack, for example = must leave either all bits set or all bits unset. However, a word that accepts a flag, such as if, until, etc. will regard as true any value on the stack that is not false.
This results in a certain ambiguity, which can be avoided by the use of "well-formed" flags. The standard states, "If an operation whose result is to be used as a flag may produce any bit pattern other than TRUE or false, the recommended discipline is to convert the result to a well formed flag by means of the Forth word 0 so that the result of any subsequent logical operation will be predictable." Thus, it is permissible but dangerous to use the result of an arithmetic operation as a flag. The errors that result from violating this guide-line may be very hard to detect. I speak here from bitter experience.
For example 7 4 - 7 3 - and will result in false. In other words, two non-false arithmetic quantities and to false.
This problem can be avoided if you always use 0<>.
Logical manipulations on the stack
The words in this section are all standard; most of them are binary operations. The bits of the two words are matched according to the rules of Boolean algebra. The beginner should experiment with these until the operations are thoroughly familiar.
These words can be used in two ways: 1) to perform logical operations on well-formed flags, and 2) for the binary operations, to set or reset specified bits. In general, the top of the stack is regarded as a mask that operates on the next-lower item; in other words, n2 is a mask and n1 is an operand.
invert ( n -- n') Perform logical NOT. invert Inverts all bits in n, that is it changes every 1 to 0 and every 0 to 1. Do not confuse with negate, which is an arithmetic operation that multiplies by -1. In the Forth 83 standard, not was equivalent to negate . However, Forths which used some value other than -1 as true, employed not as as a way to convert their true into false and vice versa. The ANS committee wisely decided not to include not in the standard.
and (n1 n2 -- n') Reset bits
or (n1 n2 -- n') Set bits
xor (n1 n2 -- n') Logical xor. Invert bits.
Bit manipulations in RAM
Certain Forth words that begin with C signify manipulation of characters in RAM. In every case, the bits affected are those that correspond to 1 bits in the mask. These words are so useful that you will probably find all of them in every Forth although some are not standard.
In Forth, an indexed array returns an address, given an index. This is also true of bit arrays, but remember that (unless you are working with an unusual CPU) it takes two words to pinpoint a bit: a mask and an address. As a result, a bit array has the stack diagram (index -- mask adr). Given the mask and address, cset, creset, and ctoggle will perform the desired action.
create masks 128 c, 64 c, 32 c, 16 c, 8 c, 4 c, 2 c, 1 c, : bit-array ( len -- ) ( i -- m a) create allot does> swap 8 /mod masks + c@ -rot + ;
We also need words to store and fetch bits. The words .@ and .! Will fetch and store, respectively, a Boolean flag on the stack to a bit array. (Do not confuse .! with cset or .@ with creset.)
: .! ( f m a -- ) rot if cset else creset then ; : .@ ( m a -- f ) c@ and 0<> ; \ Example 3 bit-array thflag \ Create a bit array for 24 bit-flags 11 thflag ctoggle \ Toggle the 11th bit 10 thFLAG .@ ( -- f) \ Extract the 10th bit and leave as well-formed Boolean flag
Code meets requrements for an ANS Forth standard program with Core Extension Set.
First Presented at North Bay Forth Interest Group, September 9, 1989.
Updated: June 18, 1996
\ Source code for bits.htm \ Bit-array is a defining word that will create a bit array. \ l is the number of bytes create masks 128 c, 64 c, 32 c, 16 c, 8 c, 4 c, 2 c, 1 c, : bit-array ( l -- ) ( i -- m a) create allot does> swap 8 /mod masks + c@ -rot + ; \ We also need words to store and fetch bits. The words .@ and .! \ Will fetch and store, respectively, a Boolean flag on the stack to \ a bit array. (Do not confuse .! with cset or .@ with creset.) : .! ( f m a -- ) rot if cset else creset then ; : .@ ( m a -- f ) c@ and 0<> ; \ Example 3 bit-array thflag \ Create a bit array for 24 bit-flags 11 thflag ctoggle \ Toggle the 11th bit 10 thFLAG .@ ( -- f) \ Extract the 10th bit and leave as well-formed Boolean flag