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
31namespace WTF {
32
33const char nonAlphabet = -1;
34
35static 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
46static 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
65static 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
76static 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
95static inline void base64EncodeInternal(const char* data, unsigned len, Vector<char>& out, Base64EncodePolicy policy, const char (&encodeMap)[64])
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
160String base64Encode(const void* data, unsigned length, Base64EncodePolicy policy)
161{
162    Vector<char> result;
163    base64EncodeInternal(static_cast<const char*>(data), length, result, policy, base64EncMap);
164    return String(result.data(), result.size());
165}
166
167void base64Encode(const void* data, unsigned len, Vector<char>& out, Base64EncodePolicy policy)
168{
169    base64EncodeInternal(static_cast<const char*>(data), len, out, policy, base64EncMap);
170}
171
172String base64URLEncode(const void* data, unsigned length)
173{
174    Vector<char> result;
175    base64EncodeInternal(static_cast<const char*>(data), length, result, Base64URLPolicy, base64URLEncMap);
176    return String(result.data(), result.size());
177}
178
179void base64URLEncode(const void* data, unsigned len, Vector<char>& out)
180{
181    base64EncodeInternal(static_cast<const char*>(data), len, out, Base64URLPolicy, base64URLEncMap);
182}
183
184template<typename T>
185static inline bool base64DecodeInternal(const T* data, unsigned length, Vector<char>& out, Base64DecodePolicy policy, const char (&decodeMap)[128])
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 = ch < WTF_ARRAY_LENGTH(decodeMap) ? decodeMap[ch] : nonAlphabet;
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
251bool base64Decode(const String& in, SignedOrUnsignedCharVectorAdapter out, Base64DecodePolicy policy)
252{
253    unsigned length = in.length();
254    if (!length || in.is8Bit())
255        return base64DecodeInternal(in.characters8(), length, out, policy, base64DecMap);
256    return base64DecodeInternal(in.characters16(), length, out, policy, base64DecMap);
257}
258
259bool base64Decode(const Vector<char>& in, SignedOrUnsignedCharVectorAdapter out, Base64DecodePolicy policy)
260{
261    out.clear();
262
263    // If the input string is pathologically large, just return nothing.
264    if (in.size() > UINT_MAX)
265        return false;
266
267    return base64DecodeInternal(reinterpret_cast<const LChar*>(in.data()), in.size(), out, policy, base64DecMap);
268}
269
270bool base64Decode(const char* data, unsigned len, SignedOrUnsignedCharVectorAdapter out, Base64DecodePolicy policy)
271{
272    return base64DecodeInternal(reinterpret_cast<const LChar*>(data), len, out, policy, base64DecMap);
273}
274
275bool base64URLDecode(const String& in, SignedOrUnsignedCharVectorAdapter out)
276{
277    unsigned length = in.length();
278    if (!length || in.is8Bit())
279        return base64DecodeInternal(in.characters8(), length, out, Base64FailOnInvalidCharacter, base64URLDecMap);
280    return base64DecodeInternal(in.characters16(), length, out, Base64FailOnInvalidCharacter, base64URLDecMap);
281}
282
283bool base64URLDecode(const Vector<char>& in, SignedOrUnsignedCharVectorAdapter out)
284{
285    out.clear();
286
287    // If the input string is pathologically large, just return nothing.
288    if (in.size() > UINT_MAX)
289        return false;
290
291    return base64DecodeInternal(reinterpret_cast<const LChar*>(in.data()), in.size(), out, Base64FailOnInvalidCharacter, base64URLDecMap);
292}
293
294bool base64URLDecode(const char* data, unsigned len, SignedOrUnsignedCharVectorAdapter out)
295{
296    return base64DecodeInternal(reinterpret_cast<const LChar*>(data), len, out, Base64FailOnInvalidCharacter, base64URLDecMap);
297}
298
299} // namespace WTF
300