Adding upstream version 1.25~pre1.upstream/1.25_pre1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 244 insertions, 0 deletions

diff --git a/gf8.cc b/gf8.cc
new file mode 100644
index 0000000..2bb19f0
--- /dev/null
+++ b/gf8.cc
@@ -0,0 +1,244 @@
+/* Lziprecover - Data recovery tool for the lzip format
+   Copyright (C) 2023-2024 Antonio Diaz Diaz.
+
+   This program is free software: you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation, either version 2 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.
+*/
+
+#define _FILE_OFFSET_BITS 64
+
+#include <cstdio>
+#include <cstring>
+#include <list>
+#include <string>
+#include <vector>
+#include <stdint.h>
+
+#include "lzip.h"
+#include "md5.h"
+#include "fec.h"
+
+namespace {
+
+struct Galois8_table		// addition/subtraction is exclusive or
+  {
+  enum { size = 1 << 8, poly = 0x11D };		// generator polynomial
+  uint8_t * log, * ilog, * mul_table;
+
+  Galois8_table() : log( 0 ), ilog( 0 ), mul_table( 0 ) {}
+//  ~Galois8_table() { delete[] mul_table; delete[] ilog; delete[] log; }
+
+  void init()	// fill log, inverse log, and multiplication tables
+    {
+    if( log ) return;
+    log = new uint8_t[size]; ilog = new uint8_t[size];
+    mul_table = new uint8_t[size * size];
+    for( unsigned b = 1, i = 0; i < size - 1; ++i )
+      {
+      log[b] = i;
+      ilog[i] = b;
+      b <<= 1;
+      if( b & size ) b ^= poly;
+      }
+    log[0] = size - 1;	// log(0) is not defined, so use a special value
+    ilog[size-1] = 1;
+
+    for( int i = 1; i < size; ++i )
+      {
+      uint8_t * const mul_row = mul_table + i * size;
+      for( int j = 1; j < size; ++j )
+        mul_row[j] = ilog[(log[i] + log[j]) % (size - 1)];
+      }
+    for( int i = 0; i < size; ++i )
+      mul_table[0 * size + i] = mul_table[i * size + 0] = 0;
+    }
+
+  uint8_t inverse( const uint8_t a ) const { return ilog[size-1-log[a]]; }
+  } gf;
+
+
+// check that A * B = I (A, B, I are square matrices of size k * k)
+bool check_inverse( const uint8_t * const A, const uint8_t * const B,
+                    const unsigned k )
+  {
+  for( unsigned row = 0; row < k; ++row )	// multiply A * B
+    for( unsigned col = 0; col < k; ++col )
+      {
+      const uint8_t * pa = A + row * k;
+      const uint8_t * pb = B + col;
+      uint8_t sum = 0;
+      for( unsigned i = 0; i < k; ++i, ++pa, pb += k )
+        sum ^= gf.mul_table[*pa * gf.size + *pb];
+      if( sum != ( row == col ) ) return false;		// A * B != I
+      }
+  return true;
+  }
+
+
+/* Invert in place a matrix of size k * k.
+   This is like Gaussian elimination with a virtual identity matrix:
+   A --some_changes--> I, I --same_changes--> A^-1
+   Galois arithmetic is exact. Swapping rows or columns is not needed. */
+bool invert_matrix( uint8_t * const matrix, const unsigned k )
+  {
+  for( unsigned row = 0; row < k; ++row )
+    {
+    uint8_t * const pivot_row = matrix + row * k;
+    const uint8_t pivot = pivot_row[row];
+    if( pivot == 0 ) return false;
+    if( pivot != 1 )				// scale the pivot_row
+      {
+      const uint8_t * const mul_row =
+        gf.mul_table + gf.inverse( pivot ) * gf.size;
+      pivot_row[row] = 1;
+      for( unsigned col = 0; col < k; ++col )
+        pivot_row[col] = mul_row[pivot_row[col]];
+      }
+    // subtract pivot_row from the other rows
+    for( unsigned row2 = 0; row2 < k; ++row2 )
+      if( row2 != row )
+        {
+        uint8_t * const dst_row = matrix + row2 * k;
+        const uint8_t c = dst_row[row]; dst_row[row] = 0;
+        const uint8_t * const mul_row = gf.mul_table + c * gf.size;
+        for( unsigned col = 0; col < k; ++col )
+          dst_row[col] ^= mul_row[pivot_row[col]];
+        }
+    }
+  return true;
+  }
+
+
+// create dec_matrix containing only the rows needed and invert it in place
+const uint8_t * init_dec_matrix( const std::vector< unsigned > & bb_vector,
+                                 const std::vector< unsigned > & fbn_vector )
+  {
+  const unsigned bad_blocks = bb_vector.size();
+  uint8_t * const dec_matrix = new uint8_t[bad_blocks * bad_blocks];
+
+  // one row for each missing data block
+  for( unsigned row = 0; row < bad_blocks; ++row )
+    {
+    uint8_t * const dec_row = dec_matrix + row * bad_blocks;
+    const unsigned fbn = fbn_vector[row] | 0x80;
+    for( unsigned col = 0; col < bad_blocks; ++col )
+      dec_row[col] = gf.inverse( fbn ^ bb_vector[col] );
+    }
+  if( !invert_matrix( dec_matrix, bad_blocks ) )
+    internal_error( "GF(2^8) matrix not invertible." );
+  return dec_matrix;
+  }
+
+
+/* compute dst[] += c * src[]
+   treat the buffers as arrays of quadruples of 8-bit Galois values */
+inline void mul_add( const uint8_t * const src, uint8_t * const dst,
+                     const unsigned long fbs, const uint8_t c )
+  {
+  if( c == 0 ) return;				// nothing to add
+  const uint8_t * const mul_row = gf.mul_table + c * gf.size;
+  const uint32_t * const src32 = (const uint32_t *)src;
+  uint32_t * const dst32 = (uint32_t *)dst;
+
+  for( unsigned long i = 0; i < fbs / 4; ++i )
+    { const uint32_t s = src32[i];
+      dst32[i] ^= mul_row[s & 0xFF] ^ mul_row[s >> 8 & 0xFF] << 8 ^
+                  mul_row[s >> 16 & 0xFF] << 16 ^ mul_row[s >> 24] << 24; }
+  }
+
+} // end namespace
+
+
+void gf8_init() { gf.init(); }
+
+bool gf8_check( const std::vector< unsigned > & fbn_vector, const unsigned k )
+  {
+  if( k == 0 ) return true;
+  gf.init();
+  bool good = true;
+  for( unsigned a = 1; a < gf.size; ++a )
+    if( gf.mul_table[a * gf.size + gf.inverse( a )] != 1 )
+      { good = false;
+        std::fprintf( stderr, "%u * ( 1/%u ) != 1 in GF(2^8)\n", a, a ); }
+  uint8_t * const enc_matrix = new uint8_t[k * k];
+  uint8_t * const dec_matrix = new uint8_t[k * k];
+  const bool random = fbn_vector.size() == k;
+  for( unsigned row = 0; row < k; ++row )
+    {
+    const unsigned fbn = ( random ? fbn_vector[row] : row ) | 0x80;
+    uint8_t * const enc_row = enc_matrix + row * k;
+    for( unsigned col = 0; col < k; ++col )
+      enc_row[col] = gf.inverse( fbn ^ col );
+    }
+  std::memcpy( dec_matrix, enc_matrix, k * k );
+  if( !invert_matrix( dec_matrix, k ) )
+    { good = false; show_error( "GF(2^8) matrix not invertible." ); }
+  else if( !check_inverse( enc_matrix, dec_matrix, k ) )
+    { good = false; show_error( "GF(2^8) matrix A * A^-1 != I" ); }
+  delete[] dec_matrix;
+  delete[] enc_matrix;
+  return good;
+  }
+
+
+void rs8_encode( const uint8_t * const buffer, const uint8_t * const lastbuf,
+                 uint8_t * const fec_block, const unsigned long fbs,
+                 const unsigned fbn, const unsigned k )
+  {
+  if( !gf.log ) internal_error( "GF(2^8) tables not initialized." );
+  /* The encode matrix is a Hilbert matrix of size k * k with one row per
+     fec block and one column per data block.
+     The value of each element is computed on the fly with inverse. */
+  const unsigned row = fbn | 0x80;
+  std::memset( fec_block, 0, fbs );
+  for( unsigned col = 0; col < k; ++col )
+    {
+    const uint8_t * const src =
+      ( col < k - (lastbuf != 0) ) ? buffer + col * fbs : lastbuf;
+    mul_add( src, fec_block, fbs, gf.inverse( row ^ col ) );
+    }
+  }
+
+
+void rs8_decode( uint8_t * const buffer, uint8_t * const lastbuf,
+                 const std::vector< unsigned > & bb_vector,
+                 const std::vector< unsigned > & fbn_vector,
+                 uint8_t * const fecbuf, const unsigned long fbs,
+                 const unsigned k )
+  {
+  gf.init();
+  const unsigned bad_blocks = bb_vector.size();
+  for( unsigned col = 0, bi = 0; col < k; ++col )	// reduce
+    {
+    if( bi < bad_blocks && col == bb_vector[bi] ) { ++bi; continue; }
+    const uint8_t * const src =
+      ( col < k - (lastbuf != 0) ) ? buffer + col * fbs : lastbuf;
+    for( unsigned row = 0; row < bad_blocks; ++row )
+      {
+      const unsigned fbn = fbn_vector[row] | 0x80;
+      mul_add( src, fecbuf + row * fbs, fbs, gf.inverse( fbn ^ col ) );
+      }
+    }
+  const uint8_t * const dec_matrix = init_dec_matrix( bb_vector, fbn_vector );
+  for( unsigned col = 0; col < bad_blocks; ++col )	// solve
+    {
+    const unsigned di = bb_vector[col];
+    uint8_t * const dst =
+      ( di < k - (lastbuf != 0) ) ? buffer + di * fbs : lastbuf;
+    std::memset( dst, 0, fbs );
+    const uint8_t * const dec_row = dec_matrix + col * bad_blocks;
+    for( unsigned row = 0; row < bad_blocks; ++row )
+      mul_add( fecbuf + row * fbs, dst, fbs, dec_row[row] );
+    }
+  delete[] dec_matrix;
+  }