gf2.h

Go to the documentation of this file.

/*
This file is part of BitPunch
Copyright (C) 2013-2015 Frantisek Uhrecky <frantisek.uhrecky[what here]gmail.com>
Copyright (C) 2013-2015 Andrej Gulyas <andrej.guly[what here]gmail.com>
Copyright (C) 2013-2014 Marek Klein  <kleinmrk[what here]gmail.com>
Copyright (C) 2013-2014 Filip Machovec  <filipmachovec[what here]yahoo.com>
Copyright (C) 2013-2014 Jozef Kudlac <jozef[what here]kudlac.sk>

This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/
#ifndef BPU_GF2_H
#define BPU_GF2_H

#include <stdio.h>
#include <string.h>

#include <bitpunch/config.h>
#include "permtypes.h"
#include "gf2types.h"
#include "int.h"

#ifdef BPU_CONF_PRINT
/* ==================================== Print functions ==================================== */
// TODO: Be enable to turn off print function, to not compile in in code
void BPU_printBinaryMsb(uint32_t in, int len);

void BPU_printBinaryMsbLn(uint32_t in, int len);

void BPU_printBinaryMsb32(uint32_t in);

void BPU_printBinaryMsb32Ln(uint32_t in);

void BPU_printBinaryLsb(uint32_t in, int len);

void BPU_printBinaryLsbLn(uint32_t in, int len);

void BPU_printBinaryLsb32(uint32_t in);

void BPU_printBinary32LsbLn(uint32_t in);

void BPU_printGf2Mat(const BPU_T_GF2_Matrix *m);

void BPU_printGf2Vec(const BPU_T_GF2_Vector *v);

void BPU_printGf2VecMsb(const BPU_T_GF2_Vector* v);

void BPU_printGf2VecOnes(const BPU_T_GF2_Vector *vec);


void BPU_printGf2SparsePoly (const BPU_T_GF2_Sparse_Poly *v);

void BPU_printGf2PolyForMatrix(const BPU_T_GF2_Poly* v);

void BPU_printGf2Poly(const BPU_T_GF2_Poly* v);

void BPU_printGf2QcMatrix(const BPU_T_GF2_QC_Matrix *v);

void BPU_printGf2SparseQcMatrix(const BPU_T_GF2_Sparse_Qc_Matrix *v);

/* ------------------------------------ Print functions ------------------------------------ */
#endif // BPU_CONF_PRINT

#define BPU_getBit(w, n) ((int)((((uint32_t)w) >> (n)) & 1u))

#define BPU_gf2MatGetBit(m_pointer, s, t) (BPU_getBit((m_pointer)->elements[s][(t) / (m_pointer)->element_bit_size], (t) % (m_pointer)->element_bit_size))

#define BPU_gf2VecGetBit(v_pointer, i) (BPU_getBit((v_pointer)->elements[(i) / (v_pointer)->element_bit_size], (i) % (v_pointer)->element_bit_size))

#define BPU_gf2MatSetBit(m_pointer, s, t, bit)  if (bit) { \
                                                                                                (m_pointer)->elements[s][t / (m_pointer)->element_bit_size] |= ((BPU_T_GF2) 1) << ((t) % (m_pointer)->element_bit_size);\
                                                                                                } \
                                                                                                else { \
                                                                                                        /* this is like: 00101111 ^ 00000100 = 00101011 */\
                                                                                                        (m_pointer)->elements[s][(t) / (m_pointer)->element_bit_size] &= ((BPU_T_GF2) (0xFFFFFFFFu)) ^ (((BPU_T_GF2) 1) << ((t) % (m_pointer)->element_bit_size));\
                                                                                                }

#define BPU_gf2VecSetBit(v_pointer, i, bit)  if (bit) { \
                                                                                                (v_pointer)->elements[(i) / (v_pointer)->element_bit_size] |= ((BPU_T_GF2) 1) << ((i) % (v_pointer)->element_bit_size);\
                                                                                                } \
                                                                                                else { \
                                                                                                        /* this is like: 00101111 ^ 00000100 = 00101011 */\
                                                                                                        (v_pointer)->elements[(i) / (v_pointer)->element_bit_size] &= ((BPU_T_GF2) (0xFFFFFFFFu)) ^ (((BPU_T_GF2) 1) << ((i) % (v_pointer)->element_bit_size));\
                                                                                                }

#define BPU_gf2MatCopyRowToVec(v_pointer, m_pointer, row) memcpy((void *) ((v_pointer)->elements), (void *) ((m_pointer)->elements[row]), (v_pointer)->element_bit_size / 8 * (v_pointer)->elements_in_row)

#define BPU_gf2PolyGetBit(poly, bit) ((poly->elements[bit/poly->element_bit_size] >> (bit%poly->element_bit_size)) & 1ul)

int BPU_gf2MatCopy(BPU_T_GF2_Matrix *out, const BPU_T_GF2_Matrix *in);

int BPU_gf2MatPermute(BPU_T_GF2_Matrix *m, BPU_T_Perm_Vector *permutation);

int BPU_gf2VecPermute(BPU_T_GF2_Vector *vec, const BPU_T_Perm_Vector *permutation);

BPU_T_GF2 BPU_gf2MatGetMaskedBit(const BPU_T_GF2_Matrix *m, uint32_t row, uint32_t bit);

BPU_T_GF2 BPU_gf2VecGetMaskedBit(const BPU_T_GF2_Vector *vec, uint32_t bit);

int BPU_gf2MatTransp(BPU_T_GF2_Matrix *out, const BPU_T_GF2_Matrix *in);

void BPU_gf2Swap(BPU_T_GF2 *a, BPU_T_GF2 *b);

void BPU_gf2MatSwapRows(BPU_T_GF2_Matrix *mat, int i, int j);

int BPU_gf2MatFindRow(const BPU_T_GF2_Matrix *mat, int i, int start_index);

int BPU_gf2MatFindCol(const BPU_T_GF2_Matrix *mat, int i, int start_index);

int BPU_gf2MatMakeSystematic(BPU_T_GF2_Matrix *inout);

int BPU_gf2VecConcat(BPU_T_GF2_Vector *out, const BPU_T_GF2_Vector *vec1, const BPU_T_GF2_Vector *vec2);

int BPU_gf2VecCrop(BPU_T_GF2_Vector *out, const BPU_T_GF2_Vector *in, const int start, const int length);

int BPU_gf2MatGetRowAsGf2Vec(BPU_T_GF2_Vector *out, const BPU_T_GF2_Matrix *in, int row);

void BPU_gf2VecCopy(BPU_T_GF2_Vector *dest, const BPU_T_GF2_Vector *src);

int BPU_gf2VecCmp(const BPU_T_GF2_Vector *v1, const BPU_T_GF2_Vector *v2);

void BPU_gf2MatXorRows(BPU_T_GF2_Matrix *mat, int i, int j);

int BPU_gf2VecXor(BPU_T_GF2_Vector *out, const BPU_T_GF2_Vector *in);

int BPU_gf2VecRand(BPU_T_GF2_Vector *out, int w);

int BPU_gf2VecMulMat(BPU_T_GF2_Vector *x, const BPU_T_GF2_Vector *v, const BPU_T_GF2_Matrix *b);

int BPU_gf2MatCrop(BPU_T_GF2_Matrix *m, uint16_t width);

uint8_t BPU_getParity(BPU_T_GF2 dword);

/************************************************
POLYNOMIAL UTILS
************************************************/

int BPU_gf2PolyIsZero(const BPU_T_GF2_Poly *a);

void BPU_gf2PolySetDeg(BPU_T_GF2_Poly *a, int deg);

int BPU_gf2PolyGetHighestBitPos(BPU_T_GF2_Poly *a);

void BPU_gf2PolyShiftLeft(BPU_T_GF2_Poly *a, int shift_count);

void BPU_gf2PolyShiftRightOne(BPU_T_GF2_Poly *a);

void BPU_gf2PolyTransp(BPU_T_GF2_Poly *out, const BPU_T_GF2_Poly *in);


/************************************************
POLYNOMIAL MATH
************************************************/

void BPU_gf2PolyMulX(BPU_T_GF2_Poly *a);

void BPU_gf2PolyAdd(BPU_T_GF2_Poly *out, const BPU_T_GF2_Poly *in, int crop);

void BPU_gf2PolyMulMod(const BPU_T_GF2_Poly *a, const BPU_T_GF2_Poly *b, BPU_T_GF2_Poly *c, const BPU_T_GF2_Poly *m, int crop);

void BPU_gf2PolyDiv(BPU_T_GF2_Poly *q, BPU_T_GF2_Poly *r, const BPU_T_GF2_Poly *a, const BPU_T_GF2_Poly *b);

void BPU_gf2PolyExtEuclidA(BPU_T_GF2_Poly *d, BPU_T_GF2_Poly *s, BPU_T_GF2_Poly *t, const BPU_T_GF2_Poly *a, const BPU_T_GF2_Poly *b, const BPU_T_GF2_Poly *m);

int BPU_gf2PolyInv(BPU_T_GF2_Poly *out, const BPU_T_GF2_Poly *a, const BPU_T_GF2_Poly *mod);


/************************************************
SPARSE POLYNOMIAL UTILS
************************************************/

void BPU_gf2SparsePolyCopy(BPU_T_GF2_Sparse_Poly *out, const BPU_T_GF2_Sparse_Poly *in);

void BPU_gf2PolyCopy(BPU_T_GF2_Poly *out, const BPU_T_GF2_Poly *in);

int BPU_gf2PolyInitRand(BPU_T_GF2_Poly *out, int l, int w, int set_deg);


/************************************************
SPARSE POLYNOMIAL MATH
************************************************/

void BPU_gf2SparsePolyAdd(BPU_T_GF2_Poly *out, const BPU_T_GF2_Sparse_Poly *in);

int BPU_gf2SparsePolyAndHW(const BPU_T_GF2_Poly *a, const BPU_T_GF2_Sparse_Poly *b);


/************************************************
QUASI-CYCLIC MATRIX UTILS
************************************************/

void BPU_gf2QcMatrixTransp(BPU_T_GF2_QC_Matrix *out, const BPU_T_GF2_QC_Matrix *in);

int BPU_gf2QcMatrixToSparse(BPU_T_GF2_Sparse_Qc_Matrix *out, const BPU_T_GF2_QC_Matrix *in, const int wi[]);


/************************************************
SPARSE QUASI-CYCLIC MATRIX UTILS
************************************************/

void BPU_gf2SparseQcMatrixGetRow(BPU_T_GF2_Sparse_Poly *p, const BPU_T_GF2_Sparse_Qc_Matrix *m, int row_num);

void BPU_gf2SparseQcMatrixTransp(BPU_T_GF2_Sparse_Qc_Matrix *out, const BPU_T_GF2_Sparse_Qc_Matrix *in);

#endif // BPU_GF2_H