用于大数的Crockford base 32编码- Java实现

n3schb8v  于 2023-06-28  发布在  Java
关注(0)|答案(3)|浏览(108)

我正在寻找一个Crockford Base32的Java实现,将与非常大的数字。下面是我正在处理的数字类型的示例:

0003019140802085400304608040952

我见过几个使用编码Long并解码为long的实现,但这比Long的最大值大得多。
我发现了这个实现,但它似乎给出了奇怪的结果:https://gist.githubusercontent.com/markov/5206312/raw/ba5ec8ff1ef894ac889d2d1fad359d51d91e8ab9/CrockfordBase32.java
上面的数字应该编码为2E1BZQDAGC4G6TTENZR,但是这个实现并没有给我任何接近这个的东西。

qv7cva1a

qv7cva1a1#

下面是Base 32的一般实现,其中包含Crockford字符集的实现。它有formatparse两个方法,应该是互补的。

/**
 * Parse and format base 32 numbers.
 *
 * Some of this may apply to almost any format but there's much that won't
 * such as allowing both uppercase and lowercase forms of each digit.
 *
 * See: http://en.wikipedia.org/wiki/Base32
 */
public class Base32 {
      // The character sets.
  // Like Hex but up to V
  private static final String base32HexCharacterSet = "0123456789ABCDEFGHIJKLMNOPQRSTUV";
  // Common alternative - avoids O/0, i/1 etc.
  private static final String base32CharacterSet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ234567";
  // Avoids vowels (and therefore real words)
  private static final String zBase32CharacterSet = "YBNDRFG8EJKMCPQXOT1UWISZA345H769";
  // Avoids o/0 confusion.
  private static final String crockfordCharacterSet = "0123456789ABCDEFGHJKMNPQRSTVWXYZ";
      // Known/published formats.
  // Uses the BigInteger formatter.
  public static final Base32 ordinary = new Base32();
  // A lot like the BigInteger formatter - but using my mechanism.
  public static final Base32 base32Hex = new Base32(base32HexCharacterSet);
  // The RFC 4648 Base32.
  public static final Base32 base32 = new Base32(base32CharacterSet);
  // Supposedly more natural than RFC 4648.
  public static final Base32 zBase32 = new Base32(zBase32CharacterSet);
  // Much like normal but recodes some similar looking characters to the same character.
  public static final Base32 crockfords = new Base32(crockfordCharacterSet, "O0", "o0", "L1", "l1", "I1", "i1");
  // Invalid character.
  private static final int Invalid = -1;
  // The radix - fixed at 32 bits.
  private static final int radix = 32;
  // The bits per digit - could use (int) (Math.log(radix) / Math.log(2))
  private static final int bitsPerDigit = 5;
  // The bits per byte.
  private static final int bitsPerByte = 8;
  // Translation table for each code.
  private final char[] formatTable;
  // Translation table for each character.
  private final int[] parseTable;

  // Constructor - Probably should be private but why restrict the user.
  public Base32() {
    // Empty tables makes us match BigInteger format so no formatting/parsing is required.
    formatTable = null;
    parseTable = null;
  }

  // Constructor with character set and optional extras :).
  protected Base32(String characterSet, String... extras) {
    // Check the character set against the radix.
    if (characterSet.length() != radix) {
      throw new NumberFormatException("Invalid character set. Must be " + radix + " long");
    }
    // Build the format table.
    formatTable = buildFormatTable(characterSet);
    // And the parse table.
    parseTable = buildParseTable(characterSet, extras);
  }

  // Build a format table from the character set.
  private char[] buildFormatTable(String characterSet) {
    // Start clear.
    char[] table = new char[radix];
    // Put each character from the character set in.
    for (int i = 0; i < radix; i++) {
      table[i] = characterSet.charAt(i);
    }
    return table;
  }

  private int[] buildParseTable(String characterSet, String... extras) {
    // Handle all characters up to and including 'z'.
    int[] table = new int['z' + 1];
    // By default invalid character.
    Arrays.fill(table, Invalid);
    // Lowercase and uppercase versions.
    String lc = characterSet.toLowerCase();
    String uc = characterSet.toUpperCase();
    // Walk through the character set.
    for (int i = 0; i < radix; i++) {
      char l = lc.charAt(i);
      char u = uc.charAt(i);
      // Something wrong if we've already filled this one in.
      if (table[l] == Invalid && table[u] == Invalid) {
        // Put both lowercase and uppercase forms in the table.
        table[l] = i;
        table[u] = i;
      } else {
        // Failed.
        throw new NumberFormatException("Invalid character set - duplicate found at position " + i);
      }
    }
    // Add extras.
    for (String pair : extras) {
      // Each Must be length 2.
      if (pair.length() == 2) {
        // From
        int f = pair.charAt(1);
        // To
        int t = pair.charAt(0);
        // Something wrong if we've already filled this one in or we are copying from one that is not filled in.
        if (table[f] != Invalid && table[t] == Invalid) {
          // EG "O0" means a capital oh should be treated as a zero.
          table[t] = table[f];
        } else {
          // Failed.
          throw new NumberFormatException("Invalid character set extra - copying from " + f + " to " + t);
        }
      } else {
        // Failed.
        throw new NumberFormatException("Invalid extra \"" + pair + "\" - should be 2 characters wide.");
      }

    }
    return table;
  }

  // Format a BigInteger.
  public String format(BigInteger n) {
    // Get its raw Radix32 string - in uppercase.
    String formatted = n.toString(radix).toUpperCase();
    // Further formatting through the format table?
    if (formatTable != null) {
      // Translate it.
      char[] translated = new char[formatted.length()];
      for (int i = 0; i < formatted.length(); i++) {
        // Use Character.digit to decode the digit value.
        int d = Character.digit(formatted.charAt(i), radix);
        // Translate to that.
        translated[i] = formatTable[d];
      }
      formatted = new String(translated);
    }
    return formatted;
  }

  // Parse a string.
  public BigInteger parse(String s) {
    BigInteger big;
    // Pass it through the parse table if present.
    if (parseTable != null) {
      // Digits in the number.
      int digits = s.length();
      // Total bits (+1 to avoid sign bit).
      int bits = digits * bitsPerDigit + 1;
      // Number of bytes.
      int bytes = (bits + bitsPerByte - 1) / bitsPerByte;
      // Bias bits to slide to the right to get the bottom bit rightmost (+1 to avoid sign bit).
      int bias = (bytes * bitsPerByte) - bits + 1;
      // Make my array.
      byte[] parsed = new byte[bytes];
      // Walk the string.
      for (int i = 0, bit = bias; i < digits; i++, bit += bitsPerDigit) {
        // The character.
        char c = s.charAt(i);
        // Must be in the parse table.
        if (c < parseTable.length) {
          // Roll in each digit value into the correct bits.
          int n = parseTable[c];
          // Special cases.
          switch (n) {
            case 0:
              // Nothing to do.
              break;

            default:
              // How far to shift it to line up with "bit"
              int shift = (bitsPerByte - bitsPerDigit - (bit % bitsPerByte));
              // Sorry about the name.
              int bite = bit / bitsPerByte;
              // +ve shift is left into this byte.
              if (shift >= 0) {
                // Slide left only.
                parsed[bite] |= n << shift;
              } else {
                // Split across this byte and the next.
                parsed[bite] |= n >>> -shift;
                // Slide right.
                parsed[bite + 1] |= n << (bitsPerByte + shift);
              }
              break;

            case Invalid:
              // Must be mapped to something.
              throw new NumberFormatException("Invalid character '" + c + "' at position " + i);
          }
        } else {
          // Failed.
          throw new NumberFormatException("Invalid character '" + c + "' at position " + i);
        }
      }
      // Grow the biginteger out of the byte array.
      big = new BigInteger(parsed);
    } else {
      // No parsing - it's ordinary.
      big = new BigInteger(s, radix);
    }
    return big;
  }

  // Check a string.
  public boolean good(String s) {
    boolean good = true;
    // Check each character.
    for (int i = 0; i < s.length() && good; i++) {
      // The character.
      char c = s.charAt(i);
      if (parseTable != null) {
        if (c < parseTable.length) {
          // Must be a valid character.
          good = parseTable[c] != Invalid;
        } else {
          // Out of range of the parse table.
          good = false;
        }
      } else {
        // Use Character.digit - returns -1 if not valid.
        good = Character.digit(c, radix) != -1;
      }
    }
    return good;
  }

  public static void main(String args[]) {
    Test.main(args);
  }

}

class Test {
  // For testing only.
  private static Random r = new Random();
  /*
   * A 95 bit number fits in a 12 byte binary with a bit to spare (sign bit).
   * A 95 bit number formats in base 32 to 19 digits exactly.
   * 
   * Other numbers of this type:
   * 15 bits 2 bytes 3 digits
   * 55 bits 7 bytes 11 digits
   * 95 bits 12 bytes 19 digits
   * 135 bits 17 bytes 27 digits
   * 175 bits 22 bytes 35 digits
   * 215 bits 27 bytes 43 digits
   * 255 bits 32 bytes 51 digits
   */
  private static final int testBits = 95;

  public static void main(String args[]) {
    test(new BigInteger("10"));
    test(new BigInteger("32"));
    test(new BigInteger("100"));
    BigInteger big = BigInteger.valueOf(0);
    for (int i = 0; i < 1000; i++, big = big.add(BigInteger.ONE)) {
      test(big);
    }
    for (int i = 0; i < 1000; i++) {
      test(new BigInteger(testBits, r));
    }
    testCrockfords();
  }

  private static void test(BigInteger i) {
    test(i, Base32.ordinary, "Ordinary");
    test(i, Base32.base32Hex, "Base32Hex");
    test(i, Base32.base32, "Base32");
    test(i, Base32.crockfords, "Crockfords");
    test(i, Base32.zBase32, "ZBase32");
  }

  private static void test(BigInteger i, Base32 f, String name) {
    test(i, f, f.format(i), name);
  }

  private static void test(BigInteger i, Base32 f, String formatted, String name) {
    BigInteger parsed = f.parse(formatted);
    boolean ok = parsed.equals(i) && f.good(formatted);
        //if (!ok) {
    // For debug - so we can trace the issue.
    BigInteger reParsed = f.parse(formatted);
    boolean good = f.good(formatted);
    System.out.println(i + " = " + f.format(i) + " in " + name + (ok ? " Ok" : " BAD!"));
    if (!ok) {
      System.out.println(reParsed + " != " + i);
    }
    //}
  }

  private static void testCrockfords() {
    /// Crockford uses extras.
    BigInteger anztenney = new BigInteger("0003019140802085400304608040952");
    String formatted = Base32.crockfords.format(anztenney);
    test(anztenney, Base32.crockfords, formatted, "Crockfords Test");
    for (int i = 0; i < 100; i++) {
      BigInteger b = BigInteger.valueOf(i);
      formatted = Base32.crockfords.format(b);
      test(b, Base32.crockfords, formatted, "Crockfords Test");
    }
    for (int i = 0; i < 1000; i++) {
      BigInteger b = new BigInteger(testBits, r);
      formatted = Base32.crockfords.format(b)
              .replace('0', 'O')
              .replace('1', 'l');
      test(b, Base32.crockfords, formatted, "Crockfords Test");
    }
  }

}

注意:请彻底测试-这从来没有被用在一个严重的方式,所以可能有错误。
测试输出行:

3019140802085400304608040952 = 2E1BZQDAGC4G6TTENZR in Crockfords Test Ok

所以你的数字似乎翻译得没错

3phpmpom

3phpmpom2#

使用来自@OldCurmudgeon的答案(这是我所问问题的正确答案),我做了一些修改,以允许从/到base 10的任何基本编码/解码。这不是为了性能而构建的,而是为了功能。

import java.math.BigInteger;
import java.util.Arrays;

public abstract class BaseXEncoder {

// Invalid character.
private static final int Invalid = -1;
// x in baseX encoding
private int radix = 32;
// Translation table for each code.
private final char[] formatTable;
// Translation table for each character.
private final int[] parseTable;

// Constructor with character set and optional extras :).
protected BaseXEncoder(int radix, String characterSet, String... extras) {
    this.radix = radix;

    // Check the character set against the radix.
    if (characterSet.length() != radix) {
        throw new NumberFormatException("Invalid character set. Must be " + radix + " long");
    }
    // Build the format table.
    formatTable = buildFormatTable(characterSet);
    // And the parse table.
    parseTable = buildParseTable(characterSet, extras);
}

public String encode(String numberValue) {
    return encodeBigInt(new BigInteger(numberValue));
}

public String decode(String encoded) {
    return decodeBigInt(encoded).toString();
}

// Format a BigInteger.
public String encodeBigInt(BigInteger n) {
    // Get its raw Radix32 string - in uppercase.
    String formatted = n.toString(radix).toUpperCase();
    // Further formatting through the format table?
    if (formatTable != null) {
        // Translate it.
        char[] translated = new char[formatted.length()];
        for (int i = 0; i < formatted.length(); i++) {
            // Use Character.digit to decode the digit value.
            int d = Character.digit(formatted.charAt(i), radix);
            // Translate to that.
            translated[i] = formatTable[d];
        }
        formatted = new String(translated);
    }
    return formatted;
}

// Parse a string.
public BigInteger decodeBigInt(String encoded) {
    BigInteger decoded = BigInteger.ZERO;
    // Pass it through the parse table if present.
    if (parseTable != null) {
        BigInteger RADIX = new BigInteger(Integer.toString(radix));
        // Digits in the number.
        int digits = encoded.length();
        // Walk the string.
        for (int i = 0; i < digits; i++) {
            // The character.
            char c = encoded.charAt(i);
            // Must be in the parse table.
            if (c < parseTable.length) {
                // Roll in each digit value into the correct bits.
                int n = parseTable[c];
                // Special cases.
                switch (n) {
                case Invalid:
                    // Must be mapped to something.
                    throw new NumberFormatException("Invalid character '" + c + "' at position " + i);

                default:
                    if(i==0) {//First character, do something special
                        decoded = new BigInteger(Integer.toString(n));
                    } else {
                        decoded = RADIX.multiply(decoded).add(new BigInteger(Integer.toString(n)));
                    }
                    break;

                }
            } else {
                // Failed.
                throw new NumberFormatException("Invalid character '" + c + "' at position " + i);
            }
        }
    } else {
        // No parsing - it's ordinary.
        decoded = new BigInteger(encoded, radix);
    }
    return decoded;
}

// Check a string.
public boolean good(String s) {
    boolean good = true;
    // Check each character.
    for (int i = 0; i < s.length() && good; i++) {
        // The character.
        char c = s.charAt(i);
        if (parseTable != null) {
            if (c < parseTable.length) {
                // Must be a valid character.
                good = parseTable[c] != Invalid;
            } else {
                // Out of range of the parse table.
                good = false;
            }
        } else {
            // Use Character.digit - returns -1 if not valid.
            good = Character.digit(c, radix) != -1;
        }
    }
    return good;
}

// Build a format table from the character set.
private char[] buildFormatTable(String characterSet) {
    // Start clear.
    char[] table = new char[radix];
    // Put each character from the character set in.
    for (int i = 0; i < radix; i++) {
        table[i] = characterSet.charAt(i);
    }
    return table;
}

private int[] buildParseTable(String characterSet, String... extras) {
    // Handle all characters up to and including 'z'.
    int[] table = new int['z' + 1];
    // By default invalid character.
    Arrays.fill(table, Invalid);
    // Lowercase and uppercase versions.
    String lc = characterSet.toLowerCase();
    String uc = characterSet.toUpperCase();
    // Walk through the character set.
    for (int i = 0; i < radix; i++) {
        char l = lc.charAt(i);
        char u = uc.charAt(i);
        // Something wrong if we've already filled this one in.
        if (table[l] == Invalid && table[u] == Invalid) {
            // Put both lowercase and uppercase forms in the table.
            table[l] = i;
            table[u] = i;
        } else {
            // Failed.
            throw new NumberFormatException("Invalid character set - duplicate found at position " + i);
        }
    }
    // Add extras.
    for (String pair : extras) {
        // Each Must be length 2.
        if (pair.length() == 2) {
            // From
            int f = pair.charAt(1);
            // To
            int t = pair.charAt(0);
            // Something wrong if we've already filled this one in or we are copying from one that is not filled in.
            if (table[f] != Invalid && table[t] == Invalid) {
                // EG "O0" means a capital oh should be treated as a zero.
                table[t] = table[f];
            } else {
                // Failed.
                throw new NumberFormatException("Invalid character set extra - copying from " + f + " to " + t);
            }
        } else {
            // Failed.
            throw new NumberFormatException("Invalid extra \"" + pair + "\" - should be 2 characters wide.");
        }

    }
    return table;
}

}
u4dcyp6a

u4dcyp6a3#

不是很难(这是闲聊,但你应该明白这个想法)unitsMax = 31,shiftBy = -5(对于基数32)

encodeInteger: anInt

    | int |

    int := anInt.

    ^ (String  streamContents: [ :str |
        [ str nextPut: (self tableAt: (int bitAnd: unitsMax)).
          (int := int  bitShift: shiftBy) = 0 ]
           
            whileFalse: [ ].
    ]) reverse

相关问题