1 package icecream;
2 
3 import aligner.AlignmentResult;
4 import shared.KillSwitch;
5 import shared.Shared;
6 
7 public final class IceCreamAlignerJNI extends IceCreamAligner {
8 
9 	static {
Shared.loadJNI()10 		Shared.loadJNI();
11 	}
12 
IceCreamAlignerJNI()13 	IceCreamAlignerJNI(){}
14 
15 	/**
16 	 * @param query
17 	 * @param ref
18 	 * @param qstart
19 	 * @param rstart
20 	 * @param rstop
21 	 * @param minScore Quit early if score drops below this
22 	 * @param minRatio Don't return results if max score is less than this fraction of max possible score
23 	 * @return
24 	 */
25 	@Override
alignForward(final byte[] query, final byte[] ref, final int rstart, final int rstop, final int minScore, final float minRatio)26 	public AlignmentResult alignForward(final byte[] query, final byte[] ref, final int rstart, final int rstop, final int minScore,
27 			final float minRatio) {
28 
29 		final int qlen=query.length;
30 		final int rlen=rstop-rstart+1;
31 		final int[] retVec=KillSwitch.allocInt1D(4);
32 
33 //		alignForwardJNI(qInt, rInt, retVec, qlen, rlen, minScore, minRatio);
34 //		alignForwardPseudo(qInt, rInt, retVec, qlen, rlen, minScore, minRatio);
35 
36 		if((qlen+rlen+32)*2>Short.MAX_VALUE) {
37 			final int[] qInt=new int[query.length];
38 			final int[] rInt=new int[rlen];
39 			for(int i=0; i<query.length; i++){qInt[i]=query[i];}
40 			for(int i=0; i<rlen; i++){rInt[i]=ref[i+rstart];}
41 
42 //			alignForwardPseudo(qInt, rInt, retVec, qlen, rlen, minScore, minRatio);
43 			alignForwardJNI(qInt, rInt, retVec, qlen, rlen, minScore, minRatio);
44 //			alignForwardShortJNI(qInt, rInt, retVec, qlen, rlen);
45 		}else{
46 			final short[] qInt=new short[query.length];
47 			final short[] rInt=new short[rlen];
48 			for(int i=0; i<query.length; i++){qInt[i]=query[i];}
49 			for(int i=0; i<rlen; i++){rInt[i]=ref[i+rstart];}
50 
51 			alignForward16JNI(qInt, rInt, retVec, (short)qlen, (short)rlen, (short)minScore, minRatio);
52 //			alignForwardShort16JNI(qInt, rInt, retVec, (short)qlen, (short)rlen);
53 		}
54 
55 		int maxScore=retVec[0];
56 		final int maxQpos=retVec[1];
57 		final int maxRpos=retVec[2]+rstart;
58 		final int jniIters=retVec[3];
59 
60 		iters+=jniIters;
61 
62 		maxScore=(maxScore-pointsSub*query.length)/(pointsMatch-pointsSub);//Rescale 0 to length
63 		final float ratio=maxScore/(float)query.length;
64 
65 		if(ratio<minRatio){return null;}
66 
67 		return new AlignmentResult(maxScore, maxQpos, maxRpos, query.length, ref.length, rstart, rstop, ratio);
68 	}
69 
70 	/**
71 	 * @param query
72 	 * @param ref
73 	 * @param qstart
74 	 * @param rstart
75 	 * @param rstop
76 	 * @param minScore Quit early if score drops below this
77 	 * @param minRatio Don't return results if max score is less than this fraction of max possible score
78 	 * @return
79 	 */
80 	@Override
alignForwardShort(final byte[] query, final byte[] ref, final int rstart, final int rstop, final int minScore, final float minRatio)81 	public AlignmentResult alignForwardShort(final byte[] query, final byte[] ref, final int rstart, final int rstop, final int minScore,
82 			final float minRatio) {
83 
84 		final int qlen=query.length;
85 		final int rlen=rstop-rstart+1;
86 		final int[] retVec=KillSwitch.allocInt1D(4);
87 
88 		if((qlen+rlen+32)*2>Short.MAX_VALUE) {
89 			final int[] qInt=new int[query.length];
90 			final int[] rInt=new int[rlen];
91 			for(int i=0; i<query.length; i++){qInt[i]=query[i];}
92 			for(int i=0; i<rlen; i++){rInt[i]=ref[i+rstart];}
93 
94 //			alignForwardShortPseudo(qInt, rInt, retVec, qlen, rlen);
95 			alignForwardShortJNI(qInt, rInt, retVec, qlen, rlen);
96 		}else{
97 			final short[] qInt=new short[query.length];
98 			final short[] rInt=new short[rlen];
99 			for(int i=0; i<query.length; i++){qInt[i]=query[i];}
100 			for(int i=0; i<rlen; i++){rInt[i]=ref[i+rstart];}
101 
102 			alignForwardShort16JNI(qInt, rInt, retVec, (short)qlen, (short)rlen);
103 		}
104 		int maxScore=retVec[0];
105 		final int maxQpos=retVec[1];
106 		final int maxRpos=retVec[2]+rstart;
107 		final int jniIters=retVec[3];
108 
109 		itersShort+=jniIters;
110 
111 		maxScore=(maxScore-pointsSub*query.length)/(pointsMatch-pointsSub);//Rescale 0 to length
112 		final float ratio=maxScore/(float)query.length;
113 
114 		if(ratio<minRatio){return null;}
115 
116 		return new AlignmentResult(maxScore, maxQpos, maxRpos, query.length, ref.length, rstart, rstop, ratio);
117 	}
118 
119 	/*--------------------------------------------------------------*/
120 	/*----------------             JNI              ----------------*/
121 	/*--------------------------------------------------------------*/
122 
alignForwardPseudo(final int[] query, final int[] ref, final int[] retArray, final int qlen, final int rlen, final int minScore, final float minRatio)123 	private static void alignForwardPseudo(final int[] query, final int[] ref, final int[] retArray,
124 			final int qlen, final int rlen, final int minScore, final float minRatio) {
125 
126 		final int arrayLength=rlen;
127 		final int arrayLength2=rlen+1;
128 
129 		//Stack allocated; faster.
130 		int[] array1=new int[arrayLength2];
131 		int[] array2=new int[arrayLength2];
132 
133 		int[] prev=array1;
134 		int[] next=array2;
135 		int maxScore=-32000;
136 		int maxQpos=-1;
137 		int maxRpos=-1;
138 		int iters=0;
139 
140 		final int minPassingScore=(int)(qlen*minRatio*pointsMatch);
141 		final int minPassingScore3=minPassingScore-qlen*pointsMatch;
142 
143 		for(int i=0; i<=arrayLength-qlen; i++){prev[i]=0;}
144 		for(int i=arrayLength-qlen, score=0; i<=arrayLength; i++, score+=pointsDel) {
145 			prev[i]=score;
146 			next[i]=0;
147 		}
148 
149 		for(int qpos=0; qpos<qlen; qpos++){
150 			prev[0]=pointsIns*qpos;
151 
152 			final int q=query[qpos];
153 			int maxScoreThisPass=-32000;
154 			final int remainingBases=(qlen-qpos);
155 			final int remainingPoints=remainingBases*pointsMatch;
156 			final int minViableScore=minPassingScore3-remainingPoints;
157 
158 //			for(int rpos=0, apos=1; rpos<rlen; rpos++, apos++){
159 //				final int r=ref[rpos];
160 //				final boolean match=(q==r);
161 //				final int vScore=prev[apos]+pointsIns;
162 //				final int hScore=next[apos-1]+pointsDel;
163 //				final int dScore=(match ? pointsMatch : pointsSub)+prev[apos-1];
164 //
165 //				//Should be branchless conditional moves
166 //				int score=(dScore>=vScore ? dScore : vScore);
167 //				score=(hScore>score ? hScore : score);
168 //				next[apos]=score;
169 //				maxScoreThisPass=(score>maxScoreThisPass ? score : maxScoreThisPass);
170 //			}
171 
172 			for(int rpos=0, apos=1; rpos<rlen; rpos++, apos++){
173 				final int r=ref[rpos];
174 				final boolean match=(q==r);
175 				final int vScore=prev[apos]+pointsIns;
176 				final int dScore=(match ? pointsMatch : pointsSub)+prev[apos-1];
177 
178 				//Should be branchless conditional moves
179 				int score=(dScore>=vScore ? dScore : vScore);
180 				next[apos]=score;
181 			}
182 
183 			for(int apos=1; apos<arrayLength2; apos++){
184 				final int hScore=next[apos-1]+pointsDel;
185 
186 				//Should be branchless conditional moves
187 				int score=next[apos];
188 				score=(hScore>score ? hScore : score);
189 				next[apos]=score;
190 				maxScoreThisPass=(score>maxScoreThisPass ? score : maxScoreThisPass);
191 			}
192 			iters+=arrayLength;
193 
194 			//Aggressive early exit
195 			if(maxScoreThisPass<minScore){return;}
196 
197 			//Safe early exit
198 			if(maxScoreThisPass<minViableScore){return;}
199 
200 			int[] temp=prev;
201 			prev=next;
202 			next=temp;
203 		}
204 
205 		maxScore=-32000;
206 		for(int apos=1; apos<arrayLength2; apos++){//Grab high score from last iteration
207 			int score=prev[apos];
208 			if(score>=maxScore){
209 				maxScore=score;
210 				maxQpos=qlen;
211 				maxRpos=apos-1;
212 			}
213 		}
214 		retArray[0]=maxScore;
215 		retArray[1]=maxQpos;
216 		retArray[2]=maxRpos;
217 		retArray[3]=iters;
218 	}
219 
alignForwardShortPseudo(int[] query, int[] ref, int[] retArray, int qlen, int rlen)220 	private static void alignForwardShortPseudo(int[] query, int[] ref, int[] retArray, int qlen, int rlen) {
221 
222 		final int arrayLength=qlen;
223 		final int arrayLength2=qlen+1;
224 
225 		//Stack allocated; faster.
226 		int[] array1=new int[arrayLength2];
227 		int[] array2=new int[arrayLength2];
228 
229 		int[] prev=array1;
230 		int[] next=array2;
231 		int maxScore=-999999;
232 		int maxQpos=-1;
233 		int maxRpos=-1;
234 		int itersShort=0;
235 
236 		for(int i=0; i<arrayLength2; i++) {
237 			prev[i]=pointsIns*i;
238 			next[i]=0;//For C version initialization
239 		}
240 
241 		for(int rpos=0; rpos<rlen; rpos++){
242 			if(rlen-rpos<arrayLength){prev[0]=next[0]+pointsDel;}
243 
244 			final int r=ref[rpos];
245 			int score=0;
246 
247 //			//Inner loop
248 //			for(int qpos=0, apos=1; qpos<arrayLength; qpos++, apos++){
249 //				final int q=query[qpos];
250 //				final boolean match=(q==r);
251 //				final int vScore=prev[apos]+pointsIns;
252 //				final int hScore=next[apos-1]+pointsDel;
253 //				final int dScore=(match ? pointsMatch : pointsSub)+prev[apos-1];
254 //
255 //				score=(dScore>=vScore ? dScore : vScore);
256 //				score=(hScore>score ? hScore : score);
257 //
258 //				next[apos]=score;
259 //			}
260 
261 			//Inner DV loop
262 			for(int qpos=0, apos=1; qpos<arrayLength; qpos++, apos++){
263 				final int q=query[qpos];
264 				final boolean match=(q==r);
265 				final int vScore=prev[apos]+pointsIns;
266 				final int dScore=(match ? pointsMatch : pointsSub)+prev[apos-1];
267 
268 				score=(dScore>=vScore ? dScore : vScore);
269 
270 				next[apos]=score;
271 			}
272 
273 			//Inner I loop
274 			for(int qpos=0, apos=1; qpos<arrayLength; qpos++, apos++){
275 				final int hScore=next[apos-1]+pointsDel;
276 
277 				score=next[apos];
278 				score=(hScore>score ? hScore : score);
279 
280 				next[apos]=score;
281 			}
282 
283 			itersShort+=arrayLength;
284 
285 			if(score>=maxScore){
286 				maxScore=score;
287 				maxQpos=arrayLength-1;
288 				maxRpos=rpos;
289 			}
290 
291 			int[] temp=prev;
292 			prev=next;
293 			next=temp;
294 		}
295 		retArray[0]=maxScore;
296 		retArray[1]=maxQpos;
297 		retArray[2]=maxRpos;
298 		retArray[3]=itersShort;
299 	}
300 
alignForwardJNI(int[] query, int[] ref, int[] retArray, int qlen, int rlen, int minScore, float minRatio)301 	private static native void alignForwardJNI(int[] query, int[] ref, int[] retArray, int qlen, int rlen, int minScore, float minRatio);
alignForward16JNI(short[] query, short[] ref, int[] retArray, short qlen, short rlen, short minScore, float minRatio)302 	private static native void alignForward16JNI(short[] query, short[] ref, int[] retArray, short qlen, short rlen, short minScore, float minRatio);
alignForwardShortJNI(int[] query, int[] ref, int[] retArray, int qlen, int rlen)303 	private static native void alignForwardShortJNI(int[] query, int[] ref, int[] retArray, int qlen, int rlen);
alignForwardShort16JNI(short[] query, short[] ref, int[] retArray, short qlen, short rlen)304 	private static native void alignForwardShort16JNI(short[] query, short[] ref, int[] retArray, short qlen, short rlen);
305 
306 	/*--------------------------------------------------------------*/
307 	/*----------------           Getters            ----------------*/
308 	/*--------------------------------------------------------------*/
309 
310 	@Override
iters()311 	long iters(){return iters;}
312 
313 	@Override
itersShort()314 	long itersShort(){return itersShort;}
315 
316 	/*--------------------------------------------------------------*/
317 	/*----------------            Fields            ----------------*/
318 	/*--------------------------------------------------------------*/
319 
320 	long iters = 0;
321 	long itersShort = 0;
322 
323 	/*--------------------------------------------------------------*/
324 	/*----------------           Constants          ----------------*/
325 	/*--------------------------------------------------------------*/
326 
327 	public static final int pointsMatch = 1;
328 	public static final int pointsSub = -1;
329 	public static final int pointsDel = -2;
330 	public static final int pointsIns = -2;
331 
332 }
333