Bit manipulation

in Forth

This is part of the tutorial of Leonard Morgenstern


sources on SVFIG , : http://www.forth.org/svfig/Len/bits.htm#A%20bit%20array


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.

Boolean flags

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.

Example 1:

Leave a TRUE flag on the stack if A and B are unequal:

It is permissible but inadvisable to use A B - if ... then ...

Example 2:

Leave a TRUE flag on the stack if A and B are unequal AND B and C are unequal

You are in trouble if you use A B - C D - and

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

For example, A B - 0<> C D - 0<> and

Even better here is A B <> C D <> and

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

(Zero bits in n2 will reset bits to 0).

invert and

( n1 n2 -- n' ) Turn off bits.

(1 bits in n2 will reset bits to 0.)

or (n1 n2 -- n') Set bits

(1 bits in n2 will set bits to 1.)

xor (n1 n2 -- n') Logical xor. Invert bits.

(1 bits in n2 will invert bits in result.)

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.

cset (mask adr -- ) Turn on bits. (Not standard)

creset (mask adr --) Turn off bits. (Not standard)

ctoggle (mask adr -- ) Invert bits. (Not standard)

c! ( c adr -- ) Store the character at the address

erase ( adr n -- ) Fill a series of n consecutive characters with 0

fill ( adr n c -- ) Fill a series of n consecutive characters with c

blank ( adr n c -- ) Fill a series of n consecutive characters with blanks

A bit array

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.

Home

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


original document : -- Mr. Leonard Morgenstein -- web adaption by PeterForth 2019