Reorganize and commit all the modified TACLeBench code and run scripts

1 files changed, 670 insertions, 0 deletions

diff --git a/all_pairs/source/anagram/anagram.c b/all_pairs/source/anagram/anagram.c
new file mode 100644
index 0000000..8f140a3
--- /dev/null
+++ b/all_pairs/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 */