block_code.h 4.96 KB
Newer Older
Andreas Schmidt's avatar
Andreas Schmidt committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58
/*
 * fec.c -- forward error correction based on Vandermonde matrices
 * 980624
 * (C) 1997-98 Luigi Rizzo (luigi@iet.unipi.it)
 *
 * Portions derived from code by Phil Karn (karn@ka9q.ampr.org),
 * Robert Morelos-Zaragoza (robert@spectra.eng.hawaii.edu) and Hari
 * Thirumoorthy (harit@spectra.eng.hawaii.edu), Aug 1995
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. 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.
 *
 * 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
 * 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.
 */

#ifndef PRRT_BLOCK_CODE_H
#define PRRT_BLOCK_CODE_H

#ifndef GF_BITS
#define GF_BITS  8      /* code over GF(2**GF_BITS) - change to suit */
#endif
#include <linux/types.h>
#include <stdint.h>

/*
 * You should not need to change anything beyond this point.
 * The first part of the file implements linear algebra in GF.
 *
 * gf is the type used to store an element of the Galois Field.
 * Must constain at least GF_BITS bits.
 *
 * Note: unsigned char will work up to GF(256) but int seems to run
 * faster on the Pentium. We use int whenever have to deal with an
 * index, since they are generally faster.
 */
#if (GF_BITS < 2 || GF_BITS >16)
#error "GF_BITS must be 2 .. 16"
#endif
#if (GF_BITS <= 8)
59
typedef uint8_t gf;
Andreas Schmidt's avatar
Andreas Schmidt committed
60
#else
61
typedef uint16_t gf;
Andreas Schmidt's avatar
Andreas Schmidt committed
62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79
#endif

#define GF_SIZE ((1 << GF_BITS) - 1)    /* powers of \alpha */
#define FEC_MAGIC 0xFECC0DEC

/**
 * Struct holding parameters for a coder.
 */
struct FecParams {
    uint64_t magic;
    int k, n;          /* parameters of the code */
    gf *enc_matrix;
};

/**
 * This struture contains the members for a coder that can en/decode.
 * To change the code you need to free the old coder and allocate a new one.
 */
80
typedef struct prrtCoder {
Andreas Schmidt's avatar
Andreas Schmidt committed
81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98
    struct FecParams params;
    gf gf_exp[2*GF_SIZE];	/* index->poly form conversion table	*/
    int gf_log[GF_SIZE + 1];/* Poly->index form conversion table	*/
    gf inverse[GF_SIZE+1];	/* inverse of field elem.		*/
    /* inv[\alpha**i]=\alpha**(GF_SIZE-i-1)	*/
#if (GF_BITS <= 8)
    gf gf_mul_table[GF_SIZE + 1][GF_SIZE + 1];
#endif
    int count_num;
    uint64_t tot_encoding_time;
} PrrtCoder;

/**
 * This functions updates the coder with the new parameters.
 * \param k number of data packets in one block
 * \param n overall number of packets in one block
 * \return 0 on success, -1 if parameters are invalid, -2 if no memory
 */
99
int PrrtCoder_get_coder(PrrtCoder **cod, uint8_t n, uint8_t k);
Andreas Schmidt's avatar
Andreas Schmidt committed
100 101 102 103 104 105 106 107 108 109 110

/**
 * Free the coder object.
 */
void PrrtCoder_destroy(PrrtCoder *cod) ;

/**
 * This function creates an encoded packet from some given packets.
 * We are using a (k,n) systematic block code. This function takes k packets as source (the first
 * k) and creates one of the n-k remaining packets. Index is the number of the packet and therefore
 * lies between k and n (k <= index < n).
Andreas Schmidt's avatar
Andreas Schmidt committed
111 112 113 114
 * \param src: an array of pointers to the source packets.
 * \param dst: the pointer to a previously allocated space for the new packet.
 * \param index: this is the position of the new packet in the resulting set of encoded packets.
 * \param sz: the size of the packets that should be encoded.
Andreas Schmidt's avatar
Andreas Schmidt committed
115 116 117 118 119 120 121 122 123 124
 */
void PrrtCoder_encode(PrrtCoder *cod, gf **src, gf *dst, int index, int sz) ;

/**
 * This function decodes a set of packets.
 * It takes a set of packets that is given as an array of pointers to the packets. Because this
 * is an (k,n) systematic code there have to be k pointers in the array. If data packet i(< k) is
 * present it should be at position i-1 (e.g. packet 1 at 0, 2 at 1) and index[i-1] should be set
 * to i-1. If data packet i is not present, but replacement packet (k < )j(<= n) is present, its
 * data can be pointed to at pkt[i-1]. Index[i-1] should then be set to j-1.
Andreas Schmidt's avatar
Andreas Schmidt committed
125 126 127
 * \param pkt: these are the pointers to the data of the different packets.
 * \param index: this is the position of the packets in the block code.
 * \param sz: the size of the data of the packets.
Andreas Schmidt's avatar
Andreas Schmidt committed
128 129 130 131
 */
int PrrtCoder_decode(PrrtCoder *cod, gf **pkt, int *index, int sz) ;

#endif //PRRT_BLOCK_CODE_H