1 /*
  2  * Copyright (c) 2017, 2021, Oracle and/or its affiliates. All rights reserved.
  3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  4  *
  5  * This code is free software; you can redistribute it and/or modify it
  6  * under the terms of the GNU General Public License version 2 only, as
  7  * published by the Free Software Foundation.  Oracle designates this
  8  * particular file as subject to the "Classpath" exception as provided
  9  * by Oracle in the LICENSE file that accompanied this code.
 10  *
 11  * This code is distributed in the hope that it will be useful, but WITHOUT
 12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 14  * version 2 for more details (a copy is included in the LICENSE file that
 15  * accompanied this code).
 16  *
 17  * You should have received a copy of the GNU General Public License version
 18  * 2 along with this work; if not, write to the Free Software Foundation,
 19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 20  *
 21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 22  * or visit www.oracle.com if you need additional information or have any
 23  * questions.
 24  */
 25 package jdk.incubator.vector;
 26 
 27 import java.util.Objects;
 28 
 29 import jdk.internal.vm.annotation.ForceInline;
 30 
 31 import jdk.internal.misc.Unsafe;
 32 
 33 import jdk.internal.vm.vector.VectorSupport;
 34 
 35 import static jdk.incubator.vector.VectorOperators.*;
 36 
 37 abstract class AbstractMask<E> extends VectorMask<E> {
 38     AbstractMask(boolean[] bits) {
 39         super(bits);
 40     }
 41 
 42     /*package-private*/
 43     abstract boolean[] getBits();
 44 
 45     // Unary operator
 46 
 47     interface MUnOp {
 48         boolean apply(int i, boolean a);
 49     }
 50 
 51     abstract AbstractMask<E> uOp(MUnOp f);
 52 
 53     // Binary operator
 54 
 55     interface MBinOp {
 56         boolean apply(int i, boolean a, boolean b);
 57     }
 58 
 59     abstract AbstractMask<E> bOp(VectorMask<E> o, MBinOp f);
 60 
 61     /*package-private*/
 62     abstract AbstractSpecies<E> vspecies();
 63 
 64     @Override
 65     @ForceInline
 66     public final VectorSpecies<E> vectorSpecies() {
 67         return vspecies();
 68     }
 69 
 70     @Override
 71     @ForceInline
 72     public boolean laneIsSet(int i) {
 73         int length = length();
 74         Objects.checkIndex(i, length);
 75         if (length <= Long.SIZE) {
 76             return ((toLong() >>> i) & 1L) == 1;
 77         } else {
 78             return getBits()[i];
 79         }
 80     }
 81 
 82     @Override
 83     public void intoArray(boolean[] bits, int i) {
 84         AbstractSpecies<E> vsp = (AbstractSpecies<E>) vectorSpecies();
 85         int laneCount = vsp.laneCount();
 86         i = VectorIntrinsics.checkFromIndexSize(i, laneCount, bits.length);
 87         VectorSupport.store(
 88             vsp.maskType(), vsp.elementType(), laneCount,
 89             bits, (long) i + Unsafe.ARRAY_BOOLEAN_BASE_OFFSET,
 90             this, bits, i,
 91             (c, idx, s) -> System.arraycopy(s.getBits(), 0, c, (int) idx, s.length()));
 92 
 93     }
 94 
 95     @Override
 96     public boolean[] toArray() {
 97         return getBits().clone();
 98     }
 99 
100     @Override
101     @ForceInline
102     @SuppressWarnings("unchecked")
103     public
104     <F> VectorMask<F> check(Class<F> elementType) {
105         if (vectorSpecies().elementType() != elementType) {
106             throw AbstractSpecies.checkFailed(this, elementType);
107         }
108         return (VectorMask<F>) this;
109     }
110 
111     @Override
112     @ForceInline
113     @SuppressWarnings("unchecked")
114     public
115     <F> VectorMask<F> check(VectorSpecies<F> species) {
116         if (species != vectorSpecies()) {
117             throw AbstractSpecies.checkFailed(this, species);
118         }
119         return (VectorMask<F>) this;
120     }
121 
122     @Override
123     @ForceInline
124     @SuppressWarnings("unchecked")
125     <F> VectorMask<F> check(Class<? extends VectorMask<F>> maskClass, Vector<F> vector) {
126         if (!sameSpecies(maskClass, vector)) {
127             throw AbstractSpecies.checkFailed(this, vector);
128         }
129         return (VectorMask<F>) this;
130     }
131 
132     @ForceInline
133     private <F> boolean sameSpecies(Class<? extends VectorMask<F>> maskClass, Vector<F> vector) {
134         boolean same = getClass() == maskClass;
135         assert (same == (vectorSpecies() == vector.species())) : same;
136         return same;
137     }
138 
139     @Override
140     public VectorMask<E> andNot(VectorMask<E> m) {
141         return and(m.not());
142     }
143 
144     /*package-private*/
145     static boolean anyTrueHelper(boolean[] bits) {
146         // FIXME: Maybe use toLong() != 0 here.
147         for (boolean i : bits) {
148             if (i) return true;
149         }
150         return false;
151     }
152 
153     /*package-private*/
154     static boolean allTrueHelper(boolean[] bits) {
155         // FIXME: Maybe use not().toLong() == 0 here.
156         for (boolean i : bits) {
157             if (!i) return false;
158         }
159         return true;
160     }
161 
162     /*package-private*/
163     static int trueCountHelper(boolean[] bits) {
164         int c = 0;
165         for (boolean i : bits) {
166             if (i) c++;
167         }
168         return c;
169     }
170 
171     /*package-private*/
172     static int firstTrueHelper(boolean[] bits) {
173         for (int i = 0; i < bits.length; i++) {
174             if (bits[i])  return i;
175         }
176         return bits.length;
177     }
178 
179     /*package-private*/
180     static int lastTrueHelper(boolean[] bits) {
181         for (int i = bits.length-1; i >= 0; i--) {
182             if (bits[i])  return i;
183         }
184         return -1;
185     }
186 
187     /*package-private*/
188     static long toLongHelper(boolean[] bits) {
189         long res = 0;
190         long set = 1;
191         for (int i = 0; i < bits.length; i++) {
192             res = bits[i] ? res | set : res;
193             set = set << 1;
194         }
195         return res;
196     }
197 
198     @Override
199     @ForceInline
200     public VectorMask<E> indexInRange(int offset, int limit) {
201         int vlength = length();
202         Vector<E> iota = vectorSpecies().zero().addIndex(1);
203         VectorMask<E> badMask = checkIndex0(offset, limit, iota, vlength);
204         return this.andNot(badMask);
205     }
206 
207     @Override
208     @ForceInline
209     public VectorMask<E> indexInRange(long offset, long limit) {
210         int vlength = length();
211         Vector<E> iota = vectorSpecies().zero().addIndex(1);
212         VectorMask<E> badMask = checkIndex0(offset, limit, iota, vlength);
213         return this.andNot(badMask);
214     }
215 
216     /*package-private*/
217     @ForceInline
218     AbstractVector<E>
219     toVectorTemplate() {
220         AbstractSpecies<E> vsp = vspecies();
221         Vector<E> zero = vsp.broadcast(0);
222         Vector<E> mone = vsp.broadcast(-1);
223         // -1 will result in the most significant bit being set in
224         // addition to some or all other lane bits.
225         // For integral types, *all* lane bits will be set.
226         // The bits for -1.0 are like {0b10111*0000*}.
227         // FIXME: Use a conversion intrinsic for this operation.
228         // https://bugs.openjdk.java.net/browse/JDK-8225740
229         return (AbstractVector<E>) zero.blend(mone, this);
230     }
231 
232     /**
233      * Test if a masked memory access at a given offset into an array
234      * of the given length will stay within the array.
235      * The per-lane offsets are iota*esize.
236      */
237     /*package-private*/
238     @ForceInline
239     void checkIndexByLane(int offset, int length,
240                           Vector<E> iota,
241                           int esize) {
242         if (VectorIntrinsics.VECTOR_ACCESS_OOB_CHECK == 0) {
243             return;
244         }
245         // Although the specification is simple, the implementation is
246         // tricky, because the value iota*esize might possibly
247         // overflow.  So we calculate our test values as scalars,
248         // clipping to the range [-1..VLENGTH], and test them against
249         // the unscaled iota vector, whose values are in [0..VLENGTH-1].
250         int vlength = length();
251         VectorMask<E> badMask;
252         if (esize == 1) {
253             badMask = checkIndex0(offset, length, iota, vlength);
254         } else if (offset >= 0) {
255             // Masked access to multi-byte lanes in byte array.
256             // It could be aligned anywhere.
257             int elemCount = Math.min(vlength, (length - offset) / esize);
258             badMask = checkIndex0(0, elemCount, iota, vlength);
259         } else {
260             int clipOffset = Math.max(offset, -(vlength * esize));
261             badMask = checkIndex0(clipOffset, length,
262                                   iota.lanewise(VectorOperators.MUL, esize),
263                                   vlength * esize);
264         }
265         badMask = badMask.and(this);
266         if (badMask.anyTrue()) {
267             int badLane = badMask.firstTrue();
268             throw ((AbstractMask<E>)badMask)
269                    .checkIndexFailed(offset, badLane, length, esize);
270         }
271     }
272 
273     private
274     @ForceInline
275     VectorMask<E> checkIndex0(int offset, int length,
276                               Vector<E> iota, int vlength) {
277         // An active lane is bad if its number is greater than
278         // length-offset, since when added to offset it will step off
279         // of the end of the array.  To avoid overflow when
280         // converting, clip the comparison value to [0..vlength]
281         // inclusive.
282         int indexLimit = Math.max(0, Math.min(length - offset, vlength));
283         VectorMask<E> badMask =
284             iota.compare(GE, iota.broadcast(indexLimit));
285         if (offset < 0) {
286             // An active lane is bad if its number is less than
287             // -offset, because when added to offset it will then
288             // address an array element at a negative index.  To avoid
289             // overflow when converting, clip the comparison value at
290             // vlength.  This specific expression works correctly even
291             // when offset is Integer.MIN_VALUE.
292             int firstGoodIndex = -Math.max(offset, -vlength);
293             VectorMask<E> badMask2 =
294                 iota.compare(LT, iota.broadcast(firstGoodIndex));
295             if (indexLimit >= vlength) {
296                 badMask = badMask2;  // 1st badMask is all true
297             } else {
298                 badMask = badMask.or(badMask2);
299             }
300         }
301         return badMask;
302     }
303 
304     /**
305      * Test if a masked memory access at a given offset into an array
306      * of the given length will stay within the array.
307      * The per-lane offsets are iota*esize.
308      */
309     /*package-private*/
310     @ForceInline
311     void checkIndexByLane(long offset, long length,
312                           Vector<E> iota,
313                           int esize) {
314         if (VectorIntrinsics.VECTOR_ACCESS_OOB_CHECK == 0) {
315             return;
316         }
317         // Although the specification is simple, the implementation is
318         // tricky, because the value iota*esize might possibly
319         // overflow.  So we calculate our test values as scalars,
320         // clipping to the range [-1..VLENGTH], and test them against
321         // the unscaled iota vector, whose values are in [0..VLENGTH-1].
322         int vlength = length();
323         VectorMask<E> badMask;
324         if (esize == 1) {
325             badMask = checkIndex0(offset, length, iota, vlength);
326         } else if (offset >= 0) {
327             // Masked access to multi-byte lanes in byte array.
328             // It could be aligned anywhere.
329             // 0 <= elemCount <= vlength
330             int elemCount = (int) Math.min(vlength, (length - offset) / esize);
331             badMask = checkIndex0(0, elemCount, iota, vlength);
332         } else {
333             // -vlength * esize <= clipOffset <= 0
334             int clipOffset = (int) Math.max(offset, -(vlength * esize));
335             badMask = checkIndex0(clipOffset, length,
336                     iota.lanewise(VectorOperators.MUL, esize),
337                     vlength * esize);
338         }
339         badMask = badMask.and(this);
340         if (badMask.anyTrue()) {
341             int badLane = badMask.firstTrue();
342             throw ((AbstractMask<E>)badMask)
343                     .checkIndexFailed(offset, badLane, length, esize);
344         }
345     }
346 
347     private
348     @ForceInline
349     VectorMask<E> checkIndex0(long offset, long length,
350                               Vector<E> iota, int vlength) {
351         // An active lane is bad if its number is greater than
352         // length-offset, since when added to offset it will step off
353         // of the end of the array.  To avoid overflow when
354         // converting, clip the comparison value to [0..vlength]
355         // inclusive.
356         // 0 <= indexLimit <= vlength
357         int indexLimit = (int) Math.max(0, Math.min(length - offset, vlength));
358         VectorMask<E> badMask =
359                 iota.compare(GE, iota.broadcast(indexLimit));
360         if (offset < 0) {
361             // An active lane is bad if its number is less than
362             // -offset, because when added to offset it will then
363             // address an array element at a negative index.  To avoid
364             // overflow when converting, clip the comparison value at
365             // vlength.  This specific expression works correctly even
366             // when offset is Integer.MIN_VALUE.
367             // 0 <= firstGoodIndex <= vlength
368             int firstGoodIndex = (int) -Math.max(offset, -vlength);
369             VectorMask<E> badMask2 =
370                     iota.compare(LT, iota.broadcast(firstGoodIndex));
371             if (indexLimit >= vlength) {
372                 badMask = badMask2;  // 1st badMask is all true
373             } else {
374                 badMask = badMask.or(badMask2);
375             }
376         }
377         return badMask;
378     }
379 
380     private IndexOutOfBoundsException checkIndexFailed(long offset, int lane,
381                                                        long length, int esize) {
382         String msg = String.format("Masked range check failed: "+
383                                    "vector mask %s out of bounds at "+
384                                    "index %d+%d for length %d",
385                                    this, offset, lane * esize, length);
386         if (esize != 1) {
387             msg += String.format(" (each lane spans %d elements)", esize);
388         }
389         throw new IndexOutOfBoundsException(msg);
390     }
391 
392 }