Bitwise arithmetic procedures

This proposal is based mainly on SRFI 33, with some changes and additions from Olin's late revisions to SRFI 33 (which were never consummated) and a few procedures from SRFI 60 and the general vector SRFI 133.

Abstract

This SRFI proposes a coherent and comprehensive set of procedures for performing bitwise logical operations on integers; it is accompanied by a reference implementation of the spec in terms of a set of seven core operators. The sample implementation is portable, as efficient as practical with pure Scheme arithmetic (it is worthwhile replacing the core ops with C or assembly language if possible), and open source. The precise semantics of these operators is almost never an issue. A consistent, portable set of names and parameter conventions, however, is. Hence this SRFI.

Among the applications of bitwise operations are: hashing, Galois-field calculations of error-detecting and error-correcting codes, cryptography and ciphers, pseudo-random number generation, register-transfer-level modeling of digital logic designs, Fast-Fourier transforms, packing and unpacking numbers in persistant data structures, space-filling curves with applications to dimension reduction and sparse multi-dimensional database indexes, and generating approximate seed values for root-finders and transcendental function algorithms.

Procedure index

bitwise-not bitwise-and bitwise-ior bitwise-xor bitwise-eqv bitwise-nand bitwise-nor bitwise-andc1 bitwise-andc2 bitwise-orc1 bitwise-orc2 arithmetic-shift bit-count integer-length bitwise-if bit-set? copy-bit bit-swap any-bit-set? every-bit-set? first-set-bit bit-field bit-field-any? bit-field-every? bit-field-clear bit-field-set bit-field-replace bit-field-replace-same bit-field-rotate bit-field-reverse bit-field-append integer->list list->integer bits bitwise-fold bitwise-for-each bitwise-unfold

Rationale

General design principles

• These operations interpret exact integers using two's-complement representation.

• It is not optional for the associative bitwise ops to be n-ary instead of merely binary. They are required to be n-ary. Programmers can reliably write bitwise-and with 3 arguments, for example.

• The word or is never used by itself, only with modifiers: xor, ior, nor, orc1, or orc2. This is the same rule as Common Lisp.

• Extra and redundant functions such as bitwise-count, bitwise-nor and the bit-field ops have been included. Settling on a standard choice of names makes it easier to read code that uses these sorts of operations. It also means computations can be clearly expressed using the more powerful ops rather than synthesized with a snarled mess of bitwise-ands, bitwise-ors, and bitwise-nots. What we gain is having an agreed-upon set of names by which we can refer to these functions. If you believe in "small is beautiful," then what is your motivation for including anything beyond bitwise-nand?

• The programmer doesn't have to re-implement the redundant functions, and stumble over the boundary cases and error checking. The programmer can express himself using a full palette of building blocks.

• Compilers can directly implement many of these ops for great efficiency gains without requiring any tricky analysis.

• Logical right or left shift operations are excluded because they are not well defined on general integers; they are only defined on integers in some finite range. Remember that, in this library, integers are interpreted as semi-infinite bit strings that have only a finite number of ones or a finite number of zeros. Logical shifting operates on bit strings of some fixed size. If we shift left, then leftmost bits "fall off" the end (and zeros shift in on the right). If we shift right, then zeros shift into the string on the left (and rightmost bits fall off the end). So to define a logical shift operation, we must specify the size of the window. Typically this is the width of the underlying machine's register set (e.g., 32 bits). This is blatantly machine-specific and unportable, and clearly not the right thing for Scheme's more machine-independent general integers.

Differences from Common Lisp

The core of this design design mirrors the structure of Common Lisp's pretty closely. Here are some differences:

• "load" and "deposit" are the wrong verbs (e.g., Common Lisp's ldb and dpb ops), since these guys have nothing to do with the store.

• boole has been removed; it is not one with the Way of Scheme. Boolean functions are directly encoded in Scheme as first-class functions.

• The name choices are more in tune with Scheme conventions (hyphenation, using ? to mark a predicate, etc.). Common Lisp's name choices were more historically motivated, for reasons of backward compatibility with Maclisp and Zetalisp.

• The prefix log has been changed to bitwise- (e.g, lognot to bitwise-not), as the prefix bitwise- more accurately reflects what they do.

• The six trivial binary boolean ops that return constants, the left or right arguments, and the bitwise-not of the left or right arguments, do not appear in this SRFI.

Changes to SRFI 33 names

BitwiseCowan retains SRFI 33 names for procedures adapted from SRFI 33, with these exceptions:

• The name bitwise-merge is replaced by bitwise-if, the name used in SRFI 60 and R6RS.

• The name extract-bit-field (bit-field-extract in Olin's revisions) is replaced by bit-field, the name used in SRFI 60 and R6RS.

• The names any-bits-set? and all-bits-set? are replaced by any-bit-set? and every-bit-set?, in accordance with Olin's revisions.

• The name test-bit-field? has been renamed bit-field-any? and supplemented with bit-field-every?, in accordance with Olin's revisions.

• Because copy-bit-field means different things in SRFI 33 and SRFI 60, SRFI 33's name copy-bit-field (bit-field-copy in Olin's revisions) has been changed to bit-field-replace-same.

SRFI 60

SRFI 60 includes six procedures that do not have SRFI 33 equivalents. They are incorporated into this SRFI as follows:

• The names rotate-bit-field and reverse-bit-field are replaced by bit-field-rotate and bit-field-reverse, in parallel with Olin's revisions.

• The procedures copy-bit, integer->list and list->integer are incorporated into this SRFI unchanged.

• The procedure booleans->integer is a convenient way to specify a bitwise integer in the absence of datum syntax: it accepts an arbitrary number of boolean arguments and returns a non-negative integer. So in this SRFI it has the short name bits, roughly analogous to list, string, and vector.

Other sources

The following procedures are inspired by SRFI 133: bit-swap, bit-field-append, bitwise-fold, bitwise-for-each, bitwise-unfold.

• The procedure bit-field-set is the counterpart of bit-field-clear.

Argument ordering and semantics

• In general, these procedures place the bitstring arguments to be operated on first. Where the operation is not commutative, the "destination" argument that provides the background to be operated on is placed before the "source" argument that provides the bits to be transferred to it.

• In SRFI 33, bitwise-nand and bitwise-or accepted an arbitrary number of arguments even though they are not commutative. Olin's late revisions made them dyadic, and so does this SRFI.

• Common Lisp bit-field operations use a byte spec to encapsulate the position and size of the field. SRFI 33 bit-field operations had leading position and size arguments instead. These have been replaced in this SRFI by start (inclusive) and end (exclusive) arguments, the convention used not only in SRFI 60 and R6RS but also in most other subsequence operations in Scheme standards and SRFIs.

Specification

In the following procedure specifications all parameters are exact integers; unless otherwise indicated, all return values are exact integers. It is an error to pass values of other types as arguments to these functions.

Bitstrings are represented by integers, using a two's-complement encoding of the bitstring. Thus every integer represents a semi-infinite bitstring, having either a finite number of zeros (negative integers) or a finite number of ones (non-negative integers). The bits of a bitstring are numbered from the rightmost/least-significant bit: bit !#0 is the rightmost or 2⁰ bit, bit !#1 is the next or 2¹ bit, and so forth.

Basic operations

(bitwise-not i) -> exact-integer

Bitwise logical negation.

(bitwise-not 10) => -11 (bitwise-not -37) => 36

The following ten procedures correspond to the useful set of non-trivial two-argument boolean functions. For each such function, the corresponding bitwise operator maps that function across a pair of bitstrings in a bit-wise fashion.

The core idea of this group of functions is this bitwise "lifting" of the set of dyadic boolean functions to bitstring parameters.

(bitwise-and i ...) -> exact-integer
(bitwise-ior i ...) -> exact-integer
(bitwise-xor i ...) -> exact-integer
(bitwise-eqv i ...) -> exact-integer

These operations are associative. When passed no arguments, the procedures return the identity values -1, 0, 0, and -1 respectively.

The bitwise-eqv procedure produces the negation of the bitwise-xor procedure. When applied to three arguments, it does not produce a 1 bit everywhere that a, b and c all agree. That is, it does not produce

(bitwise-ior (bitwise-and a b c) (bitwise-and (bitwise-not a) (bitwise-not b) (bitwise-not c)))

Rather, it produces (bitwise-eqv a (bitwise-eqv b c)) or the equivalent (bitwise-eqv (bitwise-eqv a b) c).

(bitwise-ior 3 10) => 11 (bitwise-and 11 26) => 10 (bitwise-xor 3 10) => 9 (bitwise-eqv 37 12) => -42 (bitwise-and 37 12) => 4

(bitwise-nand i j) -> exact-integer
(bitwise-nor i j) -> exact-integer
(bitwise-andc1 i j) -> exact-integer
(bitwise-andc2 i j) -> exact-integer
(bitwise-orc1 i j) -> exact-integer
(bitwise-orc2 i j) -> exact-integer

These operations are not associative.

(bitwise-nand 11 26) => -11 (bitwise-nor 11 26) => -28 (bitwise-andc1 11 26) => 16 (bitwise-andc2 11 26) => 1 (bitwise-orc1 11 26) => -2 (bitwise-orc2 11 26) => -17

Integer operations

(arithmetic-shift i count) -> exact-integer

Arithmetic left shift when count>0; right shift when count<0.

(arithmetic-shift 8 2) => 32 (arithmetic-shift 4 0) => 4 (arithmetic-shift 8 -1) => 4 (arithmetic-shift -100000000000000000000000000000000 -100) => -79

(bit-count i) -> nonnegative-exact-integer

Population count of 1's (i >= 0) or 0's (i < 0).

(bit-count 0) => 0 (bit-count -1) => 0 (bit-count 7) => 3 (bit-count 13) => 3 ;Two's-complement binary: ...0001101 (bit-count -13) => 2 ;Two's-complement binary: ...1110011 (bit-count 30) => 4 ;Two's-complement binary: ...0011110 (bit-count -30) => 4 ;Two's-complement binary: ...1100010 (bit-count (expt 2 100)) => 1 (bit-count (- (expt 2 100))) => 100 (bit-count (- (1+ (expt 2 100)))) => 1

(integer-length i) -> nonnegative-exact-integer

The number of bits needed to represent i, i.e.

(ceiling (/ (log (if (negative? integer) (- integer) (+ 1 integer))) (log 2)))

(integer-length 0) => 0 (integer-length 1) => 1 (integer-length -1) => 0 (integer-length 7) => 3 (integer-length -7) => 3 (integer-length 8) => 4 (integer-length -8) => 3 This is equivalent to: (bitwise-ior (bitwise-and (bitwise-not mask) i) (bitwise-and mask j)) As always, the rightmost/least-significant bit in i is bit 0. (bit-set? 1 1) => false (bit-set? 0 1) => true (bit-set? 3 10) => true (bit-set? 1000000 -1) => true (bit-set? 2 6) => true (bit-set? 0 6) => false returns (not (zero? (bitwise-and ''test-bits i'')))` (first-set-bit 1) => 0 (first-set-bit 2) => 1 (first-set-bit 0) => -1 (first-set-bit 40) => 3 (first-set-bit -28) => 2 (first-set-bit (expt 2 99)) => 99 (first-set-bit (expt -2 99)) => 99 The field specified The initial value of r When The values returned by proc are discarded. Returns Otherwise, apply mapper Then get a new state Note that it is an infinite generator. SRFI 33 was never finalized, but is a comprehensive proposal. SRFI 60 (based on SLIB) is smaller but has a few procedures of its own; some of its procedures have both native (often CL) and SRFI 33 names. R6RS is a subset of SRFI 60, but all procedure names begin with a bitwise- prefix.

Function	CL	SRFI 33	SRFI 33 late revs	SRFI 60	R6RS	This SRFI
Bitwise NOT	lognot	bitwise-not	bitwise-not	lognot, bitwise-not	bitwise-not	bitwise-not
Bitwise AND	logand	bitwise-and	bitwise-and	logand, bitwise-and	bitwise-and	bitwise-and
Bitwise IOR	logior	bitwise-ior	bitwise-ior	logior, bitwise-ior	bitwise-ior	bitwise-ior
Bitwise XOR	logxor	bitwise-xor	bitwise-xor	logxor, bitwise-xor	bitwise-xor	bitwise-xor
Bitwise EQV	logeqv	bitwise-eqv	bitwise-eqv	---	---	bitwise-eqv
Bitwise NAND	lognand	bitwise-nand	bitwise-nand	---	---	bitwise-nand
Bitwise NOR	lognor	bitwise-nor	bitwise-nor	---	---	bitwise-nor
Bitwise AND with NOT of first arg	logandc1	bitwise-andc1	bitwise-andc1	---	---	bitwise-andc1
Bitwise AND with NOT of second arg	logandc2	bitwise-andc2	bitwise-andc2	---	---	bitwise-andc2
Bitwise OR with NOT of first arg	logorc1	bitwise-orc1	bitwise-orc1	---	---	bitwise-orc1
Bitwise OR with NOT of second arg	logorc2	bitwise-orc2	bitwise-orc2	---	---	bitwise-orc2
Arithmetic shift	ash	arithmetic-shift	arithmetic-shift	ash, arithmetic-shift	bitwise-arithmetic-shift	arithmetic-shift
Population count	logcount	bit-count	bit-count	logcount, bit-count	bitwise-bit-count	bit-count
Integer length	integer-length	integer-length	integer-length	integer-length	bitwise-integer-length	integer-length
Mask selects source of bits	---	bitwise-merge	bitwise-merge	bitwise-if, bitwise-merge	bitwise-if	bitwise-if
Test single bit	logbitp	bit-set?	bit-set?	logbit?, bit-set?	bitwise-bit-set?	bit-set?
See if any mask bits set	logtest	any-bits-set?	any-bit-set?	logtest, any-bit-set?	---	any-bit-set
See if all mask bits set	---	all-bits-set?	every-bit-set?	---	---	every-bit-set?
Replace single bit	---	---	copy-bit	bitwise-copy-bit	---	copy-bit
Swap bits	---	---	---	---	---	bit-swap
Find first bit set	---	first-bit-set	first-set-bit	log2-binary-factors, first-set-bit	---	first-set-bit
Extract bit field	ldb	extract-bit-field	extract-bit-field	bit-field	bitwise-bit-field	bit-field
Test bit field (any)	ldb-test	test-bit-field?	bit-field-any?	---	---	bit-field-any?
Test bit field (every)	---	---	bit-field-every?	---	---	bit-field-every?
Clear bit field	mask-field	clear-bit-field	bit-field-clear	---	---	bit-field-clear
Replace bit field	dpb	replace-bit-field	bit-field-replace	copy-bit-field	bitwise-copy-bit-field	bit-field-replace
Replace corresponding bit field	deposit-field	deposit-field	copy-bit-field	---	---	bit-field-copy-same
Fill bit field	---	---	---	---	---	bit-field-fill
Rotate bit field	---	---	---	rotate-bit-field	bitwise-rotate-bit-field	bit-field-rotate
Reverse bit field	---	---	---	reverse-bit-field	bitwise-reverse-bit-field	bit-field-reverse
Append bit fields	---	---	---	---	---	bit-field-append
Integer to boolean list	---	---	---	integer->list	---	integer->list
Boolean list to integer	---	---	---	list->integer	---	list->integer
Booleans to integer	---	---	---	booleans->integer	---	bits

||Bitwise fold||---||---||---||---||---||bitwise-fold|

Bitwise for-each	---	---	---	---	---	bitwise-for-each
Bitwise unfold	---	---	---	---	---	bitwise-unfold