The bit-ops Reference Manual

Table of Contents

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.3 "Robert April" on Wed Mar 14 02:58:25 2018 GMT+0.


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

1 Introduction

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

Build Status

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:


(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:

Also, it depends on the following libraries:

Installation

Author

Copyright

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

License

Licensed under the LLGPL License.


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

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

Description

Optimized bit-vector operations

Version

0.1

Dependencies
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

bit-ops-asd


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

4.1.2 bit-ops/src/package.lisp

Parent

src (module)

Location

src/package.lisp

Packages

bit-ops

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

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

5.2 bit-ops

Source

package.lisp (file)

Use List
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

bit-ops

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

bit-ops

Source

package.lisp (file)

Macro: dlet BINDINGS &body BODY
Package

bit-ops

Source

package.lisp (file)

Macro: dlet* BINDINGS &body BODY
Package

bit-ops

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

bit-ops

Source

functions.lisp (file)

Function: bit-implies BV1 BV2 &optional BV3

a => b :- not a or b

Package

bit-ops

Source

functions.lisp (file)

Function: make-bit-vector LENGTH
Package

bit-ops

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

bit-ops

Source

package.lisp (file)

Special Variable: *bitwise-operation-table*
Package

bit-ops

Source

package.lisp (file)

Special Variable: *common-subexpression-elimination*
Package

bit-ops

Source

package.lisp (file)

Special Variable: *first-variable*
Package

bit-ops

Source

package.lisp (file)

Special Variable: *length-variable*
Package

bit-ops

Source

package.lisp (file)

Special Variable: *ops*
Package

bit-ops

Source

package.lisp (file)

Special Variable: *register-allocation-optimization*
Package

bit-ops

Source

package.lisp (file)

Special Variable: *result-variable*
Package

bit-ops

Source

package.lisp (file)

Special Variable: *verbose*
Package

bit-ops

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

bit-ops

Source

package.lisp (file)

Function: bitwise-operation-boundp SYMBOL

Automatically defined boolean function.

Package

bit-ops

Source

package.lisp (file)

Function: build-forms RESULT
Package

bit-ops

Source

package.lisp (file)

Function: common-subexpression OP1 OP2
Package

bit-ops

Source

package.lisp (file)

Function: compile-bitwise-operations FORM RESULT
Package

bit-ops

Source

package.lisp (file)

Function: copy-op INSTANCE
Package

bit-ops

Source

package.lisp (file)

Function: make-one LENGTH
Package

bit-ops

Source

package.lisp (file)

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

bit-ops

Source

package.lisp (file)

Function: make-zero LENGTH
Package

bit-ops

Source

package.lisp (file)

Function: op NAME INPUTS OUTPUT
Package

bit-ops

Source

package.lisp (file)

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

bit-ops

Source

package.lisp (file)

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

bit-ops

Source

package.lisp (file)

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

bit-ops

Source

package.lisp (file)

Function: op-p OBJECT
Package

bit-ops

Source

package.lisp (file)

Function: parse-form FORM
Package

bit-ops

Source

package.lisp (file)

Function: reduce-allocation ()
Package

bit-ops

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

bit-ops

Source

package.lisp (file)

Writer

(setf symbol-bitwise-operation) (function)

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

Automatically defined setter function.

Package

bit-ops

Source

package.lisp (file)

Reader

symbol-bitwise-operation (function)


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

6.2.3 Conditions

Condition: unbound-bitwise-operation ()
Package

bit-ops

Source

package.lisp (file)

Direct superclasses

unbound-variable (condition)


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

6.2.4 Structures

Structure: op ()
Package

bit-ops

Source

package.lisp (file)

Direct superclasses

structure-object (structure)

Direct slots
Slot: name
Readers

op-name (function)

Writers

(setf op-name) (function)

Slot: inputs
Readers

op-inputs (function)

Writers

(setf op-inputs) (function)

Slot: output
Readers

op-output (function)

Writers

(setf op-output) (function)


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

6.2.5 Types

Type: bitwise-operation-type ()
Package

bit-ops

Source

package.lisp (file)


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

Appendix A Indexes


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

A.1 Concepts

Jump to:   B   F   L   M  
Index Entry  Section

B
bit-ops.asd: The bit-ops<dot>asd file
bit-ops/src: The bit-ops/src module
bit-ops/src/functions.lisp: The bit-ops/src/functions<dot>lisp file
bit-ops/src/macros.lisp: The bit-ops/src/macros<dot>lisp file
bit-ops/src/package.lisp: The bit-ops/src/package<dot>lisp file

F
File, Lisp, bit-ops.asd: The bit-ops<dot>asd file
File, Lisp, bit-ops/src/functions.lisp: The bit-ops/src/functions<dot>lisp file
File, Lisp, bit-ops/src/macros.lisp: The bit-ops/src/macros<dot>lisp file
File, Lisp, bit-ops/src/package.lisp: The bit-ops/src/package<dot>lisp file

L
Lisp File, bit-ops.asd: The bit-ops<dot>asd file
Lisp File, bit-ops/src/functions.lisp: The bit-ops/src/functions<dot>lisp file
Lisp File, bit-ops/src/macros.lisp: The bit-ops/src/macros<dot>lisp file
Lisp File, bit-ops/src/package.lisp: The bit-ops/src/package<dot>lisp file

M
Module, bit-ops/src: The bit-ops/src module

Jump to:   B   F   L   M  

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

A.2 Functions

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

(
(setf op-inputs): Internal functions
(setf op-name): Internal functions
(setf op-output): Internal functions
(setf symbol-bitwise-operation): Internal functions

A
as-bitwise-operations: Exported macros

B
bit-if-then-else: Exported functions
bit-implies: Exported functions
bit-replace: Internal functions
bitwise-operation-boundp: Internal functions
build-forms: Internal functions

C
common-subexpression: Internal functions
compile-bitwise-operations: Internal functions
copy-op: Internal functions

D
define-bitwise-operation: Exported macros
dlet: Exported macros
dlet*: Exported macros

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

M
Macro, as-bitwise-operations: Exported macros
Macro, define-bitwise-operation: Exported macros
Macro, dlet: Exported macros
Macro, dlet*: Exported macros
make-bit-vector: Exported functions
make-one: Internal functions
make-op: Internal functions
make-zero: Internal functions

O
op: Internal functions
op-inputs: Internal functions
op-name: Internal functions
op-output: Internal functions
op-p: Internal functions

P
parse-form: Internal functions

R
reduce-allocation: Internal functions

S
symbol-bitwise-operation: Internal functions

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

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

A.3 Variables

Jump to:   *  
I   N   O   S  
Index Entry  Section

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

I
inputs: Internal structures

N
name: Internal structures

O
output: Internal structures

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

Jump to:   *  
I   N   O   S  

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

A.4 Data types

Jump to:   B   C   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
bitwise-operation-type: Internal types

C
Condition, unbound-bitwise-operation: Internal conditions

O
op: Internal structures

P
Package, bit-ops: The bit-ops package
Package, bit-ops-asd: The bit-ops-asd package

S
Structure, op: Internal structures
System, bit-ops: The bit-ops system

T
Type, bitwise-operation-type: Internal types

U
unbound-bitwise-operation: Internal conditions

Jump to:   B   C   O   P   S   T   U