Reed Solomon

|PyPI-Status| |PyPI-Versions| |PyPI-Downloads|

|Build-Status| |Coverage|

|Conda-Forge-Status| |Conda-Forge-Platforms| |Conda-Forge-Downloads|

⏳🛡 Pythonic universal errors-and-erasures Reed-Solomon encoder/decoder codec <http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction>_ to protect your data from errors and bitrot. Includes a future-proof zero-dependencies pure-python implementation 🔮 as well as an optional speed-optimized Cython/C extension 🚀

This is a burst-type implementation, so that it supports any Galois field higher than 2^3, but not binary streams. Burst errors are non-random errors that more often happen on data storage mediums such as hard drives, hence this library is better suited for data storage protection, and less for streams noise correction, although it also works for this purpose but with a bit of overhead (since it works with bytes only, instead of bits).

Based on the wonderful tutorial at Wikiversity <http://en.wikiversity.org/wiki/Reed%E2%80%93Solomon_codes_for_coders>_, written by "Bobmath" and "LRQ3000". If you are just starting with Reed-Solomon error correction codes, the Wikiversity article is a good beginner's introduction.

---

.. contents:: Table of contents :backlinks: top :local:

Installation

For the latest stable release (compatible with Python >= 3.7), install with:

.. code:: sh

pip install --upgrade reedsolo

For the latest development release, use:

.. code:: sh

pip install --upgrade reedsolo --pre

For the cutting-edge code (likely unstable, do not use in production!), use:

.. code:: sh

pip install --upgrade git+https://github.com/tomerfiliba-org/reedsolomon

If you have some issues installing through pip, maybe this command may help, by forcing the use of sdist instead of wheels:

.. code:: sh

pip install reedsolo --no-binary="reedsolo" --no-cache

Note: for Python 2.7 and Python <= 3.6, please use v1.7.0:

.. code:: sh

pip install --upgrade reedsolo==1.7.0

Through wheels/pip, a pure-python implementation called reedsolo is installed, and for platforms supported by cibuildwheel, a precompiled speed-optimized creedsolo module is included. For other platforms or to compile from source (this requires cython>=3.0.0b2 and a C compiler), a build option can be specified:

.. code:: sh

# To compile from the latest stable release:
pip install --upgrade reedsolo --no-binary "reedsolo" --no-cache --config-setting="--build-option=--cythonize" --use-pep517 --isolated --verbose
# To compile from the latest development release:
pip install --upgrade reedsolo --no-binary "reedsolo" --no-cache --config-setting="--build-option=--cythonize" --use-pep517 --isolated --pre --verbose
# To compile from the cutting edge code:
pip install --upgrade "reedsolo @ git+https://github.com/tomerfiliba-org/reedsolomon" --no-binary "reedsolo" --no-cache --config-setting="--build-option=--cythonize" --use-pep517 --isolated --pre --verbose

The --config-setting="--build-option=--cythonize" flag signals to the setuptools backend to propagate to reedsolo's setup.py to build the optional cythonized extension. The --no-binary "reedsolo" and --no-cache options are necessary since pip 23.1 <https://github.com/pypa/pip/issues/11453#issuecomment-1523964029>__ to force the use of the sdist instead of wheels.

or locally with:

.. code:: sh

pip install --upgrade . --config-setting="--build-option=--cythonize" --verbose

Note: for development, it's possible to add the --editable flag to use the local folder without installing in site-packages, and use .[test] instead of . to install all required packages to test this module locally.

The package for the development or cutting-edge releases can also be built locally with the pep517 compliant build tool:

.. code:: sh

pip install build
# With cythonization (from *.pyx to *.c to *.pyd)
python -sBm build --config-setting="--build-option=--cythonize"
# or skip cythonization and only compile from the already transpiled c extension (from *.c to *.pyd)
python -sBm build --config-setting="--build-option=--native-compile"

The setup.py will then try to build the Cython optimized module creedsolo.pyx if Cython is installed, which can then be imported as import creedsolo instead of import reedsolo, with the same features between both modules. Note: Make sure to use --config-setting singular, because build does not (yet <https://github.com/pypa/build/issues/608>__) recognize the plural form contrary to pip.

As an alternative, use conda <https://docs.conda.io/en/latest/>_ to install a compiled version for various platforms:

.. code:: sh

conda install -c conda-forge reedsolo

Various Linux distributions builds are also available, thanks to a network of amazing maintainers:

|dl-gentoo| |dl-debian| |dl-fedora| |dl-archlinux| |dl-alpine| |dl-altlinux| |dl-linux-others|

Usage

Basic usage with high-level RSCodec class

::

    # Initialization
    >>> from reedsolo import RSCodec, ReedSolomonError
    >>> rsc = RSCodec(10)  # 10 ecc symbols

    # Encoding
    # just a list of numbers/symbols:
    >>> rsc.encode([1,2,3,4])
    b'\x01\x02\x03\x04,\x9d\x1c+=\xf8h\xfa\x98M'
    # bytearrays are accepted and the output will be matched:
    >>> rsc.encode(bytearray([1,2,3,4]))
    bytearray(b'\x01\x02\x03\x04,\x9d\x1c+=\xf8h\xfa\x98M')
    # encoding a byte string is as easy:
    >>> rsc.encode(b'hello world')
    b'hello world\xed%T\xc4\xfd\xfd\x89\xf3\xa8\xaa'

Note: strings of any length, even if longer than the Galois field, will be encoded as well using transparent chunking.

Note2: it is strongly recommended to always use bytearrays. Using encoded strings is accepted by the RSCodec API, as
a convenient facility for neophytes, but encodings such as ``UTF-8`` have variable lengths, so internally the module has
to convert to a bytearray. If you just want to protect a string, you do not need to use a ``bytearray``, but if you need
to store or send the protected data in a fixed size field, such as in a binary file or a data stream, use a ``bytearray``.

::

    # Decoding (repairing)
    >>> rsc.decode(b'hello world\xed%T\xc4\xfd\xfd\x89\xf3\xa8\xaa')[0]  # original
    b'hello world'
    >>> rsc.decode(b'heXlo worXd\xed%T\xc4\xfdX\x89\xf3\xa8\xaa')[0]     # 3 errors
    b'hello world'
    >>> rsc.decode(b'hXXXo worXd\xed%T\xc4\xfdX\x89\xf3\xa8\xaa')[0]     # 5 errors
    b'hello world'
    >>> rsc.decode(b'hXXXo worXd\xed%T\xc4\xfdXX\xf3\xa8\xaa')[0]        # 6 errors - fail
    Traceback (most recent call last):
    ...
    reedsolo.ReedSolomonError: Too many (or few) errors found by Chien Search for the errata locator polynomial!

**Important upgrade notice for pre-1.0 users:** Note that ``RSCodec.decode()`` returns 3 variables:

    1. the decoded (corrected) message
    2. the decoded message and error correction code (which is itself also corrected)
    3. and the list of positions of the errata (errors and erasures)

Here is how to use these outputs:

::

    >>> tampered_msg = b'heXlo worXd\xed%T\xc4\xfdX\x89\xf3\xa8\xaa'
    >>> decoded_msg, decoded_msgecc, errata_pos = rsc.decode(tampered_msg)
    >>> print(decoded_msg)  # decoded/corrected message
    bytearray(b'hello world')
    >>> print(decoded_msgecc)  # decoded/corrected message and ecc symbols
    bytearray(b'hello world\xed%T\xc4\xfd\xfd\x89\xf3\xa8\xaa')
    >>> print(errata_pos)  # errata_pos is returned as a bytearray, hardly intelligible
    bytearray(b'\x10\t\x02')
    >>> print(list(errata_pos))  # convert to a list to get the errata positions as integer indices
    [16, 9, 2]

Since we failed to decode with 6 errors with a codec set with 10 error correction code (ecc) symbols, let's try to use a bigger codec, with 12 ecc symbols.

::

    >>> rsc = RSCodec(12)  # using 2 more ecc symbols (to correct max 6 errors or 12 erasures)
    >>> rsc.encode(b'hello world')
    b'hello world?Ay\xb2\xbc\xdc\x01q\xb9\xe3\xe2='
    >>> rsc.decode(b'hello worXXXXy\xb2XX\x01q\xb9\xe3\xe2=')[0]         # 6 errors - ok, but any more would fail
    b'hello world'
    >>> rsc.decode(b'helXXXXXXXXXXy\xb2XX\x01q\xb9\xe3\xe2=', erase_pos=[3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 15, 16])[0]  # 12 erasures - OK
    b'hello world'

This shows that we can decode twice as many erasures (where we provide the location of errors ourselves) than errors (with unknown locations). This is the cost of error correction compared to erasure correction.

To get the maximum number of errors *or* erasures that can be independently corrected (ie, not simultaneously):

::

    >>> maxerrors, maxerasures = rsc.maxerrata(verbose=True)
    This codec can correct up to 6 errors and 12 erasures independently
    >>> print(maxerrors, maxerasures)
    6 12

To get the maximum number of errors *and* erasures that can be simultaneously corrected, you need to specify the number of errors or erasures you expect:

::

    >>> maxerrors, maxerasures = rsc.maxerrata(erasures=6, verbose=True)  # we know the number of erasures, will calculate how many errors we can afford
    This codec can correct up to 3 errors and 6 erasures simultaneously
    >>> print(maxerrors, maxerasures)
    3 6
    >>> maxerrors, maxerasures = rsc.maxerrata(errors=5, verbose=True)  # we know the number of errors, will calculate how many erasures we can afford
    This codec can correct up to 5 errors and 2 erasures simultaneously
    >>> print(maxerrors, maxerasures)
    5 2

Note that if a chunk has more errors and erasures than the Singleton Bound as calculated by the ``maxerrata()`` method, the codec will try to raise a ``ReedSolomonError`` exception,
but may very well not detect any error either (this is a theoretical limitation of error correction codes). In other words, error correction codes are unreliable to detect if a chunk of a message
is corrupted beyond the Singleton Bound. If you want more reliability in errata detection, use a checksum or hash such as SHA or MD5 on your message, these are much more reliable and have no bounds
on the number of errata (the only potential issue is with collision but the probability is very very low).

Note: to catch a ``ReedSolomonError`` exception, do not forget to import it first with: ``from reedsolo import ReedSolomonError``

To check if a message is tampered given its error correction symbols, without decoding, use the ``check()`` method:

::

    # Checking
    >> rsc.check(b'hello worXXXXy\xb2XX\x01q\xb9\xe3\xe2=')  # Tampered message will return False
    [False]
    >> rmes, rmesecc, errata_pos = rsc.decode(b'hello worXXXXy\xb2XX\x01q\xb9\xe3\xe2=')
    >> rsc.check(rmesecc)  # Corrected or untampered message will return True
    [True]
    >> print('Number of detected errors and erasures: %i, their positions: %s' % (len(errata_pos), list(errata_pos)))
    Number of detected errors and erasures: 6, their positions: [16, 15, 12, 11, 10, 9]

By default, most Reed-Solomon codecs are limited to characters that can be encoded in 256 bits and with a length of maximum 256 characters. But this codec is universal, you can reduce or increase the length and maximum character value by increasing the Galois Field:

::

    # To use longer chunks or bigger values than 255 (may be very slow)
    >> rsc = RSCodec(12, nsize=4095)  # always use a power of 2 minus 1
    >> rsc = RSCodec(12, c_exp=12)  # alternative way to set nsize=4095
    >> mes = 'a' * (4095-12)
    >> mesecc = rsc.encode(mes)
    >> mesecc[2] = 1
    >> mesecc[-1] = 1
    >> rmes, rmesecc, errata_pos = rsc.decode(mesecc)
    >> rsc.check(mesecc)
    [False]
    >> rsc.check(rmesecc)
    [True]

Note that the ``RSCodec`` class supports transparent chunking, so you don't need to increase the Galois Field to support longer messa