From 14c854543b1a3cf344a371a5b45595657f95786b Mon Sep 17 00:00:00 2001 From: leochanj105 Date: Tue, 26 Oct 2021 13:22:32 -0400 Subject: add deadlines and costs --- baseline/source/anagram/ChangeLog.txt | 125 -- baseline/source/anagram/anagram.c | 668 --------- baseline/source/anagram/anagramTest.txt | 100 -- baseline/source/anagram/anagram_compare.h | 27 - baseline/source/anagram/anagram_ctype.h | 45 - baseline/source/anagram/anagram_input.c | 2317 ----------------------------- baseline/source/anagram/anagram_stdlib.c | 158 -- baseline/source/anagram/anagram_stdlib.h | 31 - baseline/source/anagram/anagram_strings.h | 27 - 9 files changed, 3498 deletions(-) delete mode 100644 baseline/source/anagram/ChangeLog.txt delete mode 100644 baseline/source/anagram/anagram.c delete mode 100644 baseline/source/anagram/anagramTest.txt delete mode 100644 baseline/source/anagram/anagram_compare.h delete mode 100644 baseline/source/anagram/anagram_ctype.h delete mode 100644 baseline/source/anagram/anagram_input.c delete mode 100644 baseline/source/anagram/anagram_stdlib.c delete mode 100644 baseline/source/anagram/anagram_stdlib.h delete mode 100644 baseline/source/anagram/anagram_strings.h (limited to 'baseline/source/anagram') diff --git a/baseline/source/anagram/ChangeLog.txt b/baseline/source/anagram/ChangeLog.txt deleted file mode 100644 index fdba1cc..0000000 --- a/baseline/source/anagram/ChangeLog.txt +++ /dev/null @@ -1,125 +0,0 @@ -File: anagram.c -Original provenience: unknown -Source: unknown - -2017-04-18: -- Annotated anagram_main as entry-point for timing analysis - -2016-06-22: -- Fixed type signature of function anagram_main to conform to TACLeBench - standard, i.e. `void anagram_main (void)`. - -2016-05-24: -- Changed type of global variables anagram_achPhrase and - anagram_dictionary to `char const *[]`. -- Changed parameter type of function anagram_BuildMask to - `char const *`. - -2016-04-26: -- Fixed array out-of-bounds access introduced by earlier change. - -2016-04-20: -- Fixed some compiler warnings. -- Return value of anagram_return depends on the computation inside - of anagram_main. - -2016-03-22 -- Added forward declarations for all functions. -- Renamed function main to anagram_main. -- Added function anagram_init that calls anagram_ReadDict, removed - call to anagram_ReadDict from anagram_main. -- Added function anagram_return that handles the return value. -- Added new function main that first calls anagram_init, - then anagram_main and finally returns the return value of - anagram_return. -- Added generic TACLeBench header to all files. -- Introduced comments to split file in sections for type - definitions, forward declarations, global variables, - initialization-related and return-value-related functions, - core benchmark functions, and main routine. -- Renamed ch2i, DICTWORDS, Quad, MASK_BITS, MAX_QUADS, MAXCAND, - MAXSOL, ALPHABET, Word, PWord, PPWord, apwCand, cpwCand, Letter, - PLetter, alPhrase, cchPhraseLength, aqMainMask, aqMainSign, - cchMinLength, auGlobalFrequency, achByFrequency, pchDictionary, - Reset, ReadDict, BuildMask, NewWord, NextWord, BuildWord, - AddWords, apwSol, cpwLast, OneStep, DumpWords, FindAnagram and - SortCandidates to anagram_ch2i, anagram_DICTWORDS, anagram_Quad, - anagram_MASK_BITS, anagram_MAX_QUADS, anagram_MAXCAND, - anagram_MAXSOL, anagram_ALPHABET, anagram_Word, anagram_PWord, - anagram_PPWord, anagram_apwCand, anagram_cpwCand, anagram_Letter, - anagram_PLetter, anagram_alPhrase, anagram_cchPhraseLength, - anagram_aqMainMask, anagram_aqMainSign, anagram_cchMinLength, - anagram_auGlobalFrequency, anagram_achByFrequency, - anagram_pchDictionary, anagram_Reset, anagram_ReadDict, - anagram_BuildMask, anagram_NewWord, anagram_NextWord, - anagram_BuildWord, anagram_AddWords, anagram_apwSol, - anagram_cpwLast, anagram_OneStep, anagram_DumpWords, - anagram_FindAnagram and anagram_SortCandidates. -- Renamed swapi, pivot, qsorts, simulated_heap and freeHeapPos to - anagram_swapi, anagram_pivot, anagram_qsorts, - anagram_simulated_heap and anagram_freeHeapPos. -- Renamed achPhrase and dictionary to anagram_achPhrase and - anagram_dictionary. -- Renamed CompareFrequency to anagram_CompareFrequency. -- Increased simulated heap in anagram_stdlib.c to 18000 bytes to - prevent segmentation fault. -- Changed header guard _WCCMALLOC_H to ANAGRAM_STRINGS_H. -- Renamed wccmalloc, wccbzero to anagram_malloc, anagram_bzero. -- Moved declaration of anagram_malloc to header anagram_stdlib.h. -- Introduced header guard ANAGRAM_CTYPE_H. -- Renamed wccislower, wccisupper, wccisalpha, wcctolower to - anagram_islower, anagram_isupper, anagram_isalpha, - anagram_tolower. -- Removed illegal keyword "inline". -- Changed header guard _WCCSTDLIB_H to ANAGRAM_STDLIB_H. -- Renamed wccqsort to anagram_qsort. -- Fixed compiler warning "no previous extern declaration for - non-static variable" for variables simulated_heap and - freeHeapPos by declaring them static. -- Renamed preprocessor define HEAP_SIZE to ANAGRAM_HEAP_SIZE. -- Fixed compiler warning "no previous prototype for function" by - moving includes to the top of the file. -- Fixed compiler warnings "implicit conversion changes signedness" - and "comparison of integers of different signs" by consistenly - using the type unsigned long in qsort helper functions. -- Moved function CompareFrequency to file anagram.c, added - declaration for it in file anagram_compare.h and included it in - anagram_stdlib.h. -- Fixed compiler warning "no previous extern declaration for - non-static variable" by adding forward declarations. -- Fixed compiler warning "macro is not used" by removing unused - macros MAXWORDS and i2ch. -- Replaced macro ch2i by proper function. -- Fixed compiler warning "array subscript is of type 'char' in - function CompareFrequency. -- Fixed compiler warning "unused variable" by removing variable i - in function Reset. -- Fixed compiler warning "no previous extern declaration for - non-static variable" by making global variables in file - anagram.c static. -- Replaced macro lPhrase by its expansion. -- Fixed compiler warnings "implicit conversion loses integer - precision" and "implicit conversion changes signedness" by - adding explicit casts or using the appropriate type for local - variables. -- Fixed compiler warning "array subscript is of type 'char'" by - changing type of some local variables as well as of global - variable achByFrequency to int. -- Changed all //-style comments to /* */-style comments. -- Moved contents of wccmalloc.c to anagram_stdlib.c. -- Renamed input.c to anagram_input.c. -- Renamed wccctype.h to anagram_ctype.h. -- Renamed wccstdlib.c to anagram_stdlib.c. -- Renamed wccstdlib.h to anagram_stdlib.h. -- Renamed wccmalloc.h to anagram_strings.h. -- Applied TACLeBench formatting rules via - astyle --options=doc/example/astylerc.txt -- Tested conformance to C99 via - clang -fsyntax-only -Weverything -Wno-unknown-pragmas -Wno-padded -pedantic -std=c99 - -2017-06-27 -- Remove static declarations. - -2017-07-10: -- Adjust alignment calculation in anagram_malloc to not add padding on already - aligned addresses. This prevents a buffer overflow of anagram_simulated_heap. diff --git a/baseline/source/anagram/anagram.c b/baseline/source/anagram/anagram.c deleted file mode 100644 index feb9784..0000000 --- a/baseline/source/anagram/anagram.c +++ /dev/null @@ -1,668 +0,0 @@ -/* - - 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 + 3; - } - - pchBase = anagram_pchDictionary = ( char * )anagram_malloc( len + 1 ); - - _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 ) -{ - // Reset heap - anagram_free_all(); - anagram_ReadDict(); -} - - -int anagram_return( void ) -{ - int i; - char const *answer = "duke yip arm"; - - 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 - for_each_job { - anagram_init(); - anagram_main(); - } - WRITE_TO_FILE - return anagram_return(); -} diff --git a/baseline/source/anagram/anagramTest.txt b/baseline/source/anagram/anagramTest.txt deleted file mode 100644 index 21d58d8..0000000 --- a/baseline/source/anagram/anagramTest.txt +++ /dev/null @@ -1,100 +0,0 @@ -anagram none 7 none 100 992260 anagramTest 0 none -anagram none 7 none 100 32657649 anagramTest 1 none -anagram none 7 none 100 50 anagramTest 2 none -anagram none 7 none 100 140726366772064 anagramTest 3 none -anagram none 7 none 100 140332637564920 anagramTest 4 none -anagram none 7 none 100 140332637511040 anagramTest 5 none -anagram none 7 none 100 140726366771844 anagramTest 6 none -anagram none 7 none 100 140726366772048 anagramTest 7 none -anagram none 7 none 100 140332643575048 anagramTest 8 none -anagram none 7 none 100 140724603453440 anagramTest 9 none -anagram none 7 none 100 3 anagramTest 10 none -anagram none 7 none 100 140724603453440 anagramTest 11 none -anagram none 7 none 100 3 anagramTest 12 none -anagram none 7 none 100 0 anagramTest 13 none -anagram none 7 none 100 0 anagramTest 14 none -anagram none 7 none 100 140332643726528 anagramTest 15 none -anagram none 7 none 100 140726366772208 anagramTest 16 none -anagram none 7 none 100 140332643575120 anagramTest 17 none -anagram none 7 none 100 0 anagramTest 18 none -anagram none 7 none 100 140332643725672 anagramTest 19 none -anagram none 7 none 100 140726366772248 anagramTest 20 none -anagram none 7 none 100 140332641512223 anagramTest 21 none -anagram none 7 none 100 1 anagramTest 22 none -anagram none 7 none 100 140332643575120 anagramTest 23 none -anagram none 7 none 100 1 anagramTest 24 none -anagram none 7 none 100 0 anagramTest 25 none -anagram none 7 none 100 1 anagramTest 26 none -anagram none 7 none 100 140332643725672 anagramTest 27 none -anagram none 7 none 100 1 anagramTest 28 none -anagram none 7 none 100 140332643723736 anagramTest 29 none -anagram none 7 none 100 0 anagramTest 30 none -anagram none 7 none 100 0 anagramTest 31 none -anagram none 7 none 100 140332643726528 anagramTest 32 none -anagram none 7 none 100 140726366772064 anagramTest 33 none -anagram none 7 none 100 7472231616 anagramTest 34 none -anagram none 7 none 100 140726366772048 anagramTest 35 none -anagram none 7 none 100 2090089586 anagramTest 36 none -anagram none 7 none 100 4195443 anagramTest 37 none -anagram none 7 none 100 4294967295 anagramTest 38 none -anagram none 7 none 100 140332641470296 anagramTest 39 none -anagram none 7 none 100 140332637550808 anagramTest 40 none -anagram none 7 none 100 140332643573760 anagramTest 41 none -anagram none 7 none 100 140332637522848 anagramTest 42 none -anagram none 7 none 100 2118 anagramTest 43 none -anagram none 7 none 100 140332643573760 anagramTest 44 none -anagram none 7 none 100 140332637511040 anagramTest 45 none -anagram none 7 none 100 140332637564920 anagramTest 46 none -anagram none 7 none 100 140332641510987 anagramTest 47 none -anagram none 7 none 100 2118 anagramTest 48 none -anagram none 7 none 100 140332637564920 anagramTest 49 none -anagram none 7 none 100 140332643573760 anagramTest 50 none -anagram none 7 none 100 140726366772312 anagramTest 51 none -anagram none 7 none 100 140726366772308 anagramTest 52 none -anagram none 7 none 100 6316152 anagramTest 53 none -anagram none 7 none 100 4196240 anagramTest 54 none -anagram none 7 none 100 140726366773040 anagramTest 55 none -anagram none 7 none 100 0 anagramTest 56 none -anagram none 7 none 100 0 anagramTest 57 none -anagram none 7 none 100 140726366772816 anagramTest 58 none -anagram none 7 none 100 140332641532614 anagramTest 59 none -anagram none 7 none 100 1 anagramTest 60 none -anagram none 7 none 100 0 anagramTest 61 none -anagram none 7 none 100 140332637564920 anagramTest 62 none -anagram none 7 none 100 140332637550808 anagramTest 63 none -anagram none 7 none 100 140726366772528 anagramTest 64 none -anagram none 7 none 100 140332641566447 anagramTest 65 none -anagram none 7 none 100 65280 anagramTest 66 none -anagram none 7 none 100 0 anagramTest 67 none -anagram none 7 none 100 3399988123389603631 anagramTest 68 none -anagram none 7 none 100 3399988123389603631 anagramTest 69 none -anagram none 7 none 100 0 anagramTest 70 none -anagram none 7 none 100 0 anagramTest 71 none -anagram none 7 none 100 -72057594037927936 anagramTest 72 none -anagram none 7 none 100 -72057594037927936 anagramTest 73 none -anagram none 7 none 100 6872211992017990772 anagramTest 74 none -anagram none 7 none 100 8387223540636804214 anagramTest 75 none -anagram none 7 none 100 0 anagramTest 76 none -anagram none 7 none 100 0 anagramTest 77 none -anagram none 7 none 100 0 anagramTest 78 none -anagram none 7 none 100 0 anagramTest 79 none -anagram none 7 none 100 0 anagramTest 80 none -anagram none 7 none 100 0 anagramTest 81 none -anagram none 7 none 100 1 anagramTest 82 none -anagram none 7 none 100 0 anagramTest 83 none -anagram none 7 none 100 1 anagramTest 84 none -anagram none 7 none 100 140332643725672 anagramTest 85 none -anagram none 7 none 100 0 anagramTest 86 none -anagram none 7 none 100 140332643727104 anagramTest 87 none -anagram none 7 none 100 10 anagramTest 88 none -anagram none 7 none 100 -1 anagramTest 89 none -anagram none 7 none 100 85603611 anagramTest 90 none -anagram none 7 none 100 140726366778684 anagramTest 91 none -anagram none 7 none 100 140726366773128 anagramTest 92 none -anagram none 7 none 100 140726366772560 anagramTest 93 none -anagram none 7 none 100 140726366772816 anagramTest 94 none -anagram none 7 none 100 4196240 anagramTest 95 none -anagram none 7 none 100 140726366773040 anagramTest 96 none -anagram none 7 none 100 0 anagramTest 97 none -anagram none 7 none 100 0 anagramTest 98 none -anagram none 7 none 100 140332637720208 anagramTest 99 none diff --git a/baseline/source/anagram/anagram_compare.h b/baseline/source/anagram/anagram_compare.h deleted file mode 100644 index 31e869a..0000000 --- a/baseline/source/anagram/anagram_compare.h +++ /dev/null @@ -1,27 +0,0 @@ -/* - - This header is part of the TACLeBench benchmark suite. - Version 2.0 - - Name: anagram_compare.h - - Author: Raymond Chen - - Function: This header contains the comparison functions used by anagram. - - Source: unknown - - Original name: anagram - - Changes: See ChangeLog.txt - - License: See anagram.c - -*/ - -#ifndef ANAGRAM_COMPARE_H -#define ANAGRAM_COMPARE_H - -int anagram_CompareFrequency( char *pch1, char *pch2 ); - -#endif diff --git a/baseline/source/anagram/anagram_ctype.h b/baseline/source/anagram/anagram_ctype.h deleted file mode 100644 index ebb8232..0000000 --- a/baseline/source/anagram/anagram_ctype.h +++ /dev/null @@ -1,45 +0,0 @@ -/* - - This header is part of the TACLeBench benchmark suite. - Version 2.0 - - Name: anagram_ctype.h - - Author: Raymond Chen - - Function: This header contains some C library functions used by anagram. - - Source: unknown - - Original name: anagram - - Changes: See ChangeLog.txt - - License: See anagram.c - -*/ - -#ifndef ANAGRAM_CTYPE_H -#define ANAGRAM_CTYPE_H - -int anagram_islower( int c ) -{ - return 'a' <= c && c <= 'z'; -} - -int anagram_isupper( int c ) -{ - return 'A' <= c && c <= 'Z'; -} - -int anagram_isalpha( int c ) -{ - return anagram_isupper( c ) || anagram_islower( c ); -} - -int anagram_tolower( int c ) -{ - return anagram_isupper( c ) ? c + ( 'a' - 'A' ) : c; -} - -#endif diff --git a/baseline/source/anagram/anagram_input.c b/baseline/source/anagram/anagram_input.c deleted file mode 100644 index e3d5f71..0000000 --- a/baseline/source/anagram/anagram_input.c +++ /dev/null @@ -1,2317 +0,0 @@ -/* - - This file is part of the TACLeBench benchmark suite. - Version 2.0 - - Name: anagram_input.c - - Author: Raymond Chen - - Function: This file contains the input data used by anagram. - - Source: anagram - - Original name: anagram - - Changes: See ChangeLog.txt - - License: See anagram.c - -*/ - -/* - Forward declaration of global variables -*/ - -extern char const *anagram_achPhrase[ 3 ]; -extern char const *anagram_dictionary[ 2279 ]; - - -/* - Definition of global variables -*/ -char const *anagram_achPhrase[ 3 ] = { "todd austin", - "john alledy", - "mary updike" - }; - -char const *anagram_dictionary[ 2279 ] = { "2nd", - "4th", - "8th", - "a", - "ABA", - "aback", - "abash", - "abbas", - "abbey", - "abed", - "abet", - "abort", - "abut", - "Accra", - "ACM", - "acorn", - "Acts", - "Ada", - "adapt", - "added", - "addle", - "Adele", - "Aden", - "admix", - "adore", - "adult", - "affix", - "afire", - "aft", - "agate", - "agave", - "Agee", - "agent", - "agile", - "Agnew", - "agone", - "ahoy", - "Aida", - "aim", - "Ainu", - "airy", - "Ajax", - "Alamo", - "alarm", - "alb", - "Alcoa", - "alder", - "Aleck", - "alert", - "algae", - "alia", - "alike", - "alive", - "allay", - "alley", - "Allis", - "allow", - "ally", - "Allyn", - "aloe", - "aloha", - "along", - "aloud", - "also", - "alter", - "Alton", - "Alva", - "amaze", - "amber", - "ami", - "amigo", - "amiss", - "Amman", - "Amoco", - "amok", - "Amos", - "ample", - "amra", - "amy", - "Andes", - "angel", - "Angie", - "angry", - "Angus", - "Anne", - "annex", - "annoy", - "annul", - "ante", - "any", - "apex", - "apple", - "apron", - "apt", - "arch", - "argue", - "Aries", - "arm", - "army", - "aroma", - "array", - "arrow", - "Artie", - "arty", - "arum", - "a's", - "ash", - "ashen", - "ashy", - "askew", - "assai", - "Assam", - "Astor", - "ate", - "atlas", - "atone", - "audit", - "Aug", - "augur", - "auk", - "aural", - "avid", - "avoid", - "avow", - "awash", - "awe", - "awn", - "awry", - "axe", - "axial", - "axis", - "axon", - "Ayers", - "Aztec", - "b", - "babe", - "Bach", - "bad", - "bait", - "baldy", - "balm", - "balsa", - "bam", - "ban", - "bane", - "banjo", - "barb", - "barn", - "baron", - "basal", - "Basel", - "basil", - "bassi", - "baste", - "batch", - "Bates", - "batik", - "Bator", - "bawd", - "bay", - "bayed", - "bayou", - "be", - "beak", - "bean", - "beard", - "beat", - "beck", - "Becky", - "bed", - "bedim", - "bee", - "beech", - "beep", - "beet", - "befit", - "beg", - "begin", - "beige", - "Bela", - "belch", - "belt", - "beman", - "bench", - "Benny", - "bent", - "Benz", - "berth", - "beset", - "bet", - "betel", - "Bette", - "bevy", - "Bible", - "bide", - "big", - "bile", - "bilk", - "binge", - "bit", - "bite", - "black", - "blanc", - "bland", - "blare", - "blat", - "blaze", - "bled", - "blest", - "blind", - "Blinn", - "bliss", - "blitz", - "blob", - "blond", - "blood", - "bloom", - "blot", - "blown", - "blue", - "bluff", - "Blum", - "blur", - "board", - "boat", - "bock", - "bog", - "bogy", - "boil", - "Boise", - "bomb", - "bon", - "bong", - "bonus", - "bonze", - "booby", - "book", - "booky", - "boon", - "booze", - "bore", - "Boris", - "boron", - "Bosch", - "bosom", - "bound", - "bourn", - "bowel", - "boy", - "Boyce", - "bract", - "Brady", - "brag", - "brake", - "brant", - "brass", - "Braun", - "bravo", - "bread", - "bream", - "breve", - "brew", - "briar", - "Brice", - "brief", - "bring", - "briny", - "broad", - "broth", - "brunt", - "BSTJ", - "bub", - "buck", - "Budd", - "buddy", - "Buick", - "built", - "bulge", - "bulky", - "bum", - "bump", - "bunch", - "bundy", - "bunk", - "Burch", - "burg", - "burl", - "Burma", - "burnt", - "Burr", - "bury", - "bush", - "bushy", - "bust", - "busy", - "butte", - "butyl", - "buyer", - "by", - "bylaw", - "Byrd", - "byte", - "cab", - "cable", - "cacao", - "cacti", - "Cairo", - "Caleb", - "call", - "calm", - "canal", - "canoe", - "canon", - "can't", - "cap", - "caper", - "capo", - "card", - "Carey", - "Carib", - "Carla", - "carol", - "carve", - "cash", - "caste", - "catch", - "cater", - "caulk", - "cause", - "CBS", - "cedar", - "cent", - "Cetus", - "Chad", - "chaff", - "chair", - "champ", - "char", - "chasm", - "chaw", - "cheat", - "cheer", - "chef", - "Chen", - "chew", - "chick", - "chief", - "Chile", - "chill", - "chine", - "chip", - "chock", - "choir", - "chomp", - "chose", - "Chris", - "chuff", - "chum", - "chump", - "CIA", - "cinch", - "cite", - "city", - "clad", - "clan", - "clank", - "Clara", - "Claus", - "claw", - "clean", - "cleat", - "clerk", - "clime", - "cling", - "clink", - "Clio", - "clod", - "clomp", - "cloth", - "clove", - "cluck", - "clump", - "clung", - "Clyde", - "cobra", - "coco", - "coda", - "Cody", - "Cohn", - "coin", - "col", - "Colby", - "coney", - "Congo", - "cony", - "cool", - "coon", - "copra", - "copy", - "Corey", - "corn", - "corps", - "cos", - "cosy", - "couch", - "cough", - "count", - "coup", - "cove", - "cowry", - "coy", - "CPA", - "crack", - "craft", - "Craig", - "crank", - "crash", - "crate", - "crawl", - "craze", - "creak", - "cream", - "credo", - "creek", - "Creon", - "crept", - "crest", - "crew", - "crib", - "crime", - "crimp", - "crisp", - "crock", - "croft", - "crone", - "crook", - "crowd", - "CRT", - "crumb", - "crump", - "crush", - "crux", - "cub", - "cube", - "cuff", - "cup", - "Cupid", - "cur", - "curb", - "curie", - "cusp", - "cute", - "cycad", - "cynic", - "d", - "daffy", - "dairy", - "daisy", - "dally", - "dame", - "Damon", - "Dan", - "dance", - "Dane", - "dank", - "Dante", - "Dar", - "darn", - "dart", - "dash", - "davit", - "day", - "De", - "deaf", - "deal", - "death", - "debit", - "Dec", - "decal", - "Dee", - "Deere", - "deify", - "deity", - "Della", - "delta", - "demur", - "den", - "Denny", - "dense", - "deny", - "depth", - "desk", - "deus", - "devil", - "dewar", - "Dhabi", - "diary", - "dick", - "dicta", - "did", - "die", - "Diego", - "diety", - "dill", - "din", - "dine", - "dirty", - "disc", - "ditch", - "dive", - "DNA", - "dock", - "Dodd", - "doff", - "dogma", - "dolce", - "doll", - "dolly", - "done", - "door", - "dope", - "Doric", - "dose", - "dote", - "doubt", - "Doug", - "dove", - "dowel", - "doze", - "Dr", - "Draco", - "drama", - "drape", - "drawl", - "dread", - "dreg", - "dress", - "drew", - "drib", - "drier", - "drill", - "drip", - "dross", - "drown", - "druid", - "drunk", - "dry", - "du", - "Duane", - "ducat", - "duct", - "duel", - "duff", - "Duffy", - "Dugan", - "duke", - "dull", - "dulse", - "duly", - "dump", - "dumpy", - "dunce", - "dunk", -