The bit-ops Reference Manual

This is the bit-ops Reference Manual, version 0.1, generated automatically by Declt version 4.0 beta 2 "William Riker" on Tue Nov 15 04:18:14 2022 GMT+0.

1 Introduction

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 :

Installation

Author

Masataro Asai (guicho2.71828@gmail.com)

Copyright

License

Licensed under the LLGPL License.

2 Systems

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

bit-ops

2.1 `bit-ops`

Optimized bit-vector operations

Author

Masataro Asai

Contact

guicho2.71828@gmail.com

Home Page

https://github.com/guicho271828/bit-ops

Source Control

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

Bug Tracker

https://github.com/guicho271828/bit-ops/issues

License

LLGPL

Version

0.1

Dependencies

iterate (system).
alexandria (system).
trivia (system).
immutable-struct (system).
lisp-namespace (system).

Source

bit-ops.asd.

Child Component

src (module).

3 Modules

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

bit-ops/src

3.1 `bit-ops/src`

Source

bit-ops.asd.

Parent Component

bit-ops (system).

Child Components

package.lisp (file).
macros.lisp (file).
functions.lisp (file).

4 Files

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

Lisp

4.1.1 `bit-ops/bit-ops.asd`

Source: bit-ops.asd.
Parent Component: bit-ops (system).
ASDF Systems: bit-ops.
Packages: bit-ops-asd.

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

Source

bit-ops.asd.

Parent Component

src (module).

Packages

bit-ops.

Public Interface

as-bitwise-operations (macro).
define-bitwise-operation (macro).
dlet (macro).
dlet* (macro).
make-bit-vector (function).

Internals

*bitwise-operation-doc-table* (special variable).
*bitwise-operation-table* (special variable).
*common-subexpression-elimination* (special variable).
*first-variable* (special variable).
*length-variable* (special variable).
*ops* (special variable).
*register-allocation-optimization* (special variable).
*result-variable* (special variable).
*verbose* (special variable).
bit-replace (function).
bitwise-operation-boundp (function).
bitwise-operation-type (type).
build-forms (function).
common-subexpression (function).
compile-bitwise-operations (function).
copy-op (function).
make-one (function).
make-op (function).
make-zero (function).
op (function).
op (structure).
op-inputs (reader).
(setf op-inputs) (writer).
op-name (reader).
(setf op-name) (writer).
op-output (reader).
(setf op-output) (writer).
op-p (function).
parse-form (function).
reduce-allocation (function).
symbol-bitwise-operation (function).
(setf symbol-bitwise-operation) (function).
unbound-bitwise-operation (condition).

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

Source: bit-ops.asd.
Parent Component: src (module).

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

Source

bit-ops.asd.

Parent Component

src (module).

Public Interface

bit-if-then-else (function).
bit-implies (function).

5 Packages

Packages are listed by definition order.

bit-ops
bit-ops-asd

5.1 `bit-ops`

Source

package.lisp.

Use List

alexandria.
common-lisp.
iterate.
lisp-namespace.
trivia.level2.

Public Interface

as-bitwise-operations (macro).
bit-if-then-else (function).
bit-implies (function).
define-bitwise-operation (macro).
dlet (macro).
dlet* (macro).
make-bit-vector (function).

Internals

*bitwise-operation-doc-table* (special variable).
*bitwise-operation-table* (special variable).
*common-subexpression-elimination* (special variable).
*first-variable* (special variable).
*length-variable* (special variable).
*ops* (special variable).
*register-allocation-optimization* (special variable).
*result-variable* (special variable).
*verbose* (special variable).
bit-replace (function).
bitwise-operation-boundp (function).
bitwise-operation-type (type).
build-forms (function).
common-subexpression (function).
compile-bitwise-operations (function).
copy-op (function).
make-one (function).
make-op (function).
make-zero (function).
op (function).
op (structure).
op-inputs (reader).
(setf op-inputs) (writer).
op-name (reader).
(setf op-name) (writer).
op-output (reader).
(setf op-output) (writer).
op-p (function).
parse-form (function).
reduce-allocation (function).
symbol-bitwise-operation (function).
(setf symbol-bitwise-operation) (function).
unbound-bitwise-operation (condition).

5.2 `bit-ops-asd`

Source

bit-ops.asd.

Use List

asdf/interface.
common-lisp.

6 Definitions

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

Public Interface
Internals

6.1 Public Interface

Macros
Ordinary functions

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: bit-ops.
Source: package.lisp.

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: bit-ops.
Source: package.lisp.

Macro: dlet (bindings &body body) ¶

Package: bit-ops.
Source: package.lisp.

Macro: dlet* (bindings &body body) ¶

Package: bit-ops.
Source: package.lisp.

6.1.2 Ordinary functions

Function: bit-if-then-else (condition then else &optional res) ¶

if A_i=1 then B_i else C_i

Package: bit-ops.
Source: functions.lisp.

Function: bit-implies (bv1 bv2 &optional bv3) ¶

a => b :- not a or b

Package: bit-ops.
Source: functions.lisp.

Function: make-bit-vector (length) ¶

Package: bit-ops.
Source: package.lisp.

6.2 Internals

Special variables
Ordinary functions
Conditions
Structures
Types

6.2.1 Special variables

Special Variable: *bitwise-operation-doc-table* ¶

Package: bit-ops.
Source: package.lisp.

Special Variable: *bitwise-operation-table* ¶

Package: bit-ops.
Source: package.lisp.

Special Variable: *common-subexpression-elimination* ¶

Package: bit-ops.
Source: package.lisp.

Special Variable: *first-variable* ¶

Package: bit-ops.
Source: package.lisp.

Special Variable: *length-variable* ¶

Package: bit-ops.
Source: package.lisp.

Special Variable: *ops* ¶

Package: bit-ops.
Source: package.lisp.

Special Variable: *register-allocation-optimization* ¶

Package: bit-ops.
Source: package.lisp.

Special Variable: *result-variable* ¶

Package: bit-ops.
Source: package.lisp.

Special Variable: *verbose* ¶

Package: bit-ops.
Source: package.lisp.

6.2.2 Ordinary functions

Function: bit-replace (source offset destination) ¶

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

Package: bit-ops.
Source: package.lisp.

Function: bitwise-operation-boundp (symbol) ¶

Automatically defined boolean function.

Package: bit-ops.
Source: package.lisp.

Function: build-forms (result) ¶

Package: bit-ops.
Source: package.lisp.

Function: common-subexpression (op1 op2) ¶

Package: bit-ops.
Source: package.lisp.

Function: compile-bitwise-operations (form result) ¶

Package: bit-ops.
Source: package.lisp.

Function: copy-op (instance) ¶

Package: bit-ops.
Source: package.lisp.

Function: make-one (length) ¶

Package: bit-ops.
Source: package.lisp.

Function: make-op (&key name inputs output) ¶

Package: bit-ops.
Source: package.lisp.

Function: make-zero (length) ¶

Package: bit-ops.
Source: package.lisp.

Function: op (name inputs output) ¶

Package: bit-ops.
Source: package.lisp.

Reader: op-inputs (instance) ¶

Writer: (setf op-inputs) (instance) ¶

Package: bit-ops.
Source: package.lisp.
Target Slot: inputs.

Reader: op-name (instance) ¶

Writer: (setf op-name) (instance) ¶

Package: bit-ops.
Source: package.lisp.
Target Slot: name.

Reader: op-output (instance) ¶

Writer: (setf op-output) (instance) ¶

Package: bit-ops.
Source: package.lisp.
Target Slot: output.

Function: op-p (object) ¶

Package: bit-ops.
Source: package.lisp.

Function: parse-form (form) ¶

Package: bit-ops.
Source: package.lisp.

Function: reduce-allocation () ¶

Package: bit-ops.
Source: package.lisp.

Function: symbol-bitwise-operation (symbol &optional default) ¶

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

Package: bit-ops.
Source: package.lisp.

Function: (setf symbol-bitwise-operation) (symbol) ¶

Automatically defined setter function.

Package: bit-ops.
Source: package.lisp.

6.2.3 Conditions

Condition: unbound-bitwise-operation ¶

Package: bit-ops.
Source: package.lisp.
Direct superclasses: unbound-variable.

6.2.4 Structures

Structure: op ¶

Package

bit-ops.

Source

package.lisp.

Direct superclasses

structure-object.

Direct slots

Slot: name ¶

Readers: op-name.
Writers: (setf op-name).

Slot: inputs ¶

Readers: op-inputs.
Writers: (setf op-inputs).

Slot: output ¶

Readers: op-output.
Writers: (setf op-output).

6.2.5 Types

Type: bitwise-operation-type () ¶

Package: bit-ops.
Source: package.lisp.

Appendix A Indexes

Concepts
Functions
Variables
Data types

A.1 Concepts

A.2 Functions

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

	Index Entry	Section

(
	`(setf op-inputs)`:	Private ordinary functions
	`(setf op-name)`:	Private ordinary functions
	`(setf op-output)`:	Private ordinary functions
	`(setf symbol-bitwise-operation)`:	Private ordinary functions

A
	`as-bitwise-operations`:	Public macros

B
	`bit-if-then-else`:	Public ordinary functions
	`bit-implies`:	Public ordinary functions
	`bit-replace`:	Private ordinary functions
	`bitwise-operation-boundp`:	Private ordinary functions
	`build-forms`:	Private ordinary functions

C
	`common-subexpression`:	Private ordinary functions
	`compile-bitwise-operations`:	Private ordinary functions
	`copy-op`:	Private ordinary functions

D
	`define-bitwise-operation`:	Public macros
	`dlet`:	Public macros
	`dlet*`:	Public macros

F
	`Function, (setf op-inputs)`:	Private ordinary functions
	`Function, (setf op-name)`:	Private ordinary functions
	`Function, (setf op-output)`:	Private ordinary functions
	`Function, (setf symbol-bitwise-operation)`:	Private ordinary functions
	`Function, bit-if-then-else`:	Public ordinary functions
	`Function, bit-implies`:	Public ordinary functions
	`Function, bit-replace`:	Private ordinary functions
	`Function, bitwise-operation-boundp`:	Private ordinary functions
	`Function, build-forms`:	Private ordinary functions
	`Function, common-subexpression`:	Private ordinary functions
	`Function, compile-bitwise-operations`:	Private ordinary functions
	`Function, copy-op`:	Private ordinary functions
	`Function, make-bit-vector`:	Public ordinary functions
	`Function, make-one`:	Private ordinary functions
	`Function, make-op`:	Private ordinary functions
	`Function, make-zero`:	Private ordinary functions
	`Function, op`:	Private ordinary functions
	`Function, op-inputs`:	Private ordinary functions
	`Function, op-name`:	Private ordinary functions
	`Function, op-output`:	Private ordinary functions
	`Function, op-p`:	Private ordinary functions
	`Function, parse-form`:	Private ordinary functions
	`Function, reduce-allocation`:	Private ordinary functions
	`Function, symbol-bitwise-operation`:	Private ordinary functions

M
	`Macro, as-bitwise-operations`:	Public macros
	`Macro, define-bitwise-operation`:	Public macros
	`Macro, dlet`:	Public macros
	`Macro, dlet*`:	Public macros
	`make-bit-vector`:	Public ordinary functions
	`make-one`:	Private ordinary functions
	`make-op`:	Private ordinary functions
	`make-zero`:	Private ordinary functions

O
	`op`:	Private ordinary functions
	`op-inputs`:	Private ordinary functions
	`op-name`:	Private ordinary functions
	`op-output`:	Private ordinary functions
	`op-p`:	Private ordinary functions

P
	`parse-form`:	Private ordinary functions

R
	`reduce-allocation`:	Private ordinary functions

S
	`symbol-bitwise-operation`:	Private ordinary functions

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

A.3 Variables

Jump to:	* I N O S

	Index Entry	Section

*
	`bitwise-operation-doc-table`:	Private special variables
	`bitwise-operation-table`:	Private special variables
	`common-subexpression-elimination`:	Private special variables
	`first-variable`:	Private special variables
	`length-variable`:	Private special variables
	`ops`:	Private special variables
	`register-allocation-optimization`:	Private special variables
	`result-variable`:	Private special variables
	`verbose`:	Private special variables

I
	`inputs`:	Private structures

N
	`name`:	Private structures

O
	`output`:	Private structures

S
	`Slot, inputs`:	Private structures
	`Slot, name`:	Private structures
	`Slot, output`:	Private structures
	`Special Variable, bitwise-operation-doc-table`:	Private special variables
	`Special Variable, bitwise-operation-table`:	Private special variables
	`Special Variable, common-subexpression-elimination`:	Private special variables
	`Special Variable, first-variable`:	Private special variables
	`Special Variable, length-variable`:	Private special variables
	`Special Variable, ops`:	Private special variables
	`Special Variable, register-allocation-optimization`:	Private special variables
	`Special Variable, result-variable`:	Private special variables
	`Special Variable, verbose`:	Private special variables

Jump to:	* I N O S

A.4 Data types

Jump to:	B C F M O P S T U

	Index Entry	Section

B
	`bit-ops`:	The bit-ops system
	`bit-ops`:	The bit-ops package
	`bit-ops-asd`:	The bit-ops-asd package
	`bit-ops.asd`:	The bit-ops/bit-ops․asd file
	`bitwise-operation-type`:	Private types

C
	`Condition, unbound-bitwise-operation`:	Private conditions

F
	`File, bit-ops.asd`:	The bit-ops/bit-ops․asd file
	`File, functions.lisp`:	The bit-ops/src/functions․lisp file
	`File, macros.lisp`:	The bit-ops/src/macros․lisp file
	`File, package.lisp`:	The bit-ops/src/package․lisp file
	`functions.lisp`:	The bit-ops/src/functions․lisp file

M
	`macros.lisp`:	The bit-ops/src/macros․lisp file
	`Module, src`:	The bit-ops/src module

O
	`op`:	Private structures

P
	`Package, bit-ops`:	The bit-ops package
	`Package, bit-ops-asd`:	The bit-ops-asd package
	`package.lisp`:	The bit-ops/src/package․lisp file

S
	`src`:	The bit-ops/src module
	`Structure, op`:	Private structures
	`System, bit-ops`:	The bit-ops system

T
	`Type, bitwise-operation-type`:	Private types

U
	`unbound-bitwise-operation`:	Private conditions

Jump to:	B C F M O P S T U

The bit-ops Reference Manual

The bit-ops Reference Manual

Table of Contents

1 Introduction

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

Related work

Usage

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

Dependencies

Installation

Author

Copyright

License

2 Systems

2.1 bit-ops

3 Modules

3.1 bit-ops/src

4 Files

4.1 Lisp

4.1.1 bit-ops/bit-ops.asd

4.1.2 bit-ops/src/package.lisp

4.1.3 bit-ops/src/macros.lisp

4.1.4 bit-ops/src/functions.lisp

5 Packages

5.1 bit-ops

5.2 bit-ops-asd

6 Definitions

6.1 Public Interface

6.1.1 Macros

6.1.2 Ordinary functions

6.2 Internals

6.2.1 Special variables

6.2.2 Ordinary functions

6.2.3 Conditions

6.2.4 Structures

6.2.5 Types

Appendix A Indexes

A.1 Concepts

A.2 Functions

A.3 Variables

A.4 Data types

2.1 `bit-ops`

3.1 `bit-ops/src`

4.1.1 `bit-ops/bit-ops.asd`

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

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

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

5.1 `bit-ops`

5.2 `bit-ops-asd`