1 files changed, 393 insertions, 0 deletions

diff --git a/all_pairs/source/huff_dec/huff_dec.c b/all_pairs/source/huff_dec/huff_dec.c
new file mode 100644
index 0000000..48bdf4b
--- /dev/null
+++ b/all_pairs/source/huff_dec/huff_dec.c
@@ -0,0 +1,393 @@
+/*
+
+  This program is part of the TACLeBench benchmark suite.
+  Version V 2.0
+
+  Name: huff_dec
+
+  Author: David Bourgin (David.Bourgin@ufrima.imag.fr)
+
+  Function: Example of Huffman decoding
+
+  Source: ftp://turing.imag.fr/pub/compression/ (1994-09-26)
+
+  Original name: dcodhuff.c
+
+  Changes: I/O to char arrays instead of file i/o.
+           Dynamic memory allocation replaced by array.
+
+  License:
+
+The source code files (codrl1.c, dcodrl1.c, codrle2.c, dcodrle2.c, codrle3.c,
+dcodrle3.c, codrle4.c, dcodrle4.c, codhuff.c, dcodhuff.c) are copyrighted.
+They have been uploaded on ftp in turing.imag.fr (129.88.31.7):/pub/compression
+on 22/5/94 and have been modified on 22/9/94.
+(c) David Bourgin - 1994
+The source codes I provide have no buggs (!) but being that I make them
+available for free I have some notes to make. They can change at any time
+without notice. I assume no responsability or liability for any errors or
+inaccurracies, make no warranty of any kind (express, implied or statutory)
+with respect to this publication and expressly disclaim any and all warranties
+of merchantability, fitness for particular purposes. Of course, if you have
+some problems to use the information presented here, I will try to help you if
+I can.
+
+If you include the source codes in your application, here are the conditions:
+- You have to put my name in the header of your source file (not in the
+excutable program if you don't want) (this item is a must)
+- I would like to see your resulting application, if possible (this item is not
+a must, because some applications must remain secret)
+- Whenever you gain money with your application, I would like to receive a very
+little part in order to be encouraged to update my source codes and to develop
+new schemes (this item is not a must)
+
+*/
+
+
+/*
+  Declaration of types
+*/
+
+
+#include "../extra.h"
+typedef struct s_tree {
+  unsigned int byte; /* A byte has to be coded as an unsigned integer to
+                        allow a node to have a value over 255 */
+  struct s_tree *left_ptr;
+  struct s_tree *right_ptr;
+} huff_dec_t_tree;
+
+typedef struct {
+  unsigned char bits[32];
+  unsigned int bits_nb;
+  unsigned char presence;
+} t_bin_val;
+
+
+/*
+  Forward declaration of functions
+*/
+
+void huff_dec_init( void );
+int huff_dec_return( void );
+int huff_dec_end_of_data();
+int huff_dec_read_byte();
+void huff_dec_write_byte( char ch );
+unsigned char huff_dec_read_code_1_bit();
+unsigned int huff_dec_read_code_n_bits( unsigned int n );
+void huff_dec_read_header( t_bin_val codes_table[257] );
+huff_dec_t_tree *huff_dec_tree_encoding( t_bin_val codes_table[257],
+    huff_dec_t_tree heap[514] );
+void huff_dec_main( void );
+//int main( void );
+
+
+/*
+  Declaration of global variables
+*/
+
+static int huff_dec_input_pos;
+static int huff_dec_output_pos;
+static char huff_dec_output[1024];
+unsigned char huff_dec_byte_nb_to_read = 0;
+unsigned int huff_dec_val_to_read = 0;
+
+
+/*
+  Initialization- and return-value-related functions
+*/
+
+#define huff_dec_plaintext_len 600
+static const char *huff_dec_plaintext =
+  "You are doubtless asking \"How can I reduce the data size without losing "
+  "some informations?\". It's easy to answer to this question. I'll only take "
+  "an example. I'm sure you have heard about the morse. This system established "
+  "in the 19th century use a scheme very close to the huffman one. In the morse "
+  "you encode the letters to transmit with two kinds of signs. If you encode "
+  "these two sign possibilities in one bit, the symbol 'e' is transmitted in a "
+  "single bit and the symbols 'y' and 'z' need four bits. Look at the symbols "
+  "in the text you are reading, you'll fast understand the compression ratio...";
+
+#define huff_dec_encoded_len 419
+static unsigned char huff_dec_encoded[huff_dec_encoded_len] = {
+  128, 0, 0, 0, 80, 133, 32, 32, 128, 100, 4, 32, 63, 239, 255, 240,
+  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+  4, 7, 167, 21, 129, 232, 69, 120, 132, 217, 20, 162, 19, 164, 39, 133,
+  252, 138, 105, 20, 194, 19, 129, 240, 172, 138, 248, 150, 11, 11, 240, 201,
+  68, 64, 114, 53, 17, 42, 37, 195, 128, 212, 116, 194, 41, 98, 52, 51,
+  12, 132, 112, 244, 3, 36, 33, 52, 39, 135, 164, 33, 62, 156, 87, 14,
+  110, 22, 87, 50, 85, 198, 99, 142, 140, 194, 81, 78, 158, 84, 129, 254,
+  129, 248, 110, 179, 159, 192, 145, 133, 184, 184, 28, 210, 96, 146, 73, 10,
+  226, 21, 83, 152, 74, 13, 111, 132, 199, 202, 219, 241, 74, 193, 167, 105,
+  222, 31, 147, 6, 55, 31, 129, 40, 232, 52, 153, 160, 148, 18, 36, 197,
+  45, 216, 202, 86, 30, 31, 177, 90, 133, 138, 248, 23, 81, 195, 160, 100,
+  215, 93, 50, 185, 225, 251, 23, 6, 230, 225, 229, 112, 71, 80, 96, 141,
+  205, 176, 230, 85, 196, 9, 24, 93, 90, 121, 225, 76, 68, 152, 63, 25,
+  107, 140, 101, 204, 214, 77, 26, 194, 96, 18, 48, 77, 210, 137, 1, 253,
+  4, 230, 248, 56, 240, 224, 111, 163, 95, 10, 12, 223, 7, 234, 167, 129,
+  40, 36, 96, 135, 125, 245, 250, 2, 198, 120, 127, 0, 145, 133, 213, 167,
+  135, 149, 195, 67, 235, 108, 9, 24, 87, 17, 102, 152, 37, 4, 222, 131,
+  188, 144, 73, 36, 128, 73, 20, 81, 152, 177, 133, 248, 28, 165, 131, 120,
+  127, 240, 242, 184, 104, 125, 109, 129, 35, 30, 4, 145, 65, 202, 88, 9,
+  138, 103, 44, 205, 100, 167, 24, 152, 11, 24, 51, 37, 66, 9, 24, 31,
+  174, 202, 212, 49, 152, 18, 96, 155, 208, 119, 146, 45, 97, 48, 56, 28,
+  194, 90, 224, 204, 144, 232, 176, 36, 96, 126, 187, 43, 83, 12, 121, 129,
+  209, 96, 197, 35, 2, 54, 176, 249, 92, 208, 204, 145, 188, 41, 170, 180,
+  71, 16, 36, 96, 126, 187, 43, 83, 19, 0, 145, 129, 100, 209, 15, 43,
+  135, 55, 6, 238, 180, 194, 90, 17, 229, 115, 21, 168, 251, 140, 131, 162,
+  217, 166, 93, 22, 4, 140, 31, 91, 166, 55, 25, 202, 192, 111, 20, 171,
+  207, 39, 192,
+};
+
+
+void huff_dec_init( void )
+{
+  huff_dec_input_pos = 0;
+  huff_dec_output_pos = 0;
+}
+
+
+int huff_dec_return( void )
+{
+  int i;
+  _Pragma( "loopbound min 1 max 600" )
+  for ( i = 0; i < huff_dec_plaintext_len; i++ ) {
+    if ( huff_dec_plaintext[i] != huff_dec_output[i] ) return i + 1;
+  }
+  return 0;
+}
+
+
+/*
+  Input / output functions
+*/
+
+int huff_dec_end_of_data()
+{
+  return huff_dec_input_pos >= huff_dec_encoded_len;
+}
+
+
+int huff_dec_read_byte()
+{
+  return huff_dec_encoded[huff_dec_input_pos++];
+}
+
+
+void huff_dec_write_byte( char ch )
+{
+  huff_dec_output[huff_dec_output_pos++] = ch;
+}
+
+
+unsigned char huff_dec_read_code_1_bit()
+/* Returned parameters: Returns an unsigned integer with the 0-bit (on the
+                        right of the integer) valid
+   Action: Reads the next bit in the stream of data to compress
+   Errors: An input/output error could disturb the running of the program
+   The source must have enough bits to read
+*/
+{
+  if ( huff_dec_byte_nb_to_read ) {
+    huff_dec_byte_nb_to_read--;
+    return ( ( huff_dec_val_to_read >> huff_dec_byte_nb_to_read ) & 1 );
+  } else {
+    huff_dec_val_to_read = huff_dec_read_byte();
+    huff_dec_byte_nb_to_read = 7;
+    return ( ( huff_dec_val_to_read >> 7 ) & 1 );
+  }
+}
+
+
+unsigned int huff_dec_read_code_n_bits( unsigned int n )
+/* Returned parameters: Returns an unsigned integer with the n-bits (on the
+                        right of the integer) valid
+   Action: Reads the next n bits in the stream of data to compress
+   Errors: An input/output error could disturb the running of the program
+   The source must have enough bits to read
+*/
+{
+  unsigned int result = 0;
+  unsigned i = n;
+
+  _Pragma ( "loopbound min 1 max 1" )
+  while ( i ) {
+    _Pragma ( "loopbound min 0 max 2" )
+    while ( ( huff_dec_byte_nb_to_read < 9 ) && ( !huff_dec_end_of_data() ) ) {
+      huff_dec_val_to_read = ( huff_dec_val_to_read << 8 ) + huff_dec_read_byte();
+      huff_dec_byte_nb_to_read += 8;
+    }
+    if ( i >= huff_dec_byte_nb_to_read ) {
+      result = ( result << huff_dec_byte_nb_to_read ) + huff_dec_val_to_read;
+      i -= huff_dec_byte_nb_to_read;
+      huff_dec_byte_nb_to_read = 0;
+    } else {
+      result = ( result << i ) + ( ( huff_dec_val_to_read >>
+        ( huff_dec_byte_nb_to_read - i ) ) & ( ( 1 << i ) - 1 ) );
+      huff_dec_byte_nb_to_read -= i;
+      i = 0;
+    }
+  }
+  return ( result );
+}
+
+
+void huff_dec_read_header( t_bin_val codes_table[257] )
+/* Returned parameters: The contain of 'codes_table' is modified
+   Action: Rebuilds the binary encoding array by using the header
+   Errors: An input/output error could disturb the running of the program
+*/
+{
+  unsigned int i, j;
+  unsigned num_byte;
+
+  _Pragma ( "loopbound min 257 max 257" )
+  for ( i = 0; i < 257; i++ ) {
+    codes_table[i].bits_nb = 0;
+    _Pragma ( "loopbound min 32 max 32" )
+    for ( j = 0; j < 32; j++ ) {
+      codes_table[i].bits[j] = 0;
+    }
+  }
+
+  /* == Decoding of the first part of the header === */
+  if ( huff_dec_read_code_1_bit() )
+    /* First bit=0 => Present bytes coded on n*8 bits
+                =1 => Present bytes coded on 256 bits */
+    _Pragma ( "loopbound min 256 max 256" )
+    for ( i = 0; i <= 255; i++ )
+      codes_table[i].presence = huff_dec_read_code_1_bit();
+  else {
+    i = huff_dec_read_code_n_bits( 5 ) + 1;
+    _Pragma ( "loopbound min 1 max 32" )
+    while ( i ) {
+      codes_table[huff_dec_read_code_n_bits( 8 )].presence = 1;
+      i--;
+    }
+  }
+  codes_table[256].presence = 1;
+  /* Presence of a fictive 256-byte is enforced! */
+
+  /* == Decoding the second part of the header == */
+  _Pragma ( "loopbound min 257 max 257" )
+  for ( i = 0; i <= 256; i++ )
+    if ( codes_table[i].presence ) {
+      if ( huff_dec_read_code_1_bit() )
+        /* First bit=0 => 5 bits of binary length-1 followed by a binary word
+                    =1 => 8 bits of binary length-1 followed by a binary word */
+        j = huff_dec_read_code_n_bits( 8 ) + 1;
+      else j = huff_dec_read_code_n_bits( 5 ) + 1;
+      codes_table[i].bits_nb = j;
+      /* Reading of a binary word */
+      num_byte = ( j - 1 ) >> 3;
+      if ( j & 7 ) {
+        /* Reads the bits that takes less than one byte */
+        codes_table[i].bits[num_byte] =
+          ( unsigned char )huff_dec_read_code_n_bits( j & 7 );
+        j -= j & 7;
+        num_byte--;
+      }
+
+      _Pragma ( "loopbound min 0 max 1" )
+      while ( j >= 8 ) {
+        /* Reads the bits that takes one byte, at least */
+        codes_table[i].bits[num_byte] =
+          ( unsigned char )huff_dec_read_code_n_bits( 8 );
+        j -= 8;
+        num_byte--;
+      }
+    }
+}
+
+
+huff_dec_t_tree *huff_dec_tree_encoding( t_bin_val codes_table[257],
+    huff_dec_t_tree heap[514] )
+/* Returned parameters: A binary tree is returned
+   Action: Returns the decoding binary tree built from 'codes_table'
+   Errors: None
+*/
+{
+  unsigned int i;
+  unsigned int j;
+  unsigned int heap_top = 0;
+  huff_dec_t_tree *ptr_tree;
+  huff_dec_t_tree *current_node;
+
+  ptr_tree = &heap[heap_top++];
+  ptr_tree->byte = 257;
+  ptr_tree->left_ptr = 0;
+  ptr_tree->right_ptr = 0;
+  _Pragma ( "loopbound min 257 max 257" )
+  for ( i = 0; i <= 256; i++ ) {
+    _Pragma ( "loopbound min 0 max 9" )
+    for ( current_node = ptr_tree, j = codes_table[i].bits_nb; j; j-- ) {
+      if ( codes_table[i].bits[( j - 1 ) >> 3] & ( 1 << ( (
+             j - 1 ) & 7 ) ) )
+        if ( current_node->left_ptr == 0 ) {
+          current_node->left_ptr = &heap[heap_top++];
+          current_node = current_node->left_ptr;
+          current_node->left_ptr = 0;
+          current_node->right_ptr = 0;
+        } else current_node = current_node->left_ptr;
+      else
+        if ( current_node->right_ptr == 0 ) {
+          current_node->right_ptr = &heap[heap_top++];
+          current_node = current_node->right_ptr;
+          current_node->left_ptr = 0;
+          current_node->right_ptr = 0;
+        } else current_node = current_node->right_ptr;
+      if ( j == 1 )
+        current_node->byte = i;
+      else current_node->byte = 257;
+    }
+  };
+  return ( ptr_tree );
+}
+
+
+void _Pragma( "entrypoint" ) huff_dec_main( void )
+/* Returned parameters: None
+   Action: Decompresses with Huffman method all bytes read by the function
+           'read_code_1_bit' and 'read_code_n_bits'
+   Errors: An input/output error could disturb the running of the program
+*/
+{
+  t_bin_val encoding_table[257];
+  huff_dec_t_tree heap[514]; /* space for dynamically allocated nodes */
+  huff_dec_t_tree *ptr_tree;
+  huff_dec_t_tree *current_node;
+
+  if ( !huff_dec_end_of_data() ) { /* Are there data to compress? */
+    huff_dec_read_header( encoding_table );
+    ptr_tree = huff_dec_tree_encoding( encoding_table, heap );
+    _Pragma ( "loopbound min 602 max 602" )
+    do {
+      current_node = ptr_tree;
+      _Pragma ( "loopbound min 3 max 9" )
+      while ( current_node->byte == 257 )
+        if ( huff_dec_read_code_1_bit() )
+          /* Bit=1 => Got to left in the node of the tree
+                =0 => Got to right in the node of the tree */
+          current_node = current_node->left_ptr;
+        else current_node = current_node->right_ptr;
+      if ( current_node->byte <= 255 )
+        huff_dec_write_byte( current_node->byte );
+    } while ( current_node->byte != 256 );
+  }
+}
+
+
+int main( int argc, char **argv )
+{
+        //SET_UP
+        int jobsComplete;
+        int maxJobs=5;
+        for (jobsComplete=-1; jobsComplete<maxJobs; jobsComplete++){
+        //      START_LOOP
+                huff_dec_init();
+                huff_dec_main();
+        //      STOP_LOOP
+        }
+        //WRITE_TO_FILE
+  return ( huff_dec_return() );
+}