RFR: 8349637: Integer.numberOfLeadingZeros outputs incorrectly in certain cases [v3]

[Tobias Hartmann]

On Wed, 12 Feb 2025 19:45:34 GMT, Jasmine Karthikeyan <jkarthikeyan at openjdk.org> wrote:

>> Hi all,
>> This is a fix for a miscompile in the AVX2 implementation of `CountLeadingZerosV` for int types. Currently, the implementation turns ints into floats, in order to calculating the leading zeros based on the exponent part of the float. Unfortunately, floats can only accurately represent integers up to 2^24. After that, multiple integer values can map onto the same floating point value. The issue manifests when an int is converted to a floating point representation that is higher than it, crossing a bit boundary. As an example, `(float)0x01FFFFFF == (float)0x02000000`, but `lzcnt(0x01FFFFFF) == 7` and `lzcnt(0x02000000) == 6`. The values are incorrectly rounded up.
>> 
>> This patch fixes the issue by masking the input in the cases where it is larger than 2^24, to set the low bits to 0. Removing these bits prevents the accidental rounding behavior. I've added these cases to`TestNumberOfContinuousZeros`, and removed the set random seed so that it can produce random inputs to test with.
>> 
>> Reviews would be appreciated!
>
> Jasmine Karthikeyan has updated the pull request incrementally with one additional commit since the last revision:
> 
>   Improve explanation of logic

There is at least one additional bug here. Running this test fails even with the fix:


/*
 * Copyright (c) 2025, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */

// Run with java -Xbatch -XX:-TieredCompilation TestShort.java

public class TestShort {

    public static void test() {
        short[] vals = new short[1024];
        short[] results = new short[1024];
        for (int i = 0; i < 1024; ++i) {
            vals[i] = 12;
        }
        for (int i = 0; i < 1024; ++i) {
            results[i] = (short)Integer.numberOfLeadingZeros(vals[i]);
        }
        for (int i = 0; i < 1024; ++i) {
            if (results[i] != 28) throw new RuntimeException("Wrong result");
        }
    }

    public static void main(String[] args) {
        for (int i = 0; i < 10_000; ++i) {
            test();
        }
    }
}


I found this with another test that I wrote to perform an exhaustive search over all the possible inputs with <= int-size. Will share that one later.

-------------

PR Comment: https://git.openjdk.org/jdk/pull/23579#issuecomment-2659179429