Create parser pool interface and move current pool to an implementation of this inter...
[java-idp.git] / src / edu / internet2 / middleware / shibboleth / utils / Base32.java
1 /* (PD) 2001 The Bitzi Corporation
2  * Please see http://bitzi.com/publicdomain for more info.
3  *
4  * Base32.java
5  *
6  */
7
8 package edu.internet2.middleware.shibboleth.utils;
9
10 /**
11  * Base32 - encodes and decodes 'Canonical' Base32
12  *
13  * @author  Robert Kaye & Gordon Mohr
14  */
15 public class Base32 {
16
17         /* lookup table used to encode() groups of 5 bits of data */
18         private static final String base32Chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ234567";
19
20         /* lookup table used to decode() characters in Base32 strings */
21         private static final byte[] base32Lookup =
22                 { 26,27,28,29,30,31,-1,-1,-1,-1,-1,-1,-1,-1,       //   23456789:;<=>?
23                   -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14, // @ABCDEFGHIJKLMNO
24                   15,16,17,18,19,20,21,22,23,24,25,-1,-1,-1,-1,-1, // PQRSTUVWXYZ[\]^_
25                   -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14, // `abcdefghijklmno
26                   15,16,17,18,19,20,21,22,23,24,25                 // pqrstuvwxyz
27                 };
28
29         /* Messsages for Illegal Parameter Exceptions in decode() */
30         private static final String errorCanonicalLength = "non canonical Base32 string length";
31         private static final String errorCanonicalEnd    = "non canonical bits at end of Base32 string";
32         private static final String errorInvalidChar     = "invalid character in Base32 string";
33
34         /**
35          * Encode an array of binary bytes into a Base32 string.
36          * Should not fail (the only possible exception is that the
37          * returned string cannot be allocated in memory)
38          */    
39         static public String encode(final byte[] bytes) {
40     
41                 StringBuffer base32 = new StringBuffer((bytes.length * 8 + 4) / 5);
42                 int currByte, digit, i = 0;
43
44                 while (i < bytes.length) {
45                 
46                         // INVARIANTS FOR EACH STEP n in [0..5[; digit in [0..31[; 
47                         // The remaining n bits are already aligned on top positions
48                         // of the 5 least bits of digit, the other bits are 0.
49                         
50                         // STEP n = 0; insert new 5 bits, leave 3 bits
51                         currByte = bytes[i++] & 255;
52                         base32.append(base32Chars.charAt(currByte >> 3));
53                         digit = (currByte & 7) << 2;
54                         if (i >= bytes.length) { // put the last 3 bits
55                                 base32.append(base32Chars.charAt(digit));
56                                 break;
57                         }
58             
59
60                         // STEP n = 3: insert 2 new bits, then 5 bits, leave 1 bit
61                         currByte = bytes[i++] & 255;
62                         base32.append(base32Chars.charAt(digit | (currByte >> 6)));
63                         base32.append(base32Chars.charAt((currByte >> 1) & 31));
64                         digit = (currByte & 1) << 4;
65                         if (i >= bytes.length) { // put the last 1 bit
66                                 base32.append(base32Chars.charAt(digit));
67                                 break;
68                         }
69
70                         // STEP n = 1: insert 4 new bits, leave 4 bit
71                         currByte = bytes[i++] & 255;
72                         base32.append(base32Chars.charAt(digit | (currByte >> 4)));
73                         digit = (currByte & 15) << 1;
74                         if (i >= bytes.length) { // put the last 4 bits
75                                 base32.append(base32Chars.charAt(digit));
76                                 break;
77                         }
78
79                         // STEP n = 4: insert 1 new bit, then 5 bits, leave 2 bits
80                         currByte = bytes[i++] & 255;
81                         base32.append(base32Chars.charAt(digit | (currByte >> 7)));
82                         base32.append(base32Chars.charAt((currByte >> 2) & 31));
83                         digit = (currByte & 3) << 3;
84                         if (i >= bytes.length) { // put the last 2 bits
85                                 base32.append(base32Chars.charAt(digit));
86                                 break;
87                         }
88
89                         // STEP n = 2: insert 3 new bits, then 5 bits, leave 0 bit
90                         currByte = bytes[i++] & 255;
91                         base32.append(base32Chars.charAt(digit | (currByte >> 5)));
92                         base32.append(base32Chars.charAt(currByte & 31));
93                         //// This point is reached for bytes.length multiple of 5
94                 }
95         
96                 return base32.toString();
97         }
98
99    
100         /**
101          * Decode a Base32 string into an array of binary bytes.
102          * May fail if the parameter is a non canonical Base32 string   
103          * (the only other possible exception is that the
104          * returned array cannot be allocated in memory)
105          */    
106         static public byte[] decode(final String base32) throws IllegalArgumentException {
107
108         // Note that the code below detects could detect non canonical
109         // Base32 length within the loop. However canonical Base32 length
110         // can be tested before entering the loop.
111         // A canonical Base32 length modulo 8 cannot be:
112         // 1 (aborts discarding 5 bits at STEP n=0 which produces no byte),
113         // 3 (aborts discarding 7 bits at STEP n=2 which produces no byte),
114         // 6 (aborts discarding 6 bits at STEP n=1 which produces no byte)
115         // So these tests could be avoided within the loop.
116         switch (base32.length() % 8) { // test the length of last subblock
117
118                 case 1: //  5 bits in subblock:  0 useful bits but 5 discarded
119                 case 3: // 15 bits in subblock:  8 useful bits but 7 discarded
120                 case 6: // 30 bits in subblock: 24 useful bits but 6 discarded
121           
122                 throw new IllegalArgumentException(errorCanonicalLength);
123         }
124
125         byte[] bytes = new byte[base32.length() * 5 / 8];
126         int offset = 0, i = 0, lookup;
127         byte nextByte, digit;
128
129         // Also the code below does test that other discarded bits
130         // (1 to 4 bits at end) are effectively 0.
131         while (i < base32.length()) {
132                 // Read the 1st char in a 8-chars subblock
133                 // check that chars are not outside the lookup table and valid
134                 lookup = base32.charAt(i++) - '2';
135                 if (lookup < 0 || lookup >= base32Lookup.length) {
136                         throw new IllegalArgumentException(errorInvalidChar);
137                 }
138                 digit = base32Lookup[lookup];
139                 if (digit == -1) {
140                         throw new IllegalArgumentException(errorInvalidChar);
141                 }
142
143                 // STEP n = 0: leave 5 bits
144                 nextByte = (byte)(digit << 3);
145                 // Assert(i < base32.length) // tested before loop
146                 // Read the 2nd char in a 8-chars subblock
147                 // Check that chars are not outside the lookup table and valid
148                 lookup = base32.charAt(i++) - '2';
149                 if (lookup < 0 || lookup >= base32Lookup.length) {
150                         throw new IllegalArgumentException(errorInvalidChar);
151                 }
152                 digit = base32Lookup[lookup];
153                 if (digit == -1) {
154                         throw new IllegalArgumentException(errorInvalidChar);
155                 }
156
157                 // STEP n = 5: insert 3 bits, leave 2 bits
158                 bytes[offset++] = (byte)(nextByte | (digit >> 2));
159                 nextByte = (byte)((digit & 3) << 6);
160                 if (i >= base32.length()) {
161                         if (nextByte != (byte)0) {
162                                 throw new IllegalArgumentException(errorCanonicalEnd);
163                         }
164                         break; // discard the remaining 2 bits
165                 }
166
167                 // Read the 3rd char in a 8-chars subblock
168                 // Check that chars are not outside the lookup table and valid
169                 lookup = base32.charAt(i++) - '2';
170                 if (lookup < 0 || lookup >= base32Lookup.length) {
171                         throw new IllegalArgumentException(errorInvalidChar);
172                 }
173                 digit = base32Lookup[lookup];
174                 if (digit == -1) {
175                         throw new IllegalArgumentException(errorInvalidChar);
176                 }
177
178                 // STEP n = 2: leave 7 bits
179                 nextByte |= (byte)(digit << 1);
180                 // Assert(i < base32.length) // tested before loop
181                 // Read the 4th char in a 8-chars subblock
182                 // Check that chars are not outside the lookup table and valid
183                 lookup = base32.charAt(i++) - '2';
184                 if (lookup < 0 || lookup >= base32Lookup.length) {
185                         throw new IllegalArgumentException(errorInvalidChar);
186                 }
187                 digit = base32Lookup[lookup];
188                 if (digit == -1) {
189                         throw new IllegalArgumentException(errorInvalidChar);
190                 }
191
192                 // STEP n = 7: insert 1 bit, leave 4 bits
193                 bytes[offset++] = (byte)(nextByte | (digit >> 4));
194                 nextByte = (byte)((digit & 15) << 4);
195                 if (i >= base32.length()) {
196                         if (nextByte != (byte)0) {
197                                 throw new IllegalArgumentException(errorCanonicalEnd);
198                         }
199                         break; // discard the remaining 4 bits
200                 }
201
202                 // Read the 5th char in a 8-chars subblock
203                 // Assert that chars are not outside the lookup table and valid
204                 lookup = base32.charAt(i++) - '2';
205                 if (lookup < 0 || lookup >= base32Lookup.length) {
206                         throw new IllegalArgumentException(errorInvalidChar);
207                 }
208                 digit = base32Lookup[lookup];
209                 if (digit == -1) {
210                         throw new IllegalArgumentException(errorInvalidChar);
211                 }
212
213                 // STEP n = 4: insert 4 bits, leave 1 bit
214                 bytes[offset++] = (byte)(nextByte | (digit >> 1));
215                 nextByte = (byte)((digit & 1) << 7);
216                 if (i >= base32.length()) {
217                         if (nextByte != (byte)0) {
218                                 throw new IllegalArgumentException(errorCanonicalEnd);
219                         }
220                         break; // discard the remaining 1 bit
221                 }
222
223                 // Read the 6th char in a 8-chars subblock
224                 // Check that chars are not outside the lookup table and valid
225                 lookup = base32.charAt(i++) - '2';
226                 if (lookup < 0 || lookup >= base32Lookup.length) {
227                         throw new IllegalArgumentException(errorInvalidChar);
228                 }
229                 digit = base32Lookup[lookup];
230                 if (digit == -1) {
231                         throw new IllegalArgumentException(errorInvalidChar);
232                 }
233
234                 // STEP n = 1: leave 6 bits
235                 nextByte |= (byte)(digit << 2);
236                 // Assert(i < base32.length) // tested before loop
237                 // Read the 7th char in a 8-chars subblock
238                 // Check that chars are not outside the lookup table and valid
239                 lookup = base32.charAt(i++) - '2';
240                 if (lookup < 0 || lookup >= base32Lookup.length) {
241                         throw new IllegalArgumentException(errorInvalidChar);
242                 }
243                 digit = base32Lookup[lookup];
244                 if (digit == -1) {
245                         throw new IllegalArgumentException(errorInvalidChar);
246                 }
247
248                 // STEP n = 6: insert 2 bits, leave 3 bits
249                 bytes[offset++] = (byte)(nextByte | (digit >> 3));
250                 nextByte = (byte)((digit & 7) << 5);
251                 if (i >= base32.length()) {
252                         if (nextByte != (byte)0) {
253                                 throw new IllegalArgumentException(errorCanonicalEnd);
254                         }
255                         break; // discard the remaining 3 bits
256                 }
257         
258                 // Read the 8th char in a 8-chars subblock
259                 // Check that chars are not outside the lookup table and valid
260                 lookup = base32.charAt(i++) - '2';
261                 if (lookup < 0 || lookup >= base32Lookup.length) {
262                         throw new IllegalArgumentException(errorInvalidChar);
263                 }
264                 digit = base32Lookup[lookup];
265                 if (digit == -1) {
266                         throw new IllegalArgumentException(errorInvalidChar);
267                 }
268
269                 // STEP n = 3: insert 5 bits, leave 0 bit
270                 bytes[offset++] = (byte)(nextByte | digit);
271                 // possible end of string here with no trailing bits
272         }
273
274                 // On loop exit, discard trialing n bits.
275                 return bytes;
276         }
277 }
278