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