1411f445053c39bd720d7bed66219f2f3fa4c2ee
[WebKit-https.git] / Source / WTF / wtf / text / Base64.cpp
1 /*
2    Copyright (C) 2000-2001 Dawit Alemayehu <adawit@kde.org>
3    Copyright (C) 2006 Alexey Proskuryakov <ap@webkit.org>
4    Copyright (C) 2007, 2008, 2013 Apple Inc. All rights reserved.
5    Copyright (C) 2010 Patrick Gansterer <paroga@paroga.com>
6
7    This program is free software; you can redistribute it and/or modify
8    it under the terms of the GNU Lesser General Public License (LGPL)
9    version 2 as published by the Free Software Foundation.
10
11    This program is distributed in the hope that it will be useful,
12    but WITHOUT ANY WARRANTY; without even the implied warranty of
13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14    GNU General Public License for more details.
15
16    You should have received a copy of the GNU Library General Public
17    License along with this program; if not, write to the Free Software
18    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
19
20    This code is based on the java implementation in HTTPClient
21    package by Ronald Tschalär Copyright (C) 1996-1999.
22 */
23
24 #include "config.h"
25 #include "Base64.h"
26
27 #include <limits.h>
28 #include <wtf/StringExtras.h>
29 #include <wtf/text/WTFString.h>
30
31 namespace WTF {
32
33 const char nonAlphabet = -1;
34
35 static const char base64EncMap[64] = {
36     0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48,
37     0x49, 0x4A, 0x4B, 0x4C, 0x4D, 0x4E, 0x4F, 0x50,
38     0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x57, 0x58,
39     0x59, 0x5A, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66,
40     0x67, 0x68, 0x69, 0x6A, 0x6B, 0x6C, 0x6D, 0x6E,
41     0x6F, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76,
42     0x77, 0x78, 0x79, 0x7A, 0x30, 0x31, 0x32, 0x33,
43     0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x2B, 0x2F
44 };
45
46 static const char base64DecMap[128] = {
47     nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet,
48     nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet,
49     nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet,
50     nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet,
51     nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet,
52     nonAlphabet, nonAlphabet, nonAlphabet, 0x3E, nonAlphabet, nonAlphabet, nonAlphabet, 0x3F,
53     0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x3A, 0x3B,
54     0x3C, 0x3D, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet,
55     nonAlphabet, 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06,
56     0x07, 0x08, 0x09, 0x0A, 0x0B, 0x0C, 0x0D, 0x0E,
57     0x0F, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16,
58     0x17, 0x18, 0x19, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet,
59     nonAlphabet, 0x1A, 0x1B, 0x1C, 0x1D, 0x1E, 0x1F, 0x20,
60     0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28,
61     0x29, 0x2A, 0x2B, 0x2C, 0x2D, 0x2E, 0x2F, 0x30,
62     0x31, 0x32, 0x33, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet
63 };
64
65 static const char base64URLEncMap[64] = {
66     0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48,
67     0x49, 0x4A, 0x4B, 0x4C, 0x4D, 0x4E, 0x4F, 0x50,
68     0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x57, 0x58,
69     0x59, 0x5A, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66,
70     0x67, 0x68, 0x69, 0x6A, 0x6B, 0x6C, 0x6D, 0x6E,
71     0x6F, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76,
72     0x77, 0x78, 0x79, 0x7A, 0x30, 0x31, 0x32, 0x33,
73     0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x2D, 0x5F
74 };
75
76 static const char base64URLDecMap[128] = {
77     nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet,
78     nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet,
79     nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet,
80     nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet,
81     nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet,
82     nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, 0x3E, nonAlphabet, nonAlphabet,
83     0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x3A, 0x3B,
84     0x3C, 0x3D, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet,
85     nonAlphabet, 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06,
86     0x07, 0x08, 0x09, 0x0A, 0x0B, 0x0C, 0x0D, 0x0E,
87     0x0F, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16,
88     0x17, 0x18, 0x19, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, 0x3F,
89     nonAlphabet, 0x1A, 0x1B, 0x1C, 0x1D, 0x1E, 0x1F, 0x20,
90     0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28,
91     0x29, 0x2A, 0x2B, 0x2C, 0x2D, 0x2E, 0x2F, 0x30,
92     0x31, 0x32, 0x33, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet, nonAlphabet
93 };
94
95 inline void base64EncodeInternal(const char* data, unsigned len, Vector<char>& out, Base64EncodePolicy policy, const char* encodeMap)
96 {
97     out.clear();
98     if (!len)
99         return;
100
101     // If the input string is pathologically large, just return nothing.
102     // Note: Keep this in sync with the "outLength" computation below.
103     // Rather than being perfectly precise, this is a bit conservative.
104     const unsigned maxInputBufferSize = UINT_MAX / 77 * 76 / 4 * 3 - 2;
105     if (len > maxInputBufferSize)
106         return;
107
108     unsigned sidx = 0;
109     unsigned didx = 0;
110
111     unsigned outLength = ((len + 2) / 3) * 4;
112
113     // Deal with the 76 character per line limit specified in RFC 2045.
114     bool insertLFs = (policy == Base64InsertLFs && outLength > 76);
115     if (insertLFs)
116         outLength += ((outLength - 1) / 76);
117
118     int count = 0;
119     out.grow(outLength);
120
121     // 3-byte to 4-byte conversion + 0-63 to ascii printable conversion
122     if (len > 1) {
123         while (sidx < len - 2) {
124             if (insertLFs) {
125                 if (count && !(count % 76))
126                     out[didx++] = '\n';
127                 count += 4;
128             }
129             out[didx++] = encodeMap[(data[sidx] >> 2) & 077];
130             out[didx++] = encodeMap[((data[sidx + 1] >> 4) & 017) | ((data[sidx] << 4) & 077)];
131             out[didx++] = encodeMap[((data[sidx + 2] >> 6) & 003) | ((data[sidx + 1] << 2) & 077)];
132             out[didx++] = encodeMap[data[sidx + 2] & 077];
133             sidx += 3;
134         }
135     }
136
137     if (sidx < len) {
138         if (insertLFs && (count > 0) && !(count % 76))
139            out[didx++] = '\n';
140
141         out[didx++] = encodeMap[(data[sidx] >> 2) & 077];
142         if (sidx < len - 1) {
143             out[didx++] = encodeMap[((data[sidx + 1] >> 4) & 017) | ((data[sidx] << 4) & 077)];
144             out[didx++] = encodeMap[(data[sidx + 1] << 2) & 077];
145         } else
146             out[didx++] = encodeMap[(data[sidx] << 4) & 077];
147     }
148
149     // Add padding
150     if (policy == Base64URLPolicy)
151         out.resize(didx);
152     else {
153         while (didx < out.size()) {
154             out[didx] = '=';
155             ++didx;
156         }
157     }
158 }
159
160 String base64Encode(const char* data, unsigned length, Base64EncodePolicy policy)
161 {
162     Vector<char> result;
163     base64EncodeInternal(data, length, result, policy, base64EncMap);
164     return String(result.data(), result.size());
165 }
166
167 void base64Encode(const char* data, unsigned len, Vector<char>& out, Base64EncodePolicy policy)
168 {
169     base64EncodeInternal(data, len, out, policy, base64EncMap);
170 }
171
172 String base64URLEncode(const char* data, unsigned length)
173 {
174     Vector<char> result;
175     base64EncodeInternal(data, length, result, Base64URLPolicy, base64URLEncMap);
176     return String(result.data(), result.size());
177 }
178
179 void base64URLEncode(const char* data, unsigned len, Vector<char>& out)
180 {
181     base64EncodeInternal(data, len, out, Base64URLPolicy, base64URLEncMap);
182 }
183
184 template<typename T>
185 static inline bool base64DecodeInternal(const T* data, unsigned length, Vector<char>& out, Base64DecodePolicy policy, const char* decodeMap)
186 {
187     out.clear();
188     if (!length)
189         return true;
190
191     out.grow(length);
192
193     unsigned equalsSignCount = 0;
194     unsigned outLength = 0;
195     for (unsigned idx = 0; idx < length; ++idx) {
196         unsigned ch = data[idx];
197         if (ch == '=') {
198             ++equalsSignCount;
199             // There should be no padding if length is a multiple of 4, and there
200             // should never be more than 2 padding characters.
201             if (policy == Base64FailOnInvalidCharacterOrExcessPadding && (length % 4 || equalsSignCount > 2))
202                 return false;
203         } else {
204             char decodedCharacter = decodeMap[ch];
205             if (decodedCharacter != nonAlphabet) {
206                 if (equalsSignCount)
207                     return false;
208                 out[outLength] = decodedCharacter;
209                 ++outLength;
210             } else if (policy == Base64FailOnInvalidCharacterOrExcessPadding || policy == Base64FailOnInvalidCharacter || (policy == Base64IgnoreWhitespace && !isSpaceOrNewline(ch)))
211                 return false;
212         }
213     }
214
215     if (!outLength)
216         return !equalsSignCount;
217
218     // Valid data is (n * 4 + [0,2,3]) characters long.
219     if ((outLength % 4) == 1)
220         return false;
221     
222     // 4-byte to 3-byte conversion
223     outLength -= (outLength + 3) / 4;
224     if (!outLength)
225         return false;
226
227     unsigned sidx = 0;
228     unsigned didx = 0;
229     if (outLength > 1) {
230         while (didx < outLength - 2) {
231             out[didx] = (((out[sidx] << 2) & 255) | ((out[sidx + 1] >> 4) & 003));
232             out[didx + 1] = (((out[sidx + 1] << 4) & 255) | ((out[sidx + 2] >> 2) & 017));
233             out[didx + 2] = (((out[sidx + 2] << 6) & 255) | (out[sidx + 3] & 077));
234             sidx += 4;
235             didx += 3;
236         }
237     }
238
239     if (didx < outLength)
240         out[didx] = (((out[sidx] << 2) & 255) | ((out[sidx + 1] >> 4) & 003));
241
242     if (++didx < outLength)
243         out[didx] = (((out[sidx + 1] << 4) & 255) | ((out[sidx + 2] >> 2) & 017));
244
245     if (outLength < out.size())
246         out.shrink(outLength);
247
248     return true;
249 }
250
251 bool base64Decode(const String& in, Vector<char>& out, Base64DecodePolicy policy)
252 {
253     return base64DecodeInternal<UChar>(in.characters(), in.length(), out, policy, base64DecMap);
254 }
255
256 bool base64Decode(const Vector<char>& in, Vector<char>& out, Base64DecodePolicy policy)
257 {
258     out.clear();
259
260     // If the input string is pathologically large, just return nothing.
261     if (in.size() > UINT_MAX)
262         return false;
263
264     return base64DecodeInternal<char>(in.data(), in.size(), out, policy, base64DecMap);
265 }
266
267 bool base64Decode(const char* data, unsigned len, Vector<char>& out, Base64DecodePolicy policy)
268 {
269     return base64DecodeInternal<char>(data, len, out, policy, base64DecMap);
270 }
271
272 bool base64URLDecode(const String& in, Vector<char>& out)
273 {
274     return base64DecodeInternal<UChar>(in.characters(), in.length(), out, Base64FailOnInvalidCharacter, base64URLDecMap);
275 }
276
277 bool base64URLDecode(const Vector<char>& in, Vector<char>& out)
278 {
279     out.clear();
280
281     // If the input string is pathologically large, just return nothing.
282     if (in.size() > UINT_MAX)
283         return false;
284
285     return base64DecodeInternal<char>(in.data(), in.size(), out, Base64FailOnInvalidCharacter, base64URLDecMap);
286 }
287
288 bool base64URLDecode(const char* data, unsigned len, Vector<char>& out)
289 {
290     return base64DecodeInternal<char>(data, len, out, Base64FailOnInvalidCharacter, base64URLDecMap);
291 }
292
293 } // namespace WTF