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 }