src/test/bench/shootout-reverse-complement.rs

   1 // The Computer Language Benchmarks Game
   2 // http://benchmarksgame.alioth.debian.org/
   3 //
   4 // contributed by the Rust Project Developers
   5
   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.
  40
  41 // ignore-android: FIXME(#10393) hangs without output
  42
  43 #![feature(libc)]
  44
  45 extern crate libc;
  46
  47 use std::io;
  48 use std::io::prelude::*;
  49 use std::ptr::copy;
  50 use std::thread;
  51
  52 struct Tables {
  53     table8: Box<[u8; 1 << 8]>,
  54     table16: Box<[u16; 1 << 16]>,
  55 }
  56
  57 impl Tables {
  58     fn new() -> Tables {
  59         let mut table8 = Box::new([0;1 << 8]);
  60         for (i, v) in table8.iter_mut().enumerate() {
  61             *v = Tables::computed_cpl8(i as u8);
  62         }
  63         let mut table16 = Box::new([0;1 << 16]);
  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
  93     /// Retrieves the complement for `i`.
  94     fn cpl8(&self, i: u8) -> u8 {
  95         self.table8[i as usize]
  96     }
  97
  98     /// Retrieves the complement for `i`.
  99     fn cpl16(&self, i: u16) -> u16 {
 100         self.table16[i as usize]
 101     }
 102 }
 103
 104 /// Finds the first position at which `b` occurs in `s`.
 105 fn memchr(h: &[u8], n: u8) -> Option<usize> {
 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 {
 113         Some(res as usize - h.as_ptr() as usize)
 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') {
 128             Some(i) => &mut tmp[i + 1..],
 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)
 136             }
 137         };
 138         self.s = tmp;
 139         Some(seq)
 140     }
 141 }
 142
 143 /// Length of a normal line without the terminating \n.
 144 const LINE_LEN: usize = 60;
 145
 146 /// Compute the reverse complement.
 147 fn reverse_complement(seq: &mut [u8], tables: &Tables) {
 148     let len = seq.len();
 149     let seq = &mut seq[..len - 1]; // Drop the last newline
 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 {
 155             copy(seq.as_ptr().offset((i - off) as isize),
 156                  seq.as_mut_ptr().offset((i - off + 1) as isize), off);
 157             *seq.get_unchecked_mut(i - off) = b'\n';
 158         }
 159         i += LINE_LEN + 1;
 160     }
 161
 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.
 167         let mut right = seq.as_mut_ptr().offset(len as isize - 2) as *mut u16;
 168         let end = left.offset(div as isize);
 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         }
 193     }
 194 }
 195
 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`.
 198 // FIXME: replace with thread::scoped when it exists again
 199 fn parallel<I: Iterator, F>(iter: I, ref f: F)
 200         where I::Item: Send,
 201               F: Fn(I::Item) + Sync, {
 202     iter.map(|x| {
 203         f(x)
 204     }).collect::<Vec<_>>();
 205 }
 206
 207 fn main() {
 208     let mut data = Vec::with_capacity(1024 * 1024);
 209     io::stdin().read_to_end(&mut data).unwrap();
 210     let tables = &Tables::new();
 211     parallel(mut_dna_seqs(&mut data), |seq| reverse_complement(seq, tables));
 212     io::stdout().write_all(&data).unwrap();
 213 }