# The bit-ops Reference Manual

Next: , Previous: , Up: (dir)   [Contents][Index]

# The bit-ops Reference Manual

This is the bit-ops Reference Manual, version 0.1, generated automatically by Declt version 2.4 "Will Decker" on Wed Jun 20 10:49:07 2018 GMT+0.

Next: , Previous: , Up: Top   [Contents][Index]

# Bit-Ops - Tools for Writing Optimized Bit-Vector Operations

In the modern Common Lisp implementations, bit-vector operation functions such as `bit-and` are compiled into word-size iterations where 32 or 64 bits are processed at once. However, it requires a careful handling when multiple operations are combined, e.g. for avoiding the generation of intermediate vectors by destructively modifying the existing vectors. For example,

``````(bit-and a (bit-and b c))
``````

causes consing since the intermediate value `(bit-and b c)` is generated on the heap. This library addresses this problem as well as the scarsity of useful bit-vector functions in ANSI CL.

## Related work

This section provides a review of related libraries, which I believe is important for alleviating choise paralysis.

BIT-SMASHER provides functions for converting bit-vector to/from integers, octets and hex strings. BIT-OPS does not have such conversion functions. BIT-SMASHER also provides functions for arithmetic, such as addition, subtraction, shifting. However, note that those operations are not always optimized and runs bitvec->integer->bitvec conversion each time, with possibly consing.

BITFIELD-SCHEMA provides several functions analogous to DPB and LPB for integers (GET/PUT-INTEGER). It also provides a DSL for writing accessors to bit-vectors (ala union type in C).

Example from the doc:

``````(defbitfield-schema tree-node (:offset offt)
(disabled-p   :width 1)
(values       :width 16 :count 10)
(left-child   :width 24)
(right-child  :width 7))
``````

BINARY-TYPES provides `DEFINE-BITFIELD` and `DEFINE-BINARY-CLASS` whose role is similar to `BITFIELD-SCHEMA`, but is for parsing machine integers, not bit-vectors. TRIVIAL-BIT-STREAMS provides a buffered stream of bits. NIBBLES provides optimized access to octet vectors, especially on SBCL by defining several SSE VOP operations.

## Usage

### Macro AS-BITWISE-OPERATIONS (&key result) &body body

Compute bitwise operations using bit vector arithmetic. `BODY` accepts a single form. Within `BODY`, one can use variables holding bit-vectors as arguments to bitwise operations, as well as constants 0 and 1, which maps to the bit vector filled with 0 or 1, respectively. All bit-vectors that are involved in bitwise operations should be of the same length.

Primitive operators corresponds to ANSI CL functions: For example, `(not subform)` is compiled into `(bit-not subform <temporary storage>)` . Following primitive operators are available:

``````not and andc1 andc2 eqv ior nand nor orc1 orc2 xor
``````

Additionally, `(SUBSEQ FORM OFFSET)` operator evaluates FORM and extracts its window starting from OFFSET and of the length equal to the other variables. FORM is a regular lisp expression, not a bitwise operation, and the result may be different from the other bit-vectors.

The final computation result is stored in a newly allocated vector, or in `RESULT` if specified, in spirit similar to the optional argument of Common Lisp bit-vector functions. The entire form returns the bit-vector which contains the result.

The compiler does various optimizations:

• Nested expressions store the results into dynamic-extent temporary vectors.
• Common subexpressions are eliminated.
• The number of temporary vectors are minimized/shared in spirit similar to register allocation.
• Macros for bitwise operations can be defined with `DEFINE-BITWISE-OPERATION`.
``````
(as-bitwise-operations ()
(and a b c))

->

(LET* ((#:LEN835 (LENGTH C)) (#:G833 (MAKE-BIT-VECTOR #:LEN835)))
(LET* ((+ZERO+ (MAKE-ZERO #:LEN835))
(+ONE+ (MAKE-ONE #:LEN835)))
(DECLARE (DYNAMIC-EXTENT +ZERO+ +ONE+))
(DECLARE (IGNORABLE +ZERO+ +ONE+))
(BIT-AND B C #:G833)
(BIT-AND A #:G833 #:G833)
#:G833))

(define-bitwise-operation if (condition then else)
`(ior (and ,condition ,then)
(andc1 ,condition ,else)))

(as-bitwise-operations (:result r)
(if a b c))

->

(LET* ((#:LEN839 (LENGTH C)) (#:G836 R))
(LET* ((+ZERO+ (MAKE-ZERO #:LEN839))
(+ONE+ (MAKE-ONE #:LEN839))
(#:G837 (MAKE-BIT-VECTOR #:LEN839)))
(DECLARE (DYNAMIC-EXTENT +ZERO+ +ONE+ #:G837))
(DECLARE (IGNORABLE +ZERO+ +ONE+))
(BIT-AND A B #:G836)
(BIT-ANDC1 A C #:G837)
(BIT-IOR #:G836 #:G837 #:G836)
#:G836))
``````

## Dependencies

This library is at least tested on implementation listed below:

• SBCL 1.3.13 on X86-64 Linux 4.4.0-59-generic (author's environment)
• CCL 1.11 X86-64 Linux 4.4.0-59-generic (author's environment)

Also, it depends on the following libraries:

• iterate by ** : Jonathan Amsterdam's iterator/gatherer/accumulator facility
• alexandria by Nikodemus Siivola nikodemus@sb-studio.net, and others. : Alexandria is a collection of portable public domain utilities.
• trivia :

## Author

• Masataro Asai (guicho2.71828@gmail.com)

Copyright (c) 2017 Masataro Asai (guicho2.71828@gmail.com)

Next: , Previous: , Up: Top   [Contents][Index]

## 2 Systems

The main system appears first, followed by any subsystem dependency.

Previous: , Up: Systems   [Contents][Index]

### 2.1 bit-ops

Author

Masataro Asai

Contact
Source Control

(:git "https://github.com/guicho271828/bit-ops.git")

Bug Tracker

LLGPL

Description

Optimized bit-vector operations

Version

0.1

Dependencies
• iterate
• alexandria
• trivia
• immutable-struct
• lisp-namespace
Source

bit-ops.asd (file)

Component

src (module)

Next: , Previous: , Up: Top   [Contents][Index]

## 3 Modules

Modules are listed depth-first from the system components tree.

Previous: , Up: Modules   [Contents][Index]

### 3.1 bit-ops/src

Parent

bit-ops (system)

Location

src/

Components

Next: , Previous: , Up: Top   [Contents][Index]

## 4 Files

Files are sorted by type and then listed depth-first from the systems components trees.

Previous: , Up: Files   [Contents][Index]

### 4.1 Lisp

Next: , Previous: , Up: Lisp files   [Contents][Index]

#### 4.1.1 bit-ops.asd

Location

bit-ops.asd

Systems

bit-ops (system)

Packages

Next: , Previous: , Up: Lisp files   [Contents][Index]

#### 4.1.2 bit-ops/src/package.lisp

Parent

src (module)

Location

src/package.lisp

Packages
Exported Definitions
Internal Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

#### 4.1.3 bit-ops/src/macros.lisp

Parent

src (module)

Location

src/macros.lisp

Previous: , Up: Lisp files   [Contents][Index]

#### 4.1.4 bit-ops/src/functions.lisp

Parent

src (module)

Location

src/functions.lisp

Exported Definitions

Next: , Previous: , Up: Top   [Contents][Index]

## 5 Packages

Packages are listed by definition order.

Next: , Previous: , Up: Packages   [Contents][Index]

### 5.1 bit-ops-asd

Source

bit-ops.asd

Use List
• asdf/interface
• common-lisp

Previous: , Up: Packages   [Contents][Index]

### 5.2 bit-ops

Source

package.lisp (file)

Use List
• lisp-namespace
• trivia.level2
• alexandria.0.dev
• iterate
• common-lisp
Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

## 6 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.

Next: , Previous: , Up: Definitions   [Contents][Index]

### 6.1 Exported definitions

Next: , Previous: , Up: Exported definitions   [Contents][Index]

#### 6.1.1 Macros

Macro: as-bitwise-operations (&key RESULT) &body BODY

Compute bitwise operations using bit vector arithmetic.
BODY accepts a single form. Within BODY, one can use variables holding bit-vectors as arguments to bitwise operations, as well as constants 0 and 1, which maps to the bit vector filled with
0 or 1, respectively.
All bit-vectors that are involved in bitwise operations should be of the same length.

Primitive operators corresponds to ANSI CL functions: For example, (not subform) is compiled into (bit-not subform <temporary storage>) . Following primitive operators are available:

not and andc1 andc2 eqv ior nand nor orc1 orc2 xor

Additionally, (SUBSEQ FORM OFFSET) operator evaluates FORM and
extracts its window starting from OFFSET and of the length equal to the other variables.
FORM is a regular lisp expression, not a bitwise operation, and the result may be different from the other bit-vectors.

The final computation result is stored in a newly allocated vector, or in RESULT if specified, in spirit similar to the optional argument of Common Lisp bit-vector functions.
The entire form returns the bit-vector which contains the result.

The compiler does various optimizations:

* Nested expressions store the results into dynamic-extent temporary vectors.
* Common subexpressions are eliminated.
* The number of temporary vectors are minimized/shared in spirit similar to register allocation. * Macros for bitwise operations can be defined with DEFINE-BITWISE-OPERATION.

Package
Source

package.lisp (file)

Macro: define-bitwise-operation NAME LAMBDA-LIST &body BODY

Defines a bitwise operation that is available within AS-BITWISE-OPERATIONS macro.

Primitive operators corresponds to ANSI CL functions: For example, (not subform) is compiled into (bit-not subform <temporary storage>) .

not and andc1 andc2 eqv ior nand nor orc1 orc2 xor

Package
Source

package.lisp (file)

Macro: dlet BINDINGS &body BODY
Package
Source

package.lisp (file)

Macro: dlet* BINDINGS &body BODY
Package
Source

package.lisp (file)

Previous: , Up: Exported definitions   [Contents][Index]

#### 6.1.2 Functions

Function: bit-if-then-else CONDITION THEN ELSE &optional RES

if A_i=1 then B_i else C_i

Package
Source

functions.lisp (file)

Function: bit-implies BV1 BV2 &optional BV3

a => b :- not a or b

Package
Source

functions.lisp (file)

Function: make-bit-vector LENGTH
Package
Source

package.lisp (file)

Previous: , Up: Definitions   [Contents][Index]

### 6.2 Internal definitions

Next: , Previous: , Up: Internal definitions   [Contents][Index]

#### 6.2.1 Special variables

Special Variable: *bitwise-operation-doc-table*
Package
Source

package.lisp (file)

Special Variable: *bitwise-operation-table*
Package
Source

package.lisp (file)

Special Variable: *common-subexpression-elimination*
Package
Source

package.lisp (file)

Special Variable: *first-variable*
Package
Source

package.lisp (file)

Special Variable: *length-variable*
Package
Source

package.lisp (file)

Special Variable: *ops*
Package
Source

package.lisp (file)

Special Variable: *register-allocation-optimization*
Package
Source

package.lisp (file)

Special Variable: *result-variable*
Package
Source

package.lisp (file)

Special Variable: *verbose*
Package
Source

package.lisp (file)

Next: , Previous: , Up: Internal definitions   [Contents][Index]

#### 6.2.2 Functions

Function: bit-replace SOURCE OFFSET DESTINATION

Wrapper for REPLACE which follows the syntax of bit-* (The last arg is the destination).

Package
Source

package.lisp (file)

Function: bitwise-operation-boundp SYMBOL

Automatically defined boolean function.

Package
Source

package.lisp (file)

Function: build-forms RESULT
Package
Source

package.lisp (file)

Function: common-subexpression OP1 OP2
Package
Source

package.lisp (file)

Function: compile-bitwise-operations FORM RESULT
Package
Source

package.lisp (file)

Function: copy-op INSTANCE
Package
Source

package.lisp (file)

Function: make-one LENGTH
Package
Source

package.lisp (file)

Function: make-op &key (NAME NAME) (INPUTS INPUTS) (OUTPUT OUTPUT)
Package
Source

package.lisp (file)

Function: make-zero LENGTH
Package
Source

package.lisp (file)

Function: op NAME INPUTS OUTPUT
Package
Source

package.lisp (file)

Function: op-inputs INSTANCE
Function: (setf op-inputs) VALUE INSTANCE
Package
Source

package.lisp (file)

Function: op-name INSTANCE
Function: (setf op-name) VALUE INSTANCE
Package
Source

package.lisp (file)

Function: op-output INSTANCE
Function: (setf op-output) VALUE INSTANCE
Package
Source

package.lisp (file)

Function: op-p OBJECT
Package
Source

package.lisp (file)

Function: parse-form FORM
Package
Source

package.lisp (file)

Function: reduce-allocation ()
Package
Source

package.lisp (file)

Function: symbol-bitwise-operation SYMBOL &optional DEFAULT

Automatically defined getter function. When DEFAULT is supplied, the value is set automatically.

Package
Source

package.lisp (file)

Writer

(setf symbol-bitwise-operation) (function)

Function: (setf symbol-bitwise-operation) NEW-VALUE SYMBOL

Automatically defined setter function.

Package
Source

package.lisp (file)

symbol-bitwise-operation (function)

Next: , Previous: , Up: Internal definitions   [Contents][Index]

#### 6.2.3 Conditions

Condition: unbound-bitwise-operation ()
Package
Source

package.lisp (file)

Direct superclasses

unbound-variable (condition)

Next: , Previous: , Up: Internal definitions   [Contents][Index]

#### 6.2.4 Structures

Structure: op ()
Package
Source

package.lisp (file)

Direct superclasses

structure-object (structure)

Direct slots
Slot: name

op-name (function)

Writers

(setf op-name) (function)

Slot: inputs

op-inputs (function)

Writers

(setf op-inputs) (function)

Slot: output

op-output (function)

Writers

(setf op-output) (function)

Previous: , Up: Internal definitions   [Contents][Index]

#### 6.2.5 Types

Type: bitwise-operation-type ()
Package
Source

package.lisp (file)

Previous: , Up: Top   [Contents][Index]

## Appendix A Indexes

Next: , Previous: , Up: Indexes   [Contents][Index]

### A.1 Concepts

Next: , Previous: , Up: Indexes   [Contents][Index]

### A.2 Functions

Jump to: (   A   B   C   D   F   M   O   P   R   S
Jump to: (   A   B   C   D   F   M   O   P   R   S

Next: , Previous: , Up: Indexes   [Contents][Index]