1 /*
2 * Copyright (c) 2017, 2020, 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 */
520 public abstract boolean laneIsSet(int i);
521
522 /**
523 * Checks that this mask applies to vectors with the given element type,
524 * and returns this mask unchanged.
525 * The effect is similar to this pseudocode:
526 * {@code elementType == vectorSpecies().elementType()
527 * ? this
528 * : throw new ClassCastException()}.
529 *
530 * @param elementType the required lane type
531 * @param <F> the boxed element type of the required lane type
532 * @return the same mask
533 * @throws ClassCastException if the element type is wrong
534 * @see Vector#check(Class)
535 * @see VectorMask#check(VectorSpecies)
536 */
537 public abstract <F> VectorMask<F> check(Class<F> elementType);
538
539 /**
540 * Checks that this mask has the given species,
541 * and returns this mask unchanged.
542 * The effect is similar to this pseudocode:
543 * {@code species == vectorSpecies()
544 * ? this
545 * : throw new ClassCastException()}.
546 *
547 * @param species vector species required for this mask
548 * @param <F> the boxed element type of the required species
549 * @return the same mask
550 * @throws ClassCastException if the species is wrong
551 * @see Vector#check(Class)
552 * @see Vector#check(VectorSpecies)
553 */
554 public abstract <F> VectorMask<F> check(VectorSpecies<F> species);
555
556 /**
557 * Returns a string representation of this mask, of the form
558 * {@code "Mask[T.TT...]"}, reporting the mask bit
559 * settings (as 'T' or '.' characters) in lane order.
560 *
561 * @return a string of the form {@code "Mask[T.TT...]"}
562 */
563 @Override
564 public final String toString() {
565 StringBuilder buf = new StringBuilder(length());
566 buf.append("Mask[");
567 for (boolean isSet : toArray()) {
568 buf.append(isSet ? 'T' : '.');
569 }
570 return buf.append(']').toString();
571 }
572
573 /**
574 * Indicates whether this mask is identical to some other object.
575 * Two masks are identical only if they have the same species
576 * and same source indexes, in the same order.
577 *
578 * @return whether this vector is identical to some other object
579 * @see #eq
580 */
581 @Override
582 public final boolean equals(Object obj) {
583 if (obj instanceof VectorMask) {
584 VectorMask<?> that = (VectorMask<?>) obj;
585 if (this.vectorSpecies().equals(that.vectorSpecies())) {
586 @SuppressWarnings("unchecked")
587 VectorMask<E> that2 = (VectorMask<E>) that;
588 return this.eq(that2).allTrue();
589 }
590 }
591 return false;
592 }
593
594 /**
595 * Returns a hash code value for the mask,
596 * based on the mask bit settings and the vector species.
597 *
598 * @return a hash code value for this mask
599 */
600 @Override
601 public final int hashCode() {
602 return Objects.hash(vectorSpecies(), Arrays.hashCode(toArray()));
603 }
604
605 // ==== JROSE NAME CHANGES ====
606
607 // TYPE CHANGED
608 // * toVector() return type is Vector<?> not Vector<E>
609 // ADDED
610 // * indexInRange(int,int,int) (SIMD range check, no overflow)
611 // * fromLong(VectorSpecies, long) (inverse of toLong)
612 // * check(VectorSpecies) (static type-safety check)
613 // * toString(), equals(Object), hashCode() (documented)
614 // * added <E> (not <?>) to toVector
615
616 }