0

When i looked up the implementation of CharMatcher and notice a field WHITESPACE_MULTIPLIER=1682554634 , then i set this value to 1582554634 , running the testcase CharMatcherTest#testWhitespaceBreakingWhitespaceSubset, of course it failed.

After that I changed testWhitespaceBreakingWhitespaceSubset to only invoke WHITESPACE.apply((char)c) without assert, print the index in the method of WHITESPACE.matches

int index=(WHITESPACE_MULTIPLIER * c) >>> WHITESPACE_SHIFT)

finally found that index collided after changed the WHITESPACE_MULTIPLIER from 1682554634 to 1582554634

No doubt, 1682554634 is well designed , my question is how can I infer this "magic number"?`

Upon Martin Grajcar's proposal, I try to write the "magic number generator" as follows and worked :

char[] charsReq = WHITESPACE_TABLE.toCharArray();
Arrays.sort(charsReq);
OUTER:
for (int WHITESPACE_MULTIPLIER_WANTTED = 1682553701; WHITESPACE_MULTIPLIER_WANTTED <= 1682554834; WHITESPACE_MULTIPLIER_WANTTED++) {
    int matchCnt = 0;
    for (int c = 0; c <= Character.MAX_VALUE; c++) {
        int position = Arrays.binarySearch(charsReq, (char) c);
        char index = WHITESPACE_TABLE.charAt((WHITESPACE_MULTIPLIER_WANTTED * c) >>> WHITESPACE_SHIFT);
        if (position >= 0 && index == c) {
                matchCnt++;
        } else if (position < 0 && index != c) {
                matchCnt++;
        } else {
            continue OUTER;
        }
    }
    // all valid
    if ((matchCnt - 1) == (int) (Character.MAX_VALUE)) {
        System.out.println(WHITESPACE_MULTIPLIER_WANTTED);
    }
}

if changed the sequence of characters(swap \u2001 \u2002 position) in WHITESPACE_TABLE the algorithms has no solution (changed the loop end condition to Integer.MAX_VALUE).


as the IntMath.gcd implementation is refer to http://en.wikipedia.org/wiki/Binary_GCD_algorithm
my question is : where can i find the material of CharMatcher.WHITESPACE.match implementation?

  • I'm not sure about what you're asking. Is ist still unclear how the table has been generated? Your code is a bit too complicated for what I did. – maaartinus Feb 10 '14 at 04:13
  • wantted material of CharMatcher.WHITESPACE.match implementation。the code is to generate non conflict index random number – realvalkyrie Feb 10 '14 at 04:21
  • Explanation is here: **https://code.google.com/p/guava-libraries/wiki/StringsExplained#CharMatcher** The source code seems to be here: **https://code.google.com/p/guava-libraries/source/browse/guava/src/com/google/common/base/CharMatcher.java?r=f51d8fa33a59b6f817fabffbe729a8992359e15f** – Marichyasana Feb 10 '14 at 04:28
  • 1
    @Marichyasana: The OP wanted to know, *how* `WHITESPACE_MULTIPLIER` at line 1357 has been generated, and this is AFAIK not in Guava. – maaartinus Feb 10 '14 at 04:40
  • @Marichyasana thank you for provide the information – realvalkyrie Feb 10 '14 at 05:47

1 Answers1

2

I'm not sure if the generator still exists somewhere, but it can be recreated easily. The class Result contains the data used in the implementation of CharMatcher.WHITESPACE:

static class Result {
    private int shift;
    private int multiplier;
    private String table;
}

// No duplicates allowed.
private final String allMatchingString = "\u2002\r\u0085\u200A\u2005\u2000"
        + "\u2029\u000B\u2008\u2003\u205F\u1680"
        + "\u0009\u0020\u2006\u2001\u202F\u00A0\u000C\u2009"
        + "\u2004\u2028\n\u2007\u3000";

public Result generate(String allMatchingString) {
    final char[] allMatching = allMatchingString.toCharArray();
    final char filler = allMatching[allMatching.length - 1];
    final int shift = Integer.numberOfLeadingZeros(allMatching.length);
    final char[] table = new char[1 << (32 - shift)];
    OUTER: for (int i=0; i>=0; ++i) {
        final int multiplier = 123456789 * i; // Jumping a bit makes the search faster.
        Arrays.fill(table, filler);
        for (final char c : allMatching) {
            final int index = (multiplier * c) >>> shift;
            if (table[index] != filler) continue OUTER; // Conflict found.
            table[index] = c;
        }
        return new Result(shift, multiplier, new String(table));
    }
    return null; // No solution exists.
}

It generates a different multiplier, but this doesn't matter.

In case no solution for a given allMatchingString exists, you can decrement shift and try again.

maaartinus
  • 44,714
  • 32
  • 161
  • 320