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

- Received: 2002/07/12
- Draft: 2002/07/15-2002/10/15
- Draft extension: 2003/01/31
- Withdrawn: 2003/07/17

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

Last modified: Sun Jan 28 13:40:32 MET 2007