Bit ops for Scheme Olin Shivers First draft: 6/3/96 Last Update: 98/11/11 This document can be viewed in emacs outline mode, with *'s introducing section headings -- just say M-x outline-mode in emacs. During the SRFI discussion period, the current draft may be found at ftp://ftp.ai.mit.edu/pub/shivers/bitop-doc.txt * Table of contents ------------------- Abstract Procedures General discussion Related designs Code ------------------------------------------------------------------------------- * Abstract ---------- R5RS Scheme has no utilities for performing bitwise logical operations on integers or bitstrings, which is a problem for authors of portable code. This SRFI proposes a coherent and comprehensive set of these procedures; it is accompanied by a reference implementation of the spec in terms of a set of seven core operators. The reference implementation is - portable - efficient - completely open, public-domain source The precise semantics of these operators is almost never an issue. A consistent, portable set of *name*, however, is. Hence this SRFI. ------------------------------------------------------------------------------- * Procedures ------------ bitwise-not i Associative (n-ary operators, for n >= 0) bitwise-and i ... bitwise-ior i ... bitwise-xor i ... bitwise-eqv i ... not xor Non-associative (binary) bitwise-nand i j not and bitwise-nor i j not ior bitwise-andc1 i j bitwise-andc2 i j bitwise-orc1 i j not andc2 bitwise-orc2 i j not andc1 Non-associative and trivial -- hence not provided bitwise-const0 i j (lambda (i j) 0) bitwise-const1 i j (lambda (i j) 1) bitwise-arg1 i j (lambda (i j) i) bitwise-arg2 i j (lambda (i j) j) bitwise-not1 i j (lambda (i j) (bitwise-not i)) bitwise-not2 i j (lambda (i j) (bitwise-not j)) - These 16 functions are the complete set of binary boolean operators. I have chosen to provide the full set, barring the last, trivial group of six. arithmetic-shift i count Arithmetic right shift (COUNT>0); left shift (COUNT<0). bit-count i Population count of 1's (non-neg) or 0's (neg). integer-length i As in Common Lisp -- number of bits needed for I. The Common Lisp spec, adapted for R4RS: (ceiling (/ (log (if (negative? integer) (- integer) (+ 1 integer))) (log 2))) ; Scheme needs a 2-arg LOG. For i >= 0, this is the number of bits needed to represent I in an unsigned representation. For all i, (+ 1 (integer-length i)) is the number of bits needed to represent i in a signed, twos-complement representation. (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 bitwise-merge mask i0 i1 RESULT[k] := if MASK[k] = 0 then I0[k] else I1[k]. bit-set? index i any-bits-set? test-bits i (not (zero? (bitwise-and TEST-BITS I))) all-bits-set? test-bits i (= TEST-BITS (bitwise-and TEST-BITS I))) extract-bit-field size position i test-bit-field? size position i ; #t if any of the field's bits are set in I. clear-bit-field size position i ; Zero out field's bits in I. insert-bit-field size position new-field i copy-bit-field size position from to - The bit-field ops are the Common Lisp "byte" ops. - EXTRACT-BIT-FIELD returns the designated bit field from I, shifted down to the least-significant position in the result. - INSERT-BIT-FIELD returns I with the designated bit field replaced by the least-significant SIZE bits in NEW-FIELD. - COPY-BIT-FIELD extracts the designated bit field from FROM and uses it to replace the same bit-field in TO. ------------------------------------------------------------------------------- * General discussion -------------------- - These ops interpret exact integers using two's-complement representation; integers thus represent semi-infinite bit-strings. They are only defined for exact integer arguments. - I examined Common Lisp and slib's designs when constructing this one. Further comments appear below. - It is not optional for the associative bitwise ops to be n-ary instead of merely binary. They are required to n-ary. Programmers can *reliably* write BITWISE-AND with 3 arguments, for example. - Comparisons with Common Lisp's design: + "load" and "deposit" are the wrong verbs (e.g., CL's LDB and DPB ops), since these guys have nothing to do with the store. I chose "extract" and "insert." + CL's byte datatype doesn't seem to buy you anything over just spelling out size & position, or [start,end) values. + I punted BOOLE; it is not one with the Way of Scheme. Boolean functions are directly encoded in Scheme as first-class procedures. + My name choices are more in tune with Scheme conventions (hyphenation, using "?" to mark a predicate, etc.). CL's name choices were more historically motivated, for reasons of backwards compatibility with Maclisp and Zetalisp. + I punted the prefix "log" in favor of "bitwise-" (e.g, LOGNOT, BITWISE-NOT) * The integer ops are no more "logical" than the #f/#t ops, so the "log" prefix is misleading. * The integer ops are bitwise in nature; the prefix "bitwise-" more accurately reflects what they do. * There is general agreement among people I've polled that this is the right prefix. + I also punted the 6 trivial binary boolean ops. I kept the six non-trivial but less common ops. - Is the inclusive-or function written "or" or "ior"? This kind of thing trips me up all the time when I use these types of procedures. In my design, there's a simple rule: it is *never* simply "or." The "or" always has modifiers -- "xor," "ior," "nor," "orc1," and "orc2." As it turns out, my boolean op names are *exactly* Common Lisp's. Although that was not an important criterion for the design, it's an extra plus. - Why not a minimal set of ops? I included extra and redundant functions such as BIT-COUNT, BITWISE-NOR, and the bit-field ops in my design. Doing so helps readability, writability, and efficiency. + Readability: 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-AND's, -OR's, and -NOT's. Most of these derived ops are simple to implement in under three lines of code. Providing a basic implementation does not put a burden on the implementor. In fact, all but seven of the ops can be defined in under fifty lines of code, which I append below. What we gain is having an agreed-upon set of names by which we can refer to these functions. + Writeability: The programmer doesn't have to re-implement these procedures, and stumble over the boundary cases and error checking. The programmer can express himself using a full palette of building blocks. + Efficiency: Compilers can directly implement these ops for great efficiency gains without requiring any tricky analysis. If you believe in "small is beautiful," then what is your motivation for including anything beyond BITWISE-NAND? I believe I have the basic set of ops. Have I missed anything? - In June 1996, this proposal went through a round of discussion on the Net, in particular with Clinger and Jaffer. This resulted in several updates: - The procedures were explicitly required to operate only on exact integers. - ASH was renamed ARITHMETIC-SHIFT. - BIT-COUNT was preferred to POP-COUNT and POPULATION-COUNT. Note that, as Clinger points out, "BIT-" is the proper prefix for this After the discussion converged, the proposal sat on my disk for two years. ------------------------------------------------------------------------------- * Related designs ----------------- ** Common Lisp lognot n Associative: log{ior,xor,and,eqv} Non-associative: log{nand,nor,andc1,andc2,orc1,orc2} (boole op i j) op one of boole-{clr,set,1,2,c1,c2,and,ior,xor,eqv,nand,nor, andc1,andc2,orc1,orc2} (logtest testbits n) ; #t if any of the 1 bits in TESTBITS are set in N. (not (zerop (logand x y))) (logbitp index n) ; #t if bit # INDEX in N is set. (not (zero? (logand n (ash 1 index)))) ash n count logcount n ; pop-count integer-length n A CL byte is a contiguous field of bits in an int. (byte size position) -> byte-specifier (byte-size byte-spec) -> int (byte-position byte-spec) -> int (ldb bytespec n) ; Extracted byte is shifted down to lsb position. (ldb-test bytespec n) #t if any bits in the byte are 1's. (mask-field bytespec n) Zero out all bits not in bytespec. (dpb newbyte bytespec n) ; Replacement bits are low bits of newbyte (deposit-field from bytespec n) ; Replacement bits are (ldb from bytespec) ** slib Slib has a clone of a chunk of CL's design. It also has (bit-extract n start end) which is like ldb on bits [start,end) of n. ------------------------------------------------------------------------------- * Code ------ 23 functions in the spec. 15 can be defined in under two lines of code; 16 in under three lines of code (INSERT-BIT-FIELD needs three lines). This is not an onerous implementation load; I provide the code below. That leaves 7 basic functions that must be primitively defined for each implementation: BITWISE-{NOT,AND,IOR,XOR}, ARITHMETIC-SHIFT, BIT-COUNT, and INTEGER-LENGTH. Slib has implementations of even these procedures using R4RS arithmetic, so a simple-minded implementation again doesn't need to do much to support them -- however, slib's general implementations are terribly inefficient relative to native support and should *not* be used except in case of dire emergency. (It's quite clever code, nonetheless, to provide the semantics with such little support.) Here is reference code for the 16 derived functions. A good implementation might choose to provide direct compiler support for them, or might simply define them to be integrable -- i.e., inline-expanded. As this is only 27 lines of code, it hardly seems reasonable to bother discussing copyright. To lay the issue to rest, I am the sole author, and I place it in the public domain. ;;; The seven non-trivial binary boolean functions in terms ;;; of not, and, or & xor. (define (bitwise-eqv i j) (bitwise-not (bitwise-xor i j))) (define (bitwise-nand i j) (bitwise-not (bitwise-and i j))) (define (bitwise-nor i j) (bitwise-not (bitwise-ior i j))) (define (bitwise-andc1 i j) (bitwise-and (bitwise-not i) j)) (define (bitwise-andc2 i j) (bitwise-and i (bitwise-not j))) (define (bitwise-orc1 i j) (bitwise-ior (bitwise-not i) j)) (define (bitwise-orc2 i j) (bitwise-ior i (bitwise-not j))) (define (%mask size) (- (arithmetic-shift 1 size) 1)) ; Helper function. (define (bit-set? index n) (not (zero? (bitwise-and (arithmetic-shift 1 index) n)))) (define (any-bits-set? test-bits n) (not (zero? (bitwise-and test-bits n)))) (define (all-bits-set? test-bits n) (= test-bits (bitwise-and test-bits n))) (define (bitwise-merge mask n0 n1) (bitwise-ior (bitwise-and mask n1) (bitwise-and (bitwise-not mask) n0))) ;;; Bit-field ops (define (extract-bit-field size position n) (bitwise-and (%mask size) (arithmetic-shift n (- position)))) (define (test-bit-field? size position n) (not (zero? (bitwise-and (arithmetic-shift n (- position)) (%mask size))))) ;; Integrating i-b-f reduces nicely. (define (clear-bit-field size position n) (insert-bit-field size position 0 n)) ;;; Oops -- Intermediate ARITHMETIC-SHIFT can fixnum-overflow on fixnum args. ;(define (insert-bit-field size position newfield n) ; (copy-bit-field size position (arithmetic-shift newfield position) n)) ;;; This three-line version won't fixnum-overflow on fixnum args. (define (insert-bit-field size position newfield n) (let ((m (%mask size))) (bitwise-ior (bitwise-and n (bitwise-not (arithmetic-shift m position))) (arithmetic-shift (bitwise-and newfield m) position)))) (define (copy-bit-field size position from to) (bitwise-merge (arithmetic-shift (%mask size) position) to from))