NVBIO
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
packedstream_test.cpp
Go to the documentation of this file.
1 /*
2  * nvbio
3  * Copyright (c) 2011-2014, NVIDIA CORPORATION. All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions are met:
7  * * Redistributions of source code must retain the above copyright
8  * notice, this list of conditions and the following disclaimer.
9  * * Redistributions in binary form must reproduce the above copyright
10  * notice, this list of conditions and the following disclaimer in the
11  * documentation and/or other materials provided with the distribution.
12  * * Neither the name of the NVIDIA CORPORATION nor the
13  * names of its contributors may be used to endorse or promote products
14  * derived from this software without specific prior written permission.
15  *
16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
17  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
18  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
19  * DISCLAIMED. IN NO EVENT SHALL NVIDIA CORPORATION BE LIABLE FOR ANY
20  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
21  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
22  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
23  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26  */
27 
28 // packedstream_test.cpp
29 //
30 
31 #include <stdio.h>
32 #include <stdlib.h>
33 #include <string.h>
34 #include <algorithm>
35 #include <nvbio/basic/types.h>
38 #include <sais.h>
39 
40 using namespace nvbio;
41 
42 static const uint32 LEN = 100;
43 
44 template <typename CompStream>
45 bool check_stream(const uint8* uncomp_stream, const CompStream& comp_stream)
46 {
47  for (uint32 i = 0; i < LEN; ++i)
48  {
49  if (uncomp_stream[i] != comp_stream[i])
50  {
51  fprintf(stderr, " error at %u : found %u, expected %u\n", i, uint32( comp_stream[i] ), uint32( uncomp_stream[i] ));
52  return false;
53  }
54  }
55  return true;
56 }
57 
58 template <typename CompStream>
59 bool check_forward_stream(const uint8* uncomp_stream, CompStream comp_stream)
60 {
61  for (uint32 i = 0; i < LEN; ++i)
62  {
63  if (uncomp_stream[i] != *comp_stream)
64  {
65  fprintf(stderr, " forward iterator error at %u : found %u, expected %u\n", i, uint32( *comp_stream ), uint32( uncomp_stream[i] ));
66  return false;
67  }
68  ++comp_stream;
69  }
70  return true;
71 }
72 
74 {
75  {
76  uint32 base_stream[LEN] = { 0u };
77  uint8 uncomp_stream[2*LEN] = { 0u };
78 
80  Stream stream( base_stream );
81 
82  fprintf(stderr, "2-bit stream test... started\n");
83 
84  if (check_stream( uncomp_stream, stream ) == false)
85  exit(1);
86 
87  stream.set( 0, uint8(3) );
88  uncomp_stream[0] = uint8(3);
89 
90  if (check_stream( uncomp_stream, stream ) == false)
91  exit(1);
92 
93  stream.set( 2, uint8(2) );
94  uncomp_stream[2] = uint8(2);
95 
96  if (check_stream( uncomp_stream, stream ) == false)
97  exit(1);
98 
99  stream.set( 16, uint8(3) );
100  uncomp_stream[16] = uint8(3);
101 
102  if (check_stream( uncomp_stream, stream ) == false)
103  exit(1);
104 
105  stream.set( 17, uint8(1) );
106  uncomp_stream[17] = uint8(1);
107 
108  if (check_stream( uncomp_stream, stream ) == false)
109  exit(1);
110 
111  // randomized test
112  for (uint32 i = 0; i < 1000; ++i)
113  {
114  const uint32 j = rand() % LEN;
115  const uint32 s = rand() % 4;
116  stream[j] = s;
117  uncomp_stream[j] = s;
118 
119  if (check_stream( uncomp_stream, stream ) == false)
120  exit(1);
121  }
122  // randomized test
123  Stream::iterator it = stream.begin();
124  for (uint32 i = 0; i < 1000; ++i)
125  {
126  const uint32 j = rand() % LEN;
127  const uint32 s = rand() % 4;
128  it[j] = s;
129  uncomp_stream[j] = s;
130 
131  if (check_stream( uncomp_stream, stream ) == false)
132  exit(1);
133  }
134 
135  std::swap( *uncomp_stream, *(uncomp_stream+1) );
136  std::swap( *stream.begin(), *(stream.begin()+1) );
137  if (check_stream( uncomp_stream, stream ) == false)
138  exit(1);
139 
140  std::sort( uncomp_stream, uncomp_stream + LEN );
141  std::sort( stream.begin(), stream.begin() + LEN );
142  if (check_stream( uncomp_stream, stream ) == false)
143  exit(1);
144 
145  typedef PackedStream<const_cached_iterator<uint32*>,uint8,2,true> CachedPackedStream;
146  const_cached_iterator<uint32*> cached_base_stream( base_stream );
147  CachedPackedStream cached_stream( cached_base_stream );
148  for (uint32 i = 0; i < LEN; ++i)
149  {
150  if (uncomp_stream[i] != cached_stream[i])
151  {
152  fprintf(stderr, " error at %u : found %u, expected %u\n", i, uint32( cached_stream[i] ), uint32( uncomp_stream[i] ));
153  return false;
154  }
155  }
156 
157  // test the SAIS module
158  stream[0] = 1; // B
159  stream[1] = 0; // A
160  stream[2] = 2; // N
161  stream[3] = 0; // A
162  stream[4] = 2; // N
163  stream[5] = 0; // A
164 
165  int32 SA[6];
166  saisxx( stream.begin(), SA, 6, 4 );
167  if (SA[0] != 5 ||
168  SA[1] != 3 ||
169  SA[2] != 1 ||
170  SA[3] != 0 ||
171  SA[4] != 4 ||
172  SA[5] != 2)
173  {
174  fprintf(stderr, " wrong suffix tree for \"BANANA\"\n");
175  for (uint32 i = 0; i < 6; ++i)
176  fprintf(stderr, "%u : %u\n", i, SA[i]);
177  exit(1);
178  }
179  uint32 base_bwt_stream[LEN] = { 0u };
180  Stream bwt_stream( base_bwt_stream );
181 
182  saisxx_bwt( stream.begin(), bwt_stream.begin(), SA, 6, 4 );
183  char bwt[7];
184  for (uint32 i = 0; i < 6; ++i)
185  {
186  const uint8 c = bwt_stream[i];
187  bwt[i] =
188  c == 0 ? 'A' :
189  c == 1 ? 'B' :
190  c == 2 ? 'N' :
191  'T';
192  }
193  bwt[6] = '\0';
194  if (strcmp( bwt, "ANNBAA" ) != 0)
195  {
196  fprintf(stderr, " wrong bwt: expected \"ANNBAA\", got \"%s\"\n", bwt);
197  exit(1);
198  }
199 
200  fprintf(stderr, "2-bit stream test... done\n");
201  }
202  {
203  uint32 base_stream[LEN] = { 0u };
204  uint8 uncomp_stream[4*LEN] = { 0u };
205 
206  fprintf(stderr, "4-bit uint32-stream test... started\n");
208 
209  if (check_stream( uncomp_stream, stream ) == false)
210  exit(1);
211 
212  stream.set( 9, uint8(5) );
213  uncomp_stream[9] = uint8(5);
214  if (check_stream( uncomp_stream, stream ) == false)
215  exit(1);
216 
217  stream.set( 10, uint8(15) );
218  uncomp_stream[10] = uint8(15);
219  if (check_stream( uncomp_stream, stream ) == false)
220  exit(1);
221 
222  // randomized test
223  for (uint32 i = 0; i < 1000; ++i)
224  {
225  const uint32 j = rand() % LEN;
226  const uint32 s = rand() % 16;
227  stream[j] = s;
228  uncomp_stream[j] = s;
229 
230  if (check_stream( uncomp_stream, stream ) == false)
231  exit(1);
232  }
233 
234  std::sort( uncomp_stream, uncomp_stream + LEN );
235  std::sort( stream.begin(), stream.begin() + LEN );
236  if (check_stream( uncomp_stream, stream ) == false)
237  exit(1);
238 
239  ForwardPackedStream<const uint32*,uint8,4,true> forward_stream( stream );
240  if (check_forward_stream( uncomp_stream, forward_stream ) == false)
241  exit(1);
242 
243  const_cached_iterator<const uint32*> cached_base_stream( base_stream );
244  PackedStream<const_cached_iterator<const uint32*>,uint8,4,true> cached_stream( cached_base_stream );
245  if (check_stream( uncomp_stream, cached_stream ) == false)
246  exit(1);
247 
248  fprintf(stderr, "4-bit uint32-stream test... done\n");
249  }
250  {
251  uint4 base_stream[LEN] = { { 0u } };
252  uint8 uncomp_stream[4*LEN] = { 0u };
253 
254  fprintf(stderr, "4-bit uint4-stream test... started\n");
256 
257  if (check_stream( uncomp_stream, stream ) == false)
258  exit(1);
259 
260  stream.set( 9, uint8(5) );
261  uncomp_stream[9] = uint8(5);
262  if (check_stream( uncomp_stream, stream ) == false)
263  exit(1);
264 
265  stream.set( 10, uint8(15) );
266  uncomp_stream[10] = uint8(15);
267  if (check_stream( uncomp_stream, stream ) == false)
268  exit(1);
269 
270  // randomized test
271  for (uint32 i = 0; i < 1000; ++i)
272  {
273  const uint32 j = rand() % LEN;
274  const uint32 s = rand() % 16;
275  stream[j] = s;
276  uncomp_stream[j] = s;
277 
278  if (check_stream( uncomp_stream, stream ) == false)
279  exit(1);
280  }
281 
282  std::sort( uncomp_stream, uncomp_stream + LEN );
283  std::sort( stream.begin(), stream.begin() + LEN );
284  if (check_stream( uncomp_stream, stream ) == false)
285  exit(1);
286 
287  ForwardPackedStream<const uint4*,uint8,4,true> forward_stream( stream );
288  if (check_forward_stream( uncomp_stream, forward_stream ) == false)
289  exit(1);
290 
291  const_cached_iterator<const uint4*> cached_base_stream( base_stream );
292  PackedStream<const_cached_iterator<const uint4*>,uint8,4,true> cached_stream( cached_base_stream );
293  if (check_stream( uncomp_stream, cached_stream ) == false)
294  exit(1);
295 
296  fprintf(stderr, "4-bit uint4-stream test... done\n");
297  }
298  {
299  uint32 base_stream[LEN] = { 0u };
300  uint8 uncomp_stream[3*LEN] = { 0u };
301 
302  fprintf(stderr, "3-bit uint32-stream test... started\n");
304 
305  if (check_stream( uncomp_stream, stream ) == false)
306  exit(1);
307 
308  stream.set( 9, uint8(5) );
309  uncomp_stream[9] = uint8(5);
310  if (check_stream( uncomp_stream, stream ) == false)
311  exit(1);
312 
313  stream.set( 10, uint8(7) );
314  uncomp_stream[10] = uint8(7);
315  if (check_stream( uncomp_stream, stream ) == false)
316  exit(1);
317 
318  // randomized test
319  for (uint32 i = 0; i < 1000; ++i)
320  {
321  const uint32 j = rand() % LEN;
322  const uint32 s = rand() % 8;
323  stream[j] = s;
324  uncomp_stream[j] = s;
325 
326  if (check_stream( uncomp_stream, stream ) == false)
327  exit(1);
328  }
329 
330  std::sort( uncomp_stream, uncomp_stream + LEN );
331  std::sort( stream.begin(), stream.begin() + LEN );
332  if (check_stream( uncomp_stream, stream ) == false)
333  exit(1);
334 
335  fprintf(stderr, "3-bit uint32-stream test... done\n");
336  }
337  {
338  uint8 base_stream[LEN] = { 0u };
339  uint8 uncomp_stream[2*LEN] = { 0u };
340 
341  fprintf(stderr, "2-bit byte-stream test... started\n");
343 
344  if (check_stream( uncomp_stream, stream ) == false)
345  exit(1);
346 
347  stream.set( 9, uint8(3) );
348  uncomp_stream[9] = uint8(3);
349  if (check_stream( uncomp_stream, stream ) == false)
350  exit(1);
351 
352  stream.set( 10, uint8(2) );
353  uncomp_stream[10] = uint8(2);
354  if (check_stream( uncomp_stream, stream ) == false)
355  exit(1);
356 
357  // randomized test
358  for (uint32 i = 0; i < 1000; ++i)
359  {
360  const uint32 j = rand() % LEN;
361  const uint32 s = rand() % 4;
362  stream[j] = s;
363  uncomp_stream[j] = s;
364 
365  if (check_stream( uncomp_stream, stream ) == false)
366  exit(1);
367  }
368 
369  std::sort( uncomp_stream, uncomp_stream + LEN );
370  std::sort( stream.begin(), stream.begin() + LEN );
371  if (check_stream( uncomp_stream, stream ) == false)
372  exit(1);
373 
374  ForwardPackedStream<const uint8*,uint8,2,true> forward_stream( stream );
375  if (check_forward_stream( uncomp_stream, forward_stream ) == false)
376  exit(1);
377 
378  fprintf(stderr, "2-bit byte-stream test... done\n");
379  }
380  {
381  uint4 base_stream[LEN] = { { 0u } };
382  uint8 uncomp_stream[4*LEN] = { 0u };
383 
384  fprintf(stderr, "2-bit uint4-stream test... started\n");
386 
387  if (check_stream( uncomp_stream, stream ) == false)
388  exit(1);
389 
390  stream.set( 9, uint8(3) );
391  uncomp_stream[9] = uint8(3);
392  if (check_stream( uncomp_stream, stream ) == false)
393  exit(1);
394 
395  stream.set( 10, uint8(2) );
396  uncomp_stream[10] = uint8(2);
397  if (check_stream( uncomp_stream, stream ) == false)
398  exit(1);
399 
400  // randomized test
401  for (uint32 i = 0; i < 1000; ++i)
402  {
403  const uint32 j = rand() % LEN;
404  const uint32 s = rand() % 4;
405  stream[j] = s;
406  uncomp_stream[j] = s;
407 
408  if (check_stream( uncomp_stream, stream ) == false)
409  exit(1);
410  }
411 
412  std::sort( uncomp_stream, uncomp_stream + LEN );
413  std::sort( stream.begin(), stream.begin() + LEN );
414  if (check_stream( uncomp_stream, stream ) == false)
415  exit(1);
416 
417  fprintf(stderr, "2-bit uint4-stream test... done\n");
418  }
419 
420  return 0;
421 }