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> vsp = (AbstractSpecies<E>) species;
241 bits = bits & (0xFFFFFFFFFFFFFFFFL >>> (64 - vsp.laneCount()));
242 return VectorSupport.fromBitsCoerced(vsp.maskType(), vsp.elementType(), vsp.laneCount(), bits,
243 VectorSupport.MODE_BITS_COERCED_LONG_TO_MASK, vsp,
244 (m, s) -> {
245 if (m == (m >> 1)) {
246 // Special case.
247 assert(m == 0 || m == -1);
248 return s.maskAll(m != 0);
249 }
250
251 long shifted = m;
252 boolean[] a = new boolean[s.laneCount()];
253 for (int i = 0; i < a.length; i++) {
254 a[i] = ((shifted & 1) != 0);
255 shifted >>= 1; // replicate sign bit
256 }
257 return fromValues(s, a);
258 });
259 }
260
261 /**
262 * Converts this mask to a mask of the given species of
263 * element type {@code F}.
264 * The {@code species.length()} must be equal to the
265 * mask length.
266 * The various mask lane bits are unmodified.
267 * <p>
268 * For each mask lane, where {@code N} is the lane index, if the
269 * mask lane at index {@code N} is set, then the mask lane at index
270 * {@code N} of the resulting mask is set, otherwise that mask lane is
271 * not set.
272 *
273 * @param species vector species for the desired mask
274 * @param <F> the boxed element type of the species
275 * @return a mask converted by shape and element type
276 * @throws IllegalArgumentException if this mask length and the species
277 * length differ
278 */
279 public abstract <F> VectorMask<F> cast(VectorSpecies<F> species);
280
281 /**
282 * Returns the lane elements of this mask packed into a {@code long}
283 * value for at most the first 64 lane elements.
284 * <p>
285 * The lane elements are packed in the order of least significant bit
286 * to most significant bit.
287 * For each mask lane where {@code N} is the mask lane index, if the
288 * mask lane is set then the {@code N}th bit is set to one in the
289 * resulting {@code long} value, otherwise the {@code N}th bit is set
290 * to zero.
291 * The mask must have no more than 64 lanes.
292 *
293 * @return the lane elements of this mask packed into a {@code long}
294 * value.
295 * @throws UnsupportedOperationException if there are more than 64 lanes
296 * in this mask
297 */
298 // FIXME: Consider changing method to accept part locating where to extract
299 // out a 64bit value (in effect a contracting operation)
300 public abstract long toLong();
301
302 /**
303 * Returns an {@code boolean} array containing the lane elements of this
304 * mask.
305 * <p>
306 * This method behaves as if it stores
307 * this mask into an allocated array
308 * (using {@link #intoArray(boolean[], int)})
309 * and returns that array as
310 * follows:
311 * <pre>{@code
312 * boolean[] a = new boolean[this.length()];
313 * this.intoArray(a, 0);
314 * return a;
315 * }</pre>
316 *
317 * @return an array containing the the lane elements of this vector
318 */
319 public abstract boolean[] toArray();
320
321 /**
322 * Stores this mask into a {@code boolean} array starting at offset.
323 * <p>
324 * For each mask lane, where {@code N} is the mask lane index,
325 * the lane element at index {@code N} is stored into the array
326 * element {@code a[offset+N]}.
327 *
328 * @param a the array, of type boolean[]
329 * @param offset the offset into the array
330 * @throws IndexOutOfBoundsException if {@code offset < 0} or
331 * {@code offset > a.length - this.length()}
332 */
333 public abstract void intoArray(boolean[] a, int offset);
334
335 /**
336 * Returns {@code true} if any of the mask lanes are set.
337 *
338 * @return {@code true} if any of the mask lanes are set, otherwise
339 * {@code false}.
340 */
341 public abstract boolean anyTrue();
342
343 /**
344 * Returns {@code true} if all of the mask lanes are set.
345 *
346 * @return {@code true} if all of the mask lanes are set, otherwise
347 * {@code false}.
348 */
349 public abstract boolean allTrue();
350
351 /**
352 * Returns the number of mask lanes that are set.
353 *
354 * @return the number of mask lanes that are set.
355 */
356 public abstract int trueCount();
357
358 /**
359 * Returns the index of the first mask lane that is set.
360 * Returns {@code VLENGTH} if none of them are set.
361 *
362 * @return the index of the first mask lane that is set, or {@code VLENGTH}
363 */
364 public abstract int firstTrue();
365
366 /**
367 * Returns the index of the last mask lane that is set.
368 * Returns {@code -1} if none of them are set.
369 *
370 * @return the index of the last mask lane that is set, or {@code -1}
371 */
372 public abstract int lastTrue();
373
374 /**
375 * Computes the logical intersection (as {@code a&b})
376 * between this mask and a second input mask.
377 * <p>
378 * This is a lane-wise binary operation which applies
379 * the logical {@code AND} operation
380 * ({@code &}) to each corresponding pair of mask bits.
381 *
382 * @param m the second input mask
383 * @return the result of logically conjoining the two input masks
384 */
385 public abstract VectorMask<E> and(VectorMask<E> m);
386
387 /**
388 * Computes the logical union (as {@code a|b}) of this mask
389 * and a second input mask.
390 * <p>
391 * This is a lane-wise binary operation which applies
392 * the logical {@code OR} operation
393 * ({@code |}) to each corresponding pair of mask bits.
394 *
395 * @param m the input mask
396 * @return the result of logically disjoining the two input masks
397 */
398 public abstract VectorMask<E> or(VectorMask<E> m);
399
400 /**
401 * Determines logical equivalence of this mask
402 * to a second input mask (as boolean {@code a==b}
403 * or {@code a^~b}).
404 * <p>
405 * This is a lane-wise binary operation tests each
406 * corresponding pair of mask bits for equality.
407 * It is also equivalent to a inverse {@code XOR}
408 * operation ({@code ^~}) on the mask bits.
409 *
410 * @param m the input mask
411 * @return a mask showing where the two input masks were equal
412 * @see #equals
413 */
414 public abstract VectorMask<E> eq(VectorMask<E> m);
415
416 /**
417 * Logically subtracts a second input mask
418 * from this mask (as {@code a&~b}).
419 * <p>
420 * This is a lane-wise binary operation which applies
421 * the logical {@code ANDC} operation
422 * ({@code &~}) to each corresponding pair of mask bits.
423 *
424 * @param m the second input mask
425 * @return the result of logically subtracting the second mask from this mask
426 */
427 public abstract VectorMask<E> andNot(VectorMask<E> m);
428
429 /**
430 * Logically negates this mask.
431 * <p>
432 * This is a lane-wise binary operation which applies
433 * the logical {@code NOT} operation
434 * ({@code ~}) to each mask bit.
435 *
436 * @return the result of logically negating this mask
437 */
438 public abstract VectorMask<E> not();
439
440 // FIXME: Consider blend, slice, rearrange operations.
441
442 /**
443 * Removes lanes numbered {@code N} from this mask where the
444 * adjusted index {@code N+offset}, is not in the range
445 * {@code [0..limit-1]}.
446 *
447 * <p> In all cases the series of set and unset lanes is assigned
448 * as if by using infinite precision or {@code VLENGTH-}saturating
449 * additions or subtractions, without overflow or wrap-around.
450 *
451 * @apiNote
452 *
453 * This method performs a SIMD emulation of the check performed by
454 * {@link Objects#checkIndex(int,int)}, on the index numbers in
455 * the range {@code [offset..offset+VLENGTH-1]}. If an exception
456 * is desired, the resulting mask can be compared with the
457 * original mask; if they are not equal, then at least one lane
458 * was out of range, and exception processing can be performed.
459 *
460 * <p> A mask which is a series of {@code N} set lanes followed by
461 * a series of unset lanes can be obtained by calling
462 * {@code allTrue.indexInRange(0, N)}, where {@code allTrue} is a
463 * mask of all true bits. A mask of {@code N1} unset lanes
464 * followed by {@code N2} set lanes can be obtained by calling
465 * {@code allTrue.indexInRange(-N1, N2)}.
466 *
467 * @param offset the starting index
468 * @param limit the upper-bound (exclusive) of index range
469 * @return the original mask, with out-of-range lanes unset
470 * @see VectorSpecies#indexInRange(int, int)
471 */
472 public abstract VectorMask<E> indexInRange(int offset, int limit);
473
474 /**
475 * Returns a vector representation of this mask, the
476 * lane bits of which are set or unset in correspondence
477 * to the mask bits.
478 *
479 * For each mask lane, where {@code N} is the mask lane index, if
480 * the mask lane is set at {@code N} then the specific non-default
481 * value {@code -1} is placed into the resulting vector at lane
482 * index {@code N}. Otherwise the default element value {@code 0}
483 * is placed into the resulting vector at lane index {@code N}.
484 *
485 * Whether the element type ({@code ETYPE}) of this mask is
486 * floating point or integral, the lane value, as selected by the
487 * mask, will be one of the two arithmetic values {@code 0} or
488 * {@code -1}. For every {@code ETYPE} the most significant bit
489 * of the vector lane is set if and only if the mask lane is set.
490 * In addition, for integral types, <em>all</em> lane bits are set
491 * in lanes where the mask is set.
492 *
493 * <p> The vector returned is the same as would be computed by
494 * {@code ZERO.blend(MINUS_ONE, this)}, where {@code ZERO} and
495 * {@code MINUS_ONE} are vectors which replicate the default
496 * {@code ETYPE} value and the {@code ETYPE} value representing
497 * {@code -1}, respectively.
498 *
499 * @apiNote For the sake of static type checking, users may wish
500 * to check the resulting vector against the expected integral
501 * lane type or species. If the mask is for a float-point
502 * species, then the resulting vector will have the same shape and
503 * lane size, but an integral type. If the mask is for an
504 * integral species, the resulting vector will be of exactly that
505 * species.
506 *
507 * @return a vector representation of this mask
508 * @see Vector#check(Class)
509 * @see Vector#check(VectorSpecies)
510 */
511 public abstract Vector<E> toVector();
512
513 /**
514 * Tests if the lane at index {@code i} is set
515 * @param i the lane index
516 *
517 * @return true if the lane at index {@code i} is set, otherwise false
518 * @throws IndexOutOfBoundsException if the index is out of range
519 * ({@code < 0 || >= length()})
520 */
521 public abstract boolean laneIsSet(int i);
522
523 /**
524 * Checks that this mask applies to vectors with the given element type,
525 * and returns this mask unchanged.
526 * The effect is similar to this pseudocode:
527 * {@code elementType == vectorSpecies().elementType()
528 * ? this
529 * : throw new ClassCastException()}.
530 *
531 * @param elementType the required lane type
532 * @param <F> the boxed element type of the required lane type
533 * @return the same mask
534 * @throws ClassCastException if the element type is wrong
535 * @see Vector#check(Class)
536 * @see VectorMask#check(VectorSpecies)
537 */
538 public abstract <F> VectorMask<F> check(Class<F> elementType);
539
540 /**
541 * Checks that this mask has the given species,
542 * and returns this mask unchanged.
543 * The effect is similar to this pseudocode:
544 * {@code species == vectorSpecies()
545 * ? this
546 * : throw new ClassCastException()}.
547 *
548 * @param species vector species required for this mask
549 * @param <F> the boxed element type of the required species
550 * @return the same mask
551 * @throws ClassCastException if the species is wrong
552 * @see Vector#check(Class)
553 * @see Vector#check(VectorSpecies)
554 */
555 public abstract <F> VectorMask<F> check(VectorSpecies<F> species);
556
557 /**
558 * Checks that this mask has the same class with the given mask class,
559 * and it has the same species with given vector's species,
560 * and returns this mask unchanged.
561 * The effect is similar to this pseudocode:
562 * {@code getClass() == maskClass &&
563 * vectorSpecies() == vector.species()
564 * ? this
565 * : throw new ClassCastException()}.
566 *
567 * @param maskClass the class required for this mask
568 * @param vector its species required for this mask
569 * @param <F> the boxed element type of the required species
570 * @return the same mask
571 * @throws ClassCastException if the species is wrong
572 */
573 abstract <F> VectorMask<F> check(Class<? extends VectorMask<F>> maskClass, Vector<F> vector);
574
575 /**
576 * Returns a string representation of this mask, of the form
577 * {@code "Mask[T.TT...]"}, reporting the mask bit
578 * settings (as 'T' or '.' characters) in lane order.
579 *
580 * @return a string of the form {@code "Mask[T.TT...]"}
581 */
582 @Override
583 public final String toString() {
584 StringBuilder buf = new StringBuilder(length());
585 buf.append("Mask[");
586 for (boolean isSet : toArray()) {
587 buf.append(isSet ? 'T' : '.');
588 }
589 return buf.append(']').toString();
590 }
591
592 /**
593 * Indicates whether this mask is identical to some other object.
594 * Two masks are identical only if they have the same species
595 * and same source indexes, in the same order.
596 *
597 * @return whether this vector is identical to some other object
598 * @see #eq
599 */
600 @Override
601 public final boolean equals(Object obj) {
602 if (obj instanceof VectorMask) {
603 VectorMask<?> that = (VectorMask<?>) obj;
604 if (this.vectorSpecies().equals(that.vectorSpecies())) {
605 @SuppressWarnings("unchecked")
606 VectorMask<E> that2 = (VectorMask<E>) that;
607 return this.eq(that2).allTrue();
608 }
609 }
610 return false;
611 }
612
613 /**
614 * Returns a hash code value for the mask,
615 * based on the mask bit settings and the vector species.
616 *
617 * @return a hash code value for this mask
618 */
619 @Override
620 public final int hashCode() {
621 return Objects.hash(vectorSpecies(), Arrays.hashCode(toArray()));
622 }
623
624 // ==== JROSE NAME CHANGES ====
625
626 // TYPE CHANGED
627 // * toVector() return type is Vector<?> not Vector<E>
628 // ADDED
629 // * indexInRange(int,int,int) (SIMD range check, no overflow)
630 // * fromLong(VectorSpecies, long) (inverse of toLong)
631 // * check(VectorSpecies) (static type-safety check)
632 // * toString(), equals(Object), hashCode() (documented)
633 // * added <E> (not <?>) to toVector
634
635 }