Pileus Git - ~andy/freeotp/blob - src/com/google/android/apps/authenticator/Base32String.java

   1 /*
   2  * Copyright 2009 Google Inc. All Rights Reserved.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 package com.google.android.apps.authenticator;
  18
  19 import java.util.HashMap;
  20 import java.util.Locale;
  21
  22 /**
  23  * Encodes arbitrary byte arrays as case-insensitive base-32 strings.
  24  * <p>
  25  * The implementation is slightly different than in RFC 4648. During encoding,
  26  * padding is not added, and during decoding the last incomplete chunk is not
  27  * taken into account. The result is that multiple strings decode to the same
  28  * byte array, for example, string of sixteen 7s ("7...7") and seventeen 7s both
  29  * decode to the same byte array.
  30  * TODO(sarvar): Revisit this encoding and whether this ambiguity needs fixing.
  31  *
  32  * @author sweis@google.com (Steve Weis)
  33  * @author Neal Gafter
  34  */
  35 public class Base32String {
  36   // singleton
  37
  38   private static final Base32String INSTANCE =
  39     new Base32String("ABCDEFGHIJKLMNOPQRSTUVWXYZ234567"); // RFC 4648/3548
  40
  41   static Base32String getInstance() {
  42     return INSTANCE;
  43   }
  44
  45   // 32 alpha-numeric characters.
  46   private String ALPHABET;
  47   private char[] DIGITS;
  48   private int MASK;
  49   private int SHIFT;
  50   private HashMap<Character, Integer> CHAR_MAP;
  51
  52   static final String SEPARATOR = "-";
  53
  54   protected Base32String(String alphabet) {
  55     this.ALPHABET = alphabet;
  56     DIGITS = ALPHABET.toCharArray();
  57     MASK = DIGITS.length - 1;
  58     SHIFT = Integer.numberOfTrailingZeros(DIGITS.length);
  59     CHAR_MAP = new HashMap<Character, Integer>();
  60     for (int i = 0; i < DIGITS.length; i++) {
  61       CHAR_MAP.put(DIGITS[i], i);
  62     }
  63   }
  64
  65   public static byte[] decode(String encoded) throws DecodingException {
  66     return getInstance().decodeInternal(encoded);
  67   }
  68
  69   protected byte[] decodeInternal(String encoded) throws DecodingException {
  70     // Remove whitespace and separators
  71     encoded = encoded.trim().replaceAll(SEPARATOR, "").replaceAll(" ", "");
  72
  73     // Remove padding. Note: the padding is used as hint to determine how many
  74     // bits to decode from the last incomplete chunk (which is commented out
  75     // below, so this may have been wrong to start with).
  76     encoded = encoded.replaceFirst("[=]*$", "");
  77
  78     // Canonicalize to all upper case
  79     encoded = encoded.toUpperCase(Locale.US);
  80     if (encoded.length() == 0) {
  81       return new byte[0];
  82     }
  83     int encodedLength = encoded.length();
  84     int outLength = encodedLength * SHIFT / 8;
  85     byte[] result = new byte[outLength];
  86     int buffer = 0;
  87     int next = 0;
  88     int bitsLeft = 0;
  89     for (char c : encoded.toCharArray()) {
  90       if (!CHAR_MAP.containsKey(c)) {
  91         throw new DecodingException("Illegal character: " + c);
  92       }
  93       buffer <<= SHIFT;
  94       buffer |= CHAR_MAP.get(c) & MASK;
  95       bitsLeft += SHIFT;
  96       if (bitsLeft >= 8) {
  97         result[next++] = (byte) (buffer >> (bitsLeft - 8));
  98         bitsLeft -= 8;
  99       }
 100     }
 101     // We'll ignore leftover bits for now.
 102     //
 103     // if (next != outLength || bitsLeft >= SHIFT) {
 104     //  throw new DecodingException("Bits left: " + bitsLeft);
 105     // }
 106     return result;
 107   }
 108
 109   public static String encode(byte[] data) {
 110     return getInstance().encodeInternal(data);
 111   }
 112
 113   protected String encodeInternal(byte[] data) {
 114     if (data.length == 0) {
 115       return "";
 116     }
 117
 118     // SHIFT is the number of bits per output character, so the length of the
 119     // output is the length of the input multiplied by 8/SHIFT, rounded up.
 120     if (data.length >= (1 << 28)) {
 121       // The computation below will fail, so don't do it.
 122       throw new IllegalArgumentException();
 123     }
 124
 125     int outputLength = (data.length * 8 + SHIFT - 1) / SHIFT;
 126     StringBuilder result = new StringBuilder(outputLength);
 127
 128     int buffer = data[0];
 129     int next = 1;
 130     int bitsLeft = 8;
 131     while (bitsLeft > 0 || next < data.length) {
 132       if (bitsLeft < SHIFT) {
 133         if (next < data.length) {
 134           buffer <<= 8;
 135           buffer |= (data[next++] & 0xff);
 136           bitsLeft += 8;
 137         } else {
 138           int pad = SHIFT - bitsLeft;
 139           buffer <<= pad;
 140           bitsLeft += pad;
 141         }
 142       }
 143       int index = MASK & (buffer >> (bitsLeft - SHIFT));
 144       bitsLeft -= SHIFT;
 145       result.append(DIGITS[index]);
 146     }
 147     return result.toString();
 148   }
 149
 150   @Override
 151   // enforce that this class is a singleton
 152   public Object clone() throws CloneNotSupportedException {
 153     throw new CloneNotSupportedException();
 154   }
 155
 156   public static class DecodingException extends Exception {
 157     public DecodingException(String message) {
 158       super(message);
 159     }
 160   }
 161 }