From 386b7d3366f1359a265da207a9cafa3edf553b64 Mon Sep 17 00:00:00 2001 From: Joshua Bakita Date: Mon, 7 Oct 2019 19:13:39 -0400 Subject: Reorganize and commit all the modified TACLeBench code and run scripts --- all_pairs/source/anagram/ChangeLog.txt | 125 ++ all_pairs/source/anagram/anagram.c | 670 ++++++++ all_pairs/source/anagram/anagramTest.txt | 100 ++ all_pairs/source/anagram/anagram_compare.h | 27 + all_pairs/source/anagram/anagram_ctype.h | 45 + all_pairs/source/anagram/anagram_input.c | 2317 ++++++++++++++++++++++++++++ all_pairs/source/anagram/anagram_stdlib.c | 153 ++ all_pairs/source/anagram/anagram_stdlib.h | 29 + all_pairs/source/anagram/anagram_strings.h | 27 + 9 files changed, 3493 insertions(+) create mode 100644 all_pairs/source/anagram/ChangeLog.txt create mode 100644 all_pairs/source/anagram/anagram.c create mode 100644 all_pairs/source/anagram/anagramTest.txt create mode 100644 all_pairs/source/anagram/anagram_compare.h create mode 100644 all_pairs/source/anagram/anagram_ctype.h create mode 100644 all_pairs/source/anagram/anagram_input.c create mode 100644 all_pairs/source/anagram/anagram_stdlib.c create mode 100644 all_pairs/source/anagram/anagram_stdlib.h create mode 100644 all_pairs/source/anagram/anagram_strings.h (limited to 'all_pairs/source/anagram') diff --git a/all_pairs/source/anagram/ChangeLog.txt b/all_pairs/source/anagram/ChangeLog.txt new file mode 100644 index 0000000..fdba1cc --- /dev/null +++ b/all_pairs/source/anagram/ChangeLog.txt @@ -0,0 +1,125 @@ +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/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 */ + 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