/******************************************************************************
 * BIKE -- Bit Flipping Key Encapsulation
 *
 * Copyright (c) 2021 Nir Drucker, Shay Gueron, Rafael Misoczki, Tobias Oder,
 * Tim Gueneysu, Jan Richter-Brockmann.
 * Contact: drucker.nir@gmail.com, shay.gueron@gmail.com,
 * rafaelmisoczki@google.com, tobias.oder@rub.de, tim.gueneysu@rub.de,
 * jan.richter-brockmann@rub.de.
 *
 * Permission to use this code for BIKE is granted.
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * * Redistributions of source code must retain the above copyright notice,
 *   this list of conditions and the following disclaimer.
 *
 * * Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 *
 * * The names of the contributors may not be used to endorse or promote
 *   products derived from this software without specific prior written
 *   permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHORS ""AS IS"" AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHORS CORPORATION OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 ******************************************************************************/

#include "decode.h"
#include "utilities.h"

#include "kem.h"
#include "sampling.h"

#include "ring_buffer.h"

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

// count number of 1's in tmp:
uint32_t getHammingWeight(const uint8_t tmp[R_BITS], const uint32_t length)
{
    uint32_t count = 0;
    for (uint32_t i = 0; i < length; i++)
    {
        count+=tmp[i];
    }

    return count;
}

// function (not constant time) to check if an array is zero:
uint32_t isZero(uint8_t s[R_BITS])
{
    for (uint32_t i = 0; i < R_BITS; i++)
    {
        if (s[i])
        {
            return 0;
        }
    }
    return 1;
}

void recompute_syndrome(uint8_t s[R_BITS],
        const uint32_t pos,
        const uint32_t h0_compact[DV],
        const uint32_t h1_compact[DV])
{
    if (pos < R_BITS)
    {
        for (uint32_t j = 0; j < DV; j++)
        {
            if (h0_compact[j] <= pos)
            {
                s[pos - h0_compact[j]] ^= 1;
            }
            else
            {
                s[R_BITS - h0_compact[j] +  pos] ^= 1;
            }
        }
    }
    else
    {
       for (uint32_t j = 0; j < DV; j++)
       {
          if (h1_compact[j] <= (pos - R_BITS))
               s[(pos - R_BITS) - h1_compact[j]] ^= 1;
           else
               s[R_BITS - h1_compact[j] + (pos - R_BITS)] ^= 1;
       }
    }
}

uint32_t ctr(
        uint32_t h_compact_col[DV],
        int position,
        uint8_t s[R_BITS])
{
    uint32_t count = 0;
    for (uint32_t i = 0; i < DV; i++)
    {
        if (s[(h_compact_col[i] + position) % R_BITS])
            count++;
    }
    return count;
}

void getCol(
        uint32_t h_compact_col[DV],
        uint32_t h_compact_row[DV])
{
    if (h_compact_row[0] == 0)
    {
        h_compact_col[0] = 0;

        for (uint32_t i = 1; i < DV; i++)
        {
            // set indices in increasing order:
            h_compact_col[i] = R_BITS - h_compact_row[DV-i];
        }
    } else
    {
        for (uint32_t i = 0; i < DV; i++)
        {
            // set indices in increasing order:
            h_compact_col[i] = R_BITS - h_compact_row[DV-1-i];
        }
    }
}

// The position in e is adjusted because syndrome is transposed.
void flipAdjustedErrorPosition(uint8_t e[R_BITS*2], uint32_t position)
{
    uint32_t adjustedPosition = position;
    if (position != 0 && position != R_BITS)
    {
        adjustedPosition = (position > R_BITS) ? \
                ((N_BITS - position)+R_BITS) : (R_BITS - position);
    }
    e[adjustedPosition] ^= 1;
}

void BFMaskedIter(uint8_t e[R_BITS*2],
    uint8_t s[R_BITS],
    uint8_t mask[R_BITS*2],
    uint32_t T,
    uint32_t h0_compact[DV],
    uint32_t h1_compact[DV],
    uint32_t h0_compact_col[DV],
    uint32_t h1_compact_col[DV])
{

    uint8_t pos[R_BITS*2] = {0};

    for (uint32_t j = 0; j < R_BITS; j++)
    {
        uint32_t counter = ctr(h0_compact_col, j, s);
        if (counter >= T && mask[j])
        {
            //e[j] ^= 1;
            flipAdjustedErrorPosition(e, j);
            pos[j] = 1;
        }
    }

    for (uint32_t j = 0; j < R_BITS; j++)
    {
        uint32_t counter = ctr(h1_compact_col, j, s);
        if (counter >= T && mask[R_BITS+j])
        {
            //e[R_BITS+j] ^= 1;
            flipAdjustedErrorPosition(e, R_BITS+j);
            pos[R_BITS+j] = 1;
        }
    }

    // flip bits at the end - as defined in the BGF decoder
    for(uint32_t j=0; j < 2*R_BITS; j++){
        if(pos[j] == 1){
            recompute_syndrome(s, j, h0_compact, h1_compact);
        }
    }
}

void BFIter(uint8_t e[R_BITS*2],
    uint8_t black[R_BITS*2],
    uint8_t gray[R_BITS*2],
    uint8_t s[R_BITS],
    uint32_t T,
    uint32_t h0_compact[DV],
    uint32_t h1_compact[DV],
    uint32_t h0_compact_col[DV],
    uint32_t h1_compact_col[DV])
{

    uint8_t pos[R_BITS*2] = {0};

    for (uint32_t j = 0; j < R_BITS; j++)
    {
        uint32_t counter = ctr(h0_compact_col, j, s);
        if (counter >= T)
        {
            //e[j] ^= 1;
            flipAdjustedErrorPosition(e, j);
            pos[j] = 1;
            black[j] = 1;
        } else if(counter >= T - tau)
        {
            gray[j] = 1;
        }
    }
    for (uint32_t j = 0; j < R_BITS; j++)
    {
        uint32_t counter = ctr(h1_compact_col, j, s);

        if (counter >= T)
        {
            //e[R_BITS+j] ^= 1;
            flipAdjustedErrorPosition(e, R_BITS+j);
            pos[R_BITS+j] = 1;
            black[R_BITS+j] = 1;
        } else if(counter >= T - tau)
            {
                gray[R_BITS+j] = 1;
            }
    }

    // flip bits at the end
    for(uint32_t j=0; j < 2*R_BITS; j++){
        if(pos[j] == 1){
            recompute_syndrome(s, j, h0_compact, h1_compact);
        }
    }
}

// Algorithm BGF - Black-Gray-Flip Decoder
int BGF_decoder(uint8_t e[R_BITS*2],
    uint8_t s[R_BITS],
    uint32_t h0_compact[DV],
    uint32_t h1_compact[DV])
{
    memset(e, 0, R_BITS*2);

    // computing the first column of each parity-check block:
    uint32_t h0_compact_col[DV] = {0};
    uint32_t h1_compact_col[DV] = {0};
    getCol(h0_compact_col, h0_compact);
    getCol(h1_compact_col, h1_compact);

    uint8_t black[R_BITS*2] = {0};
    uint8_t gray[R_BITS*2] = {0};

    for (int i = 1; i <= NbIter; i++)
    {
        memset(black, 0, R_BITS*2);
        memset(gray, 0, R_BITS*2);

        uint32_t T = floor(VAR_TH_FCT(getHammingWeight(s, R_BITS)));

        BFIter(e, black, gray, s, T, h0_compact, h1_compact, h0_compact_col, h1_compact_col);

        if (i == 1)
        {
            BFMaskedIter(e, s, black, (DV+1)/2 + 1, h0_compact, h1_compact, h0_compact_col, h1_compact_col);
            BFMaskedIter(e, s, gray, (DV+1)/2 + 1, h0_compact, h1_compact, h0_compact_col, h1_compact_col);
        }
    }
    if (getHammingWeight(s, R_BITS) == 0)
        return 0; // SUCCESS
    else
        return 1; // FAILURE
}


