Weight Distribution Utility
for binary linear codes
with avx2 (haswell new instructions)
and OpenCL GPGPU support


Efficiently counting bits is an interesting software problem, though few applications actually depend on it. One exception is the binary linear code weight distribution function. A program that finds the weight distribution of a binary linear code spends most of its time counting bits. The program blcutil (binary linear code utility) was created to help find what bit counting method is fastest on modern (2012) x86 processors.

The utility uses separately compiled code paths for operations on 256 bits or less, 257-512 bits, and 513-65536 bits. Each of these 3 paths is further divided into 6 algorithms: general purpose register, SSSE3, XMM+popcnt, YMM+popcnt, AVX, and AVX2. One of the 18 separately compiled code paths is chosen based on codeword size, processor type, and command line options. Here are benchmark results comparing the new utility to existing ones. GAP is an open source computational discrete algebra system. Magma is a commercial, closed source computational algebra system. The new utility blcutil is open source. The binary linear code used for this test is the 256-32-96 code returned by Magma's best known binary linear code function. Input files for all 3 programs are included in the blcutil release. Scores are in seconds to complete (smaller is better).


Execution Time in seconds for 256-32-96 Binary Linear Code Weight Distribution
 GAP 4.5.7          MAGMA V2.19-5     BLCUTIL 1.1/CPU      BLCUTIL 1.1/GPU
298                  77.5              1.82                 0.30


  1. Compiler used for blcutil: gcc version 4.7.3 (mingw-w64-bin-x86_64-20121103.7z) from http://www.drangon.org/mingw/. Microsoft Visual Studio 2012 compiler also produces good results. Both executables are included in the release.

  2. Blcutil requires a 64-bit version of Windows. Windows 7 or newer is required for running the AVX and AVX2 functions.

  3. GAP and blcutil were tested on a 4.0 GHz Intel core i7-2600K processor with AMD HD 7850 GPU. Magma scores are from the vendor's public server.




 Revision History

version 1.0   02/18/2013  Initial version.

version 1.1   05/06/2013  Add OpenCL support.

version 1.1a 09/25/2016  Built with no OpenCL support. Removes 64 processor limitation.