Algorithm-FEC
view release on metacpan or search on metacpan
Revision history for Perl extension Algorithm::FEC
1.1 Thu Nov 22 02:41:04 CET 2012
- apply fix for newer perl versions and additional testing patch by
Father Chrysostomos.
1.0 Sun Dec 23 16:43:02 CET 2007
- more small doc fixes.
- fix a crash occuring while generating an error message.
0.5 Mon Jun 21 15:06:15 CEST 2004
- check filesize and croak if mmap extends. also laid
the foundation for auto-extending short segments.
- small doc corrections by Jochen Stenzel.
0.4 Sat Sep 13 23:59:10 CEST 2003
- INCOMPATIBLE CHANGE: added shuffle, changed;
semantics of shuffled indices. (yes, I am trying
to get this right :)
void *mm;
if (fd <= 0)
croak ("invalid file descriptor for block #%d", idx);
mm = mmap (0, self->sz + (offset - ofs2),
rw ? PROT_READ | PROT_WRITE : PROT_READ,
MAP_SHARED, fd, ofs2);
if (mm == MAP_FAILED)
croak ("unable to mmap block #%d (wrong offset or size?): %s", idx, strerror (errno));
self->b_mmap[idx] = mm;
self->b_addr[idx] = (void *)((char *)mm + (offset - ofs2));
self->b_sz [idx] = self->sz + (offset - ofs2);
}
else if (sv)
self->b_sv[idx] = SvREFCNT_inc (sv);
else
croak ("unable to open block #%d, must be either string, filehandle, or [filehandle, offset]", idx);
}
{
SV **a, **b, **e, **f;
int d;
void *p;
SV *s;
int j = idx[i];
if (idx[j] == j)
{
Safefree (idx);
croak ("error while shuffling, duplicate indices?");
}
a = av_fetch ((AV *)SvRV (indices), i, 1);
b = av_fetch ((AV *)SvRV (indices), j, 1);
e = av_fetch ((AV *)SvRV (blocks ), i, 1);
f = av_fetch ((AV *)SvRV (blocks ), j, 1);
d = idx[i]; idx[i] = idx[j]; idx[j] = d;
s = *a; *a = *b; *b = s;
s = *e; *e = *f; *f = s;
/*
* fec.h -- forward error correction based on Vandermonde matrices
* 980614
* (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
* modified by Marc Lehmann <fec@schmorp.de>, Sep 2003.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
/*
* 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
* modified by Marc Lehmann <fec@schmorp.de>, Sep 2003.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* 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)
typedef uint8_t gf;
#else
typedef uint16_t gf;
#endif
#define GF_SIZE ((1 << GF_BITS) - 1) /* powers of \alpha */
/*
* (Gauss-Jordan, adapted from Numerical Recipes in C)
* Return non-zero if singular.
*/
DEB( int pivloops=0; int pivswaps=0 ; /* diagnostic */)
static int
invert_mat(gf *src, int k)
{
gf c, *p ;
int irow, icol, row, col, i, ix ;
int error = 1 ;
int *indxc = my_malloc(k*sizeof(int), "indxc");
int *indxr = my_malloc(k*sizeof(int), "indxr");
int *ipiv = my_malloc(k*sizeof(int), "ipiv");
gf *id_row = NEW_GF_MATRIX(1, k);
gf *temp_row = NEW_GF_MATRIX(1, k);
bzero(id_row, k*sizeof(gf));
DEB( pivloops=0; pivswaps=0 ; /* diagnostic */ )
/*
* ipiv marks elements already used as pivots.
fprintf(stderr, "AARGH, indxr[col] %d\n", indxr[col]);
else if (indxc[col] <0 || indxc[col] >= k)
fprintf(stderr, "AARGH, indxc[col] %d\n", indxc[col]);
else
if (indxr[col] != indxc[col] ) {
for (row = 0 ; row < k ; row++ ) {
SWAP( src[row*k + indxr[col]], src[row*k + indxc[col]], gf) ;
}
}
}
error = 0 ;
fail:
free(indxc);
free(indxr);
free(ipiv);
free(id_row);
free(temp_row);
return error ;
}
/*
* fast code for inverting a vandermonde matrix.
* XXX NOTE: It assumes that the matrix
* is not singular and _IS_ a vandermonde matrix. Only uses
* the second column of the matrix, containing the p_i's.
*
* Algorithm borrowed from "Numerical recipes in C" -- sec.2.8, but
* largely revised for my purposes.
for ( i = 0 ; i < k ; ) {
if (index[i] >= k || index[i] == i)
i++ ;
else {
/*
* put pkt in the right position (first check for conflicts).
*/
int c = index[i] ;
if (index[c] == c) {
DEB(fprintf(stderr, "\nshuffle, error at %d\n", i);)
return 1 ;
}
SWAP(index[i], index[c], int) ;
SWAP(pkt[i], pkt[c], gf *) ;
}
}
DEB( /* just test that it works... */
for ( i = 0 ; i < k ; i++ ) {
if (index[i] < k && index[i] != i) {
fprintf(stderr, "shuffle: after\n");
int
fec_decode(struct fec_parms *code, gf *pkt[], int index[], int sz)
{
gf *m_dec ;
gf **new_pkt ;
int row, col , k = code->k ;
if (GF_BITS > 8)
sz /= 2 ;
if (shuffle(pkt, index, k)) /* error if true */
return 1 ;
m_dec = build_decode_matrix(code, pkt, index);
if (m_dec == NULL)
return 1 ; /* error */
/*
* do the actual decoding
*/
new_pkt = my_malloc (k * sizeof (gf * ), "new pkt pointers" );
for (row = 0 ; row < k ; row++ ) {
if (index[row] >= k) {
new_pkt[row] = my_malloc (sz * sizeof (gf), "new pkt buffer" );
bzero(new_pkt[row], sz * sizeof(gf) ) ;
for (col = 0 ; col < k ; col++ )
addmul(new_pkt[row], pkt[col], m_dec[row*k + col], sz) ;
( run in 0.592 second using v1.01-cache-2.11-cpan-65fba6d93b7 )