]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
1 | // The Computer Language Benchmarks Game |
2 | // http://benchmarksgame.alioth.debian.org/ | |
3 | // | |
4 | // contributed by the Rust Project Developers | |
970d7e83 | 5 | |
1a4d82fc JJ |
6 | // Copyright (c) 2013-2014 The Rust Project Developers |
7 | // | |
8 | // All rights reserved. | |
9 | // | |
10 | // Redistribution and use in source and binary forms, with or without | |
11 | // modification, are permitted provided that the following conditions | |
12 | // are met: | |
13 | // | |
14 | // - Redistributions of source code must retain the above copyright | |
15 | // notice, this list of conditions and the following disclaimer. | |
16 | // | |
17 | // - Redistributions in binary form must reproduce the above copyright | |
18 | // notice, this list of conditions and the following disclaimer in | |
19 | // the documentation and/or other materials provided with the | |
20 | // distribution. | |
21 | // | |
22 | // - Neither the name of "The Computer Language Benchmarks Game" nor | |
23 | // the name of "The Computer Language Shootout Benchmarks" nor the | |
24 | // names of its contributors may be used to endorse or promote | |
25 | // products derived from this software without specific prior | |
26 | // written permission. | |
27 | // | |
28 | // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
29 | // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
30 | // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS | |
31 | // FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE | |
32 | // COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, | |
33 | // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES | |
34 | // (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR | |
35 | // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |
36 | // HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, | |
37 | // STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | |
38 | // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED | |
39 | // OF THE POSSIBILITY OF SUCH DAMAGE. | |
970d7e83 | 40 | |
d9579d0f | 41 | // ignore-android: FIXME(#10393) hangs without output |
1a4d82fc | 42 | |
9346a6ac | 43 | #![feature(libc, scoped)] |
1a4d82fc JJ |
44 | |
45 | extern crate libc; | |
46 | ||
9346a6ac AL |
47 | use std::io; |
48 | use std::io::prelude::*; | |
49 | use std::ptr::copy; | |
85aaf69f | 50 | use std::thread; |
1a4d82fc JJ |
51 | |
52 | struct Tables { | |
d9579d0f AL |
53 | table8: Box<[u8; 1 << 8]>, |
54 | table16: Box<[u16; 1 << 16]>, | |
1a4d82fc JJ |
55 | } |
56 | ||
57 | impl Tables { | |
58 | fn new() -> Tables { | |
d9579d0f | 59 | let mut table8 = Box::new([0;1 << 8]); |
1a4d82fc JJ |
60 | for (i, v) in table8.iter_mut().enumerate() { |
61 | *v = Tables::computed_cpl8(i as u8); | |
62 | } | |
d9579d0f | 63 | let mut table16 = Box::new([0;1 << 16]); |
1a4d82fc JJ |
64 | for (i, v) in table16.iter_mut().enumerate() { |
65 | *v = (table8[i & 255] as u16) << 8 | | |
66 | table8[i >> 8] as u16; | |
67 | } | |
68 | Tables { table8: table8, table16: table16 } | |
69 | } | |
70 | ||
71 | fn computed_cpl8(c: u8) -> u8 { | |
72 | match c { | |
73 | b'A' | b'a' => b'T', | |
74 | b'C' | b'c' => b'G', | |
75 | b'G' | b'g' => b'C', | |
76 | b'T' | b't' => b'A', | |
77 | b'U' | b'u' => b'A', | |
78 | b'M' | b'm' => b'K', | |
79 | b'R' | b'r' => b'Y', | |
80 | b'W' | b'w' => b'W', | |
81 | b'S' | b's' => b'S', | |
82 | b'Y' | b'y' => b'R', | |
83 | b'K' | b'k' => b'M', | |
84 | b'V' | b'v' => b'B', | |
85 | b'H' | b'h' => b'D', | |
86 | b'D' | b'd' => b'H', | |
87 | b'B' | b'b' => b'V', | |
88 | b'N' | b'n' => b'N', | |
89 | i => i, | |
90 | } | |
91 | } | |
92 | ||
85aaf69f | 93 | /// Retrieves the complement for `i`. |
1a4d82fc | 94 | fn cpl8(&self, i: u8) -> u8 { |
c34b1796 | 95 | self.table8[i as usize] |
1a4d82fc JJ |
96 | } |
97 | ||
85aaf69f | 98 | /// Retrieves the complement for `i`. |
1a4d82fc | 99 | fn cpl16(&self, i: u16) -> u16 { |
c34b1796 | 100 | self.table16[i as usize] |
1a4d82fc JJ |
101 | } |
102 | } | |
103 | ||
1a4d82fc | 104 | /// Finds the first position at which `b` occurs in `s`. |
c34b1796 | 105 | fn memchr(h: &[u8], n: u8) -> Option<usize> { |
1a4d82fc JJ |
106 | use libc::{c_void, c_int, size_t}; |
107 | let res = unsafe { | |
108 | libc::memchr(h.as_ptr() as *const c_void, n as c_int, h.len() as size_t) | |
109 | }; | |
110 | if res.is_null() { | |
111 | None | |
112 | } else { | |
c34b1796 | 113 | Some(res as usize - h.as_ptr() as usize) |
1a4d82fc JJ |
114 | } |
115 | } | |
116 | ||
117 | /// A mutable iterator over DNA sequences | |
118 | struct MutDnaSeqs<'a> { s: &'a mut [u8] } | |
119 | fn mut_dna_seqs<'a>(s: &'a mut [u8]) -> MutDnaSeqs<'a> { | |
120 | MutDnaSeqs { s: s } | |
121 | } | |
122 | impl<'a> Iterator for MutDnaSeqs<'a> { | |
123 | type Item = &'a mut [u8]; | |
124 | ||
125 | fn next(&mut self) -> Option<&'a mut [u8]> { | |
126 | let tmp = std::mem::replace(&mut self.s, &mut []); | |
127 | let tmp = match memchr(tmp, b'\n') { | |
85aaf69f | 128 | Some(i) => &mut tmp[i + 1..], |
1a4d82fc JJ |
129 | None => return None, |
130 | }; | |
131 | let (seq, tmp) = match memchr(tmp, b'>') { | |
132 | Some(i) => tmp.split_at_mut(i), | |
133 | None => { | |
134 | let len = tmp.len(); | |
135 | tmp.split_at_mut(len) | |
970d7e83 | 136 | } |
1a4d82fc JJ |
137 | }; |
138 | self.s = tmp; | |
139 | Some(seq) | |
140 | } | |
141 | } | |
970d7e83 | 142 | |
1a4d82fc | 143 | /// Length of a normal line without the terminating \n. |
c34b1796 | 144 | const LINE_LEN: usize = 60; |
1a4d82fc JJ |
145 | |
146 | /// Compute the reverse complement. | |
147 | fn reverse_complement(seq: &mut [u8], tables: &Tables) { | |
9346a6ac AL |
148 | let len = seq.len(); |
149 | let seq = &mut seq[..len - 1]; // Drop the last newline | |
1a4d82fc JJ |
150 | let len = seq.len(); |
151 | let off = LINE_LEN - len % (LINE_LEN + 1); | |
152 | let mut i = LINE_LEN; | |
153 | while i < len { | |
154 | unsafe { | |
c34b1796 AL |
155 | copy(seq.as_ptr().offset((i - off) as isize), |
156 | seq.as_mut_ptr().offset((i - off + 1) as isize), off); | |
1a4d82fc | 157 | *seq.get_unchecked_mut(i - off) = b'\n'; |
970d7e83 | 158 | } |
1a4d82fc JJ |
159 | i += LINE_LEN + 1; |
160 | } | |
970d7e83 | 161 | |
1a4d82fc JJ |
162 | let div = len / 4; |
163 | let rem = len % 4; | |
164 | unsafe { | |
165 | let mut left = seq.as_mut_ptr() as *mut u16; | |
166 | // This is slow if len % 2 != 0 but still faster than bytewise operations. | |
c34b1796 AL |
167 | let mut right = seq.as_mut_ptr().offset(len as isize - 2) as *mut u16; |
168 | let end = left.offset(div as isize); | |
1a4d82fc JJ |
169 | while left != end { |
170 | let tmp = tables.cpl16(*left); | |
171 | *left = tables.cpl16(*right); | |
172 | *right = tmp; | |
173 | left = left.offset(1); | |
174 | right = right.offset(-1); | |
175 | } | |
176 | ||
177 | let end = end as *mut u8; | |
178 | match rem { | |
179 | 1 => *end = tables.cpl8(*end), | |
180 | 2 => { | |
181 | let tmp = tables.cpl8(*end); | |
182 | *end = tables.cpl8(*end.offset(1)); | |
183 | *end.offset(1) = tmp; | |
184 | }, | |
185 | 3 => { | |
186 | *end.offset(1) = tables.cpl8(*end.offset(1)); | |
187 | let tmp = tables.cpl8(*end); | |
188 | *end = tables.cpl8(*end.offset(2)); | |
189 | *end.offset(2) = tmp; | |
190 | }, | |
191 | _ => { }, | |
192 | } | |
970d7e83 LB |
193 | } |
194 | } | |
1a4d82fc | 195 | |
1a4d82fc JJ |
196 | /// Executes a closure in parallel over the given iterator over mutable slice. |
197 | /// The closure `f` is run in parallel with an element of `iter`. | |
9346a6ac AL |
198 | fn parallel<I: Iterator, F>(iter: I, ref f: F) |
199 | where I::Item: Send, | |
200 | F: Fn(I::Item) + Sync, { | |
85aaf69f | 201 | iter.map(|x| { |
9346a6ac | 202 | thread::scoped(move || f(x)) |
1a4d82fc JJ |
203 | }).collect::<Vec<_>>(); |
204 | } | |
205 | ||
206 | fn main() { | |
9346a6ac | 207 | let mut data = Vec::with_capacity(1024 * 1024); |
d9579d0f | 208 | io::stdin().read_to_end(&mut data).unwrap(); |
1a4d82fc | 209 | let tables = &Tables::new(); |
85aaf69f | 210 | parallel(mut_dna_seqs(&mut data), |seq| reverse_complement(seq, tables)); |
9346a6ac | 211 | io::stdout().write_all(&data).unwrap(); |
1a4d82fc | 212 | } |