1 /*
2 * Copyright (c) 2017, 2019, 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
23 * questions.
24 */
25 package jdk.incubator.vector;
26
27 import jdk.internal.misc.Unsafe;
28 import jdk.internal.vm.annotation.ForceInline;
29
30 import java.util.Arrays;
31 import java.util.Objects;
32
33 /**
34 * A {@code VectorMask} represents an ordered immutable sequence of {@code boolean}
35 * values. Some vector operations accept masks to
36 * control the selection and operation of lane elements of input vectors.
37 * <p>
38 * The number of values in the sequence is referred to as the VectorMask
39 * {@link #length() length}. The length also corresponds to the number of
40 * VectorMask lanes. The lane element at lane index {@code N} (from {@code 0},
41 * inclusive, to length, exclusive) corresponds to the {@code N + 1}'th
42 * value in the sequence.
43 * A VectorMask and Vector of the same element type and shape have the same number
44 * of lanes.
45 * <p>
46 * A lane is said to be <em>set</em> if the lane element is {@code true},
47 * otherwise a lane is said to be <em>unset</em> if the lane element is
48 * {@code false}.
49 * <p>
50 * VectorMask declares a limited set of unary, binary and reduction operations.
51 * <ul>
52 * <li>
53 * A lane-wise unary operation operates on one input mask and produces a
54 * result mask.
55 * For each lane of the input mask the
56 * lane element is operated on using the specified scalar unary operation and
57 * the boolean result is placed into the mask result at the same lane.
58 * The following pseudocode illustrates the behavior of this operation category:
59 *
60 * <pre>{@code
61 * VectorMask<E> a = ...;
62 * boolean[] ar = new boolean[a.length()];
63 * for (int i = 0; i < a.length(); i++) {
64 * ar[i] = scalar_unary_op(a.laneIsSet(i));
65 * }
66 * VectorMask<E> r = VectorMask.fromArray(a.vectorSpecies(), ar, 0);
67 * }</pre>
68 *
69 * <li>
70 * A lane-wise binary operation operates on two input
71 * masks to produce a result mask.
72 * For each lane of the two input masks a and b,
73 * the corresponding lane elements from a and b are operated on
74 * using the specified scalar binary operation and the boolean result is placed
75 * into the mask result at the same lane.
76 * The following pseudocode illustrates the behavior of this operation category:
77 *
78 * <pre>{@code
79 * VectorMask<E> a = ...;
80 * VectorMask<E> b = ...;
81 * boolean[] ar = new boolean[a.length()];
82 * for (int i = 0; i < a.length(); i++) {
83 * ar[i] = scalar_binary_op(a.laneIsSet(i), b.laneIsSet(i));
84 * }
85 * VectorMask<E> r = VectorMask.fromArray(a.vectorSpecies(), ar, 0);
86 * }</pre>
87 *
88 * <li>
89 * A cross-lane reduction operation accepts an input mask and produces a scalar result.
90 * For each lane of the input mask the lane element is operated on, together with a scalar accumulation value,
91 * using the specified scalar binary operation. The scalar result is the final value of the accumulator. The
92 * following pseudocode illustrates the behaviour of this operation category:
93 *
94 * <pre>{@code
95 * Mask<E> a = ...;
96 * int acc = zero_for_scalar_binary_op; // 0, or 1 for &
97 * for (int i = 0; i < a.length(); i++) {
98 * acc = scalar_binary_op(acc, a.laneIsSet(i) ? 1 : 0); // & | +
99 * }
100 * return acc; // maybe boolean (acc != 0)
101 * }</pre>
102 *
103 * </ul>
104 * @param <E> the boxed element type of this mask
105 *
106 * <h1>Value-based classes and identity operations</h1>
107 *
108 * {@code VectorMask}, along with {@link Vector}, is a
109 * <a href="{@docRoot}/java.base/java/lang/doc-files/ValueBased.html">value-based</a>
110 * class.
111 *
112 * With {@code VectorMask}, identity-sensitive operations such as {@code ==}
113 * may yield unpredictable results, or reduced performance. Oddly
114 * enough, {@link VectorMask#equals(Object) v.equals(w)} is likely to be
115 * faster than {@code v==w}, since {@code equals} is <em>not</em>
116 * an identity sensitive method. (Neither is {@code toString} nor
117 * {@code hashCode}.)
118
119 * Also, vector mask objects can be stored in locals and parameters and as
120 * {@code static final} constants, but storing them in other Java
121 * fields or in array elements, while semantically valid, may incur
122 * performance penalties.
123 */
124 public abstract class VectorMask<E> {
125 VectorMask() {}
126
127 /**
128 * Returns the vector species to which this mask applies.
129 * This mask applies to vectors of the same species,
130 * and the same number of lanes.
131 *
132 * @return the vector species of this mask
133 */
134 public abstract VectorSpecies<E> vectorSpecies();
135
136 /**
137 * Returns the number of mask lanes.
138 * This mask applies to vectors of the same number of lanes,
139 * and the same species.
140 *
141 * @return the number of mask lanes
142 */
143 @ForceInline
144 public final int length() {
145 AbstractSpecies<E> vspecies = (AbstractSpecies<E>) vectorSpecies();
146 return vspecies.laneCount();
147 }
148
149 /**
150 * Returns a mask where each lane is set or unset according to given
151 * {@code boolean} values.
152 * <p>
153 * For each mask lane, where {@code N} is the mask lane index,
154 * if the given {@code boolean} value at index {@code N} is {@code true}
155 * then the mask lane at index {@code N} is set, otherwise it is unset.
156 * <p>
157 * The given species must have a number of lanes that is compatible
158 * with the given array.
159 *
160 * @param species vector species for the desired mask
161 * @param bits the given {@code boolean} values
162 * @return a mask where each lane is set or unset according to the given
163 * {@code boolean} value
164 * @throws IllegalArgumentException
165 * if {@code bits.length != species.length()}
166 * @see #fromLong(VectorSpecies, boolean...)
167 * @see #fromArray(VectorSpecies, boolean[], int)
168 * @see Vector#maskFromValues(boolean...)
169 */
170 @ForceInline
171 public static <E> VectorMask<E> fromValues(VectorSpecies<E> species, boolean... bits) {
172 AbstractSpecies<E> vspecies = (AbstractSpecies<E>) species;
173 VectorIntrinsics.requireLength(bits.length, vspecies.laneCount());
174 return fromArray(vspecies, bits, 0);
175 }
176
177 /**
178 * Loads a mask from a {@code boolean} array starting at an offset.
179 * <p>
180 * For each mask lane, where {@code N} is the mask lane index,
181 * if the array element at index {@code ix + N} is {@code true} then the
182 * mask lane at index {@code N} is set, otherwise it is unset.
183 *
184 * @param species vector species for the desired mask
185 * @param bits the {@code boolean} array
186 * @param offset the offset into the array
187 * @return the mask loaded from the {@code boolean} array
188 * @throws IndexOutOfBoundsException if {@code offset < 0}, or
189 * {@code offset > bits.length - species.length()}
190 * @see #fromLong(VectorSpecies, boolean...)
191 * @see #fromValues(VectorSpecies, boolean...)
192 */
193 @ForceInline
194 @SuppressWarnings("unchecked")
195 public static <E> VectorMask<E> fromArray(VectorSpecies<E> species, boolean[] bits, int offset) {
196 AbstractSpecies<E> vsp = (AbstractSpecies<E>) species;
197 int laneCount = vsp.laneCount();
198 offset = VectorIntrinsics.checkFromIndexSize(offset, laneCount, bits.length);
199 return VectorIntrinsics.load(
200 vsp.maskType(), vsp.elementType(), laneCount,
201 bits, (long) offset + Unsafe.ARRAY_BOOLEAN_BASE_OFFSET,
202 bits, offset, vsp,
203 (c, idx, s)
204 -> s.opm(n -> c[idx + n]));
205 }
206
207 /**
208 * Returns a mask where each lane is set or unset according to
209 * the bits in the given bitmask, starting with the least
210 * significant bit, and continuing up through the sign bit.
211 * <p>
212 * For each mask lane, where {@code N} is the mask lane index,
213 * if the expression {@code (bits>>min(63,N))&1} is non-zero,
214 * then the mask lane at index {@code N} is set, otherwise it is unset.
215 * <p>
216 * If the given species has fewer than 64 lanes, the high
217 * {@code 64-VLENGTH} bits of the bit-mask are ignored.
218 * If the given species has more than 64 lanes, the sign
219 * bit is replicated into lane 64 and beyond.
220 *
221 * @param species vector species for the desired mask
222 * @param bits the given mask bits, as a 64-bit signed integer
223 * @return a mask where each lane is set or unset according to
224 * the bits in the given integer value
225 * @see #fromValues(VectorSpecies, boolean...)
226 * @see #fromArray(VectorSpecies, boolean[], int)
227 * @see Vector#maskFromBits(long)
228 */
229 @ForceInline
230 public static <E> VectorMask<E> fromLong(VectorSpecies<E> species, long bits) {
231 AbstractSpecies<E> vspecies = (AbstractSpecies<E>) species;
232 int laneCount = vspecies.laneCount();
233 if (laneCount < Long.SIZE) {
234 int extraSignBits = Long.SIZE - laneCount;
235 bits <<= extraSignBits;
236 bits >>= extraSignBits;
237 }
238 if (bits == (bits >> 1)) {
239 // Special case.
240 assert(bits == 0 || bits == -1);
241 return vspecies.maskAll(bits != 0);
242 }
243 // FIXME: Intrinsify this.
244 long shifted = bits;
245 boolean[] a = new boolean[laneCount];
246 for (int i = 0; i < a.length; i++) {
247 a[i] = ((shifted & 1) != 0);
248 shifted >>= 1; // replicate sign bit
249 }
250 return fromValues(vspecies, a);
251 }
252
253 /**
254 * Converts this mask to a mask of the given species of
255 * element type {@code F}.
256 * The {@code species.length()} must be equal to the
257 * mask length.
258 * The various mask lane bits are unmodified.
259 * <p>
260 * For each mask lane, where {@code N} is the lane index, if the
261 * mask lane at index {@code N} is set, then the mask lane at index
262 * {@code N} of the resulting mask is set, otherwise that mask lane is
263 * not set.
264 *
265 * @param species vector species for the desired mask
266 * @param <F> the boxed element type of the species
267 * @return a mask converted by shape and element type
268 * @throws IllegalArgumentException if this mask length and the species
269 * length differ
270 */
271 public abstract <F> VectorMask<F> cast(VectorSpecies<F> species);
272
273 /**
274 * Returns the lane elements of this mask packed into a {@code long}
275 * value for at most the first 64 lane elements.
276 * <p>
277 * The lane elements are packed in the order of least significant bit
278 * to most significant bit.
279 * For each mask lane where {@code N} is the mask lane index, if the
280 * mask lane is set then the {@code N}th bit is set to one in the
281 * resulting {@code long} value, otherwise the {@code N}th bit is set
282 * to zero.
283 * The mask must no more than 64 lanes.
284 *
285 * @return the lane elements of this mask packed into a {@code long}
286 * value.
287 * @throws IllegalArgumentException if there are more than 64 lanes
288 * in this mask
289 */
290 public abstract long toLong();
291
292 /**
293 * Returns an {@code boolean} array containing the lane elements of this
294 * mask.
295 * <p>
296 * This method behaves as if it stores
297 * this mask into an allocated array
298 * (using {@link #intoArray(boolean[], int)})
299 * and returns that array as
300 * follows:
301 * <pre>{@code
302 * boolean[] a = new boolean[this.length()];
303 * this.intoArray(a, 0);
304 * return a;
305 * }</pre>
306 *
307 * @return an array containing the the lane elements of this vector
308 */
309 public abstract boolean[] toArray();
310
311 /**
312 * Stores this mask into a {@code boolean} array starting at offset.
313 * <p>
314 * For each mask lane, where {@code N} is the mask lane index,
315 * the lane element at index {@code N} is stored into the array
316 * element {@code a[offset+N]}.
317 *
318 * @param a the array, of type boolean[]
319 * @param offset the offset into the array
320 * @throws IndexOutOfBoundsException if {@code offset < 0} or
321 * {@code offset > a.length - this.length()}
322 */
323 public abstract void intoArray(boolean[] a, int offset);
324
325 /**
326 * Returns {@code true} if any of the mask lanes are set.
327 *
328 * @return {@code true} if any of the mask lanes are set, otherwise
329 * {@code false}.
330 */
331 public abstract boolean anyTrue();
332
333 /**
334 * Returns {@code true} if all of the mask lanes are set.
335 *
336 * @return {@code true} if all of the mask lanes are set, otherwise
337 * {@code false}.
338 */
339 public abstract boolean allTrue();
340
341 /**
342 * Returns the number of mask lanes that are set.
343 *
344 * @return the number of mask lanes that are set.
345 */
346 public abstract int trueCount();
347
348 /**
349 * Returns the index of the first mask lane that is set.
350 * Returns {@code VLENGTH} if none of them are set.
351 *
352 * @return the index of the first mask lane that is set, or {@code VLENGTH}
353 */
354 public abstract int firstTrue();
355
356 /**
357 * Returns the index of the last mask lane that is set.
358 * Returns {@code -1} if none of them are set.
359 *
360 * @return the index of the last mask lane that is set, or {@code -1}
361 */
362 public abstract int lastTrue();
363
364 /**
365 * Computes the logical intersection (as {@code a&b})
366 * between this mask and a second input mask.
367 * <p>
368 * This is a lane-wise binary operation which applies
369 * the logical {@code AND} operation
370 * ({@code &}) to each corresponding pair of mask bits.
371 *
372 * @param m the second input mask
373 * @return the result of logically conjoining the two input masks
374 */
375 public abstract VectorMask<E> and(VectorMask<E> m);
376
377 /**
378 * Computes the logical union (as {@code a|b}) of this mask
379 * and a second input mask.
380 * <p>
381 * This is a lane-wise binary operation which applies
382 * the logical {@code OR} operation
383 * ({@code |}) to each corresponding pair of mask bits.
384 *
385 * @param m the input mask
386 * @return the result of logically disjoining the two input masks
387 */
388 public abstract VectorMask<E> or(VectorMask<E> m);
389
390 /**
391 * Determines logical equivalence of this mask
392 * to a second input mask (as boolean {@code a==b}
393 * or {@code a^~b}).
394 * <p>
395 * This is a lane-wise binary operation tests each
396 * corresponding pair of mask bits for equality.
397 * It is also equivalent to a inverse {@code XOR}
398 * operation ({@code ^~}) on the mask bits.
399 *
400 * @param m the input mask
401 * @return a mask showing where the two input masks were equal
402 */
403 public abstract VectorMask<E> equal(VectorMask<E> m);
404
405 /**
406 * Logically subtracts a second input mask
407 * from this mask (as {@code a&~b}).
408 * <p>
409 * This is a lane-wise binary operation which applies
410 * the logical {@code ANDC} operation
411 * ({@code &~}) to each corresponding pair of mask bits.
412 *
413 * @param m the second input mask
414 * @return the result of logically subtracting the second mask from this mask
415 */
416 public abstract VectorMask<E> andNot(VectorMask<E> m);
417
418 /**
419 * Logically negates this mask.
420 * <p>
421 * This is a lane-wise binary operation which applies
422 * the logical {@code NOT} operation
423 * ({@code ~}) to each mask bit.
424 *
425 * @return the result of logically negating this mask
426 */
427 public abstract VectorMask<E> not();
428
429 // FIXME: Consider blend, slice, rearrange operations.
430
431 /**
432 * Removes lanes numbered {@code N} from this mask where the
433 * adjusted index {@code N+offset}, is not in the range
434 * {@code [0..limit-1]}.
435 *
436 * <p> In all cases the series of set and unset lanes is assigned
437 * as if by using infinite precision or {@code VLENGTH-}saturating
438 * additions or subtractions, without overflow or wrap-around.
439 *
440 * @apiNote
441 *
442 * This method performs a SIMD emulation of the check performed by
443 * {@link Objects#checkIndex(int,int)}, on the index numbers in
444 * the range {@code [offset..offset+VLENGTH-1]}. If an exception
445 * is desired, the resulting mask can be compared with the
446 * original mask; if they are not equal, then at least one lane
447 * was out of range, and exception processing can be performed.
448 *
449 * <p> A mask which is a series of {@code N} set lanes followed by
450 * a series of series of unset lanes can be obtained by calling
451 * {@code allTrue.indexInRange(0, N)}, where {@code allTrue} is a
452 * mask of all true bits. A mask of {@code N1} unset lanes
453 * followed by {@code N2} set lanes can be obtained by calling
454 * {@code allTrue.indexInRange(-N1, N2)}.
455 *
456 * @return the original mask, with out-of-range lanes unset
457 */
458 public abstract VectorMask<E> indexInRange(int offset, int limit);
459
460 /**
461 * Returns a vector representation of this mask, the
462 * lane bits of which are set or unset in correspondence
463 * to the mask bits.
464 *
465 * For each mask lane, where {@code N} is the mask lane index, if
466 * the mask lane is set at {@code N} then the specific non-default
467 * value {@code -1} is placed into the resulting vector at lane
468 * index {@code N}. Otherwise the default element value {@code 0}
469 * is placed into the resulting vector at lane index {@code N}.
470 *
471 * Whether the element type ({@code ETYPE}) of this mask is
472 * floating point or integral, the lane value, as selected by the
473 * mask, will be one of the two arithmetic values {@code 0} or
474 * {@code -1}. For every {@code ETYPE} the most significant bit
475 * of the vector lane is set if and only if the mask lane is set.
476 * In addition, for integral types, <em>all</em> lane bits are set
477 * in lanes where the mask is set.
478 *
479 * <p> The vector returned is the same as would be computed by
480 * {@code ZERO.blend(MINUS_ONE, this)}, where {@code ZERO} and
481 * {@code MINUS_ONE} are vectors which replicate the default
482 * {@code ETYPE} value and the {@code ETYPE} value representing
483 * {@code -1}, respectively.
484 *
485 * @apiNote For the sake of static type checking, users may wish
486 * to check the resulting vector against the expected integral
487 * lane type or species. If the mask is for a float-point
488 * species, then the resulting vector will have the same shape and
489 * lane size, but an integral type. If the mask is for an
490 * integral species, the resulting vector will be of exactly that
491 * species.
492 *
493 * @return a vector representation of this mask
494 * @see Vector#check(Class)
495 * @see Vector#check(VectorSpecies)
496 */
497 public abstract Vector<E> toVector();
498
499 /**
500 * Tests if the lane at index {@code i} is set
501 * @param i the lane index
502 *
503 * @return true if the lane at index {@code i} is set, otherwise false
504 */
505 public abstract boolean laneIsSet(int i);
506
507 /**
508 * Checks that this mask applies to vectors with the given element type,
509 * and returns this mask unchanged.
510 * The effect is similar to this pseudocode:
511 * {@code elementType == vectorSpecies().elementType()
512 * ? this
513 * : throw new ClassCastException()}.
514 *
515 * @param elementType the required lane type
516 * @param <F> the boxed element type of the required lane type
517 * @return the same mask
518 * @throws ClassCastException if the element type is wrong
519 * @see Vector#check(Class)
520 * @see VectorMask#check(VectorSpecies)
521 */
522 public abstract <F> VectorMask<F> check(Class<F> elementType);
523
524 /**
525 * Checks that this mask has the given species,
526 * and returns this mask unchanged.
527 * The effect is similar to this pseudocode:
528 * {@code species == vectorSpecies()
529 * ? this
530 * : throw new ClassCastException()}.
531 *
532 * @param species vector species required for this mask
533 * @param <F> the boxed element type of the required species
534 * @return the same mask
535 * @throws ClassCastException if the species is wrong
536 * @see Vector#check(Class)
537 * @see Vector#check(VectorSpecies)
538 */
539 public abstract <F> VectorMask<F> check(VectorSpecies<F> species);
540
541 /**
542 * Returns a string representation of this mask, of the form
543 * {@code "Mask[T.TT...]"}, reporting the mask bit
544 * settings (as 'T' or '.' characters) in lane order.
545 *
546 * @return a string of the form {@code "Mask[T.TT...]"}
547 */
548 @Override
549 public final String toString() {
550 StringBuilder buf = new StringBuilder(length());
551 buf.append("Mask[");
552 for (boolean isSet : toArray()) {
553 buf.append(isSet ? 'T' : '.');
554 }
555 return buf.append(']').toString();
556 }
557
558 /**
559 * Indicates whether this mask is identical to some other object.
560 * Two masks are identical only if they have the same species
561 * and same source indexes, in the same order.
562
563 * @return whether this vector is identical to some other object
564 */
565 @Override
566 public final boolean equals(Object obj) {
567 if (obj instanceof VectorMask) {
568 VectorMask<?> that = (VectorMask<?>) obj;
569 if (this.vectorSpecies().equals(that.vectorSpecies())) {
570 @SuppressWarnings("unchecked")
571 VectorMask<E> that2 = (VectorMask<E>) that;
572 return this.equal(that2).allTrue();
573 }
574 }
575 return false;
576 }
577
578 /**
579 * Returns a hash code value for the mask,
580 * based on the mask bit settings and the vector species.
581 *
582 * @return a hash code value for this mask
583 */
584 @Override
585 public final int hashCode() {
586 return Objects.hash(vectorSpecies(), Arrays.hashCode(toArray()));
587 }
588
589 // ==== JROSE NAME CHANGES ====
590
591 // TYPE CHANGED
592 // * toVector() return type is Vector<?> not Vector<E>
593 // ADDED
594 // * indexInRange(int,int,int) (SIMD range check, no overflow)
595 // * fromLong(VectorSpecies, long) (inverse of toLong)
596 // * check(VectorSpecies) (static type-safety check)
597 // * toString(), equals(Object), hashCode() (documented)
598 // * added <E> (not <?>) to toVector
599
600 /** Renamed to {@link #vectorSpecies()}. */
601 @Deprecated
602 public final VectorSpecies<E> species() { return vectorSpecies(); }
603
604 /** Renamed to {@link #laneIsSet(int)}. */
605 @Deprecated
606 public final boolean lane(int i) { return laneIsSet(i); }
607
608 /** Renamed to {@link #laneIsSet(int)}. */
609 @Deprecated
610 public final boolean isSet(int i) { return laneIsSet(i); }
611
612 /** Use {@link VectorSpecies#maskAll(boolean)}. */
613 @Deprecated
614 public static <E> VectorMask<E> maskAllTrue(VectorSpecies<E> species) { return fromBoolean(species, true); }
615
616 /** Use {@link VectorSpecies#maskAll(boolean)}. */
617 @Deprecated
618 public static <E> VectorMask<E> maskAllFalse(VectorSpecies<E> species) { return fromBoolean(species, false); }
619
620 /** Use {@link VectorSpecies#maskAll} */
621 public static <E> VectorMask<E> fromBoolean(VectorSpecies<E> species, boolean bit) {
622 return species.maskAll(bit);
623 }
624 }