Module Name: othersrc
Committed By: agc
Date: Wed Mar 23 03:17:48 UTC 2011
Modified Files:
othersrc/external/bsd/rs/dist: librs.3 main.c rs.c rs.h
othersrc/external/bsd/rs/librs: shlib_version
othersrc/external/bsd/rs/rs: Makefile
Log Message:
+ add code to store the encoding parameters in the generated output
+ use the encoding parameters at decode time
+ add a test for non-standard encoding values
+ update manual page to incorporate some feedback from David Young - more
to come
+ bring manual page up to date
+ bump shlib major number
To generate a diff of this commit:
cvs rdiff -u -r1.1.1.1 -r1.2 othersrc/external/bsd/rs/dist/librs.3 \
othersrc/external/bsd/rs/dist/rs.c othersrc/external/bsd/rs/dist/rs.h
cvs rdiff -u -r1.4 -r1.5 othersrc/external/bsd/rs/dist/main.c
cvs rdiff -u -r1.1.1.1 -r1.2 othersrc/external/bsd/rs/librs/shlib_version
cvs rdiff -u -r1.1.1.1 -r1.2 othersrc/external/bsd/rs/rs/Makefile
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: othersrc/external/bsd/rs/dist/librs.3
diff -u othersrc/external/bsd/rs/dist/librs.3:1.1.1.1 othersrc/external/bsd/rs/dist/librs.3:1.2
--- othersrc/external/bsd/rs/dist/librs.3:1.1.1.1 Sat Mar 12 08:08:29 2011
+++ othersrc/external/bsd/rs/dist/librs.3 Wed Mar 23 03:17:48 2011
@@ -1,4 +1,4 @@
-.\" $NetBSD: librs.3,v 1.1.1.1 2011/03/12 08:08:29 agc Exp $
+.\" $NetBSD: librs.3,v 1.2 2011/03/23 03:17:48 agc Exp $
.\"
.\" Copyright (c) 2011 Alistair Crooks <[email protected]>
.\" All rights reserved.
@@ -23,12 +23,12 @@
.\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
.\" THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
.\"/
-.Dd March 9, 2011
+.Dd March 22, 2011
.Dt LIBRS 3
.Os
.Sh NAME
.Nm librs
-.Nd reed-solomon erasure code library
+.Nd Reed-Solomon forward erasure code library
.Sh LIBRARY
.Lb librs
.Sh SYNOPSIS
@@ -46,6 +46,14 @@
.Fo rs_decode
.Fa "rs_t *rs" "const void *input" "size_t insize" "uint8_t *output" "size_t outsize"
.Fc
+.Ft ssize_t
+.Fo rs_get_header
+.Fa "rs_t *rs" "void *input" "size_t size"
+.Fc
+.Ft ssize_t
+.Fo rs_put_header
+.Fa "rs_t *rs" "const void *input" "size_t size"
+.Fc
.Sh DESCRIPTION
The
.Nm
@@ -86,6 +94,30 @@
function, the output will be split up into slices of
256 bytes, and the final buffer may contain less than
256 bytes.
+.Pp
+The
+.Fn rs_put_header
+function is used to store information about the encoding in
+the output that is generated. This will allow a future call
+of the
+.Fn rs_decode
+function to know the exact coding parameters in order to reconstruct
+the original data, by using the
+.Fn rs_get_header
+function.
+.Pp
+The output size from the
+.Fn rs_encode
+function depends on the number of parity bytes, and the number of
+data bytes used.
+In addition, there is an overhead of 12 bytes to hold the
+encoding information.
+For example, a
+.Dv 28,24
+encoding will use 4 parity bytes for every 24 data bytes.
+This means that the output will be at least
+.Dv (((datasize / 6) + 1) * 7) + 12
+bytes long.
.Sh HISTORY
The
.Nm
Index: othersrc/external/bsd/rs/dist/rs.c
diff -u othersrc/external/bsd/rs/dist/rs.c:1.1.1.1 othersrc/external/bsd/rs/dist/rs.c:1.2
--- othersrc/external/bsd/rs/dist/rs.c:1.1.1.1 Sat Mar 12 08:08:29 2011
+++ othersrc/external/bsd/rs/dist/rs.c Wed Mar 23 03:17:48 2011
@@ -63,6 +63,8 @@
#define USE_ARG(x) /*LINTED*/(void)&(x)
#endif
+#define RS_MAGIC "rs1"
+
/* set up the gf8 tables */
static int
galois_inits(const unsigned poly)
@@ -208,9 +210,9 @@
uint8_t product[MAX_DEGREE * 2];
int i;
- poly_mult(product, rs->lambda, rs->syndrome, rs->parityc * 2);
- poly_zero(rs->omega, rs->parityc * 2);
- for (i = 0; i < rs->parityc; i++) {
+ poly_mult(product, rs->lambda, rs->syndrome, rs->header.parityc * 2);
+ poly_zero(rs->omega, rs->header.parityc * 2);
+ for (i = 0; i < rs->header.parityc; i++) {
rs->omega[i] = product[i];
}
}
@@ -264,36 +266,36 @@
int n;
/* initialize Gamma, the erasure locator polynomial */
- init_gamma(rs, gamma, rs->parityc * 2);
+ init_gamma(rs, gamma, rs->header.parityc * 2);
/* initialize to z */
- (void) memcpy(D, gamma, rs->parityc * 2);
- poly_mul_z(D, rs->parityc * 2);
+ (void) memcpy(D, gamma, rs->header.parityc * 2);
+ poly_mul_z(D, rs->header.parityc * 2);
- (void) memcpy(psi, gamma, rs->parityc * 2);
+ (void) memcpy(psi, gamma, rs->header.parityc * 2);
k = -1;
- for (L = n = 0; n < rs->parityc; n++) {
+ for (L = n = 0; n < rs->header.parityc; n++) {
if ((d = compute_discrepancy(psi, rs->syndrome, L, n)) != 0) {
/* psi2 = psi - d*D */
- for (i = 0; i < rs->parityc * 2; i++) {
+ for (i = 0; i < rs->header.parityc * 2; i++) {
psi2[i] = psi[i] ^ gfmult(d, D[i]);
}
if (L < (n - k)) {
L2 = n - k;
k = n - L;
/* D = poly_scale(psi, gfinv(d), rs->parityc * 2); */
- for (i = 0; i < rs->parityc * 2; i++) {
+ for (i = 0; i < rs->header.parityc * 2; i++) {
D[i] = gfmult(psi[i], gfinv(d));
}
L = L2;
}
/* psi = psi2 */
- (void) memcpy(psi, psi2, rs->parityc * 2);
+ (void) memcpy(psi, psi2, rs->header.parityc * 2);
}
- poly_mul_z(D, rs->parityc * 2);
+ poly_mul_z(D, rs->header.parityc * 2);
}
- (void) memcpy(rs->lambda, psi, rs->parityc * 2);
+ (void) memcpy(rs->lambda, psi, rs->header.parityc * 2);
compute_modified_omega(rs);
}
@@ -314,7 +316,7 @@
for (rs->nerrors = 0, r = 1; r < MAX_GF8; r++) {
/* evaluate lambda at r */
- for (sum = 0, k = 0; k < rs->parityc + 1; k++) {
+ for (sum = 0, k = 0; k < rs->header.parityc + 1; k++) {
sum ^= gfmult(gfexp[(k * r) % (MAX_GF8 - 1)], rs->lambda[k]);
}
if (sum == 0) {
@@ -373,7 +375,7 @@
Modified_Berlekamp_Massey(rs);
find_roots(rs);
- if ((rs->nerrors <= rs->parityc) && rs->nerrors > 0) {
+ if ((rs->nerrors <= rs->header.parityc) && rs->nerrors > 0) {
/* first check for illegal error locs */
for (r = 0; r < rs->nerrors; r++) {
if (rs->errorlocs[r] >= size) {
@@ -391,7 +393,7 @@
/* evaluate Omega at alpha^(-i) */
num = 0;
- for (j = 0; j < rs->parityc * 2; j++) {
+ for (j = 0; j < rs->header.parityc * 2; j++) {
num ^= gfmult(rs->omega[j], gfexp[((MAX_GF8 - 1 - i) * j) % (MAX_GF8 - 1)]);
}
/*
@@ -399,7 +401,7 @@
* odd powers disappear
*/
denom = 0;
- for (j = 1; j < rs->parityc * 2; j += 2) {
+ for (j = 1; j < rs->header.parityc * 2; j += 2) {
denom ^= gfmult(rs->lambda[j], gfexp[((MAX_GF8 - 1 - i) * (j - 1)) % (MAX_GF8 - 1)]);
}
err = gfmult(num, gfinv(denom));
@@ -423,7 +425,7 @@
{
int i;
- for (i = 0; i < rs->parityc; i++) {
+ for (i = 0; i < rs->header.parityc; i++) {
if (rs->syndrome[i] != 0) {
return 1;
}
@@ -449,17 +451,17 @@
(void) memset(lfsr, 0x0, sizeof(lfsr));
for (i = 0; i < size; i++) {
- dbyte = msg[i] ^ lfsr[rs->parityc - 1];
- for (j = rs->parityc - 1; j > 0; j--) {
+ dbyte = msg[i] ^ lfsr[rs->header.parityc - 1];
+ for (j = rs->header.parityc - 1; j > 0; j--) {
lfsr[j] = lfsr[j - 1] ^ gfmult(rs->genPoly[j], dbyte);
}
lfsr[0] = gfmult(rs->genPoly[0], dbyte);
}
(void) memcpy(dst, msg, size);
- for (i = 0; i < rs->parityc; i++) {
- dst[size + i] = lfsr[rs->parityc - 1 - i];
+ for (i = 0; i < rs->header.parityc; i++) {
+ dst[size + i] = lfsr[rs->header.parityc - 1 - i];
}
- return size + rs->parityc;
+ return size + rs->header.parityc;
}
/* decode one chunk of the input */
@@ -471,7 +473,7 @@
int j;
(void) memcpy(dst, in, size);
- for (j = 0; j < rs->parityc; j++) {
+ for (j = 0; j < rs->header.parityc; j++) {
for (sum = 0, i = 0; i < size; i++) {
sum = dst[i] ^ gfmult(gfexp[j + 1], sum);
}
@@ -480,7 +482,21 @@
if (nonzero_syndrome(rs) && !correct_errors(rs, dst, size)) {
return -1;
}
- return size - rs->parityc;
+ return size - rs->header.parityc;
+}
+
+#define BSWAP32(x) ((((x) & 0xff) << 24) | \
+ (((x) & 0xff00) << 8) | \
+ (((x) & 0xff0000) >> 8) | \
+ (((x) & 0xff000000) >> 24))
+
+/* byte-swap 32 bits, if necessary, to get little-endian */
+static uint32_t
+le32(uint32_t in)
+{
+ int indian = 1;
+
+ return (*(char *)(void *)&indian) ? in : BSWAP32(in);
}
/****************************************************************************/
@@ -502,13 +518,13 @@
return 0;
}
(void) memset(rs, 0x0, sizeof(*rs));
- rs->poly = poly;
- rs->datac = databytes;
- rs->parityc = paritybytes;
+ rs->header.poly = poly;
+ rs->header.datac = databytes;
+ rs->header.parityc = paritybytes;
/* Initialize the galois field arithmetic tables */
galois_inits(poly);
/* Compute the encoder generator polynomial */
- compute_genpoly(rs->parityc, rs->genPoly, rs->parityc * 2);
+ compute_genpoly(rs->header.parityc, rs->genPoly, rs->header.parityc * 2);
return 1;
}
@@ -521,11 +537,11 @@
size_t incc;
size_t chunk;
- if (!rs->poly) {
+ if (!rs->header.poly) {
rs_init(rs, RS_DEFAULT_POLYNOMIAL, RS_DEFAULT_DATA, RS_DEFAULT_PARITY);
}
for (outcc = 0, incc = 0 ; incc < size && outcc < outsize ; incc += chunk) {
- chunk = MIN(size - incc, rs->datac);
+ chunk = MIN(size - incc, rs->header.datac);
outcc += encode_chunk(rs, &in[incc], chunk, &out[outcc]);
}
return (ssize_t)outcc;
@@ -541,11 +557,8 @@
size_t incc;
size_t chunk;
- if (!rs->poly) {
- rs_init(rs, RS_DEFAULT_POLYNOMIAL, RS_DEFAULT_DATA, RS_DEFAULT_PARITY);
- }
for (outcc = 0, incc = 0 ; incc < size && outcc < (ssize_t)outsize ; incc += chunk) {
- chunk = MIN(size - incc, rs->datac + rs->parityc);
+ chunk = MIN(size - incc, rs->header.datac + rs->header.parityc);
if ((cc = decode_chunk(rs, &in[incc], chunk, &out[outcc])) < 0) {
break;
}
@@ -553,3 +566,30 @@
}
return outcc;
}
+
+/* get a header from an area of memory */
+ssize_t
+rs_get_header(rs_t *rs, const void *in, size_t insize)
+{
+ rs_header_t head;
+
+ USE_ARG(insize);
+ (void) memcpy(&head, in, sizeof(head));
+ head.poly = le32(head.poly);
+ (void) memcpy(&rs->header, &head, sizeof(rs->header));
+ return sizeof(rs->header);
+}
+
+/* put a header into an area of memory */
+ssize_t
+rs_put_header(rs_t *rs, void *out, size_t outsize)
+{
+ rs_header_t head;
+
+ USE_ARG(outsize);
+ (void) memcpy(&head, &rs->header, sizeof(head));
+ (void) snprintf(head.magic, sizeof(head.magic), "%s", RS_MAGIC);
+ head.poly = le32(head.poly);
+ (void) memcpy(out, &head, sizeof(head));
+ return sizeof(head);
+}
Index: othersrc/external/bsd/rs/dist/rs.h
diff -u othersrc/external/bsd/rs/dist/rs.h:1.1.1.1 othersrc/external/bsd/rs/dist/rs.h:1.2
--- othersrc/external/bsd/rs/dist/rs.h:1.1.1.1 Sat Mar 12 08:08:29 2011
+++ othersrc/external/bsd/rs/dist/rs.h Wed Mar 23 03:17:48 2011
@@ -33,6 +33,15 @@
#include <inttypes.h>
+typedef struct rs_header_t {
+ char magic[4]; /* magic number */
+ uint32_t poly; /* polynomial used */
+ uint8_t datac; /* # of data bytes per packet */
+ uint8_t parityc; /* # of parity bytes per packet */
+ uint8_t interleave; /* interleave signature */
+ uint8_t convolution; /* convolution factor */
+} rs_header_t;
+
typedef struct rs_t {
uint8_t syndrome[256]; /* Decoder syndrome bytes */
uint8_t genPoly[256 * 2]; /* generator polynomial */
@@ -44,9 +53,7 @@
/* error locations found using Chien's search */
int nerrors;
uint8_t errorlocs[256];
- unsigned poly; /* polynomial */
- uint8_t datac; /* # of data bytes */
- uint8_t parityc; /* # of parity bytes */
+ rs_header_t header; /* header for transportation */
} rs_t;
enum {
@@ -61,9 +68,15 @@
RS_DEFAULT_PARITY = 32
};
-/* Reed Solomon encode/decode routines */
+/* initialisations */
int rs_init(rs_t *, const unsigned, const uint8_t, const uint8_t);
+
+/* Reed Solomon encode/decode routines */
ssize_t rs_decode(rs_t *, const void *, size_t, uint8_t *, size_t);
ssize_t rs_encode(rs_t *, const void *, size_t, uint8_t *, size_t);
+/* Reed Solomon header routines */
+ssize_t rs_get_header(rs_t *, const void *, size_t);
+ssize_t rs_put_header(rs_t *, void *, size_t);
+
#endif
Index: othersrc/external/bsd/rs/dist/main.c
diff -u othersrc/external/bsd/rs/dist/main.c:1.4 othersrc/external/bsd/rs/dist/main.c:1.5
--- othersrc/external/bsd/rs/dist/main.c:1.4 Fri Mar 18 23:59:55 2011
+++ othersrc/external/bsd/rs/dist/main.c Wed Mar 23 03:17:48 2011
@@ -44,9 +44,9 @@
{
uint8_t buf[256];
uint8_t out[256];
+ size_t readsize;
FILE *fpout;
FILE *fpin;
- size_t readsize;
int outcc;
int cc;
int ok;
@@ -66,7 +66,23 @@
}
return 0;
}
- readsize = (encoding) ? data : data + parity;
+ if (encoding) {
+ /* copy the encoding paramters to output */
+ readsize = data;
+ outcc = rs_put_header(rs, out, sizeof(out));
+ if (write(fileno(fpout), out, outcc) != outcc) {
+ (void) fprintf(stderr, "short write\n");
+ return 0;
+ }
+ } else {
+ /* read the encoding paramters from input */
+ if (read(fileno(fpin), &rs->header, sizeof(rs->header)) != sizeof(rs->header)) {
+ (void) fprintf(stderr, "short read\n");
+ return 0;
+ }
+ rs_get_header(rs, &rs->header, sizeof(rs->header));
+ readsize = rs->header.datac + rs->header.parityc;
+ }
for (ok = 1 ; ok && (cc = read(fileno(fpin), buf, readsize)) > 0 ; ) {
if (encoding) {
outcc = rs_encode(rs, buf, cc, out, sizeof(out));
Index: othersrc/external/bsd/rs/librs/shlib_version
diff -u othersrc/external/bsd/rs/librs/shlib_version:1.1.1.1 othersrc/external/bsd/rs/librs/shlib_version:1.2
--- othersrc/external/bsd/rs/librs/shlib_version:1.1.1.1 Sat Mar 12 08:08:29 2011
+++ othersrc/external/bsd/rs/librs/shlib_version Wed Mar 23 03:17:48 2011
@@ -1,2 +1,2 @@
-major=0
+major=1
minor=0
Index: othersrc/external/bsd/rs/rs/Makefile
diff -u othersrc/external/bsd/rs/rs/Makefile:1.1.1.1 othersrc/external/bsd/rs/rs/Makefile:1.2
--- othersrc/external/bsd/rs/rs/Makefile:1.1.1.1 Sat Mar 12 08:08:29 2011
+++ othersrc/external/bsd/rs/rs/Makefile Wed Mar 23 03:17:48 2011
@@ -1,4 +1,4 @@
-# $NetBSD: Makefile,v 1.1.1.1 2011/03/12 08:08:29 agc Exp $
+# $NetBSD: Makefile,v 1.2 2011/03/23 03:17:48 agc Exp $
.include <bsd.own.mk>
@@ -33,3 +33,7 @@
cmp a a3; \
rm -f a a2 a3; \
done
+ ./${PROG} -o a2 -p 28,24 Makefile
+ ./${PROG} -d -o a3 a2
+ diff Makefile a3
+ rm -f a2 a3
