/*
 * Licensed to the OpenAirInterface (OAI) Software Alliance under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The OpenAirInterface Software Alliance licenses this file to You under
 * the OAI Public License, Version 1.1  (the "License"); you may not use this file
 * except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.openairinterface.org/?page_id=698
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *-------------------------------------------------------------------------------
 * For more information about the OpenAirInterface (OAI) Software Alliance
 *      contact@openairinterface.org
 */

/*!\file PHY/CODING/nrPolar_tools/nr_polar_decoder.c
 * \brief
 * \author Turker Yilmaz
 * \date 2018
 * \version 0.1
 * \company EURECOM
 * \email turker.yilmaz@eurecom.fr
 * \note
 * \warning
*/

/*
 * Return values:
 *  0 --> Success
 * -1 --> All list entries have failed the CRC checks
 */

#include "PHY/CODING/nrPolar_tools/nr_polar_defs.h"


int8_t polar_decoder(
		double *input,
		uint8_t *out,
		t_nrPolar_paramsPtr polarParams,
		uint8_t listSize,
		uint8_t pathMetricAppr)
{
	//Assumes no a priori knowledge.

	uint8_t ***bit = nr_alloc_uint8_t_3D_array(polarParams->N, (polarParams->n+1), 2*listSize);
	uint8_t **bitUpdated = nr_alloc_uint8_t_2D_array(polarParams->N, (polarParams->n+1)); //0=False, 1=True
	uint8_t **llrUpdated = nr_alloc_uint8_t_2D_array(polarParams->N, (polarParams->n+1)); //0=False, 1=True
	double ***llr = nr_alloc_double_3D_array(polarParams->N, (polarParams->n+1), 2*listSize);
	uint8_t **crcChecksum = nr_alloc_uint8_t_2D_array(polarParams->crcParityBits, 2*listSize);
	double *pathMetric = malloc(sizeof(double)*(2*listSize));
	uint8_t *crcState = malloc(sizeof(uint8_t)*(2*listSize)); //0=False, 1=True

	for (int i=0; i<(2*listSize); i++) {
		pathMetric[i] = 0;
		crcState[i]=1;
	}
	for (int i=0; i<polarParams->N; i++) {
		llrUpdated[i][polarParams->n]=1;
		bitUpdated[i][0]=((polarParams->information_bit_pattern[i]+1) % 2);
	}

	uint8_t **extended_crc_generator_matrix = malloc(polarParams->K * sizeof(uint8_t *)); //G_P3
	uint8_t **tempECGM = malloc(polarParams->K * sizeof(uint8_t *)); //G_P2
	for (int i = 0; i < polarParams->K; i++){
		extended_crc_generator_matrix[i] = malloc(polarParams->crcParityBits * sizeof(uint8_t));
		tempECGM[i] = malloc(polarParams->crcParityBits * sizeof(uint8_t));
	}

	for (int i=0; i<polarParams->payloadBits; i++) {
		for (int j=0; j<polarParams->crcParityBits; j++) {
			tempECGM[i][j]=polarParams->crc_generator_matrix[i][j];
		}
	}
	for (int i=polarParams->payloadBits; i<polarParams->K; i++) {
			for (int j=0; j<polarParams->crcParityBits; j++) {
				if( (i-polarParams->payloadBits) == j ){
					tempECGM[i][j]=1;
				} else {
					tempECGM[i][j]=0;
				}
			}
	}

	for (int i=0; i<polarParams->K; i++) {
		for (int j=0; j<polarParams->crcParityBits; j++) {
			extended_crc_generator_matrix[i][j]=tempECGM[polarParams->interleaving_pattern[i]][j];
		}
	}

	//The index of the last 1-valued bit that appears in each column.
	uint16_t last1ind[polarParams->crcParityBits];
	for (int j=0; j<polarParams->crcParityBits; j++) {
			for (int i=0; i<polarParams->K; i++) {
				if (extended_crc_generator_matrix[i][j]==1) last1ind[j]=i;
			}
	}

	double *d_tilde = malloc(sizeof(double) * polarParams->N);
	nr_polar_rate_matching(input, d_tilde, polarParams->rate_matching_pattern, polarParams->K, polarParams->N, polarParams->encoderLength);
	for (int j = 0; j < polarParams->N; j++) llr[j][polarParams->n][0]=d_tilde[j];


	/*
	 * SCL polar decoder.
	 */

	uint32_t nonFrozenBit=0;
	uint8_t currentListSize=1;
	uint8_t decoderIterationCheck=0;
	int16_t checkCrcBits=-1;
	uint8_t listIndex[2*listSize], copyIndex;

	for (uint16_t currentBit=0; currentBit<polarParams->N; currentBit++){
		updateLLR(llr, llrUpdated, bit, bitUpdated, currentListSize, currentBit, 0, polarParams->N, (polarParams->n+1), pathMetricAppr);
		if (polarParams->information_bit_pattern[currentBit]==0) { //Frozen bit.
			updatePathMetric(pathMetric, llr, currentListSize, 0, currentBit, pathMetricAppr); //approximation=0 --> 11b, approximation=1 --> 12
		} else { //Information or CRC bit.
			updatePathMetric2(pathMetric, llr, currentListSize, currentBit, pathMetricAppr);

			for (int i = 0; i < currentListSize; i++) {
				for (int j = 0; j < polarParams->N; j++) {
					for (int k = 0; k < (polarParams->n+1); k++) {
						bit[j][k][i+currentListSize]=bit[j][k][i];
						llr[j][k][i+currentListSize]=llr[j][k][i];}}}
			for (int i = 0; i < currentListSize; i++) {
				bit[currentBit][0][i]=0;
				crcState[i+currentListSize]=crcState[i];
			}
			for (int i = currentListSize; i < 2*currentListSize; i++) bit[currentBit][0][i]=1;
			bitUpdated[currentBit][0]=1;
			updateCrcChecksum2(crcChecksum, extended_crc_generator_matrix, currentListSize, nonFrozenBit, polarParams->crcParityBits);
			currentListSize*=2;

			//Keep only the best "listSize" number of entries.
			if (currentListSize > listSize) {
				for (uint8_t i = 0; i < 2*listSize; i++) listIndex[i]=i;
				nr_sort_asc_double_1D_array_ind(pathMetric, listIndex, currentListSize);

				//sort listIndex[listSize, ..., 2*listSize-1] in descending order.
				uint8_t swaps, tempInd;
				for (uint8_t i = 0; i < listSize; i++) {
					swaps = 0;
					for (uint8_t j = listSize; j < (2*listSize - i) - 1; j++) {
						if (listIndex[j+1] > listIndex[j]) {
							tempInd = listIndex[j];
							listIndex[j] = listIndex[j + 1];
							listIndex[j + 1] = tempInd;
							swaps++;
						}
					}
					if (swaps == 0)
						break;
				}

				//First, backup the best "listSize" number of entries.
				for (int k=(listSize-1); k>0; k--) {
					for (int i=0; i<polarParams->N; i++) {
						for (int j=0; j<(polarParams->n+1); j++) {
							bit[i][j][listIndex[(2*listSize-1)-k]]=bit[i][j][listIndex[k]];
							llr[i][j][listIndex[(2*listSize-1)-k]]=llr[i][j][listIndex[k]];
						}
					}
				}
				for (int k=(listSize-1); k>0; k--) {
					for (int i = 0; i < polarParams->crcParityBits; i++) {
						crcChecksum[i][listIndex[(2*listSize-1)-k]] = crcChecksum[i][listIndex[k]];
					}
				}
				for (int k=(listSize-1); k>0; k--) crcState[listIndex[(2*listSize-1)-k]]=crcState[listIndex[k]];

				//Copy the best "listSize" number of entries to the first indices.
				for (int k = 0; k < listSize; k++) {
					if (k > listIndex[k]) {
						copyIndex = listIndex[(2*listSize-1)-k];
					} else { //Use the backup.
						copyIndex = listIndex[k];
					}
					for (int i = 0; i < polarParams->N; i++) {
						for (int j = 0; j < (polarParams->n + 1); j++) {
							bit[i][j][k] = bit[i][j][copyIndex];
							llr[i][j][k] = llr[i][j][copyIndex];
						}
					}
				}
				for (int k = 0; k < listSize; k++) {
					if (k > listIndex[k]) {
						copyIndex = listIndex[(2*listSize-1)-k];
					} else { //Use the backup.
						copyIndex = listIndex[k];
					}
					for (int i = 0; i < polarParams->crcParityBits; i++) {
						crcChecksum[i][k]=crcChecksum[i][copyIndex];
					}
				}
				for (int k = 0; k < listSize; k++) {
					if (k > listIndex[k]) {
						copyIndex = listIndex[(2*listSize-1)-k];
					} else { //Use the backup.
						copyIndex = listIndex[k];
					}
					crcState[k]=crcState[copyIndex];
				}
				currentListSize = listSize;
				}


			for (int i=0; i<polarParams->crcParityBits; i++) {
				if (last1ind[i]==nonFrozenBit) {
					checkCrcBits=i;
					break;
				}
			}

			if ( checkCrcBits > (-1) ) {
				for (uint8_t i = 0; i < currentListSize; i++) {
					if (crcChecksum[checkCrcBits][i]==1) {
						crcState[i]=0; //0=False, 1=True
					}
				}
			}

			for (uint8_t i = 0; i < currentListSize; i++) decoderIterationCheck+=crcState[i];
			if (decoderIterationCheck==0) {
				//perror("[SCL polar decoder] All list entries have failed the CRC checks.");
				free(d_tilde);
				free(pathMetric);
				free(crcState);
				nr_free_uint8_t_3D_array(bit, polarParams->N, (polarParams->n+1));
				nr_free_double_3D_array(llr, polarParams->N, (polarParams->n+1));
				nr_free_uint8_t_2D_array(crcChecksum, polarParams->crcParityBits);
				return(-1);
			}

			nonFrozenBit++;
			decoderIterationCheck=0;
			checkCrcBits=-1;
		}
	}

	for (uint8_t i = 0; i < 2*listSize; i++) listIndex[i]=i;
	nr_sort_asc_double_1D_array_ind(pathMetric, listIndex, currentListSize);

	for (uint8_t i = 0; i < fmin(listSize, (pow(2,polarParams->crcCorrectionBits)) ); i++) {
		if ( crcState[listIndex[i]] == 1 ) {
			for (int j = 0; j < polarParams->N; j++) polarParams->nr_polar_U[j]=bit[j][0][listIndex[i]];

			//Extract the information bits (û to ĉ)
			nr_polar_info_bit_extraction(polarParams->nr_polar_U, polarParams->nr_polar_CPrime, polarParams->information_bit_pattern, polarParams->N);

			//Deinterleaving (ĉ to b)
			nr_polar_deinterleaver(polarParams->nr_polar_CPrime, polarParams->nr_polar_B, polarParams->interleaving_pattern, polarParams->K);

			//Remove the CRC (â)
			for (int j = 0; j < polarParams->payloadBits; j++) polarParams->nr_polar_A[j]=polarParams->nr_polar_B[j];

			break;
		}
	}

	free(d_tilde);
	free(pathMetric);
	free(crcState);
	nr_free_uint8_t_3D_array(bit, polarParams->N, (polarParams->n+1));
	nr_free_double_3D_array(llr, polarParams->N, (polarParams->n+1));
	nr_free_uint8_t_2D_array(crcChecksum, polarParams->crcParityBits);
	nr_free_uint8_t_2D_array(extended_crc_generator_matrix, polarParams->K);
	nr_free_uint8_t_2D_array(tempECGM, polarParams->K);

	/*
	 * Return bits.
	 */
	//nr_byte2bit_uint8_32_t(polarParams->nr_polar_A, polarParams->payloadBits, out);
	return(0);
}

int8_t polar_decoder_aPriori(double *input,
							 uint32_t *out,
							 t_nrPolar_paramsPtr polarParams,
							 uint8_t listSize,
							 uint8_t pathMetricAppr,
							 double *aPrioriPayload)
{
	uint8_t ***bit = nr_alloc_uint8_t_3D_array(polarParams->N, (polarParams->n+1), 2*listSize);
	uint8_t **bitUpdated = nr_alloc_uint8_t_2D_array(polarParams->N, (polarParams->n+1)); //0=False, 1=True
	uint8_t **llrUpdated = nr_alloc_uint8_t_2D_array(polarParams->N, (polarParams->n+1)); //0=False, 1=True
	double ***llr = nr_alloc_double_3D_array(polarParams->N, (polarParams->n+1), 2*listSize);
	uint8_t **crcChecksum = nr_alloc_uint8_t_2D_array(polarParams->crcParityBits, 2*listSize);
	double *pathMetric = malloc(sizeof(double)*(2*listSize));
	uint8_t *crcState = malloc(sizeof(uint8_t)*(2*listSize)); //0=False, 1=True

	for (int i=0; i<(2*listSize); i++) {
		pathMetric[i] = 0;
		crcState[i]=1;
	}
	for (int i=0; i<polarParams->N; i++) {
		llrUpdated[i][polarParams->n]=1;
		bitUpdated[i][0]=((polarParams->information_bit_pattern[i]+1) % 2);
	}

	uint8_t **extended_crc_generator_matrix = malloc(polarParams->K * sizeof(uint8_t *)); //G_P3
	uint8_t **tempECGM = malloc(polarParams->K * sizeof(uint8_t *)); //G_P2
	for (int i = 0; i < polarParams->K; i++){
		extended_crc_generator_matrix[i] = malloc(polarParams->crcParityBits * sizeof(uint8_t));
		tempECGM[i] = malloc(polarParams->crcParityBits * sizeof(uint8_t));
	}

	for (int i=0; i<polarParams->payloadBits; i++) {
		for (int j=0; j<polarParams->crcParityBits; j++) {
			tempECGM[i][j]=polarParams->crc_generator_matrix[i][j];
		}
	}
	for (int i=polarParams->payloadBits; i<polarParams->K; i++) {
			for (int j=0; j<polarParams->crcParityBits; j++) {
				if( (i-polarParams->payloadBits) == j ){
					tempECGM[i][j]=1;
				} else {
					tempECGM[i][j]=0;
				}
			}
	}

	for (int i=0; i<polarParams->K; i++) {
		for (int j=0; j<polarParams->crcParityBits; j++) {
			extended_crc_generator_matrix[i][j]=tempECGM[polarParams->interleaving_pattern[i]][j];
		}
	}

	//The index of the last 1-valued bit that appears in each column.
	uint16_t last1ind[polarParams->crcParityBits];
	for (int j=0; j<polarParams->crcParityBits; j++) {
			for (int i=0; i<polarParams->K; i++) {
				if (extended_crc_generator_matrix[i][j]==1) last1ind[j]=i;
			}
	}

	double *d_tilde = malloc(sizeof(double) * polarParams->N);
	nr_polar_rate_matching(input, d_tilde, polarParams->rate_matching_pattern, polarParams->K, polarParams->N, polarParams->encoderLength);
	for (int j = 0; j < polarParams->N; j++) llr[j][polarParams->n][0]=d_tilde[j];


	/*
	 * SCL polar decoder.
	 */

	uint32_t nonFrozenBit=0;
	uint8_t currentListSize=1;
	uint8_t decoderIterationCheck=0;
	int16_t checkCrcBits=-1;
	uint8_t listIndex[2*listSize], copyIndex;

	for (uint16_t currentBit=0; currentBit<polarParams->N; currentBit++){

		updateLLR(llr, llrUpdated, bit, bitUpdated, currentListSize, currentBit, 0, polarParams->N, (polarParams->n+1), pathMetricAppr);
		if (polarParams->information_bit_pattern[currentBit]==0) { //Frozen bit.
			updatePathMetric(pathMetric, llr, currentListSize, 0, currentBit, pathMetricAppr); //approximation=0 --> 11b, approximation=1 --> 12
		} else { //Information or CRC bit.
			if ( (polarParams->interleaving_pattern[nonFrozenBit] <= polarParams->payloadBits) &&
					(aPrioriPayload[polarParams->interleaving_pattern[nonFrozenBit]] == 0) ) {
				//Information bit with known value of "0".
				updatePathMetric(pathMetric, llr, currentListSize, 0, currentBit, pathMetricAppr);
				bitUpdated[currentBit][0]=1; //0=False, 1=True
			} else if ( (polarParams->interleaving_pattern[nonFrozenBit] <= polarParams->payloadBits) &&
					(aPrioriPayload[polarParams->interleaving_pattern[nonFrozenBit]] == 1) ) {
				//Information bit with known value of "1".
				updatePathMetric(pathMetric, llr, currentListSize, 1, currentBit, pathMetricAppr);
				for (uint8_t i=0; i<currentListSize; i++) bit[currentBit][0][i]=1;
				bitUpdated[currentBit][0]=1;
				updateCrcChecksum(crcChecksum, extended_crc_generator_matrix, currentListSize, nonFrozenBit, polarParams->crcParityBits);
			} else {
				updatePathMetric2(pathMetric, llr, currentListSize, currentBit, pathMetricAppr);

				for (int i = 0; i < currentListSize; i++) {
					for (int j = 0; j < polarParams->N; j++) {
						for (int k = 0; k < (polarParams->n+1); k++) {
							bit[j][k][i+currentListSize]=bit[j][k][i];
							llr[j][k][i+currentListSize]=llr[j][k][i];}}}
				for (int i = 0; i < currentListSize; i++) {
					bit[currentBit][0][i]=0;
					crcState[i+currentListSize]=crcState[i];
				}
				for (int i = currentListSize; i < 2*currentListSize; i++) bit[currentBit][0][i]=1;
				bitUpdated[currentBit][0]=1;
				updateCrcChecksum2(crcChecksum, extended_crc_generator_matrix, currentListSize, nonFrozenBit, polarParams->crcParityBits);
				currentListSize*=2;

				//Keep only the best "listSize" number of entries.
				if (currentListSize > listSize) {
					for (uint8_t i = 0; i < 2*listSize; i++) listIndex[i]=i;
					nr_sort_asc_double_1D_array_ind(pathMetric, listIndex, currentListSize);

					//sort listIndex[listSize, ..., 2*listSize-1] in descending order.
					uint8_t swaps, tempInd;
					for (uint8_t i = 0; i < listSize; i++) {
						swaps = 0;
						for (uint8_t j = listSize; j < (2*listSize - i) - 1; j++) {
							if (listIndex[j+1] > listIndex[j]) {
								tempInd = listIndex[j];
								listIndex[j] = listIndex[j + 1];
								listIndex[j + 1] = tempInd;
								swaps++;
							}
						}
						if (swaps == 0)
							break;
					}

					//First, backup the best "listSize" number of entries.
					for (int k=(listSize-1); k>0; k--) {
						for (int i=0; i<polarParams->N; i++) {
							for (int j=0; j<(polarParams->n+1); j++) {
								bit[i][j][listIndex[(2*listSize-1)-k]]=bit[i][j][listIndex[k]];
								llr[i][j][listIndex[(2*listSize-1)-k]]=llr[i][j][listIndex[k]];
							}
						}
					}
					for (int k=(listSize-1); k>0; k--) {
						for (int i = 0; i < polarParams->crcParityBits; i++) {
							crcChecksum[i][listIndex[(2*listSize-1)-k]] = crcChecksum[i][listIndex[k]];
						}
					}
					for (int k=(listSize-1); k>0; k--) crcState[listIndex[(2*listSize-1)-k]]=crcState[listIndex[k]];

					//Copy the best "listSize" number of entries to the first indices.
					for (int k = 0; k < listSize; k++) {
						if (k > listIndex[k]) {
							copyIndex = listIndex[(2*listSize-1)-k];
						} else { //Use the backup.
							copyIndex = listIndex[k];
						}
						for (int i = 0; i < polarParams->N; i++) {
							for (int j = 0; j < (polarParams->n + 1); j++) {
								bit[i][j][k] = bit[i][j][copyIndex];
								llr[i][j][k] = llr[i][j][copyIndex];
							}
						}
					}
					for (int k = 0; k < listSize; k++) {
						if (k > listIndex[k]) {
							copyIndex = listIndex[(2*listSize-1)-k];
						} else { //Use the backup.
							copyIndex = listIndex[k];
						}
						for (int i = 0; i < polarParams->crcParityBits; i++) {
							crcChecksum[i][k]=crcChecksum[i][copyIndex];
						}
					}
					for (int k = 0; k < listSize; k++) {
						if (k > listIndex[k]) {
							copyIndex = listIndex[(2*listSize-1)-k];
						} else { //Use the backup.
							copyIndex = listIndex[k];
						}
						crcState[k]=crcState[copyIndex];
					}
					currentListSize = listSize;
				}
			}

			for (int i=0; i<polarParams->crcParityBits; i++) {
				if (last1ind[i]==nonFrozenBit) {
					checkCrcBits=i;
					break;
				}
			}

			if ( checkCrcBits > (-1) ) {
				for (uint8_t i = 0; i < currentListSize; i++) {
					if (crcChecksum[checkCrcBits][i]==1) {
						crcState[i]=0; //0=False, 1=True
					}
				}
			}

			for (uint8_t i = 0; i < currentListSize; i++) decoderIterationCheck+=crcState[i];
			if (decoderIterationCheck==0) {
				//perror("[SCL polar decoder] All list entries have failed the CRC checks.");
				free(d_tilde);
				free(pathMetric);
				free(crcState);
				nr_free_uint8_t_3D_array(bit, polarParams->N, (polarParams->n+1));
				nr_free_double_3D_array(llr, polarParams->N, (polarParams->n+1));
				nr_free_uint8_t_2D_array(crcChecksum, polarParams->crcParityBits);
				return(-1);
			}

			nonFrozenBit++;
			decoderIterationCheck=0;
			checkCrcBits=-1;
		}
	}

	for (uint8_t i = 0; i < 2*listSize; i++) listIndex[i]=i;
	nr_sort_asc_double_1D_array_ind(pathMetric, listIndex, currentListSize);

	for (uint8_t i = 0; i < fmin(listSize, (pow(2,polarParams->crcCorrectionBits)) ); i++) {
		if ( crcState[listIndex[i]] == 1 ) {
			for (int j = 0; j < polarParams->N; j++) polarParams->nr_polar_U[j]=bit[j][0][listIndex[i]];

			//Extract the information bits (û to ĉ)
			nr_polar_info_bit_extraction(polarParams->nr_polar_U, polarParams->nr_polar_CPrime, polarParams->information_bit_pattern, polarParams->N);

			//Deinterleaving (ĉ to b)
			nr_polar_deinterleaver(polarParams->nr_polar_CPrime, polarParams->nr_polar_B, polarParams->interleaving_pattern, polarParams->K);

			//Remove the CRC (â)
			for (int j = 0; j < polarParams->payloadBits; j++) polarParams->nr_polar_A[j]=polarParams->nr_polar_B[j];

			break;
		}
	}

	free(d_tilde);
	free(pathMetric);
	free(crcState);
	nr_free_uint8_t_3D_array(bit, polarParams->N, (polarParams->n+1));
	nr_free_double_3D_array(llr, polarParams->N, (polarParams->n+1));
	nr_free_uint8_t_2D_array(crcChecksum, polarParams->crcParityBits);
	nr_free_uint8_t_2D_array(extended_crc_generator_matrix, polarParams->K);
	nr_free_uint8_t_2D_array(tempECGM, polarParams->K);

	/*
	 * Return bits.
	 */
	nr_byte2bit_uint8_32_t(polarParams->nr_polar_A, polarParams->payloadBits, out);
	return(0);

}



int8_t polar_decoder_aPriori_timing(double *input,
									uint32_t *out,
									t_nrPolar_paramsPtr polarParams,
									uint8_t listSize,
									uint8_t pathMetricAppr,
									double *aPrioriPayload,
									double cpuFreqGHz,
									FILE* logFile)
{

	uint8_t ***bit = nr_alloc_uint8_t_3D_array(polarParams->N, (polarParams->n+1), 2*listSize);
	uint8_t **bitUpdated = nr_alloc_uint8_t_2D_array(polarParams->N, (polarParams->n+1)); //0=False, 1=True
	uint8_t **llrUpdated = nr_alloc_uint8_t_2D_array(polarParams->N, (polarParams->n+1)); //0=False, 1=True
	double ***llr = nr_alloc_double_3D_array(polarParams->N, (polarParams->n+1), 2*listSize);
	uint8_t **crcChecksum = nr_alloc_uint8_t_2D_array(polarParams->crcParityBits, 2*listSize);
	double *pathMetric = malloc(sizeof(double)*(2*listSize));
	uint8_t *crcState = malloc(sizeof(uint8_t)*(2*listSize)); //0=False, 1=True

	for (int i=0; i<(2*listSize); i++) {
		pathMetric[i] = 0;
		crcState[i]=1;
	}
	for (int i=0; i<polarParams->N; i++) {
		llrUpdated[i][polarParams->n]=1;
		bitUpdated[i][0]=((polarParams->information_bit_pattern[i]+1) % 2);
	}

	uint8_t **extended_crc_generator_matrix = malloc(polarParams->K * sizeof(uint8_t *)); //G_P3
	uint8_t **tempECGM = malloc(polarParams->K * sizeof(uint8_t *)); //G_P2
	for (int i = 0; i < polarParams->K; i++){
		extended_crc_generator_matrix[i] = malloc(polarParams->crcParityBits * sizeof(uint8_t));
		tempECGM[i] = malloc(polarParams->crcParityBits * sizeof(uint8_t));
	}

	for (int i=0; i<polarParams->payloadBits; i++) {
		for (int j=0; j<polarParams->crcParityBits; j++) {
			tempECGM[i][j]=polarParams->crc_generator_matrix[i][j];
		}
	}
	for (int i=polarParams->payloadBits; i<polarParams->K; i++) {
			for (int j=0; j<polarParams->crcParityBits; j++) {
				if( (i-polarParams->payloadBits) == j ){
					tempECGM[i][j]=1;
				} else {
					tempECGM[i][j]=0;
				}
			}
	}

	for (int i=0; i<polarParams->K; i++) {
		for (int j=0; j<polarParams->crcParityBits; j++) {
			extended_crc_generator_matrix[i][j]=tempECGM[polarParams->interleaving_pattern[i]][j];
		}
	}

	//The index of the last 1-valued bit that appears in each column.
	uint16_t last1ind[polarParams->crcParityBits];
	for (int j=0; j<polarParams->crcParityBits; j++) {
			for (int i=0; i<polarParams->K; i++) {
				if (extended_crc_generator_matrix[i][j]==1) last1ind[j]=i;
			}
	}

	double *d_tilde = malloc(sizeof(double) * polarParams->N);
	nr_polar_rate_matching(input, d_tilde, polarParams->rate_matching_pattern, polarParams->K, polarParams->N, polarParams->encoderLength);
	for (int j = 0; j < polarParams->N; j++) llr[j][polarParams->n][0]=d_tilde[j];


	/*
	 * SCL polar decoder.
	 */

	uint32_t nonFrozenBit=0;
	uint8_t currentListSize=1;
	uint8_t decoderIterationCheck=0;
	int16_t checkCrcBits=-1;
	uint8_t listIndex[2*listSize], copyIndex;

	for (uint16_t currentBit=0; currentBit<polarParams->N; currentBit++){
		updateLLR(llr, llrUpdated, bit, bitUpdated, currentListSize, currentBit, 0, polarParams->N, (polarParams->n+1), pathMetricAppr);
		if (polarParams->information_bit_pattern[currentBit]==0) { //Frozen bit.
			updatePathMetric(pathMetric, llr, currentListSize, 0, currentBit, pathMetricAppr); //approximation=0 --> 11b, approximation=1 --> 12
		} else { //Information or CRC bit.
			if ( (polarParams->interleaving_pattern[nonFrozenBit] <= polarParams->payloadBits) &&
					(aPrioriPayload[polarParams->interleaving_pattern[nonFrozenBit]] == 0) ) {
				//Information bit with known value of "0".
				updatePathMetric(pathMetric, llr, currentListSize, 0, currentBit, pathMetricAppr);
				bitUpdated[currentBit][0]=1; //0=False, 1=True
			} else if ( (polarParams->interleaving_pattern[nonFrozenBit] <= polarParams->payloadBits) &&
					(aPrioriPayload[polarParams->interleaving_pattern[nonFrozenBit]] == 1) ) {
				//Information bit with known value of "1".
				updatePathMetric(pathMetric, llr, currentListSize, 1, currentBit, pathMetricAppr);
				for (uint8_t i=0; i<currentListSize; i++) bit[currentBit][0][i]=1;
				bitUpdated[currentBit][0]=1;
				updateCrcChecksum(crcChecksum, extended_crc_generator_matrix, currentListSize, nonFrozenBit, polarParams->crcParityBits);
			} else {
				updatePathMetric2(pathMetric, llr, currentListSize, currentBit, pathMetricAppr);

				for (int i = 0; i < currentListSize; i++) {
					for (int j = 0; j < polarParams->N; j++) {
						for (int k = 0; k < (polarParams->n+1); k++) {
							bit[j][k][i+currentListSize]=bit[j][k][i];
							llr[j][k][i+currentListSize]=llr[j][k][i];}}}
				for (int i = 0; i < currentListSize; i++) {
					bit[currentBit][0][i]=0;
					crcState[i+currentListSize]=crcState[i];
				}
				for (int i = currentListSize; i < 2*currentListSize; i++) bit[currentBit][0][i]=1;
				bitUpdated[currentBit][0]=1;
				updateCrcChecksum2(crcChecksum, extended_crc_generator_matrix, currentListSize, nonFrozenBit, polarParams->crcParityBits);
				currentListSize*=2;

				//Keep only the best "listSize" number of entries.
				if (currentListSize > listSize) {
					for (uint8_t i = 0; i < 2*listSize; i++) listIndex[i]=i;
					nr_sort_asc_double_1D_array_ind(pathMetric, listIndex, currentListSize);

					//sort listIndex[listSize, ..., 2*listSize-1] in descending order.
					uint8_t swaps, tempInd;
					for (uint8_t i = 0; i < listSize; i++) {
						swaps = 0;
						for (uint8_t j = listSize; j < (2*listSize - i) - 1; j++) {
							if (listIndex[j+1] > listIndex[j]) {
								tempInd = listIndex[j];
								listIndex[j] = listIndex[j + 1];
								listIndex[j + 1] = tempInd;
								swaps++;
							}
						}
						if (swaps == 0)
							break;
					}

					//First, backup the best "listSize" number of entries.
					for (int k=(listSize-1); k>0; k--) {
						for (int i=0; i<polarParams->N; i++) {
							for (int j=0; j<(polarParams->n+1); j++) {
								bit[i][j][listIndex[(2*listSize-1)-k]]=bit[i][j][listIndex[k]];
								llr[i][j][listIndex[(2*listSize-1)-k]]=llr[i][j][listIndex[k]];
							}
						}
					}
					for (int k=(listSize-1); k>0; k--) {
						for (int i = 0; i < polarParams->crcParityBits; i++) {
							crcChecksum[i][listIndex[(2*listSize-1)-k]] = crcChecksum[i][listIndex[k]];
						}
					}
					for (int k=(listSize-1); k>0; k--) crcState[listIndex[(2*listSize-1)-k]]=crcState[listIndex[k]];

					//Copy the best "listSize" number of entries to the first indices.
					for (int k = 0; k < listSize; k++) {
						if (k > listIndex[k]) {
							copyIndex = listIndex[(2*listSize-1)-k];
						} else { //Use the backup.
							copyIndex = listIndex[k];
						}
						for (int i = 0; i < polarParams->N; i++) {
							for (int j = 0; j < (polarParams->n + 1); j++) {
								bit[i][j][k] = bit[i][j][copyIndex];
								llr[i][j][k] = llr[i][j][copyIndex];
							}
						}
					}
					for (int k = 0; k < listSize; k++) {
						if (k > listIndex[k]) {
							copyIndex = listIndex[(2*listSize-1)-k];
						} else { //Use the backup.
							copyIndex = listIndex[k];
						}
						for (int i = 0; i < polarParams->crcParityBits; i++) {
							crcChecksum[i][k]=crcChecksum[i][copyIndex];
						}
					}
					for (int k = 0; k < listSize; k++) {
						if (k > listIndex[k]) {
							copyIndex = listIndex[(2*listSize-1)-k];
						} else { //Use the backup.
							copyIndex = listIndex[k];
						}
						crcState[k]=crcState[copyIndex];
					}
					currentListSize = listSize;
				}
			}

			for (int i=0; i<polarParams->crcParityBits; i++) {
				if (last1ind[i]==nonFrozenBit) {
					checkCrcBits=i;
					break;
				}
			}

			if ( checkCrcBits > (-1) ) {
				for (uint8_t i = 0; i < currentListSize; i++) {
					if (crcChecksum[checkCrcBits][i]==1) {
						crcState[i]=0; //0=False, 1=True
					}
				}
			}

			for (uint8_t i = 0; i < currentListSize; i++) decoderIterationCheck+=crcState[i];
			if (decoderIterationCheck==0) {
				//perror("[SCL polar decoder] All list entries have failed the CRC checks.");
				free(d_tilde);
				free(pathMetric);
				free(crcState);
				nr_free_uint8_t_3D_array(bit, polarParams->N, (polarParams->n+1));
				nr_free_double_3D_array(llr, polarParams->N, (polarParams->n+1));
				nr_free_uint8_t_2D_array(crcChecksum, polarParams->crcParityBits);
				return(-1);
			}

			nonFrozenBit++;
			decoderIterationCheck=0;
			checkCrcBits=-1;
		}
	}

	for (uint8_t i = 0; i < 2*listSize; i++) listIndex[i]=i;
	nr_sort_asc_double_1D_array_ind(pathMetric, listIndex, currentListSize);

	for (uint8_t i = 0; i < fmin(listSize, (pow(2,polarParams->crcCorrectionBits)) ); i++) {
		if ( crcState[listIndex[i]] == 1 ) {
			for (int j = 0; j < polarParams->N; j++) polarParams->nr_polar_U[j]=bit[j][0][listIndex[i]];

			//Extract the information bits (û to ĉ)
			nr_polar_info_bit_extraction(polarParams->nr_polar_U, polarParams->nr_polar_CPrime, polarParams->information_bit_pattern, polarParams->N);

			//Deinterleaving (ĉ to b)
			nr_polar_deinterleaver(polarParams->nr_polar_CPrime, polarParams->nr_polar_B, polarParams->interleaving_pattern, polarParams->K);

			//Remove the CRC (â)
			for (int j = 0; j < polarParams->payloadBits; j++) polarParams->nr_polar_A[j]=polarParams->nr_polar_B[j];

			break;
		}
	}

	free(d_tilde);
	free(pathMetric);
	free(crcState);
	nr_free_uint8_t_3D_array(bit, polarParams->N, (polarParams->n+1));
	nr_free_double_3D_array(llr, polarParams->N, (polarParams->n+1));
	nr_free_uint8_t_2D_array(crcChecksum, polarParams->crcParityBits);
	nr_free_uint8_t_2D_array(extended_crc_generator_matrix, polarParams->K);
	nr_free_uint8_t_2D_array(tempECGM, polarParams->K);

	/*
	 * Return bits.
	 */
	nr_byte2bit_uint8_32_t(polarParams->nr_polar_A, polarParams->payloadBits, out);
	return(0);
}


int8_t polar_decoder_dci(double *input,
						 uint32_t *out,
						 t_nrPolar_paramsPtr polarParams,
						 uint8_t listSize,
						 uint8_t pathMetricAppr,
						 uint16_t n_RNTI)
{

	uint8_t ***bit = nr_alloc_uint8_t_3D_array(polarParams->N, (polarParams->n+1), 2*listSize);
	uint8_t **bitUpdated = nr_alloc_uint8_t_2D_array(polarParams->N, (polarParams->n+1)); //0=False, 1=True
	uint8_t **llrUpdated = nr_alloc_uint8_t_2D_array(polarParams->N, (polarParams->n+1)); //0=False, 1=True
	double ***llr = nr_alloc_double_3D_array(polarParams->N, (polarParams->n+1), 2*listSize);
	uint8_t **crcChecksum = nr_alloc_uint8_t_2D_array(polarParams->crcParityBits, 2*listSize);
	double *pathMetric = malloc(sizeof(double)*(2*listSize));
	uint8_t *crcState = malloc(sizeof(uint8_t)*(2*listSize)); //0=False, 1=True
	uint8_t extended_crc_scrambling_pattern[polarParams->crcParityBits];

	for (int i=0; i<(2*listSize); i++) {
		pathMetric[i] = 0;
		crcState[i]=1;
	}
	for (int i=0; i<polarParams->N; i++) {
		llrUpdated[i][polarParams->n]=1;
		bitUpdated[i][0]=((polarParams->information_bit_pattern[i]+1) % 2);
	}

	uint8_t **extended_crc_generator_matrix = malloc(polarParams->K * sizeof(uint8_t *)); //G_P3: K-by-P
	uint8_t **tempECGM = malloc(polarParams->K * sizeof(uint8_t *)); //G_P2: K-by-P
	for (int i = 0; i < polarParams->K; i++){
		extended_crc_generator_matrix[i] = malloc(polarParams->crcParityBits * sizeof(uint8_t));
		tempECGM[i] = malloc(polarParams->crcParityBits * sizeof(uint8_t));
	}

	for (int i=0; i<polarParams->payloadBits; i++) {
		for (int j=0; j<polarParams->crcParityBits; j++) {
			tempECGM[i][j]=polarParams->crc_generator_matrix[i+polarParams->crcParityBits][j];
		}
	}
	for (int i=polarParams->payloadBits; i<polarParams->K; i++) {
			for (int j=0; j<polarParams->crcParityBits; j++) {
				if( (i-polarParams->payloadBits) == j ){
					tempECGM[i][j]=1;
				} else {
					tempECGM[i][j]=0;
				}
			}
	}

	for (int i=0; i<polarParams->K; i++) {
		for (int j=0; j<polarParams->crcParityBits; j++) {
			extended_crc_generator_matrix[i][j]=tempECGM[polarParams->interleaving_pattern[i]][j];
		}
	}

	//The index of the last 1-valued bit that appears in each column.
	uint16_t last1ind[polarParams->crcParityBits];
	for (int j=0; j<polarParams->crcParityBits; j++) {
			for (int i=0; i<polarParams->K; i++) {
				if (extended_crc_generator_matrix[i][j]==1) last1ind[j]=i;
			}
	}

	for (int i=0;i<8;i++) extended_crc_scrambling_pattern[i]=0;
	for (int i=8; i<polarParams->crcParityBits; i++) {
		extended_crc_scrambling_pattern[i]=(n_RNTI>>(23-i))&1;
	}

	double *d_tilde = malloc(sizeof(double) * polarParams->N);
	nr_polar_rate_matching(input, d_tilde, polarParams->rate_matching_pattern, polarParams->K, polarParams->N, polarParams->encoderLength);
	for (int j = 0; j < polarParams->N; j++) llr[j][polarParams->n][0]=d_tilde[j];

	/*
	 * SCL polar decoder.
	 */

	for (int i=0; i<polarParams->crcParityBits; i++) {
		for (int j=0; j<polarParams->crcParityBits; j++) crcChecksum[i][0]=crcChecksum[i][0]+polarParams->crc_generator_matrix[j][i];
		crcChecksum[i][0]=(crcChecksum[i][0]%2);
	}

	uint32_t nonFrozenBit=0;
	uint8_t currentListSize=1;
	uint8_t decoderIterationCheck=0;
	int16_t checkCrcBits=-1;
	uint8_t listIndex[2*listSize], copyIndex;

	for (uint16_t currentBit=0; currentBit<polarParams->N; currentBit++){
		updateLLR(llr, llrUpdated, bit, bitUpdated, currentListSize, currentBit, 0, polarParams->N, (polarParams->n+1), pathMetricAppr);
		if (polarParams->information_bit_pattern[currentBit]==0) { //Frozen bit.
			updatePathMetric(pathMetric, llr, currentListSize, 0, currentBit, pathMetricAppr); //approximation=0 --> 11b, approximation=1 --> 12
		} else { //Information or CRC bit.
				updatePathMetric2(pathMetric, llr, currentListSize, currentBit, pathMetricAppr);

				for (int i = 0; i < currentListSize; i++) {
					for (int j = 0; j < polarParams->N; j++) {
						for (int k = 0; k < (polarParams->n+1); k++) {
							bit[j][k][i+currentListSize]=bit[j][k][i];
							llr[j][k][i+currentListSize]=llr[j][k][i];}}}
				for (int i = 0; i < currentListSize; i++) {
					bit[currentBit][0][i]=0;
					crcState[i+currentListSize]=crcState[i];
				}
				for (int i = currentListSize; i < 2*currentListSize; i++) bit[currentBit][0][i]=1;
				bitUpdated[currentBit][0]=1;
				updateCrcChecksum2(crcChecksum, extended_crc_generator_matrix, currentListSize, nonFrozenBit, polarParams->crcParityBits);
				currentListSize*=2;

				//Keep only the best "listSize" number of entries.
				if (currentListSize > listSize) {
					for (uint8_t i = 0; i < 2*listSize; i++) listIndex[i]=i;
					nr_sort_asc_double_1D_array_ind(pathMetric, listIndex, currentListSize);

					//sort listIndex[listSize, ..., 2*listSize-1] in descending order.
					uint8_t swaps, tempInd;
					for (uint8_t i = 0; i < listSize; i++) {
						swaps = 0;
						for (uint8_t j = listSize; j < (2*listSize - i) - 1; j++) {
							if (listIndex[j+1] > listIndex[j]) {
								tempInd = listIndex[j];
								listIndex[j] = listIndex[j + 1];
								listIndex[j + 1] = tempInd;
								swaps++;
							}
						}
						if (swaps == 0)
							break;
					}

					//First, backup the best "listSize" number of entries.
					for (int k=(listSize-1); k>0; k--) {
						for (int i=0; i<polarParams->N; i++) {
							for (int j=0; j<(polarParams->n+1); j++) {
								bit[i][j][listIndex[(2*listSize-1)-k]]=bit[i][j][listIndex[k]];
								llr[i][j][listIndex[(2*listSize-1)-k]]=llr[i][j][listIndex[k]];
							}
						}
					}
					for (int k=(listSize-1); k>0; k--) {
						for (int i = 0; i < polarParams->crcParityBits; i++) {
							crcChecksum[i][listIndex[(2*listSize-1)-k]] = crcChecksum[i][listIndex[k]];
						}
					}
					for (int k=(listSize-1); k>0; k--) crcState[listIndex[(2*listSize-1)-k]]=crcState[listIndex[k]];

					//Copy the best "listSize" number of entries to the first indices.
					for (int k = 0; k < listSize; k++) {
						if (k > listIndex[k]) {
							copyIndex = listIndex[(2*listSize-1)-k];
						} else { //Use the backup.
							copyIndex = listIndex[k];
						}
						for (int i = 0; i < polarParams->N; i++) {
							for (int j = 0; j < (polarParams->n + 1); j++) {
								bit[i][j][k] = bit[i][j][copyIndex];
								llr[i][j][k] = llr[i][j][copyIndex];
							}
						}
					}
					for (int k = 0; k < listSize; k++) {
						if (k > listIndex[k]) {
							copyIndex = listIndex[(2*listSize-1)-k];
						} else { //Use the backup.
							copyIndex = listIndex[k];
						}
						for (int i = 0; i < polarParams->crcParityBits; i++) {
							crcChecksum[i][k]=crcChecksum[i][copyIndex];
						}
					}
					for (int k = 0; k < listSize; k++) {
						if (k > listIndex[k]) {
							copyIndex = listIndex[(2*listSize-1)-k];
						} else { //Use the backup.
							copyIndex = listIndex[k];
						}
						crcState[k]=crcState[copyIndex];
					}
					currentListSize = listSize;
				}

			for (int i=0; i<polarParams->crcParityBits; i++) {
				if (last1ind[i]==nonFrozenBit) {
					checkCrcBits=i;
					break;
				}
			}

			if ( checkCrcBits > (-1) ) {
				for (uint8_t i = 0; i < currentListSize; i++) {
					if (crcChecksum[checkCrcBits][i]!=extended_crc_scrambling_pattern[checkCrcBits]) {
						crcState[i]=0; //0=False, 1=True
					}
				}
			}

			for (uint8_t i = 0; i < currentListSize; i++) decoderIterationCheck+=crcState[i];
			if (decoderIterationCheck==0) {
				//perror("[SCL polar decoder] All list entries have failed the CRC checks.");
				free(d_tilde);
				free(pathMetric);
				free(crcState);
				nr_free_uint8_t_3D_array(bit, polarParams->N, (polarParams->n+1));
				nr_free_double_3D_array(llr, polarParams->N, (polarParams->n+1));
				nr_free_uint8_t_2D_array(crcChecksum, polarParams->crcParityBits);
				return(-1);
			}

			nonFrozenBit++;
			decoderIterationCheck=0;
			checkCrcBits=-1;
		}
	}

	for (uint8_t i = 0; i < 2*listSize; i++) listIndex[i]=i;
	nr_sort_asc_double_1D_array_ind(pathMetric, listIndex, currentListSize);

	for (uint8_t i = 0; i < fmin(listSize, (pow(2,polarParams->crcCorrectionBits)) ); i++) {
		if ( crcState[listIndex[i]] == 1 ) {
			for (int j = 0; j < polarParams->N; j++) polarParams->nr_polar_U[j]=bit[j][0][listIndex[i]];

			//Extract the information bits (û to ĉ)
			nr_polar_info_bit_extraction(polarParams->nr_polar_U, polarParams->nr_polar_CPrime, polarParams->information_bit_pattern, polarParams->N);

			//Deinterleaving (ĉ to b)
			nr_polar_deinterleaver(polarParams->nr_polar_CPrime, polarParams->nr_polar_B, polarParams->interleaving_pattern, polarParams->K);

			//Remove the CRC (â)
			for (int j = 0; j < polarParams->payloadBits; j++) polarParams->nr_polar_A[j]=polarParams->nr_polar_B[j];

			break;
		}
	}

	free(d_tilde);
	free(pathMetric);
	free(crcState);
	nr_free_uint8_t_3D_array(bit, polarParams->N, (polarParams->n+1));
	nr_free_double_3D_array(llr, polarParams->N, (polarParams->n+1));
	nr_free_uint8_t_2D_array(crcChecksum, polarParams->crcParityBits);
	nr_free_uint8_t_2D_array(extended_crc_generator_matrix, polarParams->K);
	nr_free_uint8_t_2D_array(tempECGM, polarParams->K);

	/*
	 * Return bits.
	 */
	nr_byte2bit_uint8_32_t(polarParams->nr_polar_A, polarParams->payloadBits, out);
	return(0);
}


int8_t polar_decoder_int16(int16_t *input,
			   uint8_t *out,
			   t_nrPolar_params *polarParams)
{
  

  
  int16_t d_tilde[polarParams->N];// = malloc(sizeof(double) * polarParams->N);
  nr_polar_rate_matching_int16(input, d_tilde, polarParams->rate_matching_pattern, polarParams->K, polarParams->N, polarParams->encoderLength);
  for (int i=0;i<polarParams->N;i++) {
    if (d_tilde[i]<-128) d_tilde[i]=-128;
    else if (d_tilde[i]>127) d_tilde[i]=128;
  }
  memcpy((void*)&polarParams->tree.root->alpha[0],(void*)&d_tilde[0],sizeof(int16_t)*polarParams->N);
  
  /*
   * SCL polar decoder.
   */


  generic_polar_decoder(polarParams,polarParams->tree.root);


  //Extract the information bits (û to ĉ)
  nr_polar_info_bit_extraction(polarParams->nr_polar_U, polarParams->nr_polar_CPrime, polarParams->information_bit_pattern, polarParams->N);

  //Deinterleaving (ĉ to b)

  nr_polar_deinterleaver(polarParams->nr_polar_CPrime, polarParams->nr_polar_B, polarParams->interleaving_pattern, polarParams->K);

  //Remove the CRC (â)
  for (int j = 0; j < polarParams->payloadBits; j++) polarParams->nr_polar_A[j]=polarParams->nr_polar_B[j];  

  nr_byte2bit_uint8_32_t(polarParams->nr_polar_A, polarParams->payloadBits, out);
  
  return(0);
}