Update lzcomp

4 files changed, 53 insertions, 9 deletions

diff --git a/tools/lz/main.c b/tools/lz/main.c
index 428a027f0..62e6dc413 100644
--- a/tools/lz/main.c
+++ b/tools/lz/main.c
@@ -37,13 +37,16 @@ struct command * compress (const unsigned char * data, unsigned short * size, un
   } else {
     struct command * compressed_sequences[COMPRESSION_METHODS];
     unsigned short lengths[COMPRESSION_METHODS];
-    unsigned flags = compressor -> methods;
+    unsigned flags = 0;
     for (current = 0; current < COMPRESSION_METHODS; current ++) {
       lengths[current] = *size;
-      if (!flags) flags = (++ compressor) -> methods;
-      compressed_sequences[current] = compressor -> function(data, bitflipped, lengths + current, -- flags);
+      if (flags == compressor -> methods) {
+        flags = 0;
+        compressor ++;
+      }
+      compressed_sequences[current] = compressor -> function(data, bitflipped, lengths + current, flags ++);
     }
-    result = select_command_sequence(compressed_sequences, lengths, COMPRESSION_METHODS, size);
+    result = select_optimal_sequence(compressed_sequences, lengths, size);
     for (current = 0; current < COMPRESSION_METHODS; current ++) free(compressed_sequences[current]);
   }
   free(bitflipped);
diff --git a/tools/lz/merging.c b/tools/lz/merging.c
index def572b15..79abb6d2e 100644
--- a/tools/lz/merging.c
+++ b/tools/lz/merging.c
@@ -1,8 +1,47 @@
 #include "proto.h"
 
-struct command * select_command_sequence (struct command ** sequences, const unsigned short * lengths, unsigned count, unsigned short * final_length) {
+struct command * select_optimal_sequence (struct command ** sequences, const unsigned short * lengths, unsigned short * final_length) {
+  struct command * compressor_sequences[NUM_COMPRESSORS * 2];
+  unsigned short compressor_lengths[NUM_COMPRESSORS * 2];
+  struct command * inverted_sequences[COMPRESSION_METHODS];
+  unsigned short inverted_lengths[COMPRESSION_METHODS];
+  unsigned p, current, method = 0;
+  for (current = 0; current < NUM_COMPRESSORS; current ++) {
+    compressor_sequences[current] = select_command_sequence(sequences + method, lengths + method, compressors[current].methods, compressor_lengths + current);
+    compressor_sequences[current + NUM_COMPRESSORS] = select_command_sequence(sequences + method, lengths + method, -(int) compressors[current].methods,
+                                                                              compressor_lengths + (current + NUM_COMPRESSORS));
+    for (p = 0; p < compressors[current].methods; p ++) {
+      inverted_sequences[method + compressors[current].methods - 1 - p] = sequences[method + p];
+      inverted_lengths[method + compressors[current].methods - 1 - p] = lengths[method + p];
+    }
+    method += compressors[current].methods;
+  }
+  unsigned short final_lengths[8];
+  struct command * final_sequences[8] = {
+    select_command_sequence(compressor_sequences, compressor_lengths, NUM_COMPRESSORS, final_lengths),
+    select_command_sequence(compressor_sequences, compressor_lengths, -NUM_COMPRESSORS, final_lengths + 1),
+    select_command_sequence(compressor_sequences + NUM_COMPRESSORS, compressor_lengths + NUM_COMPRESSORS, NUM_COMPRESSORS, final_lengths + 2),
+    select_command_sequence(compressor_sequences + NUM_COMPRESSORS, compressor_lengths + NUM_COMPRESSORS, -NUM_COMPRESSORS, final_lengths + 3),
+    select_command_sequence(sequences, lengths, COMPRESSION_METHODS, final_lengths + 4),
+    select_command_sequence(sequences, lengths, -COMPRESSION_METHODS, final_lengths + 5),
+    select_command_sequence(inverted_sequences, inverted_lengths, COMPRESSION_METHODS, final_lengths + 6),
+    select_command_sequence(inverted_sequences, inverted_lengths, -COMPRESSION_METHODS, final_lengths + 7)
+  };
+  for (current = 0; current < (2 * NUM_COMPRESSORS); current ++) free(compressor_sequences[current]);
+  struct command * result = select_command_sequence(final_sequences, final_lengths, 8, final_length);
+  for (current = 0; current < 8; current ++) free(final_sequences[current]);
+  return result;
+}
+
+struct command * select_command_sequence (struct command ** sequences, const unsigned short * lengths, int count, unsigned short * final_length) {
+  // negative count indicates iterating backwards
   unsigned short min_sequence = 0, min_length = compressed_length(*sequences, *lengths);
   unsigned short seq, len;
+  int backwards = 0;
+  if (count < 0) {
+    backwards = 1;
+    count = -count;
+  }
   for (seq = 1; seq < count; seq ++) {
     len = compressed_length(sequences[seq], lengths[seq]);
     if (len < min_length) {
@@ -15,7 +54,9 @@ struct command * select_command_sequence (struct command ** sequences, const uns
   memcpy(current, sequences[min_sequence], *final_length * sizeof(struct command));
   struct command * new;
   for (seq = 1; seq < count; seq ++) {
+    if (backwards) seq = count - seq;
     new = merge_command_sequences(current, *final_length, sequences[(seq + min_sequence) % count], lengths[(seq + min_sequence) % count], final_length);
+    if (backwards) seq = count - seq; // restore the value for the loop
     free(current);
     current = new;
   }
diff --git a/tools/lz/packing.c b/tools/lz/packing.c
index b3e646347..0cb9fae90 100644
--- a/tools/lz/packing.c
+++ b/tools/lz/packing.c
@@ -17,7 +17,7 @@ void optimize (struct command * commands, unsigned short count) {
       next -> command = 7;
       continue;
     }
-    if (next -> command == commands -> command) {
+    if (next -> command == commands -> command)
       switch (commands -> command) {
         case 0:
           if ((commands -> value + commands -> count) != next -> value) break;
@@ -40,9 +40,7 @@ void optimize (struct command * commands, unsigned short count) {
           }
           next -> count = (commands -> count + next -> count) - MAX_COMMAND_COUNT;
           commands -> count = MAX_COMMAND_COUNT;
-          break;
       }
-    }
     commands = next;
   }
 }
diff --git a/tools/lz/proto.h b/tools/lz/proto.h
index 3ca987156..845774221 100644
--- a/tools/lz/proto.h
+++ b/tools/lz/proto.h
@@ -3,6 +3,7 @@
 #include <string.h>
 #include <stdarg.h>
 
+#define NUM_COMPRESSORS              4
 #define COMPRESSION_METHODS         96 /* sum of all values for the methods field in compressors */
 #define MAX_FILE_SIZE            32768
 #define SHORT_COMMAND_COUNT         32
@@ -48,7 +49,8 @@ int main(int, char **);
 struct command * compress(const unsigned char *, unsigned short *, unsigned);
 
 // merging.c
-struct command * select_command_sequence(struct command **, const unsigned short *, unsigned, unsigned short *);
+struct command * select_optimal_sequence(struct command **, const unsigned short *, unsigned short *);
+struct command * select_command_sequence(struct command **, const unsigned short *, int, unsigned short *);
 struct command * merge_command_sequences(const struct command *, unsigned short, const struct command *, unsigned short, unsigned short *);
 
 // mpcomp.c