-----------------------------------------
CONSTANT TIME IMPLEMENTATION OF BCH CODES
-----------------------------------------


1. OVERVIEW
-----------

This is an implementation of binary BCH codes encoding and decoding [1], with
decoding implemented in constant time. Galois fields GF(2^m) with 2 < m < 16
are supported. Primitive BCH codes are supported as well as shortened BCH codes
built by cutting the first coordinates from a primitive BCH code. Three binaries
can be built: 'generate', 'test_*' and 'time_*'. Binary 'generate' generates
parameter files for a chosen BCH code. Binary 'test_*' does a simple test of
encoding followed by decoding with displays. Binary 'time_*' takes time
measurements in CPU cycles of the decoding process.

Files are organized as follows:
- bin/:          generated binaries
- doc/:          doxygen files
- doc/html/:     documentation generated by doxygen
- inc/:          header files
- inc/lut/:      hardcoded lookup tables
- inc/codes/:    files related to specific BCH codes
- obj/:          object files generated during compilation
- src/:          source code
- Makefile:      makefile


2. INSTALLATION INSTRUCTIONS
----------------------------

2.1 Requirements

The following softwares are required: make and gcc.
A machine supporting the CLMUL (Carry-Less MULtiplication) instruction set is
recommended to profit from all the implemented features.

2.2 Compilation step

Three targets yield binaries:
- generate: builds binary 'generate'.
- lutmul: (LookUp Table MULtiplication) This target outputs two binaries:
  'test_lutmul_PARAM' and 'time_lutmul_PARAM' where the suffix PARAM defines
  the BCH code parameters (see 2.3). Both are compiled using lookup tables
  for Galois field multiplication which is ideal for use on Galois field GF(4096)
  and smaller.
- pclmul: This target also outputs the two binaries 'test_pclmul_PARAM' and
  'time_pclmul_PARAM' where the suffix PARAM defines the BCH code parameters
  (see 2.3) but builds them using the pclmulqdq instruction for Galois field
  multiplication. This is the recommended choice for Galois fields larger
  than GF(4096).
Note that targets lutmul and pclmul both output a third binary
'time_[lutmul|pclmul]_PARAM_once'. This binary is a subprogram of time and
is not meant to be called directly.

2.3 Binaries

- generate: takes two arguments: the parameter m of the Galois field GF(2^m)
  from which the BCH code will be built and a targeted correction capacity t.
  The program computes, if possible, the maximum dimension k, the correction
  capacity delta and the generator polynomial of the BCH code
  (2^m-1, k, delta >= t). It then outputs a directory containing the files
  necessary to compile the sources with this BCH code parameters. Options are
  available to generate a shortened BCH code or to stop at parameter computation
  and not output any files. Use 'generate --help' for more information.
- test_*: takes one argument. 1 is assumed if no argument is given. The program
  generates that many random messages. Each message is encoded, injected with a
  random correctible pattern of errors and decoded. Each decoded message is
  matched against the original and the process stops if a decoding error is
  encountered. Displays are printed at each stage.
- time_*: This binary measures decoding execution time of a BCH code. By default,
  the BCH code (796, 256, 60) is used. To use another code, assuming proper
  files have been generated with the binary 'generate', set variable BCHDIR
  to the path of the directory containing the files. So, for example, to time
  BCH code (1023, 16, 247), run

      make generate
      bin/generate 10 247

  to generate a directory bch_1023_16_247 containing the files for this code.
  Then run
  
      make lutmul BCHDIR=bch_1023_16_247
      bin/time_lutmul_1023_16_247

  to execute measurements.
  Some switches are available. See 'time --help' for more information.
- time_*_once: As stated in section 2.2, this is a subprogram of time and is not
  meant to be used on its own. It performs and times one decoding.
  

3. DOCUMENTATION 
----------------

3.1 Requirements

The following softwares are required: doxygen and bibtex.

3.2 Generation Step

- Run 'make doxygen' to generate the documentation
- Browse doc/html/index.html to read it
Note that not all documented code appears because of preprocessing,
but all code is documented in the source files.


4. ADDITIONAL INFORMATION
-------------------------

4.1 BCH codes decoding

BCH code decoding consists of three steps:
- Syndromes computation
- Error-locator polynomial computation
- Roots computation
Fore more information, see [2].

4.2 Implementation overview

Roots computation is done with an additive Fast Fourier Tranform (FFT) algorithm
by Gao and Mateer [3]. Syndromes computation uses the transpose of the
additive FFT as suggested by Bernstein, Chou and Swchabe in [4]. Galois field
arithmetic is implemented two ways in gf_lutmul.c and gf_pclmul.c, and used
in targets lutmul and pclmul respectively. The main difference is the underlying
implementation of field multiplication (see 2.2).

4.3 Constant time benchmarking

The times (in CPU cycles) output by the binary 'time_*' are obtained as follows.
Firstly, warmup decodings of random words are executed to heat the system.
Secondly, a distribution of error weights to be decoded is generated with a
spread from 0 to 1.1*delta, where delta is the correction capacity of the code.
Then for each of these weights, data sets are generated, that is random
codewords injected with the adequate number of errors. Each codeword is then
decoded multiple times and the minimum of these times is taken as to be the
measured execution time of decoding that codeword. Finally, minimums, means and
maximums of these (minimum) execution times are computed and displayed.
Note that binary 'time_*' does not perform the measures itself. It limits itself
to generating the data sets and calls binary 'time_*_once' to do measurements.
'time_*_once' takes one measurement and is called as many times as necessary by
'time'. This is done to prevent the cache from hiding leaking arrays.

4.4 Exporting the code

In order to use this implementation of BCH codes in another project, eleven
files need to be exported. First, generate the adequate files for the chosen
BCH code with 'generate' (see 2.3). This produces a BCH code parameters file
bch_PARAM.h and a BCH generator polynomial file bch_PARAM_poly.h. Then choose
an implementation of Galois field multiplication by selecting either gf_lutmul.c
or gf_pclmul.c. Add files optimizations.h, gf.h, gf_lut_1024.h, fft.c, fft.h,
fft_lut_1024_64.h, bch.c and bch.h. Lookup tables (files gf_lut_1024.h and
fft_lut_1024_64.h) are unnecessary if a Galois field other than GF(1024) is used
as long as code lines including these files are deleted. As a last step, include
the file bch_PARAM.h in all files requesting it and include the file
bch_PARAM_poly.h in your main.


5. REFERENCES
-------------

[1] Lin, Shu, and D. Costello. "Error-Correcting Codes." (1983).

[2] Joiner, Laurie L., and John J. Komo. "Decoding binary BCH codes."
Proceedings IEEE Southeastcon'95. Visualize the Future. IEEE, 1995.

[3] Gao, Shuhong, and Todd Mateer. "Additive fast Fourier transforms over finite fields."
IEEE Transactions on Information Theory 56.12 (2010): 6265-6272.

[4] Bernstein, Daniel J., Tung Chou, and Peter Schwabe.
"McBits: fast constant-time code-based cryptography."
International Workshop on Cryptographic Hardware and Embedded Systems.
Springer, Berlin, Heidelberg, 2013.


6. LICENCE
----------

This project is licensed under the GNU Lesser General Public License v3.0 - see the LICENSE file for details.