zfec/zfec/fec.c

   1 /**
   2  * zfec -- fast forward error correction library with Python interface
   3  */
   4
   5 #include <stdio.h>
   6 #include <stdlib.h>
   7 #include <string.h>
   8 #include <assert.h>
   9
  10 #include "fec.h"
  11
  12
  13 /*
  14  * If you get a error returned (negative value) from a fec_* function,
  15  * look in here for the error message.
  16  */
  17
  18 #define FEC_ERROR_SIZE 1025
  19 char fec_error[FEC_ERROR_SIZE+1];
  20
  21 #define ERR(...) (snprintf(fec_error, FEC_ERROR_SIZE, __VA_ARGS__))
  22
  23 /*
  24  * Primitive polynomials - see Lin & Costello, Appendix A,
  25  * and  Lee & Messerschmitt, p. 453.
  26  */
  27 static const char*const Pp="101110001";
  28
  29
  30 /*
  31  * To speed up computations, we have tables for logarithm, exponent and
  32  * inverse of a number.  We use a table for multiplication as well (it takes
  33  * 64K, no big deal even on a PDA, especially because it can be
  34  * pre-initialized an put into a ROM!), otherwhise we use a table of
  35  * logarithms. In any case the macro gf_mul(x,y) takes care of
  36  * multiplications.
  37  */
  38
  39 static gf gf_exp[510];  /* index->poly form conversion table    */
  40 static int gf_log[256]; /* Poly->index form conversion table    */
  41 static gf inverse[256]; /* inverse of field elem.               */
  42                                 /* inv[\alpha**i]=\alpha**(GF_SIZE-i-1) */
  43
  44 /*
  45  * modnn(x) computes x % GF_SIZE, where GF_SIZE is 2**GF_BITS - 1,
  46  * without a slow divide.
  47  */
  48 static inline gf
  49 modnn(int x) {
  50     while (x >= 255) {
  51         x -= 255;
  52         x = (x >> 8) + (x & 255);
  53     }
  54     return x;
  55 }
  56
  57 #define SWAP(a,b,t) {t tmp; tmp=a; a=b; b=tmp;}
  58
  59 /*
  60  * gf_mul(x,y) multiplies two numbers.  It is much faster to use a
  61  * multiplication table.
  62  *
  63  * USE_GF_MULC, GF_MULC0(c) and GF_ADDMULC(x) can be used when multiplying
  64  * many numbers by the same constant. In this case the first call sets the
  65  * constant, and others perform the multiplications.  A value related to the
  66  * multiplication is held in a local variable declared with USE_GF_MULC . See
  67  * usage in _addmul1().
  68  */
  69 static gf gf_mul_table[256][256];
  70
  71 #define gf_mul(x,y) gf_mul_table[x][y]
  72
  73 #define USE_GF_MULC register gf * __gf_mulc_
  74 #define GF_MULC0(c) __gf_mulc_ = gf_mul_table[c]
  75 #define GF_ADDMULC(dst, x) dst ^= __gf_mulc_[x]
  76
  77 /*
  78  * Generate GF(2**m) from the irreducible polynomial p(X) in p[0]..p[m]
  79  * Lookup tables:
  80  *     index->polynomial form           gf_exp[] contains j= \alpha^i;
  81  *     polynomial form -> index form    gf_log[ j = \alpha^i ] = i
  82  * \alpha=x is the primitive element of GF(2^m)
  83  *
  84  * For efficiency, gf_exp[] has size 2*GF_SIZE, so that a simple
  85  * multiplication of two numbers can be resolved without calling modnn
  86  */
  87 static void
  88 _init_mul_table(void) {
  89   int i, j;
  90   for (i = 0; i < 256; i++)
  91       for (j = 0; j < 256; j++)
  92           gf_mul_table[i][j] = gf_exp[modnn (gf_log[i] + gf_log[j])];
  93
  94   for (j = 0; j < 256; j++)
  95       gf_mul_table[0][j] = gf_mul_table[j][0] = 0;
  96 }
  97
  98 /*
  99  * i use malloc so many times, it is easier to put checks all in
 100  * one place.
 101  */
 102 static void *
 103 my_malloc (int sz, char *err_string) {
 104     void *p = malloc (sz);
 105     if (p == NULL) {
 106         ERR("Malloc failure allocating %s\n", err_string);
 107         exit (1);
 108     }
 109     return p;
 110 }
 111
 112 #define NEW_GF_MATRIX(rows, cols) \
 113     (gf*)my_malloc(rows * cols, " ## __LINE__ ## " )
 114
 115 /*
 116  * initialize the data structures used for computations in GF.
 117  */
 118 static void
 119 generate_gf (void) {
 120     int i;
 121     gf mask;
 122
 123     mask = 1;                     /* x ** 0 = 1 */
 124     gf_exp[8] = 0;          /* will be updated at the end of the 1st loop */
 125     /*
 126      * first, generate the (polynomial representation of) powers of \alpha,
 127      * which are stored in gf_exp[i] = \alpha ** i .
 128      * At the same time build gf_log[gf_exp[i]] = i .
 129      * The first 8 powers are simply bits shifted to the left.
 130      */
 131     for (i = 0; i < 8; i++, mask <<= 1) {
 132         gf_exp[i] = mask;
 133         gf_log[gf_exp[i]] = i;
 134         /*
 135          * If Pp[i] == 1 then \alpha ** i occurs in poly-repr
 136          * gf_exp[8] = \alpha ** 8
 137          */
 138         if (Pp[i] == '1')
 139             gf_exp[8] ^= mask;
 140     }
 141     /*
 142      * now gf_exp[8] = \alpha ** 8 is complete, so can also
 143      * compute its inverse.
 144      */
 145     gf_log[gf_exp[8]] = 8;
 146     /*
 147      * Poly-repr of \alpha ** (i+1) is given by poly-repr of
 148      * \alpha ** i shifted left one-bit and accounting for any
 149      * \alpha ** 8 term that may occur when poly-repr of
 150      * \alpha ** i is shifted.
 151      */
 152     mask = 1 << 7;
 153     for (i = 9; i < 255; i++) {
 154         if (gf_exp[i - 1] >= mask)
 155             gf_exp[i] = gf_exp[8] ^ ((gf_exp[i - 1] ^ mask) << 1);
 156         else
 157             gf_exp[i] = gf_exp[i - 1] << 1;
 158         gf_log[gf_exp[i]] = i;
 159     }
 160     /*
 161      * log(0) is not defined, so use a special value
 162      */
 163     gf_log[0] = 255;
 164     /* set the extended gf_exp values for fast multiply */
 165     for (i = 0; i < 255; i++)
 166         gf_exp[i + 255] = gf_exp[i];
 167
 168     /*
 169      * again special cases. 0 has no inverse. This used to
 170      * be initialized to 255, but it should make no difference
 171      * since noone is supposed to read from here.
 172      */
 173     inverse[0] = 0;
 174     inverse[1] = 1;
 175     for (i = 2; i <= 255; i++)
 176         inverse[i] = gf_exp[255 - gf_log[i]];
 177 }
 178
 179 /*
 180  * Various linear algebra operations that i use often.
 181  */
 182
 183 /*
 184  * addmul() computes dst[] = dst[] + c * src[]
 185  * This is used often, so better optimize it! Currently the loop is
 186  * unrolled 16 times, a good value for 486 and pentium-class machines.
 187  * The case c=0 is also optimized, whereas c=1 is not. These
 188  * calls are unfrequent in my typical apps so I did not bother.
 189  */
 190 #define addmul(dst, src, c, sz)                 \
 191     if (c != 0) _addmul1(dst, src, c, sz)
 192
 193 #define UNROLL 16               /* 1, 4, 8, 16 */
 194 static void
 195 _addmul1(register gf*restrict dst, const register gf*restrict src, gf c, size_t sz) {
 196     USE_GF_MULC;
 197     const gf* lim = &dst[sz - UNROLL + 1];
 198
 199     GF_MULC0 (c);
 200
 201 #if (UNROLL > 1)                /* unrolling by 8/16 is quite effective on the pentium */
 202     for (; dst < lim; dst += UNROLL, src += UNROLL) {
 203         GF_ADDMULC (dst[0], src[0]);
 204         GF_ADDMULC (dst[1], src[1]);
 205         GF_ADDMULC (dst[2], src[2]);
 206         GF_ADDMULC (dst[3], src[3]);
 207 #if (UNROLL > 4)
 208         GF_ADDMULC (dst[4], src[4]);
 209         GF_ADDMULC (dst[5], src[5]);
 210         GF_ADDMULC (dst[6], src[6]);
 211         GF_ADDMULC (dst[7], src[7]);
 212 #endif
 213 #if (UNROLL > 8)
 214         GF_ADDMULC (dst[8], src[8]);
 215         GF_ADDMULC (dst[9], src[9]);
 216         GF_ADDMULC (dst[10], src[10]);
 217         GF_ADDMULC (dst[11], src[11]);
 218         GF_ADDMULC (dst[12], src[12]);
 219         GF_ADDMULC (dst[13], src[13]);
 220         GF_ADDMULC (dst[14], src[14]);
 221         GF_ADDMULC (dst[15], src[15]);
 222 #endif
 223     }
 224 #endif
 225     lim += UNROLL - 1;
 226     for (; dst < lim; dst++, src++)       /* final components */
 227         GF_ADDMULC (*dst, *src);
 228 }
 229
 230 /*
 231  * computes C = AB where A is n*k, B is k*m, C is n*m
 232  */
 233 static void
 234 _matmul(gf * a, gf * b, gf * c, unsigned n, unsigned k, unsigned m) {
 235     unsigned row, col, i;
 236
 237     for (row = 0; row < n; row++) {
 238         for (col = 0; col < m; col++) {
 239             gf *pa = &a[row * k];
 240             gf *pb = &b[col];
 241             gf acc = 0;
 242             for (i = 0; i < k; i++, pa++, pb += m)
 243                 acc ^= gf_mul (*pa, *pb);
 244             c[row * m + col] = acc;
 245         }
 246     }
 247 }
 248
 249 /*
 250  * _invert_mat() takes a matrix and produces its inverse
 251  * k is the size of the matrix.
 252  * (Gauss-Jordan, adapted from Numerical Recipes in C)
 253  * Return non-zero if singular.
 254  */
 255 static void
 256 _invert_mat(gf* src, unsigned k) {
 257     gf c, *p;
 258     unsigned irow = 0;
 259     unsigned icol = 0;
 260     unsigned row, col, i, ix;
 261
 262     unsigned* indxc = (unsigned*) my_malloc (k * sizeof(unsigned), "indxc");
 263     unsigned* indxr = (unsigned*) my_malloc (k * sizeof(unsigned), "indxr");
 264     unsigned* ipiv = (unsigned*) my_malloc (k * sizeof(unsigned), "ipiv");
 265     gf *id_row = NEW_GF_MATRIX (1, k);
 266     gf *temp_row = NEW_GF_MATRIX (1, k);
 267
 268     memset (id_row, '\0', k * sizeof (gf));
 269     /*
 270      * ipiv marks elements already used as pivots.
 271      */
 272     for (i = 0; i < k; i++)
 273         ipiv[i] = 0;
 274
 275     for (col = 0; col < k; col++) {
 276         gf *pivot_row;
 277         /*
 278          * Zeroing column 'col', look for a non-zero element.
 279          * First try on the diagonal, if it fails, look elsewhere.
 280          */
 281         if (ipiv[col] != 1 && src[col * k + col] != 0) {
 282             irow = col;
 283             icol = col;
 284             goto found_piv;
 285         }
 286         for (row = 0; row < k; row++) {
 287             if (ipiv[row] != 1) {
 288                 for (ix = 0; ix < k; ix++) {
 289                     if (ipiv[ix] == 0) {
 290                         if (src[row * k + ix] != 0) {
 291                             irow = row;
 292                             icol = ix;
 293                             goto found_piv;
 294                         }
 295                     } else if (ipiv[ix] > 1) {
 296                         ERR("singular matrix");
 297                         goto fail;
 298                     }
 299                 }
 300             }
 301         }
 302       found_piv:
 303         ++(ipiv[icol]);
 304         /*
 305          * swap rows irow and icol, so afterwards the diagonal
 306          * element will be correct. Rarely done, not worth
 307          * optimizing.
 308          */
 309         if (irow != icol)
 310             for (ix = 0; ix < k; ix++)
 311                 SWAP (src[irow * k + ix], src[icol * k + ix], gf);
 312         indxr[col] = irow;
 313         indxc[col] = icol;
 314         pivot_row = &src[icol * k];
 315         c = pivot_row[icol];
 316         if (c == 0) {
 317             ERR("singular matrix 2");
 318             goto fail;
 319         }
 320         if (c != 1) {                       /* otherwhise this is a NOP */
 321             /*
 322              * this is done often , but optimizing is not so
 323              * fruitful, at least in the obvious ways (unrolling)
 324              */
 325             c = inverse[c];
 326             pivot_row[icol] = 1;
 327             for (ix = 0; ix < k; ix++)
 328                 pivot_row[ix] = gf_mul (c, pivot_row[ix]);
 329         }
 330         /*
 331          * from all rows, remove multiples of the selected row
 332          * to zero the relevant entry (in fact, the entry is not zero
 333          * because we know it must be zero).
 334          * (Here, if we know that the pivot_row is the identity,
 335          * we can optimize the addmul).
 336          */
 337         id_row[icol] = 1;
 338         if (memcmp (pivot_row, id_row, k * sizeof (gf)) != 0) {
 339             for (p = src, ix = 0; ix < k; ix++, p += k) {
 340                 if (ix != icol) {
 341                     c = p[icol];
 342                     p[icol] = 0;
 343                     addmul (p, pivot_row, c, k);
 344                 }
 345             }
 346         }
 347         id_row[icol] = 0;
 348     }                           /* done all columns */
 349     for (col = k; col > 0; col--)
 350         if (indxr[col-1] != indxc[col-1])
 351             for (row = 0; row < k; row++)
 352                 SWAP (src[row * k + indxr[col-1]], src[row * k + indxc[col-1]], gf);
 353   fail:
 354     free (indxc);
 355     free (indxr);
 356     free (ipiv);
 357     free (id_row);
 358     free (temp_row);
 359     return;
 360 }
 361
 362 /*
 363  * fast code for inverting a vandermonde matrix.
 364  *
 365  * NOTE: It assumes that the matrix is not singular and _IS_ a vandermonde
 366  * matrix. Only uses the second column of the matrix, containing the p_i's.
 367  *
 368  * Algorithm borrowed from "Numerical recipes in C" -- sec.2.8, but largely
 369  * revised for my purposes.
 370  * p = coefficients of the matrix (p_i)
 371  * q = values of the polynomial (known)
 372  */
 373 void
 374 _invert_vdm (gf* src, unsigned k) {
 375     unsigned i, j, row, col;
 376     gf *b, *c, *p;
 377     gf t, xx;
 378
 379     if (k == 1)                   /* degenerate case, matrix must be p^0 = 1 */
 380         return;
 381     /*
 382      * c holds the coefficient of P(x) = Prod (x - p_i), i=0..k-1
 383      * b holds the coefficient for the matrix inversion
 384      */
 385     c = NEW_GF_MATRIX (1, k);
 386     b = NEW_GF_MATRIX (1, k);
 387
 388     p = NEW_GF_MATRIX (1, k);
 389
 390     for (j = 1, i = 0; i < k; i++, j += k) {
 391         c[i] = 0;
 392         p[i] = src[j];            /* p[i] */
 393     }
 394     /*
 395      * construct coeffs. recursively. We know c[k] = 1 (implicit)
 396      * and start P_0 = x - p_0, then at each stage multiply by
 397      * x - p_i generating P_i = x P_{i-1} - p_i P_{i-1}
 398      * After k steps we are done.
 399      */
 400     c[k - 1] = p[0];              /* really -p(0), but x = -x in GF(2^m) */
 401     for (i = 1; i < k; i++) {
 402         gf p_i = p[i];            /* see above comment */
 403         for (j = k - 1 - (i - 1); j < k - 1; j++)
 404             c[j] ^= gf_mul (p_i, c[j + 1]);
 405         c[k - 1] ^= p_i;
 406     }
 407
 408     for (row = 0; row < k; row++) {
 409         /*
 410          * synthetic division etc.
 411          */
 412         xx = p[row];
 413         t = 1;
 414         b[k - 1] = 1;             /* this is in fact c[k] */
 415         for (i = k - 1; i > 0; i--) {
 416             b[i-1] = c[i] ^ gf_mul (xx, b[i]);
 417             t = gf_mul (xx, t) ^ b[i-1];
 418         }
 419         for (col = 0; col < k; col++)
 420             src[col * k + row] = gf_mul (inverse[t], b[col]);
 421     }
 422     free (c);
 423     free (b);
 424     free (p);
 425     return;
 426 }
 427
 428 static int fec_initialized = 0;
 429 static void
 430 init_fec (void) {
 431     generate_gf();
 432     _init_mul_table();
 433     fec_initialized = 1;
 434 }
 435
 436 /*
 437  * This section contains the proper FEC encoding/decoding routines.
 438  * The encoding matrix is computed starting with a Vandermonde matrix,
 439  * and then transforming it into a systematic matrix.
 440  */
 441
 442 #define FEC_MAGIC       0xFECC0DEC
 443
 444 void
 445 fec_free (fec_t *p) {
 446     if (p == NULL ||
 447         p->magic != (((FEC_MAGIC ^ p->k) ^ p->n) ^ (unsigned long) (p->enc_matrix))) {
 448         ERR("bad parameters to fec_free");
 449         return;
 450     }
 451     free (p->enc_matrix);
 452     free (p);
 453 }
 454
 455 fec_t *
 456 fec_new(unsigned k, unsigned n) {
 457     unsigned row, col;
 458     gf *p, *tmp_m;
 459
 460     fec_t *retval;
 461
 462     fec_error[FEC_ERROR_SIZE] = '\0';
 463
 464     if (fec_initialized == 0)
 465         init_fec ();
 466
 467     retval = (fec_t *) my_malloc (sizeof (fec_t), "new_code");
 468     retval->k = k;
 469     retval->n = n;
 470     retval->enc_matrix = NEW_GF_MATRIX (n, k);
 471     retval->magic = ((FEC_MAGIC ^ k) ^ n) ^ (unsigned long) (retval->enc_matrix);
 472     tmp_m = NEW_GF_MATRIX (n, k);
 473     /*
 474      * fill the matrix with powers of field elements, starting from 0.
 475      * The first row is special, cannot be computed with exp. table.
 476      */
 477     tmp_m[0] = 1;
 478     for (col = 1; col < k; col++)
 479         tmp_m[col] = 0;
 480     for (p = tmp_m + k, row = 0; row < n - 1; row++, p += k)
 481         for (col = 0; col < k; col++)
 482             p[col] = gf_exp[modnn (row * col)];
 483
 484     /*
 485      * quick code to build systematic matrix: invert the top
 486      * k*k vandermonde matrix, multiply right the bottom n-k rows
 487      * by the inverse, and construct the identity matrix at the top.
 488      */
 489     _invert_vdm (tmp_m, k);        /* much faster than _invert_mat */
 490     _matmul(tmp_m + k * k, tmp_m, retval->enc_matrix + k * k, n - k, k, k);
 491     /*
 492      * the upper matrix is I so do not bother with a slow multiply
 493      */
 494     memset (retval->enc_matrix, '\0', k * k * sizeof (gf));
 495     for (p = retval->enc_matrix, col = 0; col < k; col++, p += k + 1)
 496         *p = 1;
 497     free (tmp_m);
 498
 499     return retval;
 500 }
 501
 502 void
 503 fec_encode(const fec_t* code, const gf*restrict const*restrict const src, gf*restrict const*restrict const fecs, const unsigned*restrict const block_nums, size_t num_block_nums, size_t sz) {
 504     unsigned char i, j;
 505     unsigned fecnum;
 506     gf* p;
 507
 508     for (i=0; i<num_block_nums; i++) {
 509         fecnum=block_nums[i];
 510         assert (fecnum >= code->k);
 511         memset(fecs[i], 0, sz);
 512         p = &(code->enc_matrix[fecnum * code->k]);
 513         for (j = 0; j < code->k; j++)
 514             addmul(fecs[i], src[j], p[j], sz);
 515     }
 516 }
 517
 518 /**
 519  * Build decode matrix into some memory space.
 520  *
 521  * @param matrix a space allocated for a k by k matrix
 522  */
 523 void
 524 build_decode_matrix_into_space(const fec_t*restrict const code, const unsigned*const restrict index, const unsigned k, gf*restrict const matrix) {
 525     unsigned char i;
 526     gf* p;
 527     for (i=0, p=matrix; i < k; i++, p += k) {
 528         if (index[i] < k) {
 529             memset(p, 0, k);
 530             p[i] = 1;
 531         } else {
 532             memcpy(p, &(code->enc_matrix[index[i] * code->k]), k);
 533         }
 534     }
 535     _invert_mat (matrix, k);
 536 }
 537
 538 void
 539 fec_decode(const fec_t* code, const gf*restrict const*restrict const inpkts, gf*restrict const*restrict const outpkts, const unsigned*restrict const index, size_t sz) {
 540     gf m_dec[code->k * code->k];
 541     build_decode_matrix_into_space(code, index, code->k, m_dec);
 542
 543     unsigned char outix=0;
 544     for (unsigned char row=0; row<code->k; row++) {
 545         if (index[row] >= code->k) {
 546             memset(outpkts[outix], 0, sz);
 547             for (unsigned char col=0; col < code->k; col++)
 548                 addmul(outpkts[outix], inpkts[col], m_dec[row * code->k + col], sz);
 549             outix++;
 550         }
 551     }
 552 }
 553
 554 /**
 555  * zfec -- fast forward error correction library with Python interface
 556  *
 557  * Copyright (C) 2007 Allmydata, Inc.
 558  * Author: Zooko Wilcox-O'Hearn
 559  *
 560  * This file is part of zfec.
 561  *
 562  * This program is free software; you can redistribute it and/or modify it
 563  * under the terms of the GNU General Public License as published by the Free
 564  * Software Foundation; either version 2 of the License, or (at your option)
 565  * any later version, with the added permission that, if you become obligated
 566  * to release a derived work under this licence (as per section 2.b of the
 567  * GPL), you may delay the fulfillment of this obligation for up to 12 months.
 568  *
 569  * If you would like to inquire about a commercial relationship with Allmydata,
 570  * Inc., please contact partnerships@allmydata.com and visit
 571  * http://allmydata.com/.
 572  *
 573  * This program is distributed in the hope that it will be useful, but WITHOUT
 574  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 575  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
 576  * more details.
 577  */
 578
 579 /*
 580  * Much of this work is derived from the "fec" software by Luigi Rizzo, et
 581  * al., the copyright notice and licence terms of which are included below
 582  * for reference.
 583  * fec.c -- forward error correction based on Vandermonde matrices
 584  * 980624
 585  * (C) 1997-98 Luigi Rizzo (luigi@iet.unipi.it)
 586  *
 587  * Portions derived from code by Phil Karn (karn@ka9q.ampr.org),
 588  * Robert Morelos-Zaragoza (robert@spectra.eng.hawaii.edu) and Hari
 589  * Thirumoorthy (harit@spectra.eng.hawaii.edu), Aug 1995
 590  *
 591  * Modifications by Dan Rubenstein (see Modifications.txt for
 592  * their description.
 593  * Modifications (C) 1998 Dan Rubenstein (drubenst@cs.umass.edu)
 594  *
 595  * Redistribution and use in source and binary forms, with or without
 596  * modification, are permitted provided that the following conditions
 597  * are met:
 598  *
 599  * 1. Redistributions of source code must retain the above copyright
 600  *    notice, this list of conditions and the following disclaimer.
 601  * 2. Redistributions in binary form must reproduce the above
 602  *    copyright notice, this list of conditions and the following
 603  *    disclaimer in the documentation and/or other materials
 604  *    provided with the distribution.
 605  *
 606  * THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND
 607  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
 608  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
 609  * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHORS
 610  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY,
 611  * OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 612  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
 613  * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 614  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
 615  * TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
 616  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY
 617  * OF SUCH DAMAGE.
 618  */