1 /* The Computer Language Benchmarks Game
2 http://shootout.alioth.debian.org/
3 contributed by Andrew Moon
4 */
5
6 #include <stdio.h>
7 #include <stdlib.h>
8 #include <string.h>
9
10 // limit output, so we do not benchmark speed of printing
puts_limited(char * x)11 void puts_limited(char *x)
12 {
13 static int left = 550;
14 int len = strlen(x);
15 if (len <= left) {
16 puts(x);
17 left -= len;
18 return;
19 }
20 if (left > 0) {
21 x[left] = '\0';
22 puts(x);
23 x[left] = 'z';
24 left = 0;
25 }
26 }
27
28 struct Random {
29 enum { IM = 139968, IA = 3877, IC = 29573 };
RandomRandom30 Random() : last(42) {}
getRandom31 float get( float max = 1.0f ) {
32 last = ( last * IA + IC ) % IM;
33 return max * last / IM;
34 }
35 protected:
36 unsigned int last;
37 } rng;
38
39 struct IUB {
40 int c;
41 double p;
42 unsigned int pi;
43 };
44
45 struct Cumulative {
46 enum { slots = 512, };
47
CumulativeCumulative48 Cumulative( IUB *start ) {
49 double p = 0;
50 for ( IUB *iter = start; iter->c; ++iter ) {
51 p += iter->p;
52 iter->p = p < 1.0 ? p : 1.0;
53 iter->pi = (unsigned int )( iter->p * slots );
54 }
55
56 for ( unsigned int i = 0; i <= slots; i++ ) {
57 while ( i > start->pi && start->pi != 0) {
58 ++start;
59 }
60
61 table[i] = start;
62 }
63 }
64
operator []Cumulative65 const char operator[] ( float pct ) const {
66 IUB *iter = table[(unsigned int )( pct * slots )];
67 while ( iter->p < pct )
68 ++iter;
69 return iter->c;
70 }
71
72 protected:
73 IUB *table[slots + 1];
74 };
75
76 static const size_t lineLength = 60;
77
78 struct LineBuffer {
LineBufferLineBuffer79 LineBuffer() : lastN(0) {}
genrandLineBuffer80 LineBuffer &genrand( Cumulative &table, size_t N ) {
81 //assert(N <= lineLength);
82 for ( size_t i = 0; i < N; i++ )
83 buffer[i] = table[rng.get()];
84 buffer[N] = '\n';
85 buffer[N+1] = '\0';
86 lastN = N + 1;
87 return *this;
88 }
writelineLineBuffer89 void writeline() { puts_limited(buffer); }
90 protected:
91 char buffer[lineLength + 2];
92 size_t lastN;
93 };
94
95 struct RotatingString {
RotatingStringRotatingString96 RotatingString( const char *in ) : pos(0) {
97 size = strlen( in );
98 buffer = new char[size + lineLength];
99 memcpy( buffer, in, size );
100 memcpy( buffer + size, in, lineLength );
101 }
~RotatingStringRotatingString102 ~RotatingString() { delete[] buffer; }
writeRotatingString103 void write( size_t bytes ) {
104 char* temp = new char[bytes+2];
105 memcpy(temp, buffer + pos, bytes);
106 temp[bytes] = '\n';
107 temp[bytes] = '\0';
108 puts_limited(temp);
109 delete temp;
110 pos += bytes;
111 if ( pos > size )
112 pos -= size;
113 }
114 protected:
115 char *buffer;
116 size_t size, pos;
117 };
118
119 template< class Output >
makeFasta(const char * id,const char * desc,size_t N,Output & output)120 void makeFasta( const char *id, const char *desc, size_t N, Output &output ) {
121 while ( N ) {
122 const size_t bytes = N < lineLength ? N : lineLength;
123 output.writeline( bytes );
124 N -= bytes;
125 }
126 }
127
128 struct Repeater {
RepeaterRepeater129 Repeater( const char *alu ) : rot(alu) {}
writelineRepeater130 void writeline( size_t bytes ) { rot.write( bytes ); }
runRepeater131 void run( const char *id, const char *desc, size_t N ) {
132 makeFasta( id, desc, N, *this );
133 }
134 protected:
135 RotatingString rot;
136 };
137
138 struct Randomized {
RandomizedRandomized139 Randomized( IUB *start ) : table(start) {}
writelineRandomized140 void writeline( size_t bytes ) { line.genrand(table, bytes).writeline(); }
runRandomized141 void run( const char *id, const char *desc, size_t N ) {
142 makeFasta( id, desc, N, *this );
143 }
144 protected:
145 Cumulative table;
146 LineBuffer line;
147 };
148
149 IUB iub[] = {
150 { 'a', 0.27, 0 },
151 { 'c', 0.12, 0 },
152 { 'g', 0.12, 0 },
153 { 't', 0.27, 0 },
154
155 { 'B', 0.02, 0 },
156 { 'D', 0.02, 0 },
157 { 'H', 0.02, 0 },
158 { 'K', 0.02, 0 },
159 { 'M', 0.02, 0 },
160 { 'N', 0.02, 0 },
161 { 'R', 0.02, 0 },
162 { 'S', 0.02, 0 },
163 { 'V', 0.02, 0 },
164 { 'W', 0.02, 0 },
165 { 'Y', 0.02, 0 },
166 { 0, 0, 0 },
167 };
168
169 IUB homosapiens[] = {
170 { 'a', 0.3029549426680, 0 },
171 { 'c', 0.1979883004921, 0 },
172 { 'g', 0.1975473066391, 0 },
173 { 't', 0.3015094502008, 0 },
174 { 0, 0, 0 },
175 };
176
177 static const char alu[] =
178 "GGCCGGGCGCGGTGGCTCACGCCTGTAATCCCAGCACTTTG"
179 "GGAGGCCGAGGCGGGCGGATCACCTGAGGTCAGGAGTTCGA"
180 "GACCAGCCTGGCCAACATGGTGAAACCCCGTCTCTACTAAA"
181 "AATACAAAAATTAGCCGGGCGTGGTGGCGCGCGCCTGTAAT"
182 "CCCAGCTACTCGGGAGGCTGAGGCAGGAGAATCGCTTGAAC"
183 "CCGGGAGGCGGAGGTTGCAGTGAGCCGAGATCGCGCCACTG"
184 "CACTCCAGCCTGGGCGACAGAGCGAGACTCCGTCTCAAAAA";
185
main(int argc,const char * argv[])186 int main( int argc, const char *argv[] ) {
187 const size_t n = ( argc > 1 ) ? atoi( argv[1] ) : 512;
188
189 Repeater(alu)
190 .run( "ONE", "Homo sapiens alu", n*2 );
191 Randomized(iub)
192 .run( "TWO", "IUB ambiguity codes", n*3 );
193 Randomized(homosapiens)
194 .run( "THREE", "Homo sapiens frequency", n*5 );
195
196 return 0;
197 }
198
199