Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-8225397

Integer value miscalculation in toString() method of BitSet

    Details

    • Subcomponent:
    • Resolved In Build:
      b25
    • CPU:
      generic
    • OS:
      generic
    • Verification:
      Verified

      Backports

        Description

        ADDITIONAL SYSTEM INFORMATION :
        Windows 10 Pro.
        Runtime information: Java(TM) SE Runtime Environment (build 1.8.0_172-b11).
        Code is also available in OpenJDK / jdk / jdk12
        view src/java.base/share/classes/java/util/BitSet.java

        A DESCRIPTION OF THE PROBLEM :
        StringBuilder instance creation in toString method of BitSet.
        StringBuilder b = new StringBuilder(6*numBits + 2)
        When we have more than 357913940 set bit(numBits) in BitSet then "6*numBits + 2" calculation exceeds the integer range and integer value spin it back to negative number.
        That leads to NegativeArraySizeException and BitSet value representation breaks.


        STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
        Set BitSet value more than 357913940.
        Call set() method more than 357913940 times, in every set() call, passed value in set() should be distinct.

        EXPECTED VERSUS ACTUAL BEHAVIOR :
        EXPECTED -
        Every set value in BitSet should be printed/represented by toString() method.
        ACTUAL -
        Exception in thread "main" java.lang.NegativeArraySizeException
        at java.lang.AbstractStringBuilder.<init>(AbstractStringBuilder.java:68)
        at java.lang.StringBuilder.<init>(StringBuilder.java:101)
        at java.util.BitSet.toString(BitSet.java:1186)
        at java.lang.String.valueOf(String.java:2994)
        at java.lang.StringBuilder.append(StringBuilder.java:131)

        ---------- BEGIN SOURCE ----------
        import java.util.BitSet;

        public class Eratosthenes {

            public BitSet sieveNumber(int n) {
                BitSet primeSet = new BitSet(n);

                for(int p =2; p*p <= n && p*p > 2; p++) {
                    if(primeSet.get(p) && p != 2) {
                        continue;
                    }

                    for(int i = p*2; i < n && i > 1; i = i + p) {
                        primeSet.set(i);
                    }
                }

                return primeSet;
            }


            public static void main(String[] arg) {
                Eratosthenes era = new Eratosthenes();
                BitSet primeSet = era.sieveNumber(2147483647);

                System.out.println("Cardinality : " + primeSet.cardinality());
                System.out.println("Prime set : " + primeSet);

                for(int i = 2; i < primeSet.length(); i++) {
                    if(!primeSet.get(i) && i > 2147483620) {
                        System.out.println(" " + i);
                    }
                }
            }
        }
        ---------- END SOURCE ----------

        CUSTOMER SUBMITTED WORKAROUND :
        Not right now.
        As of now only thought.
        Number 6 has been chosen carefully to represent index value of set bit but when numBits exceed 357913940, we can do segmentation of index value in multiple halves and then traverse individuals one by one.

        FREQUENCY : occasionally


          Attachments

            Issue Links

              Activity

                People

                • Assignee:
                  igerasim Ivan Gerasimov
                  Reporter:
                  webbuggrp Webbug Group
                • Votes:
                  0 Vote for this issue
                  Watchers:
                  4 Start watching this issue

                  Dates

                  • Created:
                    Updated:
                    Resolved: