Title

Integer Bitwise-operation Library

Author

Olin Shivers

Status

This SRFI is currently in ``withdrawn'' status. To see an explanation of each status that a SRFI can hold, see here. To provide input on this SRFI, please mail to <srfi minus 33 at srfi dot schemers dot org>. See instructions here to subscribe to the list. You can access previous messages via the archive of the mailing list.


* Table of contents
-------------------
Abstract
Function index
Function Specification
Rationale & general discussion
Summaries of related designs
Reference implementation
Topics to be resolved during discussion phase
  SIZE/POSITION vs. FROM/TO field specs
  Order of arguments for non-bitstring parameters
  The name "bit-set?"
References & Links
Copyright

-------------------------------------------------------------------------------
* 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 functions; 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 *names* and *parameter conventions*, however, is.
Hence this SRFI.


-------------------------------------------------------------------------------
* Function 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-merge
bit-set? any-bits-set? all-bits-set?
first-set-bit

extract-bit-field test-bit-field? clear-bit-field
replace-bit-field  copy-bit-field


-------------------------------------------------------------------------------
* Function specifications
-------------------------

In a Scheme system that has a module or package system, these functions
should be contained in a module named "bitwise-lib". They may additionally
be provided as part of the general suite of numerical operations.

In the following function 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 zeroes (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^0 bit, bit #1 is
the next or 2^1 bit, and so forth.

bitwise-not i -> exact-integer
  Bitwise logical negation, i.e., -(i+1).

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

N-ary operators, for n >= 0
  Procedure 		Bit function
  ------------------	---------------------------------
  bitwise-and  i ...	And
  bitwise-ior  i ...	Inclusive or
  bitwise-xor  i ...	Exclusive or
  bitwise-eqv  i ...	(eqv b1 b2)  =  (not (xor b1 b2))
  bitwise-nand i ...	(not (and b ...))
  bitwise-nor  i ...	(not (or b ...))

  Note that the and, ior, xor and eqv operations are associative.

Exactly two arguments
  Procedure 		Bit function
  -----------------	-----------------
  bitwise-andc1 i j	(and (not bi) bj)
  bitwise-andc2 i j	(and bi (not bj))
  bitwise-orc1  i j	(ior (not bi) bj)
  bitwise-orc2  i j	(ior bi (not bj))

Trivial, hence not provided
  Procedure 		Definition
  -----------------	------------------------------
  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 procedures correspond to the complete set of two-argument
      boolean functions, that is, the complete set of
          bit x bit -> bit
      functions. For each such function, the corresponding bitwise operator
      maps that function across a pair of bitstrings in a bit-wise fashion. I
      have chosen to provide the full set, barring the last, trivial group of
      six.

      The core idea of this group of functions is this bitwise "lifting"
      of the set of dyadic boolean functions to bitstring parameters; the
      variadic generalisations are made where sensible.

    - The n-ary functions have these base, nullary cases:
      (bitwise-and)  => -1     (bitwise-ior) =>  0
      (bitwise-nand) =>  0     (bitwise-nor) => -1
      (bitwise-xor)  =>  0     (bitwise-eqv) => -1

    - Note that (bitwise-eqv a b c) does *not* produce a 1 bit
      everywhere a, b & 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)

    - Examples
      (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 11 26 12) =>  -9
      (bitwise-nor  11 26 12) => -32

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

    For i >= 0, this is the number of bits needed to
    represent I in an unsigned binary 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 -> exact-integer
    Merge the bitstrings I0 and I1, with bitstring MASK determining
    from which string to take each bit. That is,
        RESULT[k] := if MASK[k] = 0 then I0[k] else I1[k].
    or
        (bitwise-ior (bitwise-and (bitwise-not mask) i0)
                     (bitwise-and mask i1))

bit-set? index i -> boolean
    Is bit INDEX set in bitstring I? INDEX is a non-negative exact
    integer. The rightmost/least-significant bit in the bitstring 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

any-bits-set? test-bits i -> boolean
all-bits-set? test-bits i -> boolean
    Determines if any / all of the bits set in bitstring TEST-BITS are set
    in bitstring I. I.e.,  return
        (not (zero? (bitwise-and TEST-BITS I)))
    or
        (= TEST-BITS (bitwise-and TEST-BITS I)))
    respectively.

first-set-bit i -> exact-integer
    Return the index of the first (smallest index) 1 bit in bitstring I.
    Return -1 if I contains no 1 bits (i.e., if I is zero).

    (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

extract-bit-field size position i -> exact-integer
test-bit-field?   size position i -> boolean
clear-bit-field   size position i -> exact-integer
replace-bit-field size position new-field i -> exact-integer
copy-bit-field    size position from to     -> exact-integer

    These functions operate on a contiguous field of bits (a "byte," in
    Common-Lisp parlance) in a given bitstring I. SIZE and POSITION are
    non-negative exact integers specifying the field: it is the SIZE bits
    running from bit POSITION to bit POSITION+SIZE-1.

    - EXTRACT-BIT-FIELD returns the designated bit field from I, shifted
      down to the least-significant position in the result.

    - TEST-BIT-FIELD? returns true if any of the field's bits are set in
      bitstring I.

    - CLEAR-BIT-FIELD returns I with the selected field's bits zeroed out.

    - REPLACE-BIT-FIELD returns I with the designated bit field replaced
      by the least-significant SIZE bits in NEW-FIELD.

    - COPY-BIT-FIELD returns TO with the selected field's bits replaced
      by the same field's bits in FROM.


-------------------------------------------------------------------------------
* Rationale & general discussion
--------------------------------

- These operations interpret exact integers using two's-complement
  representation; integers thus represent semi-infinite bit-strings.
  They are only defined for exact integer arguments.

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

- This 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. I chose
    "extract" and "replace."

  + Common Lisp'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 functions.

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

  + 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 functions. 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 31 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.

  + Writability:
    The programmer doesn't have to re-implement these functions, 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?

- Why no "logical" right or left shift operations?
  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 zeroes. "Logical" shifting shifts bit
  strings of some fixed size. If we shift left, then leftmost bits "fall off"
  the end (and zeroes shift in on the right). If we shift right, then zeroes
  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 & unportable, and
  clearly not the right thing for Scheme's more machine-independent general
  integers. For Scheme's integers, arithmetic shift is the right thing. Note
  that this situation pertains as well in Common Lisp, and Common Lisp does
  exactly what this SRFI does: arithmetic shift, but no logical shift.

  If we were to define a "width 32" or "width 64" or "fixnum" integer datatype,
  then we could meaningfully define logical shift for these values.

  Alternately, we could define a "general" logical shift operation that
  took as an extra argument the size of the bitstring. At this point,
  we are bending over backward to force-fit an operation into Scheme
  that fundamentally doesn't belong. Arithmetic shift is the right
  thing for general integers.

- In June 1996, this proposal went through a round of discussion on the Net,
  in particular with Will Clinger and Aubrey Jaffer. This resulted in several
  updates:
    - The functions 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
      operation.
  After the discussion converged, the proposal sat on my disk for six years.

- This is a purely functional, side-effect-free implementation of bit
  operations -- all operations produce new, fresh results, rather than
  modifying old values. This can be implemented very efficiently for small
  bit vectors -- small enough to be unboxed values. Algorithms that work
  on larger bit vectors, however (such as data-flow analysis engines), might
  wish an alternate data-structure and associated set of operations that
  permits side-effecting or linear-updating operations (or both) on bit
  vectors. MIT Scheme, for example, provides such a facility. This should
  be considered for another SRFI. (See the short summary of the MIT Scheme
  system below.)

  I suggest that the design of such a system be deferred until SRFIs for
  strings and vectors have been finalised. Than a bit-vector SRFI could
  be designed that would preserve common structure with these other SRFIs,
  as well as the bitwise library in this SRFI.

  Note also that finite bit vectors have an isomorphism to finite sets.
  The design of both set-package and bit-vector SRFIs would probably want to
  keep this in mind -- maintaining parallel functional structure in the
  design.

-------------------------------------------------------------------------------
* Summaries of related designs
------------------------------
Below are summaries of the related libraries currently found in
Common Lisp, PLT Scheme, slib, Bigloo, Scheme 48, Kawa, and MIT Scheme.
I was unable to find anything for Gambit.

** 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)

** PLT Scheme
=============
bitwise-ior i1 ...
bitwise-and i1 ...
bitwise-xor i1 ...
bitwise-not i
arithmetic-shift i j

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

** Bigloo
=========
bit-or i1 i2
bit-xor i1 i2
bit-and i1 i2
bit-not i
bit-lsh i1 i2
bit-rsh i1 i2

** Chez
=======
General integers:
  integer-length i
  ash i count

Fixnums:
  fxlogand i j
  fxlogor i j
  fxlogxor i j
  fxlognot i
  fxsll i count		("shift left logical")
  fxsrl i count		("shift right logical")
  fxsla i count		("shift left arithmetic")
  fxsra i count		("shift right arithmetic")

** Scheme 48
============
bitwise-not i
bitwise-and i1 ...
bitwise-ior i1 ...
bitwise-xor i1 ...
arithmetic-shift i count

** MIT Scheme
=============
Fixnums:
  fix:not i
  fix:and i j
  fix:andc i j
  fix:or i j
  fix:xor i j
  fix:lsh i count

MIT Scheme also has a distinct datatype, the "bit vector." A bit vector
is *very* different, in that it its elements are mutable -- it is a mutable
vector of bits.

Constants are written with a sharp-star prefix, e.g. #*11111.

(make-bit-string k init)
(bit-string-allocate k)
(bit-string-copy bs)
(bit-string? object)
(bit-string-length bs)
(bit-string-ref bs k) -> boolean
(bit-string-set! bs k)
(bit-string-clear! bs k)
(bit-substring-find-next-set-bit bs start end)
(bit-string-append bs1 bs2)
(bit-substring bs start end)
(bit-string-zero? bs)
(bit-string=? bs1 bs2)
(bit-string-not bs)
(bit-string-movec! target-bs source-bs) ; Destructive NOT operation

(bit-string-and  bs1 bs2)	(bit-string-and!  target-bs1 bs2)
(bit-string-andc bs1 bs2)	(bit-string-andc! target-bs1 bs2)
(bit-string-or   bs1 bs2)	(bit-string-or!   target-bs1 bs2)
(bit-string-xor  bs1 bs2)	(bit-string-xor!  target-bs1 bs2)

(bit-string-fill! bs init)	; init is a boolean
(bit-string-move! target-bs bs)	; Must be of the same length
(bit-substring-move-right! source-bs start1 end1 target-bs start2)

(unsigned-integer->bit-string length integer)
(signed-integer->bit-string length integer)
(bit-string->unsigned-integer bit-string)
(bit-string->signed-integer bit-string)

** Guile & Kawa
===============
logand i1 ...
logior i1 ...
logxor i1 ...
lognot i
logtest i j	(any-bit-set?)
logbit? index i
ash i count
logcount i
integer-length i
bit-extract i start end

-------------------------------------------------------------------------------
* Reference implementation
--------------------------

There are 24 functions in the spec. 15 can be defined in under two lines of
code; REPLACE-BIT-FIELD needs three lines; and BITWISE-EQV needs five. This
is not an onerous implementation load; I provide the code below. As this is
only 31 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.

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

A good implementation might choose to provide direct compiler/interpreter
support for these derived functions, or might simply define them to be
integrable -- i.e., inline-expanded.

The n-ary BITWISE-EQV function should also receive primitive
compiler/interpreter support so that the expensive n-ary mechanism is not
invoked in the standard cases -- that is, an application of BITWISE-EQV should
be rewritten into an equivalent tree applying some two-argument primitive to
the arguments, in the same manner that statically-known n-ary applications of
associative operations such as + and * are handled efficiently:
  (bitwise-eqv)         => -1
  (bitwise-eqv i)       => i
  (bitwise-eqv i j)     => (%bitwise-eqv i j)
  (bitwise-eqv i j k)   => (%bitwise-eqv (%bitwise-eqv i j) k)
  (bitwise-eqv i j k l) => (%bitwise-eqv (%bitwise-eqv (%bitwise-eqv i j) k) l)

;;; The seven non-trivial boolean functions in terms
;;; of not, and, or & xor.

(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 (bitwise-eqv . args)
  (let lp ((args args) (ans -1))
    (if (pair? args)
        (lp (cdr args) (bitwise-not (bitwise-xor ans (car args))))
	ans)))

;;; Helper function -- make a mask of SIZE 1-bits, e.g. (%MASK 3) = #b111.
;;; Suppose your Scheme's fixnums are N bits wide (counting the sign bit,
;;; not counting any tag bits). This version, due to Marc Feeley, will
;;; handle SIZE in the range [0,N-1] without overflowing to bignums.
;;; (For SIZE >= N, the correct bignum value is also produced.)

(define (%mask size) (bitwise-not (arithmetic-shift -1 size)))

;;; This alternate, mathematically-equivalent expression
;;;     (- (arithmetic-shift 1 size) 1)
;;; is not as good -- it only handles SIZE in the range [0,N-2] without
;;; overflowing to bignums.
;;;
;;; Finally, note that even Feeley's expression can't build an N-bit mask
;;; without bignum help. This is fundamental, since the interpretation
;;; of fixed-size fixnum bit patterns as semi-infinite-bit-strings is that
;;; you replicate the high bit out to infinity. So you have to have a
;;; zero "stop bit" appearing after that highest one bit to turn off the
;;; replication of the ones.

(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)
  (replace-bit-field size position 0 n))

;;; Oops -- intermediate ARITHMETIC-SHIFT can fixnum-overflow on fixnum args.
;(define (replace-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 (replace-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))

;; Simple definition
;(define (first-set-bit i)
;  (and (not (zero? i))
;       (let lp ((j 0) (i start))
;         (if (bit-set? i 0) j
;             (lp (+ j 1) (arithmetic-shift i 1))))))

;;; Clever definition, assuming you have a fast BIT-COUNT.
(define (first-set-bit i) (- (bit-count (bitwise-xor i (- i 1))) 1))


-------------------------------------------------------------------------------
* Topics to be resolved during discussion phase
-----------------------------------------------
I particularly solicit comments about the following topics.

** SIZE/POSITION vs. FROM/TO field specs
========================================
Several functions in this library
    extract-bit-field size position i -> integer
    test-bit-field?   size position i -> boolean
    clear-bit-field   size position i -> integer
    replace-bit-field size position new-field i -> integer
    copy-bit-field    size position from to     -> integer
specify a contiguous "field" of bits in a bitstring. There are two
conventions we might use to do so:

  - SIZE/POSITION
    E.g., "the 8-bit field beginning at bit 3", and

  - FROM/TO
    E.g., "the field from bit 3 up to, but not including, bit 11", or, perhaps,
          "the field from bit 3 up to bit 10, inclusive."

FROM/TO specs are conventionally and most usefully "half-open" specs, meaning
"all i such that FROM <= i and i < TO" -- the FROM index is included and the
TO index is excluded.

I have chosen to use SIZE/POSITION instead of FROM/TO for this library.
Doing so eliminates any possibility of fencepost errors on the TO endpoint.
It is also the convention chosen by Common Lisp.

It is not, however, a widely-used convention within Scheme. Most ranges
in Scheme are specified with half-open intervals of the [from,to) form
(e.g., (substring s from to)). One might argue that SIZE/POSITION is still
the right thing for bit fields, as they are, in practice, frequently of fixed
size, unlike element ranges in strings or vectors.


** Order of arguments for non-bitstring parameters
==================================================
The "bitwise boolean" functions such as BITWISE-AND only take bitstring
parameters. But the following 10 functions are different in that they take
other *kinds* of parameters (masks, indices, field sizes) that indicate *the
exact operation to perform* on the bitstring parameter(s):
    arithmetic-shift i count -> integer
    bitwise-merge mask i0 i1 -> integer
    bit-set? index i -> boolean
    any-bits-set? test-bits i -> boolean
    all-bits-set? test-bits i -> boolean
    extract-bit-field size position i -> integer
    test-bit-field?   size position i -> boolean
    clear-bit-field   size position i -> integer
    replace-bit-field size position new-field i -> integer
    copy-bit-field    size position from to     -> integer
Note that in all of these functions, with the sole exception of
ARITHMETIC-SHIFT, the bitstring parameter comes last. This is consistent
with an "operation currying" convention, wherein the arguments that determine
the operation come first, and the actual value upon which we operate comes
last. MAP and FOLD, for example, work this way, too. (The "op currying"
convention is actually useful in SML; in Scheme, its utility is almost
entirely as a mnemonic convention to aid programmers in remembering argument
order.)

ARITHMETIC-SHIFT is entrenched by long and consistent tradition in the
indicated parameter order; it would be a mistake to alter this. Every
implementation of Scheme I have checked that offers a bit-shift operation on
integers (PLT Scheme, slib, Bigloo, Scheme 48, and MIT Scheme), as well as
Common Lisp, uses the "i count" argument order.

As an alternative to the "op currying" order, we could use the "data-structure
accessor" convention, wherein the data-structure being accessed (the
bitstring) comes first, and the "selector" arguments come after. For example,
this is the convention used for the functions VECTOR-REF and STRING-REF. One
could make the argument that this convention could be reasonably applied to
some of these operators, such as BIT-SET?

I recommend leaving things as they are, for maximal consistency with a simple
rule. This also provides consistency with Common Lisp, whose bitwise functions
uniformly use the ops-curry convention (see the "related designs" summary
below).


** The name "bit-set?"
======================
BIT-SET? uses the term "bit set," but that sounds like "Is this a set of
bits?" as well as the intended "is the bit set?" On the other hand, a set of
bits is a not-very-useful notion (there are, after all, only four such sets),
so I haven't pre-empted anything we'd ever really want for some other purpose,
such as a term like "bit vector" or something...


-------------------------------------------------------------------------------
* References & Links
--------------------

This document, in HTML:
    http://srfi.schemers.org/srfi-33/srfi-33.html
    [This link may not be valid while the SRFI is in draft form.]

This document, in simple text format:
    http://srfi.schemers.org/srfi-33/srfi-33.txt

Archive of SRFI-33 discussion-list email:
    http://srfi.schemers.org/srfi-33/mail-archive/maillist.html

SRFI web site:
    http://srfi.schemers.org/

[CommonLisp]
    Common Lisp: the Language
    Guy L. Steele Jr. (editor).
    Digital Press, Maynard, Mass., second edition 1990.
    Available at http://www.elwood.com/alu/table/references.htm#cltl2

    The Common Lisp "HyperSpec," produced by Kent Pitman, is essentially
    the ANSI spec for Common Lisp:
    http://www.xanalys.com/software_tools/reference/HyperSpec/

[R5RS]
    Revised^5 Report on the Algorithmic Language Scheme,
    R. Kelsey, W. Clinger, J. Rees (editors).
    Higher-Order and Symbolic Computation, Vol. 11, No. 1, September, 1998.
    and ACM SIGPLAN Notices, Vol. 33, No. 9, October, 1998.

    Available at http://www.schemers.org/Documents/Standards/


-------------------------------------------------------------------------------
* Copyright
-----------

This document is copyright (C) Olin Shivers (1998, 1999).
All Rights Reserved.

However, the program source found in section "Reference Implementation"
is by Olin Shivers and explicitly placed in the public domain.

Permission is hereby granted, free of charge, to any person obtaining
a copy of this software and associated documentation files (the
"Software"), to deal in the Software without restriction, including
without limitation the rights to use, copy, modify, merge, publish,
distribute, sublicense, and/or sell copies of the Software, and to
permit persons to whom the Software is furnished to do so, subject to
the following conditions:

The above copyright notice and this permission notice shall be
included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Editor: Francisco Solsona
Last modified: Sun Jan 28 13:40:32 MET 2007