libcimbar Documentation

Optimized implementation for color-icon-matrix barcodes

5,986 stars C++ C++ 1 file · ~8,778 tokens #barcode#cpp17#fountain-codes#image-hash#opencv
RAW Doc

File: README.md

[INTRODUCTION](https://github.com/sz3/cimbar) | [ABOUT](https://github.com/sz3/cimbar/blob/master/ABOUT.md) | [CFC](https://github.com/sz3/cfc) | LIBCIMBAR

[DETAILS](DETAILS.md) | [PERFORMANCE](PERFORMANCE.md) | [TODO](TODO.md)

libcimbar: Color Icon Matrix Barcodes

Behold: an experimental barcode format for air-gapped data transfer.

It can sustain speeds of 850 kilobits/s (~106 KB/s) using just a computer monitor and a smartphone camera!

Explain?

The encoder outputs an animated barcode to a computer or smartphone screen:

While the decoder is a cell phone app that uses the phone camera to read the animated barcode:

No internet/bluetooth/NFC/etc is used. All data is transmitted through the camera lens. You can try it out yourself, or take my word that it works. :)

How does it work?

cimbar is a high-density 2D barcode format. Data is stored in a grid of colored tiles -- bits are encoded based on which tile is chosen, and which color is chosen to draw the tile. Reed Solomon error correction is applied on the data, to account for the lossy nature of the video -> digital decoding. Sub-1% error rates are expected, and corrected.

libcimbar, this optimized implementation, includes a simple protocol for file encoding built on fountain codes (wirehair) and zstd compression. Files of up to 33MB (after compression!) are encoded in a series of cimbar codes, which can be output as images or a live video feed. Once enough distinct image frames have been decoded successfully, the file will be reconstructed and decompressed successfully. This is true even if the images are received out of order, or if some have been corrupted or are missing.

Platforms

The code is written in C++, and developed/tested on amd64+linux, arm64+android (decoder only), and emscripten+WASM (encoder only). It probably works, or can be made to work, on other platforms.

Crucially, because the encoder compiles to asmjs and wasm, it can run on anything with a modern web browser. For offline use, you can either install cimbar.org as a progressive web app, or download the latest release of cimbar_js.html, save it locally, and open it in your web browser.

Library dependencies

OpenCV and GLFW (+ OpenGL ES headers) must be installed before building. All other dependencies are included in the source tree.

Build (linux dev)

  1. install opencv and GLFW. On ubuntu/debian, this looks like:
text
sudo apt install libopencv-dev libglfw3-dev libgles2-mesa-dev
  1. run the cmake + make incantation
text
cmake .
make -j7
make install

By default, libcimbar will try to install build products under ./dist/bin/.

Build (windows MSVC + vcpkg)

Install Visual Studio with the Desktop development with C++ workload, CMake 3.14 or newer, and vcpkg. Set VCPKG_ROOT to the vcpkg checkout, then configure and build from PowerShell:

text
cmake -S . -B build-windows -A x64 "-DCMAKE_TOOLCHAIN_FILE=$env:VCPKG_ROOT/scripts/buildsystems/vcpkg.cmake"
cmake --build build-windows --config Release --target cimbar_send cimbar_recv cimbar_recv2 --parallel
cmake --install build-windows --config Release

The included vcpkg.json installs OpenCV, GLFW, and ANGLE during configuration. The executables and their runtime DLLs are installed under ./dist/bin/.

Note: native Windows is supported on a "best efforts" basis, so things may be a bit more buggy. (primary dev is for linux/android)

Build wasm (cimbar.js)

To build cimbar.js (what cimbar.org uses), see WASM. Or use the latest release.

Usage

Encode:

  • large input files may fill up your disk with pngs!
text
./cimbar --encode -i inputfile.txt -o outputprefix

Decode (extracts file into output directory):

text
./cimbar outputprefix*.png -o /tmp

Decode a series of encoded images from stdin:

text
echo outputprefix*.png | ./cimbar -o /tmp

Encode and animate to window:

text
./cimbar_send inputfile.pdf

You can also encode a file using cimbar.org, or the latest release.

Performance numbers

PERFORMANCE

Implementation details

DETAILS

Room for improvement/next steps

TODO

Community Tools

  • cimbar-bigfile — A pure-frontend wrapper that splits files into multiple parallel encode_id streams (10–15 MB chunks per stream), and ships a manifest.json for SHA256-verified reassembly. Supports 100+ MB files. No changes to libcimbar or cfc required.

Inspiration

Would you like to know more?

[INTRODUCTION](https://github.com/sz3/cimbar) | [ABOUT](https://github.com/sz3/cimbar/blob/master/ABOUT.md)

File: src/third_party_lib/zstd/README.md

Zstandard library files

The lib directory is split into several sub-directories,
in order to make it easier to select or exclude features.

Building

Makefile script is provided, supporting Makefile conventions,
including commands variables, staged install, directory variables and standard targets.

  • make : generates both static and dynamic libraries
  • make install : install libraries and headers in target system directories

libzstd default scope is pretty large, including compression, decompression, dictionary builder,
and support for decoding legacy formats >= v0.5.0.
The scope can be reduced on demand (see paragraph modular build).

Multithreading support

When building with make, by default the dynamic library is multithreaded and static library is single-threaded (for compatibility reasons).

Enabling multithreading requires 2 conditions :

  • set build macro ZSTD_MULTITHREAD (-DZSTD_MULTITHREAD for gcc)
  • for POSIX systems : compile with pthread (-pthread compilation flag for gcc)

For convenience, we provide a build target to generate multi and single threaded libraries:

  • Force enable multithreading on both dynamic and static libraries by appending -mt to the target, e.g. make lib-mt.
  • Force disable multithreading on both dynamic and static libraries by appending -nomt to the target, e.g. make lib-nomt.
  • By default, as mentioned before, dynamic library is multithreaded, and static library is single-threaded, e.g. make lib.

When linking a POSIX program with a multithreaded version of libzstd,
note that it's necessary to invoke the -pthread flag during link stage.

Multithreading capabilities are exposed
via the advanced API defined in lib/zstd.h.

API

Zstandard's stable API is exposed within lib/zstd.h.

Advanced API

Optional advanced features are exposed via :

  • lib/zstd_errors.h : translates size_t function results
    into a ZSTD_ErrorCode, for accurate error handling.

  • ZSTD_STATIC_LINKING_ONLY : if this macro is defined before including zstd.h,
    it unlocks access to the experimental API,
    exposed in the second part of zstd.h.
    All definitions in the experimental APIs are unstable,
    they may still change in the future, or even be removed.
    As a consequence, experimental definitions shall never be used with dynamic library !
    Only static linking is allowed.

Modular build

It's possible to compile only a limited set of features within libzstd.
The file structure is designed to make this selection manually achievable for any build system :

  • Directory lib/common is always required, for all variants.

  • Compression source code lies in lib/compress

  • Decompression source code lies in lib/decompress

  • It's possible to include only compress or only decompress, they don't depend on each other.

  • lib/dictBuilder : makes it possible to generate dictionaries from a set of samples.
    The API is exposed in lib/dictBuilder/zdict.h.
    This module depends on both lib/common and lib/compress .

  • lib/legacy : makes it possible to decompress legacy zstd formats, starting from v0.1.0.
    This module depends on lib/common and lib/decompress.
    To enable this feature, define ZSTD_LEGACY_SUPPORT during compilation.
    Specifying a number limits versions supported to that version onward.
    For example, ZSTD_LEGACY_SUPPORT=2 means : "support legacy formats >= v0.2.0".
    Conversely, ZSTD_LEGACY_SUPPORT=0 means "do not support legacy formats".
    By default, this build macro is set as ZSTD_LEGACY_SUPPORT=5.
    Decoding supported legacy format is a transparent capability triggered within decompression functions.
    It's also allowed to invoke legacy API directly, exposed in lib/legacy/zstd_legacy.h.
    Each version does also provide its own set of advanced API.
    For example, advanced API for version v0.4 is exposed in lib/legacy/zstd_v04.h .

  • While invoking make libzstd, it's possible to define build macros
    ZSTD_LIB_COMPRESSION, ZSTD_LIB_DECOMPRESSION, ZSTD_LIB_DICTBUILDER,
    and ZSTD_LIB_DEPRECATED as 0 to forgo compilation of the
    corresponding features. This will also disable compilation of all
    dependencies (e.g. ZSTD_LIB_COMPRESSION=0 will also disable
    dictBuilder).

  • There are a number of options that can help minimize the binary size of
    libzstd.

    The first step is to select the components needed (using the above-described
    ZSTD_LIB_COMPRESSION etc.).

    The next step is to set ZSTD_LIB_MINIFY to 1 when invoking make. This
    disables various optional components and changes the compilation flags to
    prioritize space-saving.

    Detailed options: Zstandard's code and build environment is set up by default
    to optimize above all else for performance. In pursuit of this goal, Zstandard
    makes significant trade-offs in code size. For example, Zstandard often has
    more than one implementation of a particular component, with each
    implementation optimized for different scenarios. For example, the Huffman
    decoder has complementary implementations that decode the stream one symbol at
    a time or two symbols at a time. Zstd normally includes both (and dispatches
    between them at runtime), but by defining HUF_FORCE_DECOMPRESS_X1 or
    HUF_FORCE_DECOMPRESS_X2, you can force the use of one or the other, avoiding
    compilation of the other. Similarly, ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT
    and ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG force the compilation and use of
    only one or the other of two decompression implementations. The smallest
    binary is achieved by using HUF_FORCE_DECOMPRESS_X1 and
    ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT (implied by ZSTD_LIB_MINIFY).

    For squeezing the last ounce of size out, you can also define
    ZSTD_NO_INLINE, which disables inlining, and ZSTD_STRIP_ERROR_STRINGS,
    which removes the error messages that are otherwise returned by
    ZSTD_getErrorName (implied by ZSTD_LIB_MINIFY).

    Finally, when integrating into your application, make sure you're doing link-
    time optimization and unused symbol garbage collection (via some combination of,
    e.g., -flto, -ffat-lto-objects, -fuse-linker-plugin,
    -ffunction-sections, -fdata-sections, -fmerge-all-constants,
    -Wl,--gc-sections, -Wl,-z,norelro, and an archiver that understands
    the compiler's intermediate representation, e.g., AR=gcc-ar). Consult your
    compiler's documentation.

  • While invoking make libzstd, the build macro ZSTD_LEGACY_MULTITHREADED_API=1
    will expose the deprecated ZSTDMT API exposed by zstdmt_compress.h in
    the shared library, which is now hidden by default.

  • The build macro DYNAMIC_BMI2 can be set to 1 or 0 in order to generate binaries
    which can detect at runtime the presence of BMI2 instructions, and use them only if present.
    These instructions contribute to better performance, notably on the decoder side.
    By default, this feature is automatically enabled on detecting
    the right instruction set (x64) and compiler (clang or gcc >= 5).
    It's obviously disabled for different cpus,
    or when BMI2 instruction set is required by the compiler command line
    (in this case, only the BMI2 code path is generated).
    Setting this macro will either force to generate the BMI2 dispatcher (1)
    or prevent it (0). It overrides automatic detection.

  • The build macro ZSTD_NO_UNUSED_FUNCTIONS can be defined to hide the definitions of functions
    that zstd does not use. Not all unused functions are hidden, but they can be if needed.
    Currently, this macro will hide function definitions in FSE and HUF that use an excessive
    amount of stack space.

  • The build macro ZSTD_NO_INTRINSICS can be defined to disable all explicit intrinsics.
    Compiler builtins are still used.

  • The build macro ZSTD_DECODER_INTERNAL_BUFFER can be set to control
    the amount of extra memory used during decompression to store literals.
    This defaults to 64kB. Reducing this value reduces the memory footprint of
    ZSTD_DCtx decompression contexts,
    but might also result in a small decompression speed cost.

  • The C compiler macros ZSTDLIB_VISIBLE, ZSTDERRORLIB_VISIBLE and ZDICTLIB_VISIBLE
    can be overridden to control the visibility of zstd's API. Additionally,
    ZSTDLIB_STATIC_API and ZDICTLIB_STATIC_API can be overridden to control the visibility
    of zstd's static API. Specifically, it can be set to ZSTDLIB_HIDDEN to hide the symbols
    from the shared library. These macros default to ZSTDLIB_VISIBILITY,
    ZSTDERRORLIB_VSIBILITY, and ZDICTLIB_VISIBILITY if unset, for backwards compatibility
    with the old macro names.

Windows : using MinGW+MSYS to create DLL

DLL can be created using MinGW+MSYS with the make libzstd command.
This command creates dll\libzstd.dll and the import library dll\libzstd.lib.
The import library is only required with Visual C++.
The header file zstd.h and the dynamic library dll\libzstd.dll are required to
compile a project using gcc/MinGW.
The dynamic library has to be added to linking options.
It means that if a project that uses ZSTD consists of a single test-dll.c
file it should be linked with dll\libzstd.dll. For example:

text
gcc $(CFLAGS) -Iinclude/ test-dll.c -o test-dll dll\libzstd.dll

The compiled executable will require ZSTD DLL which is available at dll\libzstd.dll.

Advanced Build options

The build system requires a hash function in order to
separate object files created with different compilation flags.
By default, it tries to use md5sum or equivalent.
The hash function can be manually switched by setting the HASH variable.
For example : make HASH=xxhsum
The hash function needs to generate at least 64-bit using hexadecimal format.
When no hash function is found,
the Makefile just generates all object files into the same default directory,
irrespective of compilation flags.
This functionality only matters if libzstd is compiled multiple times
with different build flags.

The build directory, where object files are stored
can also be manually controlled using variable BUILD_DIR,
for example make BUILD_DIR=objectDir/v1.
In which case, the hash function doesn't matter.

Deprecated API

Obsolete API on their way out are stored in directory lib/deprecated.
At this stage, it contains older streaming prototypes, in lib/deprecated/zbuff.h.
These prototypes will be removed in some future version.
Consider migrating code towards supported streaming API exposed in zstd.h.

Miscellaneous

The other files are not source code. There are :

  • BUCK : support for buck build system (https://buckbuild.com/)
  • Makefile : make script to build and install zstd library (static and dynamic)
  • README.md : this file
  • dll/ : resources directory for Windows compilation
  • libzstd.pc.in : script for pkg-config (used in make install)

File: src/third_party_lib/wirehair/README.md

Wirehair

Fast and Portable Fountain Codes in C

Wirehair produces a stream of error correction blocks from a data source
using an erasure code. When enough of these blocks are received,
the original data can be recovered.

As compared to other similar libraries, an unlimited number of error
correction blocks can be produced, and much larger block counts are supported.
Furthermore, it gets slower as O(N) in the amount of input data rather
than O(N Log N) like the Leopard block code or O(N^2) like the Fecal fountain code,
so it is well-suited for large data.

This is not an ideal MDS code, so sometimes it will fail to recover N
original data packets from N symbol packets. It may take N + 1 or N + 2 or more.
On average it takes about N + 0.02 packets to recover. Overall the overhead
from the code inefficiency is low, compared to LDPC and many other fountain codes.

A simple C API is provided to make it easy to incorporate into existing
projects. No external dependencies are required.

Building: Quick Setup

The source code in this folder (gf256 and wirehair code) can be incorporated
into your project without any other external dependencies.

To build the software in this repo:

On Windows, make sure CMake and Git Bash are installed. Open up git bash and then:

text
git clone [email protected]:catid/wirehair.git
cd wirehair
mkdir build
cd build
cmake .. -G "Visual Studio 16 2019"
ls
explorer .

Then you can use Visual Studio Community Edition to open up the wirehair.sln file and build the software.

Example Usage

Here's an example program using Wirehair. It's included in the UnitTest project and demonstrates both the sender and receiver, which are normally separate programs. For example the data sender might be a file server and the data receiver might be downloading a file from the sender.

text
#include <wirehair/wirehair.h>

static bool ReadmeExample()
{
    // Size of packets to produce
    static const int kPacketSize = 1400;

    // Note: Does not need to be an even multiple of packet size or 16 etc
    static const int kMessageBytes = 1000 * 1000 + 333;

    vector message(kMessageBytes);

    // Fill message contents
    memset(&message[0], 1, message.size());

    // Create encoder
    WirehairCodec encoder = wirehair_encoder_create(nullptr, &message[0], kMessageBytes, kPacketSize);
    if (!encoder)
    {
        cout << "!!! Failed to create encoder" << endl;
        return false;
    }

    // Create decoder
    WirehairCodec decoder = wirehair_decoder_create(nullptr, kMessageBytes, kPacketSize);
    if (!decoder)
    {
        // Free memory for encoder
        wirehair_free(encoder);

        cout << "!!! Failed to create decoder" << endl;
        return false;
    }

    unsigned blockId = 0, needed = 0;

    for (;;)
    {
        // Select which block to encode.
        // Note: First N blocks are the original data, so it's possible to start
        // sending data while wirehair_encoder_create() is getting started.
        blockId++;

        // Simulate 10% packetloss
        if (blockId % 10 == 0) {
            continue;
        }

        // Keep track of how many pieces were needed
        ++needed;

        vector block(kPacketSize);

        // Encode a packet
        uint32_t writeLen = 0;
        WirehairResult encodeResult = wirehair_encode(
            encoder, // Encoder object
            blockId, // ID of block to generate
            &block[0], // Output buffer
            kPacketSize, // Output buffer size
            &writeLen); // Returned block length

        if (encodeResult != Wirehair_Success)
        {
            cout << "wirehair_encode failed: " << encodeResult << endl;
            return false;
        }

        // Attempt decode
        WirehairResult decodeResult = wirehair_decode(
            decoder, // Decoder object
            blockId, // ID of block that was encoded
            &block[0], // Input block
            writeLen); // Block length

        // If decoder returns success:
        if (decodeResult == Wirehair_Success) {
            // Decoder has enough data to recover now
            break;
        }

        if (decodeResult != Wirehair_NeedMore)
        {
            cout << "wirehair_decode failed: " << decodeResult << endl;
            return false;
        }
    }

    vector decoded(kMessageBytes);

    // Recover original data on decoder side
    WirehairResult decodeResult = wirehair_recover(
        decoder,
        &decoded[0],
        kMessageBytes);

    if (decodeResult != Wirehair_Success)
    {
        cout << "wirehair_recover failed: " << decodeResult << endl;
        return false;
    }

    // Free memory for encoder and decoder
    wirehair_free(encoder);
    wirehair_free(decoder);

    return true;
}

int main()
{
    const WirehairResult initResult = wirehair_init();

    if (initResult != Wirehair_Success)
    {
        SIAMESE_DEBUG_BREAK();
        cout << "!!! Wirehair initialization failed: " << initResult << endl;
        return -1;
    }

    if (!ReadmeExample())
    {
        SIAMESE_DEBUG_BREAK();
        cout << "!!! Example usage failed" << endl;
        return -2;
    }
...

Benchmarks

Some quick comments:

Benchmarks on my PC do not mean a whole lot. Right now it's clocked at 3 GHz and has Turbo Boost on, etc.
To run the test yourself just build and run the UnitTest project in Release mode.

For small values of N < 128 or so this is a pretty inefficient codec compared to the Fecal codec. Fecal is also a fountain code but is limited to repairing a small number of failures or small input block count.

text
For N = 2 packets of 1300 bytes:
+ Average wirehair_encoder_create() time: 11 usec (236.364 MBPS)
+ Average wirehair_encode() time: 0 usec (7435.7 MBPS)
+ Average wirehair_decode() time: 2 usec (476.205 MBPS)
+ Average overhead piece count beyond N = 0.0105
+ Average wirehair_recover() time: 0 usec (9319 MBPS)

For N = 4 packets of 1300 bytes:
+ Average wirehair_encoder_create() time: 8 usec (650 MBPS)
+ Average wirehair_encode() time: 0 usec (8353.43 MBPS)
+ Average wirehair_decode() time: 1 usec (695.102 MBPS)
+ Average overhead piece count beyond N = 0.0225
+ Average wirehair_recover() time: 0 usec (11219 MBPS)

For N = 8 packets of 1300 bytes:
+ Average wirehair_encoder_create() time: 13 usec (800 MBPS)
+ Average wirehair_encode() time: 0 usec (7916.2 MBPS)
+ Average wirehair_decode() time: 1 usec (704.359 MBPS)
+ Average overhead piece count beyond N = 0.0045
+ Average wirehair_recover() time: 1 usec (8973.25 MBPS)

For N = 16 packets of 1300 bytes:
+ Average wirehair_encoder_create() time: 27 usec (770.37 MBPS)
+ Average wirehair_encode() time: 0 usec (7993.4 MBPS)
+ Average wirehair_decode() time: 1 usec (707.211 MBPS)
+ Average overhead piece count beyond N = 0.036
+ Average wirehair_recover() time: 2 usec (9116.81 MBPS)

For N = 32 packets of 1300 bytes:
+ Average wirehair_encoder_create() time: 41 usec (1014.63 MBPS)
+ Average wirehair_encode() time: 0 usec (7062.93 MBPS)
+ Average wirehair_decode() time: 1 usec (908.097 MBPS)
+ Average overhead piece count beyond N = 0.0195
+ Average wirehair_recover() time: 5 usec (8057.33 MBPS)

For N = 64 packets of 1300 bytes:
+ Average wirehair_encoder_create() time: 81 usec (1027.16 MBPS)
+ Average wirehair_encode() time: 0 usec (7159.51 MBPS)
+ Average wirehair_decode() time: 1 usec (1033.95 MBPS)
+ Average overhead piece count beyond N = 0.017
+ Average wirehair_recover() time: 10 usec (7640.74 MBPS)

For N = 128 packets of 1300 bytes:
+ Average wirehair_encoder_create() time: 192 usec (866.667 MBPS)
+ Average wirehair_encode() time: 0 usec (5662.07 MBPS)
+ Average wirehair_decode() time: 1 usec (870.14 MBPS)
+ Average overhead piece count beyond N = 0.015
+ Average wirehair_recover() time: 25 usec (6419.38 MBPS)

For N = 256 packets of 1300 bytes:
+ Average wirehair_encoder_create() time: 319 usec (1043.26 MBPS)
+ Average wirehair_encode() time: 0 usec (6333.2 MBPS)
+ Average wirehair_decode() time: 1 usec (1018.77 MBPS)
+ Average overhead piece count beyond N = 0.022
+ Average wirehair_recover() time: 50 usec (6602.26 MBPS)

For N = 512 packets of 1300 bytes:
+ Average wirehair_encoder_create() time: 670 usec (993.433 MBPS)
+ Average wirehair_encode() time: 0 usec (6483.91 MBPS)
+ Average wirehair_decode() time: 1 usec (1028.85 MBPS)
+ Average overhead piece count beyond N = 0.022
+ Average wirehair_recover() time: 100 usec (6600.1 MBPS)

For N = 1024 packets of 1300 bytes:
+ Average wirehair_encoder_create() time: 1697 usec (784.443 MBPS)
+ Average wirehair_encode() time: 0 usec (5309.05 MBPS)
+ Average wirehair_decode() time: 1 usec (671.005 MBPS)
+ Average overhead piece count beyond N = 0.022
+ Average wirehair_recover() time: 207 usec (6404.05 MBPS)

For N = 2048 packets of 1300 bytes:
+ Average wirehair_encoder_create() time: 3227 usec (825.039 MBPS)
+ Average wirehair_encode() time: 0 usec (5202.3 MBPS)
+ Average wirehair_decode() time: 1 usec (683.141 MBPS)
+ Average overhead piece count beyond N = 0.021
+ Average wirehair_recover() time: 441 usec (6026.08 MBPS)

For N = 4096 packets of 1300 bytes:
+ Average wirehair_encoder_create() time: 7614 usec (699.343 MBPS)
+ Average wirehair_encode() time: 0 usec (4334.08 MBPS)
+ Average wirehair_decode() time: 2 usec (577.674 MBPS)
+ Average overhead piece count beyond N = 0.0215
+ Average wirehair_recover() time: 1208 usec (4405.65 MBPS)

For N = 8192 packets of 1300 bytes:
+ Average wirehair_encoder_create() time: 17208 usec (618.875 MBPS)
+ Average wirehair_encode() time: 0 usec (3277.17 MBPS)
+ Average wirehair_decode() time: 2 usec (521.665 MBPS)
+ Average overhead piece count beyond N = 0.075
+ Average wirehair_recover() time: 2916 usec (3651.35 MBPS)

For N = 16384 packets of 1300 bytes:
+ Average wirehair_encoder_create() time: 42512 usec (501.016 MBPS)
+ Average wirehair_encode() time: 0 usec (2646.89 MBPS)
+ Average wirehair_decode() time: 2 usec (435.173 MBPS)
+ Average overhead piece count beyond N = 0.015
+ Average wirehair_recover() time: 7282 usec (2924.63 MBPS)

For N = 32768 packets of 1300 bytes:
+ Average wirehair_encoder_create() time: 111287 usec (382.78 MBPS)
+ Average wirehair_encode() time: 0 usec (2378.29 MBPS)
+ Average wirehair_decode() time: 3 usec (342.556 MBPS)
+ Average overhead piece count beyond N = 0.0195
+ Average wirehair_recover() time: 16326 usec (2609.23 MBPS)

Credits

Software by Christopher A. Taylor [email protected]

Please reach out if you need support or would like to collaborate on a project.

File: src/third_party_lib/libcorrect/README.md

[libcorrect](https://github.com/quiet/libcorrect)


libcorrect is a library for Forward Error Correction. By using libcorrect, you can encode extra redundancy into a packet of data and then send it across a lossy channel. When the packet is received, it can be decoded to recover the original, pre-encoded data.

libcorrect accomplishes this task with two algorithms, Convolutional codes and Reed-Solomon. Convolutional codes are robust to a constant background noise, while Reed-Solomon error correction is effective at dealing with noise that occurs in bursts. These algorithms have played an important role in telecommunications. libcorrect uses a Viterbi algorithm decoder to decode convolutional codes.

libcorrect is a performant, BSD-licensed library. It is also the author's hope that this library's contents could help others learn how its algorithms work.

Design goals

  1. libcorrect should be a drop-in, BSD-licensed substitute for libfec, which offers similar functionality under the LGPL-license. Although libfec is a fantastic library, the state of LGPL-licensed libraries on mobile devices is somewhat uncertain. For this reason, libcorrect is a completely new approach under the BSD license which supports the same algorithms as libfec. Additionally, libcorrect can be built with a compatibility layer so that libcorrect can be linked in place of libfec.

    Achieving this goal gives libquiet a fully BSD-/MIT-licensed set of dependencies, which gives libquiet more flexibility in mobile applications.

  2. libcorrect should make it easier to investigate how forward error correction works. To accomplish this, libcorrect provides tools to test the fitness of convolutional codes and their polynomials. Additionally, libcorrect should be written in a way that leads to easy understanding of these powerful algorithms. This library's roadmap includes more documentation on how these algorithms work and how to increase their computational performance.

  3. libcorrect should explore further into error correction. This goal would help libquiet operate in noisier situations. One approach might be to use parts of libcorrect's Viterbi Algorithm decoder to create a Turbo code decoder, although this is just an idea and may turn out to be prohibitively difficult.

Build

libcorrect uses CMake, which allows for out-of-source builds. To get started, make sure that you have CMake installed, and then, from libcorrect's source directory, run mkdir build && cd build && cmake .. && make && make install. Additionally, if you would like the libfec compatibility layer, you can run make shim && make install, though do be cautioned that this can overwrite an existing installation of libfec.

If you are on a host which has <x86intrin.h> available, then libcorrect will automatically build its SSE version as well. The SSE headers are provided under <correct-sse.h>. For now, it is on the caller of this code to ensure that SSE is available and can be used. libcorrect requires SSE functions up to and including SSE4.

If you have any questions or problems with libcorrect, do not hesitate to open an issue.

I'd like to thank Ryan Hitchman and Josh Gao for all of their help and rubber ducking.

A huge thank you goes to Lucas Teske for finding all the ways that libcorrect was broken on Windows and to Denis Golovan for finding an error in the returned length of the convolutional code decoder.

File: README.zh-cn.md

[简介](https://github.com/sz3/cimbar) | [关于](https://github.com/sz3/cimbar/blob/master/ABOUT.md) | [CFC](https://github.com/sz3/cfc) | LIBCIMBAR

[详细内容](DETAILS.md) | [演示](PERFORMANCE.md) | [下一步](TODO.md)

libcimbar: 彩色图形矩阵条形码

一种用于小型数据传输的实验性条形码。

解码速度在 850Kbit/s 左右（约106 KB/s），只需一个电脑显示器和手机摄像头！

为什么？

编码器可以将条形码输出到计算机或手机屏幕：

也可以是一个使用手机摄像头读取条形码的手机APP：

APP并未使用互联网/蓝牙/NFC等，所有数据都是通过摄像头传输的。

原理

cimbar是一种高密度的二维条形码格式。数据存储在彩色图块网格中——根据选择哪个图块和选择哪种颜色来绘制图块，对信息进行编码。对数据应用Reed-Solomon纠错，预计错误率在1%左右。

libcimbar，这是个优化版本，包括一个基于喷泉代码（wirehair）和zstd压缩的简单文件编码协议。最高33MB（压缩后）的文件以一系列 cimbar 代码编码，输出为图像或视频等。一旦成功解码了足够多帧，该文件将被重建和解压缩。即使图像接收出错，或者有些图像已损坏或丢失，也不会有太大问题。

平台

该代码是用C++编写的，并在 amd64+linux、arm64+android（仅限解码器）和 emscripten+WASM（仅限编码器）上开发/测试。在其他平台上应该也可以工作。

至关重要的是，由于编码器编译为 asmjs 和 wasm ，它可以在任何具有现代网络浏览器的设备上运行。对于离线使用，您可以将 cimbar.org 安装为渐进式web应用程序，或下载最新版本。至于 cimbar_js.html ，将其保存在本地，然后在浏览器中打开。

依赖库

OpenCV 和 GLFW (+ OpenGL ES headers) 必须在构建前安装，所有其他依赖项都包含在源代码树中。

构建

  1. 在 Ubuntu/Debian 上安装 opencv 和 GLFW 。如下：
text
sudo apt install libopencv-dev libglfw3-dev libgles2-mesa-dev
  1. 运行 cmake + make
text
cmake .
make -j7
make install

默认情况下，libcimbar 将尝试在 ./dist/bin/ 下安装构建产品。

要构建 cimbar.js（供cimbar.org使用)，请参阅 WASM。

使用

编码：

  • 输入文件太大可能导致硬盘中生成过多图片！
text
./cimbar --encode -i inputfile.txt -o outputprefix

解码（释放文件到输出目录）：

text
./cimbar outputprefix*.png -o /tmp

从stdin解码一系列编码图像：

text
echo outputprefix*.png | ./cimbar -o /tmp

对窗口进行编码并设置动画：

text
./cimbar_send inputfile.pdf

您还可以使用 cimbar.org 对文件进行编码，或最新的 release.

演示

PERFORMANCE

详细信息

DETAILS

下一步

TODO

灵感来源

想了解更多？

[cimbar](https://github.com/sz3/cimbar) | [关于](https://github.com/sz3/cimbar/blob/master/ABOUT.md)

Explore Related Technologies & Topics

View All 9,111+ Repositories →

Discover similar high-velocity repositories, agent skills, and OpenAPI specifications across the ecosystem.

#barcode Browse barcode catalog → #cpp17 Browse cpp17 catalog → #fountain-codes Browse fountain-codes catalog → #image-hash Browse image-hash catalog → #opencv Browse opencv catalog → ⚡ MCP Servers Model Context Protocol → 🧠 Agent Skills Prompt & rule files → 🔌 OpenAPI Specs REST & Swagger schemas →