Reorganize and commit all the modified TACLeBench code and run scripts

1 files changed, 670 insertions, 0 deletions

diff --git a/baseline/source/anagram/anagram.c b/baseline/source/anagram/anagram.c
new file mode 100644
index 0000000..8f140a3
--- /dev/null
+++ b/baseline/source/anagram/anagram.c
@@ -0,0 +1,670 @@
+/*
+
+  This program is part of the TACLeBench benchmark suite.
+  Version 2.0
+
+  Name: anagram
+
+  Author: Raymond Chen
+
+  Function: A program that computes anagrams.
+
+  Source: See below.
+
+  Original name: anagram
+
+  Changes: See ChangeLog.txt
+
+  License: See below.
+
+*/
+
+/*
+   Anagram program by Raymond Chen,
+   inspired by a similar program by Brian Scearce
+
+   This program is Copyright 1991 by Raymond Chen.
+               (rjc@math.princeton.edu)
+
+   This program may be freely distributed provided all alterations
+   to the original are clearly indicated as such.
+*/
+
+/* There are two tricks.  First is the Basic Idea:
+
+   When the user types in a phrase, the phrase is first preprocessed to
+   determine how many of each letter appears.  A bit field is then constructed
+   dynamically, such that each field is large enough to hold the next power
+   of two larger than the number of times the character appears.  For example,
+   if the phrase is hello, world, the bit field would be
+
+     00 00 00 000 000 00 00
+      d e   h   l   o  r  w
+
+   The phrase hello, world, itself would be encoded as
+
+     01 01 01 011 010 01 01
+      d e   h   l   o  r  w
+
+   and the word hollow would be encoded as
+
+     00 00 01 010 010 00 01
+      d  e  h   l   o  r  w
+
+   The top bit of each field is set in a special value called the sign.
+   Here, the sign would be
+
+     10 10 10 100 100 10 10
+      d  e  h   l   o  r  w
+
+
+   The reason for packing the values into a bit field is that the operation
+   of subtracting out the letters of a word from the current phrase can be
+   carried out in parallel.  for example, subtracting the word hello from
+   the phrase hello, world, is merely
+
+      d e   h   l   o  r  w
+     01 01 01 011 010 01 01 (dehllloorw)
+   - 00 00 01 010 010 00 01 (hlloow)
+   ========================
+     01 01 00 001 000 01 00 (delr)
+
+   Since none of the sign bits is set, the word fits, and we can continue.
+   Suppose the next word we tried was hood.
+
+      d e   h   l   o  r  w
+     01 01 00 001 000 01 00 (delr)
+   - 01 00 01 000 010 00 00 (hood)
+   ========================
+     00 00 11 000 110 01 00
+           ^      ^
+   A sign bit is set.  (Two, actually.)  This means that hood does not
+   fit in delr, so we skip it and try another word.  (Observe that
+   when a sign bit becomes set, it screws up the values for the letters to
+   the left of that bit, but that's not important.)
+
+   The inner loop of an anagram program is testing to see if a
+   word fits in the collection of untried letters.  Traditional methods
+   keep an array of 26 integers, which are then compared in turn.  This
+   means that there are 26 comparisons per word.
+
+   This method reduces the number of comparisons to MAX_QUAD, typically 2.
+   Instead of looping through an array, we merely perform the indicated
+   subtraction and test if any of the sign bits is set.
+*/
+
+/* The nuts and bolts:
+
+   The dictionary is loaded and preprocessed.  The preprocessed dictionary
+   is a concatenation of copies of the structure:
+
+   struct dictword {
+       char bStructureSize;             -- size of this structure
+       char cLetters;                   -- number of letters in the word
+       char achWord[];                  -- the word itself (0-terminated)
+   }
+
+   Since this is a variable-sized structure, we keep its size in the structure
+   itself for rapid stepping through the table.
+
+   When a phrase is typed in, it is first preprocessed as described in the
+   Basic Idea.  We then go through the dictionary, testing each word.  If
+   the word fits in our phrase, we build the bit field for its frequency
+   table and add it to the list of candidates.
+*/
+
+/*
+   The Second Trick:
+
+   Before diving into our anagram search, we then tabulate how many times
+   each letter appears in our list of candidates, and sort the table, with
+   the rarest letter first.
+
+   We then do our anagram search.
+
+   Like most anagram programs, this program does a depth-first search.
+   Although most anagram programs do some sort of heuristics to decide what
+   order to place words in the list_of_candidates, the search itself proceeds
+   according to a greedy algorithm.  That is, once you find a word that fits,
+   subtract it and recurse.
+
+   This anagram program exercises some restraint and does not march down
+   every branch that shows itself.  Instead, it only goes down branches
+   that use the rarest unused letter.  This helps to find dead ends faster.
+
+   FindAnagram(unused_letters, list_of_candidates) {
+    l = the rarest letter as yet unused
+    For word in list_of_candidates {
+       if word does not fit in unused_letters, go on to the next word.
+       if word does not contain l, defer.
+        FindAnagram(unused_letters - word, list_of_candidates[word,...])
+    }
+   }
+
+
+   The heuristic of the Second Trick can probably be improved.  I invite
+   anyone willing to improve it to do so.
+*/
+
+/* Before compiling, make sure Quad and MASK_BITS are set properly.  For best
+   results, make Quad the largest integer size supported on your machine.
+   So if your machine has long longs, make Quad an unsigned long long.
+   (I called it Quad because on most machines, the largest integer size
+   supported is a four-byte unsigned long.)
+
+   If you need to be able to anagram larger phrases, increase MAX_QUADS.
+   If you increase it beyond 4, you'll have to add a few more loop unrolling
+   steps to FindAnagram.
+*/
+
+#include "../extra.h"
+#include "anagram_ctype.h"
+#include "anagram_stdlib.h"
+#include "anagram_strings.h"
+
+#include "anagram_compare.h"
+
+
+/*
+  Defines
+*/
+
+#define anagram_DICTWORDS 2279
+#define anagram_MASK_BITS 32   /* number of bits in a Quad */
+#define anagram_MAX_QUADS 2    /* controls largest phrase */
+#define anagram_MAXCAND  100   /* candidates */
+#define anagram_MAXSOL   51    /* words in the solution */
+#define anagram_ALPHABET 26    /* letters in the alphabet */
+
+#define anagram_OneStep( i ) \
+        if ( ( aqNext[ i ] = pqMask[ i ] - pw->aqMask[ i ] ) & anagram_aqMainSign[ i ] ) { \
+          ppwStart ++; \
+          continue; \
+        }
+
+
+/*
+  Type definitions
+*/
+
+typedef unsigned int anagram_Quad; /* for building our bit mask */
+
+/* A Word remembers the information about a candidate word. */
+typedef struct {
+  char *pchWord;                            /* the word itself */
+  anagram_Quad aqMask[ anagram_MAX_QUADS ]; /* the word's mask */
+  unsigned cchLength;                       /* letters in the word */
+  char padding[4];
+} anagram_Word;
+typedef anagram_Word *anagram_PWord;
+typedef anagram_Word **anagram_PPWord;
+
+/* A Letter remembers information about each letter in the phrase to
+   be anagrammed. */
+typedef struct {
+  unsigned uFrequency; /* how many times it appears */
+  unsigned uShift;     /* how to mask */
+  unsigned uBits;      /* the bit mask itself */
+  unsigned iq;         /* which Quad to inspect? */
+} anagram_Letter;
+typedef anagram_Letter *anagram_PLetter;
+
+
+/*
+  Forward declaration of functions
+*/
+
+void anagram_init( void );
+void anagram_main( void );
+int anagram_return( void );
+int anagram_ch2i( int ch );
+void anagram_AddWords( void );
+void anagram_BuildMask( char const *pchPhrase );
+void anagram_BuildWord( char *pchWord );
+void anagram_DumpWords( void );
+void anagram_FindAnagram( anagram_Quad *pqMask,
+                          anagram_PPWord ppwStart,
+                          int iLetter );
+anagram_PWord anagram_NewWord( void );
+anagram_PWord anagram_NextWord( void );
+void anagram_ReadDict( void );
+void anagram_Reset( void );
+void anagram_SortCandidates( void );
+
+
+/*
+  Declaration of global variables
+*/
+
+extern char const *anagram_achPhrase[ 3 ];
+extern char const *anagram_dictionary[ anagram_DICTWORDS ];
+
+/* candidates we've found so far */
+static anagram_PWord anagram_apwCand[ anagram_MAXCAND ];
+/* how many of them? */
+static unsigned anagram_cpwCand;
+
+/* statistics on the current phrase */
+static anagram_Letter anagram_alPhrase[ anagram_ALPHABET ];
+
+/* number of letters in phrase */
+static int anagram_cchPhraseLength;
+
+/* the bit field for the full phrase */
+static anagram_Quad anagram_aqMainMask[ anagram_MAX_QUADS ];
+/* where the sign bits are */
+static anagram_Quad anagram_aqMainSign[ anagram_MAX_QUADS ];
+
+static const int anagram_cchMinLength = 3;
+
+/* auGlobalFrequency counts the number of times each letter appears,
+   summed over all candidate words. This is used to decide which letter
+   to attack first. */
+static unsigned anagram_auGlobalFrequency[ anagram_ALPHABET ];
+static int anagram_achByFrequency[ anagram_ALPHABET ]; /* for sorting */
+
+/* the dictionary is read here */
+static char *anagram_pchDictionary;
+
+/* the answers */
+static anagram_PWord anagram_apwSol[ anagram_MAXSOL ];
+static int anagram_cpwLast;
+
+/* buffer to write an answer */
+static char anagram_buffer[30];
+
+/*
+  Initialization- and return-value-related functions
+*/
+
+/* ReadDict -- read the dictionary file into memory and preprocess it
+
+   A word of length cch in the dictionary is encoded as follows:
+
+      byte 0    = cch + 3
+      byte 1    = number of letters in the word
+      byte 2... = the word itself, null-terminated
+
+   Observe that cch+3 is the length of the total encoding.  These
+   byte streams are concatenated, and terminated with a 0.
+*/
+void anagram_ReadDict( void )
+{
+  char *pch;
+  char *pchBase;
+  unsigned len;
+  unsigned cWords = 0;
+  unsigned cLetters;
+  int i;
+  volatile char bitmask = 0;
+
+  len = 0;
+  _Pragma( "loopbound min 2279 max 2279" )
+  for ( i = 0; i < anagram_DICTWORDS; i ++ ) {
+    unsigned strlen = 0;
+    _Pragma( "loopbound min 1 max 5" )
+    while ( anagram_dictionary[ i ][ strlen ] != 0 )
+      strlen ++;
+    len += strlen + 2;
+  }
+
+  pchBase = anagram_pchDictionary = ( char * )anagram_malloc( len );
+
+  _Pragma( "loopbound min 2279 max 2279" )
+  for ( i = 0; i < anagram_DICTWORDS; i ++ ) {
+    int index = 0;
+    pch = pchBase + 2; /* reserve for length */
+    cLetters = 0;
+
+    _Pragma( "loopbound min 1 max 5" )
+    while ( anagram_dictionary[ i ][ index ] != '\0' ) {
+      if ( anagram_isalpha( anagram_dictionary[ i ][ index ] ) )
+        cLetters ++;
+      *pch ++ = anagram_dictionary[ i ][ index ];
+      index ++;
+      *( pch - 1 ) ^= bitmask;
+    }
+    *pch ++ = '\0';
+    *pchBase = ( char )( pch - pchBase );
+    pchBase[ 1 ] = ( char )cLetters;
+    pchBase = pch;
+    cWords ++;
+  }
+
+  *pchBase ++ = 0;
+}
+
+
+void anagram_init( void )
+{
+  anagram_ReadDict();
+}
+
+
+int anagram_return( void )
+{
+  int i;
+  char const *answer = "duke rip amy";
+
+  for ( i = 0; i < 12; i++ )
+    if ( answer[ i ] != anagram_buffer[ i ] )
+      return 1;
+
+  return 0;
+}
+
+
+/*
+  Core benchmark functions
+*/
+
+/* convert letter to index */
+int anagram_ch2i( int ch )
+{
+  return ch - 'a';
+}
+
+
+int anagram_CompareFrequency( char *pch1, char *pch2 )
+{
+  return anagram_auGlobalFrequency[ ( (int) *pch1 ) ] <
+         anagram_auGlobalFrequency[ ( (int) *pch2 ) ]
+         ? -1 :
+         anagram_auGlobalFrequency[ ( (int) *pch1 ) ] ==
+         anagram_auGlobalFrequency[ ( (int) *pch2 ) ]
+         ? 0 : 1;
+}
+
+
+void anagram_Reset( void )
+{
+  anagram_bzero( ( char * )anagram_alPhrase,
+                 sizeof( anagram_Letter ) * anagram_ALPHABET );
+  anagram_bzero( ( char * )anagram_aqMainMask,
+                 sizeof( anagram_Quad ) * anagram_MAX_QUADS );
+  anagram_bzero( ( char * )anagram_aqMainSign,
+                 sizeof( anagram_Quad ) * anagram_MAX_QUADS );
+  anagram_bzero( ( char * )anagram_auGlobalFrequency,
+                 sizeof( unsigned ) * anagram_ALPHABET );
+  anagram_bzero( ( char * )anagram_achByFrequency,
+                 sizeof( int ) * anagram_ALPHABET );
+  anagram_bzero( ( char * )anagram_apwCand,
+                 sizeof( anagram_PWord ) * anagram_MAXCAND );
+  anagram_cchPhraseLength = 0;
+  anagram_cpwCand = 0;
+}
+
+
+void anagram_BuildMask( char const *pchPhrase )
+{
+  int i;
+  int ch;
+  unsigned iq;          /* which Quad? */
+  unsigned int cbtUsed; /* bits used in the current Quad */
+  unsigned int cbtNeed; /* bits needed for current letter */
+  anagram_Quad qNeed;   /* used to build the mask */
+
+  /* Tabulate letter frequencies in the phrase */
+  anagram_cchPhraseLength = 0;
+  _Pragma( "loopbound min 11 max 12" )
+  while ( ( ch = *pchPhrase ++ ) != '\0' ) {
+    if ( anagram_isalpha( ch ) ) {
+      ch = anagram_tolower( ch );
+      anagram_alPhrase[  anagram_ch2i( ch )  ].uFrequency ++;
+      anagram_cchPhraseLength ++;
+    }
+  }
+
+  /* Build  masks */
+  iq = 0;               /* which quad being used */
+  cbtUsed = 0;          /* bits used so far */
+
+  _Pragma( "loopbound min 26 max 26" )
+  for ( i = 0; i < anagram_ALPHABET; i ++ ) {
+    if ( anagram_alPhrase[ i ].uFrequency == 0 ) {
+      anagram_auGlobalFrequency[ i ] = ~0u;  /* to make it sort last */
+    } else {
+      anagram_auGlobalFrequency[ i ] = 0u;
+      _Pragma( "loopbound min 1 max 2" )
+      for ( cbtNeed = 1, qNeed = 1;
+            anagram_alPhrase[ i ].uFrequency >= qNeed;
+            cbtNeed ++, qNeed <<= 1 )
+        ;
+      if ( cbtUsed + cbtNeed > anagram_MASK_BITS )
+        cbtUsed = 0;
+      anagram_alPhrase[ i ].uBits = qNeed - 1;
+      if ( cbtUsed )
+        qNeed <<= cbtUsed;
+      anagram_aqMainSign[ iq ] |= qNeed;
+      anagram_aqMainMask[ iq ] |=
+        ( anagram_Quad )anagram_alPhrase[ i ].uFrequency << cbtUsed;
+      anagram_alPhrase[ i ].uShift = cbtUsed;
+      anagram_alPhrase[ i ].iq = iq;
+      cbtUsed += cbtNeed;
+    }
+  }
+}
+
+
+anagram_PWord anagram_NewWord( void )
+{
+  anagram_PWord pw;
+
+  pw = ( anagram_Word * )anagram_malloc( sizeof( anagram_Word ) );
+  return pw;
+}
+
+
+/* NextWord -- get another candidate entry, creating if necessary */
+anagram_PWord anagram_NextWord( void )
+{
+  anagram_PWord pw;
+  pw = anagram_apwCand[ anagram_cpwCand ++ ];
+  if ( pw != 0 )
+    return pw;
+  anagram_apwCand[ anagram_cpwCand - 1 ] = anagram_NewWord();
+  return anagram_apwCand[ anagram_cpwCand - 1 ];
+}
+
+
+/* BuildWord -- build a Word structure from an ASCII word
+   If the word does not fit, then do nothing. */
+void anagram_BuildWord( char *pchWord )
+{
+  unsigned char cchFrequency[ anagram_ALPHABET ];
+  int i;
+  char *pch = pchWord;
+  anagram_PWord pw;
+  unsigned int cchLength = 0;
+
+  anagram_bzero( ( char * )cchFrequency,
+                 sizeof( unsigned char ) * anagram_ALPHABET );
+
+  /* Build frequency table */
+  _Pragma( "loopbound min 3 max 636" )
+  while ( ( i = *pch ++ ) != '\0' ) {
+    if ( !anagram_isalpha( i ) )
+      continue;
+    i = anagram_ch2i( anagram_tolower( i ) );
+    if ( ++ cchFrequency[ i ] > anagram_alPhrase[ i ].uFrequency )
+      return ;
+    ++ cchLength;
+  }
+
+  /* Update global count */
+  _Pragma( "loopbound min 26 max 26" )
+  for ( i = 0; i < anagram_ALPHABET; i ++ )
+    anagram_auGlobalFrequency[ i ] += cchFrequency[ i ];
+
+  /* Create a Word structure and fill it in, including building the
+     bitfield of frequencies. */
+  pw = anagram_NextWord();
+  anagram_bzero( ( char * )( pw->aqMask ),
+                 sizeof( anagram_Quad ) * anagram_MAX_QUADS );
+
+  pw->pchWord = pchWord;
+  pw->cchLength = cchLength;
+  _Pragma( "loopbound min 26 max 26" )
+  for ( i = 0; i < anagram_ALPHABET; i ++ ) {
+    pw->aqMask[ anagram_alPhrase[i].iq ] |=
+      ( anagram_Quad )cchFrequency[ i ] << anagram_alPhrase[ i ].uShift;
+  }
+}
+
+
+/* AddWords -- build the list of candidates */
+void anagram_AddWords( void )
+{
+  char *pch = anagram_pchDictionary; /* walk through the dictionary */
+
+  anagram_cpwCand = 0;
+
+  _Pragma( "loopbound min 1967 max 1967" )
+  while ( *pch ) {
+    if ( ( pch[ 1 ] >= anagram_cchMinLength &&
+           pch[ 1 ] + anagram_cchMinLength <= anagram_cchPhraseLength )
+         || pch[ 1 ] == anagram_cchPhraseLength )
+      anagram_BuildWord( pch + 2 );
+    pch += *pch;
+  }
+}
+
+
+void anagram_DumpWords( void )
+{
+  int i, j;
+  int offset = 0;
+  _Pragma( "loopbound min 3 max 3" )
+  for ( i = 0; i < anagram_cpwLast; i ++ ) {
+    _Pragma( "loopbound min 3 max 5" )
+    for ( j = 0; anagram_apwSol[ i ]->pchWord[ j ] != '\0'; j ++ )
+      anagram_buffer[ offset + j ] = anagram_apwSol[ i ]->pchWord[ j ];
+    offset += j;
+
+    anagram_buffer[ offset ++ ] = ' ';
+  }
+  anagram_buffer[ offset ++ ] = '\0';
+}
+
+
+void anagram_FindAnagram( anagram_Quad *pqMask, anagram_PPWord ppwStart,
+                          int iLetter )
+{
+  anagram_Quad aqNext[ anagram_MAX_QUADS ];
+  register anagram_PWord pw;
+  anagram_Quad qMask;
+  unsigned iq;
+  anagram_PPWord ppwEnd = &anagram_apwCand[ 0 ];
+  ppwEnd += anagram_cpwCand;
+
+  _Pragma( "loopbound min 1 max 7" )
+  while ( 1 ) {
+    iq = anagram_alPhrase[ anagram_achByFrequency[iLetter] ].iq;
+    qMask = anagram_alPhrase[ anagram_achByFrequency[iLetter] ].uBits <<
+            anagram_alPhrase[ anagram_achByFrequency[iLetter] ].uShift;
+    if ( pqMask[ iq ] & qMask )
+      break;
+    iLetter ++;
+  }
+
+  _Pragma( "loopbound min 0 max 114" )
+  while ( ppwStart < ppwEnd ) {
+    pw = *ppwStart;
+
+    #if anagram_MAX_QUADS > 0
+    anagram_OneStep( 0 );
+    #endif
+
+    #if anagram_MAX_QUADS > 1
+    anagram_OneStep( 1 );
+    #endif
+
+    #if anagram_MAX_QUADS > 2
+    anagram_OneStep( 2 );
+    #endif
+
+    #if anagram_MAX_QUADS > 3
+    anagram_OneStep( 3 );
+    #endif
+
+    #if anagram_MAX_QUADS > 4
+    @@"Add more unrolling steps here, please."@@
+    #endif
+
+    /* If the pivot letter isn't present, defer this word until later */
+    if ( ( pw->aqMask[ iq ] & qMask ) == 0 ) {
+      *ppwStart = *( -- ppwEnd );
+      *ppwEnd = pw;
+      continue;
+    }
+
+    /* If we get here, this means the word fits. */
+    anagram_apwSol[ anagram_cpwLast ++ ] = pw;
+    if ( anagram_cchPhraseLength -= pw->cchLength ) { /* recurse */
+      /* The recursive call scrambles the tail, so we have to be
+         pessimistic. */
+      ppwEnd = &anagram_apwCand[ 0 ];
+      ppwEnd += anagram_cpwCand;
+      anagram_FindAnagram( &aqNext[ 0 ], ppwStart, iLetter );
+    } else { /* found one */
+      anagram_DumpWords();
+    }
+    anagram_cchPhraseLength += pw->cchLength;
+    -- anagram_cpwLast;
+    ppwStart ++;
+    continue;
+  }
+}
+
+
+void anagram_SortCandidates( void )
+{
+  int i;
+
+  /* Sort the letters by frequency */
+  _Pragma( "loopbound min 26 max 26" )
+  for ( i = 0; i < anagram_ALPHABET; i ++ )
+    anagram_achByFrequency[ i ] = i;
+  anagram_qsort( anagram_achByFrequency, anagram_ALPHABET, sizeof( int ) );
+}
+
+
+void _Pragma( "entrypoint" ) anagram_main( void )
+{
+  int i;
+
+  _Pragma( "loopbound min 3 max 3" )
+  for ( i = 0; i < 3; i ++ ) {
+    anagram_Reset();
+    anagram_BuildMask( anagram_achPhrase[ i ] );
+    anagram_AddWords();
+    if ( anagram_cpwCand == 0 || anagram_cchPhraseLength == 0 )
+      continue;
+
+    anagram_cpwLast = 0;
+    anagram_SortCandidates();
+    _Pragma( "marker call_find" )
+    anagram_FindAnagram( anagram_aqMainMask, anagram_apwCand, 0 );
+    _Pragma( "flowrestriction 1*anagram_FindAnagram <= 51*call_find" )
+  }
+}
+
+
+/*
+  Main function
+*/
+
+int main(int argc, char **argv)
+{
+        SET_UP
+        //int jobsComplete;
+        //int maxJobs=100;
+        //for(jobsComplete=-1; jobsComplete<maxJobs; jobsComplete++){
+                START_LOOP
+                anagram_init();
+                anagram_main();
+                STOP_LOOP
+        //}
+        WRITE_TO_FILE
+  return anagram_return();
+}