Use big_alloc().

[libucw.git] / lib / lizard.c

diff --git a/lib/lizard.c b/lib/lizard.c
index ad1a7897eca9ec0b58e725efa657d1d0fe2421a2..e5035e05698827fb0af13e0d3503110bbe79fbd8 100644 (file)
--- a/lib/lizard.c
+++ b/lib/lizard.c
@@ -3,7 +3,10 @@
  *
  *     (c) 2004, Robert Spalek <robert@ucw.cz>
  *
  *
  *     (c) 2004, Robert Spalek <robert@ucw.cz>
  *

- *     The file format is based on LZO1X and 
+ *     This software may be freely distributed and used according to the terms
+ *     of the GNU Lesser General Public License.
+ *
+ *     The file format is based on LZO1X and

  *     the compression method is based on zlib.
  */
 
  *     the compression method is based on zlib.
  */
 


@@ -11,11 +14,6 @@
 #include "lib/lizard.h"
 
 #include <string.h>
 #include "lib/lizard.h"
 
 #include <string.h>

-#include <stdlib.h>
-#include <sys/mman.h>
-#include <sys/user.h>
-#include <fcntl.h>
-#include <signal.h>

 
 typedef u16 hash_ptr_t;
 struct hash_record {
 
 typedef u16 hash_ptr_t;
 struct hash_record {


@@ -37,7 +35,7 @@ hashf(byte *string)
 }
 
 static inline byte *
 }
 
 static inline byte *

-locate_string(byte *string, uns record_id, uns head)
+locate_string(byte *string, int record_id, int head)

   /* The strings are recorded into the hash-table regularly, hence there is no
    * need to store the pointer there.  */
 {
   /* The strings are recorded into the hash-table regularly, hence there is no
    * need to store the pointer there.  */
 {


@@ -135,8 +133,18 @@ flush_copy_command(uns bof, byte *out, byte *start, uns len)
   if (bof && len <= 238)
     *out++ = len + 17;
   else if (len < 4)
   if (bof && len <= 238)
     *out++ = len + 17;
   else if (len < 4)

+  {

     /* cannot happen when !!bof */
     out[-2] |= len;                            /* invariant: lowest 2 bits 2 bytes back */
     /* cannot happen when !!bof */
     out[-2] |= len;                            /* invariant: lowest 2 bits 2 bytes back */

+#ifdef CPU_ALLOW_UNALIGNED
+    * (u32*) out = * (u32*) start;
+    return out + len;
+#else
+    while (len-- > 0)
+      *out++ = *start++;
+    return out;
+#endif
+  }

   else
   {
     /* leave 2 least significant bits of out[-2] set to 0 */
   else
   {
     /* leave 2 least significant bits of out[-2] set to 0 */


@@ -148,9 +156,8 @@ flush_copy_command(uns bof, byte *out, byte *start, uns len)
       out = dump_unary_value(out, len - 18);
     }
   }
       out = dump_unary_value(out, len - 18);
     }
   }

-  while (len-- > 0)
-    *out++ = *start++;
-  return out;
+  memcpy(out, start, len);
+  return out + len;

 }
 
 int
 }
 
 int


@@ -161,21 +168,20 @@ lizard_compress(byte *in, uns in_len, byte *out)
 {
   hash_ptr_t hash_tab[HASH_SIZE];
   struct hash_record hash_rec[HASH_RECORDS];
 {
   hash_ptr_t hash_tab[HASH_SIZE];
   struct hash_record hash_rec[HASH_RECORDS];

-  byte *in_start = in;

   byte *in_end = in + in_len;
   byte *out_start = out;
   byte *copy_start = in;
   uns head = 1;                                        /* 0 in unused */
   byte *in_end = in + in_len;
   byte *out_start = out;
   byte *copy_start = in;
   uns head = 1;                                        /* 0 in unused */

-  uns to_delete = 0;
+  uns to_delete = 0, bof = 1;

   bzero(hash_tab, sizeof(hash_tab));           /* init the hash-table */
   while (in < in_end)
   {
     uns hash = hashf(in);
   bzero(hash_tab, sizeof(hash_tab));           /* init the hash-table */
   while (in < in_end)
   {
     uns hash = hashf(in);

-    byte *best;
+    byte *best = NULL;

     uns len = find_match(hash_tab[hash], hash_rec, in, in_end, &best, head);
     if (len < 3)
 #if 0                  // TODO: now, our routine does not detect matches of length 2
     uns len = find_match(hash_tab[hash], hash_rec, in, in_end, &best, head);
     if (len < 3)
 #if 0                  // TODO: now, our routine does not detect matches of length 2

-      if (len == 2 && (in - best->string) < ((1<<10) + 1))
+      if (len == 2 && (in - best->string - 1) < (1<<10))

       { /* pass-thru */ }
       else
 #endif
       { /* pass-thru */ }
       else
 #endif


@@ -194,7 +200,7 @@ literal:
     }
     /* Record the match.  */
     uns copy_len = in - copy_start;
     }
     /* Record the match.  */
     uns copy_len = in - copy_start;

-    uns is_in_copy_mode = copy_start==in_start || copy_len >= 4;
+    uns is_in_copy_mode = bof || copy_len >= 4;

     uns shift = in - best - 1;
     /* Try to use a 2-byte sequence.  */
 #if 0
     uns shift = in - best - 1;
     /* Try to use a 2-byte sequence.  */
 #if 0


@@ -206,30 +212,31 @@ literal:
        goto dump_2sequence;
     } else
 #endif
        goto dump_2sequence;
     } else
 #endif

-    if (len == 3 && is_in_copy_mode && shift >= (1<<11) && shift < (1<<11) + (1<<10))
+    /* now, len >= 3 */
+    if (shift < (1<<11) && len <= 8)

     {
     {

-      /* optimisation for length-3 matches after a copy command */
-      shift -= 1<<11;
+      shift |= (len-3 + 2)<<11;

 dump_2sequence:
 dump_2sequence:

-      if (copy_len > 0)
-       out = flush_copy_command(copy_start==in_start, out, copy_start, copy_len);
+      if (copy_len)
+       out = flush_copy_command(bof, out, copy_start, copy_len);

       *out++ = (shift>>6) & ~3;                        /* shift fits into 10 bits */
       *out++ = shift & 0xff;
     }
       *out++ = (shift>>6) & ~3;                        /* shift fits into 10 bits */
       *out++ = shift & 0xff;
     }

-    /* now, len >= 3 */
-    else if (shift < (1<<11) && len <= 8)
+    else if (len == 3 && is_in_copy_mode)

     {
     {

-      shift |= (len-3 + 2)<<11;
-      goto dump_2sequence;                     /* shift has 11 bits and contains also len */
+      if (shift < (1<<11) + (1<<10))           /* optimisation for length-3 matches after a copy command */
+      {
+       shift -= 1<<11;
+       goto dump_2sequence;                    /* shift has 11 bits and contains also len */
+      }
+      else                                     /* avoid 3-sequence compressed to 3 sequence if it can simply be appended */
+       goto literal;

     }
     /* We have to use a 3-byte sequence.  */
     }
     /* We have to use a 3-byte sequence.  */

-    else if (len == 3 && is_in_copy_mode)
-      /* avoid 3-sequence compressed to 3 sequence if it can simply be appended */
-      goto literal;

     else
     {
     else
     {

-      if (copy_len > 0)
-       out = flush_copy_command(copy_start==in_start, out, copy_start, copy_len);
+      if (copy_len)
+       out = flush_copy_command(bof, out, copy_start, copy_len);

       if (shift < (1<<14))
       {
        if (len <= 33)
       if (shift < (1<<14))
       {
        if (len <= 33)


@@ -243,12 +250,12 @@ dump_2sequence:
       else /* shift < (1<<15)-1 becase of HASH_RECORDS */
       {
        shift++;                                /* because shift==0 is reserved for EOF */
       else /* shift < (1<<15)-1 becase of HASH_RECORDS */
       {
        shift++;                                /* because shift==0 is reserved for EOF */

-       byte pos_bit = (shift>>11) & (1<<3);
+       byte pos_bit = ((shift>>11) & (1<<3)) | (1<<4);

        if (len <= 9)
        if (len <= 9)

-         *out++ = (1<<4) | pos_bit | (len-2);
+         *out++ = pos_bit | (len-2);

        else
        {
        else
        {

-         *out++ = (1<<4) | pos_bit;
+         *out++ = pos_bit;

          out = dump_unary_value(out, len - 9);
        }
       }
          out = dump_unary_value(out, len - 9);
        }
       }


@@ -261,12 +268,11 @@ dump_2sequence:
       head = hash_string(hash_tab, hashf(in+i), hash_rec, head, &to_delete);
     in += len;
     copy_start = in;
       head = hash_string(hash_tab, hashf(in+i), hash_rec, head, &to_delete);
     in += len;
     copy_start = in;

+    bof = 0;

   }
   }

-  if (in > in_end)                             /* crop at BOF */
-    in = in_end;

   uns copy_len = in - copy_start;
   uns copy_len = in - copy_start;

-  if (copy_len > 0)
-    out = flush_copy_command(copy_start==in_start, out, copy_start, copy_len);
+  if (copy_len)
+    out = flush_copy_command(bof, out, copy_start, copy_len);

   *out++ = 17;                                 /* add EOF */
   *out++ = 0;
   *out++ = 0;
   *out++ = 17;                                 /* add EOF */
   *out++ = 0;
   *out++ = 0;


@@ -297,7 +303,6 @@ lizard_decompress(byte *in, byte *out)
   if (*in > 17)                                        /* short copy command at BOF */
   {
     len = *in++ - 17;
   if (*in > 17)                                        /* short copy command at BOF */
   {
     len = *in++ - 17;

-    expect_copy_command = 2;

     goto perform_copy_command;
   }
   while (1)
     goto perform_copy_command;
   }
   while (1)


@@ -314,7 +319,6 @@ lizard_decompress(byte *in, byte *out)
        }
        else
          len = c + 3;
        }
        else
          len = c + 3;

-       expect_copy_command = 2;

        goto perform_copy_command;
       }
       else
        goto perform_copy_command;
       }
       else


@@ -376,21 +380,29 @@ lizard_decompress(byte *in, byte *out)
     else
     {                                          /* overlapping */
       for (; len-- > 0; out++)
     else
     {                                          /* overlapping */
       for (; len-- > 0; out++)

-       *out = out[-pos];
+       *out = *(out-pos);
+      /* It's tempting to use out[-pos] above, but unfortunately it's not the same */

     }
     /* extract the copy-bits */
     len = in[-2] & 0x3;
     if (len)
     {
       expect_copy_command = 0;
     }
     /* extract the copy-bits */
     len = in[-2] & 0x3;
     if (len)
     {
       expect_copy_command = 0;

+#ifdef CPU_ALLOW_UNALIGNED
+      * (u32*) out = * (u32*) in;
+      out += len;
+      in += len;
+#else

       while (len-- > 0)
        *out++ = *in++;
       while (len-- > 0)
        *out++ = *in++;

+#endif

     }
     else
       expect_copy_command = 1;
     continue;
 
 perform_copy_command:
     }
     else
       expect_copy_command = 1;
     continue;
 
 perform_copy_command:

+    expect_copy_command = 2;

     memcpy(out, in, len);
     out += len;
     in += len;
     memcpy(out, in, len);
     out += len;
     in += len;


@@ -399,67 +411,27 @@ perform_copy_command:
   return out - out_start;
 }
 
   return out - out_start;
 }
 

-struct lizard_buffer *
-lizard_alloc(uns max_len)
-{
-  int fd = open("/dev/zero", O_RDWR);
-  if (fd < 0)
-    die("open(/dev/zero): %m");
-  struct lizard_buffer *buf = xmalloc(sizeof(struct lizard_buffer));
-  buf->len = (max_len + 2*PAGE_SIZE - 1) / PAGE_SIZE * PAGE_SIZE;
-  buf->ptr = mmap(NULL, buf->len, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
-  if (buf->ptr == MAP_FAILED)
-    die("mmap(/dev/zero): %m");
-  return buf;
-}
-
-void
-lizard_free(struct lizard_buffer *buf)
-{
-  munmap(buf->ptr, buf->len);
-  xfree(buf);
-}
-
-static void
-sigsegv_handler(int UNUSED whatsit)
-{
-  die("SIGSEGV caught when decompressing.");
-}
-
-int
-lizard_decompress_safe(byte *in, struct lizard_buffer *buf, uns expected_length)
-  /* Decompresses into buf->ptr and returns the length of the uncompressed
-   * file.  Negative return values signalise errors.  If something goes wrong
-   * and buffer would overflow, SIGSEGV is raised.  */
-{
-  uns lock_offset = (expected_length + PAGE_SIZE - 1) / PAGE_SIZE * PAGE_SIZE;
-  if (lock_offset + PAGE_SIZE > buf->len)
-    return -1;
-  mprotect(buf->ptr, lock_offset, PROT_READ | PROT_WRITE);
-  mprotect(buf->ptr + lock_offset, PAGE_SIZE, PROT_READ);
-  sighandler_t old_handler = signal(SIGSEGV, sigsegv_handler);
-  int len = lizard_decompress(in, buf->ptr);
-  signal(SIGSEGV, old_handler);
-  return len;
-}
-

 /*
 
 Description of the LZO1X format :
 =================================
 
 /*
 
 Description of the LZO1X format :
 =================================
 

+The meaning of the commands depends on the current mode. It can be either
+the compressed mode or the copy mode. In some cases, the compressed mode
+also distinguishes whether we just left the copy mode or not.
+

 Beginning of file:
 ------------------
 
 Beginning of file:
 ------------------
 

-If the first byte is 00010001, it means probably EOF (empty file), so switch
-to the compressed mode.  If it is bigger, subtract 17 and copy this number of
-the following characters to the ouput and switch to the compressed mode.  If
-it is smaller, go to the copy mode.
+Start in copy mode. If the first byte is 00010001, it means probably EOF (empty file),
+so switch to the compressed mode.  If it is bigger, subtract 17 and copy this number of
+the following characters to the output and switch to the compressed mode.
+If it is smaller, interpret it as a regular copy mode command.

 
 

-Compressed mode :
------------------
+Compressed mode:
+----------------

 
 

-Read the first byte of the sequence and determine the type of bit-encoding by
+Read the first byte of the sequence and determine the type of bit encoding by

 looking at the most significant bits.  The sequence is always at least 2 bytes
 long.  Decode sequences of these types until the EOF or END marker is read.
 
 looking at the most significant bits.  The sequence is always at least 2 bytes
 long.  Decode sequences of these types until the EOF or END marker is read.
 


@@ -478,25 +450,23 @@ long.  Decode sequences of these types until the EOF or END marker is read.
     C following characters will be copied from the compressed text to the
     output.  The number CC is always stored in the 2 least significant bits of
     the second last byte of the sequence.
     C following characters will be copied from the compressed text to the
     output.  The number CC is always stored in the 2 least significant bits of
     the second last byte of the sequence.

-    
+

     If END is read, the algorithm switches to the copy mode.
 
 pattern                                        length          position
 
     If END is read, the algorithm switches to the copy mode.
 
 pattern                                        length          position
 

-0000ppCC                pppppppp       2               10 bits (*)
-0001pLLL L*    ppppppCC pppppppp       3..9 + extend   15 bits + EOF
+0000ppCC                pppppppp       2               10 bits         [default interpretation]
+0000ppCC                pppppppp       3               10 bits + 2048  [just after return from copy mode]
+0001pLLL L*    ppppppCC pppppppp       3..9 + extend   15 bits         [pos 0 interpreted as EOF]

 001LLLLL L*    ppppppCC pppppppp       3..33 + extend  14 bits
 001LLLLL L*    ppppppCC pppppppp       3..33 + extend  14 bits

-01\
-10 \
-11  \
-LLLpppCC                pppppppp       3..8            11 bits
+LLLpppCC                pppppppp       3..8            11 bits         [LLL >= 010]

 
 

-Copy mode :
------------
+Copy mode:
+----------

 
 Read the first byte and, if the most significant bits are 0000, perform the
 following command, otherwise switch to the compressed mode (and evaluate the
 
 Read the first byte and, if the most significant bits are 0000, perform the
 following command, otherwise switch to the compressed mode (and evaluate the

-command).
+command there).

 
 pattern                                        length          position
 
 
 pattern                                        length          position
 


@@ -505,9 +475,4 @@ pattern                                     length          position
   Copy L characters from the compressed text to the output.  The overhead for
   incompressible strings is only roughly 1/256 + epsilon.
 
   Copy L characters from the compressed text to the output.  The overhead for
   incompressible strings is only roughly 1/256 + epsilon.
 

-(*) After reading one copy command, switch to the compressed mode with the
-following "optimisation": the pattern 0000ppCC expands to length 3 instead of 2
-and 2048 is added to the position (now it is slightly more than 11 bits),
-because a sequence of length 2 would never be used.
-

 */
 */